Programming with Shapes: Clunk

Today's bit of pathology is a really silly, and really fun language called Clunk, with a downloadable package containing a perl implementation here. I'm
not sure that it's Turing compete, but my best guess is that it is. It's another two dimensional
language, but it's very different from any of the other 2d languages that we've look at, because it
doesn't rely on an instruction pointer moving around the playfield; instead, it computes by
creating an image by fitting together pieces according to some pre-determined rules.

A Clunk program consists of a file containing a set of shapes. A shape is a fully
connected two-dimensional figure of non-space characters. The shape can be made up of any visible characters you want - but digits and "@" characters have some special meanings. The sum of all
of the digits in a shape are called the shape's "connectitude". If the shape contains no
digits, then it's connectitude is 1. If a shape contains a zero, but no other digits,then its
connectitude is 0.

The way that a Clunk program works is that each step, it tries to place one figure onto the
field. In the first step, if any shape(s) in the program contain an "@" character,
then one of them is randomly selected and put onto the playfield. After that, shapes are
placed, one per step, until no more can be placed. Placement is done according to the following rules:

1. A shape must be placed so that any places where one of it's edges touch another shape's
   edge, the characters on the touching edges match.
2. A shape must be placed so that the number of places where it's edges
   touch other shapes is at least it's connectitude. (Note that this means that
   a shape with connectitude 0 can be always be placed, by putting them somewhere where
   there are no other shapes - so including a connectitude 0 shape means your program will never terminate.)

Clunk has no input or output. But effectively, it uses the final image on the playfield for out. Let's look at an example to make it clearer. Here's "Hello World" in Clunk:

@a-b-c-d-e-f-g-h-i-j-k-l-m#
~~~~~~~~~~~~~~~~~~~~~~~~~~~

  H    O   R
  a    e   j  ,
     L   O    f
  E  d   i
  b       L
      W   k
  L   h      .
  c        D m
           l

The program first places the shape with the "@" onto the field:

@a-b-c-d-e-f-g-h-i-j-k-l-m#
~~~~~~~~~~~~~~~~~~~~~~~~~~~

Then it tries to find other things to place. Each of the other shapes has one of the letters of "Hello world", and one of the letters from the initial shape. Each shape has connectitude one, and each one can only possibly fit in one place. So all of the pieces get places. and we end up with:

  H E L L O ,   W O R L D .
  a b c d e f   h i j k l m                                                      
@a-b-c-d-e-f-g-h-i-j-k-l-m# 
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~    

Here's a nifty but silly program - it draws an infinite maze-like figure.

 c    d
c/-- -\d
 |    | 
 |    |
 |    | 
f\-- -/e
 f    e

This is the one that I think is incredibly cool. I'm not going to explain it - because if you download the interpeter and run it, watching it run shows you exactly how it works, far more clearly than I can do it. This is a binary adder written entire in strange shapes.

@O                    
@|                    
@|I   |O   |I   |O   |b
@|    |    |    |    |b
@|.O  |.I  |.I  |.O  |b
@|    |    |    |    |b
@aaaaaaaaaaaaaaaaaaaaaa

  O      I
  _      _
O.3.O  I.3.O
  .      .
 O.     O.
  .      .
  O      O

  I      O
  _      _
O.3.O  I.3.I
  .      .
 O.     O.
  .      .
  I      I

  I      O
  _      _
O.3.O  I.3.I
  .      .
 I.     I.
  .      .
  O      O

  O      I
  _      _
O.3.I  I.3.I
  .      .
 I.     I.
  .      .
  I      I

Here's the result when it's done. Note that it's going backwards - the least significant bit is to the left:

    I    I    O    I                          
    _    _    _    _                          
@OO.3.OO.3.OO.3.II.3.O                        
@|  .    .    .    .                          
@|II. |OO. |II. |OO. |b                       
@|  . |  . |  . |  . |b                       
@|.OO |.II |.II |.OO |b                       
@|    |    |    |    |b                       
@aaaaaaaaaaaaaaaaaaaaaa