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 mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id A7DA57FCA8 for ; Mon, 2 Mar 2015 08:26:27 +0100 (CET) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of gabriel.scherer@gmail.com) identity=pra; client-ip=209.85.223.179; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of gabriel.scherer@gmail.com designates 209.85.223.179 as permitted sender) identity=mailfrom; client-ip=209.85.223.179; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-ie0-f179.google.com) identity=helo; client-ip=209.85.223.179; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="postmaster@mail-ie0-f179.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0C8AQDfD/RUlLPfVdFag1RegwauSY1ygXSFcAKBGQdNAQEBAQEBEAEBAQEHCwsJEjCEEAEBBBIRBBkBGxILAQMMBgULGh0CAiEBAREBBQEKEgYTEhCHeAEDEQ2vTD4xiy6Ba4J3jigKGScDClSEXwEBAQEBBQEBAQEBAQEBFAEFDosEgkSCJgQHgmiBQwWEZwqOZ4NsM4FIgRoRKIt8gk2BdBIjgQwJgiUcgVE9MYJDAQEB X-IPAS-Result: A0C8AQDfD/RUlLPfVdFag1RegwauSY1ygXSFcAKBGQdNAQEBAQEBEAEBAQEHCwsJEjCEEAEBBBIRBBkBGxILAQMMBgULGh0CAiEBAREBBQEKEgYTEhCHeAEDEQ2vTD4xiy6Ba4J3jigKGScDClSEXwEBAQEBBQEBAQEBAQEBFAEFDosEgkSCJgQHgmiBQwWEZwqOZ4NsM4FIgRoRKIt8gk2BdBIjgQwJgiUcgVE9MYJDAQEB X-IronPort-AV: E=Sophos;i="5.09,674,1418079600"; d="scan'208";a="123911507" Received: from mail-ie0-f179.google.com ([209.85.223.179]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 02 Mar 2015 08:26:26 +0100 Received: by iecrl12 with SMTP id rl12so45582392iec.2 for ; Sun, 01 Mar 2015 23:26:25 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=Vx2Mnrytzmf4YepCHS4vn1fMOftX6ZKqZfWG2pulpYI=; b=Sj1OiWALnQBzCkvTOFoC2jK1buWZvd89zZ2zuk2xPi3pRc2iieMjeg79b/BfOlJ04t JZK4gqFohVJWiDHTCPSIA+wZS1HlssoSPgNjQLr2wcKnf5acxUFO+Et7/LU5QMPOu4nn Ifpbru9LZr2u0m6rwdnhpdq1xuAcQ1beAEP9JlwOrU7tWDDxP/bGQoc0mdkp/iVcjh9g pROgZ4uJOXHjbD/7+t4lcJs/wG7QoZrL92uXD/kTDlXXO7qaMqSFmIAbRGP2fgKivVmI gBZBGB+RcCzm9D35sGqXJjU+FR0IND5F9ANDJ1u99HmIIFaeQa3XT4vWtccrfIL7YVFd dhuA== X-Received: by 10.50.78.131 with SMTP id b3mr19145364igx.0.1425281185482; Sun, 01 Mar 2015 23:26:25 -0800 (PST) MIME-Version: 1.0 Received: by 10.36.13.16 with HTTP; Sun, 1 Mar 2015 23:25:45 -0800 (PST) In-Reply-To: References: From: Gabriel Scherer Date: Mon, 2 Mar 2015 08:25:45 +0100 Message-ID: To: Jordan W Cc: "caml-list@inria.fr" Content-Type: multipart/alternative; boundary=089e0111d156c40d8c05104922c8 Subject: Re: [Caml-list] Mutual recursion propagates individual recursion. Why? --089e0111d156c40d8c05104922c8 Content-Type: text/plain; charset=UTF-8 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 > --089e0111d156c40d8c05104922c8 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
=C2=A0 let x1 =3D e1 and x2 =3D e2 and ... and x= n =3D en in body

Has the effect that the x1,x2,..,xn are bound= "simultaneously" in body, and 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-pro= gramming, 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 particular= ly tempting. Mutual recursion is more expressive than single-recursion, and= I'm not sure what would be the point of allowing the former and restri= cting the latter -- the horse is already out of the barn. Instead of

=C2=A0 let rec fac =3D function
=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-recursion.

I'm not sur= e I understand your point about accidental value recursion. Do you have an = example?

Note that it is possible to use recursive module= s as a way to have recursion between phrases (structure items) without expl= icitly using "rec". It's a bad idea in most situations, becau= se using recursive modules makes you rely on more complex (and accordinly m= ore fragile) features of the language.

On Mon, Mar 2, 2015 at 7:25 AM, Jordan= 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

--089e0111d156c40d8c05104922c8--