Skip to main content Skip to navigation

Department of Computer Science

Lab 6 More on JS-EDEN / Retracing 'a walk' in the EMPE

Lab 3 gave you an introduction to JS-EDEN, a web variant of tkeden. It was apparent that JS-EDEN is still relatively immature by comparison with tkeden ("EDEN"). In this lab, we will again use the master variant of JS-EDEN, available at:

http://jseden.dcs.warwick.ac.uk/master/

Recall the disclaimer1 in Lab 3: JS-EDEN is a "work in progress" so be aware that some/all models have bugs/problems!

This lab revisits the JUGS in JS-EDEN presentation briefly introduced in Session 4.1, reviewing the unusual qualities of the JUGS construal and highlighting some features of its implementation within a presentation context using the master variant of JS-EDEN (Part 1). It also explains how to make a JS-EDEN counterpart of a standard EDEN model, bubblesortBeynon2007 (Part 2). As an additional / alternative exercise that is topical in relation to EM and software development, the use of the EMPE to trace the stream-of-thought is also demonstrated (Part 3).

You are recommended to follow through the exercise in Part 1 whether or not you intend to use JS-EDEN for your WEB-EM coursework, as it gives you valuable context for understanding the challenges of building effective tools for EM. For those who would prefer to focus on using traditional EDEN, Part 3 is an exercise from a workshop given by Beynon and Harfield in Paris in August 2010 which demonstrates how it is possible to use the EMPE to retrace a construction process that in fact took place over a period of several days.

Part 1 - The JUGS in JS-EDEN presentation revisited

The JUGS in JS-EDEN presentation was first implemented in emile. It has been revised for this lab so as to work on the new version of the master under development by Joe Butler2. This is now the version of the master that is invoked as above.

To load the presentation, you simply have to include two files3:

include("models/jspe/run.e");
include("models/cs405/JUGSinJS-E/jugspres2013.e");

and press the Next slide button to bring up the first slide. You should find the presentation easy to follow, and helpful in reminding you of the general characteristics of the master environment as introduced in Lab 3.

Part 2 - Re-engineering an EDEN construal in JS-EDEN

Having reviewed some of the key features of JS-EDEN, you are ready to tackle the principal exercise. Your task will be to make a JS-EDEN variant of a standard EDEN model, viz bubblesortBeynon2007. You can find this model in the EM archive. It is also the theme of one of the EMPE presentations presbubblesortBeynon2007 that you can find in the UsingEMPE directory that you should have downloaded into your own space previously following the instructions in Lab 2B. (Note that a syminfodefns.eden file containing a list of observables that can be loaded using the symbol info tool has recently been added to this directory at ~empublic/teaching/cs405-2011/UsingEMPE/presbubblesortBeynon2007.)

Stage 1: Study the EDEN bubblesort construal. You should first become familiar with the way in which the bubblesort model has been constructed and can be used. You can develop a basic understanding of the model by experimenting with it and by reviewing the contents of the files in bubblesortBeynon2007. The files that define the basic observables are listed in Run.e - they comprise sort.s, sort.d, sort.e, exc.e, maxminfl.e, selmaxminfl.e and rangeline.e. The more sophisticated observables that relate to phases in the sorting process can be found in the bubblesortagents.e file. To carry out the sorting process manually or automatically you will need to load both Run.e and bubblesortagents.e.

Pay particular attention to the key observables that are characteristic of the sorting scenario (such as the list val which contains the keys to be sorted) and those characteristic of bubblesort (such as which phase of sorting is currently in progress - bs_pass - and which position within that phase is currently the focus of attention - bs_pos). The sorting process is automated when the observable autoset has value 1. With autoset=0, you should be able to simulate the process manually by setting the values of bs_pos, bs_pass and exchanging keys as appropriate using the action defined in exc.e.

In preparation for the 'translation' task, you should first check out which definitions in these files can plausibly be directly imported into JS-EDEN4. There is also one rogue feature of JS-EDEN to beware of: the assignment

%eden
val = val_set0;

is used in traditional EDEN to set the value of val, the list of keys to be sorted, to a preset value. In this way it can be used to restart the sorting the process from the beginning. In JS-EDEN, this assignment is currently implemented in such a way that it gives the same value to val and val_set0 as array pointers, so that sorting the array val simultaneously sorts the array val_set0. To overcome this problem, you can use an assignment of the form:

%eden
val = val_set0 // [];

