From: David Trudgett
Subject: Code analysis, call graphs for Common Lisp
Date:
Message-ID: <m34qdpualm.fsf@rr.trudgett>
I've been having a bit of a look around for some code to do call
graphs given Common Lisp source code input. One of my purposes is to
find functions that don't get utilised at all (due to code
refactoring, for instance).
I suspect this sort of analysis might be a difficult task for CL
because of its dynamic nature, macros, and so on and so forth.
I did notice a reference to something in the SBCL profiler that
outputs a run-time call graph or something. Is that the best deal out
there? (I don't use or produce closed source software, so it needs to
be open source [Free Software], although others reading along may be
interested in non-Free solutions that may be available.)
The Lisp I'm using is CMUCL 19a. Editor is GNU Emacs/SLIME. O/S is
Debian GNU/Linux and Red Hat Linux.
Thanks for any pointers you can provide!
David
--
David Trudgett
http://www.zeta.org.au/~wpower/
Omnis enim res, quae dando non deficit, dum habetur
et non datur, nondum habetur, quomodo habenda est.
For if a thing is not diminished by being shared with others,
it is not rightly owned if it is only owned and not shared.
Book I, Chapter 1 "De doctrina christiana"
"Corpus Christianorum", "Series latina", Vol. 32, p. 6, lines 10-11.
Written 397 AD by Saint Augustinus
>>>>> "David" == David Trudgett <<······@zeta.org.au.nospamplease> > writes:
David> I've been having a bit of a look around for some code to do call
David> graphs given Common Lisp source code input. One of my purposes is to
David> find functions that don't get utilised at all (due to code
David> refactoring, for instance).
[snip]
David> The Lisp I'm using is CMUCL 19a. Editor is GNU Emacs/SLIME. O/S is
CMUCL includes an xref feature. This will produce a call graph, and
since it's in the compiler it should handle macros and such just
fine. It's described in the User manual.
Ray
From: David Trudgett
Subject: Re: Code analysis, call graphs for Common Lisp
Date:
Message-ID: <m3k6mjuxox.fsf@rr.trudgett>
Raymond Toy <···········@ericsson.com> writes:
>
> CMUCL includes an xref feature. This will produce a call graph, and
> since it's in the compiler it should handle macros and such just fine.
> It's described in the User manual.
Thanks, Ray, it looks like it might come in handy. One possible
problem is that it takes into account compiler optimisations that
eliminate code. I suppose turning off the compiler optimisations might
help in that case. Also, it would be nice if it had a recursive
"what-does-it-call?" function in addition to the "who-calls" function!
A couple of other posters have mentioned possibilities that might
work, and hopefully with more portability.
David
--
David Trudgett
http://www.zeta.org.au/~wpower/
It's sociologically interesting, though scary, that you can be inside
an evil system and be somehow unaware of it.
-- Actor Anthony Sher on growing up in apartheid-South Africa,
interviewed by John Walsh, The Independent, 1 May, 2000
David Trudgett <······@zeta.org.au.nospamplease> writes:
> I've been having a bit of a look around for some code to do call
> graphs given Common Lisp source code input. One of my purposes is to
> find functions that don't get utilised at all (due to code
> refactoring, for instance).
>
> I suspect this sort of analysis might be a difficult task for CL
> because of its dynamic nature, macros, and so on and so forth.
>
> I did notice a reference to something in the SBCL profiler that
> outputs a run-time call graph or something. Is that the best deal out
> there? (I don't use or produce closed source software, so it needs to
> be open source [Free Software], although others reading along may be
> interested in non-Free solutions that may be available.)
>
> The Lisp I'm using is CMUCL 19a. Editor is GNU Emacs/SLIME. O/S is
> Debian GNU/Linux and Red Hat Linux.
>
> Thanks for any pointers you can provide!
One thing I recently on this subject is an assignment:
http://www.cs.tufts.edu/g/80/assign/a7.php
80% of the work can be done just from the sources. The remaining
20% are the functions hidden in macros and dynamically called at
macro-expansion time or at run-time.
For source analysis purposes such as when you're refactoring code, It
may be enough to know that function f "calls" macro "m" which "calls"
function "g", it would not matter if at macro-expansion-time or at
run-time.
Otherwise, most of the work in a call-graph analyser is actually the
code walker.
http://www-cgi.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/codewalk/walk/0.html
http://clisp.cons.org/impnotes/code-walk.html
--
__Pascal Bourguignon__ http://www.informatimago.com/
This is a signature virus. Add me to your signature and help me to live
From: David Trudgett
Subject: Re: Code analysis, call graphs for Common Lisp
Date:
Message-ID: <m3oebvuy8i.fsf@rr.trudgett>
Pascal Bourguignon <···@informatimago.com> writes:
>
> One thing I recently on this subject is an assignment:
> http://www.cs.tufts.edu/g/80/assign/a7.php
>
> 80% of the work can be done just from the sources. The remaining
> 20% are the functions hidden in macros and dynamically called at
> macro-expansion time or at run-time.
>
> For source analysis purposes such as when you're refactoring code, It
> may be enough to know that function f "calls" macro "m" which "calls"
> function "g", it would not matter if at macro-expansion-time or at
> run-time.
>
> Otherwise, most of the work in a call-graph analyser is actually the
> code walker.
>
> http://www-cgi.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/codewalk/walk/0.html
>
> http://clisp.cons.org/impnotes/code-walk.html
Thanks for the tips, Pascal. I've bookmarked these references to look
at when I get a chance. Was it you who did something similar for C++
code?
Of course, I'm actually looking for some visualisation as well, and,
having looked into it for my own critical path analysis program (which
I'm working on at the moment), I know that the task is very
non-trivial. There is a whole area of active research into graph
visualisation that I stumbled onto just recently.
Another poster mentioned psgraph.lisp (and xref.lisp), which sounds
very promising! I haven't had a chance to look at it yet, though.
David
--
David Trudgett
http://www.zeta.org.au/~wpower/
You assist an evil system most effectively by obeying its orders and
decrees. An evil system never deserves such allegiance. Allegiance to
it means partaking of the evil. A good person will resist an evil
system with his or her whole soul. -- Mahatma Gandhi
David Trudgett <······@zeta.org.au.nospamplease> writes:
> Thanks for the tips, Pascal. I've bookmarked these references to look
> at when I get a chance. Was it you who did something similar for C++
> code?
In a crude way, yes. It's cxx.lisp:
cvs -z3 -d ··················@cvs.informatimago.com:/usr/local/cvs/public/chrooted-cvs/cvs co common/common-lisp/cxx.lisp
http://www.informatimago.com/develop/lisp/index.html
--
__Pascal Bourguignon__ http://www.informatimago.com/
The world will now reboot. don't bother saving your artefacts.
<······@zeta.org.au.nospamplease> wrote:
> I've been having a bit of a look around for some code to do call
> graphs given Common Lisp source code input. One of my purposes is to
> find functions that don't get utilised at all (due to code
> refactoring, for instance).
[...]
> I did notice a reference to something in the SBCL profiler that
> outputs a run-time call graph or something. Is that the best deal out
> there?
The profiler in question works by taking periodic samples of the
instruction pointer and the stack frames during program execution, so
the results are only approximate. This doesn't matter for profiling,
but makes the call-graphs just about useless for your intended
purpose.
--
Juho Snellman
"Premature profiling is the root of all evil."
One of the utilities by Mark Kantrowitz is called "xref.lisp" and it
does the obvious thing. If you also get psgraph.lisp you will be able
to print postscript versions of the call graphs.
Google for xref and psgraph (together) and you'll find them.
--
Fred Gilham ······@csl.sri.com
"If I'm going to get paged at 3 in the morning, I'd like it to at
least be my fault, and I'd also like a fighting chance of fixing the
problem." -- Tim Moore, arguing for professional open-source tools
From: David Trudgett
Subject: Re: Code analysis, call graphs for Common Lisp
Date:
Message-ID: <m3br7vuvsu.fsf@rr.trudgett>
Fred Gilham <······@snapdragon.csl.sri.com> writes:
> One of the utilities by Mark Kantrowitz is called "xref.lisp" and it
> does the obvious thing. If you also get psgraph.lisp you will be able
> to print postscript versions of the call graphs.
>
> Google for xref and psgraph (together) and you'll find them.
Thanks, Fred! I found the XREF program at:
http://www-cgi.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/tools/xref/0.html
and the psgraph program from:
http://common-lisp.net/project/asdf-packaging/psgraph-latest.tar.gz
(via http://www.cliki.net/psgraph)
Looks like psgraph will do wonders for my critical path analysis
program, which generates a DAG.
David
--
David Trudgett
http://www.zeta.org.au/~wpower/
Only let men cease to be hypocrites, and they would at once see that
this cruel social organization, which holds them in bondage, and is
represented to them as something stable, necessary, and ordained of
God, is already tottering and is only propped up by the falsehood of
hypocrisy, with which we, and others like us, support it.
-- Leo Tolstoy, "The Kingdom of God is Within You"
"David Trudgett" <······@zeta.org.au.nospamplease> wrote
>
> Thanks, Fred! I found the XREF program at:
>
>
http://www-cgi.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/too
ls/xref/0.html
>
> and the psgraph program from:
>
> http://common-lisp.net/project/asdf-packaging/psgraph-latest.tar.gz
>
> (via http://www.cliki.net/psgraph)
>
> Looks like psgraph will do wonders for my critical path analysis
> program, which generates a DAG.
If you want to generate graphs and documents with graphs, you should have a
look at cl-typegraph. It's an extension of cl-typesetting that I wrote
precisely for this kind of application (generating documentation) and it's
much more powerful than psgraph IMBO. You can see an example here:
http://www.fractalconcept.com/fcweb/download/ex.pdf
Marc
From: Eric Marsden
Subject: Re: Code analysis, call graphs for Common Lisp
Date:
Message-ID: <87sm19nux1.fsf@free.fr>
>>>>> "dt" == David Trudgett <<······@zeta.org.au.nospamplease> > writes:
dt> I've been having a bit of a look around for some code to do call
dt> graphs given Common Lisp source code input. One of my purposes is to
dt> find functions that don't get utilised at all (due to code
dt> refactoring, for instance).
dt>
dt> I suspect this sort of analysis might be a difficult task for CL
dt> because of its dynamic nature, macros, and so on and so forth.
I talked about the use of CMUCL's XREF implementation for this kind
of purpose at the 2003 Libre Software Meeting. The slides of the
presentation are at
<URL:http://www.laas.fr/~emarsden/tmp/lsm2003-emarsden.pdf>
The file contrib/stale-symbols.lisp in SBCL's source tree might also
be of marginal interest to you.
<URL:http://cvs.sourceforge.net/viewcvs.py/sbcl/sbcl/contrib/stale-symbols.lisp?rev=1.5&view=auto>
--
Eric Marsden
From: David Trudgett
Subject: Re: Code analysis, call graphs for Common Lisp
Date:
Message-ID: <m3fyx7uwhw.fsf@rr.trudgett>
Eric Marsden <············@free.fr> writes:
>>>>>> "dt" == David Trudgett <<······@zeta.org.au.nospamplease> > writes:
>
> dt> I've been having a bit of a look around for some code to do
> dt> call graphs given Common Lisp source code input. One of my
> dt> purposes is to find functions that don't get utilised at all
> dt> (due to code refactoring, for instance).
> dt>
> dt> I suspect this sort of analysis might be a difficult task for CL
> dt> because of its dynamic nature, macros, and so on and so forth.
>
> I talked about the use of CMUCL's XREF implementation for this kind
> of purpose at the 2003 Libre Software Meeting. The slides of the
> presentation are at
>
> <URL:http://www.laas.fr/~emarsden/tmp/lsm2003-emarsden.pdf>
That's a very interesting presentation, Eric! It certainly shows me
that I can do what I want utilising the XREF facility in CMUCL. Could
you tell me how you created the visualisations? Obviously (I think!),
the XREF facility by itself doesn't do it. It seems to me that I need
to find all fbound symbols in my code, and do a WHO-CALLS or whatever
on each one, and then construct a call graph, and then create a
visualisation of that.
I notice also that you discovered one of the main problems in graph
visualisation: the need to partition large graphs to avoid a useless,
uninterpretable mess! :-)
David
--
David Trudgett
http://www.zeta.org.au/~wpower/
We come here upon what, in a large proportion of cases, forms the
source of the grossest errors of mankind. Men on a lower level of
understanding, when brought into contact with phenomena of a higher
order, instead of making efforts to understand them, to raise
themselves up to the point of view from which they must look at the
subject, judge it from their lower standpoint, and the less they
understand what they are talking about, the more confidently and
unhesitatingly they pass judgment on it.
-- Leo Tolstoy, "The Kingdom of God is Within You"
From: Eric Marsden
Subject: Re: Code analysis, call graphs for Common Lisp
Date:
Message-ID: <87sm14htlp.fsf@free.fr>
>>>>> "dt" == David Trudgett <<······@zeta.org.au.nospamplease> > writes:
dt> That's a very interesting presentation, Eric! It certainly shows me
dt> that I can do what I want utilising the XREF facility in CMUCL. Could
dt> you tell me how you created the visualisations? Obviously (I think!),
dt> the XREF facility by itself doesn't do it. It seems to me that I need
dt> to find all fbound symbols in my code, and do a WHO-CALLS or whatever
dt> on each one, and then construct a call graph, and then create a
dt> visualisation of that.
all the graphs are generated using the dot application, part of the
graphviz suite. The caller graphs are generated by walking the
XREF::*WHO-CALLS* hashtable (this is not a supported interface to
XREF). The package-dependency graphs are generated by looking at all
dependencies between packages (calling functions or macros,
referencing or setting variables, again using internal structures
such as XREF::*WHO-MACROEXPANDS*). I also generated graphs of inter-file
dependencies and of class hierarchies, but I don't think they are in
the presentation.
dt> I notice also that you discovered one of the main problems in graph
dt> visualisation: the need to partition large graphs to avoid a useless,
dt> uninterpretable mess! :-)
indeed, on any real-sized program that is a major problem. I haven't
done anything concrete in this direction, unfortunately.
--
Eric Marsden
David Trudgett <······@zeta.org.au.nospamplease> writes:
> I've been having a bit of a look around for some code to do call
> graphs given Common Lisp source code input. One of my purposes is to
> find functions that don't get utilised at all (due to code
> refactoring, for instance).
Another useful resource may the COVER tool be Richard Waters:
COVER: Common Lisp test case coverage determination tool
ftp://ftp.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/testing/cover/0.html
Some Useful Lisp Algorithms: Part 1
http://www.merl.com/publications/TR1991-004/
Paolo
--
Why Lisp? http://lisp.tech.coop/RtL%20Highlight%20Film
Recommended Common Lisp libraries/tools (see also http://clrfi.alu.org):
- ASDF/ASDF-INSTALL: system building/installation
- CL-PPCRE: regular expressions
- UFFI: Foreign Function Interface