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 g...@gerd-stolpmann.de http://www.gerd-stolpmann.de Phone: +49-6151-153855 Fax: +49-6151-997714 ------------------------------------------------------------ _______________________________________________ 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
