Captain's Log: CIS 505, Programming-Language Paradigms, Fall 2009

1: Aug 24 (Mon)
Amtoft gives introduction to course, covering the syllabus, and briefly going through selected slides from Sections 1 & 2 of Schmidt's informal introduction to software architecture.
2: Aug 26 (Wed)
Schmidt starts part I of the course.
3: Aug 28 (Fri)
4: Aug 31 (Mon)
5: Sep 2 (Wed)
6: Sep 4 (Fri)
Sep 7 (Mon)
University Holiday (Labor Day)
7: Sep 9 (Wed)
8: Sep 11 (Fri)
9: Sep 14 (Mon)
10: Sep 16 (Wed)
11: Sep 18 (Fri)
12: Sep 21 (Mon)
13: Sep 23 (Wed)
14: Sep 25 (Fri)
Schmidt finishes part I of the course.
15: Sep 28 (Mon)
Amtoft starts part II of the course:
  1. motivates the functional paradigm
  2. runs SML/NJ on some simple examples, covering the first 8 pages (17-24) of Chapter 2 in Paulson.
16: Sep 30 (Wed)
We cover selected features from pp.25-43 in Paulson:
17: Oct 2 (Fri)
We cover pp.43-49 in Paulson:
Oct 5 (Mon)
Student Holiday
18: Oct 7 (Wed)
We cover pp.49-54,64-67 in Paulson:
19: Oct 9 (Fri)
We introduce the list datatype, covering pp 69-76 of Paulson.
Homework 4 out tonight, on writing in SML an interpreter for a calculator.
20: Oct 12 (Mon)
We discuss more operations on lists (pp. 77-82 of Paulson), in particular on how to append two lists and how to reverse a list; for the latter, the introduction of an "accumulating parameter" is crucial.
We also encounter equality types (p. 97 of Paulson); a function type is not an equality type since two functions cannot be easily tested for equality.
21: Oct 14 (Wed)
We present some design patterns useful for input processing.
We cover association lists, and polymorphic set operations (pp. 98-101 of Paulson).
22: Oct 16 (Fri)
We mention how it is hard to report sensible error messages in the subset of SML covered so far.
We see how to implement various list sorting algorithms (pp. 108-112 of Paulson): insertion sort is hopeless except if the input is small or already almost sorted; merge sort easily handles large random lists; quicksort also can handle large random lists but may (in its naive form) perform badly on lists that are already almost sorted.
This basically concludes the covering of lists, cf. Chapter 3 of Paulson.
23: Oct 19 (Mon)
We introduce general datatypes (lists being a special case); they can be polymorphic and/or recursive.
We have thus embarked on Chapter 4 of Paulson, covering pp.123-133.
24: Oct 21 (Wed)
We introduce a datatype for binary trees, cf. pp.141-144 in Paulson, and in particular look at how to generate "random" trees.
25: Oct 23 (Fri)
We introduce the very convenient exception feature, cf. pp. 134-140 in Paulson.
We motivate the newly posted homework assignment.
26: Oct 26 (Mon)
We discuss the upcoming assignment.
First we recall the general approach, based on activation records, to implement procedural languages; in the present exercise, several aspects can be simplified (like we do not need values in the heap, and all static links point to the top-level).
Next we discuss how to implement it in ML, in particular we state the type of the functions that evaluate expressions and execute commands.
27: Oct 28 (Wed)
We show how to output the nodes of a tree in pre/in/post-order, and how an accumulating parameter speeds up computation, cf. pp 145-147 in Paulson.
We show how a simple goto-program can be compiled into a set of mutually recursive functions, cf. p.58 in Paulson.
We discuss further the upcoming assignment.
28: Oct 30 (Fri)
We further discuss the upcoming assignment, with deadline postponed until Monday at 1pm.
29: Nov 2 (Mon)
We embark on Chapter 5 of Paulson.
We see that functions can be considered values, in particular received as function arguments and returned as function results, cf. pp 171-179.
We introduce certain standard functionals, like map and filter and foldr, cf. selected parts of pp 179-191.
30: Nov 4 (Wed)
We continue discussing functionals and combinators, cf. pp 179-191 in Paulson:
we introduce foldl and treefold, as well as the SKI combinators.
31: Nov 6 (Fri)
We show that one can represent potentially infinite lists in SML, using delayed evaluation, cf. pp 191-195 in Paulson.
To prepare for the upcoming Assignment 6, we go through the parser from Assignment 5.
32: Nov 9 (Mon)
We present several more functionals on potentially infinite lists, cf. pp 191-196 in Paulson.
To prepare for the upcoming Assignment 6, we finish the parser from Assignment 5, and discuss the syntax and semantics of the language to be interpreted.
33: Nov 11 (Wed)
We present two examples illustrating how delayed evaluation enables us to write powerful algorithms in an elegant way: We discuss the upcoming Assignment 6 in more detail, in particular we go through the model solutions for Assignment 5 that are more general than needed so as to prepare for a larger language.
This finishes part II (Amtoft's part) of the course (except for the upcoming Assignment 6).
34: Nov 13 (Fri)
Schmidt starts part III of the course.
35: Nov 16 (Mon)
36: Nov 18 (Wed)
37: Nov 20 (Fri)
38: Nov 23 (Mon)
Nov 25-27 (Wed-Fri)
Thanksgiving holiday
39: Nov 30 (Mon)
40: Dec 2 (Wed)
41: Dec 4 (Fri)
42: Dec 7 (Mon)
43: Dec 9 (Wed)
44: Dec 11 (Fri)
Last day of class.


Torben Amtoft