[Haskell-cafe] Haskell's "partial application" (not currying!) versus Business Objects Gem Cutter's "burning"

[Conor McBride]

Hi Jules

Your explanation of lambda-abstraction, dealing in full generality  
with both scope and
multiplicity, is a good one. But it's still interesting to  
investigate the possibility
of a privileged notation for linear abstraction, based on leaving  
holes in things, by
way of illustrating the design space. I seem to remember this topic  
coming up before
(on Haskell Prime?), but I can't find the archival references just now.

On 3 Jul 2007, at 11:19, Jules Bean wrote:

> peterv wrote:
>> In Haskell, currying can only be done on the last (rightmost)  
>> function arguments.

[..]


>
>> This burning looks more general to me, but cannot be done using  
>> the textual approach?
>
> Well, it can be done, but basically there are two issues:

Dead right.

> 1. You need to demarquate the 'scope' of the ?. What 'lump' of  
> expression is the partially evaluated part. An obvious way to do  
> this is with parentheses, but you have to be careful.

Let me borrow braces {..} for purposes of discussion. One might  
imagine a form of
abstraction where one simply writes an expression in braces,  
replacing some
subexpressions with ?, like Haskell Emmental

   {? * 10 + ?}

Of course...

> 2. If you have more than one ?, you need to remember which is  
> which. Think of nested expressions, nested ?s. What if you want to  
> use the 'same' ? more than once?

...we need a convention to handle this. The obvious convention is  
that each ? is
distinct and that they (and only they!) are abstracted from a brace  
in left-to-right
order. That's to say, the above means

   \x y -> x * 10 + y

hence

   {? * 10 + ?} 4 2 = 42

It can make sense to allow nested applications inside braces, using  
parentheses.

   {f ? (g ? x)}

It can even make sense to allow nested braces, provided we adopt the  
convention that
a ? is bound by its most local brace.

   {foldr {? : ?} ? ?} = flip (++)

For expressions with no ?s, {..} and (..) coincide. {f ? ... ?} means  
f. All sorts
of compositions, not just {f (g ?)}, are readily expressed, without  
resorting either
to naming or to lurid ascii-art.

[Local notational speculation: use (..) for {..}

   One might well wonder: if ?-less {..} are like (..) and ?-ful (..)  
are currently
   meaningless, why not overload (..) ? This can be done, but it  
gives a rather
   peculiar semantics to previously innocent syntax---you lose the  
ability to add
   extra parentheses to clarify grouping, so

     (f a) b   is not necessarily the same as   f a b

   and you also lose the ability to nest expressions, except via  
precedence

     (f (g ?))  means  f g  and not  f . g
     (? * 10 + ?)  may work, but  ((? * 10) + ?)  causes trouble.

End local speculation]

Oddly, to my mind, this is exactly the approach that the Gem Cutter  
crew take, but
pictorially. On the one hand, they use tree diagrams for expressions,  
so they
don't need parentheses for grouping. On the other hand, they  
explicitly choose
only to allow the abstraction of "burnt" arguments from the very  
application in
which they occur. Correspondingly

   {foo ? y}      is expressible, but
   {? * 10 + ?}   has to be expanded.

This seems like a missed opportunity to me.

What should Haskell take away from this?

(1) You know where you are with lambda-abstraction. You can even do  
some sorts
of "fast and loose" reasoning under binders, with some hope of  
preserving the
meaning of your expressions. By comparison, computing inside {..} is  
very
dangerous:

   {0 * ?} is not {0}
   {const ? ?} is not {?}
   {flip f ? ?} is not {f ? ?}
   {(\x -> (x, x)) ?} is not {(?, ?)}

(2) Even so, it might be a useful feature. Something of the sort  
*has* been
proposed before. I just found it

   http://hackage.haskell.org/trac/haskell-prime/wiki/ 
FlexiblePartialApplication

but without the special {..} bracket, it's a nightmare. Brackets are  
always at
a premium in syntax design. What would we do?

(3) Exercise for readers:

   implement constructors
     P v      for embedding pure values v
     O        for holes
     f :$ a   for application, left-associative
   and an interpreting function
     emmental
   such that
     emmental (P (+) :$ (P (*) :$ O :$ P 10) :$ O) 4 2 = 42

I think the question of whether to support linear abstractions other  
than of
an argument suffix is an interesting one. The flip answer is a bad  
answer;
lambda abstraction is a good answer, but sometimes feels too heavy  
for this
job. I really don't have a strong opinion about whether it's worth  
supporting
a lighter notation for the linear case, but I thought I'd at least  
try to
inform the debate.

All the best

Conor