31 views

Skip to first unread message

Feb 9, 2010, 3:58:36 PM2/9/10

to caml...@yquem.inria.fr

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

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?

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

Feb 9, 2010, 4:54:51 PM2/9/10

to saptars...@gmail.com, caml...@yquem.inria.fr

Saptarshi Guha a écrit :

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

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

Essentially, the fact that "rec" means anything is mostly due to the

fact that you want to be able to redefine stuff.

> let f = fun x -> x + 1

>

> let f x = f (f x)

is valid in ocaml, and you're function f is the function that adds 2.

whereas

> let rec f x = f (f x)

has a completely different meaning.

If you avoided the use of rec, saying "if unbound, assume rec", then the

line

let f x = f (f x)

has two entirely different meaning, depending on whether f is defined

before or not.

That would be quite a chaotic feature.

> Wouldn't one of way of detecting a recursive function would be to see

> if the indeed the function calls itself?

No. Because you never know if you intended to call the function

recursively, or if you intended to call an homonymous function you

defined before.

All the best,

--

Guillaume Yziquel

http://yziquel.homelinux.org/

Feb 9, 2010, 4:55:04 PM2/9/10

to saptars...@gmail.com, caml...@yquem.inria.fr

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

ge...@gerd-stolpmann.de http://www.gerd-stolpmann.de

Phone: +49-6151-153855 Fax: +49-6151-997714

------------------------------------------------------------

Feb 9, 2010, 5:14:21 PM2/9/10

to caml...@yquem.inria.fr

On Tuesday 09 February 2010 22:01:03 Gerd Stolpmann wrote:

> In the ML community it is consensus that a recursive function is a total

> different thing than a non-recursive function...> In the ML community it is consensus that a recursive function is a total

Note that Standard ML does this differently to CAML/OCaml.

--

Dr Jon Harrop, Flying Frog Consultancy Ltd.

http://www.ffconsultancy.com/?e

Feb 9, 2010, 5:14:41 PM2/9/10

to guillaum...@citycable.ch, caml...@yquem.inria.fr

Thanks, very helpful.

>> let f = fun x -> x + 1 (1)

>>

>> let f x = f (f x) (2)

This works in ocaml because, it replaces f (in (2) ) from that of (1).

Which is why i need f previously defined.

Correct me if i'm wrong.

>

>> Wouldn't one of way of detecting a recursive function would be to see

>> if the indeed the function calls itself?

>

> No. Because you never know if you intended to call the function recursively,

> or if you intended to call an homonymous function you defined before.

>

Very true, hadn't considered this.

Feb 9, 2010, 5:16:44 PM2/9/10

to Gerd Stolpmann, caml...@yquem.inria.fr

>

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

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

This makes sense. Thanks, I did read about the y-combinator and its

use in recursion in Friedman and Wand. I'll read it again.

Thanks for the help

Feb 9, 2010, 5:18:16 PM2/9/10

to saptars...@gmail.com, caml...@yquem.inria.fr

On Tuesday 09 February 2010 20:50:33 Saptarshi Guha wrote:

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

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

let f x = x + 1

let f x = 2 * f x

Is the latter "f" recursive or not?

See my answer to the same question on stack overflow:

--

Dr Jon Harrop, Flying Frog Consultancy Ltd.

http://www.ffconsultancy.com/?e

_______________________________________________

Feb 9, 2010, 5:28:08 PM2/9/10

to guillaum...@citycable.ch, caml...@yquem.inria.fr

Am Dienstag, den 09.02.2010, 22:58 +0100 schrieb Guillaume Yziquel:

> Gerd Stolpmann a écrit :

> > Am Dienstag, den 09.02.2010, 15:50 -0500 schrieb Saptarshi Guha:

> >

> > Besides the different way of defining "let" and "let rec" there are also

> > differences in typing.

Well, at least you can have new effects. Look for "polymorphic

recursion".

Gerd

Feb 9, 2010, 5:32:17 PM2/9/10

to Jon Harrop, caml...@yquem.inria.fr

Yes, I see that f isn't recursive, because it simplifies down to

2*(x+1) but for a reader(at least myself) it can be bit tricky to

consume. My experience of reading the /definition/ of a function which

includes a call

to itself is that it is recursive. On the stackoverflow post, you

mentioned that the British ML branch forces different names (since

recursion is by default), and though it does pollute the namespace,

personally I find it easier to read.

