From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id E7EDA7EE48 for ; Mon, 2 Mar 2015 10:15:07 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of bmillwood@janestreet.com) identity=pra; client-ip=38.105.200.112; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="bmillwood@janestreet.com"; x-sender="bmillwood@janestreet.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of bmillwood@janestreet.com designates 38.105.200.112 as permitted sender) identity=mailfrom; client-ip=38.105.200.112; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="bmillwood@janestreet.com"; x-sender="bmillwood@janestreet.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mxout1.mail.janestreet.com) identity=helo; client-ip=38.105.200.112; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="bmillwood@janestreet.com"; x-sender="postmaster@mxout1.mail.janestreet.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0CeAQCvKfRUnHDIaSZag1RegwauSY1ygXSFcAKBGgdNAQEBAQEBEAEBAQEBBhYJQoQPAQEBAwESEQQZAQEsCwEECwsLDQ0dAgIhARIBBQEKEgYTCAoQh3kDCQgDCq9OPjGKPnCEYgEFjnADCoUzAQEBAQEBBAEBAQEBAQEBAQEBEQYKiwiCRIImBAeCaIFDhGwKjmeDbDOBSIEaESiLfIJNgXQSI4EVgiUcgVBvgkMBAQE X-IPAS-Result: A0CeAQCvKfRUnHDIaSZag1RegwauSY1ygXSFcAKBGgdNAQEBAQEBEAEBAQEBBhYJQoQPAQEBAwESEQQZAQEsCwEECwsLDQ0dAgIhARIBBQEKEgYTCAoQh3kDCQgDCq9OPjGKPnCEYgEFjnADCoUzAQEBAQEBBAEBAQEBAQEBAQEBEQYKiwiCRIImBAeCaIFDhGwKjmeDbDOBSIEaESiLfIJNgXQSI4EVgiUcgVBvgkMBAQE X-IronPort-AV: E=Sophos;i="5.09,674,1418079600"; d="scan'208";a="101757291" Received: from mxout1.mail.janestreet.com ([38.105.200.112]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 02 Mar 2015 10:14:48 +0100 Received: from tot-qpr-mailcore1.delacy.com ([172.27.56.68] helo=tot-qpr-mailcore1) by mxout1.mail.janestreet.com with smtp (Exim 4.82) (envelope-from ) id 1YSMR2-0001HG-Al for caml-list@inria.fr; Mon, 02 Mar 2015 04:14:44 -0500 X-JS-Flow: external Received: by tot-qpr-mailcore1 with JS-mailcore (0.1) (envelope-from ) id BU9CoE-AAAAnn-J6; 2015-03-02 04:14:44.317905-05:00 Received: from mail-qa0-f54.google.com ([209.85.216.54]) by mxgoog1.mail.janestreet.com with esmtps (UNKNOWN:AES128-GCM-SHA256:128) (Exim 4.72) (envelope-from ) id 1YSMR2-0005nM-5d for caml-list@inria.fr; Mon, 02 Mar 2015 04:14:44 -0500 Received: by mail-qa0-f54.google.com with SMTP id x12so21809433qac.13 for ; Mon, 02 Mar 2015 01:14:43 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=janestreet.com; s=google; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=C/Rzuwm8piMnPlBDdkXZ7PCVP8mEC5mam/mLTJbgWcc=; b=F60+mCHwxnrM20KhPlbYh3mvwNZy1Gp2YLxdnKYvpZwVzrh3wA+9QM8dqbaDA99Mvh ZkQwXCCFYF+LYFhlwAtvR1MOxOENrz5aLv2piSumNEpHBaFSxJF24Jtvvxq0rUFhRC05 wLpj3wtKBbfGR9tP1XDi19Qe5KJedaw0gXH1U= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=C/Rzuwm8piMnPlBDdkXZ7PCVP8mEC5mam/mLTJbgWcc=; b=jJylMvUSTjfOlH0YnFsIr17ZmID6JKMOsGa1UVXsp1rmsqsxc2odnoQeXlKg39Qfbx Hsp0ZoxxwHHcD8Jo4N+e8OPA81s95fIXpGYGjx4Cm0raZNfVUzc+OAgv7GoFiODeehBB xVDANgaBwy5Txz0gcEVbbA3EUVPZo6PBmk2DIhT+AsiPP/tuCZOUvI3RxgG4uy3jt/Yr X6j/l05nCN6H0TUMd/wpM4Rc3zzboPOiDlsnp9zTHBArTydiSSDwxksk5EvtIA+OpLw0 BOsmdBUBxnPC64IHCEm1Qup4ehMzziFWIBi8cwwlqtYHTUdoMJ3EfoLqmOMdTQEs0bqT CBTQ== X-Gm-Message-State: ALoCoQlPsT5bJh376IaP02AF1z6GHXg9ekMt4VoJc5rk2LMzCcAHHPOQWflbAx4ltcgzhcMz1ZL3nPsknaXJ3q3fPqNnHJneOa00QVq1+CRrSkD25Agpf1WZGmnSAy9FoIpuibQVZZXi X-Received: by 10.140.216.139 with SMTP id m133mr40479739qhb.6.1425287683957; Mon, 02 Mar 2015 01:14:43 -0800 (PST) MIME-Version: 1.0 X-Received: by 10.140.216.139 with SMTP id m133mr40479729qhb.6.1425287683793; Mon, 02 Mar 2015 01:14:43 -0800 (PST) Received: by 10.96.81.100 with HTTP; Mon, 2 Mar 2015 01:14:43 -0800 (PST) In-Reply-To: References: Date: Mon, 2 Mar 2015 09:14:43 +0000 Message-ID: From:Ben Millwood To:Gabriel Scherer Cc:Jordan W , "caml-list@inria.fr" Content-Type: multipart/alternative; boundary=001a113598fc18bc5c05104aa66b X-JS-Processed-by: mailcore Subject: Re: [Caml-list] Mutual recursion propagates individual recursion. Why? --001a113598fc18bc5c05104aa66b Content-Type: text/plain; charset=UTF-8 As an illustrative example of the use of non-recursive and: [let x = y and y = x in ...] swaps the values of x and y. On 2 March 2015 at 07:25, Gabriel Scherer wrote: > let x1 = e1 and x2 = e2 and ... and xn = en in body > > Has the effect that the x1,x2,..,xn are bound "simultaneously" in body, > and not before. Unlike what "let x1 = e1 in let x2 = e2 in ..." does, x1 is > not visible in e2, etc. This is rarely useful when programming, but > extremely useful when meta-programming, as it allows you to evaluate > several different pieces of code in the same scope independently, without > risk of variable shadowing. > > For the record I don't find your feature suggestion particularly tempting. > Mutual recursion is more expressive than single-recursion, and I'm not sure > what would be the point of allowing the former and restricting the latter > -- the horse is already out of the barn. Instead of > > let rec fac = function > | 0 -> 1 > | n -> n * fac (n - 1) > > I can write > > let rec fac = function > | 0 -> 1 > | n -> n * f (n - 1) > and f n = fac n > > turning any self-recursion into mutual-recursion. > > I'm not sure I understand your point about accidental value recursion. Do > you have an example? > > Note that it is possible to use recursive modules as a way to have > recursion between phrases (structure items) without explicitly using "rec". > It's a bad idea in most situations, because using recursive modules makes > you rely on more complex (and accordinly more fragile) features of the > language. > > On Mon, Mar 2, 2015 at 7:25 AM, Jordan W wrote: > >> (Note: When trying any of these examples, make sure to kill/restart >> your top level between each examples - non-recursive bindings that >> should fail will appear to work because they use existing bindings in >> the environment). >> >> My understanding is that self-recursion in OCaml is introduced via the >> `let rec` binding keyword pair. >> >> let rec x a = x a >> >> >> A sequence of let bindings are made *both* mutually recursive, *and* >> individually self-recursive via a combination of `let rec` and the >> `and` keyword. >> >> (* Notice how y is made self recursive as well *) >> let rec x a = (x a + y a) and y a = (x a + y a);; >> >> The `and` keyword by itself is not sufficient to introduce mutual >> recursion, and not sufficient to introduce self-recursion for any of >> the bindings joined by the `and`. >> >> (* Does not work *) >> let x a = x a and y a = (x a + y a) >> (* Does not work *) >> let x a = y a and y a = x a >> >> >> My questions are: >> 1. Is there any effect to having the `and` keyword, without a `let >> rec` that initiates the let binding sequence? >> 2. Is there any way to introduce mutual recursion without also >> introducing self-recursion on *all* of the bindings? >> >> I would like self-recursion to be independent from mutual recursion. >> It would be nice to be able to create several mutually recursive >> bindings that are not individually self-recursive. I imagine the >> syntax to accomplish this would require each binding to be opened with >> "let" or "let rec" which would be totally reasonable. >> >> (* Three mutually recursive functions that are not self-recursive *) >> let rec thisOneIsSelfRecursive x = ... and >> let thisOneIsNotSelfRecursive y = ... and >> let rec thisOneIsAlsoSelfRecursive z = ...; >> >> This becomes more desirable when one of the mutually recursive >> bindings is a non-function value that you did not want to make >> self-recursive by accident (which causes cycles). >> >> Jordan >> >> -- >> Caml-list mailing list. Subscription management and archives: >> https://sympa.inria.fr/sympa/arc/caml-list >> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners >> Bug reports: http://caml.inria.fr/bin/caml-bugs >> > > --001a113598fc18bc5c05104aa66b Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
As an illustrative example of the use of non-recursive and= : [let x =3D y and y =3D x in ...] swaps the values of x and y.

