Published
Edited
Dec 22, 2021
3 stars
Insert cell
Insert cell
main(`print 1 + 12 < 23.4;
print 2 + 3;`)
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
runWASM(compile(parse(scanTokens(input))))
Insert cell
run(input)
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
showTokens(scanTokens(input))
Insert cell
scanTokens(input)
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
copyableCode(
defineAst("Expr", [
"Assign : name, value",
"Binary : left, operator, right",
"Call : callee, paren, args",
"Grouping : expression",
"Literal : value",
"Logical : left, operator, right",
"Unary : operator, right",
"Variable : name"
])
)
Insert cell
Insert cell
copyableCode(
defineAst("Stmt", [
"Block : statements",
"Expression : expression",
"Function : name, params, body",
"For : initializer, condition, increment, body",
"If : condition, thenBranch, elseBranch",
"Return : keyword, value",
"Print : expression",
"Var : name, initializer",
"While : condition, body"
])
)
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
pprint(parse(scanTokens(input)))
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
evaluate(parseExpr(scanTokens('1 + 1')))
Insert cell
interpret(parse(scanTokens(input)))
Insert cell
interpret(
parse(
scanTokens(`fun foo(x) {
x + 1;
}
foo(1);`)
)
)
Insert cell
interpret = stmts => new ASTInterpreter().interpret(stmts)
Insert cell
execute = stmt => new ASTInterpreter().execute(stmt)
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
compile = stmts => {
const compiler = new ASTCompiler();
return compiler.compileModule(stmts);
}
Insert cell
Insert cell
runWASM = module => {
const outputs = [];

const importObj = {
env: {
print: x => {
console.log(x);
outputs.push('' + x);
}
}
};

var wasmData = module.emitBinary();
var compiled = new WebAssembly.Module(wasmData);
var instance = new WebAssembly.Instance(compiled, importObj);
instance.exports.main();
return outputs.join('\n');
}
Insert cell
runWASM(compile(parse(scanTokens(input))))
Insert cell
mod = compile(parse(scanTokens(input)))
Insert cell
codeInput()
Insert cell
mod.emitText() + [mod.optimize(), 'OPTIMIZED:\n' + mod.emitText()][1]
Insert cell
Insert cell
class ASTCompiler extends AstVisitor {
constructor() {
super();
}
compileModule(stmts) {
this.module = new binaryen.Module();
//this.module.autoDrop(); // automatically pops values off the stack if they aren't last in a block

// Add functions needed for Lox runtime (just print for now)
this.module.addFunctionImport('print', 'env', 'print', [binaryen.i32], []);

// keep track so we don't add globals more than once
this.globals = new Set();
this.declaredGlobals = new Set();

const compiledStmts = [];
for (const stmt of stmts) {
const compiledStmt = stmt.accept(this);
compiledStmts.push(compiledStmt);
}

// Until we fix everything being global, disallow programs that
// declare the same name multiple times
for (const usedGlobal of this.globals) {
if (!this.declaredGlobals.has(usedGlobal)) {
throw new CompileError(`Global variable ${usedGlobal} never declared`);
}
}

this.module.addFunction(
"main",
[],
[binaryen.i32],
[],
this.module.block(null, [
...compiledStmts,
this.module.return(this.module.i32.const(0))
])
);
this.module.addFunctionExport("main", "main");

if (!this.module.validate()) {
throw new Error("validation error");
}

return this.module;
}
declareGlobal(name) {
if (this.declaredGlobals.has(name)) {
throw new CompileError(
"Global variable (they're all global) declared twice",
name
);
}
this.declaredGlobals.add(name);
this.ensureGlobalExists(name);
}
ensureGlobalExists(name) {
if (this.globals.has(name)) {
return;
}
this.globals.add(name);
const isMutable = 1;
this.module.addGlobal(
name,
binaryen.i32,
isMutable,
this.module.i32.const(0)
);
}
compileExpr(expr) {
return expr.accept(this);
}
compileStmt(stmt) {
// same as compileExpr, but these better be statements
return stmt.accept(this);
}
visit_FunctionStmt(stmt) {
const fun = new LoxFunction(stmt, this.env);
this.env.define(stmt.name.lexeme, fun);
}
visit_IfStmt(stmt) {
return this.module.if(
this.compileExpr(stmt.condition),
this.compileExpr(stmt.thenBranch),
stmt.elseBranch ? this.compileExpr(stmt.elseBranch) : undefined
);
}
visit_WhileStmt(stmt) {
throw CompileError("While statments not supported yet");
}
visit_BlockStmt(stmt) {
const compiledStatements = [];
for (const s of stmt.statements) {
compiledStatements.push(this.compileStmt(s));
}
return this.module.block(null, compiledStatements);
}
visit_VarStmt(stmt) {
this.declareGlobal(stmt.name.lexeme);
return this.module.global.set(
stmt.name.lexeme,
this.compileExpr(stmt.initializer)
);
}
visit_ReturnStmt(stmt) {
throw CompileError('Returning from Lox functions is not implemented');
}
visit_PrintStmt(stmt) {
const valueCode = this.compileExpr(stmt.expression);
const call = this.module.call('print', [valueCode], null);
return call;
}
visit_CallExpr(expr) {
throw CompileError('Calling Lox functions is not implemented');
}
visit_ExpressionStmt(stmt) {
return this.module.drop(this.compileExpr(stmt.expression));
}
visit_AssignExpr(expr) {
// Until our AST knows whether variable lookups are local, from closures, or global,
// let's make every single variable assignment global.
this.ensureGlobalExists(expr.name.lexeme);

const value = this.compileExpr(expr.value);
return this.module.block(
null,
[
this.module.global.set(expr.name.lexeme, value),
this.module.global.get(expr.name.lexeme, binaryen.i32)
],
binaryen.i32
);
}
visit_VariableExpr(expr) {
return this.module.global.get(expr.name.lexeme, binaryen.i32);
}
visit_LogicalExpr(expr) {
throw CompileError("Logical operators and, or not supported yet");
}
visit_BinaryExpr(expr) {
const [left, right] = [
this.compileExpr(expr.left),
this.compileExpr(expr.right)
];
switch (expr.operator.type) {
case TokenType.PLUS:
return this.module.i32.add(left, right);
case TokenType.MINUS:
return this.module.i32.sub(left, right);
case TokenType.SLASH:
return this.module.i32.div_s(left, right);
case TokenType.STAR:
return this.module.i32.mul(left, right);
case TokenType.GREATER:
return this.module.i32.gt_s(left, right);
case TokenType.GREATER_EQUAL:
return this.module.i32.ge_s(left, right);
case TokenType.LESS:
return this.module.i32.lt_s(left, right);
case TokenType.LESS_EQUAL:
return this.module.i32.le_s(left, right);
case TokenType.BANG_EQUAL:
return this.module.i32.ne_s(left, right);
case TokenType.EQUAL_EQUAL:
return this.module.i32.eq_s(left, right);
}
}
visit_GroupingExpr(expr) {
return this.compileExpr(expr.expression);
}
visit_LiteralExpr(expr) {
if (typeof expr.value == 'number') {
return this.module.i32.const(expr.value);
} else if (typeof expr.value === 'string') {
throw CompileError("We can't do strings yet");
}
return expr.value;
}
visit_UnaryExpr(expr) {
const right = this.compileExpr(expr.right);
switch (expr.operator.type) {
case TokenType.MINUS: {
return this.module.i32.sub(this.module.i32.const(0), right);
break;
}
case TokenType.BANG: {
return this.module.select(
right,
this.module.i32.const(1),
this.module.i32.const(1)
);
}
default: {
throw Error(`Unimplemented unary operator: ${expr.operator.type}`);
}
}
}
isTruthy(expr) {
return this.module.i32.ne(this.compileExpr(expr), this.module.i32.const(0));
}
}
Insert cell
mod.global.set
Insert cell
class CompileError extends Error {}
Insert cell
binaryen = require("binaryen@100.0.0") // TODO find newest version that works, 100 was chosed by guessing
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
input
Insert cell
Insert cell
showTokens(scanTokens('print 1 + 2 * 3; print 4 * 3;'))
Insert cell
Insert cell
Insert cell
showAST(parse(scanTokens('print 1 + 2 * 3; print 4 * 3;')))
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
m = new binaryen.Module();
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more