[Caml-list] generating a call-graph

[Caml-list] generating a call-graph

[Yaron M. Minsky]

Does anyone know a way of generating a call-graph from a set of ocaml
sources?  What I want to do is, at a minimum, get a list of all the
functions that could be called as a result of a given function invocation.
 Essentially, I'm looking for dependency information on the function-call
level, similar to what ocamldep provides on the module level.

y

-- 
|--------/            Yaron M. Minsky              \--------|
|--------\ http://www.cs.cornell.edu/home/yminsky/ /--------|

Open PGP --- KeyID B1FFD916 (new key as of Dec 4th)
Fingerprint: 5BF6 83E1 0CE3 1043 95D8 F8D5 9F12 B3A9 B1FF D916



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] generating a call-graph

[Jeff Henrikson]

> Does anyone know a way of generating a call-graph from a set of ocaml
> sources?  What I want to do is, at a minimum, get a list of all the
> functions that could be called as a result of a given function 
> invocation.
>  Essentially, I'm looking for dependency information on the 
> function-call
> level, similar to what ocamldep provides on the module level.

I have a tree walker function generator for caml expressions in camlp4 
that would make short work of this.  But I don't know how to get an 
MLast datum for an entire file.  Anybody know how to do this?  It seems 
that MLast.The following does not work:

Grammar.Entry.parse str_item (Stream.of_string
   "let f x = x*x;; let g x = x+x;;");;

(It stops at the semicolon and returns just the f definition.)


Jeff Henrikson


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] generating a call-graph

[Xavier Leroy]

> Does anyone know a way of generating a call-graph from a set of ocaml
> sources?  What I want to do is, at a minimum, get a list of all the
> functions that could be called as a result of a given function invocation.

This requires a non-trivial static analysis called "control flow
analysis" in the literature; particular instances include Shivers'
0-CFA and k-CFA, Jagannathan and Wright's "polymorphic splitting",
etc.

The difficulty is that functions are first-class values, so the
function you're applying can be a parameter to another function, or a
member of a data structure.  (Objects raise similar issues.)
Thus, the control flow cannot be determined independently of the data
flow, and "control flow analysis" is really a data flow analysis that
tracks the flow of functional values.

I don't know of any implementation of control-flow analysis for the
whole OCaml language.

- Xavier Leroy

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] generating a call-graph

[John Max Skaller]

Xavier Leroy wrote:

>>Does anyone know a way of generating a call-graph from a set of ocaml
>>sources?  What I want to do is, at a minimum, get a list of all the
>>functions that could be called as a result of a given function invocation.
>>
> 
> This requires a non-trivial static analysis called "control flow
> analysis" in the literature; particular instances include Shivers'
> 0-CFA and k-CFA, Jagannathan and Wright's "polymorphic splitting",
> etc.
> 
> The difficulty is that functions are first-class values

.. and the difficulty can be bypassed by considering
the actual industrial requirement, which probably
isn't as stated above.

We often want to know what the definition
of a function depends on, and that clearly *excludes*
any functions passed in as parameters.

Second, an incomplete graph would still be very useful.
For example to determine if you can move a function
definition earlier in the code, so as to call it from
some other function -- or whether you would have to move
a lot more functions back -- and if so which ones --
and, indeed, if it is possible at all (without recursion).

I guess a patch to the parser could gather the required
information easily ( the main difficulty being
the huge number of anonymous functions that tend to
float around when one does currying).

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] generating a call-graph

[Jeff Henrikson]

> Does anyone know a way of generating a call-graph from a set of ocaml
> sources?  What I want to do is, at a minimum, get a list of all the
> functions that could be called as a result of a given function 
> invocation.
>  Essentially, I'm looking for dependency information on the 
> function-call
> level, similar to what ocamldep provides on the module level.

Xavier Leroy points out something more complicated than I was thinking. 
  What I was going to do was, for each function f with a definition in 
the top environment, generate the list of all other such functions 
lexically bound inside f.  Maybe add a hack for non-functor modules or 
something.  So that throws out all anonymous functions and lots more.  
It's not really about call path.  I was presuming it was for assisting 
visual code inspection.

What is it for in reality?


Jeff



On Friday, May 23, 2003, at 12:34 PM, Yaron M. Minsky wrote:

> Does anyone know a way of generating a call-graph from a set of ocaml
> sources?  What I want to do is, at a minimum, get a list of all the
> functions that could be called as a result of a given function 
> invocation.
>  Essentially, I'm looking for dependency information on the 
> function-call
> level, similar to what ocamldep provides on the module level.
>
> y
>
> -- 
> |--------/            Yaron M. Minsky              \--------|
> |--------\ http://www.cs.cornell.edu/home/yminsky/ /--------|
>
> Open PGP --- KeyID B1FFD916 (new key as of Dec 4th)
> Fingerprint: 5BF6 83E1 0CE3 1043 95D8 F8D5 9F12 B3A9 B1FF D916
>
>
>
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr Archives: 
> http://caml.inria.fr
> Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: 
> http://caml.inria.fr/FAQ/
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners