$ cat /home/buntine/mind_melting_brilliance

A few weeks ago I gave this simple little presentation for Web Directions South, here in Melbourne. I'm a tad rusty (well, very rusty!), but I did enjoy the night. See below for video:

I've had a bunch of people ask me to rip this since I started waffling on about it. I apologise for the delay, but I finally ripped with decent quality.

MP3: http://www.andrewbuntine.com/music/ToxicTrash_mp3.zip

Unfortunately, I've never seen another copy of this in all my searching, but here is what I have found out:

Style: Black/Thrash
Country: Bratislava, Slovakia (still Czech when released)
Year: 1991/1992
Label: None/Private
Sponsor: Pring (Required for distribution in those times)

If anyone else knows more about this LP, please tell me. I wrestled mine from the grips of an Austrian guy who'd found it 11 years earlier in a second-hand store in Prague.

I think it really deserves a place amongst the other Czech classics.

Enjoy!! Track #2 is a real scorcher, in my opinion!!

We work very hard to meet our deadlines, but from time-to-time we just have to let our inner Ninja out to play.

Update May 13th: V2 is completed and available for download: https://addons.mozilla.org/en-US/firefox/addon/witchhammer/

I knew the day would come when the guys behind Metal-Archives.com would decide to unveil thier new web site. I specifically wrote Witchhammer in a way that would limit my headaches if the web sites HTML changed some time in the future.

Of course, that day has come! The new Metal-Archives.com is totally different. It's been rewritten from the ground up (as far as I can tell). The new format actually makes Witchhammer a bit more intuitive, but there are still a couple of issues (the MA JSON pseudo-API doesn't seem to respond to it's input parameters!)

I've been working sporadically over the past few nights to get the Witchhammer working with the new site. I am about 90% of the way through and should be able to deploy the new version some time in the next 48 hours.

Thanks for the patience. :)

Just a quick one so I can direct emails and nasty comments from Heavy Metal warriors here.

Metal-Archives.com, as of 31/01/11, have disabled their search functionality and replaced it with a Google site-specific search (supposedly for performance reasons). Unfortunately, this totally breaks Witchhammer.

