IO(infecting) Lisp Code
call/cccontrol0 through control to shift: A generic R5RS implementation
bottom termseval-uating open codeIF as a pure functionfold combinator#include: an article about C, but with Scheme undertones
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
IOHaskell 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.
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.
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.
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.
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.
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.
This article addresses two misconceptions about closures:
comp.lang.functional on Wed, 28 May 2003 15:45:19 -0700 and Thu, 29 May 2003
16:39:58 -0700Zipper 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.
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.
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''.
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
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 codeThe 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.
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
bottom termsA 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.
comp.lang.functional, comp.lang.lisp, comp.lang.scheme on Sun, 11 Jul 1999 22:33:16 GMTHaskell 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)))))
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.
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:
display*for-eachOne 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.
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.
fold combinatoruncurry 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.comp.lang.scheme on Sat, 02 Sep 2000 00:55:21 GMT(infecting) Lisp CodeIF as a pure functionIn 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: doesIFneed 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 beinglambda. Yes, it means that it has to be called a little differently in the theoretical variant of Scheme that doesn't have anIFprimitive; this can be hidden using a macro, though.
comp.lang.scheme on Thu, 19 Aug 1999 22:31:49 GMTSeveral 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.
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
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).
comp.lang.scheme on Sun Apr 25 20:39:55 1999 GMTEmacs' 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.
This site's top page is http://okmij.org/ftp/
Converted from SXML by SXML->HTML