Nano
the nanny of pico
verslag v0.5

Naam : Van Belle Werner
e-mail : we47091@is2.vub.ac.be
programmeerproject
1e licentie Computerwetenschappen

projectbegeleider: Wolfgang De Meuter



Doel

De bedoeling van dit project was een compiler te schrijven van pico naar .

 

 is een object georiënteerde taal ontworpen door Sun Microsystems. Het is een verbeterdeopgelapte C++ met garbage-collector, maar bovenal is ze 'architecture neutral'. Ik ga er van uit dat -source voldoende leesbaar is zodat ik geen verdere uitleg meer hoef te geven omtrent de taal.

 

Pico is een 'educational language' ontworpen door Prof. Theo D'Hondt. Hierbij werd vooral aandacht geschonken aan de universal naming of functions.  De taal op zich trekt nogal op scheme. Onderstaand is een typisch (maar niet representatief) voorbeeld van pico.

 

begin(

  eenfunctie(arg1,arg2):arg1+arg2, 

  lazy_and(pred1,pred2()):if(pred1,pred2(),false),

  lazy_and(

    begin(

      display('Side effect pred 1'),

      false)

    begin

      display('Side effect pred 2'),

      true)))

 

Dit stukje code definieert eerst een functie 'eenfunctie', nadien wordt een lazy and 'lazy_and' gedefiniëerd door het gebruik van een functionele formele parameter. (Merk op dat deze zich nadien perfect als functie gedraagt) Dan wordt de 'lazy_and' eens aangeroepen om te demonstreren dat Side effect 2 nooit zal plaatsgrijpen.

Opbouw

De compiler is opgebouwd als volgt. Er werd vooral aandacht geschonken aan het optimaliseren van function-calls omdat dit een veel voorkomend gebeuren is.

     Lexicale analyse om tokens te parsen.

     Een parser om de abstracte grammatica in geheugen te nemen.

     Een collector die de mogelijke acties ondernomen op environments opsomt. Een actie is bijvoorbeeld het refereren van een functie, het beschrijven van een naam. Het uitlezen van een naam, etc.

     Een optimizer die met de verzamelde acties een verbeterde abstracte grammatica opstelt waarin nu ook 'HowToCall' informatie steekt. De optimizer zorgt ook voor de runtimeposities van variabelen.

     De codegenerator die de verbeterde parse-tree neemt en code generereert volgens een intermediate-code specification.

     De intermediate code writer is diegene die zorgt dat de uitgevoerde code conform de norm is en dat ze inderdaad wel degelijk uitgeschreven geraakt.

Runtime specification

Om code uit te voeren moet er natuurlijk eerst een runtime-convention zijn. Deze staat hieronder beschreven:

 

De primitieve objecten uit pico worden afgebeeld op klassen in . Zo wordt het primitieve object 'fraction' gemapt naar de klasse 'Double' (vandaar de hoofdletter). Gehele getallen worden gemapt naar 'Integer' en zo verderand so on...

 

User defined functions worden ook als klasse voorgesteld omdat functies ook moeten kunnen doorgegeven worden als parameter. Met andere woorden; omdat functies first class zijn in pico. Meer specifiek zullen functies afstammen van 'BasicFunction'.

 

Omdat pico het toelaat dat native-functions geherdefiniëerd worden moeten ook al de native-functions zoals 'begin', 'if' in de runtime aanwezig zijn. Eigenlijk is er totaal geen verschil tussen de voorgedefinieerde functies en de user-defined functions. Bijgevolg worden ook deze als afstammeling van BasicFunction gerepresenteerd.

 

Functies en environments[1] zijn 1-veel gerelateerd, daarom lag het nogal voor de hand de activatie van een functie gepaard te laten gaan met de creatie van een instance. Hierbij zorgt de callee voor een nieuwe environment.  (men kan deze creatie voor functie T weglaten, maar dan is functie T non-reëntrant. Dus T kan niet recursief aangeroepen worden. Dit is bijvoorbeeld nuttig om de voorgedefinieerde functies wat sneller te laten werken)

 

