[racket] Top-down design, wish-lists, and testing

From: Don Blaheta (dblaheta at monm.edu)
Date: Sun Nov 21 22:53:44 EST 2010

I'm teaching from HtDP2 right now and I've got a bit of a... complaint?
Maybe more of a request.  The top-down design process starts to create a
significant cognitive load when combined with the test-driven approach,
especially in beginner students.  But I might have a solution.

Here's the problem.  Assuming I'm solving a non-toy problem, assuming I
haven't yet fully broken down the problem, I'm doing top-down design as
I go.  And when I do get to the "write code" step of writing a function,
I may see that there's something complex to be done---and I "wish" for a
helper function.

Now what?  What does wishing entail?

Well, I could do nothing but write it down on a piece of paper or in a
comment.  This is basically the technique described in HtDP.
Unfortunately, this doesn't mesh well with iterative design; I want to
be able to click Run frequently to verify that I don't have any
"red-letter errors" (compiler errors and run-time errors), just test
case failures.  But functions that are just written on a wish list are
not known to Racket and can't be called.

As alternatives, I have two main options.

1) I can write a function stub, with minimal description and no test
cases, just to make the error messages go away, and make sure I'm done
with the original function (at least for now) before continuing on to
write the helper functions.

2) I can write a description, signature, stub, and test cases for the
helper function, and only then set it aside to add another item to the
wish list or finish writing the original function.

#2 is better in many ways, more in keeping with the test-driven
philosophy and much less likely to be forgotten later (since the test
cases will keep failing until I've fixed the function).  However, if the
first place I can "pause" writing the helper function is after I've
worked out the test cases, I have *completely* lost my train of thought
on the original function.  Also, if I do anything wrong in terms of type
mismatches, argument mismatches, or paren problems, by the time I get to
click Run I have a lot more places to look for problems.  In practice,
#1 requires holding a lot less context in my head and eliminates the
need to "pop the stack" (it is, if you will, a tail call); it's just
that it's, well, unsafe.  In a non-test-driven system I'd use something
like #1, add a comment /* XXX */, and move on, but this is fairly
antithetical to the HtDP style.

Here's an example from a program I'm developing right now---I'm
implementing the Space Invaders assignment I just gave to my students.
I write this much:

  ;; defender-key : Defender KeyEvent -> Defender
  ; computes new defender position for given defender and given
  ; key; responds to left and right; stops at edges; moves by 10s
  (check-expect (defender-key 100 " ") 100)
  (check-expect (defender-key 100 "left") 90)
  (check-expect (defender-key 100 "right") 110)
  (check-expect (defender-key 0 "left") 0)
  (check-expect (defender-key WIDTH "right") WIDTH)
  (define (defender-key current key) 
    (cond [(string=? key "left")  ...

and as I go to fill in the ... I see that it's slightly complex so I
want to fill in with (defender-left current).  I make a note of the need
for a defender-left : Defender -> Defender in a comment, maybe with a
little description.  But if that's all I do, then when I've finished
this function (where I also add a defender-right to the wish-list before
I'm finished), if I click Run I still have errors.  And even if I write
out a bit of defender-left, including test cases, I can't test that
until I've also written out a bit of defender-right.  Before I'm done
I've written more than twenty lines of stuff before I could click Run.
And while I personally can handle that without trouble, the odds of any
but my best students getting through that without any syntax errors is
pretty low, and then they are in debugging hell.

The solution is to make the experience more like #1 above, but without
the unsafety.  Here are three ways to do so, in decreasing level of
implementation difficulty.

PROPOSAL A: wish-for
Add a construct to the tester library that reserves a to-be-defined
function name and declares it as "wished for":

  (wish-for defender-left)
  (wish-for defender-right)

This has two effects: first, the Test Results window/pane will report
that these functions are wished for, and the implementation is therefore
incomplete.  Second, execution of any function that *calls* a wished-for
function immediately halts with a check failure, giving a message like 

  defender-key depends on unimplemented function defender-left in space-invaders.rkt, line 19, column 0

But this is a check failure, not a runtime error, and so subsequent
tests can be run (i.e. the student can continue working on other parts
of their program.  This proposal is minimally intrusive into the thought
process and lets the programmer finish the original function while just
leaving a note to themselves about the helper; it corresponds most
closely to the design process suggested in HtDP while preserving both
"click-Run-ability" and check safety (where "check safety" is a property
of a function that might be defined as "either the programmer would be
satisfied that it is complete or else at least one test case fails").

PROPOSAL B: wish-stub
Add a construct to the tester library that stubs a to-be-defined
function name with a dummy value, and declares it as "wished for":

  (wish-stub defender-left 0)
  (wish-stub defender-right 0)

Similar to A but includes a dummy value of the appropriate type.
Implicitly declares a vararg function that always returns the stubbed
dummy value a la

  (define defender-left (lambda arglst 0))   ; autodefined by wish-stub

but also causes the Test Results window/pane to report these functions
as wished-for.  Compared to A, this version is only a slight added
cognitive load for the programmer (having to understand the role of the
helper well enough to give a valid dummy output value of the correct
type), but it removes the need for program tracing and/or exception
handling---since the helper will now return a valid value, the original
function will simply have a normal check failure.  However, the
programmer doesn't have to worry about half-assing some test cases or
omitting test cases and forgetting to fill in the stub later.

PROPOSAL C: check-stub
Add a construct to the tester library that declares a particular
function as "wished for", essentially just an always-failing test case.

  (define (defender-left current)
  (check-stub defender-left)

This is a simplification of B that puts the onus back on the user to
actually declare the function.  The reason I prefer B to this is that
it's more of an intrusion on the design process, and in particular, you
need to either come up with good argument names right away or else toss
in something you haven't thought about enough---and the whole goal of
this proposal is to *minimise* the amount of stack that the (student)
programmer needs to maintain.  Also, if the user forgets to remove a
wish-stub declaration when they define the function for real, this is
easily identified as a conflict (because both are trying to define the
function), while it's harder for a lingering check-stub to notice that
the corresponding function has a "real" function body now.

Sorry, that got long; I've been thinking about this for a few months
now.  Let me know what y'all think; I may try to put together a
teachpack over winter break.

-=-Don Blaheta-=-dblaheta at monm.edu-=-=-<http://www.monmsci.net/~dblaheta/>-=-
This sentence contradicts itself---no actually it doesn't.
						--Douglas Hofstadter

Posted on the users mailing list.