this post was submitted on 21 Nov 2023
1 points (100.0% liked)

Lisp

53 readers
3 users here now

founded 1 year ago
MODERATORS
 

In the eval function of chapter 4 we have different eval-foo...s, which deal with the special syntax. Why the apply function is not just part of eval function. So we could have some dispatch condition in case analysis such as ...((application? exp) (eval-application exp env))... . Why do we make it harder?

you are viewing a single comment's thread
view the rest of the comments
[–] zyni-moe@alien.top 1 points 11 months ago

Because eval is what defines what the syntax of the language is, while apply has nothing to do with syntax at all but only semantics. Imagine a lisp which was in latin. You would need to change eval but not apply. Or if there are larger changes to syntax: apply remains unchanged in all these cases.

In same way, with a slight variant of apply (it must get an environment object as well as function and arguments) then you can change the scoping rules of your Lisp while making no changes at all to eval but only to apply. Such an evaluator is here (in Racket):

#lang racket

;;;; Tiny lisp evaluator which can have dynamic or lexical scope
;;;
;;; Based on tlisp
;;;

(module+ test
  (require rackunit))

(define empty-environment '())

(define (extend-environment env variables values)
  (match* (variables values)
    [('() '())
     env]
    [((cons (? symbol? variable) more-variables)
      (cons value more-values))
     (extend-environment (cons (cons variable value) env)
                         more-variables more-values)]
    [('() _)
     (error 'extend-environment "not envough variables")]
    [(_ '())
     (error 'extend-environment "not enough values")]
    [(_ _)
     (error 'extend-environment "what even is this")]))

(define lexical-scope? (make-parameter #t))

(define (bound? var env)
  (and (assq var env) #t))

(define (value-of var env)
  (unless (bound? var env)
    (error 'value-of "~S is unbound" var))
  (cdr (assq var env)))

(struct primitive
  (fn))

(struct function
  (formals body environment))

(define (evaluate form environment)
  (match form
    [(? symbol? s)
     (value-of s environment)]
    [(list op arguments ...)
     (case op
       [(quote)
        (match arguments
          [(list thing)
           thing]
          [_
           (error 'evaluate "ill-formed quote")])]
       [(lambda λ)
        (match arguments
          [(list (list (? symbol? formals) ...) body ...)
           (function formals body environment)]
          [_
           (error 'evaluate "ill-formed λ")])]
       [(if)
        (match arguments
          [(list test then else)
           (if (evaluate test environment)
               (evaluate then environment)
               (evaluate else environment))]
          [(list test then)
           (when (evaluate test environment)
             (evaluate then environment))]
          [_
           (error 'evaluate "ill-formed if")])]
       [else
        (applicate (evaluate op environment)
                   (map (λ (a) (evaluate a environment))
                        arguments)
                   environment)])]
    [(? cons?)
     (error 'evaluate "evaluating a cons which is not a list")]
    ['()
     (error 'evaluate "null")]
    [something
     something]))

(define (applicate f arguments dynamic-environment)
  (match f
    [(primitive fn)
     (apply fn arguments)]
    [(function formals body lexical-environment)
     (define extended-environment (extend-environment
                                   (if (lexical-scope?)
                                       lexical-environment
                                       dynamic-environment)
                                   formals arguments))
     (let evb ([value (void)]
               [forms body])
       (match forms
         ['()
          value]
         [(cons form more)
          (evb (evaluate form extended-environment)
               more)]))]
    [_
     (error 'applicate "what even is this")]))

(module+ test
  (check-true
   (evaluate
    '((λ (cons car cdr nil)
        ((λ (c)
           (if (eqv? (car c) 1)
               (if (eqv? (cdr c) 2)
                   #t
                   #f)
               #f))
         (cons 1 2)))
      (λ (a b)
        (λ (s) (s a b)))
      (λ (c)
        (c (λ (a b) a)))
      (λ (c)
        (c (λ (a b) b)))
      (λ ()))
    (extend-environment empty-environment
                        '(eqv?) (list (primitive eqv?))))))

(module+ test
  (check-eqv?
   (parameterize ([lexical-scope? #t])
     (evaluate
      `((λ (x)
          (((λ (x)
             (λ () x))
            20)))
        10)
      empty-environment))
   20)
  (check-eqv?
   (parameterize ([lexical-scope? #f])
     (evaluate
      `((λ (x)
          (((λ (x)
             (λ () x))
            20)))
        10)
      empty-environment))
   10))