Notes and Miscellania

Programming: Sheep and Goats

2011-11-03T04:28:00.000-07:00

Prof Richard Bornat and Saeed Dehnad gave a fascinating EIS seminar yesterday on New Insights into Learning and Teaching Programming. Here is the abstract:

Historically a high proportion (round 30%, sometimes up to 50%) of novice programmers fails to learn to program, and the level of achievement amongst the successful is often disappointing. Until recently the reasons for this miserable state of affairs were mysterious. Now we have some insight, we have a test which reveals important differences between novices, and two potential explanations. The gloomy explanation is that there is a 'geek gene'; even if that is true, we may be able to identify the geeks. The hopeful explanation is that there is something peculiar about programming courses, which elevates difficulties into show-stopping obstacles; if true, we have at last identified one such obstacle, we can hope to identify others, we can diagnose those who are stuck and we may at last be able to do something about it.

They have devised some tests to be given to first year students before and during a programming course. The tests are based on asking students to interpret programs and visual representations of system states in a way that identifies students that can induce the rules of a machine. The test identifies those that cannot work out the rules, those that can work out a consistent set of rules that happen to be wrong, and those that get the correct set of rules.

I find this very persuasive since I noticed a change in my own programming abilities after being introduced to the SECD machine over 20 years ago. The SECD machine is for a particular language, but I hold to the principle that expert programmers have a facility for working with algebraic representations of system executions on a variety of abstraction levels. Essentially, such machines support a data representation of current states, and both past and future actual and possible system executions. That is to be contrasted with axiomatic and denotational semantics that seem less oriented to humans than to mathematics, and with other forms of operational semantics such as SOS or program interpreters where complete executions are not conveniently modularized.

The results of Bornat and Dehnad are also interesting because they can explain the often observed student learner division between sheep (those that can program) and goats (those that cannot). The claim is that introductory programming courses build topic on topic and that any programme of learning that has this feature will exhibit polarity in student results. Whilst offering no solution, it was observed that organizing programming courses for mixed ability might solve the problem of losing students at the initial hurdles.

Presentation on Model Driven CARA

2011-10-09T14:15:00.000-07:00

Last week I presented a School Research Seminar on Model Driven Context Aware Reactive Applications. The seminar generated some interesting questions, particularly about proving security and privacy aspects of applications given a precise representation such as that supported by the approach described in the slides below. This is something I had not really thought about, but is an important feature of mobile applications. Another important area is the incorporation of product lines into this approach. Static variability occurs because of the large number of (versions of) platforms and dynamic variability occurs due to changes in context (battery levels and location for example).

Context Aware Reactive Applications

View more presentations from ClarkTony.

2011-10-01T01:39:00.000-07:00

Attended a workshop yesterday on Composition and Evolution of Model Transformations at King's College, London organized by Kevin Lano and Steffen Zschaler. The presentations covered a wide range of topics including: composition of bidirectional model transformations; traceability issues in the composition of input-destructive model transformations; transformation reuse; composing ATL transformations; verification logics for transformations; visualization of transformation traces; the use of Java agents for model transformations; specifying transformations for model slicing; composition of UML-RSDS transformations. My presentation (and associated paper) was on model slicing:

Model Slicing

View more presentations from ClarkTony

Model Driven Context Aware Reactive Applications

2011-09-18T01:24:00.000-07:00

The explosion of smartphones and tablets has created a demand for fairly simple applications that are essentially driven by user events and that have some element of context-awareness. Unfortunately, the complexity of technology used to develop such applications is not commensurate with the complexity of the resulting app. Therefore, this is an area that is ripe for Model Driven Engineering. There are currently a number of ongoing attempts at developing modelling languages and code generation in this domain, however many are complex, platform specific and/or incomplete. I am currently working on an approach that uses UML-style class and state diagrams to capture the structure and big-picture behaviour of such applications and uses a typed functional calculus equipped with essential context-aware reactive features to fill in the detail. The rest of this post describes the models, I'll post the calculus next time.

The diagram on the left shows Tony's mobile phone.
Clicking on 'add' allows the current address book to be viewed and edited as shown on the right

