Sunday, March 18, 2007

Part Tatlo - Looping, wonderful looping_

(This is the third part in my Diving into INTERCAL series. If you have read the first two parts then don't feel cocky because the following will probably not make any more sense to you than to a total INTERCAL beginner.)

In this excursion into the magical world of INTERCAL programming we will try to do the almost impossible, create a program with a while loop. If you have programmed in any imperative programming language, such as C, Java, Python or Commodore BASIC, you will know that loops are usually a straight-forward construct. However INTERCAL is designed from the ground up to be like no other language, so let's see if we can actually get a loop to work.

Having taken nearly two hours to write 'Hello, world' last week, I decided to set my sights fairly low for this week. I want to implement the following Python program in INTERCAL:
x = 0
while(x != 1):
x = int(raw_input("Please input a number\n"))
print x
This is by no means a useful program - it simply asks the user repeatedly to type in a number, printing it out each time, until the user enters a number which is not equal to 1.
Anyone with any amount of experience knows that it would be a folly to attempt to convert this program to INTERCAL in one shot. It is much more wise to perform the conversion in small steps. Here is my first iteration:
1         DON'T WORRY, BE HAPPY
2 (1) PLEASE NOTE THAT WE ARE NOT PROMPTING
3 DO WRITE IN .1
4 DO READ OUT .001
5 DO GIVE UP
The line numbers are not part of the program. (This is not BASIC.) Here is a line by line analysis of the program:

1 DON'T...: Any statement which starts with DO NOT, PLEASE NOT, DON'T or PLEASE DON'T will simply be ignored by INTERCAL. The rest of the statement does not need to be valid INTERCAL syntax because since you don't want to do it the compiler doesn't have to understand it.
2 PLEASE NOTE...: Because of the rule above, many INTERCAL programs include 'PLEASE NOTE' as a way of including comments. INTERCAL only cares about the first three letters of NOT, so PLEASE NOTCH MY BELT would also be ignored.
Line two also introduces the idea of a label, (1), which in this iteration is not actually used. Labels are given numbers, not names.
In keeping with good programming practices, the comment 'PLEASE NOTE THAT WE ARE NOT PROMPTING' is 100% accurate. If you have read 'Hello, world' earlier, you will know that writing character output is just not worth the effort. Usability is overrated.
3 DO WRITE IN .1: In this statement we are asking INTERCAL to accept numeric input from the user, storing the input in the 16-bit variable .1. 16-bit variables are represented with the 'spot' (.), whilst 32-bit variables are represented with the 'two spot' (:). In INTERCAL you have 65535 16-bit variables and the same number of 32-bit variables, from .1 to .65535 and :1 to :65535. Note that .1 and .001 are the same variable, but .1 and :1 are not.
4 DO READ OUT .001: In this statement we are asking INTERCAL to send the value of variable .001 (which is the same as .1, .01, etc) to the standard output. For your convenience, the number is output in Roman numerals.
5 DO GIVE UP: Ends the program.

If I compile and run the above program it will accept my input (eg. ONE TWO THREE), output the number (eg. CXXIII) and then exit. Too easy.

If at line 5 we insert the statement 'PLEASE DO (1) NEXT', the program will jump to our label (1) instead of exiting. The program will continue looping forever, which is certainly a step in the right direction of converting our Python program to INTERCAL.
The program continues looping until the user types in invalid input. For example if I type in the input 'WHAT IS UP DOC?', the program will respond:

ICL579I WHAT BASE AND/OR LANGUAGE INCLUDES WHAT?
ON THE WAY TO 4
CORRECT SOURCE AND RESUBNIT

I am not going to try to add input validation or error handling to this program because life is simply too short. But the program still falls short of the Python original - it does not exit if the input is equal to 1. We need an IF statement.

By now we should guess that INTERCAL will not have an IF statement, and we would be correct. In keeping with the 'unlike any other language' theme, there is nothing that really approximates an IF statement at all. It turns out that implementing an IF is quite a difficult task in INTERCAL.

Here is my the next iteration of our program, trying to get around INTERCAL's lack of an IF:
1         DON'T WORRY, BE HAPPY
2 DO (2) NEXT
3 (1) PLEASE NOTE THAT WE ARE NOT PROMPTING
4 DO WRITE IN .1
5 DO READ OUT .001
6 PLEASE RESUME .1
7 (2) DO (1) NEXT
8 DO GIVE UP
Explaining the additional lines:

2 DO (2) NEXT: When we added the DO (1) NEXT line earlier, you may have assumed that it was a BASIC-style GOTO. Unlike BASIC's GOTO, the position of the next statement after a DO (in this case line 3) is placed onto a 'NEXT' stack. This NEXT stack can be manipulated by the RESUME or FORGET statements, discussed later.
7 (2) DO (1) NEXT: This is the statement which the previous statement jumped to. We simply jump straight back to label (1). Note that this statement will also push the position of line 8, DO GIVE UP, onto the NEXT stack. At this point the NEXT stack will look like this:

Line 8
Line 3

6 PLEASE RESUME .1: This is the most important line in the program. When we reach this point we have the user's input in the variable .1 and have just sent it to the output. We need to decide whether to continue looping. The RESUME statement will evaluate the expression, in this case the value of .1, and pop that many items off the NEXT stack. It will then jump to the last item popped.
So if the user types in 'ONE' the program will pop the top item from the NEXT stack and then jump to Line 8, the end of the program. This is exactly what we wanted.
Alternatively, if the user types in 'TWO' (or maybe 'DALAWA') then two items will be popped and the program will jump to line 3. This is also exactly what we wanted, because the user will then continue the loop at line 3.

So we are finished right?

Um, no. If the user types anything other than ONE or TWO (or any number at all on the second iteration) then they will receive the following message:

ICL632I THE NEXT STACK RUPTURES. ALL DIE. OH, THE EMBARRASSMENT!
ON THE WAY TO 8
CORRECT SOURCE AND RESUBNIT

Oh dear, it seems we still have a bit more learning to do before we will have mastered the IF construct in INTERCAL. Unfortunately I am very sleepy, and also incredibly confused, so the completion of this program will need to wait for another day. Stay tuned.

Are you an INTERCAL guru? Please feel free to post the solution as a comment. (It will sure save me from figuring it out.)

Desperately waiting to see how this program is written in INTERCAL? Subscribe to the 'Diving into INTERCAL' feed and you will be the first to know.

Labels: , ,

4 Comments:

Blogger Magnus said...

I'm not an INTERCAL guru, but here is my attempt.

DON'T WORRY, BE HAPPY
PLEASE COME FROM (4)
(4) DO (1) NEXT
(3) DO .2 <- '?"!1~.1'~#1"$#1'~#3
DO (5) NEXT
(7) PLEASE DO NOTHING
(5) PLEASE RESUME .2
(1) PLEASE NOTE THAT WE ARE NOT PROMPTING
DO COME FROM (7)
DO WRITE IN .1
DO READ OUT .001
DO (3) NEXT
DO .2 <- "!1~#65534'~!1~#65534'"~#1
DO .2 <- '?.2$#1'~#3
DO (2) NEXT
(6) PLEASE DON'T ASK
(2) PLEASE RESUME .2
DO COME FROM (6)
DO GIVE UP

If you want to figure out how it works for yourself, stop reading now.

This program does two tests, one at line (3) which tests whether .1 is zero, and one after the jump to (3) which tests whether .1 is one. The basic idea is that you first select the number with itself: ".1~.1", which gives you all 1-valued bits flushed to the right. Then you select the rightmost bit. If it's zero, the number must be zero; else it's greater than zero. The same logic is used to test for one, except that ".1~#65534" is used, which is essentially .1 shifted one bit to the right.

So, now we have either 1 or 0, depending on whether to jump or not. However, RESUME can't take a 0-valued argument, so we need to add one to that number: thus we RESUME either one or two steps. I did that by intermingling the number with #1 (producing either 1 or 3), XORing the result (XOR is, of course, a unary operator in INTERCAL), and masking out the high bit by selecting with #3. The result is either 1 or 2, RESUME is happy, and the rest is just spaghetti.

March 19, 2007 at 8:45 AM  
Anonymous Anonymous said...

branching is for whimps.

April 22, 2007 at 7:37 PM  
Anonymous Anonymous said...

@Magnus:

That's a rather convoluted way of solving the situation, although it looks like it might work. Generally speaking, multiple tests in INTERCAL-72 are avoided because they're so utterly complicated; normal style would be to simply coerce all invalid input to valid input, which is possibly not as neat but a lot simpler to think about.

I strongly recommend the debugger in C-INTERCAL for figuring out what expressions like yours do; it has a command for explaining what an INTERCAL command does (if optimisation is turned on).

$ ick -byO magnusloop.i
1: DON'T WORRY, BE HAPPY
On C1: Abstained 1 time.
yuk007 e4
C1: Expression is (0x2 - (! .1))
yuk007 e13
C1: Expression is (! (! ((.1 & 0xfffe) >> 0x1)))
yuk007 e14
C1: Expression is ((.2 & 0x1) + 0x1)

At line (3), which is line 4, we can see instantly from this that we get 2 or 1 depending on whether the input is 0, which is what you're aiming for. Line 13 (the large test for 1) could be optimised better (I may need to add more idioms for that sort of thing), but it's clear that what you have there is a test for "0 or 1". The line after is a common INTERCAL idiom (did you come up with it yourself, or copy it from another source), and the optimiser shows that it is indeed doing what you wanted it to do (adding 1 to the argument, given that it only has one bit).

For testing for exact equality to 1, it would be usual to mingle with 1, xor, select every second bit, select against itself, and add 1 to the bottom bit:

1: DO .2 <- "?'"'?.1$#1'~'#0$#65535'"~"'?.1$#1'~'#0$#65535'"'$#1"~#3
On C1: Abstained 0 times.
yuk007 e1
C1: Expression is (0x2 - (.1 == 0x1))

Combining INTERCAL expressions into one line is IMO good practice; it makes them easier to optimise, and has the added advantage of being more confusing.

Incidentally, there are all sorts of more modern looping constructs available which would make this program easier. Sticking with the no prompt and butchered I/O for the time being, what do you think of this?

DO COME FROM CALCULATING
DO WRITE IN .1
DO READ OUT .1
(1) PLEASE NOTE This is the loop exit
DO .1 <- .1
DO COME FROM .1
PLEASE GIVE UP

(Note that this is not INTERCAL-72, because it relies on computed COME FROM; but INTERCAL-72's control models tend not to be the easiest to use.) This program has the advantage of involving no arithmetic or comparisons at all, and being easy to understand.

Is anyone still reading this blog, by the way? A new post would be interesting.

February 3, 2009 at 2:44 AM  
Blogger Seth Williams said...

Hey Clinton, your tutorial on INTERCAL was really a bit tricky. However the program was really simple to comprehend. Thanks for sharing. We make some Python tutorials as well which your readers may find useful at https://www.youtube.com/fireboxtraining

August 1, 2014 at 8:24 PM  

Post a Comment

Links to this post:

Create a Link

<< Home