---

Findes der en god Win32 C++ -compiler som har tail recursion-
eliminering? Skal virke på virtuelle metoder. Skal bruges til at
skrive en trådet fortolker. Må selvfølgelig gerne være gratis.

(Jeg har lige konstateret at Borlands C++ builder ikke duer.)

ON/***Fjern sneglen fra min svaradresse***

---

"Ole Nielsby" <ole.nielsby@snailmail.dk> wrote in message
news:3c3e94e0$0$35541$edfadb0f@dspool01.news.tele.dk...
>
> Findes der en god Win32 C++ -compiler som har tail recursion-
> eliminering? Skal virke på virtuelle metoder. Skal bruges til at
> skrive en trådet fortolker. Må selvfølgelig gerne være gratis.

Kan du give et lille eksempel på hvad du ønsker at lave, og gerne lidt om
hvilke designovervejelser der ligger.
Vær opmærksom på at virtuelle metoder ofte afholder compilerne fra at lave
optimeringer som eller kan være nyttige - f.eks. inlining.

Venlig hilsen

Mogens Hansen

---

"Mogens Hansen" <mogens_h@dk-online.dk> writes:
Hale rekursion er meget anvendt inden for funktionsprogrammering.
Det bygger på, at hvis vi har en rekursiv funktion, hvor resultatet er
resultatet af det rekursive kald, så kaldes denne halerekursiv.
Halerekursive funktioner har den egenskab at det er (for dem som skriver oversættere),
let at omskrive til en løkke, hvorved man sparer overhead ved funktionskald.


Det kan let indses ved at se på en definition af pow:

1) Den simple rekursive version

int pow( int x, int n )
{
return x * pow( x, n - 1 );
}

2) En halerekursiv funktion:

int pow( int x, int n, int result = 1 )
{
if( n = 0 )
return result;
else
return pow( x, --n, result * x );
}


3) som nemt oversættes til en løkke:

int pow( int x, int n )
{
int result = 1;
while( n-- )
result *= x;
return result;
}

Nu er eksemplet måske lidt søgt(det er de færreste som ikke selv ville lave løkken),
men jeg syntes det er okay til at forklare hvad halekaldsrekursion er.

Så vidt jeg har forstået er halekaldsrekursion-optimering når oversætteren er snild nok til at omskrive 2) til 3)

Med hensyn til virtuelle funktioner, så kan jeg ikke lige umiddelbart se at der skulle være noget
problem med at lave den optimering på disse, da den jo kan foregå inde i selve kroppen af funktionen,
hvorfor det ikke burde gøre det umuligt at kombinere disse to ting.

Men umiddelbart syntes jeg at denne optimering er mest brugbar i funktionsprogrammering.. I den imperative
verden kan vi jo selv bare skrive løkken.. så er spørgsmålet jo bare om den hale-rekursive version er lettere
at forstå end den omskrevne løkke..
hvis man ser på ovenstående eksempel virker løkken helt sikkert som den er den klareste..

Men det vil vel vise sig, hvis der findes en oversætter til C++ med den optimering, så er der vel
nogen som der syntes at det er brugbart :)

mvh
Jonas

---

"Jonas Meyer Rasmussen" <meyer@alvis.diku.dk> wrote in message
news:xb7wuypjc9p.fsf@alvis.diku.dk...
> "Mogens Hansen" <mogens_h@dk-online.dk> writes:

> Hale rekursion er meget anvendt inden for funktionsprogrammering.
> Det bygger på, at hvis vi har en rekursiv funktion, hvor resultatet er
> resultatet af det rekursive kald, så kaldes denne halerekursiv.


Den er jeg naturligvis med på.
Men det kan have mange anvendelser, og hvor meget der optimeres afhænger af
anvendelsen.
Jeg har selv brugt det med Borland C++Builder (som spørgsmålet drejede som
om), hvor det er blevet optimeret pænt.
Det er jo ikke ensbetydende med at den kan optimere alle situationer eller
at andre ikke gør det bedre.
Derfor er det ikke muligt (for mig ihvertfald) at give hjælp uden flere
detaljer.

>
> 2) En halerekursiv funktion:
>
> int pow( int x, int n, int result = 1 )
> {
> if( n = 0 )

Du mener sikkert
if (n == 0)
^^

et godt råd: skriv så vidt muligt konstanter på højre side, så fanger
compileren den slags fejl:
if(0 == n)



Microsoft Visual C++ V6.0 og Intel C++ V5.0 laver pænt dit eksempel om til
en løkke.
Borland C++Builer V5.0 gør ikke.

Et lignende, men anderledes, eksempel:

#include <iostream>

template <int n>
inline int pow(int x)
{
return x*pow<n-1>(x);
}

template <>
inline int pow<1>(int x)
{
return x;
}

int square(int x)
{
return pow<2>(x);
}

int cube(int x)
{
return pow<3>(x);
}

int main(int argc, char* argv[])
{
// Call square to prevent all calculations from being
// compile-time computed
std::cout << square(10) << '\n'
<< cube(10);

return 0;
}

Det bliver perfekt (ikke en løkke men en sekvens af multiplikationer)
optimeret med Borland C++Builder V5.0, og det er også et eksempel på tail
recursion.
Det bliver bare udført på compile-time i stedet for run-time.

>
> Med hensyn til virtuelle funktioner, så kan jeg ikke lige umiddelbart se
at der skulle være noget
> problem med at lave den optimering på disse, da den jo kan foregå inde i
selve kroppen af funktionen,
> hvorfor det ikke burde gøre det umuligt at kombinere disse to ting.
>

Det er sikkert ikke umuligt at kombinere.
Omvendt er det simpelt at konstruere et eksempel, hvor det vil give
problemer.
Compileren kan jo ikke vide hvilken konkret funktion der skal kaldes og
dermed transformere den om til en løkke.

F.eks. bliver

#include <iostream>

class calc
{
public:
virtual int pow(int x, int n, int result = 1)
{
if(0 == n)
return result;
return pow(x, --n, result * x);
}
};

int square(int x)
{
return calc().pow(x, 2);
}

int cube(int x)
{
return calc().pow(x, 3);
}

int main(int argc, char* argv[])
{
// Call square to prevent all calculations from being
// compile-time computed
std::cout << square(10) << '\n'
<< cube(10);

return 0;
}

hverken optimeret af Intel C++ eller Microsoft C++.
Jeg kan heller ikke umiddelbart se hvordan det skulle kunne lade sig gøre.
Omvej følgende eksempel:

#include <iostream>

class calc
{
public:
virtual int pow(int x, int n, int result = 1)
{
if(0 == n)
return result;
return pow(x, --n, result * x);
}
};

class fast_calc : public calc
{
virtual int pow(int x, int n, int /*result*/ = 1)
{
return x*n; // not correct - but fast!!!
}
};


inline int pow( int x, int n, int result = 1 )
{
if( 0 == n)
return result;
else
return pow( x, --n, result * x );
}

int square(int x)
{
return calc().pow(x, 2);
}

int cube(int x)
{
return calc().pow(x, 3);
}

int foo(int x)
{
return fast_calc().calc::pow(x, 10);
}

int main(int argc, char* argv[])
{
// Call square to prevent all calculations from being
// compile-time computed
std::cout << foo(10);

return 0;
}

som tydeligere viser hvorfor det formodentligt ikke kan lade sig gøre.
Det at man er inden i en virtuel metode, viser ikke _entydigt_ at den
dynamiske type af objektet er den klasse som den virtuelle metode tilhører.
Der kan laves flere eksempler på det samme.

Venlig hilsen

Mogens Hansen

---

"Mogens Hansen" <mogens_h@dk-online.dk> wrote in message
news:3c3eeb79$1@lxcs1.manbw.dk...
>
> "Jonas Meyer Rasmussen" <meyer@alvis.diku.dk> wrote in message
> news:xb7wuypjc9p.fsf@alvis.diku.dk...
> > "Mogens Hansen" <mogens_h@dk-online.dk> writes:
>
> > Hale rekursion er meget anvendt inden for funktionsprogrammering.
> > Det bygger på, at hvis vi har en rekursiv funktion, hvor resultatet er
> > resultatet af det rekursive kald, så kaldes denne halerekursiv.
>
>
> Den er jeg naturligvis med på.
> Men det kan have mange anvendelser, og hvor meget der optimeres afhænger
af
> anvendelsen.
> Jeg har selv brugt det med Borland C++Builder (som spørgsmålet drejede som
> om), hvor det er blevet optimeret pænt.
> Det er jo ikke ensbetydende med at den kan optimere alle situationer eller
> at andre ikke gør det bedre.
> Derfor er det ikke muligt (for mig ihvertfald) at give hjælp uden flere
> detaljer.

Okay, så misforstod jeg vist.

