[PRL] basic terminology: abstraction

[Karl Lieberherr]

For me it depends on the context how the loop concept is related to
recursion.

Context: Looping through objects: Loops more abstract than recursion.
An example is that we want to loop through all B-objects contained in an
A-object. I like to think of such a loop as being specified by a graph using
the slogan LOOP=GRAPH domain-specific language. The implementation of such a
loop depends on the class graph and if the class graph is cyclic, the
typical implementation is recursive. So in this context loops are an
abstraction layer (expressed by a domain-specific language in the sense of
Hudak) that may be implemented using recursion.

The enlightened Java user would write:

A a = new A(...);
List l  = classGraph.asList(a, "from A to B");
and then loop through the list as Dave shows below.

This does not "expose details of the iteration process" as Dave writes.
Indeed it is a beautiful structure-shy specification of the loop. Of course,
the enlightened Scheme user can and has done the same.

Context: Grammars: Loops a simple application of recursion.
Loop = List. Here the loop concept is expressible in terms of recursion of
concrete and abstract nonterminals. Loops are an application of recursion.

-- Karl

-----Original Message-----
From: prl-bounces at lists.ccs.neu.edu [mailto:prl-bounces at lists.ccs.neu.edu]On
Behalf Of David Herman
Sent: Saturday, August 23, 2003 1:47 PM
To: Matthias Felleisen
Cc: prl at lists.ccs.neu.edu
Subject: Re: [PRL] basic terminology: abstraction

On Saturday, August 23, 2003, at 11:16 AM, Matthias Felleisen wrote:

> 1. Guido and I are in complete agreement. He has some intuition; I
> just wish he
> understood 311 and friends.

Well, Guido and I are only in partial agreement. He's right that loops
are at a higher level than recursion. I agree with him in that
(for-each display alos) is more appropriate than a full structural
recursion. The for-each loop is the right semantic level to think about
"display all the strings in alos." The rest is implementation detail
that's irrelevant at this level, which a full recursion would expose.

But in a language like Java (say, with generics), a loop is going to
have the exact same problem:

     List<String> alos;
     ...
     for (Iterator<String> it = alos.iterator(); it.hasNext(); ) {
         String s = it.next();
         System.out.print(s);
     }

This loop exposes detail of the iteration process just like the
recursion above. A solution is eventually coming to a future version of
Java:

     for (String s : alos) {
         System.out.print(s);
     }

So Java programmers have to wait for Java's enlightened despots to add
to the toolbox of loops. But higher-order, recursive functions in FPL's
allow the developer to decide what abstraction (in the sense of
generalization) will serve as the best abstraction (in the sense of
semantic level) for his/her particular program.

I know I'm preaching to the preacher here, but my point is that
although I agree with Guido that loops are a higher semantic level than
recursion, I think he's at least implying that recursion is somehow
"too powerful" or "too difficult" for mortal human beings. I suppose I
can accept that recursion is harder to understand than particular loop
constructs. After all, the abstract (general) is always harder to
understand than the particular. But without sufficiently powerful
abstraction (generalization) mechanisms, you can't create higher levels
of abstraction (semantic level). In other words: feed a programmer a
loop and he'll loop for a day; teach him how to recurse and he'll
create loops for a lifetime.

> Now start reading Bob's paper
> from there and a lot of things become clear. (That's where Bob's
> tremendous contribution
> is and I wish people understood this. Then again, he makes no effort
> to communicate, so
> perhaps he deserves what he gets.)

I found Hudak's report at
<http://citeseer.nj.nec.com/hudak96building.html> but couldn't figure
out which Harper paper you're referring to. Which one do you mean?

Thanks,
Dave

_______________________________________________
PRL mailing list
PRL at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/prl