p3-builtins.rkt

#lang racket

;; CIS352 -- P3 Builtins help
;;
;; I wrote up these notes based on some student meetings.
;; This project is intentionally a bit vague about how to
;; handle the builtins. That is because I want you to have
;; some ability to have the experience of figuring out how
;; you might want to engineer your own solution, considering
;; the various trade-offs.
;;
;; However, in the interests of giving you a bit of a head-
;; start, I will present two reasonable solutions.
;; (1) is easier to understand, (2) is what I sketch in the
;; starter code--it requires implementing "list lambdas,"
;; i.e., lambdas that accept lists, like:
;;     ((lambda l (second l)) 1 2 3) => 2
;; If you're feeling confused, do (1), if you're feeling
;; ambitious, try (2).
;; 
;;  (1) For every builtin in the environment, mark it as
;;     '(prim +) (or something). Then, when you evaluate a
;;     callsite (e0 e1 e2), if e0 is '+, then it will evaluate
;;     to '(prim +). Now, this will be another case you need
;;     to add to the application case: when you match on the
;;     result of (interp e0 env), you'll get back *maybe*
;;     a closure like '(closure (lambda (x ...) ...) ...),
;;     but now you *also* have to deal with things like
;;     '(prim +). For that, you just recognize: okay, applying
;;     a prim, make a Racket version of + and then apply it
;;     to the list of evaluated arguments to the function
;;
;;     Question: why not just make it 'prim? why '(prim +)?
;;     Answer: think about ((lambda (+) (+ 1 2)) -)
;;
;; (2) For every builtin in the environment, you add a closure
;;     like `(closure (lambda l (apply-prim + l)) ,(hash)).
;;     Then, when you get to (e0 e1 ...), you evaluate e0 and
;;     find that it's this new special type of closure that
;;     handles *lists* of arguments (this is a bonus case too,
;;     btw--but you also need to implement `apply` if you want
;;     the bonus credit). Now evaluate the argument list and
;;     bind it to the requisite variable. E.g., if you have
;;     '(closure (lambda l ...) (hash ...)) then you evaluate
;;     each of the es to get back a list vs (of values): you
;;     bind *the entire list vs* to the value l. Then, you
;;     also define the behavior of `apply-prim`. I do here:
;;     first evaluate the argument, then turn the prim into
;;     a Racket function using `eval` (as in (1)).


;; the easy way...
(define (interp e env)
  (match e
    [(? symbol? x) (hash-ref env x)]
    [`(lambda ,xs ,e-body) `(closure ,e ,env)]
    [(? number? n) n]
    ;; add more forms here...
    [`(,e0 ,es ...)
     (match (interp e0 env)
       [`(closure (lambda (,x) ,e-b) ,env+)
        (interp e-b (hash-set env+ x (interp e-b env+)))]
       [`(closure (lambda (,x ...) ,e-b) ,env+)
        ;; I'll leave this to you
        'todo]
       [`(prim ,op)
        ;; translate op, a symbol (like '+) to a *Racket function*
        (define op->rkt (eval op (make-base-namespace)))
        ;; We can't apply the symbol '+ to a list, but we can apply
        ;; the result of (eval '+). We need the extra parameter
        ;; (make-base-namespace) to tell Racket to load in the standard
        ;; library functions (like +)--otherwise you'll get an undefined
        ;; symbol error. eval is a weird function, and this is the
        ;; *only* place in the project it's permissible to use it.
        (apply op->rkt (map (λ (e) (interp e env)) es))])]))

;; example
(interp '(+ 1 (* 3 4)) (hash '+ '(prim +)
                             '* '(prim *)))

;; the harder way to do it: add an extra 'apply-prim form
;; that you include
(define (interp+ e env)
  (match e
    [(? symbol? x) (hash-ref env x)]
    [`(lambda ,xs ,e-body) `(closure ,e ,env)]
    ;; p had better be a symbol, lst had better be a variable
    [`(apply-prim ,p ,lst)
     (apply (eval p (make-base-namespace))
            (interp lst env))]
    [(? number? n) n]
    ;; add more forms here...
    [`(,e0 ,es ...)
     (match (interp+ e0 env)
       [`(closure (lambda (,x) ,e-b) ,env+)
        (interp+ e-b (hash-set env+ x (interp+ e-b env+)))]
       [`(closure (lambda (,x ...) ,e-b) ,env+)
        ;; I'll leave this to you
        'todo]
       [`(closure (lambda ,l ,e-b) ,env+)
        ;; extra credit, but necessary to handle it using apply-prim
        ;; I implemented this in my version--made sure it worked--and
        ;; then replaced it with 'todo
        'todo])]))

(interp+ '(+ 1 (* 3 4)) (hash '+ `(closure (lambda l (apply-prim + l)) ,(hash))
                              '* `(closure (lambda l (apply-prim * l)) ,(hash))))