The owner is altered when a phone that occurs in the address book comes into range.

There are several general features that occur in the application: hierarchical GUI; user-events; context-events; state-changes. These can be captured on stereotyped UML class diagrams and state machines.

The model on the left shows the main screen. there is a single root class called Main. Classes labelled external are part of a user-defined library that must conform to a given interface and that raise events. Classes labelled widget are user defined and can handle (via handler), raise events (via event) and perform commands (via command). Events are processed according to a containment hierarchy. The main screen is shown in the screen-shot above.

The model on the right shows the screen that is created when the 'add' button is pressed. The add screen is shown in the screen-shot above. It uses external widgets to handle the display and editing of lists of contacts. Notics the link back to the main screen that can be used when the back button is pressed. The delete screen is the same as the add screen.

The model on the left shows the screen that is created when the owner is notified of a contact that has come into range.

The behaviour is specified using a state machine where the states correspond to the root classes of the other models. The actions on the transitions are commands and transitions are fired in response to events (user or context).

SoSym Theme Issue: Enterprise Modelling

2011-06-14T14:42:00.000-07:00

SoSym Theme Issue: Enterprise Modelling

Modern organizations rely on complex configurations of distributed IT systems that implement key business processes, provide databases, data warehousing, and business intelligence. The current business environment requires organizations to comply with a range of externally defined regulations such as Sarbanes-Oxley and BASEL II.

Organizations need to be increasingly agile, robust, and be able to react to complex events, possibly in terms of dynamic reconfiguration.

In order to satisfy these complex requirements, large organizations are increasingly using Enterprise Modelling (EM) technologies to analyze their business units, processes, resources and IT systems, and to show how these elements satisfy the goals of the business. EM describes all aspects of the construction and analysis of organizational models and supports enterprise use cases including:

Business Alignment: elements of a business are shown to meet its goals.
Business Change Management: as-is and to-be models are used to plan how a business is to be changed.
Governance and Compliance: models are used to show that processes are in place to comply with regulations.
Acquisitions and Mergers: models are used to analyze the effect of combining two or more businesses.
Enterprise Resource Planning: models are used to analyze the use of resources within a business and to show that given quality criteria are achieved.

Emerging technologies, methods and techniques currently proposed for EM include:

Modelling Languages: including UML; SysML; ArchiMate; MODAF; TOGAF.
Enterprise Views: stakeholder identification; multiple linguistic communities.
Enterprise Patterns: an organization is shown to conform to general (possibly executable) organizational principles.
Event Driven Architectures: constructing enterprise architectures based on complex events.
Enterprise Simulation: executing configurations of organizational units in order to analyse and verify performance.

The Journal of Software and Systems Modeling (SoSyM) invites original, high-quality submissions for its theme issue on Enterprise Modelling (EM). The aim of the theme issue is to bring together a collection of articles that describe a range of EM technologies and approaches in order to provide the reader with a single resource that captures the state of art. The theme issue will include an introduction to the field, an overview of the leading-edge languages and technologies used to undertake EM, and in-depth analysis of techniques or approaches for specific use-cases of EM.

Papers must be written in a scientifically rigorous manner with adequate references to related work.

Submitted papers must not be simultaneously submitted in an extended form or in a shortened form to other journals or conferences. It is however possible to submit extended versions of previously published work if less than 75% of the content already appeared in a non-journal publication, or less than 40% in a journal publication. Please see the SoSyM Policy Statement on Plagiarism for further conditions.

Submitted papers do not need to adhere to a particular format or page limit, but should be prepared using font “Times New Roman” with a font size no smaller than 11 pt, and with 1.5 line spacing. Please consult the SoSyM author information for submitting papers.

Each paper will be reviewed by at least three reviewers.

Important Dates:

Intent to submit : 01 Sep 11
Paper submission: 01 Nov 11
Notification: 01 Feb 12
Publication: 2012

Follow this link for more information.

Magic Gopher

2011-06-11T23:50:00.000-07:00

My father pointed me at this British Council site (shown on the right). The games are used for learning English however my children are amazed that the Gopher can read their mind and gets the answer right every time.

XMF Source Code

