Folk Computer

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== March 2024 newsletter ======

===== What we've been up to =====

==== Demos ====

  * Andrés: Progress on the template matching games demo
    * Continuing from the work I was doing last month I started by making the tracking more accurate by adjusting the algorithm OpenCV uses to find the images. There's still noise in some lighting conditions but it's generally much more reliable now.
    * Basic path drawing demo:
      * For me the natural next step once I had highlighting working last month was to make a demo tracking the position over time to enable drawing the path of the image. It's fun to paint shapes using this.
        * {{newsletters:img_4719.gif}}
    * Pac-Man-inspired demo:
      * The goal of the project is to explore game interactions using both physical and digital objects. My first mini-game exploring this is inspired by Pac-Man: generate a grid of dots, track the image, if there's an intersection between a dot and the image delete the dots. I'll build on this by having a random path of dots rather than a grid so it's a different experience every time.
        * {{newsletters:img_4925.gif}}
    * Next step: a Pong-inspired demo
      * I want to get a simplified single-player pong experience working where you move your game piece around and bounce a ball against the wall, each time the ball gets a bit faster. I've started on the basic version of this, simulating a ball bouncing in the confines of a normal Folk program. It's satisfying to watching it move around like a little screensaver:
        * {{newsletters:bouncing-ball.gif}}
    * I also spent a few days this month figuring out what sorts of game interactions I want in the project. In the end I want a booklet of at least 5 games that show off the unique combination of interactions between physical and digital game pieces that Folk provides.

  * [[https://vedranb.com|Vedran Budimcic]] has been developing his Scratch-like programming environment for Folk -- it now has animation:
    * {{youtube>Z_bMrp_-G6I?}}

  * [[https://www.forresto.com|Forrest O.]] has been doing a lot of experiments with his [[https://www.youtube.com/watch?v=2mRqCtfaogY|hexagon tiles]], making [[https://www.youtube.com/watch?v=lHjmi4cxUC4|mini-games]], [[https://www.youtube.com/watch?v=H3AHmIHRWPs|rainbow outlining]] and [[https://www.youtube.com/watch?v=ngB2AQdHdTM|animation]], and [[https://www.youtube.com/shorts/F4xEztsgJYQ|loop puzzles]]
    * {{youtube>ngB2AQdHdTM?}}
    * {{youtube>lHjmi4cxUC4?}}

  * [[https://cristobal.space|Cristóbal Sciutto]] mirrored his [[notes:tableshots|"Towards a folk computer"]] piece about tableshots [[https://cristobal.space/writing/folk-computer.html|up on his site]]

==== New evaluator ====

Omar: lots of progress on new evaluator. I spent much of this month trying different locking and reference counting and memory reclamation schemes.

A lot of it was frustrating and had me stuck, but in the last week or two I think I've figured out something that works, where on each statement and match you have an atomic reference count (number of active pointers to that statement/match) + a bunch of either immutable or individually atomic fields: stuff like clause terms, parent count, whether to free at next opportunity, list of children. Freeing each statement or match is deferred until a pointer release that makes the number of active pointers hit 0 + parent count is 0 (if statement) or free was requested (if match). Note that the pointer count is a reference count, but it's not the full reference count -- you have to combine its 'program liveness' information with 'database liveness' information (was match free requested? / did statement parent count hit 0?).

And now that we have reasonable refcount/locking, we've been able to do the long-awaited table test, where we actually run the new parallel evaluator on a physical Folk table with webcam and camera and physical programs. (We expected it to be slow -- we need the physical table test to actually know what the performance is like and how we need to go about optimizing things.) It works:

{{newsletters:img_6487.mp4}}

So, still a lot of work to do on performance, top-level flame graph not very informative:

{{newsletters:image2.png}}

Another trick that reduces the locking/refcounting complexity (and which I mentioned briefly last month): I've gotten rid of all the backward (child->parent) pointers in the system. That reduces the number of fields on each statement/match and the amount of locking needed, since you don't need to walk back and remove the child from each parent when the child is removed. Matches' backward pointer list is removed entirely, because match removal only happens when a parent is removed (you never need to walk back from a match to see what its parents are); statements' backward pointer list is replaced with the flat parent count which is just an integer (needed so you know to remove the statement when parent count hits 0) and is easy to make atomic.

(Without backward pointers to go back to the parent, how do we get rid of parent->child forward pointers when the child they're pointing at is destroyed? The answer, hopefully, is that we can just check the pointers [they're actually weak refs that contain a slot generation, not raw pointers] and throw away / ignore any that point at dead matches/statements. We can even amortize that because we already do child pointer list resizing anyway, which is already a linear scan -- just additionally do the weak ref check on resize and throw away dangling refs then.)

But that's not all implemented yet -- still need to clean up some memory leaks (I don't think we're collecting clauses yet?) and dangling pointers:

{{newsletters:image.png}}

Nice side benefit of the new evaluator: it boots much faster, making it faster to iterate and test things, because it's only compiling virtual-program-level C code (Gpu, AprilTags); the kernel is statically compiled into a monolithic folk binary. (this feels like a reasonable tradeoff, since no one was messing with the kernel in practice anyway)

Some remaining stuff to do:
  * Performance optimization so we can get it to beat old evaluator, which is the whole point
  * Implement Collect & text/labels (the major missing functionality in new evaluator)
  * Fix memory leaks (it might end up better than old evaluator here too, since that is leaky anyway)
  * Thread management so we can spin up new worker threads as needed to run Whens when current workers are asleep/blocked/unresponsive

There are still some high-level challenges from parallelizing the workqueue, stuff that we 'got for free' from having a single thread and converging to a fixed point. like, what order do you do operations in, how do you avoid wasted work, what does 'order' mean if things can happen in parallel.. I think we can hack around a lot of this by messing with priorities and specifying manual 'wait a few milliseconds' type stuff for specific Whens, or maybe having some notion of local convergence or subconvergence.

==== Live USB & distribution ====

Omar: I've been working on massively simplifying the Folk installation process (reducing the number of steps, reporting the system state better to the user so you don't just boot to black screen or terminal, making a proper calibration/setup process and props).

The main thing is making a live USB that just boots into Folk and walks through calibration & network setup and can install to disk. (the near-term application is to distribute a version of the CNC stuff as a demo that is immediately useful)

I've been using Debian live-build, which seems to be the de facto standard for making live USBs: documentation/resources are pretty good, you can preinstall any packages from Debian, etc. Good resources are https://terkeyberger.wordpress.com/2022/03/07/live-build-how-to-build-an-installable-debian-10-buster-live-cd/ and https://dquinton.github.io/debian-install/netinstall/live-build.html (it's an interesting game to figure out the minimal set of Debian packages to preinstall so you get a 1. working Folk on boot and 2. working internet connection, and after that you don't need to rebuild until you publish, hopefully, since you can hot patch from online on boot)

(I've been building the live .iso in an Intel Linux UTM/qemu VM on my Mac laptop, which is a little annoying. I think the live build process is already slow, it's not incremental at all, so it's installing all the stuff for this 1.4GB Debian setup from scratch on each build, and it's even slower because it's in emulation. I also burned some time trying to make the live USB itself work in a VM to test on my laptop -- the graphics doesn't work, since there's no Vulkan driver for the VM. could use SwiftShader or llvmpipe, but they don't have VK_KHR_display, so now you need a new codepath in Folk and maybe you need libdrm again to put your software-rendered buffer onto the VM's screen...)

  * So we got a $40 used Dell Chromebook 11 laptop and got the Folk live USB running on it:
    * {{newsletters:img_6654.mp4}}
    * {{newsletters:chromebook-folk-medium.jpeg?400px}}
    * Did take a day or two to [[https://mrchromebox.tech|jailbreak the Chromebook]] -- you actually have to open it up and remove a firmware write-protection screw on the mainboard, then install this EFI firmware stuff which pretty much turns the Chromebook into a normal computer that can boot Windows/Linux. then you can boot it from USB stick
    * Neat: built-in webcam & display work out of the box as a quick demo that the system is running and working
  * Goal: distribute CNC demo as a live USB that a computer can just boot into
    * Will have to port the projector side of the CNC demo to run on Folk, but that should be quick, it's just lines and checkerboard; will keep the Web UI and just host it on the Folk web server, I think, so we can get it out ASAP
  * Lots to do on Folk itself to guide installation process:
    * Status report if no programs are out (or maybe always-on in corner): are we online? IP address? network interfaces? current git revision? number of displays/cameras? are we calibrated?
    * Wi-Fi setup process (not strictly necessary if the USB stick is self-contained and the Folk box has a display & keyboard, but useful so you can go to web view and ssh in from your normal computer, so Folk can federate to other Folk instances on network, so Folk can connect to network printer, & so we can pull a newer version of Folk from online if applicable)
    * Terminal by default on boot? -- may be our first way to do Wi-Fi setup, you just run iwd and dhclient stuff from an embedded terminal in Folk so we don't need to make UI for everything at first
    * Calibration (incl a physical rig for it)
    * Support addressing multiple projectors & multiple cameras
      * (especially important if running Folk on a laptop, since laptop probably has built-in display and webcam but you want to use external display & external webcam)

==== Friends and outreach ====

  * Recurse Center visitors in mid-March: big crowd, people were really excited to see everything and did a lot of programming. :-)
    * {{newsletters:img_6281.jpeg?400px}} {{newsletters:img_6270.jpeg?400px}}
    * {{newsletters:img_6272.jpeg?400px}} {{newsletters:img_6274.jpeg?400px}}

  * March open house: We had a small but really fun open house at the end of the month, where we showed the new template matching demo & people got a chance to make a few programs using the table editors.
    * {{newsletters:march-open-house.jpeg?400px}}
    * {{newsletters:img_6475.jpeg?400px}} {{newsletters:img_6470.jpeg?400px}}

===== What we'll be up to in April =====

  * **Our next [[https://partiful.com/e/MUhCwEmmtZ2ECCurpYyL|open house is in the evening on Thursday, April 25th ]] at our studio in East Williamsburg, Brooklyn.**
  * Finalizing the template matching games booklet
  * Collaboration for deeper phone/laptop integration and knowledge management explorations in Folk, should result in a more in-depth blog post later this year
  * Finish up the live-USB project, bundle/half-port the CNC demo, put it up online
  * Possibly:
    * Revisit RFID: it got pushed out a bit in March, but it's in a decent state right now
    * Revisit 3D calibration: Omar rebased it in March so it works again but hasn't really touched it otherwise
  * New evaluator work: try to surpass old evaluator on performance and see how good we can get, port more programs and semantics forward from old evaluator

===== Links we've enjoyed =====

==== Omar ====

  * https://www.marchintosh.com
  * https://timrodenbroeker.de/join-the-128kb-challenge/
  * https://mrchromebox.tech/
  * https://www.sparkfun.com/products/24540
  * https://docs.google.com/spreadsheets/d/1SWqLJ6tGmYHzqGaa4RZs54iw7C1uLcTU_rLTRHTOzaA/edit
  * https://twitter.com/Gameonysus/status/1770840155525353604
==== Andrés ====

  * [[https://apps.apple.com/us/app/tint/id1464860034?mt=12|tint — a relaxing color mixing game.]] Really clever puzzles from a seemingly limited premise about color mixing
  * [[https://www.1001mathproblems.com/p/spatial-puzzles-3d.html|a nice list of 3D spatial puzzles]]
  * [[https://www.1001mathproblems.com/2022/03/lattice-polygons-part-2.html | same website (1001mathproblems.com) on lattice polygons.]] I'm interested in what sorts of Folk-powered games you could make using these as a core mechanic