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

This is a library that exports interfaces similar to the R7RS, except
everything is call-by-need and not call-by-value: there is no need to
explictly use `delay` or `delay-force` (in most scenarios). Procedures
can be written in ways that look almost identical to regular Scheme. The
procedures return promises which can be forced by non-lazy code. Hence
lazy and non-lazy code can co-exist.

*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.

## 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][1]). Here is an example:

[1]: https://wiki.haskell.org/Foldr_Foldl_Foldl%27

    (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 easiest thing to do is `delay-force`. I

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