> [...] I came to the conclusion that we needed to build

> a language that was different. [...] The first criteria

> is that it can not be tied only to text files.

I quoted the above from one of Michael Phipps's recent newsletter articles. When I read those lines, the screen went all wobbly and I flashed back about two years in time. Back then, I contributed a little to a project called Eidola, a new experimental programming language whose main attraction was notation independence. Since articles for the OpenBeOS newsletter apparently don't really have to be on-topic (heh heh), I thought y'all might be interested in hearing about this curious programming language.

No syntax...

Barring the odd graphical language, most common programming languages are text-based. The language has a syntax, a set of rules that determine what your source code should look like: which keywords you can type, which style of braces you must use (if any), how to terminate statements, how to write comments, and so on. You use a text editor to write a bunch of text files that conform to this syntax. Together, these text files make up your program.

Not with Eidola, where source code isn't text based. Instead, a program written in Eidola is expressed in a purely formal mathematical form. Whereas a C++ snippet looks like this:

a = b * 4;

...the Eidola equivalent would be a tree with nodes for the various elements of the expression, rendered in fine ASCII art for your viewing pleasure:

       +----------+

       |  assign  |

       +----------+

        /        \

       /          \

+------------+   +----------+

| variable a |   | multiply |

+------------+   +----------+

                  /        \

                 /          \

        +------------+   +------------+

        | variable b |   | constant 4 |

        +------------+   +------------+

When you compile the C++ snippet above, the compiler first parses your source code file and then constructs a similar tree structure (the so-called "parse tree") behind the scenes. From this tree it generates the final machine code. The nice thing about Eidola is that the whole "parse" step is not needed anymore--you directly manipulate the tree.

...only semantics

Besides syntax, programming languages also have semantics. Where the syntax defines the notation of the various language constructs, the semantics determine what these constructs mean. To draw an analogy with the English language: syntax is the spelling, semantics is the grammar.

For example the C++ statement:

int c = "hello";

...has a valid syntax, but invalid semantics. The statement is well-formed, but it makes no sense to put text into a variable that is destined only to hold numbers.

Eidola only has semantics, not syntax. The example tree above illustrates this. As you can see, the tree contains five nodes: an "assignment" node, which stores the result of a computation in a variable; a "multiply" node which performs that computation; two "variable" nodes, which hold values that can change; and one "constant" node, which holds a fixed value.

Each node knows what kind of language construct it represents, what its value is, and how it relates to the other nodes. The tree is self-explanatory.

Contrast this with the first C++ snippet. After some investigation, you can probably figure out that "a" and "b" are variables, but the text file doesn't store that information anywhere. If you load that source file in your editor, all the editor sees is two ASCII characters "a" and "b". Even editors that do syntax coloring don't really know what these two characters represent. Granted, there are a few advanced IDEs that can tell the difference, but only by performing a lot of trickery.

The program database

It makes sense to imagine an Eidola program as a database of semantic elements, such as classes, functions, statements, expressions, variables, literals, comments, etc. The database not only stores all the entities that your program uses, but also the relationships between them--that's right, using the tree-like structure we saw earlier. The Eidola development environment talks directly to this database.

While you are editing, the IDE "compiles" in the background the new bits you have just added. In other words, it automatically updates the program database, making sure that whatever you are doing is in line with the semantics. This process is very fast, because it typically concerns only one (small) semantic element at a time.

This kind of incremental compilation is pretty cool, because you are immediately notified of errors in your source code. Just like some word processors draw a red wobbly line under spelling or grammatical errors, so can the Eidola development tool.

So how does one run an Eidola program? The IDE will first have to compile the contents of the database into a native executable format (like ELF). The nice thing is that there are never any compiler errors at this stage, because the correctness of the code was already verified while you were editing. A decent IDE would do this in the background as much as possible, so lengthy compile-and-link stages are a thing of the past too. An interesting alternative is a virtual machine that can run the program directly from the database.

How does the IDE store your Eidola programs on disk? Obviously not in a plain text file. Possible candidates are structured file formats such as XML or a binary equivalent. An exciting option is to store the programs in a relational database (think SQL). This would allow for very easy version control, especially in distributed environments.

Notations

So if Eidola only deals with semantics, then what exactly does an Eidola program look like? The short answer is that you can make it look like anything. Eidola doesn't care whether you write a conditional construct as:

if (a != b) { ... }

...or:

IF a <> b THEN ...

...or:

              |

              |

     +----------------+

    /                  \   no

   <  a not equal to b  >------ ...

    \                  /

     +----------------+

             |

             | yes

             |

            ...

All Eidola needs is a compatible "notation". Think of notations as plug-ins for the Eidola development environment. You could have a notation that displays your source code in C++ style (the first example), in Pascal style (the second), using visual notations (such as the flowchart), or whatever you can imagine.

Better yet, you can easily switch between different notations, or even combine them. Remember, you write code once but you read it often. A particular notation can be great for writing, while another may be much better for reading. You may find that mathematical formulas--and most programs have lots of those--are easiest to type in as:

a = 2 * 3.14 / b;

...but are more readable as:

     2 * 3.14

a = ----------

        b

Each notation plug-in allows you to view and edit the source code in a different way. After all, that is what "notation independent" means.

Why, oh why?

If you are still with me, you may be wondering what benefits a notation independent language like Eidola has over traditional programming languages. Here are a few reasons why I prefer Eidola.

Large projects become easier to manage. If your C++ programs comprise only a few source files, it is not hard to remember which class or which function goes where. But if the project grows in size, the number of separate source files rapidly increases, and things become harder to find. And more importantly, things become harder to organize. Managing many different text files quickly becomes a big hassle.

I would love my IDE to show my project's organization in a nice diagram, for example using UML-style boxes and arrows. Not after a heavy analysis phase, but on-the-fly. Sure, there are a few (very expensive) tools that will do this (to some extent), but they always have to translate from the text-based source code and back again. If you have tried this, you will have noticed that it can be pretty hard to keep your diagrams in sync with the source code.

Other kinds of diagrams would be great to have too. One that shows all incoming and outgoing calls of my functions, for example. Or how about a chart that graphs the lifetimes of my threads. Anything that helps me understand the organization (or lack thereof) of my project.

Again, there are tools to do this, such as Understand for C++. This particular program parses your source code and builds a database of all the entities (classes, functions, variables, etc). But every time you make a change, it has to re-scan your source. Eidola works the other way around: changes are made directly to the database, and the notations are updated accordingly.

Easy refactoring. Suppose I have a class "SomeClass" with a member variable named "somevar". What if I want to rename that variable to something else? With current IDEs you have to do a search-and-replace, possibly in more than one file. Good luck if that same piece of text occurs in many unrelated places also. Eidola will simply change that name in its database and tell all the notations to redraw. Done. It knows that somevar is a member variable of the class SomeClass. This makes other refactorings a breeze too.

In addition, Eidola's formal mathematical model allows easy validation and bug testing of your code. This is extremely hard, nee impossible, to do with C++ and most other text-based languages, because they always mix up their syntax with the semantics. Of course, it has been shown a long time ago that you cannot prove a program correct up-front. But Eidola's formal mathematical model really helps to verify reliability, and I wanna betcha that Eidola programs will be a lot more stable than their C++ counterparts.

Fewer flame wars. What about coding style? I probably hate your coding style and you hate mine. Where do braces go, do we need braces, how large should tabs be, do we use tabs or spaces--and so the wars rage on. With a notation-independent programming language, you simply switch to the coding style you like, and thus it will be rendered on the screen. You can do this today with so-called "pretty printer" tools, but Eidola will do this automatically for you, no hassle.

Another item that has fueled heated debate in programming circles is operator overloading. Many programming languages already treat operators as "syntactic sugar". That is, typing a "+" really means "use the plus() function". In pseudo code, "1 + 2" is really "1.plus(2)". Because they are just a syntax thing, Eidola operators are provided by the notation, not by the language itself. Any self-respecting mathematical notation, for example, would allow you to use + on complex numbers.

Theoretically, you can do all of this for traditional text-based programming languages as well, even for C++. But it certainly won't be easy--your base format is text and pure text carries none of the semantic information that the Eidola database does.

So is text out? Not at all. Text can be great for writing programs, but not all the time. Keep in mind that a notation-independent language does not favor one notation over the other, nor does it mean that the notations must be all graphical. Certainly for the insides of functions, I would prefer to type text.

Woot! Where can I get it!?

Er... Eidola doesn't really exist yet, at least not in the form I have just described. This is how I understood Eidola was supposed to work eventually, but unfortunately the project isn't that far along yet. In fact, Paul Cantrell, who invented the language, went on to pursue other things for the time being. Consider Eidola an experiment in its early stages--there are still plenty of problems to solve, but at least the goal is a worthy one.

