Feeds:
Posts
Comments

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.

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.

“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.

Exercise 3.9

Let’s start with the recursive factorial:

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

For simplicity, especially since drawing these pictures in OpenOffice is a bit tedious, let’s trace out the evaluation of (factorial 3) instead of (factorial 6). When the procedure factorial is applied to the argument 3 a new environment E1 is created who’s parent environment is the environment in which factorial was defined (the global environment), and in which the formal parameter n is bound to the value 3. Then the body of factorial is evaluated in this new environment, resulting in another application of factorial with 2 as an argument. This creates a new environment E2 in which the formal parameter n is bound to 2. The environment E3 is created in a similar manner, with n bound to 1. Finally the base case of factorial is reached, the computation unwinds and finishes:

Now let’s examine the iterative version of factorial:

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

Again everything starts with the application (factorial 3). The body of factorial is evaluated in an environment E1, where the formal parameter n is bound to 3. This results in the application (fact-iter 1 1 n), which reduces to evaluating the body of the procedure fact-iter in a new environment E2 with the formal parameters product, counter, and max-count bound to 1, 1, and 3 respectively. The process continues with the environments E3, E4, and E5 being created along the way until the computation finally ends:

Exercise 3.7

Make-joint can be implemented to return a procedure that takes two arguments – a password password and a message m. It works by checking whether password and new-password match and if they do sends the message to the local account object along with the original password:

(define (make-joint account account-password new-password)
  (lambda (password m)
    (if (eq? password new-password)
        (account account-password m)
        "Incorrect password")))

No changes to make-account are required.




Exercise 3.8

Let f be a procedure with a single local state variable last which stores the value of the argument x that was last passed to f. Initially, if f has not been called, last has the value of 0. When applied, f updates the value of last to that of its argument and returns the old value of last:

(define f
  (let ((last 0))
    (lambda (x) 
      (let ((result last))
        (set! last x)
        result))))

Now let’s consider the evaluation of the expression (+ (f 0) (f 1)). If the arguments are evaluated from left to right the first application (f 0) will evaluate to 0 (the initial value of last), and the second application (f 1) will also evaluate to 0 (the value of the argument in the previous application). Adding up 0 and 0 we get 0. If, however, the arguments are evaluated from right to left the first application would be (f 1) which evaluates to 0 (the initial value of last), and the second application (f 0) would evaluate to 1 – the value of the argument in the previous application. When we add the two together we get 1.