Scratch

Wow, that's something like almost a comprehensive design. Where is the "I love it" button for this post ;-). How did you draw the blocks (or did you already implement them)?.

I really like this proposal, but it also shows how it would make Scratch much more complex than it is now. Also, if I understand you correctly, you would like to enhance variables (at least lists) to be able to store more than just numbers, and the broadcast system by allowing for parameters, which would be another two big shifts from the current implementation, and, in my opinion, probably too much for Scratch's target users.

What I do like about your design is, that you could start by just allowing numerical values and the current numerical variables in lists, and then actually do with just a very few additional blocks. All you'd really need would be

a <size of list> reporter,
a <add ? to list>,
a <list at ?>,
and a <remove item ? from list>

block.
All others could be derived from combinations of these blocks.

Using such - much more limited - lists you could do a lot of things currently not possible in Scratch, like recording mouse drawings, music notes, score lists etc.

Personally, I'd rather see arrays than lists, though both are good general-purpose data structures.

I've found a can usually emulate list behavior in arrays better than I can emulate array behavior in lists.  That's why c++ is my main programming language, rather than LISP.

kevin_karplus wrote:

I've found a can usually emulate list behavior in arrays better than I can emulate array behavior in lists.  That's why c++ is my main programming language, rather than LISP.

I don't program in LISP and am most experienced in Java, but I think it's much easier to get array behavior from a list than the other way around, mainly because of the difficulty of adding/removing items in the middle. If you're emulating a list using an array, you have to worry about shifting elements around every time you add or delete in the middle, as opposed to at the ends. One-dimensional array emulation with a list, OTOH, is trivial, and adding dimensions turns into a simple polynomial formula. The only tricky part is the initialization of the data structure, since if you're emulating an array you'd want to fill the list up with zero values to start so that all the addressable elements exist.

I think the key is that at the Scratch programming level we're really talking about ADTs, not the underlying data structures, and if you decide that the ADT is an array, then you lose the ability to insert/remove at arbitrary locations. Perhaps there are gains from using an array ADT but I can't think of them...

This is a really interesting discussion.  I thought about this a bit over the summer- here are my notes:

Here are some ideas for how to make a list data structure in scratch.  These are just ideas on design features, meant to start a conversation about how things should work.

Properties of lists:
•    Contain only numbers
•    Indices start at one
•    One dimensional (not nested or 2D)
•    Expandable to some large fixed limit
•    Come with built in “list pointer� 

New buttons in the variables tab:
•    Make a list
•    Delete a list

The dialog box would be the same as for a variable: name it and choose local or global.

Design questions:

•    Is there a better name than “list� ?
•    Is there a better name than “pointer�  (e.g. marker, bookmark, finger, etc)?
•    What about allowing lists to include strings? There would be many implications for the rest of the language...  I’d propose to wait on this and just see what we can do with lists of numbers first.
o    If a new “string�  data type is added (as Tammy has  proposed), then there would need to be a new category of blocks for manipulating them (confusingly this might have some overlap with the operations you might want to do with lists…).
o    Maybe we could get away without a string data type, and just treat strings and numbers the same (so e.g. if a block expecting a number is handed a string, it would convert it to a reasonable default number).  Flash Actionscript lets you get away with this kind of thing, and it can be both convenient and confusing.
o    Strings could represented as text boxes (as in LCSI Microworlds).  Perhaps there could be a separate “text box�  data structure, distinct from lists.

List monitor mockup:



By default you get a display on the stage, as with variables:   
•    Shows values in the list in a column
•    All values are editable like inputs on blocks
•    Clicking on the empty box on the bottom lets you append a new value (when you type a number and hit enter, the list is expanded to include the new item, and a new empty box appears)
•    Indices are shown starting at one
•    The list pointer is shown at its current position, and can be dragged to any other index

Other features:
•    As the list display grows larger than the height of the stage, you get a scrollbar
•    If the values have more digits, the width of the list display increases
•    the list name at the top could wrap onto new rows to prevent the display having to be too wide

We could have several variants of the list display, as for variables:
•    The one described above, containing the most info
•    Another one could show only the values in the list (no indices, no pointer, no editability)
•    Another could show only the value at the current position of the pointer

Design questions:
•    Screen layout might be tricky- are there totally different ways (e.g. horizontal rather than vertical)?
•    Directly editable values in lists break UI consistency, because variable displays don’t work that way.  Is that a problem?
•    How to really make the pointer really look draggable?

List blocks

New blocks would appear on the variables tab, as when you create a variable.

A minimal set of blocks:

•    Put <number> into myList
•    Reset myList’s pointer
•    Next item in myList (getter)

The “put�  and “get next item�  blocks would both automatically increment the pointer.

Additional Blocks we should probably have:

•    Set myList’s pointer to <index>
•    myList’s pointer (getter)

Other Blocks that would be useful:

•    Clear myList
o    this would actually reset the size to 0 or 1 entries- with the above blocks you could set every entry to 0, but not actually delete them

•    Length of myList (getter)
o    Without this block, you would have to make a variable and carefully update it every time you add to the list

•    Sort myList <small to big / big to small / randomly>
o    It would be possible to implement these with the other blocks, though a bit tricky!

Design questions:

It looks like a good set of list blocks would have between 5 and 8 blocks.  Variables only have three blocks, so this is more, but is it too many more?

Two of the five are getters, so which one does the check box go next to?  Both could have check boxes- so if the one by “next item�  is checked, you see the list display, and then the box by “pointer�  is enabled, so then you can see the pointer on the list display.

Examples using lists

•    Storing several melodies in different lists
•    Recording mouse movements as X,Y coordinates to analyze or play back
•    Recording times of events
•    Gathering and analyzing sensor data from scratch board
•    Recording scores in a game
•    Simon game (store a sequence of moves, check input against sequence)
•    Mastermind game (store a secret code)
•    DDR game (store a sequence of moves)
•    Games where you want to keep track of complicated states (RPG with inventories, maze games)
•    L-systems (store symbols representing turtle drawing instructions, run a rewrite rule iteratively to make a fractal)
•    Word processor (store numbers representing letters)
•    Speech synthesizer (store phonemes)
•    Game AI that stores history of previous moves by opponent
•    Matrix multiplication (is that fun enough?)
•    Other things we haven’t thought of…

Hey, this discussion is definitely one of the most interesting and inspiring ones in this forum at the moment. It's wonderful to find out what you smart people are thinking of!

I empathically agree with Eric to keep lists (or collections, or whatever you want to call arrayed structures) confined to numerical values, keep them one-dimensional, and let the indices start at one (indices should be natural numbers only). I also strongly feel that lists should not be of a fixed size, but that you should be able to create scripts that add additional items to them, and in turn remove items from them. Lastly I think it should be possible to add/remove items at any position of the list, not just at the end.

I'm unsure, however, if I like the concept of a built in pointer, and don't really see the benefit. While this would be nice to simulate streams It also complicates things a lot and requires more blocks. In that I agree with Kevin, to keep things as simple a possible. It's Scratch, after all.

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?

Now, strings is another very interesting concept to discuss, which would also require another new data-type (character), and probably become messy in national languages with exotic charsets. I would, therefore, advocate to leave string implementation for later, and start out with very simple numerical lists instead. For the beginning, users could come up with their own string implementations, assigning numerical values to "character"-costumes. It would surely be interesting to observe the various ideas people will be getting out of this constraint.

I also think "list" is a good, natural language like name for such a collection, "array" sounds too geeky to me.

Scratch is neither assembler nor C. Memory allocation or system performance tweaking should not be a design criteria for Scratch objects, intuitive usability should be, though.

I believe we're not discussing which already existing data-class of another programming language can best be ported to Scratch, but rather how best to convey the idea of an 'indexed data sequence object' and what you can do with it to children. What I 'm trying to say is, it's not an issue of selecting something but of creating something novel for Scratch, and for that 'the sky is the limit'. It's more a question of which accessor/manipulation methods to implement with new command blocks.

Again pondering Eric's design notes one other thing struck me as possibly odd: Why should it be possible to directly set values in a stage-reporter. You can't do that with (other) variables, and I don't see any dire need for that. You're supposed to program using command blocks.

I once again agree with Kevin in that it's probably best to start out with a very simple, intuitive and straightforward dynamically sized 'array' list (i.e. very few command blocks, no fancy overhead, and only a minimal user interface).