[bitc-dev] Call by need?

wren ng thornton wren at freegeek.org
Fri Sep 10 13:32:07 PDT 2010

On 9/10/10 1:34 AM, Jonathan S. Shapiro wrote:
> That sounds more negative about compositionality than I really feel. I
> actually think that compositionality is terribly important, and I don't
> think that performance is the only important design goal. But I also think
> that the pursuit of compositionality has become an end in its own right in
> some parts of the PL community,

That is certainly true, and is part of the reason I cake certain forms 
of compositionality with a kilo of salt. And there's also a lot of faux 
compositionality like aspect-oriented programming which allows you to 
glue things together any way you like, with nothing compositional 
whatsoever about the resulting semantics.

But there is work in other forms of compositionality which don't 
introduce undue overhead or which do address the overhead issues. As an 
example of the former, Tim Sheard's pearl of using two-level types[1] 
allows separating the generic part of unification from the structural 
type being unified, and introduces no overhead you wouldn't already have 
from using a recursive ADT. And as an example of the latter, Thomas 
Nordin and Andrew Tolmach present a beautiful way of doing combinatorial 
search which matches how we think about the problem[2] (using laziness), 
and they discuss a bit about how the implementation is asymptotically 
equivalent to specialized implementations even though it has an 
unfortunately large constant factor (3~10x on an extremely old version 
of GHC, though they claim 30x would be fine for this domain; it'd be 
nice to see more modern numbers IMO).

Wouter Swierstra's solution to the expression problem[3] is sort of a 
borderline case. It's quite beautiful theoretically, and works rather 
efficiently in practice, but the layers of indirection should make any 
performance hacker scream. Conversely, the need for that indirection is 
something that could be gotten rid of if the source language can be 
tweaked in the right way. I've used this approach as an interim solution 
when needing to figure out a complex union type with many alternatives; 
one nice thing about it is that once you've figured out the type you 
want, it's very easy to flatten it to a normal ADT.

[1] http://web.cecs.pdx.edu/~sheard/papers/generic.ps
[2] http://web.cecs.pdx.edu/~apt/jfp01.ps
[3] http://www.cs.nott.ac.uk/~wss/Publications/DataTypesALaCarte.pdf

> and that along the way some of the
> participants have lost sight of the fact that PLs exist to solve real-world
> problems, and that PL problems per se aren't real-world problems unless they
> serve that objective. Which means that the relative importance of
> compositionality is very domain-dependent.
> The pursuit of PL theory has resulted in a lot of good work and useful
> outcomes. I'm pushing back because I feel that there is an urgent need to
> re-establish low-level utility as a goal, if only so that we can reconcile
> the progress in theory with the current state of the real-world problem
> space.

I agree that there needs to be a better fusion between modern PL theory 
and the needs of low-level performance. For as much as I love Haskell, 
it's a real problem that if I find Haskell to be unsuitable for some 
particular program I have no legitimate recourse. The fact that C is 
still being used as the dominant language for bit bashing is ludicrous. 
Even having such simple (yet novel) innovations as a decent module 
system and namespace separation would make C immensely more usable than 
it is. Let alone having a type system or a theoretically sound way of 
doing staged programming. Unfortunately C++ really messed things up in 
this regard, and IMO is part of the reason we haven't seen good 
theoretical PL research on systems-level coding until very recently with 
BitC, Habit, ATS, and the like.

FWIW, I was planning on developing just such a language before being 
seduced away by Haskell. These days I do a lot more NLP than I do 
systems code, so the odds are low that I'll ever get back to that 
language. But if I can help BitC "avoid success at all costs" as well as 
Haskell did, I think that'd be time well spent :)

Live well,

More information about the bitc-dev mailing list