Persistent/functional data-structures aside, bags are the most useful data type that is omitted from many container-libraries (whether or not the containers are part of the language stdlib).
I think the website is weird to navigate. "Next" links go to top-level headers instead of the "logical" next. For example, if I'm on "1.1 Fset Tutorial" clicking "Next" takes me to "1.2 Using Fset" instead of "1.1.1 The Major FSet Types".
At a conceptual level, do these data-structures store what in other languages would be pointers and so every access would mean paying for the pointer indirection or do they store objects themselves and they are cache friendly data-structures?
This is how Texinfo (which this uses) works. It's the same if you navigate it with an Info reader: "n" goes to the "next" node, which behaves as you point out.
When I'm reading in an Info reader (almost always in GNU Emacs) I always hit the spacebar when reading. This scrolls down a page and, if it's at the end of a page and, if at the bottom, goes to the next subnode - in other words, what "makes sense." (Actually the binding for this is "Info-scroll-up".)
That doesn't help when you're on a website, but for me Texinfo websites have a distinctive look and when I see them, I immediately know what clicking "Next" will do, and I know to instead go to the bottom of the page and go to the subnodes if that's what I want, which it typically is.
I agree that it's weird...but maybe understanding the overall weirdness of Texinfo helps it all make sense?? A more coherent weirdness?
I guess this might just be emacs Info-mode bias on my part (and the bias of someone who generally lives inside old documentation like this instead whatever the newfangled stuff is like I guess), but this behavior is precisely what I expect. For "next" to either mean jumping to the next in a sequence or jumping down a hierarchical level, depending on context, seems like "bad design" to me, or at the very least, trying to push the book metaphor to a fault.
The relation of 1.1.1 to 1.1 is about drilling down into detail if you want that, where you can still peruse through at the given upper level.
I did think about cache-friendliness and made them as much so as I reasonably could, mostly by trying to minimize levels of indirection; but pointers are inescapably involved, and there are limits to how cache-friendly such data structures can be.
For instance, each CHAMP node is a single CL vector; the header occupies the first few slots rather than being a separate allocated ooject.
Balancing trade-off is crucial in software design. It would be nice if the documentation listed the trade-offs of the structures compared to their native implementations. I imagine at least every mutation is consing? There are also larger fixed and slow-growing overheads in various operations.
Yeah, clojure gets away with it thanks to the high performance of the available gc in the JVM. In the Common Lisp world the compiler puts quite some effort into avoiding heap allocation ("consing"); the language was designed with that in mind. Not sure where it's now, but not too long ago SBCL's gc wasn't its strong point.
SBCL's gc is historically overly optimized for throughput at the expense of everything else. It also predates common availability of parallel systems. There's a new GC that addresses those things.
That being said, for batch processing in single-threaded applications, the older SBCL gc is actually pretty good.
Most lisp implementations use a moving collector of some kind, so heap fragmentation is less of a concern.
As far as constant factors go, this library is a middle ground; they strive for low constant factors in their algorithms, but it relies almost entirely on generic functions, so that alone is going to limit the maximum speed in e.g. tight loops.
Strings are immutable [in Scheme]. Functional point update operations are not provided, presumably out of time complexity concerns, but string-append and substring are provided, and there are functions to convert to and from lists of characters; I guess the idea is that fine-grained string construction will be done using lists and then converted. Amusingly, there’s string-copy, though it’s hard to see why one would ever use it.
Strings are actually mutable in R6RS. See https://www.r6rs.org/final/html/r6rs/r6rs-Z-H-14.html#node_s... - there is an imperative update-in-place function which mutates the argument. So of course string-copy really is useful, you might want to mutate a string and keep an unaltered copy. And the intent of string->list is to automatically let your list-processing code become string-processing code. It is way too strong to say "Functional point update operations are not provided, presumably out of time complexity concerns" - R6RS actively encourages functional operations on strings by calling string->list first, even though that's O(n) overhead.
The overall point you are making seems clearly correct: R6RS Scheme does not provide any "mostly functional" datatypes beyond basic s-expressions, so it would take a lot of work to develop Clojure/FSet-style tools. But it's strange to so badly misstate what strings in Scheme are like.
I mentioned the existence of`string-set!` a few days ago in the reddit post on this release of fset[1] (as well as some Racket inaccuracies). He might just not have gotten around to updating it.
Why is it too strong to say that functional point update operations on strings are not provided, when you seem to confirm that the supported way to manipulate strings functionally is to convert them to lists first?
I'm not the author and I can't find what you're looking for. But you could make it easily if you prefer it.
The documentation [1] seems to be in texinfo format that's commonly used for making info files used distributed with GNU and Emacs. It is converted into multipage HTML using two commands in the Makefile. You could modify them trivially to build what you want. I use it along with Sigil (epub editor) to build EPubs of user manuals for my EReader.
Hidden 13 paragraphs down the third page is the first actual description of the project:
> So FSet has a dual mission: first, to bring Common Lisp up to date, by giving it a much richer ensemble of functional collection data structures, to greatly expand the space of algorithms that can be written in an elegant functional style and still run efficiently; and second, as with Clojure, to support and encourage the use of functional collections for general programming.
Cool project but the docs could be greatly improved by putting the purpose of the project front and center. Don't make readers guess.
Not OP but it looks great! Your humility is much appreciated. I am excited for the Lisp community, and will follow this approach to CL as I do with Jank's approach to Clojure.
This library serves as the basis of cloture[0] an effort to host Clojure on Common Lisp. I hope to see both projects thrive!
[0] https://github.com/ruricolist/cloture
Persistent/functional data-structures aside, bags are the most useful data type that is omitted from many container-libraries (whether or not the containers are part of the language stdlib).
I remember watching you give a version of this talk at the Bay Area Lisp meetup!
I think the website is weird to navigate. "Next" links go to top-level headers instead of the "logical" next. For example, if I'm on "1.1 Fset Tutorial" clicking "Next" takes me to "1.2 Using Fset" instead of "1.1.1 The Major FSet Types".
At a conceptual level, do these data-structures store what in other languages would be pointers and so every access would mean paying for the pointer indirection or do they store objects themselves and they are cache friendly data-structures?
This is how Texinfo (which this uses) works. It's the same if you navigate it with an Info reader: "n" goes to the "next" node, which behaves as you point out.
When I'm reading in an Info reader (almost always in GNU Emacs) I always hit the spacebar when reading. This scrolls down a page and, if it's at the end of a page and, if at the bottom, goes to the next subnode - in other words, what "makes sense." (Actually the binding for this is "Info-scroll-up".)
That doesn't help when you're on a website, but for me Texinfo websites have a distinctive look and when I see them, I immediately know what clicking "Next" will do, and I know to instead go to the bottom of the page and go to the subnodes if that's what I want, which it typically is.
I agree that it's weird...but maybe understanding the overall weirdness of Texinfo helps it all make sense?? A more coherent weirdness?
I guess this might just be emacs Info-mode bias on my part (and the bias of someone who generally lives inside old documentation like this instead whatever the newfangled stuff is like I guess), but this behavior is precisely what I expect. For "next" to either mean jumping to the next in a sequence or jumping down a hierarchical level, depending on context, seems like "bad design" to me, or at the very least, trying to push the book metaphor to a fault.
The relation of 1.1.1 to 1.1 is about drilling down into detail if you want that, where you can still peruse through at the given upper level.
Picking another random other manual, it is the same: https://www.gnu.org/software/guile/manual/html_node/index.ht...
I did think about cache-friendliness and made them as much so as I reasonably could, mostly by trying to minimize levels of indirection; but pointers are inescapably involved, and there are limits to how cache-friendly such data structures can be.
For instance, each CHAMP node is a single CL vector; the header occupies the first few slots rather than being a separate allocated ooject.
Balancing trade-off is crucial in software design. It would be nice if the documentation listed the trade-offs of the structures compared to their native implementations. I imagine at least every mutation is consing? There are also larger fixed and slow-growing overheads in various operations.
1. Each operation lists the big-O complexity; most operations are O(lg N).
2. There are no mutations
3. I think it would be rather redundant to mention that every operation that returns a new object conses.
Btw I meant quasi-mutations of course. So every quasi-mutation conses. Alright.
Yeah, clojure gets away with it thanks to the high performance of the available gc in the JVM. In the Common Lisp world the compiler puts quite some effort into avoiding heap allocation ("consing"); the language was designed with that in mind. Not sure where it's now, but not too long ago SBCL's gc wasn't its strong point.
SBCL's gc is historically overly optimized for throughput at the expense of everything else. It also predates common availability of parallel systems. There's a new GC that addresses those things.
That being said, for batch processing in single-threaded applications, the older SBCL gc is actually pretty good.
The newish SBCL parallel gc is fantastic and uses no additional memory during gc
Big-O is one thing. Big constant factor, heap fragmentation and cache locality are other useful characteristics of data structures.
Most lisp implementations use a moving collector of some kind, so heap fragmentation is less of a concern.
As far as constant factors go, this library is a middle ground; they strive for low constant factors in their algorithms, but it relies almost entirely on generic functions, so that alone is going to limit the maximum speed in e.g. tight loops.
What do you call the "native implementations"? Assembler has no container types.
Just FYI, this section at the end about R6RS Scheme is a little confused: https://fset.common-lisp.dev/Modern-CL/Top_html/Scheme-_0028...
Strings are actually mutable in R6RS. See https://www.r6rs.org/final/html/r6rs/r6rs-Z-H-14.html#node_s... - there is an imperative update-in-place function which mutates the argument. So of course string-copy really is useful, you might want to mutate a string and keep an unaltered copy. And the intent of string->list is to automatically let your list-processing code become string-processing code. It is way too strong to say "Functional point update operations are not provided, presumably out of time complexity concerns" - R6RS actively encourages functional operations on strings by calling string->list first, even though that's O(n) overhead.The overall point you are making seems clearly correct: R6RS Scheme does not provide any "mostly functional" datatypes beyond basic s-expressions, so it would take a lot of work to develop Clojure/FSet-style tools. But it's strange to so badly misstate what strings in Scheme are like.
I mentioned the existence of`string-set!` a few days ago in the reddit post on this release of fset[1] (as well as some Racket inaccuracies). He might just not have gotten around to updating it.
[1] https://old.reddit.com/r/Common_Lisp/comments/1sk2nsl/fset_v...
Why is it too strong to say that functional point update operations on strings are not provided, when you seem to confirm that the supported way to manipulate strings functionally is to convert them to lists first?
Nice thanks, is there a single-HTML-page view available by any chance?
I'm not the author and I can't find what you're looking for. But you could make it easily if you prefer it.
The documentation [1] seems to be in texinfo format that's commonly used for making info files used distributed with GNU and Emacs. It is converted into multipage HTML using two commands in the Makefile. You could modify them trivially to build what you want. I use it along with Sigil (epub editor) to build EPubs of user manuals for my EReader.
[1] https://gitlab.common-lisp.net/fset/fset/-/tree/master/Doc/M...
I went ahead and did that. Here's the single page HTML view: https://fset-modern-cl.surge.sh/
Here's the diff. Claude helped me track down the link -> ref problem. https://github.com/shawwn/fset/commit/ce42cffde11fb84c075ddb...
Surprisingly it took 10 minutes total. Surge seems nice. (npm i -g surge)
Hidden 13 paragraphs down the third page is the first actual description of the project:
> So FSet has a dual mission: first, to bring Common Lisp up to date, by giving it a much richer ensemble of functional collection data structures, to greatly expand the space of algorithms that can be written in an elegant functional style and still run efficiently; and second, as with Clojure, to support and encourage the use of functional collections for general programming.
Cool project but the docs could be greatly improved by putting the purpose of the project front and center. Don't make readers guess.
Okay, I buried the lede :-)
Good suggestion, thanks.
If you see this — have another look — I think I've improved it.
Not OP but it looks great! Your humility is much appreciated. I am excited for the Lisp community, and will follow this approach to CL as I do with Jank's approach to Clojure.
I didn’t see the old one, but the current page made it clear straight away!
I don’t know how it was before, but I found this immediately.
[dead]