Bruce Ediger's Freely Available Programs

Bruce Ediger

I benefit immensely from code other people give away. Hopefully someone else can benefit from these offerings.

You're welcome to download, examine and use my work any way you feel like, bearing in mind that it might not do what I say it does. I do not guarantee this code works as I say it does, nor do I guarantee that you can even read it.

I run Unix-like operating systems at home, including Linux and (in the past) NetBSD. The programs I write work under those operating systems. If you run anything else, this code may only interest you in an academic sense. I urge you to consider switching to Linux or NetBSD if you run operating system that does not have freely-available source code.

Email me some comments
Return to my home page and read stimulating articles I wrote.


Download Summary

SPARC V8 Assembler for NetBSD NetBSD/sparc 1.1 object file "dumper" NetBSD/sparc 1.1 object file "dumper"
lcc-3.6 ANSI-C compiler for NetBSD/sparc 1.1 HTTP request generator CGI-BIN tester
HTTP 404 server Usenet article parser and disassembler ANSI C name space abuse code
Self-replicating and evolving shell script Self-relocating C function SPARC assembly Hello World program
Mutex locking using SPARC V8 LDSTUB instruction A graphical puzzle called Quinto Spine - programmer's caculator
Self-replicating Python program Object Oriented Self-replicating Python program Self-replicating Python program with alternating generations
Church Numerals in Python Self-replicating Web Page Python tic-tac-toe player
Self-describing string generator in Perl Self-describing string generator in Python Simple Recursive Functions Interpreter v1.0
Combinatory Logic Interpreter with arithmetic combinator bases v1.1 Combinatory Logic Interpreter with strong reduction v1.0 Combinatory Logic Interpreter v1.6
Generalized Combinatory Logic Interpreter v1.2 Ouroboros program with 4 generations, perl, bash, python, PHP Tic tac toe web app, Alpha-beta minimax tic tac toe in PHP
Nine-board distributed Tic Tac Toe. Now obsolete. I can't afford the CPU cycles anymore. Lambda Calculus Interpreter Modern Userland Exec - x86, 32 bit
Logic Machines and Monte Carlo Locks from Raymond Smullyan's book, The Lady or The Tiger. AutoMondrian, algorithmic mid-century modern art. File 1, file 2. Nine-board Tic Tac Toe, in JavaScript, plays in your browser.
Self-replicating, PHP quine. Non-recursive, non-minimaxing Tic Tac Toe in C. Linux command line program. Modern Userland Exec - x86_64, 64 bit


My Favorite Awk scripts

My favorite awk scripts, right here, right now! No download necessary, just cut-n-paste!


Formal Systems Interpreters

I have written interpreters for recursive functions, and combinatory logic formal systems. I have also written two variant combinatory logic system interpreters: strong reduction via Cβ algorithm and arithmetical combinator bases. I just added a lambda calculus interpreter.

I have written a "generalized" combinatory logic interpreter. This interpreter allows you to define your own combinators, and to define your own bracket abstraction algorithms.

I have written design documentation for recursive functions and combinatory logic, and an additional combinatory logic usage document. Usage documents for interpreters that do strong reduction and use arithmetical combinator bases also exist.


SPARC V8 Assembler

Source code for an assembler. It runs under the NetBSD/sparc 1.1 operating system. It assembles the "suggested assembly syntax" for SPARC instruction set architecture version 8. I wrote an article describing the assembler. This code may interest you if you think you need a parser and/or lexer for SPARC assembly language. It includes a YACC grammar and flex-based lexer for that language.


Nine-board Tic tac toe

An alpha-beta minimax nine-board tic tac toe player. You play nine-board tic tac toe on a 3-by-3 arrangement of ordinary tic tac toe boards. You must make your move on a board that lies in the board in the 3-by-3 arrangement of boards that corresponds to where the previous 'X' or 'O' got made on that board. The first move can appear on any board.


Tic tac toe web app in PHP

