## 1. Project Overview & Quickstart (justinmeiners/lc3-vm) ## File: README.md # LC-3 VM # [READ TUTORIAL HERE](https://www.jmeiners.com/lc3-vm/) This is a tutorial and source code for creating a VM of the [LC3 computer](https://en.wikipedia.org/wiki/Little_Computer_3). ## Editing The documentation and source are generated from the `.lit` file using [srcweave](https://github.com/justinmeiners/srcweave). If you don't want to go through the trouble of setting it up, your contributions are welcome. Just make your edits the `.lit` file, and we can regenerate it for you. ## License This applies to the article and figures: [CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) This applies to all code: MIT License Copyright (c) 2022 Justin Meiners Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. ## 2. Official Technical Reference & Guides (justinmeiners/justinmeiners.github.io) ## File: 3d-paint/README.md 3D Paint -------------------------- **10/30/16** In 2012 I came across the paper [OverCoat: An Implicit Canvas for 3D Painting][1] which describes a technique for creating 3D models using traditional painting methods. At the time I didn't have sufficient mathematical knowledge to understand all of the technical details described, but I picked up the general idea and wrote my own rough implementation. This article explains how my program was constructed and some of what I learned in the process. The basic idea is to paint 3d strokes onto a rough 3D model which acts as a canvas. The model is simply rotated to a desired orientation, and drawn upon, as if one was painting ontop of a flat a picture. The difference is that the strokes are projected into 3D space giving them their own 3D form. The model is only a placeholder which is eventually removed, leaving only the painting made up of strokes. To position the nodes which define a stroke, my program simply performed a ray-triangle test between the mouse ray and the mesh, and offset the intersection point by the face normal. The paper describes a sophisticated optimization method which evenly distributes stroke nodes, even across harshes changes in depth. The image above shows several strokes projected onto the surface of the model. Along with the node positions, information such as a color and brush size are stored for each stroke. I used the following data structures: typedef struct { Vec4_t color; int brush; float pressure; } StrokeInfo_t; typedef struct { Vec3_t pos; float radius; } StrokeNode3D_t; typedef struct { int nodeCount; StrokeNode3D_t nodes[MAX_STROKE_NODES]; Vec4_t color; // used for depth sorting Vec3_t center; StrokeInfo_t info; } Stroke3D_t; typedef struct { int strokeCount; Stroke3D_t strokes[MAX_STROKES]; int dirty; } Canvas3D_t; To render the strokes, each node position is transformed from 3D onto the 2D screen, using the camera matrix. The brush image is then rendered onto the framebuffer at each of the 2D node positions on the screen. Even though these screenshots show only a few colors and a single brush, the program supports multiple brush types and RGB colors. As the drawing becomes more dense, the strokes begin to resemble their own shape. Rendering strokes is a very efficient process because it only involves stamping the brush image in 2D, which is easily parallelized on the GPU. For the strokes to be drawn in the correct order they must be sorted by depth. This is by far the most computational expensive part of the process. My program solved this problem by only sorting strokes by their average position, which seemed to be an acceptable alternative to sorting each node. The order in which the nodes of a stroke are rendered is still important to ensure proper layering. An offline rendering process should sort each node properly. Although my program cannot produce the beautiful paintings found in the original paper, it can still draw some fun pictures. I think the technique itself is very interesting and has great potential. It would be interesting to make a small game, or animation centered around the technique since the artwork is so easy and natural to produce. Because it requires no textures, other than the small brushes, its memory usage is also very small, while its vertex requirements are similar to triangle meshes. The next natural step would be to bind a painting to a skeleton for animation. [1]: http://zurich.disneyresearch.com/OverCoat/ --- ## File: 10-hard-decisions/README.md 10 Hard Decisions: A Model for Programmer Productivity ====================================================== **09/26/20** How do you ensure that programmers are using time effectively? What can you do to help them be productive? Managers think a lot about these questions. But too often they get the answers wrong despite being very earnest and smart. This is because they have an unexamined mental model of how programming work is actually done. With an inaccurate model, managers optimize the wrong things and make bad decisions which would otherwise be good decisions in other work environments. To understand the idea, let's look at a few examples of how productivity varies between jobs. Simple manual labor, like digging holes, is easy to understand. Productivity comes down to moving as much dirt per minutes as possible. Progress is very measurable, and it easy to think about how to improve it. As a manager, you might ensure there is a rotation of workers digging at all time, and that everyone has the best tools possible. However that looks very different than the working model for a professional baseball scout. A scout can take a few years of evaluating players just to find one great pro. There aren't simple metrics you can use to measure their progress. It's hard to tell exactly what productive work should look like. Exposure to a lot of players can help, but ultimately it comes down to a few big choices. What kind of work is programming most like? In my experience (especially in agencies), the typical model of a programmer is an expensive factory machine. This is the kind of machine that occupies a lot of space and attention in the factory. It's operation is fragile, so it needs to be constantly checked on and maintained. But most importantly, every minute that it is not working on jobs is expensive money wasted. The primary metric for ensuring it stays productive is utilization time, even if that means spending time on throw away jobs. Managers understand this work model very well, perhaps they read "The Goal" in school. They look for metrics to identify throughput and bottlenecks and do lots of shuffling of programmers around to ensure maximum utilization. In it's most exaggerated form this led managers to obsess over metrics "lines of code per week". Although we have moved beyond that. The underlying thinking about what's going on has changed much. We just think about programmers as feature producers. The task the programmer needs to finish programmer needs to sit at the computer and type in the project. Here is a common example of this thinking: Bob is busy finishing task 1 and then will start project 2. Alice has a bit of downtime before she starts project 3. Let's have Alice get started on project 2, then we can have her hand off the incomplete work to Bob. In a few weeks when he is ready, Alice can move on to project 3 and leave Bob with a head start. This seems like smart move. We made sure that Alice and Bob's valuable time was well used, right? ## A better Model To see why this decision may actually waste time, we need a better understand what programming is like. The model I will describe is not perfect, it's a great simplification, but its a rough estimation that's far more accurate than the factory machine one. That better model is the following: **each project consists of making 5-15 difficult software decisions**. All of these decisions are of course somewhat dependent on one another. Each of those decisions that is made well, will lead to shipping the project, Each decision made wrong, will cause delays and waste time, now or down the road. That's all. That's the description of the job programmers need to do, and how they occupy their time. If programmers knew what to write beforehand, they could type it in no time! The time they spend fiddling at the keyboard is actually gather information through experiment and observation, in order to make decisions. As a manager, the way to improve productivity is to simply think about what would help you make hard decisions. Here are some simple ideas that become immediately obvious, given this clearer model: - Give programmers as much possible information about the project as early as possible. It's difficult to make decisions with incomplete information. When you get ideas early they can sit in the back of your mind and get some sleep time. Organize information so its easy to process. - Protect programmer time from interruptions. Design large blocks of uninterrupted time. Have quiet working environments. It's hard to make good decisions without focus. Other writers have written extensively about the cost of "[context switching][1]" when you have to forget about what you were thinking and start thinking about something new. - Ensure programmers have a clear understanding of project priorities and goals. Clearly communicate expectations and requirements. Making good decisions requires making trade-offs. Unclear priorities will lead to programmers making bad decisions. Changing priorities will invalidate previously good decisions. - It's OK if a programmer is not at their keyboard writing code. Taking a walk or a rest is often productive time. Distracting activities like watching a lot YouTube are not. - Don't treat programmers interchangeably. Give them ownership of specific project pieces so they can make long term decisions and build on previous ones. Would you hire a separate architect to design each room of a house? - Ensure your incentive structure rewards good decision making. Do you reward band-aid approaches? Are programmers just trying to get it "over the fence" so someone else has to deal with it? Are programmers are the receiving side of the fence? - Going through a crunch? [Don't add people][2] to a late project. Throw more money and effort at building an focused environment to making decisions. Can you pay someone to errands at home so the programmer doesn't have to think about them? Can you bring their family to the office for a lunch? (1) This is just a short list of suggestions and you can probably can come up with even better ideas. What's important is that as we think deeper about this model common productivity mistakes become apparent. (2) Let's analyze the Bob and Alice example again using this model. Did we help Alice and Bob make decisions or hurt them? Recall, Alice starts working on task 2 for a few weeks, to get it started for Bob. Then Bob picks it up, and Alice moves elsewhere. In our rough model we can assume that when Alice finishes, she has made 2 of the 15 decisions, and has some vague ideas about 5 others. The manager arranges a meeting for Alice to inform Bob of her work and she is swept off to task 3. Now Bob has to start thinking about task 2 from scratch, but not only that, he has to figure out what Alice was up to, whether the decisions she made were right, and what direction she was heading to address the other 13 decisions. This added information causes Bob to take more time than if he had started on his own. In practice, its even worse because Alice and Bob will need to continue to take time from each other to coordinate about what Alice had in mind. (3) ## Smarter Alternatives You might say, "that makes sense, but what am I supposed to do? Let Alice sit around for a week, wasting that time with an urgent project?". Let's use the model to work through better options. In this scenario Alice is scheduled to eventually own project 3. A better option would be to just let task 2 sit until Bob is ready, and get her stated on her project, even though it may be less urgent. Alice will be able to spend more time thinking about her project, and leave Bob with a fresh slate. "But this is really urgent, I don't even want to think about project 3 yet". The next alternative would be to identify decisions which Alice can make which have the least impact on the other work Bob needs to do. One would be having Alice better define the requirements and organize resources for this project. This will only help Bob make his decisions. Another idea is to have Alice work on "black boxes" that Bob doesn't need to know how they work. Maybe Alice has some special knowledge and can write a hard function he expects to use. What you absolutely don't want to do is interrupt Bob and have him start thinking about what decisions Alice could be making, while he is making his decisions. That doesn't make any sense! [1]: http://www.paulgraham.com/makersschedule.html [2]: https://en.wikipedia.org/wiki/Brooks%27s_law ## Notes 1. I don't think programmers *deserve* any of these special treatments over other jobs. I am not suggesting that programmers should have special privileges or are somehow more important than other kinds of work. It's all about the productivity model for the kind of work they do. 2. In video game production, art tends to be easy to outsource while programming is notoriously difficult and often unsuccessful. Perhaps this is because 3D art production can be better fit into a factory production productivity model. 3. One reason "just write it from scratch" is so appealing for programmers is that they get to make their own decisions, instead of figuring out why others made (often bad) decisions. Who wants to live with someone elses choices? For large existing codebases this represents a lot of invested knowledge, so its usually bad, but for a new task, Why would you rob a programmer of this opportunity by playing musical chairs? --- ## File: almost-solving-the-halting-problem/README.md Almost Solving the Halting Problem ================================== By: [Justin Meiners](https://github.com/justinmeiners) The halting problem is to devise a method that can determine whether a given Turing machine terminates in a finite amount of time. It is well-known to be undecidable; no such method exists. Naturally, if you ever write a proof that implies how to solve it, there is reason for concern. In doing research for my master's thesis, unfortunately, I did just that. It took quite a bit of reading and discussion to detect what went wrong. It turns out I didn't make any major mistakes, but I learned that the difference between computability and incomputability is quite subtle. I wanted to share this insight into what it means for a function to be incomputable. My thesis focused on braid group algebra, and reasoning about how a particular property of braids can be computed. Since this is a specialized topic and the details aren't important, I will explain a similar problem using Turing Machines directly. ## Turing machine A Turing machine consists of: - An infinitely long tape, divided into cells. Each cell has a symbol written on it. This symbol comes from a finite alphabet `S` (often `{ 0, 1 }` where `0` can be called "blank"). - A read/write head positioned over a particular cell on the tape. - A controller that moves the tape and reads and writes symbols. The controller is a finite state machine `Q`. As a Turing machine runs, the read/write head sends the current symbol to the controller. The controller can then: 1. replace the symbol. 2. transition to a new state. 3. shift the tape by a finite amount. Which symbol to write and which transition to make is determined entirely by the controller's state and the symbol that was read. For answering questions about computability and complexity, it doesn't matter how many symbols the alphabet has or how complex the finite state machine is. ## Estimating the number of operations How do we go about determining whether a Turing machine will halt? Here is the basic idea: run the machine for a large number of steps. If it runs for longer than we expected, it probably won't terminate! Ok, that's obvious and not very helpful. "probably won't" isn't good enough. The actual difficulty is that the machine might run for longer than we expect and still terminate. We might just need to run it a little bit longer. But, what if we could determine *exactly* what that threshold is? In other words, what if there was a specific number of steps that any terminating machine would not exceed? It might seem like there is no way to determine such a bound, but it is actually pretty straightforward. We can estimate how long a Turing machine will run based on its *complexity*. In computer science, we often think longer programs are more complex. Similarly, a Turing machine with a lot of information on the tape has a "long program" to run and work with. A Turing machine has only finitely many non-blank squares. For a fixed state machine `Q` and alphabet `S`, define `A(n, Q, S)` to be the set of Turing machines in `Q` and `S` that: - halt - have exactly `n` non-blank squares. (`n` can be thought of as an estimate of program length). There are at most `|S|^n` machines of this kind; therefore, `A(n, Q, S)` is a finite set. If we then let `l(T)` be the number of steps machine `T` runs for before termination, `{ l(T) : T in A(n, Q, S) }` is finite and thus has a maximum `M`. So given any Turing machine with this particular controller and configuration, we can run it for `M` steps, and if it goes longer, then we *know* it will never terminate! We can even define a function `f_{S, Q}(n)` that is the approximate `M` value for our inputs! In fact, we don't care about `f` in particular; ANY function that is strictly larger than `f` will do. ## Incomputability So why can't we do this? Well, to know when to stop running, we would actually have to be able to compute the bound `f` in the real world. In other words, we need an *effective procedure* or algorithm for computing `f`. Since there is no way to solve the halting problem, the only conclusion is that `f` grows faster than any function that can be computed in the real world. Even though we can write programs to compute functions such as polynomials and exponentials, none of those grow fast enough. Perhaps we could compute a lookup table to store this bound, but that would also require infinite space. This shows us that uncomputability is primarily a problem of growth rates, not any kind of tricky function definition. Some functions just grow too quickly to be computed by a machine. Note that the same limitation occurs for less sophisticated models of computation. The [Ackermann function](https://en.wikipedia.org/wiki/Ackermann_function) is a classic example of a function that requires the full power of a Turing machine to compute. This is due to its fast rate of growth. ## References Minsky. Computation: Finite and Infinite Machines. Chapter 8. --- ## File: aoc-2020-18/README.md Advent of Code 2020 Day 18: Rethinking Operator Precedence =========================================================== **12/27/20** Part 2 of [AOC Day 18][1] asks you to evaluate some math expressions, but with a twist. `+` has a greater operator precedence than `*`. (This is opposite of how we typically read math): 2 * 3 + (4 * 5) 2 * 3 + 20 2 * 23 46 The standard method for expression evaluation is the [shunting yard][2] algorithm. This is the *right* and efficient way to solve this problem. But, it's also not very obvious or natural. It's hard to imagine how you would think if it yourself, and doesn't really match how people actually see mathematical expressions. I want to show off an alternative solution demonstrating how you could think of it yourself. My code is written in Common Lisp. For this particular problem this choice goes a bit deeper than just syntax as the solution makes heavy use of a symbolic expression manipulation which is harder to do in most languages. **Thinking about Precedence** What does operator precedence actually mean? It tells us the *order in which to evaluate operators*. So naively we should just do all the additions first, and then the multiplications. Can we program that? We certainly can, but doing just one operation at a time, means at each step we produce an intermediate result which is itself a math expression, just simplified a bit. For example given the expression: (1 + 2 * 3 + 4) We first evaluate all the `+` to produce: (3 * 7) And then we evaluate all the '*' to produce: (21) After evaluating every operator, we should get a list containing a single number. Below is some code which does just that. The input `chain` is an expression (list of numbers and operators) and `allowed` is the operator we want to evaluate. (defun simplify-chain (chain allowed) (prog ((result '()) (op nil) (l nil) (r nil)) (setf l (car chain)) (setf chain (cdr chain)) loop (setf op (car chain)) (setf chain (cdr chain)) (setf r (car chain)) (setf chain (cdr chain)) (if (eq op allowed) ; evaluate the operation. ; put the result back in the expression (setf l (funcall op l r)) ; not an operation we want to evaluate right now. ; put it's symbols back in an the expression (progn (push l result) (push op result) (setf l r))) (if (consp chain) (go loop)) (push l result) (return (reverse result)))) **Handling Parenthesis** That is quite straightforward! All the trickiness is fiddling with infix. But, there is one problem. Due to parenthesis the operands may not be "ready" to evaluate. If we have: 3 + (2 * 4) We can't apply the `+` operation until the `(2 * 4)` is taken care of. But evaluating `(2 * 4)` is something we could do directly. There are only finitely many nested statements, so eventually following parenthesis must end with a list containing only numbers and operators. This is clearly a recursive problem! We need to evaluate all the parenthesized statements in a list, before we can evaluate the list itself. The algorithm for evaluation looks like the following: - To evaluate a number or operator symbol, just return it. (base case) - To evaluate a list: 1. evaluate every entry in the list. (take care of parenthesis) 2. simplify the expression by applying each operator in order. (simplify chain) 3. Return the only item left in the list. Let's write an eval function which does this, building upon simplify chain: (defun eval-expr (expr) (if (listp expr) (car (reduce #'simplify-chain '(+ *) :initial-value (mapcar #'eval-expr expr))) expr)) To summarize `simplify-chain` takes mathematical expressions and returns expressions that are simpler, while `eval-expr` always returns a number. Note that this works for any number of operators and adjusting precedence is as simple as changing the order of the `'(+ *)` list. [1]: https://adventofcode.com/2020/day/18 [2]: https://en.wikipedia.org/wiki/Shunting-yard_algorithm --- ## File: aoc-2020-19/README.md Advent of Code 2020 Day 19: An Easy way to do Part 2 ========================================================== **12/19/20** A fun mechanic in [AOC][1] is that the problem is divided into two parts, with the second only revealed after completion of the first. This challenges you to adapt an initial solution to new requirements, encouraging flexibility of design. In the case of [problem 19][2], a seemingly minor change, completely transforms the requirements. It may seem you have to rethink everything from scratch, but there is actually a tiny change to part 1 which solves the problem My personal ranking wasn't great, but you can see I still managed to catch up a bit on part 2 (even taking an additional hour!) as others got stuck. **SPOILERS AHEAD** ## Part 1 Let's outline a fairly standard solution to part 1. We will stick to psuedocode, but at then end I will show some of my Common Lisp code. **Parsing** We need to parse the rules and turn them into a structure we can work with. I chose to transform them into an expression tree. A rule such as: 3 4 | "a" "b" Becomes: (or (3 4) ("a" "b")) All the rules are stored in an array, with their index corresponding to their rule number. Lisp makes it easy to parse. I first replace the `|` with `^` because pipe has special semantics for the lisp reader. Whenever a rule contains a `^` I split it's components into a left side and right side and wrap them in an `or`. **Evaluation** Now we need a recursive evaluation function to handle the rule. It takes a rule and a string as input. It returns `FAIL` if it cannot match, or the modified string location, if it did match. For example when the rule "a" is applied to the following string: "abc" It returns "bc" indicating successful matching. The evaluation recursively handles the following cases: - evaluate a char: check that the first character agrees - evaluate a number: lookup the rule at that index and evaluate it. - evaluate an or form `(OR r1 r2)`: evaluate both options. If one succeeded, return that. Otherwise fail. - evaluate a list `(r1, ... ,rn)`: evaluate each rule in the list in order. Stop early if there is a failure. If the string ends before the list ends, the match failed. Success is indicated by returning an empty string. This means we used everything up and it matched. Test how many entries pass and you're done. ## Part 2 **What is going on?** Part 2 makes two substitutions to the rules list. 8: 42 -> 8: 42 | 42 8 11: 42 31 -> 11: 42 31 | 42 11 31 It's not immediately clear why this breaks our recursive evaluation. In fact, if you run it, it will not crash and still give you an (incorrect) answer. So what is going on? (This question took most of my time!) Consider the following rule: "a" | "a" "b" The string "ab" now matches *BOTH* possible choices. How do we know which one to pick? Logically, a disjunction (or) operation shouldn't care. But whatever choice is made will actually have an effect on whether the remaining rules in the pattern match. Here is an example of what can go wrong. Suppose our string is "abc". 0: 1 2 1: "a" | "a" "b" 2: "c" Starting with rule 0, we try rule 1. `"abc"` matches both `"a"` and `"a" "b"`. So let's pick the first rule. Now onto rule "c" which does not match "b c". The match fails. If we had chosen "a" "b" then we move to rule 2 "c" matches the remainder "c". We have a successful match. **The Hard Solution** Every time we an encounter an `OR` and both cases match, we no longer know which one to pick. The global success of a match can no longer be determined locally. We aren't going to get false positives, but we may get false negatives if we choose the wrong path to take. A proper solution must diverge at every or, creating branching possible evaluations. This can certainly be implemented, but is going to look very different than part 1, and be more complicated. **An Easy Solution** What we really want to know is whether there is *SOME* set of choices for each OR that will cause the pattern to match. Since we don't know what they are, we can just try a whole bunch, and see if we can find a set that does. The easiest way to do this is by introducing probability. Randomly pick a branch at each or. We can then run the matcher a bunch of times and see if it finds a set of choices that match. Let's work through the details. We want to replace the code for "evaluate an or form `(OR R1 R2)`". The original descrpition was: - If one succeeded, return that. Otherwise fail. Let's change it to a randomized choice when we don't have a better option: - evaluate both options. If either one failed, return the other. Otherwise both succeeded, so randomly pick which one to return. Now for each string run the pattern matcher a few hundred times. Each time it will (hopefully) try different choices for each OR. With enough tries, it should get lucky and find the best path if there is one. Remember, changing branch directions never introduces false positives, only false negatives. So if it matches even one time, then we know it works. Experiment with different numbers of times until you get a match rate that stabilizes. If you don't run it enough times, then you will get changing answers each time you run it. It works! Want to learn more? Checkout [chapter 4.3][3] of SICP on non-deterministic computing. ## My Code Here are the key snippets, some of it is a little ugly. **Eval (With Random)** (defun eval-rule (str rule all-rules) (cond ((stringp rule) (if (char= (car str) (char rule 0)) (cdr str) 'FAIL)) ((numberp rule) (eval-rule str (aref all-rules rule) all-rules)) ((and (listp rule) (eq 'or (car rule))) (let ((first (eval-rule str (nth 1 rule) all-rules)) (second (eval-rule str (nth 2 rule) all-rules))) (if (eq 'FAIL first) second (if (eq 'FAIL second) first (if (= (random 2) 1) first second ))))) ((listp rule) (prog ((s str) (l rule) (result nil)) step (setf result (eval-rule s (car l) all-rules)) (if (eq result 'FAIL) (return result)) (setf s result) (setf l (cdr l)) (if (consp l) (if (consp s) (go step) (return 'FAIL)) (return s)) )) (t (error "unknown rule ")))) **Solve Part 2** (defun solve-2 (all-rules inputs) (remove-if-not (lambda (string) ; use probablity! (some #'identity (loop for i from 1 to 500 collect (not (eval-rule (coerce string 'list) (aref all-rules 0) all-rules))))) inputs)) [1]: https://adventofcode.com/2020 [2]: https://adventofcode.com/2020/day/19 [3]: https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-28.html#%_sec_4.3 --- ## File: boring-benefits-of-lisp/README.md Boring Benefits of Lisp ======================= **10/07/20** Lisp advocates are famous for having elaborate reasons for why Lisp is their favorite language. You might have heard that it's the [most powerful language][0], thanks to features like [macros][1], first class functions, and [homioconicity][2]. Certainly, Lisp has no shortage of beautiful and influential ideas. But, almost every modern language has copied it's most productive features. Are there still compelling reasons to use it in production? For me there are. But, my interest is much more boring and practical. Fancy language abstractions [don't appeal to me][5], so the whole meta-programming isn't as important. What I do care about is a reliable and stable ecosystem which allows me to write quality code that can last for a long time. Consider the following features: - **Standards:** Common Lisp and Scheme are both fully standardized language with specifications. Consequently, they are well understood, cross-platform, and have diverse implementations, including several with free licenses. - **Documentation:** [SICP][sicp] is "the book" for Scheme and computer science. Common Lisp has several great books worth reading even if you don't care about Lisp (see [PAIP][paip]). The [CLHS][clhs] is as reliable and thorough as any language. - **Stability:** Lisp has been around since the 60s and the ANSI standard about 30 years. It is extremely stable. Code be written once, and run again years later, without modification. - **Efficiency:** Lisp implementations are reasonably fast. The true believers claim Common Lisp is as fast as C, it's probably much closer to Java. But, for a high-level, dynamic, language, [it's pretty fast][lisp-benchmark]. - **Design:** Lisp is well designed and founded on solid computer science principles. It has a focused selection of features and an elegant evaluation model which make it easy to write and compose functionality. You might think this list of features isn't remarkable or unique to Lisp. That's certainly true. C did them first, and established them as the recipe for releasing a successful language. Languages since have followed various steps, but the surprising thing is how few of them actually ended up with all the ingredients. Of course each item in this list is somewhat of a spectrum; some languages do more than others, but very few languages follow it to a degree that can be asserted with confidence. Usually, you can say a language somewhat satisfies it, followed by a list of ugly qualifications. Take Python for example. It's well designed, has great books and documentation, is fairly stable. It has an [elegant design][norvig-python] inspired by Lisp. But, is it standardized? Not really. They have a spec, but it only has one defacto implementation and changes all the time. Whatever the CPython project chooses to do defines the language. Alternative implementations exist, but they all have compatibility compromises. Python is also not very efficient. You can use a [JIT][pypy] implementation which makes it tolerable, but that has its own quirks, and you can't use many libraries with it. Lisp and C aren't the only languages with all these benefits, but there aren't as many as you think. Since Lisp has these great features and a design I enjoy using and studying it's become my go-to language. **Update: 4/30/21**: I recommend the article ["Tips for stable and portable software"][begriff-stable] which discusses principles of stability at the language level, as well as the entire OS stack. It offers specific advice for reliable unix software. **Update: 09/23/21**: Edited to clarify intended message. [0]: http://www.paulgraham.com/avg.html [1]: http://gigamonkeys.com/book/macros-defining-your-own.html [2]: https://en.wikipedia.org/wiki/Homoiconicity [norvig-python]: https://norvig.com/python-lisp.html [lisp-benchmark]: https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/lisp.html [5]: https://www.jmeiners.com/think-in-math/ [pypy]: https://www.pypy.org [begriff-stable]: https://begriffs.com/posts/2020-08-31-portable-stable-software.html [clhs]: http://www.lispworks.com/documentation/lw50/CLHS/Front/index.htm [paip]: https://github.com/norvig/paip-lisp/ [sicp]: https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book.html --- ## File: combat-robot/README.md # Combat Robot **04/05/2025** As a kid, I loved getting books from the library about combat robots. I was always interested in tools and building things, but the idea of making a robot was just a little more exciting than making furniture. Learning about robots introduced me to new building techniques, but unfortunately actually making a combat robot, was just not very accessible at the time. Welding? Car batteries? Wheel-chair motors? It's a tough sell for parents and suburban neighbors. After 20 years, the hobby has gotten a lot more accessible, thanks to 3D printers, but also improvements in batteries, motors, and radio. The whole process is smaller, cheaper, and easier to assemble, so that even local schools have robot making programs. Recently a friend (who is a 3D printer enthusiast) invited me to make a 150g robot for a small community event, and I had a great time. We didn't do anything extraordinary, but I wanted to share a little bit about the project. My takeaway, is this can be a great hobby for learning about electronics and mechanics, especially for kids. ### Design At 150g most robots use a body that's 3D-printed or adapted from an RC cars. To keep weight low, they typically only have 2 wheels. The main design decision to make is how your robot will attack. Most of your weight and body will arrange itself around that. Spinning weapons are the most popular. It's a simple and effective design that's *really* hard to beat. But we wanted to try something a little different. We found an idea online about a [spring loaded flipper](https://www.youtube.com/watch?v=63BY414Va0E). The spring is loaded by lifting an arm using a "snail cam" which can be rotated continuously. We had high hopes of having multiple weapons, but as these things tend to go, you must simplify and cut scope as you go. ### Cam The main part I worked on is the flipping arm and snail cam. It's designed with an increasing, but decelerating slope, so that the work required by the motor stays constant. My first attempt was to cut one with a hand saw from UHMW polyethylene. They may not look excellent, but should work, after a little sanding. We found the 3D printing was sturdy and smooth enough, so we chose that instead. I wrote a python script to generate the basic curve in Blender, and then used simple boolean cuts to get all the parts we need. ### Electronics N20 is a popular style of motor for this size. Apparently they vary greatly in quality and specification. We just got a few cheap ones on Amazon. I like that you can order them with a small gearbox targeted for a specific RPM, so it's easy to get the torque/speed you need. For example, the cam uses a much lower RPM than wheel motors. The radio receiver, and motor controllers are available as a single board. Just wire the motors to the appropriate terminals. The model we used is called "Malenki Nano" which is very popular. Connecting the receiver to a controller was as easy too. ### Body The body was drawn in a traditional CAD program. It went through many iterations and printings as we tried to fit everything in. Here are a few techniques we found helpful: 1. Attach components with zip ties. It makes it easy to move parts between bodies, and is very sturdy. Just add holes for them in your CAD design. 2. Prototype parts in cardboard first. If you have a simple base, it's easy to tape on pieces to see how they will fit. 3. Use fast and cheap printer settings until the final revision (and it's always one more than you think). ### Battle The event was very casual and had a positive atmosphere. People were open about showing their robots and learning from each other. Ages varied greatly, with some younger kids, teenagers, and a few Dad's joining their sons. A pro stopped by to show off his full-size robot! In our first (and only) battle we took a few big hits from a spinning blade. Luckily none of our major parts were damaged. So we should be ready to try again after printing a new body. --- ## File: common-lisp-scripts/README.md Deploying Common Lisp Scripts ---------------------------- **3/05/22** Do you want a Common Lisp workflow like Python or Perl? No dumping images, or complex deployments. Just install *a single lisp interpreter* on your computer (`/usr/local/bin/sbcl`) and *write, run, and share* source files. I've done a lot of research and I'm here to explain how to get exactly that. A step in the right direction is a `.lisp` file with an appropriate shebang: #!/usr/bin/sbcl --script (write-string "Hello, World!") It can be run with $ ./hello.lisp But you'll quickly run into roadblocks after "Hello, World!". How do you include other source files without knowing their installation path? How do you load libraries? The solution is a Quicklisp command for downloading libraries and exporting them called **[ql:bundle-systems][ql-bundle]**. It creates a single folder with an index file called `bundle.lisp`. After running `(load bundle.lisp)`, all of your dependencies are available to be load via `asdf:load-system`. The result is entirely self-contained. ## Example using `ql:bundle-system` 1. Create a bundle containing your Quicklisp dependencies: (ql:bundle-systems (list "alexandria" "cl-ppcre" ...) :to "bundle/") This `bundle/` folder will contain `alexandria` and `cl-ppcre`, along with their transitive dependencies. Each package will be organized as its own an `asdf` system. 2. Create an `.asd` file describing your project and its dependencies (see [defsystem docs][asdf] for details). (asdf:defsystem "my-lisp-program" :depends-on (:alexandria :cl-ppcre ...) :build-pathname "my-lisp-program" :components ( (:file "...") ...)) The `:depends-on` list must only reference systems which were downloaded by `ql:bundle-systems`. 3. Copy your application source into the bundle: $ mkdir -p bundle/local-projects/my-lisp-program $ cp *.lisp bundle/local-projects/my-lisp-program $ cp *.asd bundle/local-projects/my-lisp-program Now your code is just another `asdf:system`, alongside the others. 3. Install the bundle in a global system path. I prefer `/usr/local/lib`: $ cp -r bundle/ /usr/local/lib/my-lisp-program 4. Create a brief script which loads the `bundle.lisp` and the `asdf` system. For example `my-lisp-program` #!/usr/bin/sbcl --script (load "/usr/local/lib/my-lisp-program/bundle.lisp") (asdf:load-system "myapp") (my-lisp-program:do-stuff) `asdf:load-system` will examine your projects `.asd` file and load its dependencies, transitively. 5. Install the launch script in a global system path: $ mv my-lisp-program /usr/local/bin/ 6. Run your script! $ my-lisp-program That's all! Consider automating these steps for your project, such as with `make install`. The first time you run the script you may see a long log as `sbcl` compiles the code into `.fasl` files, for faster subsequent runs. ### Further guidance I use this approach in [srcweave](https://github.com/justinmeiners/srcweave). Take a look at the make file for a real-world example. ## Why other solutions didn't work for me There are a myriad of articles that claim to solve this problem. But after much research and trial and error, I found none of them to be satisfactory. Let's review them: ### Dumping an image The popular advice for deploying Common Lisp is to [dump an image][save-image] of the compiler (`save-lisp-and-die`), This makes a copy of the entire Lisp compiler with your source code included. This is a good solution for large applications. For example, if you want to deploy a web application to server, it's pretty convenient to `scp` up an image file and be done. However, it's quite cumbersome if you have more than a handful to keep track of. Your computer becomes littered with a bunch of independent copies of Lisp. If you want to update `sbcl` you need to track down all your old images, delete them, and rebuild new ones. Images files are also notoriously large (~50 MB for `sbcl`). ### Using Quicklisp in scripts Can you make a shebang script that loads code with Quicklisp? You certainly can, but first note that `sbcl --script` will skip loading your system configuration (`.sbclrc`), so you need to hard code a path to load Quicklisp. But now imaging if calling `import` in a Python started downloading code from the internet! That's a security and reliability nightmare. But that's how Quicklisp works! That's because Quicklisp isn't intended to be a library loader. It's a tool for downloading and *discovering* libraries. But it shouldn't be distributed in your source code. You should be using `asdf` for that instead. It's the standard way to describe and load libraries, and it's already included in most distributions. Note that Quicklisp is also organized as a rolling release like your operating system. Rather than picking out individual library version tags, you pick a Quicklisp version which is a snapshot in time of all the libraries that aims to be compatible. To reiterate, I will share an explanation from Reddit user [eayse][reddit]: > I advocate the habit of installing things with `ql:quickload`, but after initial installation, using `asdf:load-system` to actually bring the systems into memory. > After all missing dependencies have been satisfied by network installations from the distributions configured in Quicklisp, `ql:quickload` just thunks down to ASDF. ### Roswell? [Roswell][roswell] is advertised as a solution, but it's possibly the most un-Lispy tool in the ecosystem. It doesn't download dependencies, or help you build them. What does it do? Help you download sbcl? Why in the world does it use a config file syntax that isn't s-expressions? Why is part of it written in C? *sigh*. ## Busybox style The overhead of dumping an image can be shared by putting many scripts into a single image, instead of making an image for each. I call this "Busybox style" because it was popularized in C by the [Busybox][busybox] project. For a Common Lisp tutorial, see [Steve's article][small-cli]. This certainly solves some of the disk usage problems. But it's kind of a crutch, and the workflow is just not as good as Python. [asdf]: https://asdf.common-lisp.dev/asdf.html#Defining-systems-with-defsystem [buildapp]: https://www.xach.com/lisp/buildapp/ [small-cli]: https://stevelosh.com/blog/2021/03/small-common-lisp-cli-programs/ [ql-bundle]: https://www.quicklisp.org/beta/bundles.html [save-image]: https://lispcookbook.github.io/cl-cookbook/scripting.html [reddit]: https://old.reddit.com/r/lisp/comments/iai2ab/repairing_asdf_package_storage/g1pnxdt/ [roswell]: https://roswell.github.io/Roswell-as-a-Scripting-Environment.html [busybox]: https://fare.livejournal.com/184127.html [ql]: https://www.quicklisp.org/beta/ --- ## File: floorplan-scanning/README.md Building Scanning Patents ======================== At a previous startup, I invented an Augmented Reality (AR) system for scanning buildings, and automatically extracting floor plans from scans. Recently a few of the patents I wrote were published, and I wanted to share those, with a brief summary. ## Capturing Environmental Features Using 2D and 3D Scans [US-11989895-B2](US-11989895-B2.pdf) This describes an augmented reality workflow for capturing a 3D mesh of an environment, and recording points of interest. A key idea is to capture all the user interactions and raw 3D data first. Later in a post-process step, we determine user intent and relative positioning using complete global information. ## Floor Plan Extraction [US-12299784-B2](US-12299784-B2.pdf) Once we have a 3D scan of an environment, how do we go about turning this into a 2D floor plan? Floor plans are conceptual, rather than objective, and so are guided by user input. This invention describes both an augmented reality workflow and an algorithm for processing that input. It turns out, doing this perfectly is likely NP-complete, but this proper understanding guides effective heuristics. ## Surface Animation During Dynamic Floor Plan Generation [US-12229859-B2](US-12229859-B2.pdf) It's important to give feedback to the user during the scanning process. One way we do that is through the augmented reality visualization that shows which parts of a room are captured, and is programmed through shaders. The biggest challenge is to show accurate estimates quickly, despite the scan being incomplete. ## Aligning Polygon-like Representations With Inaccuracies [US-12651104-B2](US-12651104-B2.pdf) Scan measurements contain error, and the real world is imperfect. How can we correct the alignment of complex floor plan shapes with minimal distortion? One answer is to simultaneously move all points of the floor plan in a [multi-variable optimization](/why-train-when-you-can-optimize/) approach. ## Door and Window Detection in an AR Environment [US-12423828-B2](US-12423828-B2.pdf) Along with the shape of the building, we are also interested in the apertures of each room. The polygonal shape tells us where the walls are in 3D. We can then render the portion of the 3D mesh corresponding to each wall, and detect cutouts in the rendered image. This transforms a complex 3D detection problem into a traditional 2D computer vision problem. These 2D detections are then projected back into 3D features on the wall. --- ## File: foundations-of-math-reading/README.md Foundation of Math Reading List ------------------------------- **04/13/2019** One of my favorite courses in college was philosophy of language. Along with interesting philosphy it introduced me to the foundations of math project which has since become one of my favorite subjects to learn about. Some of my favorite books of all time come out of this interest. I wanted to organize a few of these into a list for others who are interested in the topic. Note that many good books were left out in favor of the very best. You will notice a theme in my commentary. The books I like most are those that don't shy away from hard technical knowledge, but also explore the philosophical ideas behind them. The list is arranged in a progressive sequence that will help prepare you for the next one. ### Logicomix By: [Apostolos Doxiadis][l1] Logicomix is actually a comic book! It tells an engaging historical narrative about the search for the foundations of math and the birth of analytic philosophy, in the early 20th century. It introduces you to all the major characters such as Gödel, Russel, Frege, and Wittgenstein and motivates the kinds of problems they were trying to solve. The book also explores how these ideas connect to modern computer science. It is an absolute joy to read and will give you a taste of whether this is an interesting subject for you. [l1]: https://www.apostolosdoxiadis.com ### Gödel, Escher, Bach By: [Douglas Hofstadter][geb-1] You probably have seen this work recommended elsewhere. Gödel, Escher, Bach really deserves all the praise that it gets. Hofstadter covers an enormous range of topics including formal systems, Godel's proof, theory of computation, programming, molecular biology, and artificial intelligence. Every topic is presented beautifully and with a lot of philosophical discussion. In many ways it is an introduction to the big ideas in modern science. It is written for a general audience and assumes no mathematical background. [geb-1]: https://en.wikipedia.org/wiki/Douglas_Hofstadter ### Gödel's Proof. By: [James Newman][gp-1] & [Ernest Nagel][gp-2] Gödel, Escher, Bach does a good job of introducing the incompleteness theorem and discussing its ramifications, but if you are like me you probably still won't completely understand it after a first reading. This concise book offers another perspective and a clear explanation of the mathematics of the proof, its general strategy, and the historical context surrounding the incompleteness problem. [gp-1]: https://en.wikipedia.org/wiki/Ernest_Nagel) [gp-2]: https://en.wikipedia.org/wiki/James_R._Newman ### Descartes Dream By: [Phillip Davis][dd-1] & [Reuben Hersch][dd-2] In the 17th century Descartes had a dream in which he saw a future world driven by mathematical calculations and logical systems. The theme of this book is how this dream has become a reality. The book explores how mathematics and computer science work together, surveys several interesting fields, and examines ethical issues in the technological world. This book is not technical, and should be appropriate for anyone interested in science or technology. If you like this book, the authors wrote another called *The Mathematical Experience* which is focused more on pure mathematics. [dd-1]: https://en.wikipedia.org/wiki/Philip_J._Davis [dd-2]: https://en.wikipedia.org/wiki/Reuben_Hersh ### Computation: Finite & Infinite By: [Marvin Minsky][mm-1] Marvin Minsky is an incredibly clear and deep writer. In this work he provides a mathematical framework for thinking about mechanical machines and develops the theory of computation. This book teaches you all you need to know about Turing machines, finite state, and neural networks. My project: [McCulloch & Pitts Neural Net Simulator][mm-2] is based on this book. To read this book, you should understand some logic and basic set theory such as that taught in an introductory proofs course. Unfortunately, it is out of print and may be difficult to obtain (for a reasonable amount of money). I read it from my university's library. If that is not an option, I recommend you *find it online*. If anyone knows of a place where I can reasonably purchase this book, let me know. [mm-1]: https://en.wikipedia.org/wiki/Marvin_Minsky [mm-2]: https://www.jmeiners.com/neural-nets-sim/ ### Structure and Interpretation of Computer Programs By: [Gerald Sussman][sicp-4] & [Hal Abelson][sicp-5] [Read Online][sicp-1] This classic text is designed to teach programming to MIT students who have some technical background in another areas of math and science. It is a hard read, but it assumes no programming knowledge and teaches Scheme (a Lisp dialect) and its full inter-workings from the ground up. If you want to be a professional programmer, this may be the only book you need to study. What other book teaches you to write a symbolic differentiator, interpreter, circuit simulator, and compiler? Most of the material is mixed in the [excercises][sicp-2] so don't skip them! But, this is not just a programming book. It belongs in this list because it teaches the fundamental concepts of computation. See the section [data as programs][sicp-3] for an example. [sicp-1]: https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book.html) [sicp-2]: https://github.com/justinmeiners/excercises/tree/master/sicp [sicp-3]: https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-26.html#%_sec_4.1.5 [sicp-4]: https://en.wikipedia.org/wiki/Gerald_Jay_Sussman [sicp-5]: https://en.wikipedia.org/wiki/Hal_Abelson ### Logical Foundations of Mathematics and Computational Complexity By: [Pavel Pudlak][f1] This book is a massive and dense survey of topics including formal systems, set theory, abstract algebra, computability theory, analysis of algorithms, and quantum computing. The first chapter covered almost everything I had learned about algebra and meta-mathematics in my entire undergraduate degree! Pudlak does a fantastic job of balancing technical information with philosophical discussion. I can't recommend this book enough. Reading this book definitely requires some mathematical maturity. The author does his best to explains every concept in the book but it would be hard for me to read about a "group" for the first time and really understand what he means. If you read through the other books, and have technical knowledge you should be well prepared. [f1]: http://users.math.cas.cz/~pudlak/ --- ## File: grid-neighbors/README.md Iterating grid cell neighbors =========================== **10/27/22** Suppose we need to iterate over the neighbors of a cell in a 2D grid: * * * * - * * * * This can be done with the following well known pattern: void all_neighbors() { for (int i = -1; i <= 1; ++i) { for (int j = -1; j <= 1; ++j) { if (i == 0 && j == 0) continue; std::cout << i << ", " << j << std::endl; } } } But what if we just want to iterate the horizontal and vertical neighbors, skipping the diagonal? * * - * * Most programs explicilty repeat the operation 4 times, or use a table. But there is a trick to do it in a loop. Think of the neighbor as a vector offset, and then rotate it 90 degrees, 4 times. template void rotate_2d(I& a, I& b) { std::swap(a, b); b = -b; } void direct_neighbors() { int i = 1; int j = 0; for (int k = 0; k < 4; ++k) { std::cout << i << ", " << j << std::endl; rotate_2d(i, j); } } Try it out! int main() { std::cout << "diagonal" << std::endl; all_neighbors(); std::cout << "square" << std::endl; direct_neighbors(); } --- ## File: hololens-impressions/README.md HoloLens First Impressions -------------------------- **11/10/2016** At work, I recently started on a new medical application for the [Microsoft HoloLens](https://www.microsoft.com/microsoft-hololens/en-us). I don't follow popular technology news, and rarely get excited about new gadgets, but I feel that the HoloLens is a robust platform, with real substance beyond the usual VR gimmicks. In this article I will talk a little bit about my experience with the hardware and development environment, as well as outline some its shortcomings. As the current release is a "Developer Edition" I hope some of the items will be addressed in the consumer release. Where the HoloLens succeeds most, is in offering an entirely distinct experience from VR headsets such as the Vive and Occulus. Everyone I have spoken to, who has tried both, immediately agrees the two are like apples and oranges. There is no question that the HTC Vive offers the most immersive graphical experience, but I get the feeling I could actually use the HoloLens for work, education, and other tasks beyond entertainment. The crisp display, is clear and readable, and since it doesn't overwhelm your vision it doesn't feel nauseating. The likelihood, of me setting up a full Vive room setup, to look at a piece of anatomy or the solar system is small, but quickly putting on the HoloLens to view a models from a true 3D perspective is helpful. Microsoft recommends using Unity to get started with HoloLens development, while also providing native C++ and Direct 3D. Initially. using Unity didn't excite me, but the it ends up working fairly well. Unity has a specific version of its engine adapted for HoloLens. This includes APIs and components for accessing the room scanning, world anchors, gestures, and voice controls. Once a build is exported from Unity, you can run, debug, and write code all in Visual Studio, until you need to modify the scene. The HoloLens can connect directly through USB or the WiFi for debugging. Microsoft has solid [documentation](https://developer.microsoft.com/en-us/windows/holographic/documentation) and tutorials to help you figure everything out. The voice controls are excellent, and easy to develop for. While in my quiet office, I have never had it mistake me for simple commands such as "back" and "select". I'll even admit to working with food stuffed in my mouth, and it still recognized my commands about half the time. Speaking commands to yourself is still as embarrassing as it sounds (less so than shouting at your phone), but the technology is solid, and I believe there is potential here. Development for voice controls is a pleasant process as well. In Unity you can simply register phrases you would like to listen for, and receive callbacks when they are spoken. The most noticeable limitation is the small field of view. Even though the glasses surround almost your whole vision, the displayable portion takes up only a small rectangular box at the front of your vision. This means that any objects larger than a basketball get chopped off while standing only a few feet away. This ugliness is most noticeable when a large model fills the whole viewing rectangle, leaving everything outside blank. It looks as if you are looking at the world through an open cereal box. Unfortunately, I can't show you what this looks like in a screenshot. The gesture controls aren't terrible, but still feel clunky. It takes a little bit of time to master, and then it's sort of like having a mouse that fails to click every tenth time. They are made worse when other people are nearby to distract the sensor. Since the entire system is contained within the headset, its GPU is more comparable to a mobile phone than a desktop machine. While not weak, the hardware feels a bit under powered. The frame rate cuts to about 30 frames, with roughly 50k triangles across 25 draw calls. I don't expect a ton here, but a bit faster would be nice. In my experience an iPad 2 has better GPU performance, but probably does a lot less background work. Given that I only tested in Unity, it is possible that using native C++ and Direct X would be a dramatic improvement. If you are using Unity be sure to use the optimized shaders found in [Microsoft's Holokit](https://github.com/Microsoft/HoloToolkit-Unity), and be conscious of batches. The shortcomings above can hopefully be addressed in future iterations of the hardware. In its current form, it is still a fundamentally innovative platform and I am excited to continue developing for it.