[Algemeen] for lus vraagje

[Michali]

Stel ik heb een for lus als deze.

code:

int a = 10;
int b;

for (b = 1; b <= a; b++)
{
  cout << b << endl;
  a--;
}

Wat zie je dan in het schermpje (sorry ben ergens waar ik het niet zelf kan uitproberen) echt 1 tot 10 of evalueert hij elke keer b <= a?

[Janoz]

Hij evalueert elke keer b <= a. hij zal dus al stoppen bij 5.

[Michali]

Janoz schreef op 29 september 2002 @ 13:37:
Hij evalueert elke keer b <= a. hij zal dus al stoppen bij 5.

thanx

[Alarmnummer]

Janoz schreef op 29 september 2002 @ 13:37:
Hij evalueert elke keer b <= a. hij zal dus al stoppen bij 5.

Er staat mij bij dat er wel talen zijn die op x86 de count naar een cx register wegschrijven (volgens mij waren het oa pascal en c) en daarna wordt er niet meer gekeken naar die conditie maar automatisch wordt bij iedere iteratie dat cx register verlaagt totdat er 0 uitkomt.

[mbravenboer]

Uiteraard bestaan er ook talen waarin de conditie juist niet elke keer wordt geevalueerd. Zelfs als de betekenis van een taal aangeeft dat dit wel moet gebeuren, kan een compiler specifieke situaties ook nog optimaliseren als er bijvoorbeeld gegarandeerd kan worden dat de waarde waarmee vergeleken moet worden een constante is (bijvoorbeelde de lengte van een array).

Als het aantal loops bepaald kan worden voordat de loops daadwerkelijk beginnen (en dat zou bij goed gebruik van for loops imho zo moeten zijn) kan er, zoals Alarmnummer aangeeft, gewoon afgeteld worden.

[mbravenboer]

Er bestaan overigens nog veel meer optimalisaties voor loops: bijvoorbeeld het uitrollen van de loop als het aantal loops at compile time bekend is.

Al deze mogelijkheden laten zien dat de semantiek van een taal niet percee ook een bepaalde manier van executie op hoeft te leggen: ook met andere vormen van executie kan dezelfde semantiek behouden blijven.

[Alarmnummer]

Kortom, het hangt dus af van de compiler wat hier het antwoord op gaat worden

[mbravenboer]

Alarmnummer: Kortom, het hangt dus af van de compiler wat hier het antwoord op gaat worden

Als het goed is juist niet: optimalisaties of taktieken bij compilatie mogen natuurlijk nooit de betekenis van de code beinvloeden . Het resultaat van een stuk code hangt af van de semantiek van de taal, de manier waarop de code uitgevoerd wordt hangt af van de optimalisaties in de compiler.

[Verwijderd]

Als we toch over for-lusjes praten, ik mis in C af en toe wel eens de bash optie:

code:

for i in bla1 bla2 bla3 bla4 bla5; do
  ...
  done

De enige C-variant die ik hiervoor ken is:

code:

bla_struct *blas[] = { bla1,
                bla2,
                bla3,
                bla4,
                bla5,
                NULL };
for ( ; bla != NULL; bla = &bla[1]) {
  ..
}

Of je moet voor elke 'bla' apart de code uitvoeren, maar dat wil je niet (duplication of code etc.). Bestaat hier een mooiere methode voor? Dat van mij is lelijk. .

[mbravenboer]

Een andere taal pakken .

In talen met functionale mogelijkheden wil je hier waarschijnlijk een map gebruiken. In talen met een niet C-achtige for loop zou je wat makkelijker alle indexen kunnen aflopen, maar ik ken er eigenlijk maar weinig die op een lijst van expressies toegepast zouden kunnen worden.

C# heeft (naast de for) op dit punt weer een iets andere (en best aardige) aanpak met de foreach, maar ook die kan je niet toepassen op een lijst expressies. Je zal dan toch nog een array aan moeten maken, wat toch nog wel voor een aardig resultaat zorgt.

Als het echt een ramp is, zou je een kleine syntaxtische uitbreiding van C kunnen maken die wordt omgezet naar de taktiek die jij al aangaf. Dit is vrij eenvoudig te implementeren, men is over het algemeen echter nogal bang voor de toepassing van pre-processors of andere tools die eerst de source manipuleren .

[Verwijderd]

Preprocessors, dan bedoel je macro's? Die gebruik ik al vaker dan eens... En kijken kan nooit kwaad. .

