Archive for November, 2011

My last experiment in implementing the Picture Language from SICP in JavaScript turned out to be very enlightening. That’s why this time I decided to push the limit and try something really extravagant – implement an embedded logic programming language.

The really interesting aspect of this project is the immense paradigm shift from imperative and object-oriented to formal logic, pattern matching and automatic search. This feat of wizardry is again inspired by “Structure and Interpretation of Computer Programs”. The solution itself utilizes magical ideas like infinite lists called streams and the amazing unification algorithm. As a result we have a system with power equaling that of Prolog in just a few hundred lines of JavaScript.

The source code of the project can be found at: github and Google code.

Read Full Post »

JavaScript is one of the world’s most misunderstood languages. Even though it is ubiquitous, very few people actually have a good idea how to program in it in an idiomatic way. I must admit that I am also one of them.

In an effort to right this wrong I have endeavored to look into the language more carefully. As it turned out, many of the language’s “good parts” come from the Scheme programming language. This led me to the idea to try out some of the most idiomatic Scheme code which I could find. I chose to implement Peter Henderson’s “Picture Language”, used as a wonderful example in Chapter 2 of “Structure and Interpretation of Computer Programs”. This “Picture Language” is special in that it is loaded with such idioms as functions that take functions as arguments and functions that return other functions as results. These “higher-order” functions have enormous expressive power.

In implementing the “Picture Language” in JavaScript I had to choose how to actually render the final result. First I went with the HTML5 canvas element, but since I wanted this project to give me more breadth in JavaScript’s different incarnations, I also tried a version that uses the Rhino engine (included in the Java SE 6).

In conclusion, the “Picture Language” came very naturally in JavaScript, and even turned out to be a little shorter, than my Scheme implementation.

Here is the “square limit” of Isaac Newton produced by the system:

The source code can be found on GitHub.

Read Full Post »

“The Elements of Computing Systems: Building a Modern Computer from First Principles” by Noam Nisan and Shimon Schocken is a small book of approximately 300 pages. It walks the reader through building an entire computer system (hardware and software) from 2 basic elements: a NAND gate and a data flip-flop.

I must admit however, that going through the book feels more like writing code rather than reading. The chapters, organized as programming projects, provide concise background information and clear requirements on what must be built.

“The elements of computing systems” is logically separated into 2 parts: hardware and software. In the first 5 chapters the hardware platform is gradually built using a simple HDL language and run and tested on a simulator (the hardware itself is actually software!). These projects where not difficult and I managed to complete one project per evening after work. The only exception was the final CPU project which took a bit longer. Don’t get the impression that I am some sort of hardware expert – my major is Software Engineering.

Having finished the hardware chapters in a week I was left with the false impression that the rest of the book will be as easy. But I was wrong!

The software projects started with an assembler, followed by a virtual machine and a compiler for a simple high-level object-based language (Jack). They got increasingly more difficult and time-consuming, but also educational and enlightening. As an implementation language I went with Python and it took approximately 3000 lines of code excluding the unit tests.

The final project was to write a simple operating system in the newly implemented Jack programming language. This project was not as difficult as the previous ones, but still required close to 1000 lines of code.

The discrepancy between the difficulty of the hardware and software projects may not be a coincidence, but rather a general insight into their essential complexity.

“The Elements of Computer Systems” is ideal for self study. But the reader should be warned that in order to complete it he/she will need some programming skills and be prepared to invest some effort and time – this endeavor took me approximately 2 months. However his effort will be rewarded – by the end of the book most of the “magic” of how computers work will have disappeared.

Read Full Post »