The Eidola home page is still up, but hasn't been updated in a while. You can, however, download an early implementation of Eidola and several prototype notations that I wrote. You need Java to compile and run it, though.

As far as I know, no other language like this exists already. Microsoft's .NET framework appears to have some notation independent features, but I am not sure how or how well this works. (Yes, I know what you are thinking...) LISP apparently also allows you to change notations, but again I haven't looked into this closely yet.

Will a notation-independent language ever become reality? If it is up to me, yes, although it may take a while. I am working on one or two new programming languages as side projects, and the most adventurous of these will be notation independent. To be honest, I don't think the Eidola language itself is anything special--an object oriented language in the vein of Java, eeew--but its concept of notation independence is quite dandy. I hope I convinced you of the same, or at least made you think about it for a while. ;-)

I'm sorry, this is not about how to lock OpenBeOS developers into basements to ensure they are most productive--it is a well known fact that this is BGA's speciality, anyway ;-) --no, I want to talk a bit about multiple threads and how to prevent them from mangling shared resources due to uncontrolled access.

Before you skip to the next article expecting to be bored to death by repetition of well-stressed basics, give me a chance to explain: Instead of wading through the fundamentals on BLocker or semaphores, I want to discuss a specific locking problem, for which I recently found, as I feel, quite an elegant solution.

The Problem

The setting is actually fairly simple: Given are objects, for each of which an individual read-write locking shall be provided. The problem is that the number of objects is or can be very great--think of thousands of them--so that there would be a good chance for the system to run out of semaphores, when reserving one per object. And I don't even need to mention, that a fair read-write locking strategy (new readers don't overtake waiting writers) requires not one but three semaphores. So, obviously another solution must be found.

The Idea

The solution becomes apparent when considering what the semaphores are needed for in the first place. They provide a means to block a thread, when another thread is in the critical section. Therefore, instead of a semaphore per critical section, a semaphore per thread should be fine just as well. In fact, a semaphore per thread needing to wait is sufficient, but I want to keep it simple for now, and follow the "one semaphore per thread" idea.

The question remains, how to stick the semaphore to a thread (and to do that for each possibly-locking thread). I don't want to keep you on tenterhooks--the answer is TLS, thread-local storage. Arbitrary data can be associated with a thread, and we want to use that mechanism to store, among other things, the ID of the thread's blocking semaphore. Thus, when needed, that semaphore is quickly at hand.

The Implementation

I don't want to miss pointing to the source code of the implementation, which I'm now going to outline. It is accompanied by a bunch of test code, and it passes all of the tests, but in case you find a bug, don't hesitate to tell me. I'm not going to talk about the test code, since that could make up an article on its own.

The main class ThreadLocker is scarily feature-complete. It supports:

• Nested locking: A thread already owning a read or a write lock can obtain more locks of the same kind. Just like BLocker.
• Timeouts: As with BLocker, a timeout can be specified for the locking operation.
• Cross-locking: A thread owning a write lock can acquire a read lock, and vice versa. The latter case is somewhat tricky in combination with timeouts, though. Unlike in the read-write locking MultiLocker sample code provided with an old Be Newsletter article, the locks always remain "type-safe".

Let's have a look through the code. We have four classes:

• Thread: An instance of this class is attached to each thread that runs through the locking code, using TLS.
• ThreadManager: Manages the Thread objects of all threads. This way, it is possible, for instance, to get the object of a thread other than the current thread.
• LockingInfo: Collects all relevant locking data for a thread. An object of this class is associated with each Thread.
• ThreadLocker: The main class. The user needs to utilize this class only. The other classes are used internally.

The Thread/ThreadManager framework is almost a bit overkill, but it's a clean and extensible solution. It should be very easy to use it also for other purposes. The basic idea is to create a Thread object for a thread when needed, and have a singleton ThreadManager manage the respective objects of all threads. The implicit creation "when needed" is the convenient alternative to having the user explicitly create them before using the ThreadLocker (this would be particularly annoying for BWindow and BLooper threads, which aren't explicitly spawned by the API user).

The singleton ThreadManager is retrieved via ThreadManager::GetDefault(). Its GetCurrentThread() method returns the Thread object for the current thread, and GetThread() can be used to get that of an arbitrary thread identified by thread ID. GetCurrentThread() always creates a new Thread, if it doesn't already exist, while GetThread() has to be told to do so via the second, boolean, parameter. GetNextThread() is a typical iteration method. Lock() and Unlock() can be used to explicitly lock the ThreadManager, while GetLock() returns the manager's BLocker. What the latter is needed for, you'll learn a couple of lines below.

