Mumbai: Tube Maps and Umbrellas

Met the lovely people at the Mumbai Mdx Office. Mrs Bharati Bacha, a staff line up with myself (to prove I'm really here), a tube map (to prepare students for London sight-seeing). When I arrived back at the hotel a wedding was starting. The groom is perched on a horse with an umbrella. Amazingly the horse (and groom) were unfazed by deafening drums while waiting to be introduced to the bride (the groom not the horse).

Mumbai: Beaches, Taxis and Buried Treasure

Arrived at Mumbai for a week long visit. The hotel is on the beach, which was quite full earlier on, however this photo seems to make it look fairly empty:

The front of the hotel is full of taxis, however not all of them seem to be reliable:

At the back of the hotel is an area of palm trees. I wonder if this is where the treasure is buried (not quite a 'Big W')?

Objects and Recursion

I met William Cook last year at OOPSLA 09 (renamed SPLASH as of this year) whose presentation and subsequent blog entry "objects use recursion everywhere" reminded me of work I did years ago on a pictorial representation of how recursion occurs in objects due to 'self' and 'inheritance' (leading to a colleague at the time commenting on how it reminded them of a Klein Bottle).
The basic idea is that an object is a rod of methods surrounded by an environment of variable bindings as shown in cross section on the left. All methods can reference 'self' which can be shown as a hole that is drilled through the methods rod:

At this stage, the 'self hole' is waiting for an object to be supplied. Any object that conforms to the required interface can be supplied. Recursion occurs because the object that is used to fill the hole is the object itself...



...this is achieved by grabbing the top of the object, pulling it round and feeding the object into its own 'self hole'...
grab the top ... ...pull it round...          



...feed the object in and keep going...

This trick can be be used to explain super too. Instead of onw hole there are two holes:

Inheritance means fitting rods together:

This idea was used to define a semantics for Smalltalk. The details can be found here but beware, it is a scanned document and is over 60MB. This slightly less esoteric (but a similarly large scanned document) set of notes on OOP and recursion is a useful introduction.

Operators, Precedence and Associativity

Expression languages often come with infix operators. For example:

x + y * z

It would be useful to be able to write a language module that abstracts the key properties of expression languages so that the module can be reused in different contexts. One of the challenges is to abstract the precedence and associativity rules in order to reflect the following two parse outcomes:

 x + (y * z) and (x + y) * z

Traditional approaches to parsing often use two approaches: (1) encode the precedence rules into the grammar rules; (2) write the parser so that it knows about certain types of operator. Both approaches have disadvantages: (1) complex grammar rules; (2) complex parsing machinery. The XPL parser, in conjunction with the language module approach, allows this to be achieved fairly painlessly without having to (1) encode the precedence in the rules; or (2) requiring the parser to know about operators.

Language Modules

A language consists of syntax and semantics. The concrete syntax can be defined using a grammar and actions in grammar rules can provide a language with a semantics. For example, a grammar for a simple integer expression language can evaluate the expressions as the parse progresses. However, fixing the semantics of a language too early means that the language cannot easily be viewed as a reusable module. Why would we want reusable language modules? A key driver is that language engineering has become an increasingly important part of system engineering. Modern programming languages provide facilities for extensibility and domain specific languages are developed as part of system architectures; therefore there are increasing opportunities for taking parts of one language and using them as the basis for another language. Language modules and language factories aim to  develop an understanding of composibility and reusability in language engineering.

Sadly, Peter Landin died last year after a short illness. Peter was my PhD supervisor and was a huge influence on myself and many others as recalled here. Peter was responsible for a number of very important discoveries relating to Programming and Programming Languages. Although many of these were in the 1960s and 1970s, he was active throughout the time I knew him in the 90s and early 00s when he was developing the foundation of a topic he called Calculations:

calculations seek to characterize the concept of what a program does without being prescriptive about how the desired behaviour is achieved. By providing a way of abstractly capturing program behaviour, calculations offer: an approach to program analysis, an approach to designing programs based on the desired behaviour, and a new approach to teaching about programming, [...] calculations are a missing concept in the study and teaching of Computing.

A calculation is a historical record of what went on when a program executed with respect to some specific data items. An example calculation showing mutually dependent processing of integer streams is shown on the right. Peter's notes on calculations have been typed up and recently published in the Journal of Higher-Order and Symbolic Computation.

Introducing Features for Superlanguages

Modern programming languages increasingly contain features that allow the host language system to be extended by the programmer. The requirements for extensibility stem from a desire to allow problem and solution domain features to be represented directly or declaratively in the program and for the execution engine of the host language to directly execute new features, thereby having knowledge of the language extensions. Features such as meta-programming in Smalltalk, the CLOS MOP, reflection in LISP and Java, Java Annotations, C++ Templates etc., in addition to features of more specialized languages, all offer various ways to achieve extensibility. However these languages are complex, and extensibility features are often incomplete. We will use the term superlanguage to describe a programming system that can be extended. This article is the first of a series that describes a simple core language that captures the essential features of being a superlanguage and shows examples of how it can be used to build languages from modular units.

A superlanguage offers the following features:

• Concrete syntax processing. Such a feature must allow new language constructs to be defined.
• First-class language modules. Language definitions should be data values, subject to normal scoping rules, parametric etc.
• Meta-Programming. Arbitrary computations can be performed when processing syntax in order to process declarative language constructs.
• Access to the abstract syntax ADT of host programming language that can be used to construct and transform arbitrary programs.
• Control over the scope of languages so that, once defined, a new language feature can be placed in scope for a given extent of program text.
• The ability to construct recursive definitions including those that involve grammars and language constructs.

This is the first in a series of posts that analyze essential features of superlanguages. More detail about superlanguages and a simple example language is found here.