Scratch

Jens · 2008-04-02 08:59:27

I have thought some more about Lists in Scratch, following up on this forum thread:
http://scratch.mit.edu/forums/viewtopic.php?id=2292

After some trivial coding experiments I think it can be done even simpler yet. I'm posting this in the "Advanced Topics" section, because I'm toying with actually adding this functionality to my experimental Chirp.

Like inuwali I'm suggesting another blocks category basically looking the same as the variable category, with buttons to add/remove either global or local lists.
For each list I'm proposing four new blocks:

at (index)
a round ReporterBlock answering a numerical value stored at the given index, 0 if the index is no positive integer

at (index) put (number)
a CommandBlock storing the number under the index, if the index is a positive integer.

size
a roundReporterBlock answering the largest index, under which a non-zero value is stored.

clear
an optional (not strictly neccessary) CommandBlock emptying the list.

A ScratchList simulates an indexed collection starting at 1. Each access requires an index, which must be a positive integer. Querying a value will answer the object stored under the given index or 0 by default. Quering the size reports the largest index under which a non-zero value is stored. Clearing empties it. This way a ScratchList can store an infinite amount of objects without ever having to be dimensioned.

On the Squeak side a ScratchList is merely a wrapper around a Squeak Dictionary with an extremely simplified public protocol, thereby allowing adding more functionality in the future, such as providing simple file (XML) storage for Scratch projects:

Code:

Object subclass: #ScratchList
    instanceVariableNames: 'dict '
    classVariableNames: ''
    poolDictionaries: ''
    category: ''

initialize
    dict _ Dictionary new

public protocol could then look as simple as this:

Code:

at: anInteger
    (((anInteger isKindOf: Integer) not) or: [anInteger < 1]) ifTrue: [^0].
    ^dict at: anInteger ifAbsent: [0]

at: anInteger put: anObject
    (((anInteger isKindOf: Integer) not) or: [anInteger < 1]) ifTrue: [^self].
    anObject = 0 ifTrue: [^dict removeKey: anInteger ifAbsent: []].
    dict at: anInteger put: anObject

clear
    self initialize

size
    dict isEmpty ifTrue: [^0].
    ^dict keys asSortedCollection last

Integrating this model into Scratch would additionally require adding a new instance variable to class ScriptableScratchMorph (lists - a dictionary like vars), a new category to the blocks pane (basically copying the variable stuff), and creating the new blocks for the UI.

The main reason I haven't integrated this into Chirp yet is that I haven't come up with a good solution how to resolve (or avoid) compatibility-breaks with Scratch. Any thoughts on this would be very welcome!

Paddle2See · 2008-04-02 10:31:30

This sounds amazing...arrays at last!

I don't see any way around the compatibility issue, however. Maybe we need a second experimental Scratch...one that doesn't attempt to maintain compatibility.

thecooltodd · 2008-04-02 22:06:16

What is Chirp?

Paddle2See · 2008-04-03 05:17:16

...And....Using the Search Feature results in...

http://scratch.mit.edu/forums/viewtopic.php?id=3779&p=1

Wow, that was easy! Computers are great!

Last edited by Paddle2See (2008-04-03 05:20:51)

Jens · 2008-04-03 15:17:04

Tadaa!

Turned out to be a lot easier than I expected (The Scratch Team has done an *awsome* job when they wrote Scratch! I'm telling you: God coded in Squeak and his initials are the same as mine, lol.).

Here's my current version of Lists in Scratch:
http://chirp.scratchr.org/dl/src/jens-ScratchLists.current.cs

Downlod this mini-changeset (just 21 Kb) and file it into the Scratch Source Code. Then open a ScratchFrameMorph, select the variable category and enjoy!

(Note: You cannot save projects using these new blocks until I have found out a way to cope with the resulting compatibility issues)

chalkmarrow · 2008-04-04 01:39:38

Wow. I'm definitely going to have to take a look at this.

Jens · 2008-04-04 05:59:51

I have just fixed some glitches and uploaded a new changeset. Since this will be updated often I've decided to make a permanent link to the latest version:

http://chirp.scratchr.org/dl/src/jens-ScratchLists.current.cs

Also, I have made a little introductory slideshow project in Scratch about this:

http://scratch.mit.edu/projects/Jens/134353

Please note: I have intentionally left out the capability to save projects using these new blocks, until I have found a way to cope with/avoid compatibilty breaks. If you experiment with these blocks it's best not to save the project (this will replace all new blocks with "obsolete" markings) but save the image instead.

[edit:]
sorry, the changeset I linked to and embedded in my project didn't file in correctly this morning, I just now found out and fixed it.

Last edited by Jens (2008-04-04 09:09:14)

Jens · 2008-04-08 15:15:37

update:

the current changeset
1) now allows saving/opening of projects using the new list blocks.
2) features another new block: "add _ to myList"

I also uploaded a complete version of "based on Scratch" incorporating these new list features, so you can experiment with them, creating your own projects with lists. You can download this experimental version from this link:

http://chirp.scratchr.org/dl/experimental/ScratchLists1.zip

Unzip it to a new folder and run the "ScratchList.exe".

Note: I had to change the project file format for this experimental version, breaking compatibility with Scratch in doing so. You will therefore not be able to edit/import regular Scratch projects into this experimental version, nor will you be able to reuse any projects created in this experimental version in Scratch, even if they don't use the new list blocks (this also prevents incompatible projects from being posted on the website).

Having disclaimed this, have fun playing with some new blocks! I'd be interested to know what you think. Do they work for you? Is this something that should be further investigated?

MasterOfMac · 2008-04-09 03:10:43

YES! please do!
Lists are EXTREMELY useful in flash for almost anything (Though they're called Arrays in AS3)

With this function, you needn't test for every variable when calculating something...

Jens · 2008-04-09 07:11:21

While doing some more testing with lists I created another demo project that shows how you can use lists to let users record / playback their own music on a piano keyboard, and how you can use lists to play several tunes with only one script

[edited: Now included in the zip-file]

I still haven't come up with any (easy) way to implement backward-compatibility with the Scratch file-format, any help (ideas, hints) would be *very* welcome, how I can include these new blocks in Chirp and still allow users to edit/create true Scratch projects by simply not using the list blocks. The problem is less the blocks themselves, but that to store lists I needed to add an additional instance variable (a field called "lists") to class ScriptableScratchMorph, which is currently unknown to Scratch...

Last edited by Jens (2008-04-16 03:57:42)

kevin_karplus · 2008-04-09 10:48:50

Good work, Jens!

I would prefer that the objects be called "arrays" rather than "lists". By convention, arrays allow random access and lists allow sequential access.

Being a long time C and C++ programmer, I really prefer arrays that start at 0.
But many language designers disagree, preferring to start at 1, so I recognize that this is mainly a matter of taste. Since Costume numbers start at 1, it is probably best to be compatible and have arrays start at 1 also.

I don't have any suggestions for file compatibility. It is always a good idea when designing a file format to allow for future extensions without breaking compatibility, but I guess that the Scratch designers were more interested in getting things working than in providing graceful extension capability.

Jens · 2008-04-10 04:34:02

Thanks, Kevin, for your thoughts!

I'm not sure about naming conventions for this kind of data-construct. In Smalltalk an Array refers to a very specialized subclass of "Collection", which has to be dimensioned and is basically of a fixed size, so I considered "List" to be a more general term. It probably doesn't matter anyway, since the only place this term shows up is on the two buttons which create / remove this new kind of data-construct.

Another thing I'm really unsure about is at wich index to start. Starting at 1 just seemed a tad easier to implement, and a little more consistent with the existing Costume-lists. Are there any benefits when you start with zero I should consider?

The problem with the file format is, that I'm pretty sure it allows for just that graceful extension capability you mentioned, but I can't seem to find it. The way Scratch handles opening stored projects is suprisingly complicated compared to the rest of the Scratch Source Code, and I suspect it's exactly for this reason. It's just that I'm not such an Über-Smalltalker to quickly grasp in total what's behind all this (in my amateurish view) needless complexity. So, any help from someone more into Squeak / Scratch would really be welcome, because I'm really itching to include these lists in Chirp (after some more debugging and some more refactoring, of course).

P.S.: The only way I can think of at the moment is to make use of Squeak's meta-programming abilities, i.e. to let my version of Scratch recompile itself at "runtime" the first time a list is created; that seems like cheating, though...

Paddle2See · 2008-04-10 05:40:32

Jens wrote:
Another thing I'm really unsure about is at wich index to start. Starting at 1 just seemed a tad easier to implement, and a little more consistent with the existing Costume-lists. Are there any benefits when you start with zero I should consider?

Stick with starting at 1, please! It is far more natural. When you are counting a set of anything in the real world, you start with "1" not "0".

When it comes time to describe Lists (or Arrays, as I prefer) to kids, pretty much any analogy you are likely to pick (house numbers, post office boxes, whatever...) use numbers that start with "1".

Jens · 2008-04-10 07:50:28

update:

The current changeset now also fully supports cloning sprites and duplicating scripts:
http://chirp.scratchr.org/dl/src/jens-ScratchLists.current.cs

That means, that if you drag a script containing any list block into another sprite, or if you duplicate a sprite containing scripts with list blocks, everything will be reassigned correctly, and new local lists will be created if needed (the same as with variables).

This pretty much completes what I believe should be the basic functionality regarding lists (or arrays if you prefer that term). I'm planning to eventually add the ability to export/import list contents to external (xml) files, so you can reuse them across projects.

I have again updated a complete, executable version (an image) and posted it to:
http://chirp.scratchr.org/dl/experimental/

Since there will be some more frequent updates as I begin cleaning up and commenting the code be sure to always download the archive with the highest number (which will be the latest release, until I *really* publish an installable version).

Jens · 2008-04-16 03:46:23

update:

I cleaned up, commented, and reorganized the source code for my ScratchLists, eliminating a bunch of redundant classes and generally simplifying things "under the hood", including the file format.

Now it'll be easier to experiment with additional features, such as creating new blocks to store/retrieve lists to and from external files, to concatenate lists, to also store strings in lists and so forth.

Once again, I posted the source code to:
http://chirp.scratchr.org/dl/src/jens-ScratchLists.current.cs

and a current executable version to:
http://chirp.scratchr.org/dl/experimental/

I'm still at loss how to at least implement some sort of one-way (backward) compatibility. Any thoughts/hints ... ?

AddZero · 2008-04-17 00:52:01

Very cool!
The global list is much easier to read. It's still just a bit low contrast compared to the rest of the block colored... I like how it's organized.

I'm curious how the memory works. If I have it adding to the list all night or days, will it hit a limit? (it just passed 11000 size, using 12.5mb memory. hmm... it runs at 75% cpu when the script is not running. (ubuntu linux))
Awesome work! Thanks!

Jens · 2008-04-17 01:54:03

Thanks, AddZero, for testing it. I have already changed the colors for some more contrast, and I might eventually come up with a different color altogether (although it's hard to find one that doesn't look too dark - I like it bright smile ).

The memory is not likely to hit a limit anytime soon, because you're only storing numerical values in these lists. The memory is dynamic so it keeps expanding until your computer runs out of physical and virtual memory. Technically you can also assign more memory to Scratch by changing the VM-settings, so I don't see any limitation there. In fact, there are lots of other Squeak based apps being way more memory intensive and working just fine. Importing a single costume is also likely to use up much more memory than storing tens of thousands of numbers in lists....

Jens · 2008-04-17 08:10:40

There has been some discussion if "internal pointers" in lists might be a good idea, so you can get items from lists using some kind of "next item" command, avoiding the additional index variable (like in the costume lists), which would reduce script complexity.

I just uploaded a little variation of my "mouse path recording" demo, which tries to explain why I reject that idea:

http://chirp.scratchr.org/dl/experimental/ListMultiAccessDemo.sb
Note: you need the latest experimental ScratchList3.zip to examine and play this.

In this demo-project you can drag a big cat (the "leader") around the screen recording its path. There are several other smaller cats ("followers") which will one after another trail the leader, each by accessing the same global coordinate lists which are simultaneously written (and expanded) by the leader. After you drop the leader, you can press space to replay everything.

Such parallel access to the same list would be impossible if lists were constrained to sequential access.

inuwali · 2008-04-18 16:17:09

I’m excited to see this discussion revived! I've yet to download the code and try it out, but the discussion seems to be very much alive and the implementation sounds good. Some comments below:

kevin_karplus wrote:
I would prefer that the objects be called "arrays" rather than "lists". By convention, arrays allow random access and lists allow sequential access.

Kevin, I can understand your concern; if you're thinking data structures (and I’m guessing this would be your POV as a C/C++ programmer) then arrays are generally associated with random access. However, if you're dealing with abstract data types as opposed to data structures, then I believe that "list" is a good way to go. According to popular convention as expressed in this article, lists allow for random access. Additionally, I think that "list" is appropriate terminology for the Lifelong Kindergarten audience as opposed to "array," which is decidedly more programmer-centric.

kevin_karplus wrote:
Being a long time C and C++ programmer, I really prefer arrays that start at 0.  But many language designers disagree, preferring to start at 1, so I recognize that this is mainly a matter of taste. Since Costume numbers start at 1, it is probably best to be compatible and have arrays start at 1 also.

Jens wrote:
Another thing I'm really unsure about is at wich index to start. Starting at 1 just seemed a tad easier to implement, and a little more consistent with the existing Costume-lists. Are there any benefits when you start with zero I should consider?

I agree that by convention, programmers like to start numbering at zero, and also that it is largely a matter of taste at this point (as opposed to the era of C programming, when the reasons for indexing from zero were much more evident based on underlying implementation). I can’t think of any commonplace Scratch scenario in which indexing from zero offers an advantage. (Though I do agree with Kevin’s post here that if you want to emulate a multi-dimensional array, zero-based indexing means it’s easier to use the mod function to do so.) I concur that consistency is the primary concern and again would like to add that Lifelong Kindergarteners would probably find it more natural to start counting at 1.

Jens wrote:
There has been some discussion if "internal pointers" in lists might be a good idea, so you can get items from lists using some kind of "next item" command, avoiding the additional index variable (like in the costume lists), which would reduce script complexity.
...
Such parallel access to the same list would be impossible if lists were constrained to sequential access.

I agree with Jens. In principle the idea of implementing lists with built-in pointers seems to simplify things, but it not only prevents certain uses (or certainly makes them much more difficult) as Jens shows, but also dilutes the purity of a pure data structure to some degree by introducing a built-in iterator. Iteration is a function related to lists, not an integral part of them, in my mind. A list itself is just the data.

Jens wrote:
I'm also skeptical about built-in sorting. Why not let users come up with their own sorting algos, if it's only going to be numerical values? 

(This quote was from the earlier thread.)

I’ll try to make an argument in favor of including a sorting function. ;-) I agree that there’s value in leaving sorting to the user. It encourages explorative programming and some pretty advanced problem solving. But I think that far greater value exists in a pre-made sorting script block for the following reasons:

1: Built-in rearranging functionality gets users to think about doing novel things with lists. Once you’ve built a list, it’s easy to see how to use it in its current form, but less evident that by sorting it or reversing it you can open up a whole new set of applications.

2: Sorting can be a part of solving a bigger problem. For example, a user needs the biggest number in a list. If they don’t have the sorting blocks, it might be difficult to see how to do this; if they do, they can make the logical leap more easily (remember, I teach middle school students). So you’re making the trade-off of less low-level programming for more high-level programming, which I believe fits well with the Lifelong Kindergarten model.

3: I believe in your current implementation, sharing list-sorting code would not be trivial, and therefore it’s less likely that list sorting or other rearranging would be as commonplace in the community. (Correct me if I’m wrong about this.)

I’d also like, at some point, to take up the discussion of whether it’s better to approach lists as sparse arrays, as I believe you’re doing, or as dense collections (which would require a different approach but might confer some advantages).

I wish I had something to add about the file format and backwards compatibility, but I don’t have any familiarity with the Scratch source at this point. Are you guys going to the conference this summer? I’ll be there, and perhaps we can delve into some of this more deeply.

Last edited by inuwali (2008-04-18 16:19:37)

Jens · 2008-04-20 05:25:35

Thanks, inuwali, for your suggestions and arguments in favor of additional operations for lists.

