chenyukang/eopl

my solutions to EOPL3

My answers for EOPL3

Base/libs

This is all the original code from the book. I have some modification on utilities.

Ch

My answer code for the exercises, NOT all problem are solved, so any complement is welcome.

Usually the function call (run-all) and (check-all) will run all the test-cases.

Before chapter 8, I put all the code for an interpreter in single file.

Begin with chapter 8, I put base code in the base directory of each chapter, and load it when necessary.

Note

The code are tested on Chicken Scheme with chicken-slime in Emacs, and assumed to be runnable for most other Scheme implementation.

Contribution

Please fire an issue or give Pull Request for any bug, Thanks!

mailto:[email protected]

How to run and debug these programs

• Install Chicken Scheme.
• Clone this Github repo to your local directory (e.g. ~/Desktop/).
• Access to the directory of a chapter (e.g. ~/Desktop/eopl/ch3).
• Run the following command on your terminal: csi xxx.scm

eopl's Issues

ch3引用的问题

ch3中从05.scm以后的文件中，第二行的＂(load-relative "../libs/environments.scm)"是有问题的，environment.scm不在libs中，倒是在ch3/base/下发现了此文件。但是environment.scm缺少load-relative data-structures语句。

Chapter 5 Exercise 5.7

I think the let implementation of ch5/07.scm is not correct.

The environment of evaluating variables should used the current environment instead of the extended environment with each new variable.

So given following test case, the answer should be 1 instead of 2. (same in the book 74 page, 3.16)

let x = 30
in let x = -(x,1)
         y = -(x,2)
    in -(x,y)

I suggest the following solution

(let-exp-cont (vars exps body binding-eval-env body-eval-env saved-cont)
  (if (null? exps)
    (value-of/k body (extend-env (car vars) val body-eval-env) saved-cont)
    (value-of/k (car exps)
                binding-eval-env
                (let-exp-cont
                  (cdr vars)
                  (cdr exps)
                  body
                  binding-eval-env
                  (extend-env (car vars) val body-eval-env)
                  saved-cont))))

Exercise 1.12 has some problem.

It can't get the right answer if the "slist" is something like (a b c (a b c) (a b)).

a small bug in 23.scm

(run "let makemult = proc (maker) proc (x) proc(y)
if zero?(x) then 0
else -((((maker maker) -(x, 1)) y), -(0, y))
in let times = proc(x) proc(y)
(((makemult makemult) x) y)
in ((times 3) 8)")

;; the answer shoud be (num-val 24) :)

exercise 1.13 has a question.

Should need (null? slist) test with the definition of kleene star pattern ?

My solution to exercise 3.34

; empty-env : () → Env
(define empty-env
(lambda ()
(lambda (op)
(cond
[(eqv? op 'envrionment?) #t]
[(eqv? op 'empty?) #t]
[(eqv? op 'search)
(lambda (search-var)
(eopl:error 'empty-env))]
[else (eopl:error 'empty-env)]))))

; extend-env : Var × SchemeVal × Env → Env
(define extend-env
(lambda (saved-var saved-val saved-env)
(lambda (op)
(cond
[(eqv? op 'envrionment?) #t]
[(eqv? op 'empty?) #f]
[(eqv? op 'search)
(lambda (search-var)
(if (eqv? search-var saved-var)
saved-val
(apply-env saved-env search-var)))]
[else (eopl:error 'extend-env)]))))

; extend-env : Var × Var × Expression × Env → Env
(define extend-env-rec
(lambda (proc-name bound-var proc-body saved-env)
(letrec ((env
(lambda (op)
(cond
[(eqv? op 'envrionment?) #t]
[(eqv? op 'empty?) #f]
[(eqv? op 'search)
(lambda (search-var)
(if (eqv? search-var proc-name)
(proc-val (procedure bound-var proc-body env))
(apply-env saved-env search-var)))]
[else (eopl:error 'extend-env-rec)]))))
env)))

; apply-env : Env × Var → SchemeVal
(define apply-env
(lambda (env search-var)
((env 'search) search-var)))

(define environment?
(lambda (env)
(if (procedure? env)
(env 'envrionment?)
#f)))

exercise 4.9

Why this implementation costs linear time?

When invoke new-ref, shouldn't it cost O(n) time?