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:
- motivates the functional paradigm
- 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:
-
We introduce tuples and records to represent structured data.
-
We write a recursive function,
and note that tail-recursion
can be implemented in constant space.
-
17: Oct 2 (Fri)
-
We cover pp.43-49 in Paulson:
-
We discuss various modes of evaluation: call-by-value (used by SML),
call-by-name, call-by-need (or lazy evaluation).
-
We show some examples of recursive programming.
-
Oct 5 (Mon)
-
Student Holiday
-
18: Oct 7 (Wed)
-
We cover pp.49-54,64-67 in Paulson:
-
We show how to prove, by induction,
the correctness of an iterative (and fast) fibonacci function.
-
We show how to design a recursive algorithm for integer square root
by the divide and conquer paradigm.
-
We discuss how SML infers types.
-
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:
-
computing primes, using
the sieve of Eratosthenes (p 199 in Paulson);
-
giving change (p 197 in Paulson).
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