Overview

The final exam, worth 50% of your mark, is tentatively scheduled for 2PM on April 19.

The exam is cumulative, covering all of the lectures, assignments, and tutorials.

• See tutorial5 and tutorial8 for practice questions for the two midterms. Solutions are available on the handin server.

More sample Questions

Types

Fill in a valid plai-typed type for each of the following functions.

#lang plai-typed
(define (f) 8)
(has-type f :              )
(define h  (lambda (x y) 
         (string-length (string-append x y))))
   
(has-type h :                   )

Higher order functions

Consider the tests

(test ((pair 1 3) +) 4)
(test ((pair 1 3) -) -2)
(test ((pair 2 3) *) 6)

1. Give a valid type for pair

2. Write the function pair to pass these tests.

More types

Give a valid type declaration for the following function

(define (glonk f g)
  (lambda (x)
    (let* ((h (g x))
           (i (f h)))
      i)))

Data structures with functions

Fill in the definitions of empty-map and extend such that the given tests pass.

#lang plai-typed

(define-type-alias Map  (string -> number))

(define (empty-map) : Map

                             )

(test/exn ((empty-map) "bob")  "empty map!")

(define (extend key val the-map) : Map


                                )
  
(define test-map
  (extend "mary" 1
      (extend "bob" 2
          (empty-map))))

(test (test-map "bob")  2)
(test (test-map "mary") 1)
(test/exn (test-map "happiness") "empty map!")

Recursion

• (1) Use let and lambda to define a recursive list length function that takes itself as a parameter, so that the following test passes.

#lang plai
(test 
 (let (
; ...
)
   (len len  '(a b c d e)))  5)

• (2) Write the curried version of len, (still using let and lambda) that makes the following test pass.

#lang plai
(test 
 (let 
;...
   ((len len)  '(a b c d e))) 5)

• (3) fill in the definition of make-len to make the following test pass.

#lang plai
(test
 (let 
     ((make-len 
     ; stuff
             (if (null? list)
                 0
                 (+ 1 (len (rest list)))))))))
   (let ([len (make-len make-len)])
     (len '(a b c d e)))) 5)

Evaluation Delay

• (1) What is the output of running this racket code?

#lang plai

(define (make-test self)
  (let ([test (self self)])
    (lambda (arg)
      (if arg
          arg
          (test (not arg))))))
(display "after define make-test\n")

(define test (make-test make-test))

(display "after define test\n")

(display (test #f))

• (2) Modify the let statement in the above code so that it runs to completion.

Y combinator

• (1) What is the output from the following code? Explain your answer.

#lang plai
((lambda (x) (x x)) (lambda (x) 
                      (begin 
                        (display "hi!\n")
                        (x x))))

• (2) Given the following definitions, trace the evalutation of (test #f) I recommend using the debugger, then writing down your trace.

#lang plai

(define (make-recursive f)
  ((lambda (x) (f (lambda (n) ((x x) n)))) 
   (lambda (x) (f (lambda (n) ((x x) n)))))) 

(define test 
  (make-recursive
   (lambda (test)
     (lambda (arg)
       (if arg
           arg
           (test (not arg)))))))

syntax rules

• Give a syntax rule for a short circuiting nor (negated or).

(test (nor #f) #t)
(test (nor #t (/ 1 0)) #f)
(test (nor #f #t (eq? (/ 1 0) 0)) #f)

Union types

• Give the type for the following function in typed/racket

(define (fun arg)
    (if arg
        (lambda (x) 'foo)
        "bar"))

Typechecking

Given the following definitions for a join construct (and assuming the test passes)

1. Given an appropriate typing rule.
2. Typecheck the expression in the test using your rule, and any others needed.
3. Give Racket code to define the join case of a typechecking function typecheck To test your answer, you can start with trcfae-t.rkt.

(define-type FAE
  ⋮
  [join (fun-1 : FAE) (fun-2 : FAE)])

(define (interp a-fae env)
  (type-case FAE a-fae
  ⋮
    [join (fun-1 fun-2)
          (closureV 'x
                     (call fun-2
                          (call fun-1 (id 'x))) env)]))

(test (interp (call
               (join (fun 'x (add (id 'x) (id 'x)))
                     (fun 'y (sub (id 'y) (num 1))))
               (num 3))
              (mtSub))
    (numV 5))

(test (typecheck
        (join (fun 'x (numTE) (add (id 'x) (id 'x)))
              (fun 'y (numTE) (sub (id 'y) (num 1))))
       (mtEnv))
      (arrowT (numT) (numT)))

Boxes and mutation

• What is the result of the following two code snippets. Explain the difference.
• Will this code typecheck in plai-typed? Why or why not?
• Will this code typecheck in typed/racket? Why or why not?

(define foo (list 1 3))
(define bar (second foo))
(set! bar 2)
foo

(define foo2 (list 1 (box 3)))
(define bar2 (second foo2))
(set-box! bar2 2)
foo2

Ragg Grammars

• Write a ragg format grammar that parses the following emoticons, assuming the lexer returns each character as a string token and ignores whitespace.

O_O o-o O_o o_O o_o O-O :-) :) :o) :] :c

• Explain the difference between the following two ragg grammars.

;; Grammar 1
ae: NUMBER
    | NUMBER "+" ae
    | NUMBER "-" ae

;; Grammar 2
ae: NUMBER 
    | ae "+" ae
    | ae "-" ae

Substitution rules

• Complete the following substitution rules for eager substitution

{call f arg}[y/x] =

{fun {id} body}[y/x] =

• repeat the exercise for lazy substitution

Environments

Fill in the type environments in the following output from the typechecker in trcfae-t.rkt. You can use whatever environment notation you find convenient.

>(typecheck
  (rec 'fub (arrowTE (numTE) (numTE))
   (fun 'x  (numTE)
    (if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1)))))
   (call (id 'fub) (num 1)))
  (mtEnv))
> (typecheck
   (fun 'x (numTE)
    (if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1)))))
    ___________________________________________________________)
> >(typecheck
    (if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1))))
    ___________________________________________________________)
> > (typecheck (id 'x)
    ___________________________________________________________)
< < (numT)
> > (typecheck (num 1)
    ____________________________________________________________)
< < (numT)
> > (typecheck
     (call (id 'fub) (sub (id 'x) (num 1)))
     __________________________________________________________)
> > >(typecheck
      (id 'fub)
      __________________________________________________________)
< < <(arrowT (numT) (numT))
> > >(typecheck
      (sub (id 'x) (num 1))
      __________________________________________________________)
> > > (typecheck
       (id 'x)
      __________________________________________________________)
< < < (numT)
> > > (typecheck
       (num 1)
       _________________________________________________________)
< < < (numT)
< < <(numT)
< < (numT)
< <(numT)
< (arrowT (numT) (numT))
>(typecheck (call (id 'fub) (num 1))
  _______________________________________________________________)
> (typecheck (id 'fub)
  _______________________________________________________________)
< (arrowT (numT) (numT))
> (typecheck (num 1)
  _______________________________________________________________)
< (numT)
<(numT)
(numT)

• Fill in the value environments in the following output from the the interpreter in trcfae-t.rkt. You can use whatever environment notation you find convenient, but note that in this case the environments have to be recursive

>(interp
  (rec 'fub (arrowTE (numTE) (numTE))
   (fun 'x (numTE)
    (if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1)))))
   (call (id 'fub) (num 1)))
  (mtSub))
> (interp
   (fun 'x (numTE)
    (if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1)))))
    ______________________________________________________________
    ______________________________________________________________)

< (closureV
   'x
   (if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1))))
   (aRecSub 'fub (box (numV 42)) (mtSub)))
>(interp
  (call (id 'fub) (num 1))
    ______________________________________________________________
    ______________________________________________________________)
> (interp
   (id 'fub)
    ______________________________________________________________
    ______________________________________________________________)
< #0=(closureV
      'x
      (if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1))))
      (aRecSub 'fub '#&#0# (mtSub)))
> (interp
   (num 1)
    ______________________________________________________________
    ______________________________________________________________)
   
< (numV 1)
>(interp
  (if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1))))
    ______________________________________________________________
    ______________________________________________________________)
> (interp
   (id 'x)
    ______________________________________________________________
    ______________________________________________________________)
< (numV 1)
>(interp
  (call (id 'fub) (sub (id 'x) (num 1)))
    ______________________________________________________________
    ______________________________________________________________)
> (interp
   (id 'fub)
    ______________________________________________________________
    ______________________________________________________________)
< #0=(closureV
      'x
      (if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1))))
      (aRecSub 'fub '#&#0# (mtSub)))
> (interp
   (sub (id 'x) (num 1))
    ______________________________________________________________
    ______________________________________________________________)
> >(interp
    (id 'x)
    ______________________________________________________________
    ______________________________________________________________)
< <(numV 1)
> >(interp
    (num 1)
    ______________________________________________________________
    ______________________________________________________________)

< <(numV 1)
< (numV 0)
>(interp
  #0=(if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1))))
  (aSub 'x (numV 0) #1=(aRecSub 'fub (box (closureV 'x #0# #1#)) (mtSub))))
> (interp
   (id 'x)
  ______________________________________________________________
  ______________________________________________________________)
< (numV 0)
>(interp
  (num 1)
  ______________________________________________________________
  ______________________________________________________________)
<(numV 1)
(numV 1)

Objects

Fill in the definitions of square, circle, and triangle to define a simple object hierarchy, where area is implimented in each subclass, and round? is overridden (i.e. everything should inherit from shape%.

#lang plai

(define pi 3.141592653589793)

(define (shape% method)
  (case method
    [(round?) #f]
    [else (error method "unknown method")]))

(define (square side)
  (lambda (method)
    (case method

    )))
(define (circle radius)
  (lambda (method)
    (case method

  )))
(define (triangle height width)
  (lambda (method)
    (case method


    )))

(define a-square (square 1))
(define a-circle (circle 1))
(define a-triangle (triangle 1 2))
(test (a-square 'area) 1)
(test (a-circle 'area) pi)
(test (a-triangle 'area) 1)
(test (a-square 'round?) #f)
(test (a-circle 'round?) #t)
(test (a-triangle 'round?) #f)

Background

We have mainly been using the racket dialect plai-typed this term. This dialect uses a typed system modelled on that of ML. This has some advantages, including allowing quite good type inference. Unfortunately it is unable to type several constructs that are fairly natural in dynamically typed languages. One interesting and practical idea in programming languagues is so called Gradual typing. In a gradually typed language some expressions have static types checked at compiled time while others are checked at run time. In this tutorial we will explore the idea of union types used by the gradually typed language typed/racket.

Type inference versus gradual typing

One subtlety to understand right away is that lack of type annotations is much different from gradual typing.

Conside the following function.

#lang plai-typed

(define (fun arg)
    (if arg
        'foo
        'bar))

• Type fun in the REPL to see what the infered type of this function is.

• To convince yourself that this checking happens at compile time, add the following

(define (bar)
  (fun "hello"))

Notice that the "bad" code is never run, but we still get a typecheck error.

• Try changing the #lang to plai. Not only does it typecheck, but you can run the function (bar). Why is this?

• Try changing the #lang to plai. Not only does it typecheck, but you can run the function (bar). Why is this?

• Try changing the #lang to typed/racket. What is the inferred type of fun?

  • To help understand this, note that typed/racket reports function type A B -> C as (-> A B C). This is no loss of information because the arrow is always in the same place in our usual form.

  • the (U … ) form defines a union type, which here looks a bit like dodging the question, by listing all possible return values.

  • the Any marks a dynamically typed identifier

• Write a type annotation for the function fun by copying the inferred type.

• Modify your type annotation to look more like the familar (A -> B) form

• Modify your type annotation to avoid the use union types. Note that your new type will be less precise than before, but possibly more meaningful for humans. You may want to drop or modify the function bar so you can get rid of the Any.

• Modify the actual function definition to

(define (fun arg)
    (if arg
        'foo
        "bar"))

- comment out the type annotation
- verify this no longer typechecks in `plai-typed` (comment out the type annotation)
- verify that it _does_ typecheck in `typed/racket`, and put back
  a "human friendly" type annotation.

Typing "Lambda Lists"

Let's look back at our example from implimenting data structures with functions.

#lang plai
(define (kons x y)
  (lambda (s)
    (s x y)))
(define (furst x) (x (lambda (x y) x)))
(define (rust x) (x (lambda (x y) y)))
(define a (kons 1 'alpha))
(define b (kons 'beta 4))
;
(test (furst a) 1)
(test (rust b) 4)
(test (rust a) 'alpha)

It turns out that the test form is not available in typed/racket, but similar functionality is available from rackunit.

Let's convert our example to rackunit

#lang plai
(define (kons x y)
  (lambda (s)
    (s x y)))
(define (furst x) (x (lambda (x y) x)))
(define (rust x) (x (lambda (x y) y)))

(module+ test
  (require rackunit)
  (define a (kons 1 'alpha))
  (define b (kons 'beta 4))
  (check-equal? (furst a) 1 "furst")
  (check-equal? (rust b) 4 "rust")
  (check-equal? (rust a) 'alpha))

• Try switching to #lang typed/racket. Unlike our previous example, this one doesn't typecheck without annotations.

  • The main point of the remaining error messages seems to be that typed/racket can't seem to infer when things are functions. Although plai-typed can't typecheck some things, it is actually better at inferring what is a function.

• Comment out everything but the definition of kons, and try to find an annotation for parameter s that lets typed/racket typecheck it. Be as vague as you can get away with.

• Define a type alias using (define-type-alias BinOp (Any Any -> Any))

• Use this type alias to give a type-annotation (using (: … )) for kons. Can you get rid of your previous type annotation on s? Why or why not?
• Define a second type alias Pear for the return type of kons, and use this in your type annotation. Also use Pear to annotate furst and rust, as follows:

(define (furst [x : Pear]) (x (lambda (x y) x)))
(define (rust [x : Pear]) (x (lambda (x y) y)))

• At this point, you should be able to change (require rackunit) to (require rackunit/typed) and have all tests pass.

• You might think we're not using union types at all, except that Any is really the biggest union type of all. Define a third type alias Thing and replace the use of Any with Thing. Make your definition of Thing general enough, but not too general.

Background

We have talked a bit about how to impliment objects using lambda, and we're going to talk more about about it the next few weeks. In this tutorial we're going to have a look at the Racket object system and in particular how it's used in the Racket gui library.

We will use the dialect racket/gui in our examples today, so start your file with

#lang racket/gui

Creating objects

Like many languages, objects are created using new. In Racket, this looks just like a function

#lang racket/gui
(define frame (new frame% [label "I've been Framed"]))

There's a lot going on in that one line, but not much to look at when we run it. In Java and Python it's easy to forget the original metaphor of sending messages to objects, but Racket in it is explicit with

(send <object> message <arg1> <arg2> ...)

Your turn

Steal the appropriate send form from the first example in the gui manual to get a window popping up.

Analysis

Now that we know that does something, let's look at it a bit from a language perspective. For each of the following, try to classify it as a value (like lambda), or syntax (like if).

• new
• frame%
• send

Even syntax (sometimes called special forms) mostly defines expressions.

• What's one glaring exception?
• What do new and send evaluate to as expressions? The return value send is kindof a trick question.

The event loop

It turns out we just wrote a concurrent program: multiple things are happening at the same time. We get a hint that this is the case because we are returned to the REPL with our window still showing.

In the lower REPL window of DrRacket (or Emacs), type

(send frame show #f)

Notice the window goes away. The concurrency here is managed internally by an event loop. In order to really understand the difference with sequentially executing a sequence of functions or method calls, let's handle some user generated events.

Add the following code to your example

(define msg (new message% [parent frame] [label ""]))
(new button% [parent frame]
             [label "Panic"]
             [callback
              (lambda (button event)
                (send msg set-label "Don't Panic"))])
              

Analysis

We've been using, but ignoring, something Racket calls initialization arguments e.g. label and parent. These are conceptually very similar to constructor arguments in object oriented languages. Unlike Java they use a named argument syntax rather than a positional one (Python also has optional named arguments).

The most important initialization argument here is callback. This gives a function to run when the button is pressed. It's clear now that the control flow is not totally under the control of our code: like most gui frameworks, the runtime waits for an event and then hands us back control temporarily.

Some more things to notice from a programming language perspective

• We're actually discarding the return value of (new button% ...)
• What happens if we switch the order of (define msg ...) and (new button% ...). This seemingly relies on using msg before it is defined. What do conclude (or remember) about the top level in a racket module (cf. our long discussion about recursion).

Your turn

• combine what we saw so far to make the button kill the window.

Drawing

Let's add a drawing area to our UI, so we can print more reassuring text

Here's some sample code to set up a canvas and print some text in it.

(define canvas (new canvas% [parent frame]))
(define (panic)
  (let ([dc (send canvas get-dc)])
    (send dc set-scale 5 5)
    (send dc set-text-foreground "blue")
    (send dc draw-text "Don't Panic!" 0 0)
    (send dc set-scale 1 1)))

Nothing happens until you call the function (panic) from the REPL.

Your turn

• Make the callback for the button draw the big blue text.
• If you have time, add some state so that each press of the button draws the text in a different place

Subclassing

A common way to reuse a class is to subclass it. In Racket this is done by using the class form.

Let's start with the following modification, which should not break anything.

(define my-canvas%
  (class canvas%
    (super-new)))
(define canvas (new my-canvas% [parent frame]))

Things to observe:

• We've define a new class, inheriting from canvas%
• We've explicitly called '(super-new)' to do the superclass initialization. This allows control over how initialization arguments are processed, i.e. before or after the superclass is initialized.
• Perhaps most interestingly from a programming language point of view, classes are values in the language, and we can bind them to identifiers just like numbers and functions.

In order to overide a method in a subclass, we use define/override like follows

(define my-canvas%
  (class canvas%
    (super-new)
    (define/override (on-event event)
      (when (send event button-down? 'any)
        (panic)))))

Your turn

Modify the definition of my class so that button clicks cause diameter 10 circles to be drawn at the appropriate place. You can either use this to send messages to the current object, or use the inherit to make the methods you need available as regular functions.

The second midterm, worth 15% of your mark, will be held in class on March. 14, 2017.

Sample Questions will be reviewed in the tutorial on March 13.

Background

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

Substitution

• Evaluate the following by substitution.

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

• Identify the problem with this definition of substitution semantics:

  To substitute an identifier i in an expression e with an expression v, replace all instances of i that are not themselves binding instances, and that are not in any nested scope, with the expression v.

• Consider the following two different substititution rules for with*

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]

• Evaluate the following substitution under both versions.

  {with* {{y x} {x 2} {x x}} {+ x y}}[1/x]
  

• Explain the differing results in terms of scope.

Lazy evaluation

• Evaluate the following using purely lazy substitution and purely eager substitution

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

• Give an example of WAE code exhibiting name capture

de Bruijn Indices

• Convert the following WAE expression to deBruijn form.

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

• Convert the following FLANG expression to deBruijn form.

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

Substitution Caches

• Write a lookup function with this type signature to look up a symbol in a substitution cache / environment.

(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)))

• Explain why environments use a list or list-like structure, rather than something with a faster search time like a hash table.

Dynamic and Lexical Scope

• Explain why the following evaluation rule guarantees the corresponding interpreter will not have lexical scope.

  eval ({fun { x } E} , sc ) = {fun { x } E}

• Evaluate the following dynamically scoped racket code using environments.

#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)))))

• Evaluate the same code using substitution semantics (this will get a different answer, matching racket without the the (require plai/dynamic). Note that this is worth doing in racket by copying and modifying the expression for each substitution.

• Modify the following evaluation rules so that they make sense for the limited dialect of racket used in the preceding example.

  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!

• Evaluate the previous example using your new environment based evaluation rules.

• Compare the behaviour of the following code under dynamic scope, substitution, and environment based evaluation. This question does not need a complete trace to answer.

    {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)

Background

We have seen several cases where the syntax supported by an interpreter can be modified by using some kind of preprocessor (e.g. converting with* into nested with. This tutorial is on macros, which are a way for the programmer to change the syntax of a language without changing the language interpreter / compiler.

All of the following should be in #lang plai-typed. You can use one source file for the whole tutorial; otherwise you may need to duplicate some definitions which are re-used.

Part 1. Adding FLANG syntax to racket

The first new tool is define-syntax-rule

The key idea here is a pattern. In the example below, the (with (id val) body) s-expression acts something like a type variant in type-case. The with is treated literally, and the other identifiers are bound to whatever s-expression is in that position. This is a bit analogous to a regular define, except notice the extra parens in the with syntax are no problem here.

#lang plai-typed
(define-syntax-rule (with (id val) body)
  (let [(id val)]
    body))

The body of the define-syntax-rule the racket code to replace the with form. Here is one test; add a couple more to convince yourself it is working.

(test (with (x 1) (+ x x)) 2)

Notice there is no quoting of the with in this test; it is now a Racket expression just like let.

Use define-syntax-rule to define syntax for fun and call so that the following tests (borrowed from the lectures) pass

  (test {with {add3 {fun {x} {+ x 3}}}
              {with {add1 {fun {x} {+ x 1}}}
                    {with {x 3}
                          {call add1 {call add3 x}}}}}
        7)

  (test {call {call {fun {x} {call x 1}}
                    {fun {x} {fun {y} {+ x y}}}}
              123}
        124))

Part 2. Short circuit

Some Racket forms like and and or look like function calls, but we know they are not because they support short-circuit evaluation. In this part we use define-syntax-rule to define And and Or, which are just like the lower case version except the short-circuit evaluation is from the right.

(define-syntax-rule (And a b)
  (if b a #f))

(define (die)
  (error 'die "don't run this"))

(test (And (die) #f) #f)
(test/exn (and (die) #f) "don't run this")

Define Or in a similar way to And.

(test (Or (die) #t) #t)
(test/exn (or (die) #t) "don't run this")

Part 3, multiple cases.

The syntax-rules form can be used test a sequence of patterns against a form starting with one identifier. The following code almost works to satisfy the tests. Thinking about cond, what small change do you need to make?

(define-syntax arghh
  (syntax-rules ()
    [(arghh) 0]
    [(arghh a) 1]
    [(arghh (a)) 2]))

(test (arghh) 0)
(test (arghh thptt) 1)
(test (arghh (die)) 2)

Part 4, with*, again.

Recall with* construct from Assignment 4. One of the ways to solve this was to convert with* into a nested set of with forms. It turns out this is fairly easy to do with syntax rules and recursion. A key ingredient is the ability to match sequences with syntax patterns.

Fill out the following syntax-rules in order to expand the with* into a with containing a with* (or if you prefer to skip a macro level, into a let containing a with*.

Note that ... is really valid racket syntax here, and you can place it in your expansion to mean "copy the matched sequence". Roughly speaking, (id val) ... matches a sequence of (id1 val1) (id2 val2) (id3 val3)

(define-syntax with*
  (syntax-rules ()
    [(with* () body) body]
    [(with* ((first-id first-val) (id val) ...) body)
        ]

(test {with* {{x 5} {y {- x 3}}} {+ y y}} 4)
(test {with* {{x 5} {y {- x 3}} {y x}} {* y y}} 25)

Getting started

Open a new file in DrRacket and add the following definitions to the beginning. This makes available some definitions from racket in plai-typed.

#lang plai-typed

(module tutorial6 typed/racket/base
  (require racket/math)
  (require (prefix-in plot: plot))

  (provide plot sin cos pi)

  (define (plot [fn : (Real -> Real) ] [from : Real] [to : Real])
    (plot:plot
     (plot:function fn from to)))
)


(require (typed-in 'tutorial6
                   [plot : ((number -> number) number number -> void)]
                   [pi : number]
                   [sin : (number -> number)]
                   [cos : (number -> number)]))

For the rest of the tutorial, add various definitions discussed to your file. Make a note of the types of the functions discussed.

Derivatives and integrals

We can (crudely) approximate a derivative with the following higher order function.

(define dx 0.001)

;; compute the derivative of `f` at the given point `x`
(define (deriv f x)
  (/ (- (f (+ x dx)) (f x)) dx))

Similarly, we can approximate the integral of a function at a point (more precisely from 0 to the point):

;; compute an integral of `f' at the given point `x'
(define (integrate f x)
  (local
      [(define (loop y acc)
         (if (> y x)
             (* acc dx)
             (loop (+ y dx) (+ acc (f y)))))]
    (loop 0 0)))

And say that we want to try out various functions given some `plot' function that draws graphs of numeric functions, for example:

    (define -2pi (* -2 pi))
    (define 2pi (* 2 pi))
    (plot sin -2pi 2pi)

The problem is that plot expects a single (number -> number) function -- if we want to try it with a derivative, we can do this:

;; the derivative of sin

(define sin-deriv (lambda (x) (deriv sin x)))
(plot sin-deriv -2pi 2pi)

But this will get very tedious very fast -- it is much simpler to use an anonymous function:

(plot (lambda (x) (deriv sin x)) -2pi 2pi)

we can even verify that our derivative is correct by comparing a known function to its derivative. Fill in the blank in the following with the derivative of sin

(plot (lambda (x) (- (deriv sin x)         )) -2pi 2pi)

But it's still not completely natural to do these things -- you need to explicitly combine functions, which is not too convenient. What can you observe about the numerical error here?

Combinators

Instead of explicitely combining , we can write H.O. functions that will work with functional inputs and outputs. Such functions are called 'combinators. For example, we can write a function to subtract functions:

 (define (fsub f g)
    (lambda (x) (- (f x) (g x))))

Notice that the inferred type for fsub is a bit too general. Add type annotations to fix this.

We can similarly mamke a combinator to compute (indefinite) integrals.

 (define (fderiv f)
    (lambda (x) (deriv f x)))

Now we can try the same error calculation in a much easier way:

 (plot (fsub (fderiv sin) cos) -2pi 2pi)

More than that -- our fderiv could be created from deriv automatically:

  ;; convert a double-argument function to a curried one
  (define (currify f)
    (lambda (x) (lambda (y) (f x y))))

  ;; compute the derivative function of `f'
  (define fderiv2 (currify deriv))

Same principle with fsub: we can write a function that converts a binary arithmetical function into a function that operates on unary numeric function. But to make things more readable we can define new types for unary and binary numeric functions:

;; turns an arithmetic binary operator to a function operator
(define (binop->fbinop op)
  (lambda (f g)
    (lambda (x) (op (f x) (g x)))))

Use binop->fbinop to define a new version of fsub (e.g. calling it fsub2).

As a final exercise, define a combinator called "fintegrate" to make the following plot call work:

;; want to verify that `integrate' is the opposite of `deriv':
;;   take a function, subtract it from its derivative's integral

(plot (fsub sin (fintegrate (fderiv2 sin))) 0 2pi)

This is one line if you use currify.

The first midterm, worth 15% of your mark, will be held in class on Feb. 7, 2017.

Details about topics will be added to this page closer to the date of the test.

As practice for the midterm, try to do the following exercises on paper first, then check your answers.

Racket 101

For each of the following expressions, decide what the resulting value (or error) is in plai-typed

(if "true" 0 1)

(first (rest  (list 1 2)))

(cond
 [(> 3 1) 0]
 [(< 3 1)  1])

(and #f (= 0 (/ 1 0)))

(cons 3 (list 1 2))

(let ([ x -1])
  (let ([ x 10]
    [ y (+ x 1) ])
    (+ x y)))

(define (f n)
  (if (<= n 1)
      1
      (f (- n 1))))
(f 100)

(define (g l)
  (lambda (h)
    (cons h l)))

(g 100)
(g (list 1 2 3))
((g (list 1 2 3)) 100)

Higher order functions

Find the type of the functions a, b, and c

(define (a f n)
  (f n))

(define (b f n)
  (lambda (m)
     (f n m)))

(define (c f g h)
  (lambda (x y)
    (f (g x) (h y))))

Tail recursion

• Write a tail recursive function to multiply two non-negative integers. Your function should use + but not *.

• Write a tail recursive function to sum the elements of a list.

Grammars

Write a ragg format grammar that (given a suitable lexer) passes the following tests.

(test
 (string->sexpr "wow. such language. very tricky. wow.") 
 '(doge "wow" "." "such" (subject "language") "." "very" (adjective "tricky") "." "wow" "."))

(test
 (string->sexpr "wow. such course. very tricky. wow.") 
 '(doge "wow" "." "such" (subject "course") "." "very" (adjective "tricky") "." "wow" "."))

(test
 (string->sexpr "wow. such course. very difficult. wow.") 
 '(doge "wow" "." "such" (subject "course") "." "very" (adjective "difficult") "." "wow" "."))

(test
 (string->sexpr "wow. such prof. very mean. wow.") 
 '(doge "wow" "." "such" (subject "prof") "." "very" (adjective "mean") "." "wow" "."))

To test your answer you can use doge-lexer.rkt and doge-driver.rkt

Substitution

Consider an extended with syntax such that each with can have multiple bindings, but the named-expression refers to the outer scope, not the the previous bindings. In particular the following evaluates to 3, not 4. This is the same semantics as racket's let, so you can try more examples by replacing "with" with "let" in the code.

{with {{x 1}}
    {with {{x 2} {y x}} {+ x y}}}

Give English/pseudocode rules to perform the following substitution

{with { {x1 e1} ... {x_l e_k} } body}[E/y]=
  subst({with { {x1 e1} ... {x_l e_k} } body},E,y) =

Introduction

In this assignment you will use the ragg parser toolkit to parse transcripts of encounters with dogs. These are represented as strings containing "wag", "growl", "bark", "slobber", and "bite", separated by whitespace. Each encounter is ended with a ’.’; an example input follows:

slobber slobber.
wag wag slobber. growl bark.
growl bark bite.

You should have help on ragg in drracket, under "Help -> Racket Documentation -> Miscellaneous Libraries".

Structure of solutions.

Unlike in your assignments, you will need to use multiple files for this tutorial. You can download the lexer

Write your parser in a second file starting with #lang ragg, and use the two of them from a third driver file like the following. Note that we're using plai, not plai-typed. Also notice you need to use some custom error handling code, rather than test/exn.

#lang plai

(require "grammar-1.rkt")
(require "lexer.rkt")

(define (string->sexpr str)
  (syntax->datum (parse (tokenize-string str))))

(define (catch-parse-error str)
  (with-handlers ([exn:fail? (lambda (v) 'fail)])
    (string->sexpr str)))

(test  
 (string->sexpr "bark bark.")
 '(dog (sentence (angry (before-bite "bark" "bark")) ".")))

(test (catch-parse-error "bite.") 'fail)

1. Happy Dog, Angry Dog

In this question you should construct BNF grammar that enforces the following rules:

1. Every dog encountered is either happy or angry.
2. A happy dog always slobbers at least once.
3. A happy dog may wag several times before slobbering, but once it starts slobbering, it stops wagging.
4. An angry dog may growl several times before barking, but once it starts barking, it stops growling.
5. An angry dog does not necessarily bite, but it always growls or barks before biting.

The examples in the introduction are all valid for these rules. Here some examples of invalid encounters.

bite.
bark wag.
growl bark growl.

Here is the beginning of a solution

dog: sentence +

sentence: happy "." | angry "."

Add tests to your driver to test each of the 5 rules given above.

2. To every Slobber a Wag

As an extra challenge, modify your first grammar to enforce the additional rule that the number of wags and slobbers of any happy dog is exactly equal. For this question "wag wag slobber slobber." is valid, but "wag slobber slobber." and "wag wag slobber." are not.

Types

Use pencil and paper to work out the type of the following function. Check your answer using DrRacket.

#lang plai-typed
(define (f a b c)
  (a (b c)))

Tail recursion

Complete the following tail recursive function to count the number of odd and even numbers in a list. You may use the built in functions odd? and even?. Use the racket debugger to test the stack usage of your function.

(define  (helper lst odds evens)
  (cond
    [(empty? lst) (list odds evens)]
        ;; missing two cases
    ))
(define (odds-evens lst)
    (helper lst 0 0))
    
(test (odds-evens (list 3 2 1 1 2 3 4 5 5 6)) (list 6 4))

Part 1

For each of the following code samples, add sufficient test forms to get full coverage

Sample 1

#lang plai-typed
(define (digit-num n)
  (cond [(<= n 9)    (some 1)]
        [(<= n 99)   (some 2)]
        [(<= n 999)  (some 3)]
        [(<= n 9999) (some 4)]
        [else        (none)]))

Sample 2

#lang plai-typed
(define (helper n acc)
  (if (zero? n)
    acc
    (helper (- n 1) (* acc n))))

(define (fact n)
  (helper n 1))

Sample 3

For the parser example, you'll need to peruse the documentation on expressions to figure out how to test for errors. You may also find the S-expression documentation helpful in constructing test input.

#lang plai-typed
(define-type AE
  [Num (n : number)]
  [Add (l : AE) (r : AE)]
  [Sub (l : AE) (r : AE)])
(define (parse [s : s-expression])
  (cond
     [(s-exp-number? s) (Num (s-exp->number s))]
     [(s-exp-list? s)
      (let* ([sl (s-exp->list s)]
             [op (s-exp->symbol (first sl))]
             [left (second sl)]
             [right (third sl)])
        (case op
          [(+) (Add (parse left) (parse right))]
          [(-) (Sub (parse left) (parse right))]))]
     [else (error 'parse-sexpr "bad syntax")]))

Part 2

Sample 3 has several bugs, namely syntax errors that crash the parser, rather than generate error messages about the input. Correct at least one of these bugs, and add a suitable test.

Part 1

Follow the instructions at racket-setup to get racket set up for this course. If the system version of drracket is not available (e.g. in the menus) yet, then you can start drracket by opening a terminal and running

  % ~bremner/bin/drracket

Part 2

Do the Quick racket tutorial. Although you can just copy and paste the text into DrRacket, you will get more benefit from typing things in and more importantly from changing things and observing the results.