Lists of lists explained

nembence

Lists of lists explained
https://scratch-mit-edu.ezproxyberklee.flo.org/projects/1048874723/

Why it works:

Scratch treats lists internally as special variables that store JavaScript Array objects. Arrays are stored by reference, because in JavaScript all objects are stored by reference (this means you can have the same object in multiple places and changes to one affects the others).
All list blocks modify or read the content of the Array object, except the delete all of [list v] block that puts a new, empty Array object in the list.

How to replicate the hacked blocks:

The definition of the custom blocks in the project would look like this:

{
define list view = new list
delete all of [list v]
set [variable v] to (<{
}list{
}::list ring>::variables)
}{
define list view = (value)
set <{
} list ⏷ ::list ring> to (value)::variables
set [variable v] to (value)
}::ring #fff

The definitions are hidden by setting shadow to true in their JSON to prevent them from causing editor glitches (like half of the blocks disappearing, weird scrolling etc.).

The hacked blocks can be made by editing the project JSON like this:

(<{
}list{
}::list ring>::variables)//This hacked get variable block can get the reference of the Array that's currently in the list.

(list::list)//I think it's best to make it from this list block.

The list block looks like this in the JSON: (it can be found in it's parent block's "inputs":{…} object)
```
[13,"list","-{V7u)eEk8H;D#IGl5*y"]
```
Replace the “13” with a “12”. This changes the block opcode from “data_listcontents” to “data_variable”.
Now you have the hacked get variable block.

And the hacked set variable block:

set <{
}list ⏷::list ring> to (value::custom-arg)::variables // This hacked variable block can put an Array in the list.
set [variable v] to (value::custom-arg) // I think it's best to make it from this set variable block
delete all of [list v] // but you'll need a list block, too

The set variable block's JSON looks like this:

{"opcode":"data_setvariableto", ... "fields":{"VARIABLE":["variable","ub=.M`Km!Qsa`dnJ-B_~"]}, ... }

The list block's JSON looks like this:

{... "fields":{"LIST":["list","-{V7u)eEk8H;D#IGl5*y"]}, ...}

Copy the value of the list block's LIST field to the variable block's VARIABLE field. It will look like this:
```
{"opcode":"data_setvariableto", ... "fields":{"VARIABLE":["list","-{V7u)eEk8H;D#IGl5*y"]}, ... }
```
Now you have the hacked set variable block.

Important notes:

Don't forget to set shadow:true on the top level block of every script that contains these hacked blocks, or expect serious glitches in the editor
The shadow:true hides the block stack and prevents the glitches caused by the hacked blocks. The custom blocks are okay, as the editor doesn't need to show hacked blocks to display them.
Always delete every Array object from your project before saving.
If you download a project with Arrays in variables or list items, the downloaded project won't open.

Last edited by nembence (Jan. 14, 2025 16:31:54)

Jonathan50

nembence wrote:
Don't forget to set shadow:true on the top level block of every script that contains these hacked blocks, or expect serious glitches in the editor
The shadow:true hides the block stack and prevents the glitches caused by the hacked blocks. The custom blocks are okay, as the editor doesn't need to show hacked blocks to display them.
Always delete every Array object from your project before saving.
If you download a project with Arrays in variables or list items, the downloaded project won't open.

Sounds like a little bit of a headache but it's still really great that this is finally possible. Thanks for the writeup.

ChromeCat_test

It seems like there are some painful steps when using it, I would like to make some scratch modifications to the editor to support the list of lists and handle the painful steps for the user, and some other features so it's more user friendly.

redspacecat

nembence wrote:
Always delete every Array object from your project before saving.

What happens if you don't?
—-
This looks like a really cool project!

nembence

redspacecat wrote:
nembence wrote:
Always delete every Array object from your project before saving.
What happens if you don't?

The project can't save, and if you download and then try to upload it says “The project file that was selected failed to load.”

HBALabs

nembence wrote:

Lists of lists explained
https://scratch-mit-edu.ezproxyberklee.flo.org/projects/1048874723/

Why it works:

Scratch treats lists internally as special variables that store JavaScript Array objects. Arrays are stored by reference, because in JavaScript all objects are stored by reference (this means you can have the same object in multiple places and changes to one affects the others).
All list blocks modify or read the content of the Array object, except the delete all of [list v] block that puts a new, empty Array object in the list.

How to replicate the hacked blocks:

The definition of the custom blocks in the project would look like this:
{
define list view = new list
delete all of [list v]
set [variable v] to (<{
}list{
}::list ring>::variables)
}{
define list view = (value)
set <{
} list ⏷ ::list ring> to (value)::variables
set [variable v] to (value)
}::ring #fff
The definitions are hidden by setting shadow to true in their JSON to prevent them from causing editor glitches (like half of the blocks disappearing, weird scrolling etc.).

The hacked blocks can be made by editing the project JSON like this:
(<{
}list{
}::list ring>::variables)//This hacked get variable block can get the reference of the Array that's currently in the list.
(list::list)//I think it's best to make it from this list block.
The list block looks like this in the JSON: (it can be found in it's parent block's "inputs":{…} object)
[13,"list","-{V7u)eEk8H;D#IGl5*y"]
Replace the “13” with a “12”. This changes the block opcode from “data_listcontents” to “data_variable”.
Now you have the hacked get variable block.
And the hacked set variable block:
set <{
}list ⏷::list ring> to (value::custom-arg)::variables // This hacked variable block can put an Array in the list.
set [variable v] to (value::custom-arg) // I think it's best to make it from this set variable block
delete all of [list v] // but you'll need a list block, too
The set variable block's JSON looks like this:
{"opcode":"data_setvariableto", ... "fields":{"VARIABLE":["variable","ub=.M`Km!Qsa`dnJ-B_~"]}, ... }
The list block's JSON looks like this:
{... "fields":{"LIST":["list","-{V7u)eEk8H;D#IGl5*y"]}, ...}
Copy the value of the list block's LIST field to the variable block's VARIABLE field. It will look like this:
{"opcode":"data_setvariableto", ... "fields":{"VARIABLE":["list","-{V7u)eEk8H;D#IGl5*y"]}, ... }
Now you have the hacked set variable block.
Important notes:
Don't forget to set shadow:true on the top level block of every script that contains these hacked blocks, or expect serious glitches in the editor
The shadow:true hides the block stack and prevents the glitches caused by the hacked blocks. The custom blocks are okay, as the editor doesn't need to show hacked blocks to display them.
Always delete every Array object from your project before saving.
If you download a project with Arrays in variables or list items, the downloaded project won't open.

if this is possible by just hiding the blocks, I wonder if you can do:

set (input) to []

davidtheplatform

HBALabs wrote:
nembence wrote:
~snip~
if this is possible by just hiding the blocks, I wonder if you can do:
set (input) to []

Currently this is believed to be impossible due to how variables work. Hiding the blocks wouldn't help in this case.

nembence

davidtheplatform wrote:
HBALabs wrote:
nembence wrote:
~snip~
if this is possible by just hiding the blocks, I wonder if you can do:
set (input) to []
Currently this is believed to be impossible due to how variables work. Hiding the blocks wouldn't help in this case.

You can do it, but it doesn't accept strings but rather variable reference objects.
See 5. Variable References in @Geotale's project: https://scratch-mit-edu.ezproxyberklee.flo.org/projects/1068153464/

HBATest

nembence wrote:
You can do it, but it doesn't accept strings but rather variable reference objects.
See 5. Variable References in @Geotale's project: https://scratch-mit-edu.ezproxyberklee.flo.org/projects/1068153464/

the heck are variable reference objects
*this is me, HBALabs

imfh

Wow, that's really neat. So basically, you can trick Scratch into using the variable blocks except with a list. Since the variable blocks don't deal with arrays, they just copy the array around places.

Are there any good practical applications of this? It seems like most lists of lists applications can just use math or join and a 1d array

CST1229

