A.  Appendix: Extending Elk -- An Example

A.1.  The ``ndbm'' Library Extension

      The extensibility mechanisms of Elk can be demonstrated best by examining a simple library extension. Consider the ndbm library that is available on most versions of UNIX. This library implements functions to maintain a simple database file of key/contents pairs.

      As shown in Listing 4, both the keys and the data to be stored are described by the type datum; it consists of the data (a string of bytes) and the length of the data. dbm_open() opens a database file and returns a handle to that file to be used in subsequent operations on that database (a pointer to an opaque data type, similar to the fopen and readdir interfaces); it returns a null pointer if the file could not be opened. A database is closed by a call to dbm_close(). The data stored under a given key is accessed by the function dbm_fetch(); it returns an object of type datum (with a null dptr if the key could not be found). dbm_store is used to insert an entry into a database and to modify an existing entry; it returns zero on success and a non-zero value on error.


#include <ndbm.h>


typedef struct {
    char *dptr;
    int dsize;
} datum;


DBM *dbm_open(char *file, int flags, int mode);

void dbm_close(DBM *db);

datum dbm_fetch(DBM *db, datum key);

int dbm_store(DBM *db, datum key, datum data, int flags);

Listing 4: The UNIX ndbm library

Note: For simplicity, several functions have been omitted. The flags and mode arguments of dbm_open are that of the open system call. The flags argument of dbm_store can be DBM_INSERT to insert a new entry into the database or DBM_REPLACE to change an existing entry.


      The straightforward way to write an ndbm extension to Elk is to provide a new Scheme data type dbm-file together with the obligatory type predicate dbm-file? and the Scheme primitive procedures dbm-open, dbm-close, dbm-fetch and dbm-store that operate on objects of type dbm-file.

      dbm-open receives the filename (a string or a symbol); the second argument is one of the symbols reader (open the file read-only), writer (read and write access), and create (read and write access, create new file if it does not exist). The optional filemode argument is an integer. dbm-open returns an object of type dbm-file or #f (false) if the file could not be opened. dbm-close closes the database file associated with its argument of type dbm-file. As this function is called for its side-effect only, and for lack of a better result, it returns a non-printing object.

      dbm-fetch expects a dbm-file and a string argument (the key to be searched) and returns a string (the data stored under the key) or #f if the key does not exist. Note that in Elk strings may contain arbitrary 8-bit characters, including the null byte. dbm-store is called with a dbm-file, two strings (key and data) and one of the symbols insert and replace. Its integer return value is the return value of dbm_store().

      These procedures and the new dbm-file type can be used by application programmers to manipulate database files in those parts of their applications that are written in Scheme. Listing 5 shows a small example.


