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