Archive

Archive for the ‘Programming’ Category

JavaScript, JSON and modern web MVC

June 2nd, 2011 7 comments

As web developers we’re working through a transitionary period. New technologies are becoming widespread enough to be usable in real web apps – not just toys. After years of stagnation in JavaScript engines, Google Chrome started an arms race in speed, with all the major browser makers competing to make the fastest JavaScript interpreter. These changes are opening up a new world of web app development that hasn’t been fully explored yet, but this means we may have to rethink some of the best practices we’ve been following for the past decade.

MVC today

In a modern web application framework, MVC is well defined: requests get routed to a controller, which requests data from the model (which is probably using an ORM) and instantiates a templated view with this data. This view is sent as HTML to the browser which creates a DOM from the HTML, and renders the DOM (with CSS and images) as a web page.

JavaScript then operates on the DOM, adding a layer of interactivity to the page. As things advance, the JavaScript layer has taken on more importance, reducing the number of page reloads by selectively reloading parts of the page with Ajax.

As the complexity of JavaScript on the client has increased, it’s been easy to end up with unstructured spaghetti code based around the jQuery model of “find something, do something with it”. As more state has moved to the browser, MVC frameworks for JavaScript have stepped in to add structure to the code. The problem is, now we have two MVC stacks:

Current JavaScript solutions suffer from "Double MVC". You need both server and client-side MVC stacks. Conceptual complexity is very high.
@dhh
DHH

MVC of the future

MVCMVC or MMVVCC aren’t just un-catchy, they’re a rubbish idea. If we’re going to make rich apps that rely on JavaScript (and as I said previously, I think we should), we need to lose some redundancy.

The model will usually be accessing some shared database, so in most cases it makes sense for this component to be on the server (authentication usually lives here as well). The view is the DOM, and the controller is the JavaScript. There’ll also need to be model code in the JavaScript – the extent to which the model logic is split between client and server depends on the application.

All the server needs to do is provide JSON responses when the client asks for more data, ideally using simple RESTful resources.

One benefit of the server being a simple JSON store is that it enables us to easily add redundancy to our apps – if server1 fails to deliver a response, fall back to server2.

No more HTML

The DOM is the means by which we display our app to the user. The browser thinks in terms of the DOM. HTML is just a serialisation of the DOM. Modern web app developers shouldn’t be thinking in terms of HTML. HTML is the assembly language of the web, and we should be working at a higher level of abstraction if we want to get stuff done. Most of the time we should be thinking in terms of layouts, widgets and dialogs, like grown-up UI designers.

The problem at the moment is that HTML is being used as a combined data and presentation format, and it should be obvious that this is a Bad ThingTM.

Of course at some point we’ll need to go down to the level of the HTML, and at that point we should be using templates. jQuery.tmpl is one (see my slides and presentation on the subject), but there are many others too. One interesting development (thanks to James Pearce for putting me onto this) is Model-driven Views (MDV).

MDV links JavaScript objects to the DOM in such a way that any changes to the object are automatically reflected in the DOM, and likewise, any user changes to the DOM are automatically reflected in the model objects. Hopefully this will become standard in modern browsers, as it provides a clean and easy way to keep the DOM up-to-date with the model objects without endless wiring, which again helps to insulate us from having to deal with too much HTML.

I’m not suggesting that HTML will go away, or that developers won’t need to learn it – just that most of the time, most developers won’t need to be worrying about it, just like most of the time, most C developers don’t need to worry about assembly code.

Conclusion

Most web-apps are currently halfway there in terms of moving functionality to the client. The problem is that we have ended up in the worst of both worlds as app developers. Our serverside MVC framework provides a nice template-based abstraction over the HTML, which we then break apart on the client. We’re forced to work at too many different levels of abstraction simultaneously, which is never a good thing.

Things were simple when everything happened on the server. Things will be simple again when everything happens on the client. Over time new tools and best practices will emerge to encourage this new way of working. In the meantime, it’s going to take a bit of extra effort, but it’ll be worth it.

The end of progressive enhancement revisited

May 29th, 2011 133 comments

This is a follow-up post to JavaScript and the end of progressive enhancement - you may want to read that first if you haven’t already. The comments are worth a read, as well as the Reddit thread.

The app/doc divide

What I didn’t make clear in my original post (because I wasn’t fully clear about it at the time) is the distinction between document-based web sites, and web applications. Documents are made to be read, whereas apps are made to be interacted with. James Pearce wrote a great description in the comments:

Actually what we’re maybe observing here is a clash of civilisations: the documentistas vs the applicationistas; web-as-a-medium vs web-as-a-technology-stack; designers vs programmers. It’s no wonder that progressive enhancement is a powerful tenet for the former of each pair to rally around… but not necessarily the most architecturally important consideration of the latter.

[James has since written a great, and highly relevant, post on the subject of URLs in JS apps.]

It goes without saying that apps and documents are two completely different things (even though there is a huge amount of overlap between the two). Trying to treat web design/development as a single discipline is a mistake. Anything that is primarily meant for reading, such as a newspaper website or a blog, exists as a collection of documents. I should be able to link to another blogger’s blog post and expect that in a week or a year that content will still be available at that address. I shouldn’t need to have JavaScript enabled in order to visit that address.

Web apps aren’t the same thing. A web app is an application that happens to use web technologies. Most web apps could be desktop apps – what makes a web app a web app is that it is accessed using a browser. No-one expects to be able to hyperlink to a particular view in Microsoft Excel – what would that even mean? In the same way, I can’t share a link to a particular email in Gmail. Web apps don’t always exist in the same web as everything else – many apps are islands.

Historically, web apps have been built in the document-based paradigm, using links to move to different parts of the app and forms to submit data for processing. The only reason they were made like this was because this was all the technology allowed. Now that technology has advanced, first with Ajax and now with HTML5, we aren’t tied to this old practice.

Amy Hoy summed it up nicely:

"graceful degradation" (and likewise, p.e.) died the moment we moved away from document design and into app design.
@amyhoy
Amy Hoy

The problem is that because everyone building stuff online is using the same technologies, there can be a tendency to think that there is one true way of using those technologies, independent of what they’re being used for. This is clearly false.

The end of progressive enhancement?

Progressive enhancement is still the way to make document-based sites on the web – there’s no denying that. But with applications the advantages are less clear. If we can accept the fact that the document-based paradigm isn’t the best way to make web apps, then we should also accept the fact that progressive enhancement doesn’t apply to apps.

JavaScript and the end of progressive enhancement

May 4th, 2011 60 comments

Progressive enhancement is the Right WayTM to do things in web development. It works like this:

  1. Write the HTML for your content, 100% semantically (i.e. only the necessary tags to explain the meaning of the content).

  2. Style the HTML using CSS. You may need to add hooks to your HTML in the form of classes and ids for the CSS to target.

  3. Add JavaScript enhancements to the interface, but only enhancements.

Parallel to this, the functionality of the site/app is progressively enhanced:

  1. All navigation must happen via links and form submissions – don’t use JavaScript for navigation.

  2. Add JavaScript enhancements to navigation, overriding the links and form submissions, for example to avoid page reloads. Every single link and form element should still work when JavaScript is disabled.

But of course you knew that, because that’s how you roll. I’m not sure this is the way forward though. To explain why I’ll need to start with a bit of (over-simplified) history.

A history lesson

Static pages

Originally, most sites on the web were a collection of static HTML pages saved on a server. The bit of the URL after the domain gave the location of the file on the server. This works fine as long as you’re working with static information, and don’t mind each file having to repeat the header, footer, and any other shared HTML.

Server-side dynamism

In order to make the web more useful, techniques were developed to enable the HTML to be generated on the fly, when a request was received. For a long time, this was how the web worked, and a lot of it still does.

Client-side dynamism

As JavaScript has become more prevalent on the client, developers have started using Ajax to streamline interfaces, replacing page loads with partial reloads. This either works by sending HTML snippets to replace a section of page (thus putting the burden of HTML generation on the server) or by sending raw data in XML or JSON and letting the browser construct the HTML or DOM structure.

Shifting to the client

As JavaScript engines increase in speed, the Ajax bottleneck comes in the transfer time. With a fast JavaScript engine it’s quicker to send the data to the client in the lightest way possible and let the client construct the HTML, rather than constructing the HTML on the server and saving the browser some work.

This raises an issue – we now need rendering code on the client and the server, doing the same thing. This breaks the DRY principle and leads to a maintenance nightmare. Remember, all of the functionality needs to work without JavaScript first, and only be enhanced by JavaScript.

No page reloads

If we’re trying to avoid page reloads, why not take that to its logical conclusion? All the server needs to do is spit out JSON – the client handles all of the rendering. Even if the entire page needs to change, it might be faster to load the new data asynchronously, then render a new template using this new data.

Working this way, a huge amount of functionality would need to be written twice; once on the server and once on the client. This isn’t going work for most people, so we’re left with two options – either abandon the “no reload” approach or abandon progressive enhancement.

The end of progressive enhancement

So, where does this leave things? It depends on how strongly you’re tied to progressive enhancement. Up until now, progressive enhancement was a good way to build websites and web apps – it enforced a clean separation between content, layout, behaviour and navigation. But it could be holding us back now, stopping the web moving forward towards more natural interfaces that aren’t over-burdened by its history as something very different to what it is today.

There are still good reasons to keep using progressive enhancement, but it may be time to accept that JavaScript is an essential technology on today’s web, and stop trying to make everything work in its absence.

Or maybe not

I’m completely torn on this issue. I wrote this post as a way of putting one side of the argument across in the hope of generating some kind of discussion. I don’t know what the solution is right now, but I know it’s worth talking about. So let me know what you think!

Appendix: Tools for this brave new world

Backbone.js is a JavaScript MVC framework, perfectly suited for developing applications that live on the client. You’ll want to use some kind of templating solution as well – I use jQuery.tmpl (I’ve written a presentation on the topic if you’re interested in learning more) but there are lots of others as well.

Sammy.js (suggested by justin TNT) looks like another good client-side framework, definitely influenced by Sinatra.

If anybody has any suggestions for other suitable libraries/frameworks I’ll gladly add them in here.


Edit: I’ve now written a follow-up to this post: The end of progressive enhancement revisited.

Magic in software development

April 24th, 2011 5 comments

First off, so we’re on the same page, we need to be talking in the same terms. So, what is magic? I’d define it as anything below your current level of abstraction that you don’t understand.

SICP cover

I first started thinking about this topic because of this angst I felt about all this magic I was relying on. There’s so many things that I rely on every day and I have no idea how they work. As far as I’m concerned, they’re magic. As long as I think about these things as magic, they seem unknowable. I think that’s where the angst comes from. What I need to remind myself is that everything I’ve learned about software seemed like magic before I understood it, and there’s nothing that’s unknowable, just things that aren’t known yet.

This post is my attempt to come to an understanding of what this ‘magic’ is, whether it’s a problem, and how best to deal with it.

The ‘Dave’ technique

At University, I learned how to record music. We recorded onto tape, so we had to learn how a tape machine worked. To learn how a tape machine worked, we had understand hysteresis and remanence and modulation and various other things that I’ve mostly forgotten now. We also had to understand how radio worked, so we learned about amplitude and frequency modulation, and how stereo FM was built on top of mono FM with an AM difference signal on top so as to be backwards compatible, and various other technical issues. Then came digital audio with ADCs, DACs, sampling, quantisation, dithering, etc. Each of these three topics was one or two modules, i.e. a semester’s-worth of lectures, so we went pretty deep.

Did that knowledge make me a better recording engineer? Probably not. But it was a helpful basis for the latter things I learned, which did help make me a better recording engineer.

The ‘Tim’ technique

Another lecturer taught us computer audio. This started off with an introduction to computers, starting at the level of AND, OR and NOT gates, then on to NAND and NOR (and how the simpler to understand AND, OR and NOT gates can be implemented in terms of NAND and NOR), then on to the ALU, then the CPU, then adding memory and disk storage and network and MIDI connections, creating a full computer. This was all presented in two or three lectures, so inevitably certain steps had to be left out (e.g. “we put together a load of these gates and we get the ALU”).

The benefit of this approach was that we were given a vague conceptual understanding of the basis on which computer audio is built, without having to spend hours and hours learning the full intricacies.

Bottom-up

If we’re intent on uncovering all the magic, how should we learn – bottom-up or top-down? Bottom-up, right from the bottom, implies first learning enough physics to understand electronics, which you’d need to understand digital circuit design, which you’d need to understand CPU design, which you need to understand assembly language, which you need to understand C, then enough C to understand Ruby (say). You’ll also need to understand how networks work right from the bottom of the TCP/IP stack and beyond; how storage works right from the level of hysteresis in magnetic particles on a hard disk; how RAM works from the level of individual capacitors; etc.

This reminds me of the famous Carl Sagan quote:

If you wish to make an apple pie from scratch, you must first invent the universe.

Top-down

Top-down is essentially the process followed by Structure and Interpretation of Computer Programs, at a micro and macro level. At the micro level, we are taught to solve problems using “wishful thinking”: first represent the problem using large custom building blocks, then build the pieces those blocks are made out of using language primitives. And at the macro level, the book teaches the workings of Scheme through a series of increasingly complex models.

Bottom-up vs top-down

The problem with the bottom-up approach is it would take decades of studying before you were let near an interpreted language. This approach may have worked in the fifties when there wasn’t as much to learn. But these days you won’t get anything useful done.

The problem with the top-down approach is that the levels we work at these days are so large, you can’t just learn all of your current level and then start to look at the lower levels, because you’d never finish learning all the details of the current level.

Leaky abstractions

Joel Spolsky has something to say on this matter in his piece The Law of Leaky Abstractions. This basically says that all abstractions are leaky, meaning that we cannot rely on them to shield us from the levels below our current level. So, to work at the current level we must learn the lower levels. It’s OK to work at the level of the abstraction, and it will save us time working at that level, but when it breaks down we still need to understand why. As Joel says:

the abstractions save us time working, but they don’t save us time learning.

Magic’s alright, yeah

Some of us don’t like the idea of magic. It feels like cheating. But it’s useful as a placeholder, something to learn about later; not now. It’s useful to delve down to lower levels, understanding how the abstractions we work with every day are implemented, but at some point the law of diminishing returns kicks in. (In some fields, we can’t even assume we’ll ever learn how the magic works. As @sermoa said, “we don’t understand exactly how quantum physics works but we accept that it does and make good use of it”.)

What we need to get to, eventually, is an understanding of the whole stack, but at greater and greater granularities as we get further away from our main level. So, if you’re a Ruby on Rails programmer, you need to know most of Ruby (but not all of it). It’s helpful to know a bit of C, and a bit of how the operating system responds to certain commands. Below that level, it’s good to have a vague understanding of how a computer works. And it’s useful to know that electrical signals can only transmit at a finite speed, and that there’s a physical limit to the number of transistors in a processor. As time goes on you can begin to flesh out these lower levels, remembring that the higher levels are generally going to be more beneficial to your day-to-day work.

Before you’ve delved deeper, those lower levels are magic. And that’s fine.


Thanks to @marcgravell, @ataraxia_status, @sermoa, @bytespider, @ghickman, @SamirTalwar and @josmasflores for their input on this post.

Also, thanks to Dave Fisher and Tim Brookes for being the sources of the ‘Dave’ and ‘Tim’ techniques.

Categories: Programming Tags: ,

Closures explained with JavaScript

April 22nd, 2011 22 comments

Last year I wrote A brief introduction to closures which was meant to help people understand exactly what a closure is and how it works. I’m going to attempt that again, but from a different angle. I think with these kinds of concept, you just need to read as many alternative explanations as you can in order to get a well rounded view.

First-class functions

