9 Design and Reasoning
23 September 2024
Questions?
9.1 Program Design
Fundamentals I and II use the phrase “designing programs” not “programming.” Why?
This part is about matching the design of the functionality to the choice of data representation.
9.1.1 Data Representations and Functionality
.. determines the organization of code. If it doesn’t,
the developer is in trouble
a future reader is going to be confused.
Fundamentals 1 teaches to match the nest of functions to the data definitions and the conditionals in each of them to the respective datatype.
Fundamentals 2 teaches to realize each variant as an implementing class and to allocate the respective piece of the functionality to its corresponding class.
The Shape Example
type Shape = Square(Point) | Circle(Point) | Union(Shape, Shape) |
type Point |
The desired functionality is the pointInside function:
;; is the point properly inside this shape? |
pointInside : Shape Point -> Boolean |
(define (pointInside s p) (match s [(? square?) ...] [(? circle?) ...] [(union left right) (... (pointInside left p) (pointInside right p) ...)]))
(define (pointInSquare s p) ...) (define (pointInCircle s p) ...)
According to Fundamentals 2:
The data representation is expressed via a shallow class hierarchy:
+ ----------- + + ----------- + |
| IShape | <------- | AShape | |
+ ----------- + + ----------- + |
| |
+---------------------- + ----------------------+ |
| | |
+ ----------- + + ----------- + |
| Square | | Circle | |
+ ----------- + + ----------- + |
The "signature and header" go into the interface, while the actual functionality
is distributed across the implementing classes—
interface IShape { |
;; is the point properly inside this shape? |
Boolean pointInside(Shape s, Point p) |
} |
Remind students of this—
Remind students that dynamic dispatch realizes the cond for the datatype.
All other conditionals in OOP should relate only to results not inputs.
9.1.2 Functionality Extensions
;; is the point properly inside this shape? |
maxArea : Shape -> Integer |
(define (maxArea s p) (match s [(? square?) ...] [(? circle?) ...] [(union left right) (... (maxArea left p) (maxArea right p) ...)]))
According to Fundamentals 2: yes. Every interface and every class needs surgery following plain OO design:
+ ----------- + + ----------- + |
| IShape | <------- | AShape | |
| xxxxxxxxxxx | | xxxxxxxxxxx | |
+ ----------- + + ----------- + |
| |
+---------------------- + ----------------------+ |
| | |
+ ----------- + + ----------- + |
| Square | | Circle | |
| xxxxxxxxxxx | | xxxxxxxxxxx | |
+ ----------- + + ----------- + |
If we use the Visitor pattern, we get easy functional extension. But do we get easy variant extension?
9.1.3 Variant Extensions
type Shape = Square(Point) | Circle(Point) | EquiTri(Point) | Union(Shape, Shape) |
type Point |
(define (pointInside s p) (match s [(? square?) ...] [(? circle?) ...] [(? equtry?) ...] ; <===================== [(union left right) (... (pointInside left p) (pointInside right p) ...)])) (define (maxArea s p) (match s [(? square?) ...] [(? circle?) ...] [(? equtry?) ...] ; <===================== [(union left right) (... (maxArea left p) (maxArea right p) ...)]))
According to Fundamentals 2: no, if we used plain OO design of data representations:
+ ----------- + + ----------- + |
| IShape | <------- | AShape | |
+ ----------- + + ----------- + |
| |
+---------------------- + ----------------------+ |
| | |
+ ----------- + + ----------- + + ----------- + |
| Square | | Circle | | EquiTri | |
+ ----------- + + ----------- + + ----------- + |
|
^^^^^^^^^^^^^^ |
^^^^^^^^^^^^^^ |
A plain Visitor pattern would create an obstacle for this kind of extension.
9.1.4 Data Representations for Intermediate Data
Skip if no time for reasoning
When programmers deal with use cases and external boundaries, choosing a data representation is about representing information.
When the processing of a use case involves internal components, those are designed to match a developer’s needs.
Abstract example designing a function f that consumes data A and produces data C may not be a good match because A and C are so far out of sync. Come up with a form of data B such that
#; [A -> C] (define (f a) (define b (g a)) (define c (h b)) ; return: c) #; [A -> B] (define (g a) ...) #; [B -> C] (define (h b) ...)
Concrete example The following example is artificial but derived from a real-world one that occupied people’s mind in the 1970s:
Design the program analysis, which consumes a file of text. Each line contains words formed from the letters ’a’ through ’z’ and separated by spaces from each other. The word "stop" separates paragraphs from each other. For each of these paragraphs, the program is to determine (and report) the number of words it contains and the length of the longest word it contains.
Constraint The chosen programming language supports only one function to read from text files: read-line, which reads a line at a time.
(struct result [word# longest]) #; type Result = (result Natural Natural) #; (result k n) ;; k represents the number of words in a paragraph, and ;; n the length of the longest one #; [ String -> {Listof Result}] (define (analysis file-name) (define b (read-lines-from-file file-name)) (define c (analyze-paragraphs b)) ; return: c)
Why? Such a list is easy to produce and, when consumed, allows an easy partitioning into “paragraphs.”
And that’s the general guideline for choosing such intermediate representations.
9.2 Reasoning
The following questions are about xjson or really xjson-server-script-ish.rkt.
The first one needs to be asked because a lack of types. It’s these kinds of questions that type systems help with (but not with the tracing we do here).
The second one is a fully semantic question.
The answers are to be worked out with the students in a discussion.
9.2.1 Do the ++ functions receive directories?
Trace across three function calls. Start tracing from ++file and ++dir
9.2.2 Why are Files Never Replaced?
There are two kinds of commands that may request the replacement of a file with a sub-directory:
The first one uses a file name in the "middle" of a path:
{ "path" : "/root/fileone/filetwo", "size" : 11 } |
Assuming fileone exists in root, this command requests turning it into directory and placing filetwo into it. The path is valid, but incorrect with respect to the specified functionality.
This kind of request is rejected in update. Trace from split.
The second one requests turning
{ "path" : "/root/fileone", "subs" : ["afolder", "anotherfolder"] } |
Again, assuming fileone exists in root, this one asks to treat it as a directory to place two sub-directories into it.
This second bad request is rejected in ++dir; see first cond line:
Total: 65 mins