Maar hoe maak ik een uitbreiding van C daarmee? Op standaard google opdrachten naar 'C extensions by preprocessing' kom ik niet echt veel tegen wat dit betreft (wel over standaard macro's)... . Waar moet ik naar zoeken?

[mbravenboer]

Macro's schijnen inderdaad een aardig hulpmiddel zijn, maar ik vraag me af of je er in dit geval ook iets mee kan. Ik heb er nog nooit serieus mee gewerkt, dus kan de capaciteiten niet goed beoordelen.

Ik zal zelf aan een wat gestructureerde oplossing te denken: neem een grammatica voor C, breid deze uit met de gewenste features en schrijf een kleine transformatie die deze uitbreiding omzet naar de standaard C. De AST die daaruit komt even pretty-printen en je bent klaar, althans: de compiler doet de rest.

Dit lijkt erg veel werk, maar dit valt erg mee als je de goede tools bij de hand hebt. Ik zou voor Java in een uurtje of 2 een foreach kunnen implementeren a la C# (met gebruik van een Iterator). Iterateren over een lijstje van expressies is zeker niet meer werk.

Als je erg benieuwd bent of dit echt goed werkt, kan ik het eventueel wel maken, Je kan het daarna zelf porten naar C. Ik kan het ook wel gelijk voor C doen, maar ik heb met name goede tools beschikbaar voor transformaties op Java applicaties.

[Verwijderd]

Als je het in java wilt doen, graag! Ik zal het zelf dan in C proberen te doen .

[mbravenboer]

Ok, ik zal het ff maken .

De methode die ik gebruik vereist wel een aantal talen die je waarschijnlijk niet kent, maar het is zo weinig code dat je wel goed kan zien hoe het werkt en dus kan beoordelen of het functioneel is.

[MSalters]

Verwijderd schreef op 29 september 2002 @ 19:08:
Als we toch over for-lusjes praten, ik mis in C af en toe wel eens de bash optie:

code:

for i in bla1 bla2 bla3 bla4 bla5; do
  ...
  done

De enige C-variant die ik hiervoor ken is:

code:

bla_struct *blas[] = { bla1, bla2, bla3, bla4, bla5, NULL };
for ( ; bla != NULL; bla = &bla[1]) {... }

Bestaat hier een mooiere methode voor? Dat van mij is lelijk.

Nee; 't breekt je een beetje op dat C geen OO-taal is. De enige "iterator"over een collectie is een pointer, zoals je'm gebruikt hebt. Maar C + OO bestaat natuurlijk wel

[ Voor 0% gewijzigd door MSalters op 30-09-2002 21:31 . Reden: Overquote ]

[mbravenboer]

Ok, het werkt min of meer. Het duurde allemaal iets langer want ik heb er gelijk maar een GNU automake/autoconf project van gemaakt. Daar gaat uiteindelijk meer tijd in zitten dan in de implementatie zelf .

Allereerst moet de grammatica natuurlijk uitgebreid worden. Dit gebeurt met deze productie regel in SDF:

code:

module Sweet-Java
imports Generic-Java
_
exports
  context-free syntax
    _
    "for" Type Id "in" {Expr ","}* "do" Stm -> Stm {cons("ForEach")}

Uit de Generic-Java grammatica + deze productie regel kan je een parser genereren die Java code parset. Ik heb dit maar Sweet-Java genoemd. Na het parsen van de nieuwe taal moet de for constructie omgezet worden naar normale Java code. Dit heb ik geimplementeerd in Stratego met concrete syntax voor Java:

code:

module sweet-java-to-java
imports Generic-Java lib
_
signature
  constructors
    ForEach: Type * Id * List(Expr) * Stm -> Stm
_
strategies
  _
  main =
    iowrap(topdown(try(desugar)); where(debug(!"Done")))
  _
  desugar:
    ForEach(t, n, exprs, stm)
      ->
    [java:block-stm[
      {
        ~t [] ~narray = new ~t[]{ ~*exprs } ;
        for(int i = 0; i < ~id:narray . length ; i++) {
          ~t ~id:n = ~idd:narray: [i] ;
          ~stm
        }
      }
    ]]
      where <conc-strings> (n, "array") => narray

Zoals je misschien kan ontdekken heb ik maar even gekozen voor precies dezelfde taktiek die jij gebruikte (behalve dat Java arrays natuurlijk niet via pointers te gebruiken zijn).

Na deze transformatie is er een normale Java AST (jtree noem ik die) die daarna gepretty-print kan worden met een gewone Java pretty-printer. De pretty printer die ik gebruik kan alleen nog niet met prioriteiten omgaan en daarom zet hij overal maar dom haakjes omheen. Dit zorgt voor problemen in de for-statement: de Java compiler begint te zeuren. Dit is vooral een probleem van de pretty-printer: die moet nog even worden verbeterd. De pretty-printer voor C heeft dit probleem niet (beter: negeert prioriteiten).

Een kleine test:

Java:

public class Test {
  public static void main(String[] ps) {
    for int x in 1, 2, 3, 4 do {
      System.out.println("Value: " + x);
    }
  }
}

Resultaat:

Java:

public class Test  
{ 
  public static void main (String[] ps) 
  { 
    { 
      int[] xarray = new int[]{1 , 2 , 3 , 4};
      for(int i = 0;(i < xarray.length);(i++))
      { 
        int x = xarray[i];
        { 
          System.out.println(("Value: " + x));
        }
      }
    }
  }
}

Deze code compileert niet door ( ) om de i++. Dit is dus het pretty-printer probleem. Als ik ze even weghaal compileert het wel en doet het inderdaad wat het zou moeten doen .

Dit is natuurlijk een heel triviaal voorbeeld, maar omdat er gewone Java non terminals gebruikt worden kan je het zo ingewikkeld maken als je maar wilt.

Als je dit ook echt op deze manier (SDF, Stratego) zelf wilt gaan implementeren voor C heb je nogal wat tools, packages en kennis nodig. Ik kan je wel wat linkjes geven waarmee je aan de slag kan, maar voordat ik dat allemaal ga doen moet je eerst maar even aangeven of je dat ziet zitten .

Dit is dus trouwens nog geen foreach over een Iterator: het is een foreach over een lijstje van expressies. Hij werkt hierdoor bijvoorbeeld ook niet over een array: hiervoor is semantische analyse of een andere syntax noodzakelijk. De oplossing met een andere syntax is zeer eenvoudig te implementeren (kleine uitbreiding).

Er is geen speciale constructie nodig om deze foreach te verwerken in het dangling-else probleem (normaal gesproken is dit wel noodzakelijk voor de while, for etc) omdat SDF betere mogelijkheden kent om het dangling else probleem op te lossen.

[mbravenboer]

Ik heb de pretty printer even aangepast zodat deze ook prioriteiten negeert. Niet goed uiteraard, maar dan compileert het tenminste even. De nieuwe output is:

Java:

public class Test  
{ 
  public static void main (String[] ps) 
  { 
    { 
      int[] xarray = new int[]{1 , 2 , 3 , 4};
      for(int i = 0;i < xarray.length;i++)
      { 
        int x = xarray[i];
        { 
          System.out.println("Value: " + x);
        }
      }
    }
  }
}

Ik heb ook even een foreach constructie toegevoegd om over een Iterator te itereren:

Java:

import java.util.*;

public class Iterate {
  public static void main(String[] ps) {
    List<String> list = new ArrayList<String>();
    list.add("Hello");
    list.add("Stratego");
    list.add("World");

    foreach(String s in list.iterator())
      System.out.println("Value: " + s);
  }
}

Dit is de productie regel:

Java:

"foreach" "(" RefType Id "in" Expr ")" Stm -> Stm {cons("Iterate")}

en dit is de herschrijving:

Java:

  desugar:
    Iterate(t, n, expr, stm)
      ->
    [java:block-stm[
      {
        Iterator< ~t > iterator = ~expr ;
        while(iterator.hasNext()) {
          ~t ~id:n = iterator.next() ;
          ~stm
        }
      }
    ]]

Dit is het resultaat van het eerste voorbeeld:

Java:

import java.util.*;

public class Iterate  
{ 
  public static void main (String[] ps) 
  { 
    List<String> list = new ArrayList<String>( );
    list.add("Hello");
    list.add("Stratego");
    list.add("World");
    { 
      Iterator<String> iterator = list.iterator( );
      while(iterator.hasNext( ))
      { 
        String s = iterator.next( );
        System.out.println("Value: " + s);
      }
    }
  }
}

Best een aardige manier van language prototyping . Het toevoegen van de laatste constructie kostte me maar een kleine tien minuten nu ik het project al had opgezet.

[Verwijderd]

mbravenboer schreef op 30 september 2002 @ 22:41:
Allereerst moet de grammatica natuurlijk uitgebreid worden. Dit gebeurt met deze productie regel in SDF:

Zijn er ook tutorials van sdf en tools die daar gebruik van kunnen op een begrijpbaar niveau?

code:

          ~t ~id:n = ~idd:narray: [i] ;

Deze regel kan ik niet helemaal volgen wat betekent de ":" en zit er ook niet een typefoutje in?

Dit is natuurlijk een heel triviaal voorbeeld, maar omdat er gewone Java non terminals gebruikt worden kan je het zo ingewikkeld maken als je maar wilt.

Dus nu kun je gemakkelijk allerlei constructies aan een programmeertaal toevoegen met relatief weinig werk.

[mbravenboer]

borganism: Zijn er ook tutorials van sdf en tools die daar gebruik van kunnen op een begrijpbaar niveau?

Jazeker. Hier vind je een overzichtje van SDF:

http://www.program-transf...wiki/bin/view/Tools/SDFII

Met name de quick introduction is iets wat je wilt lezen. Als je later dieper in SDF wilt duiken, kan je terecht bij: de SDF manual of Syntax Definition for Language Prototyping.. Voor de echte details kan je terecht in diverse publicaties zoals bijvoorbeeld Disambiguation Filters for Scannerless Generalized LR Parsers.

Ik heb zelf een tijd geleden op Javahova beschreven wat de verbanden zijn tussen SDF, Stratego, SGLR en ATermen. Ik kan dat topic alleen niet meer vinden . Wel is er nog dit:

[rml]mbravenboer in "[ DISC] Welke parser (generators) gebruik"[/rml]

Ook is er op Javahova een lang topic over code generatie in Stratego:
http://forum.javahova.net/topic.php?id=812

Voor Stratego kan je terecht op http://www.stratego-language.org . Er is wel documentatie, maar die is nogal achterhaald. De visie van Stratego wordt wel goed duidelijk.

Deze regel kan ik niet helemaal volgen wat betekent de ":" en zit er ook niet een typefoutje in?

Het werkt, dus het is wel correct maar het is inderdaad een obscure regel. De ~ staat allereerst voor anti-quotation: de concrete syntax voor Java wordt hier onderbroken door een Stratego constructie. Hoe dit precies zit kan je hier lezen: Meta Programming with Concrete Object Syntax

De constructie "id:" is (helaas) noodzakelijk omdat Java zoveel non-terminals kent. Ik geef hiermee expliciet aan dat de variabele van deze anti-quotation van de non-terminal Id is. Hierdoor kan deze variabele syntax loos ingepakt worden in andere constructies, maar het gaat denk ik wat ver om dit allemaal uit te leggen. Eventueel kan je hier meer over zien in een presentatie die ik pas heb gehouden: java front: techniques and applications.

Dit stukje: "~idd:narray: [i] " is een verhaal apart. Ik voel me betrapt . Er waren problemen met het bepalen van het aantal tekens wat bij deze anti-quotation hoorde. Het gaat hier alleen om de narray, maar de parser nam om een of andere reden meer constructies mee. Ik had geen zin om uit te zoeken waarom dit gebeurde en heb daarom de narray afgesloten met een ":" . Dit zorgt ervoor dat de anti-quotation met syntax begrensd wordt. Erg ranzige oplossing dus .

Dus nu kun je gemakkelijk allerlei constructies aan een programmeertaal toevoegen met relatief weinig werk.

Inderdaad, wel moet ik opmerken dat het natuurlijk een stuk complexer wordt zodra je semantische analyse nodig hebt om de nieuwe constructies te vertalen in bestaande constructies. Ook wordt het een ander verhaal als je de uitgebreidere taal wilt gaan type-checken ipv het resultaat na de ontsuikering (denk aan de C++ templates).

Bij het maken van SDF grammatica's heb ik zelf overigens eigenlijk nog het meest gehad aan voorbeelden van andere grammatica's. Door een beetje te gluren hoe anderen het aanpakken kom je er al snel achter hoe alles precies werkt. Je kan gluren in de grammar-base, maar bijvoorbeeld ook in mijn java-front package (waar dus Java grammatica's in staan).

[mbravenboer]

Ik heb nog even een aardige geimplementeerd: een serie methode aanroepen op een expressie. In Java zie je te vaak dat methoden 'this' opleveren met als enige doel om het mogelijk te maken om herhaald een methode aan te roepen op een instantie van deze klasse:

Java:

new StringBuffer().append("Hello ").append("world");

Hier levert de append methode 'this' op zodat je gelijk weer een methode aan kan roepen op de StringBuffer. Op zich heel handig, maar het is oerlelijk: het herhaald aanroepen van methoden zou absoluut geen invloed mogen opleveren op het signatuur van methoden. Daarnaast is het ook nog zeer verwarrend: je moet de documentatie raadplegen om te kijken of append een nieuwe StringBuffer of 'this' oplevert. Als er ook methoden zijn die juist niet this en dus wel een nieuwe instantie opleveren is de ramp compleet.

Wat je nodig hebt is gewoon een stukje syntax om herhaald methoden aan te roepen. Dit zie je in wel meer talen, maar een aardige benadering is deze: een methode aanroep zonder dat de 'huidige expressie' wordt aangepast naar het resultaat van de methode aanroep.

Stukje code:

Java:

public class Chain {
 
  public static void main (String[] ps) { 
    StringBuffer buffer = new StringBuffer("");
    _
    buffer <- append("Hello") <- append(' ') <- append("word") <-  append('!');
    _
    System.out.println(buffer.toString());
  }
}

De productie regels hiervoor:

Java:

Expr MethodInv+ ";" -> Stm {prefer, cons("Invocations")}
_
"<-" Id "(" {Expr ","}* ")" -> MethodInv {cons("Invocation")}

De desugaring:

Java:

  desugar:
    Invocations(e, invs) -> [java:block-stm[ { ~*stms } ]]
      where <map(!(e, <id>); create-invocation)> invs => stms
  _
  create-invocation:
    (e, Invocation(n, exprs))
      ->
    [java:block-stm[ ~expr:e . ~id:n ( ~*exprs ); ]]

Het resultaat:

Java:

public class Chain  
{ 
  public static void main (String[] ps) 
  { 
    StringBuffer buffer = new StringBuffer("");
    { 
      buffer.append("Hello");
      buffer.append(' ');
      buffer.append("word");
      buffer.append('!');
    }
    System.out.println(buffer.toString( ));
  }
}

Overigens is deze constructie alleen zinvol als hij wordt toegepast op een bestaand object. Een new ... constructie zou dus eigenlijk afgwezen moeten worden. Het is mogelijk om dit in SDF uit te drukken, maar ik vond het al lang leuk dat het werkt .

[Verwijderd]

mbravenboer schreef op 30 september 2002 @ 22:41:
Als je dit ook echt op deze manier (SDF, Stratego) zelf wilt gaan implementeren voor C heb je nogal wat tools, packages en kennis nodig. Ik kan je wel wat linkjes geven waarmee je aan de slag kan, maar voordat ik dat allemaal ga doen moet je eerst maar even aangeven of je dat ziet zitten .

Absoluut, dit is best leerzaam!

Van wat ik hier zie is dit in elk geval geen standaard C, maar het ziet er best mooi uit. Als je wat namen van packages of linkjes van meer C-specifiek gerichte zaakjes kan geven, dan zou ik enorm dankbaar zijn! Dit ziet er niet uit als iets wat ik 1-2-3 in mijn eigen programma's kan gebruiken, maar 't is wel een enorme uitbreiding van C...

Eigenlijk is C gewoon enorm beperkt. .

[mbravenboer]

beelzebubu: Absoluut, dit is best leerzaam!

Ik heb in mijn reactie op borganism al een heleboel links gepost naar SDF/Stratego gerelateerd materiaal. Ik denk dat je daar zou moeten beginnen. Het is absoluut niet iets wat je even op een avondje download en leert, dus je moet er absoluut wel de tijd voor nemen...

Van wat ik hier zie is dit in elk geval geen standaard C, maar het ziet er best mooi uit.

De transformatie is in ieder geval verre van C: dat is gewoon Stratego (wat overigens wel naar C compileert ). De transformatie transformeert in dit geval Java.

Als je wat namen van packages of linkjes van meer C-specifiek gerichte zaakjes kan geven, dan zou ik enorm dankbaar zijn!

Naast de info hierboven een paar links: er zit een C grammatica in de grammar base die ik daar noemde. Ook is er een CGEN package voor C code generatie. Voordat je hier naar gaat kijken zal je echt eerst het een en ander moeten weten van SDF (ik neem maar even aan dat je al wel bekend bent met context-vrije grammatica's ?) en Stratego.

CGEN kan je download op de locatie waar je ook Stratego kan downloaden (het zit gewoon in het complete Stratego package ).

http://www.stratego-langu...Stratego/StrategoDownload

Het gaat bij CGEN met name om een pretty printer voor C, de SDF gramamtica voor C en de signaturen voor de AST van C.