owl-lisp/owl

A functional Scheme for world domination.

Owl Lisp has moved

The project now lives at https://gitlab.com/owl-lisp/owl

owl's Issues

emscripten / webassembly support

Owl can be built with emscripten, but I/O does not appear to work out of the box.
$ node ol.js -e '(sha256 "trololo")'
Calling stub instead of sigaction()
Calling stub instead of sigaction()
5dd094a5833aba8917bfc7c105eea329143630925f47146bf520c323fbbda1b8
$ node ol.js
Calling stub instead of sigaction()
Calling stub instead of sigaction()
You see a prompt.
[hangs]

Foreign pointers and objects

Directory streams were hacked in as raw pointers, which are made to look like immediates by flipping one of the low bits quaranteed to be zero. These should be represented instead as raw objects, which also carry information about the type of pointer they are carrying.

fork should be thread

System calls are generally named after their C counterparts. It is likely confusing, that fork means starting a new green thread instead of forking a process.

It would probably make sense to rename thread creation to thread, and possibly have it be a macro that automatically wraps a function call argument to a thunk while at it.

Consider getting rid of the bind instruction

Tuples are used to hold several values together. Values can be indexed by offsets, but more often than not there are a known numbers of values along with a type tag for use as tagged unions (or sum types).

The bind primop is used to load values of a tuple into registers, or in other words, to call a function with the contents of a tuple. There is a more and a less obvious way to get rid of this primop:

1. Allow apply to take tuples as arguments in addition to lists, so that (bind tuple func) = (apply func tuple)
2. The λ-calculus definition of e.g. 2-tuples is typically λabc.(cab), in which case car can be defined as λt.(t λab.a). Along these lines, one could define tuples also in Owl as (define ((triple a b c) s) (s a b c)). For such tuples, it would be the case that (bind tuple func) = (tuple func) as such. Would this be a reasonable semantic interpretation for calling a tuple?

with child processes, fix toggle_blocking(x, 1) on stdio

The problem here is, that the file status flags are specific to a file descriptor, which is shared between a parent and a child process after fork(). So removing O_NONBLOCK in the child (as the VM currently does on stdin/stdout/stderr before exec() and exit()), propagates back to the parent, so that the I/O there does not any longer work as expected.

The toggling at exit() time is probably not required, as it should not propagate back to the parent across exec() boundaries (i.e. to the process that started Owl – but I need to verify this on different operating systems). But for the exec() case I currently see no easy (portable) solution.

Parsing functions should work better with lazy lists

Parsing functions fail with position and reason. They should also fail with a non-lazy reconstructed version of the data, because a lazy byte stream may be coming from a non-seekable data source.

Also, there is still room for improvement in parser error messages.

C interop

From what I can tell looking at the C code you have a hardcoded list of interop calls. I'm wondering how could I call other C functions? I'm playing with the idea of creating some libraries to get a good shell-like scripting environment, mostly for filesystem operations and probably scsh-like process notation. From first glance I see I'd be missing some C calls, e.g. execvp or setenv.

Thoughts? :)

improve immediate loading efficiency

There already is a two-byte instruction for loading 0 '() #t #f. But measuring shows that 1 is more often needed than #t – by factor 2.9 on jumps and 2.6 on loads (with loads, even more often than 0).

At the same time, the existing three-byte instruction for loading fixnums does not use the available bit space efficiently. With the opcode byte and one constant argument, we have ten bits available. One for the sign, and nine for the number itself. Having 0 and 1 as a short instruction, we could use this to load the integers { -512, ..., -1, 2, ..., 513 }.

C library mode

something like:

int foobar(int foo) {
  static word *state;
  if (!state) 
    state = boot_owl(heap);
  return owl_unfix(owl_call(state, owl_fixnum(foo), &state);
}

Look into Github alternatives

Apparently Microsoft is about to buy Github.

Undefined values when building on NetBSD

ENOTRECOVERABLE
EOWNERDEAD
CLOCK_PROCESS_CPUTIME_ID
CLOCK_THREAD_CPUTIME_ID

change CFLAGS= to CFLAGS?=

set CFLAGS only if not specified on make invocation

let-syntax is missing

It was removed at some point and hasn't been added back

Stream parsers should be able to resume on errors

It should suffice to pass the parser and input state to the failure function / continuation.

Repl syntax error handling

New stream parser works well in repl, but the temporary error handling is rather unforgiving :)

