Adat és kiértékelési függőségi elemzés funkcionális nyelvekre - Erlang programok statikus elemzése

Tóth, Melinda

Adat és kiértékelési függőségi elemzés funkcionális nyelvekre - Erlang programok statikus elemzése

Date: 2018

Subject: Műszaki tudományok/Informatikai tudományok
Erlang
static analysis
data flow analysis
data flow graph
data flow reaching
zeroth-order analysis
first-order analysis
data dependence analysis
behaviour dependence graph
behaviour dependence
data dependence
pattern discovery
algorithmic skeleton introduction
farm-like computation
Informatika D. I./Az informatika alapjai és módszerei.
Erlang
statikus elemzés
adatfolyam elemzés
adatfolyam-gráf
adatfolyam reláció
nulladrendű adatfolyam elemzés
elsőrendű adatfolyam elemzés
adatfüggőség elemzés
viselkedésfüggőség-gráf
viselkedésfüggőség
adatfüggőség
mintafelismerés
farm-jellegű számítások

URI: http://hdl.handle.net/10831/40597

Link to Library Catalogue: https://opac.elte.hu/Record/opac-EUL01-961786

MTMT: 30548278

DOI: 10.15476/ELTE.2018.171

Abstract:

A szoftverfejlesztést támogató eszközök jelentősége rohamosan nő az utóbbi évtizedekben. A forráskódok mérete akkorára nő, hogy humán erővel átlátni szinte lehetetlen, de legalábbis nehézkes és időigényes folyamat. Így egyre inkább elterjednek azok az eszközök, melyek a kód megértést, karbantartást, hibakeresést támogatnak vagy éppen lehetőséget nyújtanak a forráskód különböző szempontok szerinti refaktorálására. Ez a támogatás történhet dinamikusan, azaz futási időben, illetve statikusan, azaz fordı́tási időben. Előbbi esetben a már futó szoftver monitorozásával, esetlegesen a kód instrumentálásával nyerhetünk ki információt és segı́thetjük ezzel a fejlesztőket. Utóbbi esetben viszont nincs szükség a szoftver futtatására, csupán a forráskód alapján gyűjtünk információt és használjuk fel különböző célokra. Dolgozatomban ez utóbbi módszerrel, a forráskódok statikus elemzésével foglalkoztam, Erlang nyelvhez.

Definiáltam Erlang programok elsőrendű adatfolyam-gráfját, és az ezen a gráfon értelmezett elsőrendű adatfolyam relációt. A RefactorErl keretrendszer alap eszközkészletéhez igazı́tva megadtam az ehhez tartozó algoritmusokat. Erlang programok adatfolyam-gráfját ı́gy inkrementálisan fel tudjuk épı́teni a forráskódok változásának figyelembe vételével. A adatfolyam reláció segı́tségével pedig választ kaphatunk olyan kérdésekre, hogy mi lehet a program egy adott pontján lévő kifejezésének az értéke, illetve hogy egy adott érték milyen programpontokra juthat el. A reláció interprocedurálisan számı́tható és figyelembe veszi a hı́vási kontextust. Az adatfolyam relációt felhasználásával megadtam, hogyan számı́tható ki az aszinkron üzenetküldések és -fogadások közötti közvetlen adatfolyam.

Definiáltam Erlang programokon értelmezett adatfüggőség relációt, mely az adatfolyam-gráf kiterjesztésén a viselkedésfüggőség gráfon számı́tható ki. A függőségi reláció megadja, hogy két Erlang programbeli kifejezés között van-e függés, azaz kiértékelésük függ-e egymástól. A RefactorErl keretrendszerhez kidolgozott algoritmusok felhasználásra kerültek olyan problémák megoldásában mint a releváns tesztesek kiválasztása, vagy párhuzamosı́tható komponensek függőségi kapcsolatainak az ellenőrzése.

Az adatfolyam, adatfüggőség és egyéb statikus elemzések felhasználásával kidolgoztam különböző jól párhuzamosı́tható számı́tási modellek viselkedésének leı́rását, mint például az elemenkénti feldolgozás. A megadott szabályok alapján a RefactorErl keretrendszerben megadhatók azok a mintafelismerési algoritmusok, melyek segı́tségével azonosı́thatóak azok a szekvenciális kódrészletek, melyek lecserélhetőek egy ekvivalens párhuzamos végrehajtásra.

Abstract:

The importance of the tools to support software development is increasing. The size of the software products makes manual scanning for certain information almost impossible, or time consuming. Therefore tools to support code comprehension, development, maintenance, debugging, or even automatic source code transformation are really desired. We can distinguish dynamic and static tools. The former analyses the software at runtime by monitoring, instrumenting the code. The latter analyses the source code itself without executing the program. In my thesis I have developed new static analyses methods for the Erlang programming language to support code comprehension and further static analyses. I have defined the first order data flow graph for Erlang programs, and the data flow relation among the nodes of the graph, the first order data flow reaching. The reaching relation itself is able to identify the possible values of an expression at some point in the program. It also identifies the expressions where a certain value may flow. Based on the definitions I have introduced the data flow graph building and reaching calculation algorithms using the RefactorErl framework. The data flow graph building algorithm is incremental, therefore the changes of the source code can be handled without reanalysing the whole software. The data flow reaching algorithm is interprocedural and aware of function call context. Using data flow reaching I have defined the direct data flow among asynchronous message sending and receiving expressions. I have defined a data dependence relation among Erlang expressions based on the behaviour dependence graph that is an extension of the data flow graph. The dependence relation defines whether two expressions from the Erlang source code depends on each other. The corresponding algorithms have been defined in the framework of RefactorErl, and have been used in further static analyses, namely in change impact analysis and pattern discovery. I have defined the behaviour of parallelisable computations, such as the elementwise processing. The definitions use the studied data flow, data dependence relations and other static analysis methods, such as control flow graphs and execution paths. Using the definitions we can identify sequential code fragments that can be replaced with parallel equivalents. The pattern discovery algorithms have been defined in the RefactorErl framework.

Show full item record