HaScheme

A Lazy dialect of Scheme, embedded in 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. HaScheme is implicitly lazy, and only requires strictness annotations, not laziness annotations. Scheme procedures can be easily wrapped to be used in HaScheme, and Scheme can call force on HaScheme promises to obtain values from HaScheme.

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)))))

This procedure in HaScheme 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.

Since HaScheme is lazy, one can write infinite lists with it:

(let ((N (let loop ((i 0))
           (cons (! i) (loop (+ i 1))))))
  (force (list-ref (map square N) 100))) ; => 100000

This code snippet will run in a constant amount of space. (The procedure ! is a strictness annotation to avoid thunk buildup. Since HaScheme is emedded within a call-by-value language, the strictness annotation will always force i at every iteration of the loop, even if neither part of the pair is accessed.)

HaScheme does not support continuations, parameters, exceptions, or multiple value returns.

Author

Peter McGoron

Repository

https://software.mcgoron.com/hascheme/

Requirements

r7rs

API

The HaScheme library namespace is structured in a similar way to R7RS-large's namespace, except it does not export any procedure that is side-effecting.

`(hascheme base)`

Exports everything from (scheme base) as lazy procedures, except

call/cc, dynamic-wind, values, call-with-values
Any procedure ending with !
Anything to do with ports, except for eof-object and eof-object?
make-parameter, parameterize
Anything involving exceptions, except for error, error-object?, error-object-message, error-object-irritants
do
floor/, truncate/, and exact-integer-sqrt are exported, but return lists.

The functions act as one would expect they would act. Forcing (car x) forces x, but forcing (cons x y) does not force x or y.

Syntax that introduces procedures, like lambda, define, and named let make lazy procedures. Lazy procedures return a promise that when forced, force the body of the procedure.

Note that control syntax like if and cond are still syntax. They can be implemented as functions, but then they will have subtly different behavior when it comes to explicitly forcing values.

String, bytevector, and number constructors are always eager. List and vector constructors are lazy.

This library also exports seq.

[procedure] (seq x ... y)

Forces all arguments except its last argument. Returns its last argument unchanged.

`(hascheme case-lambda)`

Exports case-lambda, which creates lazy procedures.

`(hascheme char)`

Exports lazy procedure versions of (scheme char).

`(hascheme complex)`

Exports lazy procedure versions of (scheme complex).

`(hascheme cxr)`

Exports lazy procedure versions of (hascheme cxr).

`(hascheme inexact)`

Exports lazy procedure versions of (hascheme inexact).

`(hascheme control)`

Exports procedure versions of control syntax.

[procedure] (if x y [z])

Force x. If true, return y. If not, return z (or an unspecified value).

[procedure] (cond [x y] ...)

Force x. If true, return y. If not, continue on with the next pairs. If no pairs exist, return an unspecified value.

[procedure] (and x ...)

Force x. If true, force the next value, and so on. If there are no more values, return #t. If not, return #f.

[procedure] (or x ...)

Force x. If true, return x. Otherwise, force the next value, and so on. If there are no more values, return #f.

[procedure] (when pred . subsequents)

Force pred. If true, run (apply seq subsequents). Otherwise return an unspecified value.

[procedure] (unless pred . subsequents)

Force pred. If false, run (apply seq subsequents). Otherwise return an unspecified value.

`(hascheme eager)`

Procedures and syntax forms for eager evaluation.

[procedure] (! x)

Shorthand for (force x).

[syntax] (define-wrappers-from-strict (head source) ...)

Defines lazy-procedure variants of source that force all arguments. Head can either be (name formal ...) or name.

[syntax] (define-wrappers-for-lazy (head source) ...)

Define lazy-procedure variants of source that pass all arguments to a constructor. Head is defined as in define-wrappers-from-strict.

[syntax] (define-binary-wrapper (wrapper source) ...)

Defines wrapper as a non-strict n-ary comparison function. It will force the first two arguments to it, and if the comparison returns false, the procedure returns false and none of the other values are forced. Otherwise it will keep on forcing arguments until there are no more arguments or one of the comparisons fail.

[syntax] (let*! ((formal expr) ...) body ...)

Forces each expr, binds the result to formal, and executes body ....

[syntax] (let*-seq ((formal expr) ...) body ...)

Returns a promise to force each expr, bind it to formal, and then execute body ....

This library also exports seq.

Misc. Information

How is it implemented?

The implementation follows the formula of SRFI-45 with some changes for usability.

All procedure bodies are implicitly wrapped in delay-force.
Scheme procedures that require their values are, in addition, wrapped such that forcing their function forces the necessary arguments. A Scheme procedure that is a constructor does not force its arguments.
Control flow forces the value of the test expression.

Three critical things are needed to make HaScheme ergonomic:

Promises are distinct from other types.
Forcing a value returns the value.
Forcing (delay-force x) is equivalent to a tail call to (force x).

Chicken does all three. There is nothing fancy going on here, just some (relatively) easy-to-understand syntax-rules macros.

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 likein 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))))

Now if one were to define ! as the identity function in regular, call-by-value Scheme, then the block above will evaluate to the same value in both HaScheme and Scheme, in bounded space.

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 control) implements if, and, or, and the 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 (hascheme control) 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.

Issues/Future Directions

Lightly tested.
I want to implement some purely functional data structures.

License

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0.

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

HaScheme

Description

Author

Repository

Requirements

API

(hascheme base)

(hascheme case-lambda)

(hascheme char)

(hascheme complex)

(hascheme cxr)

(hascheme inexact)

(hascheme control)

(hascheme eager)