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. As an addendum a standalone peephole optimizer can be applied to the assembly output of Schimper to squeeze out faster execution times. The program is peep.c.
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.
Rick Miskowski. I am at: 55portal55 "AT" gmail "DOT" com
My twitter handle is @fossadvocate
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.
A couple of optionally applications can be built and run.
First, a 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
Second. a tester of the double floating point intrinsics can be built and run. It is a double float reader (strtod) and double writer (write_float). The output from write_float is limited to 9 digits of precision. This test starts with a program which generates some textual double float numbers which are fed to read-print-double.c. To run the test execute test-intrinsics.sh
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
All of the software for the Seqwint Project is governed by the GPLv3 License
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
Oct 2021
Use the tst opcode in schimper code generation for 68k
Add a peephole optimizer step for the compilation process
Use more free registers for aarch64, x86 64 and riscv. Updates to schimper.scm
The use of the jal and jalr instructions for C switch statements for risc-v has been flawed for a couple releases. Revert back to the way it was done (correctly) in the intial release of risc-v
Speed up schimper compilation significantly. Branch optimization code was inefficient timewise
Jun 2022
Simplify risc-v io_buf
Optimize risc-v relop. set true/false to direct relop branches
Nov 2022
schimper - reduce dependence on target-global. Pass target as argument
Feb 2023
Move the schant scheme truncate floor ceiling and round primitives to
library functions. Add an iteration limiting hook to the sqrt function
May 2023
Developed a set of double floating point assembly intriniscs that get added
automatically to the run time during the build process. These intrinsics
are testable with test-intrinsics.sh
Nov 2023
For x86 push the x86 %r11 register before calls to malloc and putchar
May 2024
Rewrite elementary function scheme code. make the functions explict in the files math8.scm and math12.scm
seqwint-1806.tar.gz
(first release June 2018)
seqwint-1906.tar.gz
(release June 2019)
seqwint-2106.tar.gz
(release June 2021)
seqwint-2110.tar.gz
(release October 2021)
seqwint-2406.tar.gz
(release June 2024)
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
Peephole optimization
Ray tracing:
Axis-aligned minimum bounding box
Octree