j9.7.0-beta8 available

[Eric Iverson]

The latest beta has a native implementation of dictionaries. They are high performance and will revolutionize how some problems are solved.

Upgrade your base library to get the associated dictionary addon.

Marcin Żołek helped Henry with the design and implementation.

Have a look at the addon. I think there will be messages from Henry and Marcin to help get this ball rolling.

***

If you have already installed 9.7, the upgrade is easy:
   load 'pacman'
   'upgrade' jpkg 'jengine'

To install 9.7 beta:
 https://code.jsoftware.com/wiki/System/Installation/J9.7

Release notes:
 https://code.jsoftware.com/wiki/System/ReleaseNotes/J9.7

Questions/bug reports/etc. should go to the beta forum.

[Henry Rich]

Ken Iverson's model of computation, in which verbs operate on whole
arrays to produce new whole arrays, was a breakthrough.  It taught us
think at the highest level of a problem rather than about individual
numbers.

However, there are times when creating an entire array as a result is
wasteful.  Modifying a few values in a large array is one example;
repeatedly appending to an existing array is another.  J has evolved to
allow those computations to be performed incrementally without copying
the entire array.

J 9.7-beta9 goes a step further.  It introduces the concept of the
/dictionary/, which is a J noun in its own locale, accessed by special
primitives that allow the noun to be shared freely between functions and
even between threads, with each shared user's changes being immediately
available to all other users.

A dictionary is a /mapping/ between /keys/ and /values/.  A key/value
pair is put into the dictionary, and later the key can be presented to
the dictionary to recover the value.  Mappings come in two kinds,
ordered and unordered.  Ordered maps allow key/values to be recovered
within ranges of keys.

Documentation is at
https://code.jsoftware.com/wiki/Vocabulary/Dictionaries_(addon) . The
initial implementation support only unordered maps, but ordered maps
will be supported soon.

The implementation is designed to be efficient, even when many threads
access the same dictionary.  An innovative locking scheme allows threads
to continue querying the dictionary while it is being modified.

Henry Rich

> To unsubscribe from this group and stop receiving emails from it, send
> an email to forum+un...@jsoftware.com.

[bill lam]

jandroid j9.7.0-beta9 available is available.

[Jan-Pieter Jacobs]

Hi Henry,

Thank you and Marcin for the implementation of dictionaries. It looks great, but I haven't had the time yet to thoroughly play with it.

Two things I've been wondering about when playing around with it, and thinking of possible extensions I originally had in mind when 

1. For writing higher-level functionality (e.g. merging dictionaries, applying functions, filtering etc) it would be handy to be able to at least list all keys. Could be that I overlooked it, but it seems such a verb is missing at the moment.

2. Currently, key/value type and shape are set as defaults when not provided explicitly. I think it would be nice if the addon would create the dictionary noun lazily only upon the first insertion, so that key/value type and shape can be automatically set based on those  keys/values inserted first. This would require making a choice on how to consider the first "put" into the dictionary: either the arguments are considered as single items in their entirety, or their items (rank _1) are considered as items to be put in the dictionary.

As proof of concept, I put together the following gist modifying the addon code: https://gist.github.com/jpjacobs/d08405607e2c1eefcd6ce5308b44695d

This would let one simply create a dictionary object, with the dictionary noun in it being lazily created upon the first put. For instance:

   load 'dictionary.ijs'

   md=: 'hash' conew 'jdictionary' NB. only locale set up, and dictionary access verbs defined as sensible placeholders.

   (0.5+i. 3 4 5) put__md 'abc'     NB. derive shapes and types from argument items, create dict noun, set stock access verbs, and put 3 corresponding keys and values.

   NB.  from here on, the dict works as if created by the official addon.

That said, the behaviour of put for dicts without values had me debugging my gist for a bit as I did not notice that even if values are ignored, an empty left argument should be provided. It would be nicer to be able to use "put" as a monad, than having to specify an empty left argument (especially in conjunction with the lazy loading, which however keeps default put behaviour at the moment).

