Deck: The Quick-and-Dirty Guided Tour

The problem with programming languages is that you can't just throw up a few screenshots on the website to show off how cool it is. You need to show code and then point out how cool it is, preferably in a brief and witty way.

Oh well.

Instead, I give you the Fibinacci Examples:

The Fibonacci Sequence

You all know what the Fibonacci sequence is, right? So I don't need to explain that it's a sequence of numbers:

    1 1 2 3 5 8 13 21 34 55 89 144 233 ...

where each number is the sum of the two previous numbers. Which is good because explaining all of that would take forever!

Basic Itterative Implementation

It's pretty simple to code a procedure that prints out some of the Fibonacci series:

    proc printFibs [count] {
        var first = 1
        var second = 1
        for n in (1 .. count) {
            say "$first "
            var ns = (first + second)
            first = second
            second = ns

Obvious things:

proc defines the procedure, printFibs is the name of the procedure, [count] is the argument list and the rest is the procedure body.

var declares a variable.

say prints its argument(s). puts does that too but it adds a newline.

for itterates over a range of numbers.

Deck provides Perl/Tcl/shell-style variable interpolation in strings. (E.g. "$first " contains the value of variable first.)

Less-obvious things:

If you think of a program "line" as not ending until all the brackets are closed, then the entire procedure can be thought of as one line.

The text between braces ({ and }) is subdivided into "lines" as above, making a single "line" able to contain multiple other "lines".

Therefore, each Deck statement is a single "line". Furthermore, the first item in the "line" is the procedure to call and the remaining items are the arguments to pass to it.

Expressions bracketted by round parentheses (( and )) are parsed as infix expressions (e.g. (2 + 3) instead of [+ 2 3]).

Assignments (e.g. first = second) have imaginary round brackets around them. So does the expression after var.

Notice the round brackets around the third argument to the for statement: (1 .. count). This is an infix expression. In fact, .. creates an object (type Interval) which mimics a list containing the range of integers between the left-hand-side and right-hand-side arguments. From this, it becomes clear that what for actually does is evaluate its body for each element of a list-like object it receives. (Unlike most Lispish languages, Deck lists are actually arrays (aka vectors).)

Special Forms, Absence of

You'll notice that a lot of statements take arguments that look like they should be evaluated but aren't: the word printFibs after proc, the n after for, the variable names, etc. In most Lisp dialects, the language has a fixed number of Special Forms--things that look like functions but have their arguments parsed differently.

Deck has one special form, the quote symbol: :. Things prefixed by a colon are not evaluated. However, there is no quoting in the example above. (Actually, that's not true: { is an implicit quote, but I'm not going into that here.)

Instead for, var and proc are all macros. In Deck, a macro is simply a function called by the compiler to modify the current expression in some way--a compiler plug-in, as it were. proc (to pick an example) invokes a macro that replaces the proc statement with another expression (a call to an undocumented internal procedure) in which all of the arguments have been normalized and the bare words quoted.

Most of Deck's built-in functionality is implemented this way.

A Recursive Fibonacci Implementation

Subject to the Laws of Computer Science, whenever I use the Fibonacci series in a programming example, I am required to show you a recursive implementation, so here it is:

    proc fib {index} {
        (index <= 2) && [return 1]
        return ([fib (index - 1)] + [fib (index - 2)])  

Of course, it also needs this function:

    proc printFibs {count} {
        for n in (1 .. count) {
            say [fib n] " "

Needless to say, it is 1) minimal and elegant and 2) pig slow because for each new Fibonacci number, it needs to recalculate the entire series. However, from this code, I can point out a few more things:

Square brackets ([ and ]) delimit subexpressions in the standard Deck form (i.e. prefix expressions). For example: [fib n].

Like assignments, expressions made up of && and || also have implicit round brackets. This lets you do Perl-style flow control with short-circuited boolean operators, as I do in the first line of fib.

Counter-intuitively, the <= expression needs to be surrounded by round parentheses so that the outer expression it lives in continues to be made up of only && and || operations.

proc lets you wrap the argument list in braces ({ and }) instead of square brackets. This is pure syntactic sugar by proc in order to make Tcl programmers a bit more comfortable.

Implementation by Closure

Now, we start getting to the contrived examples:

    proc fibFn {} {
        var {first = 1; second = 1}
        return {} => {
            var newSecond = first + second
            var result = first
            first = second
            second = newSecond
            next result
    proc printFibs {count} {
        var ff = [fibFn]
        for n in (1 .. count) {
            say [ff] " "

As you know Bob, a closure is an anonymous function that has access to the scope in which it was created. The Deck operator => creates a closure: the left operand is the argument list and the right is the function body.

So proc fibFn defines and initializes the variables first and second, then creates and returns a closure. printFibs takes the closure (referenced by variable ff) and calls it repeatedly to generate each new number in the Fibonacci sequence. The current and next Fibonacci numbers are stored in first and second in fibFn which, having exited, are now only visible to the closure.

Things to note:

The => expression in fibFn doesn't have round brackets around it, even though it should. That's because the parser automatically surrounds a => expression with them in an infix expression. This is more syntactic sugar.

The return statement has been renamed next inside a closure. This is so that you can return from a closure without returning from the function that created it.

While you never see it in this document, => is actually a convenient alias for sub which also creates closures but in a prefix way. => is more convenient but sub also lets you add a final block the closure.

A Digression: return and next

While we're talking about return (and next) I should explain just how frickin' cool they are.

In most languages, return is a control structure. Using it makes the compiler (or interpreter) exit the current function. In Deck, return is a callable object of type Continuation. Calling it like a function returns the function in which it was defined and if necessary, every function it's currently calling. For example:

    proc i2 {ret} {
        ret 42
        puts "i2 done"
    proc i1 {ret} {
        i2 ret
        puts "i1 done."
    proc i0 {} {
        puts "starting i0"
        i1 return
        puts "done i0"
    proc outer {} {
        puts "calling i0"
        puts "done i0"

when run, produces this output:

    calling i0
    starting i0
    done i0

i0 passes its return as an argument to i1 which calls i2 with it. When i2 finally calls the continuation, the call sequence is completely unwound and i0 returns. If ret had been given an argument, it would have been used as the return value.

(In closures, return has been renamed to next but is otherwise the same.)

Since unexpectedly returning from a procedure can leave loose ends, a proc (or method or closure) may take a final block. The final block is just another chunk of code added to the end of a procedure with full access to namespace. However, it is guaranteed to execute, no matter how the procedure returns. This lets you do stuff like this:

    proc readDataFile {fileName} {
        var fh = [openDataFile filename]
        [readHeader fh] || [return false]
        [readBody fh]   || [return false]
        return true
    } {
        closeDataFile fh

Because the second block always executes, closeDataFile is always called, even if readDataFile returned when readHeader called a continuation stored in a global variable or some equally idiotic thing.

Digression #2: MProcs

As mentioned above, Deck has macros. Unlike Scheme, there is no effort to make Deck macros hygenic or simple. They're just procedures that the compiler calls when it finds a matching expression. The compiler passes the expression to the macro and then tries to compile whatever it returns. This is simple, powerful and ugly. If you've led a good life, maybe you won't ever need to use them.

Deck also has a nicer lightweight macro called an mproc. An mproc is just a procedure whose calls get modified in various simple ways by an automatically-generated macro. MProcs can add default arguments to a procedure, automatically quote a bare symbol or list or turn a list argument into a closure.

This latter feature is often used to add new control structures. For example, this:

    mproc repeat {
        sub 1 pr
    } {
        for i in (0 .. count - 1) {pr i}

can be called like this:

    repeat 5 {puts "I like pie!"}

The special declaration of argument pr turns its second argument into a closure.

The Infinite Stream Implementation

Okay, back to Fibonacci.

The third implementation uses an infinite stream. This is an infinitely-long linked list which fakes infinity by computing the n'th element just before you need it. We do this by putting a procedure at the end of the list and evaluating it when we get there. The procedure computes a new node containing the next value and another procedure and this gets attached to the end.

Since Deck lists are not linked lists the way they are in $FAVOURITE_LISP_DIALECT, I first need to implement linked lists using a class:

    class Node {
        public head tail
        method _init {h t} {
            head = h
            tail = t

This is pretty straightforward:

head and tail are instance variables (aka object fields). The public declaration means (obviously) that external code can read and write the value.

_init_ is called when an instance of Node is created to initialize it.

This is a "dumb" data structure. It holds information but any processing is done by external code, just like a C struct. Since we need to process tail, we need a function to evaluate it:

    proc getTail {node} {
        if (node.tail.isCallable) {
            node.tail = [node.tail]
        return node.tail

This function returns the tail field of Node instance node. If node is a callable object, it first calls it and replaces the value of node with the result. (It also breaks if the list contains real callable values, but we're not going to worry about that now.)

The list gets set up by the function fib:

    proc fibs {v1 v2} {
        return [new Node v2 {}=>{fibs v2 (v1 + v2)} ]

So the last item in the list is always a closure which returns a new Node containing the Fibonacci value in its head and a new closure in tail and the new closure does exactly the same thing for the next item.

The printFibs procedure looks like this:

    proc printFibs {count} {
        var stream = [fibs 0 1]
        repeat count {
            say stream.head " "
            stream = [getTail stream]

As you can see, it uses fibs to create the first node, then calls getTail on the stream to generate the next node.

Some more details:

The . operator is used to access the (public) fields of Node. It can be on either side of an assignment.

., like => is treated specially by the parser. The sequence left . right is automatically surrounded by round brackets whenever it is seen in a prefix expression.

Calling getTail is pretty cumbersome. Fortunately, Deck's object system lets us fold that functionality into the Node class. The new Node looks like this:

    class Node {
        readable head
        var tail
        method _init {h t} {
            head = h
            tail = t
        method tail_get {} {
            (tail.isCallable) && (tail = [tail])
            return tail

There are three changes:

head is now readable, which means it can't be modified by external code. This change is not strictly necessary (and we could have made it readonly in the previous example) but it makes for better code overall.

tail is now declared private with the var word.

Method tail_get has been added. This is what gets called when external code tries to read tail. It contains the functionality that used to be in getTail so now, just accessing the tail field does the right thing.

And here's the (slightly) modified printFibs:

    proc printFibs {count} {
        var stream = [fibs 0 1]
        repeat count {
            say stream.head " "
            stream = stream.tail

This looks a lot cleaner.

Here are a couple of other things you should know about object attributes:

In addition to var, public and readable, fields can be declared writable. This makes then settable but not readable.

It is also possible to override writing to a field by defining a method which takes one argument and has the same name as the field with _set appended. E.g. for field head, it would be named head_set.

So far, it looks like I'm implying that the _get and _set methods are being called by a field access. It's actually backwards. All class fields are private and declaring a field public (or readable or writeable) causes the compiler to generate trivial getters and setters.

You may write a getter or setter for a non-existent variable. That is, the public interface does not need to correspond to the internal structure of the class.

(Attribution: I stole the idea of infinite streams from Mark Jason Dominus's book Higher Order Perl who stole it from somewhere in Lisp Land.)

Digression #3: More on Objects

The examples in this document aren't particularly good at highlighting all the interesting corners of Deck's object system, so I'm taking a few paragraphs to drop knowledge on you.

In Deck, everything is an object. This includes classes, which are all instances of the class Class. This includes Class itself which is its own class. Classes can be passed around and queried but all classes have the same interface. This means that there's no such thing as a class (aka "static") method or field. Instead, you should use packages. (See the reference manual for a long, tedious description of those.)

Instance variables in classes are only visible to the methods defined in that class, not in any subclass. Their scope is the equivalent of private in C++. This doesn't work:

    class Inner {
        public foo
        method _init {x} {
            foo = x
    class Outer Inner {
        method bar {m} {
            puts m foo  # ERROR: foo not visible

But this will work:

    class Outer Inner {
        method bar {m} {
            puts m

This is because invokes the getter method defined by public. (self is a reference to the current object.)

(Note that there's a bug in the current implementation of Deck that prevents you from defining an instance variable with the same name as an instance variable in a parent class even though they are unambiguous.)

Methods are normally invoked using the -> operator:

    var x = [new Outer]
    x->bar "Value: "

(-> is syntactically magical just like . and =>.)

The semantics of -> are interesting by themselves. The result of x->bar is a callable object called a MethodCall. This encapsulates the result of the method search for bar in x. When called like a procedure, it calls the method found (usually bar) with self set to x and with whatever arguments it was given. The MethodCall can thus be stored or passed around:

    var barMethodCall = [Outer->new]->bar
    barMethodCall "Value: "

If the method lookup fails (i.e. there is no method with that name in the object's class heirarchy), the lookup calls the special method doesNotUnderstand instead. Default behaviour for doesNotUnderstand is to exit with a backtrace but individual classes may override this behaviour.

If the left side of a -> or . is the word super, it is used as an alias for self but the method search starts in the superclass instead of the base class. This lets you override a method but call its base implementation:

    class MoreOuter Outer {
        method bar {m} {
            super->bar m
            puts "MoreOuter!"

Methods whose names begin with an underscore (_) are considered private to the class heirarchy (what C++ calls "protected"). It is an error to use a name starting with an underscore in a -> expression unless the left-hand-side is either self or super:

        self->_privateThingy 42             # Correct
        super._kindOfPrivate = "maybe"      # Also correct
        foo->_reallyPrivate "yes"           # Error!

As you can see, this works on attributes too, so you can give instance variables a "protected" scope.

Note that it is possible to defeat the underscore rule. -> is a macro and it performs the check at compile time. The code that the macro emits could be hand-written instead, bypassing the check. Thus, you may need to enforce the underscore rule yourself with a blunt instrument.

(Hah hah, just kidding! Use a knife.)

(Still kidding! I don't condone violence, even against really idiotic coders. Just glare at them.)

As you have seen in the above examples, there are two ways to create a new object from a class. You can use the built-in new function:

    new SomeClass "this is an argument"

or you can use the class's new method:

    SomeClass->new "this is also an argument"

The two forms are equivalent and you can use whichever one looks nicer in context.

The Fake List Fibonacci

Early on, I explained that the (1 .. count) sequence in a for statement actually created an object which mimicked a list of integers in increasing order. From that, you may have suspected that it would be easy to create a class which mimics a list of Fibonacci numbers. And you'd be right.

With such a class, printFibs becomes almost trivial:

    proc printFibs {count} {
        for n in [FibonacciList->new count] {say n " "}

The class FibonacciList does all of the heavy lifting:

    class FibonacciList {
        var first second
        var prevCallIndex
        readable size
        method isIndexable_get {} {return true}
        method _init {sz} {
            size = sz
        method _reset {} {
            first = 1
            second = 1
            prevCallIndex = 0
        method at {index} {
            self->_update [self->_sanitizeIndex index]
            return first
        method _update {reqIndex} {
            (reqIndex >= prevCallIndex) || [self->_reset]
            repeat (reqIndex - prevCallIndex) {
                var ns = first + second
                first = second
                second = ns
            prevCallIndex = reqIndex

The method _update does all of the actual work. It computes the reqIndex'th Fibonacci number. If the previous call's results come before reqIndex in the list, then it computes them from there. This is reasonably efficient if you only need to read the list from start to finish.

This class implements everything required to mimic a list. We call this the Sequence Protocol. Specifically:

A readable isIndexible attribute must return true. Class Object already implements a version of this that returns false so it is safe to use this to test a class for the presence of the rest of the sequence protocol.

size needs to be implemented to return the number of items in the list. In the example, it's an actual readable field but as with all attributes, this can also be implemented with a _get method.

at takes one argument--the index--and returns the corresponding element. The index must be an integer between 0 and (size - 1). In addition, negative indexes are allowed and interpreted as being relative to size. E.g. index -4 is treated as (size - 4). The private Object method _sanitizeIndex converts negative indexes to positive ones. How the object handles out-of-range indexes is undefined. This one allows them.

Two optional items: atPut to store values and readable attribute maker which returns a function to create an empty sequence of a compatible type. (The default implementation returns a List.)

Most of the time, you won't need to call at or atPut directly. Instead, the @ and = macros are used. Reading a list item looks like this:

    puts "Item: " (theList@42)

In this case, @ is a macro that expands into to a call to the at method of its left argument.

Storing looks like this:

    theList@42 = "item 42"

In this case, the assignment macro (=) expands the entire expression into a call to atPut method of the first item with the second (right of @) and third (right of =) as the index and value arguments.

More Reading

If you're still interested in Deck and want to read more manuals, there is a language reference manual.pod and a library reference lib.pod.

The library reference lists every procedure, macro, mproc and class available to you along with a maddeningly brief description of each. The language reference, meanwhile, explains the minutia of every nook and cranny of the Deck language as well as its deficiencies.

If you just want to see source code, the Deck library source code is in the lib-deck directory and a number of example programs (including the ones seen here) are in the directory progs.

Finally, the Deck interpreter itself is written in (ahem) highly readable Perl.