[plt-scheme] Re: Tail recursion and the Visitor Pattern

Some thoughts on this Java malarkey from someone who hasn't
studied HtDCH in any detail.

HtDP taught us that there is a direct correspondence between
type defintions and code:

Given the type

type List = Cons a List
          | Null

The code must follow

(define (something a-list)
  (cond [(cons? a-list) ... (car a-list) ... (something (cdr a-list))]
        [(null? a-list) base-case]))

Now the key insight, IIRC, of HtDCH is that a similar
mechanical transformation applies to OO code.

type List = Cons a List
          | Null


becomes

public abstract List {}

public Cons extends List {
       private Object element;  // car of the list
       private List rest;       // cdr of the list
}

public Null extends List {

}

and to implement our function something:

public Cons extends List {
       public Object something() {
          return  ... elt ... rest.something();
       }
}

public Null extends List {
       public Object something() {
          return baseCase;
       }
}


Note how the function is split across multiple classes in OO style.

Now if we take our friend the universal iterator, aka fold

(define (fold fn seed list)
  (cond [(cons? list) (fn (car list) (fold fn seed (cdr list)))]
        [(null? list) seed]))

You can, I hope, see how we can derive it from the recipe.
Now perhaps you can see how to write fold in OO style.

What about the issue of TCO?  The Dan Friedman paper
referenced earlier shows how to mechanically translate a
program to trampolined style, maintaining TCO in Java.
However this transformation is global in nature, and so
requires we break abstraction boundaries.

Hope that helps,
Noel

 
Email: noelwelsh  yahoo  com   noel  untyped  com
AIM: noelhwelsh
Blogs: http://monospaced.blogspot.com/  http://www.untyped.com/untyping/

----- Original Message ----
From: wooks <wookiz at hotmail.com>
To: plt-scheme at list.cs.brown.edu
Sent: Thursday, January 11, 2007 4:13:26 AM
Subject: [plt-scheme] Re: Tail recursion and the Visitor Pattern

...

So even if I could figure out how to use an accumulator/replace the
embedded (indirect recursion) with  tail recursive (not sure how or
which) , lack of TCO means I would still get a stack overflow, right?

_________________________________________________
  For list-related administrative tasks:
  http://list.cs.brown.edu/mailman/listinfo/plt-scheme





 
____________________________________________________________________________________
Want to start your own business?
Learn how on Yahoo! Small Business.
http://smallbusiness.yahoo.com/r-index