Nano
the
nanny of
pico
tussentijdse
evaluatie
Naam : Van Belle
Werner
e-mail : we47091@is2.vub.ac.be
programmeerproject
1e licentie Computerwetenschappen
Projectbegeleider: Wolgang
Demeuter
Pico
2 slides met een voorbeeld op. Interresant hierbij is
de dispatcher in de makepoint. Deze verwacht een willekeurig aantal parameters.
het opvragen de x/y-coordinaat gebeurt gewoon met getx/gety. Deze messages geven direct het juiste antwoord. (ze geven geen functie weer die aangeroepen moet worden om de waarde te bekomen.)
De setx/sety zetten de x/y coordinaat ook onmiddelijk. Hierbij wordt gebruikt gemaakt van een eventuele 2e parameter.
De set-functie zet de x/y coordinaat in 1 slag. Merk op dat hierbij een apply (@) gepleegd wordt. Daarom ook heeft de set een junk parameter die genegeerd dient te worden.
De setif functie zet de x coordinaar op de nieuwe waarde indien het predicaat waar is. Zet de y-coordinaat op de nieuwe waarde indien false. Belangrijk hierbij is dat de setif functionele formele parameters heeft. (Zie voorbeeld)
Java wordt niet uitgelegd omdat de taal nogal sterk voor de hand ligt.
begin(
makepoint(x,y):
begin(
setx(nx):x:=nx,
sety(ny):y:=ny,
set(junk,nx,ny): begin(x:=nx,y:=ny),
setif(pred,nx(),ny()): if(pred,setx(nx()),sety(ny())),
displaythis():
begin(
display(x),
display(','),
display(y),
display('|')),
dispatcher@argumenten:
if(argumenten[1]='getx',x,
if(argumenten[1]='gety',y,
if(argumenten[1]='setx',setx(argumenten[2]),
if(argumenten[1]='sety',sety(argumenten[2]),
if(argumenten[1]='set',set@argumenten,
if(argumenten[1]='setif',setif,
if(argumenten[1]='display',displaythis(),0))))))),
dispatcher),
punt:1,
punt:=makepoint(1,2),
punt('display'),
punt('setx',2),
punt('sety',4),
punt('display'),
punt('set',3,5),
punt('display'),
func:punt('setif'),
func(punt=1,
begin(display('setting x|'),0),
begin(display('setting y|'),0)),
punt('display')
)
Standaard compiler
Runtime Specificatie
Een standaardcompiler heeft een lexicale analyzer, een token parser, een optimizer, een codegenerator. Ik zal enkel de optimizer en de codegenerator bespreken, omdat ik beide anderen volledig overneem uit pico. (slide, snapgfx)
voordat een codegenerator besproken kan worden dient natuurlijk een runtime-specificatie opgediept te worden.
Elk object in java heeft een type dat @ compile-time gekend is. Pico heeft dit niet, daarom moet ik een mapping hebben van pico naar java, waarbij eventuele typeinformatie niet meegegeven moet worden. Dit kan gedaan worden door elk klein primitief pico-objectje af te beelden op een afstammeling van de classe 'Object'. Dit is vooral handig omdat er reeds standaard Integerobjecten/doubleobjecten/stringobjecten en zo voort voor handen zijn.
Funcies kunnen in pico gewoon als variabelen behandelt worden, zodoende moet een functie ook afgestamd zijn van Object; Dit wil zeggen dat als ik 50 functies definieer ik zeker 50 klassen zal krijgen. Native-functions moeten zich exact hetzelfde gedragen als user-defined functions en zullen daarom ook afstammen van BasicFunction.
Environments moeten ook at runtime gerepresenteerd worden. Een environment heeft 3 functies. Namelijk: 'define(nr,value)', 'set'back;nr,value)', 'lookup(back,nr,value)'. De nummer is een integer door nano wordt berekend. Back zegt hoeveel environments terug geteld moet worden en value is de waarde die toegekend moet worden. (Een object natuurlijk)
parameters worden steeds meegegeven in een array. Dit is een gevolg van het feit dat in pico een @ operator voorkomt. Dan zijn er verder nog call-mechaniscmen nodig.
Elke functie (afstammeling van BasicFunction) heeft tot nu toe de volgende call-mechanismen.
NormalCall (Object parameters[]) waarbij geen van de ontvangen parameters zijn op voorhand uitgerekend.
ActionCall(Object parameters[]) waarbij de parameters zijn direct in het formaat dat ze moeten zijn.
package
PicoRuntime;
import java.*;
import
PicoRuntime.DoorVerwijzing;
public abstract
class
FunctionObject extends BasicFunction {
protected Object
Contents[];
protected FunctionObject DefinedIn;
static final protected DoorVerwijzing NotDefined=
new DoorVerwijzing(1024,0);
static final private Class
DoorVerwijzingClass=NotDefined.getClass();
public FunctionObject(int size, FunctionObject parentenvironment)
{Contents=new Object[size];
DefinedIn=parentenvironment;}
public FunctionObject() {};
public abstract Object ActionCall(Object parameters[]);
public abstract Object NormalCall(Object parameters[]);
protected abstract Object Action();
abstract protected void SetupFormals();
protected final Object LookUp(int back, int framenr)
{if (back==0)
{Object answer=Contents[framenr];
if (answer.getClass()==DoorVerwijzingClass)
return
DefinedIn.LookUp(
((DoorVerwijzing)answer).back,
((DoorVerwijzing)answer).framenr);
return
answer;}
return DefinedIn.LookUp(back-1,framenr);}
public final void Set(int back, int framenr, Object value)
{if (back==0)
{Object answer=Contents[framenr];
if (answer==null)
System.out.print("uninitialized environment
entry.\n");
if (answer.getClass()==DoorVerwijzingClass)
DefinedIn.Set(
((DoorVerwijzing)answer).back,
((DoorVerwijzing)answer).framenr,value);
else
Contents[framenr]=value;}
else
{DefinedIn.Set(back-1,framenr,value);}}
static final public Object[] newtable(int size, Object exp)
{Object [] result;
result=new Object[size];
int i;
for(i=0;i<size;i++)
result[i]=exp;
return result;}};
package
PicoRuntime;
import
PicoRuntime.FunctionObject;
public
abstract class FunctionVarParam extends FunctionObject {
public FunctionVarParam(int size,
FunctionObject parentenvironment)
{super(size,parentenvironment);}
public Object ActionCall(Object
parameters[])
{
//1. een nieuwe instance van de klasse
genereren
FunctionObject
funcinst=(FunctionObject)this.clone();
funcinst.Contents=(Object[])Contents.clone();
//2. de parameters in de nieuwe
environment stouwen
funcinst.Contents[0]=parameters;
//3. al de lokale variabelen laten
doorverwijzen (in 1 gebeurt)
//4. de formele functieparameters
alloceren.
funcinst.SetupFormals();
//5. het nieuwe object zijn Action()
aanroepen.
return funcinst.Action();}
public Object NormalCall(Object
parameters[])
{
//1. een nieuwe instance van de klasse
genereren
FunctionObject
funcinst=(FunctionObject)this.clone();
funcinst.Contents=(Object[])Contents.clone();
//2. de parameters juist in deze klasse
kopieren
for(int i=0;i<parameters.length;i++)
parameters[i]=((FunctionObject)(parameters[i])).Action();
funcinst.Contents[0]=parameters;
//3. al de lokale variabelen laten
doorvberwijzen
//4. al de formele parameters alloceren
funcinst.SetupFormals();
//5. het nieuwe object zijn Action()
aanroepen.
return funcinst.Action();}
};
package
PicoRuntime;
import
java.*;
public
abstract class FunctionVastParam extends FunctionObject {
static boolean NoParameters[]=new
boolean[0];
protected boolean
ParameterTemplate[]=NoParameters;
//indien true moet de functie
gedenormalizeerd worden
public FunctionVastParam() {}
public FunctionVastParam(int size,
FunctionObject parentenvironment)
{super(size,parentenvironment);}
public Object ActionCall(Object
parameters[])
{//1. een nieuwe instance van de klasse
genereren
FunctionObject
funcinst=(FunctionObject)this.clone();
funcinst.Contents=(Object[])Contents.clone();
//2. de parameters in de nieuwe
environment stouwen
for(int
i=0;i<ParameterTemplate.length;i++)
funcinst.Contents[i]=parameters[i];
//3. al de lokale variabelen laten
doorverwijzen (in 1 gebeurt)
//4. de formele functieparameters
alloceren.
funcinst.SetupFormals();
//5. het nieuwe object zijn Action()
aanroepen.
return funcinst.Action();};
public Object NormalCall(Object
parameters[])
{//1. een nieuwe instance van de klasse
genereren
FunctionObject
funcinst=(FunctionObject)this.clone();
funcinst.Contents=(Object[])Contents.clone();
//2. de parameters juist in deze klasse
kopieren
for(int
i=0;i<ParameterTemplate.length;i++)
if (ParameterTemplate[i])
funcinst.Contents[i]=((FunctionObject)(parameters[i])).Action();
else funcinst.Contents[i]=parameters[i];
//3. al de lokale variabelen laten
doorvberwijzen
//4. al de formele parameters alloceren
funcinst.SetupFormals();
//5. het nieuwe object zijn Action()
aanroepen.
return funcinst.Action();};};
Intermediate code
Optimisaties
Het volledige uitschrijven van code wordt via een welbepaalde interface gedaan (ADT) (gedefinieert in 'codewriter.h'). Deze voert java-source uit. Standaardacties zijn te vinden op de bijhorende slides
Hetgeen waar in dit voorbeeld het meeste tijd inkruipt zijn de function-calls. Elke meegegeven parameter in een functieobjectje proppen en nadien weer uitpakken indien dit niet nodig bleek vraagt toch wel wat overhead.
Daarom is er het tweede call-mechanisme, waarbij de receiver zeker is dat de parameters in het juiste formaat zijn. Namelijk 'ActionCall'.
Dit mechanisme kan natuurlijk enkel opgeroepen worden indien de compiler zeker weet welke functie aangeroepen wordt. Indien men deze kennis heeft kan men ook zonder meer bepaalde native-functions inline genereren. (begin is bijvoorbeeld een zeer sterke troef)
Dit leid tot volgende opbouw van de compiler. (slide, snapgfx)
ter illustratie: Het quicksort example had 118 classen nodig indien er geen ActionCall gebruikt werd. Na het gebruik van de action-call bleven er nog maar 31 classen over. En na het inline genereren van begin/if/until & while schoten er nog maar 10 over.
Om deze informatie bij te houden dacht ik eerst scope/lifetime informatie bij te houden om te zien wanneer en waar variabelen gedefinieerd zijn en dergelijke. Wat blijkt: Ik kan geen lifetime-data bijhouden, de compiler kan zelfs niet zeggen in welke volgorde de environments benadert zullen worden. Bekijk daartoe volgende voorbeeldje:
Het enige waar de compiler wel zeker van kan zijn is welke acties mogelijk uitgevoerd zullen worden op environments. Mogelijkheden zijn
read_name (variable reference)
write_name (assignment)
define_name (defines like a:1 of a(b,c):b+c)
call_name (function reference)
Daarom de volgende interface tot environments
Nu kan een definitie worden gegeven voor : 'een variabele is gekend' : Een variabele is 'gekend' in een bepaalde environment, op het ogenblik dat de variabelenaam geen herdefinitie heeft in hoger gelegen environments.
Voor functies kan deze definitie nog wat verbeterd worden naar: 'een functiereference is gekend als de variabelenaam, (in die envioronment) nergens een assignment/functiedefinitie ondergaat.
begin(
reverse(a(),b(),c(),d(),e()):
begin(e(),d(),c(),b(),a()),
reverse(
display(a+b),
a:=1,
b:=2,
a:b,
b:23,
display('first executed')),
display(a))
/***************************************************************************/
/**
**/
/**
F.R.A.M.E.S
**/
/**
**/
/***************************************************************************/
/*
een frame is een voorstelling van de levensloop van een variabelenaam in
*
ene bepaalde envioronment */
struct
_frm_
{String name;
/* de naam van een frame.
strcmp(namefrm1, namefrm2)==0
* a.s.a namefrm1==namefrm2 */
int framenr;
/* FrameNr beschrijft waar de
frame voor zal komen in de
* environment */
_ENV_ env;
/* is een pointer naar de
environment waarin deze frame
* voorkomt */
struct flags
{int read : 1;
/* gezet, indien de variabele
uitgelezen wordt. Dit wil niet
* noodzakelijk zeggen dat de
variabele ook hier gedefinieerd
* is */
int native : 2;
/* zegt of de variabele
gedefinieerd is
* als een native function is */
int called : 3;
/* zegt of de bewuste naam gecalled
wordt. Hier zou ik
* onderscheid kunnen maken
tussen wat voor soort call
* (bv normalcall, applycall, en
enventuele anderen) maar dit
* doe ik niet. */
int parameter : 4;
/* Zegt of deze frame een
parameter is.*/
int parameterlst : 5;
/* Zegt of deze frame een
volledige parameterlijst voorstelt.
* Indien dat het geval is MOET
framenr nadien op 0 staan. */
int written : 6;
/* Zegt of de variabele ooit
beschreven is, los van het feit
* dat de variabele hier al dan
niet gedefinieerd is.
* table assignment wordt ook
bij written gevoegd */
int defined : 7;
/* de variabele wordt in deze
environmpent gedefinieerd, al
* de definities aan de
variabele staan opgegeven in de
* DefineList*/
} flags;
Plist DefineList;
/* een lijst van eventueel
nuttige expressies die ooit in de
* definitie van de
variabele voorkomen */
Plist CallList;
/* een lijst van al de
RFF-expressies die deze variabele
* callen */
};
typedef
struct _frm_ *_FRM_;
_FRM_
_frm_create_(String name, _ENV_ env);
/* creert een frame met
variabelenaam 'name', in de
* gegeven environment */
#define
_frm_valid_(frm) (frm && frm->name && frm->env)
/* check om te zien of het wel
een geldige frame is */
#define
_frm_env_(frm) (frm->env)
/* opvragen van de environment.
Deze is altijd gedefinieerd */
#define
_frm_name_(frm) (frm->name)
/* popvragen van de framename.
Deze is
* altijd gedefinieerd */
#define
_frm_set_framenr_(frm,nr) (frm->framenr=nr)
#define
_frm_framenr_(frm) (frm->framenr)
/* zetten en lezen van het
framenummer op */
#define
_frm_mark_read_(frm) (frm->flags.read=1)
#define
_frm_read_(frm) (frm->flags.read)
/* zetten en lezen van de read-flag
*/
#define
_frm_mark_written_(frm) (frm->flags.written=1)
#define
_frm_written_(frm) (frm->flags.written)
/* zetten en lezen van de
'write' flag */
#define
_frm_mark_called_(frm) (frm->flags.called=1)
#define
_frm_called_(frm) (frm->flags.called)
#define
_frm_foreach_call_(frm,func,common)
l_foreach((frm)->CallList,(func),(common))
#define
_frm_add_called_(frm, rffexp) l_add((frm)->CallList,(rffexp));
/* zetten en lezen van de
'called' flag */
#define
_frm_mark_parameter_(frm) (frm->flags.parameter=1)
#define
_frm_parameter_(frm) (frm->flags.parameter)
/* zetten en lezen van de
'parameter' flag */
#define
_frm_mark_parameterlst_(frm) (frm->flags.parameterlst=1)
#define
_frm_parameterlst_(frm) (frm->flags.parameterlst)
/* zetten en lezen van de
'parameterlst' flag */
#define
_frm_mark_native_(frm) (frm->flags.native=1)
#define
_frm_native_(frm) (frm->flags.native)
_DFF_
_frm_get_native_definition_(_FRM_ frm);
/* zetten en lezen van de
'native' flag */
#define
_frm_mark_defined_(frm) (frm->flags.defined=1)
#define
_frm_defined_(frm) (frm->flags.defined)
#define
_frm_add_definition_(frm, exp) l_add((frm)->DefineList,(exp))
#define
_frm_add_native_definition_(frm, exp) l_add((frm)->DefineList,(exp))
#define
_frm_foreach_definition_(frm,func,common)
l_foreach((frm)->DefineList,(func),(common))
/* zetten en lezen van de
'defined' flag en toebehoren */
/***************************************************************************/
/**
**/
/**
E.N.V.I.R.O.N.M.E.N.T.S
**/
/**
**/
/***************************************************************************/
/*
een environment is 1-1 gerelateerd ten opzichte van een function
*
definition dus ik vraag mij af of het niet
betere is environments en
*
functiedefinities te laten samenvallen */
struct
_env_
{struct _env_* DefinedIn;
/* DefinedIn beschrijft in
welke environment deze steeds
* gedefinieerd zal worden, bij
de root_env staat DefinedIn
* op NULL */
int size;
/* De grootte van de
environment-array @ runtime, deze is
* pas geldig na een env_close
van de root */
Plist FORlist;
/* een lijst van formele
parameters die eventueel
* gebruikt zullen worden in de
functie. Na een env_close
* is dit een lijst van
gebruikte parameters */
Plist frames;
/* hierin worden frames
opgeslagen. Zolang de environments
* niet gesloten zijn bevatten
deze halfbakken informatie.*/
};
_ENV_
_env_create_(_ENV_ DefinedIn);
#define
_env_definedin_(env) (env->DefinedIn)
/* definieert een nieuwe
environment, die gedefinieerd is in
* DefinedIn. Zet deze op 0 als
dit de root_env moet zijn */
#define
_env_size_(env) (env->size)
#define
_env_set_size_(env,siz) (env->size=siz)
/* opvragen en zetten van de
environment grootte */
#define
_env_foreach_formal_(env,func,common)
l_foreach((env)->FORlist,func,common)
#define
_env_add_formal_(env, formal) l_add(env->FORlist,formal)
/* een formele functieparameter
toevoegen */
#define
_env_add_frame_(env,frm) l_add(env->frames,frm)
#define
_env_firstthat_frm_(env,func,common)
l_firstthat(env->frames,func,common)
#define
_env_foreach_frm_(env,func,common) l_foreach(env->frames,func,common)
/* frame bewerkingen */
/**********************************************************************/
/**
**/
/**
globale
bewerkingen
**/
/**
**/
/**********************************************************************/
extern
Plist function_list;
/* een lijst van alle functies
die gedefinieerd worden */
extern
_ENV_ root_env;
/* de rootenvironment */
void
foreach_env(void (*f)(_ENV_));
struct
LookupResult {
_FRM_ frm; /* de frame die gevonden werd */
int back; /* hoeveel er teruggelopen moet
worden */
};
_FRM_
lookup_frm_in_env(_ENV_ env,String name);
/* zoekt de frame op met naam
'name' in de 'env'
* Hier wordt niet verder
gezocht in DefinedIn en hoger.
*
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 'env'
* Hier wordt niet verder
gezocht in DefinedIn en hoger.
* Als name niet voorkomt wordt
ter stond een frame gecreeert*/
struct
LookupResult next_frm(_FRM_ frm);
/* deze zoekt de volgende frame
op */
struct
LookupResult lookup_frm(_ENV_ env, String name);
/* zoekt de frame op met naam
'name' in de 'env'
* Hier wordt verder gezocht in
DefinedIn en hoger.
* Geeft NULL weer in frm
indien er geen dergelijke frame
* voorkomt */
_FRM_
introduce_name(_ENV_ env, String name);
/* creeert altijd een nieuwe
frame met name 'name'
* en environment 'env'.
* voegt de define-expressie
toe aan de lijst
* Stopt deze in env en geeft
het resultaat weer */
_FRM_
define_name(_ENV_ env, String name);
/* creeert een frame met name
'name' (indien nodig)
* en environment 'env'.
* voegt de define-expressie
toe aan de lijst
* Stopt deze in env en geeft
het resultaat weer */
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.
* Indien er zo geen frame is
zal er prompto 1 worden
* aangemaakt en natuurlijk ook
gemarkeerd als read. */
_FRM_
call_name(_ENV_ env, String name);
/* markeert de frame met naam
'name' as beeing called.
* Indien er zo geen frame is
zal er prompto 1 worden
* aangemaakt en natuurlijk ook
gemarkeerd als 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 */