|Title||:||The Approximations Vs. Abstractions Dilemma in Pointer Analysis|
|Speaker||:||Uday Khedkar (IIT Bombay)|
|Details||:||Tue, 30 Aug, 2016 4:00 PM @ BSB 361|
|Abstract:||:||The world of programming is divided in religious camps with opposing
views on the use of pointers. The verification community as well as
HPC community abors pointers while the hackers adore them. Compiler
writers love the convenience that pointers provide to build fancy data
structures but hate the difficulties that arise in trying to optimize a
program containing pointers.
There has been a lot of work on analyzing programs containing pointers. The mathematics of pointer analysis has been studied in great details and the findings conclusively say that like many other interesting problems, the analysis of pointers in its full glory is undecidable and remains intractable even if some imprecision were to be tolerated. Given the vital importance of pointer analysis and the inherent difficulty of performing precise pointer analysis for practical programs, a large fraction of pointer analysis community has come to believe that compromising on precision is necessary for scalability and efficiency. This is evidenced by the fact that a large number of reported investigations in pointer analysis involve a significant amount of engineering approximations.
We find it hard to accept this assumption as the final inevitability. We believe that a lot could be gained by exploring a science of pointer analysis that tries to build clean abstractions rather than hasty approximations. In our opinion, this is a road less travelled in pointer analysis. Without undermining the engineering efforts, we propose that a search for approximations should begin only after building clean abstractions and not before it. The talk describes our efforts in this direction.