diff options
| author | Taylan Kammer <taylan.kammer@gmail.com> | 2025-02-10 20:20:26 +0100 |
|---|---|---|
| committer | Taylan Kammer <taylan.kammer@gmail.com> | 2025-02-15 18:38:28 +0100 |
| commit | dd3d8f9d768479df36e51d402adf55afad1aff07 (patch) | |
| tree | 21b11a361ca080a2d130f33fe435b4ac284731be /html | |
| parent | 831dc694c404826e9a1bf07788e10b9ac3d9cb2d (diff) | |
update
Diffstat (limited to 'html')
| -rwxr-xr-x | html/gen.sh | 25 | ||||
| -rw-r--r-- | html/index.md | 24 | ||||
| -rw-r--r-- | html/notes/booleans.md | 32 | ||||
| -rw-r--r-- | html/notes/compilation.md | 115 | ||||
| -rw-r--r-- | html/notes/cons.md | 178 | ||||
| -rw-r--r-- | html/notes/equal.md | 255 | ||||
| -rw-r--r-- | html/notes/immutable.md | 56 | ||||
| -rw-r--r-- | html/notes/let.md | 41 | ||||
| -rw-r--r-- | html/notes/nan.md | 384 | ||||
| -rw-r--r-- | html/notes/oop.md | 3 | ||||
| -rw-r--r-- | html/notes/records.md | 54 | ||||
| -rw-r--r-- | html/notes/serialize.md | 67 | ||||
| -rw-r--r-- | html/notes/strict-mode.md | 16 | ||||
| -rw-r--r-- | html/notes/sugar.md | 85 | ||||
| -rw-r--r-- | html/notes/symbols.md | 19 | ||||
| -rw-r--r-- | html/notes/zero-values.md | 11 | ||||
| -rw-r--r-- | html/prelude.html | 13 | ||||
| -rw-r--r-- | html/style.css | 23 |
18 files changed, 1401 insertions, 0 deletions
diff --git a/html/gen.sh b/html/gen.sh new file mode 100755 index 0000000..d14286e --- /dev/null +++ b/html/gen.sh @@ -0,0 +1,25 @@ +#!/bin/bash + +set -euo pipefail + +if [ $# -eq 0 ] +then + exec find . -name \*.md -exec "$0" {} + +fi + +for file +do + if ! [ -f "$file" ] + then + echo >&2 "File not found: $file" + continue + fi + echo "$file" + { + title=$(sed '/^# / { s/# //; q }' "$file") + sed "s/__TITLE__/$title/" prelude.html + echo "<body>" + markdown2 "$file" -x fenced-code-blocks,highlightjs-lang + echo "</body>" + } > "${file%.md}".html +done diff --git a/html/index.md b/html/index.md new file mode 100644 index 0000000..e369e56 --- /dev/null +++ b/html/index.md @@ -0,0 +1,24 @@ +# Zisp: 21st-century Scheme-inspired language + +Zisp is my experimental toy language inspired by Scheme. The idea is +that it's a modern "re-imagining" of what Scheme may have been had it +been invented today, and had it been designed with pragmatic use as a +primary concern in its design. + +This language doesn't actually exist yet. You are merely reading the +ramblings of a madman. + +* [Compilation is execution](notes/compilation.html) +* [Everything can be serialized](notes/serialize.html) +* [Symbols are strings](notes/symbols.html) +* [Stop the "cons" madness!](notes/cons.html) +* [A little bit of syntax sugar never hurt anyone](notes/sugar.html) +* [More immutability](notes/immutable.html) +* [No shadowing, and fewer `let` forms](notes/let.html) +* [Return zero values](notes/zero-values.html) +* [Strict mode: Can't ignore returned values](notes/strict-mode.html) +* [Only Booleans have truthiness](notes/booleans.html) +* [Record types](notes/records.html) +* [Object-oriented programming](notes/oop.html) +* [Equality and equivalence semantics](notes/equal.html) +* [NaN-packing](notes/nan.html) diff --git a/html/notes/booleans.md b/html/notes/booleans.md new file mode 100644 index 0000000..61b9d7e --- /dev/null +++ b/html/notes/booleans.md @@ -0,0 +1,32 @@ +# Only Booleans have truthiness + +Like in Java, there should be no implicit conversion of values to a +Boolean. This leads to sloppy code and subtle bugs. + +I believe the code base of Guix contained an example of this at some +point: Build phases ending in a call to `system*` would return 0 or 1 +which would pass as "true" regardless. + +In most cases, you should know the actual type of the value you're +receiving, and do an appropriate check, be it `zero?`, `null?`, or +some other check. If you truly want to check if something is "any +value other than false" then you can always do: + +```scheme + +(if (not (eq? #f value)) + (do something)) + +``` + +No, you cannot use `(not (not x))` because `not` obviously expects a +Boolean argument! Duh. + +I'm actually serious about this. Scheme went all the way to make null +separate from false, but then refused to go all the way and decided to +allow non-Boolean values to function as Booleans anyway. + +Of course, performing a type-check on every single conditional may +incur a serious performance penalty. If so, then the same flag that +determines [whether returned values can be ignored](strict-mode.html) +may also determine whether non-Booleans can be coerced into Booleans. diff --git a/html/notes/compilation.md b/html/notes/compilation.md new file mode 100644 index 0000000..4d5fc6d --- /dev/null +++ b/html/notes/compilation.md @@ -0,0 +1,115 @@ +# Compilation is execution + +Any Scheme implementation with support for procedural macros allows +arbitrary code execution at compile-time. However, this is slightly +awkward: + +```scheme + +(define-syntax comptime + (lambda (stx) + (syntax-case stx () + ((_) + (begin + (display "foo\n"))))) + +(comptime) + +``` + +Compiling this with, for example, `guild compile foo.scm` will lead to +the line "foo" being printed. (The actual program is a no-op and will +do nothing when run after compiled.) + +One can of course implement a macro such as `eval-when-compile` to +make this slightly less awkward. Using R6RS: + +```scheme + +(import (rnrs eval)) + +(define-syntax eval-when-compile + (lambda (stx) + (syntax-case stx () + ((_ imports body ...) + (eval + (syntax->datum #'(begin body ...)) + (apply environment (syntax->datum #'imports))))))) + +(eval-when-compile + ((rnrs)) + (display "foo\n")) + +``` + +An implementation may of course contain such a macro in its standard +library, but it's unclear why the language should put such a hurdle in +our way. There are problems beyond this little hurdle as well. + +Top-level forms in Scheme are semantically executed at run-time, not +compile-time. + +(Actually, the Scheme standards don't explicitly define a run-time or +compile-time stage, but it's arguably implicit in the fact that macros +are *not* first-class, and are defined by the language in such a way +that they can be executed entirely at compile-time if ahead-of-time +compilation is supported by an implementation.) + +Consider the case where the programmer wants to perform a relatively +costly calculation at compile-time and store the result as part of the +compiled program. Say, a lookup-table. Naively, we may attempt the +following: + +```scheme + +;; The fictional file `lookup-table.dat` would be in the source code +;; repository, and the fictional procedure `process-data` would read +;; it and return a data structure. +(define lookup-table (process-data "lookup-table.dat")) + +``` + +This will not work. Compiling a Scheme file containing such a form +will produce a program that calls `process-data` at run-time and not +at compile-time as intended. + +One can of course resolve this with an explicit use of a procedural +macro. In fact, all one needs to do is redefine `process-data` as a +macro, but I find this to be an unnecessary complication. + +Further, any sufficiently intelligent implementation *will* actually +execute such top-level definitions at compile-time, given that they +only make use of compile-time constants and pure functions. + +```scheme + +;; Guile will compute the value at compile-time. +(define seconds-per-day (number->string (* 24 60 60))) + +``` + +This is easily observed by running `guild compile test.scm -o test.go` +and then `strings test.go` which will contain the string 86400 in its +output. (If we didn't use `number->string`, it would be harder to +locate the number 86400 in the output, since it would be binary.) + +This works because Guile implements the "partial evaluation" strategy +for program optimization. This requires the optimizer to know which +procedures are pure. A limitation in the implementation may lead to +some such opportunities to be missed, and for the compiled program to +execute unnecessary code at run-time. + +To recap: The top-level of a Scheme file is conceptually executed at +run-time. But an optimizer may execute some of it at compile-time +anyway. However, we're at the mercy of the implementation quality for +this to happen consistently. We can use procedural macros to force +some execution to definitely happen at compile-time. What a mess! + +It would be so much simpler if compiling a program meant, at the +language semantics level, that the top-level is executed. + +Any run-time initialization of a program or module should be explicit, +such as by putting it into a `main` function, or having the module +export an initialization function. (The language may, if I feel like +it, allow for declaring a module initializer function, which would be +invoked automatically when a module is loaded.) diff --git a/html/notes/cons.md b/html/notes/cons.md new file mode 100644 index 0000000..3f38519 --- /dev/null +++ b/html/notes/cons.md @@ -0,0 +1,178 @@ +# Stop the "cons" madness! + +Lists are neat, but they aren't the best representation for sequences +of fixed length. An array/vector is a better choice for this. + +R6RS already uses vectors in some places where a traditional lisper +may have expected to see lists. Namely, in the procedural layer of +record types, where the fields of a record type are represented by +vectors. Another example is `hashtable-keys` and `hashtable-entries` +which both return vectors. There may be more places in Scheme where +this makes sense. + +In the following, we discuss a better handling of rest-argument lists +and a change to `apply`. In short, rest arguments are not actually +lists anymore, but rather a special kind of identifier that refers to +multiple values. And `apply`, which becomes a special form, expects +its last argument not to be a list but rather an expression that may +evaluate to multiple values. + + +## Better handling of rest args + +Initially, I was thinking of using either immutable vectors, or +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 + +Let's first summarize the paper, and then see how we can adapt its +ideas for Zisp. + +Long story short, rest argumenst are received through a parameter list +such as `(arg1 ... argn & rest)` and the identifier `rest` is special +in that it can only be passed on to another procedure using the same +syntax. For example, to explicitly put the rest args into a list and +map over them: + +```scheme + +(define (map* proc & args) + (map proc (list & args))) + +(map* square 1 2 3) ;=> (1 4 9) + +``` + +Recursive functions that directly consume an arbitrary number of args, +without needing to allocate any data structure, can be implemented by +combining this feature with what is today known as `case-lambda`: + +```scheme + +(define combine* + (case-lambda + ((x) x) + ((x y & rest) (combine* (combine x y) & rest)) + +``` + +Though the paper proposes the use of `&` so as to differentiate it +from the regular rest-argument mechanism of Scheme, I intend to make +Zisp use only this mechanism, so we can use the dot notation for it. +Rewriting the above examples in this style gives us: + +```scheme + +(define (map* proc . args) + (map proc (list . args))) + +(define combine* + (case-lambda + ((x) x) + ((x y . rest) (combine* (combine x y) . rest)))) + +``` + +I find this very pleasing on the eyes, and a very elegant way to use +improper lists in evaluation context, which isn't allowed in Scheme. + + +## More ergonomic multiple-values + +The paper linked above proposes to reuse the rest args syntax for an +elegant solution to consuming multiple values: + +```scheme + +(proc x y & <expr>) + +``` + +In the above, `<expr>` may evaluate to multiple values, and the values +will be passed to `proc` as additional arguments. + +Essentially, this means that the special rest-arg identifier is itself +a representation of multiple values, or in other words, evaluating it +results in multiple values even though it's just an identifier! + +Demonstration, using Zisp notation for multiple-value rest args: + +```scheme + +(define (foobar . rest) + (let-values (((x y z) rest)) + ;; This is a meaningless example for demonstration, since we + ;; could have just made the function accept three parameters. + ;; The `let-values` here is the one from SRFI 11. + )) + +``` + +The paper also proposes terminating lambda bodies with `& <expr>` to +return multiple values, but this is obsolete as of R5RS, which allows +the final expression in a body to evaluate to multiple values anyway. + +However, the use of & to pass multiple values as arguments is very +convenient and much cleaner than R5RS's clumsy `call-with-values`: + +```scheme + +;; Returns {bool, obj} where bool indicates success/failure and obj +;; is meaningless if bool is false; allows differentiating between +;; the case where #f is found as the value vs. nothing being found. +(define (lookup alist key) + (if (null? alist) + (values #f #f) + (if (eqv? key (caar alist)) + (values #t (cdar alist)) + (lookup (cdr alist) key)))) + +(define (display-if-found found? obj) + (when found? (display obj))) + +;; Incredibly ugly `call-with-values`: +(call-with-values + (lambda () (lookup '((x . y)) 'x)) + display-if-found) + +;; (Up until here is valid R5RS code, by the way.) + +;; So much cleaner: +(display-if-found & (lookup '((x . y)) 'x)) ;; displays x + +``` + +Unfortunately, we can't reuse the improper list syntax in the last +example, since the following s-expressions are equivalent: + +```scheme + +(foo . (bar baz)) +(foo bar baz) + +``` + +In Zisp, this will be solved by making `apply` a special-form where +the last operand is expected to evaluate to multiple values rather +than a list: + +```scheme + +;; (apply <proc-expr> <argn-expr> ... <restargs-expr>) + +(apply display-if-found (lookup '((x . y)) 'x)) + +``` + +Note that this means the forms `(apply foo rest)` and `(foo . rest)` +are equivalent if `rest` is an identifier and not a pair/list, while +`(apply foo (x ...))` is of course different from `(foo x ...)`. + +I find this all incredibly pleasing. Lists never had any business in +representing arguments in the first place; it should always have been +multiple values! + +(The phrase "argument list" is probably going to stick around forever +though, even if it's technically wrong in Zisp.) diff --git a/html/notes/equal.md b/html/notes/equal.md new file mode 100644 index 0000000..8c55faa --- /dev/null +++ b/html/notes/equal.md @@ -0,0 +1,255 @@ +# A novel approach to object equivalence + +## Story time + +In my past 5 years of developing a warehouse management application, +I've frequently found myself implementing equality the following way. + +(Code massively reduced to get to the point. Implementations of the +`hashCode` method, which must be compatible with `equals`, have been +left out for brevity.) + +```java + +class Warehouse { + String code; + String name; + // ... more fields, many mutable + + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (obj instanceof Warehouse w) { + return code.equals(w.code); + } + return false; + } +} + +class Product { + int id; + LocalizedString name; + LocalizedString description; + // ... more fields, many mutable + + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (obj instanceof Product p) { + return id == p.id; + } + return false; + } +} + +``` + +And so on. A type may have a code that is a String, an id that is an +int, or some other field that uniquely identifies members of it within +our application domain. + +I'm speaking of types and their members, not classes and instances, +because I mean the application domain. The user of our program has a +number of warehouses and a number of products, in reality, which we +represent via these classes, but there may be multiple instances of a +class representing the same real entity. + +Oftentimes, there will be a database that contains unique entries for +these. For example, an SQL table for products where the id is the +primary key, and an SQL table for warehouses where the code is the +primary key. + +This way of implementing `equals()` and `hashCode()` may seem wrong to +some developers. Since the classes have mutable fields, we may end up +with two `Product` instances which are not equal in their state, yet +`equals()` returns true for them since they represent the same real +life entity, just with different state in our program. Perhaps one +has just been fetched from the database, whereas the other has been +modified to represent changes that are yet to be committed. + +I've never found this strategy to lead to any problems. Never have I +had a need to know whether two `Product` instances have the same state +right now. What I care about is which product is being represented. +This is useful in various ways. + +### Map keys, sets, and so on + +First of all, it allows us to create maps where the keys are instances +of Product or Warehouse. For example, the application may want to +create a map of which products each warehouse contains: + +```java + +Map<Warehouse, List<Product>> productsByWarehouse; + +``` + +Given the `equals()` implementation of the Warehouse class, this map +can now be given any instance of Warehouse as a key, and we need not +ensure that we have one canonical instance used as the key. + +There are of course many alternatives to this. One may not want this +map to keep Warehouse instances alive, in which case it would be more +sensible to use the codes (Strings) for the keys. One could also add +a field to Warehouse such as `List<Product> products;`. However, in +some circumstances, a map such as the above may be most natural. + +Other data structures and operations depend on equality checks as +well. For example: finding duplicates in a collection, checking +whether a collection already contains a given item, managing a set +data type, and so on. The way we implement equality is also useful +for such purposes. + +### Elegance and encapsulation + +Secondly, we may have subsystems in the application that communicate +by passing Product or Warehouse instances to each other. For example, +the user may be looking at a user interface displaying the products in +a warehouse with their current quantities. The user may then click on +an "update quantities" button which opens a sub-interface where it's +possible to add an arbitrary number of entries (products) with the +desired quantity change for each. This sub-interface may then return +a list of Product instances with the associated quantity change. The +code of the warehouse overview interface can now use `equals()` to +determine which instance of Product it received corresponds to which +Product instance it's already holding on to. + +Again, there are of course many alternative strategies which don't +require such a use of `equals()`. One may explicitly compare the id +fields, or the sub-interface may return ids associated with quantity +changes. However, the `equals()` based implementation may offer the +cleanest possible code: + +```java + +public void receiveQuantityChanges(Map<Product, Integer> changes) { + for (Row<Product> row : this.productRows) { + Integer change = changes.get(row.product); + row.quantity += change; + } +} + +``` + +As far as readability and elegance is concerned, this can hardly be +improved on, as far as one is familiar with Java. Although using a +`Map<Integer, Integer>` would hardly make the code any more verbose, +it immediately causes it to lose out on self-documentation: + +```java + +// Quantity changes of what? Should we rename this to the awfully +// long name receiveProductQuantityChanges to make it clear? +public void receiveQuantityChanges(Map<Integer, Integer> changes) { + for (Row<Product> row : this.productRows) { + Integer change = changes.get(row.product.id); + row.quantity += change; + } +} + +``` + +This is a minor change as far as readability is concerned, but it also +decreases encapsulation. The code needs to be aware that products are +represented uniquely by an id that is an integer, and changing this +implementation detail of the class may have far-reaching consequences +throughout the code base. + +The self-documenting property may not apply to a Scheme-based language +without static types, but it makes the encapsulation aspect all the +more significant, since we won't have a compiler or static analyzer +which immediately tells us about a change in the type of `id`. We +must hope that the field `id` has been removed and replaced with a +different one, not reusing the `id` identifier. (For example, this +would mean a procedure like `product-id` stops existing, so a static +analyzer or compiler can immediately warn us about its absence. Had +we reused the field but changed its type, we would have a very hard +time finding all the places in the code we now need to fix.) + +## Get to the point! + +I've explained all this to arrive at one simple conclusion: + +Perhaps it would be a good idea for a language to have a mechanism in +which compound types like records or classes can simply declare that +one of the defined fields is the "unique identifier" of the type. + +Imitating SRFI 9: + +```scheme + +(define-record-type <product> + (make-product id name description ...) + product? + (identity: id) ; <- see here + (id product-id) + (name product-name) + (description product-description) + ...) + +(define-record-type <warehouse> + (make-warehouse code name ...) + warehouse? + (identity: code) ; <- see here + (code warehouse-code) + (name warehouse-name) + ...) + +``` + +Now the million dollar question is whether it should be `equal?` that +makes use of this information, or `eqv?`, or both. + +Although `eqv?` is intended to approximate operational equivalence, +and should therefore not consider separate mutable objects to be the +same, it's not clear to me how useful this is on user-defined types. + +The rationale for defining `eqv?` in terms of operational equivalence +is that this allows implementing memoization. If a memoized function +depends on one of the mutable fields of a record, yet `eqv?` returns +true on separate instances with different state, then the function +will return an incorrect result. But I'm skeptical as to whether a +function like that would see much practical use. It seems to me like +a memoized function that is used to compute some property of an entity +in our application domain should probably depend only on immutable +properties of that object. + +Another way to look at `eqv?` is that it implements "mostly constant +time" equality. (Strictly speaking, it's a linear time operation on +numbers, assuming the implementation offers arbitrary-size numbers. +This rarely matters, as few programs make use of numbers larger than +what fits in a few dozen bytes.) Conversely, `equal?` is responsible +for deep equality testing, which is inherently linear time, though +record types were overlooked in its definition in R7RS-small. + +## "Why not neither?" + +(I'm coining this as a new meme, in contrast to "why not both?") + +I think I want Zisp to support the following: + +* `eq?`: As in Scheme, but maybe allowed to fail on procedures. +* `eqv?`: As in Scheme. +* `equiv?`: An even closer approximation of operational equivalence, + by diving into immutable compound data types that `eqv?` doesn't + handle due to trying to be constant-time. I believe this is the + same as `equal-always?` in Racket. +* `equal?`: As in Scheme, but also dives into records because why not? + +The reason `eq?` is allowed to fail on procedures is an optimization +strategy that duplicates/inlines procedures. (citation needed) + +And which one should make use of the `identity` field of user types? +Only `equiv?`, because the identity object may be a string or other +immutable but compound object. (Thinking back to my Java programs, +I've had an extremely common type that was identified by a pair of +integers, for example: document and line number. One can also +conceive of N-dimensional coordinates and other such examples.) + +We want `eqv?` to remain "pretty much constant time" with the only +exception being numbers, which seem highly unlikely to reach such a +large size that it would matter. Recursive data structures, and +uninterned strings, on the other hand, could become quite large and +costly to compare. diff --git a/html/notes/immutable.md b/html/notes/immutable.md new file mode 100644 index 0000000..78652e9 --- /dev/null +++ b/html/notes/immutable.md @@ -0,0 +1,56 @@ +# More immutability + +I see no reason to have mutable variables in the language. + +Usually, code is analyzed to distinguish between mutable and immutable +variables, because this aids in optimization. This means you end up +with two types of variables, and whether a variable is of one or the +other type is determined solely from how it's used. Ugly! + +An explicit box data structure can trivially replicate the features of +a mutable variable, so let's just use that instead. + +Our `set!` can assume a box when a plain identifier is used. But to +get the value, we call `get`. + +```scheme + +(let ((x (box 0))) + (while foo + (set! x (+ x 1))) + (get x)) + +``` + +I've not yet made up my mind on whether pairs should be immutable by +default, but they probably should. Strings, as also mentioned in +[symbols](symbols.html), will be immutable, since string constants +will be the same thing as symbols. + +## Late additions + +It now occurs to me that, if you want your explicitly boxed value to +not be heap-allocated, your compiler will need to analyze its use and +potentially unbox it. + +So, in terms of code analysis complexity, it may not actually make a +difference, but I still like the more explicit demarcation of mutable +variables. Perhaps the syntax and semantics could be changed to: + +```scheme + +(let ((x (mutable 0))) + (while foo + (set! x (+ x 1))) + x) + +``` + +This is different in that passing around `x` will not actually pass +around a box whose contents can be mutated; rather, it's a regular +variable like in Scheme, but mutable unlike normal Zisp variables. +The `mutable` identifier would be part of the `let` syntax and not +possible to use anywhere else. (Probably not even with `define`.) + +It's really just to make code more explicit and easier to grasp, +without any effects on compiler complexity, probably. diff --git a/html/notes/let.md b/html/notes/let.md new file mode 100644 index 0000000..4af41bd --- /dev/null +++ b/html/notes/let.md @@ -0,0 +1,41 @@ +# No shadowing (shock!) and a reduced set of `let` forms + +This may be shocking for Schemers but I believe shadowing variables is +evil. I've already written a bug once that would have been prevented +had it not been possible to shadow variables, and I don't even write +that much Scheme code. + +And let's face it: The presence of four different forms by the name of +`let`, `let*`, `letrec`, and `letrec*` is daunting when you're coming +from another language. Lack of shadowing allows us to reduce this +without losing out much functionality. + +In the absence of shadowing, `let` becomes nearly useless because you +can always use `letrec` to fulfill the same need; it's strictly more +powerful. (The only thing `let` can do that `letrec` can't, is to +refer to the previous binding of a variable before shadowing it.) + +Further, the value of vanilla `letrec` is dubious when `letrec*` is +strictly more powerful. So, in Zisp, `let` is the ultimate binding +form that does what `letrec*` does in Scheme. + +Except it does more! We haven't looked at the whole `let-values` +family yet. In Zisp, these are also merged into the ultimate `let`, +using the SRFI 71 syntax: + +```scheme + +(let ((a (one-value)) + (b c (two-values)) + ((values d e . rest) (arbitrary-values))) + (do-things)) + +``` + +You may be wondering whether it also supports the "let loop" syntax of +vanilla Scheme `let` and the answer is no, because I hate that syntax. +It has too high a risk of leading to absolute spaghetti code with no +clear indication as to how the loop variables are being updated. + +If you want to loop, use a dedicated looping syntax! Even `do` is +better than "let loop" shenanigans if you ask me. diff --git a/html/notes/nan.md b/html/notes/nan.md new file mode 100644 index 0000000..c56609c --- /dev/null +++ b/html/notes/nan.md @@ -0,0 +1,384 @@ +# NaN-Packing + +NaN-packing (also called NaN-boxing) is a strategy involving the use of NaN +bit patterns, that are otherwise unused, to store various values in them. + +In the implementation of a dynamically typed language, this can be used to +ensure that all types in the language can be represented by a single 64-bit +value, which is either a valid double, an actual NaN value, or one of the +other NaN bit patterns that represent some other type, potentially in the +form of a pointer to a heap object containing further data. + +This works because pointers only need 48 bits in practice, and the range of +unused NaN bit patterns contains an astounding `2^53 - 4` different values. + +IMPORTANT NOTE: All illustrations of data structures and bit patterns use +big-endian. When implementing the strategies described herein, it may be +necessary to reorder the elements. For example, the elements of packed +structs in Zig are ordered least to most significant. + + +## The double format + +The IEEE 754 double-precision binary floating-point aka binary64 format is: + + { sign: u1, exponent: u11, fraction: u52 } + +Possible types of values a double can encode include: + + { sign == any, exponent != 0x7ff, fraction == any } :: Real (finite) + { sign == any, exponent == 0x7ff, fraction == 0x0 } :: Infinity + { sign == any, exponent == 0x7ff, fraction != 0x0 } :: NaN + +Note: + + 0x7ff = u11 with all bits set (0b11111111111) + +In other words: + + all exponent bits set, fraction bits all zero :: Infinity + all exponent bits set, fraction part non-zero :: NaN + + +## Details of NaN values + +There are two different NaN types: signaling and quiet. Quiet NaN may be +returned by FP operations to denote invalid results, whereas signaling NaN +are never returned by FP operations and serve other purposes. + +Modern hardware sets the MSB of the fraction to indicate that the NaN is a +quiet one, so let's refine our definition for denoting NaN values: + + { sign: u1, exp: u11, quiet: u1, rest: u51 } + +Variants of NaN: + + { sign == any, exp == 0x7ff, quiet == 0, rest >= 0x1 } :: sNaN + { sign == any, exp == 0x7ff, quiet == 1, rest == any } :: qNaN + +Note that in case of the signaling NaN, the rest of the fraction must be +non-zero, since otherwise the entire fraction part would be zero and thus +denote an infinity rather than a NaN. + +Most systems have a "canonical" quiet NaN that they use: + + { sign == any, exp == 0x7ff, quiet == 1, rest == 0x0 } :: cqNaN + +The sign bit of the canonical quiet NaN is undefined and may differ from +operation to operation or depending on the platform. + +It's useful to see a few common examples expressed in hex: + + 0x7ff8000000000000 :: cqNaN, sign bit nil + 0xfff8000000000000 :: cqNaN, sign bit set + + 0x7ff8000000000001 :: smallest non-canon qNaN, sign bit nil + 0xfff8000000000001 :: smallest non-canon qNaN, sign bit set + + 0x7fffffffffffffff :: largest non-canon qNaN, sign bit nil + 0xffffffffffffffff :: largest non-canon qNaN, sign bit set + + 0x7ff0000000000001 :: smallest sNaN, sign bit nil + 0xfff0000000000001 :: smallest sNaN, sign bit set + + 0x7ff7ffffffffffff :: largest sNaN, sign bit nil + 0xfff7ffffffffffff :: largest sNaN, sign bit set + + +## Unused NaN bit patterns + +Let's start with the quiet NaN values. + +Theoretically, there only needs to be one canonical quiet NaN, so we would +have `2^52 - 1` unused bit patterns in the quiet NaN range. In practice, +however, the sign bit may differ from one operation to the next. + +For example, the fabs function may simply clear the sign of the argument, +without minding it being a NaN. In that case, if the platform's regular +canonical NaN is the one with the sign bit set, we would end up getting +another, "semi-canonical" quiet NaN bit pattern, with the sign bit nil. + +So, both variants of the canonical quiet NaN are in use. + +This leaves `2^52 - 2` definitely-unused quiet NaN bit patterns: + + { sign == any, exp == 0x7ff, quiet == 1, rest >= 0x1 } :: Unused qNaN + +Remember that signaling NaN are defined in a very similar way: + + { sign == any, exp == 0x7ff, quiet == 0, rest >= 0x1 } :: sNaN + +Since none of those can be returned by FP operations, they could all be seen +as unused, giving us another `2^52 - 2` bit patterns. + +In total, this gives us `2^53 - 4` definitely-unused NaN bit patterns. + + +## Representing Zisp values and pointers as unused NaN bit patterns + +Zisp wants to store two different things in unused NaN patterns: + +1. Pointers (to anything in principle) + +2. Non-double primitive aka "immediate" values + +It may seem intuitive to use signaling NaN for one, and quiet NaN for the +other. However, this would fragment our "payload" bits, since we would be +using the sign bit as its MSB and the remaining 51 bits of the fraction as +the rest of the payload. + +Further, we want to use as many bit patterns as possible for fixnums, so we +can have a nice large fixnum range. To this end, it would be nice if we +could, for example, use all bit patterns where the sign bit is set for our +representation of fixnums, and then the range of bit patterns with the sign +bit unset can be shared among the remaining values, and pointers. + +Then let's do exactly that, and use the sign as the first major distinction +between fixnums and other values, using it as a sort of `is_int` flag: + + { sign == 0x0, exp == 0x7ff, payload == ??? } :: Non-Fixnum + { sign == 0x1, exp == 0x7ff, payload == ??? } :: Fixnum + +It will become apparent in a moment why we haven't defined the payload yet. + +Given that our payload is the entire fraction part of the IEEE 754 double +format, we must be careful not to use the following two payload values +regardless of the sign bit: + +1. Zero: This would make the bit pattern represent an infinity, since the +payload is the entire fraction and a zero fraction indicates infinity. + +2. `0x8000000000000` (aka only the MSB is set): This would make the bit +pattern a canonical quiet NaN, since the payload MSB is the quiet bit. + +This means that in each category (sign bit set, or nil) we have `2^52 - 2` +possible bit patterns, and the payload has a rather strange definition: + + 0x0 < payload < 0x8000000000000 < payload < 0xfffffffffffff + +Can we really fit a continuous range of fixnum values into that payload +without significantly complicating things? Yes, we can! Observe. + + +## Fixnum representation + +We will store positive and negative fixnums as separate value ranges, using +the quiet bit to differentiate between them. + +Let's go back to considering the quiet bit a separate field: + + { sign == 0x1, exp == 0x7ff, quiet == 0x0, rest >= 0x1 } :: Positive + { 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 +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 +then use an AND mask to unset the 13 highest: + + POS_INT_PACK(x) = ~x | 0xfff8000000000000 + + POS_INT_UNPACK(x) = ~x & 0x0007ffffffffffff + +If you've been paying very close attention, you may notice something: Given +that we know the 13 highest bits must always have a certain respective value +in the packed and unpacked representation (12 highest set when packed, none +set when unpacked), we can use an XOR to flip between the two, and the same +XOR can take care of flipping the remaining 51 bits at the same time! + +This also means packing and unpacking is the same operation: + + POS_INT_PACK(x) = x ^ 0xfff7ffffffffffff + + POS_INT_UNPACK(x) = x ^ 0xfff7ffffffffffff + +There we go; packing and unpacking 51-bit positive fixnums with one XOR! +Amazing, isn't it? + +As for the negative values, it's even simpler. This time, the correct NaN +starting pattern has all 13 bits set, since the quiet bit being set is what +we use to determine the number being negative. And would you believe it; +this means the packed negative fixnum already represents itself! + + NEG_INT_PACK(x) = x + + NEG_INT_UNPACK(x) = x + +Isn't that unbelievable? I need to verify this strategy further, but based +on all information I can find about NaN values, it should work just fine. + +The only disappointing thing is that it's positive integers that need an XOR +to pack and unpack, rather than negative ones. One would expect positive +values to occur much more frequently in typical code. But I think we can +live with a single XOR instruction! + + +## Pointers & Others + +We still want to represent the following, which must share space within the +`2^52 - 2` bit patterns that can be packed into an unsigned NaN: + +- Pointers of various kinds +- Unicode code points (21-bit values) +- False, true, null, end-of-file, and maybe a few more singletons + +It seems sensible to split this into two main categories: pointers and other +values. Let's use the quiet bit as a `pointer` flag: + + { sign == 0x0, exp == 0x7ff, quiet == 0x0, rest >= 0x1 } :: Other + { sign == 0x0, exp == 0x7ff, quiet == 0x1, rest >= 0x1 } :: Pointer + +Note how neither type is allowed to have a zero payload, since in case of an +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 + +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! +Since allocations happen at 8-byte boundaries on 64-bit machines, we only +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 + +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 +aligned. As it may point to anything, there's no point in defining further +bits as tagging additional information, so we have all 50 bits available. + +Let's cut out the 12 high bits of our double since we already know what they +must contain, and look at the definition of our 52-bit payload. + +I will also mix up the notation a bit, to indicate that some fields are only +defined if a previous field has a given value. + + { pointer == 0x1, foreign: u1, rest: u50 } + +(The `pointer` field is the `quiet` bit i.e. MSB of the 52-bit fraction.) + +If the foreign bit is set, then the entire `rest` field shall be seen as +opaque and may contain any value. Another way to look at this is that we +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 + +Now let's look at what we can do with "native" Zisp pointers. + +Wouldn't it be nice if our language had an explicit "pointer" data type and +it didn't require any additional heap allocation? So let's decide that one +bit is dedicated to distinguishing between an explicit pointer object, and +regular pointers that stand in for the object being pointed to. + +Perhaps it would be good to show some Zisp pseudo-code to explain what that +means, since it may be a strange concept: + + ;; In memory, vec is represented as a regular/direct vector pointer. + (define vec (vector 1 2 3)) + + ;; We can of course use this variable as a vector. + (vector? vec) ;=> #t + (vector-ref vec 0) ;=> 1 + + ;; Now we create an explicit pointer object pointing to that vector. + ;; Distinguished by a special bit in the in-memory value of vec-ptr. + (define vec-ptr (pointer vec)) + + ;; This variable is *not* a vector; it's a vector-pointer. + (vector? vec-ptr) ;=> #f + (vector-ref vec-ptr 0) ;ERROR + (pointer? vec-ptr) ;=> #t + (pointer-ref vec-ptr) ;=> #(1 2 3) + +This is *not* the same thing as a box, because it can *only* refer to heap +allocated objects, not immediates, whereas a box would be able to hold an +immediate value like an integer or double as well. + + (pointer 42) ;ERROR + (box 42) ;=> #<box:42> + +A box would necessarily need heap allocation, whereas a pointer doesn't. + +It's *also not* the same thing as a foreign pointer, because those can be +anything, whereas these pointer objects definitely point to Zisp objects. + +Pointers may or may not be mutable; I've not made up my mind yet. It may +seem like a pointless data type, but it adds a little bit of expressive +strength to our language. For example, when working with an FFI. And +there's really not much else we can do with all our bits. + +Let's use the term "indirect" for this tag, since "pointer" is already used: + + { pointer == 0x1, foreign == 0x0, indirect: u1, rest: u49 } + +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 +zero (all non-foreign pointers must point to a valid Zisp object), we avoid +the forbidden zero pattern. Thus, we can indicate 16 different values with +our 4 remaining bits. + +It would have been nice to avoid fragmentation of these remaining tag bits. +However, we want to avoid shifting, so let's go with this definition for the +remaining 49 bits: + + { tag_high: u1, pointer_value: u45, tag_low: u3 } + +The pointer value is extracted by masking the entire bit sequence, so it +actually becomes a 48-bit value without further shifting. + +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 +any Zisp object on the heap carries its type information within itself, but +I'm not yet decided on that. + +In any case, let's list some common heap data types that our 4-bit tag can +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 + +This list is likely to change; for example: errors should probably be class +instances, continuations could be merged with procedures, and so on. But +this gives us a rough picture and demonstrates that 16 distinct values is +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 + +WIP + + +<!-- +;; Local Variables: +;; fill-column: 77 +;; End: +--> diff --git a/html/notes/oop.md b/html/notes/oop.md new file mode 100644 index 0000000..0821b42 --- /dev/null +++ b/html/notes/oop.md @@ -0,0 +1,3 @@ +# Object-oriented programming isn't that bad + +WIP diff --git a/html/notes/records.md b/html/notes/records.md new file mode 100644 index 0000000..b93e0c3 --- /dev/null +++ b/html/notes/records.md @@ -0,0 +1,54 @@ +# Subtyping of record types + +It's a serious limitation of SRFI 9 that it doesn't allow creating +subtypes with additional fields. This is an invaluable strategy for +representing a hierarchy of types, which are ubiquitious in real life +and thus in programming. + +Sadly, this brings with it some significant complications if records +are to be initialized with default values to ensure invariants. The +R6RS solves this with an incredibly sophisticated system, which we +might need to adopt. (Search for "protocol" and "record-constructor +descriptor" in the R6RS.) + +However, we may be able to get away with a simpler approach... + +UNDER CONSTRUCTION + +Are constructor protocols really that important? Consider that all we +can do is add additional fields in the subtype. What if we separated +allocation from initialization: + +```scheme +(define-record r1 + (parent #f) + (fields a b)) + +(define (init-r1! r a b) + (set-r1-a! a) + (set-r1-b! b)) + + +(define-record r2 + (parent r1) + (fields c d)) + +(define (init-r2! r a b c d) + (init-r1! r a b) + (set-r2-c! c) + (set-r2-d! d)) + + +(define-record r3 + (parent r2) + (fields e f)) + +(define (init-r3! r a b c d e f) + (init-r2! r a b c d) + (set-r3-e! e) + (set-r3-f! f)) + + +(define r (make-r3)) +(init-r3! r 1 2 3 4 5 6) +``` diff --git a/html/notes/serialize.md b/html/notes/serialize.md new file mode 100644 index 0000000..e35177e --- /dev/null +++ b/html/notes/serialize.md @@ -0,0 +1,67 @@ +# Everything can be serialized + +Let's look at the code mentioned in [compilation](compilation.html) +again: + +```scheme + +;; The fictional file `lookup-table.dat` would be in the source code +;; repository, and the fictional procedure `process-data` would read +;; it and return a data structure. +(define lookup-table (process-data "lookup-table.dat")) + +``` + +(In Zisp, this would be executed at compile-time, so the lookup table +becomes part of the compiled program.) + +If you're familiar with Guile --and I suspect most implementations of +Scheme have a similar limitation-- then you may have noticed an issue. + +Not all Scheme objects can be serialized. This not only applies to +the `write` procedure, but also the compiler's ability to put objects +into the binary representation of a compiled program. (For example, +the .data section of an ELF file in case of Guile.) + +This can be demonstrated as follows: + +```scheme + +(define-syntax process-data + (lambda (stx) + (syntax-case stx () + ((_ file) + ;; Ignore `file`; this is just an example! + (let ((ht (make-eqv-hashtable))) + (hashtable-set! ht 1 2) + ht))))) + +(define lookup-table (process-data "lookup-table.dat")) + +``` + +Compiling this with `guild` will yield an error, complaining about an +"unhandled constant" represented as #<r6rs:hashtable ...> in the error +message. What it's actually trying to say is that hash tables aren't +constants, and the compiler doesn't know how to put them into the ELF +file it's writing. + +(At least, this is the case as of February 2025, using Guile 3.0.10; +who knows what the future will provide!) + +In Zisp, I want absolutely everything to be possible to serialize, and +the compiler should simply be using this capability of the language to +write out compiled binaries. + +For example, given that any Zisp program has to declare a `main` entry +point function, all the compiler would do is execute the file and then +call `(write main)`. How elegant! + +This serialization of a function would, of course, involve traversing +all references therein, and including them in the output somehow. The +same will apply to writing out any data structure. This means that +serializing a module is *not* a matter of invoking `write` on each of +its exported definitions. This would lead to lots of duplicate data +between the outputs, and `eq?` relations would be lost after reading +them back in. We probably want a first-class `module` type that can +be serialized as one object. diff --git a/html/notes/strict-mode.md b/html/notes/strict-mode.md new file mode 100644 index 0000000..5b99386 --- /dev/null +++ b/html/notes/strict-mode.md @@ -0,0 +1,16 @@ +# Strict mode to disallow ignoring returned values + +This ties in to the last point. In Scheme, a non-tail expression in a +body can return an arbitrary number of values, which will be silently +ignored. + +This can lead to bugs, where a procedure actually returns some kind of +success or failure indicator (instead of raising an error) and the +programmer forgets to handle it. + +Though it may be too inefficient to enable globally, there should at +least be a mode of compilation that emits code which checks at every +single function return whether there are any values that are being +ignored, and raises an error if so. + +There would of course be a form to explicitly ignore values. diff --git a/html/notes/sugar.md b/html/notes/sugar.md new file mode 100644 index 0000000..217b0d3 --- /dev/null +++ b/html/notes/sugar.md @@ -0,0 +1,85 @@ +# A little bit of syntax sugar never hurt anyone + +## Lambda shorthands + +We could benefit from a more minimal syntax to express lambda, as an +alternative to the written-out form: + +```scheme + +;; {x ... expr} = (lambda (x ...) expr) + +(map {x y (+ x y)} xs ys) + +(for-each {x (display x)} objects) + +``` + +## Vector and map references + +Furthermore, `foo[bar]` could be sugar for `(vector-ref foo bar)` and +`foo{bar}` could be sugar for `(map-ref foo bar)` or the like. (Not +sure yet whether to use the word "map" for a data type, due to the +overlap with the `map` function. Perhaps `mapping`. In any case +there must be a map kind of data type in the standard library.) + +## Records + +Why not make `foo.bar` reader syntax for `(record-ref foo bar)` where +`record-ref` is a macro that interprets `bar` as a constant? + +Admittedly, this loses us some elegance compared to the widely used +SRFI 9 (standardized in R7RS-small) where field getters only exist as +procedures, so making a field "private" is simply a matter of leaving +the getter out of your module exports. + +A general `record-ref` that accepts field names would need to be aware +of the concept of private fields and block access to them except if +invoked in a context where the private fields are accessible. + +I think the nice syntax is worth the added complexity. It doesn't +seem terribly difficult to expand the concept of "lexical scope" to +include field accessibility information. + +Alternatively, we could just not have private fields, like in Python. +Fields that are meant to be private could be named in a special way by +convention, such as `%foo` or whatever. I have to check whether real +encapsulation would provide us with any substantial benefits, such as +in optimization. + +Oh, speaking of performance, of course `(record-ref x y)` has a big +problem: It would require dynamic dispatch since the type of x is not +statically known. (And no we don't want to write `person.person-age`, +we want `person.age` where `age` is not treated as an identifier but +merely as a symbol for lookup.) + +It may be that we want to add static typing to Zisp! + +We may also add OOP-style objects and only use the dot notation for +their methods, but not fields. The reader syntax for `foo.bar` may +then expand to `(method-dispatch foo bar)`. It would also work for +fields if we really did add static typing, of course. The reason it +would only work on methods is that those need dynamic dispatch anyway. + +THIS POINT NEEDS A LOT MORE CONSIDERATION! + +## Built-in SRFI 17 + +The functionality of SRFI 17 should be a core aspect of the language, +so the following all work: + +```scheme + +;; Vector +(define vec (vector 1 2 3)) +(set! vec[n] value) + +;; Some kind of mapping +(define table (make-table)) +(set! table{key} value) + +;; Record type +(define rec (make-foo)) +(set! rec.field value) + +``` diff --git a/html/notes/symbols.md b/html/notes/symbols.md new file mode 100644 index 0000000..8aa666f --- /dev/null +++ b/html/notes/symbols.md @@ -0,0 +1,19 @@ +# Symbols are strings are symbols + +In Scheme, symbols are literally just interned and immutable strings. +They can contain any character a string can, constructed either via +`string->symbol` or the modern `|foo bar baz|' syntax for quoted +symbols. Why not just embrace the fact that they are strings? + +Scheme strings are mutable, but they are a terrible choice for text +manipulation, because they are constant-length. They are literally +just vectors of characters. If you wanted a vector of characters, +well, use a vector of characters! + +Zisp won't differentiate between symbols and strings. All strings +will be immutable, string constants will be automatically interned, +and bare symbols will just be reader syntax for a string constant. + +Instead of `string->symbol` we will have `string-intern` which +basically does the same thing. Dynamically generated strings that +aren't passed to this function will be uninterned. diff --git a/html/notes/zero-values.md b/html/notes/zero-values.md new file mode 100644 index 0000000..3a1eecb --- /dev/null +++ b/html/notes/zero-values.md @@ -0,0 +1,11 @@ +# Return zero values when there's nothing to return + +This is only a minor point: + +It's a long-running pet peeve of mine that R5RS Scheme specifies "an +unspecified value" to be returned when there's nothing meaningful to +return. It's a remnant from before we had the ability to return +multiple values, and should be eliminated. + +Any operation that has nothing meaningful to return, will return zero +values in Zisp, and no more. diff --git a/html/prelude.html b/html/prelude.html new file mode 100644 index 0000000..14a155b --- /dev/null +++ b/html/prelude.html @@ -0,0 +1,13 @@ +<!doctype html> +<head> + <meta charset="utf-8"/> + <title>__TITLE__</title> + <meta name="viewport" content="width=device-width, initial-scale=1"/> + <link rel="stylesheet" type="text/css" href="/zisp/style.css"/> + <link rel="stylesheet" type="text/css" href="/zisp/highlightjs/styles/default.min.css"/> + <script src="/zisp/highlightjs/highlight.min.js"></script> + <script> + hljs.configure({languages:[]}); + hljs.initHighlightingOnLoad(); + </script> +</head> diff --git a/html/style.css b/html/style.css new file mode 100644 index 0000000..f1b474b --- /dev/null +++ b/html/style.css @@ -0,0 +1,23 @@ +body { + margin: 20px auto; + padding: 0 20px; + max-width: 80ch; + + background: #eee; + color: #333; + + font-family: sans; +} + +h1, h2, h3 { + line-height: 1.2; +} + +p { + line-height: 1.6; + text-align: justify; +} + +code { + font-size: 1.2em; +} |
