You can edit this page using wiki syntax for markup.

Article contents:== HaScheme A Lazy dialect of Scheme, embedded in Scheme [[toc:]] === Description ''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. 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)}}): <enscript language="scheme"> (define (map f list) (if (null? list) '() (cons (f (car list)) (map f (cdr list))))) </enscript> 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: <enscript language="scheme"> (let ((N (let loop ((i 0)) (cons (! i) (loop (+ i 1)))))) (force (list-ref (map square N) 100))) ; => 10000 </enscript> 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.) Why use this? *# To have fun. *# To show Haskellers that you don't need some fancy static type system to have pervasive lazyness. *# To implement lazy code that can be used with strict code. HaScheme does not support continuations, parameters, exceptions, or multiple value returns. HaScheme works by re-implementing promises as procedure objects. A promise can be called with arguments, and that returns a promise that when forced, will force the original promise and pass arguments to it. Hence argument checking is lazy. This also allows for lazy procedures to return other lazy procedures in a composable way. HaScheme 0.3.1 also functions in [[https://gitlab.com/jobol/tr7|TR7 2.0.17]]. === Author Peter McGoron === Repository https://software.mcgoron.com/hascheme/ === Requirements * [[/egg/srfi-259|srfi-259]] === 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}} * {{for-each}}, {{vector-for-each}} * {{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. Bodies are regular bodies: they can have internal {{define}}s. 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. Conditinoals force tests. String, bytevector, and number constructors are always eager. List and vector constructors are lazy. This library also exports {{seq}}. <procedure> (seq x ... y) </procedure> Forces all arguments except its last argument. Returns its last argument unchanged. <syntax>(define-record-type name (cstr name ...) predicate? (name accessor) ...)</syntax> Creates a record type, as if by the regular {{define-record-type}}. This form gives no way to create setters. The constructor is always non-strict in its arguments, and the accessors always force their arguments. <syntax>(do ((id init [update]) ...) (condition body ...) inner-body ...)</syntax> Like the do loop of before, except that the value that {{inner-body ...}} eventually evaluates to is forced for effect. Since {{inner-body ...}} is a body, nothing else is forced for effect. Consider using {{seq}} here. ==== {{(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 {{(scheme cxr)}}. ==== {{(hascheme inexact)}} Exports lazy procedure versions of {{(scheme inexact)}}. ==== {{(hascheme control)}} Exports procedure versions of control syntax. <procedure> (if x y [z])</procedure> Force {{x}}. If true, return {{y}}. If not, return {{z}} (or an unspecified value). <procedure>(cond [x y] ...)</procedure> 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 ...)</procedure> 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 ...)</procedure> 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)</procedure> Force {{pred}}. If true, run {{(apply seq subsequents)}}. Otherwise return an unspecified value. <procedure>(unless pred . subsequents)</procedure> Force {{pred}}. If false, run {{(apply seq subsequents)}}. Otherwise return an unspecified value. ==== {{(hascheme eager)}} Procedures and syntax forms for eager evaluation. This library also exports {{seq}}. <procedure> (! x) </procedure> Shorthand for {{(force x)}}. <syntax>(define-wrappers-from-strict (head source) ...)</syntax> 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) ...)</syntax> 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) ...)</syntax> 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 ...)</syntax> Forces each {{expr}}, binds the result to {{formal}}, and executes {{body ...}}. <syntax>(let*-seq ((formal expr) ...) body ...)</syntax> Returns a promise to force each {{expr}}, bind it to {{formal}}, and then execute {{body ...}}. <procedure>(promise? obj)</procedure> Returns true if the object is a HaScheme promise. HaScheme promises are procedures tagged with special data: they are not system promises. <procedure>(force obj)</procedure> If the object is a HaScheme promise, force the promise and return the value. Otherwise just return the object unchanged. <syntax>(delay expr)</syntax> Returns a HaScheme promise that when forced will evaluate the expression and return its value. <syntax>(delay-force expr)</syntax> Returns a HaScheme promise that when forced will evaluate the expression and then force its result in a tail-recursive way. The {{delay-force}}, {{force}}, and {{delay}} forms satisfy the requirements of the forms of the same name described in the R7RS. They can be used as replacements of system promises if desired. The {{make-promise}} form is redundant, as {{force}} is the identity function on non-promise objects. ==== {{(hascheme lists)}} This library exports all identifiers from [[https://srfi.schemers.org/srfi-1|SRFI-1]], except for * {{circular-list?}} * {{car+cdr}} * {{length+}} * {{for-each}}, {{pair-for-each}}, {{map-in-order}} * {{set-car!}}, {{set-cdr!}} * {{unzip[n]}} (see below) All procedures that normally return multiple values return lists. In addition, this library exports other procedures. <procedure>(length>=? list n)</procedure> <procedure>(length>? list n)</procedure> <procedure>(length<=? list n)</procedure> <procedure>(length<? list n)</procedure> <procedure>(length=? list n)</procedure> Determine the size of the list by looking at only {{n}} elements. This will decide the size of finite or infinite lists in all cases where {{n}} is not infinite. All list lengths are less than or equal to infinity, and all lists are not greater than infinity. <procedure>(unzip lists)</procedure> Returns a list, whose first element is the first element of each {{lists}}, the second element is the second element of each {{lists}}, and so on until the first empty list. <procedure>(list-iterate proc base)</procedure> This procedure is based off of the one in [[https://srfi.schemers.org/srfi-41/srfi-41.html|SRFI-41]]. Create an infinite list where the first element is {{(proc base)}}, and the second element is {{(proc (proc base))}}, etc. This procedure is eager in {{base}}. === Misc. Information ==== How is it implemented? The implementation follows the formula of [[https://srfi.schemers.org/srfi-45/|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. There is a critical difference between the SRFI 45 mechanical conversion and this library: promises are procedures that when applied to return promises. This allows for expressions like <enscript language="scheme"> (let ((f (lambda (n) (lambda (x) (+ n x))))) (map (f 10) '(10 20 30 40))) </enscript> to work without having to annotate {{f}} with {{force}}. The promises are implemented following the implementation in the R7RS. The promises objects are [[/egg/srfi-259|SRFI 259]] objects, so promises can be definitively distinguished from normal procedures without invoking the procedure. ==== 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 [[https://wiki.haskell.org/Foldr_Foldl_Foldl%27|likein Haskell]]). Here is an example: <enscript language="scheme"> (define (list-tail list n) (if (zero? n) list (list-tail (cdr list) (- n 1)))) </enscript> Thunks will build up over time in the list, so it must be forced. <enscript language="scheme"> (define (list-tail list n) (if (zero? n) list (list-tail (force (cdr list)) (- n 1)))) </enscript> 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: <enscript language="scheme"> (define (list-tail list n) (if (zero? n) list (list-tail (! (cdr list)) (- n 1)))) </enscript> 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. <enscript language="scheme"> (define naturals (list-tabulate +inf.0 (lambda (x) x))) (! (list-tail naturals 1000000000)) </enscript> 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. <enscript language="scheme"> (! (list-tail (list-tabulate +inf.0 (lambda (x) x)) 1000000000)) </enscript> 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: <enscript highlight="scheme"> (define (map f l) (cond ((null? l) '()) ((pair? l) (cons (f (car l)) (cdr l))) (else (error "not a list" l)))) </enscript> implemented with {{(hascheme control)}} is <enscript highlight="scheme"> (define (map f l) (cond (null? l) '() (pair? l) (cons f (car l) (cdr l)) #t (error "not a list" l))) </enscript> Neat, right? Well, if we go to {{list-tail}} we have a problem: <enscript highlight="scheme"> (define (list-tail list n) (if (zero? n) list (list-tail (! (cdr list)) (- n 1)))) </enscript> 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 {{n}}th form. <enscript highlight="scheme"> (define (list-tail list n) (if* (zero? n) list (seq (cdr list) (list-tail (cdr list) (- n 1))))) </enscript> ==== 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. ==== Why the Usual Transformation is Not Sufficient Scheme for a long time had `delay` and `force` that were never implemented very well. It was only in the R⁷RS that they were implemented in a safe-for-space way. However, the usual transformation does not handle higher-order procedures correctly. For example, consider the transformation advocated in SRFI 45. The {{map}} function, defined as <enscript language="scheme"> (define (map f lst) (if (null? lst) '() (cons (f (car lst)) (map f (cdr lst))))) </enscript> becomes <enscript language="scheme"> (define (map f lst) (delay-force (if (null? (force lst)) (delay '()) (delay (cons (f (car (force lst))) (map f (cdr (force lst)))))))) </enscript> So far, so good. But let us define <enscript language="scheme"> (define (add-n n) (lambda (x) (+ x n))) </enscript> which then becomes <enscript language="scheme"> (define (add-n n) (delay-force (lambda (x) (delay-force (+ (force x) (force n)))))) </enscript> If we evaluated, in normal Scheme, <enscript language="scheme"> (map (add-n 5) '(1 2 3 4)) </enscript> we would get {{(6 7 8 9)}} back. But if we evaluated this in our lazy language, we would get an error because we tried to apply arguments to a non-procedure. We could get around this by forcing each higher-order procedure: <enscript language="scheme"> (define (map f lst) (delay-force (if (null? (force lst)) (delay '()) (delay (cons ((force f) (car (force lst))) (map f (cdr (force lst)))))))) </enscript> Now this will not work if {{force}} always requires a promise: for instance, if we wanted to pass {{car}} as an argument. But a bigger problem here is that there isn't a way to automatically annotate the operator position of a call with {{force}} in standard Scheme: this would require an equivalent to Racket's {{%app}}. So we would be stuck adding manual {{force}} statements, which is counter to HaScheme's philosophy of making the code as natural as possible. Instead, this library uses [[/egg/srfi-259|SRFI-259]] tagged procedures to wrap promises. The R7RS {{delay}}/{{delay-force}}/{{force}} expressions are re-implemented using the tagged procedures. This actually makes the language ''more'' lazy. Type checks on procedure applications (is the operand actually a procedure?) are deferred until the value of the application is required. Even the check on the number of arguments is deferred. ==== What is this, semantically? (Non-strict in the Operator) (I wrote this after a discussion with who I presume to be a Haskeller.) This is a sketch of what the language in this library means. Imagine an lambda calculus with constant values, like 0, {{'()}}, etc. Application to these values is undefined: denotationally, {{Denote(“(0 0)”) = ⊥}}. This is similar to how {{Denote(“hd []”) = ⊥}} in Haskell. There is no (static) type system in HaScheme, which means that something like {{(0 0)}} in Haskell doesn't even have a denotation while it does in HaScheme. In normal Scheme, with strict semantics, {{Denote(“(car (cons 5 (0 0)))”) = ⊥}}. In a theoretical HaScheme where a constant value is a promise value that is applicable, then {{Denote(“(car (cons 5 (0 0)))”) = 5}}: HaScheme is non-strict in the operator field of an application. This is something that can't happen in a statically-typed language like Haskell. A denotational/operational semantics of this would basically be a call-by-name untyped lambda calculus with non-lambda values. If one attempts to evaluate an application of a non-lambda to a value, the result is undefined. I don't know enough about how to write semantics to make that formal. === Issues/Future Directions * Lightly tested. * I want to implement some purely functional data structures. == Version History ; 0.3.0 : Fix higher-order procedures, CHICKEN 6 support ; 0.2.0 : Added missing {{do}} form, misc. fixes, alot more tests, lists library, change license to 0BSD ; 0.1.0 : Initial Release === License Copyright (C) Peter McGoron 2025--2026 Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted. THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. Some tests were adapted from code written by André van Tonder. Copyright (C) André van Tonder (2003). All Rights Reserved. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. Description of your changes:

I would like to authenticate

Spam control

What do you get when you add 8 to 2?