This Code is Such a Brainf*ck — No, Really!
While languages such as Brainf*ck and the more kid-friendly Ook! (in name only) are generally left to the realm of toys and bragging rights, their real beauty is having an extremely simple turing complete interactive environment in which to learn underlying computer science concepts.
Engineers like to do things differently, and nothing demonstrates this more than the plethora of esoteric programming languages available. Usually relegated to research projects of debatable value, toys and bragging rights the ability to strip back to the bare metal of the computer hardware, of even an emulation thereof, can be of huge educational value for the legion of high level software developers who have no understanding on exactly a pixel is actually rendered on a screen.
For example, a code sample in the unfortunately named Brainf*ck.
++++++++++ // Set first cell (counter) to 10
[
> // Move to next cell (output)
+ // Increase value of current cell
. // Display value of current cell
< // Move to previous cell (counter)
- // Decrease value of current cell
]
The above commented code simply displays the value 1 to 10 on the output. A few things to note:
- Memory cells can be used for any purpose, their use as described in the above comments, is to aid in understanding only.
- Code blocks (defined by ‘[' and ']‘) continue to execute while the current memory cell is greater than zero.
- Brainf*ck compilers/interpreters typically display output as ASCII symbols, so running this program will not display actual characters.
- Seven of the eight available operations, with the exception of read value to current cell indicated by a comma (‘,’), are represented in the example program.
- Layout, whitespace and unknown characters are (or at least should be) ignored.
The program can be executed with an online interpreter. To see the output rendered in a human readable form you will need to use debug-mode as the ASCII symbols for number 1 to 10 are control characters and do not normally display anything on screen.
Using only eight instructions with an implicit operand makes this an excellent model for understanding memory allocation and for thinking about how these operations can be completed at the basic level. The use of ASCII output highlights the relation between the decimal value of a memory cell and it’s on screen representation. Parallels can also be drawn with assembly language programming. The highly reduced instruction set, again, coupled with implicit operands and pointer, provides a deeper insight to how a modern microprocessor might carry out instructions and introduces the thought processes required to understand memory addressing and operations.
While such and intricate understanding of the underlying implementation details of computer hardware is arguably not essential, and as such only peripherally taught in many modern degree level computer science course, esoteric programming languages such as Brainf*ck can help developers understand these underlying concepts of the digital computer by giving them an interactive path for investigation and have the potential to bring about a more enlightened, openminded and flexible developer workforce if their educational value is properly exploited — despite some rather institution unfriendly names.
Going Loopy with Loops
Reinventing the wheel can often give a deeper understanding of the problem and highlight some of the esoteric features of your chosen programming language — however, remember to go back to using the standard method and style in your production code!
I like loops, they are predictable, reliable and relatively easy to understand. For many common algorithms there are much more efficient ways of computing the solution, however loops often provide an easy to understand approach to getting to the right answer — eventually.
Recently, when demonstrating looping constructs to a beginner I provided the following three examples which spit out 1 to 10 on the terminal.
// Traditional
for(int i = 1; i <= 10; i++) {
System.out.println(i);
}
// Unorthodox
int i = 0;
while(i < 10) {
System.out.println(i+1);
i = i + 1;
}
// Too smart for own good
for(int i = 0; i < 10; System.out.println(++i));
Each sample was slightly more complex, conceptually, than the next. The final sample demonstrating how the for could be abused to show the desired output on only one correctly formatted line. In it we use my favourite pre-increment operator to push the the 0 up to 1 before we output the number to the display. Of course we could have used 1 and 11 as our bound with the post-increment operator, but any sane programmer would agree that numbering should start at zero.
Extending the code abuse further, while browsing over at Stack Overflow I discovered that while is largely redundant, if you are happy to abuse for some more. Turns out that for, as typically defined, assumes the test condition to be true when omitted and all three sections of the for statement are in fact optional. As one of the moderators put it:
This answer pretty much proves the awesomeness of the “No question is too simple” policy.
— Bill the Lizard
Likewise, while browsing an interesting article on The Daily WTF which highlights a simple method for square root calculation my muse overcame me. The article makes it quite clear that such iterative approximations are not highly regarded (unless you are John Carmack), however, it reminded me of a simple pi calculator that I wrote using JavaScript a number years ago when similarly inspired.
Armed with new knowledge about the abuse of for and an entirely redundant algorithm to code I set about developing a square root function.
double sqrt(double n) {
for(double r = 1; r != n; n = r == (r = 0.5 * (r + (n < 0 ? -n : n) / r)) ? r : n);
return n;
}
There are so many things wrong with this I’m not sure where to start. How about the blatant abuse of the parameter n as both the input and output, simply to avoid declaring another variable? This requires the break condition to determine whether the usually untouched n contains the currently calculated value of the result.
The final chunk of code actually does the calculation of the square root while deterministically assigning the value to n to terminate the loop and return the result. The calculation itself is relatively simple: is the average of our calculated root, r, and n / r equal to the previous value of r? If not, further refine r in the same way.
r == ( 0.5 * ( r + n / r ) )
The calculation, as implemented in my sqrt() function, is complicated somewhat by the embedded assignment of the new value to r, the poor-mans error handling of negative numbers (who wants to deal with imaginary numbers anyway?) and the inline if used to assign the final value to n.
Of course, we could always use the built in Java Math.sqrt() method which efficiently passes the calculation off to the hardware, but where’s the fun in that!?
The Future of Software Development
The future of software development is not found in a language, technology or technique but dependant on having a critical mass of educated individuals who apply themselves to the discipline.
I like to romanticise the history of computer science, the days where everything you could possibly need to know about a computer was printed in the included manual, from the schematic from which it was built right up to user guides explaining how to use the included software, if any. I envy those were lucky enough to be there when computers first became affordable to the general populous and they could know everything there was to know about the machine they had purchased.
As times marched on and graphical user interfaces became the norm, abstracting users from the tangled mess of syntax familiar to those using the command line, and I was born. Microsoft Windows 2.0 was just about to roll off the production line and Apple was introducing multitasking into their operating system, System 5, for the Macintosh SE and Macintosh II. Both companies laying the foundation for the computers people know and love (or hate) today.
Here in the UK, the government had been focusing of the computer literacy for around 5 years and a series of BBC programmes introduced the population to software development on the BBC Micro which was available, due to government grants, in every school and in high street retailers across the land. While I was a little late to this party, a suite of these machines were available for my use in the school computer lab and I cut my teeth on BASIC while everyone else was drawn to the pretty pictures available on the successor computers running the graphical operating system RISC OS.
There are no such drives today. While there are some general technology policies for a so called ‘Digital Britain’ concerning itself with accessible broadband and access to information there is little in the way of encouraging youth to look at computers as anything other than social entertainment devices. While I applaud the efforts of companies such as Apple to create ‘technology for the rest of us’ the increasingly limited access to the hardware will no doubt negatively affect the skill of the software developers of the future.
As computer science as a whole progresses so does it’s development tools. What was once a simple power-on prompt where the words
PRINT "Hello, World!"
would elegantly demonstrate the innate power and infinite control of the machine avaliable, users are now instead presented with ostensibly easy-to-use, but exceedingly imposing and complex environments each with their own preferred conventions in which to work. Scripting languages like Python rekindle this spirit but at the expense of being totally incongruent with the interfaces to which users have become accustom.
One area in which Microsoft should be commended is their continued high quality support of software developers. Not only does Microsoft have a comprehensive press for their extensive library of developer references but provides high quality, accessible, and often free, tools and resources. Microsoft actively target potential developers with their Beginner Developer Learning Center and specifically Kids Corner and Small Basic.
Microsoft, here, dare to fail. Small Basic is not a finished product. It has it’s flaws. The hodge-podge of objects and parameterless sub-routines makes Small Basic a little confusing for new and experienced developers alike, but in a spirit of openness the lead author has ensured solid interaction with a community of developers resulting in gradual improvement to the fledgling product. It is, no doubt, a great effort in making computing, the way I want to remember it, accessible again. While I can understand efforts like Alice and Scratch, essentially the Lego of programming, their relation to ‘real world’ development is questionable at best. In holding this view I have to question Microsoft’s own choice and the value of yet another (intentionally hobbled) language, but here the ‘Graduate’ functionality is standing by for those ready to move on.
Without drives like Microsoft’s to bring development tools, most crucially at an appropriate level, to the masses students will continue to confuse computer science with ‘IT’. As the potential of those who, had they been able to overcome the initial hurdles of development, would have gone on to create great software is wasted the true power of technology will be limited to a smaller and smaller elite who were lucky enough to have been exposed to development in the right way and at the right time. While technological dictatorship certainly has its benefits, democratisation, the freedom of knowledge and open participation is the driving force behind the computer revolution of today.
Thoughts on Computer Science Education
While the old adage “Computer science is no more about computers than astronomy is about telescopes.” is often brought to bear, I often have to ask “But how else is one supposed to chart the heavens?”.
Throughout my time at school, college and university I have been passionate about the standard of the education provided to not only myself, but my fellow students as well. At many stages I’ve wondered, could I do a better job and teaching has always been something I would consider doing given the opportunity.
While I’m not an ‘activist’ student or even one who would voluntarily join the popularity contest which masquerades as a student parliament, or whatever the institution in question happens to call it (no, I’m not bitter, I’ve never run), I do try take an active role in shaping my learning experience.
Back in 2006 Jeff Atwood of Coding Horror wrote an interesting piece regarding the teaching of programming to computer science students. In the paper to which he refers the authors, for the most part, write off a large proportion of students and their ability to ever learn the skills required. However, the paper does have some interesting points, such as the following footnote.
Nowadays in the UK one has to say that they ought to fail, but because of misguided Quality Assurance procedures and the efforts of colleagues who doggedly believe in the normal curve, very many of them are mistakenly and cruelly ‘progressed’ into following courses. That process so far degrades the quality of their education and the reputation of computer science as an academic discipline as to be of burning commercial, professional and intellectual importance, but in this paper it must be by the by.
This somewhat struck a chord. Whenever big programming projects are due and I’ve got time to spare I make myself available to my peers and even in our second year I find students who are still unsure of the correct placement of semicolons in their Java code. Was it fair — to them — that they were progressed into the second year?
Testing What You Teach
In December 2008, the first year of my computer science course, the class was given a 1 hour, open-book programming test. The failure rate was astronomical and, if I recall the figures correctly, one of the lecturers informed us that of the first 50 projects he attempted to run from his test harness none of them compiled, let alone ran — at which point he gave up and began grading manually. The test was actually relatively simple, manipulating our numeric student ID in various ways and displaying the results on the terminal; the threshold for a pass was simpler still: anything that compiled, regardless of if you attempted to answer any questions. At this point it is probably prudent to note that IDE (if you can call it that) which we were using at the time was BlueJ and as you may imagine new projects compiled by default.
Regardless of the perceptual ease of this assignment I wrote a 2500 word essay on all the things wrong with the exam, including an alternative question set which I felt was more appropriate and focused on the objects first teaching style to which we had been exposed rather than the mathematically heavy string and integer manipulation. I felt that while students likely grasped Java to a reasonable standard, it was likely that the totally left-field questions and the untaught functional style required to answer the questions was the root of the problem, but the problems ran much deeper than that.
Syntactical Challenges
During the exam season in the following May we were given a written exam for the same class. While I don’t have a copy of the exam paper (the ethics of which are moot as first year students now take Python as part of a fully re-designed module instead) I have prepared an example question from the paper as it was presented:
5. Why does the following Java code fail to compile? (1 mark)
The astute among you may notice the error message at the bottom of the editor and the associated yellow highlight on the relevant line of code which in no uncertain terms explains why the code, does indeed, fail to compile. Yes, the answer to the exam question was in plain text in the question itself. When I asked students about this after the exam none of those I spoke to claimed to have noticed this and many professed that they did not answer the question at all. In light of this revelation my 6 page rant at the teaching staff regarding functional vs. object-oriented programming styles seemed rather redundant.
Despite this, which was said to have been an essential and doubly weighted module, it appears very few students were not progressed through to the second year.
Building a Team Environment
Our second year programming assignment was done as a group project and as such I expected there to be appropriate collaboration tools at our disposal, I was sorely disappointed. Each of my repeated request for collaboration tools to be made available were summarily turned down. Despite independent research into appropriate collaborative solutions being a requirement of the module, support from the teaching staff was noticeably lacking and no mention of the options available was made.
When I made both a Trac and Subversion (SVN) server available for my group to use they were clearly in awe and immediately saw the huge potential over passing .zip files of code back and fourth as most (if not all) of the other groups were forced to do. Of course, this configuration was neither sanctioned nor easy as I had to setup each of my group members with pre-compiled binaries of subversion and have them take up a fair percentage of the allocated storage on their mapped network drive.
In addition, despite being told we would have total control over the database schema for the project the entire class was given a single login to a single, poorly designed database on the provided database server. As you can imagine the database was quickly reduced to meaningless gibberish as around 150 students hammered away at it with different perceptions of what where appropriate values for each field with their buggy code. Here I was not alone in setting up my own database for the project for our software to use, insulating us from the chaos and allowing some subtle re-engineering to simplify development.
Solving Problems
The ability to work so closely with a group of inexperienced developers allowed me to note another interesting conundrum. Some students just don’t know how to tackle a problem programmatically. For example, I gave the following code snippet to a student in my group who was having trouble getting started.
public ArrayList<Donor> name(String name) {
ArrayList donors = new ArrayList();
// Get an iterable list of all Donors
Donors allDonors = new Donors();
// TODO: Search for [name] in each donors' name
// - Add matching donors to [donors] list
return donors;
}
Where Donors is a fully documented and conveniently packaged database access class representing all rows in the donor table (unless constructed otherwise) as simple data-bearing Donor objects, and inherits from the familiar and iterable ArrayList.
40 minutes later no progress had been made. Straight forward enough you may think, but still you have to give each student their due, this still doesn’t solve the problem — and maybe it is not obvious to everyone what to do now. Despite the clue in the return type, initially the student believed that the method should return the name of the user who was being searched for until we discussed the limited value in this response as we already knew the name of the person we were looking for. I prompted the student still further by asking
What would you do if I gave you the list on paper?
We discussed the repetitive task of going down the list, checking to see if the name matched and the proceeding to copy the donors’ details to another sheet of paper if the search term matched before drafting the following solution together.
public ArrayList<Donor> name(String name) {
ArrayList donors = new ArrayList();
// Get an iterable list of all Donors
Donors allDonors = new Donors();
for (Donor d : allDonors) {
if (d.getName().toLowerCase().contains(name.toLowerCase())) {
donors.add(d);
}
}
return donors;
}
A totally workable iterative solution. Gets a little hairy with those nested statements in the if as we do the search, but nothing ground breaking or ridiculously complex. Next I asked the student to fill out the following method body to search on the address.
public ArrayList<Donor> address(String address) {
ArrayList donors = new ArrayList();
// Get an iterable list of all Donors
Donors allDonors = new Donors();
// TODO: Search for [address] in each donors' address
// - Add matching donors to [donors] list
return donors;
}
The stark similarity should have been obvious, but they simply had no idea of where to start. After showing them some copy-’n'-paste coding we had a working solution in seconds. It wasn’t until I was explaining the most basic of algorithm designs and demonstrating the flexibility and, in many ways, the purpose of using an object oriented design methodology had I realised that problems that students were facing.
In reviewing the final and submitted code for this article, I noted the following comment had been added to the return statement of the address search method.
return donors; // returns the address of the donor
My heart sank. I thought we had this concept nailed down.
Timing, it’s of the Essence
Over the course of the class the teaching staff slowly dolled out the required materials, unnecessarily slowing the development of our projects and, as I noted before, when it came to version control and collaboration tools, none were provided. To add insult to injury the week before the project was due the class was finally given a lecture on design patterns — specifically MVC — and it was suggested that we use it in our project. It was a little late to ask for the class to re-engineer their projects.
The nature of group projects also allowed a number of students to avoid work, either by being uncooperative or simply ignoring emails and not turning up. A number of groups were half the specified size by the time the project was due. My own experience of this was one student who finally showed up the day before the project was due. It was a real shame as he understood the projects, just didn’t want to do any work. Together we rushed out some thing workable for his assigned part of the project and left it at that.
Setting the Standard
While results for the module have yet to be announce the class was informed that code that met the given criteria was not expected and projects which failed to work could still easily result in a pass for the module. While the nature of group projects does require some understanding from those who grade them to allow for students who are either well in advance or below that of their peers the idea that a group software engineering project which does not come close to working as an integrated whole garnering a pass mark shocked me somewhat.
Of course, I have myself benefitted from this arrangement. Our project is by no stretch of the imagination “complete”, however it does have some basic functionality. Had our group not had to fight the system to get collaborative tools maybe we would have been able to spend more time actually getting some work done — and maybe the other groups would have had the chance to get something working at all.
Conclusions
You might wonder why I would publicly criticise my university education? Well, for starters the university itself has already acknowledged the issues in my course by opting to re-engineer it from the ground up for the 2009-2010 intake of students. It also seems that my experience is not unique with supporting research from other institutions publicly available. I also believe in acting on issues and I made a point, maybe to the teaching staffs’ dismay, of raising my issues both with them and, as appropriate, our head of year.
I still truly believe that, despite the research mentioned in the paper, everyone can learn to program, at least to a basic level. I think for most students I have spoken to, they want to learn. It seems the issue is one of breaking down a problem into manageable chunks, finding where to look for solutions and maybe most importantly learning how to RTFM.
Dreams in Code Snippet
A quick overview of my development of the code snippet used in the blog byline.
Looking for a simple graphic to add to the site byline I elected to use some C-type code, being my most familiar dialect, and being a Mac user, the Monaco typeface in an appropriately anti-aliased size.
Now I’d set out some basic requirements, the question remained, what should it do? With the line “dreams in code” it certainly had to epitomise sleep and naturally I wanted to show some Zs. Thus the concept was born: sleep makes more Z! Latching onto the universally recognised ++ notation for incrementing a variable my first iteration looked like so:
int sleep(int z) {
return z++;
}
The first thing you might notice is that my use of braces is different. The above snippet being my preferred style of layout. The reason for the change? I had limited myself to a fixed sized graphic and the alternative code-block style allowed me to use a slightly larger font size. Lets clean that up so it’ll fit better in my Photoshop template:
int sleep(int z)
{
return z++;
}
However, that keen eyed among you are more likely to point out that my function, though perfectly legal in C, C++, Java, Objective-C and probably a number of other languages, does not in fact do as it appears. As ++ is a post-increment the increase in z would happen after the function or method returns — therefore the value of z is returned before it is changed.
Now, I debated whether to keep this as it, after all you might say that when sleeping the goal is to do nothing; however, my goal had been to increase the number of z, so the solution? Pre-increment.
int sleep(int z)
{
return ++z;
}
While this notation is not nearly as commonly seen in code, it does allow the function to return an increased value for z without using another line or a hard coded value. It was a shame to drop the original concept of z++, and you might consider the whole thing rather over-engineered, but as this tiny code-snippet sits proud atop every page on a blog about development I certainly believe this was an excellent occasion to favour a correct solution over a visually appealing one.