Scheme Hash

creates a treap object. Here KEY-COMPARE-PROC is a user-supplied function
     KEY-COMPARE-PROC key1 key2
that takes two keys and returns a negative, positive, or zero number depending on how the first key compares to the second.

The treap object responds to a variety of query and update messages, including efficient methods for finding the minimum and maximum keys and their associated values, as well as traversing of a treap in an ascending or descending order of keys.

Looking up an arbitrary or the min/max keys, and deleting the min/max keys require no more key comparisons than the depth of the treap, which is O(log n) where n is the total number of keys in the treap. Arbitrary key deletion and insertions run in O(log n) amortized time.

All the treap object operations are thoroughly documented in the source code.

Martin Gasbichler has kindly ported treaps to Scheme48 and included in the Scheme Untergrund Library.

treap.scm [24K]
The source code. It contains 240 lines of title comments that document the interface and explain algorithmic and technical implementation details.

vtreap.scm [7K]
A validation/verification code. It checks to make sure all treaps methods work and make sense.

Treaps in the Scheme Untergrund Library

A USENET article announcing release of treaps [plain text file]

A USENET article touting treaps as an efficient implementation for priority queues [plain text file]

R. Seidel and C. R. Aragon, Randomized Search Trees, Algorithmica, 16(4/5):464-497, 1996.

Stefan Nilsson, Treaps in Java, Dr.Dobb's Journal, July 1997, p.40-44.

Requires

My own standard prelude

comp.lang.scheme newsgroup

an article "Treaps in Scheme" posted on Mon Sep 22 17:07:47 1997 GMT

comp.lang.scheme newsgroup

an article "Always efficient priority queues" posted on Thu, 08 Oct 1998 19:22:50 GMT

The result of matching or unification is a set of bindings of pattern variables to terms. We call this set 'environment' (env). In the term re-writing literature such a set of bindings is usually called 'substitutions'. Procedures match-tree and unify-trees accept the initial environment as an argument and return the resulting environment -- the substitutions to make both trees identical. The initial environment argument lets the user pass the existing substitutions so the user can match or unify a set of terms incrementally. Often though the initial environment is '(). If the match or unification fail, they return #f.

The source code contains extensive explanations and tests. The test cases specifically include pathological terms. The latter cause the conventional, textbook unification algorithm (recursive descent with the composition of substitutions, due to Robinson (1965)) to exponentially blow-up in time and in space. Our algorithm remains linear in space. Because we store bindings in an associative list and use assq to locate a binding, we cannot generally expect a linear time complexity (although we do achieve it in many, including pathological, cases). Storing bindings in a hash table will decrease the time complexity.

It seems that our algorithm is somewhat similar to Gerard Huet's linear unification algorithm. The latter has quite different intuition: re-writing of equations into a canonical form. In a sense, our unify-trees generates equations and normalize-subst strongly normalizes them, in O(n) iterations.

tree-unif.scm [30K]
The complete and commented source code for the above three procedures and ancillary functions. The code also contains an extensive test suite for matching and unification.

An applicative-order term rewriting system for code generation, and its termination analysis: generating efficient median filters
An application of term matching and unification algorithms.

tree-unif.txt
An article [ANN] Efficient (cyclic) unification posted on a newsgroup comp.lang.scheme on Mon, 7 Jul 2003 13:14:28 -0700

Requires

My own standard prelude

DB1:fold-left PROC INITIAL-SEED QUERY-OBJECT
A QUERY-OBJECT (which in this implementation is a list of fragments that make a SQL statement, in the reverse order -- without the terminating semi-colon) is submitted to the database, using the default database connection.
PROC is a procedure: SEED COL COL ... The procedure PROC takes 1+n arguments where n is the number of columns in the the table returned by the query. The procedure PROC must return two values: CONTINUE? NEW-SEED

The query is executed, and the PROC is applied to each returned row in order. The first invocation of PROC receives INITIAL-SEED as its first argument. Each following invocation of PROC receives as the first argument the NEW-SEED result of the previous invocation of PROC. The CONTINUE? result of PROC is an early termination flag. If that flag is returned as #f, any further applications of PROC are skipped and DB1:fold-left finishes. The function DB1:fold-left returns NEW-SEED produced by the last invocation of PROC. If the query yielded no rows, DB1:fold-left returns the INITIAL-SEED.

Thus DB1:fold-left is identical to the left fold over a sequence, modulo the early termination.

The interface defines an S-expression-based ``variant'' of SQL to construct a QUERY-OBJECT. All of SQL92 is supported.

There are a few minor variants of the above procedure, optimized for common particular cases: DB1:for-singleton, DB1:assoc-val, DB:imperative-stmt. The code can support pooling of database connections. The source code completely explains the interfaces.
 

db-util1.scm [23K]
The implementation of the enumerator and of the ``interpreter'' for the S-expression version of SQL, which translates from S-expressions to strings of SQL code. The latter part is database-independent.

db-util.scm [12K]
The source code: lower-level interfaces. The title comments document the interfaces and explain technical implementation details.

vdb-util.scm [7K]
Validation tests for the higher-level wrappers: generating SQL from the S-expression-based domain-specific language. These tests do not require any DB connection.

vdbaccess.scm [4K]
A low-level validation/verification code. It checks to make sure all DB: methods work and make sense.

Platform-independent higher-order distributed SQL database interface: The most primitive and nearly universal database interface
The first announcement of this tool and an explanation of how to script SQL across the network

Towards the best collection traversal interface
The theoretical and practical justifications for the DB1:fold-left interface.

Requires

My own standard prelude

Input parsing primitives

exec_with_piped, a scripting tool

prim-db-intf.scm [3K]

A USENET article explaining the technique [plain text file]

Another USENET article that explains how to make scripting work across the network [plain text file]

Requires

My own standard prelude

Input parsing primitives

exec_with_piped, a scripting tool

comp.lang.scheme newsgroup

an article The most primitive and nearly universal database interface posted on Fri Oct 31 18:56:18 1997 GMT

comp.lang.scheme, comp.lang.lisp, comp.databases newsgroups

an article Platform-independent higher-order distributed SQL database interface posted on Sun, 15 Nov 1998 22:05:14 GMT

The present code implements a classless, delegation-based OO system, similar to those of Self or Javascript. This is a full-fledged OO system with encapsulation, object identity, inheritance and polymorphism. It is also a purely functional system: there is not a single assignment or other mutation in the code below.

Objects' identity is decided by an eq? predicate applied to the result of an identity message. A set-x method returns an object with a new state, but with the same identity as the source object. An object in a changed state is in a sense a "child" of the original object. No wonder implementations of "mutation" and inheritance are so similar in this OO system.
 

pure-oo-system.scm [6K]
The source code, with comments and illustrative tests.

A USENET article [plain text file]
that discusses implementation of objects as functions (closures) in a non-pure and pure functional languages.

comp.lang.smalltalk, comp.lang.functional, comp.lang.scheme newsgroups

an article "Re: FP, OO and relations. Does anyone trump the others? " posted on Wed, 29 Dec 1999 05:13:58 GMT

This calculator implements a normal-order evaluator for the untyped lambda-calculus with shortcuts. Shortcuts are distinguished constants that represent terms. An association between a shortcut symbol and a term must be declared before any term that contains the shortcut could be evaluated. The declaration of a shortcut does not cause the corresponding term to be evaluated. Therefore shortcut's term may contain other shortcuts -- or even yet to be defined ones. Shortcuts make programming in lambda-calculus remarkably more convenient.

Besides terms to reduce, this lambda-calculator accepts a set of commands, which add even more convenience. Commands define new shortcuts, activate tracing of all reductions, compare terms modulo alpha-conversion, print all defined shortcuts and evaluation flags, etc. Terms to evaluate and commands are entered at a read-eval-print-loop (REPL) "prompt" -- or "included" from a file by a special command.

Examples

First we define a few shortcuts:

     (X Define %c0 (L f (L x x)))                     ; Church numeral 0
     (X Define %succ (L c (L f (L x (f (c f x))))))   ; Successor
     (X Define* %c1 (%succ %c0))
     (X Define* %c2 (%succ %c1))
     (X Define %add (L c (L d (L f (L x (c f (d f x))))))) ; Add two numerals
     (X Define %mul (L c (L d (L f (c (d f))))))	   ; Multiplication

     (X equal? (%succ %c0) %c1)
     (X equal?* (%succ %c0) %c1)

This all looks suspiciously like Scheme. However, try the following two terms: (%mul %c1 e) and (%mul %c0 e). The evaluator reduces the first term to e and the second one to (L f (L x x)), which is %c0. It must be stressed that in both terms e is a free variable. We can therefore take the evaluation result as a proof that a left-multiplication by 1 leaves a term e intact, while left-multiplication by zero yields zero -- for all terms! This is an algebraic result, a clear illustration of usefulness of lambda-calculus in logic and theorem-proof systems. On the other hand, try to evaluate (* 1 e) in Scheme with e being an unbound variable!

