[Axiom-developer] RE: dependency visualization with VCG

[Page, Bill]

David,

About Perl hacking and literate programming. You are
right of course that I should have provided more
documentation with the Perl scripts. There is never
enough time! But I promise that I will move some of
the following description into a pamphlet file at
some point in the future if the scripts appear to
have any long term value.

The algorithm that I used in the 'depends' script is
as follows:

1) First depends is given a list of spad files as an
argument list. E.g. all the files beginning with
the letter X:

  % mnt/linux/bin/depends int/algebra/X*.spad

The contents of each file, in turn, is loaded into the
work space name $buf for further processing. Let's
denote a specific spad file by 'A'.

2) Within the $buf work space, a search is made
for the )ABBREV command that marks the beginning
of a module (domain, category or package). The names
from this command are saved. Let's denote the name
of a specific module by 'M'. Anything in the buffer
prior to this command is discarded. Each input spad
file 'A' may contains more than one module 'M'.

3) For each of these modules, we also look for the
pamphlet file that contains the module. Denote the
pamphlet file by 'P'.

4) After locating the )ABBREV command, another
pattern search is done to find the actual start of
the module definition continuing up to the 'with'
clause (which often appears as part of a macro).
Here we will find a list of all the functions which
this module "exports", i.e. potentially makes
available to other modules. Let's denote a specify
function by 'F'. There are usually many 'F' for
each 'M'.

5) For each of the functions 'F' in the with clause,
a search is done (using grep) for all other spad files
which contain a reference to the function name. Some
of these names will be "overloaded" so we also check
that the files we located also contain the name of
the module itself. Let's denote each of the spad files
that contains an 'M' qualified reference to 'F' by
the symbol 'B'.

6) For each of the spad files found by the above
search, we generate a line of output indicating an
edge in the dependency graph. I.e.

  'B' uses 'F' from 'M' in 'A' ('P')

7) Now this process is repeated with the next
module 'M' found within spad file 'A', starting
again at step 2) above. And so on with each file
in the argument list.

8) The resulting list of dependencies is in ordered
on the target spad files rather than the source
files, but this is easily remedied by use of the
Linux sort command. Also, there is the possibility
that the same dependency could be generated more
than once, so the sort option -u (unique) is also
useful.

9) A script called 'unique' is provided which after
sorting, suppresses the repeated source module names
to produce a more readable dependency list in the
usual format 'index' format.

---------

About handling macros. That is where the "heuristic"
comes into the algorithm. In fact, there is no attempt
to make use of the actual macro definitions per se.
The assumption is made that *if* a spad file contains
*both* a specific function name 'F' and the module
name 'M' anywhere in the same file, then there (very
probably) exists a reference to that function. All
such references are assumed to constitute dependencies.
Very often in the coding of the spad file, the module
name will be contained in the definition of a shorter
macro (say 'm') and it is that macro 'm' that appears
together with the function name 'F' as in F$m or in a
domain expression. It is possible however for the
algorithm to make mistakes, especially in the case of
short, multiply overloaded function names which some
times occur together in a module. This will sometimes
result in "extra" bogus dependencies, but it should
not miss any really existing dependencies.

Please let me know how you make out with your trails
with the VCG / aiSee graphics package. aiSee apparently
includes an experimental "clustering" algorithm that might
be interesting for finding "tight" cyclical dependencies.
But even if an automatic layout determination is not
possible, perhaps some manual effort will produce a useful
graphical representation.

But I am starting to think perhaps some other approach
might be desirable for producing the kind of "optimized"
layered structure that Tim has described. In that regard,
counting the number of cycles in which each module appears
in the simple output of the topological sort done in the
script I called 'order' might be of some interest. The
counts might be treated as "weights" assigned to each
module in terms of their value as bootstrap candidates.

Cheers,
Bill Page.


> -----Original Message-----
> From: David MENTRE [mailto:address@hidden
> Sent: Tuesday, August 26, 2003 2:32 PM
> To: Bill Page
> Cc: address@hidden
> Subject: Re: dependency visualization with VCG
> 
> 
> Hi Bill,
> 
> Sorry for the late reply. My real life is interfering with my hacking
> activities. ;-)
> 
> "Bill Page" <address@hidden> writes:
> 
> > The Axiom dependency graph that I tried to use with xvcg has
> > over 1040 nodes and more than 17,000 edges (dependencies).
> 
> I'm currently trying with a smaller graph (just dependencies between
> spad file generated by your script).
> 
> > Do you have any ideas about the size of graphs that can be
> > successfully manipulated with VCG? Do you have any suggestions
> > on where to go from here? Do you think of any way to segment
> > the Axiom dependency graph into smaller more manageable
> > sub-graphs?
> 
> Sorry, I have no answer to all of your questions. I'm just a 
> occasional
> VCG user.
> 
> By the way, I think your script would be a good candidate for literate
> programming. The conciseness of Perl makes some parts of your script
> quite obscure. :)
> 
> In fact, the most missing part is an example that would 
> explain what the
> code is doing. 
> 
> In your perl script, how have you handle the case of macros?
> 
> Yours,
> d.
> -- 
>  address@hidden
>