Browse thread
How important are circular lists/recursive objects?
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2007-04-05 (00:56) |
From: | Jon Harrop <jon@f...> |
Subject: | Re: [Caml-list] How important are circular lists/recursive objects? |
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