5 Assignment 5: Defunctionalization

Assignment

Place your code in a file named a5.rkt and submit it to Autograder.

In this assignment, we will extend the language in Assignment 4: Interpreters to add data structures built using cons. Because cons can store any two values together as one value (even if the two values are themselves built using cons), our language will be able to handle data of unlimited size.

Because we sometimes represent closures using data structures, we need to take extra care so that values built using cons in our language stay disjoint from values built using λ in our language. To keep the two kinds of values disjoint, we cannot just define values by the grammar

Value	=	Number
	\|	Boolean
	\|	Closure
	\|	()
	\|	(Value . Value)

because then a Closure like (closure x x ()) would match the pattern (Value . Value). Instead, we define values by the grammar

Value	=	Number
	\|	Boolean
	\|	Closure
	\|	(null)
	\|	(cons Value Value)

This way, a list in our language looks like

(cons 1 (cons 2 (cons 3 (cons 4 (null)))))

(where each cons is a Racket symbol that appears as the first element of a three-element Racket list), rather than

(1 2 3 4)

a four-element Racket list.

In Racket, filter and map are built-in functions that ease common operations on lists. Below in Racket are versions of those functions that are curried and that work on our list values:

(define fn-filter
  (lambda (f)
    (lambda (v)
      (match v
       (`(null) `(null))
       (`(cons ,x ,y)
        (if (f x)
            `(cons ,x ,((fn-filter f) y))
            ((fn-filter f) y)))
       (else (error "not list"))))))

(define fn-map
  (lambda (f)
    (lambda (v)
      (match v
       (`(null) `(null))
       (`(cons ,x ,y)
        `(cons ,(f x) ,((fn-map f) y)))
       (else (error "not list"))))))

These functions fn-filter and fn-map can already be used from Racket, but you are going to make them usable from inside our language as well.

> ((fn-filter (lambda (x) (< 0 x)))
   '(cons -1 (cons 2 (cons -3 (cons 4 (null))))))
(cons 2 (cons 4 (null)))

> ((fn-map (lambda (x) (< 0 x)))
   '(cons -1 (cons 2 (cons -3 (cons 4 (null))))))
(cons #f (cons #t (cons #f (cons #t (null)))))

> ((fn-map (lambda (x) (* 10 x)))
   '(cons -1 (cons 2 (cons -3 (cons 4 (null))))))
(cons -10 (cons 20 (cons -30 (cons 40 (null)))))

Here is a more advanced use of fn-map that produces a multiplication table:

> ((fn-map (lambda (x) ((fn-map (lambda (y) (* x y)))
                        '(cons 1 (cons 2 (cons 3 (cons 4 (null))))))))
   '(cons 1 (cons 2 (cons 3 (cons 4 (null))))))
(cons (cons 1 (cons 2 (cons 3 (cons 4 (null)))))
(cons (cons 2 (cons 4 (cons 6 (cons 8 (null)))))
  (cons (cons 3 (cons 6 (cons 9 (cons 12 (null)))))
   (cons (cons 4 (cons 8 (cons 12 (cons 16 (null)))))
    (null)))))

This assignment has three parts. The first two parts are independent. They then come together in the third part.

Part 1: Defunctionalizing filter and map

Imagine that you are programming in a language, such as C, where functions cannot be passed to other functions as arguments. To achieve the effect of fn-filter and fn-map, let’s change (lambda (f) ...) above to receive data structures instead.

In fn-filter and in fn-map, replace (f x) by (fn-apply-closure f x). Define this very short helper fn-apply-closure.

Survey the tests above to find all the functions that can be this f. In other words, find all the functions that are fed to the (lambda (f) ...) in either fn-filter or fn-map. You should find five lambdas, including two that are the same, and one that is nested inside another. The one that is nested inside another uses a free variable x.

Replace each of these lambdas by a call to a new helper function:

(define fn-make-<0 (lambda () (lambda (x) (< 0 x))))
(define fn-make-*10 (lambda () (lambda (x) ...)))
(define fn-make-inner (lambda (x) (lambda (y) ...)))
(define fn-make-outer (lambda () (lambda (x) ... fn-make-inner ...)))

((fn-filter (fn-make-<0))
'(cons -1 (cons 2 (cons -3 (cons 4 (null))))))
> '(cons 2 (cons 4 (null)))

((fn-map (fn-make-<0))
'(cons -1 (cons 2 (cons -3 (cons 4 (null))))))
> '(cons #f (cons #t (cons #f (cons #t (null)))))

((fn-map (fn-make-*10))
'(cons -1 (cons 2 (cons -3 (cons 4 (null))))))
> '(cons -10 (cons 20 (cons -30 (cons 40 (null)))))

((fn-map (fn-make-outer))
'(cons 1 (cons 2 (cons 3 (cons 4 (null))))))
> '(cons (cons 1 (cons 2 (cons 3 (cons 4 (null)))))
    (cons (cons 2 (cons 4 (cons 6 (cons 8 (null)))))
     (cons (cons 3 (cons 6 (cons 9 (cons 12 (null)))))
      (cons (cons 4 (cons 8 (cons 12 (cons 16 (null)))))
       (null)))))

Make a copy of your code and rename fn-* to ds-* throughout the copy. Prepare for ds-apply-closure to receive data structures of various kinds by inserting match into its definition:
(define ds-apply-closure
  (lambda (f x)
    (match f
     (else (f x)))))
The same tests should pass.
Change ds-make-<0 to produce a data structure, and add a case to ds-apply-closure to enact the behavior of the lambda represented by this data structure:
(define ds-make-<0 (lambda () `(<0)))
(define ds-apply-closure
  (lambda (f x)
    (match f
     (`(<0) (< 0 x))
     (else (f x)))))
The same tests should pass.
Change ds-make-*10 to produce a data structure, and add a case to ds-apply-closure to enact the behavior of the lambda represented by this data structure:
(define ds-make-*10 (lambda () `(*10)))
(define ds-apply-closure
  (lambda (f x)
    (match f
     (`(<0) (< 0 x))
     (... ...)
     (else (f x)))))
The same tests should pass.
Change ds-make-outer to produce a data structure, and add a case to ds-apply-closure to enact the behavior of the lambda represented by this data structure:
(define ds-make-outer (lambda () `(outer)))
(define ds-apply-closure (... ds-make-inner ...))
The same tests should pass.
(For this step, it may help to rename (lambda (x) (lambda (y) ...)) to (lambda (x^) (lambda (x) ...)).)
Change ds-make-inner to produce a data structure, and add a case to ds-apply-closure to enact the behavior of the lambda represented by this data structure:
(define ds-make-inner ...)
(define ds-apply-closure
  (lambda (f x)
    (match f
     ...
     (`(inner ...) ...)
     ...
     (else (f x)))))
The same tests should pass.
Finally, delete the case (else (f x)) in ds-apply-closure. The same tests should pass. Congratulations, you have defunctionalized the program!

Part 2: Adding useful functions to the initial environment

Here’s the lambda calculus interpreter from class again. It uses a data-structure representation of environments and the functional representation of closures. The latter is why it’s called fn-value-of here.

Expr	=	Number
	\|	Boolean
	\|	Symbol
	\|	(if Expr Expr Expr)
	\|	(Expr Expr)
	\|	(λ Symbol Expr)

(define fn-value-of
  (lambda (e env)
    (match e
      (`,e #:when (number? e) e)
      (`,e #:when (boolean? e) e)
      (`,e #:when (symbol? e) (apply-env env e))
      (`(if ,e0 ,e1 ,e2)
       (if (fn-value-of e0 env)
           (fn-value-of e1 env)
           (fn-value-of e2 env)))
      (`(,rator ,rand)
       ((fn-value-of rator env)
        (fn-value-of rand env)))
      (`(λ ,formal ,body) #:when (symbol? formal)
       (lambda (argument)
         (fn-value-of body (extend-env formal argument env)))))))

Env		=		()
		\|		((Symbol Value) . Env)

(define empty-env
  (lambda ()
    '()))
(define extend-env
  (lambda (name value rest)
    `((,name ,value) . ,rest)))
(define apply-env
  (lambda (env n)
    (match env
      (`() (error "variable not bound"))
      (`((,name ,value) . ,rest)
       (if (eqv? name n) value (apply-env rest n))))))

In class, we defined this initial environment that contained useful functions for arithmetic:

(define fn-init-env
  (extend-env '+      (lambda (x) (lambda (y) (+ x y)))
  (extend-env '-      (lambda (x) (lambda (y) (- x y)))
  (extend-env 'zero?  zero?
  (empty-env)))))

> (fn-value-of '((- 311) 100) fn-init-env)
211

Without changing fn-value-of, let’s enhance our interpreter just by adding more useful functions to fn-init-env.

Add 10 entries to fn-init-env:

(define fn-init-env
  (extend-env '+      (lambda (x) (lambda (y) (+ x y)))
  (extend-env '-      (lambda (x) (lambda (y) (- x y)))
  (extend-env '*      ...
  (extend-env '<      ...
  (extend-env 'zero?  zero?
  (extend-env 'null   '(null)
  (extend-env 'null?  ...
  (extend-env 'cons   ...
  (extend-env 'cons?  ...
  (extend-env 'car    ...
  (extend-env 'cdr    ...
  (extend-env 'filter fn-filter
  (extend-env 'map    fn-map
  (empty-env)))))))))))))))

> (fn-value-of '((* 311) 100) fn-init-env)
31100
> (fn-value-of '((< 311) 100) fn-init-env)
#f
> (fn-value-of 'null fn-init-env)
(null)
> (fn-value-of '(null? null) fn-init-env)
#t
> (fn-value-of '(null? 0) fn-init-env)
#f
> (fn-value-of '((cons 4) null) fn-init-env)
(cons 4 (null))
> (fn-value-of '(cons? ((cons 4) null)) fn-init-env)
#t
> (fn-value-of '(cons? (λ x x)) fn-init-env)
#f
> (fn-value-of '(car ((cons 4) null)) fn-init-env)
4
> (fn-value-of '(car (λ x x)) fn-init-env)
not cons
> (fn-value-of '(cdr ((cons 4) null)) fn-init-env)
(null)
> (fn-value-of '(cdr (λ x x)) fn-init-env)
not cons
> (fn-value-of
    '((filter (< 0))
      ((cons 1) ((cons -2) ((cons -3) ((cons 4) null)))))
    fn-init-env)
(cons 1 (cons 4 (null)))
> (fn-value-of
    '((map (* 10))
      ((cons 1) ((cons -2) ((cons -3) ((cons 4) null)))))
    fn-init-env)
(cons 10 (cons -20 (cons -30 (cons 40 (null)))))
> (fn-value-of
    '((map (+ 10))
      ((filter (< 0))
       ((cons 1) ((cons -2) ((cons -3) ((cons 4) null))))))
    fn-init-env)
(cons 11 (cons 14 (null)))
> (fn-value-of
    '((λ digits ((map (λ x ((map (λ y ((* x) y))) digits))) digits))
      ((cons 1) ((cons 2) ((cons 3) ((cons 4) null)))))
    fn-init-env)
(cons (cons 1 (cons 2 (cons 3 (cons 4 (null)))))
(cons (cons 2 (cons 4 (cons 6 (cons 8 (null)))))
  (cons (cons 3 (cons 6 (cons 9 (cons 12 (null)))))
   (cons (cons 4 (cons 8 (cons 12 (cons 16 (null)))))
    (null)))))

Admire how the Racket functions fn-filter and fn-map are called from, and then call back to, code written in our language.

Part 3: Defunctionalizing the initial environment

Imagine that you are writing the interpreter in a language, such as C, where functions cannot be passed to other functions as arguments. To achieve the effect of all these useful functions you just put in fn-init-env, let’s change them to data structures instead.

In the `(,rator ,rand) case of fn-value-of, replace

((fn-value-of rator env)
(fn-value-of rand env))

(fn-apply-closure (fn-value-of rator env)
(fn-value-of rand env))

You have already defined this very short helper fn-apply-closure in part 1 above.

Survey your fn-value-of fn-init-env to find all the functions that can be this (fn-value-of rator env). In other words, find all the Closures. You should find twenty:

one in the λ case of fn-value-of
two in each curried function for + - * < cons map filter
one in each unary function for zero? null? cons? car cdr

Replace each of these lambdas by a call to a new helper function.

(define fn-make-closure
  (lambda (formal body env)
    (lambda (argument)
      (fn-value-of body (extend-env formal argument env)))))
(define fn-make-add (lambda () (lambda (x) (fn-make-add-inner x))))
(define fn-make-add-inner (lambda (x) (lambda (y) (+ x y))))
...
(define fn-make-zero? (lambda () (lambda (x) (zero? x))))
...
(define fn-make-map (lambda () (lambda (f) (fn-make-map-inner f))))
(define fn-make-map-inner (lambda (f) (lambda (v) ((fn-map f) v))))
(define fn-init-env
  (extend-env '+      (fn-make-add)
  (extend-env '-      (fn-make-sub)
  (extend-env '*      (fn-make-mul)
  (extend-env '<      (fn-make-lt)
  (extend-env 'zero?  (fn-make-zero?)
  (extend-env 'null   '(null)
  (extend-env 'null?  (fn-make-null?)
  (extend-env 'cons   (fn-make-cons)
  (extend-env 'cons?  (fn-make-cons?)
  (extend-env 'car    (fn-make-car)
  (extend-env 'cdr    (fn-make-cdr)
  (extend-env 'filter (fn-make-filter)
  (extend-env 'map    (fn-make-map)
  (empty-env)))))))))))))))

The same tests should pass.

Make a copy of your code (fn-value-of, fn-make-*, fn-init-env, and tests) and rename fn-* to ds-* throughout the copy. Due to this renaming, ds-value-of calls ds-apply-closure, so to make the same tests pass, reintroduce the case (else (f x)) in ds-apply-closure.

For each of the twenty ds-make-* helpers, change it to produce a data structure, and add a case to ds-apply-closure to enact the behavior of the lambda represented by this data structure. The same tests should pass after each change.

Follow this grammar of the data representation of closures:

Closure	=	(<0)
	\|	(*10)
	\|	(inner Number)
	\|	(outer)
	\|	(closure Symbol Expr Env)
	\|	(add)
	\|	(add Number)
	\|	(sub)
	\|	(sub Number)
	\|	(mul)
	\|	(mul Number)
	\|	(lt)
	\|	(lt Number)
	\|	(zero?)
	\|	(null?)
	\|	(cons)
	\|	(cons Value)
	\|	(cons?)
	\|	(car)
	\|	(cdr)
	\|	(filter)
	\|	(filter Value)
	\|	(map)
	\|	(map Value)

(The first four cases are from part 1.)

(define ds-make-closure (lambda (formal body env) `(closure ,formal ,body ,env)))
(define ds-make-add (lambda () `(add)))
(define ds-make-add-inner (lambda (x) `(add ,x)))
(define ds-apply-closure
  (lambda (f x)
    (match f
     ...
     (`(closure ,formal ,body ,env)
      (ds-value-of body (extend-env formal x env)))
     (`(add) (ds-make-add-inner x))
     ...
     (else (f x)))))

Finally, delete the case (else (f x)) in ds-apply-closure again. The same tests should pass. Congratulations, you have defunctionalized the interpreter!

Just Dessert

For a wider understanding of what we’re doing, read Danvy & Nielsen.

contents ← prev up next →

	Course Details
	Course policies
	Instructors
	Resources
	Schedule
	Assignments
	Frequently Asked Questions

1	Assignment 1: Recursion and Higher-Order Functional Abstractions
2	Assignment 2: Representation Independence
3	Assignment 3: Variables
4	Assignment 4: Interpreters
5	Assignment 5: Defunctionalization