Tuesday, October 22, 2013

Multi-Stage Programming in Lisp

I have been reading up on MSP recently, and trying to grok the examples in Walid Taha's Gentle Introduction. When all you have is a Lispy hammer, every problem calls for a program with parentheses, so the next order of business is to find Lisp equivalents of Bracket, Escape and Run.

'Run' is trivial; to run a Lisp program, we evaluate expressions; so 'eval' it is.

'Escape' is for dropping in actual values into placeholders, so a comma seems appropriate. However, a comma has to occur within the context of a backquote, so it seems we're stuck. But wait, an Escape has to occur within the context of a Bracket, so maybe we can use backquotes for Brackets? Further analysis, in the form of seeing how well the two words rhyme, proves that backquotes are indeed the equivalents of Brackets in Lisp.

I went through a slightly more involved process in arriving at the above mapping, but this version of the story is a lot more fun.

Without further ado, here is the famous MSP power example in Lisp:

CL-USER> (defun mypower (x n)
           (if (eq n 0)
               `(* ,x ,(mypower x (- n 1)))))

CL-USER> (mypower 10 3)
(* 10 (* 10 (* 10 1)))

CL-USER> (eval (mypower 10 3))

Yeah, we're missing the well-typed and well-formed guarantees, but Lisp's 'code-is-data' proves its worth once again. And we're not even using macros.

If we want to bring more structure to the staged expressions, we can express them as, say, closures. That's probably a topic for a future post.

I still have a lingering doubt whether we have accomplished truly multi-stage programming, seeing how trivial it has been to implement.

On a related note, what's common between the power and the logger functions? They are the only use cases that provide credibility to their respective patron saint programming paradigms, viz. MSP and aspect oriented programming. Just kidding.

With all the recent changes at the helm, can we expect less of full front-page real estate ads promising free gold coins?