Background

• Racket Guide on Tail Recursion
• Racket Guide on Loops
• Racket Guide on match.

Before the lab

• Read the description of A2, making notes of any unclear concepts. Most should be covered in today's lab, but if not, ask.

• Complete the Scribble Demo from the previous lab.

Discussion of "Before the Lab"

• Questions about Assignment 2
• Discussion / Questions on Scribble
• Discussion of T1

Tail Recursion

• make a directory ~/fcshome/cs2613/labs/L05 to store files from this lab.

• Background for this part is Racket Guide on Tail Recursion

• Run the following code in the debugger, and observe how deep the stack gets.

#lang racket

(module+ test
  (require rackunit))

(define (count-odds lst)
  (cond
    [(empty? lst) 0]
    [(odd? (first lst)) (add1 (count-odds (rest lst)))]
    [else (count-odds (rest lst))]))

(module+ test
  (check-equal? (count-odds (list 3 2 1 1 2 3 4 5 5 6)) 6))

• Our initial version of count-odds is not tail recursive because the result(s) of the recursive calls are processed further before returning (i.e. here passed to add1).

• Complete the following tail recursive function to count the number of odd and even numbers in a list. The general idea is that the recursive call to helper

  • reduces the size of the list argument by one, and
  • maybe increments odds This is a very common pattern in Racket, where recursion replaces mutation (i.e. replaces odds=odds+1)

(define (count-odds2 lst)
  (define (helper lst odds)
    (cond
      [(empty? lst) odds]
      [(odd? (first lst)) (helper                       )]
      [else (helper                )]))
  (helper lst 0))

(module+ test
  (check-equal? (count-odds2 (list 3 2 1 1 2 3 4 5 5 6)) 6)
  (define random-list (build-list 100 (lambda (x) (random 1 100))))
  (check-equal? (count-odds random-list) (count-odds2 random-list)))

• Use the racket debugger to test the stack usage of your function.

• save the results of this section in ~/fcshome/cs2613/labs/L05/count-odds.rkt, and commit this file.

For loops

• Although some Racket programmers like a minimalist style using pure tail recursion, many prefer to use for loops

• To accumulate values, one Racket library form is for/fold

(define (count-odds3 lst)
  (for/fold
      ([odds 0])
      ([n lst])
    (cond
      [(odd? n) (add1 odds)]
      [else odds])))

(module+ test
  (check-equal? (count-odds3 (list 3 2 1 1 2 3 4 5 5 6)) 6)
  (check-equal? (count-odds random-list) (count-odds3 random-list))
  (check-equal? (count-odds3 (list 3 2 1 1 2 3 4 5 5 6)) 6))

• Let's finish off by comparing the speed of our three implementations

(define big-list (range 50000000))
(for* ([fun (list count-odds count-odds2 count-odds3)]
       [rep '(1 2 3)])
  (printf "~a ~a\n" fun rep)
  (time  (fun big-list)))

• add the results of this section to ~/fcshome/cs2613/labs/L05/count-odds.rkt, and commit your changes.

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

• Start a new file ~fcshome/cs2613/labs/L05/match.rkt

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

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

    (module+ test
      (require rackunit)
      (check-equal? (my-map sub1 '(1 2 3)) '(0 1 2)))

list-length using match

• Use match to implement a list-length function that passes the following tests

  (module+ test
    (require rackunit)
    (check-equal? (list-length '(1 2 3)) 3)
    (check-equal? (list-length '()) 0))

• A common racket idiom is to use the ... "collector pattern" instead of cons. This is also useful in syntax-case in macros.

    (define (my-map2 f lst)
      (match lst
        ['() '()]
        [(list head tail ...) (cons (f head)
                                    (my-map2 f tail))]))

• Use match and a collector pattern to implement a list-length2 function that passes the following tests

  (module+ test
    (require rackunit)
    (check-equal? (list-length2 '(1 2 3)) 3)
    (check-equal? (list-length2 '()) 0))

Parsing with match

In this part of the lab we'll implement a somewhat silly four function calculator. Start with the following function, which understands only addition.

(define (calc expr)
  (match expr
    [(? number? n) n]
    [`(plus ,l ,r) (+ (calc l) (calc r))]
    [_ (error 'calc "syntax error")]))
    
(module+ test
  (require rackunit)
  (check-equal? (calc '(plus 1 2)) 3)
  (check-equal? (calc '(plus (plus 1 2) 3)) 6))

Referring to the discussion about quasiquote at the end of match, add times, div, and sub to the calculator. Here are 3 more tests to pass.

  (check-equal? (calc '(times (plus 1 2) 3)) 9)
  (check-equal? (calc '(div (times (plus 1 2) 3) 3)) 3)
  (check-equal? (calc '(sub (div (times (plus 1 2) 3) 3) 3)) 0)

• bonus question: how would you allow any number of arguments to your operations instead of just 2?

• push any new commits from this lab.