When the Metal Archives staff decide to re-enable the search, Witchhammer will start working again (unless they change their views, in which case I'll have some work to do).

Please stand by! I've also added a note on the download page: https://addons.mozilla.org/en-US/firefox/addon/9671/

Also, i've passed the 3,000 users mark. I think that's pretty cool.

The notion of continuations as first-class values has been a tricky subject for me to understand to a comfortable level of certainty. I think this is probably true for many PLT-laymen like myself. This article represents my attempt at collecting and presenting my thoughts in a coherant manner! I'd be happy to receive corrections and comments.

I will start by defining a few key terms in my own style.


Continuation

We can observe that every expression, regardless of complexity, has the ultimate goal of returning a value to some surrounding execution context. That context is known as a continuation - it represents everything that is left to compute. Therefore, every computation has an associated continuation, which specifies the place from which execution should continue once control has been returned.

As a simple example, consider the following Scheme form:

The continuation associated with the sub-expression "1" is an anonymous function, whose body consists of a call to the + primitive procedure whose first argument is the local variable n and whose second argument is being sought. With this understanding we can say expressions deliver values and continuations receive values.


Current continuation

By "current", we are referring to the continuation that would be derived from the current point in a programs execution. In other words, the current point of execution, lexical environment and state of the call stack (You should be familiar with the stack and the heap).


First-class object

For an object to be a "first-class citizen" in a programming language, it needs a few properties. Specifically, it must support being:

  - passed as a parameter to a function;
  - returned from a function;
  - stored in a variable or within a data structure;
  - constructed at runtime.

Objects like numbers and strings are first-class in most programming languages. Functions are first-class in all functional programming languages. And in Scheme, my language of choice for this article, nearly everything can be considered first-class - including continuations as we'll see shortly. To avoid confusion, note that I am using the term "object" to refer to any entity that can be controlled within the realm of a particular programming language, rather than to the OO-sense of the word (the instance of a class).


Continuations in Scheme

In order to render the abstract notion of the current execution context (the current continuation) to the programmer, Scheme needs some way to represent it. It would have been possible to implement specific objects and syntax into the language to handle this, but it's much easier to simply represent the current continuation as a first-class function. This process of transforming something implicit into something that can be explicitely expressed is known as "reification". So we can say Scheme reifies the current continuation as a function object.

Scheme provides the function call-with-current-continuation (aliased as call/cc) to furnish continuations to the programmer. call/cc is a unary function that accepts a further unary function, f, as it's argument. When invoked, Scheme will reify the current continuation, c, as a function and apply f to c. Therefore:

When c is applied to an argument, v, the existing continuation is terminated and the one represented by c is reinstated. So program flow will continue on from where the continuation was captured and v will become the overall value of the call/cc invokation.

Confusing? Take a look at this simple example:

At first glance, you may think this expression will evaluate to 7, but infact, it will evaluate to 4. This is because we've captured the current continuation in the formal parameter return and then applied it to the number 4. This causes program flow to return instantly to the point at which the continuation was taken. Yep -- when applied, c will never return! We are effectively emulating the "return" control operator that allows early-escape in many popular programming languages.

To demonstrate the concept of early-escape in a more effective manner, let me show you two versions of a small Scheme procedure - one that makes use of continuations and one that does not. The procedure has-sym? accepts as arguments an S-expression (in this case a list of symbols and/or nested lists of symbols) and a symbol. It returns true if the given symbol is present somewhere within the S-expression. First of all, take a look at the non-continuation version:

Whilst concise and easy to understand, this implementation (because it's defined as a recursive process) suffers from the slight hassle in that even if we find a match, we need to wait until the call-stack unwinds before the actual result gets back to the continuation in which the has-sym? procedure was called. If, perhaps, we captured the continuation of the has-sym? procedure with call/cc and then defined a local helper procedure (to perform the search) inside our function argument, we'd be able to invoke the continuation object and jump straight out of the procedure as soon as we found a match. For example:

At this point it may be worth pointing out that continuations in Scheme, whilst far more powerful, are also more conservative than the goto statement of other languages for we can only revert control back to a place we have already visited (obviously, this is a good thing!). Also note that applying a continuation, unlike lexical closures, does not reinstate the referencing environment! If you change the values of variables - they will remain changed.


Continuations as first-class citizens

So far I've tried to explain the notions of both first-class objects and continuations in Scheme, but when we combine the two and start considering continuations themselves as being of first-class status, we open up a treasure trove of cool ideas. For example, consider the following mind-bender:

We can demonstrate the indefinite extent of continuations in Scheme by capturing the continuation (reified as a first-class function) in the local variable k. This definition of factorial works by capturing the continuation object, modifying the parameter n and local variable total in place, and then invoking the continuation with itself as an argument. This causes something of a local GOTO and rebinds the original continuation to the local variable k. This process continues until n reaches 1 at which point we return the total back to the user. The let* form is important here as it will expand into a series of nested let forms. Without this, we'd rebind total to the original value of n on each invokation of the continuation object. With let* we can store a running total.

As you can see, we have used our power over control flow to compute factorial without using recursion or any built in looping construct. Of course, this implementation also suffers from two obvious downsides: 1) It's somewhat esoteric and hard to understand and; 2) It mutates local state, which makes it harder to prove that this function will maintain referential transparency.

Conclusion

With the power of first-class continuation handling at our disposal, we have the ability to define several control flow constructs common to other programming languages, such as backtracking, try/catch exception handling and "green" threads.

Studying a topic like continuations helps us to solidify our knowledge of several concepts we may generally grow to take for granted. The idea of managing control flow is so rudimentary to our field that we may never stop to think about how such an implicitely understood idea can be explained effectively.

In terms of further reading, I'd suggest the call-with-current-continuation, Continuation and Call stack articles on Wikipedia. The R5RS standard documents call/cc and other control-handling procedures that are available in Scheme. The discussion on understanding continuations at Lambda the Ultimate also helped me in writing this article.

And, finally, I think when such high-level control of continuations is given to a programmer, the words of the great Uncle Ben must be remembered:

  "WITH GREAT POWER THERE MUST ALSO COME - GREAT RESPONSIBILITY!"
    - Amazing Fantasy #15 (August 1962) - The first Spider-Man story.

A while ago I was having a discussion with a programmer friend of mine. He'd been writing some Javascript at work and asked me about closures. Whilst I understood the concept enough to use it in my own code, I found it difficult to explain effectively. Although common knowledge in functional programming circles, closures (and, more importantly, their usefulness) are often hard to grasp for us younger programmers who are trained to think in terms of OOP. This article represents my attempt at explaining lexical closures in the simplest possible terms. I hope my language choice of Clojure is not too esoteric.

Ok, lets get started...


Definition

A closure is a language feature in which a lambda expression (read: function) is bound to the referencing environment that was available when it was first defined. The function is said to close over it's referencing environment, hence the name. If you are unfamiliar with the term "referencing environment" (some people call it the "lexical environment"), we can think of it as a simple dictionary (key -> value) mapping free variables to their respective values. By "free variables", I refer to bindings that have occured in an outer scope (such as the surrounding function). In lexically scoped languages, a functions referencing environment can generally be known simply by looking at the source code of a program.

I don't expect you have any idea what that really means yet - just keep reading!


Explained simply

A simple way to think of a closure in practical terms is as a package that contains two things:

  1) A body of code
  2) The referencing environment that was active when said code was defined

So, when we invoke a closure (execute the body of code in the package), rather than creating a new referencing environment the closure will grab it's saved environment from the package and use that instead.

The following example demonstrates how we can use closures to hide helper functions that would serve no purpose outside their defining context. Sorry, I could not help but add a factorial example:

The function "fact-helper" is now private to the letfn expression. The named function "fact" is created in the global scope, but retains access to the referencing environment that was available when it was defined. In OOP, we generally achieve this same effect by making a class and defining private functions within it.


Language prerequisites

In order to allow for closures, a language needs to atleast support nested functions. Most functional languages and many popular imperative languages meet (well, surpass) this criteria. Python, all Lisps, Javascript, Haskell, etc all support true first-class functions and the block construct of Smalltalk and Ruby is sufficient. Without the means to lexically nest scopes (C, from memory), then closures serve no purpose - their local environment will remain the same on each invokation and the global environment will be either identical or larger. A few languages, such as Pascal and Algol, allow for nested functions but do not allow functions to be returned as values. This means that the closure is only available in the scope it was defined. Languages like these are said to have environments with "limited extent", which means that lexical bindings are destroyed upon leaving their scope.

On the flip-side, languages that support first-class and/or anonymous functions must also ensure that a referencing environment has "unlimited extent". That is, the interpreter or compiler must guarantee that the environment will not be destroyed until the garbage collector can prove that there is no reference to it. This is important because a closure may be returned from a function and thus may outlive the scope in which it was defined. The somewhat contrived example below illustrates this point:

It is important to note that the environment that the closure reinstates will contain the same bindings, but their values may not be the same. This is especially true in imperative languages in which assignment (changing the value of a variable) is key.


Conclusion

Closure is a simple concept that all programmers should atleast have a basic understanding of. Many modern programming languages are adding support for first-class functions, which means that this style of programming may well become more popular in mainstream languages. As more multi-paradigm languages hit the mainstream, it will become increasingly more important that effective programmers can reason about their programs from multiple perspectives.

In terms of further reading, I suggest you take a look at the Wikipedia page and/or read SICP. Finally, I cannot claim to be an expert on this subject, so if you have any feedback and or corrections, please let me know. Thanks!

Following on from my last article, I'd like to show you a common fractal pattern known as the Sierpinski Triangle. It was first described formally in 1915 by Waclaw Sierpinski. You've probably seen it before -- it's basically a triangle, which contains three smaller triangles within it. This process can be repeated ad infinitum.

There are many ways to construct the Sierpinski Triangle, but one method that really grabbed my attention involved an approximation from the rows of Pascal's Triangle. It's really quite simple, but I'll briefly explain Pascal's Triangle first.

Pascal's Triangle is an ancient (discovered long before Pascals time) pattern of numbers in which each number within the triangle is the sum of the two numbers directly above it. The first row is simply 1, and the sides of the triangle are made up of 1's. So it grows like this: [1], [1, 1], [1, 2, 1], [1, 3, 3, 1], etc. Take a look at the Wikipedia article for a proper introduction.

As it turns out, if we generate Pascal's Triangle to 64 rows (or, more formally, any 2^n) and then colour all of the odd numbers in, we get a bloody good representation of the Sierpinski Triangle! I'd think that if we continued this process infinitely (or to some very large n), you'd be unable to tell the difference between the two.

Writing a program to demonstrate this cool little trick was pretty simple. It's just a matter of generating the triangle as a list of expanding lists (one for each row) and then painting each row of numbers to the window by traversing it and selecting the correct colour based on the each value (dark blue for odd, light blue for even). It looks like this:

You can take a look at the source code here: http://github.com/buntine/Fractals/blob/master/pascals-triangle.scm

A few weeks ago I stumbled upon this rather eccentric documentary, narrated by Arthur C. Clarke, about the discovery of the Mandlebrot set and fractal geometry in general: Fractals - The colors of infinity.

A fractal, described very simply, is a geometric pattern that is repeatable at every level of magnification. Fractals, therefore, cannot be described by our traditional models of geometry. Typically, if you inspect a fractal at differing levels of magnification, you will see identical (or very similar) copies of the whole pattern. Of course, such phenomena has always existed, but it hasn't been until the advent of sufficiently powerful computers that we have been able to generate fractals on a large scale of complexity.

In nature, one of the most simple examples of a fractal-like shape is a tree. Using a recursive algorithm and a simple graphics library, we are able to easily generate a fractal tree. I chose the Lisp language PLT Scheme (or Racket, as it's known these days) to write my programs. Here is my first attempt:

Not bad. Well, perhaps a little too uniform. It works by implementing a recursive pattern known (not surprisingly) as tree recursion. That is, each invokation of the function triggers two further recursive calls. Each call to the function plots a new X/Y position by translating a radian (angle * (PI / 180)) and a length into "cartesian coordinates". It then calls itself again with the new X/Y as a starting position and a new angle, once for (angle - 20) and again for (angle + 20) to simulate the splitting of a branch. This process is repeated a finite number of times and the length of each branch is relative to the current depth of recursion.

By simply adding some randomisation into the angles of each branch (instead of always bending 20 degrees), we start to see a slightly more realistic looking tree! See my second attempt below, which draws four trees with some randomised angles to simulate a burnt-out looking forest:

The source code for both of these programs is available on my Github account here http://github.com/buntine/Fractals/blob/master/uniform-tree.scm; and here: http://github.com/buntine/Fractals/blob/master/random-tree.scm.

List the available shares:

$ smbclient -U my_user -L samba_hostname

Choose the share you want, and connect:

$ smbclient -U my_user //samba_hostname/Share_Name

EASY! Right?

If you get "Not enough '\' characters", do not just keep adding them! You probably want to shuffle your arguments around (such as putting -L last).

To turn off those annoying prompts on an mget, just toggle it:

prompt