Get SICP’s meta-circular lisp interpreter going. To avoid conflicts with scheme’s native eval and apply procedures, rename your interpreter’s versions to eval-sicp and apply-sicp.
[in racket use #lang sicp or try biwa-scheme on repl.it]
Get Norvig’s lisp interpreter going in Python[github;repl.it]
Add primitive procedures for doing arithmetic, creating lists, and printing.
Modernizing our Interpreter
Let’s update our host language to something current: Racket/Biwa Scheme or Python. Although the implementation will change, the language we are interpreting is still exactly SICP scheme.
Racket or Biwa
Use #t and #f rather than true and false in the host language.
Rewrite the frame implementation:
Use a hash-table to map names → values, instead of two parallel lists of names & values in the frame—Racket does not allow mutable pairs, so no set-car nor set-cdr, by default. Tip: use make-hash for mutable hash tables!
Python
Rewrite Norvig’s lisp to be closer to SICP scheme. Add a bit of syntactic sugar:
Write cond.
Support the quote syntax when parsing lisp expressions:'x ↔(quote x)
Allow define to declare procedures directly, e..g,
(define (dec x) (- x 1)) ↔(define dec (lambda (x) (- x 1))))
and and or
Exercise 4.4: Recall the definitions of the special forms and and or from Chapter 1:
and: The expressions are evaluated from left to right. If any expression evaluates to false, false is returned; any remaining expressions are not evaluated. If all the expressions evaluate to true values, the value of the last expression is returned. If there are no expressions then true is returned.
or: The expressions are evaluated from left to right. If any expression evaluates to a true value, that value is returned; any remaining expressions are not evaluated. If all expressions evaluate to false, or if there are no expressions, then false is returned.
Install and and or as new special forms for the evaluator by defining appropriate syntax procedures and evaluation procedures eval-and and eval-or. Alternatively, show how to implement and and or as derived expressions.
let
Exercise 4.6:Let expressions are derived expressions, because
(let ((⟨var₁⟩ ⟨exp₁⟩) … (⟨varₙ⟩ ⟨expₙ⟩))
⟨body⟩)
is equivalent to
((lambda (⟨var₁⟩ … ⟨varₙ⟩)
⟨body⟩)
⟨exp₁⟩
…
⟨expₙ⟩)
Implement a syntactic transformation let->combination that reduces evaluating let expressions to evaluating combinations of the type shown above, and add the appropriate clause to eval to handle let expressions.
Loops
Exercise 4.9: Many languages support a variety of iteration constructs, such as do, for, while, and until. In Scheme, iterative processes can be expressed in terms of ordinary procedure calls, so special iteration constructs provide no essential gain in computational power. On the other hand, such constructs are often convenient. Design some iteration constructs, give examples of their use, and show how to implement them as derived expressions.
BONUS
Adding let*
Exercise 4.7:Let* is similar to let, except that the bindings of the let* variables are performed sequentially from left to right, and each binding is made in an environment in which all of the preceding bindings are visible. For example
(let* ((x 3)
(y (+ x 2))
(z (+ x y 5)))
(* x z))
returns 39. Explain how a let* expression can be rewritten as a set of nested let expressions, and write a procedure let*->nested-lets that performs this transformation. If we have already implemented let(Exercise 4.6) and we want to extend the evaluator to handle let*, is it sufficient to add a clause to eval whose action is
(eval (let*->nested-lets exp) env)
or must we explicitly expand let* in terms of non-derived expressions?
Warm-Up
Modernizing our Interpreter
Racket or Biwa
Python
and and or
let
(let ((⟨var₁⟩ ⟨exp₁⟩) … (⟨varₙ⟩ ⟨expₙ⟩)) ⟨body⟩)((lambda (⟨var₁⟩ … ⟨varₙ⟩) ⟨body⟩) ⟨exp₁⟩ … ⟨expₙ⟩)Loops
BONUS
Adding let*
(let* ((x 3) (y (+ x 2)) (z (+ x y 5))) (* x z))(eval (let*->nested-lets exp) env)