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 |
|
---|
23 | public static void Main(string[] args) {
|
---|
24 | var solver = new ?IDENT?Solver();
|
---|
25 | solver.Start();
|
---|
26 | }
|
---|
27 |
|
---|
28 | public ?IDENT?Solver() {
|
---|
29 | Initialize();
|
---|
30 | }
|
---|
31 |
|
---|
32 | private void Initialize() {
|
---|
33 | ?INITCODE?
|
---|
34 | }
|
---|
35 |
|
---|
36 | private bool IsBetter(double a, double b) {
|
---|
37 | return ?MAXIMIZATION? ? a > b : a < b;
|
---|
38 | }
|
---|
39 |
|
---|
40 |
|
---|
41 | private Random seedRandom;
|
---|
42 | private int currentSeed;
|
---|
43 | private void Start() {
|
---|
44 | seedRandom = new Random();
|
---|
45 | var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
|
---|
46 | int n = 0;
|
---|
47 | var sw = new System.Diagnostics.Stopwatch();
|
---|
48 | sw.Start();
|
---|
49 | while (true) {
|
---|
50 |
|
---|
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();
|
---|
54 | var f = Calculate();
|
---|
55 |
|
---|
56 | n++;
|
---|
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 | }
|
---|
64 | }
|
---|
65 | }
|
---|
66 |
|
---|
67 | public double Calculate() {
|
---|
68 | ?FITNESSFUNCTION?
|
---|
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 |
|
---|
92 | // write the source file to disk
|
---|
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) {
|
---|
99 | var grammar = CreateGrammarFromAst(ast);
|
---|
100 | var problemClassCode =
|
---|
101 | solverTemplate
|
---|
102 | .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant())
|
---|
103 | .Replace("?IDENT?", ast.Name)
|
---|
104 | .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
|
---|
105 | .Replace("?INTERPRETERSOURCE?", GenerateInterpreterSource(grammar))
|
---|
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 |
|
---|
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 |
|
---|
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) {
|
---|
180 | sb.AppendFormat("public IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3} }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
|
---|
181 | }
|
---|
182 | }
|
---|
183 | return sb.ToString();
|
---|
184 | }
|
---|
185 |
|
---|
186 | private string GenerateInterpreterSource(AttributedGrammar grammar) {
|
---|
187 | var sb = new StringBuilder();
|
---|
188 |
|
---|
189 | // generate methods for all nonterminals and terminals using the grammar instance
|
---|
190 | foreach (var s in grammar.NonTerminalSymbols) {
|
---|
191 | sb.AppendLine(GenerateInterpreterMethod(grammar, s));
|
---|
192 | }
|
---|
193 | foreach (var s in grammar.TerminalSymbols) {
|
---|
194 | sb.AppendLine(GenerateTerminalInterpreterMethod(s));
|
---|
195 | }
|
---|
196 | return sb.ToString();
|
---|
197 | }
|
---|
198 |
|
---|
199 | private string GenerateTerminalInterpreterMethod(ISymbol s) {
|
---|
200 | var sb = new StringBuilder();
|
---|
201 | // if the terminal symbol has attributes then we must create values for these attributes
|
---|
202 | if (!s.Attributes.Any())
|
---|
203 | sb.AppendFormat("private void {0}(Random random) {{", s.Name);
|
---|
204 | else
|
---|
205 | sb.AppendFormat("private void {0}(Random random, {1}) {{", s.Name, s.GetAttributeString());
|
---|
206 |
|
---|
207 | // each field must match a formal parameter, assign a value for each parameter
|
---|
208 | foreach (var element in s.Attributes) {
|
---|
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);
|
---|
211 | }
|
---|
212 | sb.AppendLine("}");
|
---|
213 | return sb.ToString();
|
---|
214 | }
|
---|
215 |
|
---|
216 | private string GenerateInterpreterMethod(AttributedGrammar g, ISymbol s) {
|
---|
217 | var sb = new StringBuilder();
|
---|
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 |
|
---|
240 | if (!s.Attributes.Any())
|
---|
241 | sb.AppendFormat("private void {0}(Random random) {{", s.Name);
|
---|
242 | else
|
---|
243 | sb.AppendFormat("private void {0}(Random random, {1}) {{", s.Name, s.GetAttributeString());
|
---|
244 |
|
---|
245 | // generate local definitions
|
---|
246 | sb.AppendLine(g.GetLocalDefinitions(s));
|
---|
247 |
|
---|
248 |
|
---|
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;
|
---|
254 |
|
---|
255 | if (altsWithSemActions.Length > 1) {
|
---|
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);
|
---|
278 | }
|
---|
279 | } else {
|
---|
280 | foreach (var altSymb in altsWithSemActions.Single()) {
|
---|
281 | sb.AppendLine(GenerateSourceForAction(altSymb));
|
---|
282 | }
|
---|
283 | }
|
---|
284 | sb.AppendLine("}");
|
---|
285 | return sb.ToString();
|
---|
286 | }
|
---|
287 |
|
---|
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 |
|
---|
308 | // helper for generating calls to other symbol methods
|
---|
309 | private string GenerateSourceForAction(ISymbol s) {
|
---|
310 | var action = s as SemanticSymbol;
|
---|
311 | if (action != null) {
|
---|
312 | return action.Code + ";";
|
---|
313 | } else {
|
---|
314 | if (!s.Attributes.Any())
|
---|
315 | return string.Format("{0}(random);", s.Name);
|
---|
316 | else
|
---|
317 | return string.Format("{0}(random, {1});", s.Name, s.GetAttributeString());
|
---|
318 | }
|
---|
319 | }
|
---|
320 | }
|
---|
321 | }
|
---|