>
> >
> > 2) En halerekursiv funktion:
> >
> > int pow( int x, int n, int result = 1 )
> > {
> > if( n = 0 )
>
> Du mener sikkert
> if (n == 0)
> ^^

ak ja.

>
> et godt råd: skriv så vidt muligt konstanter på højre side, så fanger
> compileren den slags fejl:
> if(0 == n)

Ja, jeg har hørt det før, men af en eller anden grund forsvinder det alt for
hurtigt igen.


> Det er sikkert ikke umuligt at kombinere.
> Omvendt er det simpelt at konstruere et eksempel, hvor det vil give
> problemer.
> Compileren kan jo ikke vide hvilken konkret funktion der skal kaldes og
> dermed transformere den om til en løkke.

Når vi snakker virtuelle metoder har den vel en peger til funktionen..
kunne man ikke forestille sig at funktionen internt var skrevet om?

> hverken optimeret af Intel C++ eller Microsoft C++.
> Jeg kan heller ikke umiddelbart se hvordan det skulle kunne lade sig gøre.

Jeg kan godt se dit argument, men jeg tror ikke helt jeg forstår hvorfor den
ikke kan.

[kodeeksempel 3 klip]
> som tydeligere viser hvorfor det formodentligt ikke kan lade sig gøre.

Hvordan det, jeg forstår ikke helt?

> Det at man er inden i en virtuel metode, viser ikke _entydigt_ at den
> dynamiske type af objektet er den klasse som den virtuelle metode
tilhører.

Jeg kan godt forstå at det er umuligt hvis funktionen selv benytter sig af
virtuelle funktioner,
men hvis funktionen er triviel, så kan jeg ikke helt se hvad problemet er?

mvh
Jonas

---

"Jonas Meyer Rasmussen" <meyer_remove_@diku.dk> wrote in message
news:a1n3bv$khd$1@eising.k-net.dk...
> "Mogens Hansen" <mogens_h@dk-online.dk> wrote


> > Compileren kan jo ikke vide hvilken konkret funktion der skal kaldes og
> > dermed transformere den om til en løkke.
>
> Når vi snakker virtuelle metoder har den vel en peger til funktionen..
> kunne man ikke forestille sig at funktionen internt var skrevet om?
>

Hvordan ?
Kan du give et eksempel ?

> > hverken optimeret af Intel C++ eller Microsoft C++.
> > Jeg kan heller ikke umiddelbart se hvordan det skulle kunne lade sig
gøre.
>
> Jeg kan godt se dit argument, men jeg tror ikke helt jeg forstår hvorfor
den
> ikke kan.
>

Kan du forklare hvad det er du ikke forstår ?
Eller hvorfor du mener at det burde kunne transformeres ?

> [kodeeksempel 3 klip]
> > som tydeligere viser hvorfor det formodentligt ikke kan lade sig gøre.
>
> Hvordan det, jeg forstår ikke helt?
>

Det "rekursive" kald i "calc::pow" kalder måske sig selv og måske en anden
funktion - f.eks. "fast_calc::pow". Det vides ikke på compile-time i
"calc::pow", men skal bestemmes på run-time, og derfor er der ingen
transformation.

> > Det at man er inden i en virtuel metode, viser ikke _entydigt_ at den
> > dynamiske type af objektet er den klasse som den virtuelle metode
> tilhører.
>
> Jeg kan godt forstå at det er umuligt hvis funktionen selv benytter sig af
> virtuelle funktioner,
> men hvis funktionen er triviel, så kan jeg ikke helt se hvad problemet er?
>

Triviel på hvilken måde ?
Hvis funktionen er virtuel, og kalder sig selv rekursivt, kan man ikke bare
transformere funktionen. Det kan jo være at det rekursive kald i
virkeligheden går til en helt anden funktion, sådan som jeg viste i mit
tredie (?) eksempel.

Venlig hilsen

Mogens Hansen

---

Okay, ved nærmere eftertanke forstår jeg hvad du mener, netop ud fra dit
eksempel
3 hvor det åbenbart ikke fungerer..
Jeg var i tvivl om 3. eksempel virkede( var usikker på hvad du mente ), og
antog derfor at det virkede, da jeg ikke havde indset hvorfor det ikke kunne
lade sige gøre.

Men så for at omformulere min påstand, så ville jeg tro at det skulle være
muligt, at foretage optimeringen i klasser som der ikke er andre klasser der
nedarver fra...
Når vi er i de klasser så ved vi vel altid at "den dynamiske type af
objektet er den klasse som den virtuelle metode tilhører"...
Eller det er måske heller ikke sandt?

mvh Jonas

---

"Jonas Meyer Rasmussen" <meyer_remove_@diku.dk> wrote in message
news:a1n9pr$nv6$1@eising.k-net.dk...
> Okay, ved nærmere eftertanke forstår jeg hvad du mener, netop ud fra dit
> eksempel
> 3 hvor det åbenbart ikke fungerer..
> Jeg var i tvivl om 3. eksempel virkede( var usikker på hvad du mente ), og
> antog derfor at det virkede, da jeg ikke havde indset hvorfor det ikke
kunne
> lade sige gøre.
>

Det virker i den henseende at det compilerer og kører, som jeg umiddelbart
ville forvente:

"calc::pow" kaldes 1 gang, som så kalde "fast_calc::pow" kaldes 1 gang.

Det regner naturligvis forkert - men det er også meningen.
Det illustrerer i øvrigt det gode gamle design-princip: "et program der ikke
skal virke kan gøres vilkårligt effektivt" :)

Det væsentlige ved 3. eksempel var at man inde i en virtuel metode _ikke_
umiddelbart _ved_ hvilken dynamisk (eller præcis) type objektet er af.

Hvis du slår optimeringen til, så læg de to klasser og test-programmet i 3
separate filer, for at undgå urealistiske optimeringer (inlining af
"calc::pow").

> Men så for at omformulere min påstand, så ville jeg tro at det skulle være
> muligt, at foretage optimeringen i klasser som der ikke er andre klasser
der
> nedarver fra...

Hvad er pointen i at have virtuelle metoder, hvis det ikke bliver brugt i et
arve-hieraki ?
Compileren ved normalt ikke på kode-genereringstidspunktet for een klasse
vide om der findes afledte klasser. Så kan de ikke basere kode-genereringen
på en antagelse om at der ikke findes afledte klasser.
Der findes muligtvis undtagelser som f.eks. IBM Visual C++ V4.0 og V5.0 og
Microsoft Visual C++ .NET.
Det oprindelige spørgsmål, sagde jo også at det skulle virke med virtuelle
metoder, og mit svar var at det ofte vil afholde compilerne fra at lave
optimeringer som eller kan være nyttige (som f.eks. transformation
tail-recursion funktioner).
Det udsagn holder vist stadig.

> Når vi er i de klasser så ved vi vel altid at "den dynamiske type af
> objektet er den klasse som den virtuelle metode tilhører"...
> Eller det er måske heller ikke sandt?
>

Nej - det er _ikke_ sandt.
Fat en compiler og en debugger og single-step gennem mit 3. eksempel - hvis
du har lyst.
Et andet almindeligt eksempel er at en virtuel metode først kalder
bases-klassens funktion, og derefter gør noget mere selv.

<ikke compileret kode>

#include <typeinfo>
#include <cassert>

class base
{
public:
virtual void foo(void);
};

class derived : public base
{
public void foo(void);
};

void base::foo(void)
{
// Is the dynamic _garantied_ to be "base" ?
// No !!!
// When called from "derived::foo"
assert(typeid(*this) == typeid(base)); // could easy fail !!!

// ...
}

void derived::foo(void)
{
base::foo();
// do something more
}

<ikke compileret kode/>

Venlig hilsen

Mogens Hansen

---

"Mogens Hansen" <mogens_h@dk-online.dk> wrote in message
news:a1nfbd$2ji7$1@news.cybercity.dk...
> Det virker i den henseende at det compilerer og kører, som jeg umiddelbart
> ville forvente:
Ja, jeg var uklar i min formulering.
med at "virke", mente jeg om oversætteren optimerede det.

> Det regner naturligvis forkert - men det er også meningen.
> Det illustrerer i øvrigt det gode gamle design-princip: "et program der
ikke
> skal virke kan gøres vilkårligt effektivt" :)
Det må jeg nok sige :)

> Det væsentlige ved 3. eksempel var at man inde i en virtuel metode _ikke_
> umiddelbart _ved_ hvilken dynamisk (eller præcis) type objektet er af.
>
> Hvis du slår optimeringen til, så læg de to klasser og test-programmet i 3
> separate filer, for at undgå urealistiske optimeringer (inlining af
> "calc::pow").
>
> > Men så for at omformulere min påstand, så ville jeg tro at det skulle
være
> > muligt, at foretage optimeringen i klasser som der ikke er andre klasser
> der
> > nedarver fra...
>
> Hvad er pointen i at have virtuelle metoder, hvis det ikke bliver brugt i
et
> arve-hieraki ?

Jeg ville have et arve hieraki, men hvori der var en klasse som ingen
nedarvede fra.. det jeg manglede at indse var at oversætteren ikke
(ihvertfald ikke trivielt)
kan opdage hvornår man har sådan en klasse
ganske som du skriver nedenfor

> Nej - det er _ikke_ sandt.
> Fat en compiler og en debugger og single-step gennem mit 3. eksempel -
hvis
> du har lyst.
Ja, min misforståelse igen. jeg har kørt det og det virker ganske som
forventet(den optimerer det ikke).


Til gengæld tror jeg at jeg har fundet en løsning på problemet, det virker
ihvertfald med VC.NET.

