Scheme language Eked Quickly With INTegers (SEQWINT Project)

The Seqwint project is a collection of compilers and interpreters used to generate a scheme compiler called schant. The project is a "scheme from scratch". The process builds schant to a native target starting from a tiny virtual machine compiled down to assembly language. x86, arm, riscv and 680x0 targets are supported running on either 32 bit or 64 bit processors. The implementation uses data types no more complex than 32 bit signed integers and 32 bit integer arrays.

The process begins with the simpvir virtual machine interpreter. From that we derive a C subset compiler called shmall and a Scheme program called Schimper (SCHeme IMPERative). Finally a mostly R4RS compliant scheme compiler (implemented as a virtual machine written in C) called schant is derived.

A build of seqwint requires a *nix environment but does not require the use of a preexisting C compiler although any seqwint C source code can be compiled with any existing K&R compliant C compiler e.g. like gcc or tcc. Tools required for the build are the 'as' assembler, ld and sh/bash with its standard commands. For some OS / target combinations, in place of ld, gcc is required in which case system calls make direct use of calls to the C library functions getchar, putchar, fflush and exit. In all other cases direct kernel system calls are made without reference to any libraries.

The simpvir virtual machine is implemented in C. The target assembly language translation (pre-assembled) is provided as the starting point of the build process. Because of its simplicity simpvir could easily be implemented in any host language. All aspects of the build process could be based on the sole existence of simpvir if desired.

Author

Rick Miskowski. I am at: 55portal55 "AT" gmail "DOT" com

My twitter handle is @fossadvocate

Usage

To build the binaries in the bin directory and run validation tests run ./build.sh. For simple "hello world" examples with comments on how to use the compilation tools inspect and run ./quick-start.sh. Executables produced in the bin directory are: simpvir, schant-int, schant-bigfloat8 and schant-bigfloat12. Existing executables in the bin directory are recreated to prove the build process is self reproducing. These executables are: schant-compiler.txt, schant-int.vm.txt, schimper.txt, shmall.txt and simpvir-assembler.txt.

An optionally runable ray tracer application can be built and run which gives the floating point version of schant in schant-bigfloat8 a workout. It can be executed in the test-renderer directory. Run build-and-run-renderer.sh. More information about this project and it's web manifestation can be found at JSRender3D

Tested OS / Machine


                              a  r
                  x     a  a  a  i
                  8  a  r  r  r  s  6
            i  i  6  m  m  m  c  c  8
            5  6  _  d  v  v  h  v  0
            8  8  6  6  6  7  6  6  x
            6  6  4  4  l  l  4  4  0

Cygwin      .  Y  .  .  -  -  -  -  -
FreeBSD     .  .  .  Y  .  .  .  .  .
OpenBSD     Y  Y  .  Y  .  .  .  .  .
NetBSD      .  .  .  .  Y  .  .  .  .
Darwin      .  Y  Y  .  -  -  -  -  -
GNU/Linux   Y  Y  Y  .  Y  Y  Y  Y  -
Bare Metal  .  .  .  .  .  .  .  Y  Y

License

All of the software for the Seqwint Project is governed by the GPLv3 License

Source Code

Site Map

History

Jun 2018
Initial release

Jun 2019
Eliminate need for the m4 macro preprocessor tool. The build process is a lot slower than in the previous release, however the resulting executables are of comparable size and speed. Instead the new Schimper tool optimizes expressions, inlines simple functions and optimizes branching code. Speedup cos and sin functions.

May 2020
Schant opcodes are no longer symbols during execution. They are integers, speed up of 1%.
Schant - remove "while (processing)". Use "while (1)", speed up of 5%.
Schant - replace analyze_stack with analyze_trace. On execution failure report failing function name.
The Shmall C compiler has been recoded in Scheme. Simpler code. Fewer contingencies.
The write-string simpvir opcode has been deprecated. Shmall now generates putchar calls from C strings.
For the x86 target the nasm assembler is no longer used. The as assembler is now used as it is for all other targets.
The amd64 version of OpenBSD is supported.
The armv6 version of NetBSD is supported.
The Motorola 680x0 target has been added. Successfully tested as a bare metal OS using the Musashi emulator.
The 64 bit arm (aarch64) target has been added. Tested on GNU/Linux so far.

May 2021
C forward function declarations are ignored now by schimper
No longer need to strip them out with tac and sed in the script
A new version of multiply_biginteger for 8 digit precision schant-bigfloat8
The renderer demo runs about 20% faster
Support integers of the form #bn and #xn for binary and hexadecimal formats
A new version of multiply_biginteger this time for 12 digit precision for schant-bigfloat12
Bigfloat real numbers are now compressed a digit occupies 4 bits rather than a 32 bit word
Implemented symbol-hash from R6RS as an extension. This allows the ability to implement more time efficient hash tables in scheme
Improve code generation from schimper for riscv target

Downloads

seqwint-1806.tar.gz (first release June 2018)
seqwint-1906.tar.gz (release June 2019)
seqwint-2006.tar.gz (release June 2020)
seqwint-2106.tar.gz (release June 2021)

Bibliography

Peter Henderson. Functional Programming Application and Implementation. 1980

Kernighan, Ritchie. The C Programming Language 1988

Clinger, Rees et al. Revised(4) Report on the Algorithmic Language Scheme 1991

Peter Norvig. Paradigms of Artificial Intellegence Programming 1991

Abelson, Sussman. Structure and Interpretation of Computer Programs 1996

Shirley, Morley. Realistic Ray Tracing. 2003

www.wikipedia.org topics:
Binary trees
Hash table
Open addressing
Lexical analysis
String interning
Recursive descent parser
Shunting yard algorithm
Tracing garbage collection
Virtual machine
Ray tracing:
Axis-aligned minimum bounding box
Octree