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

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

[Garry Hodgson]

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?

is it a compiler/grammar optimization?  or to help the user, forcing them
to be precise with recursion?  or required by the type system?

do other ML's do it this way?

just curious.

----
Garry Hodgson, Senior Hacker, AT&T Labs

No act is more patriotic than speaking out when your government 
is doing the wrong thing in your name.  This is not your right
but your sacred duty.  And none are more treasonous than those
who would silence these voices.

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

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

[Chris Uzdavinis]

Garry Hodgson <garry@sage.att.com> 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?
> 
> is it a compiler/grammar optimization?  or to help the user, forcing
> them to be precise with recursion?  or required by the type system?

It affects the name lookup rules.  For example:

  let f x = x
  let f x = f x

The 2nd definition for function f is not an infinite loop.  It calls
the previously defined version of f, and is thus a more expensive
identity function.  However:

  let f x = x
  let rec f x = f x

Now the first function is not used by the second (which, due to the
"rec" having been added, is now an infinite loop calling itself.)

> do other ML's do it this way?

Yes.

-- 
Chris

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

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

[Neel Krishnaswami]

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:

  let f = fun x -> (Printf.printf "#"; x) in
  let f x = f x
  in
  f 5

versus

  let f = fun x -> (Printf.printf "#"; x) in
  let rec f x = f x
  in
  f 5
                
The reference to 'f' in the second function body refers to the f
already in scope. The 'rec' keyword is how you tell the compiler to
ignore that and make it a recursive binding.

So the first example prints "#" and return 5. The second loops
indefinitely.

-- 
Neel Krishnaswami
neelk@alum.mit.edu

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

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

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

 - Hal

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

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

[Falk Hueffner]

On Wed, 7 May 2003, Hal Daume III wrote:

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

It is often useful in code like this:

  let g = Graph.make 6 3 1 in
  let g = Graph.set_immutable_vertex g 0 in
  let g = Graph.set_immutable_vertex g 4 in
  let g = Graph.set_connected g 0 1 in
  let g = Graph.set_connected g 0 3 in
 ...

(Real World Example! ;)

	Falk

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

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

[David Brown]

On Wed, May 07, 2003 at 07:57:13AM -0700, Hal Daume III wrote:

> > 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 hope it doesn't get disabled.  There are some very common idioms that
use this type of declaration.

  let ... =
    let a = ... a ... in
    let a = ... a ... in
    let a = ... a ... in

This way, you can build up the value of a, almost like they were
assignments, but without the problems associated with mutable values.
It would be silly to have to keep thinking of new names for the variable
each time you did this.

I have also made wrappers for functions for debugging purposes, and
found it very convenient to just be able to call the old definition.

Dave Brown

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

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

[Neel Krishnaswami]

Hal Daume III writes:
> 
> 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.

Unless I misremember, Java has lexical scope, but forbids bindings
from shadowing one another. I don't know what relevance this has,
except to note that your idea has actually been implemented in a real
language. I don't think one can say whether this is helpful or not,
because the rest of Java is so much less expressive than Ocaml....

-- 
Neel Krishnaswami
neelk@alum.mit.edu

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

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

[Garry Hodgson]

thanks to all who replied (and will reply).
this list is always an education.


----
Garry Hodgson, Senior Hacker, AT&T Labs

No act is more patriotic than speaking out when your government 
is doing the wrong thing in your name.  This is not your right
but your sacred duty.  And none are more treasonous than those
who would silence these voices.

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

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

[Brian Hurt]

An example of this in action- an efficient and portable way to find the 
high bit set in an int:

let log2 x =
    if (x == 0) then -1 else
    let x, r = if (x < 0) then (x lsr 1), 1 else x, 0 in
    let x, r = if (Sys.word_size == 64) && (x > 0xFFFFFFFF) 
               then (x lsr 32), (r + 32) else x, r in
    let x, r = if x > 0xFFFF then (x lsr 16), (r + 16) else x, r in
    let x, r = if x > 0xFF then (x lsr 8), (r + 8) else x, r in
    let x, r = if x > 0xF then (x lsr 4), (r + 4) else x, r in
    let x, r = if x > 0x3 then (x lsr 2), (r + 2) else x, r in
    let r = if x > 1 then (r + 1) else r in
    r

Brian

On Wed, 7 May 2003, David Brown wrote:

> On Wed, May 07, 2003 at 07:57:13AM -0700, Hal Daume III wrote:
> 
> > > 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 hope it doesn't get disabled.  There are some very common idioms that
> use this type of declaration.
> 
>   let ... =
>     let a = ... a ... in
>     let a = ... a ... in
>     let a = ... a ... in
> 
> This way, you can build up the value of a, almost like they were
> assignments, but without the problems associated with mutable values.
> It would be silly to have to keep thinking of new names for the variable
> each time you did this.
> 
> I have also made wrappers for functions for debugging purposes, and
> found it very convenient to just be able to call the old definition.
> 
> Dave Brown
> 
> -------------------
> 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
> 

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

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

[Gerd Stolpmann]

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

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

[Pierre Weis]

[...]
> 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
> ------------------------------------------------------------

An important additional advantage of identifier rebinding
is to avoid confusion between the new and old value: the rebinding makes
it explicit that the old value is now irrelevant and the language
scoping rules will then ensure this property.

For example, consider the following (pseudo)-code snippet where we
carefully avoid rebinding of i, using a new name j instead:

 ... i ...
 let j = i + 1 in
 ... j ...         (* 3 *)

In these circumstances, the programmer can confuse i and j, using i
instead of j in part (* 3 *). Since, unfortunately, i and j have the
same type, the compiler can not detect this error. By contrast,
rebinding i elegantly avoids this problem:

 ... i ...
 let i = i + 1 in  (* 2 *)
 ... i ...         (* 3 *)

after (* 2 *) the old value of i is lost (no more accessible) and the
code is thus clearer and more robust in my opinion.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


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