== Norvig's lis.py: a simple functional interpreter

Contents:

* <<scheme_syntax_sec>>
* <<imports_sec>>
* <<parser_sec>>
* <<environment_sec>>
* <<repl_sec>>
* <<evaluator_sec>>
* <<procedure_sec>>
* <<conclusion_sec>>

https://en.wikipedia.org/wiki/Peter_Norvig[Peter Norvig] of Stanford University wrote
https://github.com/fluentpython/lispy/blob/main/original/norvig/lis.py[_lis.py_]:
an interpreter for a subset of the Scheme dialect of Lisp
in 132 lines of readable Python code.

Why should you study _lis.py_? This is what I got out of it:

. _lis.py_ is a beautiful example of idiomatic Python code;
. The simplicity of Scheme is a master class of language design;
. Learning how an interpreter works gave me a deeper understanding of Python and programming languages in general—interpreted or compiled.

Before looking at the Python code,
let's get a little taste of Scheme—in case you haven't seen it (or Lisp) before.

[[scheme_syntax_sec]]
=== Scheme Syntax

Everything in Scheme is an expression.
There are no infix operators:
all expressions use prefix notation like `(+ x 13)` instead of `x + 13`.
The same prefix notation is used for function calls—e.g. `(gcd x 13)`—and
special forms—e.g. `(define x 13)`,
which we'd write as the assignment statement `x = 13` in
Python.
The notation used by Scheme and most Lisp dialects is known as _S-expression_.footnote:[People
complain about too many parenthesis in Lisp,
but thoughtful indentation and a good editor mostly take care of that issue.
The main readability problem is using the same
`(f …)` notation for function calls and special forms like `(define …)`,
`(if …)`, and `(quote …)` that don't behave at all like function calls.]

Here is a simple example in Scheme:

[[ex_gcd_scheme]]
.Greatest common divisor in Scheme.
====
[source, scheme]
----
(define (mod m n)
    (- m (* n (quotient m n))))

(define (gcd m n)
    (if (= n 0)
        m
        (gcd n (mod m n))))

(display (gcd 18 45))
----
====

<<ex_gcd_scheme>> shows three Scheme expressions:
two function definitions—`mod` and `gcd`—and a call to `display`
which will output 9—the result of `(gcd 18 45)`.
Here is the same code in Python (shorter than an English explanation of the recursive
https://en.wikipedia.org/wiki/Euclidean_algorithm[_Euclidean algorithm_]):

[[ex_gcd_python]]
.Same as <<ex_gcd_scheme>>, written in Python.
====
[source, py]
----
def mod(m, n):
    return m - (m // n * n)

def gcd(m, n):
    if n == 0:
        return m
    else:
        return gcd(m, mod(m, n))

print(gcd(18, 45))
----
====

In idiomatic Python I'd use the `%` operator instead of reinventing `mod`,
and it would be more efficient to use a `while` loop instead of recursion.
But I wanted to show two function definitions,
and make the examples as similar as possible,
to help you read the Scheme code.

Scheme has no iterative control flow commands like `while` or `for`.
Iteration is done with recursion.
Note how there are no assignments in the Scheme and Python examples.
Extensive use of recursion and minimal use of assignment
are hallmarks of programming in a functional style.footnote:[To
make iteration through recursion practical and efficient,
Scheme and other functional languages implement _proper tail calls_. For more about this, see <<soapbox_with_match>>.]

Now let's review the code of the Python 3.10 version of _lis.py_.
The complete source code with tests is in the
https://github.com/fluentpython/example-code-2e/tree/master/18-with-match/lispy/py3.10/[_18-with-match/lispy/py3.10/_]
directory of the Github repository
https://github.com/fluentpython/example-code-2e[_fluentpython/example-code-2e_].


[[imports_sec]]
=== Imports and types

<<lis_top_ex>> shows the first lines of _lis.py_.
The use of `TypeAlias` and the `|` type union operator require Python 3.10.

[[lis_top_ex]]
.`lis.py`: top of the file
====
[source, py]
----
include::lis.py[tags=IMPORTS]
----
====

The types defined are:

`Symbol`:: Just an alias for `str`.
In _lis.py_, `Symbol` is used for identifiers,
there is no string data type with operations such as slicing, splitting etc.footnote:[But Norvig's second interpreter,
https://github.com/fluentpython/example-code-2e/blob/master/18-with-match/lispy/original/lispy.py[_lispy.py_],
supports strings as a data type, as well as advanced features like
syntactic macros, continuations, and proper tail calls.
However, _lispy.py_ is almost three times longer than _lis.py_—and
much harder to understand.]

`Atom`:: A simple syntactic element such as a number or a `Symbol`—as opposed to a composite structure made of distinct parts, like a list.

`Expression`:: The building blocks of Scheme programs are expressions made of atoms and lists, possibly nested.


[[parser_sec]]
=== The Parser

Norvig's parser is 36 lines of code showcasing the power of Python applied to handling the
simple recursive syntax of S-expression—without string data, comments, macros, and other features of standard Scheme that make parsing more complicated.

[[lis_parser_ex]]
.`lis.py`: the main parsing functions
====
[source, py]
----
include::code/18-with-match/lispy/py3.10/lis.py[lines=27..36]
    # more parsing code omitted in book listing
----
====

The main function of that group is `parse` which takes an S-expressions as a `str`
and returns an `Expression` object, as defined in <<lis_top_ex>>:
an `Atom` or a `list` that may contain more atoms and nested lists.

Norvig uses a smart trick in `tokenize`:
he adds spaces before and after each parenthesis in the input and then splits it,
resulting in a list of syntactic tokens with `'('` and `')'`
as separate tokens.
This shortcut works because there is no string type in the little Scheme of _lis.py_, so every `'('` or `')'` is an expression delimiter.
The recursive parsing code is in `read_from_tokens`,
a 14-line function that you can read in the
https://github.com/fluentpython/example-code-2e/blob/6527037ae7319ba370a1ee2d9fe79214d0ed9452/18-with-match/lispy/py3.10/lis.py#L35[_fluentpython/example-code-2e_] repository.
I will skip it because I want to focus on the other parts of the interpreter.

Here are some doctests extracted from
https://github.com/fluentpython/example-code-2e/blob/master/18-with-match/lispy/py3.10/examples_test.py[_lispy/py3.10/examples_test.py_]:

[source, pycon]
----
include::code/18-with-match/lispy/py3.10/examples_test.py[tags=PARSE]
----

The parsing rules for this subset of Scheme are simple:

. A token that looks like a number is parsed as a `float` or `int`.
. Anything else that is not `'('` or `')'` is parsed as a `Symbol`—a `str` to be used as an identifier. This includes source text like `+`, `set!`, and `make-counter` that are valid identifiers in Scheme but not in Python.
. Expressions inside `'('` and `')'` are recursively parsed as lists containing atoms or nested lists that may contain atoms and more nested lists.

Using terminology of the Python interpreter, the output of `parse` is an AST (Abstract Syntax Tree):
a convenient representation of the Scheme program as nested lists forming a tree-like structure,
where the outermost list is the trunk, inner lists are the branches, and atoms are the leaves.

[[environment_sec]]
=== The Environment

The `Environment` class extends `collections.ChainMap` adding
a `change` method to update a value inside one of the chained dicts,
which `ChainMap` instances hold in a list of mappings: the `self.maps` attribute.
The `change` method is needed to support the Scheme `(set! …)` form, described later.

[[environment_class_ex]]
.`lis.py`: the `Environment` class.
====
[source, py]
----
include::code/18-with-match/lispy/py3.10/lis.py[tags=ENV_CLASS]
----
====

Note that the `change` method only updates existing keys.footnote:[The `# type: ignore[index]` comment is there because of _typeshed_ issue https://github.com/python/typeshed/issues/6042[#6042] which is unresolved as I review this chapter. `ChainMap` is annotated as `MutableMapping` but the type hint in the `maps` attribute says it's a list of `Mapping`, indirectly making the whole `ChainMap` immutable as far as Mypy is concerned.]
Trying to change a key that is not found raises `KeyError`.

This doctest shows how `Environment` works:

[source, pycon]
----
include::code/18-with-match/lispy/py3.10/examples_test.py[tags=ENVIRONMENT]
----
<1> Assigning with `[]` overwrites or inserts new items, but always in the first mapping, `inner_env` in this example.
<2> `env.change('b', 333)` seeks the `'b'` key and assigns a new value to it in-place, in the `outer_env`.

Next is the `standard_env()` function, which builds and returns an `Environment` loaded
with predefined functions, similar to Python's `__builtins__` module that is always available.

[[lis_std_env_ex]]
.`lis.py`: `standard_env()` builds and returns the global environment
====
[source, py]
----
include::code/18-with-match/lispy/py3.10/lis.py[lines=77..85]
            # omitted here: more operator definitions
include::code/18-with-match/lispy/py3.10/lis.py[lines=92..97]
            # omitted here: more function definitions
include::code/18-with-match/lispy/py3.10/lis.py[lines=111..116]
----
====

The `env` mapping is loaded with:

* all functions from Python's `math` module;
* selected operators from Python's `op` module;
* simple but powerful functions built with Python's `lambda`;
* Python built-ins renamed like `callable` as `procedure?` or directly mapped like `round`.

Finally, `standard_env()` returns `env`.

[[repl_sec]]
=== The REPL

Norvig's REPL (Read-Eval-Print-Loop) is easy to undersand but not user-friendly.
If no command-line arguments are given to _lis.py_,
the `repl()` function is invoked by `main()`—defined at the end of the module.
At the `lis.py>` prompt we must enter correct and complete expressions—if
we forget to close one parenthesis, _lis.py_ crashes.footnote:[As I studied
Norvig's _lis.py_ and _lispy.py_, I started a fork named
https://github.com/fluentpython/lispy/blob/main/mylis[_mylis_]
which adds some features, including a REPL that accepts partial S-expressions
and prompts for the continuation, similar to how Python's REPL
knows we are not finished and presents the secondary prompt `...` until
we enter a complete expression or statement that can be evaluated.
_mylis_ also handles a few errors gracefully, but it's still easy to crash.
It's not nearly as robust as Python's REPL.]

[[ex_lispy_repl]]
.The REPL functions
====
[source, python3]
----
include::code/18-with-match/lispy/py3.10/lis.py[tags=REPL]
----
====

`repl(prompt: str = 'lis.py> ') -> NoReturn`::
    Calls `standard_env()` to provide built-in functions for the global environment,
    then enters an infinite loop reading and parsing each input line,
    evaluating it in the global environment and displaying the result—unless it's `None`.
    The `global_env` may be modified by `evaluate`.
    For example when a user defines a new global variable or named function,
    it is stored in the first mapping of the environment—the empty
    `dict` in the `Environment` constructor call in the first line of `repl`.

`lispstr(exp: object) -> str`::
    The inverse function of `parse`:
    given a Python object representing an expression,
    `parse` returns the Scheme source code for it.
    For example, given `['+', 2, 3]`, the result is `'(+ 2 3)'`.


[[evaluator_sec]]
=== The Evaluator

Now we can appreciate the beauty of Norvig's expression evaluator—made
a little prettier with `match/case`.
The `evaluate` function in <<ex_evaluate_match>> takes
an `Expression` built by `parse` and an `Environment`.

The body of `evaluate` is a single `match` statement with an expression `exp` as the subject.
The `case` patterns express the syntax and semantics of Scheme with amazing clarity.

[[ex_evaluate_match]]
.`evaluate` takes an expression and computes its value.
====
[source, python3]
----
include::code/18-with-match/lispy/py3.10/lis.py[tags=EVALUATE]
----
====

Let's study each `case` clause and what it does.
In some cases I added comments showing an S-expression that would
match the pattern below, when parsed into a Python list.
Doctests extracted from
https://github.com/fluentpython/example-code-2e/blob/00e4741926e1b771ee7c753148b1415c0bd12e39/02-array-seq/lispy/py3.10/examples_test.py[_examples_test.py_] demonstrate each `case`.


[[eval_atom_sec]]
==== Evaluating numbers

[source, python3]
----
    case int(x) | float(x):
        return x
----

Subject&#x3a;::
    Instance of `int` or `float`.

Action&#x3a;::
    Return value as is.

Example&#x3a;::

[source, pycon]
----
include::code/18-with-match/lispy/py3.10/examples_test.py[tags=EVAL_NUMBER]
----

==== Evaluating symbols

[source, python3]
----
    case Symbol(var):
        return env[var]
----

Subject&#x3a;::
    Instance of `Symbol`, i.e. a `str` used as an identifier.

Action&#x3a;::
    Look up `var` in `env` and return its value.

Examples&#x3a;::

[source, pycon]
----
include::code/18-with-match/lispy/py3.10/examples_test.py[tags=EVAL_SYMBOL]
----

==== (quote …)

The `quote` special form treats atoms and lists as data instead of expressions to be evaluated.

[source, python3]
----
    # (quote (99 bottles of beer))
    case ['quote', x]:
        return x
----

Subject&#x3a;::
    List starting with the symbol `'quote'`, followed by one expression `x`.

Action&#x3a;::
    Return `x` without evaluating it.

Examples&#x3a;::

[source, pycon]
----
include::code/18-with-match/lispy/py3.10/examples_test.py[tags=EVAL_QUOTE]
----

Without `quote`, each expression in the test would raise an error:

* `no-such-name` would be looked up in the environment, raising `KeyError`;
* `(99 bottles of beer)` cannot be evaluated because the number 99 is not a `Symbol` naming a special form, operator, or function;
* `(/ 10 0)` would raise `ZeroDivisionError`.

.Why languages have reserved keywords
****
Although simple, `quote` cannot be implemented as a function.
Its special power is to prevent the interpreter from
evaluating `(f 10)` in the expression `(quote (f 10))`:
the result is simply list with a `Symbol` and an `int`.
In contrast, in a function call like `(abs (f 10))`,
the interpreter evaluates `(f 10)` before invoking `abs`.
That's why `quote` is a reserved keyword: it must be handled as a special form.

In general, reserved keywords are needed:

* To introduce specialized evaluation rules, as in `quote` and `lambda`—which don't evaluate any of their sub-expressions;
* To change the control flow, as in `if` and function calls—which also have special evaluation rules);
* To manage the environment, as in `define` and `set`.

This is also why Python and programming languages in general need reserved keywords.
Think about Python's `def`, `if`, `yield`, `import`, `del`, and what they do.
****


==== (if …)

[source, python3]
----
    # (if (< x 0) 0 x)
    case ['if', test, consequence, alternative]:
        if evaluate(test, env):
            return evaluate(consequence, env)
        else:
            return evaluate(alternative, env)
----

Subject&#x3a;::
    List starting with `'if'` followed by three expressions: `test`, `consequence`, and `alternative`.

Action&#x3a;::
    Evaluate `test`...
    * if true, evaluate `consequence` and return its value;
    * otherwise, evaluate `alternative` and return its value.

Examples&#x3a;::

[source, pycon]
----
include::code/18-with-match/lispy/py3.10/examples_test.py[tags=EVAL_IF]
----

The `consequence` and `alternative` branches must be single expressions.
If more than one expression is needed in a branch, you can combine
them with `(begin exp1 exp2…)`, provided as a function in _lis.py_—see
<<lis_std_env_ex>>.

==== (lambda …)

Scheme's `lambda` form defines anonymous functions.
It doesn't suffer from the limitations of Python's `lambda`:
any function that can be written in Scheme can be written using the `(lambda …)` syntax.

[source, python3]
----
    # (lambda (a b) (/ (+ a b) 2))
    case ['lambda' [*parms], *body] if body:
        return Procedure(parms, body, env)
----

Subject&#x3a;::
    List starting with `'lambda'` followed by:
    * list of zero or more parameter names;
    * one or more expressions collected in `body` (the guard ensures `body` is not empty).

Action&#x3a;::
    Create and return a new `Procedure` instance with the parameter names, the list of expressions as the body, and the current environment.

Example&#x3a;::

[source, pycon]
----
include::code/18-with-match/lispy/py3.10/examples_test.py[tags=EVAL_LAMBDA]
----

The `Procedure` class implements the concept of a closure:
a callable object holding parameter names,
a function body and a reference to the environment
in which the function is defined.
We'll study the code for `Procedure` in a moment.


==== (define …)

The `define` keyword is used in two different syntactic forms.
The simplest is:

[source, python3]
----
    # (define half (/ 1 2))
    case ['define', Symbol(name), value_exp]:
        env[name] = evaluate(value_exp, env)
----

Subject&#x3a;::
    List starting with `'define'` followed by a `Symbol` and an expression.

Action&#x3a;::
    Evaluate the expression and put its value into `env`, using `name` as key.

Example&#x3a;::

[source, pycon]
----
include::code/18-with-match/lispy/py3.10/examples_test.py[tags=EVAL_DEFINE]
----

The doctest for this `case` creates a `global_env` so that we can
verify that `evaluate` puts `answer` into that `Environment`.

We can use that simple `define` form to create variables or to bind names to anonymous functions,
using a `(lambda …)` form as the `value_exp`.

Standard Scheme provides a shortcut for defining named functions.
That's the second `define` form:

[source, python3]
----

    # (define (average a b) (/ (+ a b) 2))
    case ['define', [Symbol(name), *parms], *body] if body:
        env[name] = Procedure(parms, body, env)
----

Subject&#x3a;::
    List starting with `'define'` followed by:
    * a list starting with a `Symbol(name)`, followed by zero or more items collected into a list named `parms`;
    * one or more expressions collected in `body` (the guard ensures `body` is not empty).

Action&#x3a;::
    * Create a new `Procedure` instance with the parameter names, the list of expressions as the body, and the current environment;
    * put the `Procedure` into `env`, using `name` as key.


[[test_case_defun]]
.Defining a function named `%` that computes a percentage.
====
[source, pycon]
----
include::code/18-with-match/lispy/py3.10/examples_test.py[tags=EVAL_DEFUN]
----
====

Again the doctest creates a `global_env`.
After calling `evaluate`, we check that `%` is bound to a `Procedure`
that takes two numeric arguments and returns a percentage.

The pattern for the second `define` `case` does not enforce that the items in `parms` are all `Symbol` instances;
I'd have to check that before building the `Procedure`,
but I didn't—to keep the code as easy to follow as Norvig's.



==== (set! …)

The `set!` form changes the value of a previously defined variable.footnote:[Assignment is one of the first features taught in many programming tutorials, but `set!` only appears on page 220 of the best known Scheme book, Abelson, Sussman & Sussman's
https://mitpress.mit.edu/sites/default/files/sicp/index.html[_Structure and Interpretation of Computer Programs, Second Edition_] (a.k.a. SICP or the _Wizard Book_).
Coding in a functional style can take us very far without the state changes
that are typical of imperative and Object-Orietented programming.]

[source, python3]
----
    # (set! n (+ n 1))
    case ['set!', Symbol(name), value_exp]:
        env.change(name, evaluate(value_exp, env))
----

Subject&#x3a;::
    List starting with `'set!'`, followed by a `Symbol` and an expression.

Action&#x3a;::
    Update the value of `name` in `env` with the result of evaluating the expression.

The `Environment.change` method traverses the chained environments from local to global,
and updates the first occurrence of `name` with the new value.
Without `set!`, we could use Python's `ChainMap` as the `Environment` type everywhere
in this interpreter.

.Python's `nonlocal` and Scheme's `set!` address the same issue
****
The use of the `set!` form is related to the use of the `nonlocal` keyword in Python:
declaring `nonlocal x` allows `x = 10` to update a previously defined `x` variable
outside of the local scope.
Without a `nonlocal x` declaration,
`x = 10` will always create a local variable in Python, as we saw in <<nonlocal_sec>>.

Similarly, `(set! x 10)` updates a previously defined `x` that may be
outside of the local environment of the function.
In contrast, the variable `x` in `(define x 10)` is always a local variable, created or updated in the local environment.

Both `nonlocal` and `(set! …)` are needed to update program state held in variables within a closure.
<<ex_average_fixed>> demonstrated the use of `nonlocal` to implement a function to compute a running average, holding an item `count` and `total` in a closure.
Here is that same idea, written in the Scheme subset of _lis.py_:

[source, scheme]
----
(define (make-averager)
    (define count 0)
    (define total 0)
    (lambda (new-value)
        (set! count (+ count 1))
        (set! total (+ total new-value))
        (/ total count)
    )
)
(define avg (make-averager))  # <1>
(avg 10)  # <2>
(avg 11)  # <3>
(avg 15)  # <4>
----
<1> Creates a new closure with the inner function defined by `lambda`, and the variables `count` and `total` initialized to 0; binds the closure to `avg`.
<2> Returns 10.0.
<3> Returns 10.5.
<4> Returns 12.0.

The code above is one of the tests in
https://github.com/fluentpython/example-code-2e/blob/master/18-with-match/lispy/py3.10/examples_test.py[_lispy/py3.10/examples_test.py_].

****

Now we get to a function call.

[[function_call_sec]]
==== Function call

[source, python3]
----
    # (gcd (* 2 105) 84)
    case [func_exp, *args] if func_exp not in KEYWORDS:
        proc = evaluate(func_exp, env)
        values = [evaluate(arg, env) for arg in args]
        return proc(*values)
----

Subject&#x3a;::
    List with one or more items. +
    The guard ensures that `func_exp` is not one of
    `['quote', 'if', 'define', 'lambda', 'set!']`—listed right before `evaluate` in <<ex_evaluate_match>>. +
    The pattern matches any list with one or more expressions,
    binding the first expression to `func_exp` and the rest to `args` as a list, which may be empty.

Action&#x3a;::
    * Evaluate `func_exp` to obtain a function `proc`;
    * Evaluate each item in `args` to build a list of argument values;
    * Call `proc` with the values as separate arguments, returning the result.

Example&#x3a;::

[source, pycon]
----
include::code/18-with-match/lispy/py3.10/examples_test.py[tags=EVAL_CALL]
----

The preceding doctest continues from <<test_case_defun>>:
it assumes `global_env` has a function named `%`.
The arguments given to `%` are arithmetic expressions,
to emphasize that the arguments are evaluated before the function is called.

The guard in this `case` is needed because `[func_exp, *args]`
matches any sequence subject with one or more items.
However, if `func_exp` is a keyword,
and the subject did not match any previous case,
then it is really a syntax error.


==== Catch syntax errors

If the subject `exp` does not match any of the previous cases,
the catch-all `case` raises `SyntaxError`:

[source, python3]
----
    case _:
        raise SyntaxError(lispstr(exp))
----

Here is an example of a malformed `(lambda …)` reported as a `SyntaxError`:

[source, pycon]
----
include::code/18-with-match/lispy/py3.10/examples_test.py[tags=EVAL_SYNTAX_ERROR]
----

If the `case` for function call did not have
that guard rejecting keywords, the `(lambda is not like this)`
expression would be handled as a function call,
which would raise `KeyError` because `'lambda'` is not part of the environment—just like `lambda` is not a Python built-in function.


[[procedure_sec]]
=== Procedure: a class implementing a closure

The `Procedure` class could very well be named `Closure`,
because that's what it represents:
a function definition together with an environment.
The function definition includes the name of the parameters and the expressions that make up the body of the function.
The environment is used when the function is called to provide the values of
the _free variables_: variables that appear in the body of the function but that
are not parameters, local variables, or global variables.
We saw the concepts of _closure_ and _free variable_ in <<closures_sec>>.

We learned how to use closures in Python,
but now we can dive deeper and see how a closure is implemented in _lis.py_.

[source, python]
----
include::code/18-with-match/lispy/py3.10/lis.py[tags=PROCEDURE]
----
<1> Called when a function is defined by the `lambda` or `define` forms.
<2> Save the parameter names, body expressions, and environment for later use.
<3> Called by `proc(*values)` in the last line of the `case [func_exp, *args]` clause.
<4> Build `local_env` mapping `self.parms` as local variable names and the given `args` as values.
<5> Build a new combined `env` putting `local_env` first, and then `self.env`—the environment that was saved when the function was defined.
<6> Iterate over each expression in `self.body`, evaluating it in the combined `env`.
<7> Return the result of the last expression evaluated.

There are a couple of simple functions after `evaluate` in
https://github.com/fluentpython/example-code-2e/blob/master/18-with-match/lispy/py3.10/lis.py[_lis.py_]: `run` reads a complete Scheme program and executes it,
and `main` calls `run` or `repl` depending on the command line—similar to what Python does.
I will not describe those functions because there's nothing new in them.
My goals were to share with you the beauty of Norvig's little interpreter,
to give more insight into how closures work,
and to show how `match/case` is a great addition to Python.

[[conclusion_sec]]
=== Wrapping up

Takeaways:
