cs380 scope; recursive data definions

Your name and the assignment-number must be in a comment at the start of the file, and your hardcopy must be stapled. All functions/data must include the appropriate steps ¹ of the-design-recipe.html. In particular, test cases alone might be worth half the credit for a function. Unless otherwise indicated, two test cases will suffice for most problems, if they are testing different situations.

For this (and future) assignments, bump up your DrRacket language-level to Intermediate Student with lambda. Do not call any of the following functions:

Recall: the scope of identifiers introduced with let is just the body of the let, while the scope of identifiers introduced with let* is the body of the let and all following right-hand-sides of the let*.

Fill in the blank, with the result of evaluating the expression.
For each variable-use of a below, indicate where it gets its value from — its binding-occurence (that is, the line where that a is declared). For example, if a was used in some line F7, and that use’s binding occurrence was the global declaration in line 01, write “01 → F7” (the arrow showing the direction of information-flow). A different use of a might cause you to write something like “G3 → G6”. Unlike grammars, this use of the symbol “→” is not a standard one.

DrRacket's Check-Syntax: Yes, you can answer this question by putting the code in DrRacket and clicking the Check Syntax button, and then mousing over a to see the arrows you'll write, as well as verify the result. But first attempt it “by hand”, since if it's on the exam you won't have DrRacket with you.

In all cases, presume we have:

line 01 (define a 5)
line 02 (define b 10)

line A1  (let {[z 50]
line A2        [a 51]
line A3        }
line A4    (+ a b z))

; evaluates to:         , with one use of a:       →

line B1     (let {[z 50]
line B2           [a 51]
line B3           [b (* a 3)]
line B4           }
line B5       (+ a b z))

; evaluates to:         , with two uses of a:       →       and       →      .

line C1     (define (foo a)
line C2      (let {[z 50]
line C3            [a 51]
line C4            [b (* a 3)]
line C5            }
line C6         (+ a b z)))

line C7     (foo 1001)

; evaluates to:             , with two uses of a:       →       and       →      .

line D1     (let* {[z 50]     ;note: let*, not let.
line D2            [a 51]
line D3            [b (* a 3)]
line D4            }
line D5        (+ a b z))

; evaluates to:         , with two uses of a:       →       and       →      .

processing a recursive datatype definition:

The Design Recipe

Who doesn't love binge-watching TV shows?² After extensive research to determine what aspects of a TV series are important for binge-watching information, I have personally determined that most shows have plot threads which may span several episodes. It's not even important what the plot threads are; we can abstract away to just counting how many plot threads there are.

A binge-task is one of:

A cliff-hanger, which contains three things: a number (how many existing plot threads are resolved), another number (how many new plot threads are introduced), and the remaining-show — a binge-task.
A moral, which: introduces either 0 or 1 plot threads (never more); never resolves any; contains a moral (like Be nice., or A fool might show great wisdom, like Phoebe. (Or might not, like Joey.) ); and the remaining-show — a binge-task.
A finale, which has only one piece of interesting info: how many plot threads are resolved. (None are introduced.) It's the last episode of a binge-task; there is nothing more.
A shark-jump: No plot threads are introduced, and exactly two are resolved. But it's so contrived that everybody stops watching their binge-task, so there is nothing more after that.

List-like, but not lists: Although binge-tasks are not lists, they are certainly reminiscent of them: For example, finales and shark-jumps (like empty-lists) cannot possibly followed by any additional tasks. However, cliff-hangers and morals (like cons structs) do have information about an episode, “followed” by one more binge-task (which may be another cliff-hanger which itself contains yet another binge-task, etc.).
Compare this to how we represent a list of a thousand numbers really being a cons struct with only two fields: the first number, and the remainder of the list (which is another cons which itself contains yet another cons, etc.).

So: Do not use built-in lists; everything you need comes straight from the definition above.

Give a racket data-definition to represent a binge-task. Do this by having functions named binge-task?, as well as finale?, — just like we had anc-tree?, child?, and unknown? defined in anc-tree.rkt. Of course, some of these functions might get made for you via define-struct/c.
Hint: In cases where you don't have more than one piece of information to track, you don't need to introduce any compound-data.

