[plt-scheme] Help With Abstraction - HtDP 27.2.2

On Tue, May 5, 2009 at 12:27 AM, David Yrueta <dyrueta at gmail.com> wrote:
> Hi All --
>
> The task of HtDP exercise 27.2.2 is to abstract the two functions
> below into a single function:
>
> ;; first-line : file  ->  (listof symbol)
> ;; to compute the prefix of afile up to the first occurrence of NEWLINE
> (define (first-line afile)
>  (cond
>    [(empty? afile) empty]
>    [else (cond
>      [(symbol=? (first afile) NEWLINE) empty]
>      [else (cons (first afile) (first-line (rest afile)))])]))
>
> ;; remove-first-line : file  ->  (listof symbol)
> ;; to compute the suffix of afile behind the first occurrence of NEWLINE
> (define (remove-first-line afile)
>  (cond
>    [(empty? afile) empty]
>    [else (cond
>      [(symbol=? (first afile) NEWLINE) (rest afile)]
>      [else (remove-first-line (rest afile))])]))
>
> Because they appear structurally different, though, "first-line" and
> "remove-first-line" don't seem to me like good candidates for
> abstraction.  While "first-line" appears to be a variant of the
> "reduce/combine" abstraction template introduced in 21.5 --
>
> ;; reduce : X (X  Y  ->  Y) (listof Y)  ->  Y
> (define (reduce base combine l)
>  (cond
>    [(empty? l) base]
>    [else (combine (first l)
>             (reduce base combine (rest l)))]))
>
> -- (the only difference from "first-line" being the lack of
> conditional statement ([(symbol=? (first afile) NEWLINE) empty]) --
>
> -- "remove-first-line" only reduces the input list.  As a test, I
> tried designing versions of both "first-line" and "remove-first-line"
> using the basic structure of the abstract function template "reduce"
> from HtDP.   "First-line" was straight-forward:
>
> ;reduce-symbols : (listof symbols) (listof symbols) (symbol listof
> symbols -> listof symbols) -> listof symbols
> ;function with two termination cases which consumes and produces a
> (listof symbols)
> (define (reduce-symbols l base combine)
>  (cond
>    [(empty? l) empty]
>    [else (cond
>            [(symbol=? (first l) NEWLINE) base]
>            [else (combine (first l)
>                  (reduce-symbols (rest l) base combine))])]))
>
> (define NEWLINE 'NL)
> (define list0 (list 'a 'b 'c 'NL 'd 'e 'f))
> (define list1 (list 'NL))
>
> (define (first-line-abs alist)
>  (reduce-symbols alist empty cons))
>
> (equal? (first-line list0) (first-line-abs list0))
> (equal? (first-line list1) (first-line-abs list1))
>
> "Remove-first-line" did not yield to similar efforts.  This leads me
> to believe they are structurally different, and not easily
> abstract-able.
>
> Next I tried to abstract the condition(s) under which the two
> functions either "combine/reduce" or just "reduce."  At first, it
> seemed that setting 'empty' as the base value triggers the 'combine'
> function, so I tried this:
>
> (define (combine-reduce l base combine)
>  (cond
>    [(empty? l) empty]
>    [else (cond
>            [(symbol=? NEWLINE (first l)) base]
>            [(empty? base) (cons (first l) (combine-reduce (rest l)
> base combine))]
>            [else (combine-reduce (rest l) (rest base) combine)])]))
>
> (define (remove-first-line1 alist)
>  (combine-reduce alist (rest alist) cons))
>
> That works for any list longer than 1 element.  For a 1 element list,
> though, the base evaluates to 'empty,' which changes
> "remove-first-line1" from a "reduce" function to a "combine/reduce"
> function. Also, having to reduce the base argument via (rest base)
> during the recursive call in anticipation of a specific task-- that
> is, applying it to the design of "remove-first-line" -- suggests that
> "combine-reduce" is not an authentic abstraction.
>
> At this point, I've run out of ideas.  I can't design / find a
> template that accommodates abstract versions of both "first-line" and
> "remove-first-line," and also can't manage to successfully abstract
> the conditions under which the functions vary.  What am I missing?
>
> Many thanks!
>
> Dave Yrueta

Dave,

Section 21 of HtDP establishes a recipe for abstracting functions:

http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-27.html#node_chap_21

I'll summarize (off the top of my head, so I might not be saying it
exactly the book's way):

(1) The comparison.

Essentially, here you put the two functions to abstract next to each
other, and put boxes around pairs of corresponding differences between
them (not counting their names).

Wherever the differences do not appear to correspond -- if one
function has two things and the other has three, if one has cond and
the other does not, etc. -- put a box around corresponding expressions
on each side just large enough that the difference can be expressed as
a function.  Within each of these boxes, identify common
subexpressions; anything the same between the two will be an argument
to the function.  (Essentially, the task of finding differences swaps;
inside any difference you find, look for similarities.)

(2) The abstraction.

Next, write a third function.  Its body should be all the parts of the
two functions that were the same.  For each difference you found, add
an argument to the function, and refer to that argument in place of
the differing code.

If the difference was a subexpression that needed to be expressed as a
function, apply the argument representing that function to the common
subexpressions from the two functions.

(3) The test.

Redefine the two original functions in terms of the abstraction.

(4) The contract.

Essentially, apply steps 1 and 2 to the contract.


See section 21 for a more in-depth discussion of these steps,
including some examples.  See also section 19 (linked from 21.1),
which gives the original discussion of "similarities between
functions" that helps with step 1.

It appears you have tried a "holistic" approach to step 2, trying to
find an abstraction based on patterns you have seen before, rather
than going through step 1 for first-line and remove-first-line.  You
call them "structurally different", but when I go through step 1, I in
fact come up with very few differences.

Try these steps and see if you can come up with an example.  If you
can't, let us know what you came up with for each step.

Good luck!

-- 
Carl Eastlund