From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 952F0BC0A for ; Thu, 5 Apr 2007 01:28:32 +0200 (CEST) Received: from bsd4.nyct.net (mail-out4.nyct.net [216.139.141.4]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l34NSVam015327 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Thu, 5 Apr 2007 01:28:32 +0200 Received: from [192.168.42.2] ([216.139.135.144]) by bsd4.nyct.net (8.13.4/8.13.4) with ESMTP id l34NSNAt042615; Wed, 4 Apr 2007 19:28:25 -0400 (EDT) (envelope-from bhurt@spnz.org) Date: Wed, 4 Apr 2007 19:28:41 -0400 (EDT) From: Brian Hurt X-X-Sender: bhurt@localhost To: Andrej.Bauer@andrej.com Cc: caml-list Subject: Re: [Caml-list] How important are circular lists/recursive objects? In-Reply-To: <4611FBAB.1020508@fmf.uni-lj.si> Message-ID: References: <4611FBAB.1020508@fmf.uni-lj.si> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Miltered: at concorde with ID 4614349F.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; recursive:01 andrej:01 recursive:01 comming:01 wadler:01 citeseer:01 wadler:01 datatype:01 decons:01 decons:01 compiler:01 expr:01 expr:01 compiler:01 ocaml:01 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.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