Re: query that Bob is descendant of Alice

In article <3ae4af72.9673488_at_news.nextra.sk>, Robert Vazan <robova_at_nextra.sk> wrote:
>nmm1_at_cus.cam.ac.uk (Nick Maclaren) wrote:
>>More seriously, the question of whether A can call B is insoluble in
>>general. For languages without the concept of a function address
>>variable (e.g. Fortran 77 and not C), it is trivial to produce a
>>generally useful bound. Whether SQL is the way to analyse such data
>>is beyond my knowledge ....
>
>Trivial? T-r-i-v-i-a-l ? Can you please, please, send it to
>NG? Maybe you are not talking about solution, only bound.
>But then, practical?

Yes. PFORT did it round about 1970. A few years later, I wrote an efficient program that I used for creating overlays - such as getting getting 512 KB of Minitab code down to 28 KB to run interactively on a 4 MB MVT system ....

The key for languages like Fortran is that the graph is typically acyclic, or nearly so, and routine arguments can be passed down to called routines but neither stored nor returned back up. This is NOT true for C, and programming styles like the ineffable X Windowing System are effectively unanalysable.

All you do is to complete the graph. This can be done using links, but it is typically most efficient using Warshall's method on a bit matrix. With care, you can use vectorised bit operations on complete words, and it runs like the clappers. I was analysing programs with 1,000 routines in the 1970s and not using much in the way of resources.

Note that this gives a bound, as there may be call paths that are impossible for reasons beyond the simple model. In practice, in languages like Fortran, they are rare. In some others, they are not.

Regards,
Nick Maclaren,
University of Cambridge Computing Service, New Museums Site, Pembroke Street, Cambridge CB2 3QG, England. Email: nmm1_at_cam.ac.uk
Tel.: +44 1223 334761 Fax: +44 1223 334679 Received on Tue Apr 24 2001 - 22:03:21 CEST