7. Extending Scheme with Python Functions

It is easy to extend Psyche with new Scheme procedures, written in Python. In this Chapter, Psyche will be extended with a new dict object that uses Python dictionaries for fast lookups.

7.1 General Process

Adding new features to Psyche is generally done as follows:

  1. Define the Scheme procedures that will be added
  2. Implement these procedures, using the Psyche types where necessary as described in Chapters 5 and 9.
  3. Create a new Environment, derived from SchemeEnvironment5 as described in Chapter 8. Add the new procedures to this environment.
  4. Instantiate a new Interpreter that uses this environment.

7.2 Example: Adding a Dictionary to Scheme

In Scheme, dictionaries or tables are usually implemented using association lists. While this is a nice and general algorithm, in some cases real hash tables might actually be a better choice.

In this Section we shall implement a dictionary object that works on Numbers, Characters and Symbols7.1.

7.2.1 Defining the Scheme Procedures

The first step is to define the Scheme procedures. Using the Scheme naming scheme, we come to the following set of operations:

(make-dict)
Creates a new dictionary object.

(dict-ref dict key)
key must be a key in dict. key must be a number of a symbol. dict-ref returns the value associated with key.

(dict-set! dict key value)
Associates key with value in dict. If key was already associated with a value, the old association is removed.

(dict-key? dict key)
Returns #t if key is a key in dict. Returns #f if key is not a key.

(dict->list dict)
Returns a newly allocated association list with the same bindings as dict. The order of the associations in the list is unspecified.

These procedures are probably not sufficient, but they give a nice overview of the possibilities.

Example 7..1   Using the dictionary
(define d (make-dict))              ==> unspecified
(dict-key? d 4)                     ==> #f
(dict-ref  d 4)                     ==> error
(dict-set! d 4 (list 'a 'b))        ==> unspecified
(dict-set! d "x" "y")               ==> error

(dict-key? d 4)                     ==> #t
(dict-ref d 4)                      ==> (a b)
(set-car! (dict-ref d 4) 'b)        ==> unspecified

(dict-set! d #\H "hello")           ==> unspecified

(dict->list d)                      ==> ((4 b b)) (#\H . "hello"))

7.2.2 Implementing the Python functions

We can now continue by implementing the Python functions. We start out by creating a new module and importing psyche.schemefct. The functions defined in schemefct will be useful later on. For the sake of an argument, let's assume the new module is called psychedict.

The first functions, the equivalents of make-dict, dict-ref and dict-key? are pretty straightforward.

Example 7..2   make-dict, dict-ref and dict-key?
def makeDict():
    return {}

def dictRef(d, key):
    if not isinstance(d, dict):
        schemefct.error("Not a dictionary", d)
    return d[key]

def isDictKey(d, key):
    if not isinstance(d, dict):
        schemefct.error("Not a dictionary", d)
    return schemefct.schemeBool(d.has_key(key))

Some remarks are in order. First of all, notice how we use the Psyche function error to raise explicit errors; on the other hand, for the dict-ref procedure we rely on Python's behavior of raising a KeyError when a key is not present.

Furthermore, the names of the Python procedures are created from the Scheme names by using the name mangling scheme from Chapter 6.

Finally, notice how we have to convert Python boolean values to Scheme boolean values using the schemeBool function. This is very important, since Scheme booleans have different semantics from Python booleans.

The dict-set! procedure is a bit more interesting. It will use the isNumber, isChar and isSymbol functions from schemefct to check the key.

Example 7..3   dict-set!
def dictSet(d, key, value):
    if not isinstance(d, dict):
        schemefct.error("Not a dictionary", d)
    if not (schemefct.isNumber(key)
            or schemefct.isChar(key)
            or schemefct.isSymbol(key)):
        schemefct.error("Invalid key", key)
    d[key] = value

Notice how this function has no return value; this is the preferred behavior when implementing Scheme procedures with undefined return values.

The last one, dict->list, is the most complicated. In this example, it uses the schemefct.list_ and schemefct.cons methods; it would also have been correct to import the Pair type from psyche.types and use them directly.

Example 7..4   dict->list
def dictToList(d):
    if not isinstance(d, dict):
        schemefct.error("Not a dictionary", d) 

    # assoc is a python list of pairs
    assoc = [schemefct.cons(key, value) for (key, value) in d.items()]

    # schemefct.list_ requires a list of arguments
    return schemefct.list_(*assoc)

7.2.3 Using the New Procedures

For using the new procedures, two steps are left: creating a new environment and creating a new interpreter with this environment.

There are several ways of creating new environments. This Section will show how it is done in Psyche.

First of all, we add one more statement to the psychedict module we have created in the previous chapter:

Example 7..5   Creating the map from Scheme names to Python objects
procedures = {"make-dict": makeDict,
              "dict-key?": isDictKey,
              "dict-set!": dictSet,
              "dict-ref": dictRef,
              "dict->list": dictToList}

With this statement, we map Scheme procedure names to Python function objects.

Now we go to the code where we actually want to instantiate a new interpreter using these functions. We start out by creating a new Scheme environment and we update it with our new procedures.

Example 7..6   Creating the new environment
from psyche import interpreter
import psychedict

# code...

env = interpreter.SchemeEnvironment5()
env.update(psychedict.procedures)

That's it! With these two lines of code we have registered the new dictionary procedures with the Scheme environment.

Instantiating the new interpreter then becomes trivial.

Example 7..7   Creating the new interpreter
# code...
# code creating the new environment env

i = interpreter.Interpreter(env)

i.eval("(define d (make-dict))")
i.eval("(dict-set! d 4 4)")

print i.eval("d")
# this will print {4: 4}



Footnotes

... Symbols7.1
Hash tables use hash functions for storing and accessing their associations; since hash functions for mutable objects are tricky, we only allow immutable objects as keys
Y. Duppen