There is no required textbook for this course. Electronic reference material will be provided here as the term progresses.
Note: The main or “required” material is also mirrored locally whenever this is permitted by the license of the respective material. Note however that such a material has its own license and so is not necessarily covered by the site license.
Introduction ( handout and overhead presentation) and a brief history of programming languages ( handout and overhead presentation).
Functional programming ( handout and overhead presentation). We go into a quick but judicious incursion into the functional programming paradigm using the Haskell programming language. The first main resource for this section is Notes on Functional Programming with Haskell by H. Conrad Cunningham (local copy). We will cover in class Sections 2, 3, 5, 6, 7, 8, and 15. Alternatively, A Gentle Introduction to Haskell 98 by Paul Hudak, John Peterson, and Joseph Fasel (local copy) is also worth a look; this paper is also available externally as a Web page. We cover in class all of this paper except Sections 6.3, 7, 9, and 13.
Here are some possibly interesting Haskell programs (with types): expressing dates (kind of silly but features a few explicit instantiations of type classes) and binary search trees.
Other interesting resources include the following:
Playing with Haskell: The standard compiler and interactive environment for Haskell is the Glasgow
Haskell Compiler (or GHC). This is a production-level environment and much more complex
than what is required in the course, but no lighter alternative seems to be available. Therefore I
still recommend the use of GHC for your Haskell needs. However, you do not need to concern
with anything in that package other than the interactive subsystem (aka interpreter) namely,
ghci.
Models of computation ( handout and overhead presentation). For the most part there is no need for further documentation. Indeed, the Turing machine/RAM is covered rather lightly. On the other hand we will consider the predicate calculus more in depth (and from a more practical perspective) later.
The exception is the lambda calculus. This discussion has a deeper impact to the topic of Haskell programming. To learn more check out A Tutorial Introduction to the Lambda Calculus by Raúl Rojas.
Logic programming ( handout and overhead presentation). Yet another quick (and yet judicious) incursion, this time into the logic programming paradigm and using the Prolog programming language. The main resource is Prolog Programming: A First Course by Paul Brna, courtesy of the WayBack Machine. The original location is no longer up (has been down since early 2019) and so a local copy is available despite the unclear license. We cover Chapters 2, 3, 4, 5, 6, and Section 7.2.
Other resource include:
For the enthusiasts the following texts are available in the library:
Playing with Prolog: The most popular Prolog system is SWI Prolog, which is a production-grade Prolog system including many extensions and optimizations. Another popular choice is GNU Prolog, which focuses on compliance with the ISO standard and on fast and efficient execution while featuring far fewer extensions than SWI Prolog; it even offers compilation of Prolog programs to executable. Both systems will do just fine for the programs that you will develop in this course. If anything I tend to recommend SWI Prolog, but that is simply because I am more familiar with it.
Scanning and parsing - a recap ( handout and overhead presentation). This section is just a reminder. The main resource is your knowledge on the matter acquired in CS 310. If you need a refresher or are interested in learning more you can check out Lecture Notes on Regular Languages and Finite Automata by Andrew M. Pitts (Only Chapter 1 and Section 2.1 are covered in class, but the rest of the text may be interesting to read), Introduction to Grammars and Language Analysis by Zerksis D. Umrigar, and Introduction to Recursive Descent Parsing by the same Zerksis D. Umrigar.
You may also find the following useful:
A simple parser example: Parsers are rarely built by hand, but seeing such an attempt may prove instructive. We start from the following specification. Figure 1 shows the grammar of a simple yet pretty realistic programming language. In order to construct a recursive descent parser we must convert the grammar to a form that is suitable for recursive descent parsing. The result is shown in Figure 2. The lexical structure is described by a finite automaton rather than the usual regular expressions.
Now we can then proceed with the development of a recursive descent parser. The result is parser.cc. The input (program to be parsed) is read from the standard input stream. The output is a printout of the respective parse tree, produced to the standard output stream. Note both the scanner and the parser are constructed by hand, and that arguably (and surprisingly) the scanner is a more complex implementation than the parser. The specification document also includes a few examples if you want to try the parser out.
My lectures are recorded, as follows:
Note that Lecture 14 was the first examination.