14. Macros and the Lisp surface

14.1 Two surfacesCopy Anchor Link

i has one core tree and two ways to write it. The normal surface is the syntax of §1 to §8, in files whose names end in .i. The Lisp surface writes the same core tree with brackets, in files whose names end in .is. A file uses one surface, chosen by the end of its name. A module path leaves out the extension; a module with both a .i and a .is file is a compile error. Imports, exports, dependencies and visibility mean the same in both surfaces, and a module written in one surface is used from the other with no difference.

Two trees are the same code when their parsed core trees are equal after removing only redundant groups. Type-definition kind is part of that tree: braces that distinguish an alias from a labelled definition (§4.3) are not redundant and are preserved. A .is file can be written as a .i file only when the normal surface can write its core tree; a quote and a macro definition have no normal spelling.

A macro is an i function that runs in the compiler. It takes code as data and gives code as data. Macros are defined only in .is files and are used from both surfaces. A macro has no host services: it cannot read files, use the network or read the time, and it gives the same result for the same input on every machine.

14.2 Tokens and datumsCopy Anchor Link

The Lisp surface uses the tokens of §1 and two more symbols, ` and ~. Documentation comments work as in the normal surface. The rule of lines (§1.7) is not used: every line end is a space. , does not separate parts; it is only the head of data, of a data type, of a data pattern, and of the imports and exports. Tokens are cut by the longest match (§1.5), so a space is needed where two tokens would be read as one, as between an integer and a .. after it. After . in (. e k), k is a decimal.

Datum   = Atom | Round | Square | Curly | Bits | Quote | Unquote | Splice .
Atom    = name | discard | UpName | int_lit | float_lit | string_lit | Symbol .
Round   = "(" { Datum } ")" .
Square  = "[" { Datum } "]" .
Curly   = "{" { Datum } "}" .
Bits    = "<<" { Datum } ">>" .
Quote   = "`" Datum .
Unquote = "~" Datum .
Splice  = "~" ".." Datum .
Symbol  = (* a symbol of §1.5 that is not a bracket *) .

• A .is file is a list of datums. The head of a Round is its first part.
• ~ followed by .. is always a Splice.
• An Unquote or a Splice may only be inside a Quote. A Quote may be inside a Quote only inside an Unquote or a Splice of the outer quote.
• A datum is read by its position: import item, export item, item, attribute, type, data type item, function result, expression, data item, statement, pattern, data pattern item, bit array segment, or format. Each position admits the rows of §14.3 given for it. A datum that fits no row of its position is a compile error.

14.3 How each form is writtenCopy Anchor Link

In these tables e is an expression, p a pattern, T a type, R a result type, N a named type, x and a names, C and U UpNames, F a function, and … zero or more of the thing before it.

Files and items

The { } around the right side of a name whose right side is a data type is part of the item: it is kept in Syntax, so a macro can tell a name from a labelled type.

Types

Expressions and statements

Patterns

• In the position of an expression, (-> …) is a function: an optional Square of type parameters, the parameter data pattern, the result (_ when no -> part is written, or (<- R needs) with a service pattern), and the body, which is any one expression. In the position of a type, (-> …) is a function type. In an expression, (<- e s) is a provide.
• (| …) in the position of an expression is a chain of two or more functions.
• (,) is the empty data wherever data is written. The empty () has no position.
• In the position of a data pattern item, (= n …) whose first part is a name is a labelled item: n is the label and the other parts are its pattern. So (size = whole = (w, h)) is (, (= size whole (, w h))), and ((a, b) = args) is (, (= (, a b) args)).
• |, & and - take two or more parts in a type. A string interpolation of the normal surface is written as the <> of its parts (§1.6).

14.4 Code as dataCopy Anchor Link

The module i/syntax exports these types:

Syntax = Opaque
TypeHandle = Opaque
Node = (
	TypeView
		| Name
		| Discard
		| Up
		| Symbol
		| Int
		| Float
		| Text
		| Round
		| Square
		| Curly
		| Bits
		| Quote
		| Unquote
		| Splice,
)
TypeView = (TypeHandle)
Name = (String)
Discard = (String)
Up = (String)
Symbol = (String)
Text = (String)
Round = (List(Syntax))
Square = (List(Syntax))
Curly = (List(Syntax))
Bits = (List(Syntax))
Quote = (Syntax)
Unquote = (Syntax)
Splice = (Syntax)
SyntaxError = (message = String, at = Syntax)

