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 if(auto c = typeid(void*).compare(cast(void*)ast, cast(void*)r.ast))
264 return c;
265 if(auto c = typeid(void*).compare(cast(void*)defCtx, cast(void*)r.defCtx))
266 return c;
267 return 0;// [TODO] avoid using pointer value...
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 override hash_t toHash() {
273 return (cast(hash_t)cast(void*)ast) + (cast(hash_t)cast(void*)defCtx);
274 }
275
276 AST macroCache;
277 static class MemokeyType
278 {
279 void* a; Layer b; Tuple!(string,Layer,Value)[] c;
280 hash_t toHash() {
281 hash_t h = structuralHash(a) + structuralHash(b);
282 foreach(e; c)
283 h += structuralHash(e[0])+structuralHash(e[1])+structuralHash(e[2]);
284 return h;
285 }
286 mixin SimpleToString;
287 mixin SimpleConstructor;
288 mixin SimpleCompareWithoutToHash;
289 }
290 static Tuple!(Value,int)[MemokeyType] memo;
291
292 override Value invoke(Layer lay, Table ctx, LexPosition pos)
293 {
294 if( isASTLayer(lay) )
295 return eval(ast.funbody, lay, ctx);
296
297 auto nonMemoizedRun = (){
298 if( macroCache is null )
299 {
300 auto va = macroAndEval(e.funbody, lay, ctx);
301 macroCache = va[1];
302 return va[0];
303 }
304 else
305 return eval(macroCache, lay, ctx);
306 };
307
308 if( !isUserDefinedLayer(lay) )
309 return nonMemoizedRun();
310
311 MemokeyType memokey = new MemokeyType(cast(void*)ast, lay, ctx.direct_entries());
312
313 if(auto p = memokey in memo)
314 {
315 (*p)[1] ++;
316 return (*p)[0];
317 }
318 else
319 memo[memokey] = tuple(lift(new UndefinedValue, lay, ctx, pos), 0);
320
321 Value r = nonMemoizedRun();
322
323 int touched = memo[memokey][1];
324 memo[memokey] = tuple(r, 12345678);
325 //if(touched) {DBG("rerun :: ",r);r = nonMemoizedRun();} // twice!!
326 return r;
327 }
328 }
329 return new UserDefinedFunValue(e,ctx);
330 }
331
332 public:
333 /// Add primitive function to the global context
334 void addPrimitive(R,T...)(string name, Layer defLay, R delegate (T) dg)
335 {
336 class NativeFunValue : FunValue
337 {
338 override const(Parameter[]) params() { return params_data; }
339 override Table definitionContext() { return theContext; }
340
341 override string toString() { return sprintf!"(native:%x)"(dg.funcptr); }
342 override int opCmp(Object rhs) {
343 if(auto r = cast(NativeFunValue)rhs) return typeid(typeof(dg)).compare(&dg,&r.dg);
344 if(auto r = cast(Value)rhs) return typeid(this).opCmp(typeid(r));
345 throw genex!RuntimeException("comparison with value and something other");
346 }
347 override hash_t toHash() const {
348 return typeid(dg).getHash(&dg);
349 }
350
351 R delegate(T) dg;
352 Parameter[] params_data;
353
354 this(R delegate(T) dg)
355 {
356 this.dg = dg;
357 foreach(i, Ti; T)
358 params_data ~= new Parameter(text(i), []);
359 }
360
361 override Value invoke(Layer lay, Table ctx, LexPosition pos)
362 {
363 if( lay != defLay )
364 throw genex!RuntimeException(pos,
365 text("only ", defLay, " layer can call native function: ", name));
366 T typed_args;
367 foreach(i, Ti; T) {
368 typed_args[i] = cast(Ti) ctx.get(text(i), ValueLayer, pos);
369 if( typed_args[i] is null )
370 throw genex!RuntimeException(pos,
371 sprintf!"type mismatch on the argument %d of native function: %s"(i+1,name));
372 }
373 try {
374 return dg(typed_args);
375 } catch( RuntimeException e ) {
376 throw e.pos is null ? new RuntimeException(pos, e.msg, e.file, e.line) : e;
377 }
378 }
379 }
380 theContext.set(name, defLay, new NativeFunValue(dg));
381 }
382 }
383
384 version(unittest) import polemy.runtime;
385 unittest
386 {
387 auto e = new Evaluator;
388 enrollRuntimeLibrary(e);
389 auto r = assert_nothrow( e.evalString(`var x = 21; x + x*x;`) );
390 assert_eq( r, new IntValue(BigInt(21+21*21)) );
391 assert_eq( e.globalContext.get("x",ValueLayer), new IntValue(BigInt(21)) );
392 assert_nothrow( e.globalContext.get("x",ValueLayer) );
393 assert_throw!RuntimeException( e.globalContext.get("y",ValueLayer) );
394 }
395 unittest
396 {
397 auto e = new Evaluator;
398 enrollRuntimeLibrary(e);
399 auto r = assert_nothrow( e.evalString(`var x = 21; var x = x + x*x;`) );
400 assert_eq( r, new IntValue(BigInt(21+21*21)) );
401 assert_eq( e.globalContext.get("x",ValueLayer), new IntValue(21+21*21) );
402 assert_nothrow( e.globalContext.get("x",ValueLayer) );
403 assert_throw!RuntimeException( e.globalContext.get("y",ValueLayer) );
404 }
405 unittest
406 {
407 auto e = new Evaluator;
408 enrollRuntimeLibrary(e);
409 assert_eq( e.evalString(`let x=1; let y=(let x=2); x`), new IntValue(1) );
410 assert_eq( e.evalString(`let x=1; let y=(let x=2;fun(){x}); y()`), new IntValue(2) );
411 }
412
413 unittest
414 {
415 auto e = new Evaluator;
416 enrollRuntimeLibrary(e);
417 assert_eq( e.evalString(`@a x=1; @b x=2; @a(x)`), new IntValue(BigInt(1)) );
418 assert_eq( e.evalString(`@a x=1; @b x=2; @b(x)`), new IntValue(BigInt(2)) );
419 assert_eq( e.evalString(`let x=1; let _ = (@a x=2;2); x`), new IntValue(BigInt(1)) );
420 e = new Evaluator;
421 assert_throw!Throwable( e.evalString(`let x=1; let _ = (@a x=2;2); @a(x)`) );
422 }
423
424 unittest
425 {
426 auto e = new Evaluator;
427 enrollRuntimeLibrary(e);
428 assert_eq( e.evalString(`
429 @@s(x){x};
430 @s "+" = fun(x, y) {@value(
431 @s(x) - @s(y)
432 )};
433 @s(1 + 2)
434 `), new IntValue(BigInt(-1)) );
435 }
436
437 unittest
438 {
439 auto e = new Evaluator;
440 enrollRuntimeLibrary(e);
441 assert_eq( e.evalString(`
442 @@3(x){x};
443 def incr(x) { x+1 };
444 @ 3 incr(x) {@value( if @ 3(x)+1< 3 then @3(x)+1 else 0 )};
445 def fb(n @value @3) { @3(n) };
446 fb(incr(incr(incr(0))))
447 `), new IntValue(BigInt(0)) );
448 }
449
450 unittest
451 {
452 auto e = new Evaluator;
453 enrollRuntimeLibrary(e);
454 assert_nothrow( e.evalString(`
455 @macro twice(x) { x; x };
456 def main() { twice(1) };
457 main()
458 `) );
459 }
460 unittest
461 {
462 auto e = new Evaluator;
463 enrollRuntimeLibrary(e);
464 assert_nothrow( e.evalString(`case 1`) );
465 assert_nothrow( e.evalString(`case 1 when 1: 2`) );
466 }
467
468 /*
469 unittest
470 {
471 assert_eq( evalString(`var fac = fun(x){
472 if(x)
473 { x*fac(x-1); }
474 else
475 { 1; };
476 };
477 fac(10);`).val, new IntValue(BigInt(10*9*8*5040)));
478 assert_eq( evalString(`var fib = fun(x){
479 if(x<2)
480 { 1; }
481 else
482 { fib(x-1) + fib(x-2); };
483 };
484 fib(5);`).val, new IntValue(BigInt(8)));
485 }
486 unittest
487 {
488 assert_eq( evalString(`@@t = fun(x){x+1}; @t(123)`).val, new IntValue(BigInt(124)) );
489 // there was a bug that declaration in the first line of function definition
490 // cannot be recursive
491 assert_nothrow( evalString(`def foo() {
492 def bar(y) { if(y<1) {0} else {bar(0)} };
493 bar(1)
494 }; foo()`) );
495 }
496 */