Scratch

bharvey wrote:

Note: CONS isn't "insert at place 1"!  It does not modify its input list; it makes a new list (which shares storage with the input list).  In the BYOB 3 tools this is called ADJOIN (item) TO (list).  We're considering (item) IN FRONT OF (list) as an alternative.

er...

script variables (copy)
set [copy v] to (copy of (list given as input))
delete (1) of (copy)
report (copy)

does the same thing as your CDR script but is alot faster, and

script variables (copy)
set [copy v] to (copy of (list given as input))
insert (item to be inserted) at (1) of (copy)
report (copy)

does the same thing as your CAR script. In fact, you could make this block:

{apply (function) to (list)} where function is an inline script input and list is a list input.
script variables (copy)
set [copy v] to (copy of (list given as input))
run (function) with inputs (copy)
report (copy)

for a general function to make a new list and do something to it.

joefarebrother wrote:

delete (1) of (copy)

does the same thing as your CDR script but is a lot faster [...]

No, it doesn't.  Your version changes the original list; my version makes a new, shorter list.

There are two aspects to this that need discussion:   (1) Why would one care about changing vs. not changing the input list?  (2) Isn't it slow?

(1)  Functional programming is an idea that takes some getting used to, if you're accustomed to sequential programming with assignment.  But it's really, really useful, especially in the modern era of parallelism (e.g. multicore processors), because in a functional program, each little piece of the computation is independent of the other little pieces, so things can happen in different orders -- or in parallel, at the same time.  Once you allow changing the value of a variable, you have to worry about the order in which things happen and your programs are harder to parallelize.  Functional programming also avoids the sort of bugs in which one piece of a program changes the value of a variable that another piece of the program expects not to change.

And, believe it or not, once you get in the habit, it's much easier to think about algorithms programmed functionally.  And it's easier to prove theorems about functional algorithms.

You can really see the benefits of functional programming when dealing with recursively defined data structures such as trees.  The tree traversal algorithms in the textbooks are mostly really hairy and full of bookkeeping, whereas functional tree traversal is a piece of cake.

(2) The BYOB scripts I posted for CDR and CONS are indeed slow, but as of yesterday we have primitive CDR and CONS blocks that run in constant time!  This works because we store lists internally as true (linked) lists, made of pairs (arrays of length 2) whose first element (the CAR) is an item of the list and whose second element (the CDR) points to the rest of the list (another pair, or the empty list).  So CONS just creates one new pair, and CDR dereferences the second element of the pair.

So that Scratch-style list programs will also run fast, we actually implement both Scratch-style dynamic arrays and linked lists.  If you just use commands (e.g. INSERT, REMOVE) then your list will be stored as a dynamic array, but if you just use reporters (CAR, CDR, CONS, etc.) then your list will be stored as a linked list.  If you use both styles on the same list, then the list will be converted from one form to the other a lot and your program will be slow.

bharvey wrote:

some long text 

that's cool. but what about merging and slicing? this is much more useful! 

Sorry , bracket pb !

Yay!  After several small list-related bugfixes, I can now do this:



and get an answer in less than a minute!

(@roijac:  See if the above answers your question about the usefulness of functional programming compared with JS merge and slice.  Not that the latter are useless, but you should have more than one string to your bow.)

EDIT:  It'll be even faster once the = block works correctly for empty lists. 

EDIT 2:  And it doesn't even matter if you have a watcher watching BAZ, because it doesn't get its value until the very end, after all the work is done.

EDIT 3:  The quiz:  How come the base case for ODDS, EVENS, and MERGE can be just an empty list, but the base case for SORT has to be a list of length < 2?

EDIT 4:  See, the argument was that Jens thought WARP would solve the speed problem and I thought constant-time CDR and CONS would solve it, but if either of those is missing, mergesort of 1000 numbers is way too slow. 

Last edited by bharvey (2011-11-24 00:39:35)

Yes, Xavier, that's what I like about the WARP block, too. For example I've played with a spirograph of spirographs and only warped the inner ones. that way - as you are saying, too - I can follow what's going on much better. When I was first writing BYOB in 2008 I actually started out with the WARP block, but I later replaced it for the "atomic" checkbox in the Block editor, because I did not want to introduce any new blocks. for the same reason I added a fixed "return value" field to the block editor when editing a custom reporter block, again because I did not want to introduce the REPORT block back then. Now, of course, we can do what's /right/ and add these features as blocks, what they should be.

Last edited by Jens (2011-11-24 07:54:22)

The warp block is great!! But, the name "warp" is misleading in my opinion. Why not "make atomic"?

And I'm not sure I totally understood the question in the above post, but if we keep the "warp" name, then we could use "de-warp" and if "make atomic" is used, then my suggestion would be "make un-atomic".

Jens wrote:

Snap! speed-up

Thanks to a hint from John Maloney composing blocks in the scripts pane of our Snap! pre-alpha version and editing text in input slots of long and nested scripts is now significantly faster, even in slower browers.

Check it out everybody, and thanks, John!

Help !
There is a mistake somewhere in your new speedy update.
Nothing works (like for example a simple factorial block)

suggestion: it looks that you are going to definitely add much more blocks. that's cool, but the pallet design won't work. what do you say about a search bar at the bottom, while you can tip a part of the block and it updates the block list? would be especially useful for experted users, but you could always not type anything and search if you don't know how the block's called 

roijac wrote:

suggestion: it looks that you are going to definitely add much more blocks. that's cool, but the pallet design won't work.

Of course we're going to have separate palettes for the different colors, as before.  It'll be fine.

That's not to say a search bar wouldn't be cool too.

bharvey wrote:

joefarebrother wrote:

delete (1) of (copy)

does the same thing as your CDR script but is a lot faster [...]

No, it doesn't.  Your version changes the original list; my version makes a new, shorter list.

Read the rest of the code. It uses the (copy of()) block, which creates a new list as a copy of an existing list.

Aren't we going to wait for Snap!'s official release? Plus, I think its only fair that Jens or Brian gets to manage the topic. 

Last edited by shadow_7283 (2011-11-24 18:36:51)