I'm also very excited at all the interest this discussion and my amateur-implementaion has sparked up so far. I find it extremely interesting to actually code these things, because I keep learning so much in these hands-on experiments.

I believe I have found out how I can change the project-saving code to provide backward compatibility with Scratch (and even save projects in "pure" Scratch format as long as they're not using lists). Before I'll be finalizing this, however, there are some other issues to consider:

I have started coding additional operations to concatenate, copy, sort, rearrange, save and retrieve lists, and to query additional statistical information (max, min, average, median etc.). At first I wanted to add these ops not as command blocks in Scratch but as options in the block's context menu. But, inuwali, you've got me reconsidering this decision. Now I'm pondering additional blocks, perhaps with drop-down lists of additional operations.

I'm also looking forward to perhaps discussing these issues at the conference, as it seems I might be attending after all smile

fullmoon · 2008-04-20 14:19:40

Jens wrote:
I'm also skeptical about built-in sorting. Why not let users come up with their own sorting algos, if it's only going to be numerical values?

Hmmm...I tried to write a sorting system this morning, but it didn't quite work. I'm all for letting us figure it out on our own.

fullmoon · 2008-04-20 14:21:40

AddZero wrote:
Very cool!
The global list is much easier to read. It's still just a bit low contrast compared to the rest of the block colored... I like how it's organized.

I'm curious how the memory works. If I have it adding to the list all night or days, will it hit a limit? (it just passed 11000 size, using 12.5mb memory. hmm... it runs at 75% cpu when the script is not running. (ubuntu linux))
Awesome work! Thanks!

You use Ubuntu? I tried putting Xubuntu on my old computer, but I had problems with WINE, so I caved and put Windows back on. sad

Jens · 2008-04-23 11:20:49

big update:

I think I've got this Lists-in-Scratch project where I want it to be now. The current changeset and the new executable version

http://chirp.scratchr.org/dl/experimental/ScratchLists4.zip

now have the following features:

compatibility with the Scratch file format
You can now open any Scratch project in the experimental ScratchLists app, edit it, and save it, without making the project incompatible. You can even create new projects in this experimental version, and they will be fully compatible with Scratch. If you use any of the new list features in a project, however it will no longer be compatible. Any new list projects can only be opened in the experimental version. Removing every list from a new project will again make it compatible with Scratch.

file access
I have added a block that lets you write/read lists to and from external file on your harddrive. Now you can do your highscore lists, share lists among different projects and whatmore....

a dozen blocks
I have been experimenting with very many different new blocks for lists and finally reduced the number of blocks again to 12. I have also added drop-down lists to many of these blocks to let the same block feature several functions (size, min, max, sum, average etc.). There are now 21 operations you can perform on lists, with a strong focus on making lists usable in projects without having to iterate through them every time. I also found a way to let a single reporter block add several watchers to the stage (one for each function), so to further reduce the number of blocks. Are there now too many blocks?

other changes
I've also changed the list block color to something dark-reddish to improve contrast and to make it look "right" in the variables pane.
The file format has also been changed (I hope for the last time), so you will not be able to open the previous list-demo projects (I'll supply new ones shortly).

This wraps it all up in my opinion. I'm now going to test and document it, then I'll start integrating it into Chirp. Any opinions/bug reports are greatly appreciated!

fullmoon · 2008-04-23 20:41:32

Wow...this is amazing! Does the write function use absolute filenames, or do the .lst files have to be in the same folder? Anyway, I nominate you for Scratcher of the Year.
Wow...

fullmoon · 2008-04-23 20:42:46

Many of these blocks are completely unnecessary, but they sure do make things simpler!

Scratch

archived forums

#1 2008-04-02 08:59:27

Lists for Scratch

Code:

Code:

#2 2008-04-02 10:31:30

Re: Lists for Scratch

#3 2008-04-02 22:06:16

Re: Lists for Scratch

#4 2008-04-03 05:17:16

Re: Lists for Scratch

#5 2008-04-03 15:17:04

Re: Lists for Scratch

#6 2008-04-04 01:39:38

Re: Lists for Scratch

#7 2008-04-04 05:59:51

Re: Lists for Scratch

#8 2008-04-08 15:15:37

Re: Lists for Scratch

#9 2008-04-09 03:10:43

Re: Lists for Scratch

#10 2008-04-09 07:11:21

Re: Lists for Scratch

#11 2008-04-09 10:48:50

Re: Lists for Scratch

#12 2008-04-10 04:34:02

Re: Lists for Scratch

#13 2008-04-10 05:40:32

Re: Lists for Scratch

Jens wrote:

#14 2008-04-10 07:50:28

Re: Lists for Scratch

#15 2008-04-16 03:46:23

Re: Lists for Scratch

#16 2008-04-17 00:52:01

Re: Lists for Scratch

#17 2008-04-17 01:54:03

Re: Lists for Scratch

#18 2008-04-17 08:10:40

Re: Lists for Scratch

#19 2008-04-18 16:17:09

Re: Lists for Scratch

kevin_karplus wrote:

kevin_karplus wrote:

Jens wrote:

Jens wrote:

Jens wrote:

#20 2008-04-20 05:25:35

Re: Lists for Scratch

#21 2008-04-20 14:19:40

Re: Lists for Scratch

Jens wrote:

#22 2008-04-20 14:21:40

Re: Lists for Scratch

AddZero wrote:

#23 2008-04-23 11:20:49

Re: Lists for Scratch

#24 2008-04-23 20:41:32

Re: Lists for Scratch

#25 2008-04-23 20:42:46

Re: Lists for Scratch

Board footer