While messing about with the gist, I also found a first bug to report:

I managed to make J crash using the following:

   load 'dictionary' NB. stock version

   md=: 'jdictionary' conew~ 'hash' ,&< ('keytype';'sparse boolean') , ('keyshape' ; 2 2) ,: 'valueshape' ; 0

JE has crashed, likely due to an internal bug.  Please report the code which caused the crash, as well as the following printout, to the J forum.
00005c3243357142: ?:0:  ?
000074eb5b045f5f: ./signal/../sysdeps/unix/sysv/linux/x86_64/libc_sigaction.c:0:        ?
000074eb56717db4: ?:0:  ?
000074eb56716c1b: ?:0:  ?
000074eb567169ea: ?:0:  ?
000074eb5690f2f4: ?:0:  ?
000074eb56719d3f: ?:0:  ?
000074eb566e290e: ?:0:  ?
000074eb5672cf5c: ?:0:  ?
000074eb56719d3f: ?:0:  ?
000074eb566e290e: ?:0:  ?
000074eb5672d556: ?:0:  ?
000074eb565fa3f3: ?:0:  ?
000074eb56719d3f: ?:0:  ?
000074eb56719a54: ?:0:  ?
000074eb5671f11c: ?:0:  ?
000074eb567041b4: ?:0:  ?
000074eb56703f7c: ?:0:  ?
00005c324335707f: ?:0:  ?
000074eb5b02a574: sysdeps/nptl/libc_start_call_main.h:58:       __libc_start_call_main
000074eb5b02a627: csu/libc-start.c:360: __libc_start_main_impl
00005c32433564e4: ?:0:  ?
ffffffffffffffff: ?:0:  ?
-----------------------------------------------------------------------------
Aborted (core dumped)

   JVERSION

Engine: j9.7.0-beta9/j64avx2/linux
Build: commercial/2026-01-03T02:55:44/clang-14-0-0/SLEEF=1
Library: 9.7.8
Qt IDE: 2.5.10/5.12.8(5.15.17)
OS Ver: Ubuntu 25.10 6.17.0-8-generic
Platform: Linux 64
Installer: j9.7 install
InstallPath: /home/jpjacobs/j9.7
Contact: www.jsoftware.com

Best regards,

Jan-Pieter

[Henry Rich]

Sparse arrays are not allowed as keys.  (They do not have a canonical form).  But a crash is poor form.

Henry Rich

[Pascal Jasmin]

It looks like you are considering integer1 (byte?) datatype, though trying it results in error on creation.

You may be aware of https://github.com/Pascal-J/kv

which is a fast 2 column inverted table implementation of dictionaries with a lot of ignorable syntax sugar.  keys are numbers or symbols. Values are autoboxed if inconsistent.  It is ordered and permits duplicates, and therefore undo feature, where separate set and add functions update last value, or permit a duplicate.  get returns last value.  I just noticed it is missing a getall (to include duplicates) function,  but that is easy.

The major features that kv has over this implementation.

nesting other dictionaries (compatible with json), returning filtered dictionaries.

full J expressions to query/filter values or numeric keys (converting symbols to boxed srings is easy enough to query them too)

functions that access objects (such as updating a value based on current value, or appending to a value that is a list (structural operations based on existing value/strucutre) requires fairly tedious operations on the object name passed as a string, and evaluating a big string function call with lr of arguments appended around a space padded function name, although making a new class that inserts jdictionary and includes such functions is a workaround, but OOP leaves bad tastes for me.

though a workaround with recent modifier trains is

  O =. 2 : 'm , ''_'' , (>n) , ''_''' (1 : 'm')  NB.  candidate for O. builtin to access objects with string method

'get' O d  NB. d assigned to dictionary

get_3_ NB. verb


The big missing features are just functions: keys, values, list, where keys and values return a list of respective items, and list returns both as a 2 column inverted table.  This permits not just visually checking contents of dictionary, but allows full J functions to query it, essentially providing all the functionality of my kv implementation (except nested dictionaries)

Thank you to everyone who contributed to this, as I expect there to be performance gains for many scenarios.

[Henry Rich]

Yes, we should have a way to read all keys/values/both.  I was focusing
on applications that are too big for that to perform well.

Since a dictionary is a locale, you could have 'nested' dictionaries by
using the locale#.

Allowing something like a user verb to decide which keys to return would
not work well in a multithreaded environment, where the dictionary must
appear to be locked during the operation.  That's why we limited
ourselves to simple queries and updates.

Henry Rich

[Pascal Jasmin]

correction to previous O definition

O =. 2 : 'm , ''_'' , (>n) , ''_'''~

> Since a dictionary is a locale, you could have 'nested' dictionaries by
using the locale#.

Possible for sure.  references are fragile.  references can be built from kv (must be to build object value references from scratch, as loading them from disk is fragile), and kv data structure built from references, but I feel user code always wants data instead of a references, and data is needed for serialization (disk and network)

my 2 big applications for dictionaries:

1.  inverted tables where keys are field names is the core for generic table operations.  field types can be inferred by first value, but an embedded dictionary with "magic key" TYPES (same keys as parent dictionary) could be used for "record" validation.  The append as edit optional functionality is thread/locking friendly, and afaiu, the strategy used by nearly all RDBMSs.  i: is used to retain unique access. Allowing duplicates also permits keyed multijoin operations.

In general, I believe delete operations are extremely rare, and temporal data (example current employee) can be a flag value, where you might still need person (former employee) data for other purposes (pension?).  Setting (appending) a field value to a null code can be equivalent to delete.  Having the database engine in user code allows functions that optimize down to engine level.

2. Towards a generic "windowed greed" search/optimization function build on chess positions, that include a lot of baggage properties (turn, enpassant, castling rights) and inverted table of moves, and scores that rank greediest alternative moves to explore.  Scores are lazily created whole column when accessed, and an embedded dictionary is lazily created to create the new board from applying a move.  A tree structure is created where thread friendliness is given by letting any 1 subthread have sole control over any board depth, and then updating score from parent thread (which also has sole control over top/its level board state.  Serialization comes into play where evaluation at depth shows the score of a move so incredibly poor that it is unlikely to ever be probed again, and moving it to disk can free memory for more likely depth exploration.  Dictionaries allow for "magic keys" that permit application categories (generic) in self contained datastructure, just because an application can walk down a tree structure through programming, doesn't mean that effortless serialization is not appreciated.  

Because each dictionary is modestly small and under single thread control, updating dictionary in place saves space/consistency (even if depth moves dictionaries are returned and J is forced to manage drastically expanded size of parent key value).  A serialization problem in this scenario is that the limit on number of files of OS can be reached if every depth is a single file.

I'd suggest the gold standard for dictionary representations would be a native J type (3!:1 support).  This seems very close already since 16!: function family does all operations.  However it is structured internally, if J builtin functions could see it as keys =: 0&{::  where dictvar (y argument) looks like an inverted table of keys ,&:< values ... would also be a gold standard.

As Jan-Peter suggested, inferred value types have advantages.  One being a null code that can be part of a multiple put operation to "effectively signal deletion/uninitialization of key" to application code.  While initial shapes can be marginally useful, it is more like an optional i.0 4, to signal a table shape that will be used to append to.  It is only marginally useful because this structure can be set in initial key assignment, but that is useful in empty schema creation where constraints are set, and magic keys such as TYPES, INITIALSHAPES can provide the functionality instead.  It seems extremely limited to have a value type and shape limited at dictionary creation, because values that are lists/tables of unknown length at creation time seem blocked, in addition to the "null code".

Limiting keys to numeric or symbol (boxed string equivalent) seems good enough.  The example in nuvoc page is a unique to unique table where reverse lookup would be a major use.