[Caml-list] currying...

[Caml-list] currying...

[Chris Hecker]

How does caml know when to call a function?  For example, say I have:

val f: int -> int -> int -> unit

and the definition of f is 

let f x y = Printf.printf "%d %d" x y;Printf.printf "%d"

so f actually takes two ints, prints them, and then returns a function that takes an int and returns unit.  From the val declaration above in a .cmi file, how can caml tell the difference between that f and this one:

let f x y z = Printf.printf "%d %d %d" x y z

How does it know "when" to call f, since you need a different number of parameters for the different definitions?  The top f prints x y when it's called with two parms, so it doesn't wait until all three parms have been passed.

I have a feeling I'm missing something fundamental here, or else the definition of a function internally has a field for its arity and it just partially applies until it reaches the total arity.  I thought I remembered seeing some documentation on this months ago, but I can't find it now...

It doesn't seem to partially evaluate the function or anything insane like that.

Chris

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] currying...

[Thomas Colcombet]

As I understand the problem, may be the small following examples explain
how CAML
implements curryfication :

# let f = fun x -> (Printf.printf "%d\n" x; fun y -> Printf.printf
"%d\n" y);;
val f : int -> int -> unit = <fun>
# f 1;;
1
- : int -> unit = <fun>
# f 1 2;;
1
2
- : unit = ()

This function does not behave as the following one :

# let f = fun x y -> (Printf.printf "%d\n" x; Printf.printf "%d\n" y);;
val f : int -> int -> unit = <fun>
# f 1;;
- : int -> unit = <fun>
# f 1 2;;
1
2
- : unit = ()

In other words, a fun construct is evaluated only when all its argument
are known.
The notation "let f x y = ..." is just syntactic sugar for "let f = fun
x y -> ...".

	Thomas Colcombet

> How does caml know when to call a function?  For example, say I have:
> 
> val f: int -> int -> int -> unit
> 
> and the definition of f is
> 
> let f x y = Printf.printf "%d %d" x y;Printf.printf "%d"
> 
> so f actually takes two ints, prints them, and then returns a function that takes an int and returns unit.  From the val declaration above in a .cmi file, how can caml tell the difference between that f and this one:
> 
> let f x y z = Printf.printf "%d %d %d" x y z
> 
> How does it know "when" to call f, since you need a different number of parameters for the different definitions?  The top f prints x y when it's called with two parms, so it doesn't wait until all three parms have been passed.
> 
> I have a feeling I'm missing something fundamental here, or else the definition of a function internally has a field for its arity and it just partially applies until it reaches the total arity.  I thought I remembered seeing some documentation on this months ago, but I can't find it now...
> 
> It doesn't seem to partially evaluate the function or anything insane like that.
> 
> Chris
> 
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] currying...

[Bruce Hoult]

At 1:39 AM -0800 6/3/01, Chris Hecker wrote:
>How does caml know when to call a function?  For example, say I have:
>
>val f: int -> int -> int -> unit
>
>and the definition of f is
>
>let f x y = Printf.printf "%d %d" x y;Printf.printf "%d"
>
>so f actually takes two ints, prints them, and then returns a 
>function that takes an int and returns unit.  From the val 
>declaration above in a .cmi file, how can caml tell the difference 
>between that f and this one:
>
>let f x y z = Printf.printf "%d %d %d" x y z
>
>How does it know "when" to call f, since you need a different number 
>of parameters for the different definitions?  The top f prints x y 
>when it's called with two parms, so it doesn't wait until all three 
>parms have been passed.
>
>I have a feeling I'm missing something fundamental here, or else the 
>definition of a function internally has a field for its arity and it 
>just partially applies until it reaches the total arity.  I thought 
>I remembered seeing some documentation on this months ago, but I 
>can't find it now...
>
>It doesn't seem to partially evaluate the function or anything 
>insane like that.

Let me have an attempt at this, even though I'm a beginner too :-)


