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

Aug 21 (Mon)

Class canceled so as to enable travel for solar eclipse

1: Aug 23 (Wed)

Introduction to course:

• go through syllabus
• compare the functional and the imperative paradigms (the slide set Introduction.pdf)

2: Aug 25 (Fri)

Cover the slide set Basics.pdf (except for the last part on polymorphism) with focus on types:

• SML is strongly typed: each value has exactly one type
• SML has static typing: types can be inferred at compile-time
• SML has basic types such as integers, reals, strings, booleans
• SML has composite types (that can be nested) such as lists and tuples

3: Aug 28 (Mon)

• Finish Basics by observing that functions on lists are polymorphic
• Embark on Functions:
  • how to define and use functions
  • functions are first-class citizens in SML!
• Post and discuss Lab 1, due Wednesday evening.

4: Aug 30 (Wed)

• Finish Functions; in particular emphasize
  • that SML is statically scoped; functions may still use definitions that have been overwritten
  • that SML is highly polymorphic, as witnessed by the type for function composition.
• Briefly introduce the iClicker system (guide uploaded on Canvas)

Lab 1 due at 11:59pm.

5: Sep 1 (Fri)

• Briefly discuss the recent Lab 1
• Embark on ListFunctions with guidelines for how to write functions operating on lists
• Test the iClicker system
• Discuss Lab 2 (to be posted later today), due Thursday night.

Sep 4 (Mon)

University Holiday (Labor Day)

6: Sep 6 (Wed)

• Continue ListFunctions:
  • write the append function
  • introduce the map and filter templates.
• Ask two (ungraded) quiz questions using the iClicker system.
• Briefly introduce Project 1, due late next week.
• Briefly further discuss Lab 2, due tomorrow night.

7: Sep 8 (Fri)

• Continue ListFunctions:
  • introduce the foldr and foldl templates
• Discuss Project 1:
  • explain the calculator to be implemented

8: Sep 11 (Mon)

• Continue ListFunctions:
  • discuss how to represent and manipulate sets in SML (where not all types allow test for equality)
• Further discuss Project 1:
  • outline the structure of the uploaded skeleton interpreter

9: Sep 13 (Wed)

• Scott DeLoach, the CS department head, motivates the desire to hire more faculty
• Briefly discuss the recent Lab 2 (now graded)
• Finish ListFunctions, by discussing 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 from keys to values.
  Further discuss Project 1:
  • go through the uploaded skeleton interpreter

10: Sep 15 (Fri)

• Introduce DataTypes, on how users may define their own types
  • which may be parametrized, and/or recursive
  • whose values are handled by case patterns;
• along the way, mention how the features are used in (the skeleton of) Project 1, due over the weekend.

11: Sep 18 (Mon)

• Cover TreeFunctions:
  • emphasize that the structure of trees direct the structure of functions operating on them
  • give several examples of how to write functions that operate on inductively defined datatypes.
• Give a small quiz using iClicker (which will from now on be a small part of the course grade)
• Introduce Lab 3, due Thursday night.

12: Sep 20 (Wed)

• Embark on Recursion: we
  • illustrate how the stack is used to evaluate a recursive function
  • show how a badly written function may be infeasible to evaluate on large input
  • introduce the notion of tail recursion: nothing needs to be done after recursive call
• Further discuss Lab 3, due tomorrow night:
  • motivate the various arguments to fold

13: Sep 22 (Fri)

• Finish Recursion:
  • illustrate by several examples how converting into tail recursion is often crucial for efficiency
  • give a small quiz
• Cover Exceptions, convenient to handle irregular situations;
  • show how to raise and handle (parametrized) exceptions

14: Sep 25 (Mon)

• Finish Exceptions:
  • illustrate the power (to facilitate backtracking) by a non-trivial example.
• Wrap up various material, discussing solutions to
  • the recent Lab 3
  • the recent Project 1
  • last year's midterm on SML

15: Sep 27 (Wed)

Exam 1

16: Sep 29 (Fri)

Our focus now turns to the implementation of a programming language:

• give an overview of the stages involved, as detailed in the slides PLstages;
• sketch how a lexer converts a string of characters into a list of tokens;
• show how grammars give structure to the input but may be ambiguous;
• finish with a quiz.

17: Oct 2 (Mon)

Present Programming Project 2

18: Oct 4 (Wed)

• Continue discussing Programming Project 2, going thru the skeleton interpreter provided
• See how to rewrite a grammar for expressions so as to resolve ambiguity
• finish with a quiz.

19: Oct 6 (Fri)

• Discuss, and give back, graded Exam 1.
• Outline priorities for modifying the skeleton interpreter for Project 2.
• Outline how to write a (top-down) parser

20: Oct 9 (Mon)

• Wrap up PLstages, by describing:
  • how to convert into an abstract syntax tree
  • how to interpret an abstract syntax tree
• Briefly look at the parser given for Project 2.
• Show how to encode lazy evaluation in SML (the slides Lazy):
  • illustrate how various lists functions can be rewritten to work on lazy lists.

