Making Cedalion Matter

If you tried out, or at least read the Cedalion DSL tutorial, or at the very least watched the “hello, world” video in the “first steps” page, you would agree that Cedalion is different than any other programming language you know.

Cedalion is not new.  I published my first paper on Cedalion back in 2011, about five years ago.  So why did I start blogging about it just now?  Why did I not make an effort to showcase it to people who may find it useful?

Why? because until recently, it wasn’t that useful.  In this post I will tell you why, and share the insight that I believe makes Cedalion matter.

Purely Declarative

Cedalion is a purely-declarative programming language.  I talked about what this means in my first post in this blog, but for those who do not fully understand what this means, it means that a Cedalion program does not have state, and does not interact with the world.  When you start learning one of most programming languages out there, the first program you will probably write in that language would probably print the string “hello, world” (or a variation of it) to the screen.  Printing to the screen is an effect, a way for the program to affect the world.  A purely-declarative programming language like Cedalion does not have effects.  It cannot print anything to the screen, cannot store anything to disk and cannot send anything over the Internet.  Similarly, it cannot read input from the keyboard, from a file or from the Internet.

So what can it do?  Well, mainly — answer questions.  You can ask the program a question, and you’ll get your answer.  Ask another question, and you’ll get another answer.  Because it cannot read anything from anywhere, the same program will always respond to the same question with the same answer.  This is the “no state” part.

What kind of questions?  Well, that depends on the programming language.  Haskell is a purely-functional programming language, and questions in Haskell are expressions, and answers are values.  Cedalion is a purely-declarative logic programming language, so questions are logic goals, and answers are conditions under which the goal is true (if any).

So the problem is, how do you make useful programs in a language that does not allow you to do anything?

Haskell seems to suffer from a similar problem…

Why is Purity Important?

Why is the purity of the language so important?  Why not just support effects?

The short answer is modularity.  Specifically for Cedalion, the long answer is that being pure allows programmers to add new solutions to goals without being afraid they’ll break anything.  For example, in the DSL tutorial we defined several different solutions for the “evaluates to” predicate, accounting for different kinds of expressions.  We did not have to worry about which one is evaluated first and what changes they make to the state of the program (or the world).  By being pure we ensure they do not make any changes to the state of the program (or the state of the world), and as a result, the order in which they are evaluated does not matter.  This allows us to add solution to any predicate we’d like to, without worrying about interfering with something else.  For example, two different projects can define their own expressions by providing separate solutions for ‘evaluates to’.  Even if they were developed separately, joining them together will not cause a conflict, because they are totally independent.

Making a Purely-Declarative Language Useful

So how can a language that only answers questions (and always responds to the same question with the same answer) do something useful?  The answer is, by having an imperative friend.Imagine a simple program implementing a guessing game.  The computer randomizes an integer between 0 and 99, and the player needs to guess this number.  The computer asks the player for this number.  If this is the correct number the computer tells the user so and the game ends.  If the number is incorrect, the computer tells the user if the guess is too small or too big.This game can run as a conversation between two friends: Decl, the declarative program who knows what the game is about but cannot do anything or remember anything, and Imper, an imperative runtime environment that knows nothing about the program, but knows a lot about interacting with users.  The game should look something like this:

Imper: The program started.  What should I do?
Decl: Randomize a number X and take a guess for X.
(Imper randomizes 42)
Imper: How do I take a guess for 42?
Decl: Prompt the user for a number, read number Y, 
      then respond for Y given target 42.
(Imper prompts the user, then reads number 50 from the user)
Imper: How do I respond for 50 given target 42?
Decl: Print "this is too high", then
      Prompt the user for a number, read number Y, 
      then respond for Y given target 42.
(Imper prints "this is too high" then prompts for another number
and gets 20)
Imper: how do I respond for 20 given target 42?
Decl: Print "this is too low", then
      Prompt the user for a number, read number Y, 
      then respond for Y given target 42.

As you can see, Imper (our imperative runtime) manages to execute the game by asking Decl (our declarative program) what to do at each point.  Decl does not need to remember anything.  Imper remembers for the two of them (e.g., the 42 target).  At each point along the way Imper asks Decl a question such as “how do I…”, where (expect for the first time) the thing Imper is asking about is something Decl mentioned in a previous answer.  Decl’s answers consist of instructions, for which some are familiar to Imper (e.g., printing a string, prompting the user or reading a number), and some are not.  For those that are not, Imper asks Decl how to do them.This kind of dialogue between a declarative program and an imperative runtime environment exists in Haskell, in the form of the IO Monad.  It allows Haskell users to write programs that interact with the world and maintain state, while keeping Haskell purely-declarative.Cedalion uses  similar facilities to interact with the world.  I don’t want to go into the specifics of these interactions here, but basically, the Cedalion Workbench (the Eclipse-based projectional editor for Cedalion) asks the Cedalion program questions, such as what items it should present when the user right-clicks something in the code, or what it should do when the user clicks one of these items, and the Cedalion program replies with a description of what needs to happen.  This kind of interaction provides Cedalion programmers with a few different ways to ease programming.  If you did the DSL tutorial, you  must have used quite a few of them, such as the suggestion mechanism where Cedalion proposes automatic fixes for type errors, and context-menu entries that assist in editing code: inserting elements to lists or adding projection definitions after declarations.These interactions make Cedalion very powerful in extending its own IDE, but does it make it a useful language?

