UNB/ CS/ David Bremner/ teaching/ cs2613/ labs/ Lab 7

Combinators

Time
25 minutes
Activity
Small groups / individuals

We already learned about higher order functions, functions which take other functions as arguments. Certain higher order functions return other functions; these are sometimes called combinators, especially when the "combine" two or more functions.

• start a new file `~/fcshome/cs2613/L07/plot-example.rkt` with the following
```    #lang racket
(require plot)
(require "../L06/calculus.rkt")
```
• Suppose we want to make lots of plots comparing two functions (e.g. to see how closely they match). The core of one solution to the previous part looks like
```    (lambda (x) (- (deriv sin x) (cos x)))
```
• In order to promote code re-use, abstract out the two numerical functions of x, call them `f` and `g`. Fill in the defintion for the combinator `fsub` so that the given tests pass.
```    (define (fsub f g)
(lambda (x) (                ))

(module+ test
(require rackunit)
(define (sin2 x) (integrate cos x))
(define (cos2 x) (deriv sin x))
(define epsilon 0.001)
(define test-points (build-list 20 (lambda (x) (* 2 pi (random)))))
(for ([x test-points])
(check-= ((fsub cos cos2) x) 0 epsilon)
(check-= ((fsub sin sin2) x) 0 epsilon)))
```
• A first attempt attempt to use `fsub` for plotting reveals a flaw; namely that `deriv` is not a combinator, but rather returns a number. The forces us to add some `lambda` boilerplate.
```    (plot (function (fsub (lambda (x) (deriv sin x)) cos) -2pi 2pi))
```
• We can abstract away some more boilerplate and define a function `fderiv` which is a combinator.
```    (define (fderiv f)
(lambda (x) (deriv f x)))

(plot (function (fsub (fderiv sin) cos) -2pi 2pi))
```
• This last expression `(fsub (fderiv sin) cos)` is sometimes called point-free style.

• If we think a bit about the function `fsub`, the role of `-` is easy to abstract: it's just a function with two arguments. So we can define a function "factory" that makes combinators like `fderiv`. Fill in definition of `binop->fbinop` below.

```    (define (binop->fbinop op)
(lambda (f g)
(lambda (x)                 )))

(define fsub2 (binop->fbinop -))

(plot (function (fsub2 (fderiv sin) cos) -2pi 2pi)))

(plot (function (fadd  sin cos) -2pi 2pi))
```
• The operation that transformed `deriv` into `fderiv` is itself a combinator called curry. If you have time, check out the link for an explanation.

Macros

In the first part of the lab we discussed a method of building programs at runtime using combinators. In the rest of the lab, we'll discuss the construction of programs at compile time using what are called macros.

Some Racket forms like `and` and `or` look like function calls, but we know they are not because they support short-circuit evaluation. We can define forms that behave differently than function calls (or that look like function calls, but actually do other things as well, like the `rackunit` `check-` forms). These forms are sometimes called macros.

Redefining `and`

Time
10 minutes
Activity
Demo, Group-Discussion.
• start a new file `~/fcshome/cs2613/labs/L07/short-circuit.rkt` for the second half of the lab.

• The simplest way of defining a macro in racket is to use define-syntax-rule. As a first approximation, you can think of these syntax rules as functions that don't evaluate their arguments.

• Let's start by defining `And`, which is just like the lower case version except the short-circuit evaluation is from the right.

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