As I explained in Why JavaScript is AWESOME, one of the most powerful parts of JavaScript is its first-class functions. So, what does “first-class” mean in a programming language? To quote wikipedia, something is first-class if it:

  • can be stored in variables and data structures
  • can be passed as a parameter to a subroutine
  • can be returned as the result of a subroutine
  • can be constructed at runtime
  • has intrinsic identity (independent of any given name)

So, functions in JavaScript are just like objects. In fact, in JavaScript functions are objects.

The ability to nest functions gives us closures. Which is what I’m going to talk about next…

Nested functions

Here’s a little toy example of nested functions:

The important thing to note here is that there is only one f defined. Each time f is called, a new function g is created, local to that execution of f. When that function g is returned, we can assign its value to a globally defined variable. So, we call f and assign the result to g5, then we call f again and assign the result to g1. g1 and g5 are two different functions. They happen to share the same code, but they were executed in different environments, with different free variables. (As an aside, we don’t need to use a function definition to define g and then return it. Instead, we can use a function expression which allows us to create a function without naming it. These are called ‘anonymous functions’ or lambdas. Here’s a version of the above with g converted to an anonymous function.)

Free variables and scope

A variable is free in any particular scope if it is defined within an enclosing scope. To make that more concrete, in the scope of g, the variable x is free, because it is defined within the scope of f. Any global variables are free within the scopes of f and g.

What do I mean by scope? A scope is an area of code where a variable may be defined, without the enclosing scope knowing about it. JavaScript has ‘function scope’, so each function has its own scope. So, any variable defined within f is invisible outside of f. Scopes can be nested, so in the above example, g has its own scope which is contained within the scope of f, which is contained within the global scope. Whenever a variable is accessed, the JavaScript interpreter first looks within the current scope. If the variable is not found to be defined within the current scope, the interpreter checks the enclosing scope, then the enclosing scope of the enclosing scope, all the way up to the global scope. If the variable is not found, a ReferenceError is thrown.

Closures are functions that retain a reference to their free variables

And this is the meat of the matter. Let’s look at a simplified version of the above example first:

It’s no surprise that when you call f with the argument 5, when g is called it has access to that argument. What’s a bit more surprising is that if you return g from the argument, the returned function still has access to the argument 5 (as shown in the original example). The bit that can be a bit mind-blowing (and I think generally the reason that people have such trouble understanding closures) is that the returned g actually is remembering the variable x that was defined when f was called. That might not make much sense, so here’s another example:

When person is called, the argument name is bound to the value passed. So, the first time person is called, name is bound to ‘Dave’, and the second time, it’s bound to ‘Mary’. person defines two internal functions, get and set. The first time these functions are defined, they have a free variable name which is bound to ‘Dave’. These two functions are returned in an array, which is unpacked on the outside to get two functions getDave and setDave. (If you want to return more than one value from a function, you can either return an object or an array. Using an array here is more verbose, but I didn’t want to confuse the issue by including objects as well. Here’s a version of the above using an object instead, if that makes more sense to you.)

And this is the magic bit. getDave and setDave both remember the same variable name, which was bound to ‘Dave’ originally. When setDave is called, that variable is set to ‘Bob’. Now when getDave is called, it returns ‘Bob’ (Dave never liked the name ‘Dave’ anyway). So getDave and setDave are two functions that remember the same variable. This is what I mean when I say “Closures are functions that retain a reference to their free variables”. getDave and setDave both remember the free variable name. Even though person has now returned, the variable name lives on, because it is referenced by getDave and setDave.

The variable name was bound to ‘Dave’ when person was called the first time. When person is called a second time, a new version of name comes into existence, as well as new versions of get and set. So the functions getMary and setMary are completely different to the functions getDave and setDave. They execute identical code, but in two different environments, with different free variables.

Summary

In summary, a closure is a function called in one context that remembers variables defined in another context – the context in which it was defined. Multiple closures defined within the same context remember that same context, so changes they make are shared between them. Every time a function is called that creates closures, a new, shared context is created for the new closures.

The best way to learn is to play, so I’d recommend editing the fiddles above (by clicking on the + at the top right) and having a fiddle. Enjoy!


