guile-examples/macros/CK-macros/ck-macro.scm

;; Code from http://okmij.org/ftp/Scheme/macros.html#ck-macros

;; Added: A lot of comments trying to explain how this CK-machine
;; works.

;; The macro implements a stack based machine. It internally manages a
;; stack. It uses syntax-rule to build this stack based machine. So it
;; uses facilities, which are described as not composing well, to
;; build a foundation for something that does compose well. Some sort
;; of building from minimalistic concepts. Really clever stuff.

;; The macro performs evaluations of the stack elements towards the
;; goal of expanding ck-macros recursively.

;; Meaning of the identifiers:
;; - s:   stack
;; - op:  name of a CK-macro to do the reduction
;; - va:  zero or more values
;; - v:   a single value
;; - ea:  zero or more arbitrary expressions
;; - ea1: one arbitrary expression

;; ===========
;; Explanation
;; ===========

;; The macro uses s, the stack. A stack frame on this stack looks as
;; follows:

;; ((op va ...) ea ...)

;; So basically there is a call to a CK-macro on top of the stack
;; being "destructured" into some parts:

;; a CK-macro -- op
;; zero or more values -- va ...
;; other arbitrary expressions -- ea ...

;; To evaluate, the core CK-macro needs to evaluate the other
;; arbitrary expressions.

;; ----------------------------------
;; WHAT DOES CHICKEN SCHEME WIKI SAY?
;; ----------------------------------
;; http://wiki.call-cc.org/eggref/5/ck-macros#what-are-ck-macros:

;; > Quoting is how the core ck macro knows the difference between a
;; value and a CK-macro call. Therefore, all values must be quoted,
;; even values which normally do not need to be quoted in Scheme code,
;; such as strings, numbers, and booleans.

;; > The core ck macro expands the input arguments ahead of time, so
;; the arguments will always be quoted values by the time your macro
;; is expanded.

;; > The quoted value is either used as an argument to another
;; CK-macro, or if your CK-macro is the outer-most CK-macro call, then
;; the core ck macro expands into the unquoted value.

;; > Eventually, your CK-macro must expand into a call to the core ck
;; macro with a quoted value.

(define-syntax ck
  ;; Declaring quote as literal means, that whenever a quote is
  ;; encountered in a match expression, it cannot be a placeholder for
  ;; something else, but is expected to be exactly quote and nothing
  ;; else. It is literally quote, that is why it is called a literal.
  (syntax-rules (quote)
    ;; CASE 1: EMPTY STACK

    ;; "yield the value on empty stack"

    ;; If there is nothing more to evaluate, simply return the value.
    ;; The value is unquoted!
    ((ck () 'v) v)

    ;; CASE 2: ??? TODO

    ;; "re-focus on the other argument, ea"

    ;; Match structure:
    ;; - call to the ck macro with
    ;;   - something: (((op ...) ea ...) . s)
    ;;     - a stack frame?: ((op ...) ea ...)
    ;;     - the rest of the stack now bound to s
    ;;   - and a single value: 'v

    ;; Question: Why do we focus the ea and not the arguments of op?

    ;; Question: How does (op ...) work in matching of syntax-rules?

    ;; Answer: When the ellipsis ... follows some identifier, it
    ;; means, that there can be 0 or more things in the input to match
    ;; the identifier. In the output of the match case these things
    ;; are put where the ellipsis following the same identifier in the
    ;; output is.

    ;; Question: Why is this "arg" thing added?

    ;; Beginning of an answer: We match anything that has the following structure:
    ;; 1. An arbitrary number of things including the CK-macro op.
    ;; 2. At some point an arbitrary number of arbitrary expressions starts.
    ;; This is a very general matching it seems.
    ;; 1: the top-most stack frame is destructured as ((op ...) ea ...)
    ;; 2: s is rest of the stack.

    ;; Question: Why is 'v outside of the stack?

    ;; Answer: 'v represents the input of the called CK-macro.

    ;; Question: Why is ea already outside of the op call parentheses?

    ;; Answer: ???
    ((ck (((op ...) ea ...) . s) 'v)
     (ck s "arg" (op ... 'v) ea ...))

    ;; CASE 3: SINGLE CK-MACRO WITH ARGUMENTS REMAINING

    ;; "all arguments are evaluated do the redex"

    ;; I have no idea what exactly a redex is, but when all CK-macros
    ;; are evaluated, there is no need for recursively evaluating more
    ;; macros and we have a non-CK-macro expression left. This we
    ;; output as part of the over-all CK-macro expansion / evaluation
    ;; process. This is probably the step before the stack is empty.

    ;; Question: What is a redex?

    ;; Answer: Redex is short for "reducible expression". So when Oleg
    ;; writes "do the redex", he probably means, that we evaluate the
    ;; CK-macro that is op. That will be another expansion step, which
    ;; is some kind of "reduction", thus reducing the expression of
    ;; calling op.
    ((ck s "arg" (op va ...))
     (op s va ...))

    ;; CASE 4: TAKE A VALUE BACK INSIDE THE CALL TO OP AS ARGUMENT.

    ;; "optimization when the first ea was already a value."

    ;; 1: quote is declared a literal in this syntax-rules macro. As
    ;; written in the Chicken Scheme wiki, quoted things are
    ;; recognized by the ck core macro as values. Matching against a
    ;; literal quote ensures, that the identifier is really bound to a
    ;; value.

    ;; 2: ea1 could probably also be named simply ea, as it does not
    ;; ensure, that there is at least 1 arbitrary expression. However,
    ;; it is conceptually not the same, as it is not the whole
    ;; sequence of things, but the sequence minus the first element,
    ;; which is matched by 'v.

    ;; Question: Why is the 'v taken "inside", as an argument to the
    ;; macro call op?

    ;; Answer: "arg" actually indicates, that 'v was an argument
    ;; before this expansion step! So it _must_ be moved back inside
    ;; the call of op, after making sure it is expanded and a value!
    ;; Once it is expanded to a value (meaning it is quoted), the CK
    ;; machine does not need to expand it more.
    ((ck s "arg" (op ...) 'v ea1 ...)
     (ck s "arg" (op ... 'v) ea1 ...))

    ;; CASE 5: ???

    ;; "focus on ea, to evaluate it"

    ;; 1: ((op ...) ea1 ...) is put on top of the stack.
    ;; 2: ea stays outside the op parentheses.
    ((ck s "arg" (op ...) ea ea1 ...)
     (ck (((op ...) ea1 ...) . s) ea))

    ;; CASE 6: PREPARE TO EVALUATE ARGUMENTS

    ;; "Focus: handle an application; check if args are values"

    ;; Question: Why is this "arg" thing added?

    ;; Answer: ea ... are the arguments to the call of the CK-macro
    ;; op. If they are macros themselves, they need to be expanded
    ;; before op is evaluated. Thus they are moved outside the call
    ;; and the fact, that they are arguments of the call is denoted by
    ;; the "arg" string.
    ((ck s (op ea ...))
     (ck s "arg" (op) ea ...))))