Hacking slowdown

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.

KLOS progress

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:

Representation of instances and entities

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.

Use and support of keyword in both the implementation and the API

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:

Racket

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.

DSSSL (in Kawa, Gambit and others)

Features are marked using #!optional, #!rest and #!key.

The order of #!key and #!rest is flexible and yields different results depending on the order.

Dylan

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.

Work for this week

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.

Questions

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.

KLOS progress

Working on KLOS in Kawa

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.

Keywords with Joel

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.

Syntax ideas

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.

Remaining work

• Finish defining the core generic functions in KLOS and write tests for them.
• Make (singleton ...) classes work
• Add standard method combinations (before, after, around)
• Run Eddy test suite in Kawa + KLOS

Eddy, Kiwi and Juice: oh my!

The conversations I had with Carl, Darius and Joel this week have helped me form a clearer picture of the spread of projects ahead.

Kiwi

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:

• Keyword and Optional Arguments in PLT Scheme (Flatt, Barzilay, 2009)
• An Efficient Implementation of Multiple Return Values in Scheme (Ashley & Dybvig, 94).
• Binding as Sets of Scopes (Flatt, 2016)
• Fixing letrec (Dybvig, 2005, 2009)

Also Manuel’s work on Delimited Continuations inLispX is also a thing to implement.

Eddy

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:

• an R7RS Scheme (multiple values, module system, …)
• CLOS classes, generic functions and methods,
• pervasive support keyword arguments
• support for control operators like 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.

KLOS

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:

• Dylan-like syntax (define-class, define-method, keyword arguments)
• Turn make into a generic function, i.e. understand / streamline the differences between the TinyCLOS MOP and Dylan.
• Method specializers

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:

1. How do you represent instances and entities?

• 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

2. 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.

3. 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.

Juice

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.