Principle #1: The entire program gets to know, and take advantage of, the representation of any data type.
Principle #2: In an SD, you get to write a “function composition of the values of the fields”. See detailed discussion below.
Principle #3 (by example): In a list of structures, you get to write a function composition of (book-fn (first lob)) and (lob-fn (rest lob)). The book-fn MAY be book-author or the like As with any template, you get to use multiple instances of these.
; #1: Not legal
; NOT a legal SD on robot
; -- way too complicated to be a FC of (robot-dir r)
(define (rob-north? r)
(cond
[(string=? (robot-dir r) "north") true]
[(string=? (robot-dir r) "south") false]
etc))
; this is a legal structural decomposition on robot.
; observe that (string=? x “north”) would be a legal function composition,
; so (string=? (robot-dir r) “north”) is a legal function composition of (robot-dir r).
; sd on robot
(define (rob-north? r) #2
(string=? (robot-dir r) "north"))
; sd on robot -- also legal.
(define (rob-north? r) #3
(north? (robot-dir r)))
;; legal sd on dir
(define (north? d) #4
(cond
[(string=? d "north") true]
[(string=? d "south") false]
etc
))
;; legal function comp (!)
;; this follows from
;; Direction -> Boolean
(define (north? d) #5
(string=? d "north"))
;; #6: NOT a legal SD on robot
;; Too complicated to be a FC
(define (foo r)
(cond
[(robot-north? r) ...]
[(robot-east? r) ...]
...))
;; #7 legal SD on ListOfBook
;; the template says (... (book-fn (first lob)) (lob-fn (rest lob)))
(define (books-by lob name)
(cond
[(empty? lob) empty]
[else (if (string=? (book-author (first lob)) name)
(cons (first lob) (books-by (rest lob) name))
(books-by (rest lob) name))]))
;; #8 Legal SD on ListOfBook
(define (total-margin lob)
(cond
[(empty? lob) 0]
[else (+ (- (book-price (first lob)) (book-cost (first lob)))
(total-margin (rest lob)))]))
;; This is legal, but calling a help function (book-margin b) is better.
;; This gets -0.5 for improvable code.
Examples:
Two versions of the DDs for Inventory:
A Book is ...
..interp…
..template..
A ListOfBook is one of
-- empty
-- (cons Book ListOfBook)
{no interp necessary here}
TEMPLATE:
;; lob-fn : ListOfBook -> ??
(define (lob-fn lob)
(cond
[(empty? lob) …]
[else (... (book-fn (first lob))
(lob-fn (rest lob))))]))
An Inventory is a ListOfBook
WHERE: no ISBN is duplicated
{Once they have an interpretation for Book, they don’t need anything else}
Alternative 2 (also ok, but the other is preferred)
An Inventory is one of
-- empty
-- (cons Book Inventory)
WHERE: the ISBN of the Book does not occur in the Inventory.
Contract/Strategy:
Any combination of the following is OK:
inventory-total-profit : Inventory -> Integer
OR
inventory-total-profit : ListOfBook -> Integer
Strategy: SD on ListOfBook
OR
Strategy: SD on Inventory
Most of the problems in PS03 are really ListOfBook problems, because they do not rely on the “no duplicate ISBNs” invariant.
Here’s one where it makes a difference:
;; remove-book : Inventory ISBN -> Inventory
;; RETURNS: the inventory obtained by removing the given ISBN from the given inventory
;; STRATEGY: Struct Decomp on Inventory
(define (remove-book inv isbn)
(cond
[(empty? inv) empty]
[else (if (has-isbn? (first inv) isbn)
(rest inv)
(cons (first inv) (remove-book (rest inv) isbn)))]))
If you just had a ListOfBooks, possibly with duplicate ISBNs, then the purpose statement is insufficient: it’s ambiguous about whether you are supposed to remove ALL of the books with the given ISBN. If you are supposed to remove all the books, then of course you need another recursive call at the next-to-last line.
The purpose must be clear, correct, and add at least some information beyond the contract. (That much is in the rubric).
The RETURNS clause must at least mention every one of the function arguments.
The RETURNS clause must be sufficiently specific so that any value that is described by the returns clause is acceptable as a value for the function. If there are values that satisfy the returns clause, but will cause a caller of the function (including one of our tests) to return a wrong answer, then the RETURNS clause is insufficiently specific.
Like the interpretation, the RETURNS clause may rely on the reader’s understanding of the problem set.
It is OK to omit the GIVEN clause if the givens are clearly referenced in the RETURNS, and a GIVEN clause would add no new information. Example:
;; replace-topping : Pizza Topping Topping -> Pizza
;; RETURNS: a pizza like the given one, but with
;; all instances of the first topping replaced by
;; the second one.
When we write
(... (book-fn (first lob)) (lob-fn (rest lob)))
we mean “any function composition of (book-fn (first lob)) and (lob-fn (rest lob))”
Lesson 1.7, slide 18, gives a formal definition of function composition
fc ::= var
::= (function fc fc ...)
::= (if (pred var var ...)
fc ;; no conditionals here
fc) ;; no conditionals here
When we get to SD, we change the definition of var:
var ::= variable |
::= (field-selector argument) ;; or whatever the template says
When we get to HOFC, we add some new possibilities:
fc ::= function
::= (lambda (variable ..) fc)
This is enough to allow you to reject many too-complicated definitions. The ultimate question, as always, is: Is it clear?
Must a student write HOFC+SD on… or SD on.., + HOFC ?
A student should write HOFC, rather than Functional Composition, if they use map, fold, etc. or lambda.
If they use SD on any value, then they must write SD. They don’t need to write …+HOFC or HOFC+... .