Captain's Log: CIS 505/705, Fall 2016
(Introduction To) Programming Languages

Aug 22 (Mon) & Aug 24 (Wed)

Class canceled (instructor out of town)

1: Aug 26 (Fri)

Introduction to course:

• go through syllabus
• compare the functional and the imperative paradigms (the slide set Introduction.pdf)
• briefly mention SML (Standard ML), to be used in the first third of the course

2: Aug 29 (Mon)

Cover the basic features of SML (the slide set Basics.pdf).

3: Aug 31 (Wed)

• Cover Functions: how to define and use functions (which are first-class citizens in SML!)
• Post Lab 1, due Friday evening.

4: Sep 2 (Fri)

• Finish Functions, discussing how to compose two functions.
• Embark on ListFunctions (first 10 slides), with guidelines for how to write functions operating on lists.
• Lab 1 due at 11pm.

Sep 5 (Mon)

University Holiday (Labor Day)

5: Sep 7 (Wed)

• Continue ListFunctions, introducing the map and filter and fold templates.
• Motivate the recently posted Programming Assignment 1.

6: Sep 9 (Fri)

• Continue ListFunctions:
  • elaborate on the foldr/foldl templates;
  • discuss how to represent sets in SML (where not all types allow test for equality).
• Discuss the given (recently updated) skeleton for Programming Assignment 1, and how to extend it.
• Work on a "Minilab" on writing a function to convert strings of digits into integers.

7: Sep 12 (Mon)

• Finish ListFunctions, on how to represent a dictionary that associates keys with values:
  • either as a list of pairs, with each pair a key and a value,
  • or as a function (cf. the way registers are represented in the skeleton interpreter for HW1).
• Continue discussing HW1.
• Embark on Recursion: we
  • illustrate how the stack is used to evaluate a recursive function, and
  • show how a badly written function may be infeasible to evaluate on large input.

8: Sep 14 (Wed)

• Continue Recursion, with guidelines for how to write efficient recursive functions;
  the key is tail recursion (nothing needs to be done after recursive call).
• Quiz 1 on using the various templates (map, filter, fold) for list functions.

9: Sep 16 (Fri)

• See a few more examples of tail recursion.
• Introduce DataTypes, on how users may define their own types
  • which may be parametrized, and/or recursive
• Further discuss Programming Assignment 1, due tonight.

10: Sep 19 (Mon)

• Finish DataTypes, whose values are handled by case patterns.
• Embark on TreeFunctions; the structure of trees direct the structure of functions operating on them.
• Post Lab 2, due Wednesday evening.

11: Sep 21 (Wed)

• Finish TreeFunctions, with more examples on how to write functions that operate on inductively defined datatypes.
• Discuss model solutions for Programming Assignment 1.

Lab 2 due at 11pm.

12: Sep 23 (Fri)

Cover Exceptions, convenient to handle irregular situations;

• show how to raise and handle (parametrized) exceptions
• illustrate the power of exceptions by a non-trivial example.

13: Sep 26 (Mon)

• Discuss solutions to Lab 2
• Discuss various ways to compute the "fringe" of a tree
• Discuss last year's midterm on SML

14: Sep 28 (Wed)

Exam 1

15: Sep 30 (Fri)

• Present Programming Assignment 2, posted tonight.
• Give an overview of the stages involved in implementing a programming language
  (as elaborated on in the slides PLstages).

16: Oct 3 (Mon)

Discuss the skeleton interpreter for Programming Assignment 2.

17: Oct 5 (Wed)

Further discuss Programming Assignment 2:

• indicate the priority of the various tasks
• elaborate on the tasks with the highest priority.

Discuss the first stages of implementing a programming language:

• Lexical analysis which converts a string of characters into a list of tokens
• Grammars which give structure to the input but may be ambiguous.

18: Oct 7 (Fri)

Discuss remaining stages of implementing a programming language:

• how to resolve ambiguity, so as to write a (top-down) parser
  • that has the right operator precedence
  • but the wrong associativity (can be fixed by a bottom-up parser).
• how to convert into an abstract syntax tree

Programming Assignment 2 due this weekend.

19: Oct 10 (Mon)

• Hand back, and discuss, graded Exam 1.
• Wrap up PLstages, in particular look at the parser given for Programming Assignment 2.

20: Oct 12 (Wed)

Show how to encode lazy evaluation in SML (the slides Lazy)

• illustrate how various lists functions can be rewritten to work on lazy lists.

Quiz 2 on constructing parse trees.

21: Oct 14 (Fri)

• Show how lazy evaluation may allow very succinct and elegant solutions to certain problems.
• Start discussing how to implement first-order functional languages.

