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