Carp
Macros
Macros are among the most divisive features about any Lisp. There are many different design decisions to be made, and all of them have proponents and detractors.
This document aims to give a comprehensive overview of the macro system and how to use it. If you’re in a hurry or want to see whether Carp implements your favorite macro feature, you probably want to read the section “In a Nutshell”. If you want to spend some quality time understanding how to work on or with the macro systems, the sections “Working with Macros” and “Inner Workings” will probably be more useful to you.
In a Nutshell
The macro system we’ve settled on for Carp is fairly simple. It is:
- not hygienic, but provides
gensymcapabilities, - does not currently provide quasiquoting (this is not a requirement, it is
currently just not implemented); thus the bread and butter in your macro
toolbox will be
car,cdr,cons, andlist, - defines macros with a fairly simple
defmacro-based syntax, and has support for compile-time or dynamic functions (for more information on this aspect, please read “Working with Macros” below), and - it sees the dynamic environment not just as an environment in which to
generate code through expanding macros, but also as a place for telling the
compiler more about the source. As an example, consider the dynamic function
Project.config, which allows you to set such things as the C compiler to use, the name of the compiled project, or the output directory. To see this in action, consider this Carp snippet which implements a simple multi-compiler build system for Carp in the dynamic environment.
Working with Macros
Macros are defined using the defmacro primitive form, like this:
(defmacro apply [f args] (cons f args))
(apply + (1 2)) ; => (+ 1 2)
(apply Array.replicate (5 "hello")) ; => (Array.replicate 5 "hello")
The example above defines apply, a macro that takes a function and a set of
arguments defined as a list and rewrites it so that the function gets applied
to these arguments by constructing a list with f as a head and args as
tail.
Because apply is a macro you will not need to quote the list passed to it. If
that looks strange, you might want to define apply as a dynamic function
instead. The main difference between macros and dynamic functions is that
dynamic functions evaluate their arguments and macros are expanded inside their
definitions. You may define a dynamic function like this:
(defndynamic apply [f args] (cons f args))
(apply '+ '(1 2)) ; => (+ 1 2)
(apply 'Array.replicate '(5 "hello")) ; => (Array.replicate 5 "hello")
If you compare this code example to the macro example above, you’ll see that
they are extremely similar, except for the invocation defndynamic and the
quotes in their invocation.
Macros also provide rest arguments; this basically means that you may define variadic macros by providing a “catch-all” argument as the last argument.
(defmacro apply-or-sym [head :rest tail]
(if (= (length tail) 0)
head
(cons head tail)))
(apply-or-sym *global*) ; => *global*
(apply-or-sym + 1 2) ; => (+ 1 2)
The macro apply-or-sym is slightly ridiculous, but it should drive the point
home. It takes one formal argument, head. You may provide any number of
arguments after that—they will be bound to tail. Thus, tail will be a list of
zero or more arguments. If we do not provide any, apply-or-sym will just
return head. If we do, we treat it as a regular invocation. This kind of
macro might look slightly silly, but rest assured that using rest arguments has
many legitimate use cases.
If you’d like to see more examples of macros big and small, you should now be
equipped to understand a lot of the macros in the standard
library and even fmt, a fairly
complex piece of macro machinery.
Some helpful functions for exploring macros in the REPL are expand, eval,
and macro-log. expand will expand macros for you, while eval evaluates
the resulting code. macro-log is useful for tracing your macro, a form of
“printf debugging”.
Inner Workings
The Carp compiler is split in a few different stages. The diagram below illustrates the flow of the compiler.
The dynamic evaluator is arguably one of the most central pieces of the Carp
compiler. It orchestrates macro expansion, borrow checking, and type inference,
as it encounters forms that have requirements for these services, such as
function definitions, variables, or let bindings.
Therefore, understanding the evaluator will give you a lot of insight into how Carp works generally.
The most tried-and-true starting point for understanding the dynamic evaluator
is eval in src/Eval.hs.
Data Structures
The type signature of eval is as follows:
eval :: Context -> XObj -> IO (Context, Either EvalError XObj)
Thus, to understand it, we’ll have to understand at least Context, XObj,
and EvalError. The types IO and Either are part of the Haskell standard
library and will not be covered extensively—please refer to your favorite
tool for Haskell documentation (we recommend Stackage)
to find out more about them.
All data structures that are discussed here are defined in
src/Obj.hs.
XObj
XObj is short for “Obj with eXtras”. Obj is the type for AST nodes in
Carp, and it’s used throughout the compiler. Most often, you’ll find it wrapped
in an XObj, though, which annotates such an Obj with an optional source
location information—in the field info, modelled as a Maybe Info—and
type information—in the field ty, modelled as a Maybe Ty. While both of
these fields are important, for the purposes of this document we will overlook
them and treat a XObj as an ordinary AST node. Thus, eval becomes a
function that takes a context and an AST node, and returns a pair consisting of
a new context, and either an EvalError or a new AST node.
Context
Context is a data structure that holds all of the state of the Carp compiler.
It is fairly extensive, holding information ranging from the type and value
environments to the history of evaluation frames that were traversed for
tracebacks.
The entire state of the compiler should be inspectable by inspecting its context.
EvalError
An EvalError is emitted whenever the dynamic evaluator encounters an error.
It consists of an error message and meta information (such as a traceback and
source location information).
Evaluation
The dynamic evaluator in Carp takes care both of evaluation and meta-level
information like definitions. This means that definitions are treated much like
dynamic primitives to evaluate rather than special constructs. In fact, many of
them are not treated as special forms, but are implemented as Primitives.
Because we already introduced multiple constructs by name, let us define what kinds of Carp constructs there are for the evaluator:
- Special forms: these are forms that have their own representation in the
abstract syntax tree and are treated directly in the evaluator loop.
fnandtheare examples for this category. They cannot be passed around by value, as you would do in higher order functions. - Primitives: these are regular Carp forms that do not evaluate their
arguments, and they resemble builtin macros implemented in Haskell. Examples
for this category include
defmacro,defn, andquote. - Commands: these, too, are regular Carp forms. They evaluate their arguments
and behave like builtin functions. Examples for this category include
Project.config,car, andcons.
Primitives are mostly defined in src/Primitives.hs,
commands can be found in src/Commands.hs, and special
forms can be found directly inside eval.
They are wired up into the environment and given names in
src/StartingEnv.hs.
Adding your own special forms, primitives, or commands
While there is a lot of machinery involved in getting your own primitives or commands into the Carp evaluator, there are a lot of simple functions around to help you get started.
If the name for the primitive or command is already present as a runtime function, it should try to mimic its behavior as closely as possible.
Adding special forms is a little more involved and we try to exercise caution
in what to add, since every form makes eval harder to understand and reason
about. You should probably get in touch on the
chat before embarking on a quest to
implement a new special form to avoid frustration.
A current list of special forms
Since special forms are “magical”, they deserve an enumeration. Currently there are:
iffor branching,defnfor defining functions,deffor defining global variables,letfor defining local variables,thefor type annotations,fnfor function literals.