Threaded Intercal

News!

Release version 0.7 of the Threaded Intercal compiler is now available! Download it now.

Introduction:

This document assumes that the reader already comprehends the beauty of the INTERCAL programming language. New-comers are directed to the INTERCAL Resources Page for an introduction to the wonderful world of the Compiler Language With No Pronounceable Acronym. Those of you who have already completed your initiation, read on...

The concept of Threaded Intercal was born in late 1997 out of discussion on the alt.lang.intercal newsgroup regarding the unusual restrictions placed on COME FROM statements in C-INTERCAL, vis:

It is an error for more than one COME FROM 
to refer to the same (label).

            -- The INTERCAL Programming Language
               Revised Reference Manual, 1997
While speculating why such an arbitrary restriction might exist, it struck those discussing the issue that the natural interpretation of two COME FROM statements with the same origin was to create two processes or threads, each starting at one of the COME FROMs. So Threaded Intercal was born.

It next became necessary to work out means of inter-thread synchronisation and communication. Various techniques, mostly based on shared data structures, were discussed but none seemed satisfactory to this author, as they all seemed too similar to existing methods in other, boring programming languages, and none had that special uniqueness that was peculiar to INTERCAL.

Then, in April 1998, a revelation struck the author. He saw a way to both solve the communication problem, and revitalise a part of the original INTERCAL language which had undeservedly suffered from general disuse.

The ABSTAIN and REINSTATE statements in original INTERCAL are widely admired as examples of that special programming style which is unique to INTERCAL. However, in reality they are not as widely used as they might be. The sad truth is that INTERCAL programs can be written in such a way that these wonderful statements are never actually necessary.

Threaded Intercal changes this. ABSTAIN and REINSTATE are revived to their former glory by becoming the essential foundation of inter-thread communication. There are no shared data-structures. There are no message-passing systems. There is just one body of shared code, and the ABSTAIN and REINSTATE functions to manipulate it. All communication between threads is done by turning on and off lines of the shared code base.

Finally, in order to implement synchronisation, a form of Test-and-Set operation was required. No existing INTERCAL statement could provide this behaviour, so a new command, or style of command, has been introduced. The "DO something ONCE" operation, extends the shared code-base communication technique, by enabling a process to execute a statement and ABSTAIN from it in one atomic action. Not only does this allow thread synchronisation, it is also a powerful command in its own right, and has potential uses in making even single-threaded programs more wonderfully convoluted than before.

A more detailed explanation of the proposal is outlined below, with examples. An implementation of the language, with sample source code, can be found at: ftp://ftp.cse.unsw.edu.au/pub/users/malcolmr/thick7.tgz


Proposed standard for Threaded Intercal, Version 0.2

This is a preliminary outline only. Discussion is invited.

Private Data:

Each variable has its own set of variables which are private to that thread. No shared data mechanisms are available.

Public Code:

All threads share the same code base. When one thread ABSTAINS FROM or REINSTATES a statement, all threads are affected.

Creating threads:

Initially there is only one thread. New threads are created by using COME FROM statements. Unlike standard C-Intercal, multiple COME FROM statements are allowed for a particular line number. If more than one such COME FROM exists, then the thread shall split into several threads, one for each COME FROM.

Each thread shall have all variables instantiated as they were before the COME FROM, and one thread will start execution at each COME FROM.

Example:

        (1)  DO .1 <- #1

        (2)  DO COME FROM (1)
             PLEASE DO .2 <- #1

             ...

        (3)  DO COME FROM (1)
             PLEASE DO .2 <- #2

             ...
A single thread starts executing at (1). After setting .1 to #1, it splits into two threads, each of which has a local copy of the data from the old thread (so both see .1 equal to #1). One thread starts execution at (2) and the other at (3). The first thread then sets .2 to #1 and the second set .2 to #2, each in its local data space.

Destroying threads:

A thread is destroyed when it hits a GIVE UP statement. Execution of a Threaded Intercal program ends when all threads are destroyed.

Atomic Actions:

As the program code is shared, all reads and writes to the code base need to be atomic. Thus the following operations are defined as atomic actions: Note that an ABSTAIN or REINSTATE statement that affects multiple lines (such as ABSTAIN FROM STASHING) is not a single atomic action.

As the input and output streams are also shared, READ and WRITE statements are also atomic.

Synchronisation:

In order to do inter-thread synchronisation, some kind of "Test-and-Set" operation is necessary. The following addition to Intercal is proposed for this purpose.

Any INTERCAL statement can have one of the tags ONCE or AGAIN appended to it. These tags make lines of code atomically self-abstaining or self-reinstating. A line with a ONCE tag will have its normal effect on the first execution, but will also have its abstention setting reversed, and the tag will become an AGAIN tag. A statement with an AGAIN tag has its normal effect, until such time as its abstention status is changed by an ABSTAIN or REINSTATE statement, at which point it will have its tag changed back to ONCE.

Example:

        (1)   DO .1 <- #1 ONCE
will set .1 to #1 on the first execution, and then change to:
        (1)   DO NOT .1 <- #1 AGAIN
which will have no effect, until such time as it is REINSTATED, when it shall revert to its earlier form.

Similarly:

        (1)   DO NOT .1 <- #1 ONCE
will have no effect on .1 on the first execution, but will change to:
        (1)   DO .1 <- #1 AGAIN
which will set .1 to #1 on every successive execution, until it is ABSTAINED, at which point it will revert to the previous form.

The self-abstaining and self-reinstating action of these statements is atomic, so that they may be used as synchronisation commands between threads. Implementing a binary semaphore with these commands is straightforward.

In the eyes of the proposer, however, the usefulness of these forms is not simply in programming synchronisation. There is no reason why they should not be used in single-threaded applications as a powerful means to of obfuscation.

Inter-Thread Communication:

In order to preserve its uniqueness as a language, Threaded Intercal does not have any kind of shared data structure for communicating between threads. Many systems have been considered but they all appear too similar to other concurrent languages.

Instead Threaded Intercal programs communicate by modifying their shared code base. This, it is felt, is keeping with the true spirit of Intercal, and has the added bonus of promoting the use of the ABSTAIN/REINSTATE commands, which appear to be under-used in Intercal programs to date. (In fact, it is a sad fact in the author's opinion that traditional Intercal programs can be written in such a way that ABSTAINING is never actually necessary.)

Example: Single bit comms can be done as follows.

        (100) PLEASE NOTE: Send the LSB of .1

              PLEASE STASH .2

              DO .2 <- '?.1$#1'~'#1$#1'
              DO (102) NEXT
        (101) DO REINSTATE (201)
        (102) DO (199) NEXT
              DO ABSTAIN FROM (201)
              DO FORGET #1

              PLEASE COME FROM (101)
              DO RETRIEVE .2
              DO RESUME #1
        (199) DO RESUME .2

        (200) PLEASE NOTE: Receive a message into LSB of .1

              DO .1 <- #0
        (201) PLEASE DO NOT .1 <- 'V.1$#1'~'#0$#65535'
              DO RESUME #1
Extending this to a 16-bit channel is left as an exercise to the reader.

Input/Output:

All threads share input and output streams.

For the Turing Text model, there is a single input tape and a single output tape, shared by all threads. Note that this means that the character input or output is given as an offset from the last character read or written by the last thread to do so.


History:

Version 0.2 - 1/6/98

Modified synchronisation tags, adding the AGAIN tag to provide more flexible operation. Inspired by Kyle Dean.

Version 0.1 - 28/5/98

Original standard authored by Malcolm Ryan.


Other Intercal extensions


Malcolm Ryan - malcolmr@cse.unsw.edu.au
Last updated: Wednesday, 09-Jun-2004 12:02:40 AEST