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
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/
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
------------------------------------------------------------
Note that Standard ML does this differently to CAML/OCaml.
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
>> 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.
>
> 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
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
_______________________________________________
Well, at least you can have new effects. Look for "polymorphic
recursion".
Gerd
Regards
Saptarshi
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.
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/
_______________________________________________
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
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
Eta expansion does it...
# let y x = z z x;;
val y : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
Regards,
Fran�ois
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
Not quite -- SML simply defines "fun f x = ..." to be an abbreviation for
"val rec f = fn x => ...".
/Andreas
That's what Haskell does, yes.
Stefan
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
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
_______________________________________________
http://okmij.org/ftp/ML/fixpoints.ml
Standard ML doesn't have the feature that Till described.
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
_______________________________________________
Stefan "blush!"
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..."