commit a68660f16ce9b6ec0f00e71b01fc11ba298f3fe8
parent b6d8ae1d294e540e396b01ab9d88a8375356c2aa
Author: Thomas Vigouroux <thomas.vigouroux@univ-grenoble-alpes.fr>
Date: Thu, 6 Jun 2024 14:37:25 +0200
feat: let-bindings
Diffstat:
6 files changed, 181 insertions(+), 58 deletions(-)
diff --git a/src/chunk.zig b/src/chunk.zig
@@ -6,6 +6,8 @@ pub const Op = union(enum) {
pop,
@"constant": usize,
+ @"local": usize,
+ popscope: usize,
negate,
add,
@@ -57,6 +59,10 @@ pub const Chunk = struct {
std.debug.print("constant {}\n", .{num.formatter()});
},
+ inline .@"local", .popscope => |vindex, tag| {
+ std.debug.print("{s} {}\n", .{@tagName(tag), vindex});
+ },
+
inline .@"return", .negate, .add, .substract, .multiply, .pow, .div, .pop => |_, tag| {
std.debug.print("{s}\n", .{@tagName(tag)});
},
diff --git a/src/compile.zig b/src/compile.zig
@@ -2,52 +2,127 @@ const std = @import("std");
const v = @import("value.zig");
const c = @import("chunk.zig");
-inline fn ueql(left: []const u8, right: []const u8) bool {
- return std.mem.eql(u8, left, right);
-}
-
-pub fn compile(val: *v.Value, chunk: *c.Chunk) !void {
- switch (val.val) {
- .number, .nil, .symbol => {
- const cst = try chunk.addConstant(val.ref());
- try chunk.write(.{ .constant = cst });
- },
- .list => |lst| {
- const fstsym = lst[0].val.symbol;
- // TODO: maybe this can be something else
- if (ueql(fstsym, "+")) {
- try compile(lst[1], chunk);
- for (lst[2..]) |inner| {
- try compile(inner, chunk);
- try chunk.write(.add);
- }
- } else if (ueql(fstsym, "*")) {
- try compile(lst[1], chunk);
- for (lst[2..]) |inner| {
- try compile(inner, chunk);
- try chunk.write(.multiply);
- }
- } else if (ueql(fstsym, "-")) {
- if (lst.len == 2) {
- try compile(lst[1], chunk);
- try chunk.write(.negate);
+const complog = std.log.scoped(.compile);
+pub const Compiler = struct {
+ const Self = @This();
+
+ all: std.mem.Allocator,
+ val: *v.Value,
+ chunk: c.Chunk,
+
+ // Variable management
+ sym_map: std.StringHashMap(usize),
+ scope_depth: usize,
+
+ pub fn init(all: std.mem.Allocator, val: *v.Value) !Self {
+ return Self{
+ .all = all,
+ .val = val.ref(),
+ .chunk = c.Chunk.init(all),
+ .sym_map = std.StringHashMap(usize).init(all),
+ .scope_depth = 0,
+ };
+ }
+
+ pub fn deinit(self: *Self) void {
+ self.val.unref();
+ self.chunk.deinit();
+ self.sym_map.deinit();
+ }
+
+ fn compileInner(self: *Self, val: *v.Value) !void {
+ switch (val.val) {
+ .number, .nil => {
+ const cst = try self.chunk.addConstant(val.ref());
+ try self.chunk.write(.{ .constant = cst });
+ },
+ .symbol => |sym| {
+ if (self.sym_map.get(sym)) |index| {
+ try self.chunk.write(.{ .local = index });
} else {
- try compile(lst[2], chunk);
- try compile(lst[1], chunk);
- try chunk.write(.substract);
+ return error.UndefinedVariable;
}
- } else if (ueql(fstsym, "^")) {
- try compile(lst[2], chunk);
- try compile(lst[1], chunk);
- try chunk.write(.pow);
- } else if (ueql(fstsym, "/")) {
- try compile(lst[2], chunk);
- try compile(lst[1], chunk);
- try chunk.write(.div);
- try chunk.write(.pop);
- } else {
- @panic("TODO");
- }
- },
+ },
+ .special => @panic("Cannot compile special"),
+ .list => |lst| {
+ const fstsym = lst[0].val.special;
+ // TODO: maybe this can be something else
+ switch (fstsym) {
+ inline .@"+", .@"*" => |tag| {
+ try self.compileInner(lst[1]);
+ for (lst[2..]) |inner| {
+ try self.compileInner(inner);
+ try self.chunk.write(if (tag == .@"+") .add else .multiply);
+ }
+ },
+ .@"-" => {
+ if (lst.len == 2) {
+ try self.compileInner(lst[1]);
+ try self.chunk.write(.negate);
+ } else {
+ try self.compileInner(lst[2]);
+ try self.compileInner(lst[1]);
+ try self.chunk.write(.substract);
+ }
+ },
+ .@"^" => {
+ try self.compileInner(lst[2]);
+ try self.compileInner(lst[1]);
+ try self.chunk.write(.pow);
+ },
+ .@"/" => {
+ @panic("TODO: multiple return values");
+ // try self.compileInner(lst[2]);
+ // try self.compileInner(lst[1]);
+ // try self.chunk.write(.div);
+ // try self.chunk.write(.pop);
+ },
+ // (let* (bindings...) expr)
+ .@"let*" => {
+ if (lst.len != 3) {
+ return error.InvalidNumberOfArguments;
+ }
+ if (!lst[1].isA(.list)) {
+ return error.InvalidArgType;
+ }
+
+ const blist = lst[1].val.list;
+ if (blist.len % 2 != 0) {
+ return error.UnbalancedLet;
+ }
+
+ for (0..blist.len / 2) |idx| {
+ const sym = blist[2 * idx];
+ const sval = blist[2 * idx + 1];
+
+ if (!sym.isA(.symbol)) {
+ return error.InvalidArgType;
+ }
+
+ try self.compileInner(sval);
+ complog.debug("{s} is at depth {}", .{ sym.val.symbol, self.scope_depth });
+ try self.sym_map.put(sym.val.symbol, self.scope_depth);
+ self.scope_depth += 1;
+ }
+
+ try self.compileInner(lst[2]);
+
+ // Now, remove the bindings of the variables
+ try self.chunk.write(.{ .popscope = blist.len / 2});
+ for (0..blist.len / 2) |idx| {
+ _ = self.sym_map.remove(blist[2 * idx].val.symbol);
+ self.scope_depth -= 1;
+ }
+ },
+ }
+ },
+ }
+ }
+
+ pub fn compile(self: *Self) !*const c.Chunk {
+ try self.compileInner(self.val);
+ try self.chunk.write(.@"return");
+
+ return &self.chunk;
}
-}
+};
diff --git a/src/main.zig b/src/main.zig
@@ -11,10 +11,10 @@ const GPAll = std.heap.GeneralPurposeAllocator(.{});
pub const std_options = .{
.log_level = std.log.Level.debug,
+ .log_scope_levels = &.{.{ .scope = .read, .level = .err }},
};
pub fn main() !void {
-
var gp = GPAll{};
const all = gp.allocator();
@@ -58,21 +58,19 @@ pub fn main() !void {
};
defer val.unref();
- var c = chunk.Chunk.init(all);
- defer c.deinit();
+ var compiler = try comp.Compiler.init(all, val);
+ defer compiler.deinit();
- try comp.compile(val, &c);
- try c.write(.@"return");
+ const c = try compiler.compile();
std.log.debug("Compiled version of {}", .{val.formatter()});
c.disassemble();
- const result = try v.interpret(&c);
+ const result = try v.interpret(c);
defer result.unref();
std.log.info("Result: {f}", .{result.formatter()});
}
}
-
// try v.interpret(&c);
}
diff --git a/src/scan.zig b/src/scan.zig
@@ -5,6 +5,10 @@ const ascii = std.ascii;
const readlog = std.log.scoped(.read);
+inline fn ueql(left: []const u8, right: []const u8) bool {
+ return std.mem.eql(u8, left, right);
+}
+
pub const Reader = struct {
const Self = @This();
@@ -133,11 +137,16 @@ pub const Reader = struct {
return v.Value.newInt(self.all, num);
},
.symbol => |sym| {
- if (std.mem.eql(u8, sym, "nil")) {
- return v.Value.newNil(self.all);
- } else {
- return v.Value.newSymbol(self.all, try self.all.dupe(u8, sym));
+ inline for (comptime std.enums.values(v.Special)) |tag| {
+ if (ueql(sym, @tagName(tag))) {
+ return v.Value.newSpecial(self.all, tag);
+ }
}
+
+ return if (ueql(sym, "nil"))
+ v.Value.newNil(self.all)
+ else
+ v.Value.newSymbol(self.all, try self.all.dupe(u8, sym));
},
.cparen, .eof => return error.Unexpected
}
diff --git a/src/value.zig b/src/value.zig
@@ -1,6 +1,17 @@
const std = @import("std");
pub const Int = std.math.big.int.Managed;
+pub const Special = enum {
+ // Builtin math operations
+ @"+",
+ @"/",
+ @"*",
+ @"^",
+ @"-",
+
+ @"let*",
+};
+
const vallog = std.log.scoped(.val);
pub const Value = struct {
const Self = @This();
@@ -9,6 +20,7 @@ pub const Value = struct {
number: Int,
list: []*Value,
symbol: []u8,
+ special: Special,
nil,
};
@@ -47,6 +59,10 @@ pub const Value = struct {
return try Self.init(.nil, all);
}
+ pub fn newSpecial(all: std.mem.Allocator, val: Special) !*Self {
+ return try Self.init(.{ .special = val }, all);
+ }
+
pub fn ref(self: *Self) *Self {
self.refcount += 1;
return self;
@@ -80,7 +96,7 @@ pub const Value = struct {
.symbol => |sym| {
self.all.free(sym);
},
- .nil => {},
+ .nil, .special => {},
}
self.all.destroy(self);
}
@@ -115,6 +131,7 @@ pub const Value = struct {
try writer.writeByte(')');
},
.symbol => |sym| try writer.writeAll(sym),
+ .special => |s| try writer.writeAll(@tagName(s)),
.nil => try writer.writeAll("nil"),
}
}
diff --git a/src/vm.zig b/src/vm.zig
@@ -59,6 +59,12 @@ pub const VM = struct {
try self.push(val.ref());
},
+ // ..[v].. -> ..[v]..[v]
+ .@"local" => |vindex| {
+ const val = self.stack.items[vindex];
+ try self.push(val.ref());
+ },
+
.@"return" => {
// XXX: no unref because we return
return try self.pop();
@@ -66,6 +72,17 @@ pub const VM = struct {
.pop => (try self.pop()).unref(),
+ // ..[scope...][top] -> ..[top]
+ .popscope => |amount| {
+ const topval = try self.pop();
+
+ for (0..amount) |_| {
+ (try self.pop()).unref();
+ }
+
+ try self.push(topval);
+ },
+
// ..[a] -> ..[-a]
.negate => {
var val = try self.pop();
@@ -112,6 +129,7 @@ pub const VM = struct {
const rnum = &right.val.number;
var new = try v.Int.init(self.all);
+ errdefer new.deinit();
switch (tag) {
.add => try new.add(lnum, rnum),