zahl

Log | Files | Refs | README

commit 07ee5855a365ce06eb29e62c973a92403a9a0d88
parent 74a99fe819ad724c164709d45493935ca1ce2c27
Author: Thomas Vigouroux <thomas.vigouroux@univ-grenoble-alpes.fr>
Date:   Thu, 13 Jun 2024 08:09:18 +0200

feat: lists

Also TCO

Diffstat:
Msrc/chunk.zig | 35++++++++++++++++++++++++-----------
Msrc/compile.zig | 172++++++++++++++++++++++++++++++++++++++++++++++++++++---------------------------
Msrc/main.zig | 98++++++++++++++++++++++++++++++++++++++++++-------------------------------------
Msrc/value.zig | 16+++++++++++-----
Msrc/vm.zig | 77+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------
Atest.scm | 9+++++++++
6 files changed, 281 insertions(+), 126 deletions(-)

diff --git a/src/chunk.zig b/src/chunk.zig @@ -26,8 +26,11 @@ pub const Op = union(enum) { // ..[g] -> .. define_global: u32, - // ..[scope...][top] -> ..[top] - popscope: usize, + // ..[scope...][top...] -> ..[top...] + popscope: struct { + offset: u16, + scope: u16 + }, // ..[a] -> ..[-a] negate, @@ -48,7 +51,13 @@ pub const Op = union(enum) { print, // ..[r][l] -> ..[l/r][l%r] - div + div, + + // ..[(lst.. )][h] -> ..[(h lst..)] + cons, + + // ..[(h lst..)] -> ..[(lst..)][h] + uncons, }; var _ = std.debug.assert(@sizeOf(Op) == 4); @@ -89,24 +98,28 @@ pub const Chunk = struct { } pub fn disassembleInstr(self: Self, instr: Op) void { + std.debug.print("{s} ", .{@tagName(instr)}); switch (instr) { - inline .@"constant", .get_global, .define_global => |vindex, tag| { + inline .@"constant", .get_global, .define_global => |vindex| { const num = self.values.items[vindex]; - std.debug.print("{s} {}\n", .{@tagName(tag), num.formatter()}); + std.debug.print("{}", .{num.formatter()}); }, - inline .call, .compare => |cval, tag| { - std.debug.print("{s} {}\n", .{@tagName(tag), cval}); + inline .call, .compare => |cval| { + std.debug.print("{}", .{cval}); }, - inline .@"local", .popscope, .jumpfalse, .jump => |vindex, tag| { - std.debug.print("{s} {}\n", .{@tagName(tag), vindex}); + inline .@"local", .jumpfalse, .jump => |vindex| { + std.debug.print("{}", .{vindex}); }, - inline .@"return", .negate, .add, .substract, .multiply, .pow, .div, .pop, .print => |_, tag| { - std.debug.print("{s}\n", .{@tagName(tag)}); + .popscope => |params| { + std.debug.print("offset={} scope={}", .{params.offset, params.scope}); }, + + inline else => {}, } + std.debug.print("\n", .{}); } pub fn disassemble(self: Self) void { diff --git a/src/compile.zig b/src/compile.zig @@ -6,11 +6,15 @@ const complog = std.log.scoped(.compile); const Storage = union(enum) { local: u32, value: *v.Value }; -const CompileError = error{ InvalidNumberOfArguments, InvalidArgType, UnbalancedBindings, Undefined, OutOfMemory }; +const CompileError = error{ InvalidNumberOfArguments, InvalidArgType, UnbalancedBindings, Undefined, OutOfMemory, NotEnoughArguments }; pub const Compiler = struct { const Self = @This(); + const CompileState = struct { + return_this: bool, + }; + all: std.mem.Allocator, val: *v.Value, func: v.Function, @@ -57,7 +61,8 @@ pub const Compiler = struct { return null; } - fn compileInner(self: *Self, val: *v.Value) CompileError!void { + fn compileInner(self: *Self, val: *v.Value, astate: CompileState) CompileError!void { + var state = astate; switch (val.val) { .function => |_| @panic("Unreachable"), .symbol => |sym| { @@ -85,14 +90,23 @@ pub const Compiler = struct { if (lst[0].isA(.symbol)) { // First, push the arguments one by one for (lst[1..]) |param| { - try self.compileInner(param); + try self.compileInner(param, .{ .return_this = false }); } - const symc = try self.getChunk().addConstant(lst[0].ref()); - try self.getChunk().write(.{ .get_global = symc }); - try self.getChunk().write(.{ .call = lst.len - 1 }); + // Now either TCO or call + if (state.return_this and std.mem.eql(u8, lst[0].val.symbol, self.func.name)) { + if (lst.len - 1 != self.func.arity) { + return CompileError.NotEnoughArguments; + } + try self.getChunk().write(.{ .popscope = .{ .offset = self.func.arity, .scope = self.func.arity } }); + try self.getChunk().write(.{ .jump = 0 }); + } else { + const symc = try self.getChunk().addConstant(lst[0].ref()); + try self.getChunk().write(.{ .get_global = symc }); + try self.getChunk().write(.{ .call = lst.len - 1 }); + } } else { - try self.compileSpecial(lst[0].val.special, lst); + state = try self.compileSpecial(lst[0].val.special, lst, state); } }, .number, .nil, .true, .false => { @@ -100,42 +114,48 @@ pub const Compiler = struct { try self.getChunk().write(.{ .constant = cst }); }, } + + if (state.return_this) { + try self.getChunk().write(.@"return"); + } } - fn compileSpecial(self: *Self, name: v.Special, lst: []*v.Value) !void { + fn compileSpecial(self: *Self, name: v.Special, lst: []*v.Value, state: CompileState) !CompileState { switch (name) { inline .@"+", .@"*" => |tag| { - try self.compileInner(lst[1]); + try self.compileInner(lst[1], .{ .return_this = false }); for (lst[2..]) |inner| { - try self.compileInner(inner); + try self.compileInner(inner, .{ .return_this = false }); try self.getChunk().write(if (tag == .@"+") .add else .multiply); } }, .@"-" => { if (lst.len == 2) { - try self.compileInner(lst[1]); + try self.compileInner(lst[1], .{ .return_this = false }); try self.getChunk().write(.negate); } else { - try self.compileInner(lst[2]); - try self.compileInner(lst[1]); + try self.compileInner(lst[2], .{ .return_this = false }); + try self.compileInner(lst[1], .{ .return_this = false }); try self.getChunk().write(.substract); } }, inline .@"/", .@"%" => |tag| { - try self.compileInner(lst[2]); - try self.compileInner(lst[1]); + try self.compileInner(lst[2], .{ .return_this = false }); + try self.compileInner(lst[1], .{ .return_this = false }); try self.getChunk().write(.div); try self.getChunk().write(switch (tag) { .@"/" => .pop, - .@"%" => .{ .popscope = 1 }, - else => @compileError("Unreachable") + .@"%" => .{ + .popscope = .{ .offset = 1, .scope = 1 }, + }, + else => @compileError("Unreachable"), }); }, inline .@"=", .@"<", .@"^" => |val| { - try self.compileInner(lst[2]); - try self.compileInner(lst[1]); + try self.compileInner(lst[2], .{ .return_this = false }); + try self.compileInner(lst[1], .{ .return_this = false }); try self.getChunk().write(switch (val) { .@"^" => .pow, .@"=" => .{ .compare = .eq }, @@ -169,7 +189,7 @@ pub const Compiler = struct { const storage: Storage = if (self.isConstant(sval)) |cval| .{ .value = cval } else blk: { - try self.compileInner(sval); + try self.compileInner(sval, .{ .return_this = false }); complog.debug("{s} is at depth {}", .{ sym.val.symbol, self.scope_depth }); const loc = .{ .local = self.scope_depth }; self.scope_depth += 1; @@ -179,10 +199,11 @@ pub const Compiler = struct { try self.sym_map.put(sym.val.symbol, storage); } - try self.compileInner(lst[2]); + // FIXME: TCO for let + try self.compileInner(lst[2], .{ .return_this = false }); // Now, remove the bindings of the variables - var to_pop: usize = 0; + var to_pop: u16 = 0; for (0..blist.len / 2) |idx| { const got = self.sym_map.fetchRemove(blist[2 * idx].val.symbol).?; switch (got.value) { @@ -194,7 +215,7 @@ pub const Compiler = struct { } } if (to_pop != 0) { - try self.getChunk().write(.{ .popscope = to_pop }); + try self.getChunk().write(.{ .popscope = .{ .scope = to_pop, .offset = 1 } }); } }, @@ -205,28 +226,36 @@ pub const Compiler = struct { } // Generate cond - try self.compileInner(lst[1]); + try self.compileInner(lst[1], .{ .return_this = false }); // If falsy then jump to else try self.getChunk().write(.{ .jumpfalse = undefined }); const jmpthen = self.getChunk().lastInstrRef(); - try self.compileInner(lst[2]); + try self.compileInner(lst[2], state); - try self.getChunk().write(.{ .jump = undefined }); - const jmpelse = self.getChunk().lastInstrRef(); + var jmpelse: usize = undefined; + if (!state.return_this) { + try self.getChunk().write(.{ .jump = undefined }); + jmpelse = self.getChunk().lastInstrRef(); + } self.getChunk().instrs.items[jmpthen] = .{ .jumpfalse = self.getChunk().nextPc() }; complog.debug("Backpatched jumpfalse: {}", .{jmpthen}); - try self.compileInner(lst[3]); - self.getChunk().instrs.items[jmpelse] = .{ .jump = self.getChunk().nextPc() }; - complog.debug("Backpatched jump: {}", .{jmpelse}); + try self.compileInner(lst[3], state); + if (!state.return_this) { + self.getChunk().instrs.items[jmpelse] = .{ .jump = self.getChunk().nextPc() }; + complog.debug("Backpatched jump: {}", .{jmpelse}); + } + + // Either it was false, or we generated the returns in both branches + return .{ .return_this = false }; }, - // (def! name value) - .@"def!" => { - if (lst.len != 3) { + // (defn! name (args...) value) + .@"defn!" => { + if (lst.len != 4) { return CompileError.InvalidNumberOfArguments; } @@ -234,24 +263,11 @@ pub const Compiler = struct { return CompileError.InvalidArgType; } - const sym = try self.getChunk().addConstant(lst[1].ref()); - - try self.compileInner(lst[2]); - - try self.getChunk().write(.{ .define_global = sym }); - }, - - // (fn* (args...) expr) - .@"fn*" => { - if (lst.len != 3) { - return CompileError.InvalidNumberOfArguments; - } - - if (!lst[1].isA(.list)) { + if (!lst[2].isA(.list)) { return CompileError.InvalidArgType; } - const args = lst[1].val.list; + const args = lst[2].val.list; for (args) |arg| { if (!arg.isA(.symbol)) { @@ -261,36 +277,76 @@ pub const Compiler = struct { const arity = args.len; - var inner = try Compiler.init(self.all, lst[2]); + var inner = try Compiler.init(self.all, lst[3]); defer inner.deinit(); + inner.func.name = lst[1].val.symbol; + inner.func.arity = @intCast(arity); + // Declare the parameters for (args) |arg| { - const loc: Storage = .{.local = inner.scope_depth}; - inner.scope_depth+=1; + const loc: Storage = .{ .local = inner.scope_depth }; + inner.scope_depth += 1; try inner.sym_map.put(arg.val.symbol, loc); } // Now finish compilation - var res = try inner.compile(); - res.arity = arity; + const res = try inner.compile(); const valres = try v.Value.newFunction(self.all, res); const vindex = try self.getChunk().addConstant(valres); - try self.getChunk().write(.{.constant = vindex}); + try self.getChunk().write(.{ .constant = vindex }); + + const sym = try self.getChunk().addConstant(lst[1].ref()); + + try self.getChunk().write(.{ .define_global = sym }); }, // (print expr) .@"print!" => { - try self.compileInner(lst[1]); + try self.compileInner(lst[1], .{ .return_this = false }); try self.getChunk().write(.print); - } + }, + + .cons => { + try self.compileInner(lst[2], .{ .return_this = false }); + try self.compileInner(lst[1], .{ .return_this = false }); + try self.getChunk().write(.cons); + }, + + .list => { + var newarr = try self.all.alloc(*v.Value, lst.len - 1); + + for (lst[1..], 0..) |oval, idx| { + newarr[idx] = oval.ref(); + } + + errdefer { + for (newarr) |nval| { + nval.unref(); + } + self.all.free(newarr); + } + + const val = try self.getChunk().addConstant(try v.Value.newList(self.all, newarr)); + try self.getChunk().write(.{ .constant = val }); + }, + + inline .fst, .rest => |tag| { + try self.compileInner(lst[1], .{ .return_this = false }); + try self.getChunk().write(.uncons); + try self.getChunk().write(switch (tag) { + .fst => .{ .popscope = .{ .offset = 1, .scope = 1 } }, + .rest => .pop, + else => @compileError("unreachable"), + }); + }, } + return state; } pub fn compile(self: *Self) CompileError!v.Function { - try self.compileInner(self.val); - try self.getChunk().write(.@"return"); + try self.compileInner(self.val, .{ .return_this = true }); if (std.log.logEnabled(.debug, .compile)) { complog.debug("Compiled version of {}", .{self.val.formatter()}); diff --git a/src/main.zig b/src/main.zig @@ -43,6 +43,43 @@ pub fn myLogFn( stderr.print(scope_prefix ++ format ++ "\n", args) catch return; } +fn runContent(content: []const u8, v: *vm.VM, all: std.mem.Allocator) !void { + var offset: ?usize = null; + var reader = try s.Reader.init(content, all, &offset); + + while (reader.readValue(&offset)) |val| { + defer val.unref(); + + var compiler = try comp.Compiler.init(all, val); + defer compiler.deinit(); + + var c = try compiler.compile(); + defer c.deinit(); + + const result = try v.interpret(&c); + defer result.unref(); + std.debug.assert(v.stack.items.len == 0); + + const stdout = std.io.getStdOut(); + try std.fmt.format(stdout.writer(), "=> {}\n", .{result.formatter()}); + } else |err| { + if (err != error.Eof) { + std.log.err("Parse error {} at {}, char '{c}' ({})", .{err, offset.?, content[offset.?], content[offset.?]}); + return err; + } + } +} + +fn runFile(path: []const u8, v: *vm.VM, all: std.mem.Allocator) !void { + // TODO: file parsing stuff + var file = try std.fs.cwd().openFile(path, .{}); + defer file.close(); + + const content = try file.readToEndAlloc(all, 10 * 1024 * 1024); + defer all.free(content); + try runContent(content, v, all); +} + pub fn main() !void { var gp = GPAll{}; var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator); @@ -63,62 +100,31 @@ pub fn main() !void { var args = std.process.args(); _ = args.next(); - var offset: ?usize = null; - if (args.next()) |path| { - // TODO: file parsing stuff - var file = try std.fs.cwd().openFile(path, .{}); - defer file.close(); - - const content = try file.readToEndAlloc(all, 10 * 1024 * 1024); - defer all.free(content); - - var reader = try s.Reader.init(content, all, &offset); - - while (reader.readValue(&offset)) |val| { - defer val.unref(); - - var compiler = try comp.Compiler.init(all, val); - defer compiler.deinit(); - - var c = try compiler.compile(); - defer c.deinit(); - - const result = try v.interpret(&c); - defer result.unref(); - std.debug.assert(v.stack.items.len == 0); - } else |err| { - if (err != error.Eof) { - std.log.err("Parse error {} at {}, char '{c}' ({})", .{err, offset.?, content[offset.?], content[offset.?]}); - return err; - } - } + try runFile(path, &v, all); } else { var buf: [1024:0]u8 = undefined; - const stdout = std.io.getStdOut(); + _ = cl.crossline_history_load(".zahl_history"); + defer _ = cl.crossline_history_save(".zahl_history"); while (cl.crossline_readline("> ", &buf, buf.len)) |obuf| { const input = obuf[0..std.mem.len(obuf)]; - var reader = try s.Reader.init(input, all, &offset); - var val = reader.readValue(&offset) catch |err| { - std.log.err("Parsing error {} at {}, char '{c}'", .{err, offset.?, obuf[offset.?]}); + if (input.len == 0) { continue; - }; - defer val.unref(); - - var compiler = try comp.Compiler.init(all, val); - defer compiler.deinit(); - - var c = try compiler.compile(); - defer c.deinit(); - - const result = try v.interpret(&c); - defer result.unref(); - std.debug.assert(v.stack.items.len == 0); + } - try std.fmt.format(stdout.writer(), "Result: {}\n", .{result.formatter()}); + if (input[0] == '.') { + var tokens = std.mem.tokenizeScalar(u8, input, ' '); + if (tokens.next()) |fst| { + if (std.mem.eql(u8, fst, ".read")) { + try runFile(tokens.next().?, &v, all); + } + } + } else { + try runContent(input, &v, all); + } } } } diff --git a/src/value.zig b/src/value.zig @@ -13,14 +13,19 @@ pub const Special = enum { @"let*", @"if", - @"def!", + @"defn!", @"print!", - @"fn*", // Comparisons @"=", - @"<" + @"<", + + // List manipulation + cons, + fst, + rest, + list, }; pub const Function = struct { @@ -28,7 +33,8 @@ pub const Function = struct { code: c.Chunk, all: std.mem.Allocator, - arity: usize, + arity: u16, + name: []const u8 = "_main", pub fn init(all: std.mem.Allocator) Self { return Self { @@ -194,7 +200,7 @@ pub const Value = struct { }, .symbol => |sym| try writer.writeAll(sym), .special => |s| try writer.writeAll(@tagName(s)), - .function => |_| try writer.writeAll("<function>"), + .function => |f| try writer.print("<function {s}>", .{f.name}), inline .nil, .true, .false => |_, tag| try writer.writeAll(@tagName(tag)), } } diff --git a/src/vm.zig b/src/vm.zig @@ -78,14 +78,21 @@ pub const VM = struct { self.currentFrame().ip = self.currentFrame().ip[1..]; } - fn doPopScope(self: *Self, amount: usize) !void { - const topval = self.pop(); + fn doPopScope(self: *Self, offset: u16, amount: u16) !void { + var valbuf: [255]*v.Value = undefined; + + for (0..offset) |idx| { + valbuf[idx] = self.pop(); + } for (0..amount) |_| { self.pop().unref(); } - try self.push(topval); + + for (0..offset) |idx| { + try self.push(valbuf[offset - idx - 1]); + } } fn run(self: *Self) !*v.Value { @@ -149,7 +156,9 @@ pub const VM = struct { std.debug.assert(sym.isA(.symbol)); vmlog.debug("Defining {s}", .{sym.val.symbol}); - try self.globals.put(sym.val.symbol, val); + if (try self.globals.fetchPut(sym.val.symbol, val)) |old| { + old.value.unref(); + } self.advanceIp(); }, @@ -197,7 +206,7 @@ pub const VM = struct { return try v.Value.newNil(self.all); } } else { - try self.doPopScope(frame.func.arity); + try self.doPopScope(1, frame.func.arity); } }, @@ -207,7 +216,7 @@ pub const VM = struct { }, .popscope => |amount| { - try self.doPopScope(amount); + try self.doPopScope(amount.offset, amount.scope); self.advanceIp(); }, @@ -227,6 +236,62 @@ pub const VM = struct { self.advanceIp(); }, + .cons => { + var head = self.pop(); + defer head.unref(); + + var lst = self.pop(); + defer lst.unref(); + + if (!lst.isA(.list)) { + return VMError.InvalidType; + } + + var newarr = try self.all.alloc(*v.Value, lst.val.list.len + 1); + + newarr[0] = head.ref(); + for (lst.val.list, 1..) |oldval, idx| { + newarr[idx] = oldval.ref(); + } + + errdefer { + for (newarr) |nval| { + nval.unref(); + } + self.all.free(newarr); + } + + try self.push(try v.Value.newList(self.all, newarr)); + self.advanceIp(); + }, + + .uncons => { + var lst = self.pop(); + defer lst.unref(); + + if (!lst.isA(.list)) { + return VMError.InvalidType; + } + + const oldarr = lst.val.list; + + var newarr = try self.all.alloc(*v.Value, oldarr.len - 1); + + for (oldarr[1..], 0..) |oldval, idx| { + newarr[idx] = oldval.ref(); + } + errdefer { + for (newarr) |nval| { + nval.unref(); + } + self.all.free(newarr); + } + + try self.push(try v.Value.newList(self.all, newarr)); + try self.push(oldarr[0].ref()); + self.advanceIp(); + }, + .div => { var left = self.pop(); defer left.unref(); diff --git a/test.scm b/test.scm @@ -0,0 +1,9 @@ +(defn! checkDivisor (num div bound) + (if (< div bound) + (if (= 0 (% num div)) + false + (checkDivisor num (+ 1 div) bound)) + true)) + +(defn! prime? (num) + (checkDivisor num 2 num)) ;; FIXME: check up to (sqrt num)