Cedalion, Outside the Workbench

So what is the point in making a programming language that is very expressive, but can only do something inside its IDE?  Well, I managed to help one friend with his PhD in Biology, but that was about it.  This is why, for almost five years, I did not promote Cedalion.  Not because I didn’t think it didn’t have potential, just because back then, I didn’t (yet) get to the bottom of how to make it useful.

There are many areas in which a programming language can be useful.  Of all these ares, I focused my efforts on Web applications.  I made this decision for a combination of reasons.  First, Web applications take a huge share of all software being developed today.  Second, this is a field where developers are already making the trade-off of using slower languages (e.g., Python and Ruby) to gain expressiveness.  So for a few years I’ve been trying to find useful ways to implement Web applications in Cedalion.

It’s not that I didn’t have ideas.  I tried quite a few actually.  I tried having a Servlet respond to queries by querying the Cedalion program what to do.  I tried compiling Cedalion to Javascript and running Cedalion programs on the browser.  I tried integrating Cedalion with CouchDB.  Some of these ideas were better than others, but non of these ideas gave me what I wanted.  What did I want?  I wanted to make it as easy to implement a Web application using Cedalion as it was to implement a DSL in Cedalion.  Unfortunately, that didn’t work out with either these solutions.

Why?  Because of persistent state.  Cedalion is very good at answering questions, as long as the answer depends solely on the program.  A Web application also works by answering questions, but the questions they answer depend on persistent data.  If a Cedalion program wants to answer such a question it needs to fetch the answer from the Database.  It therefore needs to implement a dialogue such as the one described above (between Decl and Imper) with a runtime environment that would fetch the data for it.  This makes the Cedalion program imperative.

This wasn’t good enough for me, so I sought a different solution.

A Different Solution

So the target was to make implementing a Web application as easy as Implementing (or defining) a DSL in Cedalion.  How does one approach such a problem?  And then (I don’t know exactly when, but it was in time for writing my PhD research proposal back in 2014) it hit me: what if I treat the Web application as a DSL?

It all made perfect sense.  A Web application is actually a DSL.  First, it is a language, because it has both syntax and semantics.  Its abstract syntax is the data model (e.g., database schema), its concrete syntax is however the UI presents this data, and the semantics is defined by the business logic.  This language is domain-specific because its data model is domain specific.

This comparison (of a Web app to a DSL) applies to all Web applications out there, regardless of how they are implemented.  The thing is, there are easier and harder ways to implement DSLs.  Unfortunately, the state of the art in Web app implementation corresponds to the harder ways.

So how are Web applications implemented?  Once upon a time, most Web applications were implemented as CGI scripts.  To implement one you would choose your favourite programming language, hand-parse arguments from environment variables, go to the database to fetch or store some data, and hand-generate HTML by formatting strings.  To me, this way of implementing Web applications resembles (in the DSL domain) hand-writing an interpreter for your DSL.

With time, application developers became fancier, and started using Web frameworks.  Web frameworks provide DSLs and tools that assist in the development of Web apps.  This is extremely similar to what language workbenches do in the DSL world: provide DSLs and tools for implementing DSLs…

Regardless of whether you use a framework or do your own thing (with CGI, Node.JS or anything else), you probably implement your Web app in a way that corresponds to implementing an external DSL.  You implement your Web application by implementing software, using a language that is external to your DSL… the Web application…

The DSLs we define in Cedalion are internal DSLs.  Cedalion acts as a host language for these DSLs.  The fact these DSLs are so easy and natural to define stems, in part, from the fact that they leverage a powerful host language.  This is external DSLs where you implement the language, and therefore you need to implement everything from scratch.  Languages workbenches make things much easier, but do not change the fact that you implement a totally new language.

So to give developers the same experience developing Web applications as they get defining DSLs in Cedalion, one needs to find out what it means for a Web app implementation to correspond to an internal DSL.  This is where another language named Cloudlog comes into the picture.

But this is a topic for another post.


One thought on “Making Cedalion Matter

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s