MASSACHVSETTS INSTITVTE OF TECHNOLOGY

Department of Electrical Engineering and Computer Science

Subject Offering: Spring 2006

Adventures in Advanced Symbolic Programming

6.891

3-0-9, Grad H Level, AI Concentration

Chris Hanson, Gerald Jay Sussman, Jack Wisdom

We will investigate advanced techniques useful for programming symbolic systems, such as compilers, computer- algebra systems, theorem provers, and some artificial intelligence applications. Although these techniques were developed for Artificial Intelligence programming, they are applicable to a wide range of topics in mathematics, science, and engineering. Topics covered will include Pattern-match/substitution systems, Dependencies and Dependency Analysis, Constraint Propagation, and Derivational (Rule-based) systems. Topics will be chosen dynamically, based on student and faculty interest. Typical topics include:

• Control structure and continuations
• Embedded languages, levels of language
• Interpreted language levels
• Methods of organizing generic operations that extend primitives
• Canonical Forms and Memoization
• Dependency structures and Truth-Maintenance Systems
• Constraint Propagation
• Pattern-directed invocation
• Pattern match and substitution
• Unification and Logic

There will be extensive programming assignments, using MIT/GNU Scheme. The assignments may expand the state of the art in system architecture and software engineering. Students should have significant programming experience in Scheme or Common Lisp.

This subject awards H-LEVEL Graduate Credit, applicable to the AI Engineering Concentration. However, the subject is appropriate for undergraduates who have taken the prerequisites. Undergraduates are welcome.

Prerequisites: 6.001, 6.034, mathematical sophistication.

Time: MWF 1:00PM–2:00PM Room: 24-307

Red Tape Memo

Assignments

Request for proposals for term papers

Project Reports

To get the software used in this class go here.

Here is SICP online:

6.001 Book (HTML)

Here is the MIT/GNU Scheme documentation.

Here is some code that has been used in examples in class.

Notes

• The paper referred to in class today (2006-02-21) is Efficient Method Dispatch in PCL.
• John Kraemer has put up a useful page of material related to this class.
• David Glasser asked about a paper on unification with segment variables. Here is a link.
• Anyone who is seriously interested in unification should read the wonderful paper by Alberto Martelli and Ugo Montanari, entitled "An Efficient Unification Algorithm," in ACM Transactions on Programming Languages and Systems, Vol. 4, No. 2, April 1982, pp.258--282. Their algorithm, although excellent, is extremely long and presented in Pascal.