We ended part II of this tutorial at a point where our DSL allowed us to define functions. But these functions are limited. We easily defined a function that squares a number, but if we were to generalize this to say, raise a number by a given power, we were in for a problem. We could do this with recursion, of course, but recursion needs to stop at some point. For that, we need support for conditionals — a way to ask whether we need to stop or to carry on recursing.

In this part we will define the two necessary components: a >= predicate that compares expressions, and a conditional expression. We will focus on giving both the look and feel of their mathematical counterparts. To demonstrate our new abilities we will implement the factorial operator.

Greater Than Life!

Let’s get started. Create a new file under the simpleExpr project. Name it “cond.ced”. Start this file with a behavior for “ge(A, B)” (ge for “greater or equals”). The type is pred of namespace /bootstrap, and the description is “succeeds if A evaluates to a value greater than that B does” (I’m not a native English speaker, so I can only hope this sentence is syntactically correct. Please correct me if I’m wrong).

Let Cedalion help you with declaring this new concept, and assign A and B the type expr (of namespace /simpleExpr, obviously). Add a projection definition, and insert an element to the horizontal list between the visualization of A and of B.

Remember not to save your file at this point. Wait with that until the projection is complete.

We can define our projection as A >= B, just as it would be in C, Java or nearly any other programming language on the planet. But what’s the fun in that? With projectional editing we are not bound by the laws of US ASCII… We can define our projection however we want! And we want it the way it would be written in a mathematical paper, using the ≥ charater.

To do this, select the underscore you have just inserted and select “symbol” from the auto-completion menu. You’ll see a question-mark with a small underscore below it. Right-click the question-mark and select “Mathematical Symbols” from the context menu. A view will open showing you a bunch of mathematical symbols. Scroll to find the one you’re looking for and double-click it. The question-mark is replaced with the ≥ character, and the number 8805 is written in place of the underscore. 8805 is the Unicode value for ≥. You can edit this number to change the character. Save the file to see the effect.

Lovely. Now we move on to giving it meaning. As good TDD boy/girl scouts we start with a failing test. You know the drill… Open the behavior and replace the underscore with the test:

2 ≥ 1

OK, that’s not so easy to do… You need to start with the predicate (≥), but you will not find “≥” in the auto-completion menu. So far we were used to finding what we are looking for in the auto-completion menu based on its projection. When we defined plus(A, B) to be projected as A + B, Cedalion automatically added “+” to the auto-completion menu. However, now that we used a symbol instead of a string, and we cannot really type this symbol using a standard keyboard. We can use the concept’s name — “ge”, but that is not that intuitive. A better solution is to fall back to the way we would do this in C, Java and most other languages — just write “>=”. To be able to do this we need to first define “>=” as an alias of ≥.

Create a new statement below our projection definition (after the second statement). Select “alias” from the auto-completion menu. On the left-most underscore enter the string “>=”, and on top of the _::_ copy and paste the A≥B::pred from the declaration or projection definition.

Now you can easily enter the test. Just select “>=” from the auto-completion menu (be sure to choose the one from namespace /simpleExpr, and not the one from namespace /Fucntional) and enter 2 on its left and 1 on its right.

This test fails because ≥ is undefined. Let’s define it. Append a new statement after the behavior, select (the correct) “>=” from the auto-completion menu and save. Problem solved. Test passing.

This is obviously not what we intended, but this is a correct solution for our under-specified predicate. Basically, our definition of ≥ will succeed unconditionally (:- true) for any input (_ and _). To solve the underspecification problem, let’s create a counterexample.

Between the behavior we have and the definition of ≥ insert a new behavior. Copy the concept and its type from the previous behavior (you can select the “::” for both copying and pasting) and enter the description: “fails if A<B” (this is not entirely true, as A and B are expressions and not numbers, but I didn’t want the grammatical problems I had with the previous description. KISS…). The test needs to be:

1≥2

and it should pass. To make this test correct, select the whole goal and select “not” from the auto-completion menu. This should add a ¬ character on the left. Now the test fails, as it should.

To fix this, let us fix the predicate’s definition. Replace the two underscores with variables A and B. On the right-hand side, replace the “true” with:

A evaluates to A',
B evaluates to B',
A' > B'

Remember that to get a variable to look like A’ you need to call it APrime. The predicate > used on the third line is a built-in Cedalion predicate that comes without a namespace. Save, and the error shall go away.

