Owl Lisp 0.2

Owl Lisp is a simple programming language. The main motivation for writing it was to get a portable system for writing standalone programs in a subjectively pleasant dialect of LISP, which in this case means a minimal core language and runtime, purely functional operation and support for asynchronous evaluation.

It should be easy to get owl up and running on most somewhat POSIX-compliant systems, such as Linux, any BSD. Owl is mainly developed on OpenBSD and Linux. You should have make and a working C-compiler installed. For example in Debian-based Linux distributions you can use:

$ sudo apt-get install gcc

You may also need git and make if you download the sources from git or want to build the full source package.

Building

The easiest option is to download the current precompiled C-version of ol, and compile with with a C-compiler. Ol is the standalone repl and compiler, which also has the builtin libraries described in this manual.

$ curl https://haltp.org/files/ol-0.2.c.gz \
   | gzip -d \
   | gcc -x c -O2 -o ol -
$ ./ol
You see a prompt.
> (cons 1 (list 2))
'(1 2)
> ,quit
bye bye _o/~

This version of ol is compiled with no C-code optimizations, so the resulting C-code is small and takes very little time and resources to compile. Alternatively you can download all of the sources and make a traditional install.

$ git clone https://gitlab.com/owl-lisp/owl.git
$ cd owl-lisp
$ make

If you just built ol, you can use it from wherever convenient. Usually it is convenient to put such binaries to your home directory under bin/ -directory.

You can install owl and the manual pages with sudo make install after building the sources or a release tarball.

Testing Operation

When started, owl greets the user is ready to proceed evaluating terms given to it. This is the REPL, or read-eval-print -loop familiar from many modern programming languages.

$ ol
You see a prompt.
> (+ 1 2)
3
> (reverse (list 1 2 3))
'(3 2 1)
>

You can exit owl by pressing Ctrl-d, denoting end of input in UNIX, asking the REPL to exit via ,quit, or by asking the thread scheduler to stop everything with (halt 1).

Compiler mode can be tested for example by doing

$ echo '(lambda (args) (print "hello world") 0)' \
   | ol  -x c -o - \
   | gcc -x c -o test -
$ ./test
hello world

It is possible to write fairly large programs using just definitions, but they tend to become rather messy and hard to maintain. Programming languages usually allow encapsulating related definitions into a library or a module, which has a well defined interface or interfaces. In Owl these are called libraries. R7RS Scheme happened to defined modules almost exactly equally to Owl libraries, so the naming was converted to match that of R7RS.

A library consists of a listing of other libraries it depends on, a listing of values it intends to expose, and the actual definitions of the values. A simple library can be defined and imported for use as follows:

> (define-library (my test)
     (import
        (owl base)) ;; required
     (export
        barrow
        barrow?)
     (begin
        (define barrow (cdr '(wheel barrow)))
        (define barrow?
           (lambda (x)
              (eq? x barrow)))))
;; Library (my test) added
> (import (my test))
;; Imported (my test)
> barrow
'(barrow)
> (barrow? barrow)
#true

Owl contains a number of builtin libraries. Some of them are general purpose ones and others were mainly needed to implement the repl and compiler. A listing of readily available libraries can be shown with the ,libraries REPL command. They are also available in the *libraries* variable, which is an association list of library names and the values of the library. There is nothing magical about libraries - they are just values like everything else.

Libraries can be defined anywhere at toplevel whether using the REPL or loading files. There is however a naming and loading convention, which makes it easier to load libraries. If a library (foo bar baz) is to be imported and one is not already loaded, then Owl will automatically attempt to load it from foo/bar/baz.scm.

If you know the name of the value you would like to import, but don't know the library, then you can search for if using ,find.

> ,find stat
,find stat
current toplevel: *state*, type-thread-state
   (owl base): type-thread-state
   (owl sys): stat
   (owl core): type-thread-state
> (import (owl sys))
;; Imported (owl sys)
> (assoc 'size (stat "Makefile" #t))
'(size . 3869)

Lazy lists (or streams) are like lists, but they are computed only as far as needed. You can for example define a lazy list of all integers below a million, and then proceed to run computations on them, without worrying whether you have enough memory to hold a million numbers. Lazy lists are for example useful in computations, where you know how something is constructed, but don't yet know how many of them will be needed, or know that you only need them one at a time and don't want to waste memory.

A lazy list is either #null, a pair of a value and rest of the lazy list, or a function of zero arguments (a thunk) which when called will return the rest of the lazy list. Therefore, since normal lists are a subset of lazy lists, all lazy list functions can also take normal lists as arguments.

Scheme warning: recall that Owl does not have mutable data structures, so lazy lists do not cache their results.

(pair head exp) → ll, lazy equivalent of (cons head exp), but exp is not evaluated yet (force-ll ll) → list, turn a lazy list into a regular one

Exported values:

• lfold
• lfoldr
• lmap
• lappend
• lfor
• liota
• liter
• lnums
• lzip
• ltake
• lsplit
• llast
• llen
• lcar
• lcdr
• lkeep
• lremove
• ldrop
• llref
• ledit
• pair
• tail
• uncons
• force-ll
• subsets
• permutations
• lunfold
• delay
• force
• avg
• lnull?
• lpair?

Examples:

• (lsplit '(1 2 3 4) 2) = (values '(1 2) '(3 4))

Exported values:

• qnull
• qnull?
• qlen
• qcons
• qsnoc
• quncons
• qunsnoc
• qcar
• qrac
• list->queue
• queue->list

Exported values:

• string?
• string-length
• runes->string
• bytes->string
• string->bytes
• string->runes
• list->string
• string->list
• string-append
• string-concatenate
• c-string
• null-terminate
• finish-string
• render-string
• render-quoted-string
• str-iter
• str-iterr
• str-fold
• str-foldr
• str-iter-bytes
• str-replace
• string-map
• str-rev
• string
• string-copy
• substring
• string-ref
• string=?
• string<?
• string>?
• string<=?
• string>=?
• string-ci=?
• string-ci<?
• string-ci>?
• string-ci<=?
• string-ci>=?
• unicode-fold-char
• make-string

Operations in this library depend only on primitive operations. The rest of the usual operations typically depend on numbers, which are implemented in (owl math).

Exported values:

• pair?
• null
• null?
• caar
• cadr
• cdar
• cddr
• car*
• cdr*
• list?
• zip
• foldl
• foldr
• fold
• map
• for-each
• mem
• memq
• assq
• getq
• last
• fold-map
• foldr-map
• append
• concatenate
• reverse
• filter
• remove
• separate
• keep
• every
• any
• unfold
• first
• find
• find-tail
• take-while
• break
• split
• fold2
• halve
• interleave
• diff
• union
• intersect
• ╯°□°╯

Examples:

• (zip cons '(1 2 3) '(a b c d)) = '((1 . a) (2 . b) (3 . c))
• (foldr cons () '(a b c)) = '(a b c)
• (map not '(#false #false #true)) = '(#true #true #false)
• (mem eq? '(1 2 3) 2) = '(2 3)
• (assq 'a '((a . 1) (b . 2))) = '(a . 1)
• (assq 'c '((a . 1) (b . 2))) = #false
• (last '(1 2 3) 'a) = 3
• (last '() 'a) = 'a
• (append '(1 2 3) '(a b c)) = '(1 2 3 a b c)
• (reverse '(1 2 3)) = '(3 2 1)
• (find null? '(1 2 3)) = #false
• (find null? '(1 ())) = ()
• (split (lambda (x) (eq? x 'x)) '(a b x c d x e)) = '((a b) (c d) (e))
• let l = '(1 2 () 3 () 4)
• (filter null? l) = '(() ())
• (remove null? l) = '(1 2 3 4)
• let l = '(#true (1 2) #false (3))
• (separate l pair?) = (values '((1 2) (3)) '(#true #false))
• (interleave 'x '(a b c)) = '(a x b x c)
• (interleave 'x '()) = ()
• (halve '(a b c d)) = (values '(a b) '(c d))
• (halve '(a b c d e)) = (values '(a b c) '(d e))

Vectors are one-dimensional data structures indexable by natural numbers, having O(n log_256 n) access and memory use (effectively O(1)). They are mainly intended to be used for static data requiring relatively efficient iteration and random access.

Vectors are implemented as complete 256-ary trees. Small vectors fitting to one node of the tree are of raw or allocated type 11, meaning they usually take 8+4n or 4+n bytes of memory, depending on whether the values are fixnums in the range 0-255 or other values.

Large vectors are trees. Each node in the tree handles one byte of an index, and nodes starting from root each dispatch the highest byte of an index. When only one byte is left, one reads the reached leaf node, or the leaf node stored to the dispatch node.

Reading the vector in order corresponds to breadth-first walk of the tree. No nonzero number has 0 as the highest byte, so the first dispatch position of the root is always free. This position contains the size of the vector, so that it is accessable in O(1) without space overhead or special case handling. Leaf nodes have the size as part of the normal object header.

Order example using binary trees:

          (0 1)                 bits 0 and 1, only 1 can have children
             |                  dispatch the top bit
           (2 3)                bits from top, 10 11, numbers ending here 2 and 3
           /   \                dispatch top and second bit
          /     \
      (4 5)     (6 7)           bits from top, (100 101) (110 111)
      /  |       |  \
     /   |       |   \
(9 8) (10 11) (12 13) (14 15)   etc

Vectors use the same order, but with up to 256 links per node.

Exported values:

• vector
• vector?
• vector-length
• vector-ref
• list->vector
• vector->list
• vec-iter
• vec-iterr
• vec-fold
• vec-foldr
• vec-range
• vec-iter-range
• vector-map
• merge-chunks
• make-vector
• leaf-data
• vec-leaf-of
• vec-leaves
• vec-cat
• vec-rev
• *vec-leaf-size*

Examples:

• (vector-ref (make-vector 100 42) 99) = 42
• (vector-map (lambda (x) (+ x 10)) (vector 1 2 3)) = (vector 11 12 13)
• (vec-fold - 0 (vector 1 2 3 4)) = (fold - 0 (list 1 2 3 4))
• (vec-foldr - 0 (vector 1 2 3 4)) = (foldr - 0 (list 1 2 3 4))

These common list processing operations require numbers, so they are defined in a library loaded after math code.

Exported values:

• lset
• ldel
• lget
• length
• led
• ledn
• lins
• lref
• take
• drop
• iota
• list-ref
• list-tail
• make-list
• split-at
• has?
• hasq?

Examples:

• (lref '(a b c) 1) = 'b
• (lset '(a b c) 1 'x) = '(a x c)
• (ldel '(a b c) 1) = '(a c)
• (led '(1 2 3) 1 (C * 10)) = '(1 20 3)
• (ledn '(1 2 3) 1 (H cons 'x)) = '(1 x 2 3)
• (lins '(a b c) 1 'x) = '(a x b c)
• (length '(a b c)) = 3
• (take '(a b c) 2) = '(a b)
• (take '(a) 100) = '(a)
• (drop '(a b c) 2) = '(c)
• (drop '(a) 100) = '()
• (iota 0 1 5) = '(0 1 2 3 4)
• (iota 10 -2 0) = '(10 8 6 4 2)
• (list-tail '(a b c) 1) = '(b c)
• (make-list 3 'x) = '(x x x)
• (split-at '(a b c d) 2) = (values '(a b) '(c d))

Byte vectors are vectors holding only numbers in the range 0-255. They are internally represented as chunks of memory in the garbage collected heap. Typical use cases for them is packing data for an operating system call, or receiving data from an external source.

Vectors and byte vectors differ from Scheme in that they are not disjoint types. Regular vectors can be, or can contain, byte vectors if the content happens to fit in the range representable by bytes. This makes it possible to use a more compact representation of data where possible. Representation changes to regular vectors where necessary, much like numbers are converted from fixnums to bignums where the values would no longer be representable by fixnums.

Exported values:

• bytevector
• bytevector?
• bytevector-length
• bytevector-u8-ref
• bytevector-append
• bytevector-concatenate
• bytevector-concatenate->list
• bytevector-copy
• bytevector->list
• list->bytevector

Random access lists are a data structure similar to lists, but with very different efficiency characteristics. A regular list built out of cons cells is an optimal solution, if one needs to work mainly with the initial elements or the whole list at a time. However, if you need to frequently find and maybe update values in the middle of the list, you have to perform operations taking time proportional to the length of the list. In other words, those list operations are linear time, or have complexity O(n). Cons, car and cdr on the other hand are very efficient for regular lists. Regardless of the size of a list, it will always take a fixed amount of time to add, take or remove a value from it. In other words, these operations are constant time, or have complexity O(1).

A random access list is a data structure, which unsurprisingly attempts to make random access and update efficient.

The performance characteristics of this random access list library are:

car → O(1)
cdr → O(log n)
cons → O(log n)
get → O(log n)
set → O(log n)
len → O(log n)
fold → O(n)
foldr → O(n)
map → O(n)
append → O(n log n)
list->rlist → O(n log n)
rlist->list → O(n)

The operation is based on two ideas. Firstly, a random access list consists of a sequence of complete binary trees. The binary trees are built out of cons cells when needed. The first tree is always of height 1, meaning it just holds the value, much like a regular cons cell. The next node always holds a binary tree either of the same or next height. There can be at most two trees of the same height next to each other. Therefore, tree heights (1 1), (1 2 4) and (1 1 2 4 4) are valid, whereas (1 1 1), (2 2 4) and (1 2 2 8) are not. (5) is right out.

Secondly, trees can be addressed directly with bits. It takes a n-bit number to address each node of a complete binary tree of height n. Finding a value from a random access list works here by first finding the tree in which the value is held, and then using the remaining bits to find the correct leaf node in the tree.

It is easy to see that it takes O(log n) steps to find the tree in which some particular value is held, and then another O(log n) steps to walk the tree to a given position, Threfore we have a total complexity of O(log n) for access and update.

Exported values:

• rnull
• rcons
• rget
• rcar
• rcdr
• rset
• rlen
• rmap
• rlist
• rfold
• rfoldr
• rnull?
• rpair?
• rreverse
• rappend
• list->rlist
• rlist->list

Examples:

• let rla = (rlist 1 2)
• let rlb = (rlist 3 4 5)
• (rcar (rcons 11 rnull)) = 11
• (rget rnull 100 'no) = 'no
• (rget rla 1 'no) = 2
• (rget rla 9 'no) = 'no
• (rnull? (rcdr (rcons 11 rnull))) = #true
• (rlen (rcons 11 rnull)) = 1
• (rlist->list (rlist 11 22 33)) = '(11 22 33)
• (rmap dup (rlist 10 20 30)) = (rlist 20 40 60)
• (rappend rla rlb) = (rlist 1 2 3 4 5)

This library defines finite functions. They are commonly used in Owl to construct efficient key-value mappings. A finite function is much like an association list, which are frequently used in Lisp. The main difference is that finite functions are represented as red-black trees internally, so the performance is much better when there are many keys.

The value `empty` is an empty finite function. It contains no mappings. You can read the value of of a mapping with `get`, which accepts a finite function, a key to be fetched and optionally a default value to return if the key is not mapped. `put` can be used to extend a ff and `del` removes a mapping.

> (define f (put (put empty 'foo 100) 'bar 42)) > f #<function> > (get f 'foo #f) 100 > (get f 'x #f) #f > (get (del f 'foo) 'foo #f) #f This data structure is made possible by the fact, that Owl has an order-preserving garbage collector. Therefore we have a total order on objects, which makes it possible to build balanced trees by comparison.

Exported values:

• put
• get
• del
• empty
• empty?
• fupd
• ff-fold
• ff-foldr
• ff-union
• ff-has?
• list->ff
• ff->list
• ff-iter
• ff-min
• ff-max
• ff-map
• ff
• keys

Examples:

• let test = (list->ff '((a . 1) (b . 2) (c . 3)))
• (get test 'a 0) = 1
• (get test 'x 0) = 0
• (keys test) = '(a b c)
• (ff->list empty) = ()
• (ff->list (put empty 'a 42)) = '((a . 42))
• (ff->list (put test 'a 42)) = '((a . 42) (b . 2) (c . 3))
• (ff->list (put test 'd 42)) = '((a . 1) (b . 2) (c . 3) (d . 42))
• (ff->list (del test 'a)) = '((b . 2) (c . 3))
• (ff->list (del test 'x)) = '((a . 1) (b . 2) (c . 3))
• (ff-fold (λ (out k v) (cons v out)) () test) = '(3 2 1)
• (ff-foldr (λ (out k v) (cons v out)) () test) = '(1 2 3)
• (ff-map (lambda (k v) (null? v)) (ff 'a 1 'b '())) = (ff 'a #false 'b #true)

Number stores (radix trees with a ff at each node)

Exported values:

• iget
• iput
• ifold
• iff->list
• iempty

This library implements serialization of objects to byte lists, and parsing of the byte lists to corresponding objects. The format is used internally for storing memory images to disk. Files with .fasl suffix used in booting up Owl are just fasl-encoded functions.

Exported values:

• fasl-encode
• fasl-encode-cooked
• fasl-encode-stream
• fasl-decode
• decode-or
• encode
• objects-below
• decode-stream
• sub-objects

Examples:

• (fasl-decode '() 'x) = 'x
• (fasl-decode (fasl-encode 42) 'x) = 42
• (fasl-decode (fasl-encode '(1 2)) 'x) = '(1 2)
• (fasl-encode 42) = '(0 0 42)
• (fasl-encode 1/4+i) = '(1 42 2 0 0 1 0 0 4 1 43 2 1 0 0 1 0)
• (fasl-decode '(0 0 0 0) 'bad) = 'bad
• ((fasl-decode (fasl-encode prime?) 'bad) 13337) = #true

This library defines macros for using functions (which are lambda expressions) as data structures.

Exported values:

• define-sum-type
• trod

This library writes programs in formats required from the compiler. Programs can currently be written as FASL-encoded bytecode for use in the VM, or a mixture of C and FASL when compiling to C.

Exported values:

• make-compiler
• dump-fasl
• load-fasl
• suspend

It is sometimes useful to get symbols, which do not occur elsewhere. This is typically needed in the compiler, but it may also be needed elsewhere. Gensyms in Owl are just regular symbols, which do not occur in a given expression. This requires walking through the whole expression. To avoid having to walk the original expression in many cases when gensyms are needed, they work in a way that ensures that the gensym of the gensym of an expression also does not occur in the original expression.

Exported values:

• fresh
• gensym

Examples:

• (gensym 'x) = 'g1
• (gensym 'g1) = 'g2
• (gensym '(lambda (x) x)) = 'g1
• (gensym '(lambda (g10) g11)) = 'g12

You cannot mutate values, but threads can also be used to encapsulate state. This library introduces seemingly variable values implemented threads which allow setting and getting a value.

Exported values:

• make-variable
• link-variable

The goal of this library is to make writing software tests and documenting functionality as simple as possible. The operation is as follows:

• Tests run automatically when a program or library is loaded. Failure aborts the load via an error.
• Tests can be collected from code automatically for documentation.
• To add tests, import (owl proof) and write an example.

Exported values:

• theorem
• theorem-equal?
• example

Examples:

• 1 = 1
• (cons 1 2) = '(1 . 2)
• (values 1 2) = (values 1 2)

This library implements hygienic macro expansion. The role of this library is to construct the transformer functions out of the usual define-syntax definitions as specified in R7RS Scheme.

A macro mainly consists of a set of patterns to be tried on code. If one of them matches, then the corresponding rewrite rule is used to transform the expression. A pattern may contain literals, which means symbols that must be the same as in the pattern, and rest are generally used as syntax variables. A syntax variable is matched to any expression in the input expression, and it can be used to place the expression somewhere in the rewrite rule.

It is also possible to use the ellipsis pattern, denoted by suffixing a pattern ..., which means that the pattern may occur zero or more times. Suffixing a syntax variable bound within such pattern with ... in the rewrite rule causes all of the matches to be added.

Exported values:

• define-syntax
• new-define-syntax-transformer

Examples:

• (new-ellipsis '() 1) = '(())
• (new-ellipsis '(a) 1) = '(a ())
• (new-ellipsis '(a (b c)) 2) = '(a (b c ()))
• (push-ellipsis '(a b c) 1 'd) = '(a b c d)
• (push-ellipsis '((a b) (c d)) 2 'e) = '((a b) (c d e))
• (test-rewrite '(a b c) '((a bound . A) (b bound . B) (c literal))) = '(ok (A B c))
• (test-rewrite '(a ... b ...) '((a 1 a1 a2 a3) (b 1 b1 b2 b3))) = '(ok (a1 a2 a3 b1 b2 b3))
• (test-rewrite '((a b) ...) '((a 1 a1 a2 a3) (b 1 b1 b2 b3))) = '(ok ((a1 b1) (a2 b2) (a3 b3)))
• (test-rewrite '((a b ...) ...) '((a 1 a1 a2) (b 2 (b1 b2 b3) (B1 B2 B3)))) = '(ok ((a1 b1 b2 b3) (a2 B1 B2 B3)))
• (test-rewrite '(x y z) '()) = '(ok (g1 g2 g3))
• (test-rewrite '(x (a x) ... x) '((a 1 a1 a2))) = '(ok (g1 (a1 g1) (a2 g1) g1))
• (test-rewrite '((a x) ...) '((a 1 a1 a2))) = '(ok ((a1 g1) (a2 g2)))
• (xlet ((foo 100)) foo) = 42
• (xlet ((a 1) (b 2)) (list a b)) = '(1 2)

This library defines the thread controller. It handles activation, suspension and requested external actions of continuation-based threads. It is much like a very small kernel.

A thread is simply a function. Owl programs have two continuations, one for the regular one and one for the thread scheduler under which the function is running. Every function eventually calls its own final continuation, which results in the thread being removed from the thread scheduler. It can also call the second continuation and request operations from this thread scheduler.

The task of the thread scheduler is to run each running thread for a while, suspend and activate them, and handle message passing.

Threads have a primitive only for asynchronous message passing, but they can voluntarily wait for a specific kind of response, resulting in synchronous operation where desired.

Exported values:

• start-thread-controller
• thread-controller
• signal-handler/repl
• signal-handler/halt
• signal-handler/ignore
• report-failure
• try-thunk
• try

This library exports the usual arbitrary precision bignum arithmetic functions. You can also use specific (owl math X) libraries if necessary.

Exported values:

• quotient
• <<
• >>
• band
• bior
• bxor
• fx-width
• ncar
• ncdr
• fx-greatest
• zero?
• integer?
• truncate/
• even?
• odd?
• fixnum?
• ediv
• numerator
• denominator
• gcd
• (exports (owl math complex))
• (exports (owl math extra))

This library defines arbitrary precision integer arithmetic. Some of the functions are only defined for integers, whereas others are typically extended to handle also more complex kinds of numbers.

Operations to be extended typically export both the operation defined for integers only, and a corresponding mk-* version which calls a given function in case the types of inputs are not integers. This allows extending the definitions in other modules while checking the most common cases of integer inputs in first branches.

Owl currently has 24 bits available for encoding a value in an immediate value, meaning a value that does not have to be stored in memory. A fixnum, or a fixed size number, is a number which fits these bits. The sign of a fixnum is stored the type of the immediate object.

When a number is bigger or smaller than the maximum fixnum, it is converted to an allocated integer. In this case the representation of the number is a linked sequence of base 2²⁴ digits of the number starting from the least significant digits. Again the sign of the number is stored in the type.

A valid fixnum zero is always positive, and a valid negative bignum has the negative type only at the root node.

Exported values:

• fixnum?
• integer?
• mk-add
• mk-sub
• +
• -
• *
• =
• /
• <<
• <
• <=
• =
• >=
• >
• >>
• band
• bior
• bxor
• quotient
• ediv
• truncate/
• nat-succ
• big-bad-args
• negate
• ncar
• ncdr
• even?
• odd?
• zero?
• negative?
• positive?
• rem
• mod
• ncons
• ncar
• ncdr
• big-digits-equal?
• fx-greatest
• fx-width
• to-int-
• to-int+
• to-fix+
• to-fix-
• add-big
• sub-big
• right-out

This library defines arbitrary precision rational arithmetic operations. A rational number p/q is a typed pair of arbitrary precision integers. A valid rational number has q != 0, q != 1, and gcd(p, q) = 1.

Exported values:

• mk-rational-add
• mk-rational-sub
• +
• -
• <
• /
• gcd
• gcdl
• rational
• numerator
• denominator
• divide
• negate

This library defines complex arbitrary precision math functions.

Exported values:

• +
• -
• *
• /
• =
• complex
• negate

Exported values:

• abs
• floor
• sum
• product
• render-number
• log2
• log
• lcm
• negative?
• positive?
• number?
• exact-integer-sqrt
• isqrt
• sqrt
• expt
• expt-mod
• round
• ncr
• npr
• truncate
• modulo
• remainder
• ceiling
• !
• factor
• prime?
• real?
• complex?
• rational?
• primes-between
• totient
• phi
• divisor-sum
• divisor-count
• dlog
• dlog-simple
• fib
• histogram
• negative?
• min
• max
• minl
• maxl
• <
• >
• >=
• <=
• +
• -
• *
• /

Examples:

• (round 10000000000001/10000000000000) = 1
• (round 14999999999999/10000000000000) = 1
• (round 3/2) = 2
• (round -7/5) = -1
• (round -3/2) = -2
• (round -1/2) = -1
• (round 30864/25) = 1235
• (round 9/5) = 2
• (round -9/5) = -2
• (round -149/100) = -1
• (round 199999999999999999999999/10000000000000000000000) = 20
• (floor 199999999999999999999999/100000000000000000000000) = 1
• (ceiling 1/100000000000000000000000) = 1

This library makes it easy to write tools which use standard UNIX command line tool conventions. These include accepting short and long versions of flags (-h or --help), packing multiple flags to a single short one (-hai = -h -a -i), handling and verification of flag arguments (--output foo.txt), ability to handle flags anywhere in the arguments and use of -- to stop command line argument processing (e.g. to remove a file called -h or process globbed files coming from an untrusted source).

Exported values:

• process-arguments
• format-rules
• print-rules
• parse-args
• cl-rules

This library is for converting potentially large integers to more readable and less accurate form. Mainly used for formatting output of ,time repl command.

Exported values:

• format-time
• format-number
• format-number-base2

Examples:

• (format-time 123456789) = "123.45ms"
• (format-number 4096) = "4.09k"
• (format-number-base2 4096) = "4.00K"

This library implements a simple DSL for constructing parsing functions. The operation is traditional top down backtracking parsing.

Exported values:

• parses
• byte
• imm
• input-ready?
• seq
• epsilon
• ε
• byte-if
• peek-byte
• rune
• rune-if
• either
• either!
• one-of
• one-of!
• star
• plus
• greedy-star
• star!
• greedy-plus
• plus!
• byte-between
• parse-head
• backtrack
• parse
• try-parse
• first-match
• word
• maybe
• byte-stream->exp-stream
• fd->exp-stream
• file->exp-stream
• silent-syntax-fail
• resuming-syntax-fail

Examples:

• (first-match byte '(1 2) 'x) = (values 1 '(2) 1)
• (first-match (imm 42) '(1 2) 'x) = (values 'x '(1 2) 0)
• (first-match (seq (imm 1) (imm 2)) '(1 1 2) 'x) = (values 'x '(1 1 2) 1)
• (first-match (seq (imm 1) (imm 1)) '(1 1 2) 'x) = (values '(1 . 1) '(2) 2)
• (first-match (star (imm 1)) '(1 1 1 2) 'x) = (values '(1 1 1) '(2) 3)
• (first-match (plus (byte-if even?)) '(2 4 8 9) 'x) = (values '(2 4 8) '(9) 3)
• (first-match (plus (one-of (imm 1) (imm 2))) '(1 2 3 4) 'x) = (values '(1 2) '(3 4) 2)
• (first-match (either (seq (imm 1) (imm 1)) (seq (imm 1) (imm 2))) '(1 2 3) 'x) = (values '(1 . 2) '(3) 2)
• (first-match (either! (seq (imm 1) (imm 1)) (seq (imm 1) (imm 2))) '(1 2 3) 'x) = (values 'x '(1 2 3) 1)
• (first-match (either! (seq (imm 2) (imm 1)) (seq (imm 1) (imm 2))) '(1 2 3) 'x) = (values '(1 . 2) '(3) 2)
• (first-match (seq (imm 1) (peek-byte (λ (x) (eq? x 2)))) '(1 2 3) 'x) = (values '(1 . 2) '(2 3) 1)
• (first-match (seq (imm 1) (peek-byte (λ (x) (eq? x 2)))) '(1 3 3) 'x) = (values 'x '(1 3 3) 1)

This library attempts to implement date processing functions. Dates are typically represented as seconds or milliseconds since UNIX Epoch 1.1.1970. These are generally a good way to work with time, apart from assuming that an absolute time exists at all. Sometimes it is however necessary to convert time stamps to human readable form, which means splitting the time according to various more and less sensible rules.

 (time)                → current time in seconds since epoch
 (time-ms)             → current time in milliseconds since epoch
 (date-str 0)          → "00:00:00 1.1.1970 UTC+00:00"
 (date-str (time) 2.5) → "20:49:08 19.3.2018 UTC+02:30"
 (date 0)              → 1 1 1970 0 0 0 ; as multiple values
 (leap-year? 2018)     → ##false

Exported values:

• date
• leap-year?
• valid-date?
• next-date
• next-date-with-week
• week-info
• day-names-fi
• day-names-en
• date-str
• date-str-tz
• year-start-day
• year-start-week-info
• minute
• hour
• day
• week
• year
• leap-year

Examples:

• (next-date-with-week 31 12 1971 5 1) = (values 1 1 1972 6 1)
• (next-date-with-week 27 12 1970 7 52) = (values 28 12 1970 1 53)
• (date-str 0) = "00:00:00 1.1.1970 UTC+00:00"
• (date-str 0 5/2) = "02:30:00 1.1.1970 UTC+02:30"
• (date-str 1234567890 0) = "23:31:30 13.2.2009 UTC+00:00"

The digest library provides functions for computing cryptographic signatures. Currently SHA1 and SHA256 digests and corresponding message authentication codes are supported.

The hash functions also have `hasher-raw` and `hasher-bytes` -variants, which return the state words and raw signature bytes correspondingly.

(sha1 data) → hash-string (sha256 data) → hash-string (hmac-sha1 key message) → hash-string (hmac-sha256 key message) → hash-string

Exported values:

• sha1
• sha1-raw
• sha1-bytes
• sha256
• sha256-raw
• sha256-bytes
• hmac-sha1
• hmac-sha1-bytes
• hmac-sha256
• hmac-sha256-bytes

Examples:

• (sha1 "") = "da39a3ee5e6b4b0d3255bfef95601890afd80709"
• (sha1 "owl") = "2c730e3a6d2aad6d914872e45f868d20a543570a"
• (sha1 "λä.ä") = "726f4307d91f7433472917b27c486c9004b94179"
• (sha256 "") = "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
• (sha256 "owl") = "10f7127b980b0b06ef157749f8a02cca1c606d22642729dcb2d24dbbf2bf30df"
• (sha256 "λä.ä") = "e5b21ee5e8532c8f768aa9090ba71ae799016a0904b13ee855cbd58853464234"

This library is used by by the REPL to read input similarly to what the traditional readline library does.

Exported values:

• readline-default-options
• readline-result-stream
• readline
• port->readline-line-stream
• port->readline-byte-stream

this library implements a mostly complete POSIX-compatible regular expressions. at the moment lib-regex tries to just get all the features right. *lots* of non-constant-factor optimizations are missing.

spec: http://pubs.opengroup.org/onlinepubs/007908799/xbd/re.html syntax ref of portable scheme regexps (Dorai Sitaram): http://evalwhen.com/pregexp/index-Z-H-3.html

Exported values:

• get-sexp-regex
• get-replace-regex
• string->regex
• string->replace-regex
• string->complete-match-regex
• rex-matches

Randomness is an interesting thing to work with in a purely functional setting. Owl builds randomness around streams of typically deterministically generated 24-bit fixnums. These are usually called rands in the code.

A function involving randomness typically receives a rand stream, and also returns one after possibly consuming some rands. Behavior like this would be easy to hide using macros or monadic code, but Owl generally strives to be explicit and simple, so the rand streams are handled just like any other value.

> (define rs (seed->rands 9)) > (rand rs 10000) '(values #<function> 3942) ;; the new rand stream and 3942 > (lets ((rs a (rand rs 10000))) a) 3942 > (lets ((rs elem (rand-elem rs '(a b c d e f g)))) elem) 'c > (lets ((rs sub (rand-subset rs '(a b c d e f g)))) sub) '(b e f) > (lets ((rs perm (random-permutation rs '(a b c d e f g)))) perm) '(g e c b d a f) > (lets ((rs ns (random-numbers rs 100 10))) ns) '(95 39 69 99 2 98 56 85 77 39)

Exported values:

• lcg-rands
• seed->rands
• rands->bits
• seed->bits
• rands->bytes
• seed->bytes
• rand
• rand-nbit
• rand-log
• rand-elem
• rand-subset
• rand-range
• random-numbers
• reservoir-sample
• shuffle
• random-permutation
• random-subset
• rand-occurs?

Owl is is by default a multitasking system. Multiple threads can be working on tasks and waiting for input or output at the same time, so we cannot simply define input and output (I/O) as lisp functions calling the corresponding operating system code via the VM.

There are a few ways how I/O could work in a multithreaded setting. Having a lot of I/O code in the thread scheduler is convenient to use, but results in an ugly thread scheduler. Having separate threads for each file descriptor and using only message passing for I/O is elegant, but turned out to be somewhat cumbersome to use. The current version is something in between. One thread, called iomux, handles port blocking and timers. Threads attempt to do I/O directly when calling e.g. print or read, but if the operation would require waiting for input or output, then the thread sends a synchronous message to iomux and gets a response when the task can be completed without blocking.

Notice that the I/O defined in this library cannot in general be used unless iomux is running. This may happen when working with code that has not called (start-muxer), and when trying to debug the thread scheduler.

Exported values:

• open-output-file
• open-input-file
• open-append-file
• open-socket
• open-tcp-socket
• open-udp-socket
• open-connection
• file-size
• port->fd
• fd->port
• port?
• close-port
• start-base-threads
• wait-write
• when-readable
• blocks->port
• closing-blocks->port
• tcp-client
• tcp-clients
• tcp-send
• udp-packets
• udp-client-socket
• wait-udp-packet
• check-udp-packet
• send-udp-packet
• file->vector
• file->list
• file->byte-stream
• vector->file
• write-vector
• port->meta-byte-stream
• port->byte-stream
• port->tail-byte-stream
• byte-stream->port
• byte-stream->block-stream
• port->block-stream
• block-stream->port
• copy-port
• copy-file
• display-to
• print-to
• print
• print*
• print*-to
• write
• writer-to
• write-to
• write-bytes
• write-bytevector
• read-bytevector
• try-get-block
• byte-stream->lines
• lines
• system-print
• system-println
• system-stderr
• fasl-save
• fasl-load
• start-muxer
• sleep

There are two ways to serialize values to sequences of bytes: S-expressions and the FASL encoding. S-expressions represent trees of certain values and can thus only be used to accurately represent a subset of all possible values. FASL encoding can represent all values, apart from from their external semantics such as open network connections.

This library implements the S-expression part. There are further two flavors of rendering: the one intended to be printed out of programs and the one which results in expressions that can be read back in. The first one is usually seen as the output of print, whereas the other one is typically written with write.

Some R7RS Scheme extensions to represent shared structure in S-expressions is also implemented.

Str and str* are used to translate values to strings, whereas render and render* are typically used in a fold to construct lists of bytes to be later converted to strings or other formats.

Exported values:

• make-serializer
• render
• render*
• str
• str*

Examples:

• (render "foo" null) = (string->list "foo")
• (render* "foo" null) = (string->list "\"foo\"")

Exported values:

• sort
• isort
• quicksort
• mergesort

Examples:

• (sort < '(1 4 2)) = '(1 2 4)
• (sort (λ (a b) (< (>> a 1) (>> b 1))) '(2 8 4 9 0 5 1 6 7 3 5)) = '(0 1 2 3 4 5 5 6 7 8 9)

Typical Scheme programs have a continuation underlying in the execution of a program. Depending on the implementation strategy, this continuation may be an actual variable and a function, as is done in Owl, or it is simulated on a more traditional stack-based system.

Owl has in fact two continuations. One is the normal one you can capture with call-with-current-continuation, but the other one is threaded even through that operation. The other continuation is that of the thread scheduler. It is also a regular program. The main difference in it is that it is expected to be called initially when the program starts and the second continuation is blank. Calling the blank continuation is what eventually terminates the whole program.

Normal progams can only access the second continuation via a primop. When this happens, the continuation of the running program is captured as usual, and the second thread scheduler continuation is called with the information provided in the call along with the continuation allowing resuming execution of the program from the corresponding state.

Wrappers for calling the thread scheduler are defined in this library.

Exported values:

• syscall
• error
• interact
• accept-mail
• wait-mail
• next-mail
• check-mail
• exit-owl
• release-thread
• catch-thread
• set-signal-action
• single-thread?
• kill
• link
• mail
• return-mails
• fork-named
• exit-thread
• exit-owl
• poll-mail-from
• start-profiling
• stop-profiling
• running-threads
• library-exit
• thread
• thunk->thread

This library defined various system calls and wrappers for calling them. The calls available are mainly frequently needed ones defined in the POSIX standard, or otherwise portable enough to be available in most systems these days.

Exported values:

• dir-fold
• dir->list
• dir->list-all
• errno
• strerror
• exec
• fork
• pipe
• wait
• waitpid
• getpid
• kill
• getenv
• setenv
• unsetenv
• umask
• getcwd
• chdir
• readlink
• symlink
• link
• rename
• unlink
• rmdir
• mknod
• mkdir
• mkfifo
• stat
• directory?
• file?
• chmod
• chown
• lseek
• seek-current
• seek-set
• seek-end
• sighup
• sigint
• sigquit
• sigill
• sigabrt
• sigfpe
• sigkill
• sigsegv
• sigpipe
• sigalrm
• sigterm
• O_RDONLY
• O_WRONLY
• O_APPEND
• O_CREAT
• O_TRUNC
• close
• fcntl
• open
• dupfd
• read
• write
• port->non-blocking
• port->blocking
• CLOCK_REALTIME
• clock_gettime
• set-terminal-rawness
• mem-string
• mem-strings
• peek-word
• peek-byte
• get-environment
• get-heap-bytes-written
• get-heap-max-live
• isatty
• resolve-host
• catch-signals
• execvp
• system

#false Exported values:

• set-terminal-rawness
• font-normal
• font-bright
• font-dim
• font-standard
• font-reverse
• font-attrs
• font-gray
• font-fg-black
• font-fg-red
• font-fg-green
• font-fg-yellow
• font-fg-blue
• font-fg-magenta
• font-fg-cyan
• font-fg-white
• font-bg-black
• font-bg-red
• font-bg-green
• font-bg-yellow
• font-bg-blue
• font-bg-magenta
• font-bg-cyan
• font-bg-white
• clear-screen
• clear-screen-top
• clear-screen-bottom
• clear-line
• clear-line-left
• clear-line-right
• set-cursor
• cursor-hide
• cursor-show
• cursor-save
• cursor-restore
• cursor-up
• cursor-down
• cursor-left
• cursor-right
• enable-line-wrap
• disable-line-wrap
• set-scroll-range
• scroll-up
• scroll-down
• cursor-pos
• terminal-input
• get-terminal-size
• get-cursor-position

#false Exported values:

• elapsed-real-time
• time
• time-ms
• time-ns

Exported values:

• utf8-encode
• utf8-decode
• utf8-sloppy-decode
• utf8-decoder
• encode-point
• min-2byte
• min-3byte
• min-4byte
• two-byte-point
• three-byte-point
• four-byte-point
• last-code-point
• valid-code-point?

Most of the system is implemented in Owl itself. The code responsible for implementing language features resides mainly in (owl eval ...) modules. These allow translating S-expressions down to bytecode for a really simple virtual machine. The bytecode can also be converted to C to make programs standalone and reduce some interpretive overhead.

Runtime

Source code of the virtual machine is at c/ovm.c It consists of about 1500 lines of C responsible for implementing the primitive data types and operations, garbage collection, loading FASL-encoded images and implementing a simple register-based virtual machine for running the bytecode.

No external dependencies are allowed and the VM should compile and run as such without extra configuration steps. The goal has been to keep all of the required runtime code at around 1000 lines with 2000 as the absolute maximum.

Data Representation

The VM works on registers having the width of a pointer, which is generally 32 or 64 bits. Values stored in registers are called words. There are two kinds words: allocated and immediate ones. An immediate word holds some value and information about its type within itself. An allocated word similarly has a few bits of metadata, but mainly it's job is to point to memory where the rest of the value is stored.

All pointers on 32- and 64-bit machines have two or three zero bits at the bottom. One of these is used by the GC, and the other is used to mark whether the number is an immediate value. As a consequence, a lisp pointer is just a regular pointer.

Immediate values further have the type of the value and room for the actual encoded value in the subsequent higher bits. An immediate 32-bit value is encoded as:

                          .------------> 24-bit payload
                          |      .-----> type tag if immediate
                          |      |.----> immediateness
 .------------------------| .----||.---> mark bit (can only be 1 during gc)
 |                        | |    |||
[pppppppp pppppppp pppppppp tttttt10]

An allocated value is represented simply as the pointer to the corresponding object, because the pointers are always aligned to 32-bit words and consequently the 2 lowest bits as always 0, which means the value is treated as an allocated one.

Non-immediate values are called allocated, because they point to allocated memory. In this case the pointer points to an immediate value, which is the header of an allocated object. The header mainly contains the type of the object, its size, and a flag whether the contents are themselves descriptors or just raw data.

Garbage Collection

Owl uses a single continuous chunk of memory. Originally only the sbrk() system call was needed to adjust the size of the memory, but this was converted to more complex malloc/resize because it turned out OSX does not support is properly.

The GC is order preserving. Objects are in general allocated in the same or reverse order to how they are later read. Moving objects around would cause unnecessary load on caches, so we want to preseve the order in which they were allocated. Since we are also compacting the heap, this means the GC usually makes the heap more cache friendly. This also makes it possible to define total order on objects, which is an important feature for implementing some core data structures efficiently.

Purely functional operation and order preserving heap result in a unidirectional memory where pointers can only point down. This seemed to be a unique feature on which very little existing information or algorithms were found, so it made sense to desing a new GC taking advantage of the property.

The design relies on the ideas I first saw in threading garbage collectors. In particular the paper "Efficient Garbage Compaction Algorithm" by Johannes Martin (1982). In a nutshell, we find all the places pointing to a particular object and reverse the links to a single chain, so that the original object holds a linked list of all places where it was linked from. This makes it possible to place the object anywhere in the heap, because traversing the list and restoring the pointers makes it possible to point them to the new location.

This process is used to first thread all the pointers starting from VM registers. All objects not reached from the registers have an empty thread of links pointing to them, so they can be freed. The next step is to slide all objects down in the heap and unthread the pointers to them.

This would be sufficient for reclaiming free space, but we additionally take advantage of the fact that young objects tend to be discarded frequently while old ones tend to stick around for a long time. This is taken advantage of by generational collectors, which can treat newer objects differently from other ones. The idea is to use each free space resulting from compaction phase as a new generation, if it is at least a few kilobytes in size. The next GC will therefore only process the new objects and not look at the rest of the heap most of the time.

Operating System Interface

Most calls to the underlying operating system happen via prim_sys() function. It is called via sys-prim primop from lisp side. The function receives a system call number to call and three arbitrary lisp values. prim_sys() is then expected to do its thing and return one lisp value.

New calls can be added by placing them to the switch statement in ovm.c, recompiling the vm with make bin/vm, starting it with bin/vm fasl/init.fasl and calling the newly added primitive with something like (sys-prim 42 1 2 3).

Ideally we would like to just call the kernel just like done in assembly, but there are no sufficiently portable ways to do this from C, so we use the standard library functions and definitions.

Virtual Machine

Most of evaluation time is spent in vm() function. It implements a simple virtual register machine. It uses a traditional large switch statement for instruction dispatch, which these days is reliably compiled to a jump table. Each bytecode has six bits for the instruction and two bits for optional extra information.

There is also a separate dispatch loop for instructions generated by the C-compiler. This is not needed when running vanilla bytecode, such as fasl/init.fasl.

Compiler

Evaluation ties together all the separate compiler passes. Each pass is a function of the environment in which the evaluation occurs and the current version of the expression to be evaluated, and returns either an error or next versions of the environment and expression. In the final step the expression has been converted to a thunk, meaning a function of zero arguments, which when called gives the value(s) of the expression.

Evaluate returns the success/failure data structure used in the compiler. Exported-eval is the function typically found at toplevel as eval.

Exported values:

• evaluate
• exported-eval

Examples:

• (evaluate '(car '(11 22)) *toplevel*) = (ok 11 *toplevel*)
• (exported-eval '(car '(11 . 22)) *toplevel*) = 11

This step renames all variables to fresh symbols. This is not strictly necessary, but it makes some compilation steps easier.

Exported values:

• alpha-convert

This library converts the RTL expressions to bytecode executable by the VM.

CPS conversion usually produces a lot of small functions with equal bytecode but potentially different bindings in the environment. In order to make programs smaller and improve cache friendliness the bytecode is interned, just like we do with symbols.

Exported values:

• assemble-code
• simple-value?
• small-value?

S-expressions could be used internally by the compiler at each step. Here we however construct a simple tree of tuples format out of the S-expression while checking its structure. This is done so that the subsequent compiler steps don't have to check S-expression structure.

The AST format could switch to using sum types at some point.

Exported values:

• call?
• var?
• value-of
• sexp->ast
• mkcall
• mklambda
• mkvarlambda
• mkvar
• mkval

This library is needed when compiling programs to C-programs. This library is also used to compile Owl itself.

The simples way to build standalone C-programs out of owl programs is to write the virtual machine code and the FASL-encoded program to run to a file. This happens when owl is invoked without the -O flags. On the plus side the resulting program has very little C-code, so the C-compiler won't take much time when compiling it. This is how the small Owl version is built.

Typically the output is optimized. This is done by translating some of the bytecode sequences of the program to be compiled to corresponding C-code fragments, adding them as new instructions to the vanilla virtual machine, and replacing them from the program with calls to the new instructions. The resulting C-code is larger and may take quite a bit of memory to compile using some C-compilers, but the resulting binary will be faster. This is how the usual bin/ol interpreter is built.

Exported values:

• compile-to-c

Even though all bindings and operations are just lambdas, we need to differentiate a few kinds of them depending on their content and use.

A lambda occurring in the operator position does not need to be treated as a function, because it simply means assigning names to values. They are leaft intact and generally end up being implemented as register moves.

The lambdas we need to represent somehow at runtime are further split to closures and procedures. A procedure is lambda which does not depend on values known only at runtime, so the corresponding object can be constructed at compile time. In the special case where it also does not require any references to non-trivial other values, the value ends up being just the bytecode.

A closure is a lambda which requires some values known only at runtime. For these a procedure is generated at compile time, and instructions to add the remaining values at runtime are added to bytecode.

Exported values:

• build-closures
• uncompiled-closure?

Lambdas can have any number of variables. The variables eventually end up representing virtual machine registers. There are only a fixed number of registers in the VM, and certain values should be in certain registers at certain points in evaluation. Therefore we need a transformation from the AST expression to something closer to bytecode operating on registers. This format uses a similar tuple structure and is called RTL, short for register transfer language.

The task of this library is mainly to assign a VM register to each variable and convert references accordingly.

This module is quite old. The register allocator could be updated at some point, after which the number of VM registers could be reduced.

Exported values:

• compile

The continuation passing style, or CPS, transformation converts a lambda expression to another lambda expression, with some useful properties. The output is a function with one extra argument, which will be called with the result of the original function.

There are three main reasons for using the conversion. For one, the resulting lambda expression can be evaluated without the need for a stack, because nested function calls are eliminated and replaced by tail calls. What would normally be stored on a stack now ends up being stored in a closure.

The second reason is that Scheme allows capturing the added argument, which is called the continuation, to a variable. This requires no special support from the runtime, because the continuation is just a regular lambda.

Thirdly the presence of continuations makes implementing multithreading easy. Owl has pre-emptive multithreading, meaning a thread does not need to voluntarily give up control for other threads to run. This is done by jumping from the thread-local continuation to thread-scheduler continuation whenever a thread switch occurs.

Exported values:

• cps

This library contains shared data structures used in the compiler. Originally all the data structures were either S-expressions or tuples with a fixed structure. They are being converted to sum types, which makes it possible to verify some aspects of use of the data structure at compile time.

Exported values:

• success
• ok
• fail
• rtl-case
• ret
• move
• prim
• cons-close
• ld
• refi
• goto
• jeqi
• jeq

Evaluation happens in an environment. An environment maps variables to values. This library defines operations on the environment structure used by the compiler.

Exported values:

• lookup
• env-bind
• empty-env
• apply-env
• env-fold
• verbose-vm-error
• prim-opcodes
• opcode->wrapper
• primop-of
• primitive?
• poll-tag
• link-tag
• buffer-tag
• signal-tag
• thread-quantum
• current-library-key
• env-set-macro
• *tabula-rasa*
• env-del
• env-get
• env-del
• env-set
• env-keep
• env-get-raw
• env-put-raw
• env-keys

Implementing recursion becomes an interesting problem when mutation is not allowed. Scheme allows recursion in definitions and via the letrec primitive form, which under the hood require mutable data structures. We don't have them here, and the only way to construct bindings and functions is a run of the mill lambda.

Luckily, a lambda is all it takes to recurse. This library takes a version of the program in which one can use a recursive lambda, or rlambda, and converts it to a corresponding expression using only normal lambdas.

The conversion is a custom one developed for the first version of Owl. It operates by exteding each recursive lambda with the other recursive functions it may call, propagating the required values to required call sites at required places, and constructing wrapper functions which convert the originally intended arguments to ones the actual recursive operations need.

The added extra arguments are added after the original ones. This is important, because we want the wrapper functions to just consist of a few loads to free registers from their environment and a jump.

Exported values:

• fix-points

The VM has only a finite number of registers. This library attempts to reduce the number of registers needed by the RTL, and choose better registers for values to avoid unnecessary shuffling of values.

Old code. Scheduled for a rewrite.

Exported values:

• allocate-registers
• n-registers

Owl Lisp is being written mainly as a standalone pet project, but it has gotten many useful bug reports, suggestions and patches during the course of its development. Here is a partial list of people who have helped in the development:

Jo Henke           A ton of improvements
Doug Currie        GC improvements, data representation optimizations, etc.
John Cowan         A slew of filed bugs.
Pekka Pietikäinen  Portability suggestions and patches.
Erno Kuusela       Portability suggestions and general insight.

The code similarly isn't based on any implementation or document, but many have definitely had an impact on it. A partial list of such sources follows:

Recursive Programming Techniques, William H. Burge, 1975
Essentials of Programming Languages, Friedman, Wand, Haynes, 1992
Efficient Garbage Compaction Algorithm, Johannes Martin, 1982
Scheme48, http://s48.org/ and various papers on it
Structure and Interpretation of Computer Programs, http://mitpress.mit.edu/sicp/

Otus Lisp is a related language. It adds features such as FFI to be able to write graphical programs and interface with other external libraries.

R7RS Scheme (pdf)

FAQ

Q: Where can I get help?: You can stop by at #owl-lisp on freenode, file tickets to gitlab or send email to [email protected].

Q: How can I use third party libraries?: Grab them to source directory and include them. `(import (foo bar))` attempts to load ./foo/bar.scm, which should have (define-library (foo bar) ...)

Q: The error messages suck.: True. Current best practice in Owl programs is not to make errors.

Q: Why is it not called a Scheme?: I don't want people filing issues about set-car! not working.

Q: Is this the last question?: No, that one was already asked some years ago.

#project #owl #post