Programming: Sheep and Goats

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

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.

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

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

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

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

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

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

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

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.

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

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

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')?