Fri Sep 11 11:07:48 CEST 2009

Two Attacks

1. Concatenative languages and combinators.

I believe that concatenative languages (point-free functional
programming) are a good framework for expressing performance-oriented
DSLs with well-formed mathematical models.

First, as a basic substrate, concatenative _stack_ languages can serve
as the basic _sequential_ scripting substrate of an overall system.

Second, (not necessarily as a stack language) point-free style allows
a higher abstraction level (data flow instead of sequential control
flow), while at the same time allowing _restricted_ semantics to
emerge as sublanguages.  The more restrictions on the language, the
easier mathematical manipulation of _programs_ becomes.

I see two main advantages here:

   * Automated program manipulation is important for abstracting
     implementation strategies.  Automatic partial evaluation alone
     can not solve this, because it assumes there is a single good
     solution.  (The main problem being whether to unroll/inline or
     not is in general not decidable.)

   * In data-oriented programming, the combinators might have a large
     design space for mapping to actual hardware.  Making these
     parameters explicit allows one to get a better grip on how they
     relate to performance and implementability.

In short: separating algorithm+correctness from implementation mapping
is undoubtedly a great productivity gain, _if_ the specification of
implementation mapping is done in a _meaningful_ way, i.e. as a point
in a search space, possibly in combination with some mathematical laws
about the search space, in a form that makes sense.

2. Focus on static semantics and program manipulation.

Practically, in Staapl I would like to shift focus to

   * Putting the current eager partial evaluation (staging without
     annotation) on a better theoretical ground.  The guideline here
     is partially evaluating threaded state.  The attack is probably
     related to monads and arrows.

   * Construction of combinator subsets that satisfy mathematical laws
     (in the FL sense) on top of this substrate of partial evaluation
     of parallel threaded state.

So, the slogan is something like:

   ``Avoid low-level control constructs such as recursion and

Any serial code (i.e. accumulation), expressed as function
composition, should indicate only _necessary_ data dependency.  All
control flow should be expressed as higher order combinators which can
then be treated as opaque mathematical objects.  As Guy Steele[1] with
his mind on Fortress puts the latter: ``Get rid of CONS!'', maybe one
should also add[2]: ``and LAMBDA!'' ;)

[1] http://research.sun.com/projects/plrg/Publications/ICFPAugust2009Steele.pdf
[2] http://news.ycombinator.com/item?id=814632