2*(x+1) but for a reader(at least myself) it can be bit tricky to

consume. My experience of reading the /definition/ of a function which

includes a call

to itself is that it is recursive. On the stackoverflow post, you

mentioned that the British ML branch forces different names (since

recursion is by default), and though it does pollute the namespace,

personally I find it easier to read.

Regards

Saptarshi

Feb 9, 2010, 5:56:37 PM2/9/10

to saptars...@gmail.com, caml...@yquem.inria.fr

On Tuesday 09 February 2010 22:31:49 Saptarshi Guha wrote:

> Yes, I see that f isn't recursive, because it simplifies down to

> 2*(x+1) but for a reader(at least myself) it can be bit tricky to

> consume.

> Yes, I see that f isn't recursive, because it simplifies down to

> 2*(x+1) but for a reader(at least myself) it can be bit tricky to

> consume.

But for a writer it can be useful to produce. For example, imagine a function

in an interpreter that evaluates an expression to a value in the context of a

set of variable bindings:

let rec eval vars = function

...

| Add(f, g) -> eval vars f + eval vars g

| Mul(f, g) -> eval vars f * eval vars g

...

Such functions make a *lot* of recursive calls.

Now imagine you want to inject some code around every external call into

that "expr" function but not recursive calls, e.g. logging exceptional

returns. Do you want to change the name of that "expr" function not only in

its definition but at every recursive call in its body? No.

Fortunately, in OCaml you can just append a definition to supercede "expr"

without touching the original definition at all:

let eval vars expr =

...

let result = eval vars expr in

...

result

This is a useful and common OCaml idiom.

> My experience of reading the /definition/ of a function which

> includes a call to itself is that it is recursive.

Definitions are often superceded in ML.

> On the stackoverflow post, you mentioned that the British ML branch forces

> different names (since recursion is by default), and though it does pollute

> the namespace, personally I find it easier to read.

You can do that in OCaml as well, if you choose.

Feb 9, 2010, 7:07:17 PM2/9/10

to Gerd Stolpmann, caml...@yquem.inria.fr

Gerd Stolpmann a écrit :

> Am Dienstag, den 09.02.2010, 22:58 +0100 schrieb Guillaume Yziquel:

>> Gerd Stolpmann a écrit :

>>> Am Dienstag, den 09.02.2010, 15:50 -0500 schrieb Saptarshi Guha:

>>>

>>> Besides the different way of defining "let" and "let rec" there are also

>>> differences in typing.

>

> Well, at least you can have new effects. Look for "polymorphic

> recursion".

> Am Dienstag, den 09.02.2010, 22:58 +0100 schrieb Guillaume Yziquel:

>> Gerd Stolpmann a écrit :

>>> Am Dienstag, den 09.02.2010, 15:50 -0500 schrieb Saptarshi Guha:

>>>

>>> Besides the different way of defining "let" and "let rec" there are also

>>> differences in typing.

>

> Well, at least you can have new effects. Look for "polymorphic

> recursion".

You mean something like this?

http://alaska-kamtchatka.blogspot.com/2009/05/polymorphic-recursion.html

With the following code

> type length = { length : 'a . int -> 'a vec -> int }

>

> let length v =

> let rec f = { length = fun n l -> match l with

> Nil -> n

> | Zero ps -> f.length ( 2 * n) ps

> | One (_, ps) -> f.length (1 + 2 * n) ps

> } in f.length 0 v

you get to use a function, here f.length, in two different contexts for

type inference, allowing it to be used with multiple types? 'a * 'a

instead of 'a? Am I getting this post right?

But then, this seems to go into rather elaborate constructions

(existential types with OCaml records), which are quite remote from the

simple 'let rec' issue we were talking about.

Is it possible to have polymorphic recursion with vanilla 'let rec'

invocations? Or am I getting you wrong?

All the best,

--

Guillaume Yziquel

http://yziquel.homelinux.org/

_______________________________________________

Feb 9, 2010, 10:11:09 PM2/9/10

to caml...@yquem.inria.fr

On 2/10/2010 1:07 AM, Guillaume Yziquel wrote:

> Is it possible to have polymorphic recursion with vanilla 'let rec'

> invocations?

> Is it possible to have polymorphic recursion with vanilla 'let rec'

> invocations?

This is something that Jacques recently merged in the current

development branch. The code below should work with OCaml 3.12.

let length v =

