Feeds:
Posts
Comments

Archive for the ‘Toy Projects’ Category

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 »

XSLT 1.0 Sudoku Solver

Taking a dry academic course on XML and its derivatives is, not surprisingly, just plain old boring. But you still can create a little bit of fun for yourself.

A few days ago, while the lecturer was diligently enumerating the endless features of the different version of XSLT in front of the sleepy audience, a bright idea suddenly struck my mind. Why not implement a little Sudoku solver in this language?

During the next few days the picture of exactly what I wanted implemented started to take shape. It should be something simple, that would run in a regular browser without the need for any external XSLT processors. Clearly the only version of the language that could achieve this is XSLT 1.0. In a day or two I had a working “prototype” that relied on nothing more than named templates, conditionals and a little bit of “magic” XPath string manipulations. After gaining confidence that everything seemed to work as expected, a final transformation, to a “user-friendly” HTML output was added:

The algorithm implemented is just a brute-force backtracking search with some amount of pruning. The main challenge was to come up with the appropriate data-structures for representing the intermediate stages of the computation and to encode them as strings – particularly annoying was the fact that strings in XPath are indexed starting from one, which made the “index arithmetic” clumsier than it needed to be.

The performance varies according to how “tough” a puzzle is – the number of recursive calls required to reach a solution. Since the search does not employ any special heuristics, such as the “least constrained variable first”, the program’s measure of “tough” is not necessary the same as a human solver would perceive. Exceptionally nasty cases, with tens of millions of recursive calls, might take as much as tens of seconds. Most puzzles, however, are solved in pretty reasonable time.

The code of this small project can be downloaded from here.

Read Full Post »