001: package sisc.compiler;
002:
003: import java.io.InputStreamReader;
004: import java.util.*;
005: import sisc.data.*;
006: import sisc.exprs.*;
007: import sisc.exprs.fp.*;
008: import sisc.env.*;
009: import sisc.nativefun.FixableProcedure;
010: import sisc.interpreter.Context;
011: import sisc.interpreter.ContinuationException;
012: import sisc.interpreter.Interpreter;
013: import sisc.reader.*;
014: import sisc.util.FreeReference;
015:
016: /**
017: * Compiler - Compiles regularized Scheme s-expressions into an
018: * AST of SISC Expression objects.
019: *
020: * From v1.9 on, the Compiler expects analyzed s-expressions which
021: * have been annotated with various information about the code
022: * including free variables, lexically referenced variables, etc.
023: * The default compile() entrypoint will call the Analyzer implicitly
024: * unless instructed not to, so one may still pass fully-expanded but
025: * unanalyzed Scheme code.
026: *
027: * The format for the annotations may change in the future, but is currently:
028: *
029: * (program (referenced-var-list ...) (set-var-list ...) (free-var-list ...)
030: *
031: * <s-expression>)
032: *
033: * TODO: Make output a valid Scheme program by moving #t into the body
034: * (#%lambda #t <formals> (lexically-referenced-vars ...) <body>)
035: * (#%letrec #t <bindings (lexically-referenced-vars ...) <body>)
036: */
037: public class Compiler extends CompilerConstants {
038:
039: public Compiler() {
040: }
041:
042: public static void addSpecialForms(SymbolicEnvironment menv) {
043: for (Iterator i = SYNTACTIC_TOKENS.keySet().iterator(); i
044: .hasNext();) {
045: Object ns = i.next();
046: if (ns instanceof String) {
047: String name = (String) ns;
048: extendenv(menv, name, (Syntax) SYNTACTIC_TOKENS
049: .get(name));
050: }
051: }
052: }
053:
054: protected Expression compile(Interpreter r, Expression v,
055: Pair sets, ReferenceFactory rf, int context,
056: SymbolicEnvironment env, Pair an)
057: throws ContinuationException {
058: if (v == EMPTYLIST) {
059: //we evaluate () to the empty list, which is an "ignorable
060: //error", according to R5RS. Note that presently we never
061: //actually end up in this code since the macro expander
062: //expands () to '().
063: return EMPTYLIST;
064: } else if (v instanceof Pair) {
065: Pair expr = (Pair) v;
066: return compileApp(r, expr, sets, rf, context, env, an);
067: } else if (v instanceof Symbol) {
068: Symbol sym = (Symbol) v;
069:
070: Expression ref = rf.createReference(sym, sets, env);
071: if (an != null)
072: setAnnotations(ref, an);
073: return ref;
074: } else
075: return v;
076: }
077:
078: public Expression compile(Interpreter r, Expression v,
079: SymbolicEnvironment env) throws ContinuationException {
080: Expression e = compile(r, v, EMPTYLIST, new ReferenceFactory(),
081: REALTAIL, env, null);
082: return e;
083: }
084:
085: public static final int getExpType(SymbolicEnvironment env, Value s) {
086: if (s instanceof Syntax) {
087: return ((Syntax) s).synid;
088: } else if (s instanceof Symbol) {
089: Object h = env.lookup((Symbol) s);
090: if (h != null && (h instanceof Syntax))
091: return ((Syntax) h).synid;
092: }
093: return APPLICATION;
094: }
095:
096: static void addAnnotations(Expression e, Map m) {
097: if (m != null)
098: if (e.annotations == null)
099: e.annotations = m;
100: else
101: e.annotations.putAll(m);
102: }
103:
104: static void setAnnotations(Expression e, Pair p) {
105: while (p != EMPTYLIST) {
106: Pair kv = (Pair) p.car();
107: e.setAnnotation(symbol(kv.car()), kv.cdr());
108: p = (Pair) p.cdr();
109: }
110: }
111:
112: static void propagateNameAnnotation(Expression from, Expression to) {
113: if (from instanceof FreeReferenceExp) {
114: to.setAnnotation(PROCNAME, ((FreeReferenceExp) from)
115: .getSym());
116: }
117: }
118:
119: static boolean isImmediate(Expression e) {
120: return (e instanceof Immediate)
121: || ((e instanceof AnnotatedExpr) && (((AnnotatedExpr) e).expr instanceof Immediate));
122: }
123:
124: Expression makeEvalExp(Expression pre, Expression post) {
125: EvalExp ee = new EvalExp(pre, post, isImmediate(pre));
126: ee.setHosts();
127: return ee;
128: }
129:
130: protected int[][] resolveCopies(ReferenceFactory rf,
131: Symbol[] lexicals) {
132: List locs = new ArrayList(5), lexs = new ArrayList(5);
133: for (int i = lexicals.length - 1; i >= 0; i--) {
134: Ref t = rf.fetchRefType(lexicals[i]);
135: if (t != null) {
136: if (t.lcl)
137: locs.add(new Integer(t.idx));
138: else
139: lexs.add(new Integer(t.idx));
140: }
141: }
142: int rv[][] = new int[2][];
143:
144: rv[0] = new int[locs.size()];
145: rv[1] = new int[lexs.size()];
146: for (int i = 0; i < locs.size(); i++) {
147: rv[0][i] = ((Integer) locs.get(i)).intValue();
148: }
149:
150: for (int i = 0; i < lexs.size(); i++) {
151: rv[1][i] = ((Integer) lexs.get(i)).intValue();
152: }
153: return rv;
154: }
155:
156: public int[] findBoxes(Symbol[] formals, Pair sets) {
157: ArrayList v = new ArrayList(5);
158: for (int i = 0; i < formals.length; i++) {
159: if (assq(formals[i], sets) != FALSE)
160: v.add(new Integer(i));
161: }
162: int[] boxes = new int[v.size()];
163: for (int i = 0; i < boxes.length; i++)
164: boxes[i] = ((Integer) v.get(i)).intValue();
165: return boxes;
166: }
167:
168: public Expression compileApp(Interpreter r, Pair expr, Pair sets,
169: ReferenceFactory rf, int context, SymbolicEnvironment env,
170: Pair an) throws ContinuationException {
171:
172: Expression tmp, rv;
173:
174: Value oper = expr.car();
175: int eType = getExpType(env, oper);
176: expr = (Pair) expr.cdr();
177:
178: switch (eType) {
179: case QUOTE:
180: rv = expr.car();
181: break;
182: case PROGRAM:
183: //References
184: expr = (Pair) expr.cdr();
185: //Sets
186: sets = append((Pair) expr.car(), sets);
187: expr = (Pair) expr.cdr();
188: //Frees
189: expr = (Pair) expr.cdr();
190: rv = compile(r, expr.car(), sets, rf, context, env, null);
191: break;
192: case LAMBDA: {
193: boolean infArity = false;
194: // Skip #t
195: expr = (Pair) expr.cdr();
196:
197: Symbol[] formals = null;
198: Value ftmp = expr.car();
199: if (ftmp instanceof Pair && ftmp != EMPTYLIST) {
200: formals = argsToSymbols((Pair) ftmp);
201: do {
202: ftmp = ((Pair) ftmp).cdr();
203: } while (ftmp != EMPTYLIST && ftmp instanceof Pair);
204: infArity = ftmp instanceof Symbol;
205: } else if (expr.car() instanceof Symbol) {
206: formals = new Symbol[] { (Symbol) expr.car() };
207: infArity = true;
208: } else {
209: formals = new Symbol[0];
210: }
211:
212: expr = (Pair) expr.cdr();
213:
214: Symbol[] lexicalSyms = argsToSymbols((Pair) expr.car());
215: expr = (Pair) expr.cdr();
216: ReferenceFactory nf = new ReferenceFactory(formals,
217: lexicalSyms);
218:
219: tmp = compile(r, expr.car(), sets, nf, REALTAIL, env, null);
220: int[][] copies = resolveCopies(rf, lexicalSyms);
221: int[] boxes = findBoxes(formals, sets);
222: rv = new LambdaExp(formals.length, tmp, infArity,
223: copies[0], copies[1], (boxes.length == 0 ? null
224: : boxes));
225: }
226: break;
227: case LETREC: {
228: // Skip the #t marker
229: expr = (Pair) expr.cdr();
230:
231: Pair tmpp = (Pair) expr.car();
232:
233: Vector formv = new Vector();
234: Vector expv = new Vector();
235:
236: while (tmpp != EMPTYLIST) {
237: Pair bp = (Pair) tmpp.car();
238:
239: formv.add(bp.car());
240: expv.add(((Pair) bp.cdr()).car());
241: tmpp = (Pair) tmpp.cdr();
242: }
243:
244: Symbol[] formals = new Symbol[formv.size()];
245: Expression[] rhses = new Expression[expv.size()];
246: formv.copyInto(formals);
247: expv.copyInto(rhses);
248:
249: expr = (Pair) expr.cdr();
250: Symbol[] lexicalSyms = argsToSymbols((Pair) expr.car());
251: expr = (Pair) expr.cdr();
252:
253: rv = compileLetrec(r, formals, lexicalSyms, rhses, expr
254: .car(), sets, rf, env, context);
255: }
256: break;
257: case _IF:
258: tmp = compile(r, expr.car(), sets, rf, 0, env, null);
259: expr = (Pair) expr.cdr();
260:
261: Expression conseq = compile(r, expr.car(), sets, rf, 0,
262: env, null);
263: expr = (Pair) expr.cdr();
264: Expression altern = compile(r, expr.car(), sets, rf, 0,
265: env, null);
266: rv = new IfEval(conseq, altern);
267: ((OptimisticHost) rv).setHosts();
268: rv.annotations = tmp.annotations;
269: rv = makeEvalExp(tmp, rv);
270: break;
271: case BEGIN:
272: rv = compileBegin(r, pairToExpressions(expr), context,
273: sets, rf, env);
274: break;
275: case SET:
276: Symbol sym = (Symbol) expr.car();
277: tmp = compile(r, sym, sets, rf, 0, env, null);
278: expr = (Pair) expr.cdr();
279: Expression rhs = compile(r, expr.car(), sets, rf, 0, env,
280: null);
281: if (tmp instanceof FreeReferenceExp)
282: rv = new FreeSetEval(sym, env);
283: else
284: rv = new SetboxEval(((UnboxExp) tmp).ref);
285: rv.annotations = rhs.annotations;
286: rv = makeEvalExp(rhs, rv);
287: break;
288: case DEFINE:
289: Symbol lhs = (Symbol) expr.car();
290: expr = (Pair) expr.cdr();
291: rhs = compile(r, expr.car(), sets, rf, 0, env, null);
292: rv = new DefineEval(lhs, env);
293: addAnnotations(rv, rhs.annotations);
294: rv = makeEvalExp(rhs, rv);
295: break;
296: case MAKEANNOTATION:
297: Value aexpr = expr.car();
298: expr = (Pair) expr.cdr();
299: Pair annot = null;
300: if (expr.car() instanceof Pair)
301: annot = pair(expr.car());
302: else
303: annot = list(new Pair(OTHER, expr.car()));
304: rv = compile(r, aexpr, sets, rf, context, env, annot);
305: an = null;
306: break;
307: case APPLICATION:
308: case UNKNOWN:
309: Expression[] exps = pairToExpressions(expr);
310: compileExpressions(r, exps, sets, rf, 0, env);
311: Expression operout = compile(r, oper, sets, rf, 0, env, an);
312: rv = application(r, operout, exps, context, an, env);
313: break;
314: default:
315: error(r, "Unsupported syntactic type [" + eType
316: + "]. Should never happen!");
317: rv = null;
318: }
319: if (an != null)
320: setAnnotations(rv, an);
321: return rv;
322: }
323:
324: public static final Expression makeFillRib(Interpreter r,
325: Expression lastRand, Expression rand, int pos,
326: Expression nxp, boolean immediate) {
327: nxp = new FillRibExp(lastRand, pos, nxp, immediate);
328: addAnnotations(nxp, rand.annotations);
329:
330: /* If we're emitting debugging symbols, annotate the
331: * FillRibExps with the names of the functions in the operator
332: * position.
333: */
334: if (r.dynenv.emitDebuggingSymbols && rand instanceof AppExp) {
335: AppExp ae = (AppExp) rand;
336: propagateNameAnnotation(ae.exp, nxp);
337: }
338:
339: return nxp;
340: }
341:
342: public Expression compileLetrec(Interpreter r, Symbol[] formals,
343: Symbol[] lexicals, Expression[] rands, Expression body,
344: Pair sets, ReferenceFactory rf, SymbolicEnvironment env,
345: int context) throws ContinuationException {
346: ReferenceFactory nrf = new ReferenceFactory(formals, lexicals);
347: compileExpressions(r, rands, sets, nrf, 0, env);
348: boolean allImmediate = true;
349:
350: Expression nxp = new LetrecEval(compile(r, body, sets, nrf, 0,
351: env, null));
352: ((OptimisticHost) nxp).setHosts();
353:
354: /* If we're emitting debugging symbols, annotate the LetrecEval
355: with the name of the procedure.
356: */
357: if (r.dynenv.emitDebuggingSymbols)
358: nxp.setAnnotation(PROCNAME, _LETREC);
359:
360: Expression lastRand = VOID;
361:
362: for (int i = 0; i < rands.length; i++) {
363: if (!isImmediate(rands[i])) {
364: nxp = makeFillRib(r, lastRand, rands[i], i, nxp,
365: allImmediate);
366: lastRand = rands[i];
367: rands[i] = null;
368: allImmediate = false;
369: }
370: }
371:
372: int[][] copies = resolveCopies(rf, lexicals);
373: LetrecExp res = new LetrecExp(lastRand, rands, nxp, copies[0],
374: copies[1], allImmediate);
375: res.setHosts();
376: return res;
377: }
378:
379: public static final Expression application(Interpreter r,
380: Expression rator, Expression rands[], int context,
381: Pair annotation, SymbolicEnvironment env)
382: throws ContinuationException {
383: if (rator instanceof Value && !(rator instanceof Procedure)
384: && !(rator instanceof AnnotatedExpr)) {
385: System.err.println(warn("nonprocappdetected",
386: ((Value) rator).synopsis()));
387: }
388: Expression nxp = new AppEval();
389:
390: if (annotation != null)
391: setAnnotations(nxp, annotation);
392:
393: /* If we're emitting debugging symbols, annotate the AppEval
394: with the name of the procedure.
395: */
396: if (r.dynenv.emitDebuggingSymbols) {
397: propagateNameAnnotation(rator, nxp);
398: }
399:
400: Expression lastRand = rator;
401: boolean allImmediate = isImmediate(rator);
402:
403: addAnnotations(nxp, lastRand.annotations);
404:
405: for (int i = 0; i < rands.length; i++) {
406: if (!isImmediate(rands[i])) {
407: nxp = makeFillRib(r, lastRand, rands[i], i, nxp,
408: allImmediate);
409: lastRand = rands[i];
410: rands[i] = null;
411: allImmediate = false;
412: }
413: }
414:
415: if (allImmediate && rator instanceof FreeReferenceExp &&
416: //The realtail check is necessary since an Optimistic
417: //Expression in real tail has no parent uExp
418: (context & REALTAIL) == 0) {
419: FreeReference ref = ((FreeReferenceExp) rator)
420: .getReference();
421: Symbol ratorsym = ref.getName();
422: Value ratorval = env.lookup(ratorsym);
423: if (ratorval instanceof FixableProcedure) {
424: Expression fixedCall = null;
425:
426: switch (rands.length) {
427: case 0:
428: fixedCall = new FixedAppExp_0(ref);
429: break;
430: case 1:
431: fixedCall = new FixedAppExp_1((Immediate) rands[0],
432: ref);
433: break;
434: case 2:
435: fixedCall = new FixedAppExp_2((Immediate) rands[0],
436: (Immediate) rands[1], ref);
437: break;
438: case 3:
439: fixedCall = new FixedAppExp_3((Immediate) rands[0],
440: (Immediate) rands[1], (Immediate) rands[2],
441: ref);
442: break;
443: }
444: if (fixedCall != null) {
445: if (annotation != null)
446: setAnnotations(fixedCall, annotation);
447: if (r.dynenv.emitDebuggingSymbols) {
448: propagateNameAnnotation(rator, fixedCall);
449: }
450: addAnnotations(fixedCall, lastRand.annotations);
451: if (fixedCall instanceof OptimisticHost)
452: ((OptimisticHost) fixedCall).setHosts();
453: if (!r.dynenv.hedgedInlining) {
454: ((OptimisticExpression) fixedCall).dropSafe();
455: }
456: return fixedCall;
457: }
458: }
459: }
460:
461: AppExp res = new AppExp(lastRand, rands, nxp, allImmediate);
462: if (annotation != null)
463: setAnnotations(res, annotation);
464: res.setHosts();
465: return res;
466: }
467:
468: void compileExpressions(Interpreter r, Expression exprs[],
469: Pair sets, ReferenceFactory rf, int context,
470: SymbolicEnvironment env) throws ContinuationException {
471: for (int i = exprs.length - 1; i >= 0; i--)
472: exprs[i] = compile(r, exprs[i], sets, rf, context, env,
473: null);
474: }
475:
476: Expression compileBegin(Interpreter r, Expression[] v, int context,
477: Pair sets, ReferenceFactory rf, SymbolicEnvironment env)
478: throws ContinuationException {
479: Expression last = compile(r, v[v.length - 1], sets, rf,
480: (v.length > 1 ? REALTAIL : 0), env, null);
481: Expression be = last;
482: for (int i = v.length - 2; i >= 0; --i) {
483: Expression e = compile(r, v[i], sets, rf, 0, env, null);
484: addAnnotations(be, e.annotations);
485: be = makeEvalExp(e, be);
486: }
487: return be;
488: }
489:
490: static class Ref {
491: int idx;
492: boolean lcl;
493:
494: public Ref(boolean lcl, int idx) {
495: this .lcl = lcl;
496: this .idx = idx;
497: }
498: }
499:
500: static class ReferenceFactory {
501: Symbol[] locals, lexicals;
502:
503: public ReferenceFactory() {
504: }
505:
506: public ReferenceFactory(Symbol[] lcls, Symbol[] lxcls) {
507: locals = lcls;
508: lexicals = lxcls;
509: }
510:
511: public Ref fetchRefType(Symbol s) {
512: if (locals != null)
513: for (int i = locals.length - 1; i >= 0; i--) {
514: if (locals[i] == s)
515: return new Ref(true, i);
516: }
517: if (lexicals != null)
518: for (int i = lexicals.length - 1; i >= 0; i--) {
519: if (lexicals[i] == s)
520: return new Ref(false, i);
521: }
522: return null;
523: }
524:
525: public Expression createReference(Symbol s, Pair sets,
526: SymbolicEnvironment env) {
527: Ref r = fetchRefType(s);
528:
529: if (r == null)
530: return new FreeReferenceExp(s, env);
531:
532: Immediate ref;
533: if (r.lcl) {
534: ref = new LocalReferenceExp(r.idx);
535: } else {
536: ref = new LexicalReferenceExp(r.idx);
537: }
538:
539: return (assq(s, sets) != FALSE) ? new UnboxExp(ref)
540: : (Expression) ref;
541: }
542: }
543:
544: public static void main(String[] args) throws Exception {
545: Interpreter r = Context.enter();
546: Parser p = new Parser(new Lexer());
547: SourceReader in = new SourceReader(new InputStreamReader(
548: System.in), "stdin");
549: SymbolicEnvironment env = new MemorySymEnv();
550: Compiler.addSpecialForms(env);
551: new sisc.modules.Primitives.Index().bindAll(r, env);
552: Compiler c = new Compiler();
553: Expression v = c.compile(r, p.nextExpression(in), env);
554: System.out.println(v.express());
555: System.err.println(r.interpret(v));
556: }
557: }
558: /*
559: * The contents of this file are subject to the Mozilla Public
560: * License Version 1.1 (the "License"); you may not use this file
561: * except in compliance with the License. You may obtain a copy of
562: * the License at http://www.mozilla.org/MPL/
563: *
564: * Software distributed under the License is distributed on an "AS
565: * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
566: * implied. See the License for the specific language governing
567: * rights and limitations under the License.
568: *
569: * The Original Code is the Second Interpreter of Scheme Code (SISC).
570: *
571: * The Initial Developer of the Original Code is Scott G. Miller.
572: * Portions created by Scott G. Miller are Copyright (C) 2000-2007
573: * Scott G. Miller. All Rights Reserved.
574: *
575: * Contributor(s):
576: * Matthias Radestock
577: *
578: * Alternatively, the contents of this file may be used under the
579: * terms of the GNU General Public License Version 2 or later (the
580: * "GPL"), in which case the provisions of the GPL are applicable
581: * instead of those above. If you wish to allow use of your
582: * version of this file only under the terms of the GPL and not to
583: * allow others to use your version of this file under the MPL,
584: * indicate your decision by deleting the provisions above and
585: * replace them with the notice and other provisions required by
586: * the GPL. If you do not delete the provisions above, a recipient
587: * may use your version of this file under either the MPL or the
588: * GPL.
589: */
|