Free cookie consent management tool by TermsFeed Policy Generator

Changeset 10335


Ignore:
Timestamp:
01/14/14 12:40:26 (11 years ago)
Author:
gkronber
Message:

#2026 worked on code generator for random search (work in progress commit)

Location:
branches/HeuristicLab.Problems.GPDL
Files:
4 edited

Legend:

Unmodified
Added
Removed

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

    r10086 r10335  
    22using System.Collections.Generic;
    33using System.Diagnostics;
    4 using System.IO;
    54using System.Linq;
    6 using System.Text;
    75using HeuristicLab.Grammars;
    8 using Attribute = HeuristicLab.Grammars.Attribute;
    96
    107namespace CodeGenerator {
    118  public class BruteForceCodeGen {
    12 
    13     private string usings = @"
    14 using System.Collections.Generic;
    15 using System.Linq;
    16 using System;
    17 ";
    18 
    199    private string solverTemplate = @"
    2010namespace ?PROBLEMNAME? {
    2111  public sealed class ?IDENT?Solver {
    2212
     13    private static Dictionary<int, int[]> transition = new Dictionary<int, int[]>() {
     14?TRANSITIONTABLE?
     15    };
     16    private static Dictionary<int, int> subtreeCount = new Dictionary<int, int>() {
     17       { -1, 0 }, // terminals
     18?SUBTREECOUNTTABLE?
     19    };
     20
     21    private static string[] symb = new string[] { ?SYMBOLNAMES? };
     22    private static bool[] isTerminal = new bool[] { ?TERMINALTABLE? };
     23    private static bool[] hasAlternatives = new bool[] {?HASALTERNATIVESTABLE? };
     24
     25   
     26    public sealed class SolverState : ISolverState {
     27      private class Node {
     28        public int state;
     29        public int count;
     30        public List<Node> nodes;
     31        public bool done;
     32        private int nextAlt;
     33        public Node(int state) {
     34          this.state = state;
     35          nodes = new List<Node>(transition[state].Length);
     36          if (!hasAlternatives[state]) {
     37            foreach (var t in transition[state]) { nodes.Add(new Node(t)); }
     38          }
     39        }
     40
     41        public int GetNextAlternative() {
     42          System.Diagnostics.Debug.Assert(hasAlternatives[state]);
     43          if(nodes.Count == 0 && !isTerminal[state]) {
     44            foreach(var targetState in transition[state]) nodes.Add(new Node(targetState));
     45            nextAlt = 0;
     46            // begin with a terminal if possible
     47            if(!isTerminal[nodes[nextAlt].state])
     48              do { nextAlt = (nextAlt + 1) % nodes.Count; } while(nextAlt != 0 /* full circle*/ && !isTerminal[nodes[nextAlt].state]);
     49          }
     50
     51          throw new NotImplementedException(); // TODO: handle terminal classes correctly
     52          return nextAlt;
     53        }
     54
     55        public void Update() {
     56          count++;
     57          if(hasAlternatives[state] && !isTerminal[state]) {
     58            nodes[GetNextAlternative()].Update();
     59            // check if all nodes done and set this node to done
     60            if(nodes.All(n=>n.done)) {
     61              this.done = true;
     62            } else {
     63              // must not walk nodes that are done
     64              do { nextAlt = (nextAlt + 1) % nodes.Count; } while (nodes[nextAlt].done);
     65            }
     66          } else {
     67            if(isTerminal[state]) {
     68              throw new NotImplementedException(); // TODO: handle terminal classes correctly
     69              done = (nextAlt + 1) >= GetAlternativesCount(symb[state]);
     70            } else {
     71              // update the smallest count. this basically means keeping all sub-trees the same and only altering the updated one
     72              Node minNode = nodes.First();
     73              foreach(var node in nodes.Skip(1)) {
     74                if(node.count < minNode.count) {
     75                  minNode = node;
     76                }
     77              }
     78              minNode.Update();
     79              if(nodes.All(n=>n.done)) this.done = true;
     80            }
     81          }
     82        }
     83      }
     84
     85
     86      ?ALTERNATIVESCOUNTMETHOD?
     87
     88
     89      public int curDepth;
     90      public int steps;
     91      public int depth;
     92      private readonly Stack<Node> nodes;
     93      private readonly IGpdlProblem problem;
     94      private readonly Node searchTree;
     95
     96      public SolverState(IGpdlProblem problem) {
     97        this.problem = problem;
     98        nodes = new Stack<Node>();
     99        searchTree = new Node(0);
     100        nodes.Push(searchTree);
     101      }
     102
     103      public void Reset() {
     104        System.Diagnostics.Debug.Assert(nodes.Count == 1);
     105        steps = 0;
     106        depth = 0;
     107        curDepth = 0;
     108      }
     109
     110      public int PeekNextAlternative() {
     111        var curNode = nodes.Peek();
     112        System.Diagnostics.Debug.Assert(hasAlternatives[curNode.state]);
     113        return curNode.GetNextAlternative();
     114      }
     115
     116      public void Follow(int idx) {
     117        steps++;
     118        curDepth++;
     119        depth = Math.Max(depth, curDepth);
     120        var curNode = nodes.Peek();
     121        if(hasAlternatives[curNode.state]) {
     122          nodes.Push(curNode.nodes[curNode.GetNextAlternative()]);
     123        } else {
     124          nodes.Push(curNode.nodes[idx]);
     125        }
     126      }
     127
     128      public void Unwind() {
     129        nodes.Pop();
     130        curDepth--;
     131      }
     132
     133      public void Update() {
     134        searchTree.Update();
     135      }
     136    }
     137
    23138    public static void Main(string[] args) {
    24       var solver = new ?IDENT?Solver();
     139      var problem = new ?IDENT?Problem();
     140      var solver = new ?IDENT?Solver(problem);
    25141      solver.Start();
    26142    }
    27 
    28     public ?IDENT?Solver() {
    29       Initialize();
    30     }   
    31 
    32     private void Initialize() {
    33       ?INITCODE?
     143   
     144    private readonly ?IDENT?Problem problem;
     145    public ?IDENT?Solver(?IDENT?Problem problem) {
     146      this.problem = problem;
     147    }
     148
     149    private void Start() {
     150      var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
     151      int n = 0;
     152      long sumDepth = 0;
     153      long sumSize = 0;
     154      var sumF = 0.0;
     155      var sw = new System.Diagnostics.Stopwatch();
     156      sw.Start();
     157      var _state = new SolverState(problem);
     158      while (true) {
     159
     160        var f = problem.Evaluate(_state);
     161        _state.Update();
     162
     163        n++;
     164        sumSize += _state.steps;
     165        sumDepth += _state.depth;
     166        sumF += f;
     167        if (IsBetter(f, bestF)) {
     168          // evaluate again with tracing to console
     169          // problem.Evaluate(new SolverState(_state.seed, true));
     170          bestF = f;
     171          Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, _state.steps, _state.depth);
     172        }
     173        if (n % 1000 == 0) {
     174          sw.Stop();
     175          Console.WriteLine(""{0}\tbest: {1:0.000}\t(avg: {2:0.000})\t(avg size: {3:0.0})\t(avg. depth: {4:0.0})\t({5:0.00} sols/ms)"", n, bestF, sumF/1000.0, sumSize/1000.0, sumDepth/1000.0, 1000.0 / sw.ElapsedMilliseconds);
     176          sw.Reset();
     177          sumSize = 0;
     178          sumDepth = 0;
     179          sumF = 0.0;
     180          sw.Start();
     181        }
     182      }
    34183    }
    35184
    … …  
    37186      return ?MAXIMIZATION? ? a > b : a < b;
    38187    }
    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         } else {
    84           // for sequenceNodes update all sub-trees
    85           foreach (var t in subTrees) t.UpdatePath();
    86         }
    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         }       
    93       }
    94 
    95       public bool IsAlternativeNode { get; set; }
    96       public bool IsSequenceNode { get; set; }
    97       public int Count { get; private set; }
    98     }
    99 
    100     private SearchTree tree;
    101     private void Start() {
    102       // start with empty tree
    103       tree = new SearchTree();
    104       var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
    105       int n = 0;
    106       var sw = new System.Diagnostics.Stopwatch();
    107       sw.Start();
    108       while (!tree.Done) {
    109 
    110         var f = Calculate();
    111         // do one more run through the tree to update the path
    112         tree.UpdatePath();
    113 
    114         n++;
    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         }
    122       }
    123     }
    124 
    125     public double Calculate() {
    126       ?FITNESSFUNCTION?
    127     }
    128 
    129     ?ADDITIONALCODE?
    130 
    131     ?INTERPRETERSOURCE?
    132 
    133     ?CONSTRAINTSSOURCE?
    134188  }
    135189}";
    136190
    137191
    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 
    150       // write the source file to disk
    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) {
    157       var grammar = CreateGrammarFromAst(ast);
    158       var problemClassCode =
    159         solverTemplate
    160           .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant())
    161           .Replace("?IDENT?", ast.Name)
    162           .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
    163           .Replace("?INTERPRETERSOURCE?", GenerateInterpreterSource(grammar))
    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 
    172     private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
    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();
    176       string startSymbolName = ast.Rules.First().NtSymbol;
    177 
    178       // create startSymbol
    179       var startSymbol = nonTerminals.Single(s => s.Name == startSymbolName);
    180       var g = new AttributedGrammar(startSymbol, nonTerminals, terminals);
    181 
    182       // add all production rules
    183       foreach (var rule in ast.Rules) {
    184         var ntSymbol = nonTerminals.Single(s => s.Name == rule.NtSymbol);
    185         foreach (var alt in GetAlternatives(rule.Alternatives, nonTerminals.Concat(terminals))) {
    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 
    194     private IEnumerable<IAttribute> GetSymbolAttributes(string formalParameters) {
    195       return (from fieldDef in Util.ExtractParameters(formalParameters)
    196               select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
    197         ToList();
    198     }
    199 
    200     private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode, IEnumerable<ISymbol> allSymbols) {
    201       foreach (var alt in altNode.Alternatives) {
    202         yield return GetSequence(alt.Sequence, allSymbols);
    203       }
    204     }
    205 
    206     private Sequence GetSequence(IEnumerable<RuleExprNode> sequence, IEnumerable<ISymbol> allSymbols) {
    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) {
    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)));
    216         } else if (actionNode != null) {
    217           l.Add(new SemanticSymbol("SEM", actionNode.SrcCode));
    218         }
    219       }
    220       return new Sequence(l);
    221     }
    222 
    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));
     192    public void Generate(IGrammar grammar, bool maximization, SourceBuilder problemSourceCode) {
     193      var solverSourceCode = new SourceBuilder();
     194      solverSourceCode.Append(solverTemplate)
     195        .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
     196        .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", "))
     197        .Replace("?TERMINALTABLE?", grammar.Symbols.Select(grammar.IsTerminal).Aggregate(string.Empty, (str, b) => str + b.ToString().ToLowerInvariant() + ", "))
     198        .Replace("?HASALTERNATIVESTABLE?", grammar.Symbols.Select(s => grammar.IsNonTerminal(s) && (grammar.NumberOfAlternatives(s) > 1)).Aggregate(string.Empty, (str, b) => str + b.ToString().ToLowerInvariant() + ", "))
     199        .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar))
     200        .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))
     201        .Replace("?ALTERNATIVESCOUNTMETHOD?", GenerateAlternativesCountMethod(grammar))
     202      ;
     203
     204      problemSourceCode.Append(solverSourceCode.ToString());
     205    }
     206
     207    #region same as random search
     208    private string GenerateTransitionTable(IGrammar grammar) {
     209      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
     210      var sb = new SourceBuilder();
     211
     212      // state idx = idx of the corresponding symbol in the grammar
     213      var allSymbols = grammar.Symbols.ToList();
     214      var attributes = new List<string>();
     215      foreach (var s in grammar.Symbols) {
     216        var targetStates = new List<int>();
     217        if (grammar.IsTerminal(s)) {
     218          foreach (var att in s.Attributes) {
     219            targetStates.Add(allSymbols.Count + attributes.Count);
     220            attributes.Add(s.Name + "_" + att);
     221          }
     222        } else {
     223          if (grammar.NumberOfAlternatives(s) > 1) {
     224            foreach (var alt in grammar.GetAlternatives(s)) {
     225              // only single-symbol alternatives are supported
     226              Debug.Assert(alt.Count() == 1);
     227              targetStates.Add(allSymbols.IndexOf(alt.Single()));
     228            }
     229          } else {
     230            // rule is a sequence of symbols
     231            var seq = grammar.GetAlternatives(s).Single();
     232            targetStates.AddRange(seq.Select(symb => allSymbols.IndexOf(symb)));
     233          }
     234        }
     235
     236        var targetStateString = targetStates.Aggregate(string.Empty, (str, state) => str + state + ", ");
     237
     238        var idxOfSourceState = allSymbols.IndexOf(s);
     239        sb.AppendFormat("// {0}", s).AppendLine();
     240        sb.AppendFormat("{{ {0} , new int[] {{ {1} }} }},", idxOfSourceState, targetStateString).AppendLine();
     241      }
     242      for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
     243        sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();
     244        sb.AppendFormat("{{ {0} , new int[] {{ }} }},", attIdx + allSymbols.Count).AppendLine();
    229245      }
    230246      return sb.ToString();
    231247    }
    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);
     248    private string GenerateSubtreeCountTable(IGrammar grammar) {
     249      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
     250      var sb = new SourceBuilder();
     251
     252      // state idx = idx of the corresponding symbol in the grammar
     253      var allSymbols = grammar.Symbols.ToList();
     254      var attributes = new List<string>();
     255      foreach (var s in grammar.Symbols) {
     256        int subtreeCount;
     257        if (grammar.IsTerminal(s)) {
     258          subtreeCount = s.Attributes.Count();
     259          attributes.AddRange(s.Attributes.Select(att => s.Name + "_" + att.Name));
     260        } else {
     261          if (grammar.NumberOfAlternatives(s) > 1) {
     262            Debug.Assert(grammar.GetAlternatives(s).All(alt => alt.Count() == 1));
     263            subtreeCount = 1;
     264          } else {
     265            subtreeCount = grammar.GetAlternative(s, 0).Count();
     266          }
     267        }
     268
     269        sb.AppendFormat("// {0}", s).AppendLine();
     270        sb.AppendFormat("{{ {0} , {1} }},", allSymbols.IndexOf(s), subtreeCount).AppendLine();
     271      }
     272
     273      for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
     274        sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();
     275        sb.AppendFormat("{{ {0} , 1 }},", attIdx + allSymbols.Count).AppendLine();
    245276      }
    246277      return sb.ToString();
    247278    }
    248 
    249     private string GenerateInterpreterSource(AttributedGrammar grammar) {
    250       var sb = new StringBuilder();
    251 
    252 
    253       // get formal parameters of start symbol
    254       var attr = grammar.StartSymbol.Attributes;
    255 
    256       var formalParameter = grammar.StartSymbol.GetAttributeString();
    257       // actual parameter are the same as formalparameter only without type identifier
    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 
    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); }
    266       sb.AppendFormat("void {0}({1}) {{", grammar.StartSymbol.Name, formalParameter).AppendLine();
    267       sb.AppendFormat("{0}(tree, {1});", grammar.StartSymbol.Name, actualParameter).AppendLine();
    268       sb.AppendLine("}");
    269 
    270       // generate methods for all nonterminals and terminals using the grammar instance
    271       foreach (var s in grammar.NonTerminalSymbols) {
    272         sb.AppendLine(GenerateInterpreterMethod(grammar, s));
    273       }
    274       foreach (var s in grammar.TerminalSymbols) {
    275         sb.AppendLine(GenerateTerminalInterpreterMethod(s));
    276       }
     279    #endregion
     280    private string GenerateAlternativesCountMethod(IGrammar grammar) {
     281      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
     282      var sb = new SourceBuilder();
     283      sb.Append("public int GetAlternativesCount(string symbol, string attribute = null) {").BeginBlock();
     284      sb.AppendLine("switch(symbol) {");
     285      foreach (var s in grammar.Symbols) {
     286        sb.AppendFormat("case \"{0}\":", s.Name).AppendLine();
     287        int altCount;
     288        if (grammar.IsTerminal(s)) {
     289          if (s.Attributes.Any()) {
     290            sb.Append("switch(attribute) {").BeginBlock();
     291            foreach (var att in s.Attributes) {
     292              sb.AppendFormat("case \"{1}\": return problem.GetCardinality(\"{0}\", \"{1}\");", s.Name, att.Name).AppendLine();
     293            }
     294            sb.Append("} // switch").EndBlock();
     295          } else {
     296            sb.AppendLine("return 0;");
     297          }
     298        } else {
     299          sb.AppendFormat("return {0};", grammar.NumberOfAlternatives(s)).AppendLine();
     300        }
     301
     302
     303      }
     304      sb.AppendLine("} // switch");
     305      sb.Append("}").EndBlock();
    277306      return sb.ToString();
    278     }
    279 
    280     private string GenerateTerminalInterpreterMethod(ISymbol s) {
    281       var sb = new StringBuilder();
    282       // if the terminal symbol has attributes then we must create values for these attributes
    283       if (!s.Attributes.Any())
    284         sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
    285       else
    286         sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());
    287 
    288       sb.AppendFormat("if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", s.Attributes.Count());
    289       // each field must match a formal parameter, assign a value for each parameter
    290       int i = 0;
    291       foreach (var element in s.Attributes) {
    292         // read next symbol
    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(";");
    295       }
    296       sb.AppendLine("}");
    297       return sb.ToString();
    298     }
    299 
    300     private string GenerateInterpreterMethod(AttributedGrammar g, ISymbol s) {
    301       var sb = new StringBuilder();
    302       if (!s.Attributes.Any())
    303         sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
    304       else
    305         sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());
    306 
    307       // generate local definitions
    308       sb.AppendLine(g.GetLocalDefinitions(s));
    309 
    310 
    311 
    312       // make sure we first descent into terminal alternatives -> we just order by number of non-terminals in the alternative
    313       var altsWithSemActions = g.GetAlternativesWithSemanticActions(s)
    314         .OrderBy(alt => alt.Count(symb => g.IsNonTerminal(symb))).ToArray();
    315 
    316       if (altsWithSemActions.Length > 1) {
    317         sb.AppendFormat("      if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsAlternativeNode = true; }}", altsWithSemActions.Length);
    318 
    319         int i = 0;
    320         sb.AppendLine("switch(tree.GetNextAlternative()) {");
    321         // generate a case for each alternative
    322         foreach (var alt in altsWithSemActions) {
    323           sb.AppendFormat("case {0}: {{ ", i).AppendLine();
    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));
    333           }
    334           i++;
    335           sb.AppendLine("break;").AppendLine("}");
    336         }
    337         sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}");
    338       } else {
    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));
    345         }
    346       }
    347       sb.AppendLine("}");
    348       return sb.ToString();
    349     }
    350 
    351     // helper for generating calls to other symbol methods
    352     private string GenerateSourceForAction(ISymbol s) {
    353       var action = s as SemanticSymbol;
    354       if (action != null) {
    355         return action.Code + ";";
    356       } else {
    357         if (!s.Attributes.Any())
    358           return string.Format("{0}(subtree);", s.Name);
    359         else
    360           return string.Format("{0}(subtree, {1});", s.Name, s.GetAttributeString());
    361       }
    362307    }
    363308  }

  • branches/HeuristicLab.Problems.GPDL/CodeGenerator/ProblemCodeGen.cs

    r10100 r10335  
    1818    private const string problemTemplate = @"
    1919namespace ?PROBLEMNAME? {
    20   public interface IGpdlProblem {
    21     int GetCardinality(string terminalSymbol, string attribute);
    22   }
     20
     21  // generic interface for communication from problem interpretation to solver
    2322  public interface ISolverState {
    2423    void Reset();
    25     int PeekNextAlternative();
    26     void Follow(int idx);
    27     void Unwind();
     24    int PeekNextAlternative(); // in alternative nodes returns the index of the alternative that should be followed
     25    void Follow(int idx); // next: derive the NT symbol with index=idx;
     26    void Unwind(); // finished with deriving the NT symbol
    2827  }
    2928
    30   public sealed class ?IDENT?Problem : IGpdlProblem {
     29  public sealed class ?IDENT?Problem {
    3130   
    32    private readonly Dictionary<string, Dictionary<string, int>> cardinalities = new Dictionary<string, Dictionary<string, int>>();
    3331   public ?IDENT?Problem() {
    3432      Initialize();
    35 
    36 ?CONSTRUCTORSOURCE?
    37 
    3833    }   
    3934
    4035    private void Initialize() {
     36      // the following is the source code from the INIT section of the problem definition
     37#region INIT section
    4138?INITSOURCE?
     39#endregion
    4240    }
    4341
    … …  
    4543    public double Evaluate(ISolverState _state) {
    4644      this._state = _state;
     45#region objective function (MINIMIZE / MAXIMIZE section)
    4746?FITNESSFUNCTION?
    48     }
    49 
     47#endregion
     48    }
     49
     50// additional code from the problem definition (CODE section)
     51#region additional code
    5052?ADDITIONALCODE?
    51 
     53#endregion
     54
     55#region generated source for interpretation
    5256?INTERPRETERSOURCE?
    53 
     57#endregion
     58
     59#region generated code for the constraints for terminals
    5460?CONSTRAINTSSOURCE?
    55 
    56     public int GetCardinality(string terminal, string attribute) {
    57       return cardinalities[terminal][attribute];
    58     }
     61#endregion
    5962  }
    6063}";
    … …  
    7679        .Replace("?IDENT?", ast.Name);
    7780
    78 
    7981      // write the source file to disk
    8082      using (var stream = new StreamWriter(ast.Name + ".cs")) {
    … …  
    8890        .AppendLine(problemTemplate)
    8991        .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
    90         .Replace("?CONSTRUCTORSOURCE?", GenerateConstructorSource(ast))
    9192        .Replace("?INITSOURCE?", ast.InitCodeNode.SrcCode)
    9293        .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
    … …  
    99100      var grammar = CreateGrammarFromAst(ast);
    100101      var randomSearchCodeGen = new RandomSearchCodeGen();
    101       randomSearchCodeGen.Generate(grammar, ast.FitnessFunctionNode.Maximization, ast.Terminals, solverSourceCode);
     102      randomSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
     103      //var bruteForceSearchCodeGen = new BruteForceCodeGen();
     104      //bruteForceSearchCodeGen.Generate(grammar, ast.FitnessFunctionNode.Maximization, solverSourceCode);
    102105    }
    103106
    104107    #region create grammar instance from AST
     108    // should be refactored so that we can directly query the AST
    105109    private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
    106110
    … …  
    131135    private IEnumerable<IAttribute> GetSymbolAttributes(string formalParameters) {
    132136      return (from fieldDef in Util.ExtractParameters(formalParameters)
    133               select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
    134         ToList();
     137              select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut)))
     138              .ToList();
    135139    }
    136140
    … …  
    178182          sb.AppendFormat("public {0} GetMax{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMaxExpression).AppendLine();
    179183          sb.AppendFormat("public {0} GetMin{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMinExpression).AppendLine();
    180           // sb.AppendFormat("public {0} Get{1}_{2}(ISolverState _state) {{ return _state.random.NextDouble() * (GetMax{1}_{2}() - GetMin{1}_{2}()) + GetMin{1}_{2}(); }}", fieldType, t.Ident, c.Ident).AppendLine();
    181           sb.AppendFormat("public {0} Get{1}_{2}(ISolverState _state) {{ throw new NotSupportedException(\"range constraints for terminals are not supported.\"); }}", fieldType, t.Ident, c.Ident).AppendLine();
     184          //sb.AppendFormat("public {0} Get{1}_{2}(ISolverState _state) {{ _state. }}", fieldType, t.Ident, c.Ident, )
    182185        } else if (c.Type == ConstraintNodeType.Set) {
    183186          sb.AppendFormat("public IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
    184           sb.AppendFormat("private readonly {0}[] values_{1}_{2};", fieldType, t.Ident, c.Ident).AppendLine();
    185           sb.AppendFormat("public {0} Get{1}_{2}(ISolverState _state) {{ return values_{1}_{2}[_state.PeekNextAlternative()]; }}", fieldType, t.Ident, c.Ident).AppendLine();
    186         }
    187       }
    188     }
    189     private string GenerateConstructorSource(GPDefNode ast) {
    190       var sb = new SourceBuilder();
    191       // generate code to initialize the tables for terminals
    192       foreach (var t in ast.Terminals.OfType<TerminalNode>()) {
    193         if (t.Constraints.Any()) {
    194           foreach (var constraint in t.Constraints) {
    195             sb.AppendFormat("values_{0}_{1} = GetAllowed{0}_{1}().ToArray();", t.Ident, constraint.Ident);
    196           }
    197           sb.AppendFormat("cardinalities[\"{0}\"] = new Dictionary<string, int>() {{ ", t.Ident);
    198           foreach (var constraint in t.Constraints) {
    199             sb.AppendFormat("{{ \"{1}\", values_{0}_{1}.Length }}, ", t.Ident, constraint.Ident);
    200           }
    201           sb.Append("};").AppendLine();
    202         }
    203       }
    204       return sb.ToString();
    205     }
    206 
    207 
     187        }
     188      }
     189    }
    208190    #endregion
    209191
    210192    private string GenerateInterpreterSource(AttributedGrammar grammar) {
    211193      var sb = new SourceBuilder();
     194      GenerateInterpreterStart(grammar, sb);
    212195
    213196      // generate methods for all nonterminals and terminals using the grammar instance
    … …  
    221204    }
    222205
     206    private void GenerateInterpreterStart(AttributedGrammar grammar, SourceBuilder sb) {
     207      var s = grammar.StartSymbol;
     208      // create the method which can be called from the fitness function
     209      if (!s.Attributes.Any())
     210        sb.AppendFormat("private void {0}() {{", s.Name).BeginBlock();
     211      else
     212        sb.AppendFormat("private void {0}({1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
     213
     214      // get formal parameters of start symbol
     215      var attr = s.Attributes;
     216
     217      // actual parameter are the same as formalparameter only without type identifier
     218      string actualParameter;
     219      if (attr.Any())
     220        actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
     221      else
     222        actualParameter = string.Empty;
     223      sb.AppendLine("_state.Reset();");
     224      sb.AppendFormat("{0}(_state, {1});", s.Name, actualParameter).AppendLine();
     225      sb.AppendLine("}").EndBlock();
     226    }
     227
    223228    private void GenerateInterpreterMethod(AttributedGrammar g, ISymbol s, SourceBuilder sb) {
    224       // if this is the start symbol we additionally have to create the method which can be called from the fitness function
    225       if (g.StartSymbol.Equals(s)) {
    226         if (!s.Attributes.Any())
    227           sb.AppendFormat("private void {0}() {{", s.Name).BeginBlock();
    228         else
    229           sb.AppendFormat("private void {0}({1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
    230 
    231         // get formal parameters of start symbol
    232         var attr = g.StartSymbol.Attributes;
    233 
    234         // actual parameter are the same as formalparameter only without type identifier
    235         string actualParameter;
    236         if (attr.Any())
    237           actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
    238         else
    239           actualParameter = string.Empty;
    240         sb.AppendLine("_state.Reset();");
    241         sb.AppendFormat("{0}(_state, {1});", g.StartSymbol.Name, actualParameter).AppendLine();
    242         sb.AppendLine("}").EndBlock();
    243       }
    244 
    245229      if (!s.Attributes.Any())
    246230        sb.AppendFormat("private void {0}(ISolverState _state) {{", s.Name).BeginBlock();
    … …  
    272256        sb.AppendFormat("case {0}: {{ ", i).BeginBlock();
    273257
    274         // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far!
     258        // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols)!
    275259        // a way to handle this is through grammar transformation (the examplary grammars all have the correct from)
    276260        Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1);
    … …  
    295279    }
    296280
    297     private string GenerateTerminalInterpreterMethod(ISymbol s, SourceBuilder sb) {
     281    private void GenerateTerminalInterpreterMethod(ISymbol s, SourceBuilder sb) {
    298282      // if the terminal symbol has attributes then we must samples values for these attributes
    299283      if (!s.Attributes.Any())
    … …  
    310294      }
    311295      sb.Append("}").EndBlock();
    312       return sb.ToString();
    313296    }
    314297  }

  • branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs

    r10100 r10335  
    33using System.Diagnostics;
    44using System.Linq;
     5using System.Text;
    56using HeuristicLab.Grammars;
    67
    … …  
    1314    private static double baseTerminalProbability = 0.05; // 5% of all samples are only a terminal node
    1415    private static double terminalProbabilityInc = 0.05; // for each level the probability to sample a terminal grows by 5%
     16
     17    private static Dictionary<int, int[]> transition = new Dictionary<int, int[]>() {
     18?TRANSITIONTABLE?
     19    };
     20    private static Dictionary<int, int> subtreeCount = new Dictionary<int, int>() {
     21       { -1, 0 }, // terminals
     22?SUBTREECOUNTTABLE?
     23    };
     24    private static string[] symb = new string[] { ?SYMBOLNAMES? };
     25
    1526   
    1627    public sealed class SolverState : ISolverState {
    … …  
    2435        }
    2536      }
     37
     38      ?TERMINALNODEDEFINITIONS?
     39
    2640      public int curDepth;
    2741      public int steps;
    2842      public int depth;
    2943      private readonly Stack<Tree> nodes;
    30       private readonly IGpdlProblem problem;
    31 
    32       private static Dictionary<int, int[]> transition = new Dictionary<int, int[]>() {
    33 ?TRANSITIONTABLE?
    34       };
    35       private static Dictionary<int, int> subtreeCount = new Dictionary<int, int>() {
    36          { -1, 0 }, // terminals
    37 ?SUBTREECOUNTTABLE?
    38       };
    39       private static string[] symb = new string[] { ?SYMBOLNAMES? };
    40 
    41       public SolverState(IGpdlProblem problem, int seed) {
     44      private readonly ?IDENT?Problem problem;
     45
     46      public SolverState(?IDENT?Problem problem, int seed) {
    4247        this.problem = problem;
    4348        this.nodes = new Stack<Tree>();
    … …  
    5964        depth = Math.Max(depth, curDepth);
    6065        var t = new Tree(state, altIdx);
     66
    6167        // t.symbol = symb.Length > state ? symb[state] : ""TERM"";
    6268        // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case)
    … …  
    173179        sumF += f;
    174180        if (IsBetter(f, bestF)) {
    175           // evaluate again with tracing to console
    176           // problem.Evaluate(new SolverState(_state.seed, true));
    177181          bestF = f;
    178182          Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, _state.steps, _state.depth);
    … …  
    196200}";
    197201
    198     public void Generate(IGrammar grammar, bool maximization, IEnumerable<SymbolNode> terminalSymbols, SourceBuilder problemSourceCode) {
     202    public void Generate(IGrammar grammar, IEnumerable<TerminalNode> terminals, bool maximization, SourceBuilder problemSourceCode) {
    199203      var solverSourceCode = new SourceBuilder();
    200204      solverSourceCode.Append(solverTemplate)
     205        // .Replace("?TERMINALFIELDS?", GenerateTerminalFields(grammar))
     206        .Replace("?TERMINALNODEDEFINITIONS?", GenerateTerminalNodeDefinitions(terminals))
     207        // .Replace("?CONSTRUCTORCODE?", GenerateConstructorCode(grammar))
    201208        .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
    202209        .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", "))
    … …  
    204211        .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))
    205212        .Replace("?SAMPLEALTERNATIVECODE?", GenerateSampleAlternativeSource(grammar))
     213//        .Replace("?SAMPLETERMINALCODE?", GenerateSampleTerminalSource(grammar))
    206214      ;
    207215
    … …  
    209217    }
    210218
     219    private string GenerateTerminalNodeDefinitions(IEnumerable<TerminalNode> terminals) {
     220      var sb = new SourceBuilder();
     221
     222      foreach (var terminal in terminals) {
     223        GenerateTerminalNodeDefinitions(terminal, sb);
     224      }
     225      return sb.ToString();
     226    }
     227
     228    private void GenerateTerminalNodeDefinitions(TerminalNode terminal, SourceBuilder sb) {
     229      sb.AppendFormat("private class {0}Tree {{", terminal.Ident).BeginBlock();
     230      foreach (var att in terminal.FieldDefinitions) {
     231        sb.AppendFormat("{0} {1};", att.Type, att.Identifier).AppendLine();
     232      }
     233      sb.AppendFormat(" static {0}Tree Create(Random random, ?IDENT?Problem problem) {{", terminal.Ident).BeginBlock();
     234      sb.AppendFormat("var t = new {0}Tree();", terminal.Ident);
     235      foreach (var constr in terminal.Constraints) {
     236        if (constr.Type == ConstraintNodeType.Set) {
     237          sb.AppendLine("{").BeginBlock();
     238          sb.AppendFormat(" var elements = problem.GetAllowed{0}_{1}().ToArray();", terminal.Ident, constr.Ident);
     239          sb.AppendFormat("t.{0} = elements[random.Next(elements.Length)]; ", constr.Ident).AppendLine();
     240          sb.AppendLine("}").EndBlock();
     241        } else {
     242          sb.AppendLine("{").BeginBlock();
     243          sb.AppendFormat(" var max = problem.GetMax{0}_{1}();", terminal.Ident, constr.Ident);
     244          sb.AppendFormat(" var min = problem.GetMin{0}_{1}();", terminal.Ident, constr.Ident);
     245          sb.AppendFormat("t.{0} = random.NextDouble() * (max - min) + min ", constr.Ident).AppendLine();
     246          sb.AppendLine("}").EndBlock();
     247        }
     248      }
     249      sb.AppendLine("return t;");
     250      sb.AppendLine("}").EndBlock();
     251      sb.AppendLine("}").EndBlock();
     252    }
     253
     254    //private string GenerateSampleTerminalSource(IGrammar grammar) {
     255    //  StringBuilder sb = new StringBuilder();
     256    //  foreach (var t in grammar.TerminalSymbols) {
     257    //    sb.AppendFormat("public void {0}(ISolverState _state, {1}) {{", t.Name, t.GetAttributeString()).AppendLine();
     258    //    foreach (var att in t.Attributes) {
     259    //      // need constraints
     260    //      sb.AppendFormat("{0}", att.Name);
     261    //    }
     262    //    sb.AppendLine("}");
     263    //  }
     264    //  return sb.ToString();
     265    //}
    211266
    212267
    … …  
    287342      var sb = new SourceBuilder();
    288343      int stateCount = 0;
    289       var attributes = new List<Tuple<string, string>>();
    290344      foreach (var s in grammar.Symbols) {
    291345        sb.AppendFormat("case {0}: ", stateCount++);
    292346        if (grammar.IsTerminal(s)) {
    293           GenerateReturnStatement(s.Attributes.Count(), sb);
    294           attributes.AddRange(s.Attributes.Select(att => Tuple.Create(s.Name, att.Name)));
     347          // ignore
    295348        } else {
    296349          var terminalAltIndexes = grammar.GetAlternatives(s)
    … …  
    315368        }
    316369      }
    317       for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
    318         var terminalName = attributes[attIdx].Item1;
    319         var attributeName = attributes[attIdx].Item2;
    320         sb.AppendFormat("case {0}: return random.Next(problem.GetCardinality(\"{1}\", \"{2}\"));", attIdx + stateCount, terminalName, attributeName).AppendLine();
    321       }
    322370      return sb.ToString();
    323371    }

  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/HeuristicLab.Grammars-3.3.csproj

    r10067 r10335  
    77    <SchemaVersion>2.0</SchemaVersion>
    88    <ProjectGuid>{A5452B63-B33B-4F9F-9E81-98B75EDB5612}</ProjectGuid>
    9     <OutputType>Exe</OutputType>
     9    <OutputType>Library</OutputType>
    1010    <AppDesignerFolder>Properties</AppDesignerFolder>
    1111    <RootNamespace>HeuristicLab.Grammars</RootNamespace>
    … …  
    107107    <Compile Include="SemanticSymbol.cs" />
    108108    <Compile Include="Sequence.cs" />
    109     <Compile Include="Test.cs" />
    110109    <Compile Include="Symbol.cs" />
    111     <Compile Include="Language.cs" />
    112110    <Compile Include="Grammar.cs" />
    113111    <Compile Include="Interfaces\IAttribute.cs" />
Note: See TracChangeset for help on using the changeset viewer.