Bachelorarbeit (abgeschlossen): corediff: Diff-Tool für GHC Core Programme

Compiler-Entwickler vergleichen oft die Zwischenrepräsentationen zweier verschiedene Versionen des gleichen Programms (falsch übersetzte vs. letzte funktionierende Version, schnelle vs. langsame Version). Im Fall vom GHC liegen die Programme in Core IR vor, die vor allem textuell inspiziert wird. Beispiel:


-- Alt

-- RHS size: {terms: 5, types: 14, coercions: 0, joins: 0/0}
flags :: Options -> X
[GblId[[RecSel]],
 Arity=1,
 Caf=NoCafRefs,
 Str=m,
 Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True,
         WorkFree=True, Expandable=True,
         Guidance=ALWAYS_IF(arity=1,unsat_ok=True,boring_ok=True)
         Tmpl= \ (ds_dNe [Occ=Once!] :: Options) ->
                 case ds_dNe of
                 { Options ds1_dNf [Occ=Once] _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead]
                           _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead]
                           _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead] ->
                 ds1_dNf
                 }}]
flags
  = \ (ds_dNe :: Options) ->
      case ds_dNe of
      { Options ds1_dNf ds2_dNg ds3_dNh ds4_dNi ds5_dNj ds6_dNk ds7_dNl
                ds8_dNm ds9_dNn ds10_dNo ds11_dNp ds12_dNq ->
      ds1_dNf
      }


-- Neu

-- RHS size: {terms: 5, types: 14, coercions: 0, joins: 0/0}
flags :: Options -> X
[GblId[[RecSel]],
 Arity=1,
 Caf=NoCafRefs,
 Str=,
 Cpr=m,
 Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True,
         WorkFree=True, Expandable=True,
         Guidance=ALWAYS_IF(arity=1,unsat_ok=True,boring_ok=True)
         Tmpl= \ (ds_dNw [Occ=Once!] :: Options) ->
                 case ds_dNw of
                 { Options ds1_dNx [Occ=Once] _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead]
                           _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead]
                           _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead] ->
                 ds1_dNx
                 }}]
flags
  = \ (ds_dNw :: Options) ->
      case ds_dNw of
      { Options ds1_dNx ds2_dNy ds3_dNz ds4_dNA ds5_dNB ds6_dNC ds7_dND
                ds8_dNE ds9_dNF ds10_dNG ds11_dNH ds12_dNI ->
      ds1_dNx
      }

Was ist der Unterschied zwischen beiden Programmen? Ein textueller Diff schafft Abhilfe:


--- new.log     2020-01-23 18:16:26.441312390 +0100
+++ alt.log     2020-01-23 18:16:36.317314562 +0100
@@ -1,26 +1,25 @@
--- Neu
+-- Alt

 -- RHS size: {terms: 5, types: 14, coercions: 0, joins: 0/0}
 flags :: Options -> X
 [GblId[[RecSel]],
  Arity=1,
  Caf=NoCafRefs,
- Str=,
- Cpr=m,
+ Str=m,
  Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True,
          WorkFree=True, Expandable=True,
          Guidance=ALWAYS_IF(arity=1,unsat_ok=True,boring_ok=True)
-         Tmpl= \ (ds_dNw [Occ=Once!] :: Options) ->
-                 case ds_dNw of
-                 { Options ds1_dNx [Occ=Once] _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead]
+         Tmpl= \ (ds_dNe [Occ=Once!] :: Options) ->
+                 case ds_dNe of
+                 { Options ds1_dNf [Occ=Once] _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead]
                            _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead]
                            _ [Occ=Dead] _ [Occ=Dead] _ [Occ=Dead] ->
-                 ds1_dNx
+                 ds1_dNf
                  }}]
 flags
-  = \ (ds_dNw :: Options) ->
-      case ds_dNw of
-      { Options ds1_dNx ds2_dNy ds3_dNz ds4_dNA ds5_dNB ds6_dNC ds7_dND
-                ds8_dNE ds9_dNF ds10_dNG ds11_dNH ds12_dNI ->
-      ds1_dNx
+  = \ (ds_dNe :: Options) ->
+      case ds_dNe of
+      { Options ds1_dNf ds2_dNg ds3_dNh ds4_dNi ds5_dNj ds6_dNk ds7_dNl
+                ds8_dNm ds9_dNn ds10_dNo ds11_dNp ds12_dNq ->
+      ds1_dNf
       }

Aber das enthält immer noch viel falsch-positive Information. Im vorliegenden Beispiel stören die leicht anderen, expliziten Namen der gebundenen Variablen, die es schwer machen, Alphaäquivalenz festzustellen. Aber auch kleinere Unterschiede in der textuellen Repräsentation, wie andere Einrückung oder Zeilenumbrüche, sorgen für lästige Ablenkung.

Der einzige Unterschied zwischen beiden Funktionen besteht tatsächlich nur in der Art und Weise, wie Analyseinformation formatiert wird.

Aufgabe:

In dieser Arbeit soll ein strukturelles Diff-Tool für GHC Core entstehen, das auch gleiche Terme modulo Alphaäquivalenz identifiziert und möglichst minimale Diffs produziert, eventuell sogar minimale Patches. In dieser Hinsicht dürfte ein Ansatz wie in An efficient algorithm for type-safe structural diffing interessant sein. Für Alphaäquivalenz kann die Theorie aus Nominal Unification hilfreich sein.

Voraussetzungen

Gute Haskell-Kenntnisse

Schlüsselworte

Haskell, Compiler

Veröffentlichungen

Veröffentlichung

Structural Diffing for GHC Core Programs

Betreuer

Wissenschaftliche Mitarbeiter
Sebastian Graf

Studenten

Ehemalige Tutoren
Paul Brinkmeier