#lang racket
;; Programs as Data in Racket -- subset interpreter
;; CS 251
;;
;; Programs and lists are both expressed with S-expressions
;; in Racket.  This means that it is really easy to write
;; programs that manipulate other programs as data.
;;
;; This file contains our first interpreter.
;; We will return to examine interpreters
;; more carefully (and in different styles) later in the semester.
;;
;; This interpreter is a simple Racket subset evaluator.
;; It differs from McCarthy's definition of eval in a few ways,
;; including using lexical scoping, but lacking recursion.
;; We'll wait until later to look at ways of implementing recursion.
;;
;; Try the following:
;;
;; - experiment calling reval and desugar to check their correctness
;;   and understand their relation to the evaluation rules and
;;   syntactic sugar definitions we have discussed.
;;
;; - add special forms (for exactly two arguments): +, -, *, /
;;
;; - add syntactic sugar: let with multiple bindings, or, cond
;;
;; - define a function reval-nice that takes only one
;;   argument (a quoted expression), desugars it, and
;;   evaluates the resulting expression in an environment
;;   with bindings such that null?, cons?, eq?, car, cdr, cons,
;;   +, -, *, / are bound to closures and can thus be treated
;;   as first-class functions in programs.
;;   This requires NO changes to reval itself.  You may build the
;;   initial environment either by "pre-evaluating" some function
;;   definitions to build the environment before getting to the
;;   actual program.  Or, you can explicitly build closure objects
;;   and add them to the environment directly.
;;
;; Remember to disinguish between Racket expressions and values
;; in the implementation language and the *representation* of
;; expressions and values used to implement the source language.

;; Lookup the variable sym in the environment env.
;; Environments are association lists.
(define (lookup sym env)
  (cond [(null? env) (error "no such variable")]
        [(eq? sym (caar env)) (cdar env)]
        [#t (lookup sym (cdr env))]))

;; Return the new environment extending env
;; by binding each of the variables in vars
;; to the corresponding value in args.
;; args must contain only values, not unevaluated expressions
(define (bind-all env vars args)
  (if (null? vars)
      env
      (cons (cons (car vars) (car args))
            (bind-all env (cdr vars) (cdr args)))))

;; Evaluate quoted expression e in environment env.
;; Each branch of this definition corresponds to the
;; evaluation rule we have discussed for the given
;; expression.
(define (reval e env)
  (cond
    ; values evaluate to themselves
    [(or (null? e) (boolean? e) (number? e)) e]
    
    ; variables evaluate to their bound value in the current environment
    [(symbol? e) (lookup e env)]
    
    ; application '(<e1> ... <en>)
    ; special forms
    ; '(null? <e1>) ; evaluate e1 and check if the result is null
    [(eq? (car e) 'null?)   (null? (reval (cadr   e) env))]
    
    ; '(cons? <e1>) ; evaluate e1 and check if the result is a cons cell
    [(eq? (car e) 'cons?)   (cons? (reval (cadr   e) env))]
    
    ; '(eq? <e1> <e2>) ; evaluate e1 and e2 and check if they are equal
    [(eq? (car e) 'eq?)     (eq?   (reval (cadr   e) env)
                                   (reval (caddr  e) env))]
    
    ; '(car <e1>) ; evaluate e1 and get its car
    [(eq? (car e) 'car)     (car   (reval (cadr   e) env))]
    
    ; '(cdr <e1>) ; evaluate e1 and get its cdr
    [(eq? (car e) 'cdr)     (cdr   (reval (cadr   e) env))]
    
    ; '(cons <e1> <e2>) ; evaluate e1 and e2 and create a cons cell of them
    [(eq? (car e) 'cons)    (cons  (reval (cadr   e) env)
                                   (reval (caddr  e) env))]
    
    ; '(if <e1> <e2> <e3>) ; if e1 evaluates to true, evaluate e2, else evaluate e3
    [(eq? (car e) 'if)      (if    (reval (cadr   e) env)
                                   (reval (caddr  e) env)
                                   (reval (cadddr e) env))]


    ; ... add functions later ...
    ))
    
    
;; Support for desugaring.
;; To use a program with sugar, first desugar it before evaluating it:
;; (reval (desugar '(and #f #t)) null)

;; Mapping: sugar -> desugaring rule
;; An association list where:
;; - Each key is the symbol indentifying an expression.
;; - Each value is the rule for desugaring such an expression.
;;   The rule is a function that takes the sugar expression
;;   as an argument and returns the desugared version.
;; Note the storage of functions in a data structure!
(define sugars
  (list
   ; '(and <e1> <e2>) -> '(if <e1> <e2> #f)
   ; This rule says: given an expression of the form '(and <e1> <e2>)
   ; it should be replaced by an expression '(if <e1> <e2> #f).
   ; Each 
   ; Each function in this association list takes the whole expression
   ; as an argument.
   (cons 'and
         (lambda (e) (list 'if (desugar (cadr e)) (caddr e) #f)))
   ; '(let ([x <e1>]) <e2>) -> '((lambda (x) <e2>) <e1>)
   ; Multiple bindings not currently supported.
   (cons 'let
         (lambda (e)
           (let ([binding (caadr e)]
                 [body (caddr e)])
             (list (list 'lambda (list (car binding)) body) (cadr binding)))))))

;; Recursively desugar an expression e using the rules given above.
(define (desugar e)
  (if (or (null? e) (boolean? e) (number? e) (symbol? e))
      e ; values and variables need no desugaring
      ; Otherwise, if this is a larger sugar expression...
      ; (assoc is like lookup, but returns
      ; the (key . value) pair if found and #f if not found)
      (let([sugar-rule (assoc (car e) sugars)])
        (if sugar-rule
            ; If this expression is sugar, then
            ; desugar this expression using the given rule
            ; and then desugar the result (to desugar subexpressions).
            (desugar ((cdr sugar-rule) e))
            ; otherwise this expression is not sugar, buts its
            ; subexpressions should be desugared.
            (map desugar e)))))