Sat Jul 5 12:25:00 CEST 2008

scheme vs. purrr PE macros

It's about macro arguments. The fundamental idea is that the expansion
depends on the input _values_ not just the input structure. In
ordinary day-to-day Scheme macros this is seldom the case.

What I'd like to find is a way to explain the essential difference
between Scheme's macros system and Purrr's macro system, which is a
polymorphic concatenative language where values represent postponed

Building such a Scheme partial evaluator in transforming all functions
to macros shouldn't be too difficult. This is called "introducing
staging".  The analogous intelligent scheme macro:

(define-syntax-ns (pesel) +
  (lambda (stx)
    (syntax-case stx ()
      ((_ a b)
       (let ((da (syntax->datum #'a))
             (db (syntax->datum #'b)))
         (let ((na (number? da))
               (nb (number? db)))
            (and na nb)
            (datum->syntax stx (+ da db))
            #`(+ a b))))))))

So, is there ar real difference between the concatenative (string)
rewriter and the tree rewriter? Not really. The only problem is that
for a tree rewriter which optimizes applications, the appropriate
rules for lambda rewriting need to be implemented. The only difference
is thus convenience: this kind of stuff is easier to do in
concatenative languages due to absence of names.

  * Concatenative languages: non-primitives can be expanded as a
    concatenation of primitives, which are simply applied in order.

  * Lambda languages: non-primitives need to implement the usual
    lambda reduction mechanics.

So, partial evaluation of pure lambda expressions is actually not so
difficult: if you start from normal order reduction, just reduce
things that can be reduced for a certain expression.

So.. Applied to the case of image processors. If they can be written
as pure expressions, making evaluation order irrelevant, a program is
easily specialized:

       1. library of primitives + combinator HOFs
       2. specialized expressions

   -> eliminate all applications of HOFs to yield a single expression

So, really, this seems quite straightforward. Am I missing something?
Yes. This does not include deforestation (or, the simplified version
for image data structures).

  * write a lambda expression reducer
  * obtain rewrite rules for image HOFs
  * alternatively, formulate it in a concatenative language to avoid
    the lambda reducer.