On 2 March 2015 at 07:2= 5, Gabriel Scherer <gabriel.scherer@gmail.com> wrote= :
=C2=A0 let x= 1 =3D e1 and x2 =3D e2 and ... and xn =3D en in body

Has the e= ffect that the x1,x2,..,xn are bound "simultaneously" in body, an= d not before. Unlike what "let x1 =3D e1 in let x2 =3D e2 in ..."= does, x1 is not visible in e2, etc. This is rarely useful when programming= , but extremely useful when meta-programming, as it allows you to evaluate = several different pieces of code in the same scope independently, without r= isk of variable shadowing.

For the record I don't fin= d your feature suggestion particularly tempting. Mutual recursion is more e= xpressive than single-recursion, and I'm not sure what would be the poi= nt of allowing the former and restricting the latter -- the horse is alread= y out of the barn. Instead of

=C2=A0 let rec fac =3D func= tion
=C2=A0=C2=A0=C2=A0 | 0 -> 1
=C2=A0=C2=A0=C2=A0 | n= -> n * fac (n - 1)

I can write

=C2= =A0 let rec fac =3D function
=C2=A0=C2=A0=C2=A0 | 0 -> 1
=C2=A0=C2=A0=C2=A0 | n -> n * f (n - 1)
=C2=A0 and f n = =3D fac n