$ ol
You see a prompt.
> #a
bye bye _o/~
$

restructure vm bootup

something like:
vm -> owl_apply(progptr, arg)
main() -> decode_fixnum(owl_apply(decode_heap(builtin-heap/file), encode_stringlist(args, nargs))

macro expander error message

Macro expander should add the term being expanded to error message when expansion fails. Otherwise one can't see e.g. in libraries which definition triggers the error.

$ ol -e '(define-library (owl bar) (import (owl base)) (export foo) (begin (define foo ->)))'
An error occurred while evaluating: (define-library (owl bar) (import (owl base)) (export foo) (begin (define foo ->)))
Library (owl bar) failed:
Macro expansion failed:
Macro being used as a value: ->

Remove unused instructions from the VM

Remove at next fasl update / minor release.

Small speedup, maybe.

Hello,

Maybe this will be interesting for you:
I have made some tests and found that in case of splitting the "25" virtual machine command (that in fact contains two commands - 25 and 89) into completely separated ones, the whole runtime speeds up approx. 5%.

This command(s) use a lot (~18% of common application time) and cpu's branch predictor does not work fine for most cases.

Numbers are not disjoint from characters.

Sooner or later they have to be, so keeping track of this in a bug.

do the errno handling on Owl side

• add the errno POSIX constants
• simplify the C system primitives where possible

arity error fail

$ bin/vm fasl/bootp.fasl -e '(map 1)'
An error occurred while evaluating: (map 1)
arity error # arguments (1) or return arity error where first is function
$ bin/vm fasl/ol.fasl -e '(map 1)'
An error occurred while evaluating: (map 1)
arity error # arguments (1) or return arity error where first is function
$ bin/ol -e '(map 1)'
crickets

Broke when the error report was changed?

Quantified builds

Some speed and size tests should be done automatically to track performance. Early on this was done locally using a set of scripts at bench/.

consider using dotted lists with bignum arithmetic

In a dotted (improper) list, cdr would be either of type-fix or of type-int – like the root. That way, creation and calculation could be simplified, and it would save three words on the heap for every bignum.

This would probably require the introduction of a new type. Would be good, if signedness could be checked for type-fix and type-int in the same way, e. g. via (eq? (fxband (type number) 32) 32).

…or maybe it would be sufficient to have just one type-int (and the root node decides about the signedness: via type-fix+ or type-fix-.

there is no partial evaluation

Primitive inlining hacks and macro optimizations in defmac should really be handled via partial evaluation instead.

Signal handling

It would be nice to be able to handle signals from lisp side. The signal handled could for example collect a mask of all received signals, and there could be a primop which gets the signals and clears the mask, or this could be added to poll/select.

Macro environments and libraries

Hygienic macros were added before libraries, so they don't expect definitions to disappear from underneath in the environment. It was convenient to allow macros to refer to future definitions this way, but the right thing to do would probably be to capture the current environment to the transformer.

> (define-library (my foo) (import (owl defmac)) (export foo) (begin (define x 42) (define-syntax foo (syntax-rules () ((foo) x)))))
;; Library (my foo) added
> (import (my foo))
;; Imported (my foo)
> (foo)
What is 'x'?

Test error on Mac OS X

Mac OS X Yosemite (10.10.3)

clang --version
Apple LLVM version 6.1.0 (clang-602.0.53) (based on LLVM 3.6.0svn)
Target: x86_64-apple-darwin14.3.0
Thread model: posix

make

# make a vm without a bundled heap
echo "unsigned char *heap = 0;" > c/vm.c
cat c/ovm.c >> c/vm.c
cc -Wall -O2 -o bin/vm c/vm.c
# start bootstrapping with the bundled init.fasl image
cp fasl/init.fasl fasl/boot.fasl
# selfcompile boot.fasl until a fixed point is reached
bin/vm fasl/boot.fasl --run owl/ol.scm -s none -o fasl/bootp.fasl
;; Defined *interactive*
> ;; Defined *include-dirs*
> ;; Defined *owl-names*
> ;; Library (owl syscall) added
> ;; Imported (owl syscall)
> ;; Imported (owl primop)
> ;; Defined *loaded*
> ;; Defined *owl-version*
> ;; Defined exit-seccomp-failed
> ;; Defined max-object-size
> ;; Defined owl-ohai
> ;; Defined owl-ohai-seccomp
> ;; Library (owl boolean) added
> ;; Imported (owl boolean)
> ;; Library (owl list) added
> ;; Imported (owl list)
> ;; Library (owl ff) added
> ;; Imported (owl ff)
> ;; Library (owl iff) added
> ;; Imported (only (owl iff))
> ;; Library (owl math) added
> ;; Imported (owl math)
> ;; Library (owl list-extra) added
> ;; Imported (owl list-extra)
> ;; Library (owl sort) added
> ;; Imported (owl sort)
> ;; Library (owl math-extra) added
> ;; Imported (owl math-extra)
> ;; Library (owl lazy) added
> ;; Imported (owl lazy)
> ;; Library (owl unicode) added
> ;; Imported (only (owl unicode) encode-point)
> ;; Library (owl string) added
> ;; Imported (owl string)
> ;; Defined fopen
> ;; Library (owl vector) added
> ;; Imported (owl vector)
> ;; Library (owl symbol) added
> ;; Imported (owl symbol)
> ;; Library (owl tuple) added
> ;; Imported (owl tuple)
> ;; Library (owl function) added
> ;; Imported (owl function)
> ;; Library (owl equal) added
> ;; Imported (owl equal)
> ;; Library (owl rlist) added
> ;; Imported (owl rlist)
> ;; Library (owl eof) added
> ;; Library (owl render) added
> ;; Imported (owl render)
> ;; Library (owl queue) added
> ;; Imported (only (owl queue))
> ;; Library (owl intern) added
> ;; Imported (owl intern)
> ;; Imported (owl eof)
> ;; Imported (owl io)
> ;; Library (owl parse) added
> ;; Imported (owl parse)
> ;; Library (owl regex) added
> ;; Imported (owl regex)
> ;; Library (owl sexp) added
> ;; Imported (owl sexp)
> ;; Defined ok?
> ;; Defined ok
> ;; Defined fail
> ;; Library (scheme cxr) added
> ;; Imported (scheme cxr)
> ;; Library (scheme base) added
> ;; Imported (scheme base)
> ;; Library (scheme case-lambda) added
> ;; Imported (scheme case-lambda)
> ;; Library (owl env) added
> ;; Imported (owl env)
> ;; Library (owl gensym) added
> ;; Imported (owl gensym)
> ;; Library (owl bisect) added
> ;; Imported (owl bisect)
> ;; Defined verbose-vm-error
> ;; Defined prim-opcodes
> ;; Defined opcode->wrapper
> ;; Defined primop-of
> ;; Defined primitive?
> ;; Library (owl macro) added
> ;; Imported (owl macro)
> ;; Library (owl ast) added
> ;; Imported (owl ast)
> ;; Library (owl fixedpoint) added
> ;; Imported (owl fixedpoint)
> ;; Library (owl cps) added
> ;; Imported (owl cps)
> ;; Library (owl alpha) added
> ;; Imported (owl alpha)
> ;; Defined small-value?
> ;; Library (owl thread) added
> ;; Imported (owl thread)
> ;; Library (owl assemble) added
> ;; Imported (owl assemble)
> ;; Library (owl closure) added
> ;; Imported (owl closure)
> ;; Library (owl compile) added
> ;; Imported (owl compile)
> ;; Library (owl suffix) added
> ;; Imported (owl suffix)
> ;; Defined error-tag
> ;; Defined error?
> ;; Library (owl time) added
> ;; Imported (owl time)
> ;; Defined sleep
> ;; Defined input-chunk-size
> ;; Defined output-chunk-size
> ;; Defined file-in
> ;; Defined file-out
> ;; Defined read-file
> 'share-bindings
> ;; Defined share-modules
> ;; Library (owl random) added
> ;; Imported (owl random)
> ;; Defined blocksize
> #<function>
> ;; Imported (owl random)
> ;; Library (owl args) added
> ;; Imported (owl args)
> ;; Library (owl cgen) added
> ;; Imported (owl cgen)
> ;; Library (owl dump) added
> ;; Imported (only (owl dump) make-compiler dump-fasl load-fasl)
> ;; Defined compiler
> ;; Defined suspend
> ;; Library (owl checksum) added
> ;; Imported (owl checksum)
> ;; Library (owl sys) added
> ;; Imported (owl sys)
> ;; Defined ensure-free-heap-space
> ;; Defined seccomp
> ;; Library (owl char) added
> ;; Defined profile
> ;; Defined *features*
> ;; Library (owl eval) added
> ;; Imported (owl eval)
> ;; Library (owl base) added
> ;; Imported (owl base)
> ;; Defined *libraries*
> ;; Defined shared-misc
> ;; Defined shared-bindings
> ;; Defined initial-environment-sans-macros
> ;; Defined initial-environment
> ;; Defined command-line-rules
> ;; Defined brief-usage-text
> ;; Defined error-usage-text
> ;; Defined strip-zeros
> ;; Defined memory-limit-ok?
> ;; Defined maybe-set-memory-limit
> ;; Defined c-source-name
> ;; Defined try
> ;; Defined owl-run
> ;; Defined about-owl
> ;; Library (owl usuals) added
> ;; Imported (owl usuals)
> ;; Defined repl-compile
> ;; Defined try-load-state
> ;; Defined try-repl-string
> ;; Defined try-test-string
> ;; Defined greeting
> ;; Defined repl-start
> ;; Defined directory-of
> ;; Defined heap-entry
> ;; Defined command-line-rules
> ;; Defined choose-natives
> Code loaded at 21943ms.
#true
> #<function>
> Output written at 36264ms.
ls -la fasl/bootp.fasl
-rw-------  1 vito  staff  561212 Jun 21 17:45 fasl/bootp.fasl
# check that the new image passes tests
CC=cc tests/run all bin/vm fasl/bootp.fasl
-n Running tests/ against bin/vm fasl/bootp.fasl:
 o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o oERROR: tests/no-threads.sh
ERROR: tests/cout.sh
2a3,6
> tmp/bare-13415.c:1617:8: warning: comparison of array 'heap' equal to a null pointer is always false [-Wtautological-pointer-compare]
>    if (heap == NULL) { /* if no preloaded heap, try to load it from first arg */
>        ^~~~    ~~~~
> 1 warning generated.
ERROR: tests/no-threads.sh
0a1,8
> tmp/foo-C1-13274.c:2551:8: warning: comparison of array 'heap' equal to a null pointer is always false [-Wtautological-pointer-compare]
>    if (heap == NULL) { /* if no preloaded heap, try to load it from first arg */
>        ^~~~    ~~~~
> 1 warning generated.
> tmp/foo-C1-13274.c:2551:8: warning: comparison of array 'heap' equal to a null pointer is always false [-Wtautological-pointer-compare]
>    if (heap == NULL) { /* if no preloaded heap, try to load it from first arg */
>        ^~~~    ~~~~
> 1 warning generated.
ERROR: tests/cout.sh
make: *** [fasl/ol.fasl] Error 1

eq? wrapper function has deprecated bytecode

$ ol -e '(cast eq? (type (vector)))'

(3 54 4 5 6 24 6)

clean-up the VM after the fasl 0.1.17 release

Some opcodes/functions will be unused then.

Make fails

I've downloaded the version 0.1.7 and tried to buld owl-lisp.

When running:

# make

I get the following error:

# selfcompile boot.fasl until a fixed point is reached
bin/vm fasl/boot.fasl --run owl/ol.scm -s none -o fasl/bootp.fasl
;; Defined *interactive*
> ;; Defined *include-dirs*
> ;; Defined *owl-names*
> ;; Library (owl syscall) added
> ;; Imported (owl syscall)
> ;; Imported (owl primop)
> ;; Defined *loaded*
> ;; Defined *owl-version*
> ;; Defined exit-seccomp-failed
> ;; Defined max-object-size
> ;; Defined owl-ohai
> ;; Defined owl-ohai-seccomp
> ;; Library (owl unsupported) added
> ;; Library (owl boolean) added
> ;; Imported (owl boolean)
> ;; Library (owl list) added
> ;; Imported (owl list)
> ;; Library (owl ff) added
> ;; Imported (owl ff)
> ;; Library (owl iff) added
> ;; Imported (only (owl iff))
> ;; Library (owl math) added
> ;; Imported (owl math)
> ;; Library (owl list-extra) added
> ;; Imported (owl list-extra)
> ;; Library (owl sort) added
> ;; Imported (owl sort)
> ;; Library (owl math-extra) added
> ;; Imported (owl math-extra)
> ;; Library (owl lazy) added
> ;; Imported (owl lazy)
> ;; Library (owl unicode) added
> ;; Imported (only (owl unicode) encode-point)
> ;; Library (owl string) added
> ;; Imported (owl string)
> ;; Defined number->string
> ;; Defined fopen
> ;; Library (owl vector) added
> ;; Imported (owl vector)
> ;; Library (owl symbol) added
> ;; Imported (owl symbol)
> ;; Library (owl tuple) added
> ;; Imported (owl tuple)
> ;; Library (owl function) added
> ;; Imported (owl function)
> ;; Library (owl equal) added
> ;; Imported (owl equal)
> ;; Library (owl rlist) added
> ;; Imported (owl rlist)
> ;; Library (owl eof) added
> ;; Library (owl render) added
> ;; Imported (owl render)
> ;; Library (owl queue) added
> ;; Imported (only (owl queue))
> ;; Library (owl intern) added
> ;; Imported (owl intern)
> ;; Imported (owl eof)
> ;; Imported (owl io)
> ;; Library (owl parse) added
> ;; Imported (owl parse)
> ;; Library (owl regex) added
> ;; Imported (owl regex)
> ;; Library (owl sexp) added
> ;; Imported (owl sexp)
> ;; Defined ok?
> ;; Defined ok
> ;; Defined fail
> ;; Library (scheme misc) added
> ;; Imported (scheme misc)
> ;; Library (owl env) added
> ;; Imported (owl env)
> ;; Library (owl gensym) added
> ;; Imported (owl gensym)
> ;; Library (owl bisect) added
> ;; Imported (owl bisect)
> ;; Defined verbose-vm-error
> ;; Defined prim-opcodes
> ;; Defined opcode->wrapper
> ;; Defined primop-of
> ;; Defined primitive?
> ;; Library (owl macro) added
> ;; Imported (owl macro)
> ;; Library (owl ast) added
> ;; Imported (owl ast)
> ;; Library (owl fixedpoint) added
> ;; Imported (owl fixedpoint)
> ;; Library (owl cps) added
> ;; Imported (owl cps)
> ;; Library (owl alpha) added
> ;; Imported (owl alpha)
> ;; Defined small-value?
> ;; Library (owl thread) added
> ;; Imported (owl thread)
> ;; Library (owl assemble) added
> ;; Imported (owl assemble)
> ;; Library (owl closure) added
> ;; Imported (owl closure)
> ;; Library (owl compile) added
> ;; Imported (owl compile)
> ;; Library (owl suffix) added
> ;; Imported (owl suffix)
> ;; Defined error-tag
> ;; Defined error?
> ;; Library (owl time) added
> ;; Imported (owl time)
> ;; Defined sleep
> ;; Defined input-chunk-size
> ;; Defined output-chunk-size
> ;; Defined file-in
> ;; Defined file-out
> ;; Defined read-file
> 'share-bindings
> ;; Defined share-modules
> ;; Library (owl random) added
> ;; Imported (owl random)
> ;; Defined blocksize
> #<function>
> ;; Imported (owl random)
> ;; Library (owl args) added
> ;; Imported (owl args)
> ;; Library (owl cgen) added
> ;; Imported (owl cgen)
> ;; Library (owl dump) added
> ;; Imported (only (owl dump) make-compiler dump-fasl load-fasl)
> ;; Defined compiler
> ;; Defined suspend
> ;; Library (owl checksum) added
> ;; Imported (owl checksum)
> ;; Library (owl sys) added
> ;; Imported (owl sys)
> ;; Defined ensure-free-heap-space
> ;; Defined seccomp
> ;; Library (owl char) added
> ;; Defined profile
> ;; Defined *features*
> ;; Library (owl eval) added
> ;; Imported (owl eval)
> ;; Library (owl base) added
> ;; Imported (owl base)
> ;; Defined *libraries*
> ;; Defined shared-misc
> ;; Defined shared-bindings
> ;; Defined initial-environment-sans-macros
> ;; Defined initial-environment
> ;; Defined command-line-rules
> ;; Defined brief-usage-text
> ;; Defined error-usage-text
> ;; Defined strip-zeros
> ;; Defined memory-limit-ok?
> ;; Defined maybe-set-memory-limit
> ;; Defined c-source-name
> ;; Defined try
> ;; Defined owl-run
> ;; Defined about-owl
> ;; Library (owl usuals) added
> ;; Imported (owl usuals)
> ;; Defined repl-compile
> ;; Defined try-load-state
> ;; Defined try-repl-string
> ;; Defined try-test-string
> ;; Defined greeting
> ;; Defined repl-start
> ;; Defined directory-of
> ;; Defined heap-entry
> ;; Defined command-line-rules
> ;; Defined choose-natives
> Code loaded at 8496ms.
#true
> #<function>
> Output written at 13987ms.
ls -la fasl/bootp.fasl
-rw------- 1 root root 547408 Sep 18 16:16 fasl/bootp.fasl
# check that the new image passes tests
tests/run all bin/vm fasl/bootp.fasl
Running tests/ against bin/vm fasl/bootp.fasl: o o o o o o o o o o o o o o o o/bin/echo: write error: Resource temporarily unavailable
 o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o oERROR: tests/hashbang.sh
1d0
< ohai
ERROR: tests/hashbang.sh
Makefile:28: recipe for target 'fasl/ol.fasl' failed
make: *** [fasl/ol.fasl] Error 1

Add UDP primops

increase data density on the heap

Currently, with a 64-bit VM, each immediate wastes four bytes (the 32 upper bits) on the heap. This could be improved in two ways:

1. Introduce flexible-width fixnums
   Immediates would be able to carry a value being word_size - 8 bits wide (with the current format). With this in place, big-num calculations could be faster, and take less memory on 64-bit systems.

2. Store offsets instead of absolute pointers (and use 32-bit words)
   Read and write each pointer through a macro, which optionally converts it to an offset (depending on the VM configuration). On the one hand this would add some overhead, but on the other hand offsets help the garbage collector when realloc() moves the memory. (And on x86_64 the binary size could be reduced a bit, when using more 32-bit instructions.) Offsets should be calculated from a fixed point (probably the start of the heap), so that eq? still works.

Whether the VM uses 32-bit or native-width words should be a compile time (or even run-time?) option, to serve different use cases. The same Owl byte-code should run on all VM variants.

Repl eval errors

After simplifying repl thunk evaluation mechanism, user thrown errors are no longer differentiated from crashes that would occur in the compiler. Should be easy to fix.

$ ol
You see a prompt.
> (error "n" "o")
error: no

compiler bug
>

(owl eof)

Libraries should be able to get a reference to eof-object without having to know about the implementation related libraries. There should therefore be an (owl eof) library which exports eof-object? and eof-object.

(owl boolean) and boolean? is a good example for this.

Decide where to keep definition metadata

Related to #59: Environments are mappings from names to values. Partial evaluation and metadata in general needs a mapping from values to their metadata.

This metadata store should be used at least for function names and possibly source for inlining and partial evaluation purposes.

Less registers

The main reason for currently rather high register count is the ancient register allocator. It should be upgraded and register count dropped to around 32.