HaScheme -- Call By Name Scheme

Scheme demonstrates that a very small number of rules for forming expressions, with no restrictions on how they are composed, suffice to form a practical and efficient programming language that is flexible enough to support most of the major programming paradigms in use today.

-- Revisedⁿ Reports on the Algorithmic Language Scheme (n ≥ 3, 1986–)

HaScheme is a library that implements a subset of the R7RS's libraries in a lazy way, using force and delay-force. When HaScheme is used by itself, it is a lazy functional programming language with the same syntax as Scheme, embedded within Scheme.

For instance, the following map implementation is both valid HaScheme (importing (hascheme base)) and Scheme (importing (scheme base)):

(define (map f list)
  (if (null? list)
      '()
      (cons (f (car list)) (map f (cdr list)))))

Since HaScheme is lazy, this function will return a promise. The function's body is only executed if, when attempting to force a promise containing the map, the contents of the map are needed for a computation.

Procedures in HaScheme can be written in ways that look identical to regular Scheme. They do not need to be explicitly delayed or delay-forceed, and they only need to force to reduce space usage. HaScheme procedures return promises which can be forced by regular code. HaScheme's datatypes are the same as regular Schemes. Hence lazy and non-lazy code can co-exist. It is easy to wrap eager Scheme procedures to be usable in HaScheme.

HaScheme should run in any R7RS-compatible system that distinguishes promises from all other types, and that allows forcing non-promises. There is no need to support implicit forcing.

HaScheme uses delay-force, which is not available in R6RS. HaScheme could be implemented on top of SRFI-45 if the representation of promises was changed to a define-record-type datatype instead of cons cells.

See also Lazy Racket.

Every procedure in HaScheme is lazy. Values are forced in conditionals, or explicitly using seq. This allows for the call-by-value semantics of Scheme to be turned into call-by-need semantics without any syntactic cruft.

Why use this?

1. To have fun playing around with functional infinite data structures.
2. To embed lazy and pure algorithms into impure Scheme with ease.
3. To show those dirty Haskellers that you don't need no stinkin' static type system.

Restrictions and Implementation Notes

1. No call/cc. Explanation
2. No call-with-values or multiple-valued returns. Explanation
3. No exceptions (but error exists).
4. Strings and bytevectors are eager objects. For example, forcing a string will also force any characters and strings used to build the string.
5. Pairs and vectors are lazy objects. Forcing a pair will not force its components.
6. No mutation and no I/O (i.e. no ports).
7. Parameters are not supported because forcing a promise uses the parameters of the dynamic extent of the force, and not the dynamic extent of the delay. This makes them useless in this context. This would be fixed by SRFI-226.
8. No quasiquote.

Fun (or Pain) with Laziness

You need to be careful with lazy functions because they can cause space leaks. This is a problem in general with lazy languages (like in Haskell). Here is an example:

(define (list-tail list n)
  (if (zero? n)
      list
      (list-tail (cdr list) (- n 1))))

Thunks will build up over time in the list, so it must be forced.

(define (list-tail list n)
  (if (zero? n)
      list
      (list-tail (force (cdr list)) (- n 1))))

Note that n is never explicitly forced: it is implicitly forced by the control flow.

The first code block has the attractive property that it operates the same way on finite lists in both Scheme and HaScheme, while the second one could differ in exotic cases (like promises that return promises). Instead of writing force, the operator ! is used:

(define (list-tail list n)
  (if (zero? n)
      list
      (list-tail (! (cdr list)) (- n 1))))

where (! x) is defined to just be x in Scheme. Now the code block above operates the same in Scheme and HaScheme.

Ok, now we have fixed our space leak issues. Right? Let's try another infinite list trick: a list of all natural numbers.

(define naturals (list-tabulate +inf.0 (lambda (x) x)))
(! (list-tail naturals 1000000000))

This also leaks! This is because the promises are making new cons cells, and storing them in naturals. We need to organize things to make sure the program can clean up.

(! (list-tail (list-tabulate +inf.0 (lambda (x) x)) 1000000000))

This will run in bounded space.

Call-by-Need and Conditionals

Since call-by-need will only execute a function when needed, conditional forms like if can be implemented as functions and not syntax. In fact, HaScheme implements if, and, or, and the cond-like cond* as functions, meaning one can pass them around as values.

For instance:

(define (map f l)
  (cond
    ((null? l) '())
    ((pair? l) (cons (f (car l)) (cdr l)))
    (else (error "not a list" l))))

implemented with cond* is

(define (map f l)
  (cond*
   (null? l) '()
   (pair? l) (cons f (car l) (cdr l))
   #t (error "not a list" l)))

Neat, right? Well, if we go to list-tail we have a problem:

(define (list-tail list n)
  (if (zero? n)
      list
      (list-tail (! (cdr list)) (- n 1))))

Since if is now a function, Scheme (our call-by-value host language) will attempt to reduce (! (cdr list)) every time, even when we don't need to. We could go back to syntactic if, or we could add some wrapper to the procedure. The seq function (named after the function in Haskell) takes n forms, forces the first n-1, and returns the nth form.

(define (list-tail list n)
  (if* (zero? n)
       list
       (seq (cdr list)
            (list-tail (cdr list) (- n 1)))))

Multiple Values and Continuations

HaScheme doesn't have call/cc. call/cc is not a function because it does not return, so that's strike one for inclusion in a pure language. Reified continuations make sense in a call-by-value language, because there is a definite evaluation order (outermost first), but a lazy language can execute any code at basically any time.

A future implementation might be able to use SRFI-226's delimited control structures to implement continuations, because they are actual functions.

Multiple values are specified as returning values to their continuation. Since HaScheme does not (conceptually) have continuations, multiple values have to be interpreted differently. But a bigger issue occurs because a promise is a single value. It cannot be decomposed into more values without forcing the promise.

License

0BSD for everything except for (hascheme implemetation-support), which implements a modified version of the SRFI-45 sample implementation for systems that do not implement the requirements for promises here.