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