Implementing lambda statement in Scheme?

Question

I am trying to write an interpreter for Scheme using Scheme, I implemented if let define statements and some other numerical operations, but I have no idea how to start to implement lambda procedure. Below is my current situation. It would be much appreciated if you can point me into the right direction.

(define get-operator (lambda (op-symbol)
  (cond
    ((equal? op-symbol '+) +)
    ((equal? op-symbol '-) -)
    ((equal? op-symbol '*) *)
    ((equal? op-symbol '/) /)
    (else (error "s6-interpret: operator not implemented -->" op-symbol)))))

(define if-stmt? (lambda (e)
  (and (list? e) (equal? (car e) 'if) (= (length e) 4))))

(define letstar-stmt? (lambda (e)
  (and (list? e) (equal? (car e) 'letstar) (= (length e) 3))))

(define let-stmt? (lambda (e)
  (and (list? e) (equal? (car e) 'let) (= (length e) 3))))

(define define-stmt? (lambda (e)
  (and (list? e) (equal? (car e) 'define) (symbol? (cadr e)) 
                                            (= (length e) 3))))

(define get-value (lambda (var env)
  (cond
    ((null? env) (error "s6-interpret: unbound variable -->" var))
    ((equal? (caar env) var) (cdar env))
    (else (get-value var (cdr env))))))

(define extend-env (lambda (var val old-env)
  (cons (cons var val) old-env)))

(define repl (lambda (env)
  (let* (
    (dummy1 (display "cs305> "))
    (expr (read))
    (new-env (if (define-stmt? expr)
               (extend-env (cadr expr) (s6-interpret (caddr expr) env) env)
               env))
    (val (if (define-stmt? expr)
           (cadr expr)
           (s6-interpret expr env)))
    (dummy2 (display "cs305: "))
    (dummy3 (display val))
    (dummy4 (newline))
    (dummy4 (newline)))
   (repl new-env))))

(define s6-interpret (lambda (e env)
  (cond
    ((number? e) e)
    ((symbol? e) (get-value e env))
    ((not (list? e)) (error "s6-interpret: cannot evaluate -->" e))
    ((if-stmt? e) (if (eq? (s6-interpret (cadr e) env) 0) 
                    ( s6-interpret (cadddr e) env) 
                    ( s6-interpret (caddr e) env)))
    ((let-stmt? e)
      (let ((names (map car  (cadr e)))
            (inits (map cadr (cadr e))))
        (let ((vals (map (lambda (init) (s6-interpret init env)) 
                         inits)))
          (let ((new-env (append (map cons names vals) env)))
            (s6-interpret (caddr e) new-env)))))
    (else
      (let ((operands (map s6-interpret (cdr e)
                        (make-list (length (cdr e)) env)))
            (operator (get-operator (car e))))
        (apply operator operands))))))

(define cs305 (lambda () (repl '())))

you have some parentheses mix-up near the end of code (around 5th line from bottom). — Will Ness
– Will Ness, Commented May 31, 2013 at 14:34

Will Ness · Accepted Answer · 2022-06-26 19:40:39Z

You'll find all the needed information to get you started in SICP, under the sections titled "Representing procedures" and "Combinations", refer to the linked book for all the referenced code.

Basically, you'll have to add two extra cases in eval, one for evaluating lambda expressions (it's easy!) and one for actually executing them: this last one must check if the expression being evaluated is a procedure application, and if so it evaluates (i.e. finds the value of) the operator and the list of operands, and then applies the value of the operator to the values of those operands.

Here's the gist of it, notice that evaluating a lambda form is really simple, the interesting part is the implementation of apply, that depending on the operator type invokes either a primitive procedure or a compound procedure (a lambda) on the operands - in turn, applying a compound procedure entails the evaluation of the sequence of its instructions and capturing and extending its environment. You must adapt this to your own implementation:

(define (eval exp env)
  (cond ... ; other cases
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ... ; other cases
        ((application? exp)
         (apply (eval (operator exp) env) ; eval calls apply
                (list-of-values (operands exp) env)))
        (else (error "Unknown expression type -- EVAL" exp))))

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence ; apply calls eval
          (procedure-body procedure)
          (extend-environment
           (procedure-parameters procedure)
           arguments
           (procedure-environment procedure))))
        (else (error "Unknown procedure type -- APPLY" procedure))))

(define (lambda? exp)
  (tagged-list? exp 'lambda))

(define (compound-procedure? p)
  (tagged-list? p 'procedure))

(define (make-procedure parameters body env)
  (list 'procedure parameters body env))

(define (list-of-values exps env)
  (if (no-operands? exps)
      '()
      (cons (eval (first-operand exps) env)
            (list-of-values (rest-operands exps) env))))

(define (eval-sequence exps env)
  (cond ((last-exp? exps) (eval (first-exp exps) env))
        (else (eval (first-exp exps) env)
              (eval-sequence (rest-exps exps) env))))

(define (extend-environment vars vals base-env)
  (if (= (length vars) (length vals))
      (cons (make-frame vars vals) base-env)
      (if (< (length vars) (length vals))
          (error "Too many arguments supplied" vars vals)
          (error "Too few arguments supplied" vars vals))))

Collectives™ on Stack Overflow

Implementing lambda statement in Scheme?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related