My first effort at a PHP program, an alpha-beta minimax tic tac toe player. Every human's move sends an HTTP POST back to the ttt.php module, which figures out its next move, and gives back HTML with the current board state, plus HTML buttons for the human to choose the next move. This works because tic tac toe has a particularly simple state at any stage of the game.

Try it, but the best you can do is draw.


NetBSD/sparc 1.1 object file "dumper"

Source code for a program to print out the headers, relocation data and symbol table for a NetBSD/sparc 1.1 object file. You could probably get it to work on SunOS 4.1.x object files with only a small amount of work.


SPARC disassembler

Source code for Solaris 2.3, SPARC V8 instruction set architecture disassembler.

This program stars in a technical report by Cristina Cifuentes and Norman Ramsey.

The paper is titled Measuring the Cost of Decoding Machine Instructions in Software - Hand-crafted vs Automatically-generated Decoders.

Cifuentes and Ramsey have this to say about elfdis:

This is a standalone disassembler that implements an ELF loader and a decoder of SPARC machine instructions; it does not handle flow of control or produce an intermediate representation [...] The code is clearly modularized, and 4 different modules ... deal with the decoding of the instructions.


Even though my disassembler is the "before" exhibit in this paper, it comes out a bit faster than Cifuentes & Ramsey's automatically generated disassembler. My disassembler takes 0.000368 seconds to disassemble a SPARC instruction, while theirs takes 0.000389 seconds.

You may find Norman Ramsey's SPARC disassembler more interesting. Ramsey based that disassembler on the NJ Machine code tool kit.

You may also find this SPARC disassembler interesting.

You can find disassemblers for other architectures (mostly Intel x86) at the Disassembler home page.


lcc-3.6 ANSI-C compiler for NetBSD/sparc 1.1

The files neccessary to get lcc version 3.6 running under NetBSD/sparc 1.1. Here's the README file. In addition to NetBSD/sparc 1.1, and this distribution, you'll need lcc-3.6 and Perl. This port is not perfect. It has a few problems.


HTTP request generator

Send an arbitrary HTTP request with the HTTP request generator.

New! Version 2.10 as of 2001-07-09.

I use this HTTP request generator to:

I tried to make this request generator very robust. It makes every effort to generate some output before exiting for every circumstance.

I composed tests specifically to exercise as much of the code as possible: of 227 basic blocks, my tests executed all but 40. I checked memory leaks using dmalloc and memory access using efence.

I've built this program under:

Dave Bodenstab contributed a FreeBSD patch, included in the source.

Related Tools

Jef Poskanzer wrote http_get, a program very similar to my HTTP request generator. Jef Poskanzer also wrote WebCat and WebPost, which do pretty much the same thing, but are written in Java.

WebCopy is a Perl program that can recursively retrieve the contents of any web page and its links.

SWebget "does nothing else but get you a webpage and prints it to stdout"

cURL - a client that groks URLs is said to be a similar program that understands HTTP, FTP and GOPHER protocols. Said to compile under Win32 as well as on most Unixes.

Snarf "is a command line resource grabber. It can transfer files through the http, gopher, finger, and ftp protocols without user interaction."

Greed connects to a web site or FTP site and downloads files for you and supports resuming.

Pagesucker is "a little program which will download a web page from a remote web server, from details you pass through the command line, of in a file, which is a list of webservers, paths and an output file name".

Laurent Demailly has quite a few WWW tools, including a tiny HTTP server and client in Tcl.


CGI-BIN tester

Examine exactly what environment your HTTP server provides to CGI-BIN programs with the CGI tester.

This sh script examines command lines, environment variables, HTTP methods and url-encoded data. It generates HTML that may inform you of the reasons why your CGI-BIN programs work the way they do. I find this script indispensable when working with HTML forms and the CGI-BIN programs that interact with them.

Tested under:

To install:

  1. Copy it to the CGI-BIN directory of your web server.
  2. Make that copy executable: chmod 666 xxx2.cgi
  3. Run it by asking the web server for its URL.
  4. Marvel at the odd information your web server passes to CGI-BIN programs.

