The need to specify 'rec' in a recursive function defintion

The need to specify 'rec' in a recursive function defintion

[Saptarshi Guha]

Hello,
 I was wondering why recursive functions need to be specified with
"rec". According to Practical Ocaml, to "inform the compiler that the function
exists". But when entering the function definition, can't the compiler note that
the function is being defined so that when it sees the function calling itself,
it wont say "Unbound value f"?

How is the knowledge of a function being rec taken advantage of (in
ocaml) as opposed to other languages
(leaving aside tail call optimization).

Wouldn't one of way of detecting a recursive function would be to see
if the indeed the function calls itself?

These are very much beginners' questions.
Thank you
Saptarshi

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[Guillaume Yziquel]

Saptarshi Guha a écrit :
> Hello,
>  I was wondering why recursive functions need to be specified with
> "rec". According to Practical Ocaml, to "inform the compiler that the function
> exists". But when entering the function definition, can't the compiler note that
> the function is being defined so that when it sees the function calling itself,
> it wont say "Unbound value f"?

Essentially, the fact that "rec" means anything is mostly due to the 
fact that you want to be able to redefine stuff.

> let f = fun x -> x + 1
> 
> let f x = f (f x)

is valid in ocaml, and you're function f is the function that adds 2.

whereas

> let rec f x = f (f x)

has a completely different meaning.

If you avoided the use of rec, saying "if unbound, assume rec", then the 
line

let f x = f (f x)

has two entirely different meaning, depending on whether f is defined 
before or not.

That would be quite a chaotic feature.

> Wouldn't one of way of detecting a recursive function would be to see
> if the indeed the function calls itself?

No. Because you never know if you intended to call the function 
recursively, or if you intended to call an homonymous function you 
defined before.

All the best,

-- 
      Guillaume Yziquel
http://yziquel.homelinux.org/

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[Saptarshi Guha]

Thanks, very helpful.

>> let f = fun x -> x + 1   (1)
>>
>> let f x = f (f x)  (2)

This works in ocaml because, it replaces f (in (2) ) from that of (1).
Which is why i need f previously defined.
Correct me if i'm wrong.


>
>> Wouldn't one of way of detecting a recursive function would be to see
>> if the indeed the function calls itself?
>
> No. Because you never know if you intended to call the function recursively,
> or if you intended to call an homonymous function you defined before.
>

Very true, hadn't considered this.


> All the best,
>
> --
>     Guillaume Yziquel
> http://yziquel.homelinux.org/
>

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[Gerd Stolpmann]

Am Dienstag, den 09.02.2010, 15:50 -0500 schrieb Saptarshi Guha:
> Hello,
>  I was wondering why recursive functions need to be specified with
> "rec". According to Practical Ocaml, to "inform the compiler that the function
> exists". But when entering the function definition, can't the compiler note that
> the function is being defined so that when it sees the function calling itself,
> it wont say "Unbound value f"?
> 
> How is the knowledge of a function being rec taken advantage of (in
> ocaml) as opposed to other languages
> (leaving aside tail call optimization).
> 
> Wouldn't one of way of detecting a recursive function would be to see
> if the indeed the function calls itself?

Sure, but that's a purely syntactical point of view.

In the ML community it is consensus that a recursive function is a total
different thing than a non-recursive function. The "rec" is just the
syntactical expression of this differentiation. Keep in mind that

let f arg = expr

is just a short-hand notation for

let f = (fun arg -> expr)

or, in other words, the anonymous function constructor (fun arg -> expr)
is the basic building block to which the "let" construction is broken
down. The anonymous function has a direct counterpart in the lambda
calculus, i.e. this is the level of mathematical groundwork.

You cannot directly express recursion in an anonymous function. For
defining the operational meaning of a recursive function a special
helper is needed, the Y-combinator. It gets quite complicated here from
a theoretical point of view because the Y-combinator is not typable. But
generally, the idea is to have a combinator y that can be applied to a
function like
   y (fun f arg -> expr) arg
