🚀 go-pugleaf

In article <TMB.92Oct7181835@arolla.idiap.ch>, tmb@arolla.idiap.ch (Thomas M. Breuel) writes:

|> (Please note that I said "difficult", not "impossible", and that I
|> gave a benchmark. Current compilers apparently have difficulties with
|> optimizing currying well, and here are the reasons...)

I think I misinterpreted your use of the word "difficult". I tend to
reserve that to things like intermodule context analysis over non-flat 
domains ... ;-)

Seriously, though, you have a point in that all things being equal, it
is a weakness for a language to require very powerful optimizations to
run with decent performance.

< stuff deleted >
 
|> (in fact, not having this
|> control over evaluation and resources is precisely why I don't like
|> lazy evaluation).

And it is precisely why I like it. I believe that the "creative" part
of an algorithm is specifying the data dependencies. Then a good
compiler should be able to come up with an evaluation order that is at
least as efficient in terms of resource (eg memory) consumption,
locality and (when the machine can take advantage of it) parallelism,
as any I could come up with myself with a reasonable amount of work.

Or, if you don't like the use of the word "believe" above, let's say 
it's the hypothesis my research is meant to test.

|> Consider:
|> 
|> 	val make_opaque : ('a -> 'b) -> ('a,'b) opaque
|> 	val apply_opaque : ('a,'b) opaque * 'a -> 'b
|> 
|> 	fun p x y = ...
|> 	fun q x = make_opaque(fn y => ...)
|> 
|> By your rules, you will generate entry points for "p" with two
|> arguments and for "q" with one argument. That means that calls with
|> the number of arguments you expect like "p 1 2" and "q 1" will be
|> faster than calls like "p 1" and "apply_opaque(q 1,2)".

Basically correct. "p 1" will be represented as a thunk in the heap 
and "p" will only be called when that thunk is applied to a (second)
argument. The other case is more complicated: If "x" occurs inside
the "..." in "(fn y => ...)", lambda lifting will take it out as an
extra argument and transform "q" to:

fun q x = make_opaque((fn x => fn y => ...) x)

so "make_opaque" will be called with a thunk representing the 
"fn x => fn y => ..." abstraction applied to one argument. Then
"apply_opaque" gets whatever "make_opaque" returns and does
someting with that and "2". Having multiple entrypoints is the 
least hassle in this.

< stuff deleted >

|> I see. So you are saying that several entrypoints need to be
|> generated. That was my point: you either pay space (plus a little
|> time), or you pay time.

< stuff deleted >

|> Note that, as far as I can tell, unless you duplicate the code for the
|> function completely for each possible entrypoint, even if you generate
|> different entrypoints for the same function, you still pay some
|> overhead in jumps and some register space for state. The reason is
|> that different entrypoints have different results.

The code pointer you store in a thunk must point to code that knows the 
size of the thunk (e.g. "one argument in the thunk, two on the stack").
Each entry point fetches the arguments from the thunk (preferably into 
registers), pops the reamaining arguments (the rightmost ones) off the 
stack, and then jumps to the "fast" entrypoint. 

Now, if you had used tuples (e.g. "f (x,y) (z,w) = e" instead of
"f x y z w = e"), the arguments in your registers at this point
would be pointers to pairs, so you'd have to destructure them. On
the other hand, you get fewer entrypoints. On the third hand, if
you only use the function with certain number of arguments, some of
the entry points can be optimized away. So it might leave you with
only one entry point that makes it all the way into assembly.

Now, I think this thread is starting to be a bit silly (especially
THIS posting :-). There is no reason to tell anyone that they should
or shouldn't use tuples in their function definitions. But if one
does't have strong stylistic preferences, it might be a good thing
to check out what's most efficient with the language/compiler one
is using. And it seems to be most prudent for language implementors
to try to generate good code for both alternatives.

< Thomas wrote: >

|>    |> it gives uninformative type signatures (is "'a -> 'a -> 'a"
|>    |> intended to be a function of one argument returning a function, or is
|>    |> it intended to be a function of two arguments returning a "'a"?),

< I replied: >

|>    It is both.

< Thomas aswered: >

|> Well, that's like saying that "lists" and "arrays" are the same. 

Well, maybe they are? Both a list and a one-dimensional array can be
seen as a function from an integer subrange to some type. In the 
future, when our compilers are wiser, it might be best to leave the
choice of representation to them.

Cheers,
         Karl-Filip

------------------------------------------------------------
Make the frequent case fast, and the fast case frequent!