From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 1F876BC37 for ; Tue, 9 Feb 2010 22:54:55 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AnkCAINocUvU436rkWdsb2JhbACOeYtsFQEBAQEJCwoHEwMgvXgChFIE X-IronPort-AV: E=Sophos;i="4.49,438,1262559600"; d="scan'208";a="44153175" Received: from moutng.kundenserver.de ([212.227.126.171]) by mail2-smtp-roc.national.inria.fr with ESMTP; 09 Feb 2010 22:54:54 +0100 Received: from office1.lan.sumadev.de (dslb-188-097-013-108.pools.arcor-ip.net [188.97.13.108]) by mrelayeu.kundenserver.de (node=mreu1) with ESMTP (Nemesis) id 0MZhpC-1NR9DW1Djy-00Ld50; Tue, 09 Feb 2010 22:54:52 +0100 Received: from [192.168.5.104] (dslb-188-097-013-108.pools.arcor-ip.net [188.97.13.108]) by office1.lan.sumadev.de (Postfix) with ESMTPSA id 17DBA5F702; Tue, 9 Feb 2010 22:54:52 +0100 (CET) Subject: Re: [Caml-list] The need to specify 'rec' in a recursive function defintion From: Gerd Stolpmann To: saptarshi.guha@gmail.com Cc: caml-list@yquem.inria.fr In-Reply-To: <1e7471d51002091250of7a686fq537a03c9401c868f@mail.gmail.com> References: <1e7471d51002091250of7a686fq537a03c9401c868f@mail.gmail.com> Content-Type: text/plain Date: Tue, 09 Feb 2010 23:01:03 +0100 Message-Id: <1265752863.5482.42.camel@flake.lan.gerd-stolpmann.de> Mime-Version: 1.0 X-Mailer: Evolution 2.12.1 Content-Transfer-Encoding: 7bit X-Provags-ID: V01U2FsdGVkX19AxmoEc8NYGtUsr3RZV2Hon2HN8v0vDFNcpXp oeW4DH1GReaVOYlJwCScUMdZvxqSR4aqWDt86U4veffLuM7ONN GNcBr2yx+C8fFyPJ9LMgA== X-Spam: no; 0.00; recursive:01 defintion:01 gerd:01 stolpmann:01 gerd:01 recursive:01 ocaml:01 compiler:01 compiler:01 ocaml:01 syntactical:01 syntactical:01 expr:01 notation:01 expr:01 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 ------------------------------------------------------------