turning any self-recursion into mutual-recursio= n.

I'm not sure I understand your point about acciden= tal value recursion. Do you have an example?

Note that it= is possible to use recursive modules as a way to have recursion between ph= rases (structure items) without explicitly using "rec". It's = a bad idea in most situations, because using recursive modules makes you re= ly on more complex (and accordinly more fragile) features of the language.<= br>

On Mon, Mar 2, 2015 at 7:25 AM, Jorda= n W <jordojw@gmail.com> wrote:
(Note: When trying any of these examples, make sure to kill/restart
your top level between each examples - non-recursive bindings that
should fail will appear to work because they use existing bindings in
the environment).

My understanding is that self-recursion in OCaml is introduced via the
`let rec` binding keyword pair.

=C2=A0 =C2=A0 let rec x a =3D x a


A sequence of let bindings are made *both* mutually recursive, *and*
individually self-recursive via a combination of `let rec` and the
`and` keyword.

=C2=A0 =C2=A0(* Notice how y is made self recursive as well *)
=C2=A0 =C2=A0let rec x a =3D (x a + y a) and y a =3D (x a + y a);;

The `and` keyword by itself is not sufficient to introduce mutual
recursion, and not sufficient to introduce self-recursion for any of
the bindings joined by the `and`.

=C2=A0 =C2=A0 (* Does not work *)
=C2=A0 =C2=A0 let x a =3D x a and y a =3D (x a + y a)
=C2=A0 =C2=A0 (* Does not work *)
=C2=A0 =C2=A0 let x a =3D y a and y a =3D x a


My questions are:
1. Is there any effect to having the `and` keyword, without a `let
rec` that initiates the let binding sequence?
2. Is there any way to introduce mutual recursion without also
introducing self-recursion on *all* of the bindings?

I would like self-recursion to be independent from mutual recursion.
It would be nice to be able to create several mutually recursive
bindings that are not individually self-recursive. I imagine the
syntax to accomplish this would require each binding to be opened with
"let" or "let rec" which would be totally reasonable.
=C2=A0 =C2=A0 (* Three mutually recursive functions that are not self-recur= sive *)
=C2=A0 =C2=A0 let rec thisOneIsSelfRecursive x =3D ... and
=C2=A0 =C2=A0 let thisOneIsNotSelfRecursive y =3D ... and
=C2=A0 =C2=A0 let rec thisOneIsAlsoSelfRecursive z =3D ...;

This becomes more desirable when one of the mutually recursive
bindings is a non-function value that you did not want to make
self-recursive by accident (which causes cycles).

Jordan

--
Caml-list mailing list.=C2=A0 Subscription management and archives:
ht= tps://sympa.inria.fr/sympa/arc/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs


--001a113598fc18bc5c05104aa66b--