Little Oddities


 

Lazy evaluation and lazy recursion in flattening of a (cyclic) list

A non-traditional way to flatten a list, by infecting it with a lazy virus. The algorithm runs in truly constant working space. Each atomic element of the original list is accessed exactly once; the elements are not cloned, duplicated or even moved in memory. The flattener is properly tail-recursive and tail-infective. It is also capable of handling cyclic lists, an "infinite" data structure.
Version
The current version is 1.1, Oct 20, 1997.
References

flatten-list.scm [3K]
The source code

Flattening a (cyclic) list by a lazy virus [plain text file]
An article describing the trick, posted on a newsgroup comp.lang.scheme on Mon Oct 20 18:19:12 1997 GMT

Requires
My own standard prelude
 

Monads, Scheme, and IO

Haskell shows best and brightest the glamour of monads for i/o, C function calls and other interactions. However lazy i/o expressed by monads is more a matter of style, and can be closely emulated in other languages. Scheme for example allows both unbridled side-effecting interaction, and a "pure", monadic IO with all worldly effects performed only by a distinguished actor.

A message "lazy string-append and HTML generation" gives another example of monads, in concatenating strings. Rather than applying string-append to a list of strings, we can "assume" the operation and leave the list of strings as it is. If we need to concatenate more strings, we will join the corresponding lists. We can assume the join operation as well, and represent (append l1 l2) with just (list l1 l2). The resulting tree of string chunks denotes the concatenated string: the string-append action is implied but not actually performed. Chances are we may not need any explicit string-append at all: if the resulting string is meant to be written, we will walk the tree instead and display the chunks in-order.

In this formulation, list plays the role of a monad, IO () to be precise. Placing two atoms or trees x and y in a list denotes the action of writing of x before writing of y -- but does not perform the action. Monad axioms are satisfied.

Version
The current version is 1.1, Mar 29, 1998.
References

The USENET article showing off the monadic scheme [plain text file]
An article Monadic scheme of I/O posted on comp.lang.scheme, comp.lang.lisp, comp.lang.functional newsgroups on Sun Mar 29 21:45:07 1998 GMT

My own standard prelude
which defines cout

Philip Wadler, How to Declare an Imperative - ACM Computing Surveys, 1997, v. 29, N3, pp. 240-263.

lazy string-append and HTML generation
A message on a SRFI-13 discussion list posted on Wed, 9 Feb 2000 20:47:58 GMT.

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.

 

Expressing formal proofs in a computer language: Y Scheme

It appears that an algorithmic language can not only implement an algorithm but also formulate propositions about implementation's complexity and other properties, and to express the logic of a rigorous proof of these propositions. Two USENET articles referenced below show that Scheme can be used to formally reason about its own code.

The first article makes a claim about a particular priority queue algorithm, and formally proves it. This sets the context for the next article, which reflects on that formal proof. I found it uncanny that the same language -- Scheme -- was used to:

Another article, posted in September 2003, shows that the Scheme macro-expander makes a good proof assistant.

One can really think in Scheme.

References

A USENET article formally proving complexity of one particular implementation of priority queues. [plain text file]
It was posted as Can one prove complexity of priority queues? on a newsgroup comp.lang.scheme on on Mon, 12 Oct 1998 23:51:39 GMT

A USENET article reflecting on the one above [plain text file]
It was posted as Expressing formal proofs in a computer language: Y Scheme on newsgroups comp.lang.scheme, comp.theory, sci.logic on Sun, 18 Oct 1998 20:58:45 GMT

Self-application as the fixpoint of call/cc
The macro-expander was instrumental in proving the theorem about repeated applications of call/cc. The proof relied on a CPS transform, performed by a syntax-rule macro. Another macro reduced away administrative redexes and made the terms easier to compare.

 

Implementing keyword and default arguments, function's resource database

This article tries to talk about keyword and default arguments of a function in a rather general way:
When a function is called with positional parameters, its argument list is, well, a list. It's a list indeed in Scheme/Perl, and to some extent in C/C++ keeping in mind a stdarg/varargs facility. To permit keyword parameters, the argument list should become an associative list, or a "dictionary" where arguments are to be looked up. This insight helps implement keyword and default arguments in any language.
The article discusses several implementation approaches and shows them off on code snippets in Scheme, C++, Perl and a bit of Haskell. The examples are complete, working, and self-contained.
References

