Archive for the 'pathological programming' category

The Wrong Way To Write Concurrent Programs: Actors in Cruise

Jan 20 2012 Published by under pathological programming

I've been planning to write a few posts about some programming stuff that interests me. I've spent a good part of my career working on systems that need to support concurrent computation. I even did my PhD working on a system to allow a particular style of parallel programming. It's a really hard problem - concurrency creates a host of complex issues in how systems behave, and the way that you express concurrency in a programming language has a huge impact on how hard it is to read, write, debug, and reason about systems.

So, like I've said, I've spent a lot of time thinking about these issues, and looking at various different proposed solutions, as well as proposing a couple of my own. But I really don't know of any good writeup describing the basics of the most successful approaches for beginners. So I thought I could write one.

But that's not really today's post. Todays post is my version of a train-wreck. Long-time readers of the blog know that I'm fascinated with bizarre programming languages. So today, I'm going to show you a twisted, annoying, and thoroughly pointless language that I created. It's based on one of the most successful models of concurrent programming, called Actors, which was originally proposed by Professor Gul Agha of UIUC. There've been some really nice languages built using ideas from Actors, but this is not one of them.

The language is called "Cruise". Why? Because it's a really bad Actor language. And what name comes to mind when I think of really, really bad actors with delusions of adequacy? Tom Cruise.

You can grab my implementation from github. Just so you know, the code sucks. It's something I threw together in my spare time a couple of years ago, and haven't really looked at since. So it's sloppy, overcomplicated, probably buggy, and slow as a snail on tranquilizers.

Quick overview of the actor model

Actors are a theoretical model of computation, which is designed to describe completely asynchronous parallel computation. Doing things totally asynchronously is very strange, and very counter-intuitive. But the fact of the matter is, in real distributed systems, everything *is* fundamentally asynchronous, so being able to describe distributed systems in terms of a simple, analyzable model is a good thing.

According to the actor model, a computation is described by a collection of things called, what else, actors. An actor has a mailbox, and a behavior. The mailbox is a uniquely named place where messages sent to an actor can be queued; the behavior is a definition of how the actor is going to process a message from its mailbox. The behavior gets to look at the message, and based on its contents, it can do three kinds of things:

  1. Create other actors.
  2. Send messages to other actors whose mailbox it knows.
  3. Specify a new behavior for the actor to use to process its next message.

You can do pretty much anything you need to do in computations with that basic mechanism. The catch is, as I said, it's all asynchronous. So, for example, if you want to write an actor that adds two numbers, you can't do it by what you'd normally think of as a function call. In a lot of ways, it looks like a method call in something like Smalltalk: one actor (object) sends a message to another actor, and in response, the receiver takes some action specified by them message.

But subroutines and methods are synchronous, and nothing in actors is synchronous. In an object-oriented language, when you send a message, you stop and wait until the receiver of the message is done with it. In Actors, it doesn't work that way: you send a message, and it's sent; that's it, it's over and done with. You don't wait for anything; you're done. If you want a reply, you need to send the the other actor a reference to your mailbox, and make sure that your behavior knows what to do when the reply comes in.

It ends up looking something like the continuation passing form of a functional programming language: to do a subroutine-like operation, you need to pass an extra parameter to the subroutine invocation; that extra parameter is the *intended receiver* of the result.

You'll see some examples of this when we get to some code.

Tuples - A Really Ugly Way of Handling Data

This subtitle is a bit over-the-top. I actually think that my tuple notion is pretty cool. It's loosely based on how you do data-types in Prolog. But the way that it's implemented in Cruise is absolutely awful.

Cruise has a strange data model. The idea behind it is to make it easy to build actor behaviors around the idea of pattern matching. The easiest/stupidest way of doing this is to make all data consist of tagged tuples. A tagged tuple consists of a tag name (an identifier starting with an uppercase letter), and a list of values enclosed in the tuple. The values inside of a tuple can be either other tuples, or actor names (identifiers starting with lower-case letters).

So, for example, Foo(Bar(), adder) is a tuple. The tag is "Foo". It's contents are another tuple, "Bar()", and an actor name, "adder".

