Your First Cedalion DSL – Part II

In Part I we started defining a small DSL in Cedalion.  For now, our DSL consists of expressions, but the only type of expression we currently support is a constant.  Not a very interesting DSL…

We will now change this, by adding some arithmetics into our expressions.

Plus One

The next step would be to define the plus (+) operator.

Create a new file under the simpleExpr project, and name it “arith.ced“.  Once again, you’ll be faced with an empty list of statements.

Screenshot from 2016-05-02 21:02:43.png

Insert a new statement and create a behavior (“beh” + Ctrl+Space + select from menu).  Replace the three underscores with:

plus(A, B)
"Should evaluate to the sum of the values of A and B

(for expr, you can use auto-completion by pressing Ctrl+Space and selecting the expr from namespace /simpleExpr, but you can also just type it).

Screenshot from 2016-05-02 21:12:08.png

expr is already declared, but plus(A, B) needs a declaration.  Double-click the error sign and accept the suggestion.  Then select the types of both A and B to be expr.

Screenshot from 2016-05-02 21:14:31.png

Important: if you choose expr from the auto-completion menu, please be sure to choose the one from the /simpleExpr namespace.

Save, and the error will go away.

We want our plus operator to appear in infix form (A+B).  To achieve this we will define projection for it.

Select the bullet next to the declaration (actually, this will select the whole file) and hit F9.  In the projection definition that opens (display … as …) select the list tail that contains B (and not A) and hit Alt+Shift+Insert.  This will insert an underscore between A and B.  Be careful not to save the file at this point.

Screenshot from 2016-05-02 21:22:12.png

In place of the underscore, enter:


Now save, to see your plus operator shine as a brand new infix expression.

Screenshot from 2016-05-02 21:23:36.png

Now we need to give it meaning.  Open the behavior using the little “+” to its left, and on the underscore inside the white box type “eva” and ask for completion (Ctrl+Space).  Choose “evaluates to”, which is our own eval predicate from namespace /simpleExpr.

Screenshot from 2016-05-02 21:26:41.png

Select the underscore on the left-hand side of the “evaluates to”.  Now enter:


The number 1 will appear, surrounded by a light-grey border.  Rings any bells?  The reason why entering a number automatically wrapped it with “const” was that we declared “const” to be an adapter of numbers in the context of expressions.  Now type “+” and hit Ctrl+Space.  Select the plus operator from the menu.  The plus operator will wrap the constant (1).

Screenshot from 2016-05-02 21:32:27.png

Now select the underscore at the right-hand side of the “+” (Alt+Shift+End), and enter:


It too will be wrapped by the light-grey constant box.  You can save the file now.

Screenshot from 2016-05-02 21:39:23.png

Our test is failing (as you can learn from the tooltip you can see by hovering above the test).  eval() is failing for plus expressions.  Why?  Because we did not define how plus expressions are to be evaluated.  In other words, we did not define the semantics of the plus operator.  So let’s!

Append a statement at the end of the file (right-click the last bullet and choose “Append“, or select the last statement with its bullet and press Alt+Insert).  Select the underscore and type “evalu” and press Ctrl+Space.  Select “evaluates to” from the menu.  This will add a trivial solution to our “evaluates to” predicate.  Save, and the error will go away.

Screenshot from 2016-05-02 21:46:57.png

But did we fix the problem?  No!  It is just that our test is not good enough (yet).

In the test box inside the behavior, select the underscore to the right of “evaluates to” and enter:


Now select the entire goal (“1+2 evaluates to X”) and type “,” and Ctrl+Space, and select the one option you  are given.  On the second line you are presented with type “should” and select “should equal”.  Fill the blanks in this line with:




and fix the type error by accepting the suggestion.  Now our test fails as it should.

Screenshot from 2016-05-02 21:52:02.png

Hovering over the error will reveal that it is the correct one: “actual value _ does not match expected 3”, meaning we expected to get 3 and got a free variable (“_”) instead.  To fix that, we need to implement “evaluates to” for the case of the plus operator.

On the first underscore of the last statement, type “+” and select our plus operator.  It will appear between two underscores.  On the left-hand one place variable A, and on the right-hand one place variable B.

Screenshot from 2016-05-02 21:58:59.png

Move to the underscore to the right of “evaluates to” and place variable C in that place.