21: Oct 11 (Wed)

• Show (followed by a quiz) how lazy evaluation may allow very succinct and elegant solutions to certain problems, such as:
  • finding primes using the Sieve of Eratosthenes.
• Start discussing how to implement first-order functional languages (the slides InterpretFirstOrderFunctions);
  • 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

22: Oct 13 (Fri)

Continue discussing how to implement functional languages:

• as in Chapter 6 of the textbook, we
  • for a first-order language, show an implementation that uses environments
  • mention the difference between dynamic and static scope.
• a small quiz on CBN and CBV
• briefly (again!) motivate the use of higher order functions (the slides InterpretHigherOrderFunctions)

Project 2 due over the weekend.

23: Oct 16 (Mon)

As in Chapter 7 of the textbook, we embark on how to interpret higher order functions (the slides InterpretHigherOrderFunctions)

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

24: Oct 18 (Wed)

• Embark on the presentation of Programming Project 3.
• A small quiz on the use of closures
• Embark on a brief introduction (the slides Racket) to the Racket language (more details to be found in this guide).

25: Oct 20 (Fri)

• Finish covering the slides on key features of Racket
• Introduce Racket Lab 1, due Tuesday night
• Start discussing the skeleton interpreter provided for Project 3

26: Oct 23 (Mon)

• Discuss in detail the skeleton interpreter provided for Project 3
• Briefly mention various extra features of Racket

Racket Lab 1 due tomorrow night.

27: Oct 25 (Wed)

• Discuss solutions to the recent Racket Lab 1
• Look at more examples of the capabilities of the language being interpreted in Project 3
• Start discussing solutions to the recent Project 2

28: Oct 27 (Fri)

• Finish discussing solutions to the recent Project 2.
• 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
  • see an example of how to define, and how not to define, a counter (Section 8.1.3)

Project 3 due over the weekend.

29: Oct 30 (Mon)

Prepare for Exam 2:

• discuss solutions for Project 3
• discuss questions from last year's exam set.

30: Nov 1 (Wed)

Exam 2

31: Nov 3 (Fri)

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

• present examples of how to interpret programs in the language

Continue the slides InterpretMutations (cf Chapter 8 of the textbook):

• argue that environments alone are not sufficient to record mutations properly (Section 8.1.5)
• therefore introduce stores, to be used in addition to environments (Section 8.1.6).

32: Nov 6 (Mon)

Continue the slides InterpretMutations (cf Chapter 8 of the textbook):

• give the structure of the interpreter
• go through the various clauses (Section 8.1.7), with focus on
  • how stores propagate in a different way than environments
  • the treatment of boxes.

Continue discussing Project 4:

• explain the semantics
• go thru the uploaded skeleton interpreter.

33: Nov 8 (Wed)

Finish the slides InterpretMutations (Chapter 8 of the textbook):

• how to assign to variables
• how to interpret function application
• finish with a quiz.

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

• cover propositional logic
• and introduce CNF (conjunctive normal form).

34: Nov 10 (Fri)

• Discuss, and give back, graded Exam 2.
• Continue propositional logic, with emphasis on the resolution method.

Project 4 due over the weekend.

35: Nov 13 (Mon)

Finish the crash course in logic:

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

36: Nov 15 (Wed)

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

• cover the most basic features
• cover lists, in particular
  • the member predicate and its various call patterns
  • the double (function-like) predicate.

Introduce Prolog Lab 1, due Friday night

37: Nov 17 (Fri)

• Illustrate how Prolog implements the resolution method using backtracking.
• Show how to use functors to encode trees in Prolog.
• Point out that the order of literals, and of clauses, often matters.

Prolog Lab 1 due tonight.

Nov 20-24 (Mon-Fri)

Thanksgiving holiday

38: Nov 27 (Mon)

Introduce Project 5 (due the coming weekend):

• the constraint language to be interpreted
• guidelines for how to augment the skeleton interpreter.

Discuss model solutions for Prolog Lab 1.

39: Nov 29 (Wed)

Continue Prolog:

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

Continue discussing the skeleton interpreter for Project 5, in particular:

• how to parse (Prolog automatically tries out all possibilities).

40: Dec 1 (Fri)

See some non-trivial applications of Prolog:

• how to find the change for a given amount
• how to sort:
  • the implementation (almost) equals the specification!
  • but for a practical implementation, a bit more work is needed.

Put Prolog in perspective, also mentioning Datalog which is a proper subset.

3:30-4:30pm: CIS705 presentations in room 2168.

Project 5 due this weekend.

41: Dec 4 (Mon)

• Discuss solutions for Project 4
• "Holiday talk": sketch a security analyzer that works on source code.

Dec 5 (Tue)

1-5pm in room 2207: CIS705 presentations

Dec 6 (Wed)

Class canceled

Dec 7 (Thu)

10am-1pm in room 2168: CIS705 presentations

42: Dec 8 (Fri)

Review session, discussing

• the recent Project 5
• last year's final exam.

Dec 11 (Mon)

Final exam, 11:50am - 1:40pm