# 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)
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

Torben Amtoft