and that "runs" this function recursively, where "f" is the recursion.

"let rec" is considered to be just a short-hand notation for using y.

Besides the different way of defining "let" and "let rec" there are also
differences in typing.

Gerd

> These are very much beginners' questions.
> Thank you
> Saptarshi
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 
-- 
------------------------------------------------------------
Gerd Stolpmann, Bad Nauheimer Str.3, 64289 Darmstadt,Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Phone: +49-6151-153855                  Fax: +49-6151-997714
------------------------------------------------------------

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[Guillaume Yziquel]

Gerd Stolpmann a écrit :
> Am Dienstag, den 09.02.2010, 15:50 -0500 schrieb Saptarshi Guha:
> 
> Besides the different way of defining "let" and "let rec" there are also
> differences in typing.

Which ones?

> Gerd

-- 
      Guillaume Yziquel
http://yziquel.homelinux.org/

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[Gerd Stolpmann]

Am Dienstag, den 09.02.2010, 22:58 +0100 schrieb Guillaume Yziquel:
> Gerd Stolpmann a écrit :
> > Am Dienstag, den 09.02.2010, 15:50 -0500 schrieb Saptarshi Guha:
> > 
> > Besides the different way of defining "let" and "let rec" there are also
> > differences in typing.

Well, at least you can have new effects. Look for "polymorphic
recursion".

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann, Bad Nauheimer Str.3, 64289 Darmstadt,Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Phone: +49-6151-153855                  Fax: +49-6151-997714
------------------------------------------------------------

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[Guillaume Yziquel]

Gerd Stolpmann a écrit :
> Am Dienstag, den 09.02.2010, 22:58 +0100 schrieb Guillaume Yziquel:
>> Gerd Stolpmann a écrit :
>>> Am Dienstag, den 09.02.2010, 15:50 -0500 schrieb Saptarshi Guha:
>>>
>>> Besides the different way of defining "let" and "let rec" there are also
>>> differences in typing.
> 
> Well, at least you can have new effects. Look for "polymorphic
> recursion".

You mean something like this?

http://alaska-kamtchatka.blogspot.com/2009/05/polymorphic-recursion.html

With the following code

> type length = { length : 'a . int -> 'a vec -> int }
> 
> let length v =
>   let rec f = { length = fun n l -> match l with
>     Nil         -> n
>   | Zero    ps  -> f.length (    2 * n) ps
>   | One (_, ps) -> f.length (1 + 2 * n) ps
>   } in f.length 0 v

you get to use a function, here f.length, in two different contexts for 
type inference, allowing it to be used with multiple types? 'a * 'a 
instead of 'a? Am I getting this post right?

But then, this seems to go into rather elaborate constructions 
(existential types with OCaml records), which are quite remote from the 
simple 'let rec' issue we were talking about.

Is it possible to have polymorphic recursion with vanilla 'let rec' 
invocations? Or am I getting you wrong?

All the best,

-- 
      Guillaume Yziquel
http://yziquel.homelinux.org/

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[Alain Frisch]

On 2/10/2010 1:07 AM, Guillaume Yziquel wrote:
> Is it possible to have polymorphic recursion with vanilla 'let rec'
> invocations?

This is something that Jacques recently merged in the current 
development branch. The code below should work with OCaml 3.12.

let length v =
   let rec f : 'a. int -> 'a vec -> int = fun n l -> match l with
      Nil -> n
    | Zero ps -> f (2 * n) ps
    | One (_, ps) -> f (1 + 2 * n) ps
  in
  f 0 v


-- Alain

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[Saptarshi Guha]

>
> let f arg = expr
>
> is just a short-hand notation for
>
> let f = (fun arg -> expr)
>
> or, in other words, the anonymous function constructor (fun arg -> expr)
> is the basic building block to which the "let" construction is broken
> down. The anonymous function has a direct counterpart in the lambda
> calculus, i.e. this is the level of mathematical groundwork.