In OCaml, *all* functions actually take *one* argument.  When you write...

    let f x y = Printf.printf "%d %d" x y;Printf.printf "%d"

... it is actually just shorthand for a function that takes *one* 
argument (x) and returns as it's result a function that takes *one* 
argument (y) and prints x and y and then returns a function that 
takes one argument and prints it.

val f: int -> int -> int -> unit

.. actually means...

val f: int -> (int -> (int -> unit)))

.. it's just that since -> is right-associative you don't need the brackets.

Your first function would be perhaps better written as:

val f: int -> int -> (int -> unit)

But you don't need the parens :-)


In Scheme your first function would be like this:

(define f
   (lambda (x)
     (lambda (y)
       (display x)
       (display " ")
       (display y)
       (lambda (a)
         (display a)))))

(((f 1) 2) 3)


How does an OCaml function know how many arguments to take?  It's 
*always* one.  So you don't need the parens that you do in scheme. 
And if a function returns another function then applying it to the 
next argument in line is automatic.

This would of course be very inefficient if the compiler didn't do 
clever things...

-- Bruce
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] currying...

[Remi VANICAT]

Chris Hecker <checker@d6.com> writes:

> How does caml know when to call a function?  For example, say I have:
> 
> val f: int -> int -> int -> unit
> 
> and the definition of f is 
> 
> let f x y = Printf.printf "%d %d" x y;Printf.printf "%d"
> 
> so f actually takes two ints, prints them, and then returns a
> function that takes an int and returns unit.  From the val
> declaration above in a .cmi file, how can caml tell the difference
> between that f and this one: 
> 
> let f x y z = Printf.printf "%d %d %d" x y z
> 
> How does it know "when" to call f, since you need a different number
> of parameters for the different definitions?  The top f prints x y
> when it's called with two parms, so it doesn't wait until all three
> parms have been passed. 


there is a problem here : Printf.printf is a strange function, it
process argument one by one. A better vision of the problem can be see by
using print_int :

# let f x y = print_int x; print_char ' '; print_int y; print_int;;
val f : int -> int -> int -> unit = <fun>
# f 1;;
- : int -> int -> unit = <fun>
# f 1 2;;
1 2- : int -> unit = <fun>
# f 1 2 3;;
1 23- : unit = ()
# let f x y z = print_int x; print_char ' '; print_int y; print_int z;;
val f : int -> int -> int -> unit = <fun>
# f 1;;    
- : int -> int -> unit = <fun>
# f 1 2;;
- : int -> unit = <fun>
# f 1 2 3;;
1 23- : unit = ()

in fact, when caml create a function, it build a closure, and the
closure contain the information of how many argument it need to be
evaluate. 

> 
> I have a feeling I'm missing something fundamental here, or else the
> definition of a function internally has a field for its arity and it
> just partially applies until it reaches the total arity.  I thought
> I remembered seeing some documentation on this months ago, but I
> can't find it now... 

yes, there is such a field. I've never seen a documentation about it,
but it is clear when you read the output of
ocaml -dinstr
and the byterun/interp.c file of the source code

> 
> It doesn't seem to partially evaluate the function or anything
> insane like that. 

it mostly true, with the remarkable exception of printf

-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] currying...

[Xavier Leroy]

> [Curried functions, functions returning functions, and all that]

> I have a feeling I'm missing something fundamental here, or else the
> definition of a function internally has a field for its arity and it
> just partially applies until it reaches the total arity.

This is pretty much how it works internally, although the precise
mechanisms used are slightly different in the bytecode interpreter and
in the native-code compiler.  Viewed from the outside, it maintains
the illusion that every function takes only one parameter,
and fun x y -> ... behaves like fun x -> (fun y -> ...).

- Xavier Leroy
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] currying...

[Chris Hecker]

>This is pretty much how it works internally, although the precise
>mechanisms used are slightly different in the bytecode interpreter and
>in the native-code compiler.  Viewed from the outside, it maintains
>the illusion that every function takes only one parameter,
>and fun x y -> ... behaves like fun x -> (fun y -> ...).

Okay, that makes sense, thanks.  Now my question is, is there any way to introspect to get at the arity information?  I think it must be stored somewhere at runtime, because I can pass both f's to another function because they have the same "illusory type".  

Or do they?  Is int -> int -> int typechecked _exactly_ like int -> (int -> int)?  I assume they must be or the illusion wouldn't hold up.  I'd also assume this arity check only happens during application and doesn't affect typechecking at all.

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] currying...

[Sven LUTHER]

On Tue, Mar 06, 2001 at 09:41:38AM -0800, Chris Hecker wrote:
> 
> >This is pretty much how it works internally, although the precise
> >mechanisms used are slightly different in the bytecode interpreter and
> >in the native-code compiler.  Viewed from the outside, it maintains
> >the illusion that every function takes only one parameter,
> >and fun x y -> ... behaves like fun x -> (fun y -> ...).
> 
> Okay, that makes sense, thanks.  Now my question is, is there any way to introspect to get at the arity information?  I think it must be stored somewhere at runtime, because I can pass both f's to another function because they have the same "illusory type".  
> 
> Or do they?  Is int -> int -> int typechecked _exactly_ like int -> (int -> int)?  I assume they must be or the illusion wouldn't hold up.  I'd also assume this arity check only happens during application and doesn't affect typechecking at all.

Yes, they do, int -> int -> int is just an abreviation (or parenthesing
convention) of int -> (int -> int).

Friendly,

ven LUther
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] currying...

[Marcin 'Qrczak' Kowalczyk]

Tue, 06 Mar 2001 09:41:38 -0800, Chris Hecker <checker@d6.com> pisze:

> Now my question is, is there any way to introspect to get at the
> arity information?

You shouldn't need it. It's an implementation detail and doesn't have
to have any meaning. It should never be used to drive the semantics -
code should behave in the same way no matter how a function is built
internally.

AFAIK this internal "uncurrying" is limited to a constant (up to 5
arguments or something). Above that functions are really implemented
as functions returning functions, in groups of 5 arguments. There
might be also differences between native code and bytecode.

> Is int -> int -> int typechecked _exactly_ like int -> (int -> int)?

Yes.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] currying...

[Chris Hecker]

>> Now my question is, is there any way to introspect to get at the
>> arity information?
>You shouldn't need it. It's an implementation detail and doesn't have
>to have any meaning. It should never be used to drive the semantics -
>code should behave in the same way no matter how a function is built
>internally.

But that's not true if I'm trying to proxy a caml function with a c function.  I need to know where the "return value" starts.  So yes, on the caml side it's an implementation detail, but on the C side it's important (since it's hooking into the implementation).

>AFAIK this internal "uncurrying" is limited to a constant (up to 5
>arguments or something). Above that functions are really implemented
>as functions returning functions, in groups of 5 arguments.

That can't be true at the lowest level, unless caml does some really stoked partial evaluation analysis.  If I write a function that takes 10 parms and uses them in a nonlinear way then I don't think you can factor it into 2 5-parm functions.  Unless you're saying it just substitutes them into the function, but then it would have to build a whole new function every time your partially applied.

Chris

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] currying...

[Marcin 'Qrczak' Kowalczyk]

Tue, 06 Mar 2001 12:14:35 -0800, Chris Hecker <checker@d6.com> pisze:

> But that's not true if I'm trying to proxy a caml function with
> a c function.  I need to know where the "return value" starts.

There is no such concept. The same function can have different physical
arity depending on how it was compiled - it doesn't correspond
to anything meaningful in the source. Functions present the same
interface no matter what their physical arity is. From the C level too.

A library which has different behavior depending on the physical
arity of functions it works on is broken. The programmer has no
control how functions are compiled - it's the compiler's business.

> >AFAIK this internal "uncurrying" is limited to a constant (up to 5
> >arguments or something). Above that functions are really implemented
> >as functions returning functions, in groups of 5 arguments.
> 
> That can't be true at the lowest level,

