1 /**
2 * Authors: k.inaba
3 * License: NYSL 0.9982 http://www.kmonos.net/nysl/
4 *
5 * Evaluator for Polemy programming language.
6 */
7 module polemy.eval;
8 import polemy._common;
9 import polemy.failure;
10 import polemy.ast;
11 import polemy.parse;
12 import polemy.value;
13 import polemy.layer;
14 import polemy.value;
15 import polemy.valueconv;
16
17 /// Objects for maitaining global environment and evaluation of expression on it
18 class Evaluator
19 {
20 public:
21 /// Initialize evaluator with empty context
22 this() { theContext = new Table; }
23
24 /// Evaluate the AST
25 Value evalAST(AST e)
26 {
27 return macroAndEval(e, ValueLayer, theContext, OverwriteCtx)[0];
28 }
29
30 /// Evaluate the string
31 Value evalString(S,T...)(S str, T fn_ln_cn)
32 {
33 return evalAST(parseString(str,fn_ln_cn));
34 }
35
36 /// Evaluate the file
37 Value evalFile(S,T...)(S filename, T ln_cn)
38 {
39 return evalAST(parseFile(filename,ln_cn));
40 }
41
42 /// Get the global context
43 Table globalContext()
44 {
45 return theContext;
46 }
47
48 private:
49 Table theContext;
50
51 enum : bool { CascadeCtx=false, OverwriteCtx=true };
52
53 Value eval( AST e, Layer lay, Table ctx, bool overwriteCtx=CascadeCtx )
54 {
55 // dynamic-overload-resolution-pattern: modify here
56 enum funName = "eval";
57 alias TypeTuple!(e,lay,ctx,overwriteCtx) params;
58
59 // dynamic-overload-resolution-pattern: dispatch
60 alias typeof(__traits(getOverloads, this, funName)) ovTypes;
61 alias staticMap!(firstParam, ovTypes) fstTypes;
62 alias DerivedToFront!(fstTypes) fstTypes_sorted;
63 foreach(i, T; fstTypes_sorted)
64 static if( is(T == typeof(params[0])) ) {} else if( auto _x = cast(T)params[0] )
65 return __traits(getOverloads, this, funName)[i](_x, params[1..$]);
66
67 // dynamic-overload-resolution-pattern: default behavior
68 assert(false, text("eval() for ",typeid(e)," [",e.pos,"] is not defined"));
69 }
70
71 Value eval( Str e, Layer lay, Table ctx, bool overwriteCtx=CascadeCtx )
72 {
73 if( isASTLayer(lay) )
74 return ast2table(e, (AST e){return eval(e,lay,ctx);});
75 if( isUserDefinedLayer(lay) )
76 return lift(new StrValue(e.data), lay, ctx, e.pos);
77 return new StrValue(e.data);
78 }
79
80 Value eval( Int e, Layer lay, Table ctx, bool overwriteCtx=CascadeCtx )
81 {
82 if( isASTLayer(lay) )
83 return ast2table(e, (AST e){return eval(e,lay,ctx);});
84 if( isUserDefinedLayer(lay) )
85 return lift(new IntValue(e.data), lay, ctx, e.pos);
86 return new IntValue(e.data);
87 }
88
89 Value eval( Var e, Layer lay, Table ctx, bool overwriteCtx=CascadeCtx )
90 {
91 if( isASTLayer(lay) )
92 if( isMacroLayer(lay) && ctx.has(e.name,MacroLayer) )
93 return ctx.get(e.name, MacroLayer, e.pos);
94 else
95 return ast2table(e, (AST e){return eval(e,lay,ctx);});
96 if( isUserDefinedLayer(lay) && !ctx.has(e.name, lay) )
97 return lift(ctx.get(e.name, ValueLayer, e.pos), lay, ctx, e.pos);
98 return ctx.get(e.name, lay, e.pos);
99 }
100
101 Value eval( App e, Layer lay, Table ctx, bool overwriteCtx=CascadeCtx )
102 {
103 Value f = eval( e.fun, lay, ctx );
104 if( isASTLayer(lay) ) {
105 auto ff = cast(FunValue)f;
106 if( ff !is null && isMacroLayer(lay) )
107 return invokeFunction(ff, e.args, lay, ctx, e.pos, getNameIfPossible(e.fun));
108 else
109 return ast2table(e, (AST e){return eval(e,lay,ctx);});
110 }
111 return invokeFunction(f, e.args, lay, ctx, e.pos, getNameIfPossible(e.fun));
112 }
113
114 Value eval( Fun e, Layer lay, Table ctx, bool overwriteCtx=CascadeCtx )
115 {
116 if( isASTLayer(lay) )
117 {
118 // need this for correct scoping (outer scope macro variables must be hidden!)
119 Table newCtx = new Table(ctx, Table.Kind.NotPropagateSet);
120 foreach(p; e.params)
121 newCtx.set(p.name, ValueLayer, new UndefinedValue);
122 return ast2table(e, (AST e){return eval(e,lay,newCtx);});
123 }
124 else
125 return createNewFunction(e, ctx);
126 }
127
128 Value eval( Lay e, Layer lay, Table ctx, bool overwriteCtx=CascadeCtx )
129 {
130 if( isNoLayerChangeLayer(lay) )
131 return ast2table(e, (AST e){return eval(e,lay,ctx);});
132 else
133 return eval(e.expr, e.layer, ctx);
134 }
135
136 Value eval( Let e, Layer lay, Table ctx, bool overwriteCtx=CascadeCtx )
137 {
138 Table newCtx = overwriteCtx ? ctx : new Table(ctx, Table.Kind.NotPropagateSet);
139 if( isASTLayer(lay) )
140 return ast2table(e, (AST ee){
141 // need this for correct scoping (outer scope macro variables must be hidden!)
142 if(ee is e.expr)
143 newCtx.set(e.name, ValueLayer, new UndefinedValue);
144 return eval(ee,lay,newCtx);
145 });
146 else
147 {
148 Value ri = eval(e.init, lay, newCtx);
149 newCtx.set(e.name, e.layer.empty ? lay : e.layer, ri);
150 return eval(e.expr, lay, newCtx, OverwriteCtx);
151 }
152 }
153
154 private:
155 // little little bit incremental macro defining version.
156 // enables @macro foo(x)=... in ... foo ..., only at the top level of the
157 // interpreter and functions. better than nothing :P
158 Tuple!(Value,AST) macroAndEval( AST e_, Layer lay, Table ctx, bool overwriteCtx=CascadeCtx )
159 {
160 assert( !isASTLayer(lay) );
161
162 AST decodeAST(Value v, LexPosition pos)
163 {
164 // [TODO] more informative error message
165 return polemy2d!(AST)(v, pos);
166 }
167
168 if(auto e = cast(Let)e_)
169 {
170 AST ai = decodeAST(eval(e.init, RawMacroLayer, ctx), e.init.pos);
171 Value vi = eval(ai, lay, ctx);
172
173 if( !overwriteCtx )
174 ctx = new Table(ctx, Table.Kind.NotPropagateSet);
175 string theLayer = e.layer.empty ? lay : e.layer;
176 ctx.set(e.name, theLayer, vi);
177
178 auto ave = macroAndEval( e.expr, lay, ctx, OverwriteCtx );
179 AST a = new Let(e.pos, e.name, e.layer, ai, ave[1]);
180 return tuple(ave[0], a);
181 }
182 else
183 {
184 AST a = decodeAST(eval(e_, RawMacroLayer, ctx), e_.pos);
185 Value v = eval(a, lay, ctx);
186 return tuple(v, a);
187 }
188 }
189
190 private:
191 string getNameIfPossible(AST e)
192 {
193 if(auto v = cast(Var)e)
194 return v.name;
195 return "";
196 }
197
198 Value invokeFunction(Value _f, AST[] args, Layer lay, Table ctx, LexPosition pos, string callstackmsg)
199 {
200 if(auto f = cast(FunValue)_f)
201 {
202 Table newCtx = new Table(f.definitionContext(), Table.Kind.NotPropagateSet);
203 foreach(i,p; f.params())
204 if( p.layers.empty )
205 newCtx.set(p.name, isMacroLayer(lay)?MacroLayer:lay, eval(args[i], lay, ctx));
206 else
207 foreach(argLay; p.layers)
208 newCtx.set(p.name, argLay, eval(args[i], argLay, ctx));
209 scope _ = new PushCallStack(pos, callstackmsg);
210 return f.invoke(isMacroLayer(lay)?MacroLayer:lay, newCtx, pos);
211 }
212 throw genex!RuntimeException(pos, text("tried to call non-function: ",_f));
213 }
214
215 Value lift(Value v, Layer lay, Table ctx, LexPosition pos)
216 {
217 assert( !isASTLayer(lay), "lift to the @macro layer should never happen" );
218
219 // functions are automatically lifterd
220 if( cast(FunValue) v )
221 return v;
222
223 if( !ctx.has(lay, SystemLayer) )
224 throw genex!RuntimeException(pos, "lift function for "~lay~" is not registered" );
225
226 // similar to invokeFunction, but with only one argument bound to ValueLayer
227 auto _f = ctx.get(lay, SystemLayer, pos);
228 if(auto f = cast(FunValue)_f)
229 {
230 Table newCtx = new Table(f.definitionContext(), Table.Kind.NotPropagateSet);
231 auto ps = f.params();
232 if( ps.length != 1 )
233 throw genex!RuntimeException(pos,
234 text("lift function for", lay, " must take exactly one argument of ", ValueLayer));
235 if( ps[0].layers.length==0 || ps[0].layers.length==1 && ps[0].layers[0]==ValueLayer )
236 {
237 newCtx.set(ps[0].name, ValueLayer, v);
238 scope _ = new PushCallStack(pos, lay);
239 return f.invoke(ValueLayer, newCtx, pos);
240 }
241 else
242 throw genex!RuntimeException(pos,
243 text("lift function for", lay, " must take exactly one argument of ", ValueLayer));
244 }
245 throw genex!RuntimeException(pos,
246 text("non-function ", _f, " is registered as the lift function for ", lay));
247 }
248
249 Value createNewFunction(Fun e, Table ctx)
250 {
251 class UserDefinedFunValue : FunValue
252 {
253 Fun ast;
254 Table defCtx;
255 override const(Parameter[]) params() { return ast.params; }
256 override Table definitionContext() { return defCtx; }
257
258 this(Fun ast, Table defCtx) { this.ast=ast; this.defCtx=defCtx; }
259 override string toString() const
260 { return sprintf!"(function:%x:%x)"(cast(void*)ast, cast(void*)defCtx); }
261 override int opCmp(Object rhs) {
262 if(auto r = cast(UserDefinedFunValue)rhs) {
263 auto a = cast(void*)this.ast;
264 auto b = cast(void*)r.ast;
265 if(a<b) return -1;
266 if(a>b) return +1; // [TODO] avoid using pointer value...
267 return this.defCtx.opCmp(r.defCtx);
268 }
269 if(auto r = cast(Value)rhs) return typeid(this).opCmp(typeid(r));
270 throw genex!RuntimeException("comparison with value and something other");
271 }
272 mixin SimpleToHash;
273
274 AST afterMacroAST;
275 override Value invoke(Layer lay, Table ctx, LexPosition pos)
276 {
277 if( isASTLayer(lay) )
278 return eval(ast.funbody, lay, ctx);
279 if( afterMacroAST is null )
280 {
281 auto va = macroAndEval(e.funbody, lay, ctx);
282 afterMacroAST = va[1];
283 return va[0];
284 }
285 else
286 return eval(afterMacroAST, lay, ctx);
287 }
288 }
289 return new UserDefinedFunValue(e,ctx);
290 }
291
292 public:
293 /// Add primitive function to the global context
294 void addPrimitive(R,T...)(string name, Layer defLay, R delegate (T) dg)
295 {
296 class NativeFunValue : FunValue
297 {
298 override const(Parameter[]) params() { return params_data; }
299 override Table definitionContext() { return theContext; }
300
301 override string toString() { return sprintf!"(native:%x)"(dg.funcptr); }
302 override int opCmp(Object rhs) {
303 if(auto r = cast(NativeFunValue)rhs) return typeid(typeof(dg)).compare(&dg,&r.dg);
304 if(auto r = cast(Value)rhs) return typeid(this).opCmp(typeid(r));
305 throw genex!RuntimeException("comparison with value and something other");
306 }
307 mixin SimpleToHash;
308
309 R delegate(T) dg;
310 Parameter[] params_data;
311
312 this(R delegate(T) dg)
313 {
314 this.dg = dg;
315 foreach(i, Ti; T)
316 params_data ~= new Parameter(text(i), []);
317 }
318
319 override Value invoke(Layer lay, Table ctx, LexPosition pos)
320 {
321 if( lay != defLay )
322 throw genex!RuntimeException(pos,
323 text("only ", defLay, " layer can call native function: ", name));
324 T typed_args;
325 foreach(i, Ti; T) {
326 typed_args[i] = cast(Ti) ctx.get(text(i), ValueLayer, pos);
327 if( typed_args[i] is null )
328 throw genex!RuntimeException(pos,
329 sprintf!"type mismatch on the argument %d of native function: %s"(i+1,name));
330 }
331 try {
332 return dg(typed_args);
333 } catch( RuntimeException e ) {
334 throw e.pos is null ? new RuntimeException(pos, e.msg, e.file, e.line) : e;
335 }
336 }
337 }
338 theContext.set(name, defLay, new NativeFunValue(dg));
339 }
340 }
341
342 version(unittest) import polemy.runtime;
343 unittest
344 {
345 auto e = new Evaluator;
346 enrollRuntimeLibrary(e);
347 auto r = assert_nothrow( e.evalString(`var x = 21; x + x*x;`) );
348 assert_eq( r, new IntValue(BigInt(21+21*21)) );
349 assert_eq( e.globalContext.get("x",ValueLayer), new IntValue(BigInt(21)) );
350 assert_nothrow( e.globalContext.get("x",ValueLayer) );
351 assert_throw!RuntimeException( e.globalContext.get("y",ValueLayer) );
352 }
353 unittest
354 {
355 auto e = new Evaluator;
356 enrollRuntimeLibrary(e);
357 auto r = assert_nothrow( e.evalString(`var x = 21; var x = x + x*x;`) );
358 assert_eq( r, new IntValue(BigInt(21+21*21)) );
359 assert_eq( e.globalContext.get("x",ValueLayer), new IntValue(21+21*21) );
360 assert_nothrow( e.globalContext.get("x",ValueLayer) );
361 assert_throw!RuntimeException( e.globalContext.get("y",ValueLayer) );
362 }
363 unittest
364 {
365 auto e = new Evaluator;
366 enrollRuntimeLibrary(e);
367 assert_eq( e.evalString(`let x=1; let y=(let x=2); x`), new IntValue(1) );
368 assert_eq( e.evalString(`let x=1; let y=(let x=2;fun(){x}); y()`), new IntValue(2) );
369 }
370
371 unittest
372 {
373 auto e = new Evaluator;
374 enrollRuntimeLibrary(e);
375 assert_eq( e.evalString(`@a x=1; @b x=2; @a(x)`), new IntValue(BigInt(1)) );
376 assert_eq( e.evalString(`@a x=1; @b x=2; @b(x)`), new IntValue(BigInt(2)) );
377 assert_eq( e.evalString(`let x=1; let _ = (@a x=2;2); x`), new IntValue(BigInt(1)) );
378 e = new Evaluator;
379 assert_throw!Throwable( e.evalString(`let x=1; let _ = (@a x=2;2); @a(x)`) );
380 }
381
382 unittest
383 {
384 auto e = new Evaluator;
385 enrollRuntimeLibrary(e);
386 assert_eq( e.evalString(`
387 @@s(x){x};
388 @s "+" = fun(x, y) {@value(
389 @s(x) - @s(y)
390 )};
391 @s(1 + 2)
392 `), new IntValue(BigInt(-1)) );
393 }
394
395 unittest
396 {
397 auto e = new Evaluator;
398 enrollRuntimeLibrary(e);
399 assert_eq( e.evalString(`
400 @@3(x){x};
401 def incr(x) { x+1 };
402 @ 3 incr(x) {@value( if @ 3(x)+1< 3 then @3(x)+1 else 0 )};
403 def fb(n @value @3) { @3(n) };
404 fb(incr(incr(incr(0))))
405 `), new IntValue(BigInt(0)) );
406 }
407
408 unittest
409 {
410 auto e = new Evaluator;
411 enrollRuntimeLibrary(e);
412 assert_nothrow( e.evalString(`
413 @macro twice(x) { x; x };
414 def main() { twice(1) };
415 main()
416 `) );
417 }
418 unittest
419 {
420 auto e = new Evaluator;
421 enrollRuntimeLibrary(e);
422 assert_nothrow( e.evalString(`case 1`) );
423 assert_nothrow( e.evalString(`case 1 when 1: 2`) );
424 }
425
426 /*
427 unittest
428 {
429 assert_eq( evalString(`var fac = fun(x){
430 if(x)
431 { x*fac(x-1); }
432 else
433 { 1; };
434 };
435 fac(10);`).val, new IntValue(BigInt(10*9*8*5040)));
436 assert_eq( evalString(`var fib = fun(x){
437 if(x<2)
438 { 1; }
439 else
440 { fib(x-1) + fib(x-2); };
441 };
442 fib(5);`).val, new IntValue(BigInt(8)));
443 }
444 unittest
445 {
446 assert_eq( evalString(`@@t = fun(x){x+1}; @t(123)`).val, new IntValue(BigInt(124)) );
447 // there was a bug that declaration in the first line of function definition
448 // cannot be recursive
449 assert_nothrow( evalString(`def foo() {
450 def bar(y) { if(y<1) {0} else {bar(0)} };
451 bar(1)
452 }; foo()`) );
453 }
454 */