CPS 343/543: Comparative Languages/Spring 2011

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, but does require an open mind, an intellectual and scientific curiosity, and a passion for languages.

CPS 343/543: Comparative Languages Spring 2011
Pre-requisite: CPS 350 (Data Structures & 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, e-mail id: sperugini1, 229-4079, AN 145, OHs: M W 5:45pm-6:15pm, & by appointment.

Teaching assistant: Trevor Dasch, e-mail id: dascht1, AN 26, OHs: T Th noon-1:15pm, F 2:50pm-4:50pm, & by appointment.

Required textbook: [EOPL] Essentials of Programming Languages by D.P. Friedman, M. Wand, & C.T. Haynes. MIT Press, Cambridge, MA, 2nd 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. This book is also on reserve at the Roesch library.

Recommended textbooks:
    [TLS] The little schemer by D.P. Friedman & M. Felleisen. MIT Press, Cambridge, MA, 4th edition, 1996. ISBN: 0-262-56099-2. This book is on reserve at the Roesch library.
    [TSS] The seasoned schemer by D.P. Friedman & 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, 4th edition, 2009. ISBN: 978-0-262-51298-5 (entire text 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 & C.S. Mellish. Springer-Verlag, Berlin, 5th edition, 2003. ISBN: 3540006788.
    [QTOL] Squeak: A quick trip to ObjectLand by G. Korienek, T. Wrensch, & 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/paradigms of programming and exotic ways of affecting computation.
Evaluation, workload, and policies

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

  2. Data abstraction ([EOPL] Ch 2)
    1. inductive data types & abstract syntax (§§2.1-2.2): Feb 16 21
    2. representation strategies (procedural) (§2.3): Feb 23
    3. representation strategies (list & abstract syntax) (§§2.3-2.4) [HW 3 due]: Feb 23

  3. Environment-passing interpreters ([EOPL] Ch 3, [PIH] Ch 4, 5, 12)
    1. front end, conditional evaluation, & local binding (§§3.1-3.4) [scanner-parser.scm] [The Roots of LISP]: Feb 28
    2. (non-recursive) procedures & closures (§3.5) [about closures] [HW 4 due]: Mar 2
    3. recursion (§3.6) & variable assignment (§3.7): Mar 7
    4. parameter-passing mechanisms (§3.8) [HW 5 due]: Mar 9
      Exam II (closed book, closed notes) [practice problems]: Mar 14
    5. lazy evaluation & thunks (call-by-name & call-by-need; §3.8) [HW 6 due]: Mar 16
    6. lazy evaluation & thunks (call-by-name & call-by-need; §3.8): Mar 21
    7. lazy evaluation in Haskell [installing & using HUGS98] ([PIH] Ch 4, 5, 12) [HW 7 due]: Mar 23
    8. statements & side effects (§3.9): Mar 23

  4. Types ([EOPL] Ch 4, [PIH] Ch 3, 7, 10, [EMLP] Ch 3, 5, 6, 8)
    1. strong typing, type inference, & currying (in Haskell; [PIH] Ch 3, 7): Mar 28
    2. type systems (in Haskell; [PIH] Ch 10): [HW 8 due]: Mar 30

  5. Control ([EOPL] pp. 241-243, §8.1, [TSPL] §§3.2-3.4, [TSS] Ch 13, 19)
    1. continuations & call/cc [about continuations] ([TSPL] §3.3, [TSS] Ch13): Apr 4
    2. tail calls (pp. 241-243, [TSPL] §3.2) & continuation-passing style (§8.1, [TSPL] §3.4, [TSS] Ch19) [Exam III due]: Apr 6
    3. tail calls (pp. 241-243, [TSPL] §3.2) & continuation-passing style (§8.1, [TSPL] §3.4, [TSS] Ch19): Apr 11

  6. Logic programming ([EOPL] §7.6)
    1. first-order predicate logic (Horn clauses, resolution, & unification; §7.6): Apr 18
    2. logic programming in PROLOG (facts, rules, & goals) [A Brief Introduction to PROLOG, installing & using SWI-PROLOG, logic programming resources, Prolog Programming A First Course]: Apr 18
      logic programming in PROLOG (control & cut) [HW 9 due]: Apr 20

  7. Object-oriented programming ([EOPL] pp. 169-171, [QTOL])
    1. message passing, dynamic binding, & reflection (pp. 169-171): Apr 25
    2. Smalltalk & Squeak ([QTOL]) [A Brief Introduction to Smalltalk, installing & using Squeak, object-oriented programming resources]: Apr 27
    3. course reflection (terms and themes; ACM A.M. Turing award winners with contributions related to languages) [HW 10 due]: Apr 27

  8. Final Exam (comprehensive, closed book, closed notes) [practice problems]: M May 2, 4:30pm-6:20pm, MH 203
Programming style guide

Programming languages resources

Practice problems

Grades: available in Isidore

Computer accounts: UDit | CPS labs hours | Keeping your password safe | A beginner's guide to effective e-mail

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.