APL Trivia – Loopy, Quine & Turing
Vector 3:1, page 124
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 124
Following your call for more trivial APL functions (so much more interesting than the useful sort) here are a pair of self reproducing functions; one reproduces its ⎕CR form, the other its ⎕VR.
∇ r←CRSELFREP
[1] r← 2 89 ⍴(38⌽127↑r),1⌽⎕AV[⎕IO+2⍴39],r←'r← 2 89 ⍴(38⌽127↑r),1⌽⎕AV[⎕IO+2⍴39],r←r←CRSELFREP'
∇
∇ r←VRSELFREP
[1] r←7⌽⎕TCNL,⎕AV[⎕IO+ 32 32 32 32 236],⎕TCNL,(¯17⌽⎕TCNL,r),1⌽⎕AV[⎕IO+2⍴39],r←'[1] r←7⌽⎕TCNL,⎕AV[⎕IO+ 32 32 32 32 236],⎕TCNL,(¯17⌽⎕TCNL,r),1⌽⎕AV[⎕IO+2⍴39],r← ∇ r←VRSELFREP'
∇
Both these functions use the same trick, first formulated by the logician E.Quine. If we have a function QUINE with the property that QUINE x is x’x’, then we can create a self-reproducing expression by writing QUINE’QUINE’.
Try evaluating the expression:
QUINE’Applying QUINE to the following vector creates a false statement’.
Do you believe what it says or not?
Although this may seem a rather fanciful function it is not without its serious side; it has profound applications in both logic and computer science. Godel relied upon a version of it to prove the incompleteness of formal mathematics, and see how it fits into the following rather curious result.
LOOPY is a function of one argument, x, that returns 1 if executing x would cause an infinite loop, and 0 otherwise.
Obviously LOOPY can’t actually execute x itself, because if it did go into an infinite loop there would be no way it could return a result to say so; instead it must perform a clever syntactic analysis, coupled with the execution of carefully selected bits of code (looking for lines that perform an unconditional branch to themselves would probably be a good place to start).
But now consider the following function, named after its discoverer, Alan Turing:
What is the value of TURING’TURING’? In particular, does it go into an infinite loop or not?
The only solution to the above dilemma is to conclude that the function LOOPY is impossible, it just can’t be written to behave as described. But if there’s no algorithm we can express in APL that will let a computer tell if a function goes into an infinite loop or not, how can we, as mere humans, do it? Presumably we can’t, which makes debugging programs a rather fraught exercise. By building on Turing’s work logicians were able to show that for every function specification we can realise in APL (or any other language), there are literally infinitely many we can’t – which makes writing programs sound like an even more futile activity than debugging them.
All this is beginning to sound dangerously non-trivial, so I shall move on from functions that can’t be written to functions that never should have been. Those of you with access to STSC APL*PLUS/PC (I haven’t tried this on other systems) might like to try the following little function, coyly named BUG.
∇ BUG;f
[1] f← 2 4 ⍴'r←L9','r←L8'
[2] ⎕WA←⎕FX f
[3] →L9
[4] L8:⎕←'LINE EIGHT'
[5] →0
[6] L9:⎕←'LINE NINE'
[7] →0
∇
As Gilman and Rose explain on page 150, labels are like local variables but you can’t assign new values to them; as you can see however it is possible to ⎕FX a function of the same name, and this can return any value you like! I showed this to Martyn Adams who came up with the bright idea of expunging the newly created function, this ‘works’ as you would expect too (imagine the effect of a virus function that spent the morning infecting other pieces of code and then during lunch re-assigned or removed all their line labels!).
∇ BUGTWO;f
[1] f← 1 2 ⍴'L9'
[2] ⎕WA←⎕FX f
[3] ⎕WA←⎕EX 'L9'
[4] →L9
[5] L8:⎕←'LINE EIGHT'
[6] →0
[7] L9:⎕←'LINE NINE'
[8] →0
∇
Now that the line label had thoroughly disappeared I tried re-introducing it by direct assignment, i.e.
∇ BUGTHREE;f
[1] f← 1 2 ⍴'L9'
[2] ⎕WA←⎕FX f
[3] ⎕WA←⎕EX 'L9'
[4] L9←L8
[5] →L9
[6] L8:⎕←'LINE EIGHT'
[7] →0
[8] L9:⎕←'LINE NINE'
[9] →0
∇
Oddly, at this point the interpreter ‘remembered’ that L9 was a line label and came back at me with a domain error. It proved a lot more obliging, however, if the branch and the assignment took place on the same line.
∇ BUGFOUR;f
[1] f← 1 2 ⍴'L9'
[2] ⎕WA←⎕FX f
[3] ⎕WA←⎕EX 'L9'
[4] →L9←L8
[5] L8:⎕←'LINE EIGHT'
[6] →0
[7] L9:⎕←'LINE NINE'
[8] →0
∇
Even more oddly, I discovered that this trick failed when the following line contained a simple branch, even though it was never called.
∇ BUGFIVE;f
[1] f← 1 2 ⍴'L9'
[2] ⎕WA←⎕FX f
[3] ⎕WA←⎕EX 'L9'
[4] →L9←L8
[5] →L9
[6] L8:⎕←'LINE EIGHT'
[7] →0
[8] L9:⎕←'LINE NINE'
[9] →0
∇
Before you all go rushing off to incorporate these tricks into your latest devishly cunning lines of code, I should point out that these are real bugs, not features. Every time I have run these functions I have had some sort of system crash a few moments later, ranging from the spectacular vision of all the characters rushing to the centre of the screen and vanishing, while the disk drive lights glowed fiercely (a software black hole ?) to the quiet but resolute announcement that my attempt to issue )SAVE was a domain error!
P.S. Would it be possible to suggest that the trivia section of VECTOR be renamed ‘Iota-zero’ ? (Because it’s a vector with trivial content. Oh well!)