re-fun-valof.rkt

#lang racket

#| What does our valof defunctionalize? |#

;; So far we fully defunctionalized environments and closures. Rather
;; than explicit higher-order function calls, we instead dispatch
;; against the choices, where we have represented each choice with a
;; corresponding data structure.

;; Josh
  ;; Env is a function; translate to a data structure to avoid passing
    ;; functions in closure creation and fn application.
  ;; Closure is a function; translate to a data structure to
    ;; avoid passing function in fn application.

#| NOTE - Removed to make way for functional variants later in doc that make `(define apply (lambda (c a) (c a)))` hold

(define (make-closure x b env)
  `(closure ,x ,b ,env))

(define (apply-closure c a)
  (match c
    [`(closure ,x ,b ,env) 
     (valof b (extend-env x a env))]))
|#

(define (extend-env x a env)
  `(extension ,x ,a ,env))

(define (empty-env)
  `(empty))

(define (apply-env env y)
  (match env
    [`(empty) (error "unbound id" y)]
    [`(extension ,x ,a ,env) 
      (if (eqv? x y) a (apply-env env y))]))

;; However, we began with one match expression already: in valof. We
;; didn't start by defunctionalizing higher-order functions to get
;; here. But morally, we should have. What did we defunctionalize in
;; order to create these first-order data structures?

