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) +
(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
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.