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 newCtx.set(p.name, argLay, eval(args[i], argLay, ctx));
227 scope _ = new PushCallStack(pos, callstackmsg);
228 return f.invoke(isMacroLayer(lay)?MacroLayer:lay, newCtx, pos);
229 }
230 throw genex!RuntimeException(pos, text("tried to call non-function: ",_f));
231 }
232
233 Value lift(Value v, Layer lay, Table ctx, LexPosition pos)
234 {
235 assert( !isASTLayer(lay), "lift to the @macro layer should never happen" );
236
237 // functions are automatically lifterd
238 if( cast(FunValue) v )
239 return v;
240
241 if( !ctx.has(lay, LiftLayer) )
242 throw genex!RuntimeException(pos, "lift function for "~lay~" is not registered" );
243
244 // similar to invokeFunction, but with only one argument bound to ValueLayer
245 auto _f = ctx.get(lay, LiftLayer, pos);
246 if(auto f = cast(FunValue)_f)
247 {
248 Table newCtx = new Table(f.definitionContext(), Table.Kind.NotPropagateSet);
249 auto ps = f.params();
250 if( ps.length != 1 )
251 throw genex!RuntimeException(pos,
252 text("lift function for", lay, " must take exactly one argument of ", ValueLayer));
253 if( ps[0].layers.length==0 || ps[0].layers.length==1 && ps[0].layers[0]==ValueLayer )
254 {
255 newCtx.set(ps[0].name, ValueLayer, v);
256 scope _ = new PushCallStack(pos, lay);
257 return f.invoke(ValueLayer, newCtx, pos);
258 }
259 else
260 throw genex!RuntimeException(pos,
261 text("lift function for", lay, " must take exactly one argument of ", ValueLayer));
262 }
263 throw genex!RuntimeException(pos,
264 text("non-function ", _f, " is registered as the lift function for ", lay));
265 }
266
267 Value createNewFunction(Fun e, Table ctx)
268 {
269 class UserDefinedFunValue : FunValue
270 {
271 Fun ast;
272 Table defCtx;
273 override const(Parameter[]) params() { return ast.params; }
274 override Table definitionContext() { return defCtx; }
275
276 this(Fun ast, Table defCtx) { this.ast=ast; this.defCtx=defCtx; }
277 override string toString() const
278 { return sprintf!"(function:%x:%x)"(cast(void*)ast, cast(void*)defCtx); }
279 override int opCmp(Object rhs) {
280 if(auto r = cast(UserDefinedFunValue)rhs) {
281 if(auto c = typeid(void*).compare(cast(void*)ast, cast(void*)r.ast))
282 return c;
283 if(auto c = typeid(void*).compare(cast(void*)defCtx, cast(void*)r.defCtx))
284 return c;
285 return 0;// [TODO] avoid using pointer value...
286 }
287 if(auto r = cast(Value)rhs) return typeid(this).opCmp(typeid(r));
288 throw genex!RuntimeException("comparison with value and something other");
289 }
290 override hash_t toHash() {
291 return (cast(hash_t)cast(void*)ast) + (cast(hash_t)cast(void*)defCtx);
292 }
293
294 AST macroCache;
295 AST[void*] mandeCache;
296 static class MemokeyType
297 {
298 void* a; Layer b; Tuple!(string,Layer,Value)[] c;
299 hash_t toHash() {
300 hash_t h = structuralHash(a) + structuralHash(b);
301 foreach(e; c)
302 h += structuralHash(e[0])+structuralHash(e[1])+structuralHash(e[2]);
303 return h;
304 }
305 mixin SimpleToString;
306 mixin SimpleConstructor;
307 mixin SimpleCompareWithoutToHash;
308 }
309 static Tuple!(Value,int)[MemokeyType] memo;
310
311 override Value invoke(Layer lay, Table ctx, LexPosition pos)
312 {
313 if( isASTLayer(lay) )
314 return eval(ast.funbody, lay, ctx);
315
316 auto nonMemoizedRun = (){
317 if( macroCache is null )
318 {
319 auto va = macroAndEval(e.funbody, lay, ctx, CascadeCtx, mandeCache);
320 macroCache = va[1];
321 return va[0];
322 }
323 else
324 return eval(macroCache, lay, ctx);
325 };
326
327 if( !isUserDefinedLayer(lay) )
328 return nonMemoizedRun();
329
330 MemokeyType memokey = new MemokeyType(cast(void*)ast, lay, ctx.direct_entries());
331
332 if(auto p = memokey in memo)
333 {
334 (*p)[1] ++;
335 return (*p)[0];
336 }
337 else
338 memo[memokey] = tuple(lift(new UndefinedValue, lay, ctx, pos), 0);
339
340 Value r = nonMemoizedRun();
341
342 int touched = memo[memokey][1];
343 memo[memokey] = tuple(r, 12345678);
344 //if(touched) {DBG("rerun :: ",r);r = nonMemoizedRun();} // twice!!
345 return r;
346 }
347 }
348 return new UserDefinedFunValue(e,ctx);
349 }
350
351 public:
352 /// Add primitive function to the global context
353 void addPrimitive(R,T...)(string name, Layer defLay, R delegate (T) dg)
354 {
355 class NativeFunValue : FunValue
356 {
357 override const(Parameter[]) params() { return params_data; }
358 override Table definitionContext() { return theContext; }
359
360 override string toString() { return sprintf!"(native:%x)"(dg.funcptr); }
361 override int opCmp(Object rhs) {
362 if(auto r = cast(NativeFunValue)rhs) return typeid(typeof(dg)).compare(&dg,&r.dg);
363 if(auto r = cast(Value)rhs) return typeid(this).opCmp(typeid(r));
364 throw genex!RuntimeException("comparison with value and something other");
365 }
366 override hash_t toHash() const {
367 return typeid(dg).getHash(&dg);
368 }
369
370 R delegate(T) dg;
371 Parameter[] params_data;
372
373 this(R delegate(T) dg)
374 {
375 this.dg = dg;
376 foreach(i, Ti; T)
377 params_data ~= new Parameter(text(i), []);
378 }
379
380 override Value invoke(Layer lay, Table ctx, LexPosition pos)
381 {
382 if( lay != defLay )
383 throw genex!RuntimeException(pos,
384 text("only ", defLay, " layer can call native function: ", name));
385 T typed_args;
386 foreach(i, Ti; T) {
387 typed_args[i] = cast(Ti) ctx.get(text(i), ValueLayer, pos);
388 if( typed_args[i] is null )
389 throw genex!RuntimeException(pos,
390 sprintf!"type mismatch on the argument %d of native function: %s"(i+1,name));
391 }
392 try {
393 return dg(typed_args);
394 } catch( RuntimeException e ) {
395 throw e.pos is null ? new RuntimeException(pos, e.msg, e.file, e.line) : e;
396 }
397 }
398 }
399 theContext.set(name, defLay, new NativeFunValue(dg));
400 }
401 }
402
403 version(unittest) import polemy.runtime;
404 unittest
405 {
406 auto e = new Evaluator;
407 enrollRuntimeLibrary(e);
408 auto r = assert_nothrow( e.evalString(`var x = 21; x + x*x;`) );
409 assert_eq( r, new IntValue(BigInt(21+21*21)) );
410 assert_eq( e.globalContext.get("x",ValueLayer), new IntValue(BigInt(21)) );
411 assert_nothrow( e.globalContext.get("x",ValueLayer) );
412 assert_throw!RuntimeException( e.globalContext.get("y",ValueLayer) );
413 }
414 unittest
415 {
416 auto e = new Evaluator;
417 enrollRuntimeLibrary(e);
418 auto r = assert_nothrow( e.evalString(`var x = 21; var x = x + x*x;`) );
419 assert_eq( r, new IntValue(BigInt(21+21*21)) );
420 assert_eq( e.globalContext.get("x",ValueLayer), new IntValue(21+21*21) );
421 assert_nothrow( e.globalContext.get("x",ValueLayer) );
422 assert_throw!RuntimeException( e.globalContext.get("y",ValueLayer) );
423 }
424 unittest
425 {
426 auto e = new Evaluator;
427 enrollRuntimeLibrary(e);
428 assert_eq( e.evalString(`let x=1; let y=(let x=2); x`), new IntValue(1) );
429 assert_eq( e.evalString(`let x=1; let y=(let x=2;fun(){x}); y()`), new IntValue(2) );
430 }
431
432 unittest
433 {
434 auto e = new Evaluator;
435 enrollRuntimeLibrary(e);
436 assert_eq( e.evalString(`@a x=1; @b x=2; @a(x)`), new IntValue(BigInt(1)) );
437 assert_eq( e.evalString(`@a x=1; @b x=2; @b(x)`), new IntValue(BigInt(2)) );
438 assert_eq( e.evalString(`let x=1; let _ = (@a x=2;2); x`), new IntValue(BigInt(1)) );
439 e = new Evaluator;
440 assert_throw!Throwable( e.evalString(`let x=1; let _ = (@a x=2;2); @a(x)`) );
441 }
442
443 unittest
444 {
445 auto e = new Evaluator;
446 enrollRuntimeLibrary(e);
447 assert_eq( e.evalString(`
448 @@s(x){x};
449 @s "+" = fun(x, y) {@value(
450 @s(x) - @s(y)
451 )};
452 @s(1 + 2)
453 `), new IntValue(BigInt(-1)) );
454 }
455
456 unittest
457 {
458 auto e = new Evaluator;
459 enrollRuntimeLibrary(e);
460 assert_eq( e.evalString(`
461 @@3(x){x};
462 def incr(x) { x+1 };
463 @ 3 incr(x) {@value( if @ 3(x)+1< 3 then @3(x)+1 else 0 )};
464 def fb(n @value @3) { @3(n) };
465 fb(incr(incr(incr(0))))
466 `), new IntValue(BigInt(0)) );
467 }
468
469 unittest
470 {
471 auto e = new Evaluator;
472 enrollRuntimeLibrary(e);
473 assert_nothrow( e.evalString(`
474 @macro twice(x) { x; x };
475 def main() { twice(1) };
476 main()
477 `) );
478 }
479 unittest
480 {
481 auto e = new Evaluator;
482 enrollRuntimeLibrary(e);
483 assert_nothrow( e.evalString(`case 1`) );
484 assert_nothrow( e.evalString(`case 1 when 1: 2`) );
485
486 // this is a shorthand for
487 // @macro x = fun(){} in @macro(x)
488 // so it is ok to fail, but it is really incovenient on REPL
489 assert_nothrow( e.evalString(`@macro x=fun(){}`) );
490 }