Implementing keyword and default arguments, function's resource database [plain text file]
An article posted on newsgroups comp.lang.dylan, comp.lang.clos, comp.lang.scheme, comp.functional on Tue, 27 Oct 1998 20:55:50 GMT

Macros with keyword (labeled) arguments

Genuine keyword arguments in Haskell

Database_as-a_language.ps.gz [33K]
Database as-a (OO)P language: late binding, delegation, inheritance, and the Fragile Base Class problem
Looking up the value of a keyword argument is the simplest kind of a database query. It is a search through a symbol table, a query of function's environment. The paper argues that all the variety of OO species has sprung from different structures of underlying databases-environments, which hold the data and their labels. Conversely, a way queries to these databases are formulated and executed has everything to do with how powerful and expressive the corresponding OO system is.

A delegation language to request weather products, and a scheme of its interpretation
An example of a production system that is based on multi-level defaults and profiles of various levels of scope and generality.

 

Two misconceptions about closures

This article addresses two misconceptions about closures:

`Closures are synonymous with first-class functions'
In truth, a pure functional language can have first-class abstractions without closures. Closure is just an optimization technique.
`Closures capture their environment at the moment of creation, and thus are unaffected by changes in state that have occurred between their creation and their evaluation'
Environment and state are not synonymous. Generally, a closure does not capture state and so it can be affected by changes in state.
Version
The current version is 1.1, May 29, 2003.
References
The text of the article with the illustrative Scheme code. [plain text file]
The article was posted in a series of two messages Re: Closures without assignment on a newsgroup comp.lang.functional on Wed, 28 May 2003 15:45:19 -0700 and Thu, 29 May 2003 16:39:58 -0700
 

Zipper in Scheme

Zipper is an updateable and yet pure functional cursor into a data structure. It lets us replace an item deep in a data structure, e.g., a tree or a term, without any mutation. The result will share as much of its components with the old structure as possible. The old data structure is still available, which is useful if we wish to 'undo' the operation later on.

Zipper is a delimited continuation reified as a data structure. Somehow that idea is not commonly discussed in the zipper literature. Because Scheme has first-class and delimited continuations, we can derive and use zipper far more easily.

The article below shows the Scheme implementation and the use of Zipper, on a real-life example related to genetic programming.

Version
The current version is 1.2, Oct 25, 2004.
References

Zipper in scheme [plain text file]
The first version of this article was posted on a newsgroup comp.lang.scheme on Sun, 24 Oct 2004 16:19:36 -0700

Joint processing of two immutable SXML documents with update cursors

Continuations and delimited control

zipper data structure
<http://www.nist.gov/dads/HTML/zipper.html>

Ralf Hinze and Johan Jeuring. Weaving a Web
Journal of Functional Programming 11(6), pages 681 - 689, 2001. Technical report ICS Utrecht University, UU-CS-2001-33.
<http://citeseer.ist.psu.edu/hinze01web.html>

Martin Gasbichler and Michael Sperber
Final Shift for Call/cc: Direct Implementation of Shift and Reset. ICFP 2002, pp. 271-282
<http://citeseer.ist.psu.edu/gasbichler02final.html>
This article, among other things, explains the Danvy/Filinski implementation of shift/reset in R5RS Scheme.

 

Multiple values as an effect. Monadic reflection and reification

We describe a hopefully less confusing view of multiple values in Scheme -- as a computational exception. When the function values is invoked with more or fewer than one argument, the function does not return at all. Rather, it throws an exception. The article defines a translation of the R5RS Scheme into a Scheme without multiple values but with SRFI-12 exceptions.

As any effect, multiple-values are not first-class. However, we can convert an effect to its denotation. The latter is a first-class value, can be stored in data structures and passed and returned from functions. We can also turn the denotation of an effect into the effect itself. The first operation -- from an effect to its denotation -- is called a (monadic) reification. Its converse is a (monadic) reflection. The article expounds on the reflection/reification pair for the multiple-value effect in R5RS Scheme.

