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.