The thETA language

Welcome to thETA

thETA stands for 'threaded ETA'. I describe here some extensions to the ETA language that give it fully-fledged multi-threading capability (well, kind of!). What's more, I have added this capability without colouring the purity of the language by increasing the number of significant instruction characters. And even more remarkably, the thETA interpreter is fully backward compatible - it will function perfectly on plain old ETA programs.

I have done this by utilising previously illegal instruction usages, such as divide by zero. There are three such instructions, described below:

'T' - Transfer - The 'forkif' instruction
This works in the same way the traditional 'T' instruction, except that if the line number parameter (the top item of the stack) is negative, the absolute value of this is taken and a new thread is started, beginning executing at that line. Note that the condition value is still respected - if it is zero then the fork will not occur.
A forked thread starts it life with a copy of the stack of its parent.
'E' - dividE - The 'returnvalue' instruction
Threads that have finished their work can just exit using the usual transfer to zero mechanism, or by falling off the end of the program. However, often you will want to return a value to the parent thread. To do this, you divide that value by zero. This causes the thread to exit, and the value to be retained ready when when that thread is collected by the parent.
'O' - Output - The 'collect thread output' instruction
If a thread exits using transfer to zero then the parent will know nothing about it - the thread died and that's the end of the matter. However, if the thread returned a value using the 'returnvalue' instruction described above, then the parent can collect this value using the 'O' instruction.
In this usage, 'O' takes one negative parameter. The absolute value of that parameter is taken, and that number of child-threads are collected (blocking if required). On completion, 'O' will push each of the return values on the stack, followed by the number of values it just pushed. The order in which the threads are collected is not necessarily known.
In the case where 'O' runs out of threads to collect, (if fewer values are returned than it was expecting, and there are no more running children), then 'O' returns with however many it got. This is the purpose of pushing the number of values returned onto the stack - it enables you to continue to manage the stack even with an uncertain number of thread returns.

About parents

Each thread is started by one parent. When a thread dies, its children are passed to its parent. If its parent is dead, then they are passed to its parent's parent, and so on. So a thread always has a parent that can collect it. In my implementation, calling 'O' actually causes all children threads that are dead to be cleared up - but this is really an implementation detail - you shouldn't care that there are loads of dead threads lying around making the place look untidy.

Program end

A thETA program will not terminate until all its threads are dead. To achieve this, my implementation needs to poll the threads to check their status. It does this once per second (if there are no higher priority threads running) - so there may be a delay of up to one second before the thETA interpreter exits.

Example

Here is a short example program to demonstrate the use of thETA

* Knuth TeX #1                                        BABY BAT: 50
  NURTURES nude: what?  1nternnet?                    BABY BAT: dec and goto 3 if nz, else goto 5
      An east 1nternaet!                              BABY BAT: fork to line 4, return to 2
  Nude hunt waxes bluntly, temptingly; Czech pussy blundered. BABY BAT: tx to 8 if not 9, else return val
* Knuth TeX #2                                        BABY BAT: 50
  NURTURES new hun: the TNT DECnet.                   BABY BAT: dec and goto 7 if nz, else exit
  Unencrypted, scorned, husks.  Gunmen ssess1on tense, but -- BABY BAT: wait and print value, goto 6
      Burns superbly!
  NURTURES new hunt: abject
  Sneer!                                              BABY BAT: return val

The program forks 50 threads, and waits for 50 to return one at a time. They each loop for a bit, then return a number from 0 - 49, which then gets added to 48 (ascii for zero) and printed. The exception is the thread for character '9', which waits for user input before returning. This demonstrates the asynchronous nature of the threads - all the others return first.

Interptreter

This is a modified version of my Ruby ETA interpreter. The modifications are quite small in size, mostly due to my being able to utilise Ruby's built in thread mechanism.

You can download the thETA interpreter here. Note that using Ruby 1.6.4 under Windows I suffered frequent crashes when running multiple threads. I recommend Ruby 1.6.5 or later.

thETA builder

Here is a modified version of the ETA builder that supports threads. There are three new instructions in thETA builder - forkif, threadreturn and threadcollect.

Here is a sample program that shows their usage:

# factorise any number below 23
require 'theta-rb'
def tryit(n,x)
  forkif (true) {
    forkif(true) {       # fork yet another thread just to prove it works
      eif (n % x == 0) {
        threadreturn(x)
      }
      eelse {
        threadreturn(0)
      }
    }
    threadcollect(1)
    threadreturn($threadResults[0]) # the global $threadResults is an EtaArray
  }                                 # with the return values in - currently limited
end                                 # to a max of 20 - see theta-rb.rb

eprint "Enter number to be factorised: "
n = EtaInt.new(input_number)
eprint "Forking threads...\n"
tryit(n,2)
tryit(n,3)
tryit(n,5)
tryit(n,7)
tryit(n,11)
tryit(n,13)
tryit(n,17)
tryit(n,19)
eprint "Collecting threads...\n"
threadcollect(8)
8.times {|z|
  eif ($threadResults[z] != 0) {
    eprint $threadResults[z], "\n"
  }
}
eexit
finish

And if that isn't enough for you, try this program, which is a nice demonstration of the concurrency you can achieve. This one seems to work better on a unix system rather than under windows, where oddly the output thread seems to block once you have started to type input - it resumes once you have pressed return.

# continuously prints a number and accepts commands 'u'
# or 'd' to increase or decrease the number
# just typing return exits
require 'theta-rb.rb'
x = EtaInt.new
z = EtaInt.new
forkif(true) {
  threadreturn(input)
}
ewhile(true) {
  forkif(z == 0) {
    eprint x
    threadreturn(0)
  }
  forkif(z != 0) {
    threadreturn(input)
  }
  threadcollect(1)
  z.val = $threadResults[0]
  eif (z > 0) {
    eif (z > ?d) {
      x.val = x + 1
    }
    eelse {
      x.val = x - 1
    }
    eif (z == ?\n) {
      eexit
    }
    z.val = input # chomp newline
  }
}
finish

Download the compiled thETA code for this here.

Acknowledgements

The name 'thETA' was coined by Mike Taylor, who also beautified the first thETA example program above. The idea of adding threads to ETA was due to a fine curry at the Elahee Restaurant, 218a Middle Lane, London, N8. Bring your own alcohol.

S.D.Sykes Feb 2002