The second, earlier article, illustrates the reification/reflection for other effects such as run-time exceptions, e.g., taking a car of an empty list. This technique permits a lexically-scoped error handling. We should point out that programming with exceptions is akin to multi-threaded programming. The reification of exceptions lets us suspend their handling and thus introduce 'critical sections'. In other words, reification/reflection makes programming with exceptions ``cooperatively multi-threaded'' rather than ``preemptively muilti- threaded''.

Version
The current version is 1.1, Oct 21, 2003.
References

Multiple values as an effect [plain text file]
The USENET article originally posted on a newsgroup comp.lang.scheme on Tue, 21 Oct 2003 13:11:27 -0700

Reified exceptions [plain text file]
An article showing that other effects such as the division by zero or taking a car of an empty list can be reified and thus treated as first-class values. The article was originally posted as Re: multilambda implementation: recreational macrology challenge! on a newsgroup comp.lang.scheme on Mon, 10 Jun 2002 13:16:23 -0700

 

The taste of logic programming

This code develops a minimal logic programming system: just enough to get the taste of the concept. The over-arching idea is logic programming being the combination of logic variables and `non-deterministic functions' (that is, `functions' that can return more or fewer than one result). We also make an attempt at the multiple-world semantics of logic programs, and the treatment of logic variables as quantum mechanical quantities, with unification being `the measurement'.
This code is an attempt to distill Kanren to the simplest terms.
Version
The current version is 1.1, May 10, 2006.
References

sokuza-kanren.scm [16K]
The R5RS Scheme code. There is actually little code, most of the file are the comments.

Kanren: A declarative applicative logic programming system
A more elaborate logic programming system in Scheme, which underlies The Reasoned Schemer

 

eval-uating open code

The articles below describe difficulties and work-arounds of passing open code to eval. By open code we mean the code that contains free variables not bound in the Scheme report environment. These free variables presumably refer to the bindings in the main program, i.e., the program that invokes eval. The motivation is to compile the main program -- and still be able to eval-uate (i.e., interpret) customization scripts and exchange data between the main compiled code and the interpreted customization scripts via bindings.

The first article shows that R5RS does not actually guarantee that the environment denoted by the (interaction-environment) includes all or any of the bindings from the main program. R5RS leaves it to an implementation to decide which bindings to include in the interaction environment. We give several code snippets that show the dangers of relying on interaction-environment. The behavior may vary depending on the main program being compiled or interpreted.

The second article shows a work-around: A method of sharing of bindings between the compiled and eval-uated code that is guaranteed to work on any R5RS system. The method implicitly closes the code being evaluated, and implicitly maintains the closing environment -- while giving an illusion of evaluating the open code.

References

Re: define-top-level-value [plain text file]
An article posted on a newsgroup comp.lang.scheme on Sun, 10 Aug 2003 15:51:18 -0700

Re: Eval and Define [plain text file]
An article with the code and transcripts, originally posted on a newsgroup comp.lang.scheme on Sun, 30 Dec 2001 15:41:44 -0800

 

Four evaluators of CL/Scheme and their bottom terms

A Common Lisp/Scheme system has not one but four built-in evaluators. In addition to the run-time evaluator, there is a compile-time one (macro-expander), and a read-time evaluator. Furthermore, reading of input and character-dispatch can also be considered term evaluation. Some of these engines implement an applicative-order, call-by-value lambda-calculus, while the others are more powerful normal evaluators. The difference between the two types of evaluators is especially noticeable when they face a term with a bottom subterm. A bottom term (probably better called 'bottomless') is designed to send its evaluator into a never-ending spin. A bottom is just as fatal when it is embedded as an argument in some other term -- to an applicative order evaluator. Normal evaluators can sometimes escape the bottom's grasp.

This article exposes bottom terms for all four evaluators and shows how some of them are able to cope with insane input. A bottom term for a reader-lexer is particularly noteworthy -- it is a character that cannot be read as it literally drives the reader nuts. The laziness of the lexer however can be its saving grace.

References
Lambda-calculi of four built-in CL/Scheme evaluators [plain text file]
An article posted on newsgroups comp.lang.functional, comp.lang.lisp, comp.lang.scheme on Sun, 11 Jul 1999 22:33:16 GMT
 

Lazy Fibonacci stream in Scheme: a value or a macro

Although (potentially infinite) streams are not built-in in Scheme, they are rather easily emulated. The first article below presents a stream-lined Fibonacci sequence re-written from a previously published Haskell code, which was beautiful indeed. The second article demonstrates that Scheme/CL macro-expansion models the non-strict computation of Haskell functions.

Haskell code (by Art Duncan)

     fibs = 1 : 1 : pointwise (+) fibs (tail fibs)

Scheme code

     (define fibs (l-cons 1 (l-cons 1 (pointwise + fibs (e-cdr fibs)))

Scheme macro code

     (defmacro fibs () '(1 1 . (zipWith add (fibs) (tail (fibs)))))
Version
The current version is 1.1, Dec 23, 1998 and Feb 15, 2002.
References

Lazy Fibonacci Scheme [plain text file]
An article with the complete code and transcripts, posted on a newsgroup comp.lang.scheme on Wed Dec 23 15:01:28 1998

Flattening a (cyclic) list by a lazy virusAnother example of lazy streams in Scheme

Haskell functions as CL/Scheme macros [plain text file]
An article posted on newsgroups comp.lang.functional and comp.lang.scheme on Fri, 15 Feb 2002 14:40:19 -0800

Art Duncan's summary Follow Up: Tail Recursive Fibonacci Programs posted on Jan 7, 1999. The summary ends with a fascinating discussion about general rules of programming lazy computations in a strict language.

 

Blending static and dynamic typing: Scheme programming in ML

Robert Harper stated that dynamic typing is a particular case of static typing. This article is to give a simple illustration of that fact. We show several examples of writing ML (OCaml) code in the style of Scheme programs, taking the fullest advantage of latent typing and placing no type annotations. The ML code features:

We limit ourselves to a pure-functional subset of Scheme. References and first-class continuations can be added easily. `Scheme' procedures are expressed in a higher-order syntax. As in real Scheme, the embedded Scheme procedures take the list of arguments.

One may say that the appearance of datatype constructors such as String and Proc and the explicit use of the apply function s_app makes the embedding of Scheme imperfect. We must note however that in the `Scheme' user code, the datatype constructors occur only by the literals. One may abbreviate Str to S, List to L, Int to I and write L[S"string"; I(1); L[]]. We then declare S"..." to be the syntax of string literals, etc. Incidentally, it seems that ocamlbuild took exactly that approach. Because the type tags can be regarded as part of the literal syntax, camlp4 can make the syntax prettier, if so really desired.

We could have chosen a shorter name for s_app or made it an infix operator, which might have improved the appearance. Because the meta-language is still typed, if we by accident omit s_app, we immediately get the type error. Like in Scheme, one may write, however nonsensical, the application of an integer to a string: s_app I(1) L[S"x"]. If that piece of code never gets executed, there is no error. But one may not write I(1) L[S"x"], because that is an invalid object level expression. A bit informally speaking, OCaml typechecker enforces the syntax of the embedded dynamic language...

The code is trivial -- and that is the point. Defining and using the Universal type in a statically typed language is indeed embarrassingly easy. The code has not a single type annotation, and looks as dynamically typed as Scheme code. The source language is still OCaml, with static typing present and available to the programmer. Thus ML offers a blend of dynamic and static type programming; it's a programmer who chooses the proportions of this blend.

References

scheme.ml [7K]
The well-commented OCaml source code
It was originally posted in an article ML as Scheme: Dynamic typing in a strongly-typed language on newsgroups comp.lang.scheme and comp.lang.functional on Wed, 29 Nov 2000 04:32:40 GMT

The follow-up article [plain text file]
with more discussion of blending static and dynamic typing, posted on Thu, 30 Nov 2000 03:50:57 GMT

Nicolas Pouillard: ocamlbuild
An example of the embedding of a Scheme-like polymorphic list in OCaml. Instead of S"..." they write A"..." and instead of L[...], S[...]. The example of an ocamlbuild plug-in is quite illustrative.

 

Currying, Uncurrying, and the fold combinator

The topic of the article is implementing an uncurry combinator:
     (uncurry f a1 a2 ...an) ==> (((f a1) a2) ... an)
and a lambda-curried special form:
     (lambda-curried (a1 a2 ... an) body) ==>
          (lambda (a1) (lambda (a2) .... (lambda (an) body)))
The article was inspired by a problem of representing uncurry as a repetition of an uncurry-1, and proving that the representation works. We then show how uncurry and curry are related to the left- and right-fold combinators.
References
Re: Currying and Uncurrying in Scheme [plain text file]
An article posted on a newsgroup comp.lang.scheme on Sat, 02 Sep 2000 00:55:21 GMT
 

Self-propagating (infecting) Lisp Code

A curious example of implementing circular lists in strict LISP. The curious feature is a function that propagates itself through the list with every call, thus resembling the behavior of biological viruses.
Version
The current version is 1.1, Aug 11, 1994.
References
circular-list-infections.txt [7K]
Description and the eLISP source code
 

IF as a pure function

In most languages, IF has a distinguished status, of a statement or a special syntax form. One wonders whether IF can be a regular function. The answer is yes, provided that a lazy evaluation of branch arguments can somehow be specified explicitly.

The article shows possible solutions in Scheme, and how they literally translate to Python. The discussion thread also notes a striking similarity between the pure IF function in Scheme and conditional expressions in Smalltalk.

Barry Margolin has made the excellent summary of this topic in his follow-up article:

This is a discussion about language design: does IF need to be a special form, or can it be constructed out of other, existing primitives? The answer is that it can, with the only special form required being lambda. Yes, it means that it has to be called a little differently in the theoretical variant of Scheme that doesn't have an IF primitive; this can be hidden using a macro, though.
References
'if' as a _function_, in Scheme and Python [plain text file]
An article posted on a newsgroup comp.lang.scheme on Thu, 19 Aug 1999 22:31:49 GMT
 

Unitary type as a self-referential set

Several programming languages define a distinguished type that contains only one, special value. An example is a unit datatype () in Haskell, with only one non-bottom value, (). Note that the same id labels the type and denotes its only value. It is curious to see how to express a unitary type in Scheme, and how its constructor will look like.

An interesting discussion followed: how does a predicate eqv? apply to procedural values and when two procedures can be called equivalent.

Version
The current version is 1.1, Feb 14, 2000.
References

Unitary type as a self-referential set [plain text file]
An article posted on newsgroups comp.lang.scheme, comp.lang.functional on Mon Feb 14 20:07:43 2000 GMT

Discussion thread about equivalence of procedural values

 

Counting dotted pairs and other leaves in trees of Scheme objects

The problem: given a tree of scheme objects, count all the leaves that are other than '().

The article shows two solutions, for nested (improper) lists and general trees. The first solution counts the number of "improper pairs" that are reachable from a given pair. An "improper pair" is defined as a pair whose cdr is neither a pair nor '().

A more general solution traverses trees built with pairs and vectors. This algorithm effectively counts the number of "singular dots" in a written representation of a Scheme object (sans dots as character constants and dots in character strings).

Version
The current version is 1.1, Apr 25, 1999.
References
Re: Dotted Pairs , and searching for them in trees [plain text file]
An article with the complete code and transcripts, posted on a newsgroup comp.lang.scheme on Sun Apr 25 20:39:55 1999 GMT
 

Scheme Mode for Alpha Editor

Alpha is Emacs' brother in spirit on a Mac. It is written in Tcl rather than in e-lisp.

The Scheme mode tells Alpha about the syntax of Scheme, so that Alpha can properly identify words for selection/highlighting, and syntax-color keywords and comments. The Scheme mode also defines a Tcl procedure to search for and mark up definitions of Scheme functions (for easy navigation in the code).

The new version adds an electric-tab indentation of a line/lines of Scheme code. The Tcl interpreter itself is called upon recursively to figure out when a parenthesis is a parenthesis, and when it is escaped, quoted, or commented out.

Version
The current version is Jul 3, 1996.
References
SchemeMode.tcl [6K]


Last updated November 4, 2007

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

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

Converted from SXML by SXML->HTML