cdiggins.com

Starting Friday at 5pm is Blitzweekend: a 48 coding marathon and product incubator. You and a team develop an idea. There really aren’t any rules, it is an opportunity to meet some people, do some innovation, and show off your chops.

This will be a new experience for since code development has always been a very private endeavour: I usually lock myself in a room and emerge a few weeks later with strange products. It will be an interesting expreience though, and I both look forward to and fear meeting so many people. I sometimes get uncomfortable in social circumstances. It isn’t an accident that I work with computers.

 Anyway, my Blitzweekend product will be a Heron editor that provides two methods of editing the source: visually (like a UML editor) and textually (like … well a text editor). My partner Hugo Duncan, is planning on developing a Heron to XMI and back again converter so that we can interoperability with other UML tools. This will be the first xUML editor that I am aware of that provides a view of the models in text format and allows them to be edited. Hopefully I will have something fun to share at the end of this.

While the Heron specification isn’t yet ready to be downloaded, I recently completed a sample application using the prototype Heron to Java compiler and thought I would share it with the community. The Heron source code is available at: http://code.google.com/p/heron-language/wiki/BouncingBallsExample. The resulting applet requires Java 1.6 and can be viewed at http://www.heron-language.com/demo.html.

The Heron to Java compiler is written in C++ using the YARD parsing library. The source code is licensed under the MIT licence 1.0. and can be browsed online at Google codehosting. Contact me if you would like the source as a single archive, or if you need a different license. Please note that this is a very preliminary version of the Heron to Java compiler and is not intended for general consumption.

Heron is a general purpose programming language that is designed to be compatible with executable UML (xUML). It is intended to facilitate round-trip engineering between UML and text-based source code. Heron is an object-oriented language with support for functional programming inspired by the Scala language by Martin Odersky at EPFL and the Object Action Language used in the book Executable UML: A Foundation for Model-Driven Architecture by Mellor and Balcer . The Heron language extends the JAction action language, a surface syntax for UML actions, that allows programmers to develop xUML applications using text-based tools. JAction is being developed by professor Abdelwahab Hamou-Lhadj at Concordia University and myself.

One of the more novel features of Heron is the ability for objects to handles asynchronous messages using state diagrams. This allows us to write code that explicitly models an object’s lifecycle. This makes Heron particularly well suited for event driven applications, such as those with graphical users interfaces.

This is a follow-up to my earlier post, succinctness is not power.

My criticism of Paul Graham’s essay, Succinctness is Power, was that his emphasis was too much on compactness rather than clarity. I tried to make the point that clarity was more important, and that being too compact could interfere with clarity. However, several people have pointed out to me that I was not giving Paul enough credit and that his essay could be paraphrased as: ”undue verbosity obscures clarity”. This is definitely something I agree with.

The following  is my response to a recent post on lambda-the-ultimate.org concerning one of Paul Graham’s essays. The question is, is succintness power?

For most users of computer languages (software developers) programming languages are for specifying the implementation of software systems that are correct and easily maintainable. Succinctness is at the bottom of a long list of desirable qualities.

To test the truthfulness of the “succinctness is power” hypothesis we simply need to consider the case of any maximally succinct language. That would be a language with maximum information content (i.e. no more compression is possible). Such a language would clearly be utterly unusable.

While I agree that some degree of succinctness is important (clearly we don’t want the expression of basic algorithms to be an order of magnitude longer than it should be) the challenge with developing software isn’t writing the code, it is finding bugs and making changes. It is more important to the vast majority of software developers that languages make those tasks easier than to allow us to type as fast as possible.

This is a blog post that is intended to help people new to interpreters with the steps of building a translator from Cat to some other language.

The first step is to figure out how you want to embed Cat in the other language. Two of the simplest ways to do this are: map every Cat instruction on to a function or object in the target language or write a mini-interpreter in the other language. 

A mini-interpreter might be in the form of an evaluate statement that takes a list of objects representing Cat instructions. An example of a mini-interpreter of Cat in Scheme is:

(define (cat-eval stk exp)
  (if (not (list? exp))
      (error "can only evaluate lists"))
  (if (null? exp)
      stk
      (cat-eval
      (trace
       (case (car exp)
	 ((true)   (cons #t stk))
	 ((false)  (cons #f stk))
	 ((apply)  (cat-eval (cdr stk) (car stk)))
	 ((papply) (cons (cons (cadr stk) (car stk)) (cddr stk)))
	 ((pop)    (cdr stk))
	 ((dup)    (cons (car stk) stk))
	 ((swap)   (cons (cadr stk) (cons (car stk) (cddr stk))))
	 ((dip)    (cons (cadr stk) (cat-eval (cddr stk) (car stk))))
	 ((add)    (cons (+ (cadr stk) (car stk)) (cddr stk)))
	 ((mul)    (cons (* (cadr stk) (car stk)) (cddr stk)))
	 ((sub)    (cons (- (cadr stk) (car stk)) (cddr stk)))
	 ((div)    (cons (/ (cadr stk) (car stk)) (cddr stk)))
	 ((eq)     (cons (= (cadr stk) (car stk)) (cddr stk)))
	 ((lt)     (cons (< (cadr stk) (car stk)) (cddr stk)))
	 ((lteq)   (cons (<= (cadr stk) (car stk)) (cddr stk)))
	 ((gt)     (cons (> (cadr stk) (car stk)) (cddr stk)))
	 ((gteq)   (cons (>= (cadr stk) (car stk)) (cddr stk)))
	 ((empty)  (cons (null? (car stk)) stk))
	 ((cons)   (cons (list (cadr stk) (car stk)) (cddr stk)))
	 ((uncons) (cat-eval (cdr stk) (car stk)))
	 ((unconsd)(cons (car stk) (cat-eval (cddr stk) (cadr stk))))
	 ((makeref)(cons (list (car stk)) (cdr stk)))
	 ((setref) (begin
		     (set-car! (car stk) (cadr stk))
		     (cons (car stk) (cddr stk))))
	 ((deref)  (cons (car (car stk)) (cdr stk)))
	 ((if)     (if (caddr stk)
		       (cat-eval (cdddr stk) (cadr stk))
		       (cat-eval (cdddr stk) (car stk))))
	 (else     (cons (car exp) stk))))
       (cdr exp))))

Notice that there are two arguments: the stack and the expression. This function manipulates the stack according to the instructions.

If Scheme is hard for you to read I suggest taking a look at the JavaScript interpreter source code which shows a similar approach in JavaScript.

The other option for a translator is to map Cat instructions and literals directly on to functions or objects in the target language, and provide a library for the primitives. For example: we can imagine with the proper library support translating the following function definition in Cat

define f { 2 dup quote apply add }

into the following C++ (or Java or C#) code where all functions share access to a common global stack:

class F : Object {
  virtual void eval() {
    int_literal(2).eval();
    dup().eval();
    quote().eval();
    apply().eval();
    add().eval();
  }
};

I should point out that this only one of a huge number of possible implementation options. A stack-based language can be implemented in many different ways such as through the use of graph reduction, or rewriting rules. I suggest though that a first attempt you should try and stay as simple as possible. Afterwards you will probably have lots of ideas about how to optimize your implementation in different ways (e.g. making it run concurrently, running as fast as possible on a single thread, making it extremely space efficient, etc.)

One of my favourite features of the upcoming Heron 2.0 is the introduction of “states”. A state refers to a stage in an object’s lifecycle (perhaps stage or step would be a better name to avoid confusion). Whenever a signal (i.e. message) is recieved by an object (not to be confused with operations which correspond to plain old member functions) the object transitions to a new state. Each state has an entry procedure which is executed upon receipt of the signal, and a transition table which shows what signals map to what states. 

All of this happens asynchronously, and makes it easier for software to be executed on concurrent systems, without exposing the nasty details of multi-threaded programming to the programmer. Thank god, because I suck at writing multi-threaded code. Don’t laugh, most people suck at multi-threaded code more than they realize. Almost all non-trivial multi-threaded code falls into at least one of the following categories:

• doesn’t scale
• is broken (try a true multi-processor machine)
• is inefficient
• is unmaintainable

To realize the truth of this, consider how much of the progress on C++ in the last 10 years has been discovering new ways that multi-threaded code doesn’t play well with it. Anyway, I’m ranting now.

The state machine approach in Heron is basically a direct implementation of the idea of using state machines to model an object’s lifecycle as described in Executable UML: A Foundation for Model Driven Architecture by Mellor and Balcer. Heron is motivated by my desire to represent the concepts of xUML in a programming language, so that we can move back and forth freely between UML diagrams and source code. I feel this is key for gaining widespread support for MDA.

On the subject of state-charts and state-machines, my friend Frank Krueger pointed me to the following links:

Tim Sweeney’s implementation of States in his language “UnrealScript”:
http://unreal.epicgames.com/UnrealScript.htm#States

David Harel’s Statechart work:
http://citeseer.ist.psu.edu/harel87statecharts.html

– 

To this I’ll add:

[169] Yuri Gurevich, Benjamin Rossman and Wolfram Schulte
Semantic Essence of AsmL
Theoretical Computer Science
Volume 343, issue 3, 17 October 2005, pages 370-412
Originally published as Microsoft Research TR-2004-27, March 2004

The Abstract State Machine Language, AsmL, is a novel executable specification language based on the theory of Abstract State Machines. AsmL is object-oriented, provides high-level mathematical data-structures, and is built around the notion of synchronous updates and finite choice. AsmL is fully integrated into the .NET framework and Microsoft development tools. In this paper, we explain the design rationale of AsmL and provide static and dynamic semantics for a kernel of the language.

I guess there’s no reason to be coy about it, while looking for work I’ve restarted work on Heron. Heron is now taking a new direction though: I am making it compatible with executable UML (xUML). The idea is for Heron to be an interchange format with xUML. Heron incorporates an action language called JAction, which can be used alone with UML diagrams to express action semantics. 

Action languages are used to express the procedures when a state transition occurs in a state diagram, or the actions associated with an operation, or can be used to express constraints in UML (instead of OCL).

Heron extends JAction with a text-based method of expressing UML classes and associations. Ultimately the goal is to be able to move seamlessly between Heron and UML.