De manieren waarop parameters doorgegeven worden kan zelf gekozen worden door de compiler. Elke functie moet al de voorziene manieren ondersteunen. Parameters worden altijd doorgegeven als een array van Objecten. Dit is noodzakelijk omdat pico een @-operator heeft en deze zeer sterk steunt op zijn table-representatie. Op het ogenblik zijn er slechts twee parameter passing conventions:

 

     NormalCall: elke actuele parameter wordt doorgegeven als functie.

     ActionCall: enkel de actuele parameters die een functionele formele definitie hebben worden als functie meegegeven.

 

Laat ik in het eerder gegeven pico-voorbeeld eens het aantal gegenereerde klassen tellen indien enkel NormalCall gebruikt wordt.

 

begin(                                      begin

  eenfunctie(arg1,arg2):                  normal1      eenfunctie

    arg1                                             normal3

    +                                                   _add

    arg2,                                            normal4
  lazy_and(pred1,pred2()):               
normal2       lazy_uand

    if(                                                   if

      pred1,                                         normal5

      pred2(),                                       normal6

      false),                                        normal8

  lazy_and(                               normal3

    begin(                                           normal9

      display('Side effect pred 1'),                               normal11            display

                                                                          normal15

      false)                                                   normal12

    begin                                           normal10

      display('Side effect pred 2'),                               normal13        normal16

      true)))                                                  normal14

 

De 'begin'-klasse is nodig omdat voorgedefiniëerde functies voor de pico-programmeur in geen enkel opzicht afwijken van de user-defined functions. Deze functie wordt opgeroepen met een NormalCall en dat wil zeggen dat elke actuele parameter als functie doorgegeven moet worden. Dus 3 nieuwe door de compiler gegenereerde klassen: 'normal1', 'normal2' en 'normal3'.

 

Het voorkomen van 'eenfunctie' geeft vanzelfsprekend aanleiding tot een nieuwe klasse 'eenfunctie'.  De '+' operator in de body van deze functie wordt ook geNormalCalled en genereerd dus weer twee klassen.  Met name één voor het eerste argument 'arg1' en één voor het tweede argument 'arg2' mee te kunnen geven.

 

Zo verder werkend, voor elke parameter die meegegeven wordt een klasse definiërend, bekomen we 22 klassen. Een verschrikkelijk aantal voor dergelijk klein voorbeeld.

Optimaliseren

Het is zo dat in bovenstaand voorbeeld de meeste Normalcalls overbodig waren omdat voldoende van de functie gekend was. Normal1, Normal2 en Normal3 kunnen weggelaten worden als de compiler 'ziet' dat deze meegegeven worden aan de functie 'begin'. Normal3 en Normal4 kunnen op dezelfde wijze direct doorgegeven worden omdat de plus-operator gekend is, nergens geherdefiniëerd wordt en 2 values verwacht.

 

Een geval waar iets meer intelligentie komt bij kijken is de Normal5, Normal6 en Normal8. Het is hier duidelijk dat Normal5 steeds meegegeven wordt als het predicaat van de if-structuur. Omdat de if-structuur hier niet geherdefiniëerd wordt, is geweten dat 'pred1' direct als value mag doorgegeven worden. Dus Normal5 valt weg. Normal6 representeert 'pred2()' en Normal8 representeert de 'false'. Of  Normal6 of  Normal8 uitgevoerd worden hangt af van het predicaat en aldus moeten deze meegegeven worden als thunk.

 

Hetzelfde geld voor de zelf gedefiniëerde lazy-and. In dit voorbeeld is de lazy_and gekend en is geweten dat de eerste parameter steeds berekend dient te worden. De tweede paramater mag niet noodzakelijk direct berekend worden! Bijgevolg wordt enkel Normal10 overgehouden voor deze functioncall.

 

Samengevat geeft dit:

 

begin(                                      begin

  eenfunctie(arg1,arg2):                                             normal1      eenfunctie

    arg1                                              normal3

    +                                                   _add

    arg2,                                             normal4
  lazy_and(pred1,pred2()):                 normal2       lazy_uand

    if(                                                   if

      pred1,                                          normal5

      pred2(),                                       normal6

      false),                                        normal8

  lazy_and(                                normal3

    begin(                                            normal9

      display('Side effect pred 1'),                                 normal11            display

                                                                           normal15

      false)                                                    normal12

    begin                                           normal10

      display('Side effect pred 2'),                                 normal13           normal16

      true)))                                                   normal14

 

U ziet het, de meeste van de door de compiler gegenereerde klassen vallen weg. Diegene die blijven staan zijn werkelijk nodig. 'normal6' en 'normal8' zijn de twee takken van de if-structuur en  'normal10' is het lazy deel van de lazy_and.  In het totaal schieten er nog maar 9 klassen over.

Bepalen functiereference

Bovenstaande intuïtie moet nu in de compiler gegoten worden:

 

Als de compiler een functiereferentie ziet wordt eerst gekeken of er voldoende van de functie gekend is om de call-methode goed te kiezen. Kennis die hierbij nodig is, is welke functie gecalled zal worden en of deze functie eventuele herdefinities heeft die zichtbaar zijn in de huidige scope.  Bijvoorbeeld (hieronder), de 2e herdefinitie van 'demodemodemo' is niet schadelijk voor de function-call omdat deze herdefinitie vrijwel volledig buiten de scope van de eerste definitie ligt.

 

begin(

  env1():

    begin(

      demodemodemo(x):x,

      demodemodemo(12)),

  env2():

    begin(

      demodemodemo(x):x*2)).

     

Hadden deze definities anderzijds direct in 1 blok gestoken (zoals hieronder) kan men niet meer bepalen naar welke functie demodemodemo(12) eigenlijk refereert.

 

begin(

  demodemodemo(x):x,

  demodemodemo(12),

  demodemodemo(x):x*2).

 

Nu is de vraag natuurlijk wanneer een 'functiereferentie' formeel gekend is. Ik heb onderstaande stelregel gebruikt:

 

Een functiereference is gekend als de variablenaam in de huidige environments nergens een assignment/herdefinitie ondergaat.

 

Om deze data te verzamelen werk ik met 'acties op environments'. Dus elke referentie, assignment, definition  wordt beschouwd als een actie op een environment. Een reference is bijvoorbeeld voorgesteld door de 'read-nam' actie. Een functie-reference komt overeen met de 'call-nam' actie. De assignment is een eenvoudige 'write-nam' en de definition is een 'def-nam'. Door deze informatie dan op voldoende wijze doorheen de environment-tree te bubbelen kan direct afgelezen worden of de functie als constante behandelt mag worden.

 

De environments die zo in ons eerder gegeven voorbeeld gegenereerd worden zijn:

<root-environment>

       defnam('eenfunc')

       defnam('lazy_and')

       callnam('lazy_and')

       callnam('begin')

       callnam('display')

       readnam('false')

       readnam('true')

<eefunctie> parent-env = <root-env>

       readnam('arg1')

       readnam('arg2')

       callnam('+')

<lazy_and> parent-env = <root-env>

       callnam('if')

       readnam('pred1')

       callnam('pred2')

       readnam('false')

 

Voorstelling van een 'actie'

Frames

Bovenbeschreven acties worden voorgesteld door een 'frame' in de compiler. Een frame is dus eigenlijk de voorstelling van de levensloop van een bepaalde variabele in 1 environment. De frame heeft volgende interface:

 

ADT FRAME

_FRM_ _frm_create_(String, _ENV_);

Creëert een frame met variabelenaam 'name', in de gegeven  environment

int _frm_valid_(_FRM_);

Check om te zien of het wel een geldige frame is. Bijvoorbeeld, een ontbrekende environment-pointer in een frame wordt niet getolereerd.

_ENV_ _frm_env_(_FRM_);

Opvragen van de environment waarin de frame geldt. Deze is altijd gedefiniëerd.

String _frm_name_(_FRM_);

            

Opvragen van de framename. Deze is altijd gedefiniëerd.

void _frm_set_framenr_(_FRM_, int);

int_frm_framenr_(_FRM_);          

Zetten en lezen van het framenummer (dit is het lexicale adres in de java-source). Deze wordt normaal opgeroepen door de optimizer.

void _frm_mark_read_(_FRM_)

int _frm_read_(_FRM_)            

Zetten en lezen van de read-flag. Deze zegt of de variabele ooit uitgelezen wordt in deze environment.

void _frm_mark_written_(_FRM_)

int _frm_written_(_FRM_)             

Zetten en lezen van de 'write' flag. Deze zegt of de variabelenaam ooit een toekenning krijgt in deze environment.

void _frm_mark_called_(frm);

int _frm_called_(frm);

void _frm_foreach_call_(frm,func,common);

void _frm_add_caller_(frm, rffexp);           

Zetten en lezen van de 'called' flag. Zegt of de variabele ooit als functie gebruikt wordt. Een lijst van callers is ook beschikbaar.

void _frm_mark_parameter_(_FRM_);

int _frm_parameter_(_FRM_);            

Zetten en lezen van de 'parameter' flag. Zegt of deze variabele in de parameterlijst gedefiniëerd wordt.

void _frm_mark_parameterlst_(_FRM_)

int _frm_parameterlst_(_FRM_)

Zetten en lezen van de 'parameterlst' flag. Zegt of deze variabele als parameterlijst gedefiniëerd wordt.

void _frm_mark_native_(frm);

int _frm_native_(frm);

_DFF_ _frm_get_native_definition_(_FRM_ frm);           

Zetten en lezen van de 'native' flag. Zegt of deze variabele een voorgedefiniëerd 'iets' voorsteld.

void _frm_mark_defined_(frm)

int _frm_defined_(frm)

void _frm_add_definition_(frm, exp)

void _frm_add_native_definition_(frm, exp)

void _frm_foreach_definition_(frm,func,common)           

Zetten en lezen van de 'defined' flag en toebehoren. Zegt of de variabele in deze environment gedeclareerd wordt. Een lijst van definities is ook beschikbaar.

 

Environments

Een environment is een verzameling acties.

 

ADT ENVIRONMENT

_ENV_ _env_create_(_ENV_ DefinedIn);

Definiëert een nieuwe environment, die als parent DefinedIn heeft. Zet DefinedIn op NULL als dit de root environment moet zijn.

_ENV_ _env_definedin_(env)

Vraagt de hoger gelegen environment op.

int _env_size_(env)

void _env_set_size_(env,siz)

Opvragen en zetten van de environment grootte (nodig om de runtime environment te kunnen alloceren)

void _env_foreach_formal_(env,func,common)

void _env_add_formal_(env, formal)

Een formal is een door de compiler gegenereerde thunk die dienst doet als normal passed parameter. Deze formal parameters horen in een environment.

void _env_add_frame_(env,frm)

void* _env_firstthat_frm_(env,func,common)

void _env_foreach_frm_(env,func,common)

Het benaderen van de frames die opgeslagen zitten in een environment

 

Frames U Environments

Met aparte interfaces voor frames en environments komt men niet toe in die zin dat ze in een soort symbiose leven. Bijvoorbeeld een 'readnam' moet zowel de environment als de frame aanspreken: Eerst om de frame op te zoeken en indien nodig toe te voegen aan een environment en nadien om de 'read'-flag aan te zetten.

Er is dus nood aan een reeks functies die op beide ingrijpen. Hierbij wordt natuurlijk gebruik gemaakt van de interface van beide ADT's. Dit zijn dus een reeks functies om het leven gemakkelijker te maken. (en de code leesbaarder).

 

FRAME U  ENVIRONMENT

void foreach_env(void (*f)(_ENV_));

Voor elke environment die ooit gedefiniëerd is wordt de functie 'f' opgeroepen.

_FRM_ lookup_frm_in_env(_ENV_ env,String name);

Zoekt de frame op met naam 'name' in de environment 'env'. Hier wordt niet verder gezocht in de vader. Geeft NULL weer indien er geen dergelijke frame voorkomt

_FRM_ find_frm_in_env(_ENV_ env,String name);

Zoekt de frame op met naam 'name' in de environment 'env'. Hier wordt niet verder gezocht in de vader. Als de naam niet voorkomt in 'env' wordt terstond een frame met de juiste naam gecreëerd en toegevoegd.

struct LookupResult next_frm(_FRM_ frm);

