From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id NAA25636 for caml-red; Thu, 23 Nov 2000 13:25:48 +0100 (MET) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id XAA29133 for ; Wed, 22 Nov 2000 23:41:02 +0100 (MET) Received: from smtpproxy1.mitre.org (mb-20-100.mitre.org [129.83.20.100]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id eAMMf0P22772 for ; Wed, 22 Nov 2000 23:41:01 +0100 (MET) Received: from avsrv1.mitre.org (avsrv1.mitre.org [129.83.20.58]) by smtpproxy1.mitre.org (8.9.3/8.9.3) with ESMTP id RAA25214 for ; Wed, 22 Nov 2000 17:40:54 -0500 (EST) Received: from linus.mitre.org (linus.mitre.org [129.83.10.1]) by smtpsrv1.mitre.org (8.9.3/8.9.3) with ESMTP id RAA25917; Wed, 22 Nov 2000 17:40:53 -0500 (EST) Received: from malabar.mitre.org (malabar.mitre.org [129.83.10.30]) by linus.mitre.org (8.9.3/8.9.3) with ESMTP id RAA22873; Wed, 22 Nov 2000 17:40:52 -0500 (EST) Received: (from guttman@localhost) by malabar.mitre.org (8.9.3/8.9.3) id RAA01119; Wed, 22 Nov 2000 17:40:52 -0500 X-Authentication-Warning: malabar.mitre.org: guttman set sender to guttman@mitre.org using -f To: caml-list@inria.fr Subject: let rec for non-function values Reply-To: guttman@mitre.org (Joshua D. Guttman) From: guttman@mitre.org (Joshua D. Guttman) Date: 22 Nov 2000 17:40:52 -0500 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: weis@pauillac.inria.fr I don't understand when OCaml will allow me to define non-functional values via let rec. Here's a puzzling example. It arose in the course of implementing some algorithms manipulating non-deterministic finite automata. type 'a t = Node of bool * (* Accepting state? *) ('a * 'a t) list * (* Next states for different events *) 'a t list (* Next states after tau (silent event) *) Then the following is accepted by ocaml v. 3: let star_sketch (Node(b, i_0, t_0)) = let rec n = let rec traverse_initial (e,n_1) = e, traverse n_1 and traverse = function Node (true,i,t) -> Node (true, List.map traverse_initial i, (n :: (List.map traverse t))) | Node (false,i,t) -> Node (false, List.map traverse_initial i, List.map traverse t) in Node (b, List.map traverse_initial i_0, List.map traverse t_0) in n # val star_sketch : 'a t -> 'a t = I know it's not a good definition of Kleene star, because it will loop if the argument already has cycles. But it's syntactically OK. By contrast: let rec star_sketch_2 (Node(b, i_0, t_0)) = let rec n = Node (b, List.map traverse_initial i_0, List.map traverse t_0) and traverse_initial (e,n_1) = e, traverse n_1 and traverse = function Node (true,i,t) -> Node (true, List.map traverse_initial i, (n :: (List.map traverse t))) | Node (false,i,t) -> Node (false, List.map traverse_initial i, List.map traverse t) in n is syntactically not OK: Characters 59-133: This kind of expression is not allowed as right-hand side of `let rec' And yet star_sketch_2 seems to be derived from star_sketch by a sound transformation for unnesting let recs. The manual is not terribly informative: The current implementation also supports a certain class of recursive definitions of non-functional values, such as let rec name_1 = 1 :: name_2 and name_2 = 2 :: name_1 in expr which binds name_1 to the cyclic list 1::2::1::2::..., and name_2 to the cyclic list 2::1::2::1::... Informally, the class of accepted definitions consists of those definitions where the defined names occur only inside function bodies or as argument to a data constructor. I ask this question because using let rec to define immutable cyclic data is pretty attractive, but clearly one can't write a program in that style if such small differences break things. Many variants were either accepted or rejected in patterns that I found inscrutable. Thanks -- Joshua -- Joshua D. Guttman MITRE, Mail Stop A150 202 Burlington Rd. Tel: +1 781 271 2654 Bedford, MA 01730-1420 USA Fax: +1 781 271 3816