################################# The Actinide Programming Language ################################# .. highlight:: scheme ***** Forms ***** * The basic unit of Actinide syntax. * The basic unit of Actinide evaluation. * A program is evaluated by *reducing* forms to produce a final value, applying side effects during the reduction. * What does a form look like? * Simple forms: literals (and intro to types) * Integers: an optional leading - sign for negative numbers, followed by a sequence of digits and underscores. Represent base-ten values with no fractional part. Examples: ``10``, ``-2_049``. * Decimals: an optional leading - sign for negative numbers, followed by a sequence of digits and underscores, followed by a dot, followed by a sequence of digits and underscores. Represent base-ten values which may have a factional part. Examples: ``10.0``, ``-2_049.501_2``. * Strings: any sequence of characters other than ``"`` or ``\``, enclosed in matching ``"`` marks. The sequences ``\"`` and ``\\`` are "escape" sequences, representing a ``"`` or ``\`` character respectively. Examples: ``"Hello, world."``, ``"😡💩🚀"``, ``"Quoth the raven, \"Four Oh Four.\""``. * Booleans: the special values meaning "true" and "false." Preferred for boolean logic operations. They are ``#t`` for true, and ``#f`` for false. * Simple forms: symbols * Sequences of letters, numbers, and symbols not surrounded by quotes, and which are not themselves integers, decimals, or booleans. * Represent variables and constants in the program's source. * Evaluation of variables is covered later in this document. * Examples: ``hello``, ``+``, ``my-🚀``. * Special mention: comments * Cannot appear *inside* a string. * Starts with a ``;``, continues to the end of the line. * Dropped from the program entirely. * Examples: ``; this function is extremely spicy.`` * Compound forms: conses and dotted pairs * An opening ``(``, followed by a head subform, followed by spaces, followed by a ``.``, followed by a tail subform, followed by a closing ``)``. * Represents a *cons* with the given head and tail. * A dotted pair which appears as the head of a dotted pair does not require an additional dot. * Examples: ``(1 . 2)``, ``(1 2 . 3)``, ``(('ll . 'lr) . ('rl . 'rr))`` * Compound forms: lists * An opening ``(``, followed by a sequence of "subforms" separated by spaces, followed by a closing ``)``. * Subforms may be any form, including another list. * Represent function application as well as special * Compound forms: quotes, quasiquotes, and unqoute forms. * The forms ``'``, `````, ``,``, and ``,@`` represent "quote" forms. * These are discussed in detail in the Macros section, later on. ********** Evaluation ********** * When an Actinide program is run, its top-level form is evaluated. * Evaluation of a form *reduces* the form to a simpler form - ideally, into a list of atomic values. * Every kind of form can be evaluated. ****************** Simple Expressions ****************** * Evaluation of literals: * Integers, decimals, strings, booleans evaluate to themselves. The number ``1`` or the string ``"Hello, world"`` cannot be reduced any further. * Evaluation of symbols: * The symbol is replaced by a value from the current *environment*. * This is analogous to variable expansion in other languages. * How do environments get their values? Defines and function application, covered below. * Certain symbols are *built in* and are automatically given values in the top-level environment before the program starts. ******************** Function Application ******************** * Evaluation of lists: * A list that starts with the symbols ``begin``, ``values``, ``if``, ``lambda``, ``define``, ``define-macro``, or ``quote`` is a *special form*, which are covered separately. * Any other list represents a function application. * The subforms representing the list elements are evaluated first, left to right. * If the first subform evaluates to a procedure * During application: * A new *child* environment is created, with the names of the arguments bound to the values from the function application expression. The environment captured by the procedure is the *parent* of this new environment: any name not found in the *child* environment will be looked up in the parent environment instead. * The body of the function is run as a program, in the newly-created environment. * The result of the last form in the function is the result of the function application. ************* Special Forms ************* Lists that begin with one of the following symbols are evaluated specially. * ``begin``: A ``begin`` form evaluates a sequence of subforms, reducing to the result of the last subform in the sequence. Example: :: (begin ; define a function... (define (f) 1) ; ...and call it (f)) The forms whose results are discarded are still evaluated for their side effects. * ``values``: A ``values`` form evaluates a sequence of subforms, then reduces to those values in the context of the containing form. This allows functions to return multiple values. Example: :: (begin (define (two x) (values x x)) (= (two 53))) The ``two`` function returns two values, which are placed in the argument positions for the ``=`` function. This program reduces to ``#t`` if run, and defines ``two`` as a side effect. * ``if``: An ``if`` form must include a ``cond`` subform producing exactly one value, and either one or two consequent subforms (named ``true`` and ``false`` subforms in this document). * The ``if`` form first evaluates the ``cond`` subform. * If it evaluates to a true value (``#t``, a non-zero integer, a non-zero decimal, a non-empty string, or a non-nil ``cons``), then the ``if`` form evaluates the ``true`` subform. * If the ``cond`` subform evaluates to a false value (any other value), then the ``if`` form evaluates the ``false`` subform. * If the ``if`` form does not have a ``false`` subform, the ``if`` form evaluates to ``nil`` when the ``cond`` subform evaluates to a false value. * Examples: ``(if #t 1)`` (always equal to ``1``), ``(if some-var "okay" "failure")``. * ``lambda``: A ``lambda`` form defines a procedure, and evaluates to a procedure value which can be used to apply the newly-defined procedure. * Must include a ``formals`` subform, which is generally a list of argument names (as symbols). If the formals subform is a bare symbol, or a dotted pair whose tail is a symbol, the function has variable arity, and all arguments not assigned to a name from the formals list are collected into a list and bound to that symbol. * May include a sequence of body subforms, which are evaluated in order (as if by ``begin``) whenever the function is applied. * Functions capture the environment in effect when they are defined. Symbols within the function body can refer to names defined in the surrounding lexical context. * Function bodies are evaluated in a new environment for each application, with the symbols representing the arguments bound to the corresponding values in the function application form. * Examples: :: (lambda () 1) This defines a constant function (which takes no arguments) whose evaluation is always 1. :: (begin (define x 5) (lambda () x)) This defines a constant function whose evaluation is always the value of ``x`` in the top-level environment (initially 5). :: (lambda (a b) (+ a b)) This defines a binary function (which takes two arguments) whose evaluation is the sum of those arguments. This is a simple replacement for the ``+`` function itself, but it illustrates the idea that functions can include other functions. :: (lambda (a . b) b) This defines a function which takes one or more arguments, whose evaluation is the list of arguments other than the first. * ``define``: A ``define`` form sets the value of a new binding in the current environment. This has two forms: * ``(define symbol value)``: evaluates the ``value`` subform, and binds the result to ``symbol`` in the current environment. Example: :: (begin ; Bind x to a value (define x 5) ; Expands x in the same environment x) This program evaluates to ``5``. * ``(define (name formals...) body...)``: defines a function and binds it to ``name`` in the current environemnt. This is expanded to an equivalent ``lambda`` form, within a ``define`` form binding the resulting procedure to ``name``. For example: :: (define (f a b) (+ a b)) is equivalent to :: (define f (lambda (a b) (+ a b))) * ``define-macro``: This has the same syntaxes as the ``define`` form, but it binds values to a special "macro table" which is used to transform code prior to evaluation. Macros are described later in this document. * ``quote``: A ``quote`` form must have exactly one form in argument position. It evaluates to exactly the argument form, without evaluating it. For example: :: (quote (+ 1 2)) evaluates to the list ``(+ 1 2)``. Quote forms are the easiest way to obtain unevaluated symbols as values, and are an integral part of the Actinide macro system. ******************* Loops and Recursion ******************* * To loop, a function must recurse. Actinide has no looping primitives other than function application. * Actinide guarantees that functions that recurse in tail position, either directly or indirectly, can recurse indefinitely. * What is tail position? * Function bodies: the final form of the function is in tail position with respect to the function. * ``begin`` forms: the final subform is in tail position with respect to the ``begin`` form. * ``if`` forms: the ``true`` subform is in tail position with respect to the ``if`` form if the ``cond`` subform reduces to a true value. The ``false`` subform is in tail position with respect to the ``if`` form if the ``cond`` subform reduces to a false value. * If a form is in tail position with respect to its containing form, it is in tail position with respect to *that* form's containing form, and so on, out to the nearest ``lambda`` body or to the top level of the program. * Example: * A simple, non-tail recursive factorial: :: (define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1))))) The ``factorial`` function *is not* called in tail position with respect to the body of the ``factorial`` function: After reducing that function application, the reduction of the outer ``factorial`` application still needs to apply the ``*`` function to the result. Attempting to evaluate ``(factorial 1000)`` fails due to limits on call depth: ``maximum recursion depth exceeded while calling a Python object`` :: (define (fact n a) (if (= n 1) a (fact (- n 1) (* n a)))) The ``fact`` function *is* called in tail position with respect to the body of ``fact``. Specifically, it is in tail position with respect to the ``if`` form whenever ``n`` is not equal to ``1``, and the ``if`` form is in tail position with respect to the body of the ``fact`` function. Evaluating ``(fact 1000 1)`` correctly computes the factorial of ``1000`` on any machine with enough memory to store the result. ****** Macros ****** * Before Actinide evaluates a program, it *expands* a program. * Expansion replaces macros (defined by ``define-macro``, as above). * A *macro* is an Actinide procedure, as with ``lambda``, which accepts forms as arguments and reduces to a new form. * Macros can be used to define new syntax. * Macro expansion is recursive: the result of expanding a macro is expanded again, which allows macros to produce macro forms. * Example: The ``let-one`` macro defines a single local variable, with a known value, and evaluates a body form in a temporary environment with that variable bound. :: (define-macro (let-one binding body) (begin (define name (head binding)) (define val (head (tail binding))) `((lambda (,name) ,body) ,val)))) To use this macro, apply it as if it were a function: :: (let-one (x 1) x) The macro procedure accepts the forms ``(x 1)`` and ``x``, unevaluated, as arguments, and substitutes them into a *quasiquoted* form, which is used as a template. The three *unquoted* parts (``,name``, ``,body``, and ``val``) are replaced by evaluating the symbols in the context of the macro procedure, and expand to the relevant parts of the input forms. The returned form is approximately :: ((lambda (x) x) 1) and evaluates as such. This program evaluates to 1, but *does not* bind ``x`` in the top-level environment. * Actinide macros are *not hygienic*. A quoted symbol in the macro body will be evaluated in the location where the macro is expanded, with full access to the environment at that location. Similarly, symbols defined in the macro will be fully visible to code running in the environment where the macro is expanded. * Macros often use quote notation to build the returned form. Quote notation is ultimately a sequence of ``quote`` forms. However, Actinide supports *quasiquote* notation to simplify the creation of nested quoted forms containing unquoted parts. * A quasiquote form begins with `````. If the form contains no unquoted parts, this will quasiquote each subform, terminating by quoting each symbol or literal form and constructing a new list with the resulting quoted forms. ```(a b)`` expands to ``('a 'b)``. * Within a quasiquote form, an *unquote* form prevents the following form from being quoted. An unquote form begins with ``,``, followed by a single form (often, but not always, a single symbol). ```(a ,b c)`` expands to ``('a b 'c)``. * Within a quasiquote form, an *unquote-splicing* form prevents the following form from being quoted. An unquote-splicing form begins with ``,@``, followed by a single form, which must evaluate to a list. The elements of that list are grafted into the resulting form. Given ``(define x (list 1 2))``, the form ```(a ,@x b)`` expands to ``('a 1 2 'b)``. * Macros defined inside of a function body are not visible to the top-level expander.