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'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))))