Re: evaluater problem

On Jul 22, 11:50=A0am, fooor...@[EMAIL PROTECTED]
 wrote:
> I have to Write a procedure (rename exp) which renames all repeated
> declarations
> (parameters) in nested scopes. Modify =93eval-substitution.scm=94.
>
-------------------------------------------------------------------------=
------------
> eval-substitution.scm=94.
>
;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> ;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ evaluator core
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> ;;; Pre-conditions: The given expression is legal according to the
> concrete syntax.
> ;;; Inner 'define' expressions are not legal.
> ;;; Evaluator does not sup****t inner recursive procedures.
> (define (eval exp)
> =A0 (cond ((atomic? exp) (eval-atomic exp))
> =A0 =A0 =A0 =A0 ((special-form? exp) (eval-special-form exp))
> =A0 =A0 =A0 =A0 ((derived? exp) (eval-derived exp))
> =A0 =A0 =A0 =A0 (else (apply-procedure (eval (operator exp))
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0
=A0(list-of-v=
alues (operands exp))))))
>
> ;~~~~~~~~~~~~~~~~~~~~ atomic ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> (define (atomic? exp)
> =A0 (or (number? exp) (boolean? exp) (variable? exp)))
>
> (define (eval-atomic exp)
> =A0 (cond ((number? exp) exp)
> =A0 =A0 =A0 =A0 ((boolean? exp) exp)
> =A0 =A0 =A0 =A0 ((variable? exp) (lookup-variable-value exp))))
>
> ;~~~~~~~~~~~~~~~~~~~ special form ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
> (define (special-form? exp)
> =A0 (or (quoted? exp) (lambda? exp) (cond? exp) (definition? exp) (or?
> exp)))
>
> (define (eval-special-form exp)
> =A0 (cond ((quoted? exp) (text-of-quotation exp))
> =A0 =A0 =A0 =A0 ((lambda? exp) exp)
> =A0 =A0 =A0 =A0 ((cond? exp) (eval-cond exp))
> =A0 =A0 =A0 =A0 ((definition? exp) (eval-definition exp))
> =A0 =A0 =A0 =A0 ((or? exp) (eval-or exp))))
>
> (define (eval-cond exp)
> =A0 (let ((clauses =A0(cond-clauses exp)))
> =A0 =A0 (cond ((null? clauses) 'unspecified)
> =A0 =A0 =A0 =A0 =A0 ((or (and (cond-last-clause? clauses) (eq?
(cond-pred=
icate
> (cond-first-clause clauses)) 'else))
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(eval (cond-predicate (cond-first-clause
c=
lauses))))
> =A0 =A0 =A0 =A0 =A0 =A0(eval-sequence (cond-actions (cond-first-clause
(c=
ond-
> clauses exp)))))
> =A0 =A0 =A0 =A0 =A0 (else (eval-cond (make-cond (cond-rest-clauses
(cond-=
clauses
> exp))))))))
>
> ;;; Purpose: Handle define expression. Bind a variable to a value in
> the global environment.
> (define (eval-definition exp)
> =A0 (add-binding-to-environment (definition-variable exp) (eval
> (definition-value exp)))
> =A0 'ok)
>
> (define (eval-or exp)
> =A0 (if (null? (or-expressions exp))
> =A0 =A0 =A0 #f
> =A0 =A0 =A0 (let ((or-first-result (eval (or-first-expression exp))))
> =A0 =A0 =A0 =A0 (if (or (=3D (length (or-expressions exp)) 1)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 or-first-result)
> =A0 =A0 =A0 =A0 =A0 =A0 or-first-result
> =A0 =A0 =A0 =A0 =A0 =A0 (eval (make-or (or-rest-expression exp)))))))
>
>
;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> ;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ derived expressions ( syntactic
> sugars ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> (define (derived? exp)
> =A0 (or (if? exp) (let? exp)))
>
> (define (eval-derived exp)
> =A0 (cond ((if? exp) (eval (if->cond exp)))
> =A0 =A0 =A0 =A0 ((let? exp) (eval (let->combination exp)))))
>
> ;;;Pre-condition: (if? exp)
> (define (if->cond exp)
> =A0 (let ((first-predicate =A0(if-predicate exp))
> =A0 =A0 =A0 =A0 (first-actions (list (if-consequent exp)))
> =A0 =A0 =A0 =A0 (second-actions (list (if-alternative exp))) )
> =A0 =A0 (let ( (first-clause (make-cond-clause first-predicate first-
> actions))
> =A0 =A0 =A0 =A0 =A0 =A0(second-clause (make-cond-clause 'else
second-acti=
ons)) )
> =A0 =A0 =A0 =A0 =A0 (make-cond (list first-clause second-clause))
> =A0 =A0 =A0 =A0 )))
>
> ;;; Pre-conditions: (let? exp)
> (define (let->combination exp)
> =A0 (make-application (make-lambda (let-variables exp) (let-body exp))
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (let-initial-values exp)))
>
> ;~~~~~~~~~~~~~~~~~ application ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
> (define (apply-procedure procedure arguments)
> =A0 (cond ((lambda? procedure)
> =A0 =A0 =A0 =A0 =A0(eval-sequence
> =A0 =A0 =A0 =A0 =A0 (substitute (lambda-body procedure)
(lambda-parameter=
s
> procedure) arguments)))
> =A0 =A0 =A0 =A0 ((defined-proc-in-global? procedure)
> =A0 =A0 =A0 =A0 =A0(apply-primitive-procedure procedure arguments))
> =A0 =A0 =A0 =A0 (else
> =A0 =A0 =A0 =A0 =A0(error
> =A0 =A0 =A0 =A0 =A0 "eval: Illegal procedure" procedure))))
>
> (define (eval-sequence exps)
> =A0 (cond ((null? (cdr exps)) (eval (car exps)))
> =A0 =A0 =A0 =A0 (else (eval (car exps))
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 (eval-sequence (cdr exps)))))
>
> (define (apply-primitive-procedure proc args)
> =A0 (apply proc args)) ; apply in underlying Scheme
>
> ;;; list-of-values is used in 'eval'.
> (define (list-of-values exps)
> =A0 (if (no-operands? exps)
> =A0 =A0 =A0 ()
> =A0 =A0 =A0 (cons (eval (first-operand exps))
> =A0 =A0 =A0 =A0 =A0 =A0 (list-of-values (rest-operands exps)))))
>
> ;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> ;~~~~~~~~~~~~~~~~ substitute procedures ~~~~~~~~~~~~~~~~~~~~~~~~~~~
> ;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> ;;; Pre-conditions: substitute is not performed on 'define' or 'let'
> expressions
> ;;; or expression containing such sub-expressions.
> (define (substitute exp vars vals)
> =A0 (letrec (( substitute-var-val
> =A0 =A0 =A0 =A0 =A0 =A0 =A0(lambda (exp var val)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(cond ((or (number? exp) (quoted? exp)
(bo=
olean? exp))
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 exp)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0((variable? exp)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (if (and (eq? exp var))
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 val ;; substitute
fre=
e occurrence of var
> with val
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 exp))
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0((lambda? exp)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (if (memq =A0var
(lambda-para=
meters exp))
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 exp
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (make-lambda
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0
=A0(lambda-parameters=
 exp)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(map (lambda (e)
(=
substitute-var-val e var
> val))
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0
(lambda-b=
ody
> exp)))) )
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(else ; expression is a list
o=
f expressions:
> application, cond.
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (map (lambda(e)
(substitute-v=
ar-val e var val))
> exp)))) ))
> =A0 =A0 (if (and (null? vars) (null? vals))
> =A0 =A0 =A0 =A0 exp
> =A0 =A0 =A0 =A0 (substitute
> =A0 =A0 =A0 =A0 =A0(substitute-var-val exp (car vars) (car vals))
> =A0 =A0 =A0 =A0 =A0(cdr vars)
> =A0 =A0 =A0 =A0 =A0(cdr vals))
> =A0 =A0 =A0 =A0 ) ))
>
>
;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> ;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ global environment ADT
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
> (define global-environment
> =A0 (list
> =A0 =A0; primitive procedures
> =A0 =A0(list 'car car)
> =A0 =A0(list 'cdr cdr)
> =A0 =A0(list 'cons cons)
> =A0 =A0(list 'null? null?)
> =A0 =A0(list 'list list)
> =A0 =A0(list 'length length)
> =A0 =A0(list '+ +)
> =A0 =A0(list '* *)
> =A0 =A0(list '> >)
> =A0 =A0(list '< <)
> =A0 =A0(list '- -)
> =A0 =A0(list '=3D =3D)
> =A0 =A0(list 'expt expt)
> =A0 =A0))
>
> (define (lookup-variable-value var)
> =A0 (if (assoc var global-environment)
> =A0 =A0 =A0 (cadr (assoc var global-environment))
> =A0 =A0 =A0 (error "variable is not defined" var )))
>
> (define (defined-proc-in-global? proc)
> =A0 (member proc (map cadr global-environment)))
>
> (define (add-binding-to-environment var val)
> =A0 (set! global-environment (cons (list var val) global-environment)))
>
-------------------------------------------------------------------------=
------------------------------------------
> The procedure may have internal procedures defined using letrec. Use
> parser
> procedures to get and build the expressions components.
> Use the primitive procedure gensym to give a new variable name. For
> example,> (gensym)
> g305
> > (gensym)
>
> g306
> Here are some examples of how rename is expected to work:>(rename 3)
> 3
> >(rename '(quote r))
> 2
> >r
> >(rename '(x 3))
> (x 3)
> >(rename '(lambda(x y)
>
> (* x y)))
> (lambda (x y) (* x y))>(rename '(lambda(x y)
>
> (* ((lambda(y z)
> (+ y x)) x y
> )
> y)))
> (lambda (x y)
> (* ((lambda (g423 z)
> (+ g423 x)) x y
> )
> y))>(rename '(lambda(x y)
>
> (* ((lambda(y z)
> (+ y ((lambda (x)
> x)
> x)))
> x y)
> y)))
> (lambda (x y)
> (* ((lambda (g446 z)
> (+ g446 ((lambda (g445)
> g445)
> x)))
> x y)
> y))
> Hint: review the substitute procedure and take ideas from it. The
> procedure
> rename may be similar to substitute and may even call substitute.
> The contract
> ;;; 1. Signature: (rename exp)
> ;;; 2. Type: Expression -> Expression
> ;;; 3. Purpose: renames all repeated declarations (parameters) in
> nested scopes.
> ;;; 4. Example: above.
> ;;; 5. Pre-conditions: exp is a legal expression.
> ;;; 6. Post-conditions: the result is an expression with identical
> functionality to
> exp.
> ;;; 7. Tests:

Sorry, we cant do your homework for you...