Wow this is cool and you did this really fast!

So you did kind of a functional style where each row represents an instruction being run with a full copy of the state of the VM at that point in time. Then each subsequent row is based on the state of the previous one. Am I reading that right? (I'm not familiar with Brainfk)

Yes. Had to store state somewhere, spreadsheets find "one row per thing" to be most natural, and in my case the "thing" I'm working with is state, so one row per state transition it is.

The more interesting hackery is in the parenthesis parser...

Yeah I don't follow the parenthesis parser. Plan to do a write-up of some kind on how it works?

The basic algorithm is "parentheses counting": walk the string starting from an opening bracket, counting +1 per `[` and -1 per `]`; when you reach 0 you're at the matching closing bracket.

First, lets split the code to one char per row:

    =MID($A$1,D3,1)

(D3,D4,... are simply 1,2,3,...)

Now, lets parse `[` as 1, `]` as -1, anything else as 0:

    =IF(E3="[",1,if(E3="]",-1,0))

Now, we will need one column per character in the code, where in the i'th column the first row is the i'th character's value and each row we go down accumulates the value of the next character.

    =G2+OFFSET($F2,G$1,0)
    =G3+OFFSET($F3,G$1,0)
    ...

(Column F is the 1,0,-1s. Row 1 is 0,1,2,3..., this time horizontally, which we use to translate horizontal motion into vertical motion)

Now for the i'th row of the "] match" column, lets find the index of the first 0 in the i'th column, and add `i-1` to get an index from the beginning of the code instead of from the opening bracket:

    =MATCH(0,offset($G$3,0,D3-1,18,1),0)+D3-1
    =MATCH(0,offset($G$3,0,D4-1,18,1),0)+D4-1
    ...

And all that's left is reverse-search this table to find the matching opening brackets to every closing bracket, and while we're at it lets clean up all irrelevant rows to the empty string:

    =IF(F3=1,C3,IF(F3=-1,MATCH(D3,$B$3:$B$20,0),""))

(D3 is the index of the closing bracket, $B$3:$B$20 is interestingly the column we're currently in - Sheets does not complain as long as there is no actual circular referencing going on)

Voila! Column B now contains for every bracket its matching bracket's index in the code, and for anything else, "".

Oh, that's pretty clever. Thanks for the explanation!

Awesome, nice work.

This is very cool as well.

A comment about how you have presented this - not everything has to be an interesting technical accomplishment.

Creating beginners is a much harder skill and topic than most realize.

Making topics easy to approach and learn is often much harder than learning the technical topic.

Impressive how quickly you whipped this up

My previous startup was about teaching programming to beginners with computer games, so I definitely have an appreciation for that. I made sure to point out that I still consider Brian's accomplishment very impressive.

It's just that I clicked hoping for one thing and found another, so I felt a need to show that the second one is also doable :-)

Also, it took me more than I expected. I had to go through a couple of wrong approaches and some confusion until I figured out bracket matching, and also had a bug or two that took a while to debug in the interpreter table. These things aren't hard to make! Try it sometime :-)

Neat to hear you're in the edtech space as well - I am as well at present.

Would love to learn and chat a bit more about your previous startup (I see you have posted below and will reply there).

Sure! I emailed you. Or we can discuss it publicly here :-)

What was your previous startup? Are you still connected to anything like that these days? Sounds super cool.

We were bootstrapped and only sold in Israel, so there is nothing about us in English.

It started with a programming course I founded for data analysts in my army unit that taught them enough Python and sql and requests and win32com to be able to automate significant parts of their own jobs, creating a lot of value, and I wanted to figure out how to teach the same course outside.

The answer was "nobody outside the army knows how to deal with losing an employee for 3 weeks", so we cut the material again and again and even at the minimum we could reach - 80 hours - we couldn't make a single sell.

So my cofounder quit and I started playing with different models of teaching, and found out that there are huge benefits to teaching with a computer game (more fun, more engaging, more self-driven, but mostly - you get so much data and can optimize your lessons so fast... I really don't understand why e.g. Codecademy don't do a lot more data-based micro-optimization).

I partnered with some people that sold after-class activities to middle schools and we sold a lot more courses than we planned, so I had a frantic year of supervising the teaching of 14 courses while trying to amend my weekend prototype to teach the whole material. On the way I developed a bunch of other nice teaching activities.

But working alone sucked, so I put it on hold and went looking for the best team I could find for my "real" startup (this one was started with the explicit intention of failing but learning as much as I can, as I was pretty clueless in business at the time).

I strongly believe in educational technology as an efficient way to improve the world (though a bit less than I use to as a way to get rich). I fully intend to return to working in the field when I'm no longer needed at FeezBack (sorry, again we're Israel-only at the moment, so no links).

Interesting. I'm familiar with Israeli tech companies and it's odd they wouldn't buy in.

בהצלחה!

Also, I think I'm going to use this in beginners' lessons in programming from now on. Everyone understands the level of Excel formulas used in the orange table, so this really shows how simple a thing a CPU is.

Have you used Brainfuck in an educational context before? It seems rather esoteric and unfamiliar, especially for beginners. They will likely be distracted by the inscrutable syntax and "what the fuck is Brainfuck?" (the name itself, which you feel the need to censor, seems problematic for many educational settings).

I would say that the original submission illustrates much better how simple a CPU is. And it actually exposes the user to syntax (ASM) and concepts (program counter, registers, memory usage, stack, etc) that directly transfer to basic CPU design. Your version, while technically more impressive, buries this under formulas and the particulars of parsing a language nobody uses.

FWIW, I agree with j45 that you presented this poorly. From being "disappointed" and "fixing" another user's submission, to your token parenthetical (in which you actually did not "make sure" to say it was "very impressive"). It all seems a bit condescending and arrogant for someone who would be an educator. Compare the tone and demeanor of his comments on your submission (positive, supportive) to yours on his (negative, critical).

First of all, I must agree about the way I presented it, and admit that when j45 posted that first comment I checked if I could still edit my post and it turned out I couldn't.

I've used Brainfuck in some educational contexts (like the talk on virtual machines that I gave in PyCon IL a few weeks ago and in a local python meetup before that), although not yet with complete beginners.

It's useful in some contexts and not others. It's especially useful when some of your audience has heard of it before.

It's especially useful because it lets me mention other "war stories", like this one (students love war stories): https://news.ycombinator.com/item?id=7943514

Before I teach asm, I always take 1.5 hours to teach an exercise I once developed called the "shirts exercise", which is about optimizing code for a simple and very intuitive vm that looks a lot less like real asm than Brainfuck does (for example, it has conservation of material). Real asm has so much incidental complexity and I prefer to show the beauty and motivation for learning it before we start learning about number encoding etc'.

The reason to use this spreadsheet is that it's written in a format that my students would be able to follow and understand. So if I tell them "this is exactly how a computer is built", I hope to demistify a bit the idea of a computer. A good programmer is a programmer that is not afraid to dig into abstractions.

(Replying next to you because I can't reply deeper)

I don't feel you were overharsh, you justifiably called my bullshit, which is an important thing to do once in a while.

Re: Brainfuck in education, it's not about unfamiliarity, it's about time-to-grasp-core-idea, and number-of-other-ideas-you-need-to-understand-first. You really want to minimize those.

Specifically in teaching asm, you want your students to reach as fast as possible the state where they completely wrap their head about all the details and edge cases of the machine. Brainfuck is a really simple machine, very easy to hold completely in your head. Even the simplest RISC processor that can do anything real would require you to first understand binary, hex, two's complement, the idea and implementation of a stack, and so many more things...

For another example see this Twitter discussion between David Beazly, Aaron Meurer and myself on the subject of teaching TDD to complete beginners: https://twitter.com/dabeaz/status/879487816538914817

FYI: if you click on the comment time-posted link (n [minutes/hours/days] ago), you can reply even when the reply link doesn’t show up.

Thanks for the response, now I feel like I was, in turn, overly harsh, haha.

I can see where using Brainfuck would have its advantages, sometimes that unfamiliarity can help you focus on the underlying abstractions rather than the syntax.

The creator of Brainfuck, Urban Müller, made a once in a lifetime presentation about it recently. It was at a company event where we had the pleasure of watching him talk about how he developed it. If you are interested you can check it out at the livestream recording that was posted in youtube (position 2:52) https://youtu.be/gjm9irBs96U?t=8722

If you still don't get some part of what's going on after copying it and playing with it a bit (A1 is the code, A2 is the input, you can find an explanation of BF and a simple Python implementation in my linked slides), try reading my discussion with briansteffens, who is also the guy who wrote the Apps Script implementation that inspired this.

See also: https://www.youtube.com/watch?v=uNjxe8ShM-8 (On The Turing Completeness of PowerPoint)

This is why I come to HN.

Wait, did you use to work for Codecademy? Can we chat a while? As a former competitor, I am really curious why you did some stuff this way and not that, and would really like to be able to recommend you to all the people asking me how to learn programming now that I don't actively teach anymore.

This probably wasn't why he came to HN..

It helps to visualize the machine activity if you use conditional formatting to show the cursor location:

https://docs.google.com/spreadsheets/d/1ZJECuw6GXA_wEMnfe2Oj...

Next step is emulating a more fulfilling instruction set using formulas only?

Not sure what you mean by "more fulfilling", but I don't think any new techniques would be required. I encourage you to try! Maybe build a Forth? That would be extremely cool!

You made my day. Though an explanation would help understanding it. For the commonfolk like me.

I suggest you first try to follow it yourself, maybe copy and play with A1 and see what happens, maybe copy aside parts of the formulas and see what they output.

Then you can read the writeup I wrote in response to another commenter (the guy who wrote the original Apps Script VM).

Brainfuck is a stack-based language with only 6-8? syntactic elements for manipulating the stack. + increments the current stack element, - decrements it. > increases the stack pointer and < decreases it. [ and ] have to with conditional jumping I believe. And it is common to convert the elements in the stack to ascii characters to display a result.

So if you go to the orange section of the sheet you see where the program state is displayed. Each row represents the state of the program at that point. The "Out" column is the stack represented as ASCII characters. The "Cursor" column is the stack pointer. The "IP" column is the instruction pointer (which instruction you're currently looking at). The "Instruction" column is the instruction being done at that point in time. The "Cells" column is the stack displayed from left to right.

I may be a little off but that is the general idea.

You got it basically right, a few small corrections:

Replace the word "stack" with "memory buffer" or "tape" everywhere. "Out" represents STDOUT, there is the "." command for printing (and "," for reading from STDIN).

Thanks!

Ah. I thought "." must be printing (as it's something similar to that in Forth [guess it's ".s" though not "."]), but I was confused by the comma because I didn't understand how you'd be reading from stdin here. Actually I'm still confused. What are you reading in?

`.` in Forth is to pop a number and print it, `.s` is to print the whole stack non-destructively

A2

Welcome back to 1985