You probably don't want to install this program on a web server available to the entire Internet. It gives away a lot of information invaluable not only to the CGI-BIN programmer, but also to system crackers.


HTTP 404 server

Serve File Not Found messages with the HTTP 404 server.

This program understands a very small part of the HTTP protocol (RFC 1945). It uses this knowledge to respond to every incoming HTTP request with the beloved "404 - File Not Found" error message.

This server complements the HTTP request generator above. It lets you view the HTTP request headers generated by browsers or Web Spiders, and record those headers along with the time of the request.

I've compiled and tried this program under:

The 404 Server is not terrifically well-tested on any of the platforms listed above. The distribution lacks any documentation, including only a ".c" file and a makefile. Consider it an alpha release.

Other people's small or limited scope HTTP servers:




Usenet article parser and disassembler

This program reads a file containing concatenated usenet articles. For each usenet article it finds in the input file, it creates a headers file and a body file in separate directories. It puts the headers lines of the article it just found in one file, and the body text of the article in the other file. It names the two files after the "Message-ID:" line found in the that article's header lines.

It has problems with usenet articles that contain unquoted usenet articles. It will incorrectly break the unquoted included article into its own seperate file. I don't think this problem has a solution, though.

I believe that one could modify it to break up "mailbox" files, too. To do this, one would add another header line to the lex specification: the lexer should consider all lines beginning with From as header lines.


ANSI C name space abuse code

ANSI C allows a programmer to use any legal identifier in at least 5 different contexts in the same scope. This program illustrates the use of the identifier list in all those contexts. Works great under Solaris 2.5.1, NetBSD's gcc 2.4.5, 2.7.2.2, SuSE linux's GCC 2.95.3, lcc 4.27 under linux, and finer C compilers everywhere.

Please email me if you find or know of another way to use a particular, legal identifier.


Church Numerals in Python

I read M-J. Dominus' article Perl contains the λ-calculus right as I encountered Python's nested functions. It occurred to me that Python also contains the λ-calculus, in exactly the same way that Perl does, as well as actually having "lambda" to make anonymous functions. So, I wrote a script that proves it. This script creates Church Numerals, a Y-combinator, and an addition function, all without an explicit "lambda:" keyword.

Someone else implemented the same sort of thing. Here's another implementation of Church Numerals in Python. Haldar uses Python's lambda construct, while I took advantage of other Python features.

Matt Might has a blog post on the same topic. He probably makes more sense than me.


Self-replicating and evolving web page

This HTML file, when interpreted by a web browser, opens a new window (or tab, depending on how you have your browser set up) with an "evolved" copy of itself. The interpretation happens under controlled circumstances, when the user clicks a button on the web page. Each "evolved" copy also replicates on a button click. I think this constitutes a mixed JavaScript and HTML quine (another quine page). Y. Kanada has his own self-reproduction of web pages web page. So does Joseph S. Miller. Perhaps you will find one or the other of more interest.


Self-replicating and evolving shell script

This shell script prints an "evolved" version of itself on stdout. Use it like this:

% chmod 555 replicate
% replicate > r2
% chmod 555 r2
% r2 > r3
% diff replicate r2
% diff r2 r3



Self-replicating Python program

This Python program rather imaginatively prints a version of itself on stdout. Use it like this:

$ python ./self_replicating.py > r2.py
$ python ./r2.py > r3.py
$ diff self_replicating.py r2.py
$ diff r2.py r3.py

No differences should appear. This code appears mainly as a Python transliteration of a self-replicating sh script. Not too modern, and not even very difficult. Therefore, I have written a most remarkably improved Object Oriented self-replicating python program.




Object Oriented self-replicating Python program

In a most modern, object oriented way, this Python program prints a version of itself on stdout. Use it like this:

$ python ./objectOrientedSelfReplication.py > r2.py
$ python ./r2.py > r3.py
$ diff objectOrientedSelfReplication.py r2.py
$ diff r2.py r3.py