let rec f : 'a. int -> 'a vec -> int = fun n l -> match l with

Nil -> n

| Zero ps -> f (2 * n) ps

| One (_, ps) -> f (1 + 2 * n) ps

in

f 0 v

-- Alain

Feb 10, 2010, 2:19:20 AM2/10/10

to Gerd Stolpmann, caml...@yquem.inria.fr

On Tue, Feb 9, 2010 at 11:01 PM, Gerd Stolpmann <ge...@gerd-stolpmann.de> wrote:

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

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

A small correction: y is typeable. It's a fixed-point operator, so it's type is

('a -> 'a) -> 'a

or if we only care about recursive functions it is:

# let rec y f x = f (y f) x ;;

val y : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>

(Yes, I know I used "let rec", it doesn't matter for checking that y

has a type). Let's check that it works:

# let fac = y (fun f n -> if n = 0 then 1 else n * f (n - 1)) ;;

val fac : int -> int = <fun>

# fac 7 ;;

- : int = 5040

What Gerd probably meant was that the usual untyped lambda-calculus

definition of y, which gets us recursion out of nothing isn't typeable

because self-application requires unrestricted recursive types. But

again, it's an intermediate definition that is not typeable, not y

itself (here adapted so that it works for functions in an eager

language):

$ ocaml -rectypes

Objective Caml version 3.11.1

# let z = fun u v w -> v (u u v) w ;;

