diff options
Diffstat (limited to 'html/notes/reader.md')
| -rw-r--r-- | html/notes/reader.md | 470 |
1 files changed, 0 insertions, 470 deletions
diff --git a/html/notes/reader.md b/html/notes/reader.md deleted file mode 100644 index ebbe1ea..0000000 --- a/html/notes/reader.md +++ /dev/null @@ -1,470 +0,0 @@ -# Reader? Decoder? I barely know 'er! - -*This started from an expansion to the following, then became its own -article:* - -[Symbols are strings are symbols](symbols.html) - -OK but hear me out... What if there were different reader modes, for -code and (pure) data? - -I want Zisp to have various neat [syntactic extensions](sugar.html) -for programming purposes anyway, like the lambda shorthand, and these -shouldn't apply to configuration files, either. (Although they seem -unlikely to occur by accident.) - -So what if the transform from string literal to quoted string literal -only occurred in code reading mode? - -At least one problem remains, which is that `'(foo "bar")` would turn -into `(quote (foo (quote bar)))` because the reader would be in code -mode while reading it... - -This reminds me of the long-standing annoyance in Scheme that "quote -is unhygienic" and maybe we can tackle this problem as well now. - -Also, expressions like `'(foo '(bar))` always seemed weird to me, and -probably have no place in Scheme, because we don't generate code via -quote; we generate it with macros that operate on explicit syntax -objects rather than pure data. - -I want to experiment with an idea like this: - - ;; "code reader mode" transformations - - '(foo bar) -> (#quote foo bar) - - '(foo 'bar) -> ERROR - - "foo" -> (#quote . foo) - - "foo bar" -> (#quote . "foo bar") - - '(foo "bar") -> (#quote foo bar) - - '(foo "x y") -> (#quote foo "x y") - -The right-hand side shows what you would get if you read the form on -the left in code reader mode, then wrote it back out in data mode. - -The writer could also have a code writer mode, which applies the -reverse transformations. There should be a one to one mapping, -unambiguous, so this always works. A "hygienic" way to quote is -imperative here, since the writer could otherwise not know whether -some `quote` keyword in a list is *the* quote special form, or just -part of some data. - -We've made quote into a special token, `#quote`, to solve that. -Instead of adding a separate symbol data type that's a subtype of -strings, I think I'll add something called a "rune" or such that's -represented like `#foo` and allows for custom reader extensions, or -rather, writer extensions. - -Essentially, these runes would be bound to a pair of the following: - -1. A procedure that accepts a datum and returns some type of value. - -2. A procedure that takes values of that type, and turns them back - into written format. - -For `#quote`, the reader procedure would be the identity function. -The writer procedure would need to be a little more sophisticated. - -Note that the first procedure would not actually be called during -reading of data. Somewhat confusingly, it would only be called in -evaluation of code. - -Let's recap. Starting with pure data reading and writing: - -1. There is no special reader syntax. This s-expression format is a -bare minimum of what's needed to represent sequential data i.e. lists -and lists are the only compound data type recognized by the reader. -Anything that isn't a list is either an atomic value, or a string -which may or may not be considered atomic depending on how pedantic -you want to be. Oh and runes are allowed. - - A. This is basically "classic" s-expressions with runes added. - Only lists, numbers, and strings/symbols are recognized. - - B. Heck, numbers may not be recognized. Or maybe they will be - limited to integers and floats, but no rationals or such, and - reading a float will guarantee no loss of precision? - -2. Writing data returned by the data reader back out, in data form, -will produce exactly what was read, with the sole exception being -whitespace differences. The data is not allowed to contain any -non-atomic values other than proper lists. - - A. It's important not to allow floats that IEEE 754 doubles can't - represent, since then differences between input and output would - occur. But what about numbers like "10.00"? That would also - become something else when written back out. - - B. OK, maybe numbers represented in a non-canonical way are a - second source of difference between reading and writing back out, - but let's at least guarantee there's no loss of precision. - -(I've not considered comments. Maybe they will be preserved? Maybe -they should be implemented as code reader syntax sugar as well??) - -And now code reading and writing: - -1. Various syntax sugar is internally transformed into runes, with -non-list compound data literals (vectors, hash tables, etc.) needing -this type of representation to appear in code. - - A. Writing that data back out in data mode will reveal the inner - workings of the language, producing output containing runes. - - B. Direct use of runes may be forbidden; not sure about this. - - C. Evaluating this data containing runes will produce, in-memory, - the actual values being represented. The "reader procedure" tied - to the rune is responsible for this, though the fact that it's - evaluation and not reading that calls that procedure makes it - confusing so a better name is needed. Maybe just "decoder." - -2. For every data type that falls outside the pure data syntax, there -is a procedure that turns it into a canonical data representation -based on lists and atomics, always using the format `(#rune ...)`. - - A. Another procedure is capable of turning that back into reader - sugar, but this is not terribly important. Although it would be - neat to be able to write out code that looks like hand-written - program code, this really is just a bonus feature. - - B. For some types, turning them back into code without any runes - may be highly complicated; procedures, in particular, would need - decompilation to make this work. - - -## Recap (or not?) - -Wow, that was a long "recap." I actually came up with new ideas in -writing that. Let's recap the recap. I'll represent the mechanisms -as different pipelines that can happen using the various features. - -Typical pipeline when reading and evaluating code: - - code-file --[code-reader]--> code-data --[eval]--> values - ^^^^^^^^^^^ ^^^^ - turns sugar into calls rune decoders - rune calls to produce values - i.e. desugars code & compiles code - -Reading in a [serialized program](compile.html): - - data-file --[data-reader]--> data --[eval]--> values - ^^^^ - fairly trivial - (no lambdas, only runes) - -Reading pure and simple data like a config file: - - data-file --[data-reader]--> data (no runes to eval) - -Note that "data" is a subset of "values" basically. And the term -"code-data" which was used above just means data that is meant to be -evaluated as code, but is totally valid as pure data. This is not to -be confused with the "data" that existed in the intermediate step -while we were reading a serialized program; that was absent of any -forms like lambdas that need compilation. - -OK, that last bit was a bit confusing, and I realize it stems from -conflating rune decoding with code compilation, so let's split that -further up. Above, "eval" is "decode + compile" basically, but it's -possible to separate them, for example if we want to read a file of -serialized values that should not contain any code: - - values-file --[data-reader]--> values-data --[decode]--> values - -This is a secure way to read complex data even if it comes from an -untrusted source. It may contain runes that represent code, such as -in the form of `(#program "binary")` (compiled procedure) or even -`(#lambda (x) (do-things))` but so long as you don't actually call -those things after having decoded them, they can't do anything. -Decoding runes can't define macros or register new rune decoders, -meaning there's no way to achieve arbitrary code execution. - -Heck, although `#lambda` exists to represent the desugaring of the -`{...}` convenience syntax, it wouldn't actually work here because -decoding runes would happen in a null-environment without any bound -identifiers, meaning that e.g. `(#lambda (x) (+ x x))` would just -raise an error during decoding, because the compiler would consider -`+` unbound. - -Alternatively, instead of calling the compiler, the `#lambda` decoder -could just be a no-op that returns the same form back, but without the -rune, like `(lambda (x) (+ x x))`, because the compiler will take care -of that later. Yeah, I think this makes more sense. Why doesn't the -code reader directly give `(lambda ...)` for the `{...}` sugar? Well, -actually, the `#lambda` decoder may yield a syntax object where the -first element specifically refers to the binding of `lambda` in the -default environment, so you could use `{...}` in an environment where -`lambda` is bound to something else, and you would still hygienically -get the default lambda behavior from `{...}`. Yay! - -(Wow, it's rabbit hole after rabbit hole today. This is good though. -I'm coming up with some crazy stuff.) - -It would be possible to decode "code-data" and get an internal memory -representation of an uncompiled program which however already has -various data structure literals turned into values. This is super -obscure but for sake of completeness: - - code-file --[code-reader]--> code-data --[decode]--> code-values - -(These so-called "code-values" would only ever be useful for piping -them into the compiler. By the way, I initially used "eval" in the -example of reading a serialized program, but "decode" would have been -sufficient there.) - - -## Here's a well-deserved break - -(There wasn't a new header in a while. This seemed a good spot.) - -Now writing pipelines. Let's reverse the above pipelines, from the -bottom back towards eventually the first... - -The reverse of the super obscure thing above: - - code-values --[encode]--> code-data --[code-writer]--> code-file - -That would only ever be useful for debugging things. Now writing a -data structure into a serialized file, without unnecessarily invoking -the decompiler: - - values --[encode]--> values-data --[data-writer]--> data-file - -That gives you a file containing only data, but the data is the -encoded format of various data structures Zisp recognizes... -Actually, that may include compiled procedures as well. - -Now the simple config file case, being serialized: - - data -[data writer]-> data-file - -Now serializing a compiled program to a file, without decompilation: - - values --[encode]--> values-data --[data-writer]--> data-file - ^^^^^^ ^^^^^^^^^^^ - data structures no decompilation - become rune calls or "re-sugaring" - -Oh, look at that. It's the same as writing out data structures, as -we've already seen previously... This recap of a recap will need -another recap for sure. - -And now, the full decompiler: - - values --[uneval]--> code-data --[code-writer]--> code-file - ^^^^^^ - decompilation - -Actually, just like "eval" is "decode + compile", the "uneval" here -really is "decompile + encode". - - -## The Revised Recap of the Recap - -The following exist: - -1. Readers: - - 1. Data reader: Reads lists, strings/symbols, runes, integers, and - IEEE 754 double-precision floats without loss of precision. - - 2. Code reader: Reads code that can contain various syntax sugar, - all of which has an equivalent representation with runes. - -2. In-memory transformers: - - 1. Decoder: Calls decoders for runes in data, to yield values. - - 2. Evaluator: [Executes aka compiles](compile.html) decoded values - into other values.[*] - -3. Reverse in-memory transformers: - - 1. Encoder: Reverse of the decoder. (Lossless?) - - 2. Unevaluator: Reverse of the evaluator. (Lossy.) - -4. Writers: - - 1. Data writer: Reverse of data reader. (Lossless.) - - 2. Code writer: Reverse of code reader. (Lossy?) - -(*) This needs decoding to run first, because otherwise it wouldn't - realize that you're e.g. calling `+` on a pair of rational number - constants represented through runes, so constant folding wouldn't - work. Same with `vector-ref` on a vector literal represented as a - rune, and so on. - - -## How in the seven hells did I arrive at this point? - -Jesus Christ! - -This was about symbols and strings being the same thing. - -But I love these rabbit holes. They're mind expanding and you find -out so many new things you never thought about. - -Did you notice, by the way, that the code reader/writer above is -essentially a parser (and unparser) you would have in a regular -programming language, where syntax becomes an AST? The pure data -format is basically our AST! - -But this doesn't mean we lost homoiconicity. No, we merely expanded -upon it by providing a more detailed explanation of the relationship -between textual representation of code and in-memory data that exists -at various stages before ultimate compilation. - -Oh, and did we achieve our strategy of strings = symbols now, or does -it need to be dropped? I think we achieved it. The code reader, as -described all the way up where the section "Reconsidering AGAIN" -begins --in the original article; see top-- will desugar string -literals into: - - "foo" -> (#quote foo) - -(As already described originally...) - -And the `#quote` rune? Well, it will not actually just return its -operand verbatim, no! It will return a syntax object that's a list -with the first element specifically refers to the binding of `quote` -from the standard library. In other words, it's the evaluator that -actually implements quote, not the decoder. - -Oh yes, this is very satisfying. Everything is coming together. - -Syntax objects, by the way, will also have a rune-based external -representation, so you can inspect the result of macro expansion. - -And yes, I think using runes directly in code mode should be illegal, -because it allows referring to bindings in the standard library, or -even bindings in arbitrary libraries by crafting syntax objects -represented via runes, to bypass environment limits. - -That bug actually existed in Guile at some point, where one could -craft syntax objects, represented as vector literals, to refer to -bindings in other modules, making it impossible to run code in a -sandboxed environment. (It was fixed long ago, I believe.) - -Oh, but what about `#true` and `#false`? OK, maybe there will be a -whitelist of runes that are allowed in code. That makes sense. - -We will see. Still more details to be fleshed out. - -In any case, some runes must be able to declare that they don't take -arguments, in which case `(#rune ...)` isn't decoded by passing the -entire form to the decoder of `#rune`, but rather treated as a normal -list whose first element is decoded as a nullary rune. That's how -boolean literals in code will be implemented. - - -## Looking at more of the initial problems - -What happened to `'(quote "foo")` in code mode being weird? Well, -encountering an apostrophe tells the code reader that the next -expression is a datum, so it switches to data mode for that. - -Wow, that was easy. - -This also means you can't use syntax sugar inside it, which is good -because as we said previously, we don't want to use quoting to create -code; we want to use syntax objects for that. - -This is really orthogonal to the whole runes issue, and could have -been solved without that mechanism, but I'm happy I came up with it -because it resolves hygiene issues. - -The syntax `#'(quote "foo")` would be sugar for a different rune, and -the reader would remain in code mode, further desugaring any sugar -found within, so this works: `#'{x (+ x x)}` - -Oh and I mentioned reader extensions (for code mode) but then didn't -expand on that. Well, whenever the code reader encounters this: - - #foo(blah blah blah) - -It will turn that into: - - (#foo blah blah blah) - -After which the decoder for `#foo` will be invoked, which could have -been registered by the programmer. - -Can that registration be done in the same file though? Normally, the -execution step comes after decoding, and we decided that we don't want -to allow arbitrary code execution to happen just when reading a data -file and decoding it. So something exceptional would need to happen -for this to work. Or maybe not. - -Remember that [compilation is execution](compile.html) in Zisp, -meaning that compiling a file looks like this in pseudo-Scheme: - - (define env (null-environment)) ;start out empty - - (while (not (eof? input)) - (let* ((datum (read-code input)) ;desugar - (value (decode datum))) ;decode - (eval! value env))) ;eval in mutable env - - (write (env-lookup env 'main)) ;serialize - -I've called eval `eval!` to indicate that it can mutate the env it -receives, which is what import statements and defines would do. - -Let's modify that a little further to indicate the fact that reader -macros, or in our terms, custom rune decoders, can be defined in the -middle of the code file by affecting the environment: - - (define env (null-environment)) ;start out empty - - (while (not (eof? input)) - (let* ((datum (read-code input)) ;desugar - (value (decode datum env))) ;decode in env - (eval! value env))) ;eval in mutable env - - (write (env-lookup env 'main)) ;serialize - -Since the `decode` procedure is given an environment, it will look up -decoders from therein. So, after the evaluation of each top-level -expression, the expressions coming after it could be using a custom -decoder. - -What our reader macros cannot do is completely affect the lexical -syntax of the language, as in, add more sugar. You must rely on the -global desugaring feature of `#x(...) -> (#x ...)` which, now that I -think about it, is completely useless because a regular macro could -have achieved exactly the same thing. - -OK, let's try that again. The global desugaring wouldn't work on -lists only, it would work on a number of things: - - #x"foo" -> (#x #string . foo) - - #x[foo] -> (#x #square . foo) - - #x{foo} -> (#x #braces . foo) - -You get the idea! - -(I've changed my mind that `"foo"` should desugar into a call to the -regular `#quote` rune; it should be `#string` instead to disambiguate -from the apostrophe if needed.) - -Also, all those would work without a rune as well, to allow a file to -change the meaning of some of the default syntax sugar if desired: - - "foo" -> (#string . foo) - - [foo bar] -> (#square foo bar) - - {foo bar} -> (#braces foo bar) - -Or something like that. I'm making this all up as I go. |