A Glasgow Haskell Compiler fordítási folyamata
A GHC napjaink legelterjedtebb és legkifinomultabb Haskell fordítója, ezért a Haskell programok fordítási folyamatát itt vizsgáljuk.
A GHC struktúrája
A GHC három főbb komponensre osztható:
- A fordító: Haskellben írva, aminek feladata a Haskell forráskód átírása gépi kóddá.
- A Boot könyvtárak: Ezek azok a könyvtárak amitől a fordító függ. Mivel ezek a könyvtárak a GHC forrásában vannak, az le tudja fordítani saját magát. Ezen könyvtárak némelyike nagyon szorosan kötődik a GHC-hoz, mert alacsonyszintű működést implementálnak mint például az Int típust. Más könyvtárak magasabb szintűek, és fordító függetlenek, mint például a Data.Map könyvtár.
- A Futtatórendszer (Runtime System, RTS): Ez egy nagy, C nyelven íródott programkönyvtár, ami a lefordított Haskell kód futtatásával kapcsolatos feladatokat látja el, mint a szemétgyűjtést, szálütemezést, kivételkezelést, stb. Az RTS minden Haskell programmal linkelve van.
A fordító felépítése
- A fordításkezelő (compilation manager): Ez felelős több Haskell forrásfájl együttes fordításáért. A feladata, hogy kitalálja, milyen sorrendben kell lefordítani a megfelelő fájlokat, és hogy eldöntse melyik fájlokat nem szükséges újrafordítani, mert nem változtak meg a függőségei az utolsó fordítás óta.
- A Haskell fordító: Ez felelős egyetlen Haskell fájl lefordításáért, a legtöbb munka itt történik. A kimenete a választott backendtől függ: assembly, LLVM kód vagy bájtkód.
- A csővezeték (pipeline): Ami felelős külső programok meghívásáért, amik szükségesek a Haskell forrásfájlok objektumfájlokká fordításában. Például egy Haskell forrásfájlt lehet, hogy előbb át kell küldeni a C preprocesszoron mielőtt megkapja a Haskell fordító, aztán pedig ennek assembly kimenetét tovább kell adni egy assemblernek, hogy megkapjuk a végleges objektumfájlokat.
A fordítási folyamat
Szintaktikus elemző
Ebben a lépésben a Haskell forrásfájl átalakul absztrakt szintaxisfává, amiven az azonosítók egyszerű karakterláncok. A GHC az Alex és Happy eszközöket használja a lexikális elemzéshez és a kód szintaktikus elemzéséhez, amik megfelelnek a lex és yacc eszközöknek C-ben.
A GHC szintaktikus elemzője tisztán funkcionális, sőt, a GHC könyvtár API-ja biztosít egy parser nevű függvényt, ami egy Stringet és néhány egyéb paramétert vár, és visszaad egy absztrakt szintaxisfát vagy egy hibaüzenetet.
Átnevezés
Az átnevezés során minden Haskell forráskódbeli azonosítót felold teljesen minősített nevekké, és egyidőben azonosít minden szkópon kívül eső azonosítót, és megfelelően jelzi ezeket a hibákat.
A nevek feloldása az átnevező fő feladata, de számtalan más feladatot is ellát: összegyűjti függvények egyenleteit, és jelzi a hibákat, ha eltérő számú argumentumaik vannak; átrendezi az infix operátorokat a kötési irányuknak megfelelően; megkeresi a többszörös deklarációkat; hibákat generál a használatlan azonosítókhoz, és így tovább.
Típusellenőzés
A típusellenőrzés során dől el, hogy a Haskell program típushelyes-e. Ha a program átmegy a típusellenőrzőn, garantáltan nem fog lefagyni futási időben. (A "lefagyásnak" itt létezik egy formális definíciója, ami tartalmazza például a szegmentációs hibákat, de a mintaillesztést nem. A nem-lefagyási garancia megkerülhető bizonyos nem biztonságos nyelvi eszközök használatával, mint például a Foreign Funcion Interface.)
A gyakorlatban az átnevezés a és a típusellenőrzés összefésülhető, mert a Template Haskell futási időben generál kódot, amit szintén át kell futtatni az átnevezőn és a típusellenőrzőn.
A szintaktikai cukor eltávolítása (desugaring) és a Core nyelv
A Haskell egy igen nagy nyelv, sok különböző szintaktikai alakkal. Több módon is leírhatjuk ugyanazt a kódot, például egy if kifejezés jelentésében megegyezik egy case kifejezéssel aminek True és False ágai vannak, és a halmazkifejezések is átírhatók a map, filter és concat függvények hívásaivá. Sőt mi több, a Haskell nyelv a magasabbszintű nyelvi elemeket egyszerűbb nyelvi elemekre alakítással definiálja. Az ilyen átírható kifejezéseket "szintaktikai cukornak" hívjuk.
A desugaring eltávolítja az összes szintaktikai cukrot, és a Haskell kódot Core nyelvre alakítja. A Core nyelv egy köztes nyelv, a Haskell egy résznyelve, ami az Fc típusozott lambdakalkuloson alapszik.
Fc típusozott lambdakalkulus
A Haskell eredetileg az F rendszert használta a Core alapjául, de az Általánosított Absztrakt Adattípusok (GADT) bevezetése miatt problémák merültek fel az implementációban; az F rendszer nem volt elég erős ezek hatékony kezeléséhez. Az Fc rendszer az F rendszert egészíti ki típusegyenlőség-kényszerítéssel. A bevezetett típuskonverziós kényszerítések fordítási időben generálódnak, és a fordítás végére eltávolítódnak a kódból, ezért nem járnak futásidejű költséggel.Optimalizálás
Az optimalizálás a program Core nyelvű formáján hajtódik végre. A Core egy kis funkcionális nyelv, de hihetetlenül rugalmas médium az optimalizálások kifejezéséhez.
A Core nyelvi reprezentáción átalakításokat végez a fordító, ezek a következő két kategóriába esnek:
-
Sok egyszerű, helyi átalakítás
Ezek az átalakítások hatékonysági okokból egyetlen fordítási menetben hajtódnak végre (simplifier). Mivel ezeknek az átalakításoknak az eredményeként újabb átalakítási lehetőségek adódhatnak, ez a menet többször végrehajtódik, amíg csak történik átalakítás, vagy el nem éri a maximális átalakítási menetek számát.
Ilyen átalakítás az inlining, vagyis a függvényhívás belyehettesítése a hívott függvény törzsével. Funkcionális nyelvek esetén 20-40%-os teljesítményjavulást hoz. Az inlining nemcsak a függvényhívás költségét spórolja meg, mert a behelyettesített függvény újabb átalakítási lehetőségeket hozhat.
Nem csak függvényhívásokat, de minden let kifejezést potenciálisan inlineosíthatunk. -
Kevés bonyolult, globális átalakítás (pl.: strictness analysis, túlterhelt függvények specializálása)
Ezen átalakítások mindegyike külön menetben történik. Legtöbbjük elemzési fázissal kezdődik, amit egy átalakítási fázis követ, ami felhasználja az elemzési fázis eredményeit. Többjük egy őket követő simplifier menetre is számít, ami megtisztítja az általuk generált kódot.
Kódgenerálás
Miután a Core programot kellően optimalizálta a fordító, elkezdődik a kódgenerálás folyamata. Néhány adminisztratív futam után a kóddal két dolog történhet: vagy bájtkóddá fordul, amit az interaktív interpreter futtat, vagy átadódik a kódgenerátornak, hogy végül gépi kóddá alakuljon.
A kódgenerátor először átalakítja a Core nyelvet STG nyelvre, ami lényegében olyan mint a Core nyelv, csak több, a kódgenerátor számára szükséges információval van annotálva. Ezután az STG kód C-- nyelvre fordul, ami egy alacsonyszintű imperatív nyelv.
Ezután az alábbi három kódgenerációs folyamat egyike hajtódik végre:
- Natív kód generálása: A GHC-ben vannak egyszerű natív kód generátorok néhány processzorarchitektúrához. Ez az út gyors és elfogadható kódot generál a legtöbb esetben.
- LLVM kódgenerálás: A C-- kód LLVM kóddá fordul, és átadódik az LLVM forító számára. Ez az út lényegesen jobb kódot generál néhány esetben, habár tovább tart mint a natív kódgenerátor.
- C kódgenerátor: A GHC képes rendes C kód generálására is. Ez az út lényegesen lassabb kódot generál mint az első két út, de hasznos lehet a GHC új platformokra portolásában.