Fixes GitHub #103, and a bug in FSet/Jzon.

FSet v2.3.0 adds transients, which improve performance when initially populating a collection, especially a large one. Transients are available for the CHAMP types: ch-set, ch-map, ch-2-relation, ch-replay-set, and ch-replay-map. See the MR for details.

Yikes! I really screwed up on the v2.1.0 release — didn't test it thoroughly. And I only just now noticed the bugs, after Zach Beane released a new Quicklisp.

The bugs are all in the seq code, so if you don't use seqs much, you may not see them. Nonetheless, I recommend pulling down the latest version from this site. (Clone under ~/quicklisp/local-projects/ to automatically shadow the version in Quicklisp.)

The new seq optimizations in v2.1.0 were not as well tested as they should have been. The bugs mostly show up as type errors, except that the splice operation could return an invalid tree. I have improved the test suite and fixed the bugs it turned up.

This release adds a new system, FSet/Jzon, wrapping the Jzon JASON parser/printer. For more info see the MR.

It also reverts the map and seq default printing behavior to be like FSet 1 in that a nil default is not printed. If there is no default, a case introduced in FSet 2, the map or seq's printed representation is followed by /[no default]. Examples:

> (in-package :fset2-user)
#<PACKAGE "FSET2-USER">
FSET2-USER> (map)
##{| |}
FSET2-USER> (map :default nil)
##{| |}     ; same value as for (map)
FSET2-USER> (map :default "")
##{| |}/""  ; non-nil defaults are printed after '/'
FSET2-USER> (map :no-default)
##{| |}/[no default]
FSET2-USER> (seq)
#[ ]
FSET2-USER> (seq :default nil)
#[ ]        ; same value as for (seq)
FSET2-USER> (seq :default 0)
#[ ]/0
FSET2-USER> (seq :no-default)
#[ ]/[no default]

Previously (for the month or so since FSet 2 was released), the no-default case would print nothing, and a nil default would print as /NIL. Besides the obvious rationale of greater consistency with FSet 1, this reversion removes the visual clutter of having /NIL appear after almost every map or seq, and makes it more obvious when a map or seq actually has no default, which is not a very common case.

Fixes GitHub #97. The new CHAMP collections are printed starting with ## (since these are hash-based, I joke that the first # is pronounced "sharp" and the second is pronounced "hash"), and so I added reader functions to the FSet readtables to read this syntax. However, the way I did it broke CL's ability to read back structure printed with *print-circle*, that contains back-references in the form #n#. This is now fixed.

FSet 1 exported map-default, which is an accessor for structure class map. For FSet 2, I wanted to switch people over to default, which is a generic function that works on both maps and seqs, so I removed map-default from the exports for both the fset and fset2 packages. But this caused Quicklisp breakage, so I'm restoring the export from fset (not fset2).

I had forgotten to export char-seq?. See v2.1.0.

This release is mostly to add some performance and functionality improvements for seqs. I'll summarize first, then give details:

• Access to and updating of elements at the beginning or end of a long seq is now faster.
• I have finally gotten around to implementing search and mismatch on seqs. NOTE: this may require changes to your package definitions; see below.
• Seqs containing only characters are now treated specially, making them a viable replacement for CL strings in many cases.
• In an FSet 2 context, the seq constructor macros now permit specification of a default.
• There are changes to some convert methods.
• There are a couple more FSet 2 API changes, involving image.

Head/tail optimization

Seqs of over a threshold size (currently 32) now keep head and tail vectors, attached to the root. This considerably speeds up first, last, with-first, with-last, less-first, and less-last on long seqs. The speedup on with-first or with-last varies from around 1.5x at size 128, to 2x at 256, to 3.3x at 2048, to 4.3x at 65536, to 4.6x at 524288; it doesn't get much better after that.

