wiki:Bootstrapping1

How Lisp's features are related to the capacity of defining DSLs?

First of all, we need first-class high-order procedures.

Actually, it goes a bit deeper - because every symbol is a reference (a pointer) to some value (NOT an object, just a value) then everything, every value that we could bind a symbol to is first-class. This is a consequence of the uniform, general rule - everything is a pointer.

Another important moment - symbols are just symbols (they are mere names, labels attached to a value) it is a value itself that has a type. Type is attached to a value as a tag.

Logically, each value has zero (when a self-evaluated value - which represent a number or a string - is used explicitly), one or many names (symbols) associated with it, and one or more type-tags attached to it. This is also uniform, general rule.

Together we have very unique trait of Lisps - we could reference and pass everything everywhere, and types are checked at run-time, so, no, it won't add 3 to "4".

Functions, then, are just values with some type-tag attached, which gives to a compiler (or an interpreter) information that this value is a function.

Let's see how it works. Remember what a special form is logically? It is a Lisp expression which has its own, unique evaluation rule, which is different from the uniform general evaluation rule for all Lisp expressions (which is: 1. eval all the given arguments in order. 2. apply the procedure (which is always in the car of an expression list) to the values of the arguments).

There is a special form called do (or begin, or progn)

The special form do (do forms) is equivalent to an in-place invocation of a lambda expression containing given forms as its body ((lambda () (forms))

Remember what is a macro logically? It is a procedure that perform a syntactic transformation of a lisp expression at read-time, which is just a stage (a pass) before compile-time and run-time. It produces new Lisp expressions, which are semantically equivalent, to be compiled (or interpreted).

Now what is a macro technically?)

in Arc it is just a procedure, annotated with type-tag 'mac

(assign do (annotate 'mac
             (fn args `((fn () ,@args)))))

So, a macro is just a lambda (what else could it be?'')

In classic Scheme it could be

(define-syntax do
   (sc-macro-transformer
       (lambda (exp env)
          `((lambda () ,@(cdr exp))))))

where this ,@(...) form is just "unquote-splicing this in-place created list".

Let's do it again slowly. This time we will define the let special form.

Have you already realized why we are bothering with all this - macros are the way to add new control structures (special forms) into the language. This is the first glimpse of real power of Lisp - it is a layer upon a layer of DSLs, where each new DSL is written in terms of previous ones. The Lisp itself is just a very few special forms lambda define if set! and primitive procedures cons car cdr pair? null? which are used to create (glue together) any kind of compound data structures. and read eval apply quasi-quote unquote, etc.. which are at the core of a Lisp.

Let's add let to a Lisp.)

; the local binding form
(let ((x 1)) x)
1

; is equivalent to implicit invocation of a lambda with corresponding parameters
((lambda (x) x) 1)
1

; a syntax transformation, such that expression
(let ((x 1) (y 2)) (+ x y))
3

; becomes
((lambda (x y) (+ x y)) 1 2)      ; is called Macro Transformation
3

Let's understand the structure of a let expression.

; bindings is a list of pairs, where car is a symbol and cdr is a value
'((a 1) (b 2))

; to get a list of symbols
(map car '((a 1) (b 2)))

; to extract a list of values
(map cadr '((a 1) (b 2)))

Now lets write this syntactic transformation in terms of what we have

(lambda (bindings . body)
   `((lambda ,(map car bindings)
        ,@body) ,@(map cadr bindings)))

This is "close to an ideal", not yet complicated or cluttered definition of a procedure which perform a syntactic transformation, by manipulating Lisp forms at the read-time.

Now we must somehow annotate it as a macro, which means to tag it with the type (tag) "macro" - so it would be recognized as a read-time instead of run-time procedure.

Unfortunately, classic Scheme has this wired syntax

; too much boilerplate, too cumbersome, redundant let, non-intuitive destructuring.

(define-syntax lett
  (sc-macro-transformer
    (lambda (exp env)                               ; evaluate exp in env
       (let ((bindings (cadr exp))                  ; destructuring
             (body     (cddr exp)))
          `((lambda ,(map car bindings)
               ,@body) ,@(map cadr bindings))))))

Logically we cannot use let for in the definition of let, so

(define-syntax lett
  (sc-macro-transformer
    (lambda (exp env)                                 ; always the same parameter list
       `((lambda ,(map car (cadr exp))                ; ugly in-place destructuring
           ,@(cddr exp)) ,@(map cadr (cadr exp))))))

While in Arc it is just

(mac lett (bindings . body)
           `((fn ,(map1 car bindings)
                ,@body) ,@(map1 cadr bindings)))

which is much more intuitive, clean and beautiful, as it supposed to be within Lisps.

Last modified 7 years ago Last modified on Dec 27, 2013, 4:45:12 AM
Note: See TracWiki for help on using the wiki.