Hvis man nu bare implementerer den funktion som skal halekalds optimeres som
en privat funktion, så
kan oversætteren fint håndtere det...
således:

class calc
{
public:
virtual int pow(int x, int n )
{
return ppow( x, n, 1 );
}
private:
int ppow( int x, int n, int result )
{
if( n == 0 )
return result;
return ppow( x, --n, result * x );
}
};

Det kræver at programmøren skal tænke og selv skrive den på denne form,
men skal man allgivel ikke det hvis man laver funktioner hvor denne her
optimering kan spille ind.


mvh Jonas

---

Jeg skrev:
> kan opdage hvornår man har sådan en klasse
> ganske som du skriver nedenfor

det som jeg referer nedenfor blev vist sakset.

---

"Jonas Meyer Rasmussen" <meyer_remove_@diku.dk> wrote in message
news:a1q25e$eb1$1@eising.k-net.dk...

>
> Til gengæld tror jeg at jeg har fundet en løsning på problemet, det virker
> ihvertfald med VC.NET.
>

Jeg vil også tro at det virker med Visual C++ V6.0 og Intel C++.

> Hvis man nu bare implementerer den funktion som skal halekalds optimeres
som
> en privat funktion, så
> kan oversætteren fint håndtere det...
> således:
>
> class calc
> {
> public:
> virtual int pow(int x, int n )
> {
> return ppow( x, n, 1 );
> }
> private:
> int ppow( int x, int n, int result )
> {
> if( n == 0 )
> return result;
> return ppow( x, --n, result * x );
> }
> };
>
> Det kræver at programmøren skal tænke og selv skrive den på denne form,
> men skal man allgivel ikke det hvis man laver funktioner hvor denne her
> optimering kan spille ind.
>

Netop.
Det var også den mulighed jeg tænkte på. (jeg var ikke hjemme i går, så jeg
nåede ikke at poste det).
Bemærk dog at den løsning ikke er ækvivalent med det eksempel hvor pow
kaldes sig selv rekursiv. Netop derfor kan compileren ikke tillade sig at
lave transformationen.
Hvis man er i tvivl om hvorvidt det er ækvivalent, så prøv mit tidligere
eksempel med kaldet
int foo(int x)
{
return fast_calc().calc::pow(x, 10);
}
og se om opførslen er ændret.

En væsentlig designparameter er hvor meget compile-time dynamik og run-time
dynamik man har behov for. Det er ikke trivielt, men det er en nøgle til
væsentlige design overvejelser og god performance.

F.eks.:
1. "n" er compile-time statisk. Her vil en compile-time statisk løsning med
f.eks. templates være optimal, som jeg viste i
int square(int x)
{
return pow<2>(x);
}

2. "n" er run-time dynamisk. Her vil den løsning som du viste oprindeligt
være optimal.

3. "n" er run-time dynamisk, og resultatet afhænger af een dynamiske type i
et arvehieraki. Her vil den løsning som du viste med een virtuel metode, der
kalder en anden ikke-virtuel, inlinet recursiv metode, formodentlig være
optimal.

4. "n" er run-time dynamisk, og resultatet afhænger af flere dynamsike typer
i et arvehieraki. Her vil en løsning med en virtuel metode, der rekursivt
kaldes sig selv formodentlig være optimal. Og man må så leve med at man
afskærer compileren fra at transformere funktionen.

Jo mere run-time dynamik man har behov for, des langsommere kører
programmer.
Det er jo egentlig også rimeligt.
Performance mæssigt er en given løsning kun sub-optimal, såfremt der er
implementeret mere run-time dynamik en problemet kræver.

Se bogen
Multi-Paradigm DESIGN for C++
James O. Coplien
ISBN 0-201-82467-1
for en god gennemgang af design overvejelser af denne art.


Venlig hilsen

Mogens Hansen

---

"Mogens Hansen" <mogens_h@dk-online.dk> skrev den 11-Jan-02:

> et godt råd: skriv så vidt muligt konstanter på højre side, så fanger
> compileren den slags fejl:
> if(0 == n)

Jeg synes personligt at et bedre råd er slet ikke at bruge værdien af
tildelinger, og så i øvrigt slå den advarsel til, som fortæller når
man gør det alligevel.

Og du mener vist "[...] konstanter på venstre side [...]" .


Anders.

---