warning: Make sure that you can distinguish between a shark-jump, and a finale that happens to resolve two threads (they are different). Also, do not try to represent all the above using a single struct -- one which contains a number-of-threads-introduced and a number-resolved and some sort of tag, plus further fields that are only meaningful depending on the tag. That would be sloppy data-modeling; a shark-jump struct/object shouldn't contain fields that are meaningless, nor fields whose value is a function of other fields ³.
Make five examples of binge-tasks (each different from each other in an interesting way). Give names to them (using define); four suggested names are provided; be sure to provide the close-paren.
(define finale0 (define shark0 (define moral1 (define cliffhanger1 (define
Note that to build examples from our definition, your first example(s) must necessarily be ones that don't contain a remainder-of-the-binge-task.

Write the function count-morals which is given a binge-task, and returns how many (possibly nested) morals it contains.

(check-expect (count-morals finale0)         )
(check-expect (count-morals shark0)         )
(check-expect (count-morals moral1)         )
(check-expect (count-morals cliffhanger1)         )
(check-expect (count-morals                         )         )

Your function should follow the template directly. Thus it will not be tail-recursive. You do not need to write the template-for-binge-tasks, but certainly all its steps are required for writing the above function.

Write the function net-unresolved : binge-task -> number
which returns how many plot threads are introduced, minus how many are resolved.

Note: If somebody starts a binge-task halfway through, this might be a negative number, if they see a thread resolved that they never saw originally introduced ⁴ .

(check-expect (net-unresolved finale0)         )
(check-expect (net-unresolved shark0)         )
(check-expect (net-unresolved moral1)         )
(check-expect (net-unresolved cliffhanger1)         )
(check-expect (net-unresolved                         )         )

Write the function bullseye : (-> natural? image?), where:

(check-expect (bullseye 3) (underlay (circle 30 'solid 'blue) (circle 20 'solid 'red) (circle 10 'solid 'blue)))

data def: Recall: A natural-number is:

0, OR

(+ 1 [natural-number])
The built-in predicates zero? and positive? are often used to distinguish the two branches, though of course = and > could be used equally-well.
And/or, see the lecture's notes on natnums as recursive data [code: before, after], about viewing sub1 as the getter to pull out the natural-number field, which a positive is built out of.

The built-in function even? can help you decide what color a circle be.

processing the natnum datatype definition: Write my-take, which takes a list and a number, and returns the list containing the that many items from the front of the list. (my-take 2 (list 'a 'b 'c 'd 'e)) will return (list 'a 'b). The pre-condition ⁵ is that the list contains at least the given number of items. Of course, do not just call the built-in take. Follow the data-definition for natural numbers, instead of for lists. (So do not check for the empty-list.)

Write a function that takes in an anc-tree, an eye-color to change, and a new eye-color to replace it with. It returns a similar anc-tree where those eye-colors have been changed, but stopping if the new-eye-color is encountered. For example, you'll might replace all brown-eyed childs with a 'green except that when you reach a green-eyed person, you don't change any of their ancestors. Call your function change-eyes-to-until⁷.

¹ Your final program doesn’t need to include any "transitional" results from the template: For example, you don’t need the stubbed-out version of a function from step 5. However, you should still have passed through this phase. ↩

² Who'd love to have enough time to binge-watch a show? ↩

³ A field which is a function of the other fields is a violation of 2nd Normal Form, in database-speak. In O.O., we might have a getter without having a backing field. ↩

⁴ Heck, if the writers resolve a thread that never was introduced, this could be negative?! Our data-definition doesn't preclude that. It would be reasonable to do so (if you want to rule out later writing prequels). However, that property is one that isn't a function of the binge-task itself; it relies on information about binge-tasks that refer to it. Thus the current datatype-definition and its template is not appropriate, or at least not self-contained. ↩

⁵ Remember, your code doesn't need to check the pre-condition; if the caller violates it, your code can do whatever it likes — return a wrong answer, throw a (different) exception, run forever. For example, in Java "hello".substring(3,1) throws an exception with the slightly odd message “String index out of range: -2”. ↩

⁷ Well, more seriously: we’ll do an equivalent tree-traversal in the future, when working with parse-trees for a programming-language:
we’ll want to re-name all occurrences of a variable x, but if we come across a new variable-declaration named x, that’s making a new, different variable — so don’t change that x, nor any x in sub-trees of that declaration. We say that the newly-declared x is shadowing the original “outer” x. ↩

⁶ People sometimes wonder what possible use-case such a function could have. Well, sometimes you want to forge an ancestor-tree to make yourself appear to be irish, by having a version where all your 'brown-eyed ancestors are now listed as 'green. But once a particular branch encounters a real green-eyed ancestor, there's no need to extend the lie further. I mean, we have our standards, right?⁷ ↩