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.

Pre-requisite: CPS 350 (Data Structures and Algorithms) (a minimum grade of C is required for students enrolled in CPS 543)

Meeting times: M W 4:30pm-5:45pm, MH 203

Instructor: Dr. S. Perugini, AN 145, 229-4079, e-mail id: perugisa, OH's: M W 5:45pm-6:45pm, T Th noon-1:00pm, and by appointment.

Teaching assistant: Travis Suel, AN 26, e-mail id: sueltraz, OH's: M W 1:00pm-2:00pm, T Th 6:30pm-7:30pm, and by appointment.

Required textbook: [EOPL] Essentials of Programming Languages by D.P. Friedman, M. Wand, and C.T. Haynes. MIT Press, Cambridge, MA, Second edition, 2001. ISBN: 0-262-06217-8 (textbook webpage contains links to the source code of all programs in the text). An eBook of [EOPL] is available free to all UD students in the library's eContent collection. To access it conduct a search for the title in the library's catalog at library.udayton.edu.

Recommended textbooks:
    [TLS] The Little Schemer by D.P. Friedman and M. Felleisen. MIT Press, Cambridge, MA, Fourth edition, 1996. ISBN: 0-262-56099-2.
    [TSS] The Seasoned Schemer by D.P. Friedman and M. Felleisen. MIT Press, Cambridge, MA, 1996. ISBN: 0-262-56100-X.
    [TSPL] The Scheme Programming Language by R.K. Dybvig. MIT Press, Cambridge, MA, Third edition, 2003. ISBN: 0-262-54148-3 (entire text of second and third editions is available online)
    [PIH] Programming in Haskell by G. Hutton. Cambridge University Press, Cambridge, 2007. ISBN: 0-521-69269-5.
    [PPFC] Prolog Programming A First Course by P. Brna (entire text available online in various formats).
    [PIP] Programming in Prolog by W.F. Clocksin and C.S. Mellish. Springer-Verlag, Berlin, Fourth edition, 1997.
    [QTOL] Squeak: A Quick Trip to ObjectLand by G. Korienek, T. Wrensch, and D. Dechow. Addison-Wesley, Boston, MA, 2002. ISBN: 0-201-73114-2.

Course objectives:
  • Establish an understanding of language concepts through the implementation of interpreters.
  • Improve ability to understand new languages and technologies, and improve background for selecting appropriate languages.
  • Expose students to alternate styles of programming and exotic ways of affecting computation.
Evaluation, workload, and policies

Course outline, lecture notes, and homework and reading assignments (to be completed prior to class):
  1. Fundamentals ([EOPL] Preface, Ch 1)
    1. introduction and programming language paradigms [A Brief Introduction to Lisp, about closures]: Jan 5
    2. formal languages and grammars (Backus-Naur form) (§1.1): Jan 7 12
    3. recursive programming in Scheme (λ-calculus and S-expressions) (§1.2) [installing & using PLT Scheme, functional programming resources, The Scheme Programming Language]: Jan 14
    4. recursive programming in Scheme (building data structures, e.g., binary trees, with lists) (§1.2) [HW 1 due]: Jan 21
    5. recursive programming in Scheme (let, let*, letrec) (§1.2): Jan 21
    6. [HW 2 due]: Jan 28
    7. Exam I (closed book, closed notes): Feb 2
    8. binding and scope (§1.3): Feb 4

  2. Data abstraction ([EOPL] Ch 2)
    1. inductive data types and abstract syntax (§§2.1-2.2): Feb 9
    2. inductive data types and abstract syntax (§§2.1-2.2) [HW 3 due]: Feb 11
    3. representation strategies (procedural) (§2.3): Feb 16
    4. representation strategies (list and abstract syntax) (§§2.3-2.4) [HW 4 due]: Feb 18
    5. Exam II (closed book, closed notes): Feb 23

  3. Environment-passing interpreters ([EOPL] Ch 3, [PIH] Ch 4, 5, 12)
    1. front end, conditional evaluation, and local binding (§§3.1-3.4) [scanner-parser.scm] [The Roots of LISP]: Feb 25
    2. procedures and closures (§3.5): Mar 2
    3. recursion (§3.6) and variable assignment (§3.7) [HW 5 due]: Mar 4
    4. parameter-passing mechanisms (§3.8): Mar 9
    5. lazy evaluation and thunks (call-by-name and call-by-need; §3.8): Mar 9
    6. lazy evaluation in Haskell [installing & using HUGS98] ([PIH] Ch 4, 5, 12), and statements and side effects (§3.9) [HW 6 due]: Mar 11 16

  4. Types ([EOPL] Ch 4, [PIH] Ch 3, 7, 10, [EMLP] Ch 3, 5, 6, 8)
    1. strong typing, type inference, and currying (in Haskell; [PIH] Ch 3, 7) [Exam III due]: Mar 18
    2. type systems (in Haskell; [PIH] Ch 10): Mar 23

  5. Control ([EOPL] pp. 241-243, §8.1, [TSPL] §§3.2-3.4, [TSS] Ch 13, 19)
    1. continuations and call/cc [about continuations] ([TSPL] §3.3, [TSS] Ch13) [HW 7 due]: Mar 25
    2. tail calls (pp. 241-243, [TSPL] §3.2) and continuation-passing style (§8.1, [TSPL] §3.4, [TSS] Ch19): Mar 30

  6. Logic programming ([EOPL] §7.6)
    1. first-order predicate logic (Horn clauses, resolution, and unification; §7.6) [HW 8 due]: Apr 1
    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 13
    3. logic programming in PROLOG (control and cut) [HW 9 due]: Apr 15

  7. Object-oriented programming ([EOPL] pp. 169-171, [QTOL])
    1. message passing, dynamic binding, and reflection (pp. 169-171): Apr 20
    2. Smalltalk and Squeak ([QTOL]) [A Brief Introduction to Smalltalk, installing & using Squeak, object-oriented programming resources]: Apr 22
    3. course reflection [HW 10 due]: Apr 22

  8. Final Exam (comprehensive, closed book, closed notes): M April 27, 4:30pm-6:20pm, MH 203
Programming style guide

Programming languages resources

Practice problems More practice problems

Grades: available in Isidore

Computer accounts: CPS account access @ home | CPS labs hours | Keeping your password safe | A beginner's guide to effective e-mail
If you are unable to log into your CPS (Windows or UNIX) account or if you forget your CPS (Windows or UNIX) account password, contact the CPS systems administrator, Mr. Tramontana, at tramonjr at notes dot udayton dot edu or 229-3858, and be as specific as possible.

Helpful links: academic calendar | student handbook | UDit policies 

Feedback: Dr. Perugini welcomes any feedback you may have on the style of the lectures, the concepts presented in class, the course webpage, homeworks, deadlines, course and grading policies, or your general experience in the course.