I started working as a v-dash at Microsoft last week, so I haven’t had time to work on KLOS/Kiwi/Eddy.
The last bit of hacking I was doing is to add keyword support to class initialization. There’s no function that takes a normal list and turns it into an arglist, so that made it difficult to process slot descriptors.
I hope to be able to change compute-slots to not destructure the slot descriptors so that they can stay argilst.
I wrote a while back that the first program I’d like to run on Kiwi would be TinyCLOS, now that I have KLOS going on Kawa, I’m gonna revise what I said: I think the first program that Kiwi should run ought to be the Scheme48 module system (and by extension, its command processor).
Taking a break from KLOS hacking this weekend, I re-read JAR’s paper on the Scheme48 module system this weekend. The section on configuration mutation grabbed my attention in particular.
Reading the Scheme48 manual, it’s clear that the module system and command processor really work together as a whole. One thing I noticed trying to read the module-system code is that due to bootstrapping, since Scheme48 is built on top of Scheme itself, there’s also a fake version of the module system to be loaded on systems that don’t have a module system.
Things get complicated, and often necessarily repetitive, when you need to bootstrap a system. There needs to be a base, fake (or at least simplified), definition to get the system running, and then another, more complete, aka. real implementation is repeated once more to get to the full semantics later on. This makes the definitions read somewhat circularly.
I also noticed this when I was reading the code for the Thomas Dylan->Scheme compiler. Since Thomas just compiles Dylan into Scheme, its class and generic-function definitions are a lot simpler than TinyCLOS’s.
I wonder if I side-step the issue and implement the underlying structures only in Kotlin, maybe I can arrive at the simpler (Thomas-like) implementation of the module system in Kiwi.
The two module systems are largely the same, modulo some differences in naming (define-structure in S48 vs. define-library in R7RS), but there are two parts that stand out: explicitly named interfaces and the marking of syntax definitions and exports.
As noted in the S48 manual, explicitly named interfaces are not strictly necessary, but there are good reasons why it’s nice to have them named, such as the ability to control the visibility of an identifier during interactive development.
Andrew has ported parts of the R7RS module syntax on top of Scheme48 for his Precheme work, so I can make use of that if I decide to just implement the S48 module system.
One thing that I have yet to figure out is what it means to have (or not have) the :syntax and for-syntax markers in the definitions. Scheme48 has them, R7RS doesn’t.
I spent the last week working on KLOS and I’m happy to see that one of examples now run on Kawa, so success!
KLOS is a port of TinyCLOS to Kawa with some changes:
In TinyCLOS, the instance structure is stored as a vector, and there’s a mapping of closures to instances in order to support entities (generic functions). Because such a mapping already exists, instances are also then stored as closures that return the vector, so that access to both instances and entities is unified via the same lambda interface. This was beneficial also because there is no built-in support of printing circular structures, so the opaqueness of lambdas come in handy for both instances and entities.
In KLOS, I opted to use Records to store instances (same as R7RS-TinyCLOS aka Virgo). Without funcallable objects in Scheme, however, the mapping of closures to instances is still necessary. What this means that instances and entities have separate accessors: instance-ref and instance-set! reads into the slots vector inside the instance record; and entity-ref/entity-set! need to first looks up the record using the entity closure.
In Swindle (TinyCLOS for Racket), because Racket has callable structs, everything is actually represented the same way, but for some reason (that Eli has forgotten and can’t quite explain to me), the distinction of allocate-instance and allocate-entity still exists in the source code.
In all existing TinyCLOS variants, init arguments are handled using a helper function called getl which is used to lookup values by key. In KLOS, running under Kawa with its built-in support for DSSSL keywords, I have replaced all the usages of getl with #!key in the lambda list directly.
;; Instead of this:
{define {foo #!rest initargs)
(let ((a (getl initargs 'a #f))
...))
;; Write it directly like this:
(define (foo #!key a) ...)
I thought this ought to be a simple and straight-forward change, but progress came slower than expected because now I’ve had to learn more about how keywords are handled, specifically the handling of #!key and #!rest together, and how to pass keywords arguments through a series of functions. Turns out Kawa has special syntax supporting the merging of keywords arguments, but I also learned later on (via testing on Gambit Scheme) that (apply func args) works without using non-portable syntax.
(define (bar #!rest rest #!key a b) (list a b rest))
;; When passing the argument directly, the keywords passed to FOO1 do not get processed by BAR
(define (foo1 #!rest rest) (bar rest))
(foo1 a: 1 b: 2)
> (#f #f ((a: 1 b: 2)))
;; Using Kawa @: syntax, the two arglists are spliced into one
(define (foo2 #!rest rest) (bar @:rest))
(foo2 a: 1 b: 2)
> (1 2 (a: 1 b: 2))
;;APPLY does the same thing portably
;;
(define (foo3 #!rest rest) (apply bar rest))
(foo3 a: 1 b: 2)
> (1 2 (a: 1 b: 2))
Additionally, now I have a better sense of the differences between Dylan, DSSSL and Racket’s handling of keywords:
Lambdas are defined like this: (define (foo a (b 'b) #:c c . d) (list a b c d))
Racket supports optional arguments, keyword arguments and rest arguments.
Its basic syntax does not allow arbitrary keyword arguments.
Features are marked using #!optional, #!rest and #!key.
The order of #!key and #!rest is flexible and yields different results depending on the order.
It’s the same as DSSSL, except #key must come after #rest and there’s no support for #optional.
For KLOS, I’ve chosen to stick to Dylan semantics while using the DSSSL system, which means not using #!optional.
I hope to add support for initargs so that the code snippet from Dylan Design Note #3: Make Class Specification (Addition) runs.
If time permits, I’d also like to add syntax support so we can write define-class and define-method.
I’d also like to port bps.dylan to Scheme as a typing exercise to get a better feel for what’s actual in use and required for the port.
Common Lisp has &allow-other-keys and Infix Dylan has #all-keys. Guile also supports :allow-other-key. Will it be sufficient to just write #!rest r #!key a b c, because neither Kawa nor Gambit support such a marker.
I spent the last week in emacs (instead of IntelliJ) and wrote only Scheme. I’ve been reading the different variants of TinyCLOS and making it work on Kawa.
I first tried using r7rs-tinyclos as is in Kawa, but somehow that just crashes. I didn’t want to debug the crash so I just started with my KLOS repo and started writing the definitions of allocate-instance and allocate-entity and went from there.
I learned a bit about how to setup an R7RS project in Kawa along the way, and it felt pretty productive.
Incidentally, the difference between allocate-instance and allocate-entity has to do with whether or not the object is funcallable. In an implementation that has funcallable instances, this distinction wouldn’t be necessary. In addition, because normal Scheme doesn’t have funcallable records, there needs to be an additional alist to map the closure (so it’s funcallable) and the actual object instance (in KLOS, I’m calling that *all-entities*.
By now I have code that allocates instances and entities (the (klos internals) library) and also defined the foundational classes ((klos class), defining <object>, <class> and <generic-function>, etc). I’ve also defined the instance-creation protocol (make, initialize, etc) but I need to fill that in and add tests.
The plan is to customize KLOS so that it matches a MOP that matches Dylan semantics. Dylan actually doesn’t expose the introspection protocol (compute-cal, compute-methods, etc…) so I don’t know if I need to expose that either.
I had a good session with Joel last week and we started working on keywords. The cool thing I realized now is that the work for keywords has a lot of overlap with Call-site optimization for Common Lisp, and that’s also a direct link to Fast Generic Dispatch for Common Lisp, so it’s cool that all these things are coming together (multiple values is tied in with this too).
Specifically: I think the snippet idea from the Call-site optimization paper is the key piece to both supporting keywords and generic functions, so it’ll be neat to see if we can define a representation of that in Kotlin for Kiwi.
I’m warming up to the idea of defining foo::<type> as a way of specifying specializers. I see that Kawa has a similar syntax, and it’s also in Bigloo. Unfortunately, it doesn’t look like there’s a way for me to access the type specifier from Scheme in Kawa.
(singleton ...) classes workbefore, after, around)The conversations I had with Carl, Darius and Joel this week have helped me form a clearer picture of the spread of projects ahead.
The work of Kiwi is to write an R7RS Scheme on Truffle (in Kotlin). The purpose of this project is to read / digest Scheme implementation papers and then actually implement them for real.
Right now, Ive done flat closures from The Three Implementations of Scheme (Dybvig, 1987).
Here is the pending list of papers to imlement:
Also Manuel’s work on Delimited Continuations inLispX is also a thing to implement.
Eddy is now the project to take Deuce source code from infix Dylan and porting them to Scheme. Like I wrote earlier, a suitable runtime is needed to test that the port actually works. Such a system must be:
unwind-protect(This list should be updated as I learn more)
I tried to start the port using Guile, but that didn’t go thru because keyword support is poor in GOOPS (though I did learn that someone defined as define-method* that adds keywords, so maybe I can fallback to Guile if the others don’t work out).
I also tried STklos, but having to run it inside Docker is just too slow, but its macro-expander seems a bit wobbly.
Now I’m trying Sagittarius Scheme, which seems viable.
Turns out there’s a list of other implementations here.
The inconsistent handling of keywords between implementations is particularly irksome - on top of the different ways to denote a symbol (is it foo:, :foo, or #:foo?) the syntax of lambda lists is also different (#key, :key or nothing in Racket’s case). Perhaps I should write an external program that converts from one notation to another. I like #:foo, but I’m also okay with foo: which is DSSSL style. It’s a pain that Sagittarius only supports :foo.
One possible system that could run Eddy is if I port TinyCLOS + Dylan-like syntax to Kawa, this is the same as the old KLOS project that I tried a few years ago and didn’t figure out then.
One place to start is to go take r7rs-tinyclos and make it run on Kawa, and then add the missing support:
define-class, define-method, keyword arguments)make into a generic function, i.e. understand / streamline the differences between the TinyCLOS MOP and Dylan.One thing I realized now (that I didn’t get years ago) is that JVM integration is optional - there’s a viable path to getting a working system without exposing CLOS classes as JVM classes. So really, it boils down to 3 points:
TinyCLOS uses the most low-tech technique available in R4RS - Scheme vectors.
R7RS-CLOS represent them as Scheme records (R5RS and onwards)
On a system like Kawa, they can represent be as Java classes, but coming up with an encoding requires some novel technique to be determined.
On Truffle, the Static Object Model or Dynamic Object Model can be used
How do you call Java methods?
Learning from Joe Marshall’s technique from Common Larceny, turns out (c) is not the only way to do it. You could always just reflect the Java class hierarchy and replicate them into the CLOS side and install bridges.
How would Java call your methods?
This point I never figured out, while it’s cool to allow that, it turns out it’s not at all necessary for my purpose of implementing an editor.
There’s a neat research paper in this space also:
Fast Generic Dispatch for Common Lisp (Strandh, 2014) presents a cool way to do method dispatch.
When Kiwi is mature enough to run actual code, KLOS is going to be the first big piece of code for Kiwi to run.
Lastly, just because it’s a good name, it will be interesting to also port the Deuce data structures to JS, and the name of that project is Juice.
Rereading BruceM’s note on Deuce’s architecture, I was motivated to look into the core data structures that drive the entire app. I have also started looking from the other direction, and started from start.dylan of Deuce to see how the editor gets booted up.
It looks like Bruce might be right, and there are many parts of the editor that’s not tied to the UI system, in which case, I could start porting that code back to a lisp well before having a running Kiwi system.
This investligation revealed clearly one of the difficulties in the Scheme ecosystem - even though there are many choices, the feature sets are all over the place, and you’re not gonna find the right mix of features that you’re looking for.
In Deuce’s case, I’m looking for a R7RS Scheme that supports the following:
unwind-protect and bind-exitI’ve checked Kawa (doesn’t support CLOS), MIT Scheme (no keyword arguments), Bigloo (no R7RS, no multiple inheritance) and STklos (no unwind-protect, but there’s call/cc and friends).
So maybe the initial target is to port the Deuce data structures to a form that’s runnable on Stklos as a first pass.
Even so, I just found out that the define-class form in Stklos is subtly different, it requires a () around all the slots, which is not required in Dylan:
;; This is Stklos
(define-class <point> ()
((x :init-form 0 :getter get-x :setter set-x! :init-keyword :x)
(y :init-form 0 :getter get-y :setter set-y! :init-keyword :y)))
This looks almost like Dylan code, but here’s the actual code:
;; This is Dylan
(define-class <point> ()
(x init-value: 0 getter: get-x setter: set-x! init-keyword: x:)
(y init-value: 0 getter: get-y setter: set-y! init-keyword: y:))
The support for keywords is also subtly different between implementations. This page is a survey of the different variations. Kawa and Dylan support what’s called DSSSL style keywords, but I actually like the paper Eli wrote on how it’s done in Racket. For the sake of compatibility, I might stick to DSSSL style for now.
In researching this topic, I came across this LtU discussion and a note from Andy.
Here’s one path that might work:
Port Deuce data structures to R7RS libraries and make the tests run in Stklos, let’s call this project Eddy.
Go back to my KLOS attempt from 2015 and port TinyCLOS to Kawa, without tackling integration with Java classes.
Work on Kiwi to build a real Dylan-like language on top of R7RS Scheme + a scope sets macro-expander, with native mirroring of Java classes into Kiwi’s CLOS classes.
If this does indeed pan out, then both Kawa+KLOS and Kiwi can be vehicles for running Eddy. The GUI code that calls into JavaFX would be different between Kawa and Kiwi, because Java integration will be different. The syntactic idiosyncrasies of Stklos can be updated to follow match Dylan when we move to running on (2), which of course will break on (1).
I have 4 or 5 failing test cases in my general-tco branch, I think they’re all pointing out the same bug.
I feel more motivated to port some Deuce data structures now, so I think I’ll finish that before coming back to Kiwi. Besides, looking at the Deuce code, it doesn’t look like tail-calls are used that often (however, I did see delimited control like unwind-protect and multiple values show up pretty early on)
I finally got self tail-calls working yesterday, which is a good milestone.
The work involved adding code to identify and mark the tail position, as well as figuring out if we’re tail-calling onto ourselves (self-tail).
The emitted code is a trampoline, so instead of applying the function, we throw an exception and rewrite the outer call site as a while loop.
One change that took 2 days to do is to swap the argument passing from the frame.arguments array onto using FrameSlots. The return value from the while loop also needed to be written into another FrameSlot, so that was done as well.
As part of porting over some test cases, I also added support for and and or - it was nice that I could do it during the compile into KiwiNode and rewrite them as IfNodes. It’s interesting to learn that:
(and) returns #t(or) returns #f(and 1 2 3) hold onto the last non-false value, returning 3.(or 1 2 3) returns the first non-false value: 1.I think once I’m done with general tail-calls, I’ll go back to writing the macro-expander, and and and or can be implemented there instead of the compiler, which will give me a chance to simplify the expression by doing constant folding.
The work on TCO helped me understand more of how RootNodes work in Truffle. With that in mind, adding delimited continuations and multiple-values now seems within reach.
Maybe this is the direction I’ll take next:
August: finish TCO (self tailcalls and general tailcalls)
September: port micro macro expander or implement Dybvig’s mulitple-values paper.
Fixed the reader to read multiple forms, which also fixed how comments are parsed. The issue was the missing neg operator in PetitParser (not not.
I read up on TruffleScheme and the Truffle/Oz paper and I now have a better understanding on what it takes to implement TCO. To fix it properly, the current compilation pipeline should be refactored:
Current:
KiwiSymbols)asKiwiNode (turn them into LiteralNodes)compile (turn LiteralNodes into AST nodes like IfNode and LambdaNode)Refactored:
expand (can be no-op for now)compile (turn Syntax into AST nodes)This means all the Literal nodes will be replaced by Syntax objects.
Oh yeah, got laid off on my birthday, so now I need to prepare for interviews.
Progress is moving slower, but I feel like a roadmap is emerging in my mind.
Writing the line “the first real Scheme program that I really want Kiwi to run in TinyCLOS” in the last post gave me some clarity on how I should be spending my time. Last week, I looked into how TruffleRuby bootstraps and specifically how the CoreLibrary class is used.
In my mind, the order of operations is something like this:
Support loading scheme files on boot. As a test, I want to load a banner.scm that just prints "Hello Kiwi!".
Load a partial file called ‘tinyclos.scm’ and populate the file with a function at a time.
TinyCLOS will fail, but it’ll drive the focus of the missing support in the language.
Eventually, when I get to having a more complete expander (with module system support), I can replace tinyclos.scm with a package.scm that includes a tinyclos module.
I also started reading how the command processor works in Scheme48.
Prescheme.org was announced, it’s something to keep an eye on.
So the first real Scheme program that I really want Kiwi to run in TinyCLOS. And just to get started, I’ll need at least let.
I’ve been dragging my feet on nano-expander, so last Sunday, I thought, having read this note from Scheme from Scratch, that I can just do a quick thing inside the existing KiwiNode::compile to transform lets into lambdas.
Typing in the transformation is easy enough, but when I tried to also do let*, it dawned on me that I really do need to have a proper expander – you have to expand all lets to lambdas before compiling, and what I did only worked for the outer-most layer, once I have nested let expressions, the inner lets will already be wrapped inside the outer lambda, without a chance to expand.
So I read up on the next stages of the scope-sets expander and I think I’m gonna merge my nano branch as is, and just proceed to the next micro stage. Once I have micro ported, I can add let and letrec as additional core forms.
Kiwi
I did a little bit of hacking in Hong Kong on the control branch but other than that, I haven’t been coding much. I thought I’d work on getting LET in place, but it turns out that depends on a beefier expander so that’s what I should be doing next.
Next steps:
nano-exapnder and merge that in.LET.letrec?Once I have quasiquoting (shouldn’t be too hard), here’s a good test case.
DUIM
I also wanted to start working from the other end of the project, so I started reading the DUIM source code.
Figured out what the protocol-class does in DUIM so that’s a place to start typing.
I kind of lost focus the past week so I’ve multiple strands of WIP going on now.
Standalone
I ported the code from Java to Kotlin, but didn’t figure out how to actually make it run. It’s disappointing that SL is not compatible with the latest v24 release, so that’s another snag.
Nano expander
I started handling #%app but I lost focus working on it. I need to get back to it soon.
Control operators
I did some reading on the various control operators, I feel like I’m ready to tackle that soon.
Emulator sources
I found some old prefix-dylan source code in a forgotten branch of the Dylan repo.
I got the expander tests to pass last night. It feels good to wrap up this work after having worked on it for a month.
Next steps
There are a directions I can take:
Port the standalone module over - this might be a good quick thing to do that will only take a few days.
Work on implementing the control operators from Lispx, this might take a while, but it’ll be fun to do.
Learn about the Truffle’s Dynamic Object Model and get the grounds prepared for porting TinyCLOS.
I was stuck last week because I couldn’t get eval to work during expansion. I tried using Polyglot.eval but that made life worse because now I have to convert between Java values, Kiwi values and Polyglot values. Things moved along, but ultimately it didn’t work (and didn’t feel right).
I had a chat with the Truffle team and had a scare thinking that maybe the port to Kotlin wasn’t so wise after all - maybe it is only working in interpreter mode but not compilation mode, but alas, all is well, I’ve been testing in compile mode the whole time, so maybe it’ll be safe to stick with Kotlin.
I’m back to using Kiwi class to eval the expander code and this time it seems to be getting further along. I don’t know why it didn’t work when I tried it the first time 2 weeks ago. Hopefully the pico expander will be ported by the end of the week.
Macro-expansion is basically working, but the last step is still stuck because eval turned everything into a Truffle Polyglot value.
Quotation needs a bit of a rework, so taking a detour to fix that up now.
Decided to publish these notes in the public instead of as private notes.
Feb 22
Ported Kiwi from Java 21 to Kotlin, the code size was reduced by roughly half.
Can’t run tests (yet?) because we can’t seem to initialize the TruffleLanguage.
Feb 25
Kotlin port was successful!
The past week or two, I’ve started porting the @mflatt pico expander.
Also bought some books from t3x.org/index.htm… to get some more references on implementing a Scheme.