[Caml-list] The need to specify 'rec' in a recursive function defintion
Saptarshi Guha
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
_______________________________________________
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
Guillaume Yziquel
> 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/
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
ge...@gerd-stolpmann.de http://www.gerd-stolpmann.de
Phone: +49-6151-153855 Fax: +49-6151-997714
------------------------------------------------------------
Jon Harrop
> In the ML community it is consensus that a recursive function is a total
Note that Standard ML does this differently to CAML/OCaml.
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
Saptarshi Guha
>> 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.
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
Jon Harrop
> 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:
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
_______________________________________________
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
Saptarshi Guha
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
Jon Harrop
> 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.
Guillaume Yziquel
> 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/
_______________________________________________
Alain Frisch
> 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
Andrej Bauer
> 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
Francois Maurel
>
> # let y = z z ;;
> val y : (('_a -> '_b) -> '_a -> '_b) -> '_a -> '_b = <fun>
>
> 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
ross...@mpi-sws.org
>
> 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
ross...@mpi-sws.org
> 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
Stefan Monnier
> if the indeed the function calls itself?
That's what Haskell does, yes.
Stefan
Till Varoquaux
<mon...@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
Jon Harrop
> 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
_______________________________________________
ol...@okmij.org
Fortunately OCaml is (much more) than simply-typed lambda
calculus. Almost any feature of OCaml -- recursive data types,
recursive types, reference cells, mutable records, exceptions,
objects, recursive modules and polymorphic variants -- can be used to
express the fixpoint combinator. Sometimes there is more than one way
to use the same feature to express the fixpoint combinator. The more
and less known ways of expressing fix are collected in the following
document:
http://okmij.org/ftp/ML/fixpoints.ml
Jon Harrop
> Till Varoquaux had written:
> > Let's make things clear here: the "rec" *really* is 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
_______________________________________________
Stefan Monnier
^^^
val
Stefan "blush!"
Ashish Agarwal
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..."