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, NoopLayer, null);
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(e.name!="_" && ee is e.expr)
143 newCtx.set(e.name, NoopLayer, null);
144 return eval(ee,lay,newCtx);
145 });
146 else
147 {
148 Value ri = eval(e.init, lay, newCtx);
149 if(e.name!="_")
150 newCtx.set(e.name, e.layer.empty ? lay : e.layer, ri);
151 return eval(e.expr, lay, newCtx, OverwriteCtx);
152 }
153 }
154
155 private:
156 // little little bit incremental macro defining version.
157 // enables @macro foo(x)=... in ... foo ..., only at the top level of the
158 // interpreter and functions. better than nothing :P
159 Tuple!(Value,AST) macroAndEval( AST e_, Layer lay, Table ctx, bool overwriteCtx=CascadeCtx )
160 {
161 assert( !isASTLayer(lay) );
162
163 AST decodeAST(Value v, LexPosition pos)
164 {
165 // [TODO] more informative error message
166 return polemy2d!(AST)(v, pos);
167 }
168
169 if(auto e = cast(Let)e_)
170 {
171 AST ai = decodeAST(eval(e.init, RawMacroLayer, ctx), e.init.pos);
172 Value vi = eval(ai, lay, ctx);
173
174 if( !overwriteCtx )
175 ctx = new Table(ctx, Table.Kind.NotPropagateSet);
176 string theLayer = e.layer.empty ? lay : e.layer;
177 ctx.set(e.name, theLayer, vi);
178
179 auto ave = macroAndEval( e.expr, lay, ctx, OverwriteCtx );
180 AST a = new Let(e.pos, e.name, e.layer, ai, ave[1]);
181 return tuple(ave[0], a);
182 }
183 else
184 {
185 AST a = decodeAST(eval(e_, RawMacroLayer, ctx), e_.pos);
186 Value v = eval(a, lay, ctx);
187 return tuple(v, a);
188 }
189 }
190
191 private:
192 string getNameIfPossible(AST e)
193 {
194 if(auto v = cast(Var)e)
195 return v.name;
196 return "";
197 }
198
199 Value invokeFunction(Value _f, AST[] args, Layer lay, Table ctx, LexPosition pos, string callstackmsg)
200 {
201 if(auto f = cast(FunValue)_f)
202 {
203 Table newCtx = new Table(f.definitionContext(), Table.Kind.NotPropagateSet);
204 foreach(i,p; f.params())
205 if( p.layers.empty )
206 newCtx.set(p.name, isMacroLayer(lay)?MacroLayer:lay, eval(args[i], lay, ctx));
207 else
208 foreach(argLay; p.layers)
209 newCtx.set(p.name, argLay, eval(args[i], argLay, ctx));
210 scope _ = new PushCallStack(pos, callstackmsg);
211 return f.invoke(isMacroLayer(lay)?MacroLayer:lay, newCtx, pos);
212 }
213 throw genex!RuntimeException(pos, text("tried to call non-function: ",_f));
214 }
215
216 Value lift(Value v, Layer lay, Table ctx, LexPosition pos)
217 {
218 assert( !isASTLayer(lay), "lift to the @macro layer should never happen" );
219
220 // functions are automatically lifterd
221 if( cast(FunValue) v )
222 return v;
223
224 if( !ctx.has(lay, LiftLayer) )
225 throw genex!RuntimeException(pos, "lift function for "~lay~" is not registered" );
226
227 // similar to invokeFunction, but with only one argument bound to ValueLayer
228 auto _f = ctx.get(lay, LiftLayer, pos);
229 if(auto f = cast(FunValue)_f)
230 {
231 Table newCtx = new Table(f.definitionContext(), Table.Kind.NotPropagateSet);
232 auto ps = f.params();
233 if( ps.length != 1 )
234 throw genex!RuntimeException(pos,
235 text("lift function for", lay, " must take exactly one argument of ", ValueLayer));
236 if( ps[0].layers.length==0 || ps[0].layers.length==1 && ps[0].layers[0]==ValueLayer )
237 {
238 newCtx.set(ps[0].name, ValueLayer, v);
239 scope _ = new PushCallStack(pos, lay);
240 return f.invoke(ValueLayer, newCtx, pos);
241 }
242 else
243 throw genex!RuntimeException(pos,
244 text("lift function for", lay, " must take exactly one argument of ", ValueLayer));
245 }
246 throw genex!RuntimeException(pos,
247 text("non-function ", _f, " is registered as the lift function for ", lay));
248 }
249
250 Value createNewFunction(Fun e, Table ctx)
251 {
252 class UserDefinedFunValue : FunValue
253 {
254 Fun ast;
255 Table defCtx;
256 override const(Parameter[]) params() { return ast.params; }
257 override Table definitionContext() { return defCtx; }
258
259 this(Fun ast, Table defCtx) { this.ast=ast; this.defCtx=defCtx; }
260 override string toString() const
261 { return sprintf!"(function:%x:%x)"(cast(void*)ast, cast(void*)defCtx); }
262 override int opCmp(Object rhs) {
263 if(auto r = cast(UserDefinedFunValue)rhs) {
264 if(auto c = typeid(void*).compare(cast(void*)ast, cast(void*)r.ast))
265 return c;
266 if(auto c = typeid(void*).compare(cast(void*)defCtx, cast(void*)r.defCtx))
267 return c;
268 return 0;// [TODO] avoid using pointer value...
269 }
270 if(auto r = cast(Value)rhs) return typeid(this).opCmp(typeid(r));
271 throw genex!RuntimeException("comparison with value and something other");
272 }
273 override hash_t toHash() {
274 return (cast(hash_t)cast(void*)ast) + (cast(hash_t)cast(void*)defCtx);
275 }
276
277 AST macroCache;
278 static class MemokeyType
279 {
280 void* a; Layer b; Tuple!(string,Layer,Value)[] c;
281 hash_t toHash() {
282 hash_t h = structuralHash(a) + structuralHash(b);
283 foreach(e; c)
284 h += structuralHash(e[0])+structuralHash(e[1])+structuralHash(e[2]);
285 return h;
286 }
287 mixin SimpleToString;
288 mixin SimpleConstructor;
289 mixin SimpleCompareWithoutToHash;
290 }
291 static Tuple!(Value,int)[MemokeyType] memo;
292
293 override Value invoke(Layer lay, Table ctx, LexPosition pos)
294 {
295 if( isASTLayer(lay) )
296 return eval(ast.funbody, lay, ctx);
297
298 auto nonMemoizedRun = (){
299 if( macroCache is null )
300 {
301 auto va = macroAndEval(e.funbody, lay, ctx);
302 macroCache = va[1];
303 return va[0];
304 }
305 else
306 return eval(macroCache, lay, ctx);
307 };
308
309 if( !isUserDefinedLayer(lay) )
310 return nonMemoizedRun();
311
312 MemokeyType memokey = new MemokeyType(cast(void*)ast, lay, ctx.direct_entries());
313
314 if(auto p = memokey in memo)
315 {
316 (*p)[1] ++;
317 return (*p)[0];
318 }
319 else
320 memo[memokey] = tuple(lift(new UndefinedValue, lay, ctx, pos), 0);
321
322 Value r = nonMemoizedRun();
323
324 int touched = memo[memokey][1];
325 memo[memokey] = tuple(r, 12345678);
326 //if(touched) {DBG("rerun :: ",r);r = nonMemoizedRun();} // twice!!
327 return r;
328 }
329 }
330 return new UserDefinedFunValue(e,ctx);
331 }
332
333 public:
334 /// Add primitive function to the global context
335 void addPrimitive(R,T...)(string name, Layer defLay, R delegate (T) dg)
336 {
337 class NativeFunValue : FunValue
338 {
339 override const(Parameter[]) params() { return params_data; }
340 override Table definitionContext() { return theContext; }
341
342 override string toString() { return sprintf!"(native:%x)"(dg.funcptr); }
343 override int opCmp(Object rhs) {
344 if(auto r = cast(NativeFunValue)rhs) return typeid(typeof(dg)).compare(&dg,&r.dg);
345 if(auto r = cast(Value)rhs) return typeid(this).opCmp(typeid(r));
346 throw genex!RuntimeException("comparison with value and something other");
347 }
348 override hash_t toHash() const {
349 return typeid(dg).getHash(&dg);
350 }
351
352 R delegate(T) dg;
353 Parameter[] params_data;
354
355 this(R delegate(T) dg)
356 {
357 this.dg = dg;
358 foreach(i, Ti; T)
359 params_data ~= new Parameter(text(i), []);
360 }
361
362 override Value invoke(Layer lay, Table ctx, LexPosition pos)
363 {
364 if( lay != defLay )
365 throw genex!RuntimeException(pos,
366 text("only ", defLay, " layer can call native function: ", name));
367 T typed_args;
368 foreach(i, Ti; T) {
369 typed_args[i] = cast(Ti) ctx.get(text(i), ValueLayer, pos);
370 if( typed_args[i] is null )
371 throw genex!RuntimeException(pos,
372 sprintf!"type mismatch on the argument %d of native function: %s"(i+1,name));
373 }
374 try {
375 return dg(typed_args);
376 } catch( RuntimeException e ) {
377 throw e.pos is null ? new RuntimeException(pos, e.msg, e.file, e.line) : e;
378 }
379 }
380 }
381 theContext.set(name, defLay, new NativeFunValue(dg));
382 }
383 }
384
385 version(unittest) import polemy.runtime;
386 unittest
387 {
388 auto e = new Evaluator;
389 enrollRuntimeLibrary(e);
390 auto r = assert_nothrow( e.evalString(`var x = 21; x + x*x;`) );
391 assert_eq( r, new IntValue(BigInt(21+21*21)) );
392 assert_eq( e.globalContext.get("x",ValueLayer), new IntValue(BigInt(21)) );
393 assert_nothrow( e.globalContext.get("x",ValueLayer) );
394 assert_throw!RuntimeException( e.globalContext.get("y",ValueLayer) );
395 }
396 unittest
397 {
398 auto e = new Evaluator;
399 enrollRuntimeLibrary(e);
400 auto r = assert_nothrow( e.evalString(`var x = 21; var x = x + x*x;`) );
401 assert_eq( r, new IntValue(BigInt(21+21*21)) );
402 assert_eq( e.globalContext.get("x",ValueLayer), new IntValue(21+21*21) );
403 assert_nothrow( e.globalContext.get("x",ValueLayer) );
404 assert_throw!RuntimeException( e.globalContext.get("y",ValueLayer) );
405 }
406 unittest
407 {
408 auto e = new Evaluator;
409 enrollRuntimeLibrary(e);
410 assert_eq( e.evalString(`let x=1; let y=(let x=2); x`), new IntValue(1) );
411 assert_eq( e.evalString(`let x=1; let y=(let x=2;fun(){x}); y()`), new IntValue(2) );
412 }
413
414 unittest
415 {
416 auto e = new Evaluator;
417 enrollRuntimeLibrary(e);
418 assert_eq( e.evalString(`@a x=1; @b x=2; @a(x)`), new IntValue(BigInt(1)) );
419 assert_eq( e.evalString(`@a x=1; @b x=2; @b(x)`), new IntValue(BigInt(2)) );
420 assert_eq( e.evalString(`let x=1; let _ = (@a x=2;2); x`), new IntValue(BigInt(1)) );
421 e = new Evaluator;
422 assert_throw!Throwable( e.evalString(`let x=1; let _ = (@a x=2;2); @a(x)`) );
423 }
424
425 unittest
426 {
427 auto e = new Evaluator;
428 enrollRuntimeLibrary(e);
429 assert_eq( e.evalString(`
430 @@s(x){x};
431 @s "+" = fun(x, y) {@value(
432 @s(x) - @s(y)
433 )};
434 @s(1 + 2)
435 `), new IntValue(BigInt(-1)) );
436 }
437
438 unittest
439 {
440 auto e = new Evaluator;
441 enrollRuntimeLibrary(e);
442 assert_eq( e.evalString(`
443 @@3(x){x};
444 def incr(x) { x+1 };
445 @ 3 incr(x) {@value( if @ 3(x)+1< 3 then @3(x)+1 else 0 )};
446 def fb(n @value @3) { @3(n) };
447 fb(incr(incr(incr(0))))
448 `), new IntValue(BigInt(0)) );
449 }
450
451 unittest
452 {
453 auto e = new Evaluator;
454 enrollRuntimeLibrary(e);
455 assert_nothrow( e.evalString(`
456 @macro twice(x) { x; x };
457 def main() { twice(1) };
458 main()
459 `) );
460 }
461 unittest
462 {
463 auto e = new Evaluator;
464 enrollRuntimeLibrary(e);
465 assert_nothrow( e.evalString(`case 1`) );
466 assert_nothrow( e.evalString(`case 1 when 1: 2`) );
467
468 // this is a shorthand for
469 // @macro x = fun(){} in @macro(x)
470 // so it is ok to fail, but it is really incovenient on REPL
471 assert_nothrow( e.evalString(`@macro x=fun(){}`) );
472 }
473
474 /*
475 unittest
476 {
477 assert_eq( evalString(`var fac = fun(x){
478 if(x)
479 { x*fac(x-1); }
480 else
481 { 1; };
482 };
483 fac(10);`).val, new IntValue(BigInt(10*9*8*5040)));
484 assert_eq( evalString(`var fib = fun(x){
485 if(x<2)
486 { 1; }
487 else
488 { fib(x-1) + fib(x-2); };
489 };
490 fib(5);`).val, new IntValue(BigInt(8)));
491 }
492 unittest
493 {
494 assert_eq( evalString(`@@t = fun(x){x+1}; @t(123)`).val, new IntValue(BigInt(124)) );
495 // there was a bug that declaration in the first line of function definition
496 // cannot be recursive
497 assert_nothrow( evalString(`def foo() {
498 def bar(y) { if(y<1) {0} else {bar(0)} };
499 bar(1)
500 }; foo()`) );
501 }
502 */