Mittwoch, September 03, 2008

Multi-Stage Programming in Scheme

Vor nicht allzu langer Zeit habe ich mich in einem Beitrag mit "Multi-Stage Programming" (MSP) beschäftigt. Ich warf in dem Blog-Posting die Frage auf, ob MSP im Grunde nicht mit der Makroprogrammierung wie z.B. in Scheme oder Lisp vergleichbar sei.

In der Tat kann das MetaOCaml-Beispiel, die Auflösung der Power-Funktion, sehr leicht mit defmacro, dem Urmakro aus Lisp, in Scheme nachgebildet werden. Hier kommt PLT-Scheme zum Einsatz -- mit Dank an Tim für den Code:

(require (lib "defmacro.ss"))
; POWER MACRO
(define-macro power
(lambda (n x)
(if (= n 0)
'1
`(* ,x (power ,(- n 1) ,x)))))
(power 2 4)

Stellt man dem Code in PLT-Scheme noch ein

(require (lib "../macro-debugger/expand.ss"))

voran und gibt dann interaktiv ein

(expand/step '(power 2 2))

ein, dann öffnet sich ein Fenster zum schrittweisen Makroauflösen. Ich habe ein wenig mit den Check-Boxen experimentiert: Mit "Enable macro hiding?" und "Hide mzscheme syntax" sieht die Auflösung unkryptisch aus.

Nun lese ich die Tage von Oleg Kiselyov etwas über "MetaScheme, or untyped MetaOCaml". In seinem Beitrag implementiert er "the four MetaOCaml special forms -- bracket, escape, cross-stage persistence (aka `lift'), and run -- in R5RS Scheme." Er argumentiert, dass eine 1:1-Übersetzung der MetaOCaml Special Forms in Scheme ("MetaOCaml's bracket is like quasiquote, escape is like unquote, and `run' is eval") nicht zum gewünschten Ergebnis führt. Vor allem übersieht Scheme die Bindungsstrukturen, die MetaOCaml natürlich sauber berücksichtigt.

Kiselyov bietet die MetaOCaml Special Forms als Macros für R5RS an, die nun dasselbe Verhalten zeigen wie die Special Forms in MetaOCaml. Eine beeindruckende Lösung, die -- wie alles bei Kiselyov -- ein tiefes Verständnis für Scheme aufweist. Sie verrät aber auch, wie MSP implementiert werden kann.

Eine Einsicht bleibt dennoch: Macros sind der Fast Track zu MSP in Scheme bzw. Lisp -- ohne Netz und doppelten Boden.

Keine Kommentare: