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 verbeterde
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
verder...
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. |
|
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.)
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