Advanced Methods in Programming Languages (201-2-4411-01)
Notes Week 1 - Michael Elhadad
Intro Material on Scheme
Review this material if you don't remember Scheme:
-
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).
-
A WEB-Workshop on Scheme
(by John David Stone).
- Schemers.org: repository
of Scheme related info
-
Introductory slides on Scheme (by Daniel
P. Friedman, CS Dept. Indiana University).
- Introduction to Scheme and its implementation (by G. Wilson et al)
Scheme Refresher
- Primitives, composition, abstraction.
- Data types: numbers, booleans, characters, strings, symbols.
- Compound data types:
- Lists
- Vectors: (vector 1 2 3), #(1 2 3) /
Heterogeneous, random-access (like arrays and like records).
- Procedures: (lambda (x) x)
- First-class procedures:
- lambda: anonymous procedures
- map, for-each
- closures
- cell object
Inductive Specification of Data
- Backus-Naur Form: list of numbers
- Deriving program from BNF specification: list-of-number?
- Context-sensitive specification: binary-search-tree?
- Using BNF specification for processing: remove-first, subst
Example: Syntax and properties of lambda calculus expressions
- lambda calculus syntax
- Free and bound variables
- Renaming variables: alpha conversion
Syntactic Abstraction
- Definition of let with lambda.
- Definition of and and or with if.
- Abstract data types: define-datatype, cases.
- Representation of abstract syntax with abstract data types: BNF for lambda
calculus, parse on lists.
- Parsing with sllgen.
Last modified 23 Feb 2003
Michael Elhadad