The title comments to the source code of the calculator explain the differences between a call-by-value evaluator such as Scheme, an applicative-order lambda-calculator, a normal-order evaluator such as Scheme's macro-expander, and the present normal-order lambda-calculator.
 

lambda-calc.scm [28K]
A well-commented source code.

lambda-arithm-basic.scm [3K]
Definitions for the most frequently used shortcuts such as %true, %false, %Y, %c0, %c1 and a few other Church numerals, addition, multiplication, exponentiation and zero checking abstractions. This file also contains tests that illustrate the capabilities of the calculator.

Lambda Calculus and Lambda Calculators
Descriptions of other calculators and examples of applying the calculators to problems in lambda calculus.

Read-time application is an extensible external representation of Scheme values. It is similar to Smalltalk's object serialization and #. and #S() reader-macros of Common Lisp. A proposed #, form can construct arbitrary values at read-time, including S-expressions representing code to be compiled/interpreted. The #, form can be used to denote values that do not have a convenient printed representation -- e.g., ports and records. A read-time application can also represent standard Scheme values whose canonical notation is cumbersome (e.g., pi, log2), dependent on compiler options, or otherwise unsuitable. In addition, the #, form can be used for conditional compilation, in spirit of SRFI-0 and feature expressions of Common Lisp: #+ and #- reader macros.

Examples:

Alternative printed representations for standard Scheme datatypes and other values

   (define-reader-ctor '+ +)
   (with-input-from-string "#,(+ 1 2)" read) ==> 3

   (define-reader-ctor 'my-vector
     (lambda x (apply vector (cons 'my-vector-tag x))))
   (with-input-from-string 
     "#,(my-vector #,(my-vector #,(+ 9 -4)))" read) ==>
       '#(my-vector-tag #(my-vector-tag 5))

   (define-reader-ctor 'f32 f32vector)
   (with-input-from-string "#,(f32 1.0 2.0 3.0)" read) ==>
       a uniform f32 vector with three elements

   (define-reader-ctor 'file open-input-file)
   (with-input-from-string "#,(file \"/tmp/a\")"
     (lambda () (read-char (read)))

cond-expand construct of SRFI-0 as a read-time application:

 printing cond-expanded code from SRFI-0, example 1...
   #,(cond-expand
       ((and srfi-1 srfi-10) (write 1))
        ((or srfi-1 srfi-10) (write 2))
        (else))

   when features (srfi-1) are defined: (begin (write 2))
   when features (srfi-10) are defined: (begin (write 2))
   when features (srfi-1 srfi-10) are defined: (begin (write 1))
   when features (srfi-2) are defined: (begin)

 interpreting a string: 
   (cons #,(cond-expand (lispm "Spice") (spice "foo")
     ((not (or lispm spice)) 7)) 'x)

   when features (spice perq) are defined: ("foo" . x)
   when features (lispm) are defined: ("Spice" . x)
   when features (srfi-10) are defined: (7 . x)

The read-time application proposal has been submitted as a SRFI "#, external form: applying a value/code constructor at read time".
 

read-apply.scm [10K]
The commented source code of a reference implementation.

vread-apply.scm [4K]
Validation code; the title comments explain how to run it. This code also checks that syntax and semantic errors in #, forms are correctly detected and reported.

A USENET article [plain text file]
that discusses reader-constructors, read-time applications, and their implementation.

cond-expand.scm [3K]
Implementation of the cond-expand construction of SRFI-0 as a read-time application.

vcond-expand.scm [3K]
The validation code; it makes it a point to use examples of Feature Expressions from Section 24.1.2.1.1 of ANSI Common Lisp standard, X3.226.

A USENET article [plain text file]
that relates #+/#-, SRFI-0, SRFI-7, and conditional Scheme compilation to read-time applications.
 

comp.lang.scheme newsgroup

an article Announce: Read-time _apply_ and its usual and unusual applications posted on Mon Jul 05 17:28:37 1999 GMT

comp.lang.scheme newsgroup

an article SRFI-0 and #+/#- "clones" as read-time applications posted on Fri Jul 16 20:15:50 1999 GMT

SRFI-0, "Feature-based conditional expansion construct"

24.1.2.1 Feature Expressions, ANSI Common Lisp standard, X3.226