Venery (Collections for Forth)

[RogerLevy]

I was inspired by 8th's collections and decided to start a collections library for standard Forth.

Spent just 5 or 6 hours and already we've got basic functionality on arrays, strings, and node trees. All tested and working.

Arrays and strings are static but node allocation is user-defined (an example using system heap is in the test code at the bottom)

https://github.com/RogerLevy/venery

[larsbrinkhoff]

Nice!

[AntonErtl]

The ffl (Forth Foundation Library) contains collections.

[RogerLevy]

True. This is a framework in classic minimalist Forth style. And it will provide a set of common commands that will work on different kinds of collections - operations like search, itterate (with break) join, split, push, pop etc. It is meant more as a dialect you adopt, like those OO extensions.

[pahihu]

+1

See Rob Pike: “Notes on Programming in C" (https://www.lysator.liu.se/c/pikestyle.html) section Complexity Rule 4.

"The following data structures are a complete list for almost all practical programs: array linked list hash table binary tree"

[alexshpilkin]

Well, first of all, a good collections library is hard. The Scheme list library (SRFI 1) took a lot of design work, and it only deals with a particular flavour of singly linked lists in a case that’s easier than that in Forth (higher-order functions, automatic memory management). The C++ people thought they they had it... until they hadn’t, and even berfore people with specialized needs (read: heavy users of the containers) complained that the libraries were at the same time slowed down by their generality and not general enough (and again, the C++ case, where opaque non–machine-word–sized things can be treated as first-class, is easier abstraction-wise). The Rust people may also have something interesting to say in this respect.

So it’s good to have more than one general-ish Forth data structures library, I think.

The Pike quote is better taken with a grain of salt. His context essentially presumes the absence of libraries, i.e. what you should be ready to reimplement yourself (and be alarmed if you stray outside), rather than what you should expect in a library. The things he mentions are thus better thought of as categories of data structures than concrete data structures.

Linked lists, in particular: singly- or doubly-linked? Intrusive or not? Circular or not, distinguished head node or not? If singly-linked, use O(1) deletion at the cost of copying the node contents (needs sentinel tail node), or keep a pointer to the previous node while iterating, or settle for O(n) deletion? If doubly-linked, use the Knuth XOR trick to halve the overhead or not? &c.

The ways to implement hash tables are even more diverse. (I’ll also dare to presume that Pike didn’t include crit-bit/PATRICIA/&c. trees on his list because he didn’t know about them.) And we haven’t even touched dynamic memory allocation, which is both difficult interface-wise and shouldn’t be implemented using only the structures on Pike’s list (unless “arrays” are counted very loosely).

[pahihu]

Nice overview, thanks.

[RogerLevy]

I'm not doing any fancy tricks, so it won't have blazing speed. I'll optimize it here and there but I'll leave the hardcore work to others assuming it got adopted on any scale. Primary goals are to make it easy-to-use and powerful.

[RogerLevy]

Just added several words (insertion, deletion, joining, conditional iteration)

Also documented all the commands.