Fast Nested Lists?

MegaEliteCoder

I know HOW to make nested lists but I don’t know how to do it efficiently
I’ve made a nested list engine https://scratch.mit.edu/projects/746483283/ but it’s slow.

I want to do this to make a memory unit that supports nested lists for my programming language in scratch

uwv

use a single list and just insert elements, have an element for list length at the start and boom you have a nested list

Last edited by uwv (Feb. 3, 2023 05:46:49)

_nix

I usually use a “references” type structure where each item in a list is a reference to a value stored in a “objects” list. So like:

# all in one Scratch list, "LISTS", space represents a new item
4 P 1 P 2 L 2 P 3 3 P 4 L 1 P 5

# a separate "PRIMITIVES" list for normal Scratch values (strings, numbers)
hello 42 apple banana true

This represents two lists, which I'll write out in JS syntax below:

[hello, 42, (reference to list 2), apple]
[banana, (reference to list 1), banana]

As you can see it's a circular list (list 1 includes list 2 which includes list 1 which includes list 2…). That's something you can't do if you “flatten” the list during tokenization.

Because we're including a sub-list by reference instead of tokenizing it, that means if somewhere else in the program mutates the sub-list (i.e. because it's stored in a variable IN ADDITION TO inside the parent list), the parent list will reflect those changes (when the program actually reads the values of the sub-list from the parent list).

There's a bunch of stuff you can do to optimize this and implement “garbage collecting” so that old lists which aren't being used anymore are freed up (and the list index & references are all adjusted accordingly), and stuff you can do to make the actual format more compact too (e.g. encoding “P” and “L” as part of a number you can manipulate with math & thus not use two Scratch list items for each value in your custom lists), and by preparing a cached index you don't need to parse through the entire list at once to figure out the starting position of, say, list 2284, but above is the basic idea.

Last edited by _nix (Feb. 3, 2023 12:33:23)

Redstone1080

I figured out how you could do this.

Here's an example:

In this instance, '[' starts a new list and ‘]’ ends it. The first item in each list is how long the list is. Then the items follow the length.

It's really simple and it's all contained inside a Scratch list.

Discuss Scratch