How to make a visual programing language like snap

Computer Science
42

Yeah, that's what I thought, I mis-spoke. What I should have said was "once it clears that base case, it moves to the next step"

You give it the values of coins, and the total amount of money you want, not the "count of each coin"; that's what it has to figure out.

As in, the final block is essentially a list of the coins and their weighting, so coin one should only be used once, but coin five can be used fifty times.

As expanded in the next part, it's driving home that computations can be more complex than they appear but that complexity can be controlled if you know how to break down the problem.

43

Actually the final block reports the value (denomination) of each kind of coin. Or put more precisely: the coins are supposed to be sorted by value from small to large, so if you have one kind-of-coin, they are all cents (value = 1); if you have two kinds-of-coins, they are nickels (value = 5) and cents; if you have three kinds, they are dimes (10), nickels and cents. Within the scope of this problem the numbers of coins of each of the (5) denominations is unlimited.

Perhaps you'd better try to implement SICP's Scheme code bottom-up, so start with making a first-denomination block in Snap!.

Whatever Abelson and Sussman (and @bh?) may say, you're not the only one who'll find reading Scheme (or Lisp, for that matter) is challenging - Snap! is equally powerful, but much easier to read (and write) for the rest of us.

44

By Weight, I mean mathematical average weight. A coin with low value is going to be used more because it has less weight that the high-value coin which won't be used as often.

Anyway, the point is I skipped it for now, figuring I know what it's driving at and I'll revisit it later...
I'll revisit it at some point... Maybe. Eventually... (Chances are low)

Basically it's because my issue was only the example actual code, not the problem itself.

45

Huh. This idea about weights of coins is interesting. I don't think I've ever heard it before in this context.

I'm not (yet) convinced it's relevant. It'd be more convincing if the question were something like "What is the most probable collection of coins to make this amount of money?" But even then, if I want to give you 25¢ I'm much more likely to give you a quarter than to give you 25 pennies.

But this isn't a question about the most practical way to make this amount of money in coins either. So I did an experiment to test your theory. For no particular reason my favorite amount of money to play with in count-change is $1.37, and I restricted the coins to quarters, dimes, nickels, and pennies. Turns out there are 517 ways to do that, and if you combine all those ways, the total numbers of coins used are 571 quarters, 1768 dimes, 3784 nickels, and 19954 pennies. So, unsurprisingly, we use way more pennies than anything else, as you say. How precise is your idea that the number of uses of a coin is inversely proportional to its value?

count change script pic
count change script pic914×290 40.6 KB

That's in the ballpark, but the high-value coins are used even less than your weighting theory would predict. Still, that's a really good intuition that would never have occurred to me. But you said

and that suggests to me that you think this weighting business isn't just a ballpark intuition but a rule, and it isn't. To take an extreme case (which is always a good way to stress-test ideas), if you ask for (count-change 1) then you'll use one penny, but zero of all the other kinds of coins, not anything like inversely proportional to their values.

I'm not sure exactly what tree you think you're traversing. Could you maybe sketch the tree for 11¢? Because yes, any branched recursive problem can be thought of as a tree traversal, for some tree or other, but that's not at all how I think of this problem. I think, the number of ways to make this amount with these coins is the sum of

  • the number of ways using the first kind of coin
  • the number of ways not using the first kind of coin

and each of those can be expressed as a call to count-change. For me, the virtue of this way of thinking is that it's very close to the language of the problem itself (high level of abstraction) as opposed to the language of data structures (lower level of abstraction).

You're right that it lists the values of the coins, not their weighting, but as it turns out they don't have to be in any particular order. You get the same answer however they're arranged. A question we asked in lab in our SICP course: Is ordering the coins small to large faster, slower, or the same amount of time as ordering them large to small?

46

I have NOT tried but I’m pretty sure the order as used in the SICP example (try “large” coins first) is superior (in terms of evaluation speed) to any other order. The number of branches to be visited is determined solely by the number of failed attempts. An extreme example: coin values are 1 and 100, how can one pay 99?

  • If one starts with trying 100, it will turn out that this is impossible, the algorithm will find 99 x 1, and terminate.
  • If the order of coins is reversed, 100 is tried, 1 + 100, 2 + 100, …, 98 + 100, all fails.
