Alma Homepage

Alma System (resumo em português)

·        Create a system able to extract the meaning of a program and to present it in a clear way using visual explanations of the program behaviour simulations.

·        Remove language and program dependencies

                       

Alma System: Design Goals

 

·        Build an integrated and easy to use environment

·        Avoid the need for any kind of change in the source code

·        Allow the selection of different views of the same program

·        Create a system as generic as possible in order to be used by different source languages

 

Alma System: Architecture

 

 

Input and Output of ALMA

 

·        INPUT – the specification of FE allows the user to map the conceptual elements of his language to the DAST nodes

·        OUTPUT – the BE works on that DAST using two bases of rules (visualizing rules and rewriting rules) and constructs the output – the animation.

 

Alma System: Internal Representation (DAST- Decorated Abstract Syntax Tree)

 

·        Structure of DAST nodes – name of the symbol, production identifier, set of attributes, children nodes, ... (that will represent names, types and values of the source program identifiers)

·        The set of symbols is pre-defined and the symbols that can be generated belong to the abstract grammar of the Alma

·        One node can represent different things depending on the source language but it must represent the same underlying semantics

·        These nodes are used on the BE rules definition (VRB and RRB)

 

Alma System: Front-end

 

n      One FE for each language (grammar) that constructs the DAST using pre-defined methods in the semantic evaluation (the use of these methods depends on a mapping that associates concepts of the source program to DAST nodes)

 

Alma System: Back-end

 

n      Independent of the source language

n      It’s the same for all the FE’s

n      Implements the algorithm animation

n      Works over the DAST based on a set of visualizing rules (VRB) and a set of rewriting rules (RRB)

n      The animation is based on the internal representation of the source program

n      That internal representation has standard syntax formally specified by a grammar

n      The visualizing and rewriting mapping are easily specified

 

      

 

 

 

Animation Algorithm

 

Is divided into:

Tree walker visualizer

–         Traverses the tree applying the visualizing rules to the appropriate subtrees

–         Applies several (as many as possible) rules in one traversal

–         Produces the visualization of one state of the program

Tree walker rewriter

–         Traverses the tree but it applies only one rewriting rule (semantic or syntactic modification)

–         Then the tree will be ready to be visualized again

 

Visualizing rules

 

VRB: DAST ® set (condition ´ drawprod)

Vis_rule(ProdId) = <tree_pattern>,

                   (condition),

                   {drawing procedure}

<tree_pattern>=<root,child1,...,childn>

 

*      Note that it can be specified more then one rule for each production

 

Rewriting rules

 

RRB: DAST ® set(condition ´ newtree ´ attribsEval)

Rew_rule(ProdId) = <tree_pattern>,

                   (condition),

                   <newtree>,

                   {attribsEval}

 

*      Note that it can be specified more then one rule for each production

 

Reusing Lisa System in Alma Implementation

 

  • Lisa System is used to construct the FE for each new input language of Alma System.
  • Some of its Java classes and editors are used to edit and show the inputs and results of Alma.

 

 

Reusing LISA in BE of ALMA

 

 

The first example is a simple imperative language…

 

Source text…

 

a ? ;

b ? ;

let  c  =  a  +  b  ;

c  !  ;

 

FE construction

 

rule AlmaAxioma{

     PROG ::= STATS  compute {PROG.dast = mkroot(STATS.tree);};         

     }                            

rule STS {

     STATS ::= STAT \; STATS  compute {STATS[0].tree =  mkstats(STAT.tree,STATS[1].tree);}                                    

             | STAT \; compute {STATS.tree=STAT.tree;};

     }

rule STATEMENT {

     STAT ::=  let  VAR  =  EXP  compute {STAT.tree = mkassign(VAR.tree, EXP.tree);}

             | VAR  \?  compute {STAT.tree = mkread(VAR.tree);}

             | VAR  !  compute {STAT.tree = mkwrite(VAR.tree);};

     }

rule EXPR {

     EXP ::=  T #opad EXP  compute {EXP[0].tree = mkoper(T.tree,EXP[1].tree,#opad.value());}

            | T  compute {EXP.tree = T.tree;};

     }     

 

Generated DAST

 

 


                       

 

 

 

 

 

 

 

 

 

 

 

 

Generated Animation

           

 

With a new FE for a robot language and some new rewriting and visualizing rule we will get very different results….

We will  get a different abstraction level…

 

Source language grammar

 

robot → ini_pos moves

ini_pos → “xi =“ INT “yi =“ INT

moves →  moves mov

      |  mov

mov → dir nsteps

dir → DOWN | RIGHT | UP | LEFT

nsteps → INT

 

Source text

 

xi= 0

yi= 0

DOWN 3

RIGHT 7

UP 2

LEFT 4

 

Generated DAST

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Rewriting Rules

 

rew_rule(lstmov) = <a:lst, b:const, c:const>,

                   (getvalue(b)!=NULL),

                   <a:lst, b: const, c: const>,

                   { x=getTableVal(xi);

                     y=getTableVal(yi);

                     calculate(x,y,getValue(b),getValue(c))

                     putTableVal(xi,x);

                     putTableVal(yi,y);}

 

rew_rule(passign) = <at:assign, a1: var, b: exp>,

                    (getValue(b)!=NULL),

                    <passign: at: assign, a2: var, b: exp>,

                    { setName(a2,getName(a1));

                      setValue(a2,getValue(b));}

 

Visualising Rules

 

vis_rule(robot) = <a: procdef, b: stats>,

                  (),

                  <a:procdef, b:stats>,

                  {drawrobot(getValue(xi), getValue(yi))}

 

drawrobot(int x, int y){

          String fich = getImage(x,y);

          drawImage(“fich.gif”);

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


With a new FE for Prolog programs and using the same rules used in the first examples we will get the animation below….

 

Source program

 

mãe(alda,joana).

mãe(joana,joão).

pai(luis,pedro).

pai(luis joana).

pais(M,P,E) :- mae(M,E), pai(P,E).

 

 

Generated DAST

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Image nº1

Image nº2

Image nº3

 

 

Image nº4

 

 

Image nº5