Why? "Uncurrying" anything at all is an optimization. A straightforward
implementation would just apply arguments one at a time, allocating
a closure at each step.

Since currying is so common and there is so much performance gain in
treating it specially, OCaml does the trouble of applying multiple
arguments at once when it can. This requires a more complex calling
protocol, but is worth the effort.

> unless caml does some really stoked partial evaluation analysis.

I'm not sure what you mean.

> If I write a function that takes 10 parms and uses them in a
> nonlinear way then I don't think you can factor it into 2 5-parm
> functions.

It happens under the cover. From OCaml's point of view you can treat
is a function which returns a function which returns a function etc.
- 10 times. Or a curried 10-argument function. The point of split
is an implementation detail. It has no effect on the semantics.

No code should rely on where it is, unless it hides this under its
cover too and presents a unified interface to the outside. Do you
really have a case where you can use this fact to enable better
performance?

I understood that you want to use the distinction to decide to which
C type an OCaml type corresponds. This is broken. An OCaml type of a
binary function, and of an unary function returning an unary function,
is the same.

> Unless you're saying it just substitutes them into the function,
> but then it would have to build a whole new function every time
> your partially applied.

Indeed you allocate a new object when you partially apply a function.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] currying...

[Chris Hecker]

>A library which has different behavior depending on the physical
>arity of functions it works on is broken. 

It's not going to have different behavior, and it's not an optimization.  The library has to know because it has to know when to call a C function from another C function and it has to tell caml when to call it from caml.

Say I give a prototype to the library that's int -> int -> int -> int and I expect the library to give me back a closure that thunks to a c function.  Two things (at least) have to go on here:

- the library needs to know whether this is "int (*)(int,int,int)" or "int (*(*)(int))(int)" (or something else) so that it can create a closure to pass back to caml that has the right physical arity so that caml will call it and expect the right return type

- the library also needs to know the above so that it can call the linked c function correctly with the right number of arguments (this is analogous to the cast you have to make in C when you GetProcAddress/dlsym)

Since this is all happening dynamically, I need to be able to deduce the physical arity of the functions at runtime.

> Why? "Uncurrying" anything at all is an optimization. A straightforward
>implementation would just apply arguments one at a time, allocating
>a closure at each step.

Yes, I understand allocating the closure and it appearing like there's a bunch of 1 parm functions, but at some point the _actual_ function that does the work has to be called, so the implementation must know.  The only alternative is real partial evaluation to reduce the actual physical arity (meaning the function is specialized on its partially applied parameters and regenerated as an arity - 1 function), which is just way too complicated for caml or any other production language, I'd assume, so caml must just allocate a bunch of closures until it gets enough to call the original physical function.

> No code should rely on where it is, unless it hides this under its
>cover too and presents a unified interface to the outside. Do you
>really have a case where you can use this fact to enable better
>performance?

Again, it's not performance.  The C side has to know for me to write this library, as I said above.  All this will definitely be hidden, so you'll be able to pass partially applied functions and partially apply the returned functions, so the programmer won't know.  But there'll be a lot of stuff going on underneath to make this work.

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] currying...

[Marcin 'Qrczak' Kowalczyk]

Tue, 06 Mar 2001 15:23:50 -0800, Chris Hecker <checker@d6.com> pisze:

> - the library needs to know whether this is "int (*)(int,int,int)"
> or "int (*(*)(int))(int)" (or something else)

So you have to tell it (by some other mean than OCaml's type alone).
It has nothing to do with physical arity of OCaml's function closures.
It describes a C type.

> so that it can create a closure to pass back to caml that has the
> right physical arity

No, it needs not to create an OCaml closure of any particular arity.
It must create a closure which behaves in a particular way: calls the
C function after it received the necessary number of arguments. It
doesn't matter what is the arity from OCaml's internals' point of view.

You can't in general let the original C function pointer mimic OCaml's
code pointer in a closure anyway. First of all, types of values will
be different: C has a wide variety of types, OCamls wraps everything
as either a pointer or a tagged integer.

> Since this is all happening dynamically, I need to be able to deduce
> the physical arity of the functions at runtime.

Deduce from what? I understood that you create an OCamls function,
not examine it!

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] currying...

