Sun Jun 15 10:09:14 CEST 2008

array comprehensions

The trouble is then, the problem I want to solve is to generate
efficient code for a dataflow graph + array comprehension

The real problems for comprehensions (translation to nested loops)
are performance (P) and correctness (C).

  * Inner loop generation (P)
  * Cache memory optimization (P)
  * Handle border conditions. (C)

Here (P) need to be fast and (C) if applicable (i.e. in convolution)
might be approximately correct.

There is a discussion on the concatenative list about Backus' FP and
APL not having first class functions, but comprehensions. Is it fair
to say that this is the thing to do for numerical code? First class
functions are overkill, but anything you would want to solve with them
can be solved with comprehensions: you turn higher order operations
into syntax, which converts them to easily inlined loops.

There's a thread on concatenative about this:

My answer, without thinking too much, would be: macros. Languages
based on composition can have partial evaluation. Higher order macros
can expand to combination forms: Have higher order macros, but don't
allow such functions at run time. Is this cheating, or completely
beside the point?

   "We owe a great debt to Kenneth Iverson for showing us that there
   are programs that are neither word-at-a-time nor dependent on
   lambda expressions, and for introducing us to the use of new
   functional forms." - John Backus, 'Can Programming Be Liberated
   from the von Neumann Style?'

The basic idea; use concatenative syntax for specification of:

* pure functions, which are translated to a dataflow representation.
* higher order macros which serve as combining forms (combining forms).

Maybe I should try to answer this, and relate it to unrolled
reflection and partial evaluation:


I don't know how though.. Maybe best to try the combinator route first.

   The idea here is that "combining forms" as found in FP and APL are
   related to the macros in Purrr that are not compilable. My stress
   on macros is really about giving up first class functions at
   runtime, but not at compile time.