New Book, out Sept 23, 2025: Forty-Four Esolangs, the first artist's monograph of programming language concepts. It is with great excitement that we share the original INTERCAL-72 compiler source…
It is with great excitement that we share the original INTERCAL-72 compiler source code, as both scans and transcriptions (see below). INTERCAL was created by Don Woods (previously interviewed here) and Jim Lyon as undergrads at Princeton in an infamous late-night session after freshman finals in 1972. Don recently rediscovered a print-out, on green-barred, continuous-feed pages, of the SPITBOL source code for the original compiler. If the legend holds true, this code had not been run since Woods and Lyon's Princeton days. Sean Haas (of the Advent of Computing podcast) and I transcribed the code from these scans, proof-reading each others' interpretations of fading characters. Haas has also produced a refined, runnable version of the script.
INTERCAL ("Compiler Language with No Pronounceable Acronym") is the first language that can unequivocally be called an esolang. While previous languages had odd designs as pl research and experimentation, INTERCAL intentionally subverts its programmers' effort to write what Dijkstra called "good code": that which "shortens the conceptual gap between the static program and the dynamic process." In INTERCAL, code is circuitous, full of symbols used in bizarre ways and with unique designations (#, for example, is the "mesh" sign). It is a challenge to read or to run in ones head, even for those deeply immersed in the language. Furthermore, it does this for parody and play, not with any practical aim in mind.
The length of INTERCAL's shadow cannot be overstated. It was twenty years after its creation that a series of minimalist languages (FALSE, Befunge, brainfuck) took the next steps toward what would become the esolang movement. INTERCAL-72 offered somewhat of a different path from these; it was less concerned with minimalism, and more explicitly dramatized the act of programming. Woods and Lyon described it as eschewing conventions of languages like ALGOL, SNOBOL, FOCAL, and AP/I, yet it is also clearly parody, embracing and exaggerating their worst eccentricities and inefficiencies for an alienating experience.
INTERCAL's most striking feature is its humanizing of the interpreter, a mercurial being who we literally plead with to get our programs to run. Use the command PLEASE too little and the interpreter will be offended and ignore the whole program; use it too much and it writes you off as a suck-up and... also ignore the whole program. Its subjectivity feels particularly relevant in an age when AI systems are designed to deliberately confuse the human and algorithmic. The influence of just this one feature can be seen in early parody languages like Chicken and Ook! that undermine the seriousness of the interpreter, to English, where the interpreter was once literally another person but is now downgraded to an AI prompt system. More personally, the interpreter for my language Olympus has many, competing personalities in the form of the Greek gods, any of which might become offended and ignore the rest of the program, in INTERCAL style.
However, for such an influential esolang, it is one that we experience primarily in derivative forms. The most well-known INTERCAL keyword (apart from PLEASE) is not part of the INTERCAL-72 language at all. That would be the COME FROM statement, an inverse of GOTO, where one has to trace back jumps from destination to source, like cheating in a choose-your-own-adventure book. It was added in 1990 by Eric S Raymond (interviewed here) for his adaptation C-INTERCAL. The original INTERCAL-72 compiler never left Princeton according to Woods; it is likely that ESR worked from the INTERCAL-72 manual without access to the reference compiler. Almost all who have used the language since then have actually used C-INTERCAL or one of its successors (CLC-INTERCAL etc). These later versions capture much of the spirit of the original but differ significantly in style and content. Now, with access to the original, we can experience INTERCAL-72 first-hand and make new discoveries.
Sean Haas describes the process of getting the ical.sbl (INTERCAL compiler) program running on a modern system, using SPITBOLx64. As he points out, ICAL is actually a transpiler; some of its infamous slowness is due to the overhead of generating a SPITBOL program and executing it. More surprisingly, it avoids SPITBOL's math functions, performing math through pure string manipulation. Sean discusses this in the latest episode of his podcast, Advent of Computing, explaining the infamous thirty seconds needed to perform a single division:
The two operations you get, called MINGLE and SELECT, operate on binary data. Internally, ICAL will store numbers as a string of binary digits. A 4 becomes "100", for instance. When you operate on that number it's done as a string operation. The result is that any operation with numbers become this convoluted mess, both in INTERCAL and in the final output SPITBOL. Hence, 30 second divides.
The full set of scans and transcribed code can be found on GitHub.
Read the original article
Comments
By entrepy123 2025-06-022:51 The INTERCAL satirical language (the original compiler's source code of which is announced as recovered in TFA) was covered in a couple of episodes [0, 1] of the (highly recommended, if I may say) Advent of Computing podcast [2].
[0] https://adventofcomputing.libsyn.com/website/episode-78-intercal-and-esoterica [1] https://adventofcomputing.libsyn.com/website/episode-158-intercal-rides-again-restoring-a-lost-compiler [2] https://adventofcomputing.comThey call it an esoteric language but event-driven programming is basically based on "COME FROM" structures. Shell also extensively uses PLEASE-like fonctionality in the form of SUDO. The syntax of INTERCAL is very clean if we compare it to, say, regex.
Not sure about regex. Its syntax is, by definition, regular. (Okay, most regex engines people use aren’t technically fully regular languages anymore, but that just makes things more convenient.)
> Its syntax is, by definition, regular.
No, not at all. Regexes describe regular languages, but that doesn't mean that their own syntax needs to be a regular language.
Eg many regexes allow parens, so you can have both 'ab|c' and 'a(b|c)'. But if you require your parens to be balanced, that's no longer a regular language.
> if you require your parens to be balanced, that's no longer a regular language.
TIL: https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang...
As someone who has only recently learned the formal definition of regular language ( Thanks to https://www.youtube.com/watch?v=9syvZr-9xwk as mentioned on this board recently ), I'm interested in the formal proof for this?
It feels intuitively true, but I haven't finished the course yet and therefore haven't come across it and can't yet reason well about it.
Is the problem then in trying to "encode" whether brackets are balanced, that we would need infinite "levels" of how many more brackets we've opened rather than closed, (i.e a stack) and that violates the finite nature of finite automota?
So I've googled it now, and I've found the result is due to the "Pumping lemma": https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang...
Pulling on the thread of your intuition about needing infinite levels, a regular language is one that can be recognized by a finite automaton, so requiring infinite memory or arbitrarily high counting suggests that the language is not regular. It’s not perfect; we prove it as below.
Assume for purpose of contraction that our language L of balanced parentheses is regular. Then L has pumping length p ≥ 1 such that every w ∈ L where |w| ≥ p can be decomposed w = xyz where |y| ≥ 1 and |xy| ≤ p. It is called the pumping lemma because we can “pump” the non-empty substring y either up or down, i.e., xy⁰z = xz and xyⁿz are also all in L. In formal languages, exponentiation notates character or string repetition.
We don’t know p and may not cherry pick it. Pretend you are playing a game against an adversary who gets to select arbitrary p ≥ 1, and then you use that p to choose w ∈ L to spoil the regular language party. With the language of balanced parentheses, no matter what p the adversary selects, you can force the leading xy prefix to contain all left-parentheses by choosing w = (ᵖ)ᵖ. The substring y cannot be empty, so pumping down gives xy⁰z = (ᵖ⁻ᵏ)ᵖ belongs to L, a contradiction.
One of my favorite test questions for automata theory classes is to have ChatGPT attempt a proof that a language is not regular and then have students correct the proof. You linked to a lecture by Michael Sipser, and the undergraduate version of the course I teach uses his excellent textbook.
https://www.amazon.com/Introduction-Theory-Computation-Micha...
His lecture on the pumping lemma for regular languages is
I've just watched that video, thank you, and it's interesting that he shows an example where my intuition of counting leading to non-regularity fails:
We've seen you can't detect if there is a balanced number of 0's and 1's in a string of 0's and 1's with a FA/Regular expression, howver you CAN detect if there are a balanced number of "01" and "10" substrings in a string of 0's and 1's.
Proving that 01 and 10 balancing was left as an exercise to the reader, which I will try to work through here, hopefully I've not made a mistake. My intuition here says that it is equivalent to checking whether it starts and ends with the same symbol, because 01 leaves you having last read a 1, and therefore then requires a "10" substring to get back to having last read a 0, and vice-versa.
The FA I believe therefore can be constructed with transitions
Or presented differently, (0(0U1)0) U (1(0U1)1) U epsilonQ0 -> epsilon -> Q1 Q0 -> epsilon -> Q3 Q1 -> 0 -> Q2 Q2 -> 1 -> Q1 Q1 -> epsilon -> Q5 Q3 -> 1 -> Q4 Q4 -> 0 -> Q3 Q3 -> epsilon -> Q5 ( Starting Q0, Accepting Q5 )By gbacon 2025-06-0421:26 Your intuition about starting and ending with the same symbol is correct. This is a good example of why the unbounded memory rule of thumb is not perfect.
The NFA you described recognizes
All strings in the above language will begin and end with different symbols and have only even lengths. (Balanced means not only equal in number but that they nest properly, e.g., )()()( and ())( have equal numbers of left- and right-parentheses but not in balance.) The empty string ε does belong to the language, and your NFA — but not your regular expression — correctly accepts it. The language from Sipser’s lecture has strings of odd length as well, the shortest being 0 and 1 that an equal number (namely, zero) of 01 and 10 substrings.(01)* ∪ (10)*Your regular expression is close. It looks like HN’s markdown formatting ate your Kleene stars. Always account for the empty string, and in your case it does need to appear explicitly.
Because this is a simple enough language, I suggest building a DFA rather than an NFA. You know that your automaton will have two branches: one for strings beginning with 0 and the other for those that begin with 1. That accounts for three states so far, and your initial state q0 has both of its transitions defined. Let’s say that q1 is the state after reading the initial 0. (Remember that you can interpret each state in a finite automaton’s transition graph as “I have read …”) When you’re in q1 and read a 0, where do you go? When you’re in q1 and read a 1, where do you go? You’ll know you completed this branch when you have defined 0 and 1 transitions for all its states. Then move on to completing the branch for strings that begin with 1. The intuition is it ought to have similar structure to the first branch. Finally, label your final or accept states. Always remember to account for the empty string!ε ∪ 0 ∪ 1 ∪ 0(0 ∪ 1)*0 ∪ 1(0 ∪ 1)*1What’s really interesting is the NFA you defined has, after conversion to DFA and minimization, almost the same structure as the correct DFA: the only difference is which are accept states.
By anyfoo 2025-06-0221:40 You're right!
> But if you require your parens to be balanced, that's no longer a regular language
From a certain pedantic perspective, it still is a regular language, since there is a finite (implementation dependent) upper bound on nesting depth, and balanced parens with a finite upper bound of nesting is regular.
OTOH, one can appeal to the linguistic distinction between competence and performance, and say that regexes are irregular in pure competence, even though all (practically usable) languages turn out to be regular once we constrain them by performance as well.
> From a certain pedantic perspective, it still is a regular language, since there is a finite (implementation dependent) upper bound on nesting depth, and balanced parens with a finite upper bound of nesting is regular.
That's a silly point, because it makes all languages trivially finite, even monsters like C++. (Finity is even more of a restriction than being regular.)
Is it silly? Well, if a person feels drawn to an ultrafinist philosophy of mathematics, they may feel it is important to emphasise the inherent finitude of all creations of inherently finite human minds, formalisms such as programming languages included.
Oh, finitism is perfectly fine by me. I have a lot of sympathy for it!
What is silly is not finitism (or ultrafinitism), but trying to apply concepts like 'regular language' or 'context free language' without modification in such a setting.
I suspect you should be able to suitably alter most of these concepts to make sense in the strictly finite setting. But they are going to become a lot more complicated.
For a similar flavour, you can also check out the differences and similarities between differential equations and difference equations.
Right, but the “finite setting” is the real world. Yes, if we talk about C++ as a mathematical abstraction, maybe a C++ program containing a googolplex tokens could be in a theoretical sense syntactically and semantically valid. But such a program can’t exist in the real world
Let’s say a compiler has a (very plausible) implementation restriction that the source code of a program can be no longer than 2^32 bytes. Then, even if the abstract grammar is (e.g.) an unbounded context-free language, the actually accepted language has a finite upper bound on length-and it is well-known that applying a length constraint turns a context-free language into a regular language. This doesn’t require us to “to suitably alter most of these concepts to make sense in the strictly finite setting”, because formal language theory in an infinite setting permits constraining languages to be finite, and we have a very good understanding of what that the results of that are - this doesn’t require any new or different math, just applying the same math.
Now, it is true that, we will say that certain algorithms only work for regular languages, not context-free - but once we impose a finite bound on length, those algorithms do actually work in principle. In practice, of course, they are likely impractically slow - but the formalism we are talking about (the Chomsky hierarchy) is based on computability (can it answer the question in a finite but unbounded amount of time), not asymptotic computational complexity (nor real-world performance, which isn’t the same thing, as e.g. galactic algorithms demonstrate)
And those formalisms all become silly. Computability also becomes trivial, if you only have a finite amount of memory: either your program halts after a finite amount of time, or it enters a loop after at most 2^(number of bits in your memory) steps.
> Computability also becomes trivial, if you only have a finite amount of memory
I disagree. Computability isn't trivial if you have a finite amount of memory.
In the real world, we have machines with finite space and time. It is far from trivial to work out what problems they can and can't solve. In very many cases, all we can say is "we don't know how to solve this problem, but for all we know there is a way of solving it which nobody has discovered yet". There are many problems for which, a century will pass from today, and we'll likely be no closer to knowing whether they are solvable than we are now.
Yes, if you actually had a machine with infinite storage, and you had an eternity to wait for its computations to complete, then you could always eventually get the decisive answer to the question of whether a machine could solve a problem given some finite bound on storage and time. But that's a very unusual sense of "trivial", essentially "this problem is trivial if we assume humans are immortal beings with infinite resources"
Now you are mixing things up.
> It is far from trivial to work out what problems they can and can't solve.
Yes, and I am exactly saying that if you want to talk about explicitly finite machines, you need more sophisticated concepts. Formally defined 'computability' (with the usual definition) is a silly notion for these finite machines, because it captures nothing of the subtlety. It's trivial for finite machines. Trivial concepts are seldom useful.
The standard formal definition of computability doesn't care about your finite human life. Similar for the standard formal definition of 'regular language' etc.
It seems like you are agreeing with me, but don't really know the terms very well.
> Formally defined 'computability' (with the usual definition) is a silly notion for these finite machines, because it captures nothing of the subtlety. It's trivial for finite machines.
Computability is relative to the definition of an abstract machine - e.g. there are problems which aren’t computable given a standard Turing machine, but which are for e.g. a Turing machine with an oracle, or a Turing machine that can execute supertasks - the halting problem for a standard Turing machine is computable by a Turing machine with an oracle for the first-order halting problem (but its own halting problem remains uncomputable for it)
And if “computability” can be meaningful for abstract machines stronger than a Turing machine, it can also be a meaningful concept for weaker machines
e.g. a problem for which the fastest possible algorithm is O(n^2) isn’t computable by a linear bounded automaton, but problems for which the fastest possible algorithm is O(n) or O(log n) are computable by an LBA
> but don't really know the terms very well.
I think the same about you
> e.g. a problem for which the fastest possible algorithm is O(n^2) isn’t computable by a linear bounded automaton, but problems for which the fastest possible algorithm is O(n) or O(log n) are computable by an LBA
You are right that there's lots of interesting mysteries to explore. But the tools we commonly use only work for (potentially) infinite machines.
Alas, Computability for all finite machines is trivial. And big-O notation is another silly one for finite machines: it's all O(1) for them. Big-O notation is too blunt a tool to deal with finite machines, at least by itself.
By skissane 2025-06-049:46 You seem to be using the word “computability” to mean “computable by an abstract machine of Turing degree 0”, whereas I am using it in the broader sense of “computable by an abstract machine of specified type”. As I said, in that broader sense, computability is non-trivial for finite machines.
And that broader sense is very standard, you’ll find heaps of papers/etc containing variations of the phrase “computable by a Turing machine with an oracle”… but if that oracle is e.g. for the standard (Turing degree 0) halting problem, then that halting problem is computable by such a machine.
You were earlier claiming I wasn’t familiar with the definitions, but you are giving me the impression you aren’t familiar with “computable” as a relative term
By Duanemclemore 2025-06-023:44 Probably my single favorite podcast episode ever is the Future of Coding's episode on INTERCAL [0]. At least I think they tried to make it about INTERCAL.
No matter what - a consideration befitting the subject.