But is our predicate correct? Yes and no. Yes, because it lives up to its spec (all tests pass). An no, because the spec is lacking one case, in which A equals B. In the current definition the ≥ predicate will fail, although we expect it to pass. We can verify this with yet another behavior. Copy the first behavior and paste it as a new statement after the second one. Replace the description with “succeeds if A and B evaluate to the same number” and add a “+ 1” to the expression on the left-hand side (to do this you will need to click the “1” and then go to its parent — the const, by pressing Alt+Shift+Page Up, then select “+” from the menu and enter 1 as the right operand).

We chose to test 2≥1+1 and not simply 2≥2, because we wanted to test the “evaluates to the same number” part, and not just “are the same”. Different expressions evaluating to the same number are still equal under this.

So let’s fix our bug. In Cedalion we do not have a built-in ≥ operator for numbers, so we were right to use what we had. In logic-programming, however, the definition of a predicate may consist of more than one clause (a statement of the form A:-B) representing different cases. So we write another clause for ≥, covering the equality case.

Append a statement at the end of the file and select (our version of) “>=” from the auto-completion menu. Give the variables at both sides of the “≥” names (A and B), and replace the “true” at the right-hand side of the “:-” with:

A evaluates to V,
B evaluates to V

Save. This should fix the bug.

What we did was require that both A and B evaluate to the same number V. That’s it. our ≥ predicate is ready.

Conditionally Accepted

Now we can define our conditional expression. In imperative programming languages conditionals take a form similar to:

if(<some condition>) {
    <what to do if the condition is true>
} else {
    <what to do if the condition is false>
}

Many languages also provide a conditional expression, such as:

<some condition> ? <value if true> : <value if false>

Here the expressions on both sides of the “:” are needed, since the expression needs a value regardless of the value of the condition.

We need something similar in our DSL to allow recursion. Let’s start, as always with a behavior. Add one at the end of cond.ced.

Name our concept “cond(Cond, Then, Else)”, of type expr. The description will be: “should evaluate to Then if Cond holds”.

Add a declaration. Cond should be a pred (namespace /bootstrap), Then and Else should be expr (our /simpleExpr namespace). Save. We’ll add a projection definition later.

Now let’s write the test. We want a condition that holds and two values. Write:

cond(true, 1, 2) evaluates to X

(when I say ‘write’ I actually mean, edit in the Cedalion way. First the ‘evaluates to’, then the ‘cond’, then the ‘true’, which needs to be of namespace builtin, then the numbers and X.)

This test will fail because we have not defined cond yet.

You know the drill. Now comes the part where we define cond…

Append a new statement and select “evaluates to” from the auto-completion menu. On the left-hand side select “cond” from the auto-completion menu, and save. The test should pass.

To the test, add the goal:

X should equal 1 :: number

The test will fail again. Solve by giving the middle underscore in cond’s definition the name “Then”, then give the underscore to the right of “evaluates to” the name “V”, and replace the “true” on the body of that clause (the right-hand side of the “:-“) with:

Then evaluates to V

Problem solved.

If you feel the familiar smell of underspecification, you’re not wrong. A conditional cannot be specified with just one test case. Let’s add the second case.

Copy the behavior into a new one. Change the description to: “should evaluate to Else if Cond does not hold”. In the test, replace “true” with “fail” (also, of the builtin namespace), and change the expected result to 2 (instead of 1). The test will fail.

The error tells us it took 1 instead of 2. Let’s fix that! Cedalion has an “if” builtin predicate. Let’s use it.

Fill in the missing variable names in the head of the clause defining cond (the left-hand side of the “:-“). Then select the body of that clause and select “if” from the auto-completion menu. An if/then/else block opens. “Then evaluates to V” that was previously in the if block’s place is now placed as the condition. Copy it to the “then” part of the block. Paste it also in the “else” part of the block, but this time, replace the “Then” variable with an “Else”. Finally, replace the if’s condition with variable Cond. Save, and our conditional works as expected.

Makeup Time!

It works as expected, but doesn’t quite look as desired. Recall we want things to look and feel like their mathematical origins. So what do conditional look like in mathematics? A common way to do this is to draw a large brace at the left, and then write two or more expressions, each with the condition in which they apply. The last case is annotated “otherwise”, and applies if non of the conditions hold. In our case, we have only one condition, so we are always going to have two expressions, one annotated with our condition and the other with “otherwise”. Something like this:

 ⌈<then expr> <cond>
{
 ⌊<else expr> otherwise

(please excuse my poor ASCII-art skills. I promise in Cedalion it will look much better…)

Ok, so the only thing missing here is the projection definition. Select the bullet next to the declaration of cond and press F9 to append a projection definition.

Important, once again, do not save the file until you finish editing the visualization. Saving the file when a projection definition is incomplete may result in your projectional editor not able to show your code, and you’ll have to open a text editor and remove the projection there. To avoid this — just don’t save…

In this definition, clear the horizontal list, and insert three empty elements. You can clear it by hitting Alt+Shift+Delete a few times, or by entering “[]” in place of the existing list. In both cases, this will only work if you select the list itself and not the “h”.

on the first and last elements, select “symbol” from the auto-completion menu. Right-click the left-hand symbol and choose “ASCII” from the context menu. From the view that opens, choose a left brace (“{“). Edit the right-hand symbol and enter the number 0 as its Unicode value (below the question mark). The question mark will go away.

Right-click the space between the “h” and the left-brace symbol, and choose “Create brackets” from the context menu. This will bring the middle underscore and the brace closer together. These brackets that we created will shrink or grow with the size of whatever we will put in the middle. So let’s put something in the middle.

On the underscore right of the brace, choose “vert” from the auto-completion menu. You’ll see a small “v” and an empty list ([]). This is a vertical layout. Let’s add content to it. Insert two elements to the list. Note how the left brace grows with the content!

Select each of the new elements and choose “horiz” from the auto-completion menu. Please note, there are two versions of horiz. Choose the one with only an empty list. To each list insert two elements.

To three of the four underscores we are going to copy and paste Variable::type pairs from the above declaration. To the first line, copy and paste Then::expr and Cond::pred. To the first element in the second line paste Else::expr. On the second underscore in the second line enter the string “otherwise”.

Now you can save and watch it take effect.

Not as nice as LaTeX would print it, but much nicer than my ASCII-art from before…

Factorial!

OK, so now that we have conditionals, let’s define a recursive function! One of the most common examples given in literature for such functions is factorial, so let’s make us a factorial!

Create a new file named factorial.ced, and create a new behavior. The new concept will be “fact(N)”, the type will be (our) expr, and the description will be “should evaluate to the factorial of N”. Let Cedalion help you with the declaration and update the type of N to (our) expr.

Add a projection definition (F9 from the bullet next to the declaration). Insert an element before the visualization of N, and enter string “!” there.

As a test, write (in the Cedalion way, of-course…):

!4 evaluates to X,
X should equal 24::number

The test should fail.

To fix, define !N. Append a statement after the behavior and select “:=” from the auto-completion menu. On the left-hand side write !N, and on the right-hand choose “cond” from the auto-completion menu.

OK, we have three blanks to fill. Let’s start from the second line. If N < 2, the result is 1, so replace the underscore on the second line with the number 1.

Our condition is N>=2. Put that above the “otherwise”. Our “then” expression is the most complicated. It’s supposed to be N*!(N-1). Let’s do this one step at a time.

Start with the variable N. Then choose “*” and move to the right-hand operand. Start there from N, select “-” (I trust that you implemented – back in Part II. If not, to ahead and implement it now…), and to its right enter 1. Select the whole N-1 expression and select “!” from the auto-completion menu. Things should look like this:

Save, and the test passes.

But hey, this isn’t right! The expression reads:

N*!N-1

which is understood, but the normal laws of operator precedence as:

(N*!N)-1

and not:

N*!(N-1)

This behavior stems from the idea of projectional editing. Because we do not parse our code, there is no need for an unambiguous look to our code, so (N*!N)-1 and N*!(N-1) can look the same. Cedalion understands the “correct” meaning (the test passes), because we built it this way. But for a mortal, reading this code will be hard and misleading. So let’s assist mortals by adding parenthesis around N-1.

Cedalion supports annotations. Annotations are concepts that appear in the projection, but are removed from the code before it is interpreted. As a result, they can be placed anywhere, but they do not have effect on the behavior of our program. Annotations belong to the annotation namespace.

Select the N-1, and choose “()” from the auto-completion menu.

That’s it. Problem solved.

(Now that I look at the code I see a problem in the lack of space between the “then” value and the condition. When I’ll shoot the video I’ll add this space in the projection definition of cond).

Conclusion

That’s it! Tutorial completed. If you went through the tutorial and really did stuff and understood what you were doing you’re probably good to start your own Cedalion programming. One topic we haven’t yet covered in great detail is the type system, so I’ll make a note to myself to talk about it soon, so we could do fancier stuff such as expressions that take any type.

The sources of this tutorial are published on GitHub, so if you are not in the mood to do everything and just want to look around, you can clone the project into your Eclipse environment (and restart Eclipse… don’t forget).

I’d love to hear what you have to say! About the tutorial, about Cedalion, about the weather… Leave a comment.