UNB/ CS/ David Bremner/ teaching/ cs3613/ tutorials/ CS3613 Tutorial 8

Background

This will be another review session for the midterm. To get maximum benefit, you should probably attempt the questions before the tutorial.

Substitution

{with {x {+ 4 2}}
      {with {x {+ x 1}}
            {* x x }}}

Version 1

{with* {{x1 e1[E/y]} {x2 e2[E/y]} ... {x_k e_k}[E/y]}[E/y]  newbody}
where
   newbody = body   if y in x1..xk
else
   newbody = body[E/y]

Version 2

 {with* {} E2}[v/z] =  E2[v/z]
 {with* { {x1 E1} bindings } E3}[v/z] = {with {x1 E1}
                                              {with* bindings E3}}[v/z]

Lazy evaluation

 {with {x 1}
       {with {x {+ x 1}}
         x}}

de Bruijn Indices

{with {x 1}
      {with {x {+ x 1}}
            {with {y x} x}}}
 {with {f {fun {x} {+ x 1}}}
       {with {y 2}
            {call f y}}}

Substitution Caches

(define-type BindingPair
    [pair (name : symbol) (val : s-expression)])

(define-type-alias ENV (listof BindingPair))
    
(define (lookup [name : symbol] [env : ENV]) : s-expression
    )

Here are some sample tests:

(define test-env
  (list
   (pair 'f '(lambda (x) (+ x 1)))
   (pair 'x '1)))
  
(test/exn
 (lookup 'y test-env) "free identifier")

(test
 (lookup 'x test-env) '1)

(test
 (lookup 'f test-env)
 '(lambda (x) (+ x 1)))

Dynamic and Lexical Scope

#lang plai
(require plai/dynamic)

(let ([blah (lambda (func x) (func x))])
    (let ((x 7))
        (let ((f (lambda (y) (+ x y))))
            (let ((x 6))
                (blah f 5)))))
  eval(N,env)         = N
  eval({+ E1 E2},env) = eval(E1,env) + 
                        eval(E2,env)
  ; ...
  eval(x,env)                = lookup(x,env)
  eval({with {x E1} E2},env) = eval(E2,extend(x,eval(E1,env),env))
  eval({fun {x} E},env)      = <{fun {x} E}, env>
  eval({call E1 E2},env1)  =
          if eval(E1,env1) = <{fun {x} Ef}, env2> then
                eval(Ef,extend(x,eval(E2,env1),env2))
          else 
                error!
    {with {f {fun {y} {+ x y}}}
          {with {x 7}
            {call f 1}}}
  

Functions as data structures

Fill in the definition of tree-max so that it computes the maximum number stored in a non-empty tree.

#lang plai

(define (make-tree left value right)
  (lambda (key)
      (case key
        [(getLeft) left]
        [(getValue) value]
        [(getRight) right])))

(define empty-tree 'emptyTree)
(define (empty-tree? val) (eq? val 'emptyTree))

(define (make-leaf num)
  (make-tree empty-tree num empty-tree))

(define (tree-max tree)
  (let [(l _______________)
        (r _______________)
        (v _______________)]
    (cond
        [__________________________________________      v]
        [_____________________________(max v (tree-max r))]
        [_____________________________(max v (tree-max l))]
        [else____________________________________________ ])
        
(define test-tree-1
  (make-tree (make-leaf 1) 2 (make-leaf 3)))

(test (tree-max test-tree-1) 3)

Curried Functions

One annoying feature of working with curried functions in racket is the need to explicitely call them repeatedly once per argument. Write a function call that takes a curried function and a list of arguments, and evaluates the appropriate number of calls.

#lang plai

(define plus
  (lambda (x) (lambda (y) (+ x y))))

(test ((plus 1) 2) 3)

(define plus3
  (lambda (x) (lambda (y) (lambda (z) (+ x (+ y z))))))

(test (((plus3 1) 2) 3) 6)

(define (call f l)
___________________________________________________
___________________________________________________
___________________________________________________)


(test (call plus '(1 2)) 3)

(test (call plus3 '(1 2 3)) 6)