Position is a name for the union of one labelled type with data () for each position of §14.2: ImportItem, ExportItem, Item, Attribute, Type, DataTypeItem, FunctionResult, Expression, DataItem, Statement, Pattern, DataPatternItem, Segment and Format.

• A Syntax value is one datum with its span in a source file and its scope (§14.6). Syntax has no constructors: only the compiler, a quote and make give Syntax values. TypeHandle is a checked type that a typed macro query gives (§14.8); it is valid only in the position of a type.
• The Syntax of a piece of code is the datum that the Lisp surface writes for it, also for code from a .i file. So the node of the argument n > 0 is Node(Round(…)) whose parts have the nodes Node(Symbol(">")), Node(Name("n")) and Node(0). Int and Float atoms are the built-in types in the union of Node.
• A macro receives code with only redundant groups removed, preserving the definition kinds required by §14.1.
• An atom is one token of its kind. A negative number is the Round (- 1). make gives a SyntaxError for any other atom.
• == on two Syntax values is True only for the same value; same_code compares code.

Quote. A quote is written only in a .is file; the datum in it is a template. As an expression, `d gives the Syntax of d, with the scope of the module where it is written. Inside it, ~e puts in the value of e : Syntax, and ~..e puts in every member of e : List(Syntax); ~..e may only be a part of a bracket. As a pattern, `d matches a Syntax value: an atom matches a node of the same kind with the same text or value, a bracket matches the same bracket with the same number of parts, ~p matches one part with p, and ~..p, only as the last part of a bracket, matches the rest as a List(Syntax). Spans and scopes are not compared. A quote pattern may fail.

14.5 Syntax macrosCopy Anchor Link

A syntax macro is a top-level binding in a .is file with the attribute @macro and no declaration of the same name. Its pattern is one name, its value an ordinary function or chain of shape branches whose parameter items are bare names (positional) or label = name (labelled), and the value must have a subtype of (Syntax, …) <- (Assert, Definitions, Diagnostics, Fail(SyntaxError), Items) -> Syntax, with one Syntax for each parameter. @macro in a .i file, and an item with @macro in the result of an expansion, are compile errors. A macro is exported and imported as a value is. Its name may only be used in the imports, in the exports, and as the macro of a macro call. A macro may not be used in the module that defines it; a call in a template is data, not a use.

