QaSaC

QaSaC ("Queues and Stacks and Combinators", the elements from which the language is built) is a cross between a stack-based concatenative language like Forth and Joy, and a graphical dataflow language like PureData.

A program consists of a number of "nodes" which run asynchronously and are wired together through queues.

Each node has its own stack, and executes a short, single-line sub-program of the order of magnitude of a Forth "word" (a couple of dozen symbols).

A node's sub-program is split into two phases : an initialization phase, and an looping phase. The initialization phase executes once when the node starts running, and from then on the node cycles through the series of instructions in its looping phase. These instructions pull data from its input queues, manipulating it with the help of its local stack, and sending it on through its output queues. Each node runs asynchronously, and blocks while waiting for new input.

The whole program ends when the final output channel (normally sent to standard out) has pulled a specified number of outputs.

Like Joy, QaSaC can work with blocks of code (ie. sub-lists of instructions which are "quoted" in the Lisp sense). Blocks can be passed as data from one node to another, and then unquoted and executed elsewhere. Blocks are normally unquoted by "combinators", that is, higher order operators that work with blocks of code that have previously been placed on the stack. These are more or less the equivalent of Lisp "forms". The most common is COND (a conditional combinator, the equivalent of Joy's "IF" though named for Lisp's "cond"), and LINREC (a linear recursion combinator borrowed from Joy that can be used to construct various kinds of looping).

Here is a minimal QaSaC program. It consists of just one node which produces the sequence of integers, counting upwards from 0. Eventually, wiring together the individual nodes into the flow-chart will be done through a graphical editor, but we have a somewhat clunky text syntax, just to have something to work with.

The line starting ! declares the named channels which a QaSaC program demands from its environment. A line starting with = defines extra named channels within the program. Finally we have a series of nodes, each of which is defined in two lines : the first wires up the internal channel names to the global channel names. The second is the actual code of the node's sub-program.

Locally, nodes have three predefined input channels called X, Y and Z. And two predefined output channels called -> and +>

The node's code has an initiation phase and a looping phase. The vertical bar | separates the two.

Simple counter

! out 

{-> out}
0 | DUP -> 1 +  

The initialization phase consists of putting a 0 on the stack. The infinite loop then duplicates the top of the stack, pops the top of stack and sends it to the output channel (which is wired to global "out"), the program puts a 1 on the stack and executes the + operator to add the top two items on the stack, the 0 and the 1. The resulting 1 is placed back on the stack and we return to the beginning of the looping section ...

Now let's wire a filter to this counter

! out
= c1

{-> c1}
0 | DUP -> 1 +

{X c1} {-> out}
X DUP [->] SWAP 2 % 0 == [DROP] SWAP COND

Here we create a second, internal channel called c1. We connect the output of our counter to it.

c1 feeds into the second node which filters the stream for even numbers. This node is wired with X as the local name for c1. So X pulls the next available value from c1 and puts in on the stack. We duplicate it. Then place a block on the stack. The block contains the instruction to output the top of the stack to ->, but we aren't executing it yet. We now SWAP the top two items on the stack so we have <x, [->], x> where x is the number pulled from the input queue. We now place 2 on the stack and execute the % (modulus) operator. If x was divisible by two we get a 0 on top of the stack, if not we get 1.

Now we place a second 0 and execute the equality test == to put either a True or False on the top of the stack which now looks, for example, like this <12, [->], True> (if x was 12). We place the block containing DROP to make <12, [->], True, [DROP]> and swap the top two to get <12,[->],[DROP],True> ... we are now set up to use the COND combinator. This combinators takes the top three items from the stack. The top is assumed to be a boolean. If it's true we execute the third ("leftmost" when looking at our representation of the stack, it's more intuitive to read this way around) block. If it's false we execute the second.

In the current example, 12 is divisible by 2, and the boolean is True, so COND executes the block of code containing [->]. The three arguments to COND are already gone, so the filter now outputs the number 12. Had we had the number 13 <13,[->],[DROP],False> then the COND would have executed the [DROP] block (ie. dropping the top of the stack without output.)

Implementations

QaSaC is work in progress. The interpreter is written in Clojure, and can be found at https://github.com/interstar/qasac