in Computer Programming
|Mailing List | Language Lab | Essential Tools | Retrocomputing Museum | Random Languages List | Weird Programming Languages | The Turing Tarpit|
|A hush falls over the world as we wait with baited breath to find out who won The 2000 Esoteric Awards!|
Esoteric Program Forms
The Null Program
If a program is a series of instructions, then the null program is a series of zero instructions. The null program has some interesting properties, not the least of which being that it's simultaneously written in many languages and many paradigms...
A quine is a program which produces a listing of itself as it's output when run. Gary Thompson has a comprehensive quine page. David Madore has a page on quines which describes the underlying principles and explains how to write them. Ben Olmstead also has a quines list. The null program can be considered a quine in many languages, since it consists of nothing and represents a program which produces no output!
A polyglot is a source code file for a computer program written in multiple computer programming languages simultaneously.
Gary Thompson has a polyglot page. (Some of the polyglots he lists are also full-fledged quines!) The null program is a polyglot in many languages, though not a particularly interesting one.
Palindrome programs are exactly the same idea as palindrome sentences: they read the same forwards as backwards (disregarding whitespace and punctuation.)
Esoteric Programming Practices
A self-modifying program is a series of instructions which contains one or more instructions to change, at some point during the execution of the program, one or more of the instructions in the series.
There are few if any general rules that apply when code modifies itself. A particularly difficult situation arises when one goes to compile self-modifying code, that is, translate it into another language with a different or non-existent notion of self-modification; the compiler must either produce programs which include a copy of the compiler itself, or the compiler must use sophisticated self-modifying code-and-data flow analysis techniques to try to determine the actual range of semantics of the given program, with self-modifications. Either way, interpreting self-modifying code is generally simpler.
But the bottom line about self-modification is that it's just plain weird. Once you let a program reason about and alter it's own instructions, you've crossed a line where the further execution of the program becomes extremely difficult to predict.
Malbolge requires use of self-modification to achieve Turing-Completeness. SMITH has an instruction pointer which cannot do anything except advance (no jumps!) and thus also relies on self-modification to simulate a loop. At the extreme, all SMETANA can do is modify itself, and is probably not Turing-Complete.
Polycoding is the act of non-trivially compiling or executing a single instance of code in multiple contexts. Generally this is accomplished by programming in multiple dimensions and/or directions and/or topologies or using creative GOTOs, such as with a line number variable (a computed jump) like some BASICs allow.
Optimized tail recursion is an example of a simple polycoding technique; instead of using a subroutine call as the last instruction in a subroutine, use a plain jump to the desired subroutine instead. As with most polycoding techniques, it saves a tiny bit of space and/or time at the cost of making the program harder to maintain.
Befunge-93 (and to a lesser extent, Wierd) programmers trying to squeeze programs into small spaces, in the quests for such things as the smallest random number generators, bred the development of polycoding idioms in that language, just to get a bit more mileage out of fewer instructions.
The Boo-yah language (an implementation for which is in the works) forces the programmer to write polycode.
Bullfrog has no conditionals whatsoever; all control flow must be done with computed jumps.
It would seem some programmers are simply masochists.
Brainf*ck is a good introductory language for those looking to get into the world of cruel and unusual programming.
Trying to write a program with a nested loop and subroutines in SMITH ought to keep your mind occupied for a while.
The programming language Malbolge was named after a level of Dante's Inferno; that should give you a clue as to how easy it is to program.
reMorse should be mentioned here as well; the author repeatedly forewarns that he is not responsible for any loss of sanity caused by reMorse, and for good reason.
If you like relying on references to yourself, you'll enjoy BAK.
And who can ignore INTERCAL, which was created in 1972 for the purpose of being as unlike any other language as possible; it's name is an acronym for "Compiler Language With No Pronounceable Acronym."
Size Matters, and Less is More
Brainf*ck was designed to be a language for which an ultra-tiny compiler could be written.
So was False, which has nice quasi-functional touches - lambda abstraction and a stack. (False is just one of Wouter van Oortmerssen's many languages, and is named after his favourite Boolean value.)
Shelta is in many ways a minimal version of FALSE. One implementation of Shelta is written in assembly; another is written in Shelta! Shelta is one of the smallest languages to ever be bootstrapped.
Just Plain Weird
Unlambda demonstrates that the lambda calculus can be a dangerous tool in the wrong hands.
Java2K seems to be the product of an extremely disturbed mind - don't show this one to psychiatrists.
And why stop with Earthly languages? var'aq gives Klingons far and wide the opportunity to do applications programming in their native tongue.
Finally, ILLGOL is pure joke, sort of a parody of commercial, proprietary development languages. It has no specification, but fairly interesting release notes; the compiler is only available for DOS platforms and is most definitely not open-source.
Esoteric Brain Banks
Where the academics fear to tread, business - to fulfill the demands of the hobbyists - takes up the slack. A lowly sole proprietorship in Canada, Cat's Eye Technologies, hosts this page.
Assurdo Technologies provides some incredibly (and happily) sick products to the world including dd/sh and an INTERCAL compiler for quantum computers.
Esoteric Programming Languages
There are a wide variety of programming languages in the world today that require one to use decidedly different paradigms than one might typically use in day-to-day computer programming. They present the programmer with the challenge, intrigue, and entertainment of looking at known algorithms and concepts in a whole new light.
Programmers who work exclusively with imperative languages - that is, those languages with an explicit assignment statement - (e.g., C, C++, Perl, Pascal, Java, BASIC, COBOL, etc ad nauseum) typically have more difficulty handling languages where the flow of control is not as directly related to a "currently executing position" in the program source.
So much can be said on the topic of different paradigms, in fact, that I've decided to devote an entire separate page to them.
A metalanguage is a language that describes another language. Besides the old chestnuts such as Wirth's EBNF and the countless attributed applications of it for compiler-compilers, here are some fairly freakish variations on the theme:
ALPACA is a language for programming arbitrary cellular automata, a metalanguage which can succinctly describe any CA, even complex ones.
SQUISHY, which is now probably lost to the mists of time, was an application of a language-theory construct known as a semi-Thue grammar. The SQUISHY compiler treats each input file as the definition of a compiler. The grammar for such a compiler has embedded semantics such that it can compute by continuously rewriting strings, so it would be quite possible to write a compiler that sings "99 Bottles" by taking any string as input and writing the lyrics to the song as output.
SQUISHY has been superseded by a language called Thue, which differs only in small ways (nondeterministic instead of deterministic; BNF-like instead of EBNF-like; directly based on a semi-Thue grammar; and a proper tarpit to wit,) and for which an implementation is being developed.
Automata as Languages
Some cellular automata, such as John Conway's Life, can (in theory) solve any solvable mathematical problem (such as computing pi to a hundred decimal places) and, as such, can be considered Turing-Complete.
noit o' mnain worb can be looked at a tarpit version of the kind of automaton RUBE 'should have been', for clarity: not a cellular automaton, but a particle automaton, in which states do not simply propagate, but particles actually move and collide.
In the world of computing and informatics, a tar pit (sometimes merged into one word, tarpit), more fully Turing tar pit, is a Turing-complete machine with an arbitrarily low number of discrete instructions. (There are other definitions, but the author of this page prefers this one.)
OISC and URISC, which can be found at the RCM, have only one instruction each. SMETANA has two instructions but has not been proven Turing-Complete and in all likelihood isn't. reMorse was originally designed with only two instructions, represented as Morse code. FORTH can be built up from 3 basic instructions. Shelta has "no" instructions (it relies on in-line assembly.) Wierd has a handful of basic instructions determined by angles in chains of only two kinds of specifier characters, 'space' and 'not space'. Malbolge has 7 instructions. Brainf*ck has 8 parameterless instructions but is one of the most popular tarpits, having a very beautifully symmetrical grammar for which a very tiny compiler can be built. Fromage is a ten-instruction tarpit with the bit as the basic data type.
Who says a tarpit has to be modeled after Turing's machine, anyway? Sally is nearly a tarpit and under every reasonable definition it is not an imperative language, but a functional one.
Thue is also pretty much a tarpit, having only the barest semantics, and a rather boneheadedly simple syntax. But it can only be classified as a constraint-based language.
noit o' mnain worb could be classified as a constraint-based language, or maybe a concurrent fungeoid, or a particle automaton. Call it what you will, it has an arbitrarily low number of discrete components which function in combination to simulate a (nearly) Turing-Complete system.
OOPS and beta-Juliet break the object-oriented model down to it's barest form -
passing messages - and offer few other semantics. Are these not object-oriented tarpits?
Computer can be built using operational amplifiers instead of logic gates. These machines, called analogue computers (or analog computers if you're in the United States,) take input, perform computations, and produce output, but all in terms of amplitudes of electrical signals, rather than combinations of quantized "on or off" amplitudes, looked at as Boolean values or binary digits.
Even though electricity is an easy-to-manage resource on which to base computing machinery, it is far from the only one.
Entirely mechanical computers can be built - abacuses and cash registers are two simple examples. More involved examples include the "Tinkertoy" computers (which could play Tic-Tac-Toe at an expert level) and "ropes and pulleys" and "billiard balls" logic gates.
This is because that Turing-Complete in the real world relies on the following law of physics: two particles cannot share the same space at the same time and will resist doing so.
So, analogous to their electronic cousins, it should be entirely possible (if not exactly economically feasible) to create hydraulic and pneumatic computers based on the same principles of pressure and flow (one-way valves). worb is an example of a generalized computing environment which is neither electronic nor hydraulic nor pneumatic, but works in an analogous way.
Specs on Spec
While many languages are designed by sheer dint of building a compiler for them, others are so conceptually bizarre that the specification comes first, and the implementation may or may not follow eventually...
*W has no purpose besides annoying the user.
Tamerlane attempts to resist all efforts to classify it.
The spec for TURKEY BOMB is probably best left unviewed by mortal eyes.
Magenta is in many ways a cursed language, wholly vague and full of committee-thinking.
Last Updated Jan 27 2001 Cat's Eye Technologies.