MASSACHVSETTS INSTITVTE OF TECHNOLOGY Department of Electrical Engineering and Computer Science 6.5150/6.5151 Spring 2023 Problem Set 7 Issued: Wed. 5 April 2023 Due: Fri. 14 April 2023 Reading: SDF Chapter 5 -- Evaluation: Sections 5.3 and 5.4 Some, perhaps useful background material SICP, From Chapter 4: section 4.3; (pp. 412--437) Heavy Evaluator Hacking In this problem set we build interpreters in a different direction. We start with the essential EVAL/APPLY interpreter, written as an analyzer of the syntax into a compiler of compositions of execution procedures -- a small combinator language. We will warm up by making modifications to this evaluator. Next, we will change the evaluator to include AMB expressions. To add AMB, the execution procedures will all have a different shape: in addition to the environment, each will take two "continuation procedures" SUCCEED and FAIL. In general, when a computation comes up with a value it will invoke SUCCEED with the proposed value and a complaint department which, if invoked, will try to produce an alternate value. If a computation cannot come up with a value, it will invoke the complaint department passed to it in the FAIL continuation. An important lesson to be learned here is how to use continuation procedures to partially escape the expression structure of the language. By construction, a functional expression has a unique value. However, in the AMB system an expression may be ambiguous as to its value... Think about how we arrange that to make sense! Separating Syntactic Analysis from Execution (Compiling to Execution Procedures) You should read Section 5.3 of SDF (and perhaps SICP section 4.1.7 for more background) carefully here. To Do ------------- Load the material for the following problems, with the incantation (manage 'new 'compiling-to-execution-procedures) This will get the evaluator described in SDF (similar to the one described in SICP, but generalized for extensibility). Exercise 5.14: Constant folding p. 268 Remember, you already have some experience with "algebraic simplification" from chapter 4. Exercise 5.15: Other optimizations p. 269 One way ot implement optimizations is to integrate a code simplifier into each of the handlers for ANALYZE. For example, in the analysis of an IF, can we determine the value of a predicate expression, perhaps by constant folding, at compile time? If so, the consequent or the alternative of the IF can be elided (dead-code elimination). A really good job on these problems may require adding a compile-time environment to each ANALYZE handler. AMB and Nondeterministic Programming Now comes the real fun part of this problem set! Please read section 5.4 of SDF (and perhaps section 4.3 of SICP) carefully before starting this part. This interpreter requires a change in the interface structure of the execution procedures that code compiles into, so it is quite different. Of course, our system differs from the one in SICP in that it is implemented with generic extension capability. You can load the interpreter extended for AMB with: (manage 'new 'exploratory-behavior) To Do ------------- Exercise 5.17: A puzzle pp. 277-278 Exercise 5.18: Failure Detection p. 278 Exercise 5.20: Choice ordering p. 279