[Caml-list] Mutual recursion propagates individual recursion. Why?

[Caml-list] Mutual recursion propagates individual recursion. Why?

[Jordan W]

(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

Re: [Caml-list] Mutual recursion propagates individual recursion. Why?

[Gabriel Scherer]

[-- Attachment #1: Type: text/plain, Size: 3593 bytes --]

  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 <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.
>
>     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
>

[-- Attachment #2: Type: text/html, Size: 4656 bytes --]

Re: [Caml-list] Mutual recursion propagates individual recursion. Why?

[Ben Millwood]

[-- Attachment #1: Type: text/plain, Size: 3917 bytes --]

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 <gabriel.scherer@gmail.com> 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 <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.
>>
>>     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
>>
>
>

[-- Attachment #2: Type: text/html, Size: 5186 bytes --]

Re: [Caml-list] Mutual recursion propagates individual recursion. Why?

[Jordan W]

>> 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

I would have never considered that case, but now that you point it
out, it absolutely makes sense. I can't think of many use cases for
let/and (with no rec) beyond metaprogramming, but I do agree that the
language wouldn't feel complete without it so I'm glad remains.

let rec .. in let rec ... in E
  Several self-recursive, non-mutually recursive bindings, dependent
environments.
let rec ... and ... in E
   Several self-recursive, and mutually recursive bindings,
"simultaneously polluted" environments.
let ... and ... in E
  Several non-self-recursive, non-mutually recursive bindings with
"simultaneously isolated" environments.
let .. in let ... in E
  Several non-self-recursive, non-mutually recursive bindings with
dependent environments.

So is it correct to say that "and" acts in two completely different ways.
A. For "let rec", assigns multiple bindings "simultaneously" such that
each binding is in every binding's environment (including itself's).
B. For "let", assigns multiple bindings "simultaneously" such that
each binding is *not* in any other binding's environment (including
itself's).

I think two forms seems to be lacking:
1. The ability for even just one in a set of "simultaneous" bindings
who are all in each other's environments (mutually recursive), to not
be in its own environment (non-self-recursive).
2. The ability for even just one of these "simultaneous" bindings who
are not in each other's environments (non-mutually recursive), to be
in its own environment (self-recursive).

I suspect #2 would benefit metaprogramming just as well as the `let ..
and ` example. With metaprogramming, where we wish to isolate the
environments of several bindings simultaneously, how does a *single*
one of these bindings opt into self-recursiveness without forcing the
others into self-recursiveness (and thus "polluting the environment")?


For #1, here's a simplified/contrived (and nonsensical) example that
I've taken it from a real example (but altered/simplified).

    type nodeType = {decrement: int; msg: unit -> string; subNode:
nodeType option};;

    let rec sum n = 1 + (sum (n - node.decrement))
    and node = {
      msg = (fun () -> "sum:" ^ (string_of_int (sum 10)));
      decrement = 1;
      subNode = Some node;   (* Whoops - Cycle! *)
    };;


For the `subNode` field, I might have wanted to refer to some other
`node` in scope. But because `node` and `sum` needed to be mutually
recursive, there was no choice but for the `node` record value to be
self-recursive as well.

I'm not yet suggesting a solution, but just trying to articulate my
understanding of what is/isn't supported, though it would be great if
there was a way to represent each of the possible cases intuitively.
If the above explanation is correct, is there any documentation that
explains this?

On Sun, Mar 1, 2015 at 11:25 PM, Gabriel Scherer
<gabriel.scherer@gmail.com> 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 <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.
>>
>>     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
>
>

Re: [Caml-list] Mutual recursion propagates individual recursion. Why?

[Ben Millwood]

[-- Attachment #1: Type: text/plain, Size: 553 bytes --]

On 2 March 2015 at 09:18, Jordan W <jordojw@gmail.com> wrote:
>
> I suspect #2 would benefit metaprogramming just as well as the `let ..
> and ` example. With metaprogramming, where we wish to isolate the
> environments of several bindings simultaneously, how does a *single*
> one of these bindings opt into self-recursiveness without forcing the
> others into self-recursiveness (and thus "polluting the environment")?


There's always this:

let x = 4
and y = 7
and factorial = let rec f n = if n = 0 then 1 else n * f (n - 1) in f
and z = 12
in
...

[-- Attachment #2: Type: text/html, Size: 956 bytes --]