No differences should appear. This particular program should satisfy even the most pure of object oriented purists' need for a self-replicating program.


Self-replicating Python program that alternates generations

This wee curiosity emulates ferns that have alternation of generations.

$ python ./self_rep_alternating.py > a.py
$ python ./a.py > b.py
$ python ./b.py > c.py
$ cksum self_rep_alternating.py [abc].py

You should see checksums that indicate that files self_rep_alternating.py and b.py have the same contents, and that a.py and c.py have identical contents.

This doesn't truly match the way ferns alternate generations, but it does prove that art can imitate nature.


Self-replicating program that alternates generations between Python and Bash

Perhaps a better curiosity. Written in Python, it outputs a Bash program. When executed, the bash program outputs a replica of the original python program, so on and so forth.

I agree that it cheats a bit, in that Python and Bash look alike for what the two program do, differing mainly in syntax of string concatentation.

You could probably use "sh", "ksh" or "zsh" instead of Bash. You could probably extend this to a three-generation alternation by using a Perl script as the extra generation.

You'd run it something like this, assuming you've save the contents of the link above in a file named 'mrgd':

$ ./mrgd > m1
$ chmod 755 ./m1
$ ./m1 > m2
$ chmod 755 ./m2
$ ./m2 > m3
$ diff mrgd m2
$ diff m1 m3
$ cksum mrgd m?

Checksums of mrgd and m2 should equate, as should checksums of m1 and m3. diff should not report any differences.


Ask and ye shall receive: Self-replicating program that goes through four generations, Python, Bash, Perl, PHP

This took a bit longer to do than I'd thought. Perl and PHP have syntaxes similar to both Python and Bourne-shell-derivatives (bash, ksh, zsh). The Perl (5.x in this case) print statement, and PHP's echo do not put newlines on any output strings, unlike Bash or Python print statements. Getting newlines on the ends of output strings from the Perl and PHP generations gets complicated by the differences in how Python, Bash, Perl and PHP represent a backslash (ASCII 0x5C) literal.

Download, and run from a command line like this:

$ tar xf ouroboros.tar
$ cd ouroboros
$ ./run_replication
Running m1, output to m2
Running m2, output to m3
   ...
Running m12, output to m13

195942699 1782 m1
195942699 1782 m5
195942699 1782 m9
...

The cksum command will show that the run_replication script produced 4 sets (one set for each language in the cycle) of 3 identical scripts.

Ha! I'm late to the game. Apparently these things are called "Ouroboros programs", and someone did one that had 11 generations between exact repeats. Quoting might arise as an important issue with less-modern languages that make a big distinction betwen single- and double-quotes.

Apparently, these related sets of programs are also known as "Quine Relays". Here's one that goes through 50 generations.


Self-replicating PHP program

The structure of this quine interests me:

<?php
$genome='echo chr(60).chr(63).chr(112).chr(104).chr(112).chr(10); echo chr(36)."genome=".chr(39).$genome.chr(39).chr(59).chr(10); echo $genome.chr(10).chr(63).chr(62).chr(10);';
echo chr(60).chr(63).chr(112).chr(104).chr(112).chr(10); echo chr(36)."genome=".chr(39).$genome.chr(39).chr(59).chr(10); echo $genome.chr(10).chr(63).chr(62).chr(10);
?>

That code is very similar to Raymond Smullyan's "norm" or "associate" of a term: program "program". In the Mystery of the Monte Carlo Lock, the McCulloch's Machine self-reproducing term is 323. The '3' is the instruction for "compose the associate of whatever comes back from the next instruction". The '2' is the quote character and the second '3' is the quoted program itself.

PHP needs the programmer to quote the string first, as PHP has variables, and the quine uses one. That make the PHP program more like $x = "program"; $x($x);, but the "norm" of the string $genome is clearly what the program above executes.

You could also read the code as a variation on Quine's paradox. The above code seems like you could read it as "yields self-replication when appended to itself" yields self replication when appended to itself.


Self-relocating C function