47

Wait what? If you start with pennies, you find 99 pennies first thing. (That is, you try one penny, that's not enough, so you add a second penny, etc.)
Then you try 100 and fail.

If the goal were to find any one successful bunch of coins, starting with pennies would be slightly better because it'd never get around to trying 100 so there would be no failures. But if the goal is to find all possibilities, then the two orders are equally good in your example.

48

You’re right, I was mistaken. In fact all orders are equally good in any case. My fallacy was I didn’t consider the algorithm would try to search a path without any coin denominations left; but actually the relevant test is performed inside a call, not a priori.

49

Would you be helped by a “Reverse codification” function, one that would translate any Scheme code to Snap! blocks?

50

Fair Warning. RAMBLING MADWOMAN AHEAD.

That's very much been my goal from the beginning.

The problem I have with programming languages and abstraction, is I'd MUCH rather see the mechanical nature instead of trusting someone telling me "oh this works"

I love snap! but the world of CompSci is sadly powered by c or javascript or "insert brand name here"

The reason I keep trying to use snap! is because Snap! is very much almost there, by showing rather than telling you can demonstrate what's going on, which is why the frame by frame stepping is my favourite feature in snap!

That however is my beef. Sure if I take these scheme reporter out and make them use script variables, I can see the machine a little better, but what I'm actually seeing is still symbolism.

I don't know if the Snap! fork Edgy is still being maintained, but when someone showed me it I was overjoyed, because I was going to have so much fun... except, due to the "just trust us dude" nature of programming and abstraction.

What I got was not what I wanted and I ignored it. Maybe it got better, maybe it didn't... but SHOW, not Tell.

My primary thesis, and one I'm trying to wrap my head around old programming languages so I can use snap! to prove or disprove, is that Programming Languages and Abstraction are actually no longer relevant and if we keep using them, we're creating a whole game of telephone and eroding the power of comp-sci, because the whole NATURE of programming, as it stands, is the assumption, that someone, somewhere else knows what's going on and that all you need to do is find them and ask.

There's a fantastic example of this in SICP.

Chapter 1.2 is about using "simple" functions to build "advanced" things, ie, by breaking things down into pieces you can take a whole slew of smaller pieces to build larger more complicated things, like as Brian said elsewhere on this forum "The fact that Snap! looks like Lego isn't accidental"

What happens is one of the bigger programs in that section suddenly without rhyme or reason introduces "even?" into the logic. Now, having used an actual scheme interpreter when I first read the book, I know what Even? does, and I know it's a predicate.

But there's no explanation, it's just THERE.

And then, six pages later we get THIS

Of course we could get along without ever defining this procedure, by always writing
expressions such as
(* 3 3 3)
(* x x x)
(* y y y)
and never mentioning cube explicitly.
This would place us at a serious disadvantage, forcing us to work always at the level of the particular operations that happen to be primitives in the language (multiplication, in this case) rather than in terms of higher-level operations. Our programs would be able to compute cubes, but our language would lack the ability to express the concept of cubing.

Which is exactly what they just DID with the "Even?" primitive...

And it's not just SICP. Almost every programming textbook that I've read makes this mistake multiple times.

I know someone with a Doctorate in this, he's very smart, and I'm one of the reasons he got that in the first place! He's an expert in this stuff, and I whined to him about that and he said "Those are reference manuals, you're not meant to read them, you're meant to REFERENCE them"

The frustrating thing to me is he, completely without realising it, is demonstrating exactly the Telephone effect without understanding he's doing it.

To not be guilty of what I'm complaining about, Telephone is the game we teach pre-school children about how if you have a string of people passing messages, there is a very high chance the message gets garbled, and even if you remove the kids doing it deliberately, the garbling still happens by accident.

Computational Technology as a whole, think's it's not making the telephone mistake, while very much MAKING it, and insisting it's not doing any such thing.

And it annoys me to no end because as someone who loves technology, but for a whole host of reasons over the years ended up on the outside of the technology industry looking in and watching this slow motion train wreck unfold and no way to prove it.

Until I found Snap!

Except Snap! is still considered a novelty and the person I mentioned earlier still considers it "training
wheels" for "production languages" a logical fallacy that gets bandied around in these forums too!

Block Languages are not training wheels, they're the biggest ducking paradigm shift in the whole computational industry and the whole ducking industry is desperately trying to pretend it's not coming like a freight train to ruin everyone's day.

END RAMBLING MADWOMAN. (If you see this post it's because I didn't freak out and delete it half an hour later LOL)

51

I don't understand your complaint about EVEN?. They could have just said

(= (MOD foo 2) 0)

all over, but instead they defined a procedure with a name that says what it's for. Just like CUBE.

52

In fact they defined (even?) immediately after its first use:

We can express this method as a procedure:
(define (fast-expt b n) (cond ((= n 0) 1)
_ ((even? n) (square (fast-expt b (/ n 2)))) (else (* b (fast-expt b (- n 1)))))) …

- - - page break - - -

… where the predicate to test whether an integer is even is defined in terms of the primitive procedure remainder by:
(define (even? n)
_ (= (remainder n 2) 0))

Stiil, I think I do understand at least some of what @callietastrophic is trying to convey (what follows is my own perspective, not necessarily the same as callie’s).

The world is getting more and more complicated each day, with multiple layers of hardware, software, networks, services, and what not.

  • I guess not even the lead design engineer of e.g. a common household appliance, like a washing machine, fully grasps how it’s made and why it works the way it does: the mechanics, materials science, software, manufacturing technology, logistic chain, part design features, etc.
  • When in need of help with any product or (network, financial, government, …) service that isn’t easily replace, if one manages to reach a help desk in the first place, chances are it’s still going to take days or weeks for one’s problem to be solved, if at all.
  • Society at large has become so complex that even the most competent public administrators are unable to fundamentally solve them.

At the same time all of us have grown ever more dependent on products and services we don’t understand anymore.

This state of things is not a disaster per se, if we can trust suppliers and experts to do the best they can, and they in turn can trust their experts and suppliers. Trust these days is among the world’s most prized assets. Of course it helps if it is tested now and then, with positive result; and if “trustees” facilitate inspection of their work.

Like @jens explained recently Snap! was not designed for fast execution, but rather for easy and safe operation also by inexperienced users. I guess there would be an opportunity for a mainstream production language with a block-based user interface, but that’s a different animal.

53

Yeah, that would be GP.

I definitely share this feeling. Partly it's because people are asking more from their computers (including phones in that category), and also partly because software has become an object of commerce. I grew up in a world in which if I had a problem with someone else's software I could read the code and fix it. But, yes, even free (as in Free) software has become super complex.

But no one person fully understood a washing machine down to the materials science even before they had computers in them. And that was a good thing! If you had to be a materials scientist to repair a washing machine, there would be a lot more washing machines in landfills. Washing machines are repairable because of abstraction, same as in software. Without abstraction, nobody except Jens would be able to write a program in Snap!.

So it's a dialectical contradiction. Complexity means you have to take a lot on faith, but it also means we can have smartphones and CT scanners and vaccines and electric cars.

I don't think the issue with help desks is about complexity, really. It's about economics; companies can't waste engineers on answering telephones.

tech_support
tech_support625×923 122 KB

The actual magic word is "elevate," as in "I'm going to elevate your problem to a higher level."

And as for society, I'm afraid the problem isn't complexity, although there's plenty of that in a bureaucracy, but capitalism. The wealth dichotomy these days means that social resources are concentrated in private hands (a few private hands). If we could somehow implement a 100% tax on wealth over $1B, just watch those public administrators start solving problems!

54

I had never heard of it, it’s not even in Wikipedia. So not mainstream (yet).

I’m afraid there’s not one werewolf, and therefore no silver bullet.

55

Right. But I mean, that's one of its goals -- to be a visual language for professional programmers. Used to be its only goal, but it turned out to be more popular among teachers and kids than among pros.

Aren't silver bullets for vampires?

Anyway, you're right and wrong. Yes, there are lots of things standing in the way of a perfect society, but a lot of them are reducible to capitalism.

If you haven't already, you should try to watch Fred Wiseman's film Welfare. It's three hours long, it's painful to watch, and it doesn't settle the question we're discussing. There is certainly plenty of incompetence and just not caring on the part of the welfare office staff, supporting your candidate, but to my eyes anyway it's very clear that the welfare clients would be treated much, much better if they had money. (I know, then they wouldn't be at the welfare office, but, you know, imagine the same bureaucrats as the receptionist at the doctor's office.) One virtue is that, unlike many of Wiseman's films, this one turns out (by an accident of filming in the right place at the right time) to have a hero, a welfare clerk who just decides, for no particular reason, that this client in front of him right now is going to get what she needs, and who walks her paperwork through half a dozen offices, then more or less blackmails his boss into signing the final approval.

EDIT: I should have made clear (I always assume everyone knows Wiseman's work) that this isn't a scripted movie, but a true documentary shot in a NYC welfare office with no added commentary, other than the implicit commentary in Wiseman's editing of the footage..

56

This expanded quickly in a direction I wasn't expecting it to take lol.

First things first, an apology. Namely, after both of you showed me where it WAS defined, I magically found it... There is a reason I usually vent into the ether and then delete those rants and try and find an alternate path.

Also part of the problem is this time I was reading a pdf version of the file, one that has as a preface that they were using a .tex file converted to html, intended to be read on emacs. (and the writer of that preface says, "The conversion isn't 100%, we'll let the reader find those mistakes" (Welp. It worked! (I did find a land-mine mistake) because they're making the erroneous assumption whoever grabs the pdf also has the .tex file and the patience to compare)

Somewhere along the line, actually demonstrating the game of telephone I was complaining about, a revision of a revision of that html file was converted to pdf and put on the MIT website, so when hapless people decide to teach themselves SICP and the pdf link appears on the MIT website, they assume it's legit.

That's my fault, because last time I read the book I used the Open Access version on the MITPress page, and I should have again, because lo and behold, the example that angered me enough to complain on these forums, is formatted correctly and in the same way the chapter 1 scheme file presents it, because that scheme file comes from the same page, on the Open Access page link.

So I should have checked, but my point's been proven in a different way. This is my issue with tech, not so much the issues with capitalism, which while absolutely correct, also mean that instead of finding out how to fix it, the problem is perceived as insurmountable and thus not worth it, and the endless game of telephone continues.

So from here on in, I'm using the Open Access version and Snap open side by side. (Last time I did this was on a much smaller monitor, it worked but was very much a kludge. (I looove ultra-wide screen)

Alright. Let's keep going.

57

Can you point me at the bad MIT version? That should be fixed, by replacing it with the MIT Press version. Thanks.

58

"https://web.mit.edu/6.001/6.037/sicp.pdf"

If you drop down to 6.001 it says "we don't really teach this anymore, try this" which jumps to 6.0001 which is the 2024 course.

59

Oh, I see. That version is a special-purpose one meant for reading in info (i.e., in emacs) or in a Kindle-ish device. You should definitely use the HTML version at MIT Press if you're reading in a browser.

I have posted a comment at sicpebook.wordpress.com suggesting that they make a more prominent display of the link to that version, but I have no idea if anyone's actually maintaining the site.

I've also emailed Hal and Gerry to suggest that that 6.037 page should point to the MIT Press versions (pdf and html), but I don't know if they actively maintain 6.001's web presence at MIT.

60

I mean, I don't really care if I use PDF/HTML/TXT. As long it formats correctly, which, it isn't doing.

I mean, I'm still having trouble trying to make sense of coin change even in HTML. So much so I'm watching Doctor Who instead lol. (Not the idea, just the code, but I'll not open that can of worms again)

The thing is, my point still stands, yeah I can copy that text... Though if I stop stalling I'll probably turn the kind of coins into a list of lists instead of a conditional.

But I'd still rather watch what it's doing instead of getting a reporter that spits out 292 when I input 100, and I'm vaguely hoping I can eventually get there (I deleted another rant fyi)

Maybe I'm still chasing down the wrong path, chances are high I absolutely am, but the only way I can figure out I'm wrong is to, you know, be wrong? Once I'm wrong, I'm right, because I now have the information I didn't have before, and abstraction, for me (and maybe only me), doesn't let me be wrong, it tells me "No, go away" and I do not like being told to go away.

61

Good idea! Then you won't just be copying the code.

You don't need a list of lists, though, just a list whose items are numbers, the denomination ot the coins (1, 5, 10, 25, 50).