CPS 343/543 (3 sem hrs) is a course in programming language concepts. The approach involves studying language concepts, such as scope and parameter passing, by implementing a series of interpreters in Scheme, for purposes of its combined simplicity and power, and assessing the differences in the resulting languages. Students can also expect a comparative survey of programming paradigms, including the use of representative languages, such as Haskell, PROLOG, and Smalltalk. The course emphasizes alternative language features such as continuations, currying, and lazy evaluation, and the use of these features in novel application areas such as web interaction management. Course themes include the relationship between languages and the capacity to express ideas about computation, and the influence of language design and implementation options on current trends in programming practice and vice versa. This course assumes no prior experience with Scheme, Haskell, PROLOG, or Smalltalk.

1. Fundamentals ([EOPL] Preface, Ch1)
   1. introduction, course objectives and outline, and programming language paradigms [A Brief Introduction to Lisp, about closures]: Jan 7
   2. formal languages and grammars (Backus-Naur form) (§1.1): Jan 9 14
   3. recursive programming in Scheme (λ-calculus and S-expressions) (§1.2) [installing & using PLT Scheme, functional programming resources, The Scheme Programming Language]: Jan 16 23 28 30
   4. Exam I: Feb 4 (closed book, closed notes)
   5. variable binding and scope (§1.3): Feb 6
   
   
2. Data abstraction ([EOPL] Ch2)
   1. inductive data types and abstract syntax (§§2.1-2.2): Feb 11
   2. representation strategies (list, abstract syntax, and procedural) (§§2.3-2.4): Feb 13
   
   
3. Environment-passing interpreters ([EOPL] Ch3, [PIH] Ch4,5,12)
   1. front end, conditional evaluation, and local binding (§§3.1-3.4) [The Roots of LISP]: Feb 18
   2. procedures and closures (§3.5): Feb 20
   3. Exam II: Feb 25 (closed book, closed notes)
   4. recursion (§3.6) and variable assignment (§3.7): Feb 27
   5. parameter-passing mechanisms (§3.8): Mar 3
   6. lazy evaluation and thunks (call-by-name and call-by-need; §3.8): Mar 5
   7. lazy evaluation in Haskell [installing & using HUGS98] ([PIH] Ch4,5,12), and statements and side effects (§3.9): Mar 10 12
   
   
4. Types ([EOPL] Ch4, [PIH] Ch3,7,10, [EMLP] Ch3,5,6,8)
   1. strong typing, type inference, and currying (in Haskell; [PIH] Ch3,7): Mar 12
   2. type systems (in Haskell; [PIH] Ch10): Mar 26
   3. Exam III: Mar 31 (take home)
   
   
5. Control ([EOPL] pp. 241-243, §8.1, [TSPL] §§3.2-3.4, [TSS] Ch13, 19)
   1. continuations and call/cc [about continuations] ([TSPL] §3.3, [TSS] Ch13): Mar 31
   2. tail calls (pp. 241-243, [TSPL] §3.2) and continuation-passing style (§8.1, [TSPL] §3.4, [TSS] Ch19): Apr 2
   
   
6. Logic programming ([EOPL] §7.6)
   1. first-order predicate logic (Horn clauses, resolution, and unification; §7.6): Apr 7
   2. logic programming in PROLOG (facts, rules, and goals) [A Brief Introduction to PROLOG, installing & using SWI-PROLOG, logic programming resources, Prolog Programming A First Course]: Apr 14
   3. logic programming in PROLOG (control and cut): Apr 16
   
   
7. Object-oriented programming ([EOPL] pp. 169-171, [QTOL])
   1. message passing, dynamic binding, and reflection (pp. 169-171): Apr 21
   2. Smalltalk and Squeak ([QTOL]) [A Brief Introduction to Smalltalk, installing & using Squeak, object-oriented programming resources]; and course reflection: Apr 23
   
   
8. Final Exam: M April 28, 4:30pm-6:20pm, MH 203 (comprehensive, closed book, closed notes)