The code that implements Arc illustrates many useful programming techniques. Some of the techniques occur multiple times, and can be considered idioms of Arc programming; techniques that can be applied to many problems. This article describes some of the most common idioms, and how they can be used in Arc programming. The techniques described focus largely on macros and recursion.
Macros
Not surprisingly, given Paul Graham's enthusiasm for macros, Arc makes heavy use of macros. A few idioms appear commonly in the code.
"Decorated body"
The most common use of macros in Arc is something I call the "decorated body", which wraps a chunk of body code with something to extend it, analogous to the
decorator design pattern. Typically the decorator will set something up before executing the body code, as in
w/outstring,
w/table, and
fromstring.
(Note: the link for each operation goes to the documentation. Clicking on the code icon in the documentation will show the code for the operation.)
The pattern is also used to set something up before execution and then clean up afterwards. This is especially useful for file operations, as in
w/infile,
w/outfile, and
w/instring.
These macros often have names starting with "w/", short for "with/", indicating what they are providing to the body.
The
HTML library makes heavy
use of this idiom, for example in
tag,
form,
and
cdata,
which wrap the body in various HTML opening and closing tags.
To examine the implementation of this idiom, consider
let,
which is defined as:
(mac let (var val . body)
`(with (,var ,val) ,@body))
The typical features of this idiom are a macro definition with argument
. body to pick up the remainder of the arguments, a macro definition starting with quasiquote
`, and unquote-splicing
,@body to substitute the body code into the macro. The macro performs simple substitution:
arc> (macex1 '(let foo 42 body1 body2))
(with (foo 42) body1 body2)
Macro for control of evaluation
Unlike functions, macros receive their arguments unevaluated. This allows macros to be used for
conditional execution of code, or to execute code multiple times
iteratively. Some examples are
when,
unless,
while,
and
for.
(You might expect if to be a macro. It is actually a built-in special form, since conditional macros need to be based on some underlying conditional form.)
The code for repeat illustrates that this idiom also uses the ,@body structure as "decorated body":
(mac repeat (n . body)
`(for ,(uniq) 1 ,n ,@body))
Macro as lambda adapter
A variant of the body decorator is to use a macro to convert body code into a lambda function, which is similar to
an
adapter design pattern. This idiom is used when a function expects to receive a lambda function, but passing in body code is more convenient, especially when the base function is a Scheme primitive. Examples are
thread,
atomic,
w/stdin,
and
w/stdout:
(mac w/stdout (str . body)
`(call-w/stdout ,str (fn () ,@body)))
arc> (macex '(w/stdout foo body1 body2))
(call-w/stdout foo (fn nil body1 body2))
Macro to create functions with parameters
Another common macro idiom is to take a list of parameters and body code, and build a function out of these. This idiom is typically used to define a function that has special properties, and is often given a name that starts with "def". Some examples are
rfn,
afn,
defmemo,
defop,
defopr,
linkf,
and
rlinkf.
The code for defmemo shows the key component of this idiom: (fn ,parms ,@body) to build the function out of the parameters and body.
(mac defmemo (name parms . body)
`(safeset ,name (memo (fn ,parms ,@body))))
Complex macros
One irony is that even though though macros are extremely powerful, most of the macros in Arc perform simple substitutions.
There are, however, some macros that perform complex manipulation of their arguments.
Assignment is built from the
setform macro, which implements generalized variables through intricate macro processing of the arguments. Slightly less complex is
and, which implements short-circuit evaluation by turning its arguments into nested
if statements. Another interesting example is
with; the macro splits up the arguments into variables and values:
arc> (macex '(with (a 1 b 2) (prn a b)))
((fn (a b) (prn a b)) 1 2)
The
litmatch macro performs string matching by generating code to perform a sequence of character comparisons.
arc> (macex '(litmatch "abc" foo))
((fn (gs1442 gs1443) (unless (> (+ gs1443 3) (len gs1442))
(and (is #\a (gs1442 (+ gs1443 0))) (is #\b (gs1442 (+ gs1443 1)))
(is #\c (gs1442 (+ gs1443 2)))))) foo 0)
Recursion
Tail recursion is a standard Scheme technique for efficient recursion. If the last operation of a function is a recursive call, the compiler will use tail-call optimization to turn the recursion into iteration, avoiding creation of a stack frame on each call.
Iteration in Arc is built on top of tail recursion. Basic loop operations
such as
while,
loop, and
whilet use tail recursion on a function built from
rfn:
(mac while (test . body)
(w/uniq (gf gp)
`((rfn ,gf (,gp)
(when ,gp ,@body (,gf ,test)))
,test)))
cdr-scanning
A typical idiom for scanning a list is to tail-recursively call the function on the cdr of the list. Some examples are
reclist,
nthcdr,
last,
and rev.
The code for
assoc
illustrates this idiom. If there is no match, assoc is called on the cdr, until the whole list has been scanned:
(def assoc (key al)
(if (atom al)
nil
(and (acons (car al)) (is (caar al) key))
(car al)
(assoc key (cdr al))))
Tail-recursive string functions
One idiom in Arc for using tail recursion with strings is to add an index parameter to the function. This index parameter indexes into the string, and by incrementing it in each call, the function can be made tail-recursive and doesn't require modifying the string. The index parameter is often made an optional parameter so "normal" uses of the function don't need to specify the index. Some examples of this idiom are
recstring,
findsubseq,
indented-code,
parabreak,
and
urlend.
The code for headmatch illustrates this idiom; in this case the tail-recursion uses an anaphoric function:
(def headmatch (pat seq (o start 0))
(let p (len pat)
((afn (i)
(or (is i p)
(and (is (pat i) (seq (+ i start)))
(self (+ i 1)))))
0)))
Recursion with cons
Many operations in Arc need to perform operations on a sequence and create a result list. The common Arc idiom is to recurse through a sequence, building up the result with
cons.
Specifically, a macro
(op seq) will return the cons of something done to
(car seq) and
(op (cdr seq)). Thus,
op recursively steps through
seq, processing an element at a time and building up the result.
This idiom provides an interesting contrast to the previous recursion examples because this idiom is not tail-recursive. Because the
cons is applied to the result of the recursive function call, tail-call optimization cannot be applied.
Several examples of this idiom are
join,
rem,
reinsert-sorted,
pair,
firstn,
firstn-that,
tuples,
and
range.
The code for
map1
illustrates this idiom:
(def map1 (f xs)
(if (no xs)
nil
(cons (f (car xs)) (map1 f (cdr xs)))))
Note that
f is applied to
(car xs),
map1 is called recursively on
(cdr xs), and the two are cons'd together.
Miscellaneous
The majority of the idioms I discuss are based on macros or recursion. This secion discusses some miscellaneous idioms that don't fit those categories.
Push and reverse
The "push and reverse" idiom is an efficient, but somewhat surprising way to generate a list. In this idiom, successive elements are pushed onto the front of the list, and when the entire list is generated, it is reversed to obtain the desired order. This is a well-known
Lisp idiom and is more efficient than the obvious method of appending elements to the end of the list.
Several examples of "push and reverse" are
drain,
dedup,
parse-format,
litmatch,
endmatch,
and
handle-post.
The code for n-of illustrates the idiom. Items are added with
push
to an accumulator (ga in this case), and the accumulator is reversed with
rev
at the end:
(mac n-of (n expr)
(w/uniq ga
`(let ,ga nil
(repeat ,n (push ,expr ,ga))
(rev ,ga))))
String stdout
Arc makes extensive use of an idiom I'll call "string stdout" because a string is used as stdout. The code writes multiple chunks to stdout, and the results are gathered into a string. This idiom avoids having to manually concatenate the components into the result string.
The
tostring
macro is used to implement this idiom.
Arc has a surprisingly large number of macros that use this idiom, including
readline,
code-block,
unmarkdown,
varfield,
markdown,
eschtml,
striptags,
parafy,
subst,
multisubst,
and
num.
Typically, code using this idiom will use produce output with pr or writec, and use tostring to collect the output.
The code for multisubst illustrates this:
(def multisubst (pairs seq)
(tostring
(forlen i seq
(iflet (old new) (find [begins seq (car _) i] pairs)
(do (++ i (- (len old) 1))
(pr new))
(pr (seq i))))))
The flip side of this idiom is the "string stdin" idiom, where a string is used as stdin. The "string stdin" idiom is rarely used; one example is
parse-format.
Summary
The Arc code illustrates several common Arc idioms, some of which are well-known Scheme or Lisp idioms. Since Paul Graham is a Lisp expert, carefully studying his Arc code is a rewarding way to learn more about programming Lisp-like languages.
Undoubtedly I've missed some important idioms. Please let me know if your favorite idiom is missing, or if I've mangled the descriptions of any idioms.
exercises in Java; maybe I'll post details later.
.)