upvote

points

by vq8 hours ago |
comments
upvoteby emih8 hours ago|
next
[-]
That's a very good point, I never thought really about how this relates to the execution model & graph reduction and such. Do you have an example of a function where this can make a difference? I might add something to the article about it.

It's also a question of whether this is exclusive to a curried definition or if such an optimization may also apply to partial application with a special operator like in the article. I think it could, but the compiler might need to do some extra work?

reply
upvoteby taolson5 hours ago|
parent|
next
[-]
An example where this is useful is to help inline otherwise recursive functions, by writing the function to take some useful parameters first, then return a recursive function which takes the remaining parameters. This allows the function to be partially in-lined, resulting in better performance due to the specialization on the first parameters. For example, foldr:

foldr f z = go

  where

    go [] = z

    go (x : xs) = f x (go xs)
when called with (+) and 0 can be inlined to

go xs = case xs of

    [] -> 0

    (x : xs) = x + go xs
which doesn't have to create a closure to pass around the function and zero value, and can subsequently inline (+), etc.
reply
upvoteby vq8 hours ago|
parent|
prev|
[-]
One slightly contrived example would be if you had a function that returned the point of a set closest to another given point.

getClosest :: Set Point -> Point -> Point

You could imagine getClosest build a quadtree internally and that tree wouldn't depend on the second argument. I say slightly contrived because I would probably prefer to make the tree explicit if this was important.

Another example would be if you were wrapping a C-library but were exposing a pure interface. Say you had to create some object and lock a mutex for the first argument but the second was safe. If this was a function intended to be passed to higher-order functions then you might avoid a lot of unnecessary lock contention.

You may be able to achieve something like this with optimisations of your explicit syntax, but argument order is relevant for this. I don't immediately see how it would be achieved without compiling a function for every permutation of the arguments.

reply
upvoteby twic7 hours ago|
parent|
next
[-]
I think we need to see a few non-contrived examples, because i think in every case where you might take advantage of currying like this, you actually want to make it explicit, as you say.

The flip side of your example is that people see a function signature like getClosest, and think it's fine to call it many times with a set and a point, and now you're building a fresh quadtree on each call. Making the staging explicit steers them away from this.

reply
upvoteby 12_throw_away5 hours ago|
parent|
next
[-]
> and now you're building a fresh quadtree on each call [...] Making the staging explicit steers them away from this.

Irrespective of currying, this is a really interesting point - that the structure of an API should reflect its runtime resource requirements.

reply
upvoteby addaon6 hours ago|
parent|
prev|
[-]
Consider a function like ‘match regex str’. While non-lazy languages may offer an alternate API for pre-compiling the regex to speed up matching, partial evaluation makes that unnecessary.
reply
upvoteby emih7 hours ago|
parent|
prev|
[-]
Those are nice examples, thanks.

I was imagining you might achieve this optimization by inlining the function. So if you have

  getClosest(points, p) = findInTree(buildTree(points), p)
And call it like

  myPoints = [...]
  map (getClosest(myPoints, $)) myPoints
Then the compiler might unfold the definition of getClosest and give you

  map (\p -> findInTree(buildTree(myPoints), p)) myPoints
Where it then notices the first part does not depend on p, and rewrite this to

  let tree = buildTree(myPoints) in map (\p -> findInTree(tree, p)) myPoints
Again, pretty contrived example. But maybe it could work.
reply
upvoteby vq6 hours ago|
parent|
[-]
I didn't consider inlining but I believe you're correct, you could regain the optimisation for this example since the function is non-recursive and the application is shallow. The GHC optimisation I had in mind is like the opposite of inlining, it factors out a common part out of a lambda expression that doesn't depend on the variable.

I don't believe inlining can take you to the exact same place though. Thinking about explicit INLINE pragmas, I envision that if you were to implement your partial function application sugar you would have to decide whether the output of your sugar is marked INLINE and either way you choose would be a compromise, right? The compromise with Haskell and curried functions today is that the programmer has to consider the order of arguments, it only works in one direction but on the other hand the optimisation is very dependable.

reply
upvoteby ackfoobar5 hours ago|
prev|
[-]
> explicitly written to do this

In that case I want the signature of "this function pre-computes, then returns another function" and "this function takes two arguments" to be different, to show intent.

> achieved through compiler optimisation

Haskell is different in that its evaluation ordering allows this. But in strict evaluation languages, this is much harder, or even forbidden by language semantics.

Here's what Yaron Minsky (an OCaml guy) has to say:

> starting from scratch, I’d avoid partial application as the default way of building multi-argument functions.

https://discuss.ocaml.org/t/reason-general-function-syntax-d...

reply