#+TITLE:     Macros for Patzers By A Patzer
#+AUTHOR:    Earl Spillar
#+EMAIL:     espillar@mac.com
#+DATE:      2011-07-27 Sun
#+DESCRIPTION:
#+KEYWORDS:
#+LANGUAGE:  en
#+OPTIONS:   H:3 num:t toc:t \n:nil @:t ::t |:t ^:t -:t f:t *:t <:t
#+OPTIONS:   TeX:t LaTeX:t skip:nil d:nil todo:t pri:nil tags:not-in-toc
#+INFOJS_OPT: view:nil toc:nil ltoc:t mouse:underline buttons:0 path:http://orgmode.org/org-info.js
#+EXPORT_SELECT_TAGS: export
#+EXPORT_EXCLUDE_TAGS: noexport
#+LINK_UP:   
#+LINK_HOME: 
#+XSLT:
#+LaTeX_CLASS: beamer
#+LaTeX_CLASS_OPTIONS: [presentation] 
#+BEAMER_FRAME_LEVEL: 2
#+BEAMER_HEADER_EXTRA: \usetheme{Madrid}\usecolortheme{default} 
#+COLUMNS: %35ITEM %10BEAMER_env(Env) %10BEAMER_envargs(Args) %4BEAMER_col(Col) %8BEAMER_extra(Ex)


* Lisp Macro System
** Macros as Substitutions
- Most simply,  macros are pre-compile time substitutions,
  programmable in lisp 
- Example: (from "On Lisp"):
#+begin_src lisp
(defmacro nil! (var)   
      (list ’setq var nil)) 
#+end_src
- expands as follows:
#+begin_src lisp
(nil! aVar) =>
(setq aVar nil)
#+end_src

- Paraphrased in English, this definition tells Lisp: “Whenever you
  see an expression of the form (nil! var), turn it into one of the
  form (setq var nil) before compiling/evaluating it.”
** Some Basics
- This happens at macro expansion time, before compile/interpret time
- It's essential that we have (something like) lists to enable this
- Homoiconic:  "the primary representation of programs is also a data structure in a primitive type of the language itself"
** Said another way
- Macros are essentially allowing you to write "arbitrary" lisp code which
  operates on the s-expressions before they are passed to the compiler
- "There are no semantics behind the syntax" of the s-expr we are munging
- Multiple macros will be handled recursively (repeatedly).
- Execution/runtime based on the macro-expanded code.
- Each chunk code may be run many times.
  
** Tools "for" macros
*** Lisp has several tools useful in macros
(It took me a while to realize some of these could be used outside of macros!)
*** It would be painful to build lists using things like (list ...)
*** Of course forward quote make literal lists more succinct. 
#+begin_src lisp
(list a  c d)
'(a b c d)
#+end_src
** Back Quotes and Splicing
*** In a macro, we frequently want to evaluate some lisp to create the list we are forming at macro expanstion time.  
*** Back quotes with comma splices give us a way to evaluate things within a list:
#+begin_src lisp
`(1 2 3 ,(+ 2 2))
=> (1 2 3 4)
#+end_src
*** In words, 
Create the list we are as if it were literal, but evaluate the sexpr
after the comma at macro expansion time using the full majesty that is lisp!

** Splicing
*** Sometimes we would like to "splice in" a whole list: use ,@ splice
#+begin_src lisp    
(defparameter b '(4 5 6))
`(1 2 3 ,@b)
(1 2 3 4 5 6)
#+end_src
*** Implement like this:
#+begin_src lisp
(defmacro sum ( &body body)
           `( + ,@body ))
Yields:
(sum 1 2 30) => 33
(sum 4 5 1 4 2) => 16
#+end_src

* Uses
** Conventional Uses
- We'll discuss each in turn:
- Providing cosmetics- simplifying code
- Introducing binding constructs 
- Implementing “control operators”, i.e., ones that alter the order of
  evaluation 
- Defining Domain Specific Languages (DSLs)

** Simplification of Code
- An example from Land of Lisp: get rid of one layer of parens:
#+begin_src lisp
(defmacro let1 (var val &body body)   
   `(let ((,var ,val))
   ,@body))
#+end_src 