(module+ test
(require rackunit)
(define (die)
(error 'die "don't run this"))

(check-equal? (And (die) #f) #f)
(check-exn exn:fail? (lambda () (and (die) #f))))
```
• Notice the use of `lambda` to delay evaluation in `check-exn`; that's exactly the kind of boilerplate we can eliminate with a syntax rule:
```    (module+ test
(define-syntax-rule (check-fail expr)
(check-exn exn:fail? (lambda () expr)))
(check-fail (and (die) #f))
(check-fail (And #f (die))))
```
• Macros are a key part of the implimentation strategy of racket. What's an example of some syntax we saw already that is (probably) implimented as a macro?

Redefining `or`

Time
15 minutes
Activity
Individual work, small groups
• Let's define `Or` in terms of `if` in a similar way to `And`. It should pass the following tests
```    (module+ test
(check-equal? (Or #t #t) #t)
(check-equal? (Or #f #t) #t)
(check-equal? (Or #t #f) #t)
(check-equal? (Or (die) #t) #t)
(check-fail (or (die) #t)))
```

Pattern Matching

One very useful feature of racket is pattern matching. This is used in `syntax-case` to define macros, but also in more familiar function definitions using match.

Roughly speaking, you can think about `match` as fancy `cond`, where instead of specifying a test for each case, you specify a pattern to match against the data.

`map` using `match`

Time
10 min
Activity
Demo
• Start a new file `~fcshome/cs2613/labs/L07/match.rkt`

• Compare the following implementation of `my-map` with the definition in L03.

```    (define (my-map f lst)
(match lst
['() '()]
(my-map f tail))]))

(module+ test
(require rackunit)
(check-equal? (my-map sub1 '(1 2 3)) '(0 1 2)))
```
• A common racket idiom is to use the `...` "collector pattern" instead of `cons`. This is also useful in `syntax-case`, below.
```    (define (my-map2 f lst)
(match lst
['() '()]
(my-map2 f tail))]))
```

Let and Let*

Time
25 min
Activity
Individual work / small-groups

We have discussed the difference between `let` and `let*` a bit in the labs. It turns out that `let*` can be implimented in terms of `let` using a macro. In this section we'll do the

Let's start by reviewing `let*`:

```    (module+ test
(check-equal? (let* ([x 5]
[y (- x 3)])
(+ y y))
4)
(check-equal? (let* ([x 5]
[y (- x 3)]
[y x])
(* y y))
25))
```
• The key insight is that `let*` behaves like a nested set of `let`s. Let us transform the examples about according to this idea:
```    (module+ test
(check-equal? (let ([x 5])
(let ([y (- x 3)])
(+ y y)))
4)
(check-equal? (let ([x 5])
(let ([y (- x 3)])
(let ([y x])
(* y y))))
25))
```
• That's more cumbersome to write, of course, but that's why `let*` exists. So how can we formulate this recursively? Well, racket syntax already looks like a list, so lets turn this into a recursive problem on lists. Start a new file `~fcshome/cs2613/labs/L07/let-transformer.rkt`

• Complete the following skeleton for the `let-transformer` module.

```    (provide let-transformer)
(define (let-transformer lst)
(match lst
[(list 'Let* '() body)     ]
[(list 'Let* (cons (list       ) tail) body)
(list 'let  (list (list id val))
(let-transformer
(list 'Let*          )))]))

(module+ test
(require rackunit)
(check-equal? (let-transformer '(Let* ([x 5]
[y (- x 3)])
(+ y y)))
'(let ([x 5]) (let ([y (- x 3)]) (+ y y)))))
```

From list transformers to macros.

Time
10 min
Activity
Demo
• In this last part we'll show how to extend the Racket Compiler in a quite general way.

• Start a new file `~fcshome/cs2613/labs/L07/let-macros.rkt`. Roughly speaking, the following takes the input racket code `stx`, turns it into a list, processes with the function we defined already, and then turns it back into racket code.

```    (require (for-syntax racket/match))
(require (for-syntax "let-transformer.rkt"))

(define-syntax (Let* stx)
(datum->syntax #'here (let-transformer (syntax->datum stx))))
```
• We can also use `syntax-case`, which is roughly speaking `match` for macros. This eliminates the need to write a seperate transformer function. It's also harder to debug. (`Let^` is just the macro name, so as not to collide with `Let*`)
```    (define-syntax (Let^ stx)
(syntax-case stx ()
[(Let^ () body) #'body]
[(Let^ ((first-id first-val) (id val) ...) body)
#'(let ([first-id first-val])
(Let^ [(id val) ...] body))]))

(module+ test
(require rackunit)
(check-equal? (Let^ ([x 5] [y (- x 3)]) (+ y y)) 4)
(check-equal? (Let^ ([x 5] [y (- x 3)] [y x]) (* y y)) 25))
```

Before you Leave

Commit and push the `.rkt` files you wrote today.