22: Oct 17 (Mon)

Discuss how to implement first-order functional languages (the slides InterpretFunctionsFO):

• as in Chapter 5 of the textbook, we
  • show an implementation that uses substitutions
  • mention the difference between call-by-name and call-by-value
• as in Chapter 6 of the textbook, we
  • show an implementation that uses environments
  • mention the difference between dynamic and static scope.

23: Oct 19 (Wed)

As in Chapter 7 of the textbook, we interpret higher order functions (the slides InterpretHigherOrder)

• where functions are promoted to "first-class citizens"
• by means of closures.

Briefly present Programming Assignment 3.

24: Oct 21 (Fri)

• Further introduce Programming Assignment 3.
• Embark on a brief introduction (the slides Racket) to the Racket language (more details to be found in this guide).

25: Oct 24 (Mon)

• Finish the brief introduction to the Racket language
• Discuss the skeleton interpreter provided for Assignment 3
• Post Racket Lab 1, due Wednesday evening.

26: Oct 26 (Wed)

Embark on Chapter 8 of the textbook, on mutable structures (the slides InterpretMutations)

• We consider a higher-order functional language extended with boxes and sequential composition
• We argue that environments alone are not sufficient to record mutations properly.

Briefly discuss Racket Lab 1, due at 11pm.

27: Oct 28 (Fri)

We extend the interpreter for a functional language to handle mutations, by using

• not just environments
• but also stores.

We go through the various clauses (as in Section 8.1.7 of the textbook) with focus on

• how stores propagate in a different way than environments
• the treatment of boxes.

Discuss model solutions for Racket Lab 1.
Programming Assignment 3 due this weekend.

28: Oct 31 (Mon)

Prepare for Exam 2:

• discuss questions from last year's exam sets
• discuss solutions for Programming Assignment 3.

29: Nov 2 (Wed)

Exam 2

30: Nov 4 (Fri)

Introduce Programming Assignment 4, on writing an interpreter for an object-oriented functional language:

• present examples of how to interpret programs in the language
• give an overview of the skeleton interpreter.

31: Nov 7 (Mon)

• Finish the slides InterpretMutations
• Further discuss the skeleton interpreter for Assignment 4

32: Nov 9 (Wed)

To prepare for Prolog (the 3rd part of the course), start on a crash course in logic:

• cover propositional logic
• with emphasis on the resolution method.

Discuss how to implement call-by-name using environments (cf. Assignment 3).

33: Nov 11 (Fri)

Finish the crash course in logic:

• cover predicate logic
• still with emphasis on the resolution method.

Programming Assignment 4 due this weekend.

34: Nov 14 (Mon)

Introduction to Prolog (also described in Chapter 8 of Schmidt's notes):

• cover the most basic features
• illustrate how it implements the resolution method using backtracking.

35: Nov 16 (Wed)

Discuss how to handle lists in Prolog:

• the member predicate and its various call patterns
• the double (function-like) predicate
• Prolog Lab 1, due Friday evening.

36: Nov 18 (Fri)

Data structures in Prolog:

• trees
• general functors.

Control in Prolog:

• the order of literals, and of clauses, may matter

Prolog Lab 1 due tonight.

Nov 21-25 (Mon-Fri)

Thanksgiving holiday

37: Nov 28 (Mon)

Introduce Programming Assignment 5:

• the constraint language to be interpreted
• the skeleton interpreter provided.

Discuss model solutions for Prolog Lab 1.

38: Nov 30 (Wed)

Continue Prolog:

• search trees may be pruned using "!" (cut)
• how to express negation, in particular in the presence of variables
• how to find the change for a given amount.

Further discuss Programming Assignment 5.

39: Dec 2 (Fri)

Discuss how to sort in Prolog;

• implementation (almost) equals the specification!
• but for a practical implementation, a bit more work is needed.

Hand back, and discuss, graded Exam 2.
Programming Assignment 5 due this weekend.

40: Dec 5 (Mon)

• Wrap up Prolog, also mentioning Datalog which is a proper subset.
• "Holiday talk": sketch a security analyzer that works on source code

Dec 6 (Tue)

11am-noon in 3099: CIS705 presentations

Dec 7 (Wed)

Class canceled

Dec 8 (Thu)

10am-noon in 2168: CIS705 presentations

Dec 9 (Fri)

noon-1pm in 3099: CIS705 presentations

41: Dec 9 (Fri)

Review session, discussing

• previous exam questions
• the recent Assignments 4 & 5.

Dec 14 (Wed)

Final exam, 4:10 - 6:00pm