Re: [Caml-list] why the "rec" in "let rec"?

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

Am Mit, 2003-05-07 um 16.57 schrieb Hal Daume III:
> Hi all,
> 
> On Wed, 7 May 2003, Neel Krishnaswami wrote:
> 
> > Garry Hodgson writes:
> > > 
> > > something i was always curious about:  why do you need to 
> > > specify the "rec" in a "let rec" function definition?  as opposed
> > > to, say, having the compiler figure out when a function is recursive?
> > 
> > It's the simplest way of dealing with the interaction of lexical scope
> > and recursion. Consider the following examples:
> 
> Both responses so far have pointed out how it's different from jsut 'let',
> but I don't think this was the point of the question.  Arguably, the
> "simplest" way to dealing with:
> 
> > let f x = ..
> > let f x = f x
> 
> is to simply disallow bindings like this.  I would think that they're
> almost always a bug.  Especially if the first definition appears at the
> top of your file and the second (perhaps you forgot the "rec" and the body
> is actually long) appears at the bottom.  Likely it would turn out to be a
> type error anyway, but why risk it?
> 
> Anyway, I think the question was more along the lines of "why let the
> programmer do something like this."  I cannot answer that.

I think the reason is that "let" is theoretically derived from the
lambda construct, e.g.

  let f x = e

does the same as the anonmyous counterpart

  (fun x -> e)

and the scoping rules for "fun" (coming from a mathematical theory) are
also applied to "let", so you have always the same scoping rules, except
when you explicitly select a different rule, as in "let rec".

That ML has a theoretical foundation makes this language different from
others. There are often theorerical reasons for things that are commonly
only seen from a practical point of view.

The foundation says that "let" and "let rec" are very different
constructs. As mentioned, "let" is another notation for "fun" which is
lambda abstraction (to be exact, this is not 100% true for Ocaml,
because different typing rules are used for "let" and "fun" with
different strengths). "let rec" has no direct counterpart in the lambda
calculus, and must be emulated with so-called combinators. As far as I
remember, typing of recursive combinators is impossible, and so the
language foundation must be "augmented" by additional theories that are
not as strong as the lambda calculus. I am not an expert for "let rec"
typechecking, but I suppose the capabilities of the compiler are limited
because there is the risk that the typechecker itself loops endlessly.

To summarize, the difference between "let" and "let rec" is that they
are based on theories with different strengths, and the language
designers don't want to unify such constructs (IMHO, a good attitude).

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
------------------------------------------------------------

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners