It’s been three months since my last post.  During these three months I was busy  mainly with writing a paper for submission to a conference, and I find it hard to invest in “side write-ups” while being totally invested in authoring a paper.

For a week or so I thought about how I should continue the tale this blog was intended to tell, the line of thought behind my research, along with some technical information, tutorials maybe, to help readers interested in trying things themselves.  Looking for a story, I looked back at the early days of my research, and then I realized this is a story worth telling.  So in this blog post I will tell the story of the first half of my research so far (my MSc thesis) — how I started, and mainly why.  Why I went to research, and why this particular research topic.

How it all Began

Fresh out of the Technion, equipped with the best CS degree one can get in Israel, I started my career at the Israeli high-tech industry.  It was the end of the 1990’s, and the skies were the limit.  My dream was to find an interesting idea and to open a startup.  Not for the money.  For the challenge.

So I started thinking about problems I saw in my day-to-day work, and thought about solutions.  The main problem I could see was the immense amount of code my colleagues and I needed to write to get a small thing to work, a problem I would now phrase as “the programming language was not as expressive as I wanted it to be“.  We used C++ at the time, which I now know to be a horrible language for the kind of programming we did (actually, anything where deterministic computation time is not a strict requirement), but as I learned other languages such as Java and Perl (hey, it was the late 1990’s) I came to realize that no programming language will give me exactly what I needed, and we (software developers) are stuck writing tons of code to get the simplest features to work.  I had a few ideas for programming languages that I hoped would be highly expressive for solving certain kinds of problems.  For example, I thought about a visual language for implementing low-level real-time software.  I even started prototyping an IDE for this language, and started talking to people about making a starup out of this (the year was 2000, and anything was possible).

But then I realized that no real-life problem falls under a single “kind” of problem.  Real-time systems are not just real-time systems.  They do stuff — control motors, read sensors, do math, communicate… and typically some of those at the same time.  A language that is good for real-time systems can be lousy for communication or for control, and vice versa.  If we want our language to be expressive for all aspects of our software, we need it to be tailored for all of them.

The Dream Language Principle

And then I had an idea: what if programmers could make their own languages?  What if they could tailor a language exactly to their needs?  I called this idea the dream-language principle, stating that for any software design there is a “dream language” waiting to be defined.  Implementing the software in that language would simply be a formalization of the design.

I think the last sentence needs some explanation.  At the early days of computing, many scientists speculated that some day computers will be smart enough to program themselves.  I guess the most obvious question to ask someone making this claim is:  program themselves to do what?  A reasonable answer to that could be, humans write some requirements document, and the computer implements a program that meets these requirements.

Two problems hinder making this a reality:

1. The requirements document is written in a natural language, and natural languages are ambiguous.  Unlike computer languages, that try very hard to be unambiguous (one meaning for one program), a sentences in a natural language can have more than one meaning, so one requirements document can have several, different meanings resulting in several, different programs.
2. The requirements define problems computers are not necessarily able to solve.  Early computer scientists such as Alan Turing proved surprising results regarding to what a computer cannot do, or cannot do within reasonable time.  As consequence, humans are left with solving many kinds of problems themselves, while computers are used to check the result (see for example proof assistants).

For these two reasons, a computer is not (and will not be, in the foreseeable future) able to implement software based on a requirements document.  However, if we (humans) perform the step of turning a problem into a description of a solution (the “design” phase of software development) and write that design in an unambiguous manner, there is no theoretical reason why a computer cannot understand it and turn it into an implementation.

No theoretical reasons, just a very big practical one — someone needs to implement that language.  C++ is a language.  It is unambiguous, and it has numerous implementations.  However, no one in his or her right mind would use C++ to write a design document…  A design document would probably be written in terms of state-machines, messages passing between components and mathematical equations.  C++ does not have all these as part of the language.  Programmers can implement state machines, messages and equations, but this is implementation, the phase that usually comes after design.

The dream language principle, as I called it, suggests that software developers can write design documents for their software in a formal (unambiguous) language that they define, and then implement the software by implementing the language.  I later learned that this practice has already been invented by someone else — Martin Ward, who gave it a different name: Language Oriented Programming (or LOP for short).

My Love Affair with Prolog

Applying the Dream-Language Principle to real software projects mean that regular programmers need to be proficient in the subtle art of defining and implementing programming languages.  Knowing that, I spent a few years (in my spare time) trying to find easy ways to implement expressive languages.  I looked at a variety of ideas, but did not get that far.  At this point I realized this problem is too hard to be startup material, and I started thinking in terms of pursuing it in academia, where you don’t need to provide a short-term plan for your idea to become piles of money.

My first breakthrough was when I rediscovered Prolog.  I knew Prolog since I was a teenager, after a friend of mine introduced me to the language.  I officially learned it for the first time in a “Programming Languages” course at the Technion.  But both times I learned it the way most people learn Prolog: as a language for traversing trees of options, to perform AI-like tasks (give me a criterion and a solution space, and I shall give you a solution).  I don’t remember how I got to look at Prolog again, sometime around 2004, but when I did, I found out I could do a lot of really cool stuff with it, stuff that had nothing to do with AI.

I discovered I could create an expressive build system (a GNU-make alternative) using Prolog, where the “makefile” is a Prolog program.  Then I found out I could create a powerful code generation framework using Prolog, where a simple preprocessor would convert the template code to a Prolog program.  Finally I realized that Prolog is an ideal language for defining the semantics of programming languages, and I implemented a compiler framework using Lex, Yacc and Prolog to perform lexical, syntactic and semantic analysis, respectively.

This discovery that Prolog was so powerful and expressive, and was able to address such different problems in such an elegant way got me thinking maybe Prolog is the answer I was looking for.  Maybe Prolog can allow programmers define their own dream language with ease… or maybe… Prolog itself is the dream language…

On my search for answers I found these lecture notes by Tim Menzies, which explain in much details how Domain-Specific Languages (DSLs, “dream languages” for particular problems) can be developed using Prolog.  Although Menzies wrote these notes as an academic, and although this is the first mention I found on the Internet of DSLs in Prolog, he did not bother to write an academic paper on the subject.  I believe Menzies did not realize he discovered something new.

So what makes Prolog so good for implementing these “dream languages”?  Today I can say that it is probably a combination of two unique properties of Prolog:

1. In Prolog, code is data, and data is also code.  Prolog programs don’t have variables in the sense that exist in “normal” programming languages.  Instead, a program can add “knowledge” (facts) to itself in order to “remember” things.  This “knowledge” is actually added to the program, modifying it at runtime.
2. A question in Prolog has zero or more answers.  Unlike “normal” programming languages, where a function returns exactly one value, Predicates (the Prolog equivalent of functions) can “return” any number of alternative solutions, or have no solution at all.

I feel I should dedicate a complete post to Prolog and logic programming, but for now I ask you to trust me on this one…  These features two are unique to logic programming, and help very much in making it easy to implement DSLs and “dream languages”.

Dream Syntax with Projectional Editing

One drawback that Prolog has, one I had to deal with in all sorts of awkward ways was Prolog’s syntax.  Prolog does its best to accommodate DSLs.  It has flexible syntax where programmers can define new operators.  But still, Prolog’s syntax is limited.  This is not because the designers of Prolog did something bad.  It is because at the end of the day some parser needs to understand the code we write. This means there must not be any chance for ambiguity in the code.

It is because of Prolog’s syntax that I needed a preprocessor when implementing my Prolog-based code-generation framework, and why the syntax of my Prolog-based build system was a bit awkward.  If I were to offer Prolog-based DSLs as “dream languages”, I needed a better solution for syntax.

Then, around July 2005,  I found an article written by Sergei Dmitriev.  This article, written in the previous year, was named Language Oriented Programming, just like Ward’s paper from 1994.  As Dmitriev didn’t mention Ward in his article, I take it he came up by this name independently.  Nonetheless, the idea he presented in the article is similar to Ward’s, but with a few improvements.

First, the article does not only describe an approach.  It also described a tool named MPS, designed to make it easier for developers to create languages.  Later, MPS was classified as a language workbench by Martin Fowler.  Another innovation in Dmitriev’s article was the idea of building software from many DSLs rather than one big “dream language”.  MPS helps define many of these DSLs and use them in concert.

It was interesting reading, but I already knew how to do all these.  After all, Prolog DSLs are implemented as “libraries” or “modules” in Prolog, so mixing different DSLs in Prolog was no harder than mixing code that uses different libraries in C++ or Java.

But the real innovation in this article, the one that gave my research the boost it needed, was the way MPS handled syntax, something that was later called projectional editing by Martin Fowler.  Basically, it means that instead of holding the code in a text file, the code is held in some tree format (XML, in the case of MPS) and a special editor, dubbed a projectional editor is used to display the code (typically as text), and allows editing.

Projectional editing was exactly what I was missing in Prolog.  Because rendering text out of a tree is easier than parsing a tree out of text, Projectional editing allows DSLs to take any syntax their developers see fit.  Projectional editing over Prolog would give me all the expressive power of Prolog, with any syntax I see fit.  If this is not a dream language, I don’t know what is…

And There Shall Be Cedalion

That was almost eleven years ago.  After finding out about projectional editing it took me about a year to implement the first prototype of Cedalion (then called VisualTerm), as an Eclipse plug-in.  It took me another two years to refine it into something workable, especially with the addition of a type system.  At about the same time  (2008) I enrolled to an MSc program at the Open University of Israel, where I met my advisor, David H. Lorenz a year later.

The name Cedalion, which I came up with in 2009, is taken from Greek mythology.  Cedalion was a servant who stood on the shoulders of Orion the blind giant, leading him to find cure.  This story was the inspiration behind the saying “standing on the shoulders of giants”, and indeed, the language Cedalion does not try to reinvent the wheel.  Unlike MPS and other language workbenches, which are new tools allowing users to implement new languages, Cedalion is a language combining old (Prolog) and new (projectional editing) technologies, with each DSL built on top of a Prolog-like language with all the other DSLs already implemented available to the developer, just like existing software libraries are available to programmers implementing a new library.

Cedalion was everything I meant it to be.  I managed to with it things I could only imagine when I first embarked on this journey.  Unfortunately, I found it hard to interest other people in Cedalion.  Most prominently, because I found it hard to make it useful.  So when I decided to continue my academic research and pursue a PhD degree, it was clear to me what the goal will be: turn Cedalion into something that matters.

And I believe I did.