diff options
| -rw-r--r-- | .gitignore | 3 | ||||
| -rw-r--r-- | build.zig | 10 | ||||
| -rw-r--r-- | html/notes/cons.md | 2 | ||||
| -rw-r--r-- | html/notes/nan.md | 120 | ||||
| -rw-r--r-- | src/libzisp.zig | 51 | ||||
| -rw-r--r-- | src/libzisp/value.zig | 221 | ||||
| -rw-r--r-- | src/libzisp/value/boole.zig | 10 | ||||
| -rw-r--r-- | src/libzisp/value/char.zig | 24 | ||||
| -rw-r--r-- | src/libzisp/value/double.zig | 37 | ||||
| -rw-r--r-- | src/libzisp/value/fixnum.zig | 87 | ||||
| -rw-r--r-- | src/libzisp/value/misc.zig | 6 | ||||
| -rw-r--r-- | src/libzisp/value/ptr.zig | 176 | ||||
| -rw-r--r-- | src/libzisp/value/sstr.zig | 3 | ||||
| -rw-r--r-- | src/main.zig | 2 | ||||
| -rw-r--r-- | src/root.zig | 191 |
15 files changed, 722 insertions, 221 deletions
@@ -2,4 +2,5 @@ /html/index.html /html/notes/*.html .zig-cache -zig-out
\ No newline at end of file +zig-out +a.out @@ -23,7 +23,7 @@ pub fn build(b: *std.Build) void { // only contains e.g. external object files, you can make this `null`. // In this case the main source file is merely a path, however, in more // complicated build scripts, this could be a generated file. - .root_source_file = b.path("src/root.zig"), + .root_source_file = b.path("src/libzisp.zig"), .target = target, .optimize = optimize, }); @@ -42,14 +42,14 @@ pub fn build(b: *std.Build) void { // Modules can depend on one another using the `std.Build.Module.addImport` function. // This is what allows Zig source code to use `@import("foo")` where 'foo' is not a // file path. In this case, we set up `exe_mod` to import `lib_mod`. - exe_mod.addImport("zisp_lib", lib_mod); + exe_mod.addImport("libzisp", lib_mod); // Now, we will create a static library based on the module we created above. // This creates a `std.Build.Step.Compile`, which is the build step responsible // for actually invoking the compiler. const lib = b.addLibrary(.{ .linkage = .static, - .name = "zisp", + .name = "libzisp", .root_module = lib_mod, }); @@ -114,3 +114,7 @@ pub fn build(b: *std.Build) void { test_step.dependOn(&run_lib_unit_tests.step); test_step.dependOn(&run_exe_unit_tests.step); } + +// Local Variables: +// fill-column: 90 +// End: diff --git a/html/notes/cons.md b/html/notes/cons.md index 3f38519..29bb2d6 100644 --- a/html/notes/cons.md +++ b/html/notes/cons.md @@ -25,7 +25,7 @@ immutable lists transparently backed by arrays, to represent rest arguments. But the following paper offers a very compelling alternative: -https://legacy.cs.indiana.edu/~dyb/pubs/LaSC-3-3-pp229-244.pdf +[A New Approach to Procedures with Variable Arity](https://legacy.cs.indiana.edu/~dyb/pubs/LaSC-3-3-pp229-244.pdf) Let's first summarize the paper, and then see how we can adapt its ideas for Zisp. diff --git a/html/notes/nan.md b/html/notes/nan.md index c56609c..35a562f 100644 --- a/html/notes/nan.md +++ b/html/notes/nan.md @@ -171,13 +171,13 @@ Let's go back to considering the quiet bit a separate field: { sign == 0x1, exp == 0x7ff, quiet == 0x1, rest >= 0x1 } :: Negative But, I hear you say, the positive range is missing zero! Worry not, for -maths is wizardry. We will actually store positive values as their unary +maths is wizardry. We will actually store positive values as their ones' complement (bitwise NOT) meaning that all bits being set is our zero, and only the LSB being set is the highest possible value. This must be combined with a bitwise OR mask, to ensure that the 13 highest of the 64 bits turn into the correct starting bit pattern for a signed NaN. -Unpacking it is just as simple: Take the unary complement (bitwise NOT) and +Unpacking it is just as simple: Take the ones' complement (bitwise NOT) and then use an AND mask to unset the 13 highest: POS_INT_PACK(x) = ~x | 0xfff8000000000000 @@ -237,7 +237,8 @@ unset quiet bit, this would make our value an infinity, and in case of a set quiet bit it would give us a canonical quiet NaN. Each of them is allowed any other payload than zero. -### Pointers + +## Pointers It would seem that we have 51 bits left to represent a pointer (though we need to avoid the value zero). But we only need 48 bits... or even less! @@ -246,7 +247,7 @@ really need 45 of the 48 bits, given the least significant 3 will never be set. This gives us a whole 6 free bits to tag pointers with! If we have that much play room, we can do some crazy things. -#### Foreign pointers +### Foreign pointers Firstly, let's introduce the concept of a "foreign" pointer. This means the pointer doesn't necessarily point to a Zisp object, and may not be 8-byte @@ -269,7 +270,7 @@ essentially defined another fixnum range of 50 bits. This can include the value zero, since the foreign bit being set ensures we don't step on the forbidden all-zero payload value. -#### Zisp pointers +### Zisp pointers Now let's look at what we can do with "native" Zisp pointers. @@ -319,6 +320,13 @@ Let's use the term "indirect" for this tag, since "pointer" is already used: { pointer == 0x1, foreign == 0x0, indirect: u1, rest: u49 } +Should these indirect pointers objects be mutable, then they may contain a +null pointer; the forbidden zero value is avoided through the fact that the +indirect bit is set. + +Hmm, indirect pointers may instead become weak pointers at some point! This +would fit perfectly since they can contain null. + Direct or indirect makes no difference to the fact that the pointer value will be 8-byte aligned, so we still have 4 bits for more information about what's being pointed to. Also, since the actual pointer value can never be @@ -335,6 +343,10 @@ remaining 49 bits: The pointer value is extracted by masking the entire bit sequence, so it actually becomes a 48-bit value without further shifting. +(This part of the article is kinda obsolete. Implementation details are up +for debate and we may or may not use bit shifting. It's not that expensive +of an operation, after all.) + The tag can be used to tell us what we're pointing to, so that type checks often don't require following the pointer. The memory location that's being pointed to may duplicate this information, since we may want to ensure that @@ -347,22 +359,22 @@ represent, making sure to have an "other" wildcard for future extensions. The right side shows the value of the type tag when it's acquired by masking the 49-bit Zisp pointer payload. - 0. String (Symbol) .... 0x0000000000000 - 1. Pair (List) 0x0000000000001 - 2. Vector ............. 0x0000000000002 - 3. Map (Hash-table) 0x0000000000003 - 4. Box ................ 0x0000000000004 - 5. Record 0x0000000000005 - 6. Class .............. 0x0000000000006 - 7. Instance 0x0000000000007 - 8. Text ............... 0x1000000000000 - 9. Byte-vector 0x1000000000001 - 10. Procedure ......... 0x1000000000002 - 11. Continuation 0x1000000000003 - 12. Port .............. 0x1000000000004 - 13. Error 0x1000000000005 - 14. Enum .............. 0x1000000000006 - 15. Other 0x1000000000007 + 0. String (Symbol) ... 0x0000000000000 + 1. Pair (List) 0x0000000000001 + 2. Vector ............ 0x0000000000002 + 3. Map (Hash-table) 0x0000000000003 + 4. Box ............... 0x0000000000004 + 5. Record 0x0000000000005 + 6. Class ............. 0x0000000000006 + 7. Instance 0x0000000000007 + 8. Text .............. 0x1000000000000 + 9. Byte-vector 0x1000000000001 + 10. Procedure ........ 0x1000000000002 + 11. Continuation 0x1000000000003 + 12. Port ............. 0x1000000000004 + 13. Error 0x1000000000005 + 14. Enum ............. 0x1000000000006 + 15. Other 0x1000000000007 This list is likely to change; for example: errors should probably be class instances, continuations could be merged with procedures, and so on. But @@ -372,10 +384,72 @@ quite sufficient for avoiding a pointer de-reference in type checking. (Why is it so important to avoid following a pointer when checking a type? Who knows? Did I say it was important? Why look at me like that??) -### Other values, including Unicode +(Since I wrote this, I decided to use bit shifting after all, and the tags +are straightforward values from 0 to 15.) + + +## Other values + +We still have one entire `2^51 - 1` value range left. We will split it the +following way. This one uses a very simple partitioning scheme: + + { tag: u3, payload: u48 } + +The following tags are defined: + + 001 = short string + 010 = char (Unicode code point) + 100 = singletons (false, true, etc.) + +Other tags are undefined and reserved for the future. Note that 000 is +missing, so we automatically avoid the forbidden zero payload. + +### What the heck is a "short string"? + +Remember that (strings are immutable)[symbols.html] in Zisp. This allows us +to use an amazing optimization where short strings can be represented as +immediate values. + +We can't get to 56 bits (7 bytes), but 48 bits (6 bytes) fits perfectly into +our payload! So any interned string (equivalent to a Scheme symbol) in Zisp +will in fact be an immediate value if 6 bytes or shorter, and doesn't need +any heap allocation. Awesome! + +There can still be uninterned strings that are 6 bytes or shorter, and +calling intern on them would return the canonical, immediate version. + +### Unicode code points + +This is an easy one. We have 48 bits, and only need 21. Just write the +Unicode code point into the payload: done. + +This value range may be split in the future to fit other things in it, as +we've wasted a ton of bits here. + +### Singletons + +This 48-bit value range contains various singletons like Boolean values, the +empty list aka null, and so on. + +This is even more wasteful than using 48 bits for Unicode, so again this +value range may be partitioned further at some point. + +### Undefined ranges + +We have a whole 48-bit value range (sans one forbidden value) that's still +unused, plus another 50-bit range (or two 49-bit ranges, or three 48-bit). + +It's incredible just how much stuff you can cram into a NaN. I would have +never thought it possible. -WIP +Ours may just be the most sophisticated NaN-packing strategy ever devised, +because I couldn't find any information on the web about the possibility of +using both signaling and quiet NaNs. All articles I've stumbled upon either +claim that you must avoid signaling NaNs or quiet NaNs, or they take a naive +approach to the subdivision of the available bit patterns and end up wasting +tons of bit real estate. +Stay tuned for the development of Zisp, because this is getting serious! <!-- ;; Local Variables: diff --git a/src/libzisp.zig b/src/libzisp.zig new file mode 100644 index 0000000..542b84c --- /dev/null +++ b/src/libzisp.zig @@ -0,0 +1,51 @@ +//! By convention, root.zig is the root source file when making a library. If +//! you are making an executable, the convention is to delete this file and +//! start with main.zig instead. +const std = @import("std"); +const builtin = @import("builtin"); +const testing = std.testing; + +const value = @import("libzisp/value.zig"); + +test "double" { + const d1: f64 = 0.123456789; + const d2: f64 = -0.987654321; + const v1 = value.double.pack(d1); + const v2 = value.double.pack(d2); + const v3 = value.double.add(v1, v2); + const result = value.double.unpack(v3); + + try std.testing.expect(value.double.check(v1)); + try std.testing.expect(value.double.check(v2)); + try std.testing.expect(value.double.check(v3)); + try std.testing.expect(result == d1 + d2); +} + +test "fixnum" { + const int1: i64 = 123456789; + const int2: i64 = -987654321; + const v1 = value.fixnum.pack(int1); + const v2 = value.fixnum.pack(int2); + const v3 = value.fixnum.add(v1, v2); + const result = value.fixnum.unpack(v3); + + try std.testing.expect(value.fixnum.check(v1)); + try std.testing.expect(value.fixnum.check(v2)); + try std.testing.expect(value.fixnum.check(v3)); + try std.testing.expect(result == int1 + int2); +} + +test "ptr" { + const ptr1 = value.ptr.pack(@ptrFromInt(256), value.ptr.Tag.string); + try std.testing.expect(value.ptr.check(ptr1)); + try std.testing.expect(value.ptr.checkZisp(ptr1)); + try std.testing.expect(value.ptr.checkNormal(ptr1)); + + const ptr2 = value.ptr.makeWeak(ptr1); + try std.testing.expect(value.ptr.check(ptr2)); + try std.testing.expect(value.ptr.checkZisp(ptr2)); + try std.testing.expect(value.ptr.checkWeak(ptr2)); + + // Make sure ptr1 wasn't modified + try std.testing.expect(value.ptr.checkNormal(ptr1)); +} diff --git a/src/libzisp/value.zig b/src/libzisp/value.zig new file mode 100644 index 0000000..62807be --- /dev/null +++ b/src/libzisp/value.zig @@ -0,0 +1,221 @@ +// +// Here's a summary of our packing strategy. +// +// Format of a double, in Zig least-to-most significant field order: +// +// { sign: u1, exponent: u11, fraction: u52 } +// +// When the exponent bits are all set, it's either a NaN or an Infinity. +// +// For value packing, almost all remaining 53 bits are available, giving us +// about 2^53 values, except for the four following bit patterns: +// +// *** FORBIDDEN VALUES *** +// +// 1. Negative cqNaN = { sign = 1, exponent = max, fraction = 2^51 } +// +// 2. Negative Infinity = { sign = 1, exponent = max, fraction = 0 } +// +// 3. Positive cqNaN = { sign = 0, exponent = max, fraction = 2^51 } +// +// 4. Positive Infinity = { sign = 0, exponent = max, fraction = 0 } +// +// The abbreviation "cqNaN" stands for canonical quiet NaN. +// +// Note that 2^51 means the MSb of the 52 fraction bits being set, and the rest +// being zero. Th fraction MSb is also called the is_quiet flag, because it +// demarcates quiet NaNs. The rest being zero makes it the canonical qNaN. +// +// The positive and negative cqNaN are the *only* NaN values that can actually +// be returned by any FP operations, which is why we don't use them to pack +// values; we want to be able to represent NaN in Zisp as a double. +// +// Beyond those four bit patterns, all values with a maximum exponent (all bits +// set) are fair game for representing other values, so 2^53 - 4 possibilities. +// +// We split those 2^53 - 4 available values into four groups, each allowing for +// 2^51 - 1 different values to be encoded in them: +// +// sign = 1, quiet = 1 :: Negative Fixnum from -1 to -2^51+1 +// +// sign = 1, quiet = 0 :: Positive Fixnum from 0 to 2^51-2 +// +// sign = 0, quiet = 1 :: Pointers +// +// sign = 0, quiet = 0 :: Others +// +// +// === Fixnums === +// +// Negative fixnums actually represent themselves without needing to go through +// any transformation. Only the smallest 52-bit signed negative, -2^51, cannot +// be represented, as it would step on forbidden value 1, Negative cqNaN. +// +// Positive fixnums go through bitsiwe NOT (implemented via an XOR mask here to +// make it one operation together with the NaN masking) to avoid the all-zero +// payload value, which would step on forbidden value 2, Negative Infinity. +// +// +// === Pointers === +// +// Pointers are further subdivided as follows based on the remaining 51 bits: +// +// MSb = 1 :: Foreign Pointer (or a "special 50-bit fixnum") +// +// MSb = 0, SSb = 0 :: Pointer to heap object (string, vector, etc.) +// +// MSb = 0, SSb = 1 :: Weak pointer to heap object +// +// (SSb = Second-most significant bit) +// +// This means regular pointers to the Zisp heap are 49 bits. Of these, we only +// really need 45, since 64-bit platforms are in practice limited to 48-bit +// addresses, and allocations happen at 8-byte boundaries, meaning the least +// significant 3 bit are always 0. Thus, we are able to store 4-bit tags in +// those 49-bit pointers alongside the actual, multiple-of-8, 48-bit address. +// +// Note that foreign pointers avoid stepping on any forbidden value, thanks to +// bit 51 being set. +// +// The forbidden value 3, Positive cqNaN, is avoided thanks to the fact that a +// regular Zisp heap pointer can never be null. Weak pointers, which can be +// null, avoid stepping on that forbidden value thanks to bit 50 being set. +// +// +// === Other values === +// +// This 51-bit range is divided as follows, based on the initial bits: +// +// 000 :: Undefined +// +// 001 :: Small string +// +// 010 :: Unicode code point +// +// 011 :: Singleton values +// +// 1.. :: Undefined +// +// Zisp strings are immutable and always encoded in UTF-8. Any string fitting +// into 6 bytes or less will be stored as an immediate value, not requiring any +// heap allocation or interning. (It's implicitly interned.) +// +// There may still be uninterned strings on the heap that are just as short. +// Calling intern on them will return the equivalent small string. +// +// Unicode code points need a maximum of 21 bits, yet we have 48 available. +// This may be exploited for a future extension. +// +// Similarly, it's extremely unlikely that we will ever need more than a few +// dozen singleton values (false, true, null, and so on). As such, this range +// of bit patterns may be subdivided further in the future. +// +// And on top of all that we still have two 50-bit ranges left! +// +// The forbidden value 4, Positive Infinity, is in one of the two undefined +// value ranges. +// + +// Here's the original article explaining the strategy: +// +// https://tkammer.de/zisp/notes/nan.html +// +// Note: Packed structs are least-to-most significant, so the order of fields +// must be reversed relative to a typical big-endian illustration of the bit +// patterns of IEEE 754 double-precision floating point numbers. + +const std = @import("std"); + +pub const double = @import("value/double.zig"); +pub const fixnum = @import("value/fixnum.zig"); + +pub const ptr = @import("value/ptr.zig"); + +pub const sstr = @import("value/sstr.zig"); +pub const char = @import("value/char.zig"); +pub const misc = @import("value/misc.zig"); +pub const boole = @import("value/boole.zig"); + +/// To fill up the u11 exponent part of a NaN. +const FILL = 0x7ff; + +/// Represents a Zisp value/object. +pub const Value = packed union { + double: f64, + + nan: packed struct { + rest: u51, + quiet: u1, + exp: u11 = FILL, + sign: u1, + }, + + fixnum: packed struct { + code: u51, + negative: bool, + _: u11 = FILL, + is_fixnum: bool = true, + }, + + ptr: packed struct { + // if foreign, we don't actually use value and is_weak + value: u49, + weak: bool = false, + foreign: bool = false, + is_ptr: bool = true, + _: u11 = FILL, + _fixnum: bool = false, + }, + + fptr: packed struct { + value: u50, + _foreign: bool = true, + _ptr: bool = true, + _: u11 = FILL, + _fixnum: bool = false, + }, + + sstr: packed struct { + // packed struct cannot contain array + value: u48, + tag: Tag = .str, + ptr: bool = false, + _: u11 = FILL, + fixnum: bool = false, + }, + + char: packed struct { + value: u48, + tag: u3 = 2, + ptr: bool = false, + _: u11 = FILL, + fixnum: bool = false, + }, + + misc: packed struct { + value: u48, + tag: u3 = 3, + ptr: bool = false, + _: u11 = FILL, + fixnum: bool = false, + }, + + const Tag = enum(u3) { str = 1, char = 2, misc = 3 }; + + const Self = @This(); + + /// Hexdumps the value. + pub fn dump(self: Self) void { + std.debug.dumpHex(std.mem.asBytes(&self)); + } + + /// Checks for any IEEE 754 NaN. + pub fn isNan(self: Self) bool { + return self.nan.exp == FILL; + } + + /// Checks for a Zisp value (non-double) packed into a NaN. + pub fn isPacked(self: Self) bool { + return self.isNan() and self.nan.rest != 0; + } +}; diff --git a/src/libzisp/value/boole.zig b/src/libzisp/value/boole.zig new file mode 100644 index 0000000..d4fbd28 --- /dev/null +++ b/src/libzisp/value/boole.zig @@ -0,0 +1,10 @@ +const Value = @import("../value.zig").Value; +const misc = @import("misc.zig"); + +// These can be accessed from either namespace. +pub const f = misc.f; +pub const t = misc.t; + +pub fn pack(b: bool) Value { + return if (b) f else t; +} diff --git a/src/libzisp/value/char.zig b/src/libzisp/value/char.zig new file mode 100644 index 0000000..7034128 --- /dev/null +++ b/src/libzisp/value/char.zig @@ -0,0 +1,24 @@ +const Value = @import("../value.zig").Value; + +pub fn check(v: Value) bool { + return v.isPacked() and + !v.char.fixnum and + !v.char.ptr and + v.char.tag == .char; +} + +pub fn assert(v: Value) void { + if (!check(v)) { + v.dump(); + @panic("not char"); + } +} + +pub fn pack(c: u21) Value { + return .{ .char = .{c} }; +} + +pub fn unpack(v: Value) u21 { + assert(v); + return v.char.value; +} diff --git a/src/libzisp/value/double.zig b/src/libzisp/value/double.zig new file mode 100644 index 0000000..5c98324 --- /dev/null +++ b/src/libzisp/value/double.zig @@ -0,0 +1,37 @@ +const Value = @import("../value.zig").Value; + +// Zig API + +/// Checks for a Zisp double (double, +inf, -inf, or canonical NaN). +pub fn check(v: Value) bool { + return !v.isPacked(); +} + +/// Asserts check(). +pub fn assert(v: Value) void { + if (!check(v)) { + v.dump(); + @panic("not double"); + } +} + +pub fn pack(d: f64) Value { + return .{ .double = d }; +} + +pub fn unpack(v: Value) f64 { + assert(v); + return v.double; +} + +// Zisp API + +pub fn pred(v: Value) Value { + return Value.boole.pack(check(v)); +} + +pub fn add(v1: Value, v2: Value) Value { + const d1 = unpack(v1); + const d2 = unpack(v2); + return pack(d1 + d2); +} diff --git a/src/libzisp/value/fixnum.zig b/src/libzisp/value/fixnum.zig new file mode 100644 index 0000000..60b4239 --- /dev/null +++ b/src/libzisp/value/fixnum.zig @@ -0,0 +1,87 @@ +const std = @import("std"); + +const Value = @import("../value.zig").Value; + +// Zig API + +/// Checks for a Zisp fixnum. +pub fn check(v: Value) bool { + return v.isPacked() and v.fixnum.is_fixnum; +} + +/// Asserts check(). +pub fn assert(v: Value) void { + if (!check(v)) { + v.dump(); + @panic("not fixnum"); + } +} + +// See detailed NaN packing docs for why the +/- 1. +const fixnum_min = std.math.minInt(i52) + 1; +const fixnum_max = std.math.maxInt(i52) - 1; + +fn isValidRange(int: i64) bool { + return fixnum_min < int and int < fixnum_max; +} + +fn assertValidRange(int: i64) void { + if (int < fixnum_min) { + std.debug.print("int too small for fixnum: {}", .{int}); + @panic("int too small for fixnum"); + } + if (int > fixnum_max) { + std.debug.print("int too large for fixnum: {}", .{int}); + @panic("int too large for fixnum"); + } +} + +fn packNegative(int: i64) Value { + return @bitCast(int); +} + +fn unpackNegative(v: Value) i64 { + return @bitCast(v); +} + +const positive_mask: u64 = 0xfff7ffffffffffff; + +fn packPositive(int: i64) Value { + const uint: u64 = @bitCast(int); + return @bitCast(uint ^ positive_mask); +} + +fn unpackPositive(v: Value) i64 { + const uint: u64 = @bitCast(v); + return @bitCast(uint ^ positive_mask); +} + +pub fn pack(int: i64) Value { + assertValidRange(int); + if (int < 0) { + return packNegative(int); + } else { + return packPositive(int); + } +} + +pub fn unpack(v: Value) i64 { + assert(v); + if (v.fixnum.negative) { + return unpackNegative(v); + } else { + return unpackPositive(v); + } +} + +// Zisp API + +pub fn pred(v: Value) Value { + return Value.boole.pack(check(v)); +} + +pub fn add(v1: Value, v2: Value) Value { + const int1 = unpack(v1); + const int2 = unpack(v2); + return pack(int1 + int2); +} diff --git a/src/libzisp/value/misc.zig b/src/libzisp/value/misc.zig new file mode 100644 index 0000000..2570644 --- /dev/null +++ b/src/libzisp/value/misc.zig @@ -0,0 +1,6 @@ +const Value = @import("../value.zig").Value; + +pub const f = Value{ .misc = .{0} }; +pub const t = Value{ .misc = .{1} }; +pub const nil = Value{ .misc = .{2} }; +pub const eof = Value{ .misc = .{3} }; diff --git a/src/libzisp/value/ptr.zig b/src/libzisp/value/ptr.zig new file mode 100644 index 0000000..4bf92b6 --- /dev/null +++ b/src/libzisp/value/ptr.zig @@ -0,0 +1,176 @@ +const std = @import("std"); + +const Value = @import("../value.zig").Value; + +// Zig API + +pub fn check(v: Value) bool { + return v.isPacked() and v.ptr.is_ptr; +} + +pub fn assert(v: Value) void { + if (!check(v)) { + v.dump(); + @panic("not a pointer"); + } +} + +// Foreign Pointers + +pub fn checkForeign(v: Value) bool { + return check(v) and v.ptr.foreign; +} + +pub fn assertForeign(v: Value) void { + if (!checkForeign(v)) { + v.dump(); + @panic("not foreign pointer"); + } +} + +pub fn packForeign(int: u50) Value { + return .{ .fptr = .{int} }; +} + +pub fn unpackForeign(v: Value) u64 { + assertForeign(v); + return v.ptr.value.foreign; +} + +// Zisp Pointers + +pub fn checkZisp(v: Value) bool { + return check(v) and !v.ptr.foreign; +} + +pub fn assertZisp(v: Value) void { + if (!checkZisp(v)) { + v.dump(); + @panic("not zisp pointer"); + } +} + +pub fn checkWeak(v: Value) bool { + return checkZisp(v) and v.ptr.weak; +} + +pub fn assertWeak(v: Value) void { + if (!checkWeak(v)) { + v.dump(); + @panic("not weak zisp pointer"); + } +} + +pub fn checkNormal(v: Value) bool { + return checkZisp(v) and !v.ptr.weak; +} + +pub fn assertNormal(v: Value) void { + if (!checkNormal(v)) { + v.dump(); + @panic("not normal zisp pointer"); + } +} + +pub fn packZisp(ptr: *anyopaque, tag: Tag, weak: bool) Value { + return .{ .ptr = .{ + .value = tagPtr(ptr, tag), + .weak = weak, + } }; +} + +pub fn pack(ptr: *anyopaque, tag: Tag) Value { + return packZisp(ptr, tag, false); +} + +pub fn packWeak(ptr: *anyopaque, tag: Tag) Value { + return packZisp(ptr, tag, true); +} + +// Unpacks weak as well; no need for a separate fn. +pub fn unpack(v: Value) struct { ptr: *anyopaque, tag: Tag } { + assertZisp(v); + return untagPtr(v.ptr.value.tagged); +} + +// Weak pointers may be null. +pub fn isNull(v: Value) bool { + assertWeak(v); + const ptr, _ = untagPtr(v.ptr.value.tagged); + return @intFromPtr(ptr) == 0; +} + +pub fn tagPtr(ptr: *anyopaque, tag: Tag) u49 { + const int: u64 = @intFromPtr(ptr); + const untagged: u49 = @truncate(int); + return untagged << 1 | @intFromEnum(tag); +} + +pub fn untagPtr(tagged: 49) struct { ptr: *anyopaque, tag: Tag } { + const untagged: u49 = tagged >> 1 & 0xfffffffffff0; + const ptr: *anyopaque = @ptrFromInt(untagged); + const int: u4 = @truncate(tagged); + const tag: Tag = @enumFromInt(int); + return .{ .ptr = ptr, .tag = tag }; +} + +pub const Tag = enum(u4) { + /// 1. Strings / Symbols + string, + /// 2. Bignums / Ratnums + number, + /// 3. Pairs ([2]Value) + pair, + /// 4. Vector, bytevector, etc. + array, + /// 5. Ordered hash table + table, + /// 6. String buffer + text, + /// 7. Class, interface, etc. + role, + /// 8. Instance, basically + actor, + /// 9. I/O Port + port, + /// 10. Procedure + proc, + /// 11. Continuation + cont, + /// Other + other = 15, +}; + +// Zisp API + +pub fn predForeign(v: Value) Value { + return Value.boole.pack(checkForeign(v)); +} + +pub fn makeWeak(v: Value) Value { + assertNormal(v); + var copy = v; + copy.ptr.weak = true; + return copy; +} + +pub fn predWeak(v: Value) Value { + const isWeak = checkWeak(v); + return Value.boole.pack(isWeak); +} + +pub fn predWeakNull(v: Value) Value { + assertWeak(v); + return Value.boole.pack(v.ptr.weak); +} + +pub fn getWeak(v: Value) Value { + assertWeak(v); + if (isNull(v)) { + return Value.boole.pack(false); + } else { + var copy = v; + copy.ptr.weak = false; + return copy; + } +} diff --git a/src/libzisp/value/sstr.zig b/src/libzisp/value/sstr.zig new file mode 100644 index 0000000..3c0755d --- /dev/null +++ b/src/libzisp/value/sstr.zig @@ -0,0 +1,3 @@ +const Value = @import("../value.zig").Value; + +// stub diff --git a/src/main.zig b/src/main.zig index d40f09a..c9a5404 100644 --- a/src/main.zig +++ b/src/main.zig @@ -69,5 +69,3 @@ test "fuzz example" { }; try std.testing.fuzz(Context{}, Context.testOne, .{}); } - -test "nan" {} diff --git a/src/root.zig b/src/root.zig deleted file mode 100644 index 05ad381..0000000 --- a/src/root.zig +++ /dev/null @@ -1,191 +0,0 @@ -//! By convention, root.zig is the root source file when making a library. If -//! you are making an executable, the convention is to delete this file and -//! start with main.zig instead. -const std = @import("std"); -const builtin = @import("builtin"); -const testing = std.testing; - -// Read the following article to understand the NaN-packing strategy: -// -// https://tkammer.de/zisp/notes/nan.html -// -// Note: Packed structs are least-to-most significant, so the order of fields -// must be reversed relative to a typical big-endian illustration of the bit -// patterns of IEEE 754 double-precision floating point numbers. - -const Value = packed union { - double: f64, - nan: packed struct { - rest: u51, - quiet: u1, - exp: u11, - sign: u1, - }, - int: packed struct { - code: u51, - neg: bool, - exp: u11, - is_int: bool, - }, - pointer: packed struct { - value: u48, - type: u3, - _zo: u1, - _qnan: u12, - }, -}; - -// Helpers - -inline fn zisp_dump(v: Value) void { - std.debug.dumpHex(std.mem.asBytes(&v)); -} - -///! Checks for any IEEE 754 NaN. -inline fn zisp_is_nan(v: Value) bool { - return v.nan.exp == std.math.maxInt(u11); -} - -///! Checks for a Zisp value packed into a NaN. -inline fn zisp_is_packed(v: Value) bool { - return zisp_is_nan(v) and v.nan.rest != 0; -} - -///! Checks for a regular double including infinity or canonical NaN -inline fn zisp_is_double(v: Value) bool { - return !zisp_is_packed(v); -} - -inline fn zisp_assert_double(v: Value) void { - if (!zisp_is_double(v)) { - zisp_dump(v); - @panic("not double"); - } -} - -inline fn zisp_is_int(v: Value) bool { - return zisp_is_packed(v) and v.int.is_int; -} - -inline fn zisp_assert_int(v: Value) void { - if (!zisp_is_int(v)) { - zisp_dump(v); - @panic("not int"); - } -} - -// See detailed NaN packing docs for why the +/- 1. -const zisp_int_min = std.math.minInt(i52) + 1; -const zisp_int_max = std.math.maxInt(i52) - 1; - -inline fn zisp_assert_int_range(int: i64) void { - if (int < zisp_int_min) { - std.debug.print("int to pack is too small: {}", .{int}); - @panic("int to pack is too small"); - } - if (int > zisp_int_max) { - std.debug.print("int to pack is too large: {}", .{int}); - @panic("int to pack is too large"); - } -} - -inline fn zisp_int_pack_neg(int: i64) Value { - return @bitCast(int); -} - -inline fn zisp_int_unpack_neg(v: Value) i64 { - return @bitCast(v); -} - -const zisp_int_pos_mask: u64 = 0xfff7ffffffffffff; - -inline fn zisp_int_pack_pos(int: i64) Value { - const uint: u64 = @bitCast(int); - return @bitCast(uint ^ zisp_int_pos_mask); -} - -inline fn zisp_int_unpack_pos(v: Value) i64 { - const uint: u64 = @bitCast(v); - return @bitCast(uint ^ zisp_int_pos_mask); -} - -inline fn zisp_int_pack(int: i64) Value { - zisp_assert_int_range(int); - if (int < 0) { - return zisp_int_pack_neg(int); - } else { - return zisp_int_pack_pos(int); - } -} - -inline fn zisp_int_unpack(v: Value) i64 { - zisp_assert_int(v); - if (v.int.neg) { - return zisp_int_unpack_neg(v); - } else { - return zisp_int_unpack_pos(v); - } -} - -// Doubles - -pub fn zisp_double(d: f64) Value { - return @bitCast(d); -} - -// pub fn zisp_double_p(v: Value) Value { -// return zisp_bool(zisp_is_double(v)); -// } - -pub fn zisp_double_get(v: Value) f64 { - zisp_assert_double(v); - return v.double; -} - -pub fn zisp_double_add(v1: Value, v2: Value) Value { - const d1 = zisp_double_get(v1); - const d2 = zisp_double_get(v2); - return zisp_double(d1 + d2); -} - -// Ints - -pub fn zisp_int(int: i64) Value { - return zisp_int_pack(int); -} - -// pub fn zisp_int_p(v: Value) Value { -// return zisp_bool(zisp_is_int(v)); -// } - -pub fn zisp_int_get(v: Value) i64 { - return zisp_int_unpack(v); -} - -pub fn zisp_int_add(v1: Value, v2: Value) Value { - const int1 = zisp_int_get(v1); - const int2 = zisp_int_get(v2); - return zisp_int(int1 + int2); -} - -// Tests - -test "double add functionality" { - const d1: f64 = 0.123456789; - const d2: f64 = -0.987654321; - const v1 = zisp_double(d1); - const v2 = zisp_double(d2); - const v3 = zisp_double_add(v1, v2); - const result = zisp_double_get(v3); - try std.testing.expect(result == d1 + d2); -} - -test "int add functionality" { - const int1: i64 = 123456789; - const int2: i64 = -987654321; - const v1 = zisp_int(int1); - const v2 = zisp_int(int2); - const v3 = zisp_int_add(v1, v2); - const result = zisp_int_get(v3); - try std.testing.expect(result == int1 + int2); -} |