2011-06-06T12:16:00.000-07:00

The source code of XMF is now available for browsing via my home page. Look under XMF -> Source Code where there are two browser trees labelled com.ceteva.xmf.machine and com.ceteva.xmf.system. The first contains the source code of the XMF VM (in Java) and the second contains the source code of XMF (in XMF under xmf-src). Note that the Java source viewer will only work when navigating from a file within the source tree due to browser security issues.

The browser trees were created by running the following XMF code over a root directory:

context Root
 @Operation list(out,root,prefix,indent)
  let path = root + "/" + prefix then
      dir = Directory(path,Seq{".*xmf",".*java",".*txt"})
  in dir.build(1);
     format(out,"~V<li><a href='#'>~S</a>~%",Seq{indent,dir.name.splitBy("/",0,0)->last});
     format(out,"~V<ul>~%",Seq{indent+2});
     @For x in dir.contents() do
      let name = x.name.splitBy("/",0,0)->last
      in if not Set{".svn","META-INF"}->includes(name)
         then
          if x.isKindOf(Directory)
          then list(out,root,prefix + "/" + name ,indent+2)
          else 
           if name.hasSuffix("java")
           then format(out,"~V<li class='item'><a onclick='display_java('~S');'>~S</a></li>~%",Seq{indent+2,prefix+"/"+name,name})
           else
            format(out,"~V<li class='item'><a href='~S' target='FILES'>~S</a></li>~%",Seq{indent+2,prefix+"/"+name,name})
           end
          end
         end
     end
    end;
    format(out,"~V</ul>~%~V</li>~%",Seq{indent+2,indent})    
  end
 end

XMF and XModeler

2011-05-25T10:51:00.000-07:00

Both XMF and XModeler are now available from my home page. Click on the links to the left to get instructions for download and for documentation. XMF is a language for developing Domain Specific Languages and for Language Oriented Programming. XModeler is an IDE for Model Driven Engineering and for developing XMF programs.

The download of XMF includes the source code. Since XMF is written in itself (on a small VM written in Java), this is an excellent place to start to see what you can do with the language. XMF supports both functional and object-oriented programming. Classes in XMF have optional grammars that can be used to create syntax-classes that extend the base language. XMF includes features for pattern matching, processing XML, writing prolog-style rules over object structures, threads, daemons, quasi-quotes for processing syntax. Virtually all aspects of the language are open for extension and reflection.

The download of XModeler includes the source code (the actual sources will follow later) so you can browse through the implementation using the various editors. XModeler is written in XMF.

XPL: A Functional Language for Language Oriented Programming

2011-05-10T10:21:00.000-07:00

XPL is a functional language that has been developed to experiment with Domain Specific Languages and Language Oriented Programming. It is written in Java. The source code for XPL v 0.1 can be downloaded here. The language has first-class grammars that can be combined and has access to its own abstract syntax. Grammars use quasi-quotes to build new syntax structures that can be inserted into the XPL execution stream. This is like macros in Scheme (in that language features can be defined with a limited scope). However unlike Scheme XPL can define the syntax of each new language feature.

Here is a simple language feature inspired by an example from Martin Fowler. Suppose that we get a stream of character codes as input. The stream contains information about customers and we need to chop up the input to produce data records. If there are a large number of different types of input data and they change regularly then it makes sense to define a declarative language construct that defines each type. The following XPL code defines a language construct for recovering structure from an input stream:

export test1,test2

// We need syntax constructors for Record and Field:

import 'src/xpl/exp.xpl'

// We need list operations:
//   take([1,2,3],2) = [1,2]
//   drop([1,2,3],2) = [3]
//   foldr(f,g,b,[1,2,3]) = g(f(1),g(f(2),g(f(3),b)))

import 'src/xpl/lists.xpl'

// Define some functions to be used as args to foldr:

combine(left,right) = [| fun(l) ${left}(l,fun(r,l) r + ${right}(l)) |]
   id(x) = x
   empty = [| fun(l) {} |]

// Define a function that constructs *the syntax* of a field extractor:
//   extractor('name',5) = [| fun(l,k) k({name=asString(take(l,5))},drop(l,5)) |]

extractor(n,i) = 
  let record = Record([Field(n,[| asString(take(l,${i})) |])]) 
  in [| fun(l,k) k(${record},drop(l,${i})) |]

// Define the grammar to consists of a sequence of fields.
// Each field builds an extractor. All extractors are combined
// into a mapping from a sequence of character codes to a record:

grammar = {
  fields -> fs=field* { foldr(id,combine,empty,fs) };
  field -> n=name whitespace ':' i=int { extractor(n,i) };
  int -> whitespace n=numeric+ { Int(asInt(n)) };
  whitespace -> (32 | 10 | 9 | 13)*;  
  name -> whitespace l=alpha ls=alpha* { asString(l:ls) }; 
  alpha -> ['a','z'];
  numeric -> ['0','9']
}

// Here is a use of the language: a customer is a name (5 chars) followed
// by an address (15 chars), followed by an account number (3 chars):

customer = 
  intern grammar {
    customer:5
    address:15
    account:3
  }

// The customer map is used by applying it to a stream of char codes:

input = [102,114,101,100,32,49,48,32,77,97,105,110,32,82,111,97,100,32,32,32,53,48,49]
 
test1() = customer(input)

// Just to show everything is first-class:

test2() = map(customer,repeat(input,10))

To use XPL you download the ZIP file (link above). It is developed as an Eclipse project, but can also be run stand-alone. The interpreter is in the xpl package in the source folder. If you run the Interpreter as a Java application in Eclipse then the console becomes an XPL top-level loop that you can type XPL commands to. Here is a transcript of the example given above (user input after a '>' followed by XPL output):

[src/xpl/xpl.xpl 2353 ms,136]
> import 'src/xpl/split.xpl';
[src/xpl/split.xpl 179 ms,262]
[src/xpl/exp.xpl 26 ms,404]
[src/xpl/lists.xpl 108 ms,164]
> test1();
{customer=fred ;address=10 Main Road   ;account=501}
> test2();
[{customer=fred ;address=10 Main Road   ;account=501},
 {customer=fred ;address=10 Main Road   ;account=501},
 {customer=fred ;address=10 Main Road   ;account=501},
 {customer=fred ;address=10 Main Road   ;account=501},
 {customer=fred ;address=10 Main Road   ;account=501},
 {customer=fred ;address=10 Main Road   ;account=501},
 {customer=fred ;address=10 Main Road   ;account=501},
 {customer=fred ;address=10 Main Road   ;account=501},
 {customer=fred ;address=10 Main Road   ;account=501},
 {customer=fred ;address=10 Main Road   ;account=501}]
>

There is currently no user documentation (contact me if you are interested in this). But there are some technical articles: language modules in XPL, modular interpreters in XPL, and parsing infix operators using XPL. In addition the source code contains a number of examples in the xpl folder.

Class Modelling

2011-03-17T08:38:00.000-07:00

System modelling is something that students often find difficult to do. One possible reason for this is that they have difficulty mapping the models to a framework that can be used to validate their design, i.e. what does the model do? Whilst modelling should be more abstract than programming in pictures, I think that grounding the models in an implementation language, at least initially, is a good place to start.

To that end, a while ago I produced and delivered some material that linked class modelling with Java implementations.This was quite well received and can be downloaded as a zip file. The application is a small hotel booking system whose model is shown on the right. The material includes the Java code (as an Eclipse project) of a basic booking system, some slides, some student activities to extend the models and implementation, and the solutions. The models contained in the material were created using the open-source modelling tool called StarUML.

A nice feature of the implementation is that it can print out the state ofthe booking system as an XML document. This means that students can understand state changes in terms of pre and post-states of the system. A natural extension of the material would be to introduce pre and post conditions that can be articulated in terms of the XML system states.

2011-03-14T01:08:00.000-07:00

Arrived back from a three week tour of India. We visited many companies and HE institutions to discuss collaboration in Thiruvananthapuram (Trivandrum), Bangalore, Chennai, Mumbai, Pune, and New Delhi. The scale of operations of IT companies is huge. One commercial campus we visited has around 25 thousand employees; others are even larger.

ISEC 2011

2011-02-25T08:03:00.000-08:00

At the ISEC 2011 Conference this week in Thiruvananthapuram. The conference is held at TCS offices and the entrance lobby was decorated with flower petals as shown on the right. Someone posted photos (of a session I was not at).

Lots of interest in development methods at the conference, particularly Agile methods and Scrum. I gave an invited talk on Domain Specific Modelling as Theory Building (see entry below) at the Advances in Model-based Software Engineering Workshop and gave a paper on Model Based Enterprise Architecture at the conference.

Logic

2010-12-08T02:09:00.000-08:00

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!

2010-11-30T08:44:00.000-08:00

The first snows of the season...

Don't Monkey Around with your Mobile

2010-11-02T10:49:00.000-07:00

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

Modelling as Theory Building

2010-11-02T06:10:00.000-07:00

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

2010-10-10T07:46:00.000-07:00

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

2010-09-18T01:45:00.000-07:00

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

2010-09-12T04:22:00.000-07:00

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

2010-09-04T02:38:00.000-07:00

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

2010-08-10T07:58:00.000-07:00

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

2010-07-29T23:17:00.000-07:00

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

2010-07-03T03:13:00.000-07:00

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

2010-07-01T11:04:00.000-07:00

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

2010-06-16T09:38:00.000-07:00

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

2010-06-04T20:34:00.000-07:00

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

2010-06-03T10:59:00.000-07:00

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

2010-06-02T00:31:00.000-07:00

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

2010-05-31T07:48:00.000-07:00

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

2010-05-30T04:15:00.000-07:00

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

2010-05-26T12:51:00.000-07:00

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

2010-05-21T07:48:00.000-07:00

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

2010-05-14T06:25:00.000-07:00

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.

2010-05-09T12:06:00.000-07:00

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

2010-05-05T10:08:00.000-07:00

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.

2010-04-25T02:33:00.000-07:00

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.

Refuctoring

2009-11-24T14:41:00.000-08:00

A Tweet by Eelco Visser pointed at a presentation by Jason Gorman on Refuctoring. Very very funny.

Language Components and Language Factories

2009-10-26T12:50:00.001-07:00

Currently at OOPSLA 09 and have just scribed for the DSM 09 Workshop and co-organized the 3rd KISS workshop. Interesting that in both these workshops there seems a great deal of interest in language components. This chimes with Role-based Approach Towards Modular Language Engineering presented at SLE 09. Domain Specific Languages researchers seems to be looking for a way to define languages using reusable fragments. Of course there is no consensus on what a language component is, but the term 'semantics' comes up alot. Laurie Tratt and are working on this issue and have termed the overall approach 'Language Factories'. Our paper is to be presented at Onward! 09.

How to Define a DSL

2009-10-21T00:24:00.000-07:00

Markus Voelter has written an article about Best practices for DSLs and Model Driven Development. The article lists and analyses approaches to the development of DSLs and gives them a point score based on whether the author thinks they work or not. Lots of interesting ideas and good advice. I'm not sure I agree with all of them. On one point: how general purpose should a DSL be? I think this is tricky. In the days before DSLs were called DSLs, I was taught to start with a very small general purpose language with a well defined semantics and gradually sugar both syntax and semantics until it had been transformed into the required language. This approach seems to achieve both generality and specificity at the same time whilst being a repeatable step-by-step process.

Programming Sheep and Non-Programming Goats

2009-07-16T05:37:00.001-07:00

Saeed Dehnadi and Richard Bornat have done some field work that claims to show that students aptitude for programming can be detected before a line of code is written. Their approach involves a giving the students a programming test before starting a programming course. I recall being given a Swedish test in junior school to determine my aptitude for French and German.

Teenage Media Behaviour

2009-07-14T10:41:00.001-07:00

Dean Kramer pointed out this interesting profile of teenage media behaviour.

Guy Steele Interviews John McCarthy, Father of Lisp

2009-05-12T14:09:00.000-07:00

I had not seen this before: http://www.infoq.com/interviews/Steele-Interviews-John-McCarthy. I particularly like the comment from John McCarthy that languages should have access to their own abstract syntax.