Introduction
Small is a simple programming language that can be implemented by a full bootstrap. I created Small while I was a graduate student at the University of Washington. Beyond being highly portable, Small has modest goals. It is a language intended to be useful for systems and application programming; it has a single integer type determined by the architecture of the host system; it supports structured programming with arithmetic and conditional statements and expressions, repetition statements, functions and procedures with parameters and recursion, and can be compiled to assembly language or interpreted. It is Turing Complete. It has enough convenient features to be practical. It is extensible by being relatively easy to add statement forms, features, and types.
A "full bootstrap" means it is possible to implement Small on a new system with a minimum of existing support software that includes an assembler and linking loader. The bootstrap process is based on macro processors. The first stage uses simcmp, a simple text processing algorithm that can be written, or translated by hand, into any available programming language or assembly language; then that is used to translate the source code for Stage 2 into any available language or assembly code. Next, this complete working version of Stage 2, with far more capable features than simcmp, is used to translate the Stage 2 source to assembly language with a number of optimizations applied to make Stage 2 an efficient, capable, general purpose macro processor. These portable software tools, simcmp and Stage 2 are components of MPS, the mobile programming system created by Professor Emeritus William Waite of the University of Colorado in the late sixties.
Small is built using Stage 2 as its bootstrap compiler. My Master of Science thesis, Small: A Contribution to the Mobile Programming System, is reproduced in the small repository as a reference manual.
Stage 2 is used in this presentation as a two pass compiler. The first pass uses a set of macros from my thesis to translate source code in Small to Mill, a machine independent low level language described in the thesis. Then Stage 2 is used with another set of macros to translate Mill to assembly language, in this case 32-bit x86 instructions for the yasm assembler. Thus with the implementation of Stage 2 presented here, and the Small to Mill translation macros, the only thing required to construct a new compiler is the set of macros to translate Mill to yet another assembly language. The example implementation serves to show how that can be accomplished. It is also possible to combine macros into a single set to make a one pass compiler. However I chose to present the two pass process for the sake of clarity.
The Repositories
Each repository contains a README.txt file that describes the contents and how it can be used and what is needed. A makefile also shows how to build components. The LICENSE is the general public license, GPLv2, and applies to all files created by me and that contain my name or initials CRB. The GPL license means this is free, open source software and documentation. You are free to use, copy, and modify, asking only that you give back under the same terms. If in doubt, read the LICENSE. Prof. Waite's original work is NOT covered by this license.
Use the blue button "View on GitHub" at the top of the page to go to the repository pages. The examples here are for use on x86 Linux systems. Some ports to ARMv6 for Raspberry Pi are in subdirectories called rpi,
simcomp
The Simple Compiler is a simple text substitution macro processor implemented here as a stand-alone C program based on the SIMCMP Fortran program of the MPS transcribed to C. The compiled executable is immediately usable on 32- and 64-bit Linux systems. The simcmp executable is used to create a first working version of the Stage 2 macro processor. There is also a subdirectory containing a port to ARMv6 for the Raspberry Pi.
stage2-1
This repository contains simcmp macros to translate the Stage 2 source code to 32-bit x86 assembly language for the yasm assembler. The source code for Stage 2 is made available here by permission from Professor Waite. Again, the stage2 executable is immediately usable.
stage2-2
This repository contains the Stage 2 macros to translate the Stage 2 source code to x86 assembly language with many simple optimizations applied. The compiled executable, stg2, should be copied to your /usr/local/bin or wherever you keep local executables for further use. The optimized executable is smaller and faster than the stage2-1 implementation.
small
This repository presents the simple mobile algorithmic language using Stage 2 as its compiler. The first pass uses the macros small.s2m to translate Small source code to Mill, a machine independent low level language. The second pass translates Mill to 32-bit x86 assembly language for the yasm assembler. A reproduction of my 1982 masters thesis serves as a reference manual for Small and Mill. Several example programs and tests are included in subdirectories along with makefiles. This is a work in progress and more examples will be forthcoming.
grandios
This repository contains a fully expanded I/O system written in C modeled on the F4IO Fortran I/O module in the MPS. The grandios I/O module is required for both Stage 2 implementations and is also currently used for Small programs. Up to nine channels can be attached to files using positional parameters on the command line. In addition channels 1, 3, and 4 can default to stdin, stdout, and stderr respectively. Also channel 1 has been modified to revert to stdin when an input file reaches end-of-file. A smaller version to be called Demios targeted for Small programs is under construction.
hexdmp
This repository contains a C program to dump the contents of a file in hexadecimal and ASCII.
crandylb.github.io
This repository contains the file index.html that displays this Web page.
Vision
My purpose in making this material available as free, open source software is two-fold. First, it is of historical value to preserve these tools and techniques that trace from the earliest days of the computer era to today, where these are still relevant. Second, I would like to see the material here developed into an introductory course in programming language concepts and techniques that spans the complete arc from concepts to implementation using free software tools students can use to gain hands-on experience. Prerequisite would be the level of computer literacy students have today who have grown up with computers in their home, school, or their own backpacks since infancy. Student projects could be modifying or adding features, types, of other language concepts, or new projects the students create themselves. The result would be a generation of students not afraid to create their own programming tools and languages. The goal would be to bootstrap students from computer users to computer masters where there are no hidden mysteries too advanced to dig into. An additional purpose would be to serve as an introduction to a more advanced course using Eli or other advanced tools.
A Little History
The first three implementations of Small were on the Prime 300, a minicomputer, the Intel 8080, an 8-bit microprocessor, and the Intel 8086, a 16-bit microprocessor and technical ancestor of the modern x86 architecture. It's an interesting story in itself.
I had just started graduate work that led to my master's thesis at UW. I was working for the Atmospheric Sciences Department as a systems programmer, part of a team supporting NASA's Viking Mars landers. I ported Stage 2 to the Prime and used it for several projects in my graduate work. The mid-seventies also coincides with the dawn of the microprocessor revolution that led to the IBM PC and the ubiquitous computers of today. But before the IBM PC existed there were hobbyists who built their own personal computers. I was one of those. I was an active member of the Northwest Computer Club that met at Seattle's Pacific Science Center. My picture from the time can be found at: commons.wikimedia.org/wiki/File:Northwest_Computer_Club_Dec_1977_pg13.jpg (I'm the one with the Marcello Mastroianni glasses.)
I built three S-100 bus PCs in that time period: an IMSAI, a Cromemco, and a large homebrew that used a dual processor CPU board. That last was the machine I used for my graduate work that led to Small and my thesis. To demonstrate the practical use of Small I wrote a text formatter called Small Runoff. It was used to format and print multiple drafts and revisions of my thesis. The output was printed on an IBM Selectric typewriter conntected to the computer through a serial port. The dual processor allowed me the switch between the CP/M and CP/M-86 operating systems that ran on the 8080 and 8086 instruction sets respectively. I also added a 10 megabyte Shugart eight inch hard disk drive to my homebrew that saved a lot of time doing software development work. There is more about Small Runoff in the Conclusion section of my thesis.Small Runoff formatted my thesis text for page layout, left and right justification, pages numbers, and all the rest of the exacting requirements of the UW Graduate School thesis guide. Illustrations were drawn by hand on the master copy pages. In order to show exactly what that looked like I have reproduced the thesis using modern tools: Libre Office, and PDF format. The reproduction uses the same Courier font as the IBM Selectric typewriter, and the illustrations have been scanned from the original and pasted in. It is a reasonably accurate reproduction. Some revisions have been made to the Small macros in the appendix to reflect corrections and additions that have been found necessary since the original publication. Each revision is marked in comments with my initials and date. The thesis reproduction is in the file thesis.pdf in the small repository.
Support or Contact
For up-to-date information about these GitHub repositories see my companion blog at http://crandylb.wordpress.com
Prof. Waite has granted permission to use Stage 2 and the MPS files and declared them to be released to Public Domain. To access his distribution of MPS go to http://ecee.colorado.edu/~waite/pubs/selected.html, scroll down to Portability and click on Source code for STAGE2. This will download a zip file containing the MPS files.
For help with GitHub check out the documentation at http://help.github.com/pages or contact support@github.com and we’ll help you sort it out.