Homework 9

Due Date Sat 11/6 at 9:00pm (Week 9)

Purpose To think more about signatures and design functions over graphs.

Finger Exercises

Exercise 1 From HTDP, 471 472

Graded Exercises

Types and Obligations

In lecture, we defined a Type data definition and a enforce function that we used to enforce what was specified in our signatures. The code we wrote in class is the following:

(define-struct pair [fst snd])

; a [Pair-of A B] is a (make-pair A B)

; A Type is one of:

; - 'number

; - 'boolean

; - 'string

(define-struct pair-ty [fst snd])

; - (make-pair-ty Type Type)

(define-struct fun-ty [arg ret])

; - (make-fun-ty Type Type)

; Interpretation: a Type represents different types of data we use in our programs.

; In particular, these are some of the types we write in our signatures.

(define (type-temp type)

(cond [(equal? type 'number) ...]

[(equal? type 'boolean) ...]

[(equal? type 'string) ...]

[(pair-ty? type) (... (type-temp (pair-ty-fst type)) ...

(type-temp (pair-ty-snd type)) ...)]

[(fun-ty? type) (... (type-temp (fun-ty-arg type)) ...

(type-temp (fun-ty-ret type)) ...)]))

(define Number 'number)

(define Boolean 'boolean)

(define String 'string)

(define (Pair-of A B) (make-pair-ty A B))

(define (Function X Y) (make-fun-ty X Y))

; enforce : Type X -> X

; ensures the argument x behaves like the type,

; erroring otherwise (either immediately or when used)

(define (enforce type x)

(local ((define (err _) (error "the type didn't match: "

x " : " type)))

(cond [(equal? type 'number) (if (number? x) x (err 1))]

[(equal? type 'boolean) (if (boolean? x) x (err 1))]

[(equal? type 'string) (if (string? x) x (err 1))]

[(pair-ty? type) (if (pair? x)

(make-pair

(enforce (pair-ty-fst type) (pair-fst x))

(enforce (pair-ty-snd type) (pair-snd x)))

(err 1))]

[(fun-ty? type)

(if (procedure? x)

(lambda (y)

(local ((define arg (enforce (fun-ty-arg type) y)))

(enforce (fun-ty-ret type) (x arg))))

(err 1))])))

(check-expect (enforce Number 1) 1)

(check-error (enforce Number "hi"))

(check-expect (enforce Boolean #true) #true)

(check-expect (enforce String "hi") "hi")

(check-error (enforce String 34))

(check-expect (enforce (Pair-of Number Number) (make-pair 1 2)) (make-pair 1 2))

(check-error (enforce (Pair-of Number String) 1))

(check-expect ((enforce (Function Number Number) (lambda (x) x)) 1) 1)

(check-error ((enforce (Function Number Number) (lambda (x) x)) "hi"))

(check-error ((enforce (Function Number String) (lambda (x) x)) 1))

An example where we used this to find a bug where our implementation did not match our signature is the following:

; positive : Number -> Boolean

; returns whether number is positive

(define positive (enforce (Function Number Boolean)

(lambda (x)

(cond

[(<= x 0) "nonpositive"]

[(> x 0) "positive"]))))

Exercise 2 Extend the Type data definition and the enforce function to handle lists (i.e., [List-of Number], [List-of [Number -> String]], etc). Use enforce to rewrite the following two functions to enforce the signatures (you should rewrite them in the same way that positive was rewritten above, and running them on input should produce an error telling you what was wrong – but do not correct the functions):

; sum-list : [List-of Number] -> Number

; Adds up the numbers in the list

(define (sum-list lon)

(cond

[(empty? lon) 0]

[(cons? lon) (+ (first lon) (sum-list (first lon)))]))

; contains-frog? : [List-of String] -> Boolean

; Returns whether or not the list contains "frog"

(define (contains-frog? los)

(cond

[(empty? los) "false"]

[(cons? los) (or (string=? (first los) "frog")

(contains-frog? (first los)))]))

Exercise 3 Design the function type->string that, given a Type, returns a string that contains the type as it would appear in a signature. Some tests (among others) that it should satisfy:

(check-expect (type->string String)

"String")

(check-expect (type->string (Pair-of Number Boolean))

"[Pair-of Number Boolean]")

(check-expect (type->string (Function (Function Number Number) String))

"[[Number -> Number] -> String]")

Now fix the enforce function so that it uses type->string when it produces error messages, so that the errors you get are easier to read.