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

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

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