Programming with Shapes: Clunk

Mar 23 2007 Published by under pathological programming

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

No responses yet

  • Compare StarLogo TNG. From their Tutorial page:

    In StarLogo TNG, you write your programs using blocks that fit together like a jigsaw puzzle. Each block has a different command and has different shapes to help your figure out what they can connect to. the blocks are "created" in the Block Factory. You can use blocks created in the Block Factory to create your program.

    People who have used it tell me that it's easy to get started and do simple things, but the difficulty of shaping the pictorial code increases faster than the complexity of the problem being solved.

  • Probably Turing complete by Wang tiling theorems.

  • Brent says:

    Definitely Turing complete. In this paper the authors show how to construct a tileset which effectively simulates a Turing machine, and it's pretty obvious how that could be translated into Clunk. nifty!

  • Antendren says:

    Can shapes be rotated and reflected, or do they have to be placed as they appear in the program?
    Also, how can the maze figure begin? There's nothing with an "@" or connectitude 0.

  • Mark C. Chu-Carroll says:

    Antendren:
    No, no rotation or reflection - pieces are placed exactly as they appear in the original program.
    If none of the shapes have an "@" character, then all shapes are treated as possible initial shapes.

Leave a Reply