val z : ('a -> ('b -> 'c -> 'd) -> 'b as 'a) -> ('b -> 'c -> 'd) -> 'c

-> 'd = <fun>

# let y = z z ;;

val y : (('_a -> '_b) -> '_a -> '_b) -> '_a -> '_b = <fun>

Observe that y has a non-recursive type, it's the auxiliary z that

requires a recursive one. And this y also works:

# let fac = y (fun f n -> if n = 0 then 1 else n * f (n - 1)) ;;

val fac : int -> int = <fun>

# fac 7 ;;

- : int = 5040

Can anyone get rid of the pesky underscores in the type of y above, so

that it becomes truly polymorphic?

With kind regards,

Andrej

Feb 10, 2010, 4:36:20 AM2/10/10

to Andrej Bauer, caml...@yquem.inria.fr, Gerd Stolpmann

>

>

> # let y = z z ;;

> val y : (('_a -> '_b) -> '_a -> '_b) -> '_a -> '_b = <fun>

>

>

> # let y = z z ;;

> val y : (('_a -> '_b) -> '_a -> '_b) -> '_a -> '_b = <fun>

>

> Can anyone get rid of the pesky underscores in the type of y above, so

> that it becomes truly polymorphic?

>

> that it becomes truly polymorphic?

>

Eta expansion does it...

# let y x = z z x;;

val y : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>

Regards,

Fran�ois

Feb 10, 2010, 5:12:47 AM2/10/10

to caml...@yquem.inria.fr

"Andrej Bauer" <andrej...@andrej.com> wrote:

>

> What Gerd probably meant was that the usual untyped lambda-calculus

> definition of y, which gets us recursion out of nothing isn't typeable

> because self-application requires unrestricted recursive types.

>

> What Gerd probably meant was that the usual untyped lambda-calculus

> definition of y, which gets us recursion out of nothing isn't typeable

> because self-application requires unrestricted recursive types.

Fortunately, even that is not quite correct: Y is perfectly typable in

plain ML, you just need to introduce the recursive type it employs

explicitly:

type 'a fix = Fix of ('a fix -> 'a)

let fix f = let z = fun (Fix g' as g) x -> f (g' g) x in z (Fix z)

Now, for example:

let fac = fix (fun fac n -> if n = 0 then 1 else n * fac (n-1))

let n = fac 7

Best,

/Andreas

Feb 10, 2010, 5:15:30 AM2/10/10

to caml...@yquem.inria.fr

Jon Harrop:

> On Tuesday 09 February 2010 22:01:03 Gerd Stolpmann wrote:

>> In the ML community it is consensus that a recursive function is a total

>> different thing than a non-recursive function...

>

> Note that Standard ML does this differently to CAML/OCaml.

> On Tuesday 09 February 2010 22:01:03 Gerd Stolpmann wrote:

>> In the ML community it is consensus that a recursive function is a total

>> different thing than a non-recursive function...

>

> Note that Standard ML does this differently to CAML/OCaml.

Not quite -- SML simply defines "fun f x = ..." to be an abbreviation for

"val rec f = fn x => ...".

/Andreas

Feb 10, 2010, 5:02:20 PM2/10/10

to caml...@inria.fr

> Wouldn't one of way of detecting a recursive function would be to see

> if the indeed the function calls itself?

> if the indeed the function calls itself?

That's what Haskell does, yes.

Stefan

Feb 10, 2010, 5:25:52 PM2/10/10

to caml...@inria.fr

On Wed, Feb 10, 2010 at 5:01 PM, Stefan Monnier

<mon...@iro.umontreal.ca> wrote:

>> Wouldn't one of way of detecting a recursive function would be to see

>> if the indeed the function calls itself?

>

> That's what Haskell does, yes.

>

>

<mon...@iro.umontreal.ca> wrote:

>> Wouldn't one of way of detecting a recursive function would be to see

>> if the indeed the function calls itself?

>

> That's what Haskell does, yes.

>

>

Let's make things clear here: the "rec" *really* is a feature; it is

very convenient to reuse the same identifier to express something in

the process of being built (e.g. something going through a pipeline).

For instance:

let g () =

let f s =

if !debug then

Printf.printf "f is called with value: %s\n%!" s

f s

in

.......

Some (including me) would even argue that it is sad that type

definitions don't use "rec".

Till

Feb 10, 2010, 7:32:51 PM2/10/10

to caml...@yquem.inria.fr

On Wednesday 10 February 2010 22:25:44 Till Varoquaux wrote:

> Some (including me) would even argue that it is sad that type

> definitions don't use "rec".

> Some (including me) would even argue that it is sad that type

> definitions don't use "rec".

Agreed. Less useful than "rec" on function definitions but that would still be

useful sometimes.

--

Dr Jon Harrop, Flying Frog Consultancy Ltd.

http://www.ffconsultancy.com/?e

_______________________________________________

Feb 11, 2010, 1:50:47 AM2/11/10

to caml...@inria.fr

Fortunately OCaml is (much more) than simply-typed lambda

calculus. Almost any feature of OCaml -- recursive data types,

recursive types, reference cells, mutable records, exceptions,

objects, recursive modules and polymorphic variants -- can be used to

express the fixpoint combinator. Sometimes there is more than one way

to use the same feature to express the fixpoint combinator. The more

and less known ways of expressing fix are collected in the following

document:

http://okmij.org/ftp/ML/fixpoints.ml

Feb 15, 2010, 11:18:00 AM2/15/10

to caml...@yquem.inria.fr

On Monday 15 February 2010 15:46:58 Stefan Monnier wrote:

> Till Varoquaux had written:

> > Let's make things clear here: the "rec" *really* is a feature;

>

> Nobody said otherwise. Eliminating the "rec" is also a feature.

> Those two features are mostly incompatible, and many reasonable people

> disagree on which one of the two is more important.

>

> Stefan "who extensively used that feature in SML, but happens

> to prefer the other feature nevertheless"

> Till Varoquaux had written:

> > Let's make things clear here: the "rec" *really* is a feature;

>

> Those two features are mostly incompatible, and many reasonable people

> disagree on which one of the two is more important.

>

> Stefan "who extensively used that feature in SML, but happens

> to prefer the other feature nevertheless"

Standard ML doesn't have the feature that Till described.

--

Dr Jon Harrop, Flying Frog Consultancy Ltd.

http://www.ffconsultancy.com/?e

_______________________________________________

Feb 16, 2010, 9:42:42 AM2/16/10

to caml...@inria.fr

> It sure does, tho not with "fun" but only with "var" definitions.

^^^

val

^^^

val

Stefan "blush!"

Feb 16, 2010, 11:22:09 AM2/16/10

to Stefan Monnier, caml...@inria.fr

It may be worth recalling the OCaml koans at

http://eigenclass.org/hiki/fp-ocaml-koans. The first one is:

let rec

http://eigenclass.org/hiki/fp-ocaml-koans. The first one is:

let rec

One day, a disciple of another sect came to Xavier Leroy and said mockingly:

"The OCaml compiler seems very limited: why do you have to indicate when a

function is recursive, cannot the compiler infer it?"

Xavier paused for a second, and replied patiently with the following story:

"One day, a disciple of another sect came to Xavier Leroy and said

mockingly..."

Reply all

Reply to author

Forward

0 new messages