Since tuples and actors are the only things that exist, we need to construct all other types of values from some combination of tuples and actors. To do math, we can use tuples to build up Peano numbers. The tuple "Z()" is zero; "I(n)" is the number n+1. So, for example, 3 is "I(I(I(Z())))".

The only way to decompose tuples is through pattern matching in messages. In an actor behavior. message handlers specify a *tuple pattern*, which is a tuple where some positions may be filled by{em unbound} variables. When a tuple is matched against a pattern, the variables in the pattern are bound to the values of the corresponding elements of the tuple.

A few examples:

  • matching I(I(I(Z()))) with I($x) will succeed with $x bound to I(I(Z)).
  • matching Cons(X(),Cons(Y(),Cons(Z,Nil()))) with Cons($x,$y) will succeed with $x bound to X(), and $y bound to Cons(Y(),Cons(Z(),Nil())).
  • matching Cons(X(),Cons(Y(),Cons(Z(),Nil()))) with Cons($x, Cons(Y(), Cons($y, Nil()))) will succeed with $x bound to X(), and $y bound to Z().
  • Code Examples!

    Instead of my rambling on even more, let's take a look at some Cruise programs. We'll start off with Hello World, sort of.


    actor !Hello {
      behavior :Main() {
        on Go() { send Hello(World()) to out }
      }
      initial :Main
    }
    
    instantiate !Hello() as hello
    send Go() to hello
    
    

    This declares an actor type "!Hello"; it's got one behavior with no parameters. It only knows how to handle one message, "Go()". When it receives go, it sends a hello world tuple to the actor named "out", which is a built-in that just prints whatever is sent to it.

    Let's be a bit more interesting, and try something using integers. Here's some code to do a greater than comparison:


    actor !GreaterThan {
      behavior :Compare() {
        on GT(Z(),Z(), $action, $iftrue, $iffalse) {
          send $action to $iffalse
        }
        on GT(Z(), I($x), $action, $iftrue, $iffalse) {
          send $action to $iffalse
        }
        on GT(I($x), Z(), $action, $iftrue, $iffalse) {
          send $action to $iftrue
        }
        on GT(I($x), I($y), $action, $iftrue, $iffalse) {
          send GT($x,$y,$action,$iftrue,$iffalse) to $self
        }
      }
      initial :Compare
    }
    
    actor !True {
      behavior :True() {
        on Result() { send True() to out}
      }
      initial :True
    }
    
    actor !False {
      behavior :False() {
        on Result() { send False() to out}
      }
      initial :False
    }
    
    instantiate !True() as true
    instantiate !False() as false
    instantiate !GreaterThan() as greater
    send GT(I(I(Z())), I(Z()), Result(), true, false) to greater
    send GT(I(I(Z())), I(I(I(Z()))), Result(), true, false) to greater
    send GT(I(I(Z())), I(I(Z())), Result(), true, false) to greater
    
    

    This is typical of how you do "control flow" in Cruise: you set up different actors for each branch, and pass those actors names to the test; one of them will receive a message to continue the execution.

    What about multiple behaviors? Here's a trivial example of a flip-flop:


    actor !FlipFlop {
      behavior :Flip() {
        on Ping($x) {
          send Flip($x) to out
          adopt :Flop()
        }
        on Pong($x) {
          send Flip($x) to out
        }
      }
      behavior :Flop() {
        on Ping($x) {
          send Flop($x) to out
        }
        on Pong($x) {
          send Flop($x) to out
          adopt :Flip()
        }
      }
      initial :Flip
    }
    
    instantiate !FlipFlop() as ff
    send Ping(I(I(Z()))) to ff
    send Ping(I(I(Z()))) to ff
    send Ping(I(I(Z()))) to ff
    send Ping(I(I(Z()))) to ff
    send Pong(I(I(Z()))) to ff
    send Pong(I(I(Z()))) to ff
    send Pong(I(I(Z()))) to ff
    send Pong(I(I(Z()))) to ff
    
    

    If the actor is in the ":Flip" behavior, then when it gets a "Ping", it sends "Flip" to out, and switches behavior to flop. If it gets point, it just sents "Flip" to out, and stays in ":Flip".

    The ":Flop" behavior is pretty much the same idea, accept that it switches behaviors on "Pong".

    An example of how behavior changing can actually be useful is implementing settable variables:


    actor !Var {
      behavior :Undefined() {
        on Set($v) { adopt :Val($v) }
        on Get($target) { send Undefined() to $target }
        on Unset() { }
      }
      behavior :Val($val) {
        on Set($v) { adopt :Val($v) }
        on Get($target) { send $val to $target }
        on Unset() { adopt :Undefined() }
      }
      initial :Undefined
    }
    instantiate !Var() as v
    send Get(out) to v
    send Set(I(I(I(Z())))) to v
    send Get(out) to v
    
    

    Two more programs, and I'll stop torturing you. First, a simple adder:


    actor !Adder {
      behavior :Add() {
        on Plus(Z(),$x, $target) {
          send $x to $target
        }
        on Plus(I($x), $y, $target) {
          send Plus($x,I($y), $target) to $self
        }
      }
      initial :Add
    }
    
    actor !Done {
      behavior :Finished() {
        on Result($x) { send Result($x) to out }
      }
      initial :Finished
    }
    
    instantiate !Adder() as adder
    instantiate !Done() as done
    send Plus(I(I(I(Z()))),I(I(Z())), out) to adder
    
    

    Pretty straightforward - the only interesting thing about it is the way that it sends the result of invoking add to a continuation actor.

    Now, let's use an addition actor to implement a multiplier actor. This shows off some interesting techniques, like carrying auxiliary values that will be needed by the continuation. It also shows you that I cheated, and added integers to the parser; they're translated into the peano-tuples by the parser.


    actor !Adder {
      behavior :Add() {
        on Plus(Z(),$x, $misc, $target) {
          send Sum($x, $misc) to $target
        }
        on Plus(I($x), $y, $misc, $target) {
          send Plus($x,I($y), $misc, $target) to $self
        }
      }
      initial :Add
    }
    
    actor !Multiplier {
      behavior :Mult() {
        on Mult(I($x), $y, $sum, $misc, $target) {
          send Plus($y, $sum, MultMisc($x, $y, $misc, $target), $self) to adder
        }
        on Sum($sum, MultMisc(Z(), $y, $misc, $target)) {
          send Product($sum, $misc) to $target
        }
        on Sum($sum, MultMisc($x, $y, $misc, $target)) {
          send Mult($x, $y, $sum, $misc, $target) to $self
        }
      }
      initial :Mult
    }
    
    instantiate !Adder() as adder
    instantiate !Multiplier() as multiplier
    send Mult(32, 191, 0, Nil(), out) to multiplier
    
    

    So, is this Turing complete? You bet: it's got peano numbers, conditionals, and recursion. If you can do those three, you can do anything.

3 responses so far

The Glorious Horror of TECO

Nov 30 2010 Published by under pathological programming, Uncategorized

In my oh-so-abundant free time, I've been working on my own little text editor. And one of my motivations is TECO: one of the oldest, and one of the very best, ever written. It's both a text editor and a programming language - and, in fact, that's exactly what made it such a brilliant tool. So much of the drudgery of programming is stuff that really could be done by a program. But we've spent so much time learning to be fancy that we've lost track of that. Nowadays, you can write an emacs lisp program to do the stuff you used to do in TECO; only it's awkward enough that you usually don't.

The problem, though, with just re-implementing TECO with a modern UI is that it was designed in a different time. When TECO was written, every byte was critical. And so the language, the syntax, the structure, it was completely ridiculous. And, as a result, it became the world's most useful pathological programming language. It's a glorious, hideous, wonderful, horrific piece of computing history

TECO is one of the most influential pieces of software ever written. If, by chance, you've ever heard of a little editor called "emacs"; well, that was originally a set of editor macros for TECO (EMACS = Editor MACroS). As a language, it's both wonderful and awful. On the good side, The central concept of the language is wonderful: it's a powerful language for processing text, which works by basically repeatedly finding text that matches some kind of pattern, taking some kind of action when it finds it, and then selecting the next pattern to look for. That's a very natural, easy to understand way of writing programs to do text processing. On the bad side, it's got the most god-awful hideous syntax ever imagined.

