Chez Scheme as the Racket VM

[Matthew Flatt]

TL;DR: I expect the main Racket distribution to run on Chez Scheme
instead of the current Racket VM sometime in the next couple of years.


Background
----------

The core Racket implementation relies on a lot of C code, and that's
a problem for maintenance, for porting it to new platforms (say,
JavaScript), and for improving performance.

My long-term plan has been to rewrite it all in Racket (except for
things like GC). Last summer, I started by rewriting Racket's macro
and module system from scratch. Although I was able to get a fresh
implementation working, the new implementation's performance was not
good enough to drop in as a replacement for our current
implementation.

After making sure that the new expander is really working with data
structures and algorithms that are at least as good as the old ones,
the new implementation is still off by up to a factor of two in time
and 25% or so in space. I'm convinced that Racket's compiler and
runtime system will have to be better to support a reimplementation of
the core in Racket.

Although I have specific ideas on how the current Racket VM could be
improved, there are already other compilers and runtime systems that
perform better. Notably, Chez Scheme has recently become available
under an open-source license (Apache).

As a first experiment, I have been able to use the new Racket expander
to compile a new Racket regexp implementation to run on Chez. As
expected, Chez runs the matcher about 2 times as fast as Racket,
putting it generally on par with the C implementation that's currently
built into Racket.

So far, so good. After more experiments along these lines, I see no
scenario where it's easier or more effective to improve Racket than to
build on Chez. Although there are some mismatches between the primitive
features that Chez and Racket provide, it will mostly work; in rare
cases where there's no other solution, we can contribute pull requests
to Chez.

A Racket on Chez won't be compatible with the current Racket VM at the
level of the C API. For that reason and others, I expect the current
Racket VM to stick around for projects that use the C API, that need
to embed Racket, or so on. The goal of rewriting Racket in Racket has
always been to support multiple VMs, so there's no conflict with
keeping the current Racket VM, too. Other VM efforts, like Pycket and
RacketScript, should also benefit. Still, I expect mainline Racket
development to move to Chez as the primary backend.

This shift in direction will affect many projects planned to use or
improve Racket. Although I expect to implement most of the conversion
myself, I've talked with others who are invested in the current Racket
direction. So far, everyone seems to be on board.

Rewriting the Racket core has always seemed prohibitively difficult
and time-consuming, but I think now's the time, especially with the
expander and module system out of the way. The other subsystems look
easy compared to the part that is done, but there's plenty of room for
surprises.


Status
------

I've reimplemented the Racket expander, reader, and regexp matcher in
Racket, and I've started on the port and filesystem path subsystems.
The new subsystem implementations have been developed in the "linklet"
branch here:

https://github.com/mflatt/racket/tree/linklet

See "expander" and "regexp" in the "pkgs" directory, for example. I
expect this branch to eventually move to a branch or repo in the
"racket" account on GitHub.

Here's my work-in-progress toward making Racket reimplementations run
on Chez:

https://github.com/mflatt/not-a-box/

For example, you can run the regexp implementation in Chez and compare
to Racket's using its built-in regexp implemenation in C or to Racket
running the new regexp implementation.


Plan
----

My immediate plan is to make Racket's reader + expander + module
system run on Chez. It could be two weeks or two months. From there,
I'll continue rewriting all of the Racket subsystems in Racket,
compiling them down to layers of Chez. See "README.txt" in the
"not-a-box" repo for a status report and thoughts on various Racket
subsystems.

When the current Racket VM becomes the legacy Racket VM, I expect that
it will retain most of its C implementation, which means that it will
keep its performance for backward compatibility. Even this legacy VM,
however, will use the new reader, expander, and module system ---
essentially as the linklet branch is now. The expander performs well
enough to be practical without affecting the runtime performance of
the programs that it expands.

Currently, I see no obstacle to getting everything running on Chez by
the end of the year, but we'll see how it goes.

[Matthew Butterick]

> On Feb 15, 2017, at 7:07 AM, Matthew Flatt <mfl...@cs.utah.edu> wrote:
>
> My immediate plan is to make Racket's reader + expander + module
> system run on Chez. It could be two weeks or two months. From there,
> I'll continue rewriting all of the Racket subsystems in Racket,
> compiling them down to layers of Chez. See "README.txt" in the
> "not-a-box" repo for a status report and thoughts on various Racket
> subsystems.

I am very grateful for your grand plans and epic efforts to continue improving Racket for everyone. Thank you.

[John Clements]

> On Feb 15, 2017, at 7:07 AM, Matthew Flatt <mfl...@cs.utah.edu> wrote:
>

> TL;DR: I expect the main Racket distribution to run on Chez Scheme
> instead of the current Racket VM sometime in the next couple of years.
>

Yikes! Exciting!

> A Racket on Chez won't be compatible with the current Racket VM at the
> level of the C API. For that reason and others, I expect the current
> Racket VM to stick around for projects that use the C API, that need
> to embed Racket, or so on. The goal of rewriting Racket in Racket has
> always been to support multiple VMs, so there's no conflict with
> keeping the current Racket VM, too. Other VM efforts, like Pycket and
> RacketScript, should also benefit. Still, I expect mainline Racket
> development to move to Chez as the primary backend.

You mention incompatibility at the level of the C API. I read that three or four
times before deciding that this isn’t about those writing Racket packages
that use FFI to interact with C libraries, but rather those rare packages
that want to use Racket’s C API to interact with Racket. Is this correct?

John

[Matthew Flatt]

At Wed, 15 Feb 2017 11:40:20 -0500, "'John Clements' via Racket Developers" wrote:
> > A Racket on Chez won't be compatible with the current Racket VM at the

> > level of the C API. [...]

>
> You mention incompatibility at the level of the C API. I read that
> three or four times before deciding that this isn’t about those
> writing Racket packages that use FFI to interact with C libraries,
> but rather those rare packages that want to use Racket’s C API to
> interact with Racket. Is this correct?

That's right. I expect Racket's FFI to mostly work as a layer on Chez's
FFI, so most Racket programs that use `ffi/unsafe` can continue to work.

[James Swaine]

How does this impact things that cannot work without special modification to the runtime system like places and futures?

--
You received this message because you are subscribed to the Google Groups "Racket Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+...@googlegroups.com.
To post to this group, send email to racke...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/20170215164752.39C97650090%40mail-svr1.cs.utah.edu.
For more options, visit https://groups.google.com/d/optout.

[Alexander McLin]

Fascinating! And thank you for the detailed write-up.

It'll be exciting to see the progress of the epic rewrite. Also +++ for being able to build on Dybvig's magnificent legacy.

On Wed, Feb 15, 2017 at 3:49 PM, James Swaine <james....@eecs.northwestern.edu> wrote:

How does this impact things that cannot work without special modification to the runtime system like places and futures?

On Wed, Feb 15, 2017 at 10:47 AM Matthew Flatt <mfl...@cs.utah.edu> wrote:

At Wed, 15 Feb 2017 11:40:20 -0500, "'John Clements' via Racket Developers" wrote:
> > A Racket on Chez won't be compatible with the current Racket VM at the
> > level of the C API. [...]
>
> You mention incompatibility at the level of the C API. I read that
> three or four times before deciding that this isn’t about those
> writing Racket packages that use FFI to interact with C libraries,
> but rather those rare packages that want to use Racket’s C API to
> interact with Racket. Is this correct?

That's right. I expect Racket's FFI to mostly work as a layer on Chez's
FFI, so most Racket programs that use `ffi/unsafe` can continue to work.

--
You received this message because you are subscribed to the Google Groups "Racket Developers" group.

To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+unsubscribe@googlegroups.com.

To post to this group, send email to racke...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/20170215164752.39C97650090%40mail-svr1.cs.utah.edu.
For more options, visit https://groups.google.com/d/optout.

--

You received this message because you are subscribed to the Google Groups "Racket Developers" group.

To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+unsubscribe@googlegroups.com.

To post to this group, send email to racke...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/CAEkQqGS-TsdUgq23K54RO4-cOs8abVh5R-Ahvfga-D2E8W1yrA%40mail.gmail.com.

[Matthew Flatt]

I've added a note to not-a-box/README.txt about futures: Chez exposes
OS-level threads with limited safety guarantees. An implementation of
futures can probably take advantage of threads with thread-unsafe
primitives wrapped to divert to a a barrier when used in a future.

In other words, while we made futures work for Racket by ensuring that
various future-safe primitives specifically cooperate, it looks like we
can do the opposite on Chez: wrap future-unsafe primitives
specifically. If that works, no changes are needed to Chez.

Places probably "just work" by using OS-level threads and not sharing
data among places.

[Alexis King]

I second other voices that this is both fascinating and exciting. Your
technical efforts are always inspiring and much appreciated, and your
detailed transparency around them perhaps even more so. These sorts of
things are always extremely interesting to read.

I have a question to add, myself: if people such as me are interested in
helping with the port, is there anything we can do? I would understand
if this is the sort of project that would be slowed down by too many
hands on deck, rather than sped up, especially for people who are
physically distant from you and virtually distant from the relevant
code. Still, if there are things that those familiar with Racket but
unfamiliar with the core could help with, I’d definitely be interested
in offering some of my time.

[Matthew Flatt]

At Wed, 15 Feb 2017 15:08:38 -0800, Alexis King wrote:
> I have a question to add, myself: if people such as me are interested in
> helping with the port, is there anything we can do?

That's a good question, and I don't have a good answer right now. Maybe
the best answer is that my failure to answer that question is a
motivation for the project: to put Racket's base on a better footing
where more people can contribute. That's why I hope and expect to have
a better answer eventually.

[zolta...@gmail.com]

I'm quite new to the world of Racket, and this made for some nice reading! If I understand it correctly, this will be quite a massive change. I'm sure a lot of folks, including myself will be happy to pitch in whichever way we can (documentation, testing, coding, etc.) in this process!

[Matthew Butterick]

On Feb 15, 2017, at 8:03 PM, Matthew Flatt <mfl...@cs.utah.edu> wrote:

At Wed, 15 Feb 2017 15:08:38 -0800, Alexis King wrote:

I have a question to add, myself: if people such as me are interested in
helping with the port, is there anything we can do?

That's a good question, and I don't have a good answer right now. Maybe
the best answer is that my failure to answer that question is a
motivation for the project: to put Racket's base on a better footing
where more people can contribute.

Perhaps the more productive form of this question would be "what dumb stuff that ordinarily taxes your time can be delegated to others in the Racket community, so that you have more time to work on the Flatt-intensive parts of the project?"

E.g., minor bugfixes, PR reviews, administrative. I'm willing to come to SLC and spend the weekend cleaning your garage if it would help.

[zolta...@gmail.com]

>I'm willing to come to SLC and spend the weekend cleaning your garage if it would help.

Hahaha!

[Matthew Flatt]

At Thu, 16 Feb 2017 07:59:14 -0800, Matthew Butterick wrote:
> Perhaps the more productive form of this question would be "what dumb stuff
> that ordinarily taxes your time can be delegated to others in the Racket
> community, so that you have more time to work on the Flatt-intensive parts of
> the project?"
>
> E.g., minor bugfixes, PR reviews, administrative. I'm willing to come to SLC
> and spend the weekend cleaning your garage if it would help.

:) Thank you of the offer! But that work is already shared.

Instead of the things that I would do anyway, I think it's more helpful
for others to do the things that I wouldn't do --- things like
_Beautiful Racket_ or Hackett.

[Abhinav Sharma]

This is the best thing I've heard this February!!

Yayyy!!!!

On Wednesday, February 15, 2017 at 8:37:19 PM UTC+5:30, mflatt wrote:

[alex.mclin]

Will Racket's internal optimizations be ported over to Chez backend eventually? I frequently see traffic about work being done in on the Racket's optimizer so it's apparent it's an active area of development. Since Racket's semantics include immutable pairs, and Chez doesn't have them, I imagine there are optimization opportunities only available when immutable pairs are assumed. I do note that Chez's compiler is written in Scheme so I figure it would be natural to modify the compiler code or fork it to fold in Racket specifics.

