Indeed. I wrote a similar framework in Actionscript / Flex a few years ago, actually with a lot of input from the Scratch team. I've been thinking about porting it to JS recently. Glad to see someone beat me to it :)
Waterbear isn't a language like Scratch, it's a toolkit to create a Scratch-like visual programming interface to any language you like. There is active development on wrappers for Javascript, Java robotics, and Arduino.
Ah scratch. Some years ago I wanted to show what cool stuff you can do with computers to a 10y old boy. Found scratch and actually got hooked myself for a bit ^^. Ended up with this (slightly embarassing thing): http://scratch.mit.edu/projects/DeepDuh/941811. After programming a bit, the limitations become apparent big time. Google's idea to implement this as a Javascript parser is probably a good idea, this way some kids may make the bridge to the actual program. Also, it's probably way way better performing.
If you like visual programming, have a look at subtext. IMO this is the best idea for a visual programmig style, I hope it gets traction http://www.subtextual.org/.
That website is glorious :). Yeah, I think this might go a bit far. Scratch's community sadly isn't so big, further fragmentation won't help that much I think. And the platform doesn't make a very solid impression to me. That's why I like google's idea, I hope they pour some money into this.
Yep it seems like it has grown quite a bit since I've looked at it last time. I still think a platform like this should be bigger - as in a substantial fraction of school children big. Every child should try playing with something like scratch, just to see whether (s)he might like it and go into programming. When I was a child I went straight from some learning program for children with some graphical macro editor (poor man's hypercard) to VB6 and it led me to what I am now. That's why I think it's really important what toys we give to our children.
Google also had App Inventor similar to that. I don't understand why they are building this. Didn't they just kill App Inventor because they wanted to "focus" or something? So why this now?
There isn't. I had to enclose the algorithm in a while (true) loop and if you reach the goal the program stops automatically. Here is a screenshot: http://imgur.com/0mape
An "else" would help; you can add one by hitting the + symbol on the if. With the else, you can get the shortest program that'll solve the maze (transcribing using approximate notation in lieu of a screenshot):
while True:
if wall(AHEAD):
turn(LEFT)
else:
move(FORWARD)
turn(RIGHT)
However, the addition of one more if makes the solution much faster and look more sensible, by not turning to the right and immediately back to the left:
while True:
if wall(AHEAD):
turn(LEFT)
else:
move(FORWARD)
if not wall(RIGHT):
turn(RIGHT)
If you started off facing a wall your code would just not do anything. You can both simplify it and fix this bug by reorganizing the loop.
while true:
turn left
while wall(AHEAD):
turn right
move forward
However, while this algorithm happens to work on this maze, it will not work against other mazes (if you care).
Imagine a 5x5 square race track, with spokes coming from the outside of the wheel to the center, where there was a flag. Your algorithm (and my modified one) would just spin clockwise around the track without ever realizing it should take a right towards the center.
Weird, that looks like you're manipulating blocks of text with the mouse. How is that a "visual programming language"? It just seems to be a fancy text editor.
Here's one with same amount of code and optimal logic (for this map) without hard coding. It also ensures that there is a forward step in every iteration of the while loop.
This seems to be done by an extraordinarily smart guy - Neil
Fraser. He's behind "google-diff-match-patch" [1] project,
which is AFAIK the machinery behind realtime collaboration
on google docs.
Not a big fan of what amounts to fairly typical coding via drag and drop, but this is a fantastic resource. I have a project in my queue that will need Google Doc collab functionality so this is very useful. Cheers.
I've worked with Neil, and he is indeed extraordinary. I'd say he's who I want to be when I grow up except it's not clear he's grown up. See, for example, the centrifuge in his living room (http://neil.fraser.name/hardware/centrifuge/).
Possibly, but as far as I can see, all it adds to the mix (that textual teaching languages, e.g. LOGO, don't have) is the certain impossibility of certain syntax errors by only allowing certain parts to click together[1]. The semantic model behind the system is otherwise identical to BASIC or some other ALGOL-ish programming language, with loops and subroutines and mutable variables and so forth. It is quite probable that this might make some tasks easier, especially to a wholly inexperienced programmer, but what I assert are the real challenges of learning to program—algorithmic thinking, code organization, reasoning about program state, &c—remain just as difficult.
[1]: It also only allows variables to be specified from an extendable set, preventing certain problems with unbound or misspelled variables. I can see the possibility of also preventing type errors by constraining shapes further, e.g. all integers could be circular while booleans are hexagonal, so and would have two hexagonal spaces while + would have two circles. If I'm not mistaken, Scratch does something like this, although I do not know how far it is taken there. It would be interesting to see how far this can be developed to constrain the space of possible incorrect programs.
After I placed turn left after move forward, what was my first instinct? Same as yours, I wanted to right-click move forward and place the copy after turn left.
var n;
var A;
var i;
var x;
var j;
n = 100;
A = [];
for (i = 0; i <= n; i++) {
A[i - 1] = true;
}
var i_end = Math.sqrt(n);
for (i = 2; i <= i_end; i++) {
if (A[i - 1] == true) {
j = Math.pow(i, 2);
while (j <= n) {
A[j - 1] = false;
j = (j || 0) + i;
}
}
}
for (x = 2; x <= n; x++) {
window.alert([x,': ',A[x - 1]].join(''));
}
Interesting that in the initialization loop it sets A[0 - 1] to true, yet in your blocky code it appears to be iterating from 0 to n. In fact it always seems to be offsetting by one in array access ... 1 based indexing maybe?
Correct, you should see the looks on non-programmers' faces when you tell them that the first element in a Java list is #0, the second is #1, etc. It's approximately the same look as you see on programmers' faces when you tell them that the first element in a Blockly list is #1, the second is #2, etc.
Still, the blocky code reads "count with i from 0 to (get n)", but the loop generated is accessing A[0-1]..A[n-1]. JavaScript is forgiving here, but A[0..n] is not the same as A[-1..(n-1)] (at least I'm not familiar enough with JavaScript to think otherwise).
If they are mapping index 1 to index 0, then it makes sense that 0 would map to -1 since it is one less than the first index. The bug is in the blockly sieve.
I understand why they are offsetting the index, it just makes things somewhat unintuitive. In most programming languages A[-1] is the same as A[len(A)-1] (assuming zero based indexing) ... so in Blocky is A[0] expected to mean the same thing as A[len(A)-1]? Nothing here is a show stopper, just a detail that could use a bit of tightening up.
The name of this language immediately made me think of the blocky.io (http://blocky.io/) visual programming language, which was written in Common Lisp by David O'Toole before this language was developed. Blocky.io is very similar to this language, in more then just name, it even has its own MIT scratch like interface: http://blocky.io/blog/wp-content/uploads/2012/03/Screenshot-....
Interestingly, that causes an "Aw, snap!" in Chrome (beta channel) for me. (Fresh load of the maze demo; right-click on the only block on the screen, click "add comment".)
while (true) do
if not (wall to the left) then
(turn left)
while (wall ahead) do
(turn right)
(move forward)
This uses the general maze-solving logic of following the outer wall in one direction until you find the exit. It never turns then turns back or runs into a wall.
The puzzle-piece representation of structure is neat, but at a 2-minute glance it seems not to scale to real complexity.
One of the big ideas in programming is abstraction/modularity/reuse, and I don't see how that fits in here.
(I found the "procedure" block, but I don't see anything that fits inside it other than "break out of loop", which doesn't make any sense. And I don't see how to call the procedure.)
So I find myself looking at the samples everyone's demonstrating here and finding they're harder to read than real well-organized code.
I should note that the appearance of Blockly is very similar to App Inventor[1]. It seems that visual programming languages with imperative and sequential semantics converge to one direction: "blocky" combining core primitives and custom primitives. In this sense I think it's THE future of domain-specific languages.
Looks good, but I just crashed my chrome after putting a "repeat while>and" block in between one of the move functions. Might want to watch out for new users accidentally crashing their browsers while trying to do something innocent.
This past weekend at the Vancouver Polyglot Conference there was a session with the author of Waterbear (http://waterbearlang.com/) that got a fairly good turnout. It looks remarkably similar.
Number of one-bits in 1 bit numbers from 0 to 1 = 1
Number of one-bits in 2 bit numbers from 0 to 3 = 4
Number of one-bits in 3 bit numbers from 0 to 7 = 12
Number of one-bits in 4 bit numbers from 0 to 15 = 32
Number of one-bits in 5 bit numbers from 0 to 31 = 80
Number of one-bits in 6 bit numbers from 0 to 63 = 192
Number of one-bits in 7 bit numbers from 0 to 127 = 448
....
JS:
var list;
var x;
var prev;
var onebits;
var doubleatprev;
list = [];
list[0] = 1;
list[1] = 4;
for (x = 2; x <= 20; x++) {
prev = x;
onebits = Math.pow(2, prev);
doubleatprev = list[x - 1] * 2;
list[1 + x - 1] = onebits + doubleatprev;
}
for (x = 1; x <= 20; x++) {
window.alert(['Number of one-bits in ',x,' bit numbers from 0 to ',Math.pow(2, x) - 1,' = ',list[x - 1]].join(''));
}
Took 15 minutes to code up and 45 minutes to debug the array indexing :) One of these days I'll be able to write the JS and get the Blockly instead of the other way around - that'd be super awesome!
Took 15 minutes to code up and 45 minutes to debug the array indexing :) One of these days I'll be able to write the JS and get the Blockly instead of the other way around - that'd be super awesome!
Does Blockly support turning JavaScript into blocks? That could be useful for visualizing minified or unfamiliar source code.
A shorter explanation with no binomial coefficients in it: Write down those 2^n numbers once in order, and once in reverse order, and pair them off. Note that each x gets paired with 2^(n-1) XOR x. So each number and its partner have exactly n 1-bits between them. In other words, twice the number we're looking for is 2^n.n; so the number we're looking for is 2^(n-1).n.
(More informally: Each bit is 0 half the time and 1 half the time, because you can pair off x and 2^(n-1) XOR x. Therefore the total number of 1-bits is half the total number of bits, QED.)
Dude, thanks for that! I really enjoyed the closed form solution, though there is absolutely no way I could have come up with that under time-pressure in a codesprint.
My solution was rather trivial:
The base case is 2 bit numbers, which are 00,01,10 and 11. The total number of one-bits is 0+1+1+2 = 4.
From then on, I just used recursion.
3 bit numbers are really 2 bit numbers with a '0' prefixed half the time, '1' prefixed the other half of the time. There are 8 3 bit numbers, so you are tacking on the '1' 8/2 = 4 times. So 4 + twicetwobits = 4+2 x 4 = 12.
4 bit numbers are really 3 bit numbers with a '0' prefixed half the time, '1' prefixed the other half of the time. There are 16 4 bit numbers, so you are tacking on the '1' 16/2 = 8 times. So 8 + twicethreebits = 8+2 x 12 = 32
If you write out the recurrence relation, it looks like:
f(n) = 2^(n-1) + 2 x f(n-1)
This seems silly since you can neither define f(n) nor recursively call f(n-1) in Blockly just yet. But if you memoize the f(n-1) results in a list, the recurrence is computable by straight iteration - which is exactly my Blockly solution.
Hey, you can create new maze puzzles for your fun from the JavaScript console (WebKit Inspector, Firebug,...)! First create a new function to paint the custom map by pasting this code into the console: https://gist.github.com/2848451
Next setup Maze.MAP matrix with value 1 for empty cell, 0 for path and 2/3 for start/finish positions.
Now run loadMazeMap() to load your new challenge ;)
128 comments
[ 3.2 ms ] story [ 173 ms ] threadEdit: Here's my old Actionscript library in case anyone is interested. https://github.com/trun/flashblocks
It was presented at JSConf last year: http://blip.tv/jsconf/jsconf2011-dethe-elza-5942746
Waterbear isn't a language like Scratch, it's a toolkit to create a Scratch-like visual programming interface to any language you like. There is active development on wrappers for Javascript, Java robotics, and Arduino.
I am so freaking proud.
[1] http://byob.berkeley.edu/
This might change your idea: http://day.scratch.mit.edu/
It's not finished yet, but it sure beats MIT's attempt to port Scratch from Squeak Smalltalk to Adobe Flash...
Edit: I didn't know that an else was possible, so I had to do it this way.
Imagine a 5x5 square race track, with spokes coming from the outside of the wheel to the center, where there was a flag. Your algorithm (and my modified one) would just spin clockwise around the track without ever realizing it should take a right towards the center.
http://i.imgur.com/gNaRA.png
http://i.imgur.com/TgS8I.png
Here's one with same amount of code and optimal logic (for this map) without hard coding. It also ensures that there is a forward step in every iteration of the while loop.
Basically it's just an order of preference:
Turn right > turn left > go straight
Definitely worth watching.
[1] http://code.google.com/p/google-diff-match-patch/
"Google blocky" > 50% brand.
http://en.wikipedia.org/wiki/App_Inventor_for_Android#Histor...
[1]: It also only allows variables to be specified from an extendable set, preventing certain problems with unbound or misspelled variables. I can see the possibility of also preventing type errors by constraining shapes further, e.g. all integers could be circular while booleans are hexagonal, so and would have two hexagonal spaces while + would have two circles. If I'm not mistaken, Scratch does something like this, although I do not know how far it is taken there. It would be interesting to see how far this can be developed to constrain the space of possible incorrect programs.
It was pretty fun.
JS generated isn't so bad..
As an aside, Lua also uses 1-based indexing.
Unsurprisingly, it still works (it just loops a few too many times).
while (true) do if(wall ahead) then turn left else move forward turn left if(wall ahead) turn right
One of the big ideas in programming is abstraction/modularity/reuse, and I don't see how that fits in here.
(I found the "procedure" block, but I don't see anything that fits inside it other than "break out of loop", which doesn't make any sense. And I don't see how to call the procedure.)
So I find myself looking at the samples everyone's demonstrating here and finding they're harder to read than real well-organized code.
As evidenced by this thread a 'Share' button would be great.
I'd love to be able to duplicate blocks by shift-click-n-drag.
[1] http://www.appinventor.org/
the problem: Count the number of one-bits from 0 to 2^n - 1, for n from 1 to 20.
my solution: http://i.imgur.com/hUxt0.png
when you run the solution:
JS: Took 15 minutes to code up and 45 minutes to debug the array indexing :) One of these days I'll be able to write the JS and get the Blockly instead of the other way around - that'd be super awesome!Does Blockly support turning JavaScript into blocks? That could be useful for visualizing minified or unfamiliar source code.
(More informally: Each bit is 0 half the time and 1 half the time, because you can pair off x and 2^(n-1) XOR x. Therefore the total number of 1-bits is half the total number of bits, QED.)
My solution was rather trivial: The base case is 2 bit numbers, which are 00,01,10 and 11. The total number of one-bits is 0+1+1+2 = 4.
From then on, I just used recursion.
3 bit numbers are really 2 bit numbers with a '0' prefixed half the time, '1' prefixed the other half of the time. There are 8 3 bit numbers, so you are tacking on the '1' 8/2 = 4 times. So 4 + twicetwobits = 4+2 x 4 = 12.
4 bit numbers are really 3 bit numbers with a '0' prefixed half the time, '1' prefixed the other half of the time. There are 16 4 bit numbers, so you are tacking on the '1' 16/2 = 8 times. So 8 + twicethreebits = 8+2 x 12 = 32
If you write out the recurrence relation, it looks like:
f(n) = 2^(n-1) + 2 x f(n-1)
This seems silly since you can neither define f(n) nor recursively call f(n-1) in Blockly just yet. But if you memoize the f(n-1) results in a list, the recurrence is computable by straight iteration - which is exactly my Blockly solution.
Next setup Maze.MAP matrix with value 1 for empty cell, 0 for path and 2/3 for start/finish positions.
Now run loadMazeMap() to load your new challenge ;)
Example: http://www.dodaj.rs/f/f/nM/4w3wop7u/custommaze.png