Continue Reading »

43 responses so far

Two Dimensional Pathological Beauty: SNUSP

Sep 10 2009 Published by under pathological programming

I'm currently away on a family vacation, and as soon as vacation is over, I'm off on a business trip for a week. And along the way, I've got some deadlines for my book. So to fill in, I'm recycling some old posts. I decided that it's been entirely too long since there was any pathological programming 'round these parts, so I'm going to repost some of my favorites.

Todays programming language insanity is a real delight - it's one
of my all-time favorites. It's a language
called SNUSP. You can find the language specification here,
a compiler, and
an interpreter embedded
in a web page
. It's sort of like a cross between Befunge
and Brainfuck,
except that it also allows subroutines. (And in a variant, threads!) The
real beauty of SNUSP is its beauty: that is, programs in SNUSP are actually
really quite pretty, and watching them run can be positively entrancing.

Continue Reading »

5 responses so far

Two-Dimensional Pathology: Befunge

Sep 08 2009 Published by under pathological programming

I'm currently away on a family vacation, and as soon as vacation is
over, I'm off on a business trip for a week. And along the way, I've got some
deadlines for my book. So to fill in, I'm recycling some old posts. I decided
that it's been entirely too long since there was any pathological programming
'round these parts, so I'm going to repost some of my favorites.

Today, we're going to take a look at a brilliant language called Befunge.
Befunge is the work of an evil genius named Chris Pressey.

Normal programming languages are based on a basically one-dimensional
syntax; the program is a string, a sequence of characters, and it's processed
by reading that string in a straight-ahead fashion. But that's not Befunge!
It's got a two-dimensional syntax. Befunge is something like a two-dimensional
turing machine: the program is written on a two dimensionaltorus called the playfield. Each
instruction in Befunge is a single character, and where it's located on the
torus is crucial - control is going to move either up/down or left/right
on the torus. All of the control flow is expressed by just changing the direction that
the head moves over the torus.

(In case you're not familiar with a torus, it's what you get
if you take a very flexible sheet of paper, and roll it so that you connect
the top edge to the bottom, and then roll that tube so that you connect the
left edge to the right. You get a donut shape where moving up from what used
to be the top of the page puts you on the bottom of the page; moving left from
the left edge of the page puts you on the right.)

Continue Reading »

10 responses so far

The One... The Only... Brainf*ck

Sep 06 2009 Published by under pathological programming

I'm currently away on a family vacation, and as soon as vacation is over, I'm off on a business trip for a week. And along the way, I've got some deadlines for my book. So to fill in, I'm recycling some old posts. I decided that it's been entirely too long since there was any pathological programming 'round these parts, so I'm going to repost some of my favorites.

As long-time readers know by now, in real life, I'm not a
mathematician; I'm a computer scientist. I'm still a math geek, mind
you, but what I really do is very much in the realm of applied math,
working on building systems to help people build programs.

One of my pathological obsessions is programming languages. Since I first got
exposed to TRS-80 Model 1 BASIC back in middle school, I've been absolutely
nuts programming languages. Last time I counted, I'd learned about 150
different languages; and I've picked up more since then. I've written programs
most of them. Like I said, I'm nuts.

These pathological programming language posts are my way of inflicting
my obsession on you in a (hopefully) amusing way. You see, in this
screwed up world of ours, there are lots and lots of thoroughly crazy
people out there. In the world of geekery, many of those crazy people
like to invent programming languages. Some very small number of them try to design
good languages and succeed; a much larger number try to design good languages
and fail; and then there are ones whose work I'm writing about. The
ones who deliberately set out to design strange, warped, twisted, and
nearly unusable languages, and succeed brilliantly. Most of the people who
design them call them "esoteric" programming languages. I call them evil.

