7 ms·

Show HN: A virtual machine made with Google Sheets formulas (no script)

620 points by SonOfLilit 9y ago

In a popular post today[1] the title claims "VM in Google Sheets", but it's actually in Google Script, which is basically Javascript and not an interesting technical accomplishment (definitely a useful educational tool, though). Disappointed, I set out to fix it. Voila! https://docs.google.com/spreadsheets/d/1g3-FZBnkDuLqFYOmk457hOvyrS798vO4X2nV77gVzGI/edit https://docs.google.com/spreadsheets/d/1g3-FZBnkDuLqFYOmk457... A Brainfk interpreter in pure Google Sheets formulas. The hard part was parentheses matching, so I think other VMs would be even easier. [1] https://news.ycombinator.com/item?id=14701460 https://news.ycombinator.com/item?id=14701460

briansteffens 9y ago
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)
- SonOfLilit 9y ago
  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...
  - briansteffens 9y ago
    Yeah I don't follow the parenthesis parser. Plan to do a write-up of some kind on how it works?
    - SonOfLilit 9y ago
      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, "".
      - briansteffens 9y ago
        Awesome, nice work.
      - doubleplusgood 9y ago
        Oh, that's pretty clever. Thanks for the explanation!
kronos29296 9y ago
You made my day. Though an explanation would help understanding it. For the commonfolk like me.
- SonOfLilit 9y ago
  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).
- eatonphil 9y ago
  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.
  - SonOfLilit 9y ago
    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!
    - eatonphil 9y ago
      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?
SonOfLilit 9y ago
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.
j45 9y ago
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
- SonOfLilit 9y ago
  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 :-)
  - eatonphil 9y ago
    What was your previous startup? Are you still connected to anything like that these days? Sounds super cool.
    - SonOfLilit 9y ago
      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).
artursapek 9y ago
This is why I come to HN.
- SonOfLilit 9y ago
  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.
  - sattoshi 9y ago
    This probably wasn't why he came to HN..
    - _ao789 9y ago
      Lol, truestory
aviraldg 9y ago
See also: https://www.youtube.com/watch?v=uNjxe8ShM-8 https://www.youtube.com/watch?v=uNjxe8ShM-8 (On The Turing Completeness of PowerPoint)
GrumpyNl 9y ago
Welcome back to 1985
thriftwy 9y ago
Next step is emulating a more fulfilling instruction set using formulas only?
- SonOfLilit 9y ago
  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!
myhf 9y ago
It helps to visualize the machine activity if you use conditional formatting to show the cursor location: https://docs.google.com/spreadsheets/d/1ZJECuw6GXA_wEMnfe2OjOD0taVQTU0rTKY8PvfHQAtU/edit?usp=sharing https://docs.google.com/spreadsheets/d/1ZJECuw6GXA_wEMnfe2Oj...

620 points by SonOfLilit 9y ago

briansteffens 9y ago

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)

SonOfLilit 9y ago
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...
- briansteffens 9y ago
  Yeah I don't follow the parenthesis parser. Plan to do a write-up of some kind on how it works?
  - SonOfLilit 9y ago
    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, "".
    - briansteffens 9y ago
      Awesome, nice work.
    - doubleplusgood 9y ago
      Oh, that's pretty clever. Thanks for the explanation!

kronos29296 9y ago

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

SonOfLilit 9y ago
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).
eatonphil 9y ago
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.
- SonOfLilit 9y ago
  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!
  - eatonphil 9y ago
    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?

SonOfLilit 9y ago

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.

j45 9y ago

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

SonOfLilit 9y ago
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 :-)
- eatonphil 9y ago
  What was your previous startup? Are you still connected to anything like that these days? Sounds super cool.
  - SonOfLilit 9y ago
    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).

artursapek 9y ago

This is why I come to HN.

SonOfLilit 9y ago
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.
- sattoshi 9y ago
  This probably wasn't why he came to HN..
  - _ao789 9y ago
    Lol, truestory

aviraldg 9y ago

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

GrumpyNl 9y ago

Welcome back to 1985

thriftwy 9y ago

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

SonOfLilit 9y ago
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!

myhf 9y ago

It helps to visualize the machine activity if you use conditional formatting to show the cursor location: https://docs.google.com/spreadsheets/d/1ZJECuw6GXA_wEMnfe2OjOD0taVQTU0rTKY8PvfHQAtU/edit?usp=sharing https://docs.google.com/spreadsheets/d/1ZJECuw6GXA_wEMnfe2Oj...