Changeset 10067 for branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs

Timestamp:

10/18/13 21:33:56 (11 years ago)

Author:

gkronber

Message:

#2026 worked on brute force solver for GPDL problems.

File:

• branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs (modified) (9 diffs)

branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs

@@ -1 +1 @@
 using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.IO;
 using System.Linq;
 using System.Text;
 using System.Threading.Tasks;
+using HeuristicLab.Grammars;
+using Attribute = HeuristicLab.Grammars.Attribute;
 
 namespace CodeGenerator {
@@ -17 +20 @@
     private string solverTemplate = @"
 namespace ?PROBLEMNAME? {
-  private static class Grammar {
+  internal static class Grammar {
     ?GRAMMARCLASSCODE?
   }
-  private sealed class PartiallyProcessedSeq {
-    private PartiallyProcessedSeq parent;
-    private int alt;
+  internal sealed class PartiallyProcessedSeq {
     private IEnumerable<string> remaining;
-    public PartiallyProcessedSeq(IEnumerable<string> alternative) {
-      this.remaining = alternative;
-    }
-    public PartiallyProcessedSeq CreateAlternative(int p, IEnumerable<string> alternative) {
-      var child = new PartiallyProcessedSeq(alternative.Concat(remaining));
-      child.parent = this;
-    }
-    public bool TryProcessToNextSymbolWithAlternatives(out string symbol) {
-      remaining = remaining.SkipWhile(s=>Grammar.NumberOfAlternatives(s)==0);
-      if(remaining.Any()) {
-        symbol = remaining.First();
-        remaining = remaining.Skip(1);
-        return true;
-      } else {
-        symbol = null;
-        return false;
-      }
-      
+    private IEnumerable<int> path;
+    public PartiallyProcessedSeq(IEnumerable<string> remaining) : this (Enumerable.Empty<int>(), remaining) {
+    }
+    public PartiallyProcessedSeq(IEnumerable<int> path, IEnumerable<string> remaining) {
+      this.path = path;
+      this.remaining = remaining;
+    }
+
+    public bool MoveNext() {
+      if(!remaining.Any()) return false;
+      else remaining = remaining.Skip(1);
+      return true;
+    }
+
+    public string Current { 
+      get {
+        return remaining.FirstOrDefault();
+      }
     }
     public IEnumerable<int> Path {
       get {
-        var cur = this;
-        var List<int> path = new List<int>();
-        while(cur.parent!=null) {
-          path.Append(cur.p);
-          cur = cur.parent;
-        }
-        return path.Reverse();
-      }
-    }
+        return path;
+      }
+    }
+    public IEnumerable<string> Remaining {
+      get {
+        return remaining;
+      }
+    }
+    public override string ToString() {
+      return path.Aggregate("""", (str, p) => str + "" "" + p) + "" >> "" +
+             remaining.Aggregate("""", (str, r) => str + "" "" + r);
+    }
+
   }
   public sealed class ?IDENT?Solver {
@@ -71 +76 @@
 
     private bool IsBetter(double a, double b) { 
-      ?MAXIMIZATION? ? a > b : a < b;
-    }
-
-    private IEnumerable<IEnumerator<int>> GeneratePaths() {
+      return ?MAXIMIZATION? ? a > b : a < b;
+    }
+
+    #region path generator (BFS in the grammar to generate solutions)
+    ?PATHGENERATORCODE?
+    #endregion
+
+    private IEnumerable<IEnumerable<int>> GeneratePaths() {
       var queue = new Queue<PartiallyProcessedSeq>();
-      foreach(var alt in Grammar.GetAlternatives(Grammar.RootSymbol)) 
-        queue.Enqueue(new PartiallyProcessedSeq(alt));
-
-      while(queue.Count > 0) {
+      queue.Enqueue(new PartiallyProcessedSeq(new string[] { Grammar.RootSymbol }));
+
+      while (queue.Count > 0) {
         var e = queue.Dequeue();
-        string ntSöymbol;
-        if(e.TryProcessToNextNtSymbol(out ntSymbol)) {
-          int i=0;
-          foreach(var alt in Grammar.GetAlternatives(symbol)) {
-            queue.Enqueue(new e.CreateAlternative(i++, alt));
+        var symb = e.Current; // the next symbol to generate paths for
+        // Console.WriteLine(""Out: "" + e);
+
+        var lastSymbol = !e.MoveNext();
+
+        if (Grammar.IsTerminal(symb)) {
+          // generate all paths for the terminal
+          if (lastSymbol) {
+            var pathsForSymb = GeneratePathsFor(symb);
+            if (pathsForSymb.Any()) {
+              foreach (var path in GeneratePathsFor(symb)) {
+                yield return e.Path.Concat(path);
+              }
+            } else {
+              yield return e.Path;
+            }
+          } else {
+            var paths = GeneratePathsFor(symb);
+            if(!paths.Any() || paths.Count() == 1) {
+              yield return e.Path;
+            } else {
+              foreach (var path in paths) {
+                var eAlt = new PartiallyProcessedSeq(e.Path.Concat(path), e.Remaining);
+                queue.Enqueue(eAlt);
+                // Console.WriteLine(""In: "" + eAlt);
+              }
+            }
           }
         } else {
-          yield return e.Path;
-        }
-      }
-    }
-
-    ?PATHGENERATORCODE?
+          // non-terminal -> generate alternatives if necessary
+          var alts = Grammar.GetAlternatives(symb);
+          if (alts.Count() == 1) {
+              var eAlt = new PartiallyProcessedSeq(e.Path, alts.Single().Concat(e.Remaining));
+              queue.Enqueue(eAlt);
+              // Console.WriteLine(""In: "" + eAlt);
+          } else {
+            int i = 0;
+            foreach (var alt in alts) {
+              var eAlt = new PartiallyProcessedSeq(e.Path.Concat(new int[] { i++ }), alt.Concat(e.Remaining));
+              queue.Enqueue(eAlt);
+              // Console.WriteLine(""In: "" + eAlt);
+            }
+          }
+        }
+      }
+    }
 
     private void Start() {
       // generate possible paths through the grammar and evaluate each of them    
       var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
+      int n = 0;
       foreach(var path in GeneratePaths()) {
+        var length = path.Count();
         currentPath = path;
         var f = Calculate();
+        n++;
         if(IsBetter(f, bestF)) bestF = f;
-        Console.WriteLine(""{0}\t{1}"",bestF, f);
-      }
-    }
-
-    private IEnumerator<int> currentPath;
+        if (n%1000 == 0) Console.WriteLine(""{0}\t{1}\t{2}\t{3}"",n, length, bestF, f);
+      }
+    }
+
+    private IEnumerable<int> currentPath;
 
     public double Calculate() {
-      try {
-        ?FITNESSFUNCTION?
-      } catch(Exception e) {
-        throw;
-      }
+      ?FITNESSFUNCTION?
     }
 
@@ -137 +177 @@
       problemSourceCode.Replace("?PROBLEMNAME?", ast.Name);
 
-      // write to a file for debugging
+      // write the source file to disk
       using (var stream = new StreamWriter(ast.Name + ".cs")) {
         stream.WriteLine(problemSourceCode.ToString());
@@ -144 +184 @@
 
     private void GenerateProblem(GPDefNode ast, StringBuilder problemSourceCode) {
+      var grammar = CreateGrammarFromAst(ast);
       var problemClassCode =
         solverTemplate
-          .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString())
-          .Replace("?GRAMMARCLASSCODE?", GenerateGrammarClassCode(ast))
+          .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant())
+          .Replace("?GRAMMARCLASSCODE?", GenerateGrammarClassCode(grammar))
           .Replace("?IDENT?", ast.Name)
           .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
-          .Replace("?INTERPRETERSOURCE?", GenerateInterpreterSource(ast))
+          .Replace("?INTERPRETERSOURCE?", GenerateInterpreterSource(grammar))
           .Replace("?INITCODE?", ast.InitCodeNode.SrcCode)
           .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
@@ -160 +201 @@
     }
 
-    private string GenerateGrammarClassCode(GPDefNode ast) {
+    private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
+      string startSymbolName = ast.Rules.First().NtSymbol;
+      var startSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == startSymbolName);
+      // create startSymbol
+      var g = new AttributedGrammar(new Symbol(startSymbolName, ParseSymbolAttributes(startSymbolNode.FormalParameters)));
+      foreach (var rule in ast.Rules) {
+        // create nt-symbol
+        var ntSymbolName = rule.NtSymbol;
+        var ntSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == ntSymbolName);
+        var attributes = ParseSymbolAttributes(ntSymbolNode.FormalParameters);
+        var ntSymbol = new Symbol(ntSymbolName, attributes);
+        foreach (var alt in GetAlternatives(rule.Alternatives)) {
+          g.AddProductionRule(ntSymbol, alt);
+        }
+        // local initialization code
+        if (!string.IsNullOrEmpty(rule.LocalCode)) g.AddLocalDefinitions(ntSymbol, rule.LocalCode);
+      }
+      return g;
+    }
+
+    private IEnumerable<IAttribute> ParseSymbolAttributes(string formalParameters) {
+      return (from fieldDef in Util.ExtractParameters(formalParameters)
+              select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
+        ToList();
+    }
+
+    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode) {
+      foreach (var alt in altNode.Alternatives) {
+        yield return GetSequence(alt.Sequence);
+      }
+    }
+
+    private Sequence GetSequence(IEnumerable<RuleExprNode> sequence) {
+      Debug.Assert(sequence.All(s => s is CallSymbolNode || s is RuleActionNode));
+      var l = new List<ISymbol>();
+      foreach (var node in sequence) {
+        var callSymbolNode = node as CallSymbolNode;
+        var actionNode = node as RuleActionNode;
+        if (callSymbolNode != null) {
+          l.Add(new Symbol(callSymbolNode.Ident, ParseSymbolAttributes(callSymbolNode.ActualParameter)));
+        } else if (actionNode != null) {
+          l.Add(new SemanticSymbol("SEM", actionNode.SrcCode));
+        }
+      }
+      return new Sequence(l);
+    }
+
+
+    private string GenerateGrammarClassCode(IGrammar grammar) {
       var sb = new StringBuilder();
       // RootSymbol
-      sb.AppendFormat("public static string RootSymbol {{ get {{ return {0}; }} }}", ast.Rules.First().NtSymbol).AppendLine();
+      sb.AppendFormat("public static string RootSymbol {{ get {{ return \"{0}\"; }} }}", grammar.StartSymbol.Name).AppendLine();
+      sb.AppendLine("public static HashSet<string> terminalSymbols = new HashSet<string>() {");
+      sb.AppendFormat("{0}", grammar.TerminalSymbols.Aggregate("", (str, symb) => str + "\"" + symb.Name + "\", "));
+      sb.AppendLine("};");
       // GetAlternatives
       sb.AppendFormat("public static IEnumerable<IEnumerable<string>> GetAlternatives(string symbol) {{");
       sb.AppendFormat("switch(symbol) {{ ").AppendLine();
-      foreach (var ntSymbol in ast.NonTerminals) {
-        sb.AppendFormat("case {0}: {{ ").AppendLine();
-        var rule = ast.Rules.Single(r => r.NtSymbol == ntSymbol.Ident);
-        sb.AppendFormat("return new string[][] {{}}", rule.RuleExpr);
-        sb.AppendLine("break;}}");
-      }
-      foreach (var tSymbol in ast.NonTerminals) {
-
-      }
-      sb.AppendFormat(" else {{ throw new InvalidOperationException(\"Unkown symbol: \"+symbol); }}");
-      sb.AppendLine("}}");
-      sb.AppendFormat("}}").AppendLine();
-
+      foreach (var ntSymbol in grammar.NonTerminalSymbols) {
+        sb.AppendFormat("case \"{0}\": {{ ", ntSymbol.Name).AppendLine();
+        sb.Append("return new string[][] { ").AppendLine();
+        foreach (var alt in grammar.GetAlternatives(ntSymbol)) {
+          sb.Append("new string[] { ")
+            .Append(alt.Skip(1).Aggregate("\"" + alt.First().Name + "\"", (str, symb) => str + ", \"" + symb.Name + "\""))
+            .AppendLine("},");
+        }
+        sb.Append("};");
+        sb.AppendLine("}");
+      }
+      sb.AppendLine(" default: { throw new InvalidOperationException(\"Unkown symbol: \"+symbol); }");
+      sb.AppendLine("}");
+      sb.AppendLine("}");
+
+      sb.AppendLine("public static bool IsTerminal(string symbol) {");
+      sb.AppendFormat("return terminalSymbols.Contains(symbol);");
+      sb.AppendLine("}");
       // NumberOfAlternatives
-      sb.AppendFormat(
-        "public static int NumberOfAlternatives(string symbol) {{ return GetAlternatives(symbol).Count(); }}").AppendLine();
-      return sb.ToString();
-    }
+      sb.AppendLine(
+        "public static int NumberOfAlternatives(string symbol) { return GetAlternatives(symbol).Count(); }");
+      return sb.ToString();
+    }
+
 
     // produces helper methods for the attributes of all terminal nodes
@@ -216 +314 @@
     private string GeneratePathGeneratorCode(GPDefNode ast) {
       var sb = new StringBuilder();
-      foreach (var s in ast.NonTerminals) {
+      foreach (var s in ast.NonTerminals.OfType<NonTerminalNode>()) {
         sb.Append(GeneratePathGeneratorCode(s));
       }
-      foreach (var s in ast.Terminals) {
-        sb.Append(GeneratePathGeneratorCode(s));
-      }
-      return sb.ToString();
-    }
-
-    // generates code for a breath-first-search generating all possible paths through the grammar
-    private string GeneratePathGeneratorCode(SymbolNode s) {
-      var sb = new StringBuilder();
-
-      return sb.ToString();
-    }
-
-    private string GenerateInterpreterSource(GPDefNode definition) {
-      var sb = new StringBuilder();
-      // create a grammar instance based on the AST
-      var g = new Grammar(definition.NonTerminals, definition.Terminals, definition.Rules);
+
+      sb.Append(GeneratePathGeneratorCode(ast.Terminals.OfType<TerminalNode>()));
+      return sb.ToString();
+    }
+
+    private string GeneratePathGeneratorCode(NonTerminalNode s) {
+      var sb = new StringBuilder();
+
+      return sb.ToString();
+    }
+
+    // generates a method for the terminal that returns all an IEnumerable of int[] representing each possible combination of values for that terminal
+    private string GeneratePathGeneratorCode(IEnumerable<TerminalNode> terminals) {
+      var sb = new StringBuilder();
+      sb.AppendLine("private IEnumerable<IEnumerable<int>> GeneratePathsFor(string tSymbol) {");
+      sb.AppendLine("switch(tSymbol) {");
+      foreach (var t in terminals) {
+        sb.AppendFormat("case \"{0}\": {{", t.Ident).AppendLine();
+        if (t.FieldDefinitions.Any()) {
+          int i = 0;
+          // open for loop for each field
+          foreach (var f in t.FieldDefinitions) {
+            sb.AppendFormat("for(int i{0}=0; i{0} < GetAllowed{1}_{2}().Length; i{0}++) {{", i++, t.Ident, f.Identifier)
+              .
+              AppendLine();
+          }
+          sb.AppendFormat("yield return new int[] {{ {0} }};",
+                          Enumerable.Range(0, i).Select(ii => "i" + ii + ", ").Aggregate((str, e) => str + e));
+          // close braces
+          while (i-- > 0) {
+            sb.AppendLine("}");
+          }
+          sb.AppendLine("break;");
+        } else {
+          sb.AppendLine("yield return Enumerable.Empty<int>();");
+          sb.AppendLine("break;");
+        }
+        sb.AppendLine("}");
+      }
+      sb.AppendLine("} }");
+      return sb.ToString();
+    }
+
+    private string GenerateInterpreterSource(AttributedGrammar grammar) {
+      var sb = new StringBuilder();
+
+
       // find formal parameters of root node
-      string formalParameter = definition.NonTerminals.Single(nt => nt.Ident == g.RootSymbol).FormalParameters;
+      var attr = grammar.StartSymbol.Attributes;
+
+      var formalParameter = grammar.StartSymbol.GetAttributeString();
       // actual parameter are the same as formalparameter only without type identifier
-      var actualParameterEnumerable =
-        Util.ExtractFormalParameters(formalParameter).Select(e => e.RefOrOut + " " + e.Identifier);
-      string actualParameter = string.Empty;
-      // generate a string of actual parameters beginning with: ', a0, a1, ...'
-      if (actualParameterEnumerable.Any()) {
-        foreach (var e in actualParameterEnumerable) {
-          actualParameter += ", " + e;
-        }
-      }
+      string actualParameter;
+      if (attr.Any())
+        actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
+      else
+        actualParameter = string.Empty;
+
       // generate entry method for evaluation. This is called from the min/max function
       // e.g.: ProgramRoot(ref int a0) { ProgramRoot(rootNode , ref a0); }
-      sb.AppendFormat("void {0}({1}) {{ {0}(currentPath {2}); }}", g.RootSymbol, formalParameter, actualParameter).AppendLine();
+      sb.AppendFormat("void {0}({1}) {{", grammar.StartSymbol.Name, formalParameter).AppendLine();
+      sb.AppendLine(" var path = currentPath.GetEnumerator();");
+      sb.AppendFormat("{0}(path, {1});", grammar.StartSymbol.Name, actualParameter).AppendLine();
+      sb.AppendLine("if(path.MoveNext()) throw new InvalidOperationException(); // assert that the full path has been processed");
+      sb.AppendLine("}");
 
       // generate methods for all nonterminals and terminals using the grammar instance
-      foreach (var s in definition.NonTerminals) {
-        sb.AppendLine(GenerateInterpreterMethod(g, s));
-      }
-      foreach (var s in definition.Terminals) {
-        sb.AppendLine(GenerateTerminalInterpreterMethod((TerminalNode)s));
-      }
-      return sb.ToString();
-    }
-
-    private string GenerateTerminalInterpreterMethod(TerminalNode s) {
+      foreach (var s in grammar.NonTerminalSymbols) {
+        sb.AppendLine(GenerateInterpreterMethod(grammar, s));
+      }
+      foreach (var s in grammar.TerminalSymbols) {
+        sb.AppendLine(GenerateTerminalInterpreterMethod(s));
+      }
+      return sb.ToString();
+    }
+
+    private string GenerateTerminalInterpreterMethod(ISymbol s) {
       var sb = new StringBuilder();
       // if the terminal symbol has attributes then we must create values for these attributes
-      if (!s.FormalParameters.Any())
-        sb.AppendFormat("private void {0}(IEnumerator<int> path) {{", s.Ident);
+      if (!s.Attributes.Any())
+        sb.AppendFormat("private void {0}(IEnumerator<int> path) {{", s.Name);
       else
-        sb.AppendFormat("private void {0}(IEnumerator<int> path, {1}) {{", s.Ident, s.FormalParameters);
+        sb.AppendFormat("private void {0}(IEnumerator<int> path, {1}) {{", s.Name, s.GetAttributeString());
 
       // each field must match a formal parameter, assign a value for each parameter
-      foreach (var element in s.FieldDefinitions) {
+      foreach (var element in s.Attributes) {
         // read next symbol
         sb.AppendLine("path.MoveNext();");
-        sb.AppendFormat("{0} = Get{1}_{0}Element(path.Current)", element.Identifier, s.Ident).AppendLine(";");
-      }
-      sb.AppendLine("}");
-      return sb.ToString();
-    }
-
-    private string GenerateInterpreterMethod(Grammar g, SymbolNode s) {
-      var sb = new StringBuilder();
-      if (!s.FormalParameters.Any())
-        sb.AppendFormat("private void {0}(IEnumerator<int> path) {{", s.Ident);
+        sb.AppendFormat("{0} = Get{1}_{0}Element(path.Current)", element.Name, s.Name).AppendLine(";");
+      }
+      sb.AppendLine("}");
+      return sb.ToString();
+    }
+
+    private string GenerateInterpreterMethod(AttributedGrammar g, ISymbol s) {
+      var sb = new StringBuilder();
+      if (!s.Attributes.Any())
+        sb.AppendFormat("private void {0}(IEnumerator<int> path) {{", s.Name);
       else
-        sb.AppendFormat("private void {0}(IEnumerator<int> path, {1}) {{", s.Ident, s.FormalParameters);
+        sb.AppendFormat("private void {0}(IEnumerator<int> path, {1}) {{", s.Name, s.GetAttributeString());
       // generate local definitions
-      sb.AppendLine(g.GetLocalDefinitions(s.Ident));
-
-      // read next symbol
-      sb.AppendLine("path.MoveNext();");
+      sb.AppendLine(g.GetLocalDefinitions(s));
+
 
       // if there are alternatives for this symbol -> choose alternative based on the path
-      var alts = g.GetAlternatives(s.Ident);
+      var alts = g.GetAlternatives(s);
       if (alts.Count() > 1) {
+        // read next symbol
+        sb.AppendLine("path.MoveNext();");
         int i = 0;
         sb.AppendLine("switch(path.Current) {");
@@ -300 +431 @@
         foreach (var l in alts) {
           sb.AppendFormat("case {0}: {{ ", i).AppendLine();
-          foreach (var e in g.GetSequenceWithSemanticActions(s.Ident, i++)) {
-            sb.AppendLine(GenerateSourceForAction(e));
+          foreach (var altS in g.GetAlternativeWithSemanticActions(s, i++)) {
+            sb.AppendLine(GenerateSourceForAction(altS));
           }
           sb.AppendLine("break;").AppendLine("}");
         }
-        sb.AppendLine("} else throw new System.InvalidOperationException()").AppendLine();
+        sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}");
       } else {
-        foreach (var e in g.GetSequenceWithSemanticActions(s.Ident, 0)) {
-          sb.AppendLine(GenerateSourceForAction(e));
+        foreach (var altS in g.GetAlternativeWithSemanticActions(s, 0)) {
+          sb.AppendLine(GenerateSourceForAction(altS));
         }
       }
@@ -316 +447 @@
 
     // helper for generating calls to other symbol methods
-    private string GenerateSourceForAction(RuleExprNode e) {
-      var action = e as RuleActionNode;
-      var call = e as CallSymbolNode;
+    private string GenerateSourceForAction(ISymbol s) {
+      var action = s as SemanticSymbol;
       if (action != null) {
-        return action.SrcCode + ";";
-      } else if (call != null) {
-        if (!call.ActualParameter.Any())
-          return string.Format("{0}(path);", call.Ident);
+        return action.Code + ";";
+      } else {
+        if (!s.Attributes.Any())
+          return string.Format("{0}(path);", s.Name);
         else
-          return string.Format("{0}(path, {1});", call.Ident, call.ActualParameter);
-      } else {
-        throw new ArgumentException();
+          return string.Format("{0}(path, {1});", s.Name, s.GetAttributeString());
       }
     }