[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 {
|
---|
[10080] | 11 | public class RandomSearchCodeGen {
|
---|
[10062] | 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 |
|
---|
[10067] | 40 |
|
---|
[10080] | 41 | private Random seedRandom;
|
---|
| 42 | private int currentSeed;
|
---|
[10062] | 43 | private void Start() {
|
---|
[10080] | 44 | seedRandom = new Random();
|
---|
[10062] | 45 | var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
|
---|
[10067] | 46 | int n = 0;
|
---|
[10074] | 47 | var sw = new System.Diagnostics.Stopwatch();
|
---|
| 48 | sw.Start();
|
---|
[10080] | 49 | while (true) {
|
---|
[10074] | 50 |
|
---|
[10080] | 51 | // must make sure that calling the start-symbol multiple times in the fitness function always leads to the same path through the grammar
|
---|
| 52 | // so we use a PRNG for generating seeds for a separate PRNG that is reset each time the start symbol is called
|
---|
| 53 | currentSeed = seedRandom.Next();
|
---|
[10062] | 54 | var f = Calculate();
|
---|
[10074] | 55 |
|
---|
[10067] | 56 | n++;
|
---|
[10074] | 57 | if (IsBetter(f, bestF)) bestF = f;
|
---|
| 58 | if (n % 100 == 0) {
|
---|
| 59 | sw.Stop();
|
---|
| 60 | Console.WriteLine(""{0}\t{1}\t{2}\t({3:0.00} sols/ms)"", n, bestF, f, 100.0 / sw.ElapsedMilliseconds);
|
---|
| 61 | sw.Reset();
|
---|
| 62 | sw.Start();
|
---|
| 63 | }
|
---|
[10062] | 64 | }
|
---|
| 65 | }
|
---|
| 66 |
|
---|
| 67 | public double Calculate() {
|
---|
[10067] | 68 | ?FITNESSFUNCTION?
|
---|
[10062] | 69 | }
|
---|
| 70 |
|
---|
| 71 | ?ADDITIONALCODE?
|
---|
| 72 |
|
---|
| 73 | ?INTERPRETERSOURCE?
|
---|
| 74 |
|
---|
| 75 | ?CONSTRAINTSSOURCE?
|
---|
| 76 | }
|
---|
| 77 | }";
|
---|
| 78 |
|
---|
| 79 |
|
---|
| 80 | /// <summary>
|
---|
| 81 | /// Generates the source code for a brute force searcher that can be compiled with a C# compiler
|
---|
| 82 | /// </summary>
|
---|
| 83 | /// <param name="ast">An abstract syntax tree for a GPDL file</param>
|
---|
| 84 | public void Generate(GPDefNode ast) {
|
---|
| 85 | var problemSourceCode = new StringBuilder();
|
---|
| 86 | problemSourceCode.AppendLine(usings);
|
---|
| 87 |
|
---|
| 88 | GenerateProblem(ast, problemSourceCode);
|
---|
| 89 |
|
---|
| 90 | problemSourceCode.Replace("?PROBLEMNAME?", ast.Name);
|
---|
| 91 |
|
---|
[10067] | 92 | // write the source file to disk
|
---|
[10062] | 93 | using (var stream = new StreamWriter(ast.Name + ".cs")) {
|
---|
| 94 | stream.WriteLine(problemSourceCode.ToString());
|
---|
| 95 | }
|
---|
| 96 | }
|
---|
| 97 |
|
---|
| 98 | private void GenerateProblem(GPDefNode ast, StringBuilder problemSourceCode) {
|
---|
[10067] | 99 | var grammar = CreateGrammarFromAst(ast);
|
---|
[10062] | 100 | var problemClassCode =
|
---|
| 101 | solverTemplate
|
---|
[10067] | 102 | .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant())
|
---|
[10062] | 103 | .Replace("?IDENT?", ast.Name)
|
---|
| 104 | .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
|
---|
[10067] | 105 | .Replace("?INTERPRETERSOURCE?", GenerateInterpreterSource(grammar))
|
---|
[10062] | 106 | .Replace("?INITCODE?", ast.InitCodeNode.SrcCode)
|
---|
| 107 | .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
|
---|
| 108 | .Replace("?CONSTRAINTSSOURCE?", GenerateConstraintMethods(ast.Terminals))
|
---|
| 109 | ;
|
---|
| 110 |
|
---|
| 111 | problemSourceCode.AppendLine(problemClassCode).AppendLine();
|
---|
| 112 | }
|
---|
| 113 |
|
---|
[10067] | 114 | private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
|
---|
| 115 | string startSymbolName = ast.Rules.First().NtSymbol;
|
---|
| 116 | var startSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == startSymbolName);
|
---|
| 117 | // create startSymbol
|
---|
| 118 | var g = new AttributedGrammar(new Symbol(startSymbolName, ParseSymbolAttributes(startSymbolNode.FormalParameters)));
|
---|
| 119 | foreach (var rule in ast.Rules) {
|
---|
| 120 | // create nt-symbol
|
---|
| 121 | var ntSymbolName = rule.NtSymbol;
|
---|
| 122 | var ntSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == ntSymbolName);
|
---|
| 123 | var attributes = ParseSymbolAttributes(ntSymbolNode.FormalParameters);
|
---|
| 124 | var ntSymbol = new Symbol(ntSymbolName, attributes);
|
---|
| 125 | foreach (var alt in GetAlternatives(rule.Alternatives)) {
|
---|
| 126 | g.AddProductionRule(ntSymbol, alt);
|
---|
| 127 | }
|
---|
| 128 | // local initialization code
|
---|
| 129 | if (!string.IsNullOrEmpty(rule.LocalCode)) g.AddLocalDefinitions(ntSymbol, rule.LocalCode);
|
---|
| 130 | }
|
---|
| 131 | return g;
|
---|
| 132 | }
|
---|
| 133 |
|
---|
| 134 | private IEnumerable<IAttribute> ParseSymbolAttributes(string formalParameters) {
|
---|
| 135 | return (from fieldDef in Util.ExtractParameters(formalParameters)
|
---|
| 136 | select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
|
---|
| 137 | ToList();
|
---|
| 138 | }
|
---|
| 139 |
|
---|
| 140 | private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode) {
|
---|
| 141 | foreach (var alt in altNode.Alternatives) {
|
---|
| 142 | yield return GetSequence(alt.Sequence);
|
---|
| 143 | }
|
---|
| 144 | }
|
---|
| 145 |
|
---|
| 146 | private Sequence GetSequence(IEnumerable<RuleExprNode> sequence) {
|
---|
| 147 | Debug.Assert(sequence.All(s => s is CallSymbolNode || s is RuleActionNode));
|
---|
| 148 | var l = new List<ISymbol>();
|
---|
| 149 | foreach (var node in sequence) {
|
---|
| 150 | var callSymbolNode = node as CallSymbolNode;
|
---|
| 151 | var actionNode = node as RuleActionNode;
|
---|
| 152 | if (callSymbolNode != null) {
|
---|
| 153 | l.Add(new Symbol(callSymbolNode.Ident, ParseSymbolAttributes(callSymbolNode.ActualParameter)));
|
---|
| 154 | } else if (actionNode != null) {
|
---|
| 155 | l.Add(new SemanticSymbol("SEM", actionNode.SrcCode));
|
---|
| 156 | }
|
---|
| 157 | }
|
---|
| 158 | return new Sequence(l);
|
---|
| 159 | }
|
---|
| 160 |
|
---|
[10062] | 161 | // produces helper methods for the attributes of all terminal nodes
|
---|
| 162 | private string GenerateConstraintMethods(List<SymbolNode> symbols) {
|
---|
| 163 | var sb = new StringBuilder();
|
---|
| 164 | var terminals = symbols.OfType<TerminalNode>();
|
---|
| 165 | foreach (var t in terminals) {
|
---|
| 166 | sb.AppendLine(GenerateConstraintMethods(t));
|
---|
| 167 | }
|
---|
| 168 | return sb.ToString();
|
---|
| 169 | }
|
---|
| 170 |
|
---|
| 171 | // generates helper methods for the attributes of a given terminal node
|
---|
| 172 | private string GenerateConstraintMethods(TerminalNode t) {
|
---|
| 173 | var sb = new StringBuilder();
|
---|
| 174 | foreach (var c in t.Constraints) {
|
---|
| 175 | var fieldType = t.FieldDefinitions.First(d => d.Identifier == c.Ident).Type;
|
---|
| 176 | if (c.Type == ConstraintNodeType.Range) {
|
---|
| 177 | sb.AppendFormat("public {0} GetMax{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMaxExpression).AppendLine();
|
---|
| 178 | sb.AppendFormat("public {0} GetMin{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMinExpression).AppendLine();
|
---|
| 179 | } else if (c.Type == ConstraintNodeType.Set) {
|
---|
[10080] | 180 | sb.AppendFormat("public IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3} }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
|
---|
[10062] | 181 | }
|
---|
| 182 | }
|
---|
| 183 | return sb.ToString();
|
---|
| 184 | }
|
---|
| 185 |
|
---|
[10067] | 186 | private string GenerateInterpreterSource(AttributedGrammar grammar) {
|
---|
| 187 | var sb = new StringBuilder();
|
---|
| 188 |
|
---|
[10062] | 189 | // generate methods for all nonterminals and terminals using the grammar instance
|
---|
[10067] | 190 | foreach (var s in grammar.NonTerminalSymbols) {
|
---|
| 191 | sb.AppendLine(GenerateInterpreterMethod(grammar, s));
|
---|
[10062] | 192 | }
|
---|
[10067] | 193 | foreach (var s in grammar.TerminalSymbols) {
|
---|
| 194 | sb.AppendLine(GenerateTerminalInterpreterMethod(s));
|
---|
[10062] | 195 | }
|
---|
| 196 | return sb.ToString();
|
---|
| 197 | }
|
---|
| 198 |
|
---|
[10067] | 199 | private string GenerateTerminalInterpreterMethod(ISymbol s) {
|
---|
[10062] | 200 | var sb = new StringBuilder();
|
---|
| 201 | // if the terminal symbol has attributes then we must create values for these attributes
|
---|
[10067] | 202 | if (!s.Attributes.Any())
|
---|
[10080] | 203 | sb.AppendFormat("private void {0}(Random random) {{", s.Name);
|
---|
[10062] | 204 | else
|
---|
[10080] | 205 | sb.AppendFormat("private void {0}(Random random, {1}) {{", s.Name, s.GetAttributeString());
|
---|
[10062] | 206 |
|
---|
| 207 | // each field must match a formal parameter, assign a value for each parameter
|
---|
[10067] | 208 | foreach (var element in s.Attributes) {
|
---|
[10080] | 209 | // only works for "IN SET"-Constraints
|
---|
| 210 | sb.AppendFormat("{{ var tmp = GetAllowed{1}_{0}().ToArray(); {0} = tmp[random.Next(tmp.Length)]; }} ", element.Name, s.Name);
|
---|
[10062] | 211 | }
|
---|
| 212 | sb.AppendLine("}");
|
---|
| 213 | return sb.ToString();
|
---|
| 214 | }
|
---|
| 215 |
|
---|
[10067] | 216 | private string GenerateInterpreterMethod(AttributedGrammar g, ISymbol s) {
|
---|
[10062] | 217 | var sb = new StringBuilder();
|
---|
[10080] | 218 | // if this is the start symbol we additionally have to create the method which can be called from the fitness function
|
---|
| 219 |
|
---|
| 220 | if (g.StartSymbol.Equals(s)) {
|
---|
| 221 | if (!s.Attributes.Any())
|
---|
| 222 | sb.AppendFormat("private void {0}() {{", s.Name);
|
---|
| 223 | else
|
---|
| 224 | sb.AppendFormat("private void {0}({1}) {{", s.Name, s.GetAttributeString());
|
---|
| 225 |
|
---|
| 226 | // get formal parameters of start symbol
|
---|
| 227 | var attr = g.StartSymbol.Attributes;
|
---|
| 228 |
|
---|
| 229 | // actual parameter are the same as formalparameter only without type identifier
|
---|
| 230 | string actualParameter;
|
---|
| 231 | if (attr.Any())
|
---|
| 232 | actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
|
---|
| 233 | else
|
---|
| 234 | actualParameter = string.Empty;
|
---|
| 235 |
|
---|
| 236 | sb.AppendFormat("{0}(new Random(currentSeed), {1});", g.StartSymbol.Name, actualParameter).AppendLine();
|
---|
| 237 | sb.AppendLine("}");
|
---|
| 238 | }
|
---|
| 239 |
|
---|
[10067] | 240 | if (!s.Attributes.Any())
|
---|
[10080] | 241 | sb.AppendFormat("private void {0}(Random random) {{", s.Name);
|
---|
[10062] | 242 | else
|
---|
[10080] | 243 | sb.AppendFormat("private void {0}(Random random, {1}) {{", s.Name, s.GetAttributeString());
|
---|
[10074] | 244 |
|
---|
[10062] | 245 | // generate local definitions
|
---|
[10067] | 246 | sb.AppendLine(g.GetLocalDefinitions(s));
|
---|
[10062] | 247 |
|
---|
| 248 |
|
---|
[10080] | 249 | var altsWithSemActions = g.GetAlternativesWithSemanticActions(s).ToArray();
|
---|
| 250 | var terminalAlts = altsWithSemActions.Where(alt => alt.Count(g.IsNonTerminal) == 0);
|
---|
| 251 | var nonTerminalAlts = altsWithSemActions.Where(alt => alt.Count(g.IsNonTerminal) > 0);
|
---|
| 252 | bool hasTerminalAlts = terminalAlts.Count() > 0;
|
---|
| 253 | bool hasNonTerminalAlts = nonTerminalAlts.Count() > 0;
|
---|
[10074] | 254 |
|
---|
| 255 | if (altsWithSemActions.Length > 1) {
|
---|
[10080] | 256 | // here we need to bias the selection of alternatives (non-terminal vs terminal alternatives) to make sure that
|
---|
| 257 | // terminals are selected with a certain probability to make sure that:
|
---|
| 258 | // 1) we don't create the same small trees all the time (terminals have high probability to be selected)
|
---|
| 259 | // 2) we don't create very big trees by recursing to deep (leads to stack-overflow) (terminals have a low probability to be selected)
|
---|
| 260 | // so we first decide if we want to generate a terminal or non-terminal (50%, 50%) and then choose a symbol in the class randomly
|
---|
| 261 | // the probability of choosing terminals should depend on the depth of the tree (small likelihood to choose terminals for small depths, large likelihood for large depths)
|
---|
| 262 | if (hasTerminalAlts && hasNonTerminalAlts) {
|
---|
| 263 | sb.AppendLine("if(random.NextDouble() < 0.5) {");
|
---|
| 264 | // terminals
|
---|
| 265 | sb.AppendLine("// terminals ");
|
---|
| 266 | GenerateSwitchStatement(sb, terminalAlts);
|
---|
| 267 | sb.AppendLine("} else {");
|
---|
| 268 | // non-terminals
|
---|
| 269 | sb.AppendLine("// non-terminals ");
|
---|
| 270 | GenerateSwitchStatement(sb, nonTerminalAlts);
|
---|
| 271 | sb.AppendLine("}");
|
---|
| 272 | } else if (hasTerminalAlts) {
|
---|
| 273 | sb.AppendLine("// terminals ");
|
---|
| 274 | GenerateSwitchStatement(sb, terminalAlts);
|
---|
| 275 | } else if (hasNonTerminalAlts) {
|
---|
| 276 | sb.AppendLine("// non-terminals ");
|
---|
| 277 | GenerateSwitchStatement(sb, nonTerminalAlts);
|
---|
[10062] | 278 | }
|
---|
| 279 | } else {
|
---|
[10074] | 280 | foreach (var altSymb in altsWithSemActions.Single()) {
|
---|
| 281 | sb.AppendLine(GenerateSourceForAction(altSymb));
|
---|
[10062] | 282 | }
|
---|
| 283 | }
|
---|
| 284 | sb.AppendLine("}");
|
---|
| 285 | return sb.ToString();
|
---|
| 286 | }
|
---|
| 287 |
|
---|
[10080] | 288 | private void GenerateSwitchStatement(StringBuilder sb, IEnumerable<Sequence> alts) {
|
---|
| 289 | sb.AppendFormat("switch(random.Next({0})) {{", alts.Count());
|
---|
| 290 | // generate a case for each alternative
|
---|
| 291 | int i = 0;
|
---|
| 292 | foreach (var alt in alts) {
|
---|
| 293 | sb.AppendFormat("case {0}: {{ ", i).AppendLine();
|
---|
| 294 |
|
---|
| 295 | // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far!
|
---|
| 296 | // a way to handle this is through grammar transformation (the examplary grammars all have the correct from)
|
---|
| 297 | Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1);
|
---|
| 298 | foreach (var altSymb in alt) {
|
---|
| 299 | sb.AppendLine(GenerateSourceForAction(altSymb));
|
---|
| 300 | }
|
---|
| 301 | i++;
|
---|
| 302 | sb.AppendLine("break;").AppendLine("}");
|
---|
| 303 | }
|
---|
| 304 | sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}");
|
---|
| 305 |
|
---|
| 306 | }
|
---|
| 307 |
|
---|
[10062] | 308 | // helper for generating calls to other symbol methods
|
---|
[10067] | 309 | private string GenerateSourceForAction(ISymbol s) {
|
---|
| 310 | var action = s as SemanticSymbol;
|
---|
[10062] | 311 | if (action != null) {
|
---|
[10067] | 312 | return action.Code + ";";
|
---|
| 313 | } else {
|
---|
| 314 | if (!s.Attributes.Any())
|
---|
[10080] | 315 | return string.Format("{0}(random);", s.Name);
|
---|
[10062] | 316 | else
|
---|
[10080] | 317 | return string.Format("{0}(random, {1});", s.Name, s.GetAttributeString());
|
---|
[10062] | 318 | }
|
---|
| 319 | }
|
---|
| 320 | }
|
---|
| 321 | }
|
---|