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

[Jon Harrop <jon@ffconsultancy.com>]

On Thursday 05 April 2007 00:28, Brian Hurt wrote:
> 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.

The cyclic graph in an interpreter is a closure<->environment cycle, whereas a 
cyclic list involves only one structure (the list itself). However, I think 
the problems and properties are equivalent in this context.

> 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

How is Wadler's proposal related to views (active patterns) in F#?

> 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.

You can do similar things with F#. A simpler example is getting rid of the 
integer total orderings of OCaml in favour of a more sane sum type:

  let (|Less|Equal|Greater|) c =
    if c<0 then Less else
      if c=0 then Equal else Greater

> As you might guess from the above example, at this point you don't need to
> define lists as a built-in data structure.

Is that not already true because pattern matching over variant type 
constructors provides everything you need?

> 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 ...

Provided it compiles to:

  let rec a = Cons(1, Cons(2, a))

you're ok.

> Ocaml handles this construct because it knows about lists.  But it doesn't
> know about this t data structure.

OCaml can already do that with user-defined data structures.

> 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.

Yes.

> 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?

Can you define more precisely what you mean by "self-referential data 
structures" because that either seems to cover arbitrarily little or too many 
useful data structures.

But I think these are orthogonal concepts. OCaml already forbids:

  let rec a = cons 1 (cons 2 a)

because you can only use constructors in that context.

> Not that recursive and mutually recursive functions would 
> still allowed, those are downright necessary.  I'm only thinking
> self-referential data structures.

But data structures can contain closures and closures contain environments 
than can refer back to the data structure.

> 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.

I have a patch for the compiler that ensures sensicalness of programs. ;-)

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists