During September I made some progress in the development of Cedalion2, namely in implementing much of its editing logic, and made some preparations towards my participation in SPLASH 2016. I’m dedicating this post to both topics.
In my previous report I mentioned Cedalion2’s projection logic is about complete. This part takes a fragment of a program (a statement or a list of statements), and transforms them to a description of the way this fragment of code should be displayed to the user.
The next step was to provide the logic that will eventually allow users to modify code. Before I could do this, I needed to provide a way to describe actions – operations that change the state of the world (in this case, the content of a file). Being a purely declarative language, Cedalion is not that good at this sort of things. However, Cedalion is good at defining new languages (DSLs), so I defined a simple DSL to represent actions. Code in this DSL is imperative, so you can have loops, conditionals and other fun things you have in imperative code. You can also have interactions with either the state of the program (the server, in our case) and with the user. User interactions include for example updating the display with the new content once the editing is done.
The editing logic itself includes an extraction of the relevant code fragment from the file, modifying it, saving it back, applying the projection logic to the modified code, and (the most difficult part) calculating the undo operation.
Calculating the undo operation is an easy thing to do if we allow ourselves to waste resources. For example, we can save the complete source file before each edit, and when undoing something we can get back to the previous version. I tried to be more subtle and save a minimal representation of the undo. I don’t want to go into the details here, but this was an interesting experience an I believe, a successful one.
After the core editing logic was complete and worked to my satisfaction, I went to sleep happy, but woke up knowing I have a bug. I tweeted the following:
I use TDD (or BDD) to try to avoid bugs as much as I can. Indeed, I find myself writing code (and tests) more and more, and debugging less and less. Unfortunately, there is one kind of bug that TDD will not catch — performance bugs. Typically, unit tests will use small data-sets to make the test simple enough so that debugging it when it is broken (its initial state) is as easy as possible. This also has the benefit that tests run fast, a fundamental requirement for TDD — fast tests can run all the time. Developers run slow tests selectively, and as result some tests only run in “builds” or other major milestones, and therefore bugs can infiltrate the code and only be caught relatively late.
The price, however, in having fast-running tests is that they do not catch performance bugs. If an function that should take O(n) time to execute (n being the size of the data) takes O(n^2) or even O(2^n), when n is very small you may not catch this problem. Cedalion behaviors have a 100ms timeout. Any test taking more time will fail. However, although much of the projection logic was O(n^2) (instead of O(n)), all tests passed.
The root cause of the bug was in the way I used containers. One of the design principles of Cedalion2 was a separation between the logic of the projectional editor and the program itself. The program resides in a container and the editor asks this container specific questions, guarded against timeouts and exceptions. This separation was meant to ensure that even when the program being edited is full of bugs, the use will still be able to edit it (this is not the case in today’s Cedalion Workbench). Unfortunately, this came at a price. Calling a program inside a container means translating the query we wish to perform to the “language” spoken by the container (i.e., add the container prefix to everything in that query). If the query is small in size, this is not a problem. Prolog (the execution engine behind Cedalion) does this sort of things very fast. Unfortunately, for the various parts of the projection, the queries being performed contain (potentially large) fragments of the code. The need to translate these fragments over and over caused the execution time to be O(n^2).
Faced with this problem, it’s clear that we cannot keep this level of separation between the editor and the program. A big part of the editor needs to be embedded in the program, so that calling this logic will be done once per update for the entire code fragment (O(n) * 1) and not when processing the individual sub-fragments. This comes at the price of making the editor fragile. To avoid the problem of potentially breaking the editor when editing its code I came up with the following solution: The editor’s code will reside in the editor (not in the program), but will be “injected” to the program’s container, under a different namespace. So when I’m editing the editor code I’ll have two “copies” of the editor logic: one under the original namespace, which I’ll be editing, and the other that is “injected” by the editor I’m using. The latter will only change when I upgrade my editor. This separation allows me to update the editor code without fear of breaking it in the interim.
I’m currently in the process of modifying the Cedalion2 software according to this new design. The change itself is not that complicated, but there are some delicate issues that need careful attention. Regardless, In the next few weeks I’ll be focusing my efforts elsewhere…
SPLASH 2016 Participation
SPLASH 2016 is my fifth SPLASH (and the seventh altogether since its rename from “OOPSLA”). This is the first SPLASH in Europe — a gamble taken by its head chair, Eelco Visser, a gamble I hope will work out (and become tradition for at least once every few years). SPLASH conferences bring together a few communities within the world of programming languages: Object-oriented (Smalltalk, Java), Scheme, Scala and more. Domain-Specific Languages (DSLs) and Language Workbenches have been topics of interest for many in this community for quite a while (Visser himself heads development of the Spoofax Language Workbench). In my previous SPLASHes I introduced Cedalion (in 2010 and 2011) and Cloudlog (in 2015). In 2014 I presented a paper about how version control could apply to data, but I abandoned this idea later on.
In this SPLASH I’m presenting three things, none of which is an actual paper.
- On Tuesday (Nov 1st) I am presenting a paper on Cedalion at the LWC@SLE workshop. This talk will mostly be a demo of the Cedalion Workbech, guided by the challenge proposed by the organizers. It will be interesting to see the different approaches taken by the different workbenches.
- On Wednesday (Nov 2nd) I am presenting a demo of cloudalion (Cloudlog + Cedalion) in SPLASH-I. In this demo I’ll build a tiny web application (a Twitter-like microblogging app). I will show how such an application can be defined, rather than implemented, and how this fact does not come at the expense of scalability.
- On Wednesday evening I’ll present a poster comparing Cloudlog applications to Cedalion DSLs.