@comment(Hey, EMACS, this is -*- SCRIBE -*- input) @device(dover) @make(6001) @modify(excounter, numbered [Exercise @1], referenced [@1]) @PageHeading(left "6.001 -- Hewlett-Packard Summer 1985", center "@Value(Page)", right "Problem set 8") @begin(center) HEWLETT-PACKARD Summer 1985 Problem Set 8 Originally Prepared As MASSACHUSETTS INSTITUTE OF TECHNOLOGY Department of Electrical Engineering and Computer Science 6.001 Structure and Interpretation of Computer Programs Spring Semester, 1985; Problem Set 8 @end(center) @blankspace(0.25 in) @begin(flushleft) @begin(itemize) Programs: (attached) @a[ps8-pps.scm], @a[ps8-eval.scm], @a[ps8-mods.scm] @end(itemize) @end(flushleft) @b[Note:] This is a two-week problem set with many difficult parts. It requires good understanding of the Scheme interpreter, which is described in section 4.1. We @b[strongly] suggest that you spread your work over the two weeks allotted, and do not attempt to do the assignment all at once. The beginning of the assignment is a pre-lab that does not require use of the computer (although there is some code that you can try out if you really want to). It would be a good idea to write up the exercises through exercise @ref(last-pre-lab) before doing any programming work. @section(Paranoid programming) Ben Bitdiddle, Chief Systems Programmer for the Itsey Bitsey Machine Company, has just made a terrible discovery: Many of his programs are giving wrong answers. A hurried investigation reveals that the bugs are not in Ben's code, but rather in the I-B-M Scientific Subroutine Library, which the company has subcontracted to a cut-rate software house. For example, the @a[sqrt] procedure supplied in the library, which Ben has used freely throughout his programs, claims that the square root of 25 is -6. Ben is so aghast at this that he decides to adopt a ``paranoid programming style.'' With each procedure he suspects of being buggy, he will associate three sets of predicates that will perform various consistency checks on the arguments and the returned value of any call to the procedure: @begin(itemize) @i[preconditions] -- which are used to check the arguments for applicability. @i[postconditions] -- which are used to check that the returned value is well formed. @i[transfer conditions] -- These are relations between the arguments and the returned value that should be satisfied in any call to the procedure. @end(itemize) For example, the @a[sqrt] procedure should only be called with a non-negative argument, should always return a non-negative value, and should have the transfer condition that the square of the returned value is approximately equal to the argument. Thus, if we define the two predicates @begin(programexample) (define (non-negative? x) (>= x 0)) (define (square-root-good-enough? v x) (define tolerance .001) (define (square x) (* x x)) (< (abs (- (square v) x)) tolerance)) @end(programexample) we can use @a[non-negative?] as both the precondition and the postcondition, and @a[square-root-good-enough?] as the transfer condition. To investigate the feasibility of this idea, Ben decides to implement a paranoid programming system (PPS) for procedures of one argument. Given a procedure of one argument, he writes a program that constructs a ``careful version'' of the procedure, which performs checks that have been indicated by appropriate declarations. For example, Ben constructs a careful version of @a[sqrt] as follows: @begin(programexample) (define csqrt (careful-version sqrt)) (declare preconditions csqrt non-negative?) (declare postconditions csqrt non-negative?) (declare transfer-conditions csqrt square-root-good-enough?) @end(programexample) Ben's @a[careful-version] constructor takes as input a suspect one-argument procedure and returns as its value another one-argument procedure, which, when applied, runs the original procedure and also checks the declared conditions, signaling an error if any condition fails. Declarations associate conditions with procedures, and the conditions associated with a procedure can be accessed via selectors called @a[preconditions], @a[postconditions], and @a[transfer-conditions]. In principle, a single procedure may have many declared conditions. Thus, @a[preconditions], @a[postconditions], and @a[transfer-conditions] each return a list of predicates. The original suspect procedure is also associated with the careful version, and can be retrieved using a selector called @a[kernel-procedure]. @begin(programexample) (define (careful-version suspect-procedure) (define (me x) ;ME will be the careful version (check-all (preconditions me) (lambda (pred) (pred x))) (let ((v (suspect-procedure x))) (check-all (postconditions me) (lambda (pred) (pred v))) (check-all (transfer-conditions me) (lambda (pred) (pred v x))) v)) (set-kernel-procedure! me suspect-procedure) me) @end(programexample) @a[Check-all] takes as arguments a set of predicates (represented as a list) and a specification of how to apply each predicate to arguments. It applies each predicate in the set, and signals an error if any predicate returns false. @begin(programexample) (define (check-all set-of-predicates predicate-application-form) (define (loop s) (cond ((null? s) t) ((predicate-application-form (car s)) (loop (cdr s))) (else (error "Failed consistency check" (car s))))) (loop set-of-predicates)) @end(programexample) The actual declarations and associations are accomplished using a general @a[get/put] mechanism, similar to the one used for implementing generic operators in Chapter 2 of the text. One stylistic difference is that the keys into the table are not symbols, but rather the actual procedure objects. @begin(programexample) (define (preconditions proc) (get proc preconditions)) (define (postconditions proc) (get proc postconditions)) (define (transfer-conditions proc) (get proc transfer-conditions)) (define (kernel-procedure f) (get f kernel-procedure)) (define (declare declaration-type proc predicate-procedure) (let ((set (get proc declaration-type))) (if (not (memq predicate-procedure set)) (put proc declaration-type (cons predicate-procedure set))) 'OK)) (define (set-kernel-procedure! f1 f2) (put f1 kernel-procedure f2)) @end(programexample) @a[Put] and @a[get] are implemented using a local table, as explained on pages 216-217 of the book. Ben's Paranoid Programming System works very well -- so well that I-B-M begins using it for its own internal software development (to protect itself, for example, from Louis Reasoner's code. Louis is a trainee working for Alyssa P. Hacker, who works for Ben Bitdiddle. His code usually contains bugs.). One common thing that people do at I-B-M is to combine procedures to make more complex procedures. For instance, given an @a[abs] procedure that computes absolute values, and a @a[sqrt] procedure that computes square roots, one can form a composition @a[sqrt-abs] that computes the square root of the absolute value of its input. @begin(programexample) (define sqrt-abs (compose sqrt abs)) @end(programexample) where @a[compose] is defined as @begin(programexample) (define (compose f g) (lambda (x) (f (g x)))) @end(programexample) Ben notices that if we use @a[compose] with careful procedures, this can lead to redundant testing of preconditions and postconditions. For example, suppose that @a[cabs] -- the careful version of @a[abs] -- has a postcondition asserting that the returned value is non-negative. @begin(programexample) (define cabs (careful-version abs)) (declare postconditions cabs non-negative?) @end(programexample) Then @a[csqrt-abs], defined as the composition of @a[csqrt] and @a[cabs], will test that the value returned by @a[cabs] is non-negative twice -- once as a postcondition of @a[cabs] and once as a precondition of @a[csqrt]. To avoid this wasteful computation, Ben proposes the following composition operator for careful procedures: @begin(programexample) (define (careful-compose f g) (define (kernel x) (let ((vg ((kernel-procedure g) x))) (check-all (postconditions g) (lambda (p) (p vg))) (check-all (transfer-conditions g) (lambda (p) (p vg x))) (check-all (set-difference (preconditions f) (postconditions g)) (lambda (p) (p vg))) (let ((vf ((kernel-procedure f) vg))) ;Compute value of F (check-all (transfer-conditions f) (lambda (p) (p vf vg))) vf))) (define (me x) (check-all (preconditions g) (lambda (p) (p x))) (let ((vme (kernel x))) (check-all (postconditions f) (lambda (p) (p vme))) vme)) (set-kernel-procedure! me kernel) (put me preconditions (preconditions g)) (put me postconditions (postconditions f)) me) @end(programexample) The idea is that the careful composition of @a[f] and @a[g] should check all the preconditions, postconditions, and transfer conditions of @a[g] and all the postconditions and transfer conditions of @a[f], but only those preconditions of @a[f] that are not automatically guaranteed by the postconditions of @a[g]. The resulting careful composition has as its preconditions the preconditions of @a[g], as its postconditions the postconditions of @a[f], and as its kernel procedure a procedure that computes the value of the composition and performs all necessary checks not included in the preconditions and postconditions of the composition. Ben eliminates redundant conditions on the interface between @a[f] and @a[g] by using a @a[set-difference] operator that returns all the elements of a set @a[s1] that are not contained in a set @a[s2]: @begin(programexample) (define (set-difference s1 s2) (cond ((null? s1) '()) ((memq (car s1) s2) (set-difference (cdr s1) s2)) (else (cons (car s1) (set-difference (cdr s1) s2))))) @end(programexample) @section(Warm-up Exercises) We suggest that you do the exercises in this section @b[before] coming to the laboratory. One of the suspect procedures in the subroutine library, @a[sort], takes as argument a list of distinct numbers, and claims to return a list of the same numbers, sorted into ascending order, for example @begin(programexample) (sort '(2 8 5 3)) ==> (2 3 5 8) @end(programexample) Alyssa P. Hacker tries to make a careful version of @a[sort], using the Paranoid Programming System. She constructs the careful version, @a[csort], using the predicates @a[list-of-numbers?] and @a[ascending-order?], which were written for Alyssa by her trainee, Louis Reasoner. @begin(programexample) (define csort (careful-version sort)) (declare preconditions csort list-of-numbers?) (declare postconditions csort list-of-numbers?) (declare postconditions csort ascending-order?) @end(programexample) @a[List-of-numbers] checks that its argument is a list whose elements are all numbers: @begin(programexample) (define (list-of-numbers? x) (cond ((null? x) t) ((atom? x) nil) ((not (number? (car x))) nil) (else (list-of-numbers? (cdr x))))) @end(programexample) @a[Ascending-order?] checks that the elements of its input list are in ascending order: @begin(programexample) (define (ascending-order? x) (cond ((null? x) t) ((< (car x) (cadr x)) (ascending-order? (cdr x))) (else nil))) @end(programexample) Unfortunately, Louis's @a[ascending-order?] procedure has a bug. @begin(exercise) Explain what the bug is. Hint: Describe what the procedure will do, given the list @a[(1)]. Show how to repair Louis's program. @end(exercise) Louis fixed his code, and @a[ascending-order?] worked as intended. Unfortunately, this was not enough to ensure correct @a[sort] behavior. @a[Csort] still did not work, even though the declarations were satisfied. The behavior was: @begin(programexample) (csort '(4 6 5 9)) --> (5 6 9) @end(programexample) Ben recommended that an appropriate transfer condition would catch this bug. Alyssa suggested checking that the input and output lists have the same length, but Ben said this would not be a sufficient test to absolutely guarantee that @a[csort] was not failing. @begin(exercise) Explain why Ben is correct, giving a particular example of an incorrect value that might be returned by @a[csort] that would not be caught by Alyssa's suggestion. Produce an appropriate predicate that, when declared as a transfer condition for @a[csort], will guarantee to catch any incorrect answers. Give @begin(alphaenumerate) a definition of the transfer predicate, in Scheme a brief statement of what condition the predicate is checking. the declaration required to add this transfer condition to @a[csort]. @end(alphaenumerate) @end(exercise) @begin(exercise) Alyssa asks Ben to explain why his @a[careful-compose] method is useful. Ben illustrates as follows: Consider computing big roots of numbers by repeatedly taking square roots: @begin(programexample) (define (big-root n) (repeated n sqrt)) (define (repeated n f) (cond ((= n 1) f) ((even? n) (let ((g (repeated (/ n 2) f))) (compose g g))) (else (compose f (repeated (-1+ n) f))))) @end(programexample) Suppose we form a careful big-root procedure by repeatedly composing the careful procedure @a[csqrt,] which is defined to have @a[non-negative?] both as a precondition and a postcondition: @begin(programexample) (define (c-big-root n) (repeated n csqrt)) @end(programexample) The number of times that @a[non-negative?] is tested in computing big roots would be considerably reduced if we had used @a[careful-compose] rather than @a[compose] in our definition of @a[repeated]. Show that Ben is right, as follows: Suppose we define @a[c-16th-root] to be @a[(c-big-root 4)] @begin(alphaenumerate) How many times will @a[non-negative?] be called in @a[(c-16th-root 2)] with @a[repeated] defined using @a[compose]? Explain your answer. How many times will @a[non-negative?] be called in @a[(c-16th-root 2)] with @a[repeated] defined using @a[careful-compose?] Explain your answer. @end(alphaenumerate) These questions are tricky, so be careful. If you like, you may check your answers by instrumenting the PPS and running it. The code for the PPS is contained in the file @a[ps8-pps.scm], which you can load and run. But you need not do this exercise on the computer at all. @end(exercise) @section(A paranoid interpreter) Ben's paranoid programming system makes programs so reliable that Oliver Warbucks, the president of I-B-M, decrees that condition testing should be installed in the I-B-M Scheme interpreter. Ben and Alyssa realize that this will make the interpreter so inefficient that they refuse to do the job, and go off to work for the Hot-Tari company to make video games. Poor Louis Reasoner is the only one left at I-B-M to install the new interpreter, and he desperately needs our help. In the new version of Scheme, the @a[careful-version] constructor will not be used at all. Every procedure is potentially a careful procedure, with associated pre- post- and transfer conditions. Moreover, the ``careful'' mechanism will be extended to work for procedures of any number of arguments. A procedure's precondition will be a predicate that takes the same arguments as the procedure. The postcondition is still a procedure of one argument (the value returned by the procedure). The transfer condition for a procedure of N arguments is a procedure of N+1 arguments -- the returned value followed by the procedure arguments. Louis begins by changing the metacircular evaluator @a[eval] procedure (as indicated in the starred line below) to call a special @a[careful-apply] rather than the old @a[apply]: @begin(programexample) (define (eval exp env) (cond ((self-evaluating? exp) exp) ((quoted? exp) (text-of-quotation exp)) ((variable? exp) (lookup-variable-value exp env)) ((definition? exp) (eval-definition exp env)) ((assignment? exp) (eval-assignment exp env)) ((lambda? exp) (make-procedure exp env)) ((conditional? exp) (eval-cond (clauses exp) env)) ((application? exp) (careful-apply (eval (operator exp) env) ;***** (list-of-values (operands exp) env))) (else (error "Unknown expression type -- EVAL")))) @end(programexample) @a[Careful-apply] uses the ordinary @a[apply] in order to apply procedures. However, if the procedure has any associated declarations, @a[careful-apply] must check these. @begin(programexample) (define (careful-apply procedure arguments) @i[] (if (not (and (null? (postconditions procedure)) (null? (transfer-conditions procedure)))) (let ((val (apply procedure arguments))) @i[] @i[] val) (apply procedure arguments))) @end(programexample) @begin(exercise) Give the missing expressions part 1, part 2, part 3 indicated above. (You do not need to do this in the laboratory.) @end(exercise) @begin(exercise) @tag(last-pre-lab) Cy D. Fect, the local Algol and Fortran wizard, asked Louis why he uses an explicit @a[if] test to see if there are any transfer and postconditions and skip to @a[apply] if not. After all, he observes, the expressions part 1, part 2, and part 3 should have no effect if there are no relevant conditions. Louis says that he doesn't understand this either, but that before Ben left, he muttered something about doing things this way so as not to destroy the tail-recursive properties of the language any more than necessary. Please explain what Ben was talking about. @end(exercise) @section(Strong typing) Having lost his most talented programming staff, Oliver has decided that it is time to tighten management controls in his programming department. He never liked the free style of Ben and his employees. Cy D. Fect, who is now the senior member of the staff, and who never liked Lisp anyway, convinces Oliver to call in a famous consultant, Professor N. Mirth, to evaluate the situation. Mirth is the internationally renowned inventor of the famous programming language, Pasqual, which was designed to force programmers to write ``well-structured'' programs. Mirth tells Oliver that Scheme (like all Lisps) is a terrible programming language because it allows programmers to write programs that are not ``type-safe'' -- a program may be passed an argument that is of the wrong type. For example, @a[sqrt] can be passed a list, which it is not prepared to handle. He advocates a ``strong type system,'' which can prevent such a problem. In a strongly typed language, every variable is declared to have a @i[type], which constrains what its value must be. In addition, every procedure that returns a value must also have a declared type of its value. Louis showed Mirth Ben's PPS system, which Mirth dismissed lightly, ``Like all Lisp-ish systems, it is very pretty, but the fatal flaw is that the declarations are optional. For effective software management it is necessary to make the declarations a mandatory part of every program. We must outlaw sloppy programs and punish sloppy programmers. Only then will we have effective management. In fact, PPS encourages sloppy work because it makes it too easy to find errors at run time and fix them. This may be good in a research environment, where the programs are continually under development and the users are the programmers, but in the situation where we want to sell a product, we want to be sure it is solid before it gets to the market.'' This was pretty convincing to Oliver and Cy, but the company could not easily switch to Pasqual because they had a huge investment in Scheme software that they had already written. Specifically, they make heavy use of procedures as arguments (which work passingly well in Pasqual) and procedures as values (which don't work at all in Pasqual). Mirth proposes a modification to Scheme that enforces strong typing. The new system will be called Pascheme. In Pascheme, every procedure is defined with a type declaration for each argument and a type declaration for the value. The types are represented as predicates that test whether an object is of the required type. Syntactically, a procedure will be defined with types declared as follows: @begin(programexample) (define @i[] (@i[] (@i[ ]) ... (@i[ ])) @i[]) @end(programexample) For example, in Pascheme we would writhe: @begin(programexample) (define integer? (factorial (integer? n)) (cond ((= n 1) 1) (else (* n (factorial (- n 1)))))) @end(programexample) The procedure name itself will automatically be declared to have type @a[pascheme-procedure?]. In addition, the syntax of @a[define] must be extended to allow the definition of variables that are not procedures, as in the Scheme definition @a[(define a 3)]. The extension that will be used is: @begin(programexample) (define @i[] @i[] @i[]) @end(programexample) For example, @begin(programexample) (define integer? a 3) @end(programexample) Lambda expressions will be extended to look like: @begin(programexample) (lambda @i[] ((@i[ ]) ... (@i[ ])) @i[]) @end(programexample) Thus, the procedure-definition syntax shown above will be syntactic sugar for @begin(programexample) (define pascheme-procedure? @i[] (lambda @i[] ((@i[ ]) ... (@i[ ])) @i[])) @end(programexample) and the lambda expression for the @a[factorial] procedure defined above will now look like: @begin(programexample) (lambda integer? ((integer? n)) (cond ((= n 1) 1) (else (* n (factorial (- n 1)))))) @end(programexample) In the initial implementation of Pascheme, a type will be a predicate in the underlying Scheme system (the implementation language), not a user-definable Pascheme predicate. @section(In the Laboratory) In this laboratory assignment, we will be helping Louis implement the changes to Scheme required to build Pascheme. The file @a[ps8-eval.scm] contains a copy of a simple Scheme interpreter written in Scheme, essentially the same as the one in Section 4.1. There are a few minor differences, of which the most important are: @begin(itemize) The procedures @a[eval] and @a[apply] have been renamed @a[mini-eval] and @a[mini-apply], so as not to interfere with Scheme's own @a[eval] and @a[apply] operators. The interface to the underlying Scheme system via @a[apply-primitive-procedure] is handled somewhat differently from in the book. @end(itemize) See the attached code for details. If you load this file into Scheme and type @a[(initialize-evaluator)], you will find yourself typing at the driver loop. Please note that this Scheme running in Scheme contains no error system of its own. If you hit an error or type @c[ctrl-G], you will bounce back into Scheme. Also, you must type in procedure definitions directly to the driver loop, since there is no interface to NMODE.@foot{However, you can use the editor to write an ordinary Scheme procedure that calls @a[mini-eval] in order to predefine various things in the global environment. Run @a[initialize-evaluator], then type @c[ctrl-G] to get back to Scheme, run your procedure to predefine things, then reenter the interpreter by typing @a[(driver-loop)].} In order to help you keep from becoming confused, the driver loop uses the prompt @a[MC-EVAL==>] instead of the ordinary Scheme prompt. Start up the interpreter and try a few simple expressions. If you bounce out into Scheme, you can re-enter the interpreter by typing @a[(driver-loop)]. If you get hopelessly fouled up, you can run @a[initialize-evaluator], but this initializes the global environment, and you will lose any definitions you have made. Also, it is instructive to run the interpreter while tracing @a[mini-eval] and/or @a[mini-apply], to see just how the evaluator works. (You will also probably need to do this while debugging your code for this assignment.) If you do trace these procedures, you may want to use the Scheme procedures @a[print-breadth] and @a[print-depth] to avoid printing huge listings of the @a[env] argument to these procedures (printed by the tracer), which is in general a circular structure. See the Chipmunk manual for information on the use of @a[print-breadth] and @a[print-depth]. For this assignment, you will need to modify a few of the procedures in the interpreter, and also write a few new procedures. To help you, @a[ps8-mods.scm] contains the procedures that you will need to modify. (You should not need to modify all of the procedures in this file. Part of your task is to figure out precisely which procedures need to be modified.) You can load this file into an NMODE buffer, which you can edit while doing this assignment. The entire @a[ps8-eval.scm] file can be LOADed directly into Scheme without your worrying about editing it. @paragraph(Strategy) The changes required to implement Pascheme are of two basic sorts. There are syntactic changes, which concern the ways in which program expressions are symbolically represented, and semantic changes, which concern the actual computations that will be performed. In general, syntactic changes are made in the constructors, selectors, and predicates that determine the syntax of the language. Semantic changes will be made in the content procedures @a[mini-eval] and @a[mini-apply] and their helper procedures. Syntax and semantics are not completely independent; they interact in the representation of the computational objects manipulated by the interpreter, such as procedure objects. In particular, in this interpreter, procedure objects are represented by lists containing a lambda expression and an environment. We will need to augment the representation of lambda expressions to include the type information. @paragraph(Syntax) The first part of the implementation is to change the interpreter syntax so that @a[define] expressions and @a[lambda] expressions have typed variables and a typed value. This change has several pieces. @begin(exercise) Change the procedure-object selectors @a[parameters] and @a[procedure-body] to correctly accommodate the new structure of lambda expressions. @a[Parameters] should return the entire typed parameter list -- do not strip off the types here. In addition, define a new selector, @a[procedure-value-type], that gets the type predicate for the value of a procedure. Modify @a[user-print] so that it prints the procedure's return value type. (You may make @a[user-print] print the entire lambda expression if you wish.) @end(exercise) @begin(exercise) @tag(def-var) Change @a[definition-variable] and @a[definition-value] to parse the new definition syntax. @a[Definition-variable] must supply a typed variable for the thing being defined. There are two cases: @begin(alphaenumerate) @begin(multiple) In the case that we are defining a simple variable to have a value, we supply the type explicitly. For example: For @a[(define integer? a 3)], @a[definition-variable] should return @a[(integer? a)] and @a[definition-value] should return 3. @end(multiple) @begin(multiple) In the case that we are defining a new compound procedure we must supply a type, @a[pascheme-procedure?] for the procedure variable being defined. For example: For @a[(define integer? (factorial ...) ...)], @a[definition-variable] should return @a[(pascheme-procedure? factorial)] and @a[definition-value] should return an appropriate @a[lambda] expression. @end(multiple) @end(alphaenumerate) @end(exercise) @begin(exercise) @tag(env-ex) An environment will be made by @a[extend-environment] by pairing the elements of the typed formal parameter list of the lambda expression with their values. An environment will thus have types in the bindings. (These types will be used in evaluating assignments, to check that values assigned to the variables are correct.) Change the procedures that define the representation of environments to implement the new features. @end(exercise) @begin(exercise) As a result of your modification to @a[definition-variable] in exercise @ref(def-var), @a[define-variable!] is now passed a typed variable. Change @a[define-variable!] so that it will pass the right information to the environment-manipulation procedures and set up the appropriate type when a variable is defined, given your new environment structure (exercise @ref(env-ex)). You should permit the type to be changed when a variable is redefined using @a[define]. @end(exercise) @begin(exercise) Change the initial global environment to have the type @a[pascheme-procedure?] for each of the initial procedure entries. Also include appropriate types for the variables @a[nil] and @a[t].@foot{Should you think of @a[nil] as false or as the empty list? Or does it matter?} @end(exercise) Your modified evaluator should now work as it did before. It should take the typed syntax and ignore the types, except in the building and accessing of elements in the environment. It is important to test this out before going on to the next step! Otherwise you may become horribly confused. You should hand in listings of the changes you made and also a demonstration of the interpreter working at this point. @paragraph(Semantics) We will now change the interpreter semantics so that the types are checked when the program is run. In this implementation, we will check types only for user-defined Pascheme procedures -- not for primitives. A type is any predicate of the underlying Scheme implementation language. Thus a type predicate will be applied to its arguments using the underlying Scheme's @a[apply]. In fact, since we will have to get at the Scheme value of the type predicate name (that is, the type predicate itself), so we can have something to @a[apply], we will have to use Scheme's @a[eval] as well. To simplify matters, you may use the following procedure to have Scheme apply the Scheme value of a symbol representing a unary (one-argument) predicate to its argument: @begin(programexample) (define (apply-unary-predicate-symbol predicate-name argument) (apply (eval predicate-name (the-environment)) (list argument))) @end(programexample) @begin(exercise) Change @a[make-frame] to check types of arguments as they are being bound to formal parameters. @end(exercise) @begin(exercise) Change @a[mini-apply] to check types of values being returned from (user-defined) procedures. @end(exercise) @begin(exercise) Change the way assignments and definitions are executed so that types are checked on assignment of a value to a variable. You should permit the type to be changed when a variable is redefined using @a[define]. @end(exercise) @begin(exercise) Define @a[pascheme-procedure?] as a type predicate so that you can pass Pascheme procedures as arguments and return them as values. @end(exercise) At this point you should be able to run a program again. Debug your changes in the context of the simple recursive @a[factorial] procedure. Pass @a[factorial] as an argument to some other procedure and demonstrate its use. Supply us listings of your changes and a demonstration that they work. Demonstrate that your interpreter checks types on input and output. @begin(exercise) @tag(extensible-types) @i[Program design problem:] Pascheme's type system is not very flexible. Since types are Scheme predicates, not Pascheme predicates, there is no good way for the Pascheme user to define a new predicate. Write a short paragraph discussing the major changes required to make Pascheme have an extensible type system -- that is, to allow the user to define new types as Pascheme procedures that return true or false. @end(exercise) @section(Post-Lab Essay: Run-time vs. compile-time checking) In fairness to advocates of type-safe languages, we should point out that Prof. Mirth would not be happy with Pascheme. Pascheme does its type checking when programs are run (so-called @i[run-time checking]), whereas most typed languages (including Pasqual) do type checking when the syntax of programs is analyzed (so-called @i[compile-time checking] or @i[static analysis]). The idea is that many kinds of type violations can be found by analyzing the text of a program without running the procedures, rather than waiting to bomb out when the program is run using actual inputs. For example, if the result of a procedure that returns type @a[integer?] is used as an argument to a procedure that expects type @a[list?], we should not need to run the program in order to know that a type violation will occur. On the other hand, Pascheme allows types that are defined by arbitrary (Scheme) predicates (and, indeed, by arbitrary Pascheme predicates, if modified as in exercise @ref(extensible-types)). Give some examples of types that it would be possible to check without running the procedures involved, and indicate roughly how to go about doing this. Give some examples of types that you think could not be checked in any useful way without actually running the procedures. Can you define a type for which you can @i[prove] that it is impossible to do check without running the program, no matter how elaborate an analysis program one writes?@foot{Hint: You may find it useful to think about the discussion of the Halting Theorem, presented in lecture on April 11.} In the same vein, notice that Pascheme (and Pasqual), unlike Ben's original PPS, does not have any transfer conditions. Can you think of any useful transfer conditions that it would be possible to check without actually running the procedures? Write a two-page essay, comparing the relative advantages of run-time type checking vs. static analysis. Do not attempt to give a complete treatment of the issues -- many Ph.D. theses could be (indeed, have been) written on this topic. @newpage() @begin(programexample) ;;;-*-scheme-*- ;;; Ben Bitdiddle's Paranoid Programming System ;;; This is the file ps8-pps.scm (define (careful-version suspect-procedure) (define (me x) ;ME will be the careful version (check-all (preconditions me) (lambda (pred) (pred x))) (let ((v (suspect-procedure x))) (check-all (postconditions me) (lambda (pred) (pred v))) (check-all (transfer-conditions me) (lambda (pred) (pred v x))) v)) (set-kernel-procedure! me suspect-procedure) me) (define (check-all set-of-predicates predicate-application-form) (define (loop s) (cond ((null? s) t) ((predicate-application-form (car s)) (loop (cdr s))) (else (error "Failed consistency check" (car s))))) (loop set-of-predicates)) (define (preconditions proc) (get proc preconditions)) (define (postconditions proc) (get proc postconditions)) (define (transfer-conditions proc) (get proc transfer-conditions)) (define (kernel-procedure f) (get f kernel-procedure)) (define (declare declaration-type proc predicate-procedure) (let ((set (get proc declaration-type))) (if (not (memq predicate-procedure set)) (put proc declaration-type (cons predicate-procedure set))) 'OK)) (define (set-kernel-procedure! f1 f2) (put f1 kernel-procedure f2)) (define (careful-compose f g) (define (kernel x) (let ((vg ((kernel-procedure g) x))) (check-all (postconditions g) (lambda (p) (p vg))) (check-all (transfer-conditions g) (lambda (p) (p vg x))) (check-all (set-difference (preconditions f) (postconditions g)) (lambda (p) (p vg))) (let ((vf ((kernel-procedure f) vg))) ;Compute value of F (check-all (transfer-conditions f) (lambda (p) (p vf vg))) vf))) (define (me x) (check-all (preconditions g) (lambda (p) (p x))) (let ((vme (kernel x))) (check-all (postconditions f) (lambda (p) (p vme))) vme)) (set-kernel-procedure! me kernel) (put me preconditions (preconditions g)) (put me postconditions (postconditions f)) me) (define (set-difference s1 s2) (cond ((null? s1) '()) ((memq (car s1) s2) (set-difference (cdr s1) s2)) (else (cons (car s1) (set-difference (cdr s1) s2))))) ;;; This is the represention for tables, taken from pages 216-217 ;;; of the book. (define (make-table) (let ((local-table (list '*table*))) (define (lookup key-1 key-2) (let ((subtable (assq key-1 (cdr local-table)))) (if (null? subtable) nil (let ((record (assq key-2 (cdr subtable)))) (if (null? record) nil (cdr record)))))) (define (insert! key-1 key-2 value) (let ((subtable (assq key-1 (cdr local-table)))) (if (null? subtable) (set-cdr! local-table (cons (list key-1 (cons key-2 value)) (cdr local-table))) (let ((record (assq key-2 (cdr subtable)))) (if (null? record) (set-cdr! subtable (cons (cons key-2 value) (cdr subtable))) (set-cdr! record value))))) 'ok) (define (dispatch m) (cond ((eq? m 'lookup-proc) lookup) ((eq? m 'insert-proc!) insert!) (else (error "Unknown operation -- TABLE" m)))) dispatch)) (define operation-table (make-table)) (define get (operation-table 'lookup-proc)) (define put (operation-table 'insert-proc!)) @end(programexample) @newpage() @begin(programexample) ;;; -*-scheme-*- ;;; This is the file ps8-eval.scm ;;; It contains the metacircular evaluator, as described in section 4.1 ;;; of the text, with a few minor modifications. ;;; You should just load this file into Scheme without editing it. The ;;; new procedures that you will need to modify in order to do the ;;; problem set have been copied into in a separate file for your ;;; convenience. ;;; SETTING UP THE ENVIRONMENT ;;; We initialize the global environment by snarfing a few primitives ;;; from the underlying scheme system. ;;; This is different from the treatment of primitives in the book. ;;; (See the comments below under "applying primitive procedures".) ;;; If you want to add more primitives to your evaluator, just modify the ;;; list PRIMITIVE-PROCEDURE-NAMES to include more Scheme primitives. ;;; The actual structure of the environment is ;;; determined by the constructor EXTEND-ENVIRONMENT which is listed ;;; below together with the code that manipulates environments. (define primitive-procedure-names '(+ - * / = < > 1+ -1+ cons car cdr atom? eq? null? not)) (define (setup-environment) (let ((initial-env (extend-environment primitive-procedure-names (mapcar (lambda (pname) (list 'primitive (eval pname user-initial-environment))) primitive-procedure-names) '()))) (define-variable! 'nil nil initial-env) (define-variable! 't (not nil) initial-env) initial-env)) (define the-global-environment '()) ;;; INITIALIZATION AND DRIVER LOOP ;;; To start the metacircular evaluator, call INITIALIZE-EVALUATOR. ;;; This initializes the global environment, and starts the DRIVER-LOOP. ;;; Use INITIALIZE-EVALUATOR instead of DRIVER-LOOP if you want ;;; to erase any definitions you have accumulated and start fresh ;;; with a clean global environment (define (initialize-evaluator) (set! the-global-environment (setup-environment)) (driver-loop)) ;;; The driver loop reads an expression, evaluates it in the global ;;; environment, and prints the result. Note that the driver ;;; uses a prompt of "MC-EVAL==> " to help you avoid confusing typing to the ;;; metacircular evaluator with typing to the underlying SCHEME interpreter. ;;; (Also, we have called our evaluator procedures MINI-EVAL and MINI-APPLY ;;; to help you avoid confusing them with Scheme's EVAL and APPLY.) ;;; When/If your interaction with the evaluator bombs out in an error, ;;; you should restart it by calling DRIVER-LOOP again. (define (driver-loop) (newline) (princ "MC-EVAL==> ") (user-print (mini-eval (read) the-global-environment)) (driver-loop)) ;;; We use a special PRINT here, which avoids printing the environment ;;; part of a compound procedure, since the latter is a very long (or ;;; even circular) list. (define (user-print object) (cond ((compound-procedure? object) (print (list 'compound-procedure (parameters object) (procedure-body object) '[procedure-env]))) (else (print object)))) ;;; THE CORE OF THE EVALUATOR -- from section 4.1.1 (define (mini-eval exp env) (cond ((self-evaluating? exp) exp) ((quoted? exp) (text-of-quotation exp)) ((variable? exp) (lookup-variable-value exp env)) ((definition? exp) (eval-definition exp env)) ((assignment? exp) (eval-assignment exp env)) ((lambda? exp) (make-procedure exp env)) ((conditional? exp) (eval-cond (clauses exp) env)) ((application? exp) (mini-apply (mini-eval (operator exp) env) (list-of-values (operands exp) env))) (else (error "Unknown expression type -- EVAL" exp)))) (define (mini-apply procedure arguments) (cond ((primitive-procedure? procedure) (apply-primitive-procedure procedure arguments)) ((compound-procedure? procedure) (eval-sequence (procedure-body procedure) (extend-environment (parameters procedure) arguments (procedure-environment procedure)))) (else (error "Unknown procedure type -- APPLY" procedure)))) (define (list-of-values exps env) (cond ((no-operands? exps) '()) (else (cons (mini-eval (first-operand exps) env) (list-of-values (rest-operands exps) env))))) (define (eval-cond clist env) (cond ((no-clauses? clist) nil) ((else-clause? (first-clause clist)) (eval-sequence (actions (first-clause clist)) env)) ((true? (mini-eval (predicate (first-clause clist)) env)) (eval-sequence (actions (first-clause clist)) env)) (else (eval-cond (rest-clauses clist) env)))) (define (eval-sequence exps env) (cond ((last-exp? exps) (mini-eval (first-exp exps) env)) (else (mini-eval (first-exp exps) env) (eval-sequence (rest-exps exps) env)))) (define (eval-assignment exp env) (let ((new-value (mini-eval (assignment-value exp) env))) (set-variable-value! (assignment-variable exp) new-value env) new-value)) (define (eval-definition exp env) (define-variable! (definition-variable exp) (mini-eval (definition-value exp) env) env) (definition-variable exp)) ;;; Syntax of the language -- from section 4.1.2 (define (self-evaluating? exp) (number? exp)) (define (quoted? exp) (if (atom? exp) nil (eq? (car exp) 'quote))) (define (text-of-quotation exp) (cadr exp)) (define (variable? exp) (symbol? exp)) (define (assignment? exp) (if (atom? exp) nil (eq? (car exp) 'set!))) (define (assignment-variable exp) (cadr exp)) (define (assignment-value exp) (caddr exp)) (define (definition? exp) (if (atom? exp) nil (eq? (car exp) 'define))) (define (definition-variable exp) (if (variable? (cadr exp)) (cadr exp) (caadr exp))) (define (definition-value exp) (if (variable? (cadr exp)) (caddr exp) (cons 'lambda (cons (cdadr exp) (cddr exp))))) (define (lambda? exp) (if (atom? exp) nil (eq? (car exp) 'lambda))) (define (conditional? exp) (if (atom? exp) nil (eq? (car exp) 'cond))) (define (clauses exp) (cdr exp)) (define (no-clauses? clauses) (null? clauses)) (define (first-clause clauses) (car clauses)) (define (rest-clauses clauses) (cdr clauses)) (define (predicate clause) (car clause)) (define (actions clause) (cdr clause)) (define (true? x) (not (null? x))) (define (else-clause? clause) (eq? (predicate clause) 'else)) (define (last-exp? seq) (null? (cdr seq))) (define (first-exp seq) (car seq)) (define (rest-exps seq) (cdr seq)) (define (application? exp) (not (atom? exp))) (define (operator app) (car app)) (define (operands app) (cdr app)) (define (no-operands? args) (null? args)) (define (first-operand args) (car args)) (define (rest-operands args) (cdr args)) (define (make-procedure lambda-exp env) (list 'procedure lambda-exp env)) (define (compound-procedure? proc) (if (atom? proc) nil (eq? (car proc) 'procedure))) (define (parameters proc) (cadr (cadr proc))) (define (procedure-body proc) (cddr (cadr proc))) (define (procedure-environment proc) (caddr proc)) ;;; APPLYING PRIMITIVE PROCEDURES ;;; The mechanism for applying primitive procedures is somewhat ;;; different from the one given in section 4.1.4 of the text. ;;; The modification is as suggested in exercise 4.8 of the text. ;;; Instead of representing a primitive as a list ;;; (primitive ) ;;; we represent it as ;;; (primitive ) (define (primitive-procedure? proc) (if (atom? proc) nil (eq? (car proc) 'primitive))) (define (primitive-id proc) (cadr proc)) ;;; To apply a primitive procedure, we ask the underlying Scheme system ;;; to perform the application. (Of course, an implementation on a ;;; low-level machine would perform the application in some other way.) (define (apply-primitive-procedure p args) (apply (primitive-id p) args)) ;;; ENVIRONMENTS -- from section 4.1.3 (define (lookup-variable-value var env) (let ((b (binding-in-env var env))) (if (found-binding? b) (binding-value b) (error "Unbound variable" var)))) (define (binding-in-env var env) (if (no-more-frames? env) no-binding (let ((b (binding-in-frame var (first-frame env)))) (if (found-binding? b) b (binding-in-env var (rest-frames env)))))) (define (extend-environment variables values base-env) (adjoin-frame (make-frame variables values) base-env)) (define (set-variable-value! var val env) (let ((b (binding-in-env var env))) (if (found-binding? b) (set-binding-value! b val) (error "Unbound variable" var)))) (define (define-variable! var val env) (let ((b (binding-in-frame var (first-frame env)))) (if (found-binding? b) (set-binding-value! b val) (set-first-frame! env (adjoin-binding (make-binding var val) (first-frame env)))))) (define (first-frame env) (car env)) (define (rest-frames env) (cdr env)) (define (no-more-frames? env) (null? env)) (define (adjoin-frame frame env) (cons frame env)) (define (set-first-frame! env new-frame) (set-car! env new-frame)) (define (make-frame variables values) (cond ((and (null? variables) (null? values)) '()) ((null? variables) (error "Too many values supplied" values)) ((null? values) (error "Too few values supplied" variables)) (else (cons (make-binding (car variables) (car values)) (make-frame (cdr variables) (cdr values)))))) (define (adjoin-binding binding frame) (cons binding frame)) (define (assq key bindings) (cond ((null? bindings) no-binding) ((eq? key (binding-variable (car bindings))) (car bindings)) (else (assq key (cdr bindings))))) (define (binding-in-frame var frame) (assq var frame)) (define (found-binding? b) (not (eq? b no-binding))) (define no-binding nil) (define (make-binding variable value) (cons variable value)) (define (binding-variable binding) (car binding)) (define (binding-value binding) (cdr binding)) (define (set-binding-value! binding value) (set-cdr! binding value)) @end(programexample) @newpage() @begin(programexample) ;;; -*-scheme-*- ;;; This is the file ps8-mods.scm. ;;; It contains (a superset of) those procedures from the file ;;; ps8-eval.scm that you will need to modify in doing problem set 8. ;;; You should load ps8-eval.scm directly into Scheme, and then load ;;; the present file into an NMODE buffer to make your modifications. ;;; initial environment (define (setup-environment) (let ((initial-env (extend-environment primitive-procedure-names (mapcar (lambda (pname) (list 'primitive (eval pname user-initial-environment))) primitive-procedure-names) '()))) (define-variable! 'nil nil initial-env) (define-variable! 't (not nil) initial-env) initial-env)) ;;; printer used in driver-loop (define (user-print object) (cond ((compound-procedure? object) (print (list 'compound-procedure (parameters object) (procedure-body object) '[procedure-env]))) (else (print object)))) ;;; apply (define (mini-apply procedure arguments) (cond ((primitive-procedure? procedure) (apply-primitive-procedure procedure arguments)) ((compound-procedure? procedure) (eval-sequence (procedure-body procedure) (extend-environment (parameters procedure) arguments (procedure-environment procedure)))) (else (error "Unknown procedure type -- APPLY" procedure)))) ;;; syntax of definitions (define (definition-variable exp) (if (variable? (cadr exp)) (cadr exp) (caadr exp))) (define (definition-value exp) (if (variable? (cadr exp)) (caddr exp) (cons 'lambda (cons (cdadr exp) (cddr exp))))) ;;; syntax of procedures (define (make-procedure lambda-exp env) (list 'procedure lambda-exp env)) (define (compound-procedure? proc) (if (atom? proc) nil (eq? (car proc) 'procedure))) (define (parameters proc) (cadr (cadr proc))) (define (procedure-body proc) (cddr (cadr proc))) (define (procedure-environment proc) (caddr proc)) ;;; ENVIRONMENTS -- from section 4.1.3 (define (lookup-variable-value var env) (let ((b (binding-in-env var env))) (if (found-binding? b) (binding-value b) (error "Unbound variable" var)))) (define (binding-in-env var env) (if (no-more-frames? env) no-binding (let ((b (binding-in-frame var (first-frame env)))) (if (found-binding? b) b (binding-in-env var (rest-frames env)))))) (define (extend-environment variables values base-env) (adjoin-frame (make-frame variables values) base-env)) (define (set-variable-value! var val env) (let ((b (binding-in-env var env))) (if (found-binding? b) (set-binding-value! b val) (error "Unbound variable" var)))) (define (define-variable! var val env) (let ((b (binding-in-frame var (first-frame env)))) (if (found-binding? b) (set-binding-value! b val) (set-first-frame! env (adjoin-binding (make-binding var val) (first-frame env)))))) (define (make-frame variables values) (cond ((and (null? variables) (null? values)) '()) ((null? variables) (error "Too many values supplied" values)) ((null? values) (error "Too few values supplied" variables)) (else (cons (make-binding (car variables) (car values)) (make-frame (cdr variables) (cdr values)))))) (define (adjoin-binding binding frame) (cons binding frame)) (define (assq key bindings) (cond ((null? bindings) no-binding) ((eq? key (binding-variable (car bindings))) (car bindings)) (else (assq key (cdr bindings))))) (define (binding-in-frame var frame) (assq var frame)) (define (found-binding? b) (not (eq? b no-binding))) (define no-binding nil) (define (make-binding variable value) (cons variable value)) (define (binding-variable binding) (car binding)) (define (binding-value binding) (cdr binding)) (define (set-binding-value! binding value) (set-cdr! binding value)) @end(programexample)