Addendum: Lasse Reichstein had some useful comments on this post on the JSMentors mailing list – read them here. The important thing to realise is that a closure actually remembers its environment rather than its free variables, so if you define a new variable in the environment of the closure after the closure’s definition, it will be accessible inside the closure.

jQuery vs DOM return false

March 22nd, 2011 2 comments

What does return false do inside a JavaScript event handler? What does it do in a jQuery event handler? Are they the same thing?

The short answer is “no”. return false in a native JavaScript event handler prevents the default behaviour of the event. It’s the equivalent of event.preventDefault(). This is the same for DOM level 0 event handlers like this:

element.onclick = function () { };

and DOM level 2 event handlers like this:

element.addEventListener('click', function () {});

return false in jQuery, on the other hand, will stop the default behaviour and stop the event propagating. This can be seen in the jQuery source:

if ( ret === false ) {
  event.preventDefault();
  event.stopPropagation();
}

If the return value of the handler is false, jQuery will call preventDefault and stopPropagation on the event object.

I’ve made a fiddle to demonstrate this behaviour, showing what return false does with DOM level 0 handlers and with jQuery handlers, and how to achieve the same in a DOM level 2 handler.

Categories: Programming Tags: ,

jQuery.tmpl() presentation

March 20th, 2011 1 comment

Back in January I did a presentation at the Bristol Ruby User Group on jQuery.tmpl() – jQuery’s templating engine.

The presentation was filmed and is available on the BRUG website. The slides are also available.

I wrote the slideshow engine using jQuery.tmpl() – if you’re interested in viewing some real-world jQuery templating, have a look at the source on Github. I tried to use as many of the concepts introduced in the presentation as possible, so it’s a useful showcase of what can be achieved using jQuery templates.

Categories: Programming Tags: ,

id_barcode – a barcode maker for Adobe InDesign

March 4th, 2011 6 comments

id_barcode is multiple things. It’s an example of writing structured, modular code for an InDesign plugin. It’s a demonstration of test-driven development for producing InDesign plugins. It also makes barcodes.

InDesign barcode maker

First off, this is a barcode maker for InDesign. It’s fairly simple – just put in your ISBN, and choose the font for the ISBN and for the numbers under the bars.

The script file is available to download here. If you don’t know how to install an InDesign script, see these instructions on InDesign Secrets.

Here it is:

id_barcode dialog

and this is what the barcode looks like:

Pretty wild.

Writing modular InDesign plugins

I split id_barcode across four files:

Really barcode_main.js should be split up into two files, one for the GUI and one for rendering the barcode.

Each part of the code does one thing. barcode_library doesn’t know anything about InDesign, all it does is produce a data structure giving the relative bar widths. The GUI code doesn’t contain any logic, it just lets the user enter the relevant details. Then the rendering code takes the barcode from the GUI, uses the library to get the bar widths, and draws the barcode with these widths and the fonts selected by the user.

Because I wanted to make the plugin easy to use, I wrote a shell script to concatenate the relevant JavaScript files and remove the #import lines. This was pretty straightforward.

Test-driven development

I’ve been reading Test-Driven JavaScript Development – an excellent book. I used some of the basics from that to construct a very basic testing framework, contained in barcode_test.js. Also in that file are a number of tests used to ensure that barcode_library.js was doing the right thing. Every time I changed something, or refactored, rather than checking to see if the barcodes still came out correctly I could just run the tests and get instant feedback. I haven’t written tests for the rendering code, but that would be a good next step.

Next steps

So far this plugin is very basic. You can’t customise anything apart from the fonts, so if you standardly use a different barcode design you’d need to do manual work to each barcode. The error handling’s a bit rubbish as well. If I make it more customisable, I think it would be worth test-driving the layout changes. The most important thing is to write a test that ensures the bars are all the correct width. I’d then have to start delving further into InDesign’s object model, which is a bit of a mess. We’ll see.

If anybody’s interested in contributing you can fork me on github!

Categories: Programming Tags: ,

A short word on nomenclature

February 26th, 2011 15 comments

