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

[Gerd Stolpmann <gerd@gerd-stolpmann.de>]

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