"Anders Melchiorsen" <anders@kalibalik.dk> wrote in message
news:m2vge72n3v.fsf@dolle.kalibalik.dk...
> "Mogens Hansen" <mogens_h@dk-online.dk> skrev den 11-Jan-02:
>
> > et godt råd: skriv så vidt muligt konstanter på højre side, så fanger
> > compileren den slags fejl:
> > if(0 == n)
>
> Jeg synes personligt at et bedre råd er slet ikke at bruge værdien af
> tildelinger, og så i øvrigt slå den advarsel til, som fortæller når
> man gør det alligevel.
>

Generelt foretrækker jeg konstruktioner, så eventuelle fejl viser sig så
åbentlyst, tidligt og automatisk som muligt under udvikling:
1. Compile-time
2. Link-time
3. Run-time (f.eks. med assert og værktøjer som CodeGuard)

> Og du mener vist "[...] konstanter på venstre side [...]" .
>

Naturligvis.

Venlig hilsen

Mogens Hansen

---

"Mogens Hansen" <mogens_h@dk-online.dk> skrev:

> Generelt foretrækker jeg konstruktioner, så eventuelle fejl viser sig så
> åbentlyst, tidligt og automatisk som muligt under udvikling:
> 1. Compile-time
> 2. Link-time
> 3. Run-time (f.eks. med assert og værktøjer som CodeGuard)

Hvis du mener at det er for uautomatisk at skulle aktivere "resultat
af tildeling brugt som sandhedsværdi" advarslen, så er "konstanter på
venstre side" naturligvis bedre end intet. Advarslen har dog sine
fordele, da den virker med to lvalues, uanset rækkefølgen.

Desuden mener jeg at det er mere læsbart når man kun udnytter enten
sideeffekt eller værdi af et udtryk; så risikerer man ikke at læseren
overser den ene af delene.



Anders.

---

Mogens Hansen <mogens_h@dk-online.dk> skrev:

> "Ole Nielsby" <ole.nielsby@snailmail.dk> wrote in message
> news:3c3e94e0$0$35541$edfadb0f@dspool01.news.tele.dk...
> >
> > Findes der en god Win32 C++ -compiler som har tail recursion-
> > eliminering? Skal virke på virtuelle metoder. Skal bruges til at
> > skrive en trådet fortolker. Må selvfølgelig gerne være gratis.
>
> Kan du give et lille eksempel på hvad du ønsker at lave, og gerne
> lidt om hvilke designovervejelser der ligger.

Det drejer sig om en fortolker til et stakløst programmeringssprog,
nærmere bestemt en kommende version af mit eget PILS design.

Den nuværende PILS-fortolker er skrevet i assembler. Med det
nuværende design så jeg ingen anden mulighed for at få en effektiv
fortolker - den betjener sig af stakken på en måde der simpelthen
ikke lader sig beskrive i C++ eller tilsvarende sprog.

(Bl.a. fordi PILS laver tail recursion-eliminering ved hjælp af
noget der minder om Prologs ! (cut)-operator.)

Siden jeg skrev den, har jeg bestemt mig for nogle ændringer i
designet - og fået en idé der vil gøre det praktisk muligt at skrive
en hurtig fortolker i et oo-sprog (sandsynligvis hurtigere end det
nuværende assemblerprogram) - forudsat at compileren kan lave
tail recursion-eliminering.

Sprogets udførelsesmekanisme kommer til at bestå i tilstands-
transformationer. Hver tilstand har et navn og nogle parametre
(altså et funktionskald), og afhængigt af parameterværdierne
fører den til en ny tilstand, og så fremdeles.

Den enkleste og mest effektive realisering af dette - både
beskrivelsesmæssigt og udføringsmæssigt - er at repræsentere
tilstande som metodekald.

Et eksempel på hvordan virtuelle metoder kan speede fortolkeren op:

En stedse tilbageværende tilstand vil være:

evaluate(expression, scope, continuation)

eller, i OO-syntax (jeg ved godt det ikke er C++, jeg er ikke stiv i
dette sprog):

expression.evaluate(scope, continuation)

Lad expression være +(x, 1)

(skrives i PILS som x + 1; jeg bruger ovenstående notation her for at
tydeliggøre strukturen.)

Dette udtryk er en node med 3 elementer: +, x og 1.

Når en node med tre elementer samles (af PILS parseren eller af en
programgenererende stump PILS kode), dannes et objekt af typen
Node3 eller en subklasse af denne (styret af en virtuel metode
"createNode3" i første element).

Node3::evaluate siger: tolk alle tre elementer og anvend derefter
funktionen på de to andre.

Men noden +(x, 1) repræsenteres ved en subclass af Node3,
hvis evaluate-metode siger: tolk 2. element og læg 1 til.