This curiosity, written in reasonably strict C, contains a function which relocates itself in memory.

This code started life under SunOS 4.0.3 on a M68020 based Sun 3/260. Since then, I have compiled and run it under quite a few Unix variants (at least SunOS, Solaris, Ultrix, NeXTStep, Irix, NetBSD, Linux). It works on hardware ranging from an M68010, SPARC, Mips R2000, R3000, R4000, and many others. It probably won't work on M68040 or Alpha CPUs without in-line assembly code to flush those CPU's instruction caches.

It definitely won't work on x86_64 Linux, as Linux takes advantage of the hardware to mark the heap as non-executable.

It will probably never work on Hewlett-Packard's ghastly HP-PA CPU because of that architecture's poorly-documented segmentation.


SPARC Assembly Hello World

Amuse yourself with my SPARC assembler language "hello world" program.

This constitutes my efforts at producing the smallest possible "hello world" program. The program prints the phrase "Hello, World!" on stdout, then exits with a zero status.

It assembles and runs under:

The final executable varies between 88 bytes (SunOS and NetBSD) and 364 bytes (Solaris 2.5.1).


Mutex locking using SPARC V8 LDSTUB instruction

An example of how to use the SPARC V8 "ldstub" instruction to implement a mutex lock between two or more processes.

This compiles and runs under Solaris 2.6 on a 2-CPU SPARCStation 10. I think you could easily get it to work on any SPARC V8 machine that runs an OS that supports System V shared memory.


A graphical puzzle called Quinto

Edmund Ronald put out a puzzle called Quinto in 1991. He wrote it in Objective-C for the old NeXTStep GUI. I did a rework of that puzzle, transforming it into Tcl/Tk.

Edmund Ronald's original Readme:

Quinto

Quinto is a game. The board is a 5*5 array of buttons, pressing one toggles its' state and that of its 4 neighbors.

The aim of the game is to highlight all the buttons.

My friend John Horton Conway, who knows some mathematics, took a few hours to solve this back in the early eighties. Other people tend to take slightly longer.

I hid one solution I found (almost certainly not the shortest) as comments in the source code.

I wrote the Tcl/Tk version under Red Hat Linux 5.0 for Alpha, which apparently means Tcl 8.0 and Tk 8.0. I also tested under NetBSD/Sparc 1.1, Tcl 7.6, Tk 4.2., and Solaris/Sparc 2.5.1. I tried it under twm, gwm, dtwm (ugh!) and fvwm-2 window managers. It seems to work the same for all permutations.

You may have to change the path to wish in the first line of the Tcl/Tk program.


Spine - a programmer's calculator

I wrote a small, yacc and lex based programmer's calculator, along the lines of bc, but without variables or flow-of-control. Why do I call it a "programmer's" calculator? It accepts input in hex, octal, decimal or binary, and you can mix up the formats. It has a full set of bitwise operators, including left and right shift, and complement. Its has operator precedence identical to that of the C programming language, so that you can cut-n-paste a tricky expression from a C program into a "spine" instance to see what the expression evaluates to.

Spine should compile and work on any unix-like operating system that has yacc and lex (or byacc and flex), like Linux, Solaris or NetBSD.


Tic Tac Toe

I wrote a player in Python, using the Alpha-Beta pruning minimax algorithm. It has a lot of features, including letting human or computer go first, and choice of mark ('X' or 'O').

I also wrote a non-recursive, non-minimaxing player in C. I believe this demonstrates that just following simple rules-of-thumb can work, if only in very simple games.

Since a simple game player isn't enough, how about a Python program that enumerates all possible Tic Tac Toe game endings? Bonus! A C program that also enumerates all possible game endings! Both programs give the same count of game endings, but I haven't verified that they both find the same set of endings.

Of course someone else has done it better. I have not played my program using this chart. Let me know if you do, and how it turns out.

I wrote a tac toe web app, an Alpha-beta minimax tic tac toe in PHP that you can actually play. To install, download the source archive, then ungzip and untar it in a directory under your web server's DocumentRoot. The web server must have PHP 5.3 (or later) set up.

For a greater challenge play Nine-board Tic Tac Toe, a web page that plays a variant of tic tac toe. The entire program is JavaScript, and runs in your browser. An obsolete version of Nine-board Tic Tac Toe ran the user interface in your browser, and did all calculation in a PHP program in the web server. That may still fit your needs. You will need 4 files from Sajax-0.13 to run it.


Random Image Generator

nude descending a staircase

Create small, mid-century Modern works of art with my PHP image generator! The PHP image generator created the little, never-the-same image above. Source here. Needs a PHP interpreter with GD and JPEG support.


A bad imitation of Mondrian

Tu'um

Create small, Mid-century Modern works of art in imitation of Piet Mondrian with the AutoMondrian image generator! The PHP image generator created the little, never-the-same image above. Source here. Needs a PHP interpreter with GD support. Use another page in a vain attempt to exert control over the Art. Try it!.


Binary Tree Pattern Matching

An implementation of Hoffman and O'Donnell's algorithm to match (sub-)trees of binary trees.

$  ./test6 -p '(a (b *))' -s '(y (x (a (b (e f)))))'
Match pattern with subtree:
(a (b (e f)))

Source code here. You get to build it, and it's in C!

I modified this algorithm to perform arbitrary bracket abstraction algorithms in my generalized Combinatory Logic interpreter.


Robinsonized Self-describing Strings

Douglas Hofstadter's book Metamagical Themas has a section about self-referential sentences. Raphael Robinson's puzzle version intrigued me. So, I wrote a Robinsonizer in Perl. I used Perl as my utility language at the time.

Hofstadter gives the puzzle like this:

In this sentence, the number of occurances of 0 is _, of 1 is _, of 2 is _, of 3 is_, of 4 is _, of 5 is _, of 6 is _, of 7 is _, of 8 is _, and of 9 is _.

Theoretically, only two solutions exist. My Robinsonizer doesn't work with the entire text of the sentence, just the digit-characters and the empty spots:

_0_1_2_3_4_5_6_7_8_9

And, yes, it reverses the order of empty spots and digits relative to Robinson's sentence. It finds self-describing sequences iteratively:

10:40AM 101 % ./robinson.pl 0123456789
0123456789
10111213141516171819
101111213141516171819
101211213141516171819
101112213141516171819
101112213141516171819

That sequence corresponds to filling out the sentence like this:

In this sentence, the number of occurances of 0 is 1, of 1 is 11, of 2 is 2, of 3 is 1, of 4 is 1, of 5 is 1, of 6 is 1, of 7 is 1, of 8 is 1, and of 9 is 1.

The Perl Robinsonizer can get into cycles of length > 3 and not realize it. It can also find self-describing sentences that don't fit Robinson's original puzzle, like "22", "1031223314", "21322314", "3122331415", "3122331416", "3122331417", "31123318" and "3122331419". Not all the digits 0 through 9 appear.

I wrote a Python Robinsonizer, which keeps better track of previously-occuring strings, making detection of much longer cycles feasible. I found the second solution with it:

11:48AM 58 % ./robinson.py 011222333444455555666666678999999999999999999
011222333444455555666666678999999999999999999
102132334455761718189
10512233242516272819
10416223142516171819
10713213241526171819
10713223141516271819
10713223141516271819

That last string corresponds to filling out the sentence like this:

In this sentence, the number of occurances of 0 is 1, of 1 is 7, of 2 is 3, of 3 is 2, of 4 is 1, of 5 is 1, of 6 is 1, of 7 is 2, of 8 is 1, and of 9 is 1.

Those "Robinsonizers" don't suit you? This Java Applet can do a lot of the same things. And, hey, here's a Ruby Robinsonizer. yet another self-referencing puzzle, that explains robinsonizing a bit better than I did above.



These pages are designed to be informative and not to win any "cool site of the week" awards.

Last update: Wed Sep 30 22:24:51 MDT 2009