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

Saptarshi Guha
 Guillaume Yziquel
 Gerd Stolpmann
 Jon Harrop
 Stefan Monnier
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20100209 (21:54) 
From:  Gerd Stolpmann <gerd@g...> 
Subject:  Re: [Camllist] The need to specify 'rec' in a recursive function defintion 
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 nonrecursive function. The "rec" is just the syntactical expression of this differentiation. Keep in mind that let f arg = expr is just a shorthand 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 Ycombinator. It gets quite complicated here from a theoretical point of view because the Ycombinator 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 shorthand 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 > > _______________________________________________ > Camllist mailing list. Subscription management: > http://yquem.inria.fr/cgibin/mailman/listinfo/camllist > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/camlbugs >   Gerd Stolpmann, Bad Nauheimer Str.3, 64289 Darmstadt,Germany gerd@gerdstolpmann.de http://www.gerdstolpmann.de Phone: +496151153855 Fax: +496151997714 