Re: [Caml-list] How important are circular lists/recursive objects?

[Brian Hurt <bhurt@spnz.org>]

On Tue, 3 Apr 2007, Andrej Bauer wrote:

> Brian Hurt wrote:
>> Does anyone  actually use this construct, and if so, for what?
>
> When I teach my students "theory" of programming languages, we write 
> interpreters for mini languages. The recursive data structures are used to 
> create closures of recursive functions, environments that contain mutually 
> recursive values, closures of objects, etc. Life would be very hard without 
> this feature.

No.  I'm just thinking about circular lists.

It's somewhat off-topic, but here's where I'm comming from.  Imagine a 
language with variant types and Wadler-style views

For those who don't know what Wadler style views, the long intro is:
http://citeseer.ist.psu.edu/wadler86views.html

The short intro is that it's a way to tie new data structures into pattern 
matching.  You could define a new data type, and a new operator on that 
datatype, for example (in pseudo-Ocaml):
 	type 'a t = Cons of 'a * 'a t | Nil;;

 	let cons h t = Cons(h, t);;

 	let decons arg matches doesnt_match =
 		match arg with
 			| Cons(h, t) -> matches h t
 			| Nil -> doesnt_match ()
 	;;

You could then tie the cons and decons functions in with the argument, 
maybe like:

 	define ( ::. ) = cons, decons ;;

so that when the compiler saw the code:

 	match lst with
 		| h ::. t -> expr1
 		| _ -> expr2

it would compile it as:
 	decons lst (fun h t -> expr1) (fun () -> expr2)

Allowing users of your new data structure to pattern match on the data 
structure using the normal operators for that data structure.

As you might guess from the above example, at this point you don't need to 
define lists as a built-in data structure.  You have all the capabilities 
you need to implement lists as a library.  With one, minor, exception- how 
does the compiler handler expressions like:
 	let rec a = 1 ::. 2 ::. a in ...

As that code compiles like:
 	let rec a = cons 1 (cons 2 a) in ...

Ocaml handles this construct because it knows about lists.  But it doesn't 
know about this t data structure.  It could be defined in another module, 
and be an abstract type.  It could have an arbitrarily complicated 
definition.  There is no garuentee in this case that cons doesn't look at 
the argument.  In fact, it'd be perfectly reasonble for t to be an 
implementation of Okasaki's random access lists:
http://citeseer.ist.psu.edu/okasaki95purely.html
at which point the implementation of cons *would* inspect the tail 
argument.

So, the question is: if a (at this point in time entirely hypothetical) 
programming language decided to go this route, and decided to simply 
outlaw self-referential data structures such as circular lists, would this 
be a problem?  Not that recursive and mutually recursive functions would 
still allowed, those are downright necessary.  I'm only thinking 
self-referential data structures.  But the compiler needs to know the 
structure of a closure, for obvious reasons, so the compiler knowing how 
to cheat and "fill in" the closure with the right values after those 
values have been generated isn't a problem.  I've become quite fond of the 
continuation passing style of code recently.

And this probably holds for a lazy thunk as well, especially considering a 
lazy thunk contains a closure (at least initially).

I will note that in Ocaml you can do:
# let rec x = lazy (Lazy.force x);;
val x : 'a Lazy.t = <lazy>
# Lazy.force x;;
Exception: Lazy.Undefined.
#

Simply because it compiles doesn't mean it makes sense, necessarily.

But hopefully this will clarify what I'm asking.

Brian