The last of ThreadManager's methods, RemoveGoneThreads(), checks whether the threads, whose Thread objects are managed, are still alive, and removes and deletes the obsolete ones. It is not so nice that this has to be done explicitly. In fact, there would be a way to have that done automatically. When a Thread object is created, a callback function could be set via on_exit_thread(), which would remove and delete the Thread object of the dying thread. But since one cannot get the current callback and only one callback per thread is possible, doing so could interfere with other attempts to use this feature. Well, I think, one should be able to live with the current solution, since unless there's quite a coming and going of threads, only relatively little memory would be wasted, and only if RemoveGoneThreads() is never called, anyway.

The Thread class doesn't have that many methods either. There's GetID(), returning the ID of the thread the object belongs to; InitCheck(), with the obvious semantics; SetPrevious(), GetPrevious(), SetNext(), and GetNext(), which are used for managing simple, doubly-linked lists of Threads; and GetLockingInfo(), returning the LockingInfo belonging to the object. Of most interest is the remaining couple, Block() and Unblock(). Block() is called by the thread itself. It uses the semaphore the Thread object has allocated to block the thread, until another thread calls Unblock() or the specified timeout (if any) occurs.

The LockingInfo class is an extended ThreadLocker*-to-int32 map. It counts the number of nested read locks the thread owns per ThreadLocker. The provided methods allow for convenient access to this information. The public flags attribute is used only when the thread is waiting for a lock, indicating whether a write lock was requested and whether the lock has been granted.

Last, but definitely most important, is the ThreadLocker class. On construction a BLocker can be supplied--if none is passed, the BLocker of the ThreadManager singleton instance is used--which will serve as a mutex for accessing the ThreadLocker's data. The other public methods, XYZLock(), XYZLockWithTimeout(), XYZUnlock(), and IsXYZLocked() (XYZ being Read or Write) have obvious meanings. The locking methods, with and without a timeout parameter, both call private methods _XYZLock(), which do the actual work.

The structures of _ReadLock() and _WriteLock() are very similar. Both first get the current Thread and check whether it owns a write lock. If that's the case, the respective nesting counter (fWriterReadNestingCount or fWriterNestingCount) is incremented and the method returns successfully. Otherwise _ReadLock() checks whether the thread already has a read lock and, if it does, it simply increments the nesting count (LockingInfo::CheckAndIncrementNestingCount()), or else locks the ThreadLocker's data for further investigation; _WriteLock() immediately does the latter. If there are no lock owners at the moment (_WriteLock()) or only readers (_ReadLock()) and no thread is already waiting for a lock (both) the lock can be granted on the spot, and the method returns with success. Otherwise the Thread is appended to the queue of waiting threads, the data are unlocked (_MetaUnlock()) and the thread blocks itself waiting for the lock (_WaitForLock(), using Thread::Block()). When it awakes again, either the lock has been granted--then it can return immediately--or a timeout occurred, which requires some cleanup like removal from the queue of waiting threads.

The remaining work is done in ReadUnlock() and WriteUnlock(). They first check whether the caller does indeed own a matching lock and, if so, decrement the nesting count. When the nesting count has reached 0, the thread has released its last lock, and a bit more has to be done: If there are waiting threads in the queue, _CheckWaiting() is invoked. It iterates through the threads in the queue, waking them up one after another (_UnblockFirstWaiting(), calling Thread::Unblock()) until either the end of the queue or a thread requesting a lock that would clash with a lock currently in possession of another thread is reached.

There are some special cases I didn't mention--e.g. when a reader acquires a write lock--but those interested in the details can examine the source code.

Optimizations

Let's finally have a look at the performance and possible optimizations. I haven't done any measurements, so be warned, this is rather theoretical. The measurements Stephen Beaulieu has done for his article show that, for x86, little to nothing can be gained speed-wise by using the described stack_base method. That's not surprising, if you take a look at the find_thread() implementation in <OS.h>--inline assembler and not exactly a lot of it. The same can be said for tls_get(), hence identifying the thread (every time but the first time) should be reasonably fast.

The second idea implemented in the MultiLocker class, using a max_possible_threads-sized array indexed by thread_id % max_possible_threads for storing thread related data, sounds fast, but unfortunately does not only waste a lot of memory--considering that our starting point was that we have a lot of objects to be locked, we must use as little memory as possible per object--it also doesn't work in general, since the assumption that thread_id % max_possible_threads generates a unique index is wrong. E.g., within a team there can, at the same time, very well exist two threads with thread_id2 == thread_id1 + max_possible_threads.

