Homework 10

Due Date Tuesday 11/17 at 9:00pm (Week 10)

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.

Graphs

Exercise 5 Design the function both-neighbors that takes two symbols and a graph and returns the list of both of their neighbors, and be sure not to include any duplicates in the output. Assume both symbols are in the graph. Hint: A function you’ve previously designed will likely be of help here.

Graph Manipulation

For this portion of the homework, you should use the following testing pattern when testing some function f that outputs a graph. Check the docs for check-satisfied for more info.

; make-graph=? : Graph -> [Graph -> Boolean]

; Takes a graph and produces a function that checks if

; its argument is graph=? to the original graph

(define make-graph=? (λ (g1) (λ (g2) (graph=? g1 g2))))

; f : Graph ... -> Graph

; Do something to g

(define (f g ...) ...)

(check-satisfied (f some-input-graph ...)

(make-graph=?

some-expected-graph))

Note on make-graph=? : By analogy, consider the function (define (make-add x) (lambda (y) (+ x y))) that takes a number and produces a function that will add its argument to the original x.

Also, as you create and manipulate graphs, always be sure to uphold the assumptions we made about graphs in our data definition.

Exercise 7 Design the function collapse, which takes in three nodes and a graph. The first two nodes are assumed to be in the graph, and the third is assumed not to be.

The function collapses the first two nodes into one new node, which is named by the third node. All nodes in the graph that were pointing to either of the first two given nodes should now point to this new one, and the new node should point to all nodes either of the first two nodes were pointing to. (To make sure you understand what collapse is supposed to do, you should first sketch out a graph before collapse and after—in other words, it helps to first sketch/visualize the input and output graphs of a test.)

Hint: A function you’ve previously designed will likely be of help here.