Issues with mutable/immutable lists

[jasonmacduffie]

Hi, this may be outside the scope of what you are doing. But I am trying to port some programs I wrote in portable R7RS, and they break because of importing (srfi 1) which assumes all lists are immutable. However in this library they are all mutable.

I don't know if there is a solution to this, but I lose a lot of value from this if I cannot use srfi libraries portably :(

[johnwcowan]

I recommend that you resolve this by using Racket pairs instead of mpairs, and simply noting that set-car! and set-cdr! are not supported in #lang r7rs. It's not perfect from a portability perspective, but it clearly provides better interaction between R7RS and the rest of the Racket libraries. This also provides better results when dealing with rest arguments in R7RS functions, since they are presumably Racket pairs rather than mpairs.

[lexi-lambda]

Hmm, yes, that is a little bit problematic, isn’t it? The R7RS spec reserves the srfi library namespace, so it would at least be semi-feasible to provide some sort of automatic glue between all the SRFI libs (or at least the common ones). Fundamentally, there is an annoying interoperability problem here. It might be feasible to create a sort of magical interop that converts immutable lists to mutable ones and back again across module boundaries, but that sounds costly, hard to do right, and inconvenient to implement.

I’m not much of a Scheme programmer myself, so I really don’t know how often set-c(a|d)r! actually get used in the world of Scheme, but it seems like poor form to just completely disallow them in Racket. Of course, if they really aren’t used much, and they would actually improve interoperability, I might consider it.

[jasonmacduffie]

I would say mutable pairs are VERY infrequently used in Scheme. One or two programs may be broken by the loss of set-car! and set-cdr!, but many more would be broken without access to common SRFIs. Some other non-SRFI libraries in Racket also probably assume the use of immutable pairs. So, priority-wise, I would say making all pairs immutable makes this more practical than any other option and with the least amount of effort.

[johnwcowan]

I agree: the whole reason Racket was able to move from mutable to immutable pairs was that pair mutation was very rare.

[johnwcowan]

I have more than 50 Schemes on my system, which of course ship with a fair amount of Scheme code. There are 8740 files of code containing over 2.5 MLOC. Of these, 2514 files contain references to set-car! or set-cdr!. However, there are a total of only 9.8 KLOC, or 0.4% with such references. So it's safe to say that while files containing pair mutations are common, actual mutations are not, and I would guess that many of them can be easily removed.

[lexi-lambda]

Those statistics are very helpful, thank you. The reason I am reluctant to compromise on this issue is that the goal of this package is to implement R7RS, not “R7RS with caveats”. Interop with the Racket module system has so far been a point of difficulty, but I think the current solution is a solid compromise that does not seem to affect existing programs in any significant way.

Racket no longer calls itself Scheme for a reason, and the Racket ecosystem has, in large part, moved on. The vast majority of Racket code makes heavy use of Racket-specific features. The goal of writing portable Scheme seems to have largely been abandoned within the Racket world. With this in mind, you may be able to understand that I do not think this package is either terribly critical or necessarily useful to a Racketeer (there seem to be very few Scheme libraries that a Racket programmer might feasibly want to use). From a Schemer’s point of view, calling out to other Racket code also seems fairly unlikely—if you are writing portable Scheme, then using Racket’s libs will involve writing glue code anyway, and if you aren’t writing portable Scheme, then why not just use #lang racket?

Indeed, my perspective on this project is really more about completeness for completeness’s sake: Racket already has R5RS and R6RS implementations... why not R7RS? From that particular perspective, it should be obvious that sacrificing implementation accuracy to improve interoperability is something of a counterproductive attitude. Now, that attitude may be totally misguided—if you think that improved interoperability is useful to some group of people, please explain to me why! I’m very open to hear perspectives from the Scheme side of things rather than the Racket one.

More to the point, I do view Scheme programs that run on most other Scheme implementations but not on this one to be a bug in my implementation, so @Taknamay’s point about SRFI incompatibility seems like a very reasonable one. My inclination would still to be to just make the common SRFIs work with R7RS by special-casing (srfi n) imports and replacing them with versions that use mutable pairs. This is much more inline with my goal of implementation accuracy over interoperability, so again, I can be convinced otherwise. But that’s the direction I’m currently leaning.

[johnwcowan]

I think there are two main use cases for this implementation other than "because it's there".

1. Developing code on Racket using its unsurpassed debugging facilities which you intend to deliver on some other Scheme platform. Examples would be Guile for server or desktop embedding, Chibi for device embedding or Plan 9, Kawa for the JVM, Chicken for final delivery as C, or Stalin (after passing it through the R7RS syntax expander now being developed) for extreme performance. For this purpose, a fully compliant R7RS is desirable but not typically essential, especially for a rarely-used feature. Some of these Schemes, notably Chicken, are only "R7RS with caveats" anyway, although different ones.

2. Importing arbitrary portable R7RS libraries to the Racket platform with minimum friction. Granted, there aren't very many such libraries yet, but one of the principal purposes of R7RS-small was to make it easy to write them and allow existing implementations to import them. I hope to see many more in future, notably including most of the R7RS-large libraries. For this purpose, I think interoperability is much more important than 100% compatibility. If libraries using pair mutation can't be imported on Racket without modification, that is far better than having to translate between two different representations of lists at the boundary, especially if that boundary winds up being crossed multiple times such that the O(n) copies are very time-consuming. That puts R7RS libraries essentially behind an FFI, without the compensating advantages for which FFIs are normally used, performance and direct access to the OS.

Given the potential importance of the second purpose, and the relative flexibility of the first, I hope you'll reconsider, or at least provide a configuration switch to make it easy for the developer to choose.

[lexi-lambda]

Those are both valid points, though I am unsure that Racket’s debugging facilities are really all that fantastic, and as you mention, there are not currently many R7RS libraries a Racket programmer might want to use. However, I want to be an optimist and believe that will change, so I am willing to accommodate that need if possible.

Would it be better to have two languages, #lang r7rs and #lang r7rs/strict or something like that? It is unfortunate that whichever one is chosen as the default will truly be the default and will need to be opted-out of, since the #!r7rs will use that default language. I do not want to sacrifice conformance if possible, especially when having a conformant implementation is possible, but the desire for smooth interop is a valid one. I would ask the Racket mailing list for further guidance, but I worry that most Racket users would be relatively dismissive of this particular issue and wouldn’t care. Perhaps I am just paranoid, though.

[johnwcowan]

Take my word for it: Racket has the best integrated development system in the Scheme world. The alternatives are kludges, and I'm not even a Racket user. Otherwise there is usually just a nested REPL and a few gdb-ish commands, or even nothing at all, just printing an error message and falling back to the top-level REPL.

Two languages is fine with me. I don't think there's any question of a default, because R7RS-small deliberately does not standardize any marker such as #!r7rs. For R7RS-large I intend to propose a facility somewhat similar to Racket's #lang, though probably in a syntactically incompatible way.

I think you're right that most Racket users (and certainly Racket developers) don't care anything about R7RS at present, so it's completely up to you.

[jasonmacduffie]

For what it is worth, I think two languages is a good idea as well.

[lexi-lambda]

Alright, I have had time to give this some actual thought, and it seems like two languages is probably the way to go. The question remains what these languages should be called. There are a few possibilities:

1. Create #lang r7rs/interop or similar, which reduces compliance to increase compatibility with Racket, and leave #lang r7rs as-is.
2. Change #lang r7rs to the less compliant version and create #lang r7rs/strict, which adheres as closely to the standard as possible.
3. Drop #lang r7rs entirely and create two new languages to avoid any default.

Currently, option 2 seems the most appealing to me. Any opinions?

[jasonmacduffie]

Option 2 is my preference. Option 3 and 1 also seem totally fine to me, with a slight leaning towards 3.

NOTE:

As a way around this, people can momentarily use this import statement:

(only (rename (racket base) (list ilist)) ilist)
(only (compatibility mlist) mlist->list)

That will let you integrate Racket libraries with R7RS code without too much pain. This is what I am doing for now.

[samth]

@lexi-lambda I've worked some (but not finished) on an r6rs-immutable library, which would be like r6rs but without mutable pairs, to make it easier to reuse useful R6RS code.

[rain-1]

set-car!/cdr! is very useful to me. It would not be possible to run existing code I've written in racket r7rs mode without them.

We just need import srfi-1 to import a mutable version of the srfi.

I am fine with the idea of having 2 languages, #lang r7rs would support mutable pairs and r7rs-immutable not.