The ThreadLocker implementation keeps the read lock nesting count thread-local instead of storing it in a thread -> count mapping in the locker object. This has the advantage that this information can (mostly) be accessed without needing to lock the locker data, e.g. in the case of nested read locking or IsReadLocked(). The used map (LockingData) is kept as small as possible, i.e. when the nesting count reaches 0, the entry is removed. So, unless a thread holds read locks of thousands of objects at the same time, access should be reasonably fast. Even if it does, O(log(n)) complexity is bearable. As a speed optimization a hash map could be used. All other utilized data structures are very lightweight. Well, the only other data structure is the queue of waiting threads, and all accesses to it are apparently O(1).

Consider two extreme situations: The first one is, you have really many objects, like millions of them, and want to save as much memory as possible. ThreadLocker uses 28 bytes on a 32 bit architecture, but some of this can be bargained for performance. fMetaLocker is not really needed; one can always use the locker of the ThreadManager directly. The nesting counts for the writer, fWriterNestingCount and fWriterReadNestingCount, can be omitted. The latter one can be stored in the LockingInfo as done, when the thread isn't the write lock owner, and the former could be managed similarly to the read lock nesting counts, in a separate map. Furthermore fWriter could be dropped. A simple flag would be sufficient, e.g., in form of a bit in fReaderCount which could be shrunk to 16 bits. Either fLastWaiting or fFirstWaiting can be dropped, sacrificing the O(1) complexity of the waiting thread queue. Only six bytes are left. The other extreme situation occurs when the team runs many threads. In this case one may want to dynamically create and delete the semaphore a thread uses, again with a loss of performance.

A final remark: In a setting where you want to deploy the locker class described in this article, you'll have to carefully choose a locking policy (e.g. locking multiple objects always in a certain order). Otherwise dead locks are guaranteed.

Have fun, and good lock. ;-)

There are a number of issues to address in this scenario to make a tool (or set of tools) that will address all of these needs. Different "clients" of the document will have different needs; Management may not want all of the details. Support may not care how to test the application, etc. Often times, the data needed for a portion of the document exists in another place that is not easily compatible in a simple way with the document creation tool; an example of this might be a database schema stored in a format proprietary to the database tool. These pieces can not easily be kept up to date. Finally, versioning is often difficult and/or unsupported.

The question to ask yourself here is, "What is the Be way of putting all of these requirements together into a single, cohesive solution"?

I believe that the answer is actually from an older Apple product called "OpenDoc". For those who aren't familiar, OpenDoc had a concept that a document consisted of areas that were controlled by small applications. A picture, dragged into an OpenDoc, would be edited by a picture editor. Much like replicants in BeOS. Imagine a simple application whose only purpose is to hold replicants, allow them to be resized, added, moved and deleted and handle saving and printing. This application would be a container. A user can add replicant-based areas or regions to the document. These regions could include anything from a simple text box, a vector drawing or a portion of a spreadsheet. The data, though, is not stored in the container. A reference to the data is stored. When updates occur, the document is updated via node monitoring. An export option would be needed to create a version of the document for people who are not on the same network.

That addresses only some of the issues, though. A view or a perspective of the document would contain the sections that are relevant to a particular class of users. Sections could be added or removed at will. Security might even enforce that certain portions of the document (maybe financial info) is not available to everyone. Finally, a method of storing these files in such a way that versioning is possible and easy needs to exist. For this, I would propose an "overlay" filesystem--a pseudo-filesystem that sits on top of BFS. Instead of replacing a file on save, it makes another copy of it and stores the old one (possibly compressed) elsewhere, but retaining the original inode. This allows apps to point to a particular version of a file without distinct user intervention. A query could be constructed to show the values of all of the files at a particular version or date.

From an operating system level, very little is needed to support this. Even the versioning filesystem would be an add-on. From an application level, the document application should be fairly easy: an app that allows positioning and resizing of replicants, plus loading, saving and printing. Then the replicants themselves would need to be written. Much of the difficult work in building applications like word processors comes from page layout and dealing with other types (embedding spreadsheets, etc). With these difficulties handled elsewhere, the replicants should be fairly straightforward to write. A short list would include text, bitmap, vector, chart, graph, and html, possibly later adding things like database schema, syntax-colored source code, and media types (video, etc).