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
        }
        puts
    }

Obvious things:

Less-obvious things:

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] " "
        }
        puts
    }

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:

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] " "
        }
        puts
    }

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:

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"
        i0
        puts "done i0"
    }
    
    outer

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 {
        count
        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:

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]
        }
        puts
    }

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:

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:

And here's the (slightly) modified printFibs:

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

This looks a lot cleaner.

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

(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 self.foo
        }
    }

This is because self.foo 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 " "}
        puts
    }

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
            self->_reset
        }
        
        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:

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.