:strip_exif()/u/396800/D-_3427da0a9c293b63f2a66dea2e642102.gif?f=community)
Ik ben bezig met het porten van mijn lexer en interpreter naar een ESP(8266). Simpel gezegd parsed mijn lexer mijn syntax naar een AST die ik vervolgens mij met interpreter doorloop. Het doorlopen van mijn AST deed ik met een recursieve functie (zie onderaan). Het hele spul werkt prima op mijn X86 machine, maar niet op mijn ESP.
Ik heb sterk het vermoedde dat dit komt door stack overflows door de vele recursies. Nu zijn er twee manieren om dit op te lossen:
1) Voorkomen van recursie d.m.v. dubbele loops m.b.v. een eigen stack.
2) Implementeren van tail-recursion.
Nu moet ik zeggen dat ik beide methoden voor mijn aanvankelijk probleem onbekend waren. De eerste methode werkt op zich, maar vraagt meer resources dan een goed geïmplementeerde tweede methode.
Ik neem in onderstaande voorbeelden even deze simpele AST als uitgangspunt:
:fill(white):strip_exif()/f/image/Os2BzwFcaqzGZOso5XwLztQT.png?f=user_large)
Het parsen van de variabele ($a) heb ik even buiten beschouwing gelaten.
De vraag is echter of mijn tail-recurion (in C) ook echt zorgt voor een nette kleine stack. In een compact stukje code ziet dat er nu als volgt uit:
De interpret functie eindigt nu gegarandeerd elke keer met een functie aanroep zonder daarna nog iets aan logica te hebben. Van wat ik van tail-recursion begrijp moet dit ervoor zorgen dat de stack schoon blijft.
Nu heb ik bijv. in de functie interpret_value het parsen van mijn waardes gezet, maar dit zou net zo goed in mijn interpret functie kunnen zoals dit:
De functie aanroep van regels 4 en 5 zorgen nu voor tenminste 1 recursie die op de stack blijft staan, maar de TINTEGER case is een eindpunt, dus het zal nooit verder gaan en beide stack entries zullen snel van de stack verdwijnen. Is er dan een voordeel om voor de eerste implementatie te gaan of maakt dat t.o.v. de tweede implementatie geen verschil voor de stack? In beide versies eindigt de boel van een tail-recursive functie aanroep waardoor de stack vervolgens weer netjes wordt opgeruimd.
Heb ik het goed begrepen dat het doel van tail-recursion niet perse is het volledig voorkomen van het vullen van de stack met een aantal recursies, maar dat het doel vooral is te kunnen voorspellen wat de maximale aantal stack ruimte is die je functie zal gebruiken? Zoals nu dus maximaal 1 recursie.
Als laatste nogmaals. Kan ik er vanuit gaan dat deze versies van mijn code correct tail-recursie implementeren?
Ten overvloede nog even de oorspronkelijke recursieve implementatie van mijn functie die niet vriendelijk is voor de stack, omdat die oneindig kan groeien.
Ik heb sterk het vermoedde dat dit komt door stack overflows door de vele recursies. Nu zijn er twee manieren om dit op te lossen:
1) Voorkomen van recursie d.m.v. dubbele loops m.b.v. een eigen stack.
2) Implementeren van tail-recursion.
Nu moet ik zeggen dat ik beide methoden voor mijn aanvankelijk probleem onbekend waren. De eerste methode werkt op zich, maar vraagt meer resources dan een goed geïmplementeerde tweede methode.
Ik neem in onderstaande voorbeelden even deze simpele AST als uitgangspunt:
Het parsen van de variabele ($a) heb ik even buiten beschouwing gelaten.
De vraag is echter of mijn tail-recurion (in C) ook echt zorgt voor een nette kleine stack. In een compact stukje code ziet dat er nu als volgt uit:
C:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| int interpret(struct tree_t *tree, struct varcont_t *v_out, void (*cb)(...)) { switch(tree->token->type) { case TOPERATOR: { interpret_value(tree->child[0], &var1); interpret_value(tree->child[1], &var2); operator_callback(tree->token->value, &var1, &var2, v_out); ... return cb(tree->parent, v_out); } break; case TIF: { return interpret(tree->child[0], ..., interpret_if); } break; case TTRUE: { ... } break; case TFALSE: { ... } break; default: { return -1; } break; } } |
De interpret functie eindigt nu gegarandeerd elke keer met een functie aanroep zonder daarna nog iets aan logica te hebben. Van wat ik van tail-recursion begrijp moet dit ervoor zorgen dat de stack schoon blijft.
Nu heb ik bijv. in de functie interpret_value het parsen van mijn waardes gezet, maar dit zou net zo goed in mijn interpret functie kunnen zoals dit:
C:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| int interpret(struct tree_t *tree, struct varcont_t *v_out, void (*cb)(...)) { switch(tree->token->type) { case TOPERATOR: { interpret(tree->child[0], &var1); interpret(tree->child[1], &var2); operator_callback(tree->token->value, &var1, &var2, v_out); ... return cb(tree->parent, v_out); } break; case TIF: { return interpret(tree->child[0], ..., interpret_if); } break; case TINTEGER: { ... return 0; } break; case TTRUE: { ... } break; case TFALSE: { ... } break; default: { return -1; } break; } } |
De functie aanroep van regels 4 en 5 zorgen nu voor tenminste 1 recursie die op de stack blijft staan, maar de TINTEGER case is een eindpunt, dus het zal nooit verder gaan en beide stack entries zullen snel van de stack verdwijnen. Is er dan een voordeel om voor de eerste implementatie te gaan of maakt dat t.o.v. de tweede implementatie geen verschil voor de stack? In beide versies eindigt de boel van een tail-recursive functie aanroep waardoor de stack vervolgens weer netjes wordt opgeruimd.
Heb ik het goed begrepen dat het doel van tail-recursion niet perse is het volledig voorkomen van het vullen van de stack met een aantal recursies, maar dat het doel vooral is te kunnen voorspellen wat de maximale aantal stack ruimte is die je functie zal gebruiken? Zoals nu dus maximaal 1 recursie.
Als laatste nogmaals. Kan ik er vanuit gaan dat deze versies van mijn code correct tail-recursie implementeren?
Ten overvloede nog even de oorspronkelijke recursieve implementatie van mijn functie die niet vriendelijk is voor de stack, omdat die oneindig kan groeien.
C:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| int interpret(struct tree_t *tree, struct varcont_t *v_out) { switch(tree->token->type) { case TINTEGER: { ... return 0; } break; case TIF: { int x = interpret(tree->child[0], ...); if(x == 0) { interpret(tree->child[1], ...); return 0; } else if(tree->nrchildren == 3) { interpret(tree->child[2], ...); return 0; } return -1; } break; case TOPERATOR: { interpret(tree->child[0], &var1); interpret(tree->child[1], &var2); operator_callback(tree->token->value, &var1, &var2, v_out); return 0; } break; } } |
Sinds de 2 dagen regel reageer ik hier niet meer
/u/3813/100_8985_ICON2.JPG?f=community)
:strip_exif()/u/248854/rudolph3.gif?f=community)
De vorige heeft inderdaad netjes 4.000.000 tellingen gedaan.:fill(white):strip_exif()/f/image/EAning5smIY4axGgn2yNwRDw.png?f=user_large)
:fill(white):strip_exif()/f/image/3ThW4w2dbm9yeaCwrbSAERdK.png?f=user_large)
:fill(white):strip_exif()/f/image/TZOvHzTG5INSO5bf3tshYnQJ.png?f=user_large)
:fill(white):strip_exif()/f/image/CsQg2Jd9HiUYwM8orwQ95Nx8.png?f=user_large)
:fill(white):strip_exif()/f/image/ITulWw6B0Qnsa6BchHj7gomw.png?f=user_large)