- This allows us to do things like this:
#+begin_src lisp
(let1 a 2 (+ (* a 3) 4)) => 10
#+end_src
** Anaphoric macros- macros that create new variables
*** Macros can do some "prep work" for functions that you feed them
*** Anaphoric macros create some new variables used by the body function:
#+begin_src lisp
(defmacro split (val fun)
     `(let ((1st (car ,val)) (2nd (cdr ,val)))
         ,fun))

(split (cons 4 5) (* 1st 2nd)) 
=> 20
#+end_src
** Introducing New Control and Data Structures
*** There are many examples given of doing things like re-creating cond or other structures
*** Basically, you are able to "re-call" the compiler at "run-time", and change the parsing
*** We are doing things at "run time" that (most) languages only do at "compile time"
*** Rather than an example, lets look in the Common Lisp Quick Reference for examples-

** Domain Specific Languages
*** Macros can be used to re-arrange syntax and create little languages that are appropriate for a particular problem domain
** Stepping Through Expansions
***  ( macroexpand arg) expands it's argument and returns the
  expanded argument.
#+begin_src lisp
(macroexpand '(split (cons 3 4) (* 1st 2nd)))
(LET ((1ST (CAR (CONS 3 4))) (2ND (CDR (CONS 3 4))))
  (* 1ST 2ND))
T
#+end_src
*** (macroexpand-1) only does the first expansion, rather than performing recursives subsitutions like macroexpand
    
* Macro Pathologies
** Variable Capture
- You may accidentally create an "extra version" of a variable inside
  you macro.
#+begin_src lisp
(defmacro for ((var start stop) &body body)
   `(do ((,var ,start (1+ ,var))
       (limit ,stop))
       ((> ,var limit))
     ,@body))
#+end_src
#+begin_src lisp
(macroexpand '(for (limit 1 5) princ limit))  =>
(do ((limit 1 (1+ limit)) (limit 5))
     ((> limit limit)) (princ limit))
#+end_src
- We have a variable name clash!!
** Variable Capture Continued
- Note anaphoric macros use this "problem" to good effect!
- One solution is to use something like gensym to create a new name
  automagically: ( gensym ) -> #:G3422 (a unique variable name)
- Hygnic macros solve this, to a certain extent- see Scheme Macros
#+begin_src lisp
(defmacro split (val yes no) 􏰀 
     (let1 g (gensym)  `(let1 ,g ,val
         (if ,g (let ((head (car ,g))
                (tail (cdr ,g))) ,yes)
          ,no))))
#+end_src
** Obscurity
- Macros are more difficult to write then functions
- They (can) change syntax in unusual ways.
- So, other programmers (and even you!) will have a harder time
  understanding your code.
- Sometimes you DO want to create "your own language," these languages
  are called DSLs: Domain Specific Languages
* Scheme Macros
** Quick tour of basic scheme Macros
*** The scheme community is moving ahead quickly on more advanced macro schemes
*** I will discuss the simplest R5RS scheme macro system
*** Chez Scheme and others are more advanced!
*** Unfortunately, this leads to a little balkanization
** define-syntax, let-syntax, letrec-syntax
*** These three are similar except for scope-
Top level, let like, and letrec like.
*** They define that a sexpr with a particular head will be expanded
*** How they will expand is defiend by the <syntax transformer> (next)
#+begin_src lisp
;; define-syntax creates a top-level binding
(define-syntax macro-head  <syntax transformer>)
#+end_src 
** syntax-rules (1)
*** syntax-rules transform the sexpr
*** templates make the changes easier
*** Simplest version:
#+begin_src lisp
(define-syntax first 
  (syntax-rules ()
    (( _ aCons) (car aCons))))

> ( first (cons 1 2))
1
#+end_src
** syntax-rules (2)
*** Multiple templates are allowed-
#+begin_src lisp
(define-syntax first-2
  (syntax-rules ()
    (( _ aCons) (car aCons))
    (( _ aCons bCons) (car bCons))
    ))
> (first-2 (cons 1 2) (cons 3 4))
3
> (first-2 (cons 1 2))
1
#+end_src
** syntax-rules (3)
*** Keywords can be included  as follows:
#+begin_src lisp
(define-syntax first-2
  (syntax-rules (sec)
    (( _ aCons) (car aCons))
    (( _ aCons bCons) (car bCons))
    (( _ sec aCons bCons) (cdr bCons))
    ))

> (first-2 sec (cons 1 2) (cons 3 4))
4
#+end_src
** Macros are Hygenic!
*** The "local variables" in the macros are "Hygenic"
*** That is, they WILL NOT shadow variables in the expression being expanded
*** Essentially the (gensym) is "baked in"
* In Closing
** Questions for the Crowd
*** Why do folks say Haskell can get away without macros?
*** What are the objects that macros are manipulating? Symbols? Strings?
** References
All available on line!
- On Lisp: advanced techniques for Common Lisp.  Paul Graham.  http://www.paulgraham.com/onlisptext.html.
- Common Lisp Quick Reference http://clqr.berlios.de/
- Scheme Macros http://blog.willdonnelly.net/2008/09/04/a-scheme-syntax-rules-primer/
- Automata via Macros http://www.cs.brown.edu/~sk/Publications/Papers/Published/sk-automata-macros/paper.pdf
- Scheme Macros http://www.scheme.com/tspl4/