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 std.typecons;
14 import std.stdio;
15
16 ///
17 Table createGlobalContext()
18 {
19 auto ctx = new Table;
20 ctx.set("+", "@v", native( (IntValue lhs, IntValue rhs){return new IntValue(lhs.data + rhs.data);} ));
21 ctx.set("-", "@v", native( (IntValue lhs, IntValue rhs){return new IntValue(lhs.data - rhs.data);} ));
22 ctx.set("*", "@v", native( (IntValue lhs, IntValue rhs){return new IntValue(lhs.data * rhs.data);} ));
23 ctx.set("/", "@v", native( (IntValue lhs, IntValue rhs){return new IntValue(lhs.data / rhs.data);} ));
24 ctx.set("%", "@v", native( (IntValue lhs, IntValue rhs){return new IntValue(lhs.data % rhs.data);} ));
25 ctx.set("||", "@v", native( (IntValue lhs, IntValue rhs){return new IntValue(BigInt((lhs.data!=0) || (rhs.data!=0) ? 1:0));} ));
26 ctx.set("&&", "@v", native( (IntValue lhs, IntValue rhs){return new IntValue(BigInt((lhs.data!=0) && (rhs.data!=0) ? 1:0));} ));
27 ctx.set("<", "@v", native( (Value lhs, Value rhs){return new IntValue(BigInt(lhs < rhs ? 1: 0));} ));
28 ctx.set(">", "@v", native( (Value lhs, Value rhs){return new IntValue(BigInt(lhs > rhs ? 1: 0));} ));
29 ctx.set("<=", "@v", native( (Value lhs, Value rhs){return new IntValue(BigInt(lhs <= rhs ? 1: 0));} ));
30 ctx.set(">=", "@v", native( (Value lhs, Value rhs){return new IntValue(BigInt(lhs >= rhs ? 1: 0));} ));
31 ctx.set("==", "@v", native( (Value lhs, Value rhs){return new IntValue(BigInt(lhs == rhs ? 1: 0));} ));
32 ctx.set("!=", "@v", native( (Value lhs, Value rhs){return new IntValue(BigInt(lhs != rhs ? 1: 0));} ));
33 ctx.set("print", "@v", native( (Value a){
34 writeln(a);
35 return new IntValue(BigInt(178));
36 }));
37 ctx.set("if", "@v", native( (IntValue x, FunValue ft, FunValue fe){
38 auto toRun = (x.data==0 ? fe : ft);
39 return toRun.invoke(null, "@v", toRun.definitionContext());
40 // return toRun.invoke(pos, lay, toRun.definitionContext());
41 }));
42 ctx.set("_isint", "@v", native( (Value v){return new IntValue(BigInt(cast(IntValue)v is null ? 0 : 1));} ));
43 ctx.set("_isstr", "@v", native( (Value v){return new IntValue(BigInt(cast(StrValue)v is null ? 0 : 1));} ));
44 ctx.set("_isfun", "@v", native( (Value v){return new IntValue(BigInt(cast(FunValue)v is null ? 0 : 1));} ));
45 ctx.set("_isundefined", "@v", native( (Value v){return new IntValue(BigInt(cast(UndValue)v is null ? 0 : 1));} ));
46 ctx.set("_istable", "@v", native( (Value v){return new IntValue(BigInt(cast(Table)v is null ? 0 : 1));} ));
47 ctx.set(".", "@v", native( (Table t, StrValue s){
48 return (t.has(s.data, "@v") ? t.get(s.data, "@v") : new UndValue);
49 }) );
50 ctx.set(".?", "@v", native( (Table t, StrValue s){
51 return new IntValue(BigInt(t.has(s.data, "@v") ? 1 : 0));
52 }) );
53 ctx.set(".=", "@v", native( (Table t, StrValue s, Value v){
54 auto t2 = new Table(t, Table.Kind.NotPropagateSet);
55 t2.set(s.data, "@v", v);
56 return t2;
57 }) );
58 ctx.set("{}", "@v", native( (){
59 return new Table;
60 }) );
61 return ctx;
62 }
63
64 /// Entry point of this module
65
66 Tuple!(Value,"val",Table,"ctx") evalString(S,T...)(S str, T fn_ln_cn)
67 {
68 return eval( polemy.parse.parseString(str, fn_ln_cn) );
69 }
70
71 /// Entry point of this module
72
73 Tuple!(Value,"val",Table,"ctx") evalFile(S, T...)(S filename, T ln_cn)
74 {
75 return eval( polemy.parse.parseFile(filename, ln_cn) );
76 }
77
78 /// Entry point of this module
79
80 Tuple!(Value,"val",Table,"ctx") eval(AST e)
81 {
82 Table ctx = createGlobalContext();
83 return typeof(return)(eval(e, ctx, false, "@v"), ctx);
84 }
85
86 Value invokeFunction(in LexPosition pos, Value _f, AST[] args, Table callerCtx, Layer lay, bool AlwaysMacro=false)
87 {
88 if(auto f = cast(FunValue)_f)
89 {
90 Table ctx = new Table(f.definitionContext(), Table.Kind.NotPropagateSet);
91 foreach(i,p; f.params())
92 if( p.layers.empty )
93 if(lay=="@macro")
94 ctx.set(p.name, lay, macroEval(args[i], callerCtx, AlwaysMacro));
95 else
96 ctx.set(p.name, lay, eval(args[i], callerCtx, true, lay));
97 else
98 foreach(argLay; p.layers)
99 if(argLay=="@macro")
100 ctx.set(p.name, argLay, macroEval(args[i], callerCtx, AlwaysMacro));
101 else
102 ctx.set(p.name, argLay, eval(args[i], callerCtx, true, argLay));
103 return f.invoke(pos, lay, ctx);
104 }
105 throw genex!RuntimeException(pos, "tried to call non-function");
106 }
107
108 Value lift(in LexPosition pos, Value v, Layer lay, Table callerCtx)
109 {
110 // similar to invoke Function, but with only one argument bound to @v
111 Value _f = callerCtx.get(lay, "(system)", pos);
112 if(auto f = cast(FunValue)_f)
113 {
114 Table ctx = new Table(f.definitionContext(), Table.Kind.NotPropagateSet);
115 auto ps = f.params();
116 if( ps.length != 1 )
117 throw genex!RuntimeException(pos, "lift function must take exactly one argument at @v layer");
118 if( ps[0].layers.length==0 || ps[0].layers.length==1 && ps[0].layers[0]=="@v" )
119 {
120 ctx.set(ps[0].name, "@v", v);
121 return f.invoke(pos, "@v", ctx);
122 }
123 else
124 throw genex!RuntimeException(pos, "lift function must take exactly one argument at @v layer");
125 }
126 throw genex!RuntimeException(pos, "tried to call non-function");
127 }
128
129 /// Entry point of this module
130 /// If splitCtx = true, then inner variable declaration do not overwrite ctx.
131 /// lay is the layer ID for evaluation (standard value semantics uses "@v").
132
133 Value eval(AST e, Table ctx, bool splitCtx, Layer lay)
134 {
135 return e.match(
136 (StrLiteral e)
137 {
138 Value v = new StrValue(e.data);
139 if( lay == "@v" )
140 return v;
141 else
142 return lift(e.pos,v,lay,ctx);
143 },
144 (IntLiteral e)
145 {
146 Value v = new IntValue(e.data);
147 if( lay == "@v" )
148 return v;
149 else // rise
150 return lift(e.pos,v,lay,ctx);
151 },
152 (VarExpression e)
153 {
154 if( lay == "@v" )
155 return ctx.get(e.var, lay, e.pos);
156 try {
157 return ctx.get(e.var, lay, e.pos);
158 } catch( Throwable ) { // [TODO] more precise...
159 return lift(e.pos, ctx.get(e.var, "@v", e.pos), lay, ctx);
160 }
161 },
162 (LayeredExpression e)
163 {
164 if( e.lay == "@macro" )
165 return macroEval(e.expr, ctx, false);
166 else
167 return eval(e.expr, ctx, true, e.lay);
168 },
169 (LetExpression e)
170 {
171 // for letrec, we need this, but should avoid overwriting????
172 // ctx.set(e.var, "@v", new UndefinedValue, e.pos);
173 if(splitCtx)
174 ctx = new Table(ctx, Table.Kind.NotPropagateSet);
175 Value v = eval(e.init, ctx, true, lay);
176 ctx.set(e.var, (e.layer.length ? e.layer : lay), v, e.pos);
177 return eval(e.expr, ctx, false, lay);
178 },
179 (FuncallExpression e)
180 {
181 return invokeFunction(e.pos, eval(e.fun, ctx, true, lay), e.args, ctx, lay);
182 },
183 (FunLiteral e)
184 {
185 Value[Value[]][Layer] memo;
186 AST macroMemo = null; // cache
187
188 // funvalue need not be rised
189 // no, need to be rised !! suppose @t(fib)("int")
190 return new UserDefinedFunValue(e, ctx);
191 },
192 delegate Value (AST e)
193 {
194 throw genex!RuntimeException(e.pos, sprintf!"Unknown Kind of Expression %s"(typeid(e)));
195 }
196 );
197 }
198
199 // [TODO] Optimization
200 Value macroEval(AST e, Table ctx, bool AlwaysMacro)
201 {
202 Layer theLayer = "@v";
203
204 Table pos = new Table;
205 pos.set("filename", theLayer, new StrValue(e.pos.filename));
206 pos.set("lineno", theLayer, new IntValue(BigInt(e.pos.lineno)));
207 pos.set("column", theLayer, new IntValue(BigInt(e.pos.column)));
208 return e.match(
209 (StrLiteral e)
210 {
211 Table t = new Table;
212 t.set("pos", theLayer, pos);
213 t.set("is", theLayer, new StrValue("str"));
214 t.set("data", theLayer, new StrValue(e.data));
215 return t;
216 },
217 (IntLiteral e)
218 {
219 Table t = new Table;
220 t.set("pos", theLayer, pos);
221 t.set("is", theLayer, new StrValue("int"));
222 t.set("data", theLayer, new IntValue(e.data));
223 return t;
224 },
225 (VarExpression e)
226 {
227 try {
228 return ctx.get(e.var, "@macro", e.pos);
229 } catch( Throwable ) {// [TODO] more precies...
230 Table t = new Table;
231 t.set("pos", theLayer, pos);
232 t.set("is", theLayer, new StrValue("var"));
233 t.set("name", theLayer, new StrValue(e.var));
234 return cast(Value)t;
235 }
236 },
237 (LayeredExpression e)
238 {
239 if( AlwaysMacro )
240 {
241 Table t = new Table;
242 t.set("pos", theLayer, pos);
243 t.set("is", theLayer, new StrValue("lay"));
244 t.set("layer", theLayer, new StrValue(e.lay));
245 t.set("expr", theLayer, macroEval(e.expr,ctx,AlwaysMacro));
246 return cast(Value)t;
247 }
248 else
249 {
250 if( e.lay == "@macro" )
251 return macroEval(e.expr, ctx, false);
252 else
253 return eval(e.expr, ctx, true, e.lay);
254 }
255 },
256 (LetExpression e)
257 {
258 Table t = new Table;
259 t.set("pos", theLayer, pos);
260 t.set("is", theLayer, new StrValue("let"));
261 t.set("name", theLayer, new StrValue(e.var));
262 t.set("init", theLayer, macroEval(e.init,ctx,AlwaysMacro));
263 t.set("expr", theLayer, macroEval(e.expr,ctx,AlwaysMacro));
264 return t;
265 },
266 (FuncallExpression e)
267 {
268 Value _f = macroEval(e.fun,ctx,AlwaysMacro);
269
270 if( auto f = cast(FunValue)_f )
271 return invokeFunction(e.pos, f, e.args, ctx, "@macro", AlwaysMacro);
272
273 Table t = new Table;
274 t.set("pos", theLayer, pos);
275 t.set("is", theLayer, new StrValue("app"));
276 t.set("fun", theLayer, _f);
277 Table args = new Table;
278 foreach_reverse(a; e.args) {
279 Table cons = new Table;
280 cons.set("car",theLayer,macroEval(a,ctx,AlwaysMacro));
281 cons.set("cdr",theLayer,args);
282 args = cons;
283 }
284 t.set("arg", theLayer, args);
285 return cast(Value)t;
286 },
287 (FunLiteral e)
288 {
289 Table t = new Table;
290 t.set("pos", theLayer, pos);
291 t.set("is", theLayer, new StrValue("fun"));
292 t.set("body", theLayer, macroEval(e.funbody,ctx,AlwaysMacro));
293 Table param = new Table;
294 foreach_reverse(p; e.params)
295 {
296 Table cons = new Table;
297 Table kv = new Table;
298 kv.set("name", theLayer, new StrValue(p.name));
299 foreach_reverse(lay; p.layers)
300 {
301 Table cons2 = new Table;
302 cons2.set("car", theLayer, new StrValue(lay));
303 cons2.set("cdr", theLayer, kv);
304 kv = cons2;
305 }
306 cons.set("car", theLayer, kv);
307 cons.set("cdr", theLayer, param);
308 param = cons;
309 }
310 t.set("param", theLayer, param);
311 return t;
312 },
313 delegate Value (AST e)
314 {
315 throw genex!RuntimeException(e.pos, sprintf!"Unknown Kind of Expression %s"(typeid(e)));
316 }
317 );
318 }
319
320 unittest
321 {
322 auto r = assert_nothrow( evalString(`var x = 21; x + x*x;`) );
323 assert_eq( r.val, new IntValue(BigInt(21+21*21)) );
324 assert_eq( r.ctx.get("x","@v"), new IntValue(BigInt(21)) );
325 assert_nothrow( r.ctx.get("x","@v") );
326 assert_throw!RuntimeException( r.ctx.get("y","@v") );
327 }
328 unittest
329 {
330 auto r = assert_nothrow( evalString(`var x = 21; var x = x + x*x;`) );
331 assert_eq( r.val, new IntValue(BigInt(21+21*21)) );
332 assert_eq( r.ctx.get("x","@v"), new IntValue(BigInt(21+21*21)) );
333 assert_nothrow( r.ctx.get("x","@v") );
334 assert_throw!RuntimeException( r.ctx.get("y","@v") );
335 }
336 unittest
337 {
338 assert_eq( evalString(`let x=1; let y=(let x=2); x`).val, new IntValue(BigInt(1)) );
339 assert_eq( evalString(`let x=1; let y=(let x=2;fun(){x}); y()`).val, new IntValue(BigInt(2)) );
340 }
341 unittest
342 {
343 assert_eq( evalString(`@a x=1; @b x=2; @a(x)`).val, new IntValue(BigInt(1)) );
344 assert_eq( evalString(`@a x=1; @b x=2; @b(x)`).val, new IntValue(BigInt(2)) );
345 assert_eq( evalString(`let x=1; let _ = (@a x=2;2); x`).val, new IntValue(BigInt(1)) );
346 assert_throw!Throwable( evalString(`let x=1; let _ = (@a x=2;2); @a(x)`) );
347 }
348
349 unittest
350 {
351 assert_eq( evalString(`var fac = fun(x){
352 if(x)
353 { x*fac(x-1); }
354 else
355 { 1; };
356 };
357 fac(10);`).val, new IntValue(BigInt(10*9*8*5040)));
358 assert_eq( evalString(`var fib = fun(x){
359 if(x<2)
360 { 1; }
361 else
362 { fib(x-1) + fib(x-2); };
363 };
364 fib(5);`).val, new IntValue(BigInt(8)));
365 }
366
367 unittest
368 {
369 assert_throw!Throwable( evalString(`@@s(x){x}; @s "+"=fun(x,y){x-y};@s(1+2)`) );
370 assert_eq( evalString(`@@s(x){x}; @s "+"=fun(x,y){x-y};1+2`).val, new IntValue(BigInt(3)) );
371 assert_eq( evalString(`@@s(x){x}; @s "+"=fun(x,y){@v(@s(x)-@s(y))};1+2`).val, new IntValue(BigInt(3)) );
372 assert_eq( evalString(`@@s(x){x}; @s "+"=fun(x,y){@v(@s(x)-@s(y))};@s(1+2)`).val, new IntValue(BigInt(-1)) );
373 }
374
375 unittest
376 {
377 assert_eq( evalString(`@@t = fun(x){x+1}; @t(123)`).val, new IntValue(BigInt(124)) );
378 // there was a bug that declaration in the first line of function definition
379 // cannot be recursive
380 assert_nothrow( evalString(`def foo() {
381 def bar(y) { if(y<1) {0} else {bar(0)} };
382 bar(1)
383 }; foo()`) );
384 }
385