Scheme Hash

XML and Scheme
Consistent or conformant Scheme implementations of W3C Recommendations: XML Infoset, XPath query language and a small subset of XSL Transformations. An XML document and operations on it can be expressed in Scheme -- and regarded either as data structures or as code.

 

Web and CGI programming 
Tools and working examples of HTML, XML, FORM, HTTP and CGI programming in Scheme:
 
Treaps
A sorted dictionary data structure based on randomized search trees. It can trivially be used to implement priority queues
 
Database Interfaces

Input parsing
A number of useful functions for making sense of a stream of characters, symbols, and tokens. The procedures either skip, or build and return tokens following inclusion or delimiting semantics. The page also describes several pieces of useful sample code.
CGI:url-unquote: a CGI script utility for parsing of a QUERY_STRING
A functional-style framework to parse XML documents


 Binary Parsing
A wide-range optimized bit reader
Handling a TIFF file. A tiff-prober
Reading IEEE binary floats in R5RS Scheme


KANREN: A declarative logic programming system: http://kanren.sourceforge.net
KANREN is a declarative logic programming system with first-class relations, embedded in a pure functional subset of Scheme. The system has a set-theoretical semantics, true unions, fair scheduling, first-class relations, lexically-scoped logical variables, depth-first and iterative deepening strategies. The system achieves high performance and expressivity without cuts.

sokuza-kanren: The minimalist Kanren-like system, to give the taste of logic programming.
Soutei, a logic-based trust-management system, whose first version was implemented in Scheme and based on the compilation of Soutei assertions into Kanren.


Low- and high-level macro programming


An argument against call/cc
 
Delimited Dynamic Binding
The ICFP 2006 paper (joint work with Chung-chieh Shan and Amr Sabry) showing that dynamic binding and delimited control -- as commonly implemented in various Scheme systems -- interact in ill-defined and practically undesirable ways. The paper solves the problem. The accompanying source code includes the solution: implementations of dynamic binding (aka, fluid variables, or parameters) in terms of delimited continuations. Alternatively, we give a (Scheme48-specific) implementation of shift/reset made aware of the dynamic environment.
 
Delimited continuation operators control, shift0, control0 and others
The simplest implementation in terms of shift/reset 
From control0 through control to shift
A generic R5RS implementation of all four Friedman-Felleisen F operators
Multi-prompt delimited control in R5RS Scheme
A specialization of the multi-prompt shift yields a new implementation of the ordinary shift/reset in R5RS Scheme, which is memory efficient even if the underlying call/cc copies the whole stack.
Delimited continuations do dynamic-wind


General ways to traverse collections
The most advanced case: enumerating only a subset of a collection and performing actions that depend on the previously traversed nodes. We also discuss generators in Python, Icon, Scheme, and compare cursors and lazy lists.


Monadic Programming in Scheme
An example of a monadic programming in Scheme that juxtaposes Haskell code for a particular state monad with the corresponding Scheme code.
 
Scheme as its own meta-language
Scheme can be used to formally reason about its own code. Examples: a formal proof of complexity of one particular implementation of priority queues; a formal proof of a relationship between call/cc and Y
MetaScheme, or untyped MetaOCaml
Meta-programming in Scheme with an arbitrary number of stages and cross-stage persistence. Or, why bracket is not a quasiquote.


Purely-functional Object-Oriented System in Scheme
 
Utility functions


A delegation language to request weather products, and a scheme of its interpretation
a domain-specific little language interpreted by a Scheme interpreter


A practical Lambda-Calculator
A normal-order evaluator for the untyped lambda-calculus, extended with convenient commands and shortcuts to make programming in it more productive.
 
Non-linear matching and efficient (cyclic) unification on ordered trees (terms)
 
Lambda abstractions in C++ vs. Scheme
Examples of lambda-expressions, closures, and currying in C++
Scheme in Perl, or Perl as Scheme
 
(Functional) Programming and Computation
This is a separate set of pages about programming, logic, lambda-calculus and computability. Many examples and illustrations are written in Scheme.
Lambda Calculus and Lambda Calculators
   
Implementing Metcast in Scheme
A case study of implementing a large distributed system in Scheme. Metcast is a request-reply and subscription system for distributing, publishing and broadcasting of real-time weather information. Decoders of World Meteorological Organization's data feed, the Metcast server, XML encoders and decoders, auxiliary and monitoring CGI scripts are all written in Scheme.
The paper and the talk presented at the Workshop on Scheme and Functional Programming 2000 (Montreal, 17 September 2000).
 
An applicative-order term rewriting system for code generation, and its termination analysis
generating efficient median filters
 
A read-time application: a value/code constructor
Read-time application is an extensible external representation of Scheme values, especially values that do not have a convenient printed notation -- e.g., ports, records, pi, log2, compiler-option-dependent data. In addition, the #, form can be used for conditional compilation, in spirit of SRFI-0 and feature expressions of Common Lisp.
 
