Documentation‎ > ‎

Concatenative Programming



Introduction

This is an introduction to concatenative programming and its various idioms using Niue.  We also see how Niue is not tied down by just a single paradigm.

In concatenative programming, computations take place by composing functions (or words) that operate on a single piece of data.  In Niue, this single piece of data is a stack. So Niue is also a stack language.  This implies that Niue follows the postfix notation, where words are specified after the values they work on, as you see in the following simple arithmetic operation:

2 3 + .
=> 5

Words, literals and the data stack

Niue reads a sequence of words and literals from the input stream.  Literals are pushed to the stack, while words are executed.  A word is either a primitive operation or one that is defined by the user in terms of primitives and literals.  Values are passed between words using the data stack.  There are no named parameters or return statements.  To see how this helps in making programs concise, compare the following C function with its Niue equivalent:

/* Returns the square of an integer. */
int square (int x)
{
    return x * x;
}

This function can be used as:

int s = square (10);
printf ("square of 10 = %d\n", s);

=> square of 10 = 100

Now the same function defined as a Niue word:

[ dup * ] 'square ; 

The definition of square does not have any named parameters and there are no return statements.  It expects a number on the stack.  That number is duplicated (using the primitive word dup) and the two values on the top of the stack are multiplied to produce the result, which is left on the stack to be used by the words that follow.  As there is no explicit argument passing, it is possible to compose programs that look like statements in English.  This leads to succinct programs.

"square of 10 is" . 10 square .

=> square of 10 is 100

Having a stack as a center point of data exchange has other advantages as well, some of which are discussed below.

Multiple return values

To return multiple values from a function, programmers usually pack those values into a special data structure.  In Niue this is more straightforward.  Words simply push as many values as they want to the stack.  For instance, the following python function needs the help of a tuple to return multiple values:

def quotient_and_remainder (x, y):
     q = x / y
     r = x % y
     return (q, r)

# usage
quotient_and_remainder (16, 5)
=> (3, 1)

The user of quotient_and_remainder has to be aware of the format in which the result will be returned.  He should also deal with the details of unpacking the result.  Some time in the future, if the author of quotient_and_remainder decides to use a new data structure instead of tuple, all clients has to be changed accordingly.  This is not an issue in Niue as there is a consistent method for returning single and multiple values.  Let us rewrite quotient_and_remainder in Niue:

[ 2dup / rot rot mod swap ] 'quotient-and-remainder ; 

( usage )
16 5 quotient-and-remainder . .
=> 3 1

Note: Niue provides the /mod primitive, which does the same job as quotient-and-remainder.

Keyword arguments

Niue allows the data stack to be used as a property list (plist) of key-value pairs.  The value associated with a key can be pushed to the top of the stack using the get primitive word.  This feature enables us to use keyword parameters.  For instance, think about a word that connects to an HTTP server.  It expects two values on the stack: URL and port.  The following implementation of http-connect treats the  stack as a plist.  It consumes two keyword arguments: 'url and 'port.  If 'port is not specified, the default value of 80 is used. 

[ len 'count-args ;
  "Connecting to" . 'url get . "on port" .
  'port get
  ( if 'port is on the stack, the length of the stack will increment by one )
  len count-args = [ 80 . ] if
                   [ . ] else 
] 'http-connect ;


( usage )

'url 'www.test.com 'port 8080 http-connect
=> Connecting to www.test.com on port 8080

.clr ( clear the stack before passing new values )

'url 'www.test.com http-connect
=> Connecting to www.test.com on port 80

Adapting other paradigms

Niue can easily adapt itself to other paradigms.  Niue is a multi-paradigm language. 

Object Orientation

We can use code blocks to simulate objects that can respond to "messages" and keep track of their own "private state".  Here is a simple point object that has two private variables - x and y.

( a utility to check for valid messages )
[ swap dup rot equals ] 'message? ;

( the point object )
[ 0 'x ;; 0 'y ;; ( state variables x and y, initialized to 0 )
  ( the point object can respond to four messages, two to retrieve the private state
    and two that sets the private state )
  'x message? [ x . ] when
  'y message? [ y . ] when
  'x; message? [ swap 'x ; ] when
  'y; message? [ swap 'y ; ] when
, ] 'point ;

( some interactions with the point object )
'x point
=> 0
'y point
=> 0
10 'x; point
'x point
=> 10
100 'y; point
'y point
=> 100

One problem with the point code block is that it is a singleton, i.e, there can be only one point in the whole system.  If we need more points, we should rewrite the point definition, evaluate it and assign the value to a new variable.  The primitive operation, eval, comes to our rescue here.  eval can execute Niue code represented as strings.  So all we have to do is to wrap our point code block in a string.  When we need a new point object, we just apply eval to this string.

"[ 0 'x ;; 0 'y ;;
  'x message? [ x . ] when
  'y message? [ y . ] when
  'x; message? [ swap 'x ; ] when
  'y; message? [ swap 'y ; ] when
, ]" 'point ;

( create two instances of point and interact with them )
point eval 'p1 ;
point eval 'p2 ;

'x p1 'x p2
=> 0 0
10 'x; p1 20 'x; p2
'x p1 'x p2
=> 10 20
'y p1 'y p2
=> 0 0
100 'y; p1 200 'y; p2
'y p1 'y p2
=> 100 200

Functional power

Niue is not a pure functional language because it has mutable variables.  Still, it is possible to do functional programming in Niue.  We can emulate "higher-order functions" with named code blocks.  For example, here is the Lisp map function implemented in Niue.  It expects the bottom element of the stack to be a code block.  This block is applied for each of the remaining elements on the stack.  (Note: This is just one way to implement map).

[ [ , len 1 - at ! ] len 3 - times swap , ] 'map ;

The following code snippet use map to add a list of numbers:

[ + ] 10 20 30 40 50 map .
=> 150

It is possible to do pure functional programming in Niue by completely avoiding variables and abstracting all objects as code blocks.  Even if you use variables, bind then using ;;.  

More reading

  1. Concatenative.org.
  2. The papers and articles by Manfred von Thun.
  3. Other concatenative languages: Factor, Joy, Forth.
  4. The two great Forth books by Leo Brodie: Starting Forth and Thinking Forth.