Sun Jun 15 23:46:16 CEST 2008

partial evaluation of higher order functions

  * higher order macros (HOM)
  * list comprehensions
  * combining forms + 1st order functions (FP)
  * forth -> pure macros. what is this level shift?
  * deforestation


According to the wikipedia FP entry, limiting a language to 1st order
functions and a limited number of (non-composable) 2nd order functions
creates a simple algebraic structure. Combining forms are quite simply
defined as 2nd order functions.

List comprehensions are similar to limited order combining forms: they
avoid the use of higher order functions to perform
iteration/folding. However, they do not generate first order functions
as objects: they are merely syntax.

I found a definition for HOMs here:

   "A means of expressing certain higher-order functions in a first
    order language."

P.L. Wadler "Deforestation: Transforming programs to eliminate trees"

original paper:

Where i'd like to end up is to find the relationship between my forth
macro approach and fixed / composable 2nd order functions. I need a
theoretical framework, probably some type system restriction, to get
out of the anything->anything lisp world.

What I use this for is not necessarily to define a clean langauge
specification, but to see if it can help choose between higher order
functions and inlined expansion. Since I have higher order functions,
but would like to have inlining as optimization.

Somewhat related, i can make things such that each word is linked to
its originating macro. This might lead to functions that are both
instantiated, and available as a macro whenever they are used in a
combining form that cannot accept a function at run time.