These symbols have accepted names (in the context of programming):

  • [ ] These are opening and closing brackets. They are square, so are sometimes called square brackets.
  • { } These are opening and closing braces. You could call them curly braces, but there’s no need.
  • ( ) Theses are parentheses. One is a parenthesis. If those are a bit of a mouth- or keyboardful, call them parens. Don’t call them brackets or I’ll destroy your keyboard.
  • ~ This is a tilde.
  • | This is a pipe.

These symbols have multiple accepted names.

  • # I call this a hash because I’m British. Americans call it a pound sign. Pedants call it an octothorpe.
  • * Asterisk, star, splat. Definitely not an “asterix”.
  • ! Exclamation mark/point, bang.
  • < > Less-than and greater-than, but may also be called angle brackets.
  • . Full-stop, period, dot.
  • ? Question mark, query.
Categories: Programming Tags:

Why you should learn brainfuck (or: learn you a brainfuck for great good!)

February 20th, 2011 18 comments

Before I begin, a little disclaimer: there’s no way to write about brainfuck without offending someone. Some people will be upset about the swearing, others about the censorship. I’ve come up with a partial solution: Decensor this article (decensor plugin available on github) If you’re reading this in a feed reader then sorry for the swearing.

What is brainfuck?

Brainfuck is close to being the simplest programming language possible, with only 8 instructions:

> < + - , . [ ]

These instructions move an internal data pointer, increment and decrement the value at the data pointer, input and output data, and provide simple looping.

As an aside: brainfuck was written with the intent of having a language with the smallest-possible compiler. Many compilers for brainfuck are smaller than 200 bytes! See Wikipedia for more details.

Why would I want to learn such a stupid language?

It’s been suggested that you should learn at least 6 programming languages to be a good programmer. The more programming languages you know, the more perspectives you’ll have on problems. Brainfuck is such a simple language to learn, there’s almost no reason not to learn it. If you read the whole of this blog post now, and try out all the code samples in the interpreter, in half-an-hour to an hour you’ll have a new programming language under your belt. Tell me that’s a waste of time :)

Another good reason to learn brainfuck is to understand how basic a Turing-complete programming language can be. A common argument when programmers compare languages is “well they’re all Turing-complete”, meaning that anything you can do in one language you can do in another. Once you’ve learnt brainfuck, you’ll understand just how difficult it can be to use a Turing-complete language, and how that argument holds no water.

Ok, you’ve convinced me. Teach me!

Good. I knew you were one of the smart ones.

Brainfuck doesn’t have variable names – just one long array of cells, each of which contains a number:

address: 0  1  2  3  4  5  6  ...
value:  [0][0][0][0][0][0][0][...]

Each cell is initialized to zero. A data pointer starts off pointing to the first cell:

pointer: v
address: 0  1  2  3  4  5  6  ...
value:  [0][0][0][0][0][0][0][...]

Moving the data pointer and modifying the data

A brainfuck program is a stream of the 8 commands (other characters are allowed in this stream but are ignored). Here’s a basic brainfuck program:

>>>>++

The greater-than command moves the data pointer one cell to the right. The plus command increases the value of the cell under the data pointer by 1. Here’s what the data looks like after we run the above program:

pointer:             v
address: 0  1  2  3  4  5  6  ...
value:  [0][0][0][0][2][0][0][...]

The data pointer moved four cells to the right, and the value of that cell was increased by 2. Pretty simple.

You can probably guess what the less-than and minus commands do:

program: >>>>++<<++-

pointer:       v
address: 0  1  2  3  4  5  6  ...
value:  [0][0][1][0][2][0][0][...]

So, move four cells right, increment twice, move two cells left, increment twice and decrement once.

Well done, you’ve already learnt half of the syntax of brainfuck.

I/O

A programming language isn’t much use without the ability to input and output data. Brainfuck has two commands for I/O – , (comma) and . (full-stop/period). The comma inputs a character from the input into the current cell, and the period outputs the character in the current cell. The ASCII code of the character is used on input and output. You may not be used to interchanging characters and integers, so it’s worth having a look at this chart to see how they map.

Here’s a simple program that inputs a character, increments it once, then outputs it:

program: ,+.
input:   a