Deze zoekt de volgende frame op met dezelfde naam. Hierbij wordt eerst verder gekeken in de eigen environment en nadien wordt verder gelopen in de vader van de frame-environment.

struct LookupResult lookup_frm(_ENV_ env, String name);

Zoekt de frame met naam 'name' op in de environment 'env'. Hier wordt verder gezocht bij de vader. Geeft NULL weer in LookupResult.frm indien er geen dergelijke frame voorkomt.

_FRM_ introduce_name(_ENV_ env, String name);

Creëert altijd een nieuwe frame met naam 'name' en environment 'env'.

_FRM_ define_name(_ENV_ env, String name);

Creëert een frame met naam 'name' (indien nodig) en environment 'env'. Markeert de frame als een definitie. Dat is hier dikke shit, want ik weet niet meer exact wat er hier gebeurt.

void write_name(_ENV_ env, String name);

Markeert de frame met naam 'name' as beeing written. Indien er zo geen frame is zal er prompto 1 worden aangemaakt en natuurlijk ook gemarkeerd als written.

void read_name(_ENV_ env, String name);

Markeert de frame met naam 'name' as beeing read.

_FRM_ call_name(_ENV_ env, String name);

Markeert de frame met naam 'name' as beeing called.

void ShowFrame(_FRM_ frm);

Toont de gegeven frame.

void ShowEnvironment(_ENV_ env);

Toont de gegeven environment, met bijhorende frames.

void ShowEnvironments(_ENV_ env);

Toont de gegeven environment en al de hoger liggende.

void ShowAllEnvironments(void);

Toont al de gekende environments.

Intermediate code

De compiler genereert code door middel van een wel omschreven interface. De bedoeling van onderstaande functies is als het ware een virtuele machine te vormen voor een taal zoals pico. Hierbij wordt het resultaat direct uitgeschreven. Dus eigenlijk, echt intermediate code.

 

Het maken van variabelen @ c-t. De 'wci' staat voor 'write-code-introduce'. Dus het introduceren van een nieuwe variabele voor de compiler.

       _VAR_ _wci_label_(void);

       _VAR_ _wci_var_(void);

       _VAR_ _wci_array_(void);

Verscheidene broodnodige acties. De 'wc' staat voor 'write-code' :

       void _wc_return_(_VAR_ who);

       void _wc_lookup_var_(_VAR_ target, int back, int framenr);

       void _wc_load_parameter_(_VAR_ target, char* won);

       void _wc_define_var_(_VAR_ source, int framenr);

       void _wc_set_var_(_VAR_ source, int back, int framenr);

       void _wc_index_array_(_VAR_ target, _VAR_ source, _VAR_ idx);

       void _wc_assign_(_VAR_ target, _VAR_ source);

       void _wc_assign_index_array_(_VAR_ target,_VAR_ idx,_VAR_ source);

De parameter-calling conventions.

       void _wc_actioncall_(_VAR_ storein, _VAR_ funself,_VAR_ argsvar);

       void _wc_normalcall_(_VAR_ storein, _VAR_ funself,_VAR_ argsvar);

Introduceren van nieuwe data @ runtime. 'wca' staat voor 'write-code-allocate'

       void _wca_number_(_VAR_ target, long number);

       void _wca_function_definition_(_VAR_ target, char* name);

       void _wca_str_(_VAR_ target, char* str);

       void _wca_array_(_VAR_ target, int siz);

       void _wca_table_(_VAR_ target,_VAR_ siz, _VAR_ contexp);

Problems encountered

Scope/lifetime information

Oorspronkelijk dacht ik een scope/lifetime informatie bij te houden (zoals beschreven in mijn voorstudie). Doch ik kan dit niet doen omdat de volgorde van evaluatie met gemak omgedraaid kan worden. Bijvoorbeeld:

 

begin(

  xbegin(a(),b(),c(),d()): begin(d(),c(),b(),a()),

  xbegin(

    display(a+b),

    b:12+a,

    a:15,

    display('eerst uitgevoerd')))

Name-space conflicts

Pico heeft een rijkere verzameling identifiers dan  en zodoende moest ik in de uitgevoerde identifiers escape-sequences steken. Belangrijk hierbij is dat ik de voorkomende identifiers niet gewoon mocht nummeren omdat men anders de runtime niet meer kan aanroepen.

Java: geen lifetime-checks

Bij elke variabele die ik introduceer schrijft de intermediate werkelijk een nieuwe variabelenaam uit. Zo kan je gemakkelijk aan een 250 tal variabeles komen in 1 method-body. Dat de -compiler niet ziet dat er  bepaalde variabelen op dezelfde posities gelegd kunnen worden daar kan ik weinig aan doen. De -compiler moet maar slimmer zijn.

Pico: echte functionele formele parameters

De functionele formele parameters die ik gebruik zijn eigenlijk gewoonweg thunks. Pico laat echter toe dat deze ook parameters meekrijgen. Dit heeft tot gevolg dat mijn ganse optimising-techniek naar de maan is. Na een gesprek met de begeleidende assistenten bleek dat ik dit mocht negeren. Toch een kort voorbeeld geven (het antwoord is 4):

 

begin(

  f(a(x)):a(2),

  f(x*x))

Tools

     In het begin gebruikte ik als compiler gcc 2.5.8 onder linux 1.1.59.

     Een beetje later heb ik Watcom C/C++ v10.5 aangekocht en ben ik daarmee verder gaan compileren.

     De DOS4GW dos-extender is natuurlijk ook van de parij.

     De -compiler van Sun. (het aantal keer dat ik 'internal error, please report' heb gezien is zo groot dat ik uiteindelijk niets gerapporteerd heb. Grijns...)

     Windows '95 natuurlijk, zonder deze laatste zou er bij mij niet veel  draaien.

How to proceed

Als met dit project ooit verder wordt gegaan zou ik het volgende graag geïmplementeerd zien:

     Zorgen dat de echte functionele parameters aanvaard worden zoals ze in het pico-manifest gedefiniëerd worden. Ik wil dit natuurlijk doen zonder die sterke optimisatie te verliezen !

     Een type inferencer toevoegen zodat nog verder geoptimizeerd kan worden. (ik denk er aan deze eerst te ontwerpen in prolog en deze dan om te bouwen naar C, of eventueel te linken met C)

     Een ander ideetje waarmee ik rondloop is een taal te ontwerpen waarin de primitieve objecten bestaan uit abstracte grammaticas, stukken van parse-trees, expressies, environmentacties, typeinformatie en een garbage collector. Dit om gemakkelijk een typeinferencer kunnen over te brengen naar nano en de compiler abstracter te kunnen ontwerpen.

Tijdschema

Ik zat steeds stevig voor op het gegeven schema. Het programmeren zelf was op oudejaarsavond af.  Dat ik constant voor zat is niet verbazend aangezien ik in het eerste semester gemiddeld 4 uur les had per week. Het schrijven van de verslagen heeft nadien een aardige dosis werk opgeëist.


References

The  language specification
http://java.sun.com/...

 

The  class API
http://java.sun.com/...

 

Het pico manifest van Prof. Theo D'Hondt.

 

The C programming language
Second edition
Brian W.Kernighan/Dennis M.Ritchie

PTR Prentice Hall, Englewood Cliffs, New Jersey 07632

ISBN 0-13-110370-8 (pbk)

ISBN 0-13-110370-9

 

Compilers, principles, tools & techniques
Alfred V.Aho, Ravi Sethi, Jeffrey D.Ullman

Addison-Wesley Publishing Company

ISBN 0-201-10194-7

 

Structure and interpretation of computer programs
Harold Abelson and Gerald Jay Sussman
The MIT press: Cambridge/Massachusetts, London/England

ISBN 0-262-0171-1

McGraw-Hill Book Company: New York, St.Louis, San Francisco, Montreal, Toronto.

ISBN 0-07-000-422-6



[1]Ik gebruik een ietwat afwijkende terminologie wat betreft environments en ARI's (activation record instances). Wat in pascal een ARI genoemd wordt noem ik een 'environment'. Wat in pascal de environment genoemd wordt (de gestackte ARI's) noem ik 'environments' (in het meervoud).