which has the intended effect of assigning an initial value to val without in the process having any side-effects for val_set0. Note that - apart from this pathological feature - what translation means in this context is 'finding suitable metaphors for expressing the set of key observables using JS-EDEN rather than EDEN'. A suitable example of a visualisation using JS-EDEN is depicted beneath the EDEN visualisation in the following figure:

In the JS-EDEN visualisation, the array is represented using an html table. The elements that are yet to be sorted are highlighted on a lightblue background - this segment of elements directly reflects the current value of bs_pass. The element that is the current focus, as determined by bs_pos, is depicted without a black border. The maximum and minimum elements amongst those yet to be sorted are shown in green and red respectively. Note the precise correspondence between these visual devices and the alternative devices used in the EDEN construal depicted above.

Step 2: Develop a JS-EDEN visualisation. In order to construct the JS-EDEN construal of bubblesort, you use a Div() in place of the visualisation that is given in sort.s, sort.d and sort.e. The basic template for this Div is as follows:

offsetx = 20; offsety = 10;
arrwinDiv is Div("keyarr", offsetx, offsety, 50, 500, arrwinSpec);

where arrwinSpec is defined as follows:

arrwinSpec is "
<table border = '2'>
<tbody>
<tr>
  <th style =" // A_v1 // ";" // B_v1 // ";" // C_v1 // ">" // str(val[1]) // "</th>
  <th style =" // A_v2 // ";" // B_v2 // ";" // C_v2 // ">" // str(val[2]) // "</th>
  <th style =" // A_v3 // ";" // B_v3 // ";" // C_v3 // ">" // str(val[3]) // "</th>
  <th style =" // A_v4 // ";" // B_v4 // ";" // C_v4 // ">" // str(val[4]) // "</th>
  <th style =" // A_v5 // ";" // B_v5 // ";" // C_v5 // ">" // str(val[5]) // "</th> 
  <th style =" // A_v6 // ";" // B_v6 // ";" // C_v6 // ">" // str(val[6]) // "</th>
  <th style =" // A_v7 // ";" // B_v7 // ";" // C_v7 // ">" // str(val[7]) // "</th>
</tr>
</tbody>
</table>";

and the strings A_v1, B_v1, C_v1 etc are defined by dependency so that they specify the CSS style appropriately. For instance, the definition of A_v4 is as follows:

RED="red";
GREEN = "green";
BLACK="black";
A_v4 is "color:"// (( val4==minelt) ? RED: ((val4==maxelt) ? GREEN: BLACK));

- it ensures that the font color is red, green or black according to whether or not the 4th element is currently the largest or smallest amongst the keys yet to be sorted.

The strings B_v4 and C_v4 are similarly specified so as to reflect the status of the 4th element with respect to "being included amongst the elements to be sorted in the current pass" and "being the current focus of attention in the sorting process" respectively. For this purpose, you need to supply quite simple conditions in place of the ...'s in these formulae.

B_v4 is "background-color:" // (...) ? LIGHTBLUE : WHITE;
C_v4 is "border-style:solid;border-color:" // (...) ? ORANGE : BLACK;

The introduction of these new metaphors for state in the bubblesorting is essentially all that needs to be done to realise the JS-EDEN construal depicted above. Much of the EDEN code in bubblesortBeynon2007 can be directly re-used. The process of construction is a little messy because of the need to ensure that JS-EDEN is dealing with reasonably well-defined state at all times. You will probably not have time to complete the construction during the lab, but should be able to figure out what you need to do in principle. Should you require more guidance, a variant of the JS-EDEN construal depicted above can be found in the file:

/dcs/emp/jseden/LIVE/master/models/cs405/bubblesort.js-e

Stage 3: Exploit features of JS-EDEN to extend the EDEN construal. Some experiments with the EDEN bubblesort construal are discussed in EM paper #107, which was the subject of the reading and associated exploration in Session 5.3. These experiments can be carried out using the Web EDEN version of the bubblesort construal, as explained at:

http://www.dcs.warwick.ac.uk/~wmb/webeden/bubblesortexpts.html

As discussed in the paper and illustrated in the Web EDEN construal, it is possible to append observables that correspond to two simple invariants that can be used to prove the correctness of the sorting algorithm. With reference to the k-th pass in a bubblesort of n elements:

  • Invariant 1: the elements indexed n-k+1 up to n are sorted.
  • Invariant 2: for k>=2, the element with index n-k+2 is greater than or equal to all the elements with indices in the range 1 up to n-k+1.

A virtue of the JS-EDEN master environment is that it is easy to set up visualisation, widgets and live documentation to support experiment. To demonstrate this, load the JS-EDEN version of the bubblesort

include("models/cs405/bubblesort.js-e");)

- or the one that you developed in stage 2 if you prefer! - then:

  • define observables n and k by dependency in terms of existing observables
  • define observables inv1 and inv2 so that their boolean values reflect the status of the propositions specified in Invariants 1 and 2 above.

For the definition of inv1 and inv2, you may need to write simple JS-EDEN functions - for instance, to check whether the elements with indices between i and j in a list are in ascending order etc. Once you have introduced these observables, you can readily set up a Symbol List viewer in master that displays precisely the observables whose values need to be monitored to appreciate the significance of the invariants in the operation of the sorting algorithm5.

To make your experimentation easier, you may then like (cf. Lab 3) to add a button that initialises the sorting process, together with a combo box that allows you to choose which of a set of possible unordered lists of keys you wish to sort6.

You may also wish to explore other experimental activities that have been illustrated using the Web EDEN bubblesort construal cited above.

Part 3 - Retracing construal development using the EMPE

The EMPE can be used to document the process of developing a construal in such a way that it can be reconstructed 'live'. That is to say, you can follow the steps take by the developer but at any point branch off in whatever direction your imagination takes you. To set up the exercise, you should first consult Lab 3 from last year's version of CS405. When you have read a little about the context for the Constructionism 2010 workshop, you can make your own personal copy of the workshop files, which are stored within the following directory:

/dcs/emp/empublic/teaching/cs405-2012/lab3

As explained in the labsheet, there were four sessions in the workshop. The one most topical for the "software development process" theme is the fourth session. The counterpart of the Run.e file for this session is the file entitled Part4-AWalk.eden: You can execute this file directly by invoking the command:

~empublic/bin/tkeden Part4-AWalk.eden

The EMPE presentation is essentially a reconstruction of a stream-of-thought that extended over several days. Over this period, the developer (Meurig Beynon) extended a pre-existing construal of Sudoku solving to add a new form of visualisation. The development is interleaved with testing of the extension through the parallel solution of a specific Sudoku puzzle. It also illustrates an extension to the EMPE to support replaying files of definitions that capture a specific phase of the construction.


Appendix


The following procedure (intended for the master variant) can be called within a JS-EDEN script so as to display the selected observables in a Symbol List. It takes a single parameter - a regular expression presented between quotes (") as a string:

proc showObservables { ${{
$('.symbollist-search').val(arguments[0]);
$('.symbollist-search').keyup();
}}$; }

This can serve as a useful form of documentation e.g. enabling you to record the observables that were the specific focus of attention as each stage in developing the script.

1. This disclaimer is not meant to deter you from using JS-EDEN. Though you are unlikely to be able to make models as ambitious as those that can be developed using the traditional EDEN interpreter, this will not in any way count against you in the assessment of your WEB-EM submission. On the contrary, you are likely to find that it will be easier to think of interesting novel topics to explore if you use JS-EDEN, and this will be to your advantage. Though there are minor bugs yet to be resolved in master, you should be able to develop your construals successfully by observing the following Advice on Using JS-EDEN. An important EM principle to keep in mind in using JS-EDEN is that of continuously tracing the stream of thought, and - when the state becomes temporarily disrupted - you should give high priority to trying to restore stability rather than rush into restarting the modelling activity. (See Part 3 of this lab for an illustration of this principle in action.)

2. For which Joe has proposed the informal name JoeS-EDEN. Please note that the minor bugs in master alluded to above have been inherited rather than introduced by Joe!

3. You can inspect these files in the browser at the url as: http://jseden.dcs.warwick.ac.uk/master/models/jspe/run.e etc.

4. In earlier prototypes of JS-EDEN, it has sometimes been necessary to re-order definitions to avoid introducing undefined observables on the RHS of a definitions. This should no longer be a problem, but if it is do bring this to the attention of the tutors.

5. In developing a construal, you will typically manually enter regular expressions in a Symbol List viewer for this purpose. It is also possible to invoke the procedure of the form showObservables(reg_exp); to display selections of observables automatically. This is illustrated in the file cited in note 6 below.

6. A solution to this exercise can be found in the file extensionbs.js-e at the url: http://jseden.dcs.warwick.ac.uk/ master/models/cs405/lab6