Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs @ 10080

Last change on this file since 10080 was 10080, checked in by gkronber, 9 years ago

#2026 implemented a code generator for random search solvers for GPDL problems

File size: 14.3 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Diagnostics;
4using System.IO;
5using System.Linq;
6using System.Text;
7using HeuristicLab.Grammars;
8using Attribute = HeuristicLab.Grammars.Attribute;
9
10namespace CodeGenerator {
11  public class BruteForceCodeGen {
12
13    private string usings = @"
14using System.Collections.Generic;
15using System.Linq;
16using System;
17";
18
19    private string solverTemplate = @"
20namespace ?PROBLEMNAME? {
21  public sealed class ?IDENT?Solver {
22
23    public static void Main(string[] args) {
24      var solver = new ?IDENT?Solver();
25      solver.Start();
26    }
27
28    public ?IDENT?Solver() {
29      Initialize();
30    }   
31
32    private void Initialize() {
33      ?INITCODE?
34    }
35
36    private bool IsBetter(double a, double b) {
37      return ?MAXIMIZATION? ? a > b : a < b;
38    }
39
40    private class SearchTree {
41      private SearchTree[] subTrees;
42      public bool Done { get; private set; }
43      private int nextAlternative;
44
45      public SearchTree() {
46        Done = false;
47      }
48
49      public SearchTree GetSubtree(int i) {
50        // if (subTrees[i] == null) subTrees[i] = new SearchTree();
51        return subTrees[i];
52      }
53
54      public int GetNextAlternative() {
55        System.Diagnostics.Debug.Assert(IsAlternativeNode);
56        return nextAlternative;
57      }
58
59      public bool IsUninitialized {
60        get { return subTrees == null; }
61      }
62
63      public void SetNumberOfSubtrees(int n) {
64        this.subTrees = new SearchTree[n];
65        for(int i=0;i<n;i++) this.subTrees[i] = new SearchTree();
66        nextAlternative = 0;
67      }
68
69      public void UpdatePath() {
70        System.Diagnostics.Debug.Assert(!Done);
71        if (IsUninitialized) { return; }
72        Count++;
73        if (subTrees.Length == 0) {
74          Done = true;
75        }
76        if (IsAlternativeNode) {
77          // update only the active alternative and calculate a new alternative
78          subTrees[nextAlternative].UpdatePath();
79
80          do {
81            nextAlternative = (nextAlternative + 1) % subTrees.Length;
82          } while (subTrees[nextAlternative] != null && subTrees[nextAlternative].Done);
83
84          // from the nodes which are not done take the first with minimum count
85          //nextAlternative = (from i in Enumerable.Range(0, subTrees.Length)
86          //                   where subTrees[i] == null || !subTrees[i].Done
87          //                   orderby subTrees[i]==null?0:subTrees[i].Count ascending
88          //                   select i).FirstOrDefault(); // possibly there are no children left that can be tried
89        } else {
90          // for sequenceNodes update all sub-trees
91          foreach (var t in subTrees) t.UpdatePath();
92        }
93        // set node to done if all nodes are non-null and done
94        this.Done = true;
95        foreach(var t in subTrees) {
96          if(t == null || !t.Done)
97            { this.Done = false; break; }
98        }       
99      }
100
101      public bool IsAlternativeNode { get; set; }
102      public bool IsSequenceNode { get; set; }
103      public int Count { get; private set; }
104    }
105
106    private SearchTree tree;
107    private void Start() {
108      // start with empty tree
109      tree = new SearchTree();
110      var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
111      int n = 0;
112      var sw = new System.Diagnostics.Stopwatch();
113      sw.Start();
114      while (!tree.Done) {
115
116        var f = Calculate();
117        // do one more run through the tree to update the path
118        tree.UpdatePath();
119
120        n++;
121        if (IsBetter(f, bestF)) bestF = f;
122        if (n % 100 == 0) {
123          sw.Stop();
124          Console.WriteLine(""{0}\t{1}\t{2}\t({3:0.00} sols/ms)"", n, bestF, f, 100.0 / sw.ElapsedMilliseconds);
125          sw.Reset();
126          sw.Start();
127        }
128      }
129    }
130
131    public double Calculate() {
132      ?FITNESSFUNCTION?
133    }
134
135    ?ADDITIONALCODE?
136
137    ?INTERPRETERSOURCE?
138
139    ?CONSTRAINTSSOURCE?
140  }
141}";
142
143
144    /// <summary>
145    /// Generates the source code for a brute force searcher that can be compiled with a C# compiler
146    /// </summary>
147    /// <param name="ast">An abstract syntax tree for a GPDL file</param>
148    public void Generate(GPDefNode ast) {
149      var problemSourceCode = new StringBuilder();
150      problemSourceCode.AppendLine(usings);
151
152      GenerateProblem(ast, problemSourceCode);
153
154      problemSourceCode.Replace("?PROBLEMNAME?", ast.Name);
155
156      // write the source file to disk
157      using (var stream = new StreamWriter(ast.Name + ".cs")) {
158        stream.WriteLine(problemSourceCode.ToString());
159      }
160    }
161
162    private void GenerateProblem(GPDefNode ast, StringBuilder problemSourceCode) {
163      var grammar = CreateGrammarFromAst(ast);
164      var problemClassCode =
165        solverTemplate
166          .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant())
167          .Replace("?IDENT?", ast.Name)
168          .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
169          .Replace("?INTERPRETERSOURCE?", GenerateInterpreterSource(grammar))
170          .Replace("?INITCODE?", ast.InitCodeNode.SrcCode)
171          .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
172          .Replace("?CONSTRAINTSSOURCE?", GenerateConstraintMethods(ast.Terminals))
173          ;
174
175      problemSourceCode.AppendLine(problemClassCode).AppendLine();
176    }
177
178    private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
179      string startSymbolName = ast.Rules.First().NtSymbol;
180      var startSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == startSymbolName);
181      // create startSymbol
182      var g = new AttributedGrammar(new Symbol(startSymbolName, ParseSymbolAttributes(startSymbolNode.FormalParameters)));
183      foreach (var rule in ast.Rules) {
184        // create nt-symbol
185        var ntSymbolName = rule.NtSymbol;
186        var ntSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == ntSymbolName);
187        var attributes = ParseSymbolAttributes(ntSymbolNode.FormalParameters);
188        var ntSymbol = new Symbol(ntSymbolName, attributes);
189        foreach (var alt in GetAlternatives(rule.Alternatives)) {
190          g.AddProductionRule(ntSymbol, alt);
191        }
192        // local initialization code
193        if (!string.IsNullOrEmpty(rule.LocalCode)) g.AddLocalDefinitions(ntSymbol, rule.LocalCode);
194      }
195      return g;
196    }
197
198    private IEnumerable<IAttribute> ParseSymbolAttributes(string formalParameters) {
199      return (from fieldDef in Util.ExtractParameters(formalParameters)
200              select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
201        ToList();
202    }
203
204    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode) {
205      foreach (var alt in altNode.Alternatives) {
206        yield return GetSequence(alt.Sequence);
207      }
208    }
209
210    private Sequence GetSequence(IEnumerable<RuleExprNode> sequence) {
211      Debug.Assert(sequence.All(s => s is CallSymbolNode || s is RuleActionNode));
212      var l = new List<ISymbol>();
213      foreach (var node in sequence) {
214        var callSymbolNode = node as CallSymbolNode;
215        var actionNode = node as RuleActionNode;
216        if (callSymbolNode != null) {
217          l.Add(new Symbol(callSymbolNode.Ident, ParseSymbolAttributes(callSymbolNode.ActualParameter)));
218        } else if (actionNode != null) {
219          l.Add(new SemanticSymbol("SEM", actionNode.SrcCode));
220        }
221      }
222      return new Sequence(l);
223    }
224
225    // produces helper methods for the attributes of all terminal nodes
226    private string GenerateConstraintMethods(List<SymbolNode> symbols) {
227      var sb = new StringBuilder();
228      var terminals = symbols.OfType<TerminalNode>();
229      foreach (var t in terminals) {
230        sb.AppendLine(GenerateConstraintMethods(t));
231      }
232      return sb.ToString();
233    }
234
235    // generates helper methods for the attributes of a given terminal node
236    private string GenerateConstraintMethods(TerminalNode t) {
237      var sb = new StringBuilder();
238      foreach (var c in t.Constraints) {
239        var fieldType = t.FieldDefinitions.First(d => d.Identifier == c.Ident).Type;
240        if (c.Type == ConstraintNodeType.Range) {
241          sb.AppendFormat("public {0} GetMax{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMaxExpression).AppendLine();
242          sb.AppendFormat("public {0} GetMin{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMinExpression).AppendLine();
243        } else if (c.Type == ConstraintNodeType.Set) {
244          sb.AppendFormat("public {0}[] GetAllowed{1}_{2}() {{ return {3}.ToArray(); }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
245        }
246        sb.AppendFormat("public {0} Get{1}_{2}Element(int i) {{ return GetAllowed{1}_{2}()[i]; }}", fieldType, t.Ident, c.Ident);
247      }
248      return sb.ToString();
249    }
250
251    private string GenerateInterpreterSource(AttributedGrammar grammar) {
252      var sb = new StringBuilder();
253
254
255      // get formal parameters of start symbol
256      var attr = grammar.StartSymbol.Attributes;
257
258      var formalParameter = grammar.StartSymbol.GetAttributeString();
259      // actual parameter are the same as formalparameter only without type identifier
260      string actualParameter;
261      if (attr.Any())
262        actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
263      else
264        actualParameter = string.Empty;
265
266      // generate entry method for evaluation. This is called from the min/max function
267      // e.g.: ProgramRoot(ref int a0) { ProgramRoot(rootNode , ref a0); }
268      sb.AppendFormat("void {0}({1}) {{", grammar.StartSymbol.Name, formalParameter).AppendLine();
269      sb.AppendFormat("{0}(tree, {1});", grammar.StartSymbol.Name, actualParameter).AppendLine();
270      sb.AppendLine("}");
271
272      // generate methods for all nonterminals and terminals using the grammar instance
273      foreach (var s in grammar.NonTerminalSymbols) {
274        sb.AppendLine(GenerateInterpreterMethod(grammar, s));
275      }
276      foreach (var s in grammar.TerminalSymbols) {
277        sb.AppendLine(GenerateTerminalInterpreterMethod(s));
278      }
279      return sb.ToString();
280    }
281
282    private string GenerateTerminalInterpreterMethod(ISymbol s) {
283      var sb = new StringBuilder();
284      // if the terminal symbol has attributes then we must create values for these attributes
285      if (!s.Attributes.Any())
286        sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
287      else
288        sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());
289
290      sb.AppendFormat("if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", s.Attributes.Count());
291      // each field must match a formal parameter, assign a value for each parameter
292      int i = 0;
293      foreach (var element in s.Attributes) {
294        // read next symbol
295        sb.AppendLine("throw new NotImplementedException(); // this is not yet supported ");
296        sb.AppendFormat("{0} = Get{1}_{0}Element(tree.GetSubTree({2}).GetAlternative())", element.Name, s.Name, i++).AppendLine(";");
297      }
298      sb.AppendLine("}");
299      return sb.ToString();
300    }
301
302    private string GenerateInterpreterMethod(AttributedGrammar g, ISymbol s) {
303      var sb = new StringBuilder();
304      if (!s.Attributes.Any())
305        sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
306      else
307        sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());
308
309      // generate local definitions
310      sb.AppendLine(g.GetLocalDefinitions(s));
311
312
313
314      // make sure we first descent into terminal alternatives -> we just order by number of non-terminals in the alternative
315      var altsWithSemActions = g.GetAlternativesWithSemanticActions(s).OrderBy(alt => alt.Count(symb => g.IsNonTerminal(symb))).ToArray();
316
317      if (altsWithSemActions.Length > 1) {
318        sb.AppendFormat("      if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsAlternativeNode = true; }}", altsWithSemActions.Length);
319
320        int i = 0;
321        sb.AppendLine("switch(tree.GetNextAlternative()) {");
322        // generate a case for each alternative
323        foreach (var alt in altsWithSemActions) {
324          sb.AppendFormat("case {0}: {{ ", i).AppendLine();
325          sb.AppendLine("SearchTree subtree = null; ");
326
327          // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far!
328          // handling multiple non-terminals here would require a change in the structure of the search tree
329          // another way to handle this is through grammar transformation (the examplary grammars all have the correct from)
330          Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1);
331          foreach (var altSymb in alt) {
332            if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", i);
333            sb.AppendLine(GenerateSourceForAction(altSymb));
334          }
335          i++;
336          sb.AppendLine("break;").AppendLine("}");
337        }
338        sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}");
339      } else {
340        sb.AppendFormat("      if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", altsWithSemActions.Single().Count(symb => !(symb is SemanticSymbol)));
341        int j = 0;
342        sb.AppendLine("SearchTree subtree = null; ");
343        foreach (var altSymb in altsWithSemActions.Single()) {
344          if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", j++);
345          sb.AppendLine(GenerateSourceForAction(altSymb));
346        }
347      }
348      sb.AppendLine("}");
349      return sb.ToString();
350    }
351
352    // helper for generating calls to other symbol methods
353    private string GenerateSourceForAction(ISymbol s) {
354      var action = s as SemanticSymbol;
355      if (action != null) {
356        return action.Code + ";";
357      } else {
358        if (!s.Attributes.Any())
359          return string.Format("{0}(subtree);", s.Name);
360        else
361          return string.Format("{0}(subtree, {1});", s.Name, s.GetAttributeString());
362      }
363    }
364  }
365}
Note: See TracBrowser for help on using the repository browser.