computation.environment README

Introduction

The compoutation.environment library provides protocols and implementations for environments (not necessarily Common Lisp environments or Lisp environments), that is data structures which manage bindings of names to values. Different kinds of environments are available:

• Global environments
• Lexical environments

Lexical environments can be organized in a hierarchy such that child environments inherit entries from their ancestors.

Another feature are first-class namespaces: environments contain namespaces which in turn control how names are organized and processed within the environment.

Concepts

This section introduces the terminology used in the remainder of this document.

<glossary:name> Name

In this context, a name is an object the purpose of which is referring to another object. Their are different kinds of names with different associated rules regarding which objects are legal name of that kind and the comparison of names. All names of one particular kind form a namespace.

<glossary:namespace> Namespace

A namespace defines a particular kind of name for which it controls

<glossary:name-syntax> Name syntax

Which objects are valid names in the namespace?

For example, legal variable names are typically symbols (excluding constants such as cl:nil, cl:t and cl:pi). Function names, on the other hand, can also be of the form (cl:setf NAME).

<glossary:name-comparison> Name comparison

Given two objects which are valid names, how to decide whether they designate the same name?

For example, name1 and name2 must be eq in order to designate the same variable name. However, name1 and name2 in (let ((name1 (list 'setf foo)) (name2 (list 'setf foo)))) are not eq yet still designate the same function name.

Entry isolation

Not sure

For example, legal variable names are typically symbols (excluding constants such as cl:nil, cl:t and cl:pi) and can be compared using cl:eq. Function names, on the other hand, can also be of the form (cl:setf NAME) and must be compared using cl:equal or a specialized function. In a non-Lisp use-case, names could be non-empty strings and string= or string-equal could be appropriate comparison functions.

<glossary:environment> Environment

At the minimum, a collection of namespaces and associated binding collections. An environment may have other parts such as a reference to a parent environment.

<glossary:binding> Binding

An association of a name in a namespace and a value.

<glossary:scope> Scope

A scopes controls the way in which a value is looked up for a given name, namespace and environment.

As a concrete example, the direct scope constrains the lookup to the specified environment, that is ancestors of the environment are not considered.

Object diagram without hierarchy

Object diagram with hierarchy

Tutorial

Making environments

This library provides different kinds of environments such as global-environment. Clients create instances of theses environment classes using make-instance. In order to hold any bindings, an environment must contain at least one namespace. Namespaces are stored as bindings in a special namespace, but the details of that mechanism are not important at this point. The following code creates a global environment that contains a single namespace, called function, but no “ordinary” bindings:

(defvar *environment* (make-instance 'computation.environment:global-environment))

(setf (computation.environment:lookup 'function 'computation.environment:namespace *environment*)
      (make-instance 'computation.environment::eq-namespace))

(describe *environment*)

#<GLOBAL-ENVIRONMENT 1 namespace {100A817B03}>

:

  EQ-NAMESPACE COMMON-LISP:FUNCTION 0 entries

:

Looking up bindings

As mentioned above, the new environment does not yet contain any bindings in its function namespace, so an attempt to look up a function in that environment must result in an error:

(handler-case
    (computation.environment:lookup 'foo 'function *environment*)
  (error (condition)
    (princ-to-string condition)))

An entry for name FOO does not exist in namespace #<EQ-NAMESPACE {100BDBF7B3}>
in environment #<GLOBAL-ENVIRONMENT 1 namespace {100A817B03}>

Correspondingly, listing all entries contained in the function namespace in the environment results in the empty list:

(computation.environment:entries 'function *environment*)

NIL

Adding bindings

New bindings can be created in two ways

1. Destructively modifying a given environment by adding the new binding to it
2. Creating a new environment object that contains the new binding and is linked to the existing environment object

The first way can be achieved using the (setf computation.environment:lookup) generic function:

(setf (computation.environment:lookup 'foo 'function *environment*) :foo)
(computation.environment:lookup 'foo 'function *environment*)

:FOO

The functions computation.environment:augmented-environment and computation.environment:augmented-namespace implement the second way:

(let ((augmented (computation.environment:augmented-namespace
                  *environment* 'function '(bar) '(:bar)
                  :class 'computation.environment::lexical-environment)))
  (describe augmented)
  (format t "~&----------------")
  (handler-case
      (print (computation.environment:lookup 'bar 'function augmented))
    (error (condition)
      (princ-to-string condition))))

#<LEXICAL-ENVIRONMENT 1 namespace @1 {1011E28F13}>

:

  EQ-NAMESPACE COMMON-LISP:FUNCTION 2 entries
    BAR → :BAR
    FOO → :FOO [inherited from #<GLOBAL-ENVIRONMENT 2 namespaces {10028B3063}>]
----------------
:BAR

but the original environment is not affected:

(describe *environment*)

#<GLOBAL-ENVIRONMENT 2 namespaces {10028B3063}>

:

  EQ-NAMESPACE COMMON-LISP:FUNCTION 1 entry
    FOO → :FOO

Shadowing

(let ((augmented (computation.environment:augmented-namespace
                  *environment* 'function '(foo) '(:bar)
                  :class 'computation.environment::lexical-environment)))
  (describe *environment*)
  (terpri) (terpri)
  (describe augmented))

#<GLOBAL-ENVIRONMENT 2 namespaces {10028B3063}>

  EQ-NAMESPACE COMMON-LISP:FUNCTION 1 entry
    FOO → :FOO

#<LEXICAL-ENVIRONMENT 1 namespace @1 {1005097E73}>

  EQ-NAMESPACE COMMON-LISP:FUNCTION 2 entries
    FOO → :BAR
    FOO → :FOO [inherited from #<GLOBAL-ENVIRONMENT 2 namespaces {10028B3063}>]

Dictionary

The bindings protocol

This low-level protocol is responsible for creating and accessing bindings in a given namespace in one particular environment. Clients should usually use the higher-level environment protocol.

<<generic-function:make-bindings>>

~make-bindings~ src_lisp[:exports code]{namespace environment}

Return a bindings object for namespace in environment.

The returned object must be usable with namespace and environment in the bindings protocol.

<<generic-function:entry-count-in-bindings>>

~entry-count-in-bindings~ src_lisp[:exports code]{bindings namespace environment}

Return the number of entries in bindings in namespace, environment.

<<generic-function:map-entries-in-bindings>>

~map-entries-in-bindings~ src_lisp[:exports code]{function bindings namespace environment}

Call function with each entry in bindings in namespace, environment.

The lambda list of function must be compatible with

(name value)
  

where name is the name of the entry and value is the associated value. Any value returned by function is discarded.

<<generic-function:lookup-in-bindings>>

~lookup-in-bindings~ src_lisp[:exports code]{name bindings namespace environment}

Lookup and return the value for name in bindings in namespace, environment.

Return two values: 1) the found value or nil 2) a Boolean indicating whether a value exists

<<generic-function:setf-lookup-in-bindings>>

~(setf lookup-in-bindings)~ src_lisp[:exports code]{new-value name bindings namespace environment}

Set the value of name in bindings in namespace, environment to new-value.

Return new-value as the primary return value.

The environment protocol

This protocol allows accessing the bindings in all namespaces in a given scope starting at a particular environment. The scope controls, for example, whether bindings inherited from parent environments should be considered.

<<generic-function:entry-count>>

~entry-count~ src_lisp[:exports code]{namespace environment &key scope}

Return the number of entries in namespace in environment for scope.

<<generic-function:map-entries>>

~map-entries~ src_lisp[:exports code]{function namespace environment &key scope}

Call function for each entry in namespace in environment for scope.

The lambda list of function must be compatible with

(name value container)
  

Any value returned by function is discarded.

<<generic-function:entries>>

~entries~ src_lisp[:exports code]{namespace environment &key scope}

Return entries in namespace in environment for scope as an alist.

<<generic-function:lookup>>

~lookup~ src_lisp[:exports code]{name namespace environment &key if-does-not-exist scope}

Lookup and return the value for name in namespace in environment for scope.

Return three values:

1. the found value (subject to if-does-not-exist)
2. a Boolean indicating whether a value exists
3. the environment in which the value was found.

scope controls which bindings are considered. Examples of scopes include binding directly contained in environment and bindings contained in environment or any of its ancestor environments.

if-does-not-exist controls the behavior in case such a value does not exist.

<<generic-function:setf-lookup>>

~(setf lookup)~ src_lisp[:exports code]{new-value name namespace environment &key if-does-not-exist}

Set the value of name in namespace in environment to new-value.

Return new-value as the primary return value.

if-does-not-exist is accepted for parity with lookup.

<<generic-function:make-or-update>>

~make-or-update~ src_lisp[:exports code]{name namespace environment make-cont update-cont &key scope}

Use make-cont or update-cont to set name in namespace in environment for scope.

Return four values:

1. the new value of name in namespace in environment
2. a Boolean indicating whether the value of name in namespace in environment has been updated
3. the previous value of name in namespace in environment
4. the container in which the previous value was found.

If no value exists for name in namespace in environment, make-cont is called to make a value which is then set as the value of name in namespace in environment.

If a value exists for name in namespace in environment, update-cont is called with the existing value and the container of that existing value to potentially compute a new value. If a new value is computed, that value is set as the value of name in namespace in environment.

make-cont has to be a function with a lambda list compatible with

()
  

and has to return the new value as its primary return value.

update-cont has to be a function with a lambda list compatible with

(old-value old-container)
  

and must return between two values and three values when called:

1. a new value based on OLD-VALUE
2. a Boolean indicating whether the first return value is different from OLD-VALUE
3. optionally a container in which the returned new value should be set.

<<generic-function:ensure>>

~ensure~ src_lisp[:exports code]{name namespace environment make-cont &key scope}

Maybe use make-cont to set name in namespace in environment for scope.

Return four values:

1. the new value of name in namespace in environment
2. a Boolean indicating whether the value of name in namespace in environment has been updated
3. the container in which the previous value was found.

If no value exists for name in namespace in environment, make-cont is called to make a value which is then set as the value of name in namespace in environment.

make-cont has to be a function with a lambda list compatible with

()
  

and has to return the new value as its primary return value.

The hierarchical environment protocol

<<generic-function:parent>>

~parent~ src_lisp[:exports code]{environment}

Return the parent of environment or nil.

<<generic-function:root>>

~root~ src_lisp[:exports code]{environment}

Return the ancestor of environment that has no parent.

In particular, if environment does not have a parent, return environment.

<<generic-function:depth>>

~depth~ src_lisp[:exports code]{environment}

Return the number of ancestors environment has.

In particular, return 0 if environment does not have a parent.