[Chris Hecker]

>It's not going to have different behavior, and it's not an optimization.  The library has to know because it has to know when to call a C function from another C function and it has to tell caml when to call it from caml.

By the way, I should point out that caml itself has to deal with this problem when calling c functions, which is why type abbreviations aren't expanded during arity checking, as it says in the manual in Subsection 17-1-1 on external declarations.  You are forced to use abbreviations for returning functions so the compiler can tell the arity of the external function.

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] currying...

[Chris Hecker]

>No, it needs not to create an OCaml closure of any particular arity.
>It must create a closure which behaves in a particular way: calls the
>C function after it received the necessary number of arguments. 

Isn't this the same thing?  How is it different?

> You can't in general let the original C function pointer mimic OCaml's
>code pointer in a closure anyway. First of all, types of values will
>be different: C has a wide variety of types, OCamls wraps everything
>as either a pointer or a tagged integer.

I'll convert all the arguments, so that shouldn't be a problem.

>> Since this is all happening dynamically, I need to be able to deduce
>> the physical arity of the functions at runtime.
>Deduce from what? I understood that you create an OCamls function,
>not examine it!

Right.  Since I haven't written the code yet, I'm not 100% sure exactly which primitives I'll need.  I definitely need to be able to create a int -> int -> (int -> int) and an int -> int -> int -> int, but I'm not sure whether I'll need to decide whether a given closure takes a given number of arguments.

I'm trying to piece together all the tools I'll need to make this work, and I'm feeling out the various corners of the problem to see where there might be problems...

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] currying...

[Marcin 'Qrczak' Kowalczyk]

Tue, 06 Mar 2001 17:10:56 -0800, Chris Hecker <checker@d6.com> pisze:

> >No, it needs not to create an OCaml closure of any particular arity.
> >It must create a closure which behaves in a particular way: calls the
> >C function after it received the necessary number of arguments. 
> 
> Isn't this the same thing?  How is it different?

It can be a function of two arguments which calls the underlying C
function. Or a function of one argument which returns a function of
one argument which calls the underlying C function. It doesn't matter.

> but I'm not sure whether I'll need to decide whether a given closure
> takes a given number of arguments.

You should not. Because it's a meaningless property. It results
from the way it was compiled, not from its meaning. Writing the same
function in slightly different ways (but equivalent ways as far as
OCaml is involved) can produce differently looking closures.

It's like taking an address of a float. You can do it because a float
is expressed as a heap-allocated objects, but you should not rely
on whether two floats have the same address, because it can depend
on compiler optimizations. It's not a property of OCaml's float type
but an artifact of the implementation.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

RE: [Caml-list] currying...

[Adam Granicz]

it does evaluate it partially. you have to remember that functions are
first-class values as well. as a matter of fact, the formally declared
parameters do not really matter, they are resolved by the compiler by
looking at the body of the function. declaring formal parameters is only
necessary when the order of these parameters can not be unambigously
determined. thus

let neg = function
	true -> false
   |  false -> true

is automatically understood as val: neg: bool -> bool.

also, remember that ocaml functions take only one parameter, so

val f: int -> int -> int -> unit

is actually the composition of several functions, the first taking an int
and returning a unit, the second taking an int and returning an int, and so
on.

> so f actually takes two ints, prints them, and then returns a
> function that takes an int and returns unit.  From the val

this one would be

val f: int -> int -> (int -> unit)

anyway, as to your question: if enough arguments are supplied so that the
function can be evaluated, then it is called and returns whatever that
function was supposed to return. however, if not all arguments were given
then the function is only partially evaluated with all known parameters.

let f i j = i+j

f 1 returns a function that expects one argument, so

let g = f 1

and

g 2 return 3.

hope this helps..

adam.

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr