Pick one language: scheme or python(you can do the other as a bonus).
Warm-Up
Add primitive procedures for doing arithmetic, creating lists, and printing.
You should be able to interpret your lab 0 submission.
Modernizing our Interpreter
Scheme
Use a hashtable(biwahashtables or racket hash-tables) 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)
Add set!
Allow define to declare procedures using the MIT style, 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₁⟩) … (⟨varn⟩ ⟨expn⟩))
⟨body⟩)
is equivalent to
((lambda (⟨var₁⟩ … ⟨varn⟩)
⟨body⟩)
⟨exp₁⟩
…
⟨expn⟩)
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.
do/for/while/until loop
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?
Write a LISP in the other option: Python or Scheme(or Lua)
Warm-Up
Modernizing our Interpreter
Scheme
Python
and and or
let
(let ((⟨var₁⟩ ⟨exp₁⟩) … (⟨varn⟩ ⟨expn⟩)) ⟨body⟩)((lambda (⟨var₁⟩ … ⟨varn⟩) ⟨body⟩) ⟨exp₁⟩ … ⟨expn⟩)do/for/while/until loop
BONUS
Adding let*
(let* ((x 3) (y (+ x 2)) (z (+ x y 5))) (* x z))(eval (let*->nested-lets exp) env)Write a LISP in the other option: Python or Scheme (or Lua)
Learning Goals