Advanced Methods in Programming Languages (201-2-4411-01)
Notes Week 1 - Michael Elhadad
main page next class

Intro Material on Scheme

Review this material if you don't remember Scheme:
  1. Teach yourself Scheme in Fixnum Days by Dorai Sitaram (A brief tutorial that uses MzScheme - includes good advanced material on control structures towards the end -- call/cc, coroutines, amb, engines).
  2. A WEB-Workshop on Scheme (by John David Stone).
  3. repository of Scheme related info
  4. Introductory slides on Scheme (by Daniel P. Friedman, CS Dept. Indiana University).
  5. Introduction to Scheme and its implementation (by G. Wilson et al)

Scheme Refresher

  1. Primitives, composition, abstraction.
  2. Data types: numbers, booleans, characters, strings, symbols.
  3. Compound data types:
    1. Lists
    2. Vectors: (vector 1 2 3), #(1 2 3) / Heterogeneous, random-access (like arrays and like records).
    3. Procedures: (lambda (x) x)
  4. First-class procedures:
    1. lambda: anonymous procedures
    2. map, for-each
    3. closures
    4. cell object

Inductive Specification of Data

  1. Backus-Naur Form: list of numbers
  2. Deriving program from BNF specification: list-of-number?
  3. Context-sensitive specification: binary-search-tree?
  4. Using BNF specification for processing: remove-first, subst

Example: Syntax and properties of lambda calculus expressions

  1. lambda calculus syntax
  2. Free and bound variables
  3. Renaming variables: alpha conversion

Syntactic Abstraction

  1. Definition of let with lambda.
  2. Definition of and and or with if.
  3. Abstract data types: define-datatype, cases.
  4. Representation of abstract syntax with abstract data types: BNF for lambda calculus, parse on lists.
  5. Parsing with sllgen.

Last modified 23 Feb 2003 Michael Elhadad