(define (valof-defun exp env)
  (match exp
    [`,n #:when (number? n) n]
    [`(+ ,ne1 ,ne2) (+ (valof ne1 env) (valof ne2 env))]
    ;; the core 
    [`,y #:when (symbol? y) (apply-env env y)]
    [`(lambda (,x) ,b) (make-closure x b env)]
    [`(,rator ,rand) (apply-closure (valof rator env) (valof rand env))]))

;; In principle, we shouldn't be constructing programs willy-nilly. We
;; oughtn't be building raw syntax. Instead each of these forms ought
;; to be the result of some syntax constructors.

;; Josh
  ;; Why would we want to obfuscate the language that we're implementing
  ;; by using syntax constructors?
  ;; Ah (reading ahead) - because we want to be able to represent expressions
  ;; as functions over environments. 

#| NOTE - Remove naming collisions
(define (make-plus ne1 ne2)
  `(+ ,ne1 ,ne2))

(define (make-lambda x b)
  `(lambda (,x) ,b))

(define (make-app rator rand)
  `(,rator ,rand))
|#
  
;; With these latter ones, we don't need to use (can no longer)
;; fancier operations w/Racket's pattern matching. Truth be told, we
;; were cheating all along by using Racket's special operations.

;; Josh
  ;; Under what rules are we cheating?
  ;; Also... What fancy operations can we not use w.r.t Racket pattern matching?
  ;; > (match ((lambda () `(foo))) [`(foo) `(bar)])
  ;; '(bar)
  ;; > (match ((lambda () `(foo))) [`(,x) #:when (symbol? x) `(bar)])
  ;; '(bar)
  ;; Ahh.. Correct me if I'm wrong, but you mean the functional expressions further below

#| NOTE - Remove naming collisions
(define (make-sym s)
  `(symbol ,s))

(define (make-num n)
  `(number ,n))
|#
  
;; These are the constructors that we ontensibly used to *build* our
;; programs, rather than constructing their (internal) syntax
;; directly.

;; But further---from what higher-order function representation did we
;; defunctionalize them to get these data structure representations?
;; We can follow the pattern and the usual clues. What did we do
;; before to construct the match clauses of our `apply` functions? We
;; took the bodies of the higher-order functions and the parameter
;; lists, constructed data structures in those constructors, and then
;; matched against them in the `apply` version.

;;Josh
  ;; So... Did you defunctionalize from this representation or refunctionalize to this


;; Josh - Added functional variant
(define (make-closure x b env)
  (lambda (a) (valof b (extend-env x a env))))

;; Josh - Added functional variant
(define (apply-closure c a) (c a))

(define (make-plus ne1 ne2)
  (lambda (env)
    (+ (valof ne1 env) (valof ne2 env))))

(define (make-lambda x b)
  (lambda (env)
    (make-closure x b env)))

(define (make-app rator rand)
  (lambda (env)
    (apply-closure (valof rator env) (valof rand env))))

(define (make-sym s)
  (lambda (env)
    (apply-env env s)))

(define (make-num n)
  (lambda (env)
    n))

(define (valof exp env)
  (exp env))

;; We don't normally begin writing or expressing intepreters in this
;; style. But why not? If it's so critical to first expose students to
;; the denotations of environments and closures, then why isn't it
;; equally important to expose them first to the denotations of
;; expressions?

;; Josh
  ;; The literal concept of an expression, the vertical slice of the expression,
  ;; separated from valof. Valof only concerns itself with evaluating the expression.
  ;; No parsing necessary.
  ;; Expr : Environment -> *
  ;; Valof : Expr x Environment -> *

;; Josh
  ;; Reminds me of the valof variant where we distribute the env into each match expression. 
  ;; 1. (define (valof exp) (match (exp) (`,x #:when (symbol? x) (lambda (env) (env x)))))
  ;;   a. ((valof ...) empty-env)
  ;; 
  ;; This is interesting, though, because even though the env is distributed across expressions;
  ;; the entire interpreter seems inverted.
  ;;
  ;; Reminds me of this functional list implementation. Representing data as functions allows us
  ;; to avoid dereferencing|parsing|etc
(define (carJ ls) (lambda (a d) a))
(define (cdrJ ls) (lambda (a d) d))
(define (consJ a d) (lambda (pick) (pick a d)))

;; Further, if I wanted to express to a code-reading student the
;; importance of compositionality, I would ask that student to
;; implement a new form for my language in this setting. I think that
;; underlines it especially well.

;; Josh
  ;; Agreed
  
;; This means, though, that we should have a
;; representation-/de/pendent, *functional* version of this same
;; structure. What should *that* be? What kind of thing is that?

;; /That/ is the denotation of a program:

(lambda (env)
  (apply-closure
   (valof 
    (lambda (env)
      (apply-closure
       (valof (lambda (env)
                (make-closure 'x
                              (lambda (env)
                                (make-closure 'y (make-sym 'x) env))
                              env))
              env)
       (valof (lambda (env) '5) env)))
    env)
   (valof (lambda (env) '6) env)))
;; (This is what *I* call functional programming :-)

;; Josh
  ;; I've never met anybody who loves unrolling things as much as you, Jason.
  ;; That being said, what makes the above different from the below,
  ;; minus some substitutions? Isn't it a given that substituting
  ;; the bodies of the functional builders would give you a rep-dep
  ;; functional version?

(define test (make-app (make-app (make-lambda 'x (make-lambda 'y (make-sym 'x))) (make-num 5)) (make-num 6)))

;; It was a little bothersome that eval ended up being so much bigger
;; than apply. We have many more forms of syntax than we have kinds of
;; closures to apply. But this also relieves that fundamental
;; disparity.

;; With this version, both eval and apply are simple, one-line
;; functions. They are in fact syntactically /identical/ functions,
;; and they look more like true mirror images or a Yin-Yang pair than
;; they had defunctionalized.

;; Josh
  ;; This is slick

(lambda (c a)
  (c a))

(lambda (expr env)
  (expr env))

;; Here, an expression is truly a function from environments to values

;; Josh
  ;; #t - why is this desirable? Are expressions generally thought of as `Environment -> *` in literature?

;; The same way a closure is truly a function from values to values

;; Josh
  ;; #t

;; A lambda expression is not a closure. A lambda is a function that
;; first takes an environment.

;; Josh
  ;; And returns a closure when given an environment?
  ;; What's seen by the user of the language vs what's work is done
  ;; internally within the interpreter is important here
    ;; AKA - As a user of this language, a lambda _looks_ and _behaves_
    ;; like a closure, but under the hood it is not.
  ;; btw - this seems like a difference that could easily trip up a student,
  ;; especially considering that they're using Racket lambdas. To drive the point,
  ;; maybe a brief rename from `make-lambda` to something like `make-function` would
  ;; elucidate that difference.

;; When we say "closures are values", this denotationally means that
;; functions from values to values are *themselves* values.

;; Josh
  ;; #t

;; Further I think this gives one *more* view on how small-but-big is
;; the mistake of implementing dynamic scope instead of lexical
;; scope.

;; Josh
  ;; It's late and I'm rusty, but I want to make our `make-app` take
  ;; an additional `env` parameter to evaluate functions in the calling
  ;; environment.
  ;; It's not immediately clear to me how you'd allow this without exposing
  ;; the environment to the user, which seems like a bad idea.

(define (make-app rator rand env)
  (lambda (_env)
    (apply-closure (valof rator env) (valof rand env))))

;; There is still a really interesting story to tell here wrt
;; continuations

;; Josh
  ;; For another night.