SICP Exercise 4.14 map as compound vs. primitive type

Exercise 4.14.  Eva Lu Ator and Louis Reasoner are each experimenting with the metacircular evaluator. Eva types in the definition of map, and runs some test programs that use it. They work fine. Louis, in contrast, has installed the system version of map as a primitive for the metacircular evaluator. When he tries it, things go terribly wrong. Explain why Louis's map fails even though Eva's works.

EXPLANATION & SOLUTION

Part a of this problem: I implement Eva's way of explicitly typing in the definition of 'map' into the metacircular evaluator's input prompt. I also type in the definition of an 'inc' procedure to increment its (numerical) input. And also make use of Racket's primitive procedure 'abs'. 'inc' and 'abs' are the procedure arguments to 'map' in different tests. As can be seen from the test results, everything works as expected. Note that in this program, 'map' and 'inc' are executed by the metacircular evaluator. 'abs' is executed as a primitive procedure. The code and tests are here.

Part b of this problem: Here I implement Louis' way of installing the system version of 'map' as a primitive for the metacircular evaluator. See the results at the bottom of the program. The evaluator does not work as expected.

Note that one of the arguments to 'map' is a procedure. The metacircular evaluator constructs all the arguments to be passed in to any procedures (compound or primitive) that it executes. So the proc argument that it passes to the primitive 'map' is represented syntactically and semantically in the form that the metacircular evaluator understands. The underlying Racket interpreter does not know anything about the meta-circular evaluator's representations. The Racket version of 'map' expects a Racket procedure as its argument which it does not find when invoked by the metacircular evaluator. Hence it fails with 'contract violation' error messages. The code and tests are here.


Comments

Post a Comment

Popular posts from this blog

SICP Exercise 2.56 differentiation rule

Image
Exercise 2.56.    Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule by adding a new clause to the  deriv  program and defining appropriate procedures  exponentiation? ,  base ,  exponent , and  make-exponentiation . (You may use the symbol  **  to denote exponentiation.) Build in the rules that anything raised to the power 0 is 1 and anything raised to the power 1 is the thing itself. SOLUTION The code and tests are here .
Read more

SICP Exercise 1.28 (Miller-Rabin Test)

Exercise 1.28.    One variant of the Fermat test that cannot be fooled is called the  Miller-Rabin test  (Miller 1976; Rabin 1980). This starts from  an alternate form of Fermat's Little Theorem, which states that if  n  is a prime number and  a  is any positive integer less than  n , then  a  raised to the ( n  - 1)st power is congruent to 1 modulo  n . To test the primality of a number  n  by the Miller-Rabin test, we pick a random number  a < n  and raise  a  to the ( n  - 1)st power modulo  n  using the  expmod  procedure. However, whenever we perform the squaring step in  expmod , we check to see if we have discovered a ``nontrivial square root of 1 modulo  n ,'' that is, a number not equal to 1 or  n  - 1 whose square is equal to 1 modulo  n . It is possible to prove that if such a nontrivial square root of 1 exists, then  n  is not prime. It is also possible to prove that if  n  is an odd number that is not prime, then, for at least half the numbers a < n , co
Read more

SICP Exercise 4.18 a alternative strategy for interpreting internal definitions

Exercise 4.18.   Consider an alternative strategy for scanning out definitions that translates the example in the text to (lambda < vars >   (let ((u '*unassigned*)         (v '*unassigned*))     (let ((a < e1 >)           (b < e2 >))       (set! u a)       (set! v b))     < e3 >)) Here  a  and  b  are meant to represent new variable names, created by the interpreter, that do not appear in the user's program. Consider the  solve  procedure from section  3.5.4 : (define (solve f y0 dt)   (define y (integral (delay dy) y0 dt))   (define dy (stream-map f y))   y) Will this procedure work if internal definitions are scanned out as shown in this exercise? What if they are scanned out as shown in the text? Explain. SOLUTION & DISCUSSION The streams based procedure 'solve' in this exercise exposed several issues in my metacircular evaluator implementation. I discovered that streams are not at all handled properly by my evaluator. Moreover, the &
Read more