diff options
| -rw-r--r-- | README.rst | 16 | ||||
| -rw-r--r-- | _templates/globaltoc.html | 11 | ||||
| -rw-r--r-- | _templates/localtoc.html | 13 | ||||
| -rwxr-xr-x | conf.py | 8 | ||||
| -rw-r--r-- | docs/embedding.rst | 9 | ||||
| -rw-r--r-- | docs/language.rst | 447 | ||||
| -rw-r--r-- | docs/macros.rst | 203 | ||||
| -rw-r--r-- | docs/semantics.rst | 441 | ||||
| -rw-r--r-- | docs/syntax.rst | 211 |
9 files changed, 915 insertions, 444 deletions
@@ -5,6 +5,10 @@ Actinide .. image:: https://circleci.com/gh/ojacobson/actinide.svg?style=svg :target: https://circleci.com/gh/ojacobson/actinide +.. image:: https://readthedocs.org/projects/pip/badge/ + :target: https://https://actinide.readthedocs.io/ + + **An embeddable lisp for Python applications.** I had `an application`_ in which the ability to extend the application from @@ -50,6 +54,18 @@ Requirements Actinide requires Python 3.6 or later. +Building the documentation requires Sphinx, and should be done in a Python virtual environment: + +.. code-block:: bash + + $ python3.6 -m venv .venv + $ source .venv/bin/activate + $ pip install -r requirements-docs.txt + $ make html + $ open _build/html/index.html # or any other command to launch a browser + +The documentation is also available online at https://actinide.readthedocs.io. + ************ Installation ************ diff --git a/_templates/globaltoc.html b/_templates/globaltoc.html new file mode 100644 index 0000000..36894a8 --- /dev/null +++ b/_templates/globaltoc.html @@ -0,0 +1,11 @@ +{# + basic/globaltoc.html + ~~~~~~~~~~~~~~~~~~~~ + + Sphinx sidebar template: global table of contents. + + :copyright: Copyright 2007-2017 by the Sphinx team, see AUTHORS. + :license: BSD, see LICENSE for details. +#} +<h3><a href="{{ pathto(master_doc) }}">{{ _('Table Of Contents') }}</a></h3> +{{ toctree(maxdepth=1) }} diff --git a/_templates/localtoc.html b/_templates/localtoc.html new file mode 100644 index 0000000..bc0b79d --- /dev/null +++ b/_templates/localtoc.html @@ -0,0 +1,13 @@ +{# + basic/localtoc.html + ~~~~~~~~~~~~~~~~~~~ + + Sphinx sidebar template: local table of contents. + + :copyright: Copyright 2007-2017 by the Sphinx team, see AUTHORS. + :license: BSD, see LICENSE for details. +#} +{%- if display_toc %} + <h3><a href="{{ pathto(master_doc) }}">{{ _('This Section') }}</a></h3> + {{ toc }} +{%- endif %} @@ -89,7 +89,11 @@ html_theme = 'alabaster' # further. For a list of options available for each theme, see the # documentation. # -# html_theme_options = {} +html_theme_options = { + 'github_button': True, + 'github_user':'ojacobson', + 'github_repo': 'actinide', +} # Add any paths that contain custom static files (such as style sheets) here, # relative to this directory. They are copied after the builtin static files, @@ -103,6 +107,8 @@ html_static_path = ['_static'] # refs: http://alabaster.readthedocs.io/en/latest/installation.html#sidebars html_sidebars = { '**': [ + 'globaltoc.html', + 'localtoc.html', 'relations.html', # needs 'show_related': True theme option to display 'searchbox.html', ] diff --git a/docs/embedding.rst b/docs/embedding.rst index f07b0f6..d179baf 100644 --- a/docs/embedding.rst +++ b/docs/embedding.rst @@ -78,8 +78,8 @@ will automatically determine the name to bind to: session.bind_fn(example) print(*session.run('(example)')) # prints "5" -Finally, to bind a function returning a tuple of results, call -``bind_builtin``. This will automatically determine the name to bind to: +To bind a function returning a tuple of results, call ``bind_builtin``. This +will automatically determine the name to bind to: .. code-block:: python @@ -128,6 +128,11 @@ The symbol must be bound to an instance of the ``Registry`` class from the def two_values(): return 1, "Two" + An.eval(''' + (begin + (define (three-values) (values 1 2 3))) + ''') + # @An.macro_bind, @An.macro_void, @An.macro_fn, and @An.macro_builtin follow # the same pattern. diff --git a/docs/language.rst b/docs/language.rst index 356b490..c033f65 100644 --- a/docs/language.rst +++ b/docs/language.rst @@ -4,446 +4,11 @@ The Actinide Programming Language .. highlight:: scheme -***** -Forms -***** +The following documents fully describe the Actinide language, and all of its +built-in syntactic elements. -* The basic unit of Actinide syntax. +.. toctree:: -* The basic unit of Actinide evaluation. - -* A program is evaluated by *reducing* forms to produce a final value, applying - side effects during the reduction. - - * 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. + syntax + semantics + macros diff --git a/docs/macros.rst b/docs/macros.rst new file mode 100644 index 0000000..f544d93 --- /dev/null +++ b/docs/macros.rst @@ -0,0 +1,203 @@ +.. _macros: + +###### +Macros +###### + +This section describes Actinide's macro facility, which transforms programs +between parsing and evaluation. Macros provide a powerful way to extend Actinide's syntax. + +.. warning:: + + Actinide's macro expansion facility is broadly inspired by Common Lisp's, + and implements *non-hygienic* macros: symbols generated by macro expansion + can conflict with symbols defined in the context where the macro is + expanded in both directions. + + I would like to replace this with a macro expander based on Scheme's, but I + can't promise that I'll ever get around to it. Writing macros using + Actinide's macro system is fraught with minor but irritating problems + related to symbol capture, and macros should use user-provided symbols as + much as possible to avoid interacting with the environment at the expansion + site. + +.. warning:: + + Macro expansion is fully completed before any evaluation occurs. Programs + can define macros for future programs run in the same environment to use, + but not for themselves. The following does not expand the "remove-one" + macro: + + .. code-block:: scheme + + (begin + (define-macro (remove-one a b) b) + (remove-one 1 2)) + + Instead, that program attempts to evaluate an undefined ``remove-one`` + function as an ordinary procedure, and fails. The macro binding introduced + in this program would be available to future programs run in the same + environment. + + The Actinide REPL runs each form as an independent program, so + interactively defining macros in the REPL behaves in an intuitive way. + Programs that embed Actinide must take care to provide sensible ways to + load macro definitions, as well as any supporting functions those macro + definitions require. The embedding guide's ``An.eval`` primitive is the + recommended way to pre-load definitions into a session, as each ``eval`` + binding is run as an independent program, sharing a top-level environment + with future programs run in the same session. + +The :ref:`define-macro` form, introduced in the :ref:`semantics` chapter, +creates macro transformer bindings. In brief, a *macro transformer* is an +ordinary Actinide procedure, whose result is an unevaluated *form*, rather than +a value. The arguments to a macro transformer are also forms, which the macro +transformer can pick apart and manipulate. + +When Actinide's expansion step encounters a list form whose head is a symbol +matching a macro transformer in the top-level environment, the form is removed +from the program. The head is discarded (it only identifies the macro), and the +remaining subforms are passed, un-evaluated, to the macro transformer as +arguments. The result of the macro transformer is inserted into the program in +place of the removed macro form. + +The following example illustrates, by defining a new ``let-one`` special form. This special form has the following syntax: + +.. code-block:: scheme + + (let-one (name form) body) + +When it's reduced, it creates a new environment in which the result of reducing +``form`` is bound to the variable ``name``, then evaluates ``body`` in that +environment. + +.. code-block:: scheme + + (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: + +.. code-block:: scheme + + (let-one (x 1) (+ x 2)) + +The macro transformer receives the forms ``(x 1)`` and ``x``, unevaluated, as +arguments, and substitutes them into a :ref:`quasiquoted <quasiquotes>` form, +which is used as a template for the result of the macro. 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 equivalent to + +.. code-block:: scheme + + ((lambda (x) (+ x 2) 1) + +This program evaluates to 3, without binding ``x`` in the current environment. + +.. _quasiquotes: + +~~~~~~~~~~~ +Quasiquotes +~~~~~~~~~~~ + +Actinide provides three quote-like special forms which are fully handled by the +macro expander, and which are meant to ease the development of macros. + +quasiquote +~~~~~~~~~~ + +Syntax: + +.. code-block:: scheme + + `form + (quasiquote form) + +Evaluation of a quasiquote form produces an expression that reconstructs +``form``. If ``form`` contains no ``unquote`` or ``unquote-splicing`` forms, +then ```form`` produces a form which evaluates to the equivalent of ``'form``. + +The exact expansion of quasiquote forms produces expressions which, when +evaluated, produce equivalents to simpler quoted forms. However, the exact +result of a quasiquoted form is generally a form which, when evaluated, calls a +sequence of built-in procedures to construct lists, rather than the lists +themselves. For example, the form ```(+ 1 2)`` ultimately expands to + +.. code-block:: scheme + + (cons '+ (cons '1 (cons '2 '()))) + +which evaluates to ``'(+ 1 2)``, rather than expanding to ``'(+ 1 2)`` directly. + +unquote +~~~~~~~ + +Syntax: + +.. code-block:: scheme + + ,form + (unquote form) + +This form *must* appear within a ``quasiquote`` form. When the containing +``quasiquote`` form is expanded, the unquoted form is placed in the result +without quoting, so that it will be evaluated normally when the quasiquote form +is evaluated. The result of evaluating ``form`` will be inserted into the +result of the ``quasiquote`` form in place of the ``unquote`` form. + +Example: + +.. code-block:: scheme + + (begin + (define x 5) + `(+ ,x y)) + +This evaluates to a form equivalent to + +.. code-block:: scheme + + '(+ 5 y) + +unquote-splicing +~~~~~~~~~~~~~~~~ + +Syntax: + +.. code-block:: scheme + + ,@form + (unquote-splicing form) + +This form *must* appear within a ``quasiquote`` form. When the containing +``quasiquote`` form is expanded, each form guarded by an ``unquote-splicing`` +form will be inserted unquoted. The guarded form must evaluate to a list, which +is spliced into the ``quasiquote`` form's result. For example, given + +.. code-block:: scheme + + (define x (list 1 2)) + +then these forms + +.. code-block:: scheme + + ; unquote + `(+ ,x) + ; unquote-splicing + `(+ ,@x) + +expand to, respectively, forms equivalent to + +.. code-block:: scheme + + ; unquote + '(+ '(1 2)) + ; unquote-splicing + '(+ 1 2) diff --git a/docs/semantics.rst b/docs/semantics.rst new file mode 100644 index 0000000..9cc19a1 --- /dev/null +++ b/docs/semantics.rst @@ -0,0 +1,441 @@ +.. _semantics: + +######### +Semantics +######### + +.. highlight:: scheme + +Forms are also the most basic unit of Actinide evaluation. Execution of an +Actinide program proceeds by *reducing* one form to a simpler result, until +only a single irreducible form is left (which is the program's result). + +Most Actinide programs consist of a top-level compound form, which must be +fully reduced to run the program to completion. The following sections describe +the mechanism and results of reducing each kind of form. In general, evaluation +proceeds by reducing the inner-most, left-most unreduced form, iteratively, +until all forms have been reduced. + +******** +Literals +******** + +Literal forms reduce to themselves, unchanged. The following forms are +considered literal forms: + +* Integers +* Decmials +* Strings +* Booleans + +For example, the result of reducing ``1`` is ``1``. + +******* +Symbols +******* + +Symbols, other than those that are part of :ref:`special forms <special +forms>`, represent variables in Actinide programs, and reduce to the values of +those variables in the current *environment*. + +In an environment where a symbol has a value, the reduction of that symbol is +the value it's bound to. In an environment where a symbol is not bound to any +value, the reduction of that symbol produces an error and stops the computation. + +For example, in an environmet where the symbol ``x`` is bound to ``5``, the +result of reducing ``x`` is ``5``. + +An Actinide program is run in an initial *top-level environment*, which comes +pre-populated with bindings for all of Actinide's built-in functions and +values, plus any values placed there by the host program. As Actinide reduces a +program, the bindings in that initial environment can change, and additional +environments may be created. The *current environment* is controlled by the +:ref:`lambda` form and by :ref:`procedure application`. + +.. _special forms: + +************* +Special forms +************* + +Lists that begin with one of the following symbols are evaluated specially. + +~~~~~ +quote +~~~~~ + +Syntax: + +.. code-block:: scheme + + (quote form) + +A ``quote`` form guards another form from evaluation. The result of reducing a +quote form is exactly the guarded ``form``. This allows forms that may have +special meaning, such as lists, to be embedded in Actinide programs as literal +values, stripped of their special meaning. + +.. _begin: + +~~~~~ +begin +~~~~~ + +Syntax: + +.. code-block:: scheme + + (begin [form-1 ... form-n]) + +A ``begin`` form fully evaluates each subform in left-to-right order, then +reduces to the value of the final subform. This allows for forms with side +effects to be evaluated (and their results ignored) before evaluating a final +form that produces a result. + +An empty ``begin`` form evaluates to the empty list. + +Example: + +.. code-block:: scheme + + (begin + ; define a function... + (define (f) 1) + ; ...and call it + (f)) + +.. _if: + +~~ +if +~~ + +Syntax: + +.. code-block:: scheme + + (if cond if-true) + (if cond if-true if-false) + +An ``if`` form conditionally evaluates one of two forms based on the result of +a condition. The ``cond`` form is fully evaluated first; if it reduces to a +true value, then the ``if-true`` form is evaluated and the ``if`` form reduces +to its result; otherwise, the ``if-false`` form is evaluated and the ``if`` +form reduces to its result. In either case, the other form is discared without +evaluation. + +An ``if`` form without an ``if-false`` form reduces to nil if the ``cond`` form reduces to a false value. + +The following values are false: + +* the empty list +* ``#f`` +* integer and decimal zeroes +* empty strings +* empty vectors + +All other values are true. + +Example: + +.. code-block:: scheme + + (if #t 'was-true 'was-false) + + (if (goldback-conjecture) + "Eureka!") + +.. _lambda: + +~~~~~~ +lambda +~~~~~~ + +Syntax: + +.. code-block:: scheme + + (lambda formals [body-1...body-n]) + +Defines a procedure taking arguments described by the ``formals`` form, whose +application will evaluate the ``body`` forms in order and will reduce to the +result of the last form. + +The ``formals`` form must have one of the following structures: + +* A list of symbols, each of which will be bound to a single argument when the + procedure is applied, in the order listed. + +* An improper list of symbols. Each symbol other than the final tail symbol + will be bound to an argument from the procedure application; the final tail + symbol will be bound to a list of all arguments that were not bound to any + other symbol. + +* A single symbol, which will be bound to a list of the arguments when the + procedure is applied. + +A ``lambda`` form reduces to a newly-created procedure value whose body is the +list of body forms and whose formal argument list is the formals. + +Each procedure captures the environment in effect when the ``lambda`` form is +evaluated, allowing the procedure body to see variables that were visible at +that time, even if the procedure outlives the context where that environment is +defined. + +Each time a procedure is applied, Actinide creates a new environment that +inherits from the captured environment and binds the values of arguments from +the procedure application to the symbols named in the procedure's ``formals``. +This is the primary mechanism for creating new environments in Actinide. +Procedure application then evaluates the body forms, in that new environment, +in left-to-right order. The result of the final form is the result of the +procedure application. (In fact, procedures whose bodies consist of multiple +forms, or of no forms at all, are converted to a procedure whose body is a +single ``begin`` form.) + +Examples: + +.. code-block:: scheme + + ; Creates a constant function of zero arguments, which always + ; evaluates to 1. + (lambda () 1) + + ; Defines a variable in the current environment (as discussed + ; below), then creates a function of zero arguments that returns + ; that variable. Initially, it will always return 5, but if the + ; value of x is changed in the outer environment, the function's + ; return value will change as well. + (begin + (define x 5) + (lambda () x)) + + ; Defines a function of two arguments, a and b, whose result is + ; the sum of those arguments. This is a simple alias for the + + ; built-in function, illustrating the idea that functions can + ; call other functions. + (lambda (a b) (+ a b)) + + ; Defines a function that takes one or more arguments, with the + ; first argument bound to a (and ignored) and the list of + ; remaining arguments bound to b. This always returns b + ; unchanged, and throws away a. + (lambda (a . b) b) + + ; Defines a function that takes any number of arguments, and + ; returns them as a list. This is a simple alias for the list + ; built-in function. + (lambda a a) + +.. _define: + +~~~~~~ +define +~~~~~~ + +Syntax: + +.. code-block:: scheme + + (define symb form) + (define signature [body-1...body-n]) + +A define form creates a new variable in the current environment, and binds a +value to that variable. There are two variations on this form: simple +definition and procedure definition. + +In the first form, the ``symb`` subform must be a single symbol. The ``form`` +subform is fully reduced, and the resulting value is bound to the variable +``symb`` in the current environment. For example: + +.. code-block:: scheme + + (begin + ; Defines a variable, x, whose initial value is 5. + (define x 5) + ; Evaluates to the value of x. + x) + +In the second, the ``signature`` subform must be a procedure signature: a list +or improper list of symbols. The first element of that list is the name the +procedure will be bound to, while the rest of that list is treated as the +``formals`` form as described under :ref:`lambda`. The list of ``body`` forms become +the resulting procedure's body, as usual. + +Under the hood, the second form is translated into the first automatically - +the form + +.. code-block:: scheme + + (define (sum a b) (+ a b)) + +is exactly equivalent to the form + +.. code-block:: scheme + + (define sum + (lambda (a b) (+ a b))) + +However, when the option is available, procedure definition should be preferred +as it's generally more readable. + +~~~~~~ +values +~~~~~~ + +Syntax: + +.. code-block:: scheme + + (values [body-1...body-n]) + +Where most forms reduce to a single value, the ``values`` form reduces to a +sequence of values, in place. This allows a function or any other form to +reduce to multiple distinct values, which can be inserted into other forms. + +The body forms are evaluated left-to-right, and the ``values`` form reduces to +the resulting values, left-to-right. + +Example: + +.. code-block:: scheme + + (begin + ; A function which returns two values, both equal to its + ; sole argument + (define (two x) (values x x)) + ; = accepts two values and compares them. + (= (two 53))) + +.. _define-macro: + +~~~~~~~~~~~~ +define-macro +~~~~~~~~~~~~ + +Syntax: + +.. code-block:: scheme + + (define-macro symb form) + (define-macro signature [body-1...body-n]) + +A ``define-macro`` form creates a new :ref:`macro transformer <macros>` +function in the current environment's macro table. This is identical to the +:ref:`define` form, but the resulting binding is not visible as a variable, and +affects macro expansion of Actinide programs. Macro bindings using the first +form must bind the symbol to a procedure or built-in function producing exactly +one result. + +.. warning:: + + A ``define-macro`` form which appears within a procedure body will create a + macro in the environment created when the procedure is applied. These + macros are **never** visible to the macro expander, and will have no effect. + +.. _procedure application: + +********************* +Procedure application +********************* + +Any list which is not empty, and not a :ref:`special form <special forms>`, is +a procedure application, applying either a built-in procedure (provided by +Actinide or by the host program) or a procedure defined using the :ref:`lambda` +special form or any of its :ref:`equivalents <define>`. + +Syntax: + +.. code-block:: scheme + + (fn [arg-1...arg-n]) + +The subforms of a list form are evaluated from left to right. The ``fn`` +subform must evaluate to a procedure; the remaining ``body`` forms are +evaluated to produce the values of arguments to that procedure. Once all of the +subforms have been evaluated, the procedure is applied to its arguments, and +the procedure application itself reduces to the result of the applied procedure. + +During the application of a procedure, + +1. A new *child* environment is created from the procedure's captured + environment. In this environment, any name not defined in the child + environment is looked up in the captured environment instead. + +2. The values of the arguments from the function application form are bound to + the names given by the procedure's formal arguments list. + +3. The procedure's body forms are evaluated from left to right in the child + environment. + +4. The result of the last form in the procedure body is used as the result of + the function application. + +~~~~~~~~~~~~~~~~~~~ +Loops and Recursion +~~~~~~~~~~~~~~~~~~~ + +Actinide has no primitives dedicated to repeating parts of a program. To loop, +a procedure must recurse. Actinide guarantees that recursion in *tail position* +can proceed arbitrarily far without exhausting any resources solely due to the +number of recursive calls. Actinide guarantees tail recursion. + +The following forms are considered to be in tail position: + +* The final form of a :ref:`procedure body <lambda>` is in tail position with + respect to the application of that procedure. + +* The final form of a :ref:`begin` form is in tail position with respect to the + ``begin`` form itself. + +* The ``if-true`` form of an :ref:`if` form whose condition is true, and the + ``if-false`` form of an ``if`` form whose condition is not true, is in tail + position with respect to the ``if`` form. + +* If a form is in tail position with respect to another form, it is also in + tail position for any form that form is in the tail position of, and so on + outwards until the form is either in tail position with respect to the root + of the program or a form is found for which the containing form is not in + tail position. + +As an example, the following implementation of the factorial algorithm is +recursive, but the recursion does not appear in tail position (it is not *tail +recursive*): + +.. code-block:: scheme + + (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 the inner application of +``factorial``, the reduction of the outer ``factorial`` application must +continue so that it can 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`` + +.. note:: + + This warning leaks some implementation details, obviously. The exact + failure mode should not be relied on; the key property is that + deeply-recursive programs will raise an error when they exhaust the + implementation's resources. + +The following implementation of the factorial algorithm *is* tail-recursive: + +.. code-block:: scheme + + (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. diff --git a/docs/syntax.rst b/docs/syntax.rst new file mode 100644 index 0000000..b84e0ae --- /dev/null +++ b/docs/syntax.rst @@ -0,0 +1,211 @@ +###### +Syntax +###### + +.. highlight:: scheme + +The most basic unit of Actinide's syntax is the *form*. An Actinide program +consists of a single top-level form, which may include subforms and +sub-subforms within it nested arbitrarily deeply. + +******** +Comments +******** + +An Actinide program may contain comments. Comments are removed during parsing +and are not technically forms, but they're included here for completeness. A comment begins with a ``;`` and continues to the next newline character or until the end of the program, whichever comes first. + +Examples: + +* ``; this is a comment.`` + +***** +Atoms +***** + +The following forms are *atomic* - they do not contain any subforms, and can be +reduced in a single step to a final value. + +~~~~~~~~ +Integers +~~~~~~~~ + +An Actinide integer represents a mathematical integer: a precise number with no +fractional part, which may be positive, negative, or zero. Actinide integers do +not have a fixed range - there is no built-in maximum or minimum integer. + +The syntax of an integer consists of an optional leading ``-`` sign for +negative integers, followed by any sequence of digits and underscores. +Underscores should be used to separate thousands. + +Examples: + +* ``10`` +* ``-2_049`` + +.. note:: + + Practically, Actinide integers are represented by Python ``int`` objects, + and share their characteristics. This is not part of their specification, + but the formal properties of Actinide constracts aren't fully separable + from the implementation at this time. + +~~~~~~~~ +Decimals +~~~~~~~~ + +An Acdinide decimal represents a precise base-ten fractional value with a +finite number of decimal places. Actinide decimals do not have a fixed limit on +range or precision. + +The syntax of a decimal consists of an optional leading ``-`` sign for negative +decimal numbers, followed by an optional sequence of digits and underscores for +the integral part, followed by a ``.``, followed by an optional sequence of +digits and underscores for the fractional part, followed by an optional +exponent part consisting of an ``e`` and a sequence of digits and underscores. + +A decimal form *must* have a non-empty integral part or a non-empty fractional +part. As with integers, underscores should be used as thousands separators. + +Examples: + +* ``0.0`` +* ``-2_049.501_2`` +* ``2e10`` + +.. note:: + + Practically, Actinide decimals are represented by Python + ``decimal.Decimal`` values in the default decimal context. I haven't fully + fleshed out the Actinide semantics of decimal operations, so the Python + semantics leak through. This means that, for example, there is a negative + zero (which is equal to zero), and that ``1e1`` and ``10`` are different + (but equal) values. + +~~~~~~~ +Strings +~~~~~~~ + +An Actinide string represents a sequence of Unicode characters. + +The syntax of a string consists of a leading ``"``, followed by any sequence of +unescaped characters or escaped characters, followed by a trailing ``"``. An +escaped character is either the sequence ``\"`` or the sequence ``\\``; an +unescaped character is any Unicode character other than ``\`` or ``"``. The +enclosing quote marks and escape marks are not part of the string's value, and +are removed during parsing. + +Line breaks and non-printing characters can appear within a string. + +Examples: + +* ``"Hello, world."`` +* ``"😡💩🚀"`` +* ``"Quoth the raven, \"Four Oh Four.\""``. + +.. note:: + + As with most other Actinide primitives, strings are implemented directly on + top of a common Python type: ``str`` itself. The Python representation is + not part of the language, but does leak through in places. + +~~~~~~~~ +Booleans +~~~~~~~~ + +A boolean value represents one of two logical states: true (represented by +exactly ``#t``) and false (``#f``). + +~~~~~~~ +Symbols +~~~~~~~ + +Symbols represent variables and special keywords in an Actinide program. + +The syntax of a symbol is a sequence of unicode characters other than quotes, +semicolons, tabs, spaces, and newlines, which is not an integer, decimal, or +boolean. + +Examples: + +* ``x`` +* ``if`` +* ``+`` +* ``my-🚀`` + +************** +Compound Forms +************** + +The following forms consist of both the compound form itself and a sequence of +subforms. + +~~~~~ +Lists +~~~~~ + +Lists represent most kinds of Actinide syntax other than atoms. + +The syntax of a list consists of an opening ``(``, followed by zero or more +subforms, separated by spaces, tabs, or newlines, followed by a closing ``)``. +The subforms of a list can be any Actinide form, including another list. + +Examples: + +* ``(foo)`` +* ``()`` +* ``(1 a #f)`` + +~~~~~~ +Conses +~~~~~~ + +Conses represent pairs of forms. + +The syntax of a dotted pair consists of an opening ``(``, followed by a *head* +form, followed by a ``.``, followed by a *tail* form, followed by a closing +``)``. A dotted pair appearing as the tail of a dotted pair does not need to be +enclosed in parentheses, and can be represented by removing the preceding +``.``, instead. + +Examples: + +* ``(1 . 2)`` +* ``(1 2 . 3)`` +* ``((ll . lr) . (rl . rr))`` + +Conses whose tail form is the empty list are themselves lists. A cons whose +tail form is not a list is an *improper list*. + +~~~~~~ +Quotes +~~~~~~ + +A quote form prevents the evaluation of its contained form. + +The syntax of a quote form is either a list beginning with the symbol ``quote`` +and containing exactly two subforms, or a leading ``'`` followed by a single +form (which is exactly equivalent to ``(quote form)``). + +Examples: + +* ``'()``, ``(quote ())`` +* ``'a``, ``(quote a)`` +* ``'(1 . 2)``, ``(quote (1 . 2))`` + +~~~~~~~~~~~ +Quasiquotes +~~~~~~~~~~~ + +Actinide has a fully-featured :ref:`macro system <macros>`. To support the +macro system, the language includes a system for constructing syntactic forms +programmatically. The following special forms are part of that system: + +* ```form``, ``(quasiquote form)`` +* ``,form``, ``(unquote form)`` +* ``,@form``, ``(unquote-splicing form)`` + +Full discussion of quasiquoted forms is covered in the section on macros. These +forms cannot be reduced, and will generally raise an error if they're +evaluated, but they're normally eliminated during macro expansion before +evaluation. |