imfh wrote:
(#10)
Are there any good practical applications of this? It seems like most lists of lists applications can just use math or join and a 1d array

I think said applications are already practical, since lists of lists are easier to work with than a 1d list with joining or math.
And it's probably also possible to, say, make an “object” system using lists of lists, that make passing around data structures easier (since then you can just pass around the object itself instead of an index that could change).

imfh

CST1229 wrote:
imfh wrote:
(#10)
Are there any good practical applications of this? It seems like most lists of lists applications can just use math or join and a 1d array
I think said applications are already practical, since lists of lists are easier to work with than a 1d list with joining or math.
And it's probably also possible to, say, make an “object” system using lists of lists, that make passing around data structures easier (since then you can just pass around the object itself instead of an index that could change).

Hmm, potentially. There's still not a huge difference between math and this though. I guess it is probably slightly more performant.

With math:

define Create Object (name) (x) (y) (size)
set [ref v] to (length of [Objects v]
add (name) to [Objects v]
add (x) to [Objects v]
add (y) to [Objects v]
add (size) to [Objects v]

define Get Object (ref)
delete all of [object v]
set [i v] to (ref)
repeat (4)
change [i v] by (1)
add (item (i) of [Objects v]) to [object v]
end

Get Object (ref)
say (item (1) of [object v] :: list)
set x to (item (2) of [object v] :: list)
set y to (item (3) of [object v] :: list)
set size to (item (4) of [object v] :: list)

Or, without (Get Object ::stack custom) ::hat grey
say (item (((ref) * (4)) + (1)) of [Objects v] :: list)
set x to (item (((ref) * (4)) + (2)) of [Objects v] :: list)
set y to (item (((ref) * (4)) + (3)) of [Objects v] :: list)
set size to (item (((ref) * (4)) + (4)) of [Objects v] :: list)

With hacked blocks:

define Create Object (name) (x) (y) (size)
add (name) to [object v]
add (x) to [object v]
add (y) to [object v]
add (size) to [object v]
set [ref v] to (object ::list) // hacked

define Get Object (ref)
set [object v] to (ref) // hacked

Get Object (ref)
say (item (1) of [object v] :: list)
set x to (item (2) of [object v] :: list)
set y to (item (3) of [object v] :: list)
set size to (item (4) of [object v] :: list)

BigNate469

imfh wrote:
CST1229 wrote:
imfh wrote:
(#10)
Are there any good practical applications of this? It seems like most lists of lists applications can just use math or join and a 1d array
I think said applications are already practical, since lists of lists are easier to work with than a 1d list with joining or math.
And it's probably also possible to, say, make an “object” system using lists of lists, that make passing around data structures easier (since then you can just pass around the object itself instead of an index that could change).
Hmm, potentially. There's still not a huge difference between math and this though. I guess it is probably slightly more performant.

With math:
snip
With hacked blocks:
snip

Well, it also allows for very performant oversized lists- @Chrome_Cat made a project using this that stores 5 million items using a list that is 500 items long but each item is a reference to another list that is 10,000 items long.

That's the equivalent of 25 ordinary 200,000 item lists, and with even just nesting a single list inside another, this allows for up to 40,000,000,000 item lists- around 40 gigabytes of list indexes alone. If you were to store a maximum length string on a 32-bit system running Chromium or a Chromium-based browser (which have the smallest possible maximum string length, at 2^28 - 16 characters long), you could store up to 1.0737418e+19 bytes of information (not including list indexes)- 10,737,418 terabytes of information.

So basically this allows anyone on Scratch to store as much information as they could possibly want in a Scratch project during runtime, provided that it doesn't either crash the page or your browser or computer, and is all deleted when you go to save.

Last edited by BigNate469 (Feb. 12, 2025 20:31:25)

alwayspaytaxes

Very interesting i'll see if i can write a patcher for this cause this method of 2d lists seems wayy easier than list parsing or using sprite coords if its done right

HBATest wrote:
nembence wrote:
You can do it, but it doesn't accept strings but rather variable reference objects.
See 5. Variable References in @Geotale's project: https://scratch-mit-edu.ezproxyberklee.flo.org/projects/1068153464/
the heck are variable reference objects

Whenever you create a variable in Scratch, it is assigned a unique ID (like -{V7u)eEk8H;D#IGl5*y), which solves all the possible issues with using names (block ids can be shorter, avoid name conflicts, etc).

Last edited by alwayspaytaxes (Jan. 29, 2025 16:33:23)

Jonathan50

imfh wrote:
Hmm, potentially. There's still not a huge difference between math and this though. I guess it is probably slightly more performant.

With math:
-snip- :: grey

Or, without (Get Object ::stack custom) ::hat grey
-snip- :: grey
With hacked blocks:

(I'm a few days late) You probably realize this since it doesn't apply to the “without Get Object” example, but there's a big difference between Get Object in those cases; in the 1st, there's only one “object” list, so as long as you're using the Get Object abstraction you've just got one “current” object, and it's like a state machine-y window into the objects. So it's not really gonna work out when you're doing an operation on multiple objects, like adding two vectors, or for a recursive algorithm or something. Whereas the hacked blocks solution lets you go

Create Object [foo] [bar] :: custom
set [object 1 v] to (object)
Create Object [baz] [quux] :: custom
something with two objects (object 1) (object) :: custom // the variables have different lists in them
. . . // use result e.g. matrix product

Now in this particular case, it's no big deal vs. no hacked blocks, since you can get the same result just by doing it like your without-Get Object example (and it's more efficient than your 1st example). You just lose the convenience of ITEM 1 OF object, etc. (You could alternatively use the index of the object's first list item to avoid doing *4 each time, or if the objects are small you can have several lists, e.g. the xs and ys, cars and cdrs, and then the index is always just the pointer).

(edit: wait you can't directly use list blocks on a custom block parameter, right? so nvm half of what I said above)

But this is the most important part of the post…clearly n-D arrays (including objects like this – anything where the sublists have a fixed size) were always easy in Scratch to begin with, with just some multiplication. Where this really makes huge differences is when the sublists don't have a fixed size, for things like trees and other data structures. You could have a big list like

1: <length of 1st sublist>
2: <item 1>
...
<item n>
<length of 2nd sublist>
<item 1>
...

But then you can't delete or grow earlier lists without all subsequent pointers changing; or if you just represented the sublists by 1, 2, 3, etc. then looking them up would take linear time instead of constant time. Similar story w/ trees w/ arbitrary # of nodes. You could have a huge “memory” list and implement manual memory allocation and deal with fragmentation, etc.

My projects that have parse trees (example, I based a couple later projects on it) just do them in terms of linked lists ‘cause that’s a simple way to do it. That project just constructs a parse tree and doesn't free anything, unless the green flag is clicked and the lists are emptied. The other problem it has to deal with is that there's no way to distinguish pointers from numbers, so it parses “3+4” as the tree “(+ (number 3) (number 4))” even though “(+ 3 4)” would be smaller and faster. Ideally if it's an actual Scratch list, that's also solved and there's a way. My guess is this:

<(join (list) []) = (list)> // false for lists, true for numbers/strings

but I haven't tested it.

In general I suppose the best way without hacked blocks to make a project with any structures such as parse trees or hash tables is to deal with any arbitrary-length thing with linked lists, essentially reducing whatever to things with a length of 2. But it is harder to deal with, clouds up the code (imagine how simple a hash table implementation with lists of lists would be), and you can imagine in a graphing project based on the linked project with multiple graphs and pan/zoom, deleting a function would mean recursively deleting the parse tree, and the more complicated the project, the hairier manual memory management would be.

Another bonus is this means it's finally possible to make (garbage-collected) interpreters in Scratch without implementing garbage collection from scratch, like we had to do before!

I'm still not that likely to use this much cause of reduced clarity, fiddliness, ST ambivalence about hacked blocks, and the fact that if there's ever a new major version of Scratch it won't be guaranteed to work, but it will be cool to see what people do (sorry this post is kinda too long)

edit: oh gosh it's been like an hour since I started writing oops. once I started I had to get it done though, or the thoughts would keep annoying me XD

Last edited by Jonathan50 (Jan. 31, 2025 21:40:44)

SpyCoderX

Could you do lists in lists in lists?

Or a list which contains itself?

Jonathan50

SpyCoderX wrote:
Could you do lists in lists in lists?

Or a list which contains itself?

yes

BigNate469

SpyCoderX wrote:
Or a list which contains itself?

While that particular example may sound weird (and depending on what you're doing, break the project by making a loop run indefinitely), since variables are stored by reference in JavaScript, it is technically possible.

SpyCoderX

BigNate469 wrote:
(#18)
SpyCoderX wrote:
Or a list which contains itself?
While that particular example may sound weird (and depending on what you're doing, break the project by making a loop run indefinitely), since variables are stored by reference in JavaScript, it is technically possible.

Yea thats what I mean lol

I wonder if it would crash anything since printing its entries would result in an infinite loop, but only if it also prints the content of sublists and doesn't just print “<list>” or something similar.

(In this context I am using print to mean any sort of conversion of an object to text)

nembence

SpyCoderX wrote:
BigNate469 wrote:
(#18)
SpyCoderX wrote:
Or a list which contains itself?
While that particular example may sound weird (and depending on what you're doing, break the project by making a loop run indefinitely), since variables are stored by reference in JavaScript, it is technically possible.
Yea thats what I mean lol

I wonder if it would crash anything since printing its entries would result in an infinite loop, but only if it also prints the content of sublists and doesn't just print “<list>” or something similar.

(In this context I am using print to mean any sort of conversion of an object to text)

When an array is stringified, loops like this are omitted from the result so it doesn't break. (normally it would print the content of sublists)

Last edited by nembence (Jan. 31, 2025 13:59:15)

Discuss Scratch