>
> You cannot directly express recursion in an anonymous function. For
> defining the operational meaning of a recursive function a special
> helper is needed, the Y-combinator. It gets quite complicated here from
> a theoretical point of view because the Y-combinator is not typable. But
> generally, the idea is to have a combinator y that can be applied to a
> function like
>   y (fun f arg -> expr) arg
> and that "runs" this function recursively, where "f" is the recursion.

This makes sense. Thanks, I did read about the y-combinator and its
use in recursion in Friedman and Wand. I'll read it again.


Thanks for the help
Saptarshi

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[Jon Harrop]

On Tuesday 09 February 2010 22:01:03 Gerd Stolpmann wrote:
> In the ML community it is consensus that a recursive function is a total
> different thing than a non-recursive function...

Note that Standard ML does this differently to CAML/OCaml.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[rossberg]

Jon Harrop:
> On Tuesday 09 February 2010 22:01:03 Gerd Stolpmann wrote:
>> In the ML community it is consensus that a recursive function is a total
>> different thing than a non-recursive function...
>
> Note that Standard ML does this differently to CAML/OCaml.

Not quite -- SML simply defines "fun f x = ..." to be an abbreviation for
"val rec f = fn x => ...".

/Andreas

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[Andrej Bauer]

On Tue, Feb 9, 2010 at 11:01 PM, Gerd Stolpmann <gerd@gerd-stolpmann.de> wrote:
> For defining the operational meaning of a recursive function a special
> helper is needed, the Y-combinator. It gets quite complicated here from
> a theoretical point of view because the Y-combinator is not typable. But
> generally, the idea is to have a combinator y that can be applied to a
> function like
>   y (fun f arg -> expr) arg
> and that "runs" this function recursively, where "f" is the recursion.

A small correction: y is typeable. It's a fixed-point operator, so it's type is

('a -> 'a) -> 'a

or if we only care about recursive functions it is:

# let rec y f x = f (y f) x ;;
val y : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>

(Yes, I know I used "let rec", it doesn't matter for checking that y
has a type). Let's check that it works:

# let fac = y (fun f n -> if n = 0 then 1 else n * f (n - 1)) ;;
val fac : int -> int = <fun>

# fac 7 ;;
- : int = 5040

What Gerd probably meant was that the usual untyped lambda-calculus
definition of y, which gets us recursion out of nothing isn't typeable
because self-application requires unrestricted recursive types. But
again, it's an intermediate definition that is not typeable, not y
itself (here adapted so that it works for functions in an eager
language):

$ ocaml -rectypes
        Objective Caml version 3.11.1