(, unless)
(@ macro
  (= unless
    (-> (, cond body) _
      `(|> ~cond (| (-> (, True) _ Nil) (-> (, False) _ ~body))))))

A macro call is written in these ways in both surfaces, where m is a name, or a.m with a module name a, that is a macro there:

• The parser does not know which names are macros, so arguments are read by the grammar of the position. Arguments are not worked out: the macro gets their Syntax. A labelled argument goes only to an explicitly labelled parameter item with that label. Bare parameter names are positional and do not create labels; renaming a parameter does not change its call shape. The argument data must have exactly the positional count and explicit labels of the macro parameters, under the ordinary rules of §6.11.
• No macro call gives a statement or a pattern.
• Before a type definition, the macro adds its result after the definition, which stays as written. Before a binding or a declaration, the result takes the place of the item. The item goes to the last parameter, with the attributes written after the macro. A built-in attribute may not be written before a macro. With several macros before an item, the first is expanded first.
• A result may not contain imports, a quote, an unquote or a splice, or a Curly of items anywhere but at the top. @external, @js and @host may be in a result only when the whole attribute datum, with its arguments and its item, came unchanged from the caller’s source through the arguments of each run, and at most once.

Expanding. One call of a macro is one run. Expansion goes from the outside in, and the result is expanded again. A module is expanded in two steps: first the item macros, the macros before items and the type macros inside type definitions, until none is left; then the expression macros and the other type macros. After the first step every top-level name and type definition of the module is known, and the exports are checked. A module is expanded and checked after every module it imports, so a macro’s module is done before the modules that use it.

Limits. Each run has a fresh budget of 100,000,000 work units, 2^28 allocation words of eight bytes and 10,000 frame units, and expansions may be nested at most 256 deep. These are counted in units of the language, not of the machine; a package cannot change them. Going over a limit is a compile error at the call that names the macro and the limit. A SyntaxError from a macro is a compile error at the span of its at; a stop in a macro, also by a failure reported to Assert, is a compile error at the call.

Budget accounting. Count the following abstract evaluation, before optimization, on the expanded core tree (§14.1). It uses the evaluation and matching order of §6 and §7. Redundant groups, inferred types, compiler-generated calling conventions and machine instructions have no charge of their own. The same source operation has the same charge when folded, inlined or shared. Work and allocation are cumulative; reclaiming storage does not refund them.

An Int has max(1, ceil(bit_length(abs(value)) / 64)) magnitude limbs. For the table, type nodes are the constructor, argument, variable, binder and operator occurrences of the simplified type given to the service; a shared part is visited at each occurrence. The cost is for the language service call and its exposed input and answer, not for a compiler’s internal solver steps. An i implementation of a library function is charged by its executed i code; only primitive operations use the primitive rows. Charges in different rows add when an event includes both, for example a call and its primitive work. A failed primitive has result size zero and constructs no result. Boundary copies of Syntax use the compiler-service work row as well as their allocation charge.

Allocation words count abstract value construction, regardless of physical sharing. A name read or return of an existing value allocates nothing. A newly computed Int uses 1 + limbs words; a Float or codepoint uses 1; a String uses 1 + ceil(UTF-8 bytes / 8); a BitArray uses 1 + ceil(bits / 64). Data uses 1 + number of parts, and a labelled wrapper uses 1 plus its data’s words when that data is constructed. Each new list cell uses 2 words; construction of [] uses 1. A function value uses 1 plus the number of captured values (§11.9); a newly made identity handle uses 1. Children already constructed are not allocated again by a containing value. A newly constructed or boundary-copied Syntax node uses 4 words plus its number of children, text bytes rounded up to words, and Int magnitude limbs. Count every occurrence in a copied tree, including input arguments, service answers and the returned expansion.

A frame unit is one active i function activation. A call adds one before entering the callee; return and unwinding remove it. A tail call replaces the current activation after its callee and arguments have been evaluated. Suspension removes the paused activations from the frame count and charges one allocation word per saved activation, besides the continuation handle and its captured values. Resumption reinstates those frames above the caller’s frames; cancellation reinstates them while unwinding. Dropping a continuation refunds no allocation and runs no finals (§9.4). Primitive operations and compiler services add no i frame. A match adds no frame (§6.12). Limits apply before the corresponding event, with work checked first, then allocation, then frames. An overflow of a counter exceeds its limit; equality with the limit is allowed.

The run’s budget starts before its reachable top-level initializers (§2.5), which are evaluated once in that fresh state. Literal values and function values constructed there use the same charges as elsewhere. A deferred run retried under §14.7 is a new run with a fresh budget, including initialization; an implementation cache must reproduce the same charges. Each nested expansion has its own budget. Expansion depth counts the outermost call as 1 and adds 1 for a call in an expansion’s result. Caching, compiler retries and optimization cannot change whether these logical limits are exceeded.

Collected bindings. During an item run the service Items of i/syntax is provided:

Items = (
	add = (Syntax, Syntax, List((String, String)), Syntax) <- (
		Fail(SyntaxError),
	) -> Nil,
	expose = (Syntax) <- (Fail(SyntaxError)) -> Nil,
)
Diagnostics = (note = (String) -> Nil)

add(collection, target, data, at) records that the function target, a binding of this module whose parameter group is (), belongs to the collection named by the exported binding collection, with string metadata data (unique keys) and source position at. The target is checked by its inferred function type; aliases and computed function values are allowed. Selecting a target invokes its initialized value by the ordinary call rules (§6.6). A pair of collection and target may be added once. expose adds a name of the module to its exports. Requests of a run take effect only when the run succeeds. A tool reads a collection after checking and chooses which targets become entries (§10.2); importing a module runs none of them. Diagnostics.note adds a compiler note, given once for a successful run.

14.6 Names in expanded codeCopy Anchor Link

Every Syntax value has a scope: a module and a set of marks. Code read from a file of module M, and a template written in M, have the scope M with no marks. make(node, like) gives the scope of like. For each run the compiler makes a new mark; it adds the mark to the arguments and to every answer of Definitions or Types, runs the macro, and then flips the mark on every syntax-bearing part of the successful output transaction: the returned syntax and all recorded Items.add and Items.expose requests, including their collection, target, name and source-position syntax. The transaction is transformed as one shared syntax graph, so a name shared by a returned binding and a request retains the same scope and identity in both. A failed or postponed run commits none of its requests or diagnostics. So code from the arguments is as it was, and code the macro made has the mark.

A name is looked up in this way:

1. It is bound by the nearest binding around it with the same text and the same scope.
2. Else, when it has no marks, it is a top-level, imported or built-in name of the module of its scope by the usual rules. A made name of another module reaches only exported names.
3. Else, when it has marks, it is a top-level name that an expansion defined with the same text and scope in the module of the call; or else a top-level, imported or module name of the module of its scope, and then a built-in name. A made name reaches only exported names.

Labels are compared by text only. Every rule that compares names (§2.2, §2.3, §4.3, §4.7, §6.11, §7.1) compares text and scope. A name defined by an expansion with marks may be used only by code of the same run and cannot be exported. A marked top-level binder may not have the text of a top-level, imported or module name of the module of its scope. Marked local binders use the ordinary lexical shadowing rule (§5) and exact scope matching; an unrelated outer name does not reserve their text. A name with no marks whose scope is another module may not be defined. An atom that came from an answer of Definitions or Types may not be a binder. Services and errors are found by type, not by name, so code from a template and code from the caller share services and error handlers as they would through an ordinary function.

14.7 Asking for definitionsCopy Anchor Link

Definitions = (definition = (Syntax) <- (Fail(SyntaxError)) -> Syntax)

definition(of) gives the written type definition named by of, an UpName or (. a U), with its attributes and parameters, as the Syntax of the item. A name bound by a type variable, a type of another module that is not exported or whose constructors are not exported, and a built-in type are SyntaxErrors; Bool, Nil, Result, Assert and AssertionFailure give the definitions this document gives them. A value-dependent alias gives its written item. An unresolved name in the current module is not ready while other pending item runs could introduce it. Its absence is a compile error at of only after those runs settle. Imported modules are already complete, so an absent imported name is an immediate compile error. The definition of a binding cannot be asked for.

In the first step of expansion, a definition of the module being expanded is given only when it is ready: present in the module with no macro call left in it. A name that may still be introduced by another pending item run is not ready even when no binding for it is present yet. A run that asks for a definition that is not ready is put off and done again later as a new run. When every run left has been put off, they are done one at a time in source order, each answered from the module as it is then; at the end of the step each such answer is asked again of the complete module, and a different answer is a compile error naming the name and the two runs. Runs that wait for one another in a circle are compile errors. So the result does not depend on the order in which runs are done.

14.8 Typed macrosCopy Anchor Link

A typed macro is a declaration and a binding with one name in a .is file, both with @macro. The declaration is the signature: a full function type, with no _. The binding is the implementation: an ordinary function or chain of shape branches. It supplies an implementation group for every parameter-data shape of the signature, with the same positional count and explicit labels in each advertised shape; every part of each shape is a Syntax parameter. Additional implementation groups are allowed, as for an ordinary function accepting a larger input set, but the signature determines which calls are admitted. Correspondence is checked at the definition, including shapes that no caller uses. Each group is checked against that shape of Syntax parts with need (Assert, Definitions, Diagnostics, Fail(SyntaxError), Types) and result Syntax. A call selects its shape group by the ordinary call rules before the macro runs. A typed macro is used only in the position of an expression. Its signature is written (@ macro (: name T)), as (@ macro (: to_text (-> [A] (, A) String))).

For type checking, a call of a typed macro is a call of a function with the signature’s type: the types of the code around it never depend on what the macro gives, and whether a binding is a direct value and how it is generalized are decided before expansion. The calls of a group of bindings (§4.7) are expanded after the group is inferred, against one unchanged snapshot of its types. The result is checked against the instantiated signature without adding bounds to any type variable of the snapshot, and a result that cannot be proved to fit is a compile error at the call. A generic binding is expanded once, not once per instance.

Expansion. A binding group is inferred once, with each typed call standing for its signature; when the group has an error, none of its typed calls is expanded. Its types are kept as a snapshot that every typed call of the group sees, and outer calls are expanded before inner ones. A type variable of the caller is closed when it is local to the group, not generalized, and reachable from no published scheme, declared type parameter, generalized variable or non-generalized top-level value; every other variable is fixed. For the queries only, a closed variable that occurs only in output places of the instantiated signature is given as the union of its lower bounds (Never when there are none), one that occurs only in input places and has upper bounds as their intersection, and any other as one opaque variable; one variable gets the same answer in every query of a run. The result is checked apart from the caller: no variable of the snapshot gains a bound, only new variables of the result do, and an obligation on a variable of the snapshot must be proved from the bounds it already has, or the expansion is rejected. An argument that the result keeps whole keeps its type and the definitions its names resolve to; a binder of the result may not capture a free name of an argument. A new value reference in the result must be to the group itself, to a group it depends on, or to an imported module; a new direct read of a value type is a compile error; and the result may not contribute items, exports or collection entries. An argument that the result drops is still diagnosed from the first check, and no warning is given twice.

Yes = ()
No = ()
NotKnown = ()
Truth = Yes | No | NotKnown

Types = (
	type_of = (Syntax) <- (Fail(SyntaxError)) -> Syntax,
	signature = () -> Syntax,
	subtype = (Syntax, Syntax) <- (Fail(SyntaxError)) -> Truth,
	members = (Syntax) <- (Fail(SyntaxError)) -> List(Syntax),
)

A type is a set of values that may be written in several ways, so a macro asks subtype and members instead of matching the Syntax of a type. A type that cannot be written in the type syntax is given as a TypeView, which subtype accepts and show prints as a token that is not source text. A fixed type variable is given as an Up node with a scope of its own that only names that variable; it may be written in the result without a declaration, but not in a type test. Queries uniformly observe the completed frozen snapshot, including bounds contributed by the expected result type. A variable that occurs only in the result is subject to the same query rules: without lower bounds an output-only closed variable gives Never; invariant occurrences remain opaque variables whose existing bounds may prove a subtype query. Queries never add evidence or bounds to the snapshot. A typed macro cannot delay an argument that has a need, and it cannot make items.

14.9 Running macrosCopy Anchor Link

The macros of a module run in a program made of that module and the modules it imports, compiled for the compiler itself, not for a target. Its entry points get only Definitions, Items in an item run, Types in a typed run, Diagnostics, and an Assert whose fail stops the run. An @external function outside the library modules, or an executable @js binding, in the needs of a macro is a compile error. hash in a macro gives the unsigned 32-bit integer defined below, on every machine. It does not use addresses, allocation order, compiler type numbers or randomized seeds. Each run starts from a fresh state; a result may be kept and used again only when everything the run was given is the same, and it then gets the mark of the new run.

A compile-time binding has @macro, or has a quote or a function of i/syntax in its full dependencies (§2.5). A program selected by its entries or host exports may not need one. i test provides the functions of i/syntax, so a test may call the functions a macro is made of, give its own Definitions, and compare code with same_code.

An error in expanded code is reported at the span of the code; code from a template is reported at the macro call, with the template as a note. Warnings are given only for code whose span is in the module being compiled.

i fmt formats a file in its own surface without expanding macros. i expand writes a module after expansion, in the surface that is asked for; a module with quotes can only be written in the Lisp surface, and i expand --trace also writes each run with its macro, arguments and result. The language server shows the expansion of a macro call, gives types and completion in the arguments of a typed macro call from its signature, and goes from a name in expanded code to its definition by its span.

Portable macro hash. Begin with h = 2166136261. For each word w of the stream below, set h = ((h xor w) * 16777619) mod 2^32. Words are unsigned 32-bit integers; negative words use their value modulo 2^32. Concatenation is in the written order, and nested values contribute their complete streams, without restarting h.

Opaque identities include functions, keys, boundaries, continuations, lazy values, references and compiler-owned handles (including Syntax and type handles). Their contents and creation numbers are not hashed. Collisions between unequal values, including different labels, types or identities, are permitted (§13). Sharing does not change the stream: each occurrence contributes independently.