The case for compositional type checking

This is an based on a chapter of the M.Sc. thesis I am writing at ELTE, supervised by Péter Diviánszky.

For my M.Sc. thesis, I've been working on writing a compositional type checker for Haskell 98. The basic idea is to extend Olaf Chitil's compositional type system with ad-hoc polymorphism, Haskell 98's major extension to the Hindley-Milner type system. In this post, I'm showing the motivation behind wanting to go compositional.

A property shared by both commonly-used algorithms for doing Hindley-Milner type inference, W and M, is that both W and M infer the type of composite expressions by inferring one subexpression (in some sense, the “first” one) and using its results in inferring the type of the “next” one. They are linear in the sense that partial results are threaded throughout the type inference.

The effect of linearity on type inference is that certain sub-expressions (those that are processed earlier) can have greater influence on the typing of other subexpressions. This is bad because it imposes a hierarchy on the subexpressions that is determined solely by the actual type checking algorithm, not by the type system; thus, it can lead to misleading error messages for the programmer.

For example, let's take the following definition of a Haskell function:

There are two ways to typecheck this definition using W: either we first typecheck toUpper x, using the context {x :: α}, resulting in the type equation α ~ Char, then checking not x with {x :: Char}, or do it the other way around, by first looking at not x, then as a result recursing into toUpper x with the context {x :: Bool}.

GHC, it seems, does the former, resulting in the following error message:

Whereas Hugs 98 does the latter:

The problem is that they are both misleading, because there is nothing wrong with either not x or toUpper x by itself. The problem only comes from trying to unify their respective views on the type of x.

A compositional type checker, in contrast, descends into toUpper x and not x using the same context, {x :: α}. The first one results in the typing (which is defined to be not just the type of an expression, but also a mapping of monomorphic variables to their types) {x :: Char} ⊢ Char, and the second one in {x :: Bool} ⊢ Bool. Only afterwards are these two typings tried to be unified.

This is better because it becomes meaningful to talk about the typing of a subexpression. For the example above, my work-in-progress compositional type checker can report errors with an (IMO) much more helpful message:

Of course, the devil's in the details — but that's what my thesis will be about.

Neked aztán lehet

Ezt Viki mesélte, de szerintem érdemes ide is.

Az az alaphelyzet, hogy a suli mellett az ELTÉn dolgozik operátorként. Keveset operál, annál többet kell segítenie random ELTÉs oktatóknak akiknek "nem megy a levelezés". Szóval endless fun. Most viszont becsúszott egy jó sztori.

Bölcsészmérnök felhívja telefonon az operátori szolgálatot valami fájással, mondják neki hogy azonosítás végett küldjön egy levelet a benti címéről (ugyanis az SMTP autentikált). Persze, hogy leírja a levélben a jelszavát is. Válaszolnak neki hogy jó, akkor most mielőtt bármi egyéb történik, letiltották a jelszavát mert kiadta, itt meg itt tud ETR-en keresztül újat választani (remélhetőleg az ETR-es hozzáférését még nem adta ki senkinek).

Mivel ez már bőven túl bonyolult volt neki (amúgy én azt is el tudom képzelni, hogy azt hitte, szivatásból tiltották le), bement személyesen az irodába. Ott Viki elmondta neki az alábbi 3 (három) információt:

• Ne legyen a jelszóban ékezetes betű
• Nem praktikus, ha van benne y vagy z betű
• Soha senkinek, az operátori szolgálatnak se adja ki a jelszavát. Sosenem.

Különösebben hosszú gondolkodási idő nélkül vágta erre rá az alábbi, azóta nálunk szállóigévé vált mondatot:

Akkor lehet a jelszavam az, hogy "prüntyőke"?

Grand Slam

A mai analízis 8 vizsgával meglett a royal flush: mind a nyolc kollokvium, és (még anno, két éve) a szigorlat is jeles lett.

Gondolom, a kommentek között mindjárt feltűnik még száz ember, aki a progmaton ugyanezt megcsinálta, de szarok rá, én ma ennek örülök. Egyébként is egy állati izgalmas ride volt ez a négy év a matematika egy szeletének felépítményén át. Megérte! És sok más tantárggyal és előadóval ellentétben, az előadások 90+ százaléka izgalmas és érdekes volt nemcsak utólag, hanem akkor és ott ülve is.

Relativisztikus hiperszámítógépek

Tegnap egy nagyon érdekes előadáson vettem részt, ahol Németi István és team-je ismertette a hiperszámítás megvalósíthatóságának vizsgálata terén elért eredményeit.

A hiperszámítás olyan teoretikus kiszámítási modellekkel foglalkozik, amelyek kvalitatíven erősebbek a Turing-gépeknél (pl. meg tudják oldani a Turing-gépek megállási problémáját, vagy akár Gödel nemteljességi tételén is túl tudnak lépni. Németiék az általános relativitáselmélet eredményeit felhasználva konstruáltak egy olyan hipotetikus rendszert, amely a programozó, mint megfigyelő szempontjából nézve véges idő alatt képes végtelen sok számítást elvégezni. Mint többször hangsúlyozták az előadás alatt, a javaslatukról azt nem állítják, hogy megvalósító, de jelenleg ismert fizikai ismereteink szerint semmi nem zárja ki a megvalósíthatóságát.

Az alapötletük az, hogy a programozó egy számítógép felprogramozása után egy alkalmasan megválasztott pályán beleesik egy forgó fekete lyukba. "Kívülről" nézve a programozó az eseményhorizonton átesve "megfagy", órája végtelenül lelassul. "Belülről", a programozó szemszögéből viszont ennek a duálisa történik: a számítógép órája egyre gyorsul. Ennek eredményeképpen azalatt a (programozó számára) véges idő alatt, amíg átesik az eseményhorizonton, a számítógép számára végtelen idő telik el, ezért aztán bármilyen (nem korlátos) számítás eredményét megkaphatja. Ez azt jelenti, hogy pl. a ZFC konzisztenciáját megvizsgálhatjuk úgy, hogy az összes lehetséges (nyilván megszámlálhatóan végtelen számú) tételt egyenként vizsgáljuk, és az első inkonzisztencia megtalálásakor elindítunk egy űrhajót a programozó után. Ha a programozó nem találkozik az utánaküldött űrhajóssal azalatt a (számára véges!) idő alatt, amíg átesik az eseményhorizonton, akkor az azt jelenti, hogy a végtelen idő alatt (vagyis az összes lehetséges tétel vizsgálata során) nem találtunk ellentmondást, vagyis a ZFC konzisztens.

Nyilván az elmélet működéséhez egy csomó peremfeltételnek teljesülnie kell – kezdve például azzal, hogy végtelen időre (és a számítás energiaigénye miatt végtelen anyagra) van szükség, vagyis ha a világegyetem jövője egy Nagy zutty jellegű összezuhanást tartogatna, akkor a módszer nem működne – de a legújabb mérések azt mutatják, hogy a világegyetem folyamatosan tágul.

Mivel nem vagyok fizikus, a fenti, konyhanyelvű magyarázatban természetesen meg sem próbáltam kitérni azokra a problémákra, amiket például az jelent, hogy a programozó túlélje az utazást, vagy hogy az eredményekkel utánaküldött űrhajó ténylegesen utol is érje. Ezeket a részleteket természetesen tisztázza például ez a cikk.

A fenti leírás alapján talán nem egyértelmű, de mindenképp megemlítendő, hogy a programozó természetesen kijönni nem tud a fekete lyukból, a pl. a ZFC konzisztenciájáról szerzett ismereteit már csak a lyuk "túloldalán", egy másik univerzumban tudja felhasználni. Az előadók ennek kapcsán megemlítették annak a lehetőségét is, hogy egyfajta "Noé bárkája", akár maga a Föld haladjon át a (nyilván alkalmasan óriási) fekete lyukon, maguk mögött hagyva ebben az univerzumban egy gépet és annak kiszolgáló-civilizációját, a számítógépbe beprogramozva az összes, Turing-elven nem megoldható, érdekes problémát.

Ennyit az előadás tartalmáról – de sajnos mindenképp mesélnem kell még a formájáról is. Az történt ugyanis, hogy egy óriási pofavizit lett az előadás: a fél IK tanári kar ott tobzódott, de csak hogy lássanak és látszódjanak – az egyik végigpofázta az előadást a mellette ülőnek, a másik átlag ötpercenként dőlt a padra majdnem elaludva; az aktívabbak meg jöttek az olyan jellegű kérdésekkel, hogy "bár én nem értek a csillagászati részéhez, de...", amivel persze nincs is semmi baj, de utána ne kezdjen el még három visszakérdésben hitetlenkedni... Szerencsére az előadó nem volt szívbajos, a tényleg hülye kérdésre szemrebbenés nélkül vágta rá, hogy nem tud válaszolni, mivel a kérdés nem értelmes.

λ: A tiltott kalkulus

Az alábbi fényképet egy ELTE-s jegyzetbolt kifüggesztett árlistájáról készítettem: