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.
My favorite awk scripts, right here, right now! No download necessary, just cut-n-paste!
#!/bin/sh
# This costs memory two ways: (1) sort has to buffer up everything somehow, and
# awk has to have a huge array in-memory.
sort -n |
awk 'BEGIN{c=0;sum=0;}/^[^#]/{a[c++]=$1;sum+=$1;}END{ave=sum/c;if((c%2)==1){median=a[int(c/2)];}else{median=(a[c/2]+a[c/2-1])/2;}print sum," ",c," ",ave," ",median," ",a[0]," ",a[c-1]}'
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 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.
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.
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.
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.
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.
New! Version 2.10 as of 2001-07-09.
I use this HTTP request generator to:
- Accurately time HTTP requests.
- Reproducibly generate arbitrary HTTP POST requests to trigger CGI-BIN program bugs.
- Generate incorrect HTTP requests to test an HTTP server's abilities.
- Collect the HTML a server gives back.
- Examine HTTP protocol headers returned by a server (a help in times of mime-type crises).
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:
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.
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:
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.
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:
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 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.
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.
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.
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 |
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.
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.
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.
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.
This took a bit longer to do than I'd thought. Perl does have syntax similar to both Python and Bourne-shell-derivatives (bask, ksh, zsh). The Perl (5.x in this case) print statement does not put a newline on any output strings, unlike Bash or Python print statements. Getting newlines on the ends of output strings from Perl generations gets complicated by the differences in how Python, Bash and Perl represent a backslash (ASCII 0x5C) literal.
Download, and run from a command line like this:
$ tar xf triplet.tar $ cd triplet $ ./run_replication Running m1, output to m2 Running m2, output to m3 ... Running m8, output to m9 $ cksum m?
The cksum command will show that the run_replication script produced 3 sets 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.
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 will probably never work on Hewlett-Packard's ghastly HP-PA CPU because of that architecture's poorly-documented segmentation.
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).
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.
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:
QuintoQuinto 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.
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.
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').
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.
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