Now select the “true” at the right-hand side of the “:-“.  This side is the condition, what needs to succeed in order for the goal on the left-hand side of the “:-” to succeed.

“true” is a trivial goal.  It succeeds unconditionally.  We want our goal to succeed, but only if A and B are valid expressions, and only after we evaluated them and added them up and placed the result in C.  We will do this using three goals.

While “true” is selected, type “evalu” and select “evaluates to” form the auto-completion menu.  On its left-hand side enter variable A, and on its right-hand side enter variable APrime.  Notice how APrime is actually projected as A’.  In Cedalion, variables may have projections too…

This goal will evaluate expression A to A’, which is a number.  You can see their types by hovering the mouse over these variables.

Now select the this goal and type “,” and select the only possibility from the auto-completion menu.  In the new line that is created copy and paste the first goal, and change A to B and A’ to B’ (BPrime).  Now select the second goal (B evaluates to B’) and choose “,” again.  On the third line type “plu” and get an auto-completion menu to select “plus”.  This is the “plus” builtin predicate, which actually adds two numbers.  Fill its arguments with variables APrime, BPrime and C.  Save, and the error should go away.

(Actually, when I saved, the error did not go away.  I had to restart Eclipse for the problem to be fixed, as you can see in the above video).

Screenshot from 2016-05-02 22:18:15.png

Repeat a few Times…

Now we should repeat what we did to define the other operators.  For what we need next we only need multiplication, so I will only add it, but feel free to add subtraction and division as well.

To add multiplication, name your concept “mult(A, B)”, and use “mult(APrime, BPrime, C)” to multiply the numbers.  If you wish to implement subtraction and division, use “minus(APrime, BPrime, C)” and “div(APrime, BPrime, C)” respectively.

For multiplication, you should get something like:

Screenshot from 2016-05-03 19:24:21.png

Define Define

Ok, so now we have a somewhat rich expression language, but is it really a DSL?  Can we program anything with it, or is it just a fancy calculator language?

For it to really be a useful DSL we need to provide users with the ability to create abstractions — to define things.  We therefore need to define users’ ability to define…  We will use := as the definition operator, just as we did in the Prolog equivalent of this DSL.

Create a new file named def.ced under the simpleExpr project.  Create a new behavior for “def(A, B)” of type statement (from the /bootstrap namespace — use auto-completion for that) and for description enter “should define A as B”.

Screenshot from 2016-05-03 21:37:38.png

Double-click the error sign next to “def” and accept the suggestion.  Give both A and B type expr of namespace /simpleExpr.

Select the bullet next to the new declaration of def(A, B), and press F9 to define a projection.  In the visualization, insert the string “:=” between the visualization of A and B.  Save the file.

Screenshot from 2016-05-03 21:41:25.png

Now we want to write our test.  However, this case is different.  “:=” is a statement.  It is a top-level thing that we write in Cedalion programs.  Since it is top-level, we cannot use it inside a test.  To work around this, we will define an expression named foo, and test the effect of that definition.

Insert a new statement before the behavior and on the underscore, type “:=” and hit Ctrl+Space for the context menu.  Select def.  On its left-hand side enter: “foo” (as a concept, not a string), and on the right-hand side enter 2.

Screenshot from 2016-05-03 21:52:12.png

Double-click twice to declare foo as an expr.  By convention we use the names foo and bar and their derivatives in different namespaces as such examples, to allow testing of statements.

Now, open the behavior and enter the unit test “foo evaluates to X” (by now, you should know how to do this).  The unit test should fail.

Screenshot from 2016-05-03 21:56:29.png

Now let’s make it pass.  We already defined foo to have value (2), but we did not give this definition any meaning.  In Cedalion, we give meaning to statements using rewrite rules.

The name “rewrite rule” is somewhat misleading.  When we think of rewriting something we think of throwing away to old version in favour of the new.  Cedalion rewrites, however, are non-destructive.  They just add a new meaning, without taking away the old one.  As a result, I can rewrite a statement into two different statements using two rewrite rules.

A rewrite rule looks like this

S1 ~> S2

Where S1 and S2 are statements.  It can be read “S1 implies S2”.

Let’s write our rewrite rule for :=.  Create a new statement below the behavior.  Type “:=” and select def from the completion menu.  On its left-hand side enter variable A, and on its left-hand side enter variable B.  Then select the whole statement and type “~>” (tilde + greater-than) and select ~> from the auto-completion menu.  Then select the underscore at the right-hand side of the wavy arrow and select “evaluates to”.