(define expand-mail-alias
  (lambda (alias)
    (let ((d (dbm-open "/etc/aliases" 'reader)))
      (if (not d)
          (error 'expand-mail-alias "cannot open database"))
      (unwind-protect
        (dbm-fetch d alias)
        (dbm-close d)))))

(define address-of-staff (expand-mail-alias "staff"))

Listing 5: Using the ndbm extension

Note: The unwind-protect and the error form are not present in standard Scheme.


A.2.  The Anatomy of a Scheme Type

      Listing 6 shows the part of the extension that deals with the new data type dbm-file and the extension initialization function. The variable T_Dbm will hold the unique identifier of the newly defined type. The structure S_Dbm defines the C representation of the type; one such C structure is declared for each composite Scheme type. Its main component is the handle of the database file that is contained in each object of type dbm-file.


#include <scheme.h>
#include <ndbm.h>

int T_Dbm;

struct S_Dbm {
    DBM *dbm;
    char alive;   /* 0 or 1 */
};

#define DBMF(obj) ((struct S_Dbm *)POINTER(obj))

int Dbm_Equal(a, b) Object a, b; {
    return DBMF(a)->alive && DBMF(b)->alive && DBMF(a)->dbm == DBMF(b)->dbm;
}

void Dbm_Print(d, port) Object d, port; {
    Printf(port, "#[dbm-file %lu]", DBMF(d)->dbm);
}

Object P_Is_Dbm(x) Object x; {
    return TYPE(x) == T_Dbm ? True : False;
}

void elk_init_dbm() {
    Define_Primitive(P_Is_Dbm,    "dbm-file?", 1, 1, EVAL);
    Define_Primitive(P_Dbm_Open,  "dbm-open",  2, 3, VARARGS);
    Define_Primitive(P_Dbm_Close, "dbm-close", 1, 1, EVAL);
    Define_Primitive(P_Dbm_Store, "dbm-store", 4, 4, EVAL);
    Define_Primitive(P_Dbm_Fetch, "dbm-fetch", 2, 2, EVAL);

    T_Dbm = Define_Type("dbm-file", sizeof(struct S_Dbm),
        Dbm_Equal, Dbm_Equal, Dbm_Print, NOFUNC);
}

Listing 6: Skeleton of the ndbm extension

Note: For simplicity some details have been omitted in this listing, and the calling interface of some functions has been simplified; the program would not compile in this form. A working gdbm (GNU dbm) extension is included in the Elk distribution.


      Scheme objects can usually live longer than their underlying C objects. In case of the dbm-file type, a Scheme object of that type can obviously still be referenced after its database handle has been closed by a call to dbm-close. As Elk extensions must not crash the application, we must prevent such stale objects from being used in further calls to dbm-fetch, dbm-store, and dbm-close. One way to achieve this is to record in each Scheme object whether the underlying C object is still alive or has been terminated. The boolean component alive in the dbm-file type serves this purpose. It is initialized with true and is set to false in dbm-close. Further operations on objects with alive being false are rejected.

      The interpreter stores all Scheme objects in variables of type Object. An Object is typically a 32-bit value; it is composed of a tag part and a pointer part. The tag part indicates the type of the object, and the remaining bits hold the actual memory address of the object (they point into the interpreter's heap). The macros TYPE and POINTER are provided to extract the fields of an Object. Each type definition must define a macro to extract the object's memory address from an Object (by means of POINTER) and then cast it into a pointer to the underlying C structure (see #define DBMF in Listing 6).

      Dbm_Equal() implements both the eqv? and the equal? predicates for dbm-file objects; it returns true if both objects being compared are alive and contain identical DBM handles.

      Dbm_Print() is called by the interpreter each time an object of type dbm-file is to be printed; it is invoked with the object and the Scheme port to which the output is to be sent.

      P_Is_Dbm() implements the primitive procedure dbm-file? (the type predicate). As with all primitives, it receives arguments of type Object and returns an Object, and it has a name beginning with ``P_''.

      The definition of the initialization function elk_init_dbm() is straightforward; it invokes Define_Primitive() once for each primitive procedure and finally Define_Type() to make the new type known to the interpreter.

      The arguments that can be supplied to Define_Primitive() are a pointer to the function implementing the primitive procedure, the Scheme name of the primitive, the minimum and maximum number of arguments, and a symbol indicating the calling discipline of the primitive. For most of the functions in this example, the calling discipline is EVAL, indicating a normal procedure with a fixed number of arguments, such as car. Elk also supports procedures with variable argument list, such as list (VARARGS); and NOEVAL for special forms (variable number of unevaluated arguments).

      Define_Type() is invoked with the Scheme name of the type, the size of the type's representation in C or C++ (given as a constant or as a function), two functions implementing the eqv? and equal? predicates for objects of this type, a function that is called by the interpreter to print an object of the new type (the type's print function), and a function providing information about the type to the garbage collector. The return value of Define_Type() is a ``handle'' to the newly defined type (a small, unique integer); its main uses are to check the type of arguments supplied to primitive procedures and to instantiate objects of this type.

A.3.  Primitive Procedures -- The Details

      Listing 7 gives the definitions of the primitives dbm-open and dbm-close.


static SYMDESCR Flag_Syms[] = {
    { "reader", O_RDONLY },
    { "writer", O_RDWR },
    { "create", O_RDWR|O_CREAT },
    { 0, 0 }
};

Object P_Dbm_Open(argc, argv) int argc; Object *argv; {
    char *p;
    DBM *dp;
    Object d;

    Make_C_String(argv[0], p);
    dp = dbm_open(p, Symbols_To_Bits(argv[1], 0, Flag_Syms),
                  argc == 3 ? Get_Integer(argv[2]) : 0666);
    if (dp == 0)
        return False;
    d = Alloc_Object(sizeof(struct S_Dbm), T_Dbm, 0);
    DBMF(d)->dbm = dp;
    DBMF(d)->alive = 1;
    return d;
}

void Check_Dbm(d) Object d; {
    Check_Type(d, T_Dbm);
    if (!DBMF(d)->alive)
        Primitive_Error("invalid dbm-file: ~s", d);
}

Object P_Dbm_Close(d) Object d; {
    Check_Dbm(d);
    DBMF(d)->alive = 0;
    dbm_close(DBMF(d)->dbm);
    return Void;
}

Listing 7: ndbm extension -- implementation of dbm-open and dbm-close


      dbm-open, as it has an optional argument, is a function with VARARGS calling discipline (not to be confused with the C language feature of the same name), as indicated by the last argument to the Define_Primitive call. Primitives of this type receive an array of Objects and a count.

      The initial call to the macro Make_C_String checks if the first argument to dbm-open is a string (or a symbol) and converts it to a C string. To obtain the second argument to dbm_open(), the symbol passed to the Scheme primitive (reader, writer, etc.) has to be mapped to a corresponding flags combination (O_RDONLY, O_RDWR, etc.). This is accomplished by the Elk function Symbols_To_Bits(); it is invoked with a Scheme symbol, a flag indicating whether a single symbol or a list of symbols (a mask) is to be converted, and a table of pairs of symbol names and C integers. The third argument to dbm_open is the filemode; Get_Integer() converts a Scheme number to a C integer. dbm-open finally allocates a new Scheme object of type T_Dbm on the heap, initializes the components of the object, and returns it.

      The auxiliary function Check_Dbm() is used by the remaining primitives to check whether a given object is of type dbm-file and if so, whether it is stale. In this case an error is signaled; Primitive_Error() enters the error handler of Elk.

      P_Dbm_Close() just marks the object as stale by setting alive to false and closes the database file.

      Listing 8 shows the implementation of dbm-store and dbm-fetch. Make_Integer() is the counterpart to Get_Integer(); it converts a C integer into a Scheme number. Likewise, Make_String() converts a C string into a Scheme string.


static SYMDESCR Store_Syms[] = {
    { "insert",  DBM_INSERT },
    { "replace", DBM_REPLACE },
    { 0, 0 }
};

Object P_Dbm_Store(d, key, content, flag) Object d, key, content, flag; {
    datum k, c;
    int result;

    Check_Dbm(d);
    Check_Type(key, T_String);
    Check_Type(content, T_String);
    k.dptr = STRING(key)->data;       k.dsize = STRING(key)->size;
    c.dptr = STRING(content)->data;   c.dsize = STRING(content)->size;
    result = dbm_store(DBMF(d)->dbm, k, c,
                       Symbols_To_Bits(flag, 0, Store_Syms));
    return Make_Integer(result);
}

Object P_Dbm_Fetch(d, key) Object d, key; {
    datum k, c;

    Check_Dbm(d);
    Check_Type(key, T_String);
    k.dptr = STRING(key)->data;       k.dsize = STRING(key)->size;
    c = dbm_fetch(DBMF(d)->dbm, k);
    return c.dptr ? Make_String(c.dptr, c.dsize) : False;
}

Listing 8: ndbm extension -- implementation of dbm-store and dbm-fetch



Markup created by unroff 1.0,    September 24, 1996,    net@informatik.uni-bremen.de