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=AWL 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 6BFC5BC0A for ; Thu, 5 Apr 2007 02:56:15 +0200 (CEST) Received: from pih-relay05.plus.net (pih-relay05.plus.net [212.159.14.132]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l350uE1c001786 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO) for ; Thu, 5 Apr 2007 02:56:15 +0200 Received: from [80.229.56.224] (helo=beast.local) by pih-relay05.plus.net with esmtp (Exim) id 1HZGGs-00082Y-6A for caml-list@yquem.inria.fr; Thu, 05 Apr 2007 01:56:14 +0100 From: Jon Harrop Organization: Flying Frog Consultancy Ltd. To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] How important are circular lists/recursive objects? Date: Thu, 5 Apr 2007 01:51:18 +0100 User-Agent: KMail/1.9.5 References: <4611FBAB.1020508@fmf.uni-lj.si> In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200704050151.19005.jon@ffconsultancy.com> X-Miltered: at concorde with ID 4614492E.001 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 ocaml:01 constructors:01 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.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