The Hitchhiker’s Guide to the Galaxy

"I refuse to prove that I exist," says God, "for proof denies faith, and without faith I am nothing."

"But," says Man, "the Babel fish is a dead giveaway, isn't it? It could not have evolved by chance. It proves that You exist, and so therefore, by Your own arguments, You don't. QED"

"Oh dear," says God, "I hadn't thought of that," and promptly vanishes in a puff of logic.

"Oh, that was easy," says Man, and for an encore goes on to prove that black is white and gets himself killed on the next zebra crossing.

Throughout the Compilers Design course we've been reading the Hitchhiker's Guide to the Galaxy by Douglas Adams. I found the book quite interesting because I've listen to several references of this book in many sci-fi TV Series.

The story goes around Arthur Dent who happened to be the only earthling left after Earth's destruction by the Vogons, with the help of  Ford Prefect he manages to scape and his journey begins.

He meets Zaphod Beeblebrox aka The President of the Galaxy which goal is to find Magrathea, an ancient planet which build custom planets. In the way to this planet it is revealed that there was a machine millions of years ago which was supposed to give the ultimate answer to the universe. When the time has come the machines gives the result which happen to be 42. The machine "Deep-thought" explains that they don't know how to interpret the the answer because they never knew the question, so it prints the plains to build a new machine that can give the question to the given answer. this machine turns out to be the Earth, but ironically was destroyed seconds before it gave the question.

Eventually they found Magrathea and discover they're rebuilding planet Earth, but since one earthling continues alive, they can dissect his brain and get the questions, forcing them to flee.

In general it was a good book, but I wasn't expecting it to be comic. I understand why it is so popular in the sci-fi universes, it has a lot of important elements in the space story-telling like ships and aliens which ironically happen to be similar to us.

Technical Overview of the CLR

This week article was written by Erik Meijer and Jim Miller. Both worked at Microsoft and form important part of developing the Common Language Runtime (CLR).

The text compares some of the things offered by the Common Language Infrastructure(CLI) with the Java Virtual Machine (JVM). The main difference is that the CLI is a platform that supports a wide range of languages. Microsoft developers work closely with the implementers of these languages so that programs compiled efficiently and smoothly.

The CLI has a lot of primitive types which makes it powerful and very flexible. There are a lot of instructions available to modify and manage the evaluation and argument stack. You can do arithmentic operations, reference alterations to build for example a swap function, reference types and also value types. Something interesting is that it is mentioned in the article that one important feature is the tailcall function in order to support languages that only have recursion as a method for looping.

I consider important to take into account the functionality offered by both the JVM and the CLR of .NET when implementing a programming language, because if it is object oriented, obviously should the JVM is better and for imperatives paradigms the CLR.

The architecture that makes up the CLI are the instruction pointer, the evaluation stack, an array of the local variables, local memory pool, among other things. The CLI easily manages multiple concurrent threads, which can be seen as a list of stack frames. Also, the CLI handles different types of data, that is, has a set of primitives which in turn can be combined with different types of constructors allowing the size value be mapped. The natural size has more benefits on how the JVM defines the storage locations, because 64-bit formats occupy two locations.

If you are interested in reading this article, here's the link: Technical Overview of the CLR.

Ruby and the Interpreter Pattern

This week article was about SIF (S-Expression interpreter Framework) developed by Ariel Ortiz. This program teaches how is a programming language construct (in a tree form) and then compiled, this code is built in Ruby following the interpreter pattern.

S-expressions (symbolic expressions) are a parenthesized prefix notation, mainly used in the Lisp family languages. The interpreter pattern is one of the classical Gang of Four (GoF) behavioral patterns. A program is portrayed as a tree in which every construct or element in the source program is represented by a specific kind of node. Every node responds to a special operation called interpret, which is responsible for performing the expected behavior associated with the corresponding language element. The interpret operation receives a context as a parameter, which is basically a symbol table where variable bindings can be established and queried during runtime. The framework’s job begins by reading a source program represented as a string. The Ruby regular expression API is used to scan the input, and a hand written recursive descent parser performs the syntactic analysis that transforms the S-expressions into the equivalent Ruby data values. These objects are then traversed in order to construct the tree required by the interpreter pattern.

The Interpreter.eval class method is the heart of the SIF. This method receives a string and a context as inputs. The string should contain one or more valid S-expressions, while the context may be a hash object in which each key represents the name of a variable that’s associated with some specific value. The hash keys are assumed to be Ruby Symbols, and the hash itself should be mutable in order to allow the S-expressions to modify its contents if needed. This method parses the input string converting the Sexpressions into their equivalent Ruby data values, and then proceeds with the evaluation using the interpreter pattern.

The SIF provides a class called Primitives which provides a set of predefined primitive procedures (including operations for arithmetic, list processing, and type predicates) that can be readily used. The class method Primitives.context should be used to get a copy of the context containing the variable bindings to the primitive procedures.

The SIF uses strict evaluation when calling a procedure. This means that all the arguments of a procedure are completely evaluated before being called.

If you are interested in reading this article here's the link: Ruby and the Interpreter Pattern.

If you are interested in downloading SIF here's the link: SIF.

Compile-Time Metaprogramming

This week we listen to a podcast by Software Engineering Radio with Laurence Tratt as guest. He begin with the idea that the way to express new things is to create new syntax. For that we need to know the relevant issues with DSL.

The DSL is an abstraction relevant to specific domain, in other words, you take a particular problem and see how can you express it in a programming language. That means you move it to a higher level and that's DSL construction.

The reason you want to embed things in a host language is the alternative is making stand alone DSL, and the best example of that is “make” because is a complex stand alone application. We embed to get low level stuff.

The idea of compile-time metaprogramming is that you have a way of adding source code to the program that is not evaluated at run time but rather during the compilation process and the result of evaluating this piece of source code is a syntax tree that is then integrated into the machine code that the compiler create.

Parsing is a two stage process:

1.     You take an input and you tokenize it.

2.     Take the token and try to give it sense.

This converts into an abstract syntaxt tree in terms of the host language.

Converge is a dynamically typed object orientated programming language with compile-time meta-programming facilities - put simply, Converge has a macro-like facility that can embed domain specific languages with arbitrary syntaxes into source files.

In general he recommend us to use Converge language because it's probably that we succeed, because is easy to use and very easy to merge with your source code.

If you are interested in listening this podcast here's the link: Compile-Time Metaprogramming.