Computing a scheme expression is just like computing an algebra expression: you keep simplifying an expression until you reach a value. The only difference is that in scheme, we've augmented our world with booleans and symbols, and we've taken the declaration of functions to a new level. The half-page Law of Scheme, is the full explanation of everything that scheme does.
"Hand-evaluation" just means, following the Law of Scheme by hand, to fully understand what it's doing.
Hand-evaluate the following (admittedly small-minded) expressions:
(define zz 93)
; Use the law for values, placeholders, built-in functions:
(* zz (+ 2 1))
; Use the law for cond:
(cond [(< zz 17) true]
[true false])
A few things to note:
cond:
if the first question evaluates to true,
the entire cond
expression is equal to the first answer
(i.e., whatever that answer-expression evaluates to).
If the first question evaluates to false,
then the entire cond evaluates to
another, slightly smaller cond.
cond expressions, like any expression, can
occur on their own
(they're not limited to being inside functions).
cond,
and which just happen to be from the question or the answer
part of the question/answer pair.
(This example involved some questions and some answers
which were already values, not even function calls.)
true as your last question,
use the more idiomatic else.
(This example just shows that the law of scheme holds.)
(< zz 17)
was true, and false if it was false.
Thus this big cond is an extremely roundabout,
ungainly way of writing (< yy 17)!
and, or
can save you unnecessarily big cond statements.
Finally, let's practice the one more step of evaluating a function-applicationg for functions you've defined. Hand-evaluate:
;; less17?: number --> boolean
;; Is yy less than 17?
;; A long-winded example using cond, instead of just < !
;;
(define (foo yy)
(cond [(< yy 17) true]
[true false]))
(less17? (* 1 zz))
Note that before
less17?
ever gets called, the initial *
has already been evaluated, and
less17?
has no idea that the
placeholder zz was ever involved in the input.
Biologist Gwynn Penn, of the Flightless Avian Research Center of Estonia, is studying penguins in antarctica. She flies over the Larsen ice shelf, counting penguins. (However, due to fog, some days she is grounded at McMurdo base.) She records her data as follows:
;; A datalist is: ;; - empty ;; - (cons [number] [datalist]) ; Number of penguins sighted. ;; - (cons 'fog [datalist])
We'll write some programs to process her data. We already have the data definition given to us, so we'll follow the remaining steps of the design recipe. As a group:
and, if you don't
want your code's correctness to rely on the ordering
of your cond branches.)
We'll write the following functions. For each of them, we'll want the remaining steps of the design recipe (what are they?)
Write a function which counts how many fog-days occur in the datalist.
Gwynn has a theory about mating season being correlated to
days when she observes more than 400 penguins.
Write a function partieswhich takes in a datalist,
and returns a list:
for each penguin-count in the data, the output contains
whether or not the number of penguins is greater than 400.
(Days she was fog-bound contribute nothing to the output.)
Preliminary note:
For a number
x,
how do you get
a boolean representing whether
x is bigger than 400?
Hint: you don't need cond!
Also, be sure not to have the magic number 400 appear in your code, w/o naming it!
(solution)
Gwynn's predecessor, Ken Chi, was dismissed for fudging his data.
He had gone through his datalist,
and replaced each fog day with the most recently seen real penguin-count.
(For datalists which began with fog, he initially took 345 as fudged penguin
count.)
See if you can also write this function fudge.
(Not that you'd ever use it;
after leaving F.A.R.C.E., Ken now makes minimum wage, tallying poultry.)
This function is best written with an accumulator, which remembers the previously-seen actual penguin-count.
Optional:
If you want, you can fudge data better than Ken by
adding a random number in [0,20)
to the previous real count;
(random 20) returns such a random number.
(solution)
A variation on the previous, for practice: Write a function to return whether each penguin count is bigger-or-equal than the previous observation (ignoring fog days).
(Note that before starting the code, one of your test cases should spur you to wonder what the appropriate answer is for a datalist which is empty or has any fog days.) We'll take the position that as long as we never observe a decrease, then it's equal-or-increasing.
Optional variant: as above, but
return true only if we've observed two or more non-fog entries.
Hint: doing this by hand, what extra bit of information are
you keeping track of in your head?
Is it information derived from the sub-pieces of the list,
or from parts of the data you've already seen? The latter
indicates an accumulator is called for!)
(solution)
Just what do accumulators do for us? They capture information from parts of the data already seen. (E.g., when fudging the data, you need to remember what the previously seen penguin-count was.)
length
and
sum.
If you just write a function filter-numbers,
then you'll just need to call those existing functions!
Note: the average is ill-defined, for datalists.
Change your problem statement to return 'no-average-exists
in this case.
Note that your code will have a cond,
but it is serving a very different from other uses we've seen:
it's not doing any sort of case analysis!
Is it okay to not use the template, like this?
Yes -- if you think about it, really, the functions
length
and
sum
are the places doing the work guided by the template,
and you're deferring to them.
;; length: list --> number
;; Return the length of data.
;;
(define (length data)
(cond [(empty? data) 0]
[(cons? data) (add1 (length (rest data)))]))
;; sum: list-of-number --> number
;; Return the sum of all numbers in data.
;;
(define (sum data)
(cond [(empty? data) 0]
[(cons? data) (+ (first data) (sum (rest data)))]))
Finally, a note on this data definition. A way to organize the data which more closely matches our intuition might be to say:
; An observation is ; - [number] (the number of penguins sighted) ; - 'fog ; A datalist is ; - empty, or ; - (cons [observation] [datalist])
How does this impact functions dealing with datalists?
They only have two cond branches,
and the branch for cons
will recur on its rest,
and will call an entirely different
Observation-handling function on the first.
(Here, since we're doing accumulators, some of those
observation-handling functions might be giving their results
to serve as the accumulator of a recursive call.)
While this results in more functions,
it also cleanly separates the functions which do the work
of handling the list,
from the functions which do the work
of an individual observation.
In this case it's a wash (since Observation is so simple),
but in general we'll prefer the latter approach.
We'll make it clear on exams, if we want you to use
one approach or the other.
Exercise (if you have time):
Re-do the templates based on
this revised data definition,
and write
parties-v2.
Note that the test cases will still
look identical.
Further exercise (harder):
Write fudge-v2.