itec380 scope; recursive data definions

scope; recursive data definions

Due Oct.10 (Tue) at start of class Submit via D2l and hardcopy.

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:

sublist or take, since that's one of the problems below!

list-ref, take, drop and similar built-ins (unless you write them yourself, following the design-recipe)

append (unless you write it yourself, following the design-recipe)

remove (unless you write it yourself, following the design-recipe)

any functions with a “!” in their name, such as set! and set-rest!. They aren't in intermediate-student, anyway.

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*.

Recall: a variable-use's binding-occurrence is the place where that variable is defined.

For each variable-use of a below, indicate where it gets its value from — its binding-occurence. 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”. Another use of a might cause you to write something like “G3 → G6”.
Hint: The binding-occurrence itself is not considered a use of the variable. There are a total of seven uses of a, amongst the four parts.
Fill in the blank, with the result of evaluating the expression.

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:

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

; evaluates to:

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:

line D1     (let* {[z 50]
line D2            [a 51]
line D3            [b (* a 3)]
line D4            }
line D5        (+ a b z))

; evaluates to:

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; a true connoisseur cares only about 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 1: As always, if you introduce compound data you need to provide both the names and types of the fields (use a define-struct/c) , as we did in anc-tree.rkt. ~~and the type of the field (in a sample make-structname)~~.

Hint 2: 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 should 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                         )         )

processing the natnum datatype definition: Write my-list-ref, which takes a list and an index, and returns the list item at the indicated index (0-based). (my-list-ref 2 (list 'a 'b 'c 'd 'e)) will return 'c. In Java, this function is called List#get(int). Your signature should include a type-variable such as α or T. The pre-condition ⁵ is that the index is less than the length of the list. Of course, do not just call the built-in list-ref. Follow the data-definition for natural numbers, instead of for lists. (So do not check for the empty-list ⁶.)

data def: 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 notes on natnums as recursive data, about viewing sub1 as the getter to pull out the natural-number field, which a positive is built out of.

Big picture: One point of these exercises (and, last week's list-processing) is to note that they are all examples of the exact same problem-solving recipe — a union-of-structs (
the composite pattern
). These are not really different topics at all! Even if the exam doesn't specifically have any list-processing questions, it can still check for understanding of the underlying structure.

¹ 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”. ↩

⁶ Since passing in an empty-list is a violation of the pre-condition, you don't need to check for it. Software design suggests your code can do anything it likes in this situation; signalling and error message yourself is a nice "extra", but I want to not do that here, to help reinforce how code follows from the data-definition. ↩

This page licensed CC-BY 4.0 Ian Barland
Page last generated

Please mail any suggestions
(incl. typos, broken links)
to ibarlandradford.edu