Today, the beautiful grand-daddy of the esoteric language family: the one, the
only, the truly and deservedly infamous: Brainfuck,
designed by Urban Müller. (There are a number of different implementations available; just
follow the link.)

Only 8 commands - including input and output - all written using symbols. And
yet it's Turing complete. In fact, it's one-up on just being Turing complete - it's
actually been formally specified with a complete formal theoretical design,
called P''.
And it's even been implemented in hardware!.

Continue Reading »

10 responses so far

Pathological Programming with Primes (REPOST)

Sep 03 2009 Published by under pathological programming

I'm currently away on a family vacation, and as soon as vacation is over,
I'm off on a business trip for a week. And along the way, I've got some deadlines
for my book. So to fill in, I'm recycling some old posts. I decided that it's been
entirely too long since there was any pathological programming 'round these
parts, so I'm going to repost some of my favorites.

Today's pathological language is my personal all-time favorite pathological
monstrosity. It's an incredibly combination of perfect simplicity and complete incomprehensibility. It's based on a piece of work called
Fractran by John Conway of game theory fame. It's a really
fascinating bugger; absolutely insanely difficult to program in, but based on
one of the most bizarrely elegant concepts of computation that I've ever seen.
It's amazing that this is Turing complete. It's not a real programming
language in the sense of being able to write practical programs; it's more of
a simple theoretical computational model which has been implemented as a
language.

Continue Reading »

No responses yet

Simple Pathology: Betterave

Jun 22 2007 Published by under pathological programming

Sorry for the missed weeks of friday pathological programming language columns. To be honest, I'm running out of languages. I'm sure there must be more, but my usual sources (dealers?) are running out - so send links!
Anyway, today I'm going to look at a really simple one, which I find fun. It's
not an overly exciting language, but it is a language which is has semantics almost as
trivially simple as [BrainFuck][bf], but which ends up looking almost as much like line-noise as [TECO][teco]. It's called [Betterave][betterave].
[betterave]: http://www.esolangs.org/wiki/Betterave
[teco]: http://scienceblogs.com/goodmath/2006/09/worlds_greatest_pathological_l_1.php
[bf]: http://scienceblogs.com/goodmath/2006/07/gmbm_friday_pathological_progr.php

Continue Reading »

No responses yet

FPP: No you cant haz yr LOLCODE: Sortle Instead

Jun 01 2007 Published by under pathological programming

All week, I've been buried by a wave of requests to write about LOLCODE today. Normally, I do try to honor requests from readers, but from the time I started my friday pathological languages, I've always tried to stick to languages that actually had *something* interesting about their semantics. LOLCODE is funny because of its goofy grammar; but it's really incredibly dull semantically. And while there are lots of programs written in it,
there's no implementation (at least not yet).
Anyway, what I decided to do instead is a twistedly beautiful language called [Sortle][sortle]. Sortle is a very simple language which is based on insertion sort. The basic idea of how it works is: it takes the lines of the program, and sorts them. Then it executes them; when a line is executing, it can modify itself; when it gets modified, the interpreter re-sorts the line into its correct position in the sorted order according to its new value. So control flow is completely driven by the sort-order of the lines of the program.

Continue Reading »

No responses yet

A Pathological Way to Paint: Gammaplex

May 11 2007 Published by under pathological programming

Today's a mighty cool example of bizzare language design, called GammaPlex In terms of language
design, it's nothing particularly special: it's yet another stack language
with a befunge-like graphical syntax. What's unusual about GammaPlex is that it's strongly focused on graphics. It's got built in support for ascii graphics, OpenGL, and mouse input.

Continue Reading »

No responses yet

Even More Stack Pathology

May 04 2007 Published by under pathological programming

I thought that it would be fun to stick with the "stack-based" theme of last week's pathological post, but this time, to pick an utterly pointlessly twisted stack based language, but one that would be appreciated by the mascot of one of my fellow ScienceBlogs. Orac, this one's for you! 🙂 Our target these week is the language "Enema".

Continue Reading »

9 responses so far

Older posts »