Logic

The BBC Radio 4 weekly discussion programme In Our Time recently covered the history of Logic from Socrates through to computation with Alan Turing. It is an interesting programme and well worth a listen. Necessarily broad in scope but more accessible than the recent hilarious attempt by the same programme to deal with imaginary numbers during which the presenter, Melvyn Bragg, tied himself in knots: 'yes... but what are they?'

Snow!

The first snows of the season...

Don't Monkey Around with your Mobile

Dean Kramer tweeted the following method as part of the Android library:

Modelling as Theory Building

Balbir Barn pointed me to an old paper by Peter Naur: Programming as theory building in the Journal of Microprocessing and Microprogramming, 15(5):253 – 261, 1985. Naur proposes that program designers should explicitly build theories of an application that address all features of the domain that are related to the desired behaviour, whether the features have any direct counterpart in the eventual implementation or not. The theory is implemented by mapping it to a target platform. In doing so, the theory faithfully represents what would now be called the problem domain and represents the key development artifact that can be used to understand and maintain the application. This paper is very relevant to the activities of the DSM and DSL communities. In particular DSM development (for example profiles in UML) rarely pays attention to the semantics (the theory) of the language being defined.

OCL and Textual Modelling Workshop

The OCL and Textual Modelling Workshop at MODELS 2010 was well attended and we had excellent presentations. The day concluded with a review of the current state of the OCL standard maintained by the OMG and a discussion about features that OCL could include in the future. Jordi has blogged an overview of the presentations.

Tom Gilb Keynote

I attended the Keynote Presentation by Tom Gilb at the International Workshop on Requirements Analysis (IWRA 2010) at Middlesex University. Tom's Keynote, entitled What's Wrong with Requirements Methods included many examples of software projects with scarily large budgets where the requirements were vague and focus on software form and function rather than concrete measurable business drivers. He offered a definition of Requirement: Stakeholder Valued End-State and associated decomposition onto a hierarchy of requirement-types that is intended to be more useful than the ubiquitous functional and non-functional categories of requirements. Tom's recent work includes the requirements engineering language Planguage and the associated book Competitive Engineering.

Exam Howlers

This week the Times Higher Education magazine published some US responses to UK Exam Howlers. A personal favourite from the UK:

[A tutor] was asked for a reference via the following message: "Will you please be a referee for a job for which I am appalling?"

And from the US:

[A] lecturer cited a student's scathing observtion that "Prof seems to think that he knows more than the students."

Reminds me of an eminent UK Professor who recalled a student's query during a lecture:

"Sir, are you making all this stuff up?"

IEEE Software Special Issue: Multiparadigm Programming

Dean Wampler and I have guest edited the recent issue of IEEE Software on Multiparadigm Programming. From the guest editors' introduction:

Programming languages, frameworks, and platforms require the developer to use a collection of provided programming features—abstractions—to express data, implement desired calculations, interact with other technologies, create user interfaces, and so on. A collection of coherent, often ideologically or theoretically based abstractions constitutes a programming paradigm. Often, a given programming technology is based on one particular paradigm.

Well-known examples include object-oriented, relational, functional, constraint-based, theorem-proving, concurrent, imperative, and declarative. Less well-known (or perhaps less well-defined) examples include graphical, reflective, context-aware, rule-based, and agent-oriented.

A particular paradigm leads to a specific type of implementation style and is best suited to certain types of applications. Relational programming benefits information-rich applications, whereas imperative programming is commonly used to control hardware. But today's applications are seldom homogeneous. They are frequently complex systems, made up of many subcomponents that require a mixture of technologies. Thus, using just one language technology and paradigm is becoming much less common, replaced by multiparadigm programming in which the heterogeneous application consists of several subcomponents, each implemented with an appropriate paradigm and able to communicate with other subcomponents implemented with a different paradigm. When more than one language is used, we call this polyglot ("many tongues") programming.

Defunctionalization

Olivier Danvy's paper describing a rational deconstruction of the SECD machine is very interesting. It observes that if a machine uses lambda-abstractions to delay computations then this is equivalent, through a process called defunctionalization, to the use of stateful machine instructions and a separate auxiliary top-level interpreter. He uses this process to 'discover' the machine instructions of SECD. Effectively the free variables in the closures that are created in order to delay the computations are captured in data structures (the stateful instructions) that are subsequently fed to top-level functions. Defunctionalization was discovered by John Reynolds and, in a way, shows that higher-order functions are not fundamental to computation (a theory advocated  by Joseph Goguen). However, writing programs in a defunctionalized style would be a real pain because all lambdas would have to lifted to the top-level. So perhaps higher-order functions are fundamental to programming after all.

Lots of Tiny Languages - All Different

The MIT Technology Review reports on the Emerging Language Camp. This looks like an indication of things to come. The article makes an interesting point that existing mainstream languages were designed for computational architectures that are rapidly becoming outdated. Software systems  are no longer based on single-processors, single-heaps, and reliable in-core execution paradigms. There seems to be increasing interest in languages that are not exclusively based around the all-conquering OO message-and-state mechanisms that emerged in the 80's. Part of the change seems to be driven by the rise of mobile devices and new styles of device interface. Is the era of the 'big language' (C++, Java) over?

XCRI

I attended a meeting yesterday that introduced me to XCRI. This is an XML format for representing course information so that institutions can provide an XCRI feed, thereby publicizing their offerings for others to integrate into applications. Perhaps we are heading for a situation where it will be possible to specify your detailed HE requirements (skills, interests, teaching and learning methods) and for a system to generate matches, automatically enroll, produce learning portfolios, etc. Or perhaps its just a way for the UK government to measure and manage HE provision.

Cycling for Charity

My brother-in-law has just set off on his cycle tour from John O'Groats to Lands End.  He is raising money for the Psoriasis Association. You can follow his progress via the following blog where there are further details if you wish to support the charity.

Modular Interpreters

As part of the Language Factories work that Laurie Tratt and I started a while back, I have done some experiments to see whether a language family can be implemented using XPL and how far the differences between members of the family can be hidden. My experiment involved defining a language factory for state-machine languages. Such a factory is shown on the right where syntactic variations include the rules for the transition labels, and semantic variations include whether machine execution is single-threaded or multi-threaded and whether the labels are processed. I was particularly interested in designing a single machine interpreter that works with many different implementations. This turns out to have some relationship with monads and modular interpreters although I have not developed this with any rigour. A short article describing how this is implemented is here.

Workshop on OCL and Textual Modelling

Jordi has blogged about out up-coming workshop on OCL and Textual Modelling at MODELS 10. Please submit a paper and/or bring this event to the attention of your colleagues.

Pune: Raining, Singing and a Grumpy Chef

A short visit to Pune where it had been raining so hard it had brought branches of trees down onto the road. My colleague Shakil Shaikh took me to a restaurant hidden in the middle of the hotel. The louder the band played the grumpier the chef looked (despite being asked to say 'panir'). Off to New Delhi....

Mumbai: Shopping

After finishing in Mumbai we went for some retail therapy. Mrs Bacha is a formidable shopper and seems to know all the shopkeepers. She made sure of 'local prices' in a fantastic carpet shop. Now off to Pune 'the Oxford of the East' (which seems to be pronounced 'poon-a' and 'poon-ay' interchangeably.

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.

I came across Logicomix when browsing in a book store at St Pancras railway station. Amazingly, it is a graphic novel about the logical foundations of Mathematics told from the perspective of Bertrand Russell. I have not encountered graphic novels before but this is a fantastic introduction to the subject told with great pace and verve. Highly recommended.