[alg] coersion/cast info.

[Alarmnummer]

Ik loop nu al een tijdje met coersions in parsers te stoeien, maar ik ben niet blij met het 'geklungel' Wie weet een leuk (praktisch) stuk staan over type-casten?

[mbravenboer]
De stukken van Cardelli ken ik, maar daar staat niets praktisch in uitgelegd. En verder staat er ook niets praktisch in 'modern compiler implementation'

[ Voor 6% gewijzigd door Alarmnummer op 28-04-2003 22:24 ]

[Soultaker]

Wat bedoel je met "coercion in parsers"? Een parser weet toch helemaal niets van types af en heeft dan toch ook niets met coercion te maken?

In welk stadium kom je precies je problemen tegen? Ik heb weliswaar weinig hands-on ervaring met het bouwen van compilers maar misschien heb kan ik een creatieve suggestie doen als je een wat concretere omschrijving van het probleem kan geven waar je tegenaan loopt.

In principe lijkt me dat je type coercion net zo kunt afhandelen als type conversion, behalve dat de functies die je voor de conversie gebruikt al door de compiler vastgelegd zijn. Als je dus bijvoorbeeld een cast tegenkomt (een expliciete coercion) of je verwacht een ander type dan je beschikbaar hebt (een mogelijke impliciete coercion) dan is het kwestie van een call naar een conversie-functie toevoegen. Liefst wil je om efficiency-redenen bij het genereren van de code geen echte function calls genereren en kun je dus beter een nieuw soort node aan je abstract syntax tree toevoegen, maar dat is een implementatiedetail.

[Alarmnummer]

Soultaker schreef op 28 April 2003 @ 22:45:
Wat bedoel je met "coercion in parsers"? Een parser weet toch helemaal niets van types af en heeft dan toch ook niets met coercion te maken?

Aan de hand van de AST die ik van de parser terug krijg bouw ik de IR op, waar ik dus oa types nodig ben. En dat gedeelte van mijn systeem noem ik de parser. (Misschien zou front-end een betere benaming zijn)

In welk stadium kom je precies je problemen tegen? Ik heb weliswaar weinig hands-on ervaring met het bouwen van compilers maar misschien heb kan ik een creatieve suggestie doen als je een wat concretere omschrijving van het probleem kan geven waar je tegenaan loopt.

Bij het type-checken van expressies. Stel dat ik de volgende add operator heb.

int + int
float + float

Als ik nu de volgende expressie krijg

1+1.1

Dan is hier in 1e instantie geen enkele operator geschikt voor, maar ik kan die 1 casten naar een float

float(1)+1.1

En dan is het wel geschikt voor
float+float

Ik zit dus een beetje met het feit hoe ik die coersions kan toepassen zonder het type-checken onnodig complex te gaan maken. Ik heb een hele rijke type-strcuctuur in mijn systeem. En een van de types is een 'mutable type'. Een mutable type kan toegewezen worden aan 'dingen' die van waarde kunnen veranderen zoals een var. Je krijg dan het volgende type voor variable a van het type Int: Mutable(Int)

Maar als ik nu a+10 ga doen, dan is er in 1e instantie geen operator gedefinieerd voor Mutable(Int)+Int. Daarom moet je dus die Mutable casten naar Int.

[ Voor 5% gewijzigd door Alarmnummer op 28-04-2003 22:56 ]

[Glimi]

Waarom wil je eigen coercion? Coercion brengt voor dat stukje suiker imho een hoop problemen mee. Je zult namelijk moeten vastleggen welke volgorde welke coercions hebben zodat ze nog dieper kunnen gaan.
Of zie ik dat nu verkeerd?

[Alarmnummer]

Glimi schreef op 28 April 2003 @ 23:01:
Waarom wil je eigen coercion? Coercion brengt voor dat stukje suiker imho een hoop problemen mee. Je zult namelijk moeten vastleggen welke volgorde welke coercions hebben zodat ze nog dieper kunnen gaan.
Of zie ik dat nu verkeerd?

Omdat je anders een enorme klotensyntax gaat krijgen.


var float b;

je mag kiezen uit:

float(1)+float(b)

of

1+b

[Soultaker]

Alarmnummer schreef op 28 april 2003 @ 22:54:
Aan de hand van de AST die ik van de parser terug krijg bouw ik de IR op, waar ik dus oa types nodig ben. En dat gedeelte van mijn systeem noem ik de parser. (Misschien zou front-end een betere benaming zijn)

IR? En het maakt me niet zoveel uit hoe je 't noemt als we 't er maar over eens zijn wat het is (en dat is nu duidelijk).

k zit dus een beetje met het feit hoe ik die coersions kan toepassen zonder het type-checken onnodig complex te gaan maken. Ik heb een hele rijke type-strcuctuur in mijn systeem. En een van de types is een 'mutable type'. Een mutable type kan toegewezen worden aan 'dingen' die van waarde kunnen veranderen zoals een var. Je krijg dan het volgende type voor variable a van het type Int: Mutable(Int)
Maar als ik nu a+10 ga doen, dan is er in 1e instantie geen operator gedefinieerd voor Mutable(Int)+Int. Daarom moet je dus die Mutable casten naar Int.

Een simpele (en misschien voldoende?) benadering is om te je bindende operator/functie zo ver mogelijk te 'matchen' en als je vast komt te zitten, de overige gegeven types aan te passen aan wat je wilt hebben. In je voorbeeld van "1 + 1.0" kom je dan tot de conclusie dat de operator + met als eerste argument een int toegepast kan worden. Die operator moet dan ook een int als tweede argument hebben, maar je hebt een float! Die int moet dus naar een float gecoerced worden.

Hoe je de regels van wat je waarheen kunt converteren vastlegt is niet zo interessant. Een simpel system zou gebruik kunnen maken van klassen (zoals in C: zo'n beetje alle numerieke typen kun je heen en weer converteren) of van een hiërarchisch model (een beetje zoals Java: je kunt alleen van hoge naar lage precisie converteren) of alles ertussen in.

Met de voorgestelde methode kun je vrijwel alle expressies eenvoudig typeren. Ambiguïteiten treden pas op, als er meerdere mogelijkheden zijn voor een bepaald argument (bijvoorbeeld, als je in het voorbeeld hierboven ook een operator zou hebben die als tweede argument een boolean krijgt en je 1.0 daar ook naar geconverteerd mag worden). In dat geval zou je (nogal ad-hoc) gewoon een volgorde vast kunnen leggen, of (wat geavanceerder en misschien minder inzichtelijk voor de programmeur) kunnen specificeren welke conversies de voorkeur hebben (van double naar int is minder 'schadelijk' dan van double naar boolean, bijvoorbeeld).

Vervelender is dat je in zo'n geval altijd greedy je beschikbare types matcht en dat is niet echt wenselijk. In bovenstaande systeem zou "1 + 2.3" bijvoorbeeld met een functie op ints afgehandeld worden en "2.3 + 1" met een functie op floats, wat gezien de commutativiteit van de +-operator (en omwille van de nauwkeurigheid) niet echt de bedoeling is.

Ik kan me dan ook een variatie voorstellen waarbij je gaat backtracken. Dat zou wel eens veel werk voor de compiler kunnen worden (in theorie dan; in de praktijk zal het aantal mogelijke operators beperkt zijn, neem ik aan). Je moet dan echter een manier verzinnen om de wenselijkheid van een zekere variant te waarden, zodat je de verschillende mogelijkheden kunt vergelijken.

Het lijkt me belangrijk dat je een mechanisme kiest dat duidelijk en logisch is voor de programmeur (ik zet zelf altijd overal casts en haakjes bij, als ik het even niet meer weet; de compiler kan nog wel zo slim zijn, als ik niet exact weet hoe 'ie werkt, gebruik ik 'm niet). Waarschijnlijk wil je als tweede eis voorrang geven aan conversies waarbij geen of relatief weinig verlies van precisie optreedt, of (als derde criterium) efficient uit te voeren zijn.

Overigens zijn sommige beslissingen daarbij best lastig. Het optellen van een 32-bits int bij een 32-bits float, bijvoorbeeld: bij welke variant (int + int = int of float + float = float) de precisie behouden blijft, is afhankelijk van de feitelijke waarden van de operands. Hoewel in dit geval de variant met floats waarschijnlijk de voorkeur heeft, is die voorkeur bij het optellen van een 64-bits integer bij een 32-bits float weer minder duidelijk. Argument is in beide gevallen natuurlijk dat het converteren van een integer naar een float gemiddeld minder precisieverlies oplevert dan het converteren van een float naar een integer.

[mbravenboer]

In Stratego (of een functionele taal) zou ik hiervoor pattern-matching gebruiken. Bij bottom-up type-checking kan je dan matchen op de typen van de argumenten van de operatoren. Voorbeeldje:

code:

R1: BinOp(Mul, Typed(e1, Int), Typed(e2, Int))
      -> Typed(BinOp(MulInt, e1, e2), Int)
 
R2: BinOp(Mul, Typed(e1, Float), Typed(e2, Int))
      -> Typed(BinOp(MulFloat, e1, Coerce(Float, e2)), Float)
 
R3: BinOp(Mul, Typed(e1, Int), Typed(e2, Float))
      -> Typed(BinOp(MulFloat, Coerce(Float, e1), e2), Float)

In dit voorbeeld worden expressies in de type checker herschreven naar Typed knopen, met de expressie en zijn type als kinderen. Je kan een type-checker fraaier implementeren met behulp van attributen die je bevestigt aan de expressies. De volgende code kan beide varianten aan (Typed knopen en attributen) door de typen te bepalen en in te stellen aan de hand van gescheiden functies.

code:

R1: BinOp(Mul, e1, e2) -> <type-as-int> BinOp(MulInt, e1, e2)
      where <has-int-type> e1
          ; <has-int-type> e2
 
R2: BinOp(Mul, e1, e2) -> <type-as-float> BinOp(MulFloat, Coerce(Float, e1), e2)
     where <has-int-type> e1
         ; <has-float-type> e2

Deze voorbeelden zijn heel specifiek voor de Mul en sommen alle gevallen op. Dat is natuurlijk veel werk en daarom kan je dit gaan generaliseren en abstraheren. Je kan deze regels bijvoorbeeld laten functioneren voor alle rekenkundige operatoren en je kan de argumenten van een operator in een lijst stoppen (a + b + c wordt dan bijv Binop(Plus, [a, b, c]), waardoor je de regels nog duidelijker en efficienter uit kan drukken (omdat je de regel dan niet voor de lhs en rhs hoeft te definieren).

Uiteraard is dit wat lastiger te realiseren in Java omdat je daar geen pattern-matching hebt. Dat jij in een baggere taal compilers schrijft is echter niet mijn probleem .

Soultaker: IR?

Intermediate Representation: een source en target taal onafhankelijke 'tussentaal' die de front-end voor een specifieke taal en de back-end voor een specifiek target platform netjes scheidt.

Soultaker: Vervelender is dat je in zo'n geval altijd greedy je beschikbare types matcht en dat is niet echt wenselijk.

Alarmnummer werkt netjes op bomen, dus is er niet echt een probleem. Termen als greedy en back-tracking spelen dan niet echt.

edit:
oeps, paar tikfoutjes

[ Voor 13% gewijzigd door mbravenboer op 29-04-2003 08:30 ]

[Soultaker]

mbravenboer schreef op 29 April 2003 @ 08:25:
Intermediate Representation: een source en target taal onafhankelijke 'tussentaal' die de front-end voor een specifieke taal en de back-end voor een specifiek target platform netjes scheidt.

Ah, bedankt. Het kan sowieso geen kwaad om afkortingen die voor het eerst in dit topic voorkomen eerst (of altijd) voluit te schrijven; ik schrijf niet dagelijks compilers dus dan kan ik zulke vertaalslagen niet zomaar maken.

Alarmnummer werkt netjes op bomen, dus is er niet echt een probleem. Termen als greedy en back-tracking spelen dan niet echt.

Ik had het daarbij over het matchen van argumenten van beschikbare functies. Als ik het goed begrijp heb je een functie-aanroep met een zeker aantal argumenten, en een aantal beschikbare overloaded functies met datzelfde aantal argumenten. In het geval van de vermenigvuldiging

code:

    mul(float, float)
    mul(int, int)
    ... etc ...

Met (bijvoorbeeld) een toepassing van mul(int, float). Duidelijk is dat voor deze toepassing een van de twee argumenten geconverteerd moet worden.

Als ik het probleem goed begrijp, is het nu de vraag op welke manier de compiler het beste kan beslissen welke argumenten van de functietoepassing naar welk type geconverteerd worden. Dat komt feitelijk neer op het kiezen van een meest geschikte beschikbare functie, waarna alle ongeschikte argumenten geconverteerd worden naar het benodige type. Het kiezen van de juiste functie is echter niet zo eenvoudig.

Ik weet niet of ik het probleem zo nog goed begrijp, of dat ik al schrijvende een heel andere kant op ben gegaan?

Hoe het ook zei; in dit kader begon ik over een variant met greedy matching (waarbij je bijvoorbeeld eerst bepaald dat je iets met mul(int, ...) wilt doen, en aangezien je daarna alleen nog maar mul(int, int) overhebt, die maar kiest) of dat je alle mogelijke combinaties afgaat (vandaar backtracking) en aan allen een waarde toekent. (Een functie die een conversie van int naar float behoeft is wenselijker dan een functie die een conversie van float naar int behoeft).

[mbravenboer]

Als ik het probleem goed begrijp, is het nu de vraag op welke manier de compiler het beste kan beslissen welke argumenten van de functietoepassing naar welk type geconverteerd worden.

Het gaat met name om de manier waarop je dit het beste kan implementeren gegeven de specificatie van de coercion regels die gelden voor de taal. Tijdens het implementeren van de compiler zou je je dus niet bezig moeten houden met het verzinnen van logische regels: dit is een gescheiden taak (die je uiteraard wel in dezelfde tijd als het schrijven van de compiler kan uitvoeren ).

Als je eenmaal duidelijk weet welke regels je waar moet toepassen, komt het probleem van de implementatie: hoe verwerk je de regels zo duidelijk mogelijk? Hoe verloopt de samenwerking met de type checker? Kan je de regels misschien zelfs scheiden van de type checker en opnemen in een aparte fase?

greedy matching / backtracking

Het komt goed over hoe je er tegen aan kijkt ja. Op zich is de werking wellicht ook prima (tov de vastgelegde regels), maar het gaat nogal uit van een lineaire verwerking van de argumenten. In een compiler die werkt op een volledige AST heb je echter alle argumenten beschikbaar en heb je alle vrijheid om die AST aan te passen. Je kan de argumenten dus gewoon inspecteren en aan de hand van de typen besluiten wat je gaat doen (uiteraard aan de hand van de vastgelegde regels). In de code hierboven doe ik dit door de verschillende mogelijkheden op te sommen en toe te passen door pattern-matching over de AST. Uiteraard sluit dit een greedy/backtracking aanpak niet uit.

edit:
oeps: AST = Abstract Syntax Tree. Waarom is er geen UBB abbr

[ Voor 3% gewijzigd door mbravenboer op 29-04-2003 14:36 ]

[Alarmnummer]

Een gedeelte van de problemen heb ik eigelijk toch al in mijn type-systeem opgelost. Een Int is bij mij een subtype van een Float. Als ik de volgende 2 operatoren heb:

Int+Int
Float+Float

en de volgende expressie:
1+1.5

Dan kan ik na het inlezen van het 1e argument (en de operator) concluderen dat beide versies van de plus operator voldoen. Na het inlezen van het 2e element kom ik tot de ontdekking dat alleen nog de 2e versie (Float+Float) voldoet, en ik ben ook meteen klaar.

Het enigste waar ik dan nog mee zit zijn die reference types. Ik heb Daniel Bonniot (developer van Nice) gevraagd hoe zij het opgelost hebben. Hij plaatst net zoals ik ook geen conversies erin en laat dit gedeelte over aan de bytecode emiter. En verder heeft nice geen mutable type, maar worden assignments adhoc opgelost.

In Nice kom je alleen via functies aan 'ítems'. Als je bv een recordtype Persoon hebt, met veld voornaam, dan heb je ook een functie: voornaam(Persoon p).

Als je dan zegt:

persoonx.voornaam = '"Jan"", dan wordt dit intern omgezet naar:

voornaam(persoonx) = "Jan"

En daarna controleren ze (adhoc) of die lhs (left hand side) wel iets is waar je naartoe kan schrijven. Alles oplossen met functies had ik zelf eigelijk ook in gedachten omdat het systeem misschien wel meer functies krijgt, maar je krijgt uiteindelijk minder verschillende structuren.

Alleen wil ik graag knoeien met die mutable types

Wat ik trouwens zou kunnen doen is een Mutable(Int) een subtype te laten zijn van een Int. Hierdoor kan ik

a+1.1 ook eenvoudig bepalen.

(a is van het type (Mutable(Int))

Omdat a een subtype is van Int, en Int een subtype van float, krijg ik dus Float+Float.

En bij de evaluator zou ik het als volgt kunnen oplossen:

[ Voor 44% gewijzigd door Alarmnummer op 29-04-2003 15:43 ]

[Alarmnummer]

Bij de evaluator zou ik het kunnen oplossen door de types ook werkelijk polymorf te maken ipv dat geknoei. Dood aan de primitieve types!

code:

interface Float{
    float float();
}

interface Int extends FLoat{
    int int();
}

interface Char extends Int{
    char char():
}

class FloatImpl implements Float{
    float _float;
    
    public float float(){return _float;}
}

class IntImpl implements Int{
    int _int;
    
    public float float(){return _int;}
    
    public int int(){return _int;}
}

class CharImpl implements Char{

    char _char;
    
    public float float(){return _char;}
    
    public int int(){return _char;}
    
    public char char(){return _char;}
}

[Soultaker]

mbravenboer schreef op 29 april 2003 @ 14:31:
Het gaat met name om de manier waarop je dit het beste kan implementeren gegeven de specificatie van de coercion regels die gelden voor de taal. Tijdens het implementeren van de compiler zou je je dus niet bezig moeten houden met het verzinnen van logische regels: dit is een gescheiden taak (die je uiteraard wel in dezelfde tijd als het schrijven van de compiler kan uitvoeren ).

Ah, ok. De implementatie daarvan lijkt me op zich minder interessant: als je al beslist hebt welke variant van een functie je wilt gebruiken, hoef je alleen maar de argumenten aan te passen zodat ze voldoen aan de gewenste typen.

Dat lijkt me (zoals ik ook al in m'n eerste reactie zei, geloof ik) een kwestie van nodes tussenvoegen voor de conversie. In het simpelste geval zou je daar een stel functies voor kunnen gebruiken. Een functietoepassing als "1 + 2.3" wordt dan (bijvoorbeeld) simpelweg "to_float(1) + 2.3", waarna je de +-operator kunt toepassen.

Mocht er geen conversie van int naar float bestaan, dan is to_float(int) niet gedefinieerd en geeft je typechecker dus alsnog een foutmelding. Ik kan me trouwens voorstellen dat dit allemaal in dezelfde pass gebeurt.

edit:
oeps: AST = Abstract Syntax Tree. Waarom is er geen UBB abbr

Hehe, geen probleem: de AST was al eerder genoemd.

[alienfruit]

Soultaker jij bedoelt de tokenizer; de tokenizer weet niks van types e.d. af.
Enige wat hij doet is karakter combinaties kopelen aan een soort token, bijv. keyword, numeric, hexidecimal etc.

Vervolgens gaat de parser de resultaat van de tokenizer analyseren, op dit moment weet dus eigenlijk wat wat is. Op dit moment wil je wel weten welke is e.d.

[Soultaker]

alienfruit schreef op 29 April 2003 @ 23:48:
Soultaker jij bedoelt de tokenizer; de tokenizer weet niks van types e.d. af.
Enige wat hij doet is karakter combinaties kopelen aan een soort token, bijv. keyword, numeric, hexidecimal etc.

Vervolgens gaat de parser de resultaat van de tokenizer analyseren, op dit moment weet dus eigenlijk wat wat is. Op dit moment wil je wel weten welke is e.d.

Nee, ik dacht bij 'parser' aan het ding dat code omzet in een (concrete) syntax tree. Vervolgens gaat daar een contextual analyser/type checker overheen om allerlei annotaties toe te voegen en te controleren of aan allerhande restricties is voldaan, en tenslotte loopt een code generator de abstract syntax tree af om de feitelijke uiteindelijke programmacode voor het doelplatform te generen.

In een one-pass compiler is de parser samengevoegd met de overige onderdelen van de compiler, maar dan is nog steeds een logisch onderscheid te maken tussen het omzetten van een platte serie tokens in een boomstructuuur, aan de hand van de grammatica van de taal. Het belangrijke punt is hierbij dat (naar mijn idee) de parser werkt op basis van de grammatica van de taal en daarin zit geen type-informatie besloten! Type-informatie wordt pas na het parsen toegevoegd.

Ik bedoelde dus zeker niet de tokenizer, maar als er een andere gangbare interpratie van de term 'parser' is dan ik tot nu toe aanhield, dan wil ik me daar graag aan aanpassen, hoor.

[Alarmnummer]

Ik denk dat mijn benaming ook niet helemaal correct was. Het zou beter front-end genoemt kunnen worden ipv parser.

[alienfruit]

Soultaker zo is het mij uitgelegd hoor
Ach, Zolang het maar werkt uiteindelijk....

[ Voor 37% gewijzigd door alienfruit op 30-04-2003 10:37 ]