Låg nivå programanalys är ett grundläggande problem, tar formen av "flödesanalys" i funktionella språk och "points-to" analys i tvingande och objektorienterade språk. Trots likheterna är vokabulären och resultaten i de två samhällena fortfarande i stort sett distinkta, med begränsad korsförståelse. En av de få länkarna är Shivers k-CFA-arbete, som har avancerat begreppet "kontextkänslig analys" och är allmänt känt i båda samhällena. De senaste resultaten visar att förhållandet mellan k-CFA:s funktionella och objektorienterade inkarnationer inte är lika välbegripet som tanken. Van Horn och Mairson visade k-CFA för k ≥ 1 för att vara EXPTIM-komplett; därför kan ingen polynom-tid algoritm existera. Ändå finns det flera polynom-tid formuleringar av sammanhangskänsliga poäng-till analyser i objektorienterade språk. Det verkar alltså som om funktionell k-CFA faktiskt kan vara en helt annan analys än objektorienterad k-CFA. Vi löser denna paradox genom att visa att exakt samma specifikation av k-CFA är polynom-tid för objektorienterade språk men exponentiellt tid för funktionella sådana: objekt och stängningar är subtilt olika, på ett sätt som interagerar avgörande med kontextkänslighet och komplexitet. Denna belysning leder till en omedelbar vinst: genom att projicera objektorienterad behandling av objekt på stängningar, vi härleda en polynom-tid hierarki av sammanhangskänsliga CFAs för funktionella program. 1 Även om k-CFA-arbetet ofta används som synonym för "k-kontextkänslig" i OO-världen, är k-CFA mer korrekt en algoritm som paketerar sammanhangskänslighet tillsammans med flera andra designbeslut. I terminologin för OO-punkter-till-analys är k-CFA en k-call-plats-känslig, fält-känsliga punkter-till-analysalgoritm med en kontextkänslig hög och med on-the-fly call-graph konstruktion. (Lhoták [9] och Lhoták och Hendren [10] är goda referenser för klassificering av punkt-till-analysalgoritmer.) I detta dokument använder vi termen "k-CFA" med denna mer exakta betydelse, vilket är vanligt i den funktionella programmeringsvärlden, och inte bara som en synonym för "k-context-känslig". Även om denna klassificering är mer exakt, tillåter den fortfarande en rad algoritmer, som vi diskuterar senare.
Verk av Might, Smaragdakis och Van Horn REF diskuterar förhållandet mellan statisk analys av högre ordning funktioner och objekt.
Resolving and exploiting the k-CFA paradox: illuminating functional vs. object-oriented program analysis
{'venue': "PLDI '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}