Today’s pathological language is a bit of a treat for me. I’m going to show you a twisted,
\nannoying, and thoroughly pointless language that *I* created.
\nThe language is based on a model of computation called [Actors](http:\/\/en.wikipedia.org\/wiki\/Actor_model), 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. And that’s exactly where the name comes from. What name comes to mind when you think of *really bad* actors with delusions of adequacy? For me, it’s “Cruise”.
\nYou can get the code for Cruise on Google code, project “Cruise”, or you can grab a bundle containing the code, and a compiled binary in a jarfile [here](http:\/\/scienceblogs.com\/goodmath\/upload\/2006\/11\/cruise.zip). To run it, just “java -jar Cruise.jar cruse-program-file”. Just so you know, the code *sucks*. It’s something I threw together in my spare time, so it’s sloppy, overcomplicated, probably buggy, and slow as a snail on tranquilizers.<\/p>\n
\nQuick overview of the actor model
\n————————————-
\nActors are a theoretical model of computation, which is designed to describe completely
\nasynchronous 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.
\nAccording 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
\ncontents, it can do three kinds of things:
\n1. Create other actors.
\n2. Send messages to other actors whose mailbox it knows.
\n3. Specify a new behavior for the actor to use to process its next message.
\nYou can do pretty much anything you need to do in computations with that basic mechanism. The catch
\nis, as I said, it’s all asynchronous. So, for example, if you want to write an actor that adds two
\nnumbers, you *can’t* do it by what you’d normally think of as a subroutine 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.
\nBut 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, 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.
\nIt 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.
\nYou’ll see some examples of this when we get to some code.
\nTuples – A Really Ugly Way of Handling Data
\n———————————————-
\nCruise 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).
\nSo, for example, `Foo(Bar(), adder)` is a tuple. The tag is “`Foo`”. It’s contents are another tuple, “`Bar()`”, and an actor name, “`adder`”.
\nSince tuples and actors are the only things that exist, we need to construct all other types
\nof 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())))`”.
\nThe 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.
\nA few examples:
\n* matching `I(I(I(Z())))` with `I($x)` will succeed with `$x` bound to `I(I(Z))`.
\n* matching `Cons(X(),Cons(Y(),Cons(Z,Nil())))` with `Cons($x,$y)` will succeed with
\n$x bound to `X()`, and $y bound to `Cons(Y(),Cons(Z(),Nil()))`.
\n* 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()`.
\nCruise – the Language of Bad Actors
\n————————————–
\nInstead of my rambling on even more, let’s take a look at some Cruise programs. We’ll
\nstart off with Hello World, sort of.
\nactor !Hello {
\nbehavior :Main() {
\non Go() { send Hello(World()) to out }
\n}
\ninitial :Main
\n}
\ninstantiate !Hello() as hello
\nsend Go() to hello
\nThis declares an actor type “!Hello”; it’s got one behavior with no parameters. It only knows
\nhow 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.
\nLet’s be a bit more interesting, and try something using integers. Here’s some code to do
\na greater than comparison:
\nactor !GreaterThan {
\nbehavior :Compare() {
\non GT(Z(),Z(), $action, $iftrue, $iffalse) { send $action to $iffalse }
\non GT(Z(), I($x), $action, $iftrue, $iffalse) { send $action to $iffalse }
\non GT(I($x), Z(), $action, $iftrue, $iffalse) { send $action to $iftrue }
\non GT(I($x), I($y), $action, $iftrue, $iffalse) { send GT($x,$y,$action,$iftrue,$iffalse) to $self }
\n}
\ninitial :Compare
\n}
\nactor !True {
\nbehavior :True() {
\non Result() { send True() to out}
\n}
\ninitial :True
\n}
\nactor !False {
\nbehavior :False() {
\non Result() { send False() to out}
\n}
\ninitial :False
\n}
\ninstantiate !True() as true
\ninstantiate !False() as false
\ninstantiate !GreaterThan() as greater
\nsend GT(I(I(Z())), I(Z()), Result(), true, false) to greater
\nsend GT(I(I(Z())), I(I(I(Z()))), Result(), true, false) to greater
\nsend GT(I(I(Z())), I(I(Z())), Result(), true, false) to greater
\nThis is typical of how you do “control flow” in Cruise: you set up different actors
\nfor each branch, and pass those actors names to the test; one of them will receive
\na message to continue the execution.
\nWhat about multiple behaviors? Here’s a trivial example of a flip-flop:
\nactor !FlipFlop {
\nbehavior :Flip() {
\non Ping($x) { send Flip($x) to out
\nadopt :Flop() }
\non Pong($x) { send Flip($x) to out}
\n}
\nbehavior :Flop() {
\non Ping($x) { send Flop($x) to out }
\non Pong($x) { send Flop($x) to out
\nadopt :Flip() }
\n}
\ninitial :Flip
\n}
\ninstantiate !FlipFlop() as ff
\nsend Ping(I(I(Z()))) to ff
\nsend Ping(I(I(Z()))) to ff
\nsend Ping(I(I(Z()))) to ff
\nsend Ping(I(I(Z()))) to ff
\nsend Pong(I(I(Z()))) to ff
\nsend Pong(I(I(Z()))) to ff
\nsend Pong(I(I(Z()))) to ff
\nsend Pong(I(I(Z()))) to ff
\nIf 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”.
\nThe “:Flop” behavior is pretty much the same idea, accept that it switches behaviors on “Pong”.
\nAn example of how behavior changing can actually be useful is implementing settable variables:
\nactor !Var {
\nbehavior :Undefined() {
\non Set($v) { adopt :Val($v) }
\non Get($target) { send Undefined() to $target }
\non Unset() { }
\n}
\nbehavior :Val($val) {
\non Set($v) { adopt :Val($v) }
\non Get($target) { send $val to $target }
\non Unset() { adopt :Undefined() }
\n}
\ninitial :Undefined
\n}
\ninstantiate !Var() as v
\nsend Get(out) to v
\nsend Set(I(I(I(Z())))) to v
\nsend Get(out) to v
\nTwo more programs, and I’ll stop torturing you. First, a simple adder:
\nactor !Adder {
\nbehavior :Add() {
\non Plus(Z(),$x, $target) { send $x to $target }
\non Plus(I($x), $y, $target) { send Plus($x,I($y), $target) to $self }
\n}
\ninitial :Add
\n}
\nactor !Done {
\nbehavior :Done() {
\non Result($x) { send Result($x) to out }
\n}
\ninitial :Done
\n}
\ninstantiate !Adder() as adder
\ninstantiate !Done() as done
\nsend Plus(I(I(I(Z()))),I(I(Z())), out) to adder
\nPretty straightforward – the only interesting thing about it is the way that it sends the result of invoking add to a continuation actor.
\nNow, 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
\nyou that I cheated, and added integers to the parser; they’re translated into the peano-tuples
\nby the parser.
\nactor !Adder {
\nbehavior :Add() {
\non Plus(Z(),$x, $misc, $target) { send Sum($x, $misc) to $target }
\non Plus(I($x), $y, $misc, $target) {
\nsend Plus($x,I($y), $misc, $target) to $self
\n}
\n}
\ninitial :Add
\n}
\nactor !Multiplier {
\nbehavior :Mult() {
\non Mult(I($x), $y, $sum, $misc, $target) {
\nsend Plus($y, $sum, MultMisc($x, $y, $misc, $target), $self) to adder
\n}
\non Sum($sum, MultMisc(Z(), $y, $misc, $target)) {
\nsend Product($sum, $misc) to $target
\n}
\non Sum($sum, MultMisc($x, $y, $misc, $target)) {
\nsend Mult($x, $y, $sum, $misc, $target) to $self
\n}
\n}
\ninitial :Mult
\n}
\ninstantiate !Adder() as adder
\ninstantiate !Multiplier() as multiplier
\nsend Mult(32, 191, 0, Nil(), out) to multiplier
\nSo, is this Turing complete? You bet: it’s got peano numbers, conditionals, and recursion. If you can do those three, you can do anything.<\/p>\n","protected":false},"excerpt":{"rendered":"
Today’s pathological language is a bit of a treat for me. I’m going to show you a twisted, annoying, and thoroughly pointless language that *I* created. The language is based on a model of computation called [Actors](http:\/\/en.wikipedia.org\/wiki\/Actor_model), which was originally proposed by Professor Gul Agha of UIUC. There’ve been some really nice languages built using […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[92],"tags":[],"class_list":["post-208","post","type-post","status-publish","format-standard","hentry","category-pathological-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-3m","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/208","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=208"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/208\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=208"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=208"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=208"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}