You are looking at historical revision 33159 of this page. It may differ significantly from its current revision.

ck-macros

Composable Scheme macros based on the CK abstract machine.

The ck-macros egg provides Oleg Kiselyov's CK-macro system, describe in the article, Applicative syntax-rules: macros that compose better.

This egg provides version 1.1 (April 2011) of the core ck macro, which is the latest version as of this writing. This egg also provides many useful (and some not-so-useful) predefined CK-macros.

If you create a useful or interesting general-purpose CK-macro, or an improvement to an existing CK-macro, please contact the maintainer so your contribution can be added to the library. All source code (including contributions) is public domain.

Project / Source Code Repository
https://gitlab.com/jcroisant/ck-macros
Author
Oleg Kiselyov, with additional CK-macros and documentation by John Croisant
Egg Maintainer
John Croisant
License
Public Domain

Table of Contents:

What are CK-macros?

CK-macros are Scheme macros written to be compatible with with the core ck macro.

The core ck macro is a syntax-rules macro which implements the CK abstract machine. The CK abstract machine is a computational model described by Matthias Felleisen and Daniel P. Friedman in the paper, "Control Operators, the SECD-Machine, and the Lambda-Calculus". Fortunately, you don't need to understand the paper in order to create or use CK-macros!

Basically, the core ck macro does some clever rearranging to expand the CK-macro's arguments, allowing you to easily combine simple reusable macros to form more complex macros. This is very similar to the way Scheme makes it easy to combine simple resuable functions (map, fold, cons, etc.) to create more complex functions. In fact, many useful Scheme functions can be translated to CK-macros, allowing you to achieve the same effect at macro-expansion time!

CK-macros give you a lot of control over the macro expansion process, which allows you to implement many kinds of macros much more simply than you could with traditional style syntax-rules macros. You can even implement "higher-ordered macros" which take a macro as an argument. See c-map and c-fold for examples of higher-ordered macros.

CK-macros are not as flexibile or powerful as CHICKEN's explicit and implicit renaming macros, but CK-macros are much more portable. The core ck macro and most CK-macros are implemented using only syntax-rules, which means they will work on any implementation of R5RS or later.

How to write CK-macros

Here is a basic template for CK-macros:

(define-syntax c-foo
  (syntax-rules (quote)
    ((c-foo s 'input1 'input2 ...)
     (ck s output))))

As you can see, a CK-macro is a macro that expands into a call to the core ck macro. The core ck macro does some clever rearranging under the hood to support composition with other CK-macros.

CK-macros are usually defined using syntax-rules for maximum portability. But, it is also possible to write CK-macros using other macro systems, such as CHICKEN's explicit and implicit renaming macros, as long as those macros expand into a call to the core ck macro.

By convention, the names of CK-macros usually start with "c-", to distinguish them from non-CK macros or procedures with similar names. But, this naming convention is not required.

CK-macros treat quoting specially, so you should include quote in the first argument to syntax-rules, the list of literal identifiers.

The first argument to every CK-macro must be the stack, usually called s. The stack is used by the core ck macro to do its clever rearranging. Your CK-macro should not touch the stack, just pass it through to the core ck macro.

Each 'input is an argument passed to your macro. The core ck macro expands the arguments ahead of time (unless the argument is quoted), so the arguments will always be quoted values by the time your macro is expanded. Usually CK-macros are defined with their arguments quoted (as above), so that you can easily extract the unquoted value to use in your macro.

Your macro should transform the inputs in some way to produce the output, which is passed to the core ck macro. The output must be either:

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.

Eventually, your CK-macro must expand into a call to the core ck macro with a quoted value. We say that the macro "yields" this quoted value. 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.

So, if your CK-macro yields the quoted value '(+ 1 2), and it is the outer-most CK-macro (not an argument to another CK-macro), the core ck macro will expand to the unquoted expression (+ 1 2), which would later be evaluated to the number 3. (If you want to yield a quoted form as the final result, use c-quote as the outer-most CK-macro.)

See the original article or the source code for many examples of CK-macros.

Combining CK-macros with non-CK macros

All CK-macros must evenutally expand to a call to the core ck macro. Therefore, many non-CK macros cannot be used inside CK-macros.

But, it is always possible to write a non-CK macro which calls invokes a CK-macro. For example, if you are writing a macro for other people to use, you can create a convenience wrapper macro, like so:

;;; Convenience wrapper around c-foo.
(define-syntax foo
  (syntax-rules ()
    ((foo arg1 arg2 arg3)
     (ck () (c-foo 'arg1 'arg2 'arg3)))))

Also, it is always possible for a CK-macro to expand into a call to a non-CK macro as its final result. For example:

;;; Non-CK macro
(define-syntax bar
  (syntax-rules ()
    ((bar a b c)
     (+ a (* b c)))))

;;; CK-macro
(define-syntax c-fiz
  (syntax-rules (quote)
    ((c-fiz s 'a 'b 'c)
     (ck s '(bar a b c)))))

(ck () (c-fiz '1 '2 '3))
;;; Expands to the expression (bar 1 2 3),
;;; which expands to the expression (+ 1 (* 2 3)),
;;; which evaluates to the number 7.

Finally, some non-CK macros can be used in a way that expands into a user-provided expression. These non-CK macros can therefore be used inside CK-macros, as long as they eventually expand into a call to the core ck macro.

ck

[syntax] (ck s 'v)
[syntax] (ck s (op ...))

This is the core ck macro, which implements the CK abstract machine. This macro's public interface has two shapes: one with a quoted value, and one with a CK-macro call.

s
The stack, used internally by this macro. When initially invoking this macro, s should be the empty list, e.g. (ck () (c-cons '+ '(1 2))).
'v
A quoted value. Can be a quoted list, symbol, or other literal value. The quote is necessary, even for literal values like strings, numbers, and booleans.
(op ...)
A CK-macro call without the s argument, such as (c-cons '+ '(1 2)).

Portable CK-Macros

The CK-macros in this section are defined using only standard R5RS features, such as syntax-rules and let-syntax. Therefore, these CK-macros will work with any implementation of R5RS or later.

General

[syntax] (c-quote X) → 'X

Adds an extra level of quotation to the argument. This is useful for macros that should expand to a quoted value.

;; Without c-quote
(ck () (c-cons '+ '(1 2)))
;; Expands to (+ 1 2), which evaluates to the number 3.

;; With c-quote
(ck () (c-quote (c-cons '+ '(1 2))))
;; Expands to '(+ 1 2), a quoted list.
[syntax] (c-eval '(OP ...)) → result

Takes a quoted operation and unquotes it, allowing the CK machine to expand it. Analogous to eval.

(ck () (c-quote (c-eval '(c-cons 'a 'b))))
;; ==> '(a . b)
[syntax] (c-call '(OP ...) X ...) → result

Like c-eval, but adds the given arguments on to the end of the operation. Analogous to a lambda call in normal Scheme code.

(ck () (c-quote (c-call '(c-cons 'a) 'b)))
;; ==> '(a . b)
[syntax] (c-apply '(OP ...) X ... '(Y ...)) → result

Like c-call, but the last argument is a list of more arguments. Analogous to apply.

(ck () (c-quote (c-apply '(c-list) 'a 'b '(c d))))
;; ==> '(a b c d)
[syntax] (c-identity X) → X

Simply yields the value as given. Sometimes useful for higher-order macros like c-filter.

(ck () (c-quote (c-identity 'a)))
;; ==> 'a

Boolean Logic

[syntax] (c-not X) → '#t or '#f

Yields '#t if the argument is '#f, otherwise yields '#f. Analogous to not.

[syntax] (c-if TEST PASS FAIL) → PASS or FAIL

Conditional branching. Yields FAIL if TEST is '#f (or an operation that yields '#f). Otherwise yields PASS.

Due to the way the CK machine works, both branches will be expanded, then the unneeded branch will be discarded. If you only want the needed branch to be expanded (e.g. because the branches are complex and slow to expand, or because it would be an error to expand the unneeded branch), use c-if/q instead.

Analogous to (lambda (test pass fail) (if test pass fail)).

(ck () (c-quote (c-if (c-pair? '(x))
                      'pair
                      'not-pair)))
;; ==> 'pair

(ck () (c-quote (c-if (c-pair? 'x)
                      'pair
                      'not-pair)))
;; ==> 'not-pair
[syntax] (c-if/q 'TEST 'PASS 'FAIL) → PASS or FAIL

Similar to c-if, except that all the arguments must have an extra level of quoting, and only one branch will be expanded. This is more similar to how if behaves, but it is a bit awkward to use.

Analogous to (lambda (test pass fail) (if (eval test) (eval pass) (eval fail)))

(ck () (c-quote (c-if '(c-pair? '(x))
                      '(c-car '(x))
                      ''not-pair))
;; ==> 'x

(ck () (c-quote (c-if '(c-pair? 'x)
                      '(c-car 'x)
                      ''not-pair))
;; ==> 'not-pair
[syntax] (c-or X ...) → item or '#f

Yields the first argument that is not '#f. Yields '#f if all of the arguments are '#f, or if there are no arguments.

Roughly analogous to or, except all arguments are expanded. If you only want to expand the arguments that are needed, use c-or/q instead.

[syntax] (c-or/q 'X ...) → item or '#f

Similar to c-or, except that all the arguments must have an extra level of quoting, and the arguments will be expanded one at a time until a non-'#f value is found. This is more similar to how or behaves, but it is a bit awkward to use.

[syntax] (c-and X ...) → item or '#f

If all arguments are not '#f, yields the last argument. If any of the arguments is '#f, yields '#f. If there are no arguments, yields '#t.

Roughly analogous to and, except all arguments are expanded. If you only want to expand the arguments that are needed, use c-and/q instead.

[syntax] (c-and/q X ...) → item or '#f

Similar to c-and, except that all the arguments must have an extra level of quoting, and the arguments will be expanded one at a time until a '#f value is found. This is more similar to how and behaves, but it is a bit awkward to use.

[syntax] (c-null? X) → '#t or '#f

Yields '#t if X is the empty list, '(). Otherwise yields '#f. Analogous to null?.

[syntax] (c-pair? X) → '#t or '#f

Yields '#t if X is a dotted pair or a non-empty list. Otherwise yields '#f. Analogous to pair?.

[syntax] (c-not-pair? X) → '#t or '#f

Opposite of c-pair?. Analogous to not-pair? from SRFI-1.

[syntax] (c-boolean? X) → '#t or '#f

Yields '#t if X is either '#t or '#f. Otherwise yields '#f. Analogous to boolean?.

[syntax] (c-sym-eq? X Y) → '#t or '#f

Yields '#t if X and Y are the same symbol, otherwise yields '#f. X should be a symbol. Y can be any value. Some Scheme implementations allow X to be other types, but this macro is only portable if X is a symbol.

Roughly analogous to eq?, except it only works (portably) with symbols. Based on symbol-eq? from the article.

[syntax] (c-sym-equal? X Y) → '#t or '#f

Similar to c-sym-eq?, except it recursively compares lists and pairs.

Roughly analogous to equal?, except it only works (portably) with symbols, lists of symbols, and pairs of symbols.

List Processing

[syntax] (c-cons X Y) → pair

Yields a pair with the two given arguments. Analogous to cons.

(ck () (c-quote (c-cons '"a" '1)))
;; Expands to '("a" . 1).

(ck () (c-quote (c-cons '+ '(1 2))))
;; Expands to '(+ 1 2).

(ck () (c-quote (c-cons '+ (c-cons '1 (c-cons '2 '())))))
;; Also expands to '(+ 1 2).
[syntax] (c-list X ...) → list

Yields a list with the given arguments. Analogous to list.

[syntax] (c-car P) → item

Yields the head of the given pair. Analogous to car.

[syntax] (c-cdr P) → tail

Yields the tail of the given pair. Analogous to cdr.

[syntax] (c-first L) → item
[syntax] (c-second L) → item
[syntax] (c-third L) → item
[syntax] (c-fourth L) → item
[syntax] (c-fifth L) → item
[syntax] (c-sixth L) → item
[syntax] (c-seventh L) → item
[syntax] (c-eighth L) → item
[syntax] (c-ninth L) → item
[syntax] (c-tenth L) → item

Yields the Nth item of the given list. Fails if the list is too short.

Analogous to first ... tenth from SRFI-1.

(ck () (c-quote (c-first  '(a b c d e f g h i j k))))  ; ==> 'a
(ck () (c-quote (c-second '(a b c d e f g h i j k))))  ; ==> 'b
(ck () (c-quote (c-third  '(a b c d e f g h i j k))))  ; ==> 'c
;;; ...
(ck () (c-quote (c-tenth  '(a b c d e f g h i j k))))  ; ==> 'j
[syntax] (c-last L) → item

Yields the last value of the given list. Fails if the list is empty or is not a proper list.

Analogous to last from SRFI-1.

(ck () (c-quote (c-last '(a b c))))    ; ==> 'c
(ck () (c-quote (c-last '(a b . c))))  ; ==> ERROR!
[syntax] (c-last-pair L) → pair

Yields the last pair of the given list. Fails if the list is empty.

Analogous to last-pair from SRFI-1.

(ck () (c-quote (c-last-pair '(a b c))))    ; ==> '(c)
(ck () (c-quote (c-last-pair '(a b . c))))  ; ==> '(b . c)
[syntax] (c-drop1 L) → list
[syntax] (c-drop2 L) → list
[syntax] (c-drop3 L) → list
[syntax] (c-drop4 L) → list
[syntax] (c-drop5 L) → list

Drops a predefined number of items from the front of the given list. Fails if the list is too short.

Analogous to (drop L N) from SRFI-1. See also c-udrop.

(ck () (c-quote (c-drop1 '(a b c d e f g))))  ; ==> '(b c d e f g)
(ck () (c-quote (c-drop2 '(a b c d e f g))))  ; ==> '(c d e f g)
(ck () (c-quote (c-drop3 '(a b c d e f g))))  ; ==> '(d e f g)
(ck () (c-quote (c-drop4 '(a b c d e f g))))  ; ==> '(e f g)
(ck () (c-quote (c-drop5 '(a b c d e f g))))  ; ==> '(f g)
[syntax] (c-take1 L) → list
[syntax] (c-take2 L) → list
[syntax] (c-take3 L) → list
[syntax] (c-take4 L) → list
[syntax] (c-take5 L) → list

Yields a list containing a predefined number of items from the front of the given list. Fails if the list is too short.

Analogous to (take L N) from SRFI-1. See also c-utake.

(ck () (c-quote (c-take1 '(a b c d e f g))))  ; ==> '(a)
(ck () (c-quote (c-take2 '(a b c d e f g))))  ; ==> '(a b)
(ck () (c-quote (c-take3 '(a b c d e f g))))  ; ==> '(a b c)
(ck () (c-quote (c-take4 '(a b c d e f g))))  ; ==> '(a b c d)
(ck () (c-quote (c-take5 '(a b c d e f g))))  ; ==> '(a b c d e)
[syntax] (c-reverse L) → list

Yields the given list in reverse order. Fails if the list is not a proper list. Analogous to reverse.

[syntax] (c-suffix L X ...) → list

Yields the given list with the extra arguments added to the end. (c-suffix '(1 2) '3 '4) is equivalent to (c-append '(1 2) '(3 4)).

[syntax] (c-append L1 L2) → list

Appends the two given lists. Analogous to append.

(ck () (c-quote (c-append '(define foo) '((+ 1 2)))))
;; ==> '(define foo (+ 1 2 3))

(ck () (c-quote (c-append '(+) (c-append '(1) '(2)))))
;; ==> '(+ 1 2)
[syntax] (c-append-map '(OP ...) L) → list

Yields a list by calling the quoted operation on each item in the list, then appending the results. The operation must be a CK-macro that yields a list. The operation may have leading arguments.

Analogous to append-map from SFRI-1. This was named c-concatMap in the article.

(ck () (c-quote (c-append-map '(c-list 'a 'b) '(1 2))))
;; ==> '(a b 1 a b 2)
[syntax] (c-map '(OP ...) L) → list

Yields a list by calling the quoted operation on each item in the given list. The operation may have leading arguments. Analogous to map.

(ck () (c-quote (c-map '(c-cons 'a) '(1 2))))
;; ==> '((a . 1) (a . 2))
[syntax] (c-fold '(OP ...) INIT L) → result

Yield a value by repeatedly calling the quoted operation with each item from the list plus the previous result.

The operation is first called with two arguments, the first item of the list and the initial value. Then, the operation is called with the next item of the list and the previous result.

If list is empty, yields INIT.

Analogous to fold from SRFI-1.

[syntax] (c-filter '(OP ...) L) → list

Yields a list by calling the quoted operation on each item in the given list, and discarding any item for which the test yields '#f. Analogous to filter from SRFI-1.

[syntax] (c-remove '(OP ...) L) → list

Opposite of c-filter. Discards items that pass the test, keeps items that fail the test. Analogous to remove from SRFI-1.

[syntax] (c-find '(OP ...) L) → item or '#f

Yields the first item in the given list that passes the predicate operation (i.e. the predicate yields a non-'#f value). Yields '#f if no items pass the predicate.

Analogous to find from SRFI-1.

[syntax] (c-find-tail '(OP ...) L) → pair or '#f

Yields the first pair in the list for which the head of the pair passes the predicate operation (i.e. the predicate yields a non-'#f value). Yields '#f if no items pass the predicate.

Analogous to find-tail from SRFI-1.

[syntax] (c-sym-member X L) → '#t or '#f

Yields '#t if the list contains the given symbol, list of symbols, or pair of symbols, using c-sym-equal? for comparison. Otherwise yields '#f.

Roughly analogous to member.

[syntax] (c-any '(OP ...) L) → result or '#f

Calls the operation on each value in the given list until it finds a result that is not '#f, then yields that result. Yields '#f if the predicate yields '#f for all items in the list, or if the list is empty.

Analogous to any from SRFI-1.

[syntax] (c-every '(OP ...) L) → result or '#f

Calls the operation on each value in the given list until it finds a result that is '#f, then yields '#f. If the predicate yields a non-'#f value for every item in the list, this yields the result of calling the predicate on the last item. Yields '#t if the list is empty.

Analogous to every from SRFI-1.

[syntax] (c-assoc KEY ALIST) → pair or '#f
[syntax] (c-assoc KEY ALIST '(OP ...)) → pair or '#f

Yields the first pair in ALIST whose car matches KEY, or '#f if no match is found. Uses '(OP ...) for comparison, or '(c-sym-equal?) if '(OP ...) is omitted.

Analogous to assoc from SRFI-1.

[syntax] (c-alist-delete KEY ALIST) → list
[syntax] (c-alist-delete KEY ALIST '(OP ...)) → list

Removes all pairs in ALIST whose car matches KEY. Uses '(OP ...) for comparison, or '(c-sym-equal?) if '(OP ...) is omitted.

Analogous to alist-delete from SRFI-1. Based on c-delete-assoc from the article.

Unary Math

The CK-macros in this section perform mathematical operations by treating lists as unary numbers. Unary math is pretty slow for large values or complex operations, but it is interesting, portable, and maybe even useful in some cases.

Unary numbers are a way of representing non-negative integers as a list of a certain length. For example, the list '(a b c d e) means the number 5, and the list '() means the number 0. The contents of the list do not matter, only the length. Negative numbers and non-integral numbers cannot be represented in unary.

[syntax] (c-u= U1 U2) → '#t or '#f

Unary equality. Yields '#t if the two lists have the same lengths, otherwise yields '#f.

[syntax] (c-u< U1 U2) → '#t or '#f

Unary less-than. Yields '#t if the first list is shorter than the second list, otherwise yields '#f.

[syntax] (c-u<= U1 U2) → '#t or '#f

Unary less-than-or-equals. Yields '#t if first list is the same length or shorter than the second list, otherwise yields '#f.

[syntax] (c-u> U1 U2) → '#t or '#f

Unary greater-than. Yields '#t if the first list is longer than the second list, otherwise yields '#f.

[syntax] (c-u>= U1 U2) → '#t or '#f

Unary greater-than-or-equals. Yields '#t if first list is same length or longer than the second list, otherwise yields '#f.

[syntax] (c-uzero? U) → '#t or '#f

Unary zero?. Yields '#t if the list is empty, otherwise yields '#f. Same as c-null?.

[syntax] (c-ueven? U) → '#t or '#f

Unary even?. Yields '#t if the given list's length is even (i.e. a multiple of 2), otherwise yields '#f.

[syntax] (c-uodd? U) → '#t or '#f

Unary odd?. Yields '#t if the given list's length is odd length (i.e. not a multiple of 2), otherwise yields '#f.

[syntax] (c-u+ U1 U2) → list

Unary addition. Same as c-append. This was named c-add in the article.

[syntax] (c-u- U1 U2) → list

Unary subtraction. Drops an element from the front of the first list for each element in second list, then yields the remaining list. Negative numbers cannot be represented in unary, so this yields '() if the second list is equal or longer than the first.

[syntax] (c-u* U1 U2) → list

Unary multiplication. Yields a list containing the contents of the first list, repeated once for every item in the second list.

Based on c-mul from the article, except the symbol 'u has no special significance, and result is made from duplicating the first list.

[syntax] (c-u/ U1 U2) → list

Unary division. Yields a list of two unary numbers, representing the quotient and the remainder of the division.

Given the second list has length N, the quotient will contain every Nth item from the first list, and the remainder will contain the tail of the first list. Division by zero (empty list) is a syntax error.

[syntax] (c-ufactorial U) → list

Unary factorial. If the given list has length zero, yields the list '(u). If the given list has length one, yields the given list. Otherwise, yields a list containing items of the given list repeated (N-1)! times, where N is the length of the given list. This was named c-fact in the original source.

[syntax] (c-udrop L U) → list

Drops up to U items from the front of the given list, where U is a unary number.

Analogous to drop from SRFI-1, but uses unary numbers, and yields empty list if the list is too short.

[syntax] (c-utake L U) → list

Yields a list containing up to U items from the front of the given list, where U is a unary number.

Analogous to take from SRFI-1, but uses unary numbers, and yields the entire list if it is too short.