Miscellanea


 

Treaps

  An ordered dictionary data structure, based on randomized search trees (treaps) by Seidel and Aragon. Compared to red-black trees, treap is simpler and more elegant, and can get by without sentinels.
procedure: make-treap KEY-COMPARE-PROC
 

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.

Version
 The current version is 1.2, Sep 2, 1997.
References
 

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
From other archives
 
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
 

Non-linear matching and efficient (cyclic) unification on ordered trees (terms)

 One (in case of matching) or both (for unification) trees may contain variables, whose names begin with an underscore. A variable whose name is a lone underscore is an anonymous, wildcard variable, like the one in Prolog.

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.

procedure: match-tree TREE1 TREE2 ENV -> ENV
  A non-linear match of two ordered trees. TREE1 may contain variables, even several occurrences of the same variable. All these occurrences must match the same term. A variable match is entered into the environment. A variable _ is an exception: its match is never entered into the environment. The function returns the resulting environment or #f if the match fails.
procedure: unify-trees TREE1 TREE2 ENV -> ENV
  A unification of two ordered trees, both of which may contain variables (including several occurrences of the same variable). The unifier is capable of finding cyclic substitutions. Often unify-trees should be followed by normalize-subst below. Splitting the unification into two phases is for efficiency reasons: If we are interested only in the fact if two terms unify, we do not need to apply normalize-subst.
procedure: normalize-subst ENVI ACCEPT-CYCLIC? -> (ENVO | #f)
  ENVI is a set of bindings as returned by unify-trees. ENVO is, informally speaking, a transitive closure of ENVI. If ENVI is acyclic, then ENVO is the fixpoint of composing ENVI with itself. If the flag ACCEPT-CYCLIC? is #f and ENVI turns out to be cyclic, we return #f. If ACCEPT-CYCLIC? is #t, we always return the environment, which may contain recursive and mutually recursive bindings. Setting the flag ACCEPT-CYCLIC? to #f essentially enables the occurs-check. Many Prolog systems omit the occurs-check altogether for performance reasons: see SICTus Prolog Manual, p. 50. The manual states that unifying without the occurs-check is wrong but practical. In our algorithm however, cyclic and acyclic unifications have exactly the same time and space complexities. The occurs-check (passing #f as ACCEPT-CYCLIC?) does not impose any penalty at all.

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.

Version
 The current version is 3.0, Jul 4, 2003.
References
 

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

 

Database Interfaces

 

A truly-Scheme SQL tool

  A Scheme-database interface via scripting of a SQL user front-end. A major procedure:
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.
 

Version
 The current version is 2.7, May 10, 2003.
References
 

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
 

The most primitive and nearly universal database interface

  A Scheme-database interface via scripting of a SQL user front-end. The poorest-man solution is demonstrated with Illustra RDBMS as an example. A richer-man interface scripts an SQL interpreter from within Scheme, in a genuine client-server way. It is shown off using Informix 7.2 On-Line.
Version
 The current version is 1.2, Oct 31, 1997.
References
 

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
From other archives
 
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


 

Purely-functional Object-Oriented System

 

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.
 

Version
 The current version is 1.2, February 29, 2000.
References
 

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.

From other archives
 
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
 

A practical lambda-calculator

 

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
(%add %c1 %c2)
REPL reduces the term and prints the answer: (L f (L x (f (f (f x))))).
     (X equal? (%succ %c0) %c1)
     (X equal?* (%succ %c0) %c1)
The REPL executes the above commands and prints the answer: #f and #t, correspondingly. The second command reduces the terms before comparing them.

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.
 

Platforms
  The package is tested on Gambit-C 3.0, SCM 5d2 and Bigloo 2.2b
Version
 The current version is 1.1, March 30, 2001.
References
 

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.

 

A read-time application: a value/code constructor

 

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
Readable representations for structures (records)
   (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))
Representing uniform vectors (per SRFI-4) in the #, notation
   (define-reader-ctor 'f32 f32vector)
   (with-input-from-string "#,(f32 1.0 2.0 3.0)" read) ==>
       a uniform f32 vector with three elements
External representations for 'complex' datatypes, eg, ports
   (define-reader-ctor 'file open-input-file)
   (with-input-from-string "#,(file \"/tmp/a\")"
     (lambda () (read-char (read)))
will return the first character of the file "/tmp/a".

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)
Emulating #+ and #- of Common Lisp, specifically, examples of feature expressions from Section 24.1.2.1.1 of ANSI Common Lisp standard, X3.226.
 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".
 

Version
 The current version is 1.1, Jul 4, 1999.
References
 

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.
 

From other archives
 
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

 


Last updated July 4, 2013

This site's top page is http://okmij.org/ftp/

oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!