\documentclass[a4paper,notitlepage]{article}
\newcommand{\bfive}{\texttt{b5}}

\title{Macro processing with \bfive\ and programming in pure lambda
calculus}

\author{Panu~A.~Kalliokoski}
\date{$ $Revision: 1.8 $ $ \\ $ $Date: 2002/05/26 15:04:43 $ $}

\begin{document}

\maketitle
\tableofcontents

\section{Introduction}

\bfive\ is a macro processor oriented towards both text processing and
generic programming in pure untyped lambda calculus. It aims at a
puristic model that is yet usable for real applications. In
particular, \bfive 's stream mechanism allows users to have
side-effects while retaining referential transparency.

Unlike most other macro processors, \bfive\ does not have specific
keywords or markers to be embedded in the source input---instead, it
uses separate rule and data files to produce its output. As such, it
encourages programming in a filter-like way, treating the input as data
to put through a number of rewrite rules, after which it is written out.

\bfive\ can be considered a programming language in the family of
pure, lazily evaluated, referentially transparent functional
languages. Unlike most of these, it completely lacks other data types
than functions; and it has a special way of producing output, namely
literal output text. So the output of a program is not always a
function.

\bfive\ is very fast, and it is relatively well suited for both
organised text preprocessing tasks (such as producing HTML and raw
text output from a single source file, or producing programs,
makefiles, or whatever from templates) and simple quick hacks. As
\bfive 's pattern matching gets better, it offers better and better
support for hacks.

\section{Basic macro processing}

\subsection{The \bfive\ command line}

The \bfive\ command line has the following form:

\texttt{ \$ b5 [ - ] \textit{rule files...}}

\bfive\ treats its standard input as data to be processed according to
the listed rule files. The rule files contain statements, most of
which make definitions for processing the input data. Rule files can
also contain data, requests to include other data or rule input files,
and declarations of additional output files. Different kinds of
statements are covered later. If the ``-'' (dash) option is given,
standard input is also treated as a rule file.

\subsection{A ``Hello World!'' example}

Here is the program, given as a \bfive\ rule file:

\begin{verbatim}
data Hello World!
;;;
\end{verbatim}

When run through \verb|b5 -|, it produces the string ``Hello World!'',
followed by a newline. The newline is there because there is a newline
before the triple-semicolon, which \bfive\ uses as an end-of-statement
marker. An even more stupid example would be to use a data file
instead of a rule file, because in the absence of definitions all
input data is forwarded to output unaltered (parentheses must be
balanced, though).

Macros, on the other hand, are basically pieces of text to be replaced
with other pieces of text. Just to give a hint of how macros work in
their most basic form, let's introduce another version of
\textit{Hello World}:

\begin{verbatim}
mac h => Hello;;;
mac w => World!;;;
data h w
Goodbye w
;;;
\end{verbatim}

When run through \verb|b5 -|, it produces the following output:

\begin{verbatim}
Hello World!
Goodbye World!
\end{verbatim}

Note how easy the macro definitions are to read: on the left side,
there is the text to be replaced (the macro ``name''); on the right
side, the text that will replace it (the macro ``expansion'').

Here is a somewhat more complicated example, which uses a macro with
an argument to replicate some strings:

\begin{verbatim}
mac triple x => x x x;;;
data triple(*)
triple(Hello World!
)triple(*)
;;;
\end{verbatim}

It produces the following output:

\begin{verbatim}
***
Hello World!
Hello World!
Hello World!
***
\end{verbatim}

This time, the macro definition of triple says that triple has an
argument, x, which may be anything whatsoever---it might be text, a
macro, a literal, a name of a stream. In the expansion text, all
occurrences of the variable name are replaced by the actual argument
value - in the above example, an asterisk, or the text ``Hello
World!'' (followed by a newline). When the macro is invoked, its
arguments are given in parentheses.

If a macro does not get as many arguments as it expects, it is not
expanded at all, but rather left as is. In the above example, if we
were to put the word ``triple'' in the input data without following
parenthesis, it would just be echoed in the output.  Also note that
white space is significant in data but ignored in macro
definitions---except as a divider between words.

There's still one more thing, and then we're ready to proceed to
serious macro hacking. \bfive\ special characters and macro names
(which are defined by you) seldom coincide with true input data, but
when they do, one must quote the input data as literal. Literal
strings are put between \verb|<<<| and \verb|>>>|. For example, to get
unbalanced parenthesis in the output:

\begin{verbatim}
data <<<1)>>> Hello, World!;;;
\end{verbatim}

