---

Hej
Jeg er nybegynder i c, og er stødt på noget meget frustrerende.
Når jeg skriver i++; eller i--; så lægger den to til ved i++;, og trækker to
fra ved i--;
Og den gør det samme ved i=i+1; og i=i-1; hvad kan der være galt, det er
ikke en løkke af nogen art, så den kan ikke gentage sig selv.
MVH Janus Olsen

---

"Janus Olsen" <janus@basicelectronics.dk> wrote

> Når jeg skriver i++; eller i--; så lægger den to til ved i++;, og trækker
to
> fra ved i--;

Hmm...
Det lyder underligt.

Hvordan kan du se, at det er det der sker ?
Prøv lige at poste den mindste stump hvor du kan se den opførsel, så er det
nemmere at hjælpe.

Venlig hilsen

Mogens Hansen

---

Mogens Hansen wrote:
> "Janus Olsen" <janus@basicelectronics.dk> wrote
>
>> Når jeg skriver i++; eller i--; så lægger den to til ved i++;, og
>> trækker to fra ved i--;
>
> Hmm...
> Det lyder underligt.
>
> Hvordan kan du se, at det er det der sker ?
Jeg lavede en printf for at kunne se det.
> Prøv lige at poste den mindste stump hvor du kan se den opførsel, så
> er det nemmere at hjælpe.

Her er koden, variablen s står kun et sted i hele programmet, tro mig jeg
har gennemsøgt det mange gange
z++ gør det ikke, men r++ gør det også, men det gør ikke så meget med den,
som i også kan se i koden herunder.

x=getchar();
r=0;
while (z<(a[y][0])+2)

{
if (x==a[y][z])

{
ord[t][(z-1)]=x;
r++;
}
z ++;

}
if (r==0)
{
s++;
}

goto begin;

return 0;
}

MVH Janus Olsen

---

> x=getchar();
> r=0;
> while (z<(a[y][0])+2)
>
> {
> if (x==a[y][z])
>
> {
> ord[t][(z-1)]=x;
> r++;
> }
> z ++;
>
> }
> if (r==0)
> {
> s++;
> }
>
> goto begin;
>
> return 0;
> }

Det ovenstående er jævn uforståeligt, prøv at rydde op i koden og se om det
ikke løser dit problem.

---

Rasmus Christian Kaae skrev:

>Det ovenstående er jævn uforståeligt, prøv at rydde op i koden og se om det
>ikke løser dit problem.

Enig. Jeg tænkte på om ikke den der goto kunne være synderen. Det
kan være at den bevirker en gentagelse. Men det er umuligt at
vide ud fra den kode der blev postet.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

"Janus Olsen" <janus@basicelectronics.dk> wrote

[8<8<8<]
> Her er koden, variablen s står kun et sted i hele programmet, tro mig jeg
> har gennemsøgt det mange gange
> z++ gør det ikke, men r++ gør det også, men det gør ikke så meget med den,
> som i også kan se i koden herunder.

Det er ikke nemt at se noget ud fra den postede kode.
Prøv at lave et lille, _komplet_ eksempel, som du mener har den opførsel du
beskriver.
Forklar eventuelt lidt om hvad du havde tænkt dig koden skal lave.

Iøvrigt regnes det almindeligvis for en _dårlig_ idé at bruge goto.
Kan du forklare hvorfor der ikke findes bedre konstruktion ?

Venlig hilsen

Mogens Hansen

---

Janus Olsen wrote:
> Mogens Hansen wrote:
>
>>"Janus Olsen" <janus@basicelectronics.dk> wrote
>>
>>
>>>Når jeg skriver i++; eller i--; så lægger den to til ved i++;, og
>>>trækker to fra ved i--;
>>
>>Hmm...
>>Det lyder underligt.
>>
>>Hvordan kan du se, at det er det der sker ?
>
> Jeg lavede en printf for at kunne se det.
>
>>Prøv lige at poste den mindste stump hvor du kan se den opførsel, så
>>er det nemmere at hjælpe.
>
>
> Her er koden, variablen s står kun et sted i hele programmet, tro mig jeg
> har gennemsøgt det mange gange
> z++ gør det ikke, men r++ gør det også, men det gør ikke så meget med den,
> som i også kan se i koden herunder.
>
> x=getchar();
> r=0;
> while (z<(a[y][0])+2)
>
> {
> if (x==a[y][z])
>
> {
> ord[t][(z-1)]=x;
> r++;
> }
> z ++;
>
> }
> if (r==0)
> {
> s++;
> }
>
> goto begin;
>
> return 0;
> }
Lad mig gætte: s og r er af typen short * (pointer til short)?

/b

---

On Thu, 15 May 2003 01:45:54 +0200, Janus Olsen wrote:

> Når jeg skriver i++; eller i--; så lægger den to til ved i++;, og trækker to
> fra ved i--;

Hm, mon dog; lad os lige se koden engang... :)

/\/\\ads Orbesen Troest

---

--
http://www.basicelectronics.dk
Når service er en selvfølge
"Janus Olsen" <janus@basicelectronics.dk> skrev i en meddelelse
news:b9uker$cjq$1@sunsite.dk...
> Hej
> Jeg er nybegynder i c, og er stødt på noget meget frustrerende.
> Når jeg skriver i++; eller i--; så lægger den to til ved i++;, og trækker
to
> fra ved i--;
> Og den gør det samme ved i=i+1; og i=i-1; hvad kan der være galt, det er
> ikke en løkke af nogen art, så den kan ikke gentage sig selv.
> MVH Janus Olsen
>
>

---

> "Janus Olsen" <janus@basicelectronics.dk> skrev i en meddelelse
> news:b9uker$cjq$1@sunsite.dk...
> > Hej
> > Jeg er nybegynder i c, og er stødt på noget meget frustrerende.
> > Når jeg skriver i++; eller i--; så lægger den to til ved i++;, og
trækker
> to
> > fra ved i--;
> > Og den gør det samme ved i=i+1; og i=i-1;

Det *kan* den ikke, med mindre du har en fejlbehæftet C-compiler;

prøv at indsætte flg. stump i din kode eller i en anden funktion og se.
hvad der sker:

int i = 0;
while (i < 10) i++;
/* her kunne vi have en assert(i == 10); */
printf("%d", i);

hvad kan der være galt, det er
> > ikke en løkke af nogen art, så den kan ikke gentage sig selv.
> > MVH Janus Olsen

Som Bertel skrev, er det meget muligt, at det er GOTO-sætningen,
der er synderen - men nu er jeg jo selv et af de her stilistisk kedelige
mennesker, der mener, at man skal skrive sin kode klart og
forståelig og ikke (læs: ikke, som i "aldrig") bruge GOTO ...

venlig hilsen
Carsten Agger

--
FAKLENS NYHEDSTJENESTE:
http://www.faklen.dk/nyheder

---

Carsten Agger wrote:
> Som Bertel skrev, er det meget muligt, at det er GOTO-sætningen,
> der er synderen - men nu er jeg jo selv et af de her stilistisk kedelige
> mennesker, der mener, at man skal skrive sin kode klart og
> forståelig og ikke (læs: ikke, som i "aldrig") bruge GOTO ...

Hvordan har du det så med setjmp?

--
Jens Axel Søgaard

---

"Jens Axel Søgaard" <usenet@jasoegaard.dk> skrev i en meddelelse
news:3ecf777f$0$76157$edfadb0f@dread11.news.tele.dk...
> Carsten Agger wrote:
> > Som Bertel skrev, er det meget muligt, at det er GOTO-sætningen,
> > der er synderen - men nu er jeg jo selv et af de her stilistisk kedelige
> > mennesker, der mener, at man skal skrive sin kode klart og
> > forståelig og ikke (læs: ikke, som i "aldrig") bruge GOTO ...
>
> Hvordan har du det så med setjmp?
>

Det ved jeg med skam at melde ikke engang hvad er ...
Lad os se: Kernighan and Ritchie, side 254 i min udgave - jo,
den findes! Jeg kan bare ikke rigtig regne ud, hvad den skal bruges
till? Jeg er meget nysgerrig efter at høre det ...

--
FAKLENS NYHEDSTJENESTE:
http://www.faklen.dk/nyheder

---

Carsten Agger wrote:
> "Jens Axel Søgaard" <usenet@jasoegaard.dk> skrev i en meddelelse
> news:3ecf777f$0$76157$edfadb0f@dread11.news.tele.dk...
>
>>Carsten Agger wrote:
>>
>>>Som Bertel skrev, er det meget muligt, at det er GOTO-sætningen,
>>>der er synderen - men nu er jeg jo selv et af de her stilistisk kedelige
>>>mennesker, der mener, at man skal skrive sin kode klart og
>>>forståelig og ikke (læs: ikke, som i "aldrig") bruge GOTO ...
>>
>>Hvordan har du det så med setjmp?
>>
>
>
> Det ved jeg med skam at melde ikke engang hvad er ...
> Lad os se: Kernighan and Ritchie, side 254 i min udgave - jo,
> den findes! Jeg kan bare ikke rigtig regne ud, hvad den skal bruges
> till? Jeg er meget nysgerrig efter at høre det ...

Setjmp udgør sammen med longjmp et par.
Anvendes setjmp siger man "her vil jeg gerne vende tilbage til
på et tidspunkt". Med longjmp kan man så hoppe tilbage til det givne
sted (også med hensyn til omgivelser). Placeringen af longjmp behøver
ikke være i samme funktion som anvendelsen af setjmp. Det er dog kun
tilladt at anvende stedet gemt med setjmp sålænge stakken er intakt.

Man kan tænke på setjmp som en funktion, der laver en etiket,
og på longjmp som et goto.

Men hvad kan det bruges til?

Det kan bruges til ikke-lokal-afslutning. Forestil dig, at du
du er rekursivt er i gang med at undersøge om et af tallene
i dit gigantiske søgetræ er 0. I det øjeblik du finder et
0 ved du, at svaret er ja. Hvis du nøjes med at returnere et ja,
vil niveauet over sige hov det var et ja, så returerner jeg også et ja.
Svaret "Ja" vil altså blive returneret det antal gange træet er højt.

Ville det ikke være smart, hvis man kunne returnere værdien direkte
til det sted, hvor søgeprocessen gik i gang? Det er her setjmp og
longjmp kommer ind i billedet. Inden søgeprocessen startes anvendes
setjmp. Når man har fundet set svar kaldes longjmp, som i et hug
skræller alle rekursionlagene af. ["Stakken poppes"]

Med andre ord, setjmp/longjmp er en form for goto, som har sin
i C har sin berettigelse.

Du kan sammenligne setjmp/longjmp med undtagelser (exceptions),
af andre kaldes de udadrettede fortsættelser. Årsagen er, at man
ikke kan fortryde og springe tilbage igen. Andre sprog udvider
begrebet og gør, at godt kan springe frem og at man kan bruge
samme fortsættelse flere gange (hvilket medfører, at et funktionskald
kan returnere flere gange.

Eventuelle (og der er sikker nogle) unøjagtigheder i min beskrivelse,
kan der rettes op på ved at finde en bog (jeg kan pludselig ikke
huske, hvor meget der står i KR, men det er der jeg har bidt mærke
i konstruktionen).

--
Jens Axel Søgaard

---

> Det kan bruges til ikke-lokal-afslutning. Forestil dig, at du
> du er rekursivt er i gang med at undersøge om et af tallene
> i dit gigantiske søgetræ er 0. I det øjeblik du finder et
> 0 ved du, at svaret er ja. Hvis du nøjes med at returnere et ja,
> vil niveauet over sige hov det var et ja, så returerner jeg også et ja.
> Svaret "Ja" vil altså blive returneret det antal gange træet er højt.
>
> Ville det ikke være smart, hvis man kunne returnere værdien direkte
> til det sted, hvor søgeprocessen gik i gang? Det er her setjmp og
> longjmp kommer ind i billedet. Inden søgeprocessen startes anvendes
> setjmp. Når man har fundet set svar kaldes longjmp, som i et hug
> skræller alle rekursionlagene af. ["Stakken poppes"]

øhh.. det er så liige nøjagtig hvad alle compilere med respekt for sig selv
gør -- netop at identificere tail-calls, faktisk er det en af de simpleste
optimeringer der kan laves i en compiler.

det du skriver er noget ala:

int f(int j) {
if (j==100) return -1;
else return f(j--);
}

her er det åbenlyst at du ikke har lyst til at benytte ydereligere på
stakken i de rekursive gennemløb da 'return f(j--)' er det sidste der skal
udføres i den pågældende rekursion og compileren kan herefter snildt
optimere push/pops på stakken væk, netop som du beskriver det.

---

Rasmus Christian Kaae wrote:
>>Det kan bruges til ikke-lokal-afslutning. Forestil dig, at du
>>du er rekursivt er i gang med at undersøge om et af tallene
>>i dit gigantiske søgetræ er 0. I det øjeblik du finder et
>>0 ved du, at svaret er ja. Hvis du nøjes med at returnere et ja,
>>vil niveauet over sige hov det var et ja, så returerner jeg også et ja.
>>Svaret "Ja" vil altså blive returneret det antal gange træet er højt.
>>
>>Ville det ikke være smart, hvis man kunne returnere værdien direkte
>>til det sted, hvor søgeprocessen gik i gang? Det er her setjmp og
>>longjmp kommer ind i billedet. Inden søgeprocessen startes anvendes
>>setjmp. Når man har fundet set svar kaldes longjmp, som i et hug
>>skræller alle rekursionlagene af. ["Stakken poppes"]
>
>
> øhh.. det er så liige nøjagtig hvad alle compilere med respekt for sig selv
> gør -- netop at identificere tail-calls, faktisk er det en af de simpleste
> optimeringer der kan laves i en compiler.

Mjoh. Det kommer jo lidt an dels på sammenhængen (hvilket sprog) og
på, hvordan man definerer et, hvordan du definerer et halerekusivt
kald. [Du har fundet en af mine kæpheste.]

[Eksempel på konkret anvendelse af longjmp/setjmp længere
nede, hvis man synes den lange smøre om halerekursion er
kedelig]

Min opfattelse er, at hvis den værdi en funktion returnerer kommer
fra et funktionskald, så kaldes det funktionskald halerekursivt.

Eksempel:

/* sum(n, a) = 0 + 1 + ... n + a */
int sum(int n, int a) {
if (n==0)
return a;
else
return sum( n-1, a+1 ); /* halerekursivt kald */
}

Lad os kalde et funktionskald aktivt, hvis det endnu ikke
har returneret. Et programmeringssprog har ægte halerekursion,
hvis det tillader et ubegrænset antal aktive halekald ad gangen,
med et begrænset pladsforbrug. Dvs. pladsforbruget må
ikke stige i takt med antallet af aktive halekald. Pladsegenskaben
medfører, at man iterative beregninger kan beskrives rekursivt. [1]

Ovenstående lidt kringlede beskrivelse gør, at man kan tale
om halerekursion uden at bringe den implementationsdetalje,
at funktionskald ofte implementeres vha en stak.

At få en C-oversætte til at oversætte ovenstående til
en løkke er ikke så vanskelig. Men livet er ikke nemt.

int foo(int &n) {
int l;

l = *n;
return g(&l); /* halerekursivt kald til g */
}

Når foo kaldes oprettes der en lokal variabel l.
Da der gives en pointer til l videre til g, kan man
ikke fjerne l fra stakken inden g kaldes. Skal
C-oversætteren derfor oversætte kaldet g(&l) som
et halerekursivt kald skal værdien a l gemmes et andet
sted end på stakken, og først i det øjeblik, der ikke
findes variable indeholdende værdier, som refererer til
l (direkte eller indirekte) kan pladsen l optager frigives.
Uden en garbage collector er det ikke nemt.

[Er der nogen, der ved, hvad GCC gør i praksis?
- jeg gætter på den bruger et almindeligt funktionskald
i stedet]


Anyways, tilbage til træeksemplet og til setjmp/longjmp.

> det du skriver er noget ala:
>
> int f(int j) {
> if (j==100) return -1;
> else return f(j--);
> }

> her er det åbenlyst at du ikke har lyst til at benytte ydereligere på
> stakken i de rekursive gennemløb da 'return f(j--)' er det sidste der skal
> udføres i den pågældende rekursion og compileren kan herefter snildt
> optimere push/pops på stakken væk, netop som du beskriver det.

Parret setjmp/longjmp kan også benyttes, når de rekursive kald
ikke er halerekursive.

Lad os lave et program, som givet et træ med tal
ganger alle tallene sammen.

int produkt(træ t) {
if (tomt(t))
return 1
else if (træ_med_et_element(t)
return t.element
else
return produkt(t.venstre) * produkt(t.højre);
/* NB: Her er kaldene til produkt ikke halerekursive,
det er kaldene til * derimod.
Den stakkels oversætter er altså chanceløs.
*/
}

Se nu på dette træ:

/\
/ \
1 /\
/ \
/ \
/\ /\
2 0 3 4

Når vi opdager nullet, så ved vi, at det er spild af tid at
at regne på resten af træet. Vi ved nemlig, at det samlede
produkt giver nul.

Vi laver derfor denne modifikation:

int svar;
int færdig; /* 0=ja, 1=nej */

int produkt(træ t) {
færdig = 0;
setjmp "X-marks-the-spot";
if (færdig==1)
return svar;
else
return produkt2(t);
}

int produkt2(træ t) {
if (tomt(t))
return 1;
else if (træ_med_et_element(t) {
if (t.element==0) {
svar=0;
færdig=1;
longjmp "X-marks-the-spot";
}
else
return t.element;
}
else
return produkt2(t.venstre) * produkt2(t.højre);
/* NB: Her er kaldene til produkt ikke halerekursive,
det er kaldene til * derimod. */
}

Jeg er for doven til at slå den rigtige syntaks for setjmp/longjmp,
men meningen fremgår forhåbenligt klart.

Når longjmp benyttes, tager det konstant tid at returnere til
stedet mærket med X (i modsætning til for eksempel tid proportional
med højden af bladet med det fundne nul).


[1] De teoretisk interesserede kan finde en formel beskrivelse
af halerekursion og pladsforbrug i:

"Proper Tail Recursion and Space Efficiency."
af William Clinger

Proceedings of the 1998 ACM Conference on Programming Language
Design and Implementation. June 1998.

<ftp://ftp.ccs.neu.edu/pub/people/will/tail.ps.gz>

--
Jens Axel Søgaard

---

> Mjoh. Det kommer jo lidt an dels på sammenhængen (hvilket sprog) og
> på, hvordan man definerer et, hvordan du definerer et halerekusivt
> kald. [Du har fundet en af mine kæpheste.]

Øh, der findes da kun én definition på tail-position, at det så har
forskellige anvendelser i et funktionelt sprog end i et almindeligt
imperativt sprog er vel bare en sproglig feature.

> Eksempel:
>
> /* sum(n, a) = 0 + 1 + ... n + a */
> int sum(int n, int a) {
> if (n==0)
> return a;
> else
> return sum( n-1, a+1 ); /* halerekursivt kald */
> }

hvordan adskiller dit eksempel sig fra mit? bortset fra at dit program gør
noget mere fornuftigt end mit...


> At få en C-oversætte til at oversætte ovenstående til
> en løkke er ikke så vanskelig. Men livet er ikke nemt.

det er jo netop *ikke* en løkke man ønsker, kald-stakken skal/vil stadig
blive opbygget dog bliver den ikke traverseret når du på et tidspunkt
returnerer gennem en række tail-position kald.

> int foo(int &n) {
> int l;
>
> l = *n;
> return g(&l); /* halerekursivt kald til g */
> }

jeg forstår ikke pointen med den kode her, det er hverken c eller c++,
desuden kan jeg stadig ikke se hvad din pointe er. tail-position kan KUN
være i slutningen af et statement (læs: return).


> Når foo kaldes oprettes der en lokal variabel l.
> Da der gives en pointer til l videre til g, kan man
> ikke fjerne l fra stakken inden g kaldes. Skal
> C-oversætteren derfor oversætte kaldet g(&l) som
> et halerekursivt kald skal værdien a l gemmes et andet
> sted end på stakken, og først i det øjeblik, der ikke
> findes variable indeholdende værdier, som refererer til
> l (direkte eller indirekte) kan pladsen l optager frigives.
> Uden en garbage collector er det ikke nemt.

Hvorfor? stakken bliver da ikke smadret bare fordi du tilføjer en ny
stack-frame tilhørende det indeværende rekursionsniveau.

> [Er der nogen, der ved, hvad GCC gør i praksis?
> - jeg gætter på den bruger et almindeligt funktionskald
> i stedet]

Ja, ligesom så mange andre compilere -- tilføjer en stack-frame til stakken.

> Parret setjmp/longjmp kan også benyttes, når de rekursive kald
> ikke er halerekursive.

Ja? Mit gæt er at setjmp/longjmp er en primitiv udgave a scheme's call/cc,
som kan en masse fancy-features men tilgengæld obfuskerer koden ganske
meget.


> Lad os lave et program, som givet et træ med tal
> ganger alle tallene sammen.
>
> int produkt(træ t) {
> if (tomt(t))
> return 1
> else if (træ_med_et_element(t)
> return t.element
> else
> return produkt(t.venstre) * produkt(t.højre);
> /* NB: Her er kaldene til produkt ikke halerekursive,
> det er kaldene til * derimod.
> Den stakkels oversætter er altså chanceløs.
> */
> }
>
> Se nu på dette træ:
>
> /\
> / \
> 1 /\
> / \
> / \
> /\ /\
> 2 0 3 4
>
> Når vi opdager nullet, så ved vi, at det er spild af tid at
> at regne på resten af træet. Vi ved nemlig, at det samlede
> produkt giver nul.

hvad med almindelig kode-strategi (uden brug af kryptiske jumps som
obfuskerer koden):
....
else {
int v = produkt(t.venstre);
if (v) return v*produkt(t.højre);
else return 0;
}

et voila, ikke mere hurlumhej dér (de to kald du har til produkt-funktionen
er ikke i tail-position, det er derimod multiplikations operatoren!!)

>
> Vi laver derfor denne modifikation:

[snip .. noget usandsynlig grimt kode]

> Jeg er for doven til at slå den rigtige syntaks for setjmp/longjmp,
> men meningen fremgår forhåbenligt klart.

Ja, det er ok.

> Når longjmp benyttes, tager det konstant tid at returnere til
> stedet mærket med X (i modsætning til for eksempel tid proportional
> med højden af bladet med det fundne nul).

Se min simple ændring, som både er pænere og nemmere at overskue end det du
foreslår.

> [1] De teoretisk interesserede kan finde en formel beskrivelse
> af halerekursion og pladsforbrug i:
>
> "Proper Tail Recursion and Space Efficiency."
> af William Clinger
>
> Proceedings of the 1998 ACM Conference on Programming Language
> Design and Implementation. June 1998.
>
> <ftp://ftp.ccs.neu.edu/pub/people/will/tail.ps.gz>

samtidig vil jeg nok anbefale dig at læse en bog om det at skrive en
compiler, det virker som om du ikke har styr på hvordan en stak opfører sig.

---

Rasmus Christian Kaae wrote:
>>Mjoh. Det kommer jo lidt an dels på sammenhængen (hvilket sprog) og
>>på, hvordan man definerer et, hvordan du definerer et halerekusivt
>>kald. [Du har fundet en af mine kæpheste.]
>
>
> Øh, der findes da kun én definition på tail-position, at det så har
> forskellige anvendelser i et funktionelt sprog end i et almindeligt
> imperativt sprog er vel bare en sproglig feature.

Hvad med

int f(int n) {
return g() && h();
}

int f(int n) {
return g() || h();
}

Er kaldene til h() halerekursive?



>>Eksempel:
>>
>>/* sum(n, a) = 0 + 1 + ... n + a */
>>int sum(int n, int a) {
>> if (n==0)
>> return a;
>> else
>> return sum( n-1, a+1 ); /* halerekursivt kald */
>>}
>
>
> hvordan adskiller dit eksempel sig fra mit? bortset fra at dit program gør
> noget mere fornuftigt end mit...

Det giver en naturlig overgang til at betragte produkter.

>>At få en C-oversætte til at oversætte ovenstående til
>>en løkke er ikke så vanskelig. Men livet er ikke nemt.

> det er jo netop *ikke* en løkke man ønsker,

Det er en løkke jeg vil have, og hvis oversætteren er god
er det også en løkke jeg får.

> kald-stakken skal/vil stadig blive opbygget

Der vil ikke blive tilføjet stack frames, man kan genbruge
den gamle.

> dog bliver den ikke traverseret når du på et tidspunkt
> returnerer gennem en række tail-position kald.

Så har programmer oversat af den oversætter ikke
pladsegenskaben, nemlig at der kan være et ubegrænset
antal aktive halekald med et begrænset pladsforbrug.
Hvis der tilføjes en stakframe ved hvert halerekursivt
kald vil pladsforbruget stige i takt med antallet af
halerekursive kald.

>>int foo(int &n) {
>> int l;
>>
>> l = *n;
>> return g(&l); /* halerekursivt kald til g */
>>}

> jeg forstår ikke pointen med den kode her, det er hverken c eller c++,
> desuden kan jeg stadig ikke se hvad din pointe er. tail-position kan KUN
> være i slutningen af et statement (læs: return).

Et selvhalerekursivt kald fra f til f kan oversættes
så den gamle stackframe genbruges. Man propper argumenterne
til det nye kald af f ned i den gamle stakframe. Derpå
laver man et hop til begyndelsen af kroppen. Man får
dermed en løkke.

Pointen med ovenstående eksempel er, at kaldet til g
ikke kan genbruge den gamle stakframe for f. Årsagen
er at den lokale variabel l også ligger på stakken
og derfor vil blive overskrevet.

Man har så to muligheder, nemlig at tilføje en ny
stackframe for g [men så stiger pladsforbruget]
eller først at flytte indholdet af variablen l hen et
andet sted, for derefter at genbruge den gamle stackframe
til det nye kald af g [og så stiger pladsforbrugetikke].
Der er dog en løs ende ved den anden løsning, for hvornår
skal pladsen for den lokale variabel l frigivet? Det er et
ikke-trivielt spørgsmål.

En mere radikal løsning er at bruge separate opbevaringer
for activation frames og lokale variable. Det løser problemet
med overskrivningen af den gamle stackframe for f, men
hjælper ikke på problemet med deallokeringen af l.
Her vil man nok være tvunget til at indføre en garbage collector.


>>Når foo kaldes oprettes der en lokal variabel l.
>>Da der gives en pointer til l videre til g, kan man
>>ikke fjerne l fra stakken inden g kaldes. Skal
>>C-oversætteren derfor oversætte kaldet g(&l) som
>>et halerekursivt kald skal værdien a l gemmes et andet
>>sted end på stakken, og først i det øjeblik, der ikke
>>findes variable indeholdende værdier, som refererer til
>>l (direkte eller indirekte) kan pladsen l optager frigives.
>>Uden en garbage collector er det ikke nemt.
>
>
> Hvorfor? stakken bliver da ikke smadret bare fordi du tilføjer en ny
> stack-frame tilhørende det indeværende rekursionsniveau.

Jeg vil netop undgå at tilføje en ny stack-frame.

>>[Er der nogen, der ved, hvad GCC gør i praksis?
>> - jeg gætter på den bruger et almindeligt funktionskald
>> i stedet]
>
>
> Ja, ligesom så mange andre compilere -- tilføjer en stack-frame til stakken.

Sikker?

>>Parret setjmp/longjmp kan også benyttes, når de rekursive kald
>>ikke er halerekursive.
>
>
> Ja? Mit gæt er at setjmp/longjmp er en primitiv udgave a scheme's call/cc,

Det er lidt i samme stil, men da setjmp-stakken kun kan bruges en gang,
så er setjmp/longjmp væsentligt mindre fleksibel. Parret minder mere
om exceptions.

> som kan en masse fancy-features men tilgengæld obfuskerer koden ganske
> meget.

Call/cc er svær at forstå, men brugen kan sagtens gøres pæn ved at
kombinere den med andre af Schemes muligheder.

>>Lad os lave et program, som givet et træ med tal
>>ganger alle tallene sammen.
>>
>>int produkt(træ t) {
>> if (tomt(t))
>> return 1
>> else if (træ_med_et_element(t)
>> return t.element
>> else
>> return produkt(t.venstre) * produkt(t.højre);
>> /* NB: Her er kaldene til produkt ikke halerekursive,
>> det er kaldene til * derimod.
>> Den stakkels oversætter er altså chanceløs.
>> */
>>}
>>
>>Se nu på dette træ:
>>
>> /\
>> / \
>> 1 /\
>> / \
>> / \
>> /\ /\
>> 2 0 3 4
>>
>>Når vi opdager nullet, så ved vi, at det er spild af tid at
>>at regne på resten af træet. Vi ved nemlig, at det samlede
>>produkt giver nul.
>
>
> hvad med almindelig kode-strategi (uden brug af kryptiske jumps som
> obfuskerer koden):
> ...
> else {
> int v = produkt(t.venstre);
> if (v) return v*produkt(t.højre);
> else return 0;
> }
>
> et voila, ikke mere hurlumhej dér (de to kald du har til produkt-funktionen
> er ikke i tail-position, det er derimod multiplikations operatoren!!)

Så er kaldet af produkt i

int v = produkt(t.venstre)

ikke halerekursivt. Det betyder, at hvis man har fundet
et 0 i venstre undertræ vil man ikke returnere til det oprindelige
kald af produkt, men et af de rekursive "underkald". Hvis man
er uheldig kan man få en serie af sådanne ikke-halerekursive
underkald som har samme længde som højden af træet. Hvis
træet er dybt vil denne løsning derfor være langsommer
end setjmp/longjmp-løsningen.

>>Vi laver derfor denne modifikation:
>
>
> [snip .. noget usandsynlig grimt kode]

Men det er ikke min skyld

>>Jeg er for doven til at slå den rigtige syntaks for setjmp/longjmp,
>>men meningen fremgår forhåbenligt klart.
>
>
> Ja, det er ok.
>
>
>>Når longjmp benyttes, tager det konstant tid at returnere til
>>stedet mærket med X (i modsætning til for eksempel tid proportional
>>med højden af bladet med det fundne nul).
>
> Se min simple ændring, som både er pænere og nemmere at overskue end det du
> foreslår.

Ja, men den har et andet tidsforbrug.

--
Jens Axel Søgaard

---

"Jens Axel Søgaard" <usenet@jasoegaard.dk> wrote in message
news:3ed0b3c9$0$76121$edfadb0f@dread11.news.tele.dk...
> Rasmus Christian Kaae wrote:
> >>Mjoh. Det kommer jo lidt an dels på sammenhængen (hvilket sprog) og
> >>på, hvordan man definerer et, hvordan du definerer et halerekusivt
> >>kald. [Du har fundet en af mine kæpheste.]
> >
> >
> > Øh, der findes da kun én definition på tail-position, at det så har
> > forskellige anvendelser i et funktionelt sprog end i et almindeligt
> > imperativt sprog er vel bare en sproglig feature.
>
> Hvad med
>
> int f(int n) {
> return g() && h();
> }
>
> int f(int n) {
> return g() || h();
> }
>
> Er kaldene til h() halerekursive?

Jeg tror det er på tide at du begynder at studere sproget lidt mere før du
forsætter denne tråd. NEJ kaldet til g og h er ikke i tail-position, der i
mod er kaldet til && og || operatorne i tail-position.


> > det er jo netop *ikke* en løkke man ønsker,
>
> Det er en løkke jeg vil have, og hvis oversætteren er god
> er det også en løkke jeg får.

Nej og nej. Du vil have en kald-stak hvor du kan indsætte et flag som du så
kan hoppe tilbage til på et givent tidspunkt.. altså ikke en løkke.

> Der vil ikke blive tilføjet stack frames, man kan genbruge
> den gamle.

Det er så ret compiler-specifikt det der.

> > dog bliver den ikke traverseret når du på et tidspunkt
> > returnerer gennem en række tail-position kald.


> >>int foo(int &n) {
> >> int l;
> >>
> >> l = *n;
> >> return g(&l); /* halerekursivt kald til g */
> >>}
>
> > jeg forstår ikke pointen med den kode her, det er hverken c eller c++,
> > desuden kan jeg stadig ikke se hvad din pointe er. tail-position kan KUN
> > være i slutningen af et statement (læs: return).
>
> Et selvhalerekursivt kald fra f til f kan oversættes
> så den gamle stackframe genbruges. Man propper argumenterne
> til det nye kald af f ned i den gamle stakframe. Derpå
> laver man et hop til begyndelsen af kroppen. Man får
> dermed en løkke.

Ja og nej, du har ret med genbrug og fejl mht. løkke.

> Pointen med ovenstående eksempel er, at kaldet til g
> ikke kan genbruge den gamle stakframe for f. Årsagen
> er at den lokale variabel l også ligger på stakken
> og derfor vil blive overskrevet.

okay, men hvis du vil understrege dine pointer gennem eksempler bør du i det
mindste tage dig tid til at skrive korrekt kode.


> > Hvorfor? stakken bliver da ikke smadret bare fordi du tilføjer en ny
> > stack-frame tilhørende det indeværende rekursionsniveau.
>
> Jeg vil netop undgå at tilføje en ny stack-frame.

Ja, men problemet var vist at dine eksempler ikke var korrekte og du ikke
har styr på hvornår noget er i tail-position.

> >>Parret setjmp/longjmp kan også benyttes, når de rekursive kald
> >>ikke er halerekursive.
> > Ja? Mit gæt er at setjmp/longjmp er en primitiv udgave a scheme's
call/cc,

> Det er lidt i samme stil, men da setjmp-stakken kun kan bruges en gang,
> så er setjmp/longjmp væsentligt mindre fleksibel. Parret minder mere
> om exceptions.

og exceptions kan simuleres med call/cc

> > som kan en masse fancy-features men tilgengæld obfuskerer koden ganske
> > meget.
>
> Call/cc er svær at forstå, men brugen kan sagtens gøres pæn ved at
> kombinere den med andre af Schemes muligheder.

> > hvad med almindelig kode-strategi (uden brug af kryptiske jumps som
> > obfuskerer koden):
> > ...
> > else {
> > int v = produkt(t.venstre);
> > if (v) return v*produkt(t.højre);
> > else return 0;
> > }
> >
> > et voila, ikke mere hurlumhej dér (de to kald du har til
produkt-funktionen
> > er ikke i tail-position, det er derimod multiplikations operatoren!!)
>
> Så er kaldet af produkt i
>
> int v = produkt(t.venstre)
>
> ikke halerekursivt. Det betyder, at hvis man har fundet
> et 0 i venstre undertræ vil man ikke returnere til det oprindelige
> kald af produkt, men et af de rekursive "underkald". Hvis man
> er uheldig kan man få en serie af sådanne ikke-halerekursive
> underkald som har samme længde som højden af træet. Hvis
> træet er dybt vil denne løsning derfor være langsommer
> end setjmp/longjmp-løsningen.

Nu roder du med tail-position igen, kaldene til produkt(venstre) og
produkt(højre) har ALDRIG været i tail-position for funktionen kun for
udtrykket. Faktisk er produkt(t.højre) jo heller ikke i funktionens
tail-position i mit eksempel. Husk at operatorer bare er syntaktisk sukker
for almindelige funktioner.

> Men det er ikke min skyld

joeh

> > Se min simple ændring, som både er pænere og nemmere at overskue end det
du
> > foreslår.
>
> Ja, men den har et andet tidsforbrug.

Nej?

---

Rasmus Christian Kaae wrote:
> "Jens Axel Søgaard" <usenet@jasoegaard.dk> wrote in message
> news:3ed0b3c9$0$76121$edfadb0f@dread11.news.tele.dk...
>
>>Rasmus Christian Kaae wrote:
>>
>>>>Mjoh. Det kommer jo lidt an dels på sammenhængen (hvilket sprog) og
>>>>på, hvordan man definerer et, hvordan du definerer et halerekusivt
>>>>kald. [Du har fundet en af mine kæpheste.]
>>>
>>>
>>>Øh, der findes da kun én definition på tail-position, at det så har
>>>forskellige anvendelser i et funktionelt sprog end i et almindeligt
>>>imperativt sprog er vel bare en sproglig feature.
>>
>>Hvad med
>>
>>int f(int n) {
>> return g() && h();
>>}
>>
>>int f(int n) {
>> return g() || h();
>>}
>>
>>Er kaldene til h() halerekursive?
>
>
> Jeg tror det er på tide at du begynder at studere sproget lidt mere før du
> forsætter denne tråd. NEJ kaldet til g og h er ikke i tail-position, der i
> mod er kaldet til && og || operatorne i tail-position.


Nå. Så er alligevel mere en en definition
Lad os tage return g() && h(). Hvis kaldet af g()
returnerer en sand værdi kaldes funktionen h().
Uanset returværdien af h() er værdien af udtrykket
g() && h() lig med denne værdi. Denne værdi returneres
så af f til det sted X, f blev kaldt fra.

Men det er jo ikke effektivt. I det øjeblik h() kaldes
ved vi, at værdien skal leveres til stedet X. Det er derfor
unødvendigt at returnere værdien først til f og så til X.

Det er naturligvis et *valg* om man opfatter kaldet til
h som værende et kald, der skal optimeres. Derfor er ikke
korrekt, når du siger det er oplagt, hvilke funktionskald
der skal opfattes som halerekursive. Jeg ville klart
forvente, at det blev optimeret.

>>det er jo netop *ikke* en løkke man ønsker,
>>
>>Det er en løkke jeg vil have, og hvis oversætteren er god
>>er det også en løkke jeg får.

> Nej og nej. Du vil have en kald-stak hvor du kan indsætte et flag som du så
> kan hoppe tilbage til på et givent tidspunkt.. altså ikke en løkke.

Der er to grader af optimering. [Som sikkert er årsagen
til at vi snakker forbi hinanden]

Den ene går ud på, at man returnerer direkte til kaldstedet.
Den anden kræver også, at pladsforbruget ikke stiger
proportionalt med antallet af aktive halekald.
[Hvilket jeg eksplicit krævede i starten af tråden]

Den første optimering
er nem at lave, man lader være med at genbruge den
gamle stakramme og kopierer returadressen over i den
nye ramme.

Den anden er straks sværere at implementere.
Hvis pladsforbruget ikke må stige med antallet af
aktive halekald må man *ikke* genbruge den gamle
stakramme. Denne optimering er *ikke* triviel.

Hvis stakrammen genbruges vil en selvrekursiv funktion
med et halerekursivt kald i enden, blive oversat til
en løkke. Så *jo* det er det jeg vil have.

[Jeg gætter på, at du ikke har bidt tilstrækkelig
mærke i mit krav om pladsegenskaben i starten af tråden]

>>Der vil ikke blive tilføjet stack frames, man kan genbruge
>>den gamle.

> Det er så ret compiler-specifikt det der.

Min påstand skal naturligvis ses under forudsætning af,
at det oversatte program besidder pladsegenskaben.

>>>dog bliver den ikke traverseret når du på et tidspunkt
>>>returnerer gennem en række tail-position kald.

>>>>int foo(int &n) {
>>>> int l;
>>>>
>>>> l = *n;
>>>> return g(&l); /* halerekursivt kald til g */
>>>>}

>>>jeg forstår ikke pointen med den kode her, det er hverken c eller c++,
>>>desuden kan jeg stadig ikke se hvad din pointe er. tail-position kan KUN
>>>være i slutningen af et statement (læs: return).
>>
>>Et selvhalerekursivt kald fra f til f kan oversættes
>>så den gamle stackframe genbruges. Man propper argumenterne
>>til det nye kald af f ned i den gamle stakframe. Derpå
>>laver man et hop til begyndelsen af kroppen. Man får
>>dermed en løkke.

> Ja og nej, du har ret med genbrug og fejl mht. løkke.

Se ovenfor.

>>>Hvorfor? stakken bliver da ikke smadret bare fordi du tilføjer en ny
>>>stack-frame tilhørende det indeværende rekursionsniveau.
>>
>>Jeg vil netop undgå at tilføje en ny stack-frame.
>
>
> Ja, men problemet var vist at dine eksempler ikke var korrekte og du ikke
> har styr på hvornår noget er i tail-position.

Såeh.

>>>>Parret setjmp/longjmp kan også benyttes, når de rekursive kald
>>>>ikke er halerekursive.
>>>
>>>Ja? Mit gæt er at setjmp/longjmp er en primitiv udgave a scheme's
>>> call/cc,
>
>
>>Det er lidt i samme stil, men da setjmp-stakken kun kan bruges en gang,
>>så er setjmp/longjmp væsentligt mindre fleksibel. Parret minder mere
>>om exceptions.

> og exceptions kan simuleres med call/cc

Ja, men ikke omvendt.


>> hvad med almindelig kode-strategi (uden brug af kryptiske jumps som
>>> obfuskerer koden):
>>> ...
>>> else {
>>> int v = produkt(t.venstre);
>>> if (v) return v*produkt(t.højre);
>>> else return 0;
>>> }
>>>
>>> et voila, ikke mere hurlumhej dér (de to kald du har til
>>> produkt-funktionen
>>> er ikke i tail-position, det er derimod multiplikations operatoren!!)

>> Så er kaldet af produkt i
>>
>> int v = produkt(t.venstre)
>>
>> ikke halerekursivt. Det betyder, at hvis man har fundet
>> et 0 i venstre undertræ vil man ikke returnere til det oprindelige
>> kald af produkt, men et af de rekursive "underkald". Hvis man
>> er uheldig kan man få en serie af sådanne ikke-halerekursive
>> underkald som har samme længde som højden af træet. Hvis
>> træet er dybt vil denne løsning derfor være langsommer
>> end setjmp/longjmp-løsningen.


> Nu roder du med tail-position igen, kaldene til produkt(venstre) og
> produkt(højre) har ALDRIG været i tail-position for funktionen kun for
> udtrykket.

Jeg tror, du forveksler det indledende "Så" med et "før-og-efter-så."
Det er ment som et "I-så-fald". Det er klart, at det aldrig har
været i haleposition. Det vigtige er at bemærke er at antallet af
aktive kald er proportionalt med højden af træet.

>>>Se min simple ændring, som både er pænere og nemmere at overskue end det
> du foreslår.
>>
>>Ja, men den har et andet tidsforbrug.
>
> Nej?

Hvis din oversætter ikke optimerer noget som helst vil
returneringen af den endelige værdi tage tid proportional
med højden af træet. Løsningen med setjmp/longjmp vil derimod
returnere den endelige værdi i konstant tid.

Hvis din oversætter laver den simple udgave af optimeringen,
vil det også returnere den endelige værdi i konstant tid.
Overvejelsen om tidsforbrug er dermed blevet oversætterafhængig.

--
Jens Axel Søgaard

---

Rasmus Christian Kaae wrote:

> øhh.. det er så liige nøjagtig hvad alle compilere med respekt for
sig > selv gør -- netop at identificere tail-calls, faktisk er det en af de
> simpleste optimeringer der kan laves i en compiler.


> Ja? Mit gæt er at setjmp/longjmp er en primitiv udgave a scheme's call/cc,
> som kan en masse fancy-features men tilgengæld obfuskerer koden ganske
> meget.


> samtidig vil jeg nok anbefale dig at læse en bog om det at skrive en
> compiler, det virker som om du ikke har styr på hvordan en stak opfører sig.

Scheme...oversætter... Hov! Har du haft Danvy? Klikke, klikke. Sørme så.
Han har oversætterkurset igen. Se det er et rigtigt kursus.

Men det betyder også , at du burde vide, at kravet begrænset
pladsforbrug ved et ubegrænset antal aktive halekald påvirker stort set
alle faser af af oversætteren. Mange semantisk korrekte omskrivninger
ødelægger risikerer nemlig at omskrevet et halerekursivt kald til et
ikke-halerekusivt kald - man skal derfor passe meget på under både
desugaring og linearisering.

Jeg synes, derfor det er lidt for flot at sige, at det en simpel
optimering.

Bemærk i øvrigt, at oversættere som ChezScheme i modsætning til
DaimiScheme benytter en stak til at opbevare activation-frames.
Det medfører, at tilstedeværelsen af call/cc ikke påvirker hastigheden
af de programmer, som ikke anvender call/cc. Det er dog ingenlunde
trivielt, at implementere. Før Dybvigs afhandling, troede man ikke
det kunne lade sig gøre effektivt (Dybvig skrev ChezScheme).

--
Jens Axel Søgaard

---

"Jens Axel Søgaard" <usenet@jasoegaard.dk> wrote in message
news:3ed0bd14$0$76135$edfadb0f@dread11.news.tele.dk...
> Rasmus Christian Kaae wrote:
>
> > øhh.. det er så liige nøjagtig hvad alle compilere med respekt for
> sig > selv gør -- netop at identificere tail-calls, faktisk er det en af
de
> > simpleste optimeringer der kan laves i en compiler.
>
>
> > Ja? Mit gæt er at setjmp/longjmp er en primitiv udgave a scheme's
call/cc,
> > som kan en masse fancy-features men tilgengæld obfuskerer koden ganske
> > meget.
>
>
> > samtidig vil jeg nok anbefale dig at læse en bog om det at skrive en
> > compiler, det virker som om du ikke har styr på hvordan en stak opfører
sig.
>
> Scheme...oversætter... Hov! Har du haft Danvy? Klikke, klikke. Sørme så.
> Han har oversætterkurset igen. Se det er et rigtigt kursus.

ja, jeg har haft dOvs hos Danvy og det fag er også den eneste kilde jeg har
som baggrund indenfor compiler-skrivning

> Men det betyder også , at du burde vide, at kravet begrænset
> pladsforbrug ved et ubegrænset antal aktive halekald påvirker stort set
> alle faser af af oversætteren. Mange semantisk korrekte omskrivninger
> ødelægger risikerer nemlig at omskrevet et halerekursivt kald til et
> ikke-halerekusivt kald - man skal derfor passe meget på under både
> desugaring og linearisering.

Omvendt burde du vide hvornår noget er i tail-position Det med
pladsforbruget er også ret forskelligt fra sprog til sprog og compiler til
compiler.

> Jeg synes, derfor det er lidt for flot at sige, at det en simpel
> optimering.

Nej, for det er det -- i hvert fald var det noget vi skulle gøre i dOvs

> Bemærk i øvrigt, at oversættere som ChezScheme i modsætning til
> DaimiScheme benytter en stak til at opbevare activation-frames.
> Det medfører, at tilstedeværelsen af call/cc ikke påvirker hastigheden
> af de programmer, som ikke anvender call/cc. Det er dog ingenlunde
> trivielt, at implementere. Før Dybvigs afhandling, troede man ikke
> det kunne lade sig gøre effektivt (Dybvig skrev ChezScheme).

---

Rasmus Christian Kaae wrote:
> "Jens Axel Søgaard" <usenet@jasoegaard.dk> wrote in message

>>Scheme...oversætter... Hov! Har du haft Danvy? Klikke, klikke. Sørme så.
>>Han har oversætterkurset igen. Se det er et rigtigt kursus.

> ja, jeg har haft dOvs hos Danvy og det fag er også den eneste kilde jeg har
> som baggrund indenfor compiler-skrivning

>>Men det betyder også , at du burde vide, at kravet begrænset
>>pladsforbrug ved et ubegrænset antal aktive halekald påvirker stort set
>>alle faser af af oversætteren. Mange semantisk korrekte omskrivninger
>>ødelægger risikerer nemlig at omskrevet et halerekursivt kald til et
>>ikke-halerekusivt kald - man skal derfor passe meget på under både
>>desugaring og linearisering.

> Omvendt burde du vide hvornår noget er i tail-position Det med
> pladsforbruget er også ret forskelligt fra sprog til sprog og compiler til
> compiler.

Det var så sandelig også derfor jeg specifikt gjorde opmærksom
på, at optimeringen først er "rigtig", hvis pladsegenskaben bliver
overholdt.

>>Jeg synes, derfor det er lidt for flot at sige, at det en simpel
>>optimering.

> Nej, for det er det -- i hvert fald var det noget vi skulle gøre i dOvs

Ja, men jeg tror du groft undervurderer Danvys pædagogiske opdeling
af oversætterens faser samt grundige opremsning af omskrivninger.
Der mange hensyn, der skal tages, når omskrivningerne vælges. Der
er flere muligheder og det kan snildt lade sig gøre at vælge
omskrivninger, som får det oversatte program til at levere korrekt
input, men som forbryder sig mod pladsegenskaben. Hvis du kigger
på diverse Scheme->C oversættere, som oversætter en scheme-funktion
til en tilsvarende C-funktion, og som oversætter et Scheme-funktionskald
med et C-ditto, vil du opdage, at der altid
står, at de ikke er "Proper Tail Recursive", hvilket betyder, at
de oversatte programmer ikke har pladsegenskaben. Man kan derfor
opleve, at programmer som kører fejlfrit i en Scheme-implementation,
som overholder standarden, løber tør for stak plads i en anden,
som ikke har fået implementeret "Proper Tail Recursion" rigtigt.

[Fidusen ved at lave den direkte oversættelse er, at programmerne
ofte bliver særdeles hurtige. [og selvfølgelig findes der også en
alternativ løsning, men den er knap så simpel.]

Summasumarum, det er nemmere at implementere en Scheme-oversætter
rigtigt, end det er at forstå, at man har gjort det rigtigt

--
Jens Axel Søgaard

---

> > Nej, for det er det -- i hvert fald var det noget vi skulle gøre i dOvs

>
> Ja, men jeg tror du groft undervurderer Danvys pædagogiske opdeling
> af oversætterens faser samt grundige opremsning af omskrivninger.
> Der mange hensyn, der skal tages, når omskrivningerne vælges. Der
> er flere muligheder og det kan snildt lade sig gøre at vælge
> omskrivninger, som får det oversatte program til at levere korrekt
> input, men som forbryder sig mod pladsegenskaben. Hvis du kigger
> på diverse Scheme->C oversættere, som oversætter en scheme-funktion
> til en tilsvarende C-funktion, og som oversætter et Scheme-funktionskald
> med et C-ditto, vil du opdage, at der altid
> står, at de ikke er "Proper Tail Recursive", hvilket betyder, at
> de oversatte programmer ikke har pladsegenskaben. Man kan derfor
> opleve, at programmer som kører fejlfrit i en Scheme-implementation,
> som overholder standarden, løber tør for stak plads i en anden,
> som ikke har fået implementeret "Proper Tail Recursion" rigtigt.
>
> Summasumarum, det er nemmere at implementere en Scheme-oversætter
> rigtigt, end det er at forstå, at man har gjort det rigtigt

Tjae, det ved jeg ikke. Vi optimerer de kald der bliver genkendt som i
tail-position og koden virker

Sjovt nok var jeg også 'the VM guy' fra vores gruppe

---

Rasmus Christian Kaae wrote:
>Jens Axel:

>>Ja, men jeg tror du groft undervurderer Danvys pædagogiske opdeling
>>af oversætterens faser samt grundige opremsning af omskrivninger.
>>Der mange hensyn, der skal tages, når omskrivningerne vælges. Der
>>er flere muligheder og det kan snildt lade sig gøre at vælge
>>omskrivninger, som får det oversatte program til at levere korrekt
>>input, men som forbryder sig mod pladsegenskaben.

> Tjae, det ved jeg ikke. Vi optimerer de kald der bliver genkendt som i
> tail-position og koden virker

Hvordan "optimerer"?

Ved kodegenereringen i fase 6 er der ingen problemer med at lave
slutdelen af den omtalte optimering. Problemet er, at alle omskrivninger
i desugaring, linearisering og faktorisering skal sørge for,
at alt ender på rette plads, så den optimering kodegeneratoren
laver bliver simpel. Optimeringen finder altså ikke kun sted ved
kodegenereringen, alle foregående faser påvirkes også.

Sammenlignes med en C-oversætter, er problemet i C, hvor der skal
gøres af de lokale variable.

I DaimiScheme opbevares de lokale variable ikke i "stak"rammen
(læs trærammen), men i den garbage-collectede heap. Selvom et
funktionskald returnerer overlever de lokale variable altså
indtil de er "unreachable" (unålige?). [Man husker, at selvom
et klad har returneret, er det muligt at vende tilbage til
kroppen, hvis der er blevet gemt en fortsættelse vha call/cc]

Den garbage-collector, du har i din VM, er altså en forudsætning
for, at din "simple" optimering bevarer pladsegenskaben.

> Sjovt nok var jeg også 'the VM guy' fra vores gruppe

Ditto - og jeg skrev også kodegeneratoren

--
Jens Axel Søgaard

---

"Jens Axel Søgaard" <usenet@jasoegaard.dk> wrote in message
news:3ed32742$0$97159$edfadb0f@dread12.news.tele.dk...
> Rasmus Christian Kaae wrote:
> >Jens Axel:
>
> >>Ja, men jeg tror du groft undervurderer Danvys pædagogiske opdeling
> >>af oversætterens faser samt grundige opremsning af omskrivninger.
> >>Der mange hensyn, der skal tages, når omskrivningerne vælges. Der
> >>er flere muligheder og det kan snildt lade sig gøre at vælge
> >>omskrivninger, som får det oversatte program til at levere korrekt
> >>input, men som forbryder sig mod pladsegenskaben.
>
> > Tjae, det ved jeg ikke. Vi optimerer de kald der bliver genkendt som i
> > tail-position og koden virker
>
> Hvordan "optimerer"?
>
> Ved kodegenereringen i fase 6 er der ingen problemer med at lave
> slutdelen af den omtalte optimering. Problemet er, at alle omskrivninger
> i desugaring, linearisering og faktorisering skal sørge for,
> at alt ender på rette plads, så den optimering kodegeneratoren
> laver bliver simpel. Optimeringen finder altså ikke kun sted ved
> kodegenereringen, alle foregående faser påvirkes også.

Det er der vel heller ikke nogen der har påstået? Jeg tror ikke jeg har
omtalt andet end compileren.

> Sammenlignes med en C-oversætter, er problemet i C, hvor der skal
> gøres af de lokale variable.

Næh, som jeg lige husker det var det ret forud defineret hvor variablene
skulle proppes hen (environments).

> I DaimiScheme opbevares de lokale variable ikke i "stak"rammen
> (læs trærammen), men i den garbage-collectede heap. Selvom et
> funktionskald returnerer overlever de lokale variable altså
> indtil de er "unreachable" (unålige?). [Man husker, at selvom
> et klad har returneret, er det muligt at vende tilbage til
> kroppen, hvis der er blevet gemt en fortsættelse vha call/cc]

Nej et call/cc smed jo netop en reference til den pågældende
frame/environment ind i kald-stakken hvorefter gc'en ikke slettede den
pågældende frame fordi den netop ikke er inaktiv.

> Den garbage-collector, du har i din VM, er altså en forudsætning
> for, at din "simple" optimering bevarer pladsegenskaben.

Øh? Ja, gc'en er en del af det sprog. Men da lokale variable bliver proppet
på stakken i f.eks. C så kan jeg ikke se ligheden. Alt det der ikke ligger
på stakken er noget brugeren selv har allokeret, som derfor ligger et andet
sted men har evt. en pointer fra stakken.

> > Sjovt nok var jeg også 'the VM guy' fra vores gruppe
>
> Ditto - og jeg skrev også kodegeneratoren

Ok, jeg skrev store dele af vores one-pass desugar

---

Rasmus Christian Kaae wrote:
> "Jens Axel Søgaard" <usenet@jasoegaard.dk> wrote in message

>>Ved kodegenereringen i fase 6 er der ingen problemer med at lave
>>slutdelen af den omtalte optimering. Problemet er, at alle omskrivninger
>>i desugaring, linearisering og faktorisering skal sørge for,
>>at alt ender på rette plads, så den optimering kodegeneratoren
>>laver bliver simpel. Optimeringen finder altså ikke kun sted ved
>>kodegenereringen, alle foregående faser påvirkes også.

> Det er der vel heller ikke nogen der har påstået? Jeg tror ikke jeg har
> omtalt andet end compileren.

Ikke forstået. Dit synspunkt er, at vi taler om en simpel optimering
i C. Mit synspunkt er, at den fulde optimering langtfra er simpel.

Du argumenterer nu med at optimeringen var simpel i jeres Scheme-
oversætter. Jeg påpeger så, at selv i en Scheme-oversætteren er det
en ikke-triviel optimering, da den griber ind i alle faser.

I Scheme kan det lade sig gøre, for garbage-collectoren løser
problemet med de lokale variable. Hvis man ikke har en garbage-
collector bliver problemet med de lokale variable stort set
uløseligt.

>>Sammenlignes med en C-oversætter, er problemet i C, hvor der skal
>>gøres af de lokale variable.

> Næh, som jeg lige husker det var det ret forud defineret hvor variablene
> skulle proppes hen (environments).

Hele pointen er, at de bliver opbevaret separat fra oplysningerne
om hvem kaldte hvem.

>>I DaimiScheme opbevares de lokale variable ikke i "stak"rammen
>>(læs trærammen), men i den garbage-collectede heap. Selvom et
>>funktionskald returnerer overlever de lokale variable altså
>>indtil de er "unreachable" (unålige?). [Man husker, at selvom
>>et klad har returneret, er det muligt at vende tilbage til
>>kroppen, hvis der er blevet gemt en fortsættelse vha call/cc]

> Nej et call/cc smed jo netop en reference til den pågældende
> frame/environment ind i kald-stakken hvorefter gc'en ikke slettede den
> pågældende frame fordi den netop ikke er inaktiv.

Jeg har ikke snakket om hvad call/cc gør. Jeg siger, at man ikke
uden videre kan slette de lokale variable, når en funktion returnerer.
Du kan ikke vide om der er fanget referencer til de lokale variable;
det kan ske ved anvendelse af call/cc men det kan kan også ske
ved at man returnerer værdien af (lambda () x) hvor x er en lokal
variabel i den omliggende funktion.

I C er der ingen skrupler ved at fjerne de lokale variable når
funktionen returnerer. Bruges en pointer til slettet lokal variabel
er man selv ude om det. Det gør naturligt at implementere funktions-
kald vha en stak.

>> Den garbage-collector, du har i din VM, er altså en forudsætning
>> for, at din "simple" optimering bevarer pladsegenskaben.

> Øh? Ja, gc'en er en del af det sprog.

Hvad har det med sagen at gøre. For at lave den fulde optimering
(som du hævder er simpel) er man nødt til at placere de lokale
variable et andet sted end i stakrammen.

Garbage-collection er en løsningsmodel. Har du et andet forslag?

> Ok, jeg skrev store dele af vores one-pass desugar

En på mit hold skrev desugaren i C. Hvem der bare havde kunnet
Scheme dengang. Hvis vi havde kunnet Scheme dengang, ville
vi kunne have skrevet den på under den halve tid.

--
Jens Axel Søgaard

---

"Jens Axel Søgaard" <usenet@jasoegaard.dk> skrev i en meddelelse
news:3ed07e47$0$76145$edfadb0f@dread11.news.tele.dk...
> Carsten Agger wrote:
> > "Jens Axel Søgaard" <usenet@jasoegaard.dk> skrev i en meddelelse
> > news:3ecf777f$0$76157$edfadb0f@dread11.news.tele.dk...
> >
> >>Hvordan har du det så med setjmp?
> >
> > Det ved jeg med skam at melde ikke engang hvad er ...
> > Lad os se: Kernighan and Ritchie, side 254 i min udgave - jo,
> > den findes! Jeg kan bare ikke rigtig regne ud, hvad den skal bruges
> > till? Jeg er meget nysgerrig efter at høre det ...
>
> Setjmp udgør sammen med longjmp et par.
> Anvendes setjmp siger man "her vil jeg gerne vende tilbage til
> på et tidspunkt". Med longjmp kan man så hoppe tilbage til det givne
> sted (også med hensyn til omgivelser). Placeringen af longjmp behøver
> ikke være i samme funktion som anvendelsen af setjmp. Det er dog kun
> tilladt at anvende stedet gemt med setjmp sålænge stakken er intakt.

(...)
Ja, den kan vel bruges henefter GOTOs, men som udgangspunkt ville
jeg nok ikke anvende den. Hvis jeg f.eks. skulle lave en søgning
i et træ og stakkens dybde (og den tid, det tager at poppe den af)
var performance-kritisk, ville jeg nok foretrække at gøre det v.hj.a. en
iterator frem for rekursivt.

Så hvordan har jeg det med setjmp()? Den kan virke smart, men også
farlig i den forstand, at den kan gøre kodens opførsel uberegnelig
og koden svær at læse - og med min egen (praktiske) baggrund i
administrative
systemer har jeg en tendens til at prioritere læselighed over
performance og så lave performanceoptimeringer bagefter baseret
på målinger, hvis behovet viser sig.

vh
Carsten Agger


--
FAKLENS NYHEDSTJENESTE:
http://www.faklen.dk/nyheder

---

Carsten Agger wrote:
> "Jens Axel Søgaard" <usenet@jasoegaard.dk> skrev i en meddelelse
> news:3ed07e47$0$76145$edfadb0f@dread11.news.tele.dk...
>>Carsten Agger wrote:
>>>"Jens Axel Søgaard" <usenet@jasoegaard.dk> skrev i en meddelelse

>>>>Hvordan har du det så med setjmp?

>>>Det ved jeg med skam at melde ikke engang hvad er ...
>>>Lad os se: Kernighan and Ritchie, side 254 i min udgave - jo,
>>>den findes! Jeg kan bare ikke rigtig regne ud, hvad den skal bruges
>>>till? Jeg er meget nysgerrig efter at høre det ...

>>Setjmp udgør sammen med longjmp et par.
>>Anvendes setjmp siger man "her vil jeg gerne vende tilbage til
>>på et tidspunkt". Med longjmp kan man så hoppe tilbage til det givne
>>sted (også med hensyn til omgivelser). Placeringen af longjmp behøver
>>ikke være i samme funktion som anvendelsen af setjmp. Det er dog kun
>>tilladt at anvende stedet gemt med setjmp sålænge stakken er intakt.
>
>
> (...)
> Ja, den kan vel bruges henefter GOTOs, men som udgangspunkt ville
> jeg nok ikke anvende den. Hvis jeg f.eks. skulle lave en søgning
> i et træ og stakkens dybde (og den tid, det tager at poppe den af)
> var performance-kritisk, ville jeg nok foretrække at gøre det v.hj.a. en
> iterator frem for rekursivt.

Du har ret. Hver ting til sin tid. Iteratorteknikken kræver dog,
at den benyttede datastruktur indeholder information om, hvordan
man kommer fra et element til det næste. Det vil ikke være tilfældet
med en simpel implementation af en heap/bunke/hob. Tilføjelsen af en
iterator vil derfor kræve at eksempelvis indsæt og fjern vedligeholder
ekstra information (og kræve mere plads).

> Så hvordan har jeg det med setjmp()? Den kan virke smart, men også
> farlig i den forstand, at den kan gøre kodens opførsel uberegnelig
> og koden svær at læse - og med min egen (praktiske) baggrund i
> administrative
> systemer har jeg en tendens til at prioritere læselighed over
> performance og så lave performanceoptimeringer bagefter baseret
> på målinger, hvis behovet viser sig.

Klart. Det er ikke en konstruktion, man har brug for ret tit.
Den er dog god at have i sin pose med tricks.

Pointen var vel også nærmest, at goto (læs longjmp) enkelte steder har
sin berettigelse - at man ikke altid kan omskrive koden til at benytte
strukturede konstruktioner. Et andet eksempel er ved implementering af
endelige tilstandsmaskiner - hvis jeg husker ret er en del gotoer i kode
frembragt af yacc/bison. [Men jeg er ikke helt sikker].

Hov et tredje eksempel kommer i hu.

Antag, at du anvender et bibliotek, som implementerer træer.
Med biblioteket følger en for_each(t, f) funktion, som for alle
elementer i træet t kalder funktionen f.

Lad os sige at træet har 1.000.000 elementer. Og du er interesseret
i at vide om træer har flere elementer end 10 (der vil selvfølgelig
være en size funktion i et rigtigt bibliotek).

Det kunne gøres sådan:

int size;

int flere_end_ti(træ t) { /* returner 1 hvis ja ellers 0 */
size = 0;
antal = for_each( t, f );
if (size>10)
return 1
else
return 0;
}

int f(int n) {
size = size + 1;
}

Men f vil blive kaldt en million gange.


Men vi kan også stoppe for_each før tid (selvom vi ikke selv
har adgang til definitionen af for_each).

int size;
int over_ti;

int flere_end_ti(træ t) { /* returner 1 hvis ja ellers 0 */
size = 0;
over_ti = 0;
setjmp "done";
if (over_ti==1)
return 1
else {
antal = for_each( t, f );
if (size>10)
return 1 /* her kommer vi aldrig til */
else
return 0;
}
}

int f(int n) {
size = size + 1;
if (size>10) {
over_ti = 1;
longjmp "done";
}
}

Nu vil f kun blive kaldt 10 gange.


Med andre ord, hvis man bruger et bibliotek, som
giver angang til en gennemløbsfunktion (som for_each)
kan man stoppe gennemløbet før tid ved at anvende
setjmp/longjmp også selvom man ikke har adgang til
biblioteket.


Hvis man selv skal implementere et bibliotek, så
kan man overveje at bruge teknikken, hvis man ikke
har tid/plads til at opretholde den ekstra information
i alle knuder.

--
Jens Axel Søgaard

---

Den Sun, 25 May 2003 17:35:38 +0200 skrev Jens Axel Søgaard:
>
>int size;
>int over_ti;
>
>int flere_end_ti(træ t) { /* returner 1 hvis ja ellers 0 */
> size = 0;
> over_ti = 0;
> setjmp "done";
> if (over_ti==1)
> return 1

Hvis du havde checket dokumentationen til setjmp/longjmp, havde du
kunnet spare din globale variabel:

fra setjmp(3):

RETURN VALUE
setjmp() and sigsetjmp() return 0 if returning directly,
and non-zero when returning from longjmp() using the saved
context.

fra longjmp(3):

DESCRIPTION
longjmp() and setjmp() are useful for dealing with errors
and interrupts encountered in a low-level subroutine of a
program. longjmp() restores the environment saved by the
last call of setjmp() with the corresponding env argument.
After longjmp() is completed, program execution continues
as if the corresponding call of setjmp() had just returned
the value val. longjmp() cannot cause 0 to be returned.
If longjmp is invoked with a second argument of 0, 1 will
be returned instead.

Du kan altså returnere en værdi igennem longjmp(), og teste direkte
på den, i stedet for at bruge en global variabel.

Mvh
Kent
--
IE is the only thing capable of making Netscape look good
- D. Spider in comp.os.linux.advocacy

---

Kent Friis wrote:
> Den Sun, 25 May 2003 17:35:38 +0200 skrev Jens Axel Søgaard:
>
>>int size;
>>int over_ti;
>>
>>int flere_end_ti(træ t) { /* returner 1 hvis ja ellers 0 */
>> size = 0;
>> over_ti = 0;
>> setjmp "done";
>> if (over_ti==1)
>> return 1
>
>
> Hvis du havde checket dokumentationen til setjmp/longjmp, havde du
> kunnet spare din globale variabel:
>
> fra setjmp(3):
....
> Du kan altså returnere en værdi igennem longjmp(), og teste direkte
> på den, i stedet for at bruge en global variabel.

Det havde været meget kønnere. Tak.

--
Jens Axel Søgaard

---

"Carsten Agger" <agger@post8.tele.dk> writes:

> Så hvordan har jeg det med setjmp()? Den kan virke smart, men også
> farlig i den forstand, at den kan gøre kodens opførsel uberegnelig
> og koden svær at læse - og med min egen (praktiske) baggrund i
> administrative
> systemer har jeg en tendens til at prioritere læselighed over
> performance og så lave performanceoptimeringer bagefter baseret
> på målinger, hvis behovet viser sig.

Jeg tror setjmp primært bliver brugt til at gøre koden mere læselig
ved at matche et design som ellers ville være svært (kræve en
frygtelig masse hjælpevariable og ekstra kode) at implementere i C.

Det samme gælder i mindre grad goto.

---

Per Abrahamsen wrote:

> Jeg tror setjmp primært bliver brugt til at gøre koden mere læselig
> ved at matche et design som ellers ville være svært (kræve en
> frygtelig masse hjælpevariable og ekstra kode) at implementere i C.

Jeg fandt et godt eksempel på ovenstående på nettet
[og denne gang kan det endda oversættes]:


#include <signal.h>
#include <setjmp.h>

int i, j;
long T0;
jmp_buf Env;

void alarm_handler(int dummy)
{
long t1;

t1 = time(0) - T0;
printf("%d second%s has passed: j = %d. i = %d\n", t1,
(t1 == 1) ? "" : "s", j, i);
if (t1 >= 8) {
printf("Giving up\n");
longjmp(Env, 1);
}
alarm(1);
signal(SIGALRM, alarm_handler);
}

main()
{

signal(SIGALRM, alarm_handler);
alarm(1);

if (setjmp(Env) != 0) {
printf("Gave up: j = %d, i = %d\n", j, i);
exit(1);
}

T0 = time(0);

for (j = 0; j < 10000; j++) {
for (i = 0; i < 1000000; i++);
}
}

---

> Jeg fandt et godt eksempel på ovenstående på nettet
> [og denne gang kan det endda oversættes]:

[snip, noget kode]

denne gang giver koden også mening, da den netop anvendes lidt ala i samme
funktion som call/cc der tweakes til at lave exception-handling