Screenshot from 2016-05-03 22:16:20.png

Notice how Cedalion added “:- true” to our “evaluates to” predicate.  This is because we entered a predicate where we needed a statement.  This is an adapter, similar to the one we introduced in Part I of this tutorial.

Save, and the error should go away.

Now, add the goal:

X should equal 2...

to the test (by adding a comma).  Fix the type error by taking Cedalion’s suggestion.  The test should fail.

Screenshot from 2016-05-03 22:25:58.png

To fix this, edit the right-hand side statement of our rewrite rule to say:

A evaluates to V :- B evaluates to V

Save, and the error should go away.

Screenshot from 2016-05-03 22:27:50.png

The rewrite rule we added gave meaning to the := operator by implying something that already has a meaning.  Now we can define different things.  For example, let’s define the square(X) function, which will evaluate to X*X.

Create a new behavior for square(X) of type expr, with a reasonable description.  Declare it by taking Cedalion’s suggestion, setting X’s type to expr.

Screenshot from 2016-05-04 09:06:41.png

The unit test should be:

square(2) evaluates to Y,
Y should equal to 4 :: number

I trust that at this point you can enter this test without help…

Screenshot from 2016-05-04 09:09:42.png

For expediency, we did two things at once: the test that should pass once spquare(X) is defined, and the other — once it is defined correctly.  For things that matter, I advise you  to respect the BDD/TDD process and take things step by step.  However, here I think things are simple enough to skip the extra phase, as long as we are sure our test tests the right thing…

So let’s make our failing test pass.  Append a new statement and choose := from the auto-completion menu.  On the left-hand side choose “square” from the menu, and enter variable X as an argument.  On the right-hand side start by entering variable X and then choose “*” and on its right enter X again.  Save, and the error will go away.

Screenshot from 2016-05-04 09:20:13.png

This Too is a DSL!

So we created our very first definition using our new DSL.  It is hard for me, a person who knows Cedalion writing a tutorial for people who don’t, to know what is and isn’t clear to such readers.  One thing I think could be a bit odd and may need an explanation is how we managed to implement something similar to a function, just without defining it…  We did not define in our DSL anything about arguments.  Our unit test for the := statement involved a parameter-less constant (foo).  So how did Cedalion know what to do with variable X in our square(X) definition?

The answer is that variables are a core Cedalion feature that crosses DSL boundaries.  Concepts such as +, * and := can be considered as part of one DSL.  But variables are the way Cedalion allows two things to have the same (unknown) value.  Regardless of whether this value is a number, an expression or anything else.  For this reason, when we defined square(X), Cedalion knew what to do with X.

Another thing that can stand out here is the fact that square’s definition is located in the same source file with part of the DSL in which it was defined.  Cedalion is often compared to projectional language workbenches such as MPS.  In such workbenches there is a distinct definition of what a DSL is, and a DSL cannot be used inside its own definition.  We already used our DSLs in their definitions in unit tests inside our behaviors.  Here we took it one step further by defining a new concept, square(X), using our DSL.

And here is the killer: square(X) can also be considered part of a DSL… It can have its own concrete syntax, that does not have to be “square(X)”.  We can, for example, make it look like X2.

Select the bullet next to the declaration of square(X) and press F9.  In the visualization, append an element to the list (select the entire list and hit Alt+Shift+End a few times until a point is highlighted at the end, then press Alt+Shift+Insert.  As the new element, select “halfSize” form the auto-completion menu and in the blank type the string “2”, that is, enter:


Now right-click the little “h” at the left of the visualization and select “Set Alignment“.  An arrow pointing up will be displayed.  Save and watch the “function” becomes “syntax”.

Screenshot from 2016-05-04 09:55:26.png


We’re Almost Done!

We have a DSL in which we can define functions (in the mathematical sense, not in the functional-programming sense), and even give them special syntax so they can be their own DSL.  However, these functions cannot yet do anything interesting, since they cannot be recursive.  We can try recursion, but then, how do we stop?  We need to add one more construct — conditional evaluation.  We will do this in Part III.


2 thoughts on “Your First Cedalion DSL – Part II

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 )

Google+ photo

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

Connecting to %s