Do you envision in the future exposing Chez' own debugging and inspection tools to the Racket layer?

[Matthew Flatt]

At Fri, 17 Feb 2017 09:02:28 -0800 (PST), "alex.mclin" wrote:
> Will Racket's internal optimizations be ported over to Chez backend
> eventually? I frequently see traffic about work being done in on the
> Racket's optimizer so it's apparent it's an active area of development.
> Since Racket's semantics include immutable pairs, and Chez doesn't have
> them, I imagine there are optimization opportunities only available when
> immutable pairs are assumed. I do note that Chez's compiler is written in
> Scheme so I figure it would be natural to modify the compiler code or fork
> it to fold in Racket specifics.

I expect optimization work to start more or less afresh on Chez. We've
built up some experience, and we can compare to what Chez already does
--- and, just maybe, we'll be able to contribute some generally useful
improvements to Chez in the long run.

> Do you envision in the future exposing Chez' own debugging and inspection
> tools to the Racket layer?

Yes.

[Adeoluwa Adejumo]

not sure exactly how helpful this is but there is Nim programming language https://nim-lang.org/docs/backends.html

Compiles to (C, C++, Objective C, JavaScript)
Efficient GC that can be turned off
Macros
Interop with C/C++, Python, Lua Libraries
Python syntax
Plans to run on JVM & CLR at some point in time

new languages written in Nim can automatically get those benefits
e.g Mr Goran is working on a smalltalk+rebol like language (spry lang) and its VM can be compiled to JS and run in the browser

again none of this makes perfect sense to me yet am new to programming (python & racket) but thought it might be useful to you.

[Laurent]

Wow, what a change. I'm impressed that this is at all possible. 

Do you expect the GUI part to cause any problem? 

Apart from the rewriting, will Chez bring some new features to Racket?

And could Chez benefit from some of Racket's features?

--
You received this message because you are subscribed to the Google Groups "Racket Developers" group.

To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+unsubscribe@googlegroups.com.

To post to this group, send email to racke...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/58a46ea7.833f620a.71e85.e2caSMTPIN_ADDED_MISSING%40gmr-mx.google.com.

[Matthew Flatt]

At Sat, 18 Feb 2017 07:53:13 -0800 (PST), Adeoluwa Adejumo wrote:
> "The core Racket implementation relies on a lot of C code, and that's
> a problem for maintenance, for porting it to new platforms (say,
> JavaScript), and for improving performance. "
>
> not sure exactly how helpful this is but there is Nim programming language
> https://nim-lang.org/docs/backends.html

Thanks! I've heard of Nim, and a language like Nim or Rust might
conceivably we the way to go if it was just a matter of moving C code
to a better languages. But, of course, we want to generally move things
to Racket specifically. Meanwhile, Chez provides a temendous amount of
infrastructure that we need related to GC and compiling and running
code interactively.

[Abhinav Sharma]

Definitely agreed with the moving more parts to racket. It makes things much more exiting and approachable.

--
You received this message because you are subscribed to a topic in the Google Groups "Racket Developers" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/racket-dev/2BV3ElyfF8Y/unsubscribe.
To unsubscribe from this group and all its topics, send an email to racket-dev+unsubscribe@googlegroups.com.

To post to this group, send email to racke...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/58a8e3a1.1716620a.cb4c1.27cdSMTPIN_ADDED_MISSING%40gmr-mx.google.com.

[Matthew Flatt]

[Sorry for the delay. I just discovered that I forgot to hit "Send"
here.]

At Sat, 18 Feb 2017 17:13:59 +0000, Laurent wrote:
> Do you expect the GUI part to cause any problem?

I expect that to be relatively easy, because Racket's FFI looks enough
like Chez's, but we'll see.

> Apart from the rewriting, will Chez bring some new features to Racket?

I hope that Chez's debugging and inspection facilities will quickly
lead to better debugging tools for Racket.

> And could Chez benefit from some of Racket's features?

I can't help thinking that Racket *is* the benefit for Chez users. :)

More directly, if we end up creating pull requests for the rare new
feature that Racket needs from Chez, I hope those new features would be
worthwhile for Chez users.

[Abhinav Sharma]

Chez gets to have a package manager for a start.

--
You received this message because you are subscribed to a topic in the Google Groups "Racket Developers" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/racket-dev/2BV3ElyfF8Y/unsubscribe.
To unsubscribe from this group and all its topics, send an email to racket-dev+unsubscribe@googlegroups.com.

To post to this group, send email to racke...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/58ac5531.8883620a.f8f19.b0b9SMTPIN_ADDED_MISSING%40gmr-mx.google.com.

[vasp...@gmail.com]

Fantastic!

That means in future Racket become full in Apache License 2.0/MIT licenses? (Racket VM in C using GNU lightning, GNU GMP, but this VM in Chez Scheme don't use these libraries?) - https://github.com/racket/racket/issues/1570

And about new platforms how about *BSD (NetBSD, OpenBSD, FreeBSD, DragonflyBSD) support?

Maybe Racket implementation in Chez Scheme open more possibilities to get Racket in the mobile devices (iOS, Android), although only just for OpenGL development like Go language have mobile package?  - https://github.com/cisco/ChezScheme/issues/85

Sorry for my low English language skills, Thanks.

[Jay McCarthy]

On Wed, Feb 22, 2017 at 7:00 PM, <vasp...@gmail.com> wrote:
> Fantastic!
>
> That means in future Racket become full in Apache License 2.0/MIT licenses?
> (Racket VM in C using GNU lightning, GNU GMP, but this VM in Chez Scheme
> don't use these libraries?) - https://github.com/racket/racket/issues/1570

The two decisions were made independently, but clearly there's some synergy.

> And about new platforms how about *BSD (NetBSD, OpenBSD, FreeBSD,
> DragonflyBSD) support?
>
> Maybe Racket implementation in Chez Scheme open more possibilities to get
> Racket in the mobile devices (iOS, Android), although only just for OpenGL
> development like Go language have mobile package? -
> https://github.com/cisco/ChezScheme/issues/85

Racket on Android with OpenGL exists:
https://github.com/jeapostrophe/racket-android/

The same approach would be "easy" to do on iOS

Jay

> --
> You received this message because you are subscribed to the Google Groups
> "Racket Developers" group.

> To unsubscribe from this group and stop receiving emails from it, send an

> email to racket-dev+...@googlegroups.com.

> To post to this group, send email to racke...@googlegroups.com.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/racket-dev/0ab8fecd-cae7-4079-a545-22a8986e7d0b%40googlegroups.com.

>
> For more options, visit https://groups.google.com/d/optout.

--
-=[ Jay McCarthy http://jeapostrophe.github.io ]=-
-=[ Associate Professor PLT @ CS @ UMass Lowell ]=-
-=[ Moses 1:33: And worlds without number have I created; ]=-

[Jens Axel Søgaard]

2017-02-15 16:07 GMT+01:00 Matthew Flatt <mfl...@cs.utah.edu>:

TL;DR: I expect the main Racket distribution to run on Chez Scheme
instead of the current Racket VM sometime in the next couple of years.

This is is exciting news. Getting rid of the C portion of the source will

hopefully make the foundation of Racket both more flexible and more
approachable.

A technical issue: How do you plan to implement continuation marks?

I see several options:

  i) adding continuation marks to Chez (tricky)

 ii) pass continuation marks along each function call using an extra argument (expensive)

iii) code transformation (expensive?)

Since Chez is "friendly" (provides TCO) is it possible to use a code transformation 

without a performance hit?

/Jens Axel

[Matthew Flatt]

At Thu, 23 Feb 2017 10:04:16 +0100, Jens Axel Søgaard wrote:
> A technical issue: How do you plan to implement continuation marks?
>
> I see several options:
>
> i) adding continuation marks to Chez (tricky)
> ii) pass continuation marks along each function call using an extra
> argument (expensive)
> iii) code transformation (expensive?)
>
> Since Chez is "friendly" (provides TCO) is it possible to use a code
> transformation
> without a performance hit?

