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?
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
P.L. Wadler "Deforestation: Transforming programs to eliminate trees"
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.