This produces the string ``1) Hello World!'' (without a newline).

Other uses of literals include: inserting white space into macro
expansions (where it is otherwise ignored); ``gluing'' words together
by null (zero-length) literals; and protecting areas where you know
you never will want macro expansions---such areas are not so many, as
we will see in the following section.

\subsection{Using \bfive\ as a quick hack}

Sometimes you want to consistently do something to all occurrences of
a word. In such cases, you can make that word a macro, even if it was
not originally meant to be one. The following rule replaces all
occurrences of ``GPG'' with a hyperlink:

\begin{verbatim}
mac GPG => <<<<a href="http://www.gnupg.org/">GPG</a>>>>;;;
\end{verbatim}

With streams, you can make more complex hacks, like adding a footnote
for each occurrence of a word (well, I'm not completely serious, but
anyway). The following piece of code prints (as a line of asterisks)
the number of occurrences of the word ``doh'' in the file ``foo.txt''
before the rest of the text:

\begin{verbatim}
stream dohcount;;;
mac doh => <<<doh>>>dohcount(*);;;
data <:<dohcount>:>
;;;
input <<<foo.txt>>>;;;
\end{verbatim}

The stream facilities are discussed more in the section about streams.

\subsection{Convenience stuff}

Often it is aesthetically more pleasing to have your white space
available as macros than to put it directly into the source. Besides,
this saves you some writing when defining macros that contain white
space.  I suggest the following definitions:

\begin{verbatim}
mac nl => <<<
>>>;;; mac sp => <<< >>>;;;
\end{verbatim}

You may want to add a pseudo argument to these to prevent them from
getting used inadvertently. Personally I think quoting true nl- and
sp-words as literals is less of a nuisance than writing ``()'' after
all your calls to nl and sp.

Macro definitions can sometimes be very complicated, and need
commenting. Comments can be written into rule files by beginning them
with ///. Comments expand to the end of line.  Data files cannot have
this kind of comments, but you can make your own comment macro if you
want:

\begin{verbatim}
mac comment x => ;;;
\end{verbatim}

\section{A whiff of true macro programming}

If you've read this far, you might be asking: ``Yeah, it seems nice,
but how on earth could such a system ever do anything
interesting?'' \bfive\ reaches significant expressive power because
of some very simple but powerful mechanisms: higher-order macros,
closures, and lazy evaluation.

\subsection{Macros with multiple arguments}

Let's recall the macro definition syntax of \bfive . It begins with
the statement name ``\verb|mac|'', followed by the macro name. Then
there are zero or more argument names, which get bound to the values
given at macro invocation time. Then there is the keyword
``\verb|=>|'', followed by the macro expansion, which may contain the
argument variables zero or more times each.

At invocation time, the syntax is a bit different. The macro name is
given the same way, but argument values are given in
parentheses. Multiple arguments are given like this:
\verb|macro(one)(two)(three)|. If one is used to the common algebraic
function call notation with commas, this might look funny. However, it
has many advantages over the comma notation. One of them is that we
don't have to actually know whether we are giving all arguments to the
macro itself or a second macro returned by the first macro after, say,
half the arguments. One other is that we need not know whether we are
calling a macro or a macro with part of its arguments already given (a
closure). These things are dealt with in more detail in the following
sections.

The last, but not least significant, reason is that we avoid using yet
another syntactic character for special purposes.

\subsection{Higher order macros}

Suppose we have a macro that should do different things based on its
arguments. (This might sound like a given, but remember the comment
macro: it does \emph{not} do different things based on its arguments.)
If the ``different things'' are just putting a string in place of
another, the solution is easy: give the string as an argument, and
insert the argument where the text should occur. But what if the macro
should do some more complicated decision? And what if the string
itself logically belongs to the macro, not the caller? A case in point
are multi-language macros, which should output a different string
depending on the output language, say a ``last modification time''
text.

In these cases, the argument should control the macro's working
logic. Cases like this can always be handled by passing another macro
as an argument---this is called ``higher-order macros''. Let's
consider the ``last modified'' example above. It can be handled like
this:

\begin{verbatim}
mac lastmod lang => lang
		(<<<Most recent update: >>>)
		(<<<Viimeksi päivitetty: >>>)
		(<<<Date de modification: >>>);;;
mac english en fi fr => en;;;
mac finnish en fi fr => fi;;;
mac french en fi fr => fr;;;
\end{verbatim}

Now you can call lastmod(english), lastmod(finnish) and
lastmod(french) to get the appropriate messages. Another, probably
more clean solution would be to make it like this:

\begin{verbatim}
mac lastmod =>
en(<<<Most recent update: >>>)
fi(<<<Viimeksi päivitetty: >>>)
...
\end{verbatim}

And then have a language-specific include file, which will define the
expansions of all macros en, fi, fr, zh and so on to empty, except the
one that is the current language.

Still on the way of examples is a macro like this, which allows the
caller to give a ``degree of importance'' as argument:

\begin{verbatim}
mac sp => <<< >>>;;;
mac none x => ;;;
mac low x => x;;;
mac medium x => x x;;;
mac high x => x x x;;;
mac decorate imp text => imp(-)imp(=)imp(<) sp text sp imp(>)imp(=)imp(-);;;
data 
decorate(none)(Some problems are forthcoming)
decorate(medium)(I'm going down)
decorate(low)(Houston we've got a problem)
decorate(high)(BOOM!)
;;;
\end{verbatim}

which will expand to:

\begin{verbatim}
 Some problems are forthcoming 
--==<< I'm going down >>==--
-=< Houston we've got a problem >=-
---===<<< BOOM! >>>===---
\end{verbatim}

Here is a bunch of macros that can be used to form expressions of
various amounts of units:

\begin{verbatim}
mac plural pl sg => pl;;;
mac sing pl sg => sg;;;
mac meter pl => <<<meter>>>pl(s)();;;
mac phen pl => <<<phenomen>>>pl(a)(on);;;
mac ox pl => <<<ox>>>pl(en)();;;
mac 0 unit => <<<no >>>unit(plural);;;
mac 1 unit => <<<one >>>unit(sing);;;
mac 2 unit => <<<two >>>unit(plural);;;
mac many unit => <<<many >>>unit(plural);;;
mac each unit => <<<each >>>unit(sing);;;
\end{verbatim}

With these definitions, ``0(ox)'' expands to ``no oxen'', ``1(phen)''
expands to ``one phenomenon'', and so on. Macros such as plural and
sing (and en, fi, fr) above, which only return some of their
arguments, are called ``choice macros''.

Last, but not least, one can have macros that do nothing but rearrange
their arguments. Generic macros like these can often be used to
prevent having to write specific macro definitions. For example, this
is sometimes quite useful:

\begin{verbatim}
mac call_with x f => f(x);;;
\end{verbatim}

As a curiosity, I'd like to point out that all combinator macros
(macros that only have instances of argument variables in their
expansion) can be written as combinations of two macros, S and K,
given by \verb|mac K x y => x;;;| and
\verb|mac S x y z => x(z)(y(z));;;|. If you're interested in the
subject, search the web for ``combinatory logic''.

\subsection{Closures}

Sometimes you don't want to write a macro for every possible situation
needing ``intelligent behavior''. For example, the various unit (and
number) macros in the example above share common properties. All unit
macros seem to be of the same form: they take plurality as an
argument, output a common part, and a suffix depending on the
plurality. It would probably be handy to create them by macro.

But how can a macro create another macro? The solution is simpler than
one might think: if we allow any number of a macro's arguments to be
given at any time, we can pass ``partially parametrised'' macros
around. In \bfive , these combinations of macros and part of their
arguments are called ``closures''. The term bears some resemblance to
similar terms of other functional languages, but is much more
restricted.

Back to our example. We could define a generic unit macro and use it
to define the different units given above thus:

\begin{verbatim}
mac plural pl sg => pl;;;
mac sing pl sg => sg;;;
mac 0 unit => <<<no >>>unit(plural);;;
mac 1 unit => <<<one >>>unit(sing);;;
mac 2 unit => <<<two >>>unit(plural);;;
mac genunit baseword singsuffix plursuffix pluralp =>
	baseword pluralp(plursuffix)(singsuffix);;;
mac ox => genunit(<<<ox>>>)()(en);;;
mac meter => genunit(<<<meter>>>)()(s);;;
mac phen => genunit(<<<phenomen>>>)(on)(a);;;
\end{verbatim}

Of course, we need not define a macro for each unit anymore---we can
put them straight into data with genunit. For example, we could say
``2(genunit(ind)(ex)(ices))'' to get ``two indices''. Or we could do a
generic 99 bottles of beer macro, which could count anything besides
bottles of beer (for which the (somewhat clumsy) genunit definition is
``genunit(bottle)( of beer)(s of beer)''), for example
genunit(dat)(um)(a): 99 data on the wall \ldots 98 data on the wall
\ldots 1 datum on the wall \ldots I'm not totally serious about this,
either.

The big thing here is that all the genunit invocations above give it
only three of its four arguments immediately. The last argument is
added later. To see how this happens, let's examine the ``two
indices'' example above as stages of evaluation:

\begin{verbatim}
2(genunit(ind)(ex)(ices)) => (expansion of ``2'')
<<<two >>>genunit(ind)(ex)(ices)(plural) => (expansion of ``genunit'')
<<<two >>>ind<<<>>>plural(ices)(ex) => (expansion of ``plural'')
<<<two >>>ind<<<>>>ices => (concatenation)
two indices
\end{verbatim}

As an aside, if you don't understand how some system works, try
expanding the macros by hand. That might shed some light on the
process. (Sometimes it won't. I don't encourage anybody to
hand-evaluate loops written in continuation passing style, for
example.)

Basically, all kinds of data structures can be defined by closures
that keep the data in their arguments and which provide means for
getting the data. For example, the ordered pair data structure, which
contains two data, either of which can be retrieved, can be defined
thus:

\begin{verbatim}
mac pair 1 2 selector => selector(1)(2);;;
mac sel_1 1 2 => 1;;;
mac sel_2 1 2 => 2;;;
mac first x => x(sel_1);;;
mac second x => x(sel_2);;;
data
first(pair(foo)(bar))
second(pair(zoo)(quux))
;;;
\end{verbatim}

which will give

\begin{verbatim}
foo
quux
\end{verbatim}

Again, see how only two of pair's three arguments are given
directly. Actually, it is more appropriate to think of pair as a macro
taking two arguments, ``expanding'' to a macro that takes one
argument, the selector. By the way, lists (especially infinite lists)
are very easily constructed from ordered pairs: just put the list's
first element into the first datum, and the rest of the list into the
second one. You could define an infinite list of words ``foo'' by:
\verb|mac foolist => pair(foo)(foolist);;;|.

\subsection{Lazy evaluation}

This is probably the hardest one to explain, but basically it means
that a program will always terminate except when it actually produces
infinite output. To see why this might not be so, consider the
definition of foolist above; it expands as

\begin{verbatim}
foolist =>
pair(foo)(foolist) =>
pair(foo)(pair(foo)(foolist)) =>
pair(foo)(pair(foo)(pair(foo)(foolist))) =>
...
\end{verbatim}

As you can see, if foolist itself is to appear in the output, the
program will not terminate. (Actually \bfive\ will not produce any
output whatsoever, because it does not know that there are no
backeffects forthcoming, and so it will just hang.) However, this does
not make foolist useless. Consider the input ``first(foolist)''. It
has a well-defined expansion, namely that of ``foo''. But to get that,
we have to get an assurance that \bfive\ never will attempt to expand
foolist entirely unless it has to. This is what is called ``lazy
evaluation''. Let's see how the expansion goes:

\begin{verbatim}
first(foolist) => (expansion of ``first'')
foolist(sel_1) => (expansion of ``foolist'', 1 round)
pair(foo)(foolist)(sel_1) => (expansion of ``pair'')
sel_1(foo)(foolist) => (expansion of ``sel_1'')
foo
\end{verbatim}

It is always the \emph{topmost} macro that gets expanded. This is in
contrast to languages such as C, where a function's arguments are
evaluated before the function. But it gives you a guarantee that you
can use a macro in its own definition, as well as other
potentially-infinite structures, as long as the result is sensible.

Lazy evaluation is a very powerful tool that can be used to produce
astounding things. However, at the very least, it offers an important
facility: the ability to write loops by recursion.

\section{True programmers won't use built-in data types:
	 a survey of lambda calculus}

Now you've probably realised some of the potential of higher-order
macro systems. You might also have wondered if there are some kind of
numbers in \bfive : if numbers are valid variable names, they
apparently have no special significance. This section tries to
familiarise you with the techniques needed to build basic data types
in pure untyped lambda calculus, given in terms of \bfive .

\subsection{The ununderstood importance of representation}

There is an old proverb that says, ``Data structures create
algorithms, but algorithms do not create data structures.'' This means
that, given a specification of a data structure, one can easily come
up with algorithms to perform different operations on that data
structure; but given an algorithm, you will have hard time
understanding what it does, unless you know also the data structure it
operates on; and truly, an algorithm might do different things when
used on different data structures.

Mainstream computation languages spoil their programmers by providing
them with a heap of predefined data structures. These include
different kinds of numbers, strings, records and sometimes even
predefined hashes.  Basically, this is good as it reduces the
programmer's work of ordinary housekeeping.  However, it does blur the
fact that a data structure is not about how some specific bits are in
the memory but about how you can operate with the data.

In face of this, data structures that might seem very similar actually
have quite different properties. For example, in an environment where
an explicit tag type (enumeration) does not exist, programmers
typically use integers to represent tags without giving it a second
thought. This is possible because integers are an operational superset
of tags: they provide sufficient operations for tags, for example
comparison for equality. However, there are many integer operations
that do not make sense for tags: what does it mean, for instance, to
increment a tag or to multiply two tags?

This means that tags are not numbers, because they don't actually
provide the same operations. They can be represented by numbers, and
operations on tags are mappable to operations on numbers.

What does this have to do with our subject? It is essential to make it
clear that we should not ask the question ``How can I represent
integers in \bfive ?'' but the question ``How can I represent a data
structure that one can do operations X, Y and Z on in \bfive ?'' Of
course, most data structures, like integers, support an enormous
amount of operations. These data structures make it important to find
the ``core operations'' from which all operations can be built by
combining. Most data structures allow multiple choices for core
operations, and the choice of core operations will most likely affect
the ease and effectiveness of different algorithms on that data
structure.

For integers, one set of core operations is: incrementation,
decrementation, testing for zero.  We will study an implementation of
this core set in more detail later.  But for example, if one is
looking for a section counter, a glimpse on these operations
immediately reveals that a section counter is probably \emph{not} a
full-fledged integer: the only operations it needs are incrementation
and the ability to print itself.

Still one case in point is the example of counting ``doh'' words
above. It does its counting by appending an asterisk to a stream every
time it encounters the word ``doh''. It ``prints'' the ``count'' by
showing the contents of the stream. Did it use numbers?  In a way,
yes. It used a weak representation which allowed just enough
operations for it to accomplish the task.

Now that I've (hopefully) assured you that the important question to
ask is the one about necessary operations, let us proceed to actual
definitions.

\subsection{Representing booleans: the basic choice operation}

Booleans are sufficiently represented by one operation, the
``if''. \verb|if(cond)(b1)(b2)| is an operation which, if
\texttt{cond} is \texttt{true}, should evaluate to \texttt{b1}, and if
\texttt{cond} is \texttt{false}, should evaluate to \texttt{b2}. The
following definitions fulfill these conditions:

\begin{verbatim}
mac true b1 b2 => b1;;;
mac false b1 b2 => b2;;;
mac if cond b1 b2 => cond(b1)(b2);;;
\end{verbatim}

These definitions are highly arbitrary, as is usually the case with
data structures.  Especially note that the definition of ``if'' is
trivial, and could be given as well as
\verb|mac if cond => cond;;;|. Why? Because all ``if'' does with the
branch arguments is to forward them to the cond.

You probably noticed that the multi-language example had a similar
approach, as well as the pluralisation example: the expected behavior
is given as a choice macro. True and false are \emph{the} basic choice
macros, and could have been used in the pluralisation example as
well. (In programming languages that feature built-in booleans,
choices are often represented by booleans by programmers.)

\subsection{Tags: the customised choice operations}

It is easily seen that the choice technique can be expanded to more
alternatives than two, so I won't tease you with those. But it is
interesting to see that choice operations can be combined with
data-holding closures, for example like this:

\begin{verbatim}
mac result res b1 b2 b3 => b1(res);;;
mac error err b1 b2 b3 => b2(err);;;
mac nothing b1 b2 b3 => b3;;;
mac concat x y => x y;;;
mac print_result r => r
	(concat(<<<A result: >>>))
	(concat(<<<An error: >>>))
	(<<<Nothing>>>);;;
\end{verbatim}

Now let's see what \verb|print_result(error(no space))| does (some
white space has been added to make it fit):

\begin{verbatim}
print_result(error(no space)) => (expansion of ``print_result'')
error(no space)
	(concat(<<<A result: >>>))
	(concat(<<<An error: >>>))
	(<<<Nothing>>>) => (expansion of ``error'')
concat(<<<An error: >>>)(no space) => (expansion of ``concat'')
<<<An error: >>>no space => (concatenation)
An error: no space
\end{verbatim}

\subsection{Lists: tagged type of nil or pair}

Earlier we saw that pairs can be directly used to provide infinite
lists. Why infinite? Of course because we have no way to mark the end
of the list, which is also known as the empty list, or ``nil''. The
obvious solution is to represent lists with tagged type: the list is
either empty or it is composed of a first element and a list of
subsequent elements.

The core operations of a list are (by no means uniquely): ``nil'',
which constructs an empty list, ``cons'', which constructs a non-empty
list from an element and another list, ``car'', which returns the
first element of a list, ``cdr'', which returns all but the first
element of a list, and ``nullp'', which tests whether the list is
empty.

Using the technique from the previous section, we define list as:

\begin{verbatim}
mac nil b1 b2 => b1;;;
mac cons elm rest b1 b2 => b2(elm)(rest);;;
/// core operations on the data structure above
mac sel_1 1 2 => 1;;; /// (incidentally the same as nil)
mac sel_2 1 2 => 2;;;
mac car list => list(<<<ERROR: empty>>>)(sel_1);;;
mac cdr list => list(<<<ERROR: empty>>>)(sel_2);;;
mac nullp_false 1 2 => false;;;
mac nullp list => list(true)(nullp_false);;;
/// booleans, needed for nullp to work
mac true b1 b2 => b1;;;
mac false b1 b2 => b2;;;
mac if cond b1 b2 => cond(b1)(b2);;;
/// example macros that use the core operations
mac second_element list => car(cdr(list));;;
mac concat_list list => if(nullp(list))()
		(car(list) concat_list(cdr(list)));;;
\end{verbatim}

Again, different ways to define lists exist, and I wholeheartedly
encourage experimenting around.

\subsection{Interlude: how combinators might make your life easier}

When writing macro definitions like the one for lists above, one thing
that really gets irritating is that there always seems to be need for
some helper functions that are not meant to be called directly but are
necessary to arrange data the right way. For example, in the
definition of ``nullp'' in the previous section, we used a special
macro ``nullp\_false'' that ignores the two arguments ``cons'' gives
it (the first element and the rest of the list), and returns false.

The need for such definitions arises because a macro such as ``cons''
above gives information to the caller as arguments, and we need macros
to define what to do with those arguments---in the case of
``nullp\_false'', we discard them. ``sel\_1'' and ``sel\_2'' are
similar helper macros, only there to give as arguments to ``cons''.
Usage of such helpers could be circumvented e.g.~by defining lists in
some other way, but the problem is so commonplace that some other kind
of solution seems more appropriate.

If \bfive\ supported nameless (anonymous) functions (lambda expressions),
we could write these functions ``inline'' and so avoid an extraneous
macro definition. But because lambda expressions are not supported, I
sometimes rely on another approach, barely touched in the section
about higher-order macros. It seems that we can build many, many
definitions from some basic building blocks, the combinator macros.

For example, consider the definition \verb|mac K x y => x;;;|. With
this definition (or the isomorphic definitions for ``nil'' and
``sel\_1'' above), ``nullp\_false'' can be written as
\verb|K(K(false))|:

\begin{verbatim}
K(K(false))(element)(rest of list) => (expansion of ``K'')
K(false)(rest of list) => (expansion of ``K'')
false
\end{verbatim}

I mentioned that any combinator can be written as a combination of K
and S given by \verb|mac S x y z => x(z)(y(z));;;|. For example, the
choice macro for english in the multi-language example,
\verb|mac english en fi fr => en;;;|, can be given as
\verb|mac english => S(K(K))(K);;;| instead. But these definitions are
both nigh-unreadable and not sensible work to do by humans
anyway. However, the following definitions often come in handy:

\begin{verbatim}
mac K x y => x;;; /// K(x) is a unary macro that always returns x
mac I x => x;;; /// identity
mac flip f x y => f y x;;; /// swap arguments for f
mac . f g x => f(g(x));;; /// compose two functions
\end{verbatim}

Especially the last one, functional composition, is very useful. It
can be used to write an anonymous version of ``second\_element'', for
example: \verb|.(car)(cdr)|. ``false'' can be written as \verb|K(I)|:

\begin{verbatim}
K(I)(b1)(b2) => (expansion of ``K'')
I(b2) => (expansion of ``I'')
b2
\end{verbatim}

Why don't I use definitions like this all the time? First of all, of
course, because that would rend the examples unreadable. The second
reason is that macros that are not helpers are better off having
descriptive names. Especially when your program does not work you'll
be glad if you didn't use ``K(I)'' or ``sel\_2'' instead of ``false''
(the three are operationally equivalent), because the output will be
much more readable.

\subsection{The integer data type}

\end{document}