[Axiom-developer] [crystal] A proposed framework and associated tool: LIS (Logical Information Systems)

[David MENTRE]

Hello Axiom developers and users,

Tim has expressed the desire to have an Information System that allows
to explore and modify Axiom internals. He called that the Crystal. This
has raised some discussions on the Axiom developer list recently
(http://mail.nongnu.org/archive/html/axiom-developer/2003-12/msg00075.html).

I think I have found a *possible* approach to solve issues raised by
Tim. It is called LIS (Logical Information Systems,
http://www.irisa.fr/LIS/). This is a research made at IRISA, Rennes,
France, by Olivier RIDOUX et al. They propose a formal framework,
algorithms and tools (i.e. running code) to classify a system, *explore*
it and *modify* this classification, always in a coherent manner.

Roughly speaking, they propose to attach (valuated) attributes to files
and explore a file hierarchy according to those attributes, by following
attribute paths like one would follow file paths. It is even possible to
lively modify the explored hierarchy (in a coherent manner!). Moreover,
the files itself can be seen has having attributes (per file line for
example). For example, a C or Lisp file could been seen as a directory
containing the set of defined functions in that file.

One of the most interesting feature of their approach is that they
proposed a regular file system interface (called LISFS) to use it. In
other words, from the beginning, the system is usable with a wide range
of existing tools (bash shell, emacs & vi, Gnome and KDE graphical file
browsers, find & grep, ...).

Another interesting approach is that one can have different taxonomy
(i.e. set of classification attributes), that can be used
simultaneously. For example, language specific attributes on C files and
system attributes (file type, file size, etc.). Through a plugin system,
one can add others attributes, to enrich the file system and exibit more
information.

Here is an example that might make the LIS more clear.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
This is a shell session done in an emacs buffer. My comments are added
between shell commands.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  We want to explore the file through their extensions, so we go into
  the ext: directory.

/sfl/sfl1 $ cd ext:/
/sfl/sfl1/ext: $ ls
ext:c    mymusic     name:big         name:mp3_transducer         
name:staying_alive  size:18  size:42
ext:jpg  mypictures  name:ete_indien  name:naivec_adv_transducer  plugins       
      size:3   size:512284
ext:mp3  myprograms  name:foo         name:small                  size:118      
      size:39  size:514395

  We then want to explore only the C files, so we go into the ext:c directory.

/sfl/sfl1/ext: $ cd ext:c/
myprograms  name:foo  name:naivec_adv_transducer  plugins  size:118  size:514395
/sfl/sfl1/ext:/ext:c $ l
total 0
drwxrwxrwx   0 root     root            0 Jan  1  1970 .
drwxrwxrwx   0 root     root            0 Jan  1  1970 ..
drwxrwxrwx   0 root     root            0 Jan  1  1970 myprograms
drwxrwxrwx   0 root     root            0 Jan  1  1970 name:foo
drwxrwxrwx   0 root     root            0 Jan  1  1970 
name:naivec_adv_transducer
drwxrwxrwx   0 root     root            0 Jan  1  1970 plugins
drwxrwxrwx   0 root     root            0 Jan  1  1970 size:118
drwxrwxrwx   0 root     root            0 Jan  1  1970 size:514395

 We concentrated on the foo C file (i.e. foo.c), so we go in its
 directory named foo/.

/sfl/sfl1/ext:/ext:c $ cd name:foo/
foo.c
/sfl/sfl1/ext:/ext:c/name:foo $ l
total 0
drwxrwxrwx   0 root     root            0 Jan  1  1970 .
drwxrwxrwx   0 root     root            0 Jan  1  1970 ..
-rw-r--r--   1 pad      root          118 Jan 16 18:45 foo.c

  We can edit it if we want. foo.c appears as a regular file.

/sfl/sfl1/ext:/ext:c/name:foo $ emacs foo.c 
#<buffer foo.c>

  More interestingly, we can explore the foo.c file itself, using some
  information of the C language. So we code in the parts/ directory of
  the foo.c file (pathname /ext:c/name:foo/).

/sfl/sfl1/ext:/ext:c/name:foo $ cd parts

  Doing a ls, we see the functions defined in foo.c. We have f and f2,
  as well as the whole file, foo.c.

/sfl/sfl1/ext:/ext:c/name:foo/parts $ ls -l
total 977
drwxrwxrwx   0 root     root            0 Jan  1  1970 .
drwxrwxrwx   0 root     root            0 Jan  1  1970 ..
drwxrwxrwx   0 root     root            0 Jan  1  1970 debugging
drwxrwxrwx   0 root     root            0 Jan  1  1970 error
-rw-r--r--   1 pad      root      1000000 Jan 16 18:47 foo.c
drwxrwxrwx   0 root     root            0 Jan  1  1970 function:f
drwxrwxrwx   0 root     root            0 Jan  1  1970 function:f2
drwxrwxrwx   0 root     root            0 Jan  1  1970 synchro
drwxrwxrwx   0 root     root            0 Jan  1  1970 var:

  We can see or edit foo.c.

/sfl/sfl1/ext:/ext:c/name:foo/parts $ cat foo.c
int f(int x) {
int z;
assert(x > 1);
z = x;
fprintf(stderr, "x = 0", x);
return z * 2
}
int f2(int z) {
return z * 4
}

  But we can also go into the C function called f...

/sfl/sfl1/ext:/ext:c/name:foo/parts $ cd function:f/

  ...and visualize or edit it.

/sfl/sfl1/ext:/ext:c/name:foo/parts/function:f $ cat foo.c 

int f(int x) {
int z;
.........:1
z = x;
fprintf(stderr, "x = 0", x);
return z * 2
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

One could imagine to define attributes set for Pamhplet, SPAD, BOOT,
Lisp, etc.

As I said previously, LIS researchers have running code (under GNU GPL
license, written in Obbective Caml), although not yet released to the
public. 

If you want to know more on LIS, they have a full range of papers on
there web site (http://www.irisa.fr/LIS/). The USENIX 2003 paper is
probably the most closed to what I have shown.


So, now, what about LIS and Axiom? I am personnaly convinced that LIS is
a viable approach to solve Tim issues. I'll try in the mid term to make
a first demonstrator, focused on the algebra and the exploration of the
type hierarchy. From that demonstrator, I hope to convince Axiom
developer that the LIS approach is indeed interesting.

If you have questions, do not hesitate to ask me.

Yours,
d.
-- 
David MENTRE <address@hidden> -- http://www.nongnu.org/axiom/