environment.py

#

Functions for defining the environment. Take a look especially at the Environment class, which implements the logic for lexical scoping.

from functools import reduce
from typing import (
    Any,
    Callable,
    Generic,
    Sequence,
    TypeVar,
    Union,
    Optional,
)
from dataclasses import dataclass, field
import operator as op

#

Represents a variable. Evaluating a symbol means looking it up in the current frame.

@dataclass(eq=True, frozen=True)
class Symbol:

#

A frame is the term used by the authors of SICP to refer to variables in the the current closure.

    name: str


Atom = Union[bool, str, int, float, Symbol, "UserFunction", "PrimitiveFunction[Any]"]
Expr = Union[Sequence["Expr" | Atom], Atom]

#

Frame = dict[Symbol, Atom]

#

Represents the current environment. An environment consists of a frame, together with possibly a reference to the outer frame.

This is how lexical scoping works: variables in the current scope might shadow variables in the outer scope.

@dataclass
class Environment:

#

    vars: Frame = field(default_factory=dict)
    outer: Optional["Environment"] = None

#

Lookup variable in the environment. Lexical scoping is used: if the variable is not found in the current frame, we look it up in the outer frame recursively.

    def lookup_variable(self, variable: Symbol) -> Atom | None:

#

        var = self.vars.get(variable)
        if var is not None:
            return var

        if self.outer is not None:
            return self.outer.lookup_variable(variable)

        return None

#

Extend the current environment with the values provided by ‘values’. Creates a new frame.

    def extend_environment(self, values: list[tuple[Symbol, Atom]]) -> "Environment":

#

        return Environment(vars=dict((k, v) for k, v in values), outer=self)

#

Update the current environment. This attaches a new variable to the current frame.

    def update_environment(self, symbol: Symbol, value: Atom) -> None:

#

        self.vars[symbol] = value

#

Represents a lambda function. It has a list of args and a body. It remembers the environment in which it was created.

@dataclass
class UserFunction:

#

    body: Expr
    env: Environment
    args: list[Symbol]


SubTypeAtom = TypeVar("SubTypeAtom", bound=Expr)

#

A primitive function is a non-Lisp function, defined in the implementing language.

We give it a function and a docstring to create it.

@dataclass
class PrimitiveFunction(Generic[SubTypeAtom]):

#

    func: Callable[[Sequence[SubTypeAtom]], SubTypeAtom]
    doc: str

#

    def __call__(self, args: Sequence[SubTypeAtom]) -> SubTypeAtom:
        return self.func(args)

#

The standard environment which includes built-in functions.

def standard_env() -> Environment:

#

    return Environment(
        vars={
            Symbol("+"): PrimitiveFunction(func=add, doc="Add a list of numbers."),
            Symbol("-"): PrimitiveFunction(
                func=lambda a: op.sub(*a), doc="Subtract a list of numbers."
            ),
            Symbol("dec"): PrimitiveFunction(
                func=lambda a: a[0] - 1, doc="Decrement a number."
            ),
            Symbol("*"): PrimitiveFunction(
                func=mult, doc="Multiply a list of numbers."
            ),
            Symbol("<"): PrimitiveFunction(
                func=lambda a: op.lt(*a), doc="Less than. Accepts two arguments."
            ),
            Symbol("="): PrimitiveFunction(
                func=lambda a: op.eq(*a), doc="Equals. Accepts two arguments."
            ),
            Symbol("doc"): PrimitiveFunction(
                func=doc, doc="Print a function docstring."
            ),
            Symbol("car"): PrimitiveFunction(
                func=lambda a: car(*a),  # pyright: ignore
                doc="Return first element of list.",
            ),
        },
        outer=None,
    )

#

Print the docstring of the given function. The argument must be of type PrimitiveFunction.

def doc(expr: Sequence[Expr]) -> Expr:

#

    if len(expr) != 1:
        raise RuntimeError("Need only one argument.")
    first_el = expr[0]

    if not isinstance(first_el, PrimitiveFunction):
        raise RuntimeError("Can only show doc of built-ins.")

    return first_el.doc

#

Get the first element of a sequence of expressions.

def car(expr: Sequence[Expr]) -> Expr:

#

    return expr[0]

#

Return rest of list.

def cdr(expr: Sequence[Expr]) -> Expr:

#

    if not isinstance(expr, list):
        raise RuntimeError("expr must be a list.")
    return expr[1:]

#

Return second element in a sequence.

def cadr(expr: Sequence[Expr]) -> Expr:

#

    return expr[1]

#

Returns the third element in a sequence.

def caddr(expr: Sequence[Expr]) -> Expr:

#

    return expr[2]

#

def cadddr(expr: Sequence[Expr]) -> Expr:
    return expr[3]

#

def add(args: Sequence[int | float]) -> float:
    return reduce(lambda acc, curr: acc + curr, args, 0.0)

#

def mult(args: Sequence[int | float]) -> float:
    return reduce(lambda acc, curr: acc * curr, args, 1.0)