#################################
The Actinide Programming Language
#################################

*****
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: a 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: a 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: 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.

******************
Simple Expressions
******************

* 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.

* 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 environment is created, with the names of the arguments bound to
      the values from the function application expression.

    * The body of the function is run as a program, in this 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 produces 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).

    * May include a sequence of body subforms, which are evaluated in order
      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.

* ``define``: declares new bindings. This has two formats:

    * ``(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:

    * Simple 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)

  This program evaluates to 1, but *does not* bind ``x`` in the top-level
  environment.

TO WRITE:

* Comprehensive intro to quote forms
* Defining a simple macro
* Applying a simple macro