# let z = fun u v w -> v (u u v) w ;;
val z : ('a -> ('b -> 'c -> 'd) -> 'b as 'a) -> ('b -> 'c -> 'd) -> 'c
-> 'd = <fun>

# let y = z z ;;
val y : (('_a -> '_b) -> '_a -> '_b) -> '_a -> '_b = <fun>

Observe that y has a non-recursive type, it's the auxiliary z that
requires a recursive one. And this y also works:

# let fac = y (fun f n -> if n = 0 then 1 else n * f (n - 1)) ;;
val fac : int -> int = <fun>

# fac 7 ;;
- : int = 5040

Can anyone get rid of the pesky underscores in the type of y above, so
that it becomes truly polymorphic?

With kind regards,

Andrej

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[Francois Maurel]

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

>
>
> # let y = z z ;;
> val y : (('_a -> '_b) -> '_a -> '_b) -> '_a -> '_b = <fun>
>
> Can anyone get rid of the pesky underscores in the type of y above, so
> that it becomes truly polymorphic?
>

Eta expansion does it...

# let y x = z z x;;
val y : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>

Regards,
François

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

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[rossberg]

"Andrej Bauer" <andrej.bauer@andrej.com> wrote:
>
> What Gerd probably meant was that the usual untyped lambda-calculus
> definition of y, which gets us recursion out of nothing isn't typeable
> because self-application requires unrestricted recursive types.

Fortunately, even that is not quite correct: Y is perfectly typable in
plain ML, you just need to introduce the recursive type it employs
explicitly:

type 'a fix = Fix of ('a fix -> 'a)
let fix f = let z = fun (Fix g' as g) x -> f (g' g) x in z (Fix z)

Now, for example:

let fac = fix (fun fac n -> if n = 0 then 1 else n * fac (n-1))
let n = fac 7

Best,
/Andreas

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[Jon Harrop]

On Tuesday 09 February 2010 20:50:33 Saptarshi Guha wrote:
> Hello,
>  I was wondering why recursive functions need to be specified with
> "rec". According to Practical Ocaml, to "inform the compiler that the
> function exists". But when entering the function definition, can't the
> compiler note that the function is being defined so that when it sees the
> function calling itself, it wont say "Unbound value f"?
>
> How is the knowledge of a function being rec taken advantage of (in
> ocaml) as opposed to other languages
> (leaving aside tail call optimization).
>
> Wouldn't one of way of detecting a recursive function would be to see
> if the indeed the function calls itself?

  let f x = x + 1
  let f x = 2 * f x

Is the latter "f" recursive or not?

See my answer to the same question on stack overflow:

http://stackoverflow.com/questions/900585/why-are-functions-in-ocaml-f-not-recursive-by-default/1891573

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[Saptarshi Guha]

Yes, I see  that f isn't recursive, because it simplifies down to
2*(x+1) but for a reader(at least myself)  it can be bit tricky to
consume. My experience of reading the /definition/ of a function which
includes a call
to itself is that it is recursive. On the stackoverflow post, you
mentioned that the British ML branch forces different names (since
recursion is by default), and though it does pollute the namespace,
personally I find it easier to read.

Regards
Saptarshi


>> Wouldn't one of way of detecting a recursive function would be to see
>> if the indeed the function calls itself?
>
>  let f x = x + 1
>  let f x = 2 * f x
>
> Is the latter "f" recursive or not?
>
> See my answer to the same question on stack overflow:
>
> http://stackoverflow.com/questions/900585/why-are-functions-in-ocaml-f-not-recursive-by-default/1891573
>
> --
> Dr Jon Harrop, Flying Frog Consultancy Ltd.
> http://www.ffconsultancy.com/?e
>

Re: [Caml-list] The need to specify 'rec' in a recursive function defintion

[Jon Harrop]

On Tuesday 09 February 2010 22:31:49 Saptarshi Guha wrote:
> Yes, I see  that f isn't recursive, because it simplifies down to
> 2*(x+1) but for a reader(at least myself) it can be bit tricky to
> consume.

But for a writer it can be useful to produce. For example, imagine a function 
in an interpreter that evaluates an expression to a value in the context of a 
set of variable bindings:

  let rec eval vars = function
    ...
    | Add(f, g) -> eval vars f + eval vars g
    | Mul(f, g) -> eval vars f * eval vars g
    ...

Such functions make a *lot* of recursive calls.

Now imagine you want to inject some code around every external call into 
that "expr" function but not recursive calls, e.g. logging exceptional 
returns. Do you want to change the name of that "expr" function not only in 
its definition but at every recursive call in its body? No.

Fortunately, in OCaml you can just append a definition to supercede "expr" 
without touching the original definition at all:

  let eval vars expr =
    ...
    let result = eval vars expr in
    ...
    result

This is a useful and common OCaml idiom.

> My experience of reading the /definition/ of a function which 
> includes a call to itself is that it is recursive.

Definitions are often superceded in ML.

> On the stackoverflow post, you mentioned that the British ML branch forces
> different names (since recursion is by default), and though it does pollute
> the namespace, personally I find it easier to read.

You can do that in OCaml as well, if you choose.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: The need to specify 'rec' in a recursive function defintion

[Stefan Monnier]

> Wouldn't one of way of detecting a recursive function would be to see
> if the indeed the function calls itself?

That's what Haskell does, yes.


        Stefan

Re: [Caml-list] Re: The need to specify 'rec' in a recursive function defintion

[Till Varoquaux]

On Wed, Feb 10, 2010 at 5:01 PM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
>> Wouldn't one of way of detecting a recursive function would be to see
>> if the indeed the function calls itself?
>
> That's what Haskell does, yes.
>
>

Let's make things clear here: the "rec" *really* is a feature; it is
very convenient to reuse the same identifier to express something in
the process of being built (e.g. something going through a pipeline).

For instance:

let g () =
  let f s =
    if !debug then
       Printf.printf "f is called with value: %s\n%!" s
    f s
  in
  .......

Some (including me) would even argue that it is sad that type
definitions don't use "rec".

Till
>        Stefan
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] Re: The need to specify 'rec' in a recursive function defintion

[Jon Harrop]

On Wednesday 10 February 2010 22:25:44 Till Varoquaux wrote:
> Some (including me) would even argue that it is sad that type
> definitions don't use "rec".

Agreed. Less useful than "rec" on function definitions but that would still be 
useful sometimes.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: The need to specify 'rec' in a recursive function defintion

[Stefan Monnier]

>>> Wouldn't one of way of detecting a recursive function would be to see
>>> if the indeed the function calls itself?
>> That's what Haskell does, yes.
> Let's make things clear here: the "rec" *really* is a feature;

Nobody said otherwise.  Eliminating the "rec" is also a feature.
Those two features are mostly incompatible, and many reasonable people
disagree on which one of the two is more important.


        Stefan "who extensively used that feature in SML, but happens
                to prefer the other feature nevertheless"

Re: [Caml-list] Re: The need to specify 'rec' in a recursive function defintion

[Jon Harrop]

On Monday 15 February 2010 15:46:58 Stefan Monnier wrote:
> Till Varoquaux had written:
> > Let's make things clear here: the "rec" *really* is a feature;
>
> Nobody said otherwise.  Eliminating the "rec" is also a feature.
> Those two features are mostly incompatible, and many reasonable people
> disagree on which one of the two is more important.
>
>         Stefan "who extensively used that feature in SML, but happens
>                 to prefer the other feature nevertheless"

Standard ML doesn't have the feature that Till described.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: The need to specify 'rec' in a recursive function defintion

[Stefan Monnier]

>> Till Varoquaux had written:
>> > Let's make things clear here: the "rec" *really* is a feature;
>> Nobody said otherwise.  Eliminating the "rec" is also a feature.
>> Those two features are mostly incompatible, and many reasonable people
>> disagree on which one of the two is more important.
>> Stefan "who extensively used that feature in SML, but happens
>> to prefer the other feature nevertheless"
> Standard ML doesn't have the feature that Till described.

It sure does, tho not with "fun" but only with "var" definitions.


        Stefan

Re: The need to specify 'rec' in a recursive function defintion

[Stefan Monnier]

> It sure does, tho not with "fun" but only with "var" definitions.
                                                  ^^^
                                                  val

        Stefan "blush!"

Re: [Caml-list] Re: The need to specify 'rec' in a recursive function defintion

[Ashish Agarwal]

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

It may be worth recalling the OCaml koans at
http://eigenclass.org/hiki/fp-ocaml-koans. The first one is:
let rec

One day, a disciple of another sect came to Xavier Leroy and said mockingly:

"The OCaml compiler seems very limited: why do you have to indicate when a
function is recursive, cannot the compiler infer it?"

Xavier paused for a second, and replied patiently with the following story:

"One day, a disciple of another sect came to Xavier Leroy and said
mockingly..."



On Tue, Feb 16, 2010 at 9:42 AM, Stefan Monnier <monnier@iro.umontreal.ca>wrote:

> > It sure does, tho not with "fun" but only with "var" definitions.
>                                                   ^^^
>                                                  val
>
>        Stefan "blush!"
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> 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: 2031 bytes --]