Here's a sketch of how a `call/cm` function could work, relying on the
way that `eq?` works for detecting equivalent continuations in Chez:

(define (call/cm key val proc)
;; For this sketch, assumes `key` is always the same
(call/cc
(lambda (k)
(if (and (pair? stack)
(eq? k (caar stack)))
(begin
(set-cdr! (car stack) (cons key val))
(proc))
(begin0
(call/cc
(lambda (k)
(set! stack (cons (cons k (cons key val))
stack))
(proc)))
(set! stack (cdr stack)))))))

This approach causes the continuations that appear at the Racket level
to *not* be `eq?` when they're the same, because a continuation mark
can insert an extra frame (but only one per frame that would exist
otherwise). That loss seems ok, because Racket doesn't currently
provide an equality check on continuations.

Besides making `with-continuation-mark` expand to call `call/cc`, all
the other control operators, like `call/cc` and `dynamic-wind`, need to
be wrapped to cooperate with it. Those wrappers are going to happen,
anyway, to implement delimited control.

My tests suggest that this approach runs just a little slower than
continuation marks in Racket (which are deeply built in), and that's
good enough to get started. Longer term, I think something like this
approach could work and perform better as built into Chez; I've
experimented with that, but not conclusively.

[Gustavo Massaccesi]

I have been looking at some of the optimizations, and I found a few
interesting differences.


*** Chez may reorder expressions.

(car (list (display 1) (display 2))) ;==> 21#<void>

I think this is ok in RNRS and Chez, but it may cuase a problem for a
program translated directly from Racket. I think that all the reorders
are in the optimization phase, but I'm not sure.



*** Chez has only one vector of length 0

(eq? (vector) (make-vector (* 0 (random 7)))) ; ==> #t

This is not an optimization, but a property of the internal system. I
actually like it.

It's not very useful for vectors, but it looks like a something useful
for strings.

(eq? (string) "") ; ==> #t

I think that this is one of the small details that have to be fixed,
but the change looks like a good idea for Racket2. [But the extended
version of (eq? (vector) (vector-immutable)) is something that I
prefer to keep #f.]


Gustavo

[Matthew Flatt]

At Fri, 24 Feb 2017 16:02:45 -0300, Gustavo Massaccesi wrote:
> *** Chez may reorder expressions.
>
> (car (list (display 1) (display 2))) ;==> 21#<void>
>
> I think this is ok in RNRS and Chez, but it may cuase a problem for a
> program translated directly from Racket. I think that all the reorders
> are in the optimization phase, but I'm not sure.

Right --- The "schemify" pass at

https://github.com/mflatt/not-a-box

rewrites applications for fully expanded Racket programs. It uses
nested `let`s as necessary to enforce left-to-right evaluation (and the
optimizer surely preserves that ordering).

A `let` form with multiple binding clauses similarly has to be
rewritten to nested `let`s`. There's a subtlety related to variable
allocation and potential continuation capture, but the rewrite pass
addresses that.

[Jens Axel Søgaard]

That's quite elegant!

> My tests suggest that this approach runs just a little slower than
> continuation marks in Racket (which are deeply built in), and that's
> good enough to get started. 

Good to hear - I was somewhat worried that call/cc might be too slow

for this purpose.

> Longer term, I think something like this
> approach could work and perform better as built into Chez; I've
> experimented with that, but not conclusively.

/Jens Axel

2017-02-23 13:02 GMT+01:00 Matthew Flatt <mfl...@cs.utah.edu>:

At Thu, 23 Feb 2017 10:04:16 +0100, Jens Axel Søgaard wrote:

> A technical issue: How do you plan to implement continuation marks?
>
> I see several options:
>
>   i) adding continuation marks to Chez (tricky)
>  ii) pass continuation marks along each function call using an extra
> argument (expensive)
> iii) code transformation (expensive?)
>
> Since Chez is "friendly" (provides TCO) is it possible to use a code
> transformation
> without a performance hit?

--

--
Jens Axel Søgaard