pointer:  v     
address:  0  1  2  3  4  5  6  ...
value:  [98][0][0][0][0][0][0][...]

The program takes a character from the input, in this case the letter ‘a’, and puts it into the first data cell. It then increments it, and outputs the value of the cell. A lowercase ‘a’ has the ASCII code 97, and ‘b’ has the ASCII code 98.

Try it out. Go to my brainfuck interpreter, put the string ,+. into the “Code” box and the letter ‘a’ into the “Input” box (or use this link), then press “Run”. Try it with different input, then try using more pluses or minuses.

Every time you use the comma command you remove a character from the input stream:

program: ,>,>,.<.<.
input:   abc

pointer:  v     
address:  0   1   2  3  4  5  6  ...
value:  [97][98][99][0][0][0][0][...]

This program puts the first character of input in the first cell, the second character in the second cell and the third character in the third cell (although it looks like an evil dragon smiley). Try it out to see what happens.

Looping

Ok, that’s three-quarters of the language covered now. All that’s left is looping. This is a bit trickier, but fairly simple once you’ve got the hang of it.

[ and ] (left and right brackets) are used for looping. Anything in between pairs of brackets will loop (you can have nested loops – the pairs match like parentheses (i.e. this is the equivalent of an inner loop) and this is the outer loop (did you see what I did there? (inner inner!))). Of course there’s no point looping forever, so brainfuck needs a way of knowing when to stop. It does this by checking the value of the current data cell to see if it is zero. If it is, execution will skip to after the end of the loop.

To illustrate this I’m going to need to show the position of the current instruction. This is called the instruction pointer, or i_ptr in the figure below.

To start with, the ‘z’ is read into the first cell:

i_ptr:   v
program: ,[.-]
input:   z

pointer:  v     
address:  0   1  2  3  4  5  6  ...
value:  [122][0][0][0][0][0][0][...]

The instruction pointer moves to the next instruction in the program. It checks to see if the value in the current data cell is zero. It isn’t, so the loop is entered.

i_ptr:    v
program: ,[.-]
input:   z

pointer:  v     
address:  0   1  2  3  4  5  6  ...
value:  [122][0][0][0][0][0][0][...]

The value in the current data cell is output (‘z’), then decremented:

i_ptr:      v
program: ,[.-]
input:   z

pointer:  v     
address:  0   1  2  3  4  5  6  ...
value:  [121][0][0][0][0][0][0][...]

The instruction pointer reaches the end of the loop and jumps back to the beginning:

i_ptr:    v
program: ,[.-]
input:   z

pointer:  v     
address:  0   1  2  3  4  5  6  ...
value:  [121][0][0][0][0][0][0][...]

The current cell is still not zero, so the loop is entered again, the new value is output (‘y’), and decremented again. This keeps on going until the value of the first data cell is zero. At this point, the instruction pointer jumps to after the end of the loop, which also happens to be the end of the program:

i_ptr:        v
program: ,[.-]
input:   z

pointer: v     
address: 0  1  2  3  4  5  6  ...
value:  [0][0][0][0][0][0][0][...]

Try it out to see what happens.

Refresher

And that’s the entire language. Here’s a quick recap:

  • > Move the data pointer one cell to the right
  • < Move the data pointer one cell to the left
  • + Increment the value of the cell at the data pointer
  • - Decrement the value of the cell at the data pointer
  • , Take a character from the input and place its value into the current data cell
  • . Output the value of the current data cell as a character
  • [ If the current data cell is zero, skip to after the closing bracket, otherwise continue
  • ] Skip back to the matching opening bracket (a common optimization is to skip over this instruction if the current cell is zero, rather than going back to the opening bracket and checking)

The end

If you’ve read the whole blog post and tried out all the code, you now know brainfuck. Well done, that’s another item for your CV! If you try making anything relatively complex you’ll realise the true value of the abstractions we build software on. All languages have different levels of abstraction, and you should be working at the highest level you can afford. It’s worth dropping down to the level of brainfuck occasionally so you can really appreciate the abstractions you’re given.

Further reading

Categories: Programming Tags: ,