(Måden det gøres på er en tand mere kompliceret end beskrevet:
da PILS i den nye version bliver stakløst, foregår det ved at et
increment-led hægtes på continuation, hvorefter tolkning af
2. element igangsættes ved et tail-rekursivt kald. Continuation
har forskellige virtuelle metoder til at modtage integers, strings
etc., og der skal laves noget ruskomsnusk for at nedbringe
omkostningerne ved alle de dimser der indsættes i continuation
undervejs...)

> Vær opmærksom på at virtuelle metoder ofte afholder compilerne
> fra at lave optimeringer som eller kan være nyttige - f.eks. inlining.

Virtuelle metoder er ingen hindring for tail recursion-eliminering.

Tail recursion vil sige at metoden slutter med et kald til en anden
metode.

En "dum" compiler vil generere et call, efterfulgt af et return.

En "klog" compiler vil mufle lidt rundt med parametrene og
generere et jump.

At call/jump-instruktionen går via en v-table, er ikke afgørende,
selvom det forhindrer visse andre optimeringer, specielt omkring
stack frames.

ON/***Fjern sneglen fra min svaradresse***

---

"Ole Nielsby" <ole.nielsby@snailmail.dk> wrote in message
news:3c3f8633$0$274$edfadb0f@dspool01.news.tele.dk...
>

<snip beskrivelse af problem>

Tak for beskrivelsen.
Jeg kan desværre ikke forstå problemet og den tænkte løsning tilstrækkeligt
præcist til at komme med et præcist råd.
Derfor bliver det lidt mere generelt.

> > Vær opmærksom på at virtuelle metoder ofte afholder compilerne
> > fra at lave optimeringer som eller kan være nyttige - f.eks. inlining.
>
> Virtuelle metoder er ingen hindring for tail recursion-eliminering.
>
> Tail recursion vil sige at metoden slutter med et kald til en anden
> metode.
>
> En "dum" compiler vil generere et call, efterfulgt af et return.
>
> En "klog" compiler vil mufle lidt rundt med parametrene og
> generere et jump.
>
> At call/jump-instruktionen går via en v-table, er ikke afgørende,
> selvom det forhindrer visse andre optimeringer, specielt omkring
> stack frames.

Kan du give et eksempel på en konstruktion, som du mener bør kunne optimeres
?

Som det har været diskutteret i denne tråd, mener jeg at virtuelle metoder
nemt kan forhindre compilere i at lave ellers nyttige optimeringer. En god
mulig løsning er den som Jonas Meyer Rasmussen viste, med en virtuel metode,
der kalder videre til en ikke-virtuel, inlinet recursiv metode, hvor
transformationen så kan lade sig gøre.

En del af nøglen til løsningen er formodentlig en omhyggelig analyse af hvor
der er behov for run-time dynamik, og implementere netop det der er behov
for. Lad resten være run-time statisk.

Dit oprindelige spørgsmål gik også på compilere, som kunne generere bedre
kode end Borland C++Builder.
Som det er nævnt i denne tråd er Visual C++ V6.0, Visual C++ .NET og Intel
C++ V5.0 i stand til at lave tail recursion-eliminering (i de eksempler der
har været nævnt).
Min erfaring er at såvel Visual C++ som Intel C++ generelt (men naturligvis
afhængig af koden) generer kode der kører et par gange hurtigere end Borland
C+Builder.
Intel C++ udmærker sig ved at have en vældig god C++ implementering. Den er
imidlertid ikke gratis (en trial kan downloades), og er nemmest at have med
at gøre inde fra Visual C++ IDE'et, som heller ikke er gratis.
Man kunne også prøve med gcc - den er gratis. Jeg ved ikke hvilke
optimeringer den er i stand til at lave.


Venlig hilsen

Mogens Hansen

---

Mogens Hansen <mogens_h@dk-online.dk> skrev:

> "Ole Nielsby" <ole.nielsby@snailmail.dk> wrote in message
> news:3c3f8633$0$274$edfadb0f@dspool01.news.tele.dk...
> >
>
> <snip beskrivelse af problem>
>
> Tak for beskrivelsen.
> Jeg kan desværre ikke forstå problemet og den tænkte løsning
tilstrækkeligt
> præcist til at komme med et præcist råd.
> Derfor bliver det lidt mere generelt.
>
> > > Vær opmærksom på at virtuelle metoder ofte afholder compilerne
> > > fra at lave optimeringer som eller kan være nyttige - f.eks. inlining.
> >
> > Virtuelle metoder er ingen hindring for tail recursion-eliminering.
> >
> > Tail recursion vil sige at metoden slutter med et kald til en anden
> > metode.
> >
> > En "dum" compiler vil generere et call, efterfulgt af et return.
> >
> > En "klog" compiler vil mufle lidt rundt med parametrene og
> > generere et jump.
> >
> > At call/jump-instruktionen går via en v-table, er ikke afgørende,
> > selvom det forhindrer visse andre optimeringer, specielt omkring
> > stack frames.
>
> Kan du give et eksempel på en konstruktion, som du mener bør
> kunne optimeres?

Der bliver tale om en baseklasse med nogle hundrede virtuelle
metoder og nogle hundrede subklasser. (Det er helt i orden at der
genereres 500KB V-tables.)

Alle implementationer af alle metoderne slutter - direkte eller
indirekte - med et nyt virtuelt kald. Der returneres først når
beregningen er færdig og kontrollen går til operativsystemet.

Jeg vil ikke skrive en doktorafhandling om hvorfor jeg har
valgt den organisering af koden. Men jeg har gode grunde
til det.

Optimeringen er sagtens teknisk mulig.

I det tilfælde hvor parametrene overføres i registre og der ikke
genereres stack frames, er den faktisk triviel: der genereres en
JMP i stedet for en CALL efterfulgt af RET.

Hvis der er en stack frame, skal den pilles ned før tail-kaldet.

Der er et problem i tilfælde hvor adressen på en lokal
variabel har været brugt i et procedurekald. Men det er
ikke værre end at man kan programmere sig udenom.

> En del af nøglen til løsningen er formodentlig en omhyggelig
> analyse af hvor der er behov for run-time dynamik, og
> implementere netop det der er behov for. Lad resten være
> run-time statisk.

Behovet for run time-dynamik er stort, fordi der er tale om
en fortolker hvis opførsel hele tiden styres af de data den
har fat i. Ideen er at bruge OO-konstruktionerne i C++ til
at lave en tabelstyret fortolker.

> Dit oprindelige spørgsmål gik også på compilere, som kunne
> generere bedre kode end Borland C++Builder.
>
> Min erfaring er at såvel Visual C++ som Intel C++ generelt
> (men naturligvis afhængig af koden) generer kode der kører
> et par gange hurtigere end Borland C+Builder.

Véd du hvordan det ligger med at compilere "normale" win32-
programmer med VC.NET compileren???

> Intel C++ udmærker sig ved at have en vældig god C++
> implementering. Den er imidlertid ikke gratis (en trial kan
> downloades), og er nemmest at have med at gøre inde fra
> Visual C++ IDE'et, som heller ikke er gratis.

Taget til overvejelse.

> Man kunne også prøve med gcc - den er gratis. Jeg ved ikke hvilke
> optimeringer den er i stand til at lave.

Efter hvad jeg fik ud af en google-søgning, laver den kun optimeringen
når en statisk funktion kalder sig selv. Der snakkes i krogene om at
forbedre den så den kan fungere som mellemstation for compilere til
funktionelle sprog, men det har vist halvlange udsigter.

I mellemtiden vil jeg tjekke Aonix' Ada-compiler...

ON/***Fjern sneglen fra min svaradresse***

---

"Ole Nielsby" <ole.nielsby@snailmail.dk> wrote in message
news:3c41c429$0$89108$edfadb0f@dspool01.news.tele.dk...
>
> Véd du hvordan det ligger med at compilere "normale" win32-
> programmer med VC.NET compileren???
>

Lige et hurtigt svar inden jeg læser resten.
Visual C++ .NET kan sagtens lave normale Win32 programmer.
De andre sprog fra Microsoft (Visual Basic .NET, C# og J#) kan ikke.
Hvis du bruger Visual Studio .NET Release Candidate er installation af Win32
SDK _ikke_ slået til som default, og det er formodentlig nødvendigt at have
for at lave Win32 programmer.

Venlig hilsen

Mogens Hansen

---

"Ole Nielsby" <ole.nielsby@snailmail.dk> writes:

> Findes der en god Win32 C++ -compiler som har tail recursion-
> eliminering? Skal virke på virtuelle metoder. Skal bruges til at
> skrive en trådet fortolker. Må selvfølgelig gerne være gratis.

Bemærk lige at der er forskel på om en compiler _kan_ gøre det, og om
den _garanterer_ at det sker. En C(++) compiler vil typisk have en
række tommelfingerregler for hvornår det kan betale sig (lavet ud fra
typisk C/C++ kode), og hvis tingene bliver for komplicerede dropper
den bare optimeringen.

Det betyder at de compilere ikke direkte kan bruges som
"mellemstation" for sprog der _garanterer_ halekaldsoptimering, som
f.eks. Scheme. Selv om det går godt i de fleste tilfælde.