DOCUMENTATION FOR THE MIT SCHEME PROBLEM SET DATABASE VERSION 1.0 April 11, 1990 **************************** DISCLAIMER ***************************** * * * The problem sets in this database are offered to the public * * on an "as is" basis only. The problem sets were developed * * over a number of years using different versions of Scheme * * and a variety of text formatters. We do not guarantee that * * the problem sets are bug-free or that the code will work for * * your particular version of Scheme. Be forewarned that * * adapting these problem sets to your particular computational * * and educational environments may require significant time * * and effort. * * * ********************************************************************* I. INTRODUCTION This directory contains problem sets used for the Structure and Interpretation of Computer Programs, an MIT course (6.001) based on Abelson, Sussman, and Sussman's book by the same name. 6.001 uses Scheme, a dialect of Lisp, as a vehicle for exploring methods for controlling the complexity of large systems. The course covers a broad range of concepts, including first-class procedures, procedural abstraction, data abstraction, modularity and state, and metalinguistic abstraction (interpretation & compilation); it also introduces a wide range of programming paradigms: functional programming, imperative programming, object-oriented programming, logic programming, and assembly-level programming. 6.001 is the Electrical Engineering and Computer Science Department's core course in computer science; it is required of all undergraduates in EECS, but is also popular among undergraduates in other departments and graduate students as well. During each week of the 14-week course, students attend two lectures, two recitations, and one tutorial (led by a graduate teaching assistant). In addition, during the course of the term, the students are assigned 10 problem sets that give them "hands on" experience with the key concepts of the course. Students work on the problem sets in a staffed 24-hour computer laboratory equipped with with 48 HP-9836 (Chipmunk) machines. Since the class size tends to be large (~ 250 students in the Fall term and ~ 450 students in the Spring), the lab is almost always bustling with activity. This directory contains almost all of the problem sets used in 6.001 since it began using Scheme in Spring 1981. Many problem sets have been used multiple times with variations in the assigned textbook exercises and/or the questions for laboratory. In this cases, only the most recent version of the problem set appears in this directory. (Sometimes, however, significant variations are also included.) This directory is public. You may use all of the material contained in this directory for any non-commercial purpose as long as you follow the guidelines outlined in the copyright notice below. A copy of this notice is prepended to each of the files in the directory. +--------------------------------------------------------------------------+ | Copyright (c) 1990 Massachusetts Institute of Technology | | | | This material was developed by the Scheme project at the Massachusetts | | Institute of Technology, Department of Electrical Engineering and | | Computer Science. Permission to copy this material, to redistribute | | it, and to use it for any non-commercial purpose is granted, subject | | to the following restrictions and understandings. | | | | 1. Any copy made of this material must include this copyright notice | | in full. | | | | 2. Users of this material agree to make their best efforts (a) to | | return to the MIT Scheme project any improvements or extensions that | | they make, so that these may be included in future releases; and (b) | | to inform MIT of noteworthy uses of this material. | | | | 3. All materials developed as a consequence of the use of this | | material shall duly acknowledge such use, in accordance with the usual | | standards of acknowledging credit in academic research. | | | | 4. MIT has made no warrantee or representation that this material | | (including the operation of software contained therein) will be | | error-free, and MIT is under no obligation to provide any services, by | | way of maintenance, update, or otherwise. | | | | 5. In conjunction with products arising from the use of this material, | | there shall be no use of the name of the Massachusetts Institute of | | Technology nor of any adaptation thereof in any advertising, | | promotional, or sales literature without prior written consent from | | MIT in each case. | +--------------------------------------------------------------------------+ We make no claims that the problem sets in this directory are without errors. They have been assembled from a wide variety of sources and have not been tested. The problem sets have been created over a span of ten years using many different versions of Scheme and many different text formatters. Many of the problem sets were formatted using YTEX, an MIT-specific version of TEX; we do not supply the YTEX macros. Also, the problem sets often contain various references to MIT and the local environs. All this means that if you plan to use the materials here, you better be willing to invest a fair amount of time adapting the text and code to your particular environment. Since this directory is publicly accessible, we do not provide solutions to the problem sets. We do not have the manpower to answer detailed questions about the text or code of the problem sets. However, if you notice what you think are major bugs --- missing files, missing code, obviously buggy code, etc. --- then please send a message to the Scheme problem set librarian: Franklyn Turbak lyn@zurich.ai.mit.edu We also will accept submissions of Scheme problem sets from other sources. These will be filed and catalogued in the subdirectory ../other . *************************************************************************** II. ORGANIZATION OF THE DIRECTORY This directory is divided into subdirectories of related problem set materials. Each subdirectory usually contains one problem set, although in some cases where different problem sets share code, (the metacircular evaluator; the query language), multiple problem sets cohabit the same subdirectory. The basic content of each problem set is described in the catalogue below. The problem sets are ordered by the material they cover; those appearing earlier in the list are offered earlier in the course. A problem set usually consists of at least two files. The .TXT or .TEX file contains the text of the problem set while the .SCM file contains the Scheme code for the problem set. In some cases, the code is split up into several files. Sometimes a .MOD file is included; this is generally a subset of the Scheme code that the student is intended to modify. A .DAT file is a database to be used in a query language problem set. In a few instances, the same file is used in multiple problem sets; for example, the same query-language interpreter is used for several problem sets. In addition to the problem sets, there are some other files and directories: * chrono-hist.txt - A file detailing the history of problem set usage in 6.001 * formatting - A directory containing a few Scribe and TEX macro files that are used by various problem sets. * other - A directory of Scheme problem sets not developed at MIT * parallel.tex - Nikhil's "Structure and Interpretation of Parallel Computer Programs." * subst.tex - A description of the Revised Substitution Model *************************************************************************** III. PROBLEM SET OVERVIEW Problem sets are an integral part of 6.001. They typically consist of a non-trivial program that the student must understand and extend. Thus, students are never asked to write entire programs from scratch, although they may be asked to design and implement major modifications to a program. There are ten problem sets assigned per term. Students are usually given one week to complete a problem set, though for more difficult ones (e.g. metacircular interpreter problem sets) they may be given two weeks. The following list organizes the problem sets in categories according to the subject matter that they cover. One problem set is usually assigned from each category, although sometimes some categories will be skipped while others will yield more than one problem set. The parenthesized date after a problem set name indicates the last term that the problem set was used in 6.001. See the file chrono-hist.txt for examples of how these problem sets have been used in various terms at MIT. 1. Introductory (Introduction to the computational environment; simple procedures) Epicycloids and Hypocycloids (Fall '89) Snowflake/Debugger/Revised Substitution (Spring '89) Fractal Curves [C-Curve + some nice extra problems] (Fall '88) Wondrous Numbers (Spring '88) Cardioids And Nephroids/Debugging (Fall '87) C-Curve/Debugging (Spring '87) Lissajous Figures (Fall '85) 2. Advanced Procedural (higher-order procedures) Pascal's Triangle/Smoothing (Fall '89) Continued Fractions (Spring '89) Hi-Lo (Fall '88) RSA Cryptography (Fall '87) Primality Testing (Fall '86) 3. Simple Data + Higher Order Procedures Prisoner's Dilemma - Version 2 (Spring '88) Prisoner'S Dilemma - Version 1 (Fall '87) Henderson Language - Circle (Fall '87) Henderson Language - Triangles (Spring '87) Lunar Lander (Fall '84) (uses simple list structure) Twenty-One (Spring '83) (uses simple list structure) 4. Compound Data and Data Abstraction Stargazing (Fall '89) All-Nighter Sweepstakes (Fall '89) Navigation (Spring '89) Freshman Advisor (Spring '89) Food For Thought (Fall '88) Data Abstractions (Spring '88) Geometry Data Abstraction (Spring '87) Doctor (Fall '86) N-body Simulator (Spring '83) Huffman Encoding Trees (Fall '82) Interval Arithmetic (Spring '82) Graphs: Finding Your Way Around Cambridge (Fall '81) 5. Generic Operators Series-Parallel Resistive Networks + Automatic Resonance Finding & Circuit Generation (Fall '89) Rational Functions (Spring '89) Airline Mergers (Spring '88, [Fall '87]) Series-Parallel Resistive Networks w/Message Passing Part (Spring '87) Series-Parallel Resistive Networks + General Networks (Spring '86) 6. Objects with State and Message Passing Adventure Game - Traditional Message-Passing Version (Fall '89) Adventure Game - Object-Oriented Language Version (Spring '89) Signal Processing Language (Spring '88) Mutable Data (Spring '88) Mobot (Fall '87) Student Data Base - Tables (Spring '87) State Exercises (Spring '86) Simulation of a Queueing System (Spring '86) Deques (Fall '85) 7. Streams Heartbeat Regularity Monitoring (Fall '89) Streams of Pairs (Spring '89) Representing Signals As Streams (Spring '88) Power Series/ Integration (Spring '87) Power Series (Fall '86) Stream Exercises (Fall '84) 8. Metacircular Evaluator Paranoid Programming/Pascheme (Fall '89) Metacircular Evaluator Extensions (Spring '89) Normal Order Evaluator [Also Check Fall 88 version] (Fall '86) Partial Evaluation (Spring '84) (actually does not use metacircular evaluator per se) 9. Query Language Student Database - Query Language (Spring '89) IBM-Database/Sentence Generation (Spring '88) Hiring Database - Query Language (Fall '87) Sentence Generator (Query Language) + Metacircular Evaluator Extensions (Spring '87) Logic-Programming - Circuit Recognition (Fall '86) Logic Puzzles (Spring '85) Query Language - IBM Database (Spring '84) 10. Register Machine Simulator/ Explicit Control Evaluator/ Compiler Register Machine Simulator/ Explicit Control Evaluator (Fall '89) Compiler/Parallel Scheme (Fall '89) Register Machine Simulator/ Explicit Control Evaluator - List Reversal + Order of Evaluation/ Compiler (Optional) (Spring '89) Register Machine Simulator/ Explicit Control Evaluator/Tracing (Fall '88) Compiler/Hand-Coding (Spring '88) *************************************************************************** IV. PROBLEM SET CATALOGUE The following catalogue contains a brief description of the problem sets in the database. Not all problem sets or variations listed in the overview from Section III have actually been entered into the database, but most of them are there. Ideally, a problem set description contains: * The name of the problem set * A description of its contents * A description of the course materials it covers * A list of the files it uses * The history of the problem set (who created it, who modified it, etc.) * Notes about using or improving the problem set However, many descriptions are missing much of this information. In addition, some of the notes (especially particulars about improving problem sets) are outdated and may not accurately reflect the current state of the problem set. So the descriptions below serve only as a rough guideline for finding problem sets that you might be interested in. For more detail, you must actually take a look at the problem set files themselves. The file names used in this directory do not necessarily match the file name references that appear within the text of the problem sets. In the descriptions below, "text" refers to Abelson, Sussman, and Sussman, STRUCTURE AND INTERPRETATION OF COMPTUER PROGRAMS; "manual" refers to Sussman, Abelson, Sussman, INSTRUCTOR'S MANUAL TO ACCOMPANY STRUCTURE AND INTERPRETATION OF COMPTUER PROGRAMS. This catalogue was originally created in 1985 by Julie Sussman. Since then it has been updated by Franklyn Turbak. ---------------------------------------------------------------------- DEBUGGING LESSON Content: This is not really a problem set in itself, but is usually included with the first problem set (such as EPICYCLOIDS, LISSAJOUS, or C-CURVE) to introduce students to the debugging facilities of the machine. Files: debug\debug.scm debug\debug.txt Comments: These exercises were designed for the Scheme system running on the HP Chipmunk computers in the MIT Undergraduate computer lab. ---------------------------------------------------------------------- EPICYCLOIDS AND HYPOCYCLOIDS Content: A program to draw epicycloids and hypocycloids. Prerequisites: section 1.1 Course Material: Introduces students to the text editor and interpreter. Files: (from Fall 89) cycloid/cycloid.tex Notes: Generally includes debugging material as well (above). Used as problem set: Fall 1989, PS1 Spring 1985, PS1 To fix: The hypocycloid equation was wrong, and the txt file has been edited to correct it (the two terms for y(t) in the correct equation are combined with +, in the incorrect version with -). You must either restore the equation to its incorrect state or revise problems 5 and 6 to have different parameters and symmetries. (Note: The figures obtained in 5 are not very interesting with the correct equation. 6 is completely different.) Criticism: Problem 8 and ex1.2a encourage internal definitions other than procedure definitions. There is some reason to suspect that this leads students who have programmed to think of Define as set! and encourages an imperative style. You probably should outlaw internal definitions other than procedures, and show people examples of how to get the same effect (of computing something only once) by using auxiliary procedures. ---------------------------------------------------------------------- LISSAJOUS FIGURES Content: A program to draw a Lissajous figures. Prerequisites: section 1.1 Course Material: Introduces students to the text editor and interpreter. Files: (from Fall 84) lissajous/lissajous.txt Notes: Generally includes debugging material as well (above). History: ??? Used as problem set: Fall 1985, PS1 Fall 1984, PS1 Spring 1984, PS1 Fall 1983, PS1 Variations: Other terms varied numbers: part 4, f2=8; part 7, f2=1) ---------------------------------------------------------------------- C-CURVES Content: A program to draw a fractal C-curve. Prerequisites: section 1.1 Course Material: Introduces students to the text editor and interpreter. Files: (from Fall 1986) c-curve/c-curve.scm c-curve/c-curve.tex Notes: Generally includes debugging material as well (above). History: ??? Used as problem set: Fall 1986, PS1 ??? ---------------------------------------------------------------------- CARDIOIDS Content: A program that draws cardioids and nephroids as the envelopes of sets of circles. Prerequisites: section 1.1 Course Material: Introduces students to the text editor and interpreter. Files: (from Fall 87) cardioid/cardioid.tex Notes: Generally includes debugging material as well (above). History: Written by Ruth Shyu. Used as problem set: Fall 1987, PS1 ---------------------------------------------------------------------- PASCAL'S TRIANGLE/ SMOOTHING Content: Pascals triangle; smoothing of data. Course Material: Procedures, order of growth, higher-order procedures. Files: (from Fall '89) pascal/pascal.tex pascal/pascal.scm ---------------------------------------------------------------------- HI-LO Content: Playing the hi-lo guessing game representing strategies as procedures. Course Material: Higher-order procedures, order of growth Files: hi-lo/hi-lo.tex hi-lo/hi-lo.scm ---------------------------------------------------------------------- PRIMALITY TESTING Content: Probabilisitic testing for primality (based on text section 1.2.6 and exercises 1.16 - 1.21). Looks at Mersenne primes. (Also see manual sections 1.2.6, 1.3.1) Prerequisites: Chapter 1 Course Material: Procedures, order of growth, higher-order procedures. Files: (from Spring 1985) primes/primes.txt primes/primes.scm History: ??? Used as problem set: Fall 1985, PS2 Spring 1985, PS2 Fall 1983, PS2 Spring 1983, PS1 Fall 1982, PS1 Spring 1982, PS1 Fall 1981, PS1 Variations: can be varied by changing numbers in exercises 1.16, 1.17, 1.19 (see, for example, all the above terms except Fall 1981). ---------------------------------------------------------------------- RSA CRYPTOGRAPHY SYSTEM Content: The RSA encryption algorithm, making use of the primality material in section 1.2.6. Prerequisites: Chapter 1 Course Material: Procedures, order of growth, higher order procedures. Files: (from Fall 87) rsa/rsa.tex rsa/rsa.scm History: Written by Ruth Shyu. Theory taken from Arthur Mattuck's 18.063 course notes on the RSA Cryptography system, which was developed by Rivest, Shamir, and Adelman. Used as a Problem Set: Fall 1987, PS2 ---------------------------------------------------------------------- LUNAR LANDER Content: A simple game in which the player tries to land a spaceship through the controlled burning of a limited amount of fuel. Prerequisites: Assignment says reading is through chapter 1, but programs use stuff through 2.2.3 (lists & symbols)! Course Material: Higher-order procedures (procedures as both parameters and returned values) Files: (from Fall 1984) lunar/lunar.txt lunar/lunar.scm lunar/lunar.mod History: ??? Used as problem set: Fall 1984 PS2 Spring 1984 PS2 Fall 1982 PS2 Comments: Dependence on 2.2.3 can be removed as follows: - Change symbols in Show-ship-state to strings; - Flush symbols from End-game (either replace them with some other value, such as t, or omit them and let End-game have a nonprinting value). But even if you don't want to remove dependence on 2.2.3, you might want to change these symbols to strings, as the mixture of strings and symbols is probably confusing. Dependence on 2.2.1 can be sort of removed as follows: - Change Show-ship-state to Princ the separate items rather than to make a list and print it. But note that there are no examples of compound data objects with more than two components until 2.2.1, and no examples of car/cdr composition until 2.2.1 -- so problem 1 will be quite difficult. Corrections and criticisms: - Exercise 3: "...to get the new BURN RATE." (not "state") - Exercise 5: "For example, [running] (play...) should USE a strategy..." (delete "running", change "result in" to "use") - Terminology in ex 4-6 is very confused "higher level strategy", "compund strategy", "strategy". Actually, aren't most of the procedures here "strategy constructors"? - I didn't understand how velocities were measured (i.e., that positive velocities are up, hence that we want a negative velocity with small absolute value), hence thought the crash test in End-game was backwards. That is, I thought you should crash if your velocity was too large, not it it was too small. - I was thoroughly confused by ex.9 and the preceding paragraph. ---------------------------------------------------------------------- INTERVAL ARITHMETIC Content: Interval arithmetic, based on text section 2.1.4 Prerequisites: Section 2.1.4 Course Material: Data abstraction. Files: interval/interval.txt interval/interval.scm interval/interval.mod History: ??? Used as problem set: Spring 1982, PS3 Fall 1981, PS2 Comments: **Should add (supply and/or assign) interval printers as in manual section 2.1.4. **See comments in front of TXT file for other things to fix up. ---------------------------------------------------------------------- TWENTY-ONE CARD GAME Content: Strategies for playing the card game twenty-one. Prerequisites: section 2.2.1. Course Material: lists, data abstraction, higher-order procedures. Files: ??? twenty-one\twenty-one.scm Note: A newer version of the problem set text appears in Section 6.1 of the Instructor Manual History: ??? Used as problem set: Spring 1983, PS2 ---------------------------------------------------------------------- HENDERSON'S ESCHER PICTURE LANGUAGE - SQUARES Content: A version of Peter Henderson's "Escher Square-Limit Language", in which pictures are represented as procedures that "draw themselves" on the screen. Note: This is not a problem set as is, but is included as background and an example for the TRIANGLES and CIRCLES versions of the Henderson language below. In 6.001, one lecture is usually devoted to this material. Files: escher\sq-limit.tex escher\sq-limit.scm History: ??? ---------------------------------------------------------------------- HENDERSON'S ESCHER PICTURE LANGUAGE - TRIANGLES Content: A version of the Henderson "Escher Square-Limit" picture-drawing language in which pictures draw themselves in triangles rather than rectangles. Prerequisites: 2.2.2? (Maybe just 2.2.1. Though there are lists of lists, we deal with hierarchical data, not tree-structured data.) Course Material: Higher-order procedures, data abstraction. Files (from fall85): escher\tri-limit.txt escher\tri-limit.scm Note: The SQUARES version of the Henderson language is usually included with this problem set. History: ??? Used as problem set: Fall 1985, PS3 Fall 1984, PS3 Spring 1984, PS3 Fall 1983, PS3 Variations: Fall 1983, PS3 Parts 4-8 provide alternatives Comments (from Julie): These are notes I wrote in 11/84 based on reading the Henderson problem set. I have not run it (but sure would like to!). General remarks Uses multi-level data abstraction. Students must follow it but not do any work with data abstraction. Main subject of exercises is higher-order procedures. Requires you to be comfortable with vector addition and subtraction. Difficult: There is a lot to understand and heavy use of higher-order procedures. There is too much emphasis on vector geometry at the expense of 6.001 material. In particular, parts 3 and 5 are hard because they require understanding the coordinate system and vector manipulations. Although this is not relevant to the kinds of things you are trying to teach (data abstraction, higher-order procedures, etc.), it no doubt absorbs much of one's mental capacity. If you fail to do 3, you cannot test 4 or 6. If you fail to do 5, you cannot test 6 or 7. It would be better to supply the answers to 3 and 5 in the writeup. Then this would become a higher-order-procedure problem set rather than a vector-geometry problem set. ****I supplied partial answers to 3 and 5 in the fall85 version. But we may wish to simplify this further.--HAL*** You could then add some problems about data abstraction. For example, let the students write (or replace) some of the selectors/constructors that are currently supplied -- e.g., for picture, vector, point, segment.*****Added to fall 85 version--HAL** Some detailed comments Things used in programs that are not explained: FIRST, SECOND, THIRD (though later uses CAR, CADR, etc.) MAPC Students have trouble with the transformation model (how to rotate pictures, etc.) ---------------------------------------------------------------------- HENDERSON DRAWINGS - CIRCLES Content: A version of the Henderson "Escher Square-Limit" picture-drawing language in which pictures draw themselves in circles rather than rectangles. Prerequisites: 2.2.2? (Maybe just 2.2.1. Though there are lists of lists, we deal with hierarchical data, not tree-structured data.) Course Material: Higher-order procedures, data abstraction. Files (from Fall 87): escher\circ-limit.txt escher\circ-limit.scm Note: The SQUARES version of the Henderson language is usually included with this problem set. History: Written by Ruth Shyu. Variation of the Henderson Square-limit language. Used as problem set: Fall 1987, PS3 Comments: See comments for TRIANGLES version of the Henderson language above. ---------------------------------------------------------------------- STAR GAZING Content: A simple pattern-based recognition system, based on Eric Grimson's RAF. Files: stars/stars.tex stars/stars.scm stars/fig1.ps History: Originally written by Eric Grimson; modified by GJS. ---------------------------------------------------------------------- ALL-NIGHTER SWEEPSTAKES Content: A simple relational database. Files: all-nighter/all-nighter.tex all-nighter/all-nighter.scm ---------------------------------------------------------------------- DATA ABSTRACTION FACILITY Content: Explores a means of facilitating the making of data abstractions. Prerequisites: Section 2.1 and 2.2 Course material: Data abstraction, higher-order procedures Files: (from Spring 1988) abstract\abstract.txt abstract\abstract.scm History: Written by Rod Brooks. Used as Problem Set: Spring 1988, PS3 ---------------------------------------------------------------------- HUFFMAN ENCODING Content: Huffman variable length encoding, based on text section 2.2.6. Prerequisites: Section 2.2.6 Course Material: Data abstraction, list and tree manipulation. Files: (from Fall 83) huffman\huffman.txt huffman\huffman.scm History: ??? Used as problem set: Fall 1983, PS4 Fall 1982, PS3 Spring 1982, PS4 ---------------------------------------------------------------------- FOOD FOR THOUGHT Content: Manipulations of a database of food ingredients. Course Material: Data structures, functional style (map, filter, accumulate) Files: food/food.tex food/food.scm ---------------------------------------------------------------------- DOCTOR Content: A simple Eliza-like software psychologist, based on Section 6.5 in the Instructor's Manual. Prerequisites: 2.2.3 Course material: symbol-manipulation, list manipulation. Unlike the symbolic-differentiation program of section 2.2.4, it does not illustrate data abstraction or deal with tree-structured data. Files: (from Fall 85) doctor\doctor.txt doctor\doctor.scm Notes: DOCTOR.TXT differs from the manual in that it is problem-set-ified History: ??? Used as problem set: Fall 1985, PS4 Spring 1985, PS3 Fall 1984, PS5 Fall 1981, PS3 ---------------------------------------------------------------------- PARTIAL EVALUATOR Content: A simple partial evaluator that performs simple source-to-source transformations to a subset of Scheme code. Prerequisites: Section 2.2 Course Material: List manipuation, symbol manipulation; evaluation. Files: (from Spring 1984) partial\partial.txt parital\partial.scm History: Written by Dave Gifford. Used as a Problem Set: Spring 1984, PS4 Comments: Deals with some potentially difficult material (representing code as lists, writing an evaluator of Scheme *in* Scheme) perhaps too early in the course. Might be more suitable to use an extended version of this problem set after the metacircular interpreter has been introduced. ---------------------------------------------------------------------- PRISONER'S DILEMMA Content: Experimenting with the well-known "prisoner's dilemma" situation in game theory. Includes a three-person prisoner's dilemma contest. Prerequisites: Chapter 2, sections 2.1 and 2.2 Course Material: Higher-order procedures, list manipulation, symbolic data. Files: (from Fall 87) dilemma\dilemma.txt dilemma\dilemma.scm (Note: an slightly different version of the problem set is in the files dilemma\dilemma2.txt dilemma\dilemma2.scm ) History: Written by Mike Eisenberg and Mitch Resnick Used as problem set: Fall 1987, PS4 Spring 1988, PS4 Comments: The three-person prisoner's dilemma tournament suggested at the end of the problem set is a lot of fun. Write to duck@zurich.ai.mit.edu or lyn@zurich.ai.mit.edu for the software to run the tournament and analyze the results. ---------------------------------------------------------------------- SERIES-PARALLEL CIRCUITS Content: Modelling of resistive electrical elements, including resistors, capacitors, and inductors. Prerequisites: section 2.3.2 Course material: Like section 2.4.1, it illustrates operations that are generic over different kinds of operands (in this case, operations on circuits). It uses the manifest-type conventions of section 2.3.2. Note that the complex numbers used here do not have manifest type. They are actually plain old rectangular numbers, with all operations in terms of rectangular coordinates. Perhaps the procedure names should be changed to be different from the book? Part 2 deals with higher-order procedures. Files: (from Fall '89) circuit/circuit.tex circuit/resistance.scm circuit/impedance.scm circuit/graph.scm Notes: Manual section 6.6 is part 1 of this problem set, modified as described under TO DO below. History: ??? Used as problem set: Fall 1986, PS5 Fall 1985, PS5 Spring 1985, PS4 Fall 1984, PS4 Variations: Can change the resistances in the sample resistive network. (e.g., see fall 1984) ---------------------------------------------------------------------- GENERIC ARITHMETIC Content: Generic arithmetic with rational functions (quotients of polynomials), based on text section 2.4.3. Prerequisites: Section 2.4 Course Material: Generic operators, list manipulation. Files: (from Spring 1985) generic-arith/generic-arith.txt generic-arith/generic-arith.scm History: ??? Used as Problem Set: Spring 1985, PS5 Spring 1984, PS5 Fall 1983, PS5 Comments: Students commonly forget to reinstall procedures into the operator table after they change them. This is not surprising, since they have not yet been introduced to the notion of state and its associated confusions. They should probably be explicitly warned about this scenario. ---------------------------------------------------------------------- AIRLINE MERGERS Content: Using generic operators to merging three airline databases with different representations. Prerequisites: Section 2.3 Course Material: Generic operators Files: air/air.tex air/air.scm History: Written by Ruth Shyu. Based on recitation notes by Al Oppenheim. Used as Problem Set: Spring 1988, PS5 Fall 1987, PS5 Comments: This problem set has some very ugly code and should be extensively modified before being used again. ---------------------------------------------------------------------- N-BODY SIMULATION Content: Simulation of the dynamics of N particles under the influence of Newtonian gravitation. Prerequisites: section 3.3.1 (objects are mutable list structure, not procedures; no message passing, no set!) Course Material: Mutable data. Files: nbody/nbody.txt nbody/nbody-3vec.scm nbody/nbody-iter.scm nbody/nbody-feyn.scm nbody/nbody-grav.scm Notes: The files are from spring83, updated to follow the current naming conventions for set-...! rather than set!-... History: ??? Used as problem set: Spring 1983, PS4 Criticisms: - Either explain things well or don't explain them at all. Make it clear what students do/don't have to understand. As it is now, it's pretty incomprehensible. - Break down problem 4 into parts? mapcar over 2 lists, max of a list, ... (see problem 4 comments in nbody-ans.scm) - Problem 4: People need a way to test D to see if it is working. Tell them what answer it should give for one or two of the cases they're supposed to run. - Also see comments with ** in nbody.out ---------------------------------------------------------------------- MUTABLE DATA Contents: Uses an "instrumented" version of CONS, SET-CAR!, and SET-CDR! to compare the space utilization of purely functional and side-effecting versions of various programs. Prerequisites: Section 3.3 Course Material: Mutable data Files: mutable.tex mutable.scm History: Written by Rod Brooks (???) Used as Problem Set: Spring 1988, PS7 ---------------------------------------------------------------------- DEQUES Content: Designing and implementing double-ended queues for which all operations can be performed in O(1) time (based on text exercise 3.2.3). Prerequisites: section 3.3.1, 3.3.2 Course material: Mutable list structure Files: deque/deque.txt (no code file) History: ??? Used as problem set: Fall 1985, PS6 Comments: OK, but probably should be extended and rewritten to include an application of deques, rather than just asking students to implement them. ---------------------------------------------------------------------- ADVENTURE Content: An Adventure-like game in which the goal of a player is to successfully move through MIT to hand in a problem set without losing it or getting eaten. Prerequisites: section 3.2, (3.3 for other examples of simulation with message passing) Course material: simulation, procedures with local state, message passing. Files: (from Spring 85) adventure.txt adventure.scm adventure.mod History: ??? Used as problem set: Fall 1985, PS7 Spring 1985, PS6 Fall 1984, PS6 Fall 1983, PS6 Spring 1983, PS5 Fall 1982, PS5 Comments: The files are from Spring 1985, PS6. Changes are: -References to file names have been changed. -Make-person edited so that TAKE only works for THINGs. THING? predicate added for use by Make-person. For some other ideas on things to do in the game, see Spring 1983. To do: It has been suggested that instead of all the internal dispatch procedures for Person, Troll, and Dean being called ME, they should each have a mnemonic name. This is already true for Place and Thing, whose procedures are named Here and Object. ---------------------------------------------------------------------- MOBOTS Content: Software to control mobile robots enlisted as members of the campus security force. Prerequisites: Section 3.1 and 3.2 Course Material: Objects with state, mutable data, message-passing. Files: (from Fall 1987) mobot\mobot.tex mobot\mobot.scm mobot\mobot.mod History: Written by Ruth Shyu. Based on a Fall 1986 quiz written by Gerry Sussman. Used as a Problem Set: Fall 1987, PS6 Comment: Students complained that the internal representations of the mobots' maps were hard to understand. ---------------------------------------------------------------------- QUEUE SIMULATION Content: Simluations to compare strategies for servicing lines (queues) of people be Files: queue-sim/queue-sim.tex queue-sim/queue-sim.scm ---------------------------------------------------------------------- STREAMS AND DELAYED EVALUATION Content: Exercises manipulating streams of numbers (plotting them, integrating them, etc). Prerequisites: Section 3.4 Course Material: Infinite streams, delays. Files: (from Fall 1984) stream\stream.txt stream\stream.scm stream\stream.mod History: ??? Used as a Problem Set: Fall 1984, PS7 Spring 1984, PS6 Fall 1983, PS7 Variations: See Spring 1984 PS6 & Fall 1983 PS7 for some different numbers and equations) ---------------------------------------------------------------------- ORDERED STREAMS OF PAIRS & RAMANUJAN NUMBERS Content: First explores the generation and merging of order streams of pairs, and then uses order streams of pairs to generate Ramanujan numbers. Prerequisites: 3.4.5 Course material: Infinite streams Files: (from Spring 1985) ramanujan\ramanujan.txt ramanujan\ramanujan.scm History: A version of this problem set appears as Section 6.9 in the Instructor's Manual. Used as problem set: Fall 1985, PS8 Spring 1985, PS7 Comments; The above files, derived from Spring 1985 PS7, have been edited to use List rather than Cons to construct the pairs (as in the manual). Also, a new set of Ramanujan-number exercises has been added at the end. The problem set differs from the manual section in that: it is problem-set-ified; the early part (merge, etc.) incorporates stuff that is in the book and manual. ---------------------------------------------------------------------- HEARTBEAT REGULARITY MONITORING Content: Signal processing of a time-encoded signal (a heartbeat) using streams. Prerequisites: Section 3.4 Course Material: Streams, higher order procedures. Files: (from Fall 1987) heartbeat\heartbeat.txt heartbeat\heartbeat.scm heartbeat\plotizing.txt heartbeat\README Note: heartbeat\README contains a number of comments for improving the problem set. History: Originally written by Ruth Shyu; modified by GJS. Used as a Problem Set: Fall 1989, PS7 Fall 1987, PS7 ---------------------------------------------------------------------- METACIRCULAR EVALUATOR Content: The metacircular evaluator from text section 4.1. This is not a problem set in itself, but is used with any problem set on the metacircular evaluator. Files: (Specific problem sets usually have additional files) metacircular/mceval.scm metacircular/mceval.txt (documentation) Notes: For information on how this file relates to the book, see the comments in the code files (and also see MCEVAL.TXT) History: ??? ---------------------------------------------------------------------- PARANOID PROGRAMMING & PASCHEME Content: "Paranoid programming" in a "Pascalish" version of Scheme in which procedures have typed arguments and return values. Prerequisites: Section 4.1 Course Material: Metalinguistic abstraction, interpretation. Files: metacircular/pascheme.txt metacircular/paranoid.scm metacircular/pascheme.mod metacircular/mceval.scm History: Based on the Fall 1982 final exam. A version of this problem set appears in Section 6.10 of the Instructor's Manual. Used as problem set: Fall 1989, PS8 Spring 1985, PS8 Fall 1983, PS8 Comments: The files are from Spring 1985. Nothing has been changed except (1) file names (in text and comments) (2) typo or two (3) the wording of the exercise about parsing DEFINE (it contrasted "defining a simple variable to have a value" with "defining a new compound procedure" -- gibberish) To fix: - Footnote on essay question refers to lecture on Halting Theorem, but there was no such lecture when this was assigned. - In apply-unary-predicate-symbol, could use User-initial-environment (which is in the book) instead of (The-environment). Is either choice more machine-dependent than the other? Also: The file pascheme.old contains some stuff from the Fall 1983 problem set that was not retained but might lead to something. See the comments at the front of that file. ---------------------------------------------------------------------- NORMAL-ORDER EVALUATION Content: Modifying the interpreter in section 4.1 to be normal order rather than applicative order. Based on text section 4.2.1. Prerequisites: Sections 4.1, 4.2.1 Course Material: Metalinguisitic abstraction, interpreters, normal order vs. applicative order, thunks. Files: metacircular/normal-ord.txt metacircular/normal-ord.mod metacircular/mceval.scm History: ??? Used as problem set: Fall 1985, PS9 Fall 1984, PS8 Spring 1984, PS7 Fall 1982, PS7 Spring 1982, PS9 Comments: (from Julie) The TXT file is an updated version of the Fall 1984 file, which had not been correctly updated to match the book. The Fall 1985 version includes an additional problem that covers the same idea as exercise 4.14. However, this refers to a previous exercise in the Ramanujan problem set. **You may have to fix up the MODS file, as follows: (1) I simply replaced the obsolete procedures in the mods file with new versions of the same things. Didn't check that these are indeed the procedures needed. (2) In the lab copy of the mods file, the WARNING was deleted. Perhaps that means it should be deleted. There are many ways to do this lab -- different places in the evaluator to create and force thunks. The book only hints at what to do, does not hold people's hands. Perhaps, as in the Pascheme lab, you should try to include in the mods file a superset of the procedures to modify, and explicitly say so in the text? ---------------------------------------------------------------------- QUERY LANGUAGE Content: A modified version of the query language interpreter presented in text section 4.4. It is not a problem set in itself, but must be loaded with any problem set on the query language. Files: (Specific problem sets usually have additional files) query/query.scm query/query-comp.txt query/query-driv.txt query/query-edit.txt query/query-data.txt (note: the reference in here to the mods file should be fixed somehow.) Comments: (From Julie) The SCM file contained compiler declarations. These prevent the SCM file from loading into Chipmunk Scheme, so I commented them out; if you need them, just reinstate them. Code status: Bugs fixed on 20, 7/6/85. Edits transferred to Chipmunk version. **not tested on Chipmunk** Also: in Chipmunk version, there's a commented-out copy of contract-question-mark and a temporary version; must change HP scheme before can switch versions. **Freefor? changed 12/1/85. Should use latest version. ---------------------------------------------------------------------- IBM DATABASE Content: Playing with the query system on a database of the Itsey Bitsey Machine Corporation. Based on exercises from text section 4.4. Prerequisites: sections 4.4-4.5 Course Material: Logic programming, streams (for understanding the query model). Files: (from Fall 1984) query/query-ibm.txt (includes general TXT files from above) query/query.scm query/query-ibm.dat History: ??? Used as problem set: Fall 1985, PS9 (shortened version without problem on UNIQUE) Fall 1984, PS9 Spring 1984, PS8 Fall 1983, PS9 Spring 1983, PS8 Fall 1982, PS10 Spring 1982, PS11 (different exercises) Fall 1981, PS9 (different exercises) Comments: The database has been updated to match the book. Also, I added the Wheel rule from the book, and fixed Lives-near to use Same. The TXT file is derived from fall84 by revising the stuff about how to use the query system. ---------------------------------------------------------------------- LOGIC PUZZLES Content: Using logic programming to solve "logic puzzles", in which the goal is to infer solutions to an association problem from a small set of clues. Prerequisites: sections 4.4-4.5 Course material: Logic programming: writing rules, infinite loops Files: query/logic-puzz.txt (includes general-purpose text files from above) query/query.scm query/logic-puzz.dat History: ??? Used as problem set: Spring 1985, PS9 Comments (Julie): Should be retested due to changes in the query system code 7/85. Is there any chance that the need for separate "-1" rules goes away? Or at least that the symptoms of not making them separate might be nonfatal? If so, should revise the problem set as appropriate. To fix (minor things): - Change the people to be current staff members when assign it. - Remove cultural bias. Not everyone knows that foie-gras is liver or that yogurt is health food. Either change foods or add parenthetical explanations. To fix (major things): This problem set is a first attempt at working with logic puzzles in the query language. It is kludgey in several ways: - The need to make associations and dissociations asymmetrical; - The need to have different versions of things -- dissociate,dissociate-1,... Jerry has ideas on how to redo it, and things it should be reworked completely before it is used again. ---------------------------------------------------------------------- HIRING SCENARIO Content: Exploring the query language using a campus recruiter's database, used to make hiring decisions based on candidates' profiles. Contains an extra-credit problem on an interactive query-the-user facility used by an expert system to gain information not in its database. Prerequisites: Section 4.4 - 4.5 Course Materials: Logic-programming - forming queries, writing rules. (Need to understand the stream implementation of the query language to do the extra credit). Files: (from Fall 1987) query/hiring.tex query/query.scm query/hiring.dat (the recruiter's database) Used as Problem Set: Fall 1987, PS9 ---------------------------------------------------------------------- REGISTER MACHINES Content: Playing with the register-machine simulator, explicit-control evaluator, and compiler from Chapter 5. Prerequisites: Through Section 5.3 Course material: Comparing hand-tailored machines, evaluated code, and compiled code. For a single problem, design and simulate recursive and iterative register machines; run with eceval; compile. Compare stack use in different versions. Files: regsim.txt (for lack of a better name) regsim.scm (register-machine simulator from book + syntactic sugar for define-machine) includes monitored stack and exercise 5.9 legality checker (see comments below) eceval.scm (explicit-control evaluator from book) includes compiler interface eceval-syntax.scm (from book) compiler.scm (compiler from book) History: ??? In Fall 1986, Dave Cumming and Joe Chung added some code to graphically display the pushing and popping of the stack. Used as problem set: Fall 1985, PS10 Spring 1985, PS10 Fall 1984, PS10 Spring 1984, PS9 Fall 1983, PS10 Comments: The files are from spring 1985. I edited the text file as follows: -Flushed the screwy separation of intialization and statistics-printing. Told them to do the Init at the end (not the beginning) of their controller. **You may prefer to change this back, but if you do, you should add some explanation about the weird printing thing not really being a machine instruction. See manual.** -In the file descriptions, I added that REGSIM includes ex.5.9 legality- checking (didn't mention that it doesn't do 5.9e) -Changed the file names -Where it says you can change the stack abstraction to monitor stack operations, I added a reference to the file name. The file REGSIM.SCM is modified to check machines as specified by exercise 5.9, except that it doesn't do part e. The original book code (without checking) is available in REGSIM-NO-CHECK.SCM Code status: tested, ok - BUT: I haven't rechecked the machine-checking edits, which I ran last year in California. For paranoia's sake, someone should run a few machines through the current REGSIM and then delete this comment. To do: The problem set says that "the following files have been included with this problem set". Do you want to reword it so it doesn't sound as if listings of the files are attached? Variations: The current problem looks at exponentiation. See Spring 1984 for a different (factorial-like) procedure to implement/study. See exercises 5.1-5.2, 5.13, 5.20-5.21, 5.30-5.31, 5.34 for basically the same stuff with factorials. To make a similar study of Fibonacci, see exercises 5.6, 5.22, 5.35. (But these deal with recursion only -- you'll want to add iterative versions. Also, you'll have to omit the problem of comparing compiled code when args are interchanged, as the (+...) in Fib is symmetrical.) Beware: When you plug in different procedures, be careful of - special forms -- Stick to the ones supported by eceval and compiler - primitives -- Be sure that any primitives you use are installed in ECEVAL.SCM. If you change this list, also change it in the problem-set text file. ----------------------------------------------------------------------