(Seqs are performance-symmetrical; it doesn't matter which end you use.)

Also, the performance of image on a seq has been improved.

search and mismatch on seqs

These have been on my to-do list since, ah, 2008 😊 But no one has ever asked for them. They forward to the CL primitives, as usual, if invoked on CL sequences. They don't accept the :test-not keyword argument, which was deprecated in ANSI CL, but are otherwise compatible.

NOTE: if you have any package definitions that :use :fset or :use :fset2, you will need to add shadowing-imports for search and mismatch — either from :fset/:fset2, or from :cl if you don't want the FSet versions.

Char-seqs

There is now a concept of a "char-seq", which is a seq containing only characters. This property is tracked internally, so that the new method char-seq? runs in O(1) time. Char-seqs print like #"foo", that is, just like strings with a preceding #. The FSet custom readtables (does anybody use these?) also now accept this syntax. If you print a char-seq with escaping disabled (both *print-escape* and *print-readably* bound to false, e.g. using the ~A directive of format) then only the contents are printed. Examples:

> (convert 'seq "mum\\ble")
#"mum\\ble"
> (format t "->~A<-" *)
->mum\ble<-
NIL

Internally, seqs are represented as balanced binary trees of short vectors. The implementation now guarantees that if all the elements of a leaf vector are characters, the vector is a string; and on implementations such as SBCL in which base-char is a distinct type from character, the implementation further guarantees that if all the elements of a leaf vector are base-chars, the vector is a base-string. While there is still some space overhead for the interior tree nodes, using a seq to hold a string is acceptably space-efficient for most purposes. Also, a seq that is mostly characters, but has maybe 1% or 2% non-characters, is still stored relatively space-efficiently, because only those leaves with non-characters need to be simple-vectors.

Also, even if a seq contains non-characters, runs of at least 4 consecutive characters within it are printed as strings preceded by #$ (indicating that the string is not itself an element of the seq, but is considered to be spliced into it). This makes seqs consisting mostly, but not entirely, of characters, more readable. For example:

> (seq 'a ($ "xyzzy") 'b)
#[ A #$"xyzzy" B]/NIL
> (size *)
7
> (@ ** 2)
#\y

FSet 2 seq constructor macros accept defaults

The fset2:seq and fset2:wb-seq constructor macros now let you include :default <value> or :no-default to specify the default or absence thereof, like the map constructor macros. There's a slight complication in this case, because you might want to make a seq containing one of these keyword symbols; you can do that by quoting it. (That is, the presence of these keywords is checked for at macroexpansion time, not runtime; if a subexpression happens to evaluate to one of them, it will still be treated as an element.)

I have restricted this change to FSet 2 because it is technically an incompatible change, even if the odds of actually biting anyone seem small.

Examples:

> (in-package :fset2-user)
#<PACKAGE "FSET2-USER">
> (seq 3 17)
#[ 3 17 ]/NIL
> (seq 3 17 :default 0)
#[ 3 17 ]/0
> (seq 3 17 :no-default)
#[ 3 17 ]
> (seq 3 17 ':default)
#[ 3 17 :DEFAULT ]/NIL

Changes to convert methods

Some errors and omissions in the convert main doc string (the one in the defgeneric form) have been fixed.

Conversions to a map or seq type now all accept :default to set or override the default; in FSet 2, they also accept :no-default? to remove it.

In FSet 2, conversions between seqs and maps no longer retain the default. They did in FSet 1, but I now regard this as a design error; the range type of the map is usually different from the element type of the seq. (Additionally, map-to-seq conversions had it backwards in v2.0.0: they discarded the default in FSet 1, but retained it in FSet 2; this is fixed.) (Map-to-map conversions still retain the default, unless explicitly overridden).

(convert 'map-to-sets <2-relation>) now returns a map whose default is an empty set of the appropriate type.

FSet 2 API changes involving image

There is a semantic change to fset2:image on a seq: if the seq has a default, the result's default will be computed by calling the supplied function (the first argument to image) on it. (Previously, the default was taken from the keyword arguments :default and :no-default?.)

Related to that, there is one more incompatible API change in the fset2 package. The methods on image that specialized the second parameter on a map have been moved to a different generic function, map-image. (Motivation: these methods were the only ones that passed two arguments — a key and its value — to the supplied function, instead of one. That had two consequences: the function couldn't be applied to the default to get a new default, because there was no key available to pass to it; and while the image methods on the other types accept maps, sets, and bags as functions to be applied, the map methods could not. Probably, image on maps should never even have existed — compose is more sensibly defined and, in practice, probably covers all the important use cases — but I don't want to remove them altogether, in case people are using them.)

This release introduces FSet version 2! 🚀 🚀 The big change for v2 is that the CHAMP data structures are now used by default for sets, maps, and a few other types (see the CHAMP MR). There are some other API changes as well, mostly having to do with the treatment of defaults in maps and seqs.

Background: After using FSet myself for a while, I came to feel that the way I had made the map and seq defaults work was in some ways still infelicitous. This especially came out when using map-union, map-intersection, and compose of a map with a function. The inconvenience was that every map had a default, and the lambda expressions I was writing to process the map values were also being called on the defaults, which were generally nil, so those lambda expressions had to handle nil explicitly. I found this inelegant, and decided that FSet should distinguish the case of a nil default from that of not having a default at all. So now, these two cases are distinct.

To minimize disruption to existing clients, I have created a new package fset2: which exports its own versions of the relevant symbols. With some hopefully-minor exceptions noted below, existing clients will not see any changes in semantics. To get the new behavior, change :use fset in your package definitions to :use fset2 (similarly change the :shadowing-import-from fset clause, if you use it) and recompile.

However, one change you will see, even if you're not using the new package, is to the printed representation of maps and seqs. Previously, if the default was nil, no suffix was printed; any other default would be printed after the map or seq, preceded by a slash. Now, in the common case where the default is nil, you will see an explicit /NIL; the suffix is omitted only when there is no default.

The CHAMP-related changes are these:

• The default implementations for set and map are now ch-set and ch-map respectively. The WB versions are still available, of course, for cases when you want the collection to be maintained in a particular order.
• For some less-commonly-used collections — replay-set, replay-map, 2-relation, and list-relation — I have taken the risk of changing them to use CHAMP by default in the fset package, without introducing separate fset2: names. For the replay sets and maps, it's hard to see any reason to prefer the WB implementations, since the iteration order is externally imposed anyway. For the relations, I'm skeptical that anyone uses them but me, though I could be wrong. If this change impacts you, please speak up; I could be persuaded to limit this change to FSet2.

The default-related changes are these:

• Unless you explicitly specify another default, the default for maps and seqs is still nil. However, you can obtain a map or seq with no default by supplying :no-default to the constructor macro (map etc.) or :no-default? t to the constructor function (empty-map etc.)
• Doing lookup on a map with no default, giving a key not mapped by the map, signals an error of class map-domain-error, a subclass of lookup-error.
• An out-of-bounds access on a seq with no default signals an error of class seq-bounds-error; first or last on an empty seq with no default signals an error of class empty-seq-error. Both of these are also subclasses of lookup-error.
• Tuple keys also still have a default of nil. You can create a tuple key with no default by passing :no-default? t to define-tuple-key or get-tuple-key; and doing lookup on a tuple using a key with no default, if the tuple has no value for that key, signals an error of class tuple-key-unbound-error (also a subclass of lookup-error).
• map-union, map-intersection, and compose detect when a map has no default, and avoid calling the passed function on the default in that case. (There is also a change to the default-related behavior of map-difference-2, but this is less important).

Detailed list of changes

Constructor macros set, map, replay-set, replay-map, and 2-relation now construct CHAMP collections.

Constructor macros map, wb-map, wb-custom-map, ch-map, ch-custom-map, replay-map, wb-replay-map, wb-custom-replay-map, ch-replay-map, and ch-custom-replay-map can be made to create a collection with no default by including :no-default somewhere in the argument list.

Constructor functions empty-wb-set, empty-ch-set, empty-wb-bag, empty-map, empty-wb-map, empty-ch-map, empty-seq, empty-wb-seq, empty-wb-replay-set, empty-ch-replay-set, empty-replay-map, empty-wb-replay-map, empty-ch-replay-map, empty-wb-2-relation, empty-ch-2-relation, empty-list-relation, empty-wb-list-relation, and empty-ch-list-relation have all had their parameters changed from optional to keyword parameters. empty-map, empty-wb-map, empty-ch-map, empty-seq, empty-wb-seq, empty-replay-map, empty-wb-replay-map, and empty-ch-replay-map can be made to create a collection with no default by passing :no-default? t.

Generic function without-default can be used to remove the default from a map, seq, or replay-map.

The way map-union, map-intersection, map-difference-2, compose, and image handle defaults has changed:

• For map-union, the previous behavior (since 1.4.0) was to call the supplied val-fn on the defaults for the two maps unless those defaults were both nil. (The pre-1.4.0 behavior was to call val-fn on the defaults unconditionally.) The new behavior is to call val-fn on the defaults only when both maps have defaults; if only one has a default, that becomes the default of the result; if neither map has a default, the result has no default.
• For map-intersection, the previous behavior (both pre- and post-1.4.0) was the same as for map-union. The new behavior is to call val-fn on the defaults only when both maps have defaults; otherwise, the returned map has no default.
• For map-difference-2, the previous behavior was to simply copy the default of each argument map to its respective return value. The new behavior is to do that unless both maps have defaults and those defaults are equal.
• For compose, the previous behavior was to apply the second argument (which can be a map or a function) to the first argument's default. The new behavior is to do that only if the first argument has a default; if it doesn't, the result doesn't either.
• For image where the second argument is a map, the previous behavior is that the result would have the same default as that argument. The new behavior is that the result has no default. (We can't call the function to compute a new default, as might have seemed consistent with these other operations, because in this case, the function is called with both a domain and range value, and there's no specific domain value corresponding to the default. My guess is that this operation, as I've defined it, is not very useful anyway; compose is probably the better choice for most use cases.)

The lookup operation on a bag (most commonly invoked using the @ macro) now returns the multiplicity as its first value, rather than a boolean. (If you want a boolean result, use contains?.)

The name identity-ordering-mixin is no longer exported; it was already deprecated in favor of identity-equality-mixin.

There are some changes related to dynamic tuples. def-tuple-key, which was deprecated in favor of define-tuple-key, is no longer exported. Macro define-tuple-key now has keyword parameters, including no-default?; if a key has no default and a lookup is done with it on a tuple that has no value for that key, an error will be signaled. (The default default is still nil.) The behavior that if the default were a function, it would be invoked on the tuple to compute the value returned by lookup, has been removed. Function get-tuple-key, which can be used programmatically to obtain a tuple key, also now has keyword parameters default and no-default?, and will also now update the default on an existing key (bug fix).

The rank operator takes an ordered collection — here a wb-set, wb-bag, or wb-map — and a value. If the value is in the collection (for a map, if it is a key), then rank returns an integer giving its position within the ordering. You might think that if the value were not in the collection, rank would return the position it would have if it were added; but for some reason I don't recall, I defined it to return one less than that. FSet2 fixes this; rank now returns the position it would have if it were added.

FSet2 now exports functions compare-lists-lexicographically, compare-strings-lexicographically, compare-vectors-lexicographically, and compare-seqs-lexicographically, which may be useful as custom orderings for the WB collections.

A function instance-class-name has been added to help with comparing and hashing classes that have subclasses.

The old-syntax GMap result-types :set, :seq, :wb-seq, :map, :wb-map, :ch-map, :map-to-sets, and :concat no longer work, because they would be ambiguous between FSet1 and FSet2 semantics. Use the appropriate new-syntax form: :arg set, :result set, etc. (See section 2.4 of the Misc-Extensions README.) Also, result-type fset2:map-to-sets now uses CHAMP sets and maps.