Slava AkhmechetModify

2026-01-05 08:00:00

Many programmers complain AI is good for quickly throwing up some CRUD apps but not much else. When someone points out this isn’t true, everyone (rightly) asks for examples. There aren’t many posts with detailed examples online, so I thought I’ll offer some from a project I wrote this Christmas.

Over the winter break I started building Beep– an imaginary programming language I wanted to get out of my head and into working code (if only to exorcise it so I stop thinking about it). I had two weeks and wanted to get as much as possible done, so I wrote everything in cooperation with Claude Code/Opus 4.5.

(The word “cooperation” isn’t incidental. I picked it carefully because it accurately describes the experience of working with Claude as if you had a programming partner.)

Example I: lexical scope shadowing

Beep supports lexical scoping. You can say this and it will work:

let x = 1

def foo()
  x  # `foo` can see `x`
end

foo()

A very simple way to implement this is to put x: 1 in a map of bindings and reference this map from foo at function definition time. When foo is called it can look up the value of x in this map.

Beep also supports shadowing. You can do the following and it will work too:

let x = 1, y = 1

def foo()
  [x, y]
end

let x = 2

def bar()
  [x, y]
end

foo() # returns [1, 1]
bar() # returns [2, 1]

A simple way to implement this is to have a singly-linked list of binding maps. Every time you see a let you make a new bindings map and link it to the previous one. In the example above the interpreter goes through the following steps:

1. See let x = 1, y = 1, make a bindings map and put x: 1, y: 1 in it.
2. See def foo, reference map in step 1 from foo definition.
3. See let x = 2, make a new bindings map, put x: 2 in it. Link this map to the map we made in step 1.
4. See def bar, reference map in step 3 from bar definition.
5. User calls foo(). The interpreter follows the reference to the first map, looks up x and y, and returns the values [1, 1].
6. User calls bar(). The interpreter follows the reference to the second map, looks up x and y. Finds x: 1, but can’t see y, so it follows the chain to the first map. Finds y: 1 and returns the values [2, 1].

One problem with this approach is that it’s not obvious how to keep track of the most recent map. Consider this example:

let x = 1

def foo()
  x            # x is 1 here
  let x = 2
  x            # x is 2 here
  let x = 3
  x            # x is 3 here
end

foo()

x              # x is 1 again

There are three let statements. Every time we see one, we create a new map that points to the previous one and make it the new “current”. When we see end we have to go back to the first map and make it current again. But how do we keep track of how many maps to go back?

I considered two approaches:

1. Keep a stack of integers in the interpreter state. Every time the interpreter enters a block (like a function definition), we push zero on this stack. Whenever there is a let, we increment the counter on top of the stack. At block exit, we drop as many maps as we’ve counted and pop the top count off the stack. This approach is simple, introduces a runtime cost (which doesn’t matter in a toy interpreter), and makes the interpreter more complicated.

2. Do a separate pass to transform the AST to introduce this information statically. This pass would transform the example above into this:

   let x = 1 in
     def foo()
       x              # x is 1 here
       let x = 2 in
         x            # x is 2 here
         let x = 3 in
           x          # x is 3 here
         end
       end
     end
   
     x                # x is 1 again
   end

   Old school languages would do this explicitly in the grammar, but I didn’t want to offload this on the user in Beep. Implementing the pass is essentially taking the first approach but running it once at parse time.

I asked Claude Code for advice, and it suggested two more approaches:

1. The same thing as above, but rather than a separate pass, do the transformation straight in the parser. Claude immediately gave me a correct diff to make this change. While I ended up not choosing this approach, it’s simple, and something I wouldn’t have thought of myself.
2. Stop keeping track of the latest bindings frame in explicit interpreter state. Instead have eval return the value and the new frame. Most AST nodes would return the same frame as they got, but let node would return a new one. This would make the host programming language stack automagically take care of the problem.

This latter option is the one I chose. I’m pretty sure I would have seen it myself without Claude, but this required a large mechanical refactor, and I guess my brain subconsciously recoiled from it. Of course I wouldn’t have to do the refactor myself. I asked Claude Code and it did the refactor perfectly (see commit 4a022a04). I can just do big mechanical refactors now without worrying about it, but it takes time to retrain your subconscious to get used to the capabilities of new tools.

Example II: dynamic scope mutation

Another feature of Beep is dynamic scoping. Dynamically scoped variables are prefixed by the $ sigil. Consider this example:

def foo()
  $x
end

def bar()
  let $x = 1
  foo()       # returns 1
end

bar()         # returns 1
foo()         # error, $x is not defined

Dynamically scoped variables are extremely useful to introduce state at the bottom of the stack and have everyone on the stack see it. For example, a web server can put configuration in a dynamic variable, and have every request handler see it without having to explicitly pass the state. This is useful anywhere you’d consider using global variables, but much safer. It doesn’t pollute the global namespace, it’s scoped to your calls, and is much easier to make thread safe. Dynamically scoped variables are a much better version of global variables (or what people sometimes used to use singletons for).

I implemented dynamically scoped variables using a second linked list of binding frames, and then bumped into a question. Should these variables be mutable? My intuition was that you shouldn’t be able to assign to $x in foo because that would introduce spooky action at a distance– anyone deep on the call stack would be able to change your variable without your knowledge. But I also thought you should be able to assign to it in bar. In other words: you can only assign to dynamic variables you introduced yourself.

But how would the interpreter know to do this? Somehow it would have to keep track of where dynamically scoped variables were introduced. This seemed kind of complicated and I felt lazy to reason it out, so I asked Claude Code. Claude suggested a very simple and elegant plan– add a set to each lexical binding frame; every time you see a dynamically scoped variable declaration, put it in the set. Everything else is already taken care of by existing machinery. I asked Claude to implement this, and again it made a perfect working diff (I broke it into commits 6694c8ad and a09c3af8).

This is almost certainly something I would have eventually seen myself, but it would have taken me some time to reason it out. When you’re first learning about a new field, working through solutions yourself helps you get better. But when you’re already pretty familiar with the problem space, you can often recognize a great solution when you see one, and it can let you pierce the heart of the problem much more efficiently than if you did it yourself. For me this was obviously the case here.

Example III: parser combinator hackery

About a year ago I wrote ts-parsec– a type-safe parser combinator library in typescript. I know the library inside out so it’s easy to write throwaway parsers, and type safety provides for great ergonomics. At least that was the idea. In practice, when grammars get slightly complicated I can find myself spending hours wrangling the type system to get it to type check.

ts-parsec is not a popular library– it has 13 github stars and 395 weekly npm downloads. And yet, Claude is much better at using it than I am. I suppose there are enough parser combinator libraries in its training set, but ts-parsec is idiosyncratic enough and different enough from similar libraries that using it requires non-trivial understanding of the details.

Beep’s parser.ts file is the part of the codebase I don’t care about. If Beep ever escapes the toy stage, I’ll throw away parser.ts and either rewrite it using a mature parser generator, or write the parser by hand. So for parsing I would just give Claude pretty high level instructions. For example:

I want to introduce let expressions of the form let x = 1, $y = 2. Add these to the parser and the AST, don’t worry about evaluating them yet.

Claude Code would just do it. The let form is fairly simple, but anyone who’s done parsing knows it can get very complicated. Without getting too deep into it, PEG parser combinator libraries like ts-parsec that combine lexing and parsing into one step can make some things difficult. You need a deep understanding of the parsing library and the grammar to get things to work.

For example, struct is a Beep keyword to define records:

struct Person
  name, age
end

But ts-parsec is eager, so if you type structure the parser consumes struct first, and then throws a parsing error. When I’d find bugs like that I’d tell Claude to fix them, and it would do it effortlessly.

If you look at parser.ts the code isn’t well-structured. The order of parser combinators is unintuitive and the code is hard to read. Part of the reason is that parser combinator code can just be like that. But a bigger reason is that I deliberately abandoned caring about code quality here, and Claude Code/Opus 4.5 doesn’t magically produce a well-structured codebase by default.

Still, I was very impressed with Claude’s performance. It took an obscure little library in an idiosyncratic domain (parsers) with a lot of obscure type system hackery, and solved nearly every problem at least an order of magnitude faster than I would myself, despite being the library’s author.

Counterexample: newline sensitivity

I wanted Beep grammar to separate statements using newlines, or statements on the same line using semicolons:

def foo()
  1
  2
  3
  4; 5
end

ts-parsec didn’t initially support this. The reader had two modes: drop or keep all whitespace. Claude Code got in a loop where it was trying different approaches, none of which could plausibly work because the underlying library didn’t have sufficient support to make this possible. Claude looked into ts-parsec, understood that support for keeping newlines is missing, but couldn’t quite make the leap to tell me explicitly to solve the problem. I then changed ts-parsec reader to support a third mode– keep_newlines. Once I made the change, Claude Code trivially modified the grammar to support newline-separated statements.

In most newline-sensitive languages the grammar lets you put ;\n to end a statement. For example in Javascript you can say:

1
2

1;
2

This encourages proliferation of styles. Some codebases end each line with a newline, others with a semicolon, and some mix both. I didn’t want to defer these decisions to a linter, and instead decided to encode them in Beep. So I asked Claude to change the grammar to make ;\n illegal. Again Claude Code got stuck– it tried various approaches, each of which broke something else, and it could never quite get out of that loop. After a while I just fixed the grammar myself.

I bumped into another endless loop when I tried to publish a new version of ts-parsec. Mine is under @spakhm/ts-parsec, which is called a “scoped” package. There was some npm authentication issue that I was too lazy to figure out, so I asked Claude for advice. It kept giving me various suggestions, none of which worked, until I finally buckled down, RTFM, and figured out the issue myself.

These were the only three examples in this project where the problem was too difficult for Claude Code. The last time I tried it (pre-Opus 4.5) I bumped into these kinds of problems much more often. With Opus 4.5 the difficulty bar to hit a failure mode is higher, and the frequency even on harder problems is lower. But it does sometimes get stuck on simple things like the incantation to publish scoped npm packages.

Closing thoughts

Many people fear AI will leave them behind. I don’t share this fear. Adjusted for range of capabilities, this is arguably the most intuitive technology ever devised. You talk to it in your native language and it does what you want. You don’t need a class on Claude Code– it’s easier to learn than VS Code! It maybe takes 30 minutes to learn your way around the interface, and over the next day or two it recedes in the background and becomes so natural, you forget you’re using it all. And as it gets smarter, it will understand you better. You don’t have to get better at using AI. AI will get better at being used by you.

(There are also geopolitical fears and economic and science fiction end-of-the-world scenarios. I think there are strong reasons to be optimistic about those too, though I’m less confident on this. I’ll keep this post from devolving into an opinion piece on these topics since I’m out of my depth here.)

Another theme is that AI is all slop and bad code. I don’t share this view either. It’s true that producing bad PRs at scale is easier than ever, and we’ll have to get better at solving this problem. For this project I didn’t use Claude Code as a vibe-coding machine, but rather as a precise code surgery robot and as a partner to bounce design ideas. In this mode Claude made the quality of the codebase better than it otherwise would have been. Claude lowered the barrier to annoying refactors which made codebase hygiene and paying off technical debt easier. It also lowered the cost of brainstorming ideas so I found myself picking cleaner solutions than I would have reached for on my own.

Beep functionality is currently uneven, so progress is hard to judge. It already has reasonably advanced features like user-defined types, methods, closures, and different scoping modes, but is missing some basic functionality like conditionals and loops. I can say with certainty that without Claude there is no way I would have gotten as far as I did in two weeks, interrupted often by holiday events and family obligations. Even more interesting is that were I working alone, the project would have taken a different shape. I would have done simple things first and left more complex features for later. Claude Code led me to frontload complex features because it makes this easy and fun, and because in the back of my mind I always know should I need to implement a simple feature, it’s only a few minutes away with Claude.

EDIT: conditionals and loops now work.

I’d put the problems in this post at a “good undergraduate” level. They’re accessible to maybe top 5% of CS students at a median US university, and to 85% of CS students at an Ivy. I am not saying Claude Code is a good undergraduate– it’s a different thing altogether. It can do refactors at superhuman speed but can’t publish to npm. What I am saying is that if you’re working at this level of difficulty, Claude Code is a phenomenal coding companion. Setting aside all the productivity arguments, it dramatically amplifies what’s fun about coding by eliminating much of what’s annoying. I would not want to go back to a world without it.

2024-10-26 08:00:00

I mentioned before that getting an interpreter working is a nerd-snipe. Once it works a little, it’s so much fun to keep adding functionality you end up working on it despite yourself. In this spirit, here is a writeup about my latest changes to ts-wolfram.

Dropping OOP

I initially wrote the interpreter using OOP. There were three AST types (Integer, Symbol, and Form), each one derived from a Node interface. This worked but bothered me, primarily as an aesthetic matter. I prefer to think of programs in terms of pipelines of transformations between data types. You can do this with classes, but stylistically it doesn’t quite fit and tends to leave a feeling of dissatisfaction. So I got rid of classes in favor of an algebraic data type, which to me looks much nicer:

export type Expr = Integer | Symbol | Form | String;

export enum Types {
  Form, Integer, Symbol, String,
}

export type Form = {
  type: Types.Form,
  head: Expr,
  parts: Expr[],
}

export type Integer = {
  type: Types.Integer,
  val: number,
}

// ...

Many small changes downstream of dropping OOP also made the code much nicer. For example, I got rid of ugly instanceof calls. But overall, code organization could still use one more pass of deliberate thinking through the file structure, and putting code that belongs together in dedicated files.

Kernel/userspace interop

Second, I changed the interpreter to support mixing “kernel” and “userspace” code in expression evaluation. Previously a function could either be defined in Typescript, or in Mathematica code, but not both. For example, Times is defined in Typescript, which meant I couldn’t put convenient transformation code into the prelude. Typing -a (-b) in the REPL produced Times[Minus[a], Minus[b]]. It would be convenient to add a rule to transform this into Times[a, b], but the evaluator didn’t support that.

Supporting this ended up being a small change. Once the evaluator supported mixed definitions I added the following line to the prelude:

Times[Minus[x_], Minus[y_]] := Times[x, y];

And voilà! Typing -a (-b) now produces Times[a, b] without any changes to Typescript code.

Better printing

Finally, I wanted to improve printing. Typing something like Hold[a /. a->b] printed the full form Hold[ReplaceAll[a, Rule[a, b]]]. I wanted to print shorthand. My original plan was to add string support and then use the same trick as with Times[Minus[...], Minus[...]] to do pretty printing in userspace. I added strings, ToString and <>/StringJoin, but then realized adding userspace rules to ToString doesn’t quite work. Calling ToString from the interpreter to pretty print caused additional evaluation and printed incorrect results.

Instead of going against the grain and trying to get this to work, I just kept the string commands and implemented pretty printing in Typescript. I added support for basic syntax so expressions like Hold[a /. a->b] print correctly in shorthand. I also added the FullForm command to help with debugging when I do need to see the full form.

However, getting a good printer working is non-trivial. For example, Sin[Cos[x]] Sin[x] currently prints (Sin[Cos[x]]) (Sin[x])– the printer doesn’t know to drop parentheses. I didn’t look into this too closely, but it seems like the naive approach would require lots of special cases to print expressions nicely. To get the printer working well, I need either to add many of the special cases, or find a more general approach (assuming one exists).

2024-10-21 08:00:00

My original plan for ts-wolfram was to quickly write a toy Wolfram Language interpreter in Typescript to better understand Mathematica internals, then abandon it as an exhaust product of learning. But one feature of interpreters is that building them is really fun. Once you get something working you want to keep hacking on it. So, last weekend I decided to allow myself to get nerd-sniped and worked on ts-wolfram some more.

I wanted to find out how much slower ts-wolfram is than Mathematica. To measure this I added two more commands: Do which evaluates an expression a specified number of times, and Timing which does actual measurement. I then measured the performance of a simple (and deliberately very inefficient) fibonacci function on my Apple M1:

fib[1] := 1
fib[2] := 1
fib[n_] := fib[n-2] + fib[n-1]

Timing[Do[fib[15], 1000]]

(* Mathematica: 0.44s *)
(* ts-wolfram: 3.4s *)

A mere ~8x slowdown was surprising! I put no effort into efficiency and expected closer to ~100x slowdown. Still, I was curious how much time I could shave off with simple optimizations. I reran the code with node --inspect, connected Chrome’s excellent profile visualizer, and narrowed down the hot spots. I then made the following changes:

• Dropped a few unnecessary Map allocations in the inner loop.
• Dropped hotspot array allocations and spread operator. (In inner loops this is really expensive).
• Rewrote attribute checks using boolean branches instead of string comparisons.
• Inlined dispatching on AST node type in the inner loop.

All of these changes combined got me down to… 0.98s, an only ~2.2x slowdown!¹ I find this incredible. Certainly Mathematica’s term rewrite loop is optimized to death, and I only spent an hour or two making the most basic optimizations. The fact that V8 runs my barely optimized term rewriting code only ~2.2x slower than Mathematica’s hyper-optimized engine is a testament to the incredible work done by V8 performance engineers.

EDIT: Thanks to Aaron O’Mullan’s PR, ts-wolfram now has performance parity with Mathematica on the fib benchmark. I find this absolutely mindblowing.

As I write this I still find myself surprised. I always vaguely knew that V8 is fast. But it never sunk in exactly how fast it is until now.

2024-10-17 08:00:00

Try it on GitHub: https://github.com/coffeemug/ts-wolfram

I’ve been using Mathematica to help with learning math (and using math to help learn Mathematica). Too often my Mathematica code has surprising behavior, which means I don’t really understand the language or how it’s evaluated. So I thought I’d do two things to get better.

First, write a bunch of Mathematica rules to implement a toy symbolic differentiation operator. Second, write a toy Mathematica interpreter in Typescript that’s good enough to correctly run my custom differentiation code.

Toy differentiation

Writing a toy differentiator turns out to be shockingly easy. It’s a near verbatim transcription of differentiation rules from any calculus textbook:

D[_?NumberQ, x_Symbol] = 0;
D[x_, x_Symbol] = 1;
D[Times[expr1_, expr2_], x_Symbol] =
  D[expr1, x] expr2 + D[expr2, x] expr1;
D[Plus[expr1_, expr2_], x_Symbol] = D[expr1, x] + D[expr2, x];
D[Sin[x_], x_Symbol] = Cos[x];
D[Cos[x_], x_Symbol] = -Sin[x];
D[f_Symbol[expr_], x_Symbol] :=
  (D[f[x], x] /. x -> expr) * D[expr, x];
D[Power[expr_, p_Integer], x_Symbol] := p expr^(p - 1) * D[expr, x];

My first implementation had three more rules (one for each of $dx^k/dx, (cf)’(x)$, and $(1/f)’(x)$), which I later realized you don’t need. These are shortcuts for human differentiators, but they’re automagically covered by the multiplication and exponentiation rules above.

Some problems I encountered while writing these rules: infinite recursion, rules not matching, and rules matching but evaluating to a surprising result. The hobby edition of Mathematica has some tools for debugging these problems, but not much. Ultimately I fixed bad rules by staring at the code and thinking really hard. I found Trace impossible to read, and TracePrint (which is supposed to be better) not much better. Also MatchQ is good, but somehow not as useful for debugging as I would have liked.

Toy interpreter

I first implemented basic parsing of integers, symbols, forms, and arithmetic operators using ts-parsec (which I wrote for this project). In Mathematica a 2 b 3 evaluates to Times[6, a, b] because Times has a Flat attribute. To get this behavior I implemented attributes next– Flat, and also HoldFirst, HoldRest, and HoldAll which I’d eventually need. I also exposed Attributes, SetAttributes, and ClearAttributes. These all accept (and Attributes returns) lists, so I added those too. All this was easy enough.

I wanted to implement assignment next so I could say a = 1. In Mathematica even something this simple is implemented by adding RuleDelayed[HoldPattern[a], 1] to OwnValues.¹ So the next step was to build the skeleton of a term rewriting system.² I first implemented a version of MatchQ that does a deep equal, extended it to handle Blank[], extended it again to handle Blank[...], and extended it again to handle Pattern[foo, Blank[...]]. The version exposed to the interpreter returns True or False, but under the hood it also returns an environment with matched variables. I built on that next to implement term rewriting.

A really simple rewrite rule is f[1] /. f[x_] :> x + 1. In Mathematica this parses to

ReplaceAll[f[1], RuleDelayed[f[Pattern[x, Blank[]]], Plus[x, 1]]]

With my MatchQ implementation there was now enough machinery to get this working. I added operators /. and :> to the grammar, implemented Replace, and built ReplaceAll on top. I tested a bunch of rewrite rules and they all worked! From here it was also easy to add -> and //. which I did next.

I had enough machinery to implement assignment. I added Set and SetDelayed, and modified evaluation to apply the rules stored in OwnValues and DownValues. This let me assign values to symbols and define functions! I could now run code like this:

fib[1] := 1
fib[2] := 1
fib[x_] := fib[x-2] + fib[x-1]

One caveat is that Mathematica inserts rules into value lists in order of specificity, so specific rules are tried before general rules. I initially added rules in order of definition to get assignment working, but then went back and added a simple specificity ordering function³.

EDIT: I wrote specificity ordering code late at night, and just realized it was completely broken. I removed it; rules are now processed in the order they’re entered. But everything else still works!

Finally, I added support for PatternTest/? and NumberQ. These were all the features needed to do differentiation!

Differentiating in ts-wolfram

I ran D in ts-wolfram on the following examples, and cross-checked with the results in Mathematica:

D[1, x]
D[x, x]
D[x^5, x]
D[3 x^2, x]
D[(x + 1) (x + 2), x]
D[x^2 + x^3, x]
D[Cos[x], x]
D[x^3/(x^2 + 1), x]
D[Cos[Cos[x]], x]
D[Cos[Cos[Cos[x]]], x]
D[Cos[x^2 + 1], x]
D[(x + 1)^2, x]

Somewhat miraculously, ts-wolfram got correct results on every test! Since I didn’t add any manipulation to simplify expressions, the results weren’t exactly the same. For example:

D[Cos[Cos[x]], x] 

(* ts-wolfram outputs *)
Times[Minus[Sin[Cos[x]]], Minus[Sin[x]]]

(* With `FullForm`, Mathematica outputs *)
Times[Sin[x], Sin[Cos[x]]]

This would be easy to fix by adding the rule Times[Minus[x_], Minus[y_]]=x y, but (a) Times is implemented in typescript, and the interpreter doesn’t currently support mixing kernel and userspace rules, and (b) extending the system to simplify algebraic expressions feels like a different undertaking.

Overall, this has been a really fun and instructive project. I built it in four days hacking on it after work, and learned a great deal about Mathematica internals. Of course this is still only scratching the surface, but now I feel a lot less lost when Mathematica doesn’t behave the way I expect. I’m very happy with this outcome!

2024-10-12 08:00:00

Try it on GitHub: https://github.com/coffeemug/ts-parsec

I write a lot of throwaway interpreters to play with programming language design ideas. For these projects, writing a parser is usually the most frustrating part. Parser libraries are hard to learn, easy to forget, and finicky to use. The other option, hand-coding a custom parser for each interpreter, raises the activation energy to start a project high enough that I abandon too many ideas before I try them.

All of this is unsatisfactory. To solve this problem I wrote a parser combinator library for myself in Typescript. It has these design goals:

• Produces recursive descent parsers capable of parsing PEG grammars.
• For throwaway projects only. Will never grow big, have complex optimizations, or other fancy features.
• Small, so I can understand every detail. The library is under 500 lines of code and took maybe a couple of days to write.
• Type safe. The syntax tree types are inferred from the combinators. It’s beautiful and really fun to use.

Example

Here is a simple example:

const digit = range('0', '9');
const lower = range('a', 'z');
const upper = range('A', 'Z');
const alpha = either(lower, upper);
const alnum = either(alpha, digit);

const ident = seq(alpha, many(alnum)).map(([first, rest]) =>
  [first, ...rest].join(""));

You can see how these parsers build on top of each other. I added a map method to support transforming the concrete syntax tree into an AST on the spot. Here seq(alpha, many(alnum)) return a tuple with an alphabetic character and an array of alphanumeric characters. But we don’t want to deal with that when handling identifiers– we just want to deal with a string. I can do that with a simple map.

Parsers operate on a special stream type that’s mostly irrelevant to the end user. To parse an identifier you’d do this:

const input = "Hello";
const stream = fromString(input);
ident(stream);

Actually, I lied a little. By default the stream automagically skips whitespace. That’s the desired behavior for most higher-order parsers, but when parsing keywords, identifiers, numbers, etc. we want to turn that behavior off. So in practice ident would be defined like this:

// `lex` turns off skipping whitespace for the parser it's wrapping
const ident = lex(seq(alpha, many(alnum))).map(([first, rest]) =>
  [first, ...rest].join(""));

All the usual suspects like seq, either, maybe, some, many, and sepBy are implemented in the library. This turns out to be enough to write parsers for most grammars I may ever want to parse.¹

Calculator

One limitation of recursive descent parsers is that they fall into an infinite loop on left recursion. You can manually rewrite your parser to avoid left recursion, but it’s a pain. This is relevant for toy interpreters because left recursion is the most natural way to express grammars for basic arithmetic. To avoid having to deal with this problem I added a helper parser binop for parsing binary operators. Using binop a calculator grammar looks like this:

const factor = binop(either(str('*'), str('/')), int,
  (op, l, r) => [op, l, r]);

const term = binop(either(str('+'), str('-')), factor,
  (op, l, r) => [op, l, r]);

const input = "1 + 2 * 3";
const stream = fromString(input);

// produces `['+', 1, ['*', 2, 3]]`
term(stream);

(The version binop is left-associative. There is a right-associative version binopr for binary operators like assignments.)

Practical problems

There are two painful limitations of this library, one fixable (but not yet fixed), the other inherent to its design.

The fixable problem is that the library produces no error messages whatsoever. It’s structurally set up to handle errors, but I haven’t implemented error reporting yet. So if something goes wrong during parsing, there is no useful information at all. I have some ideas for how to make error reporting easy and really good, but haven’t gotten around to working on this.

The more serious problem is that type safe parser combinators seem like an elegant, obviously good idea, but they turn out to kind of suck in practice. Maybe I’m not smart enough, or maybe I’m too lazy to properly understand the ins and outs of the Typescript type system, or maybe I just need to work a little harder to mature the library. But whatever the reason, every time I do semi-advanced type hackery like this, I end up spending more time dealing with weird type errors than actually working on my grammar. It’s all right in this narrow case because it’s fun, I know the ins and outs of the library, and it’s meant for throwaway/toy interpreters. But for a serious project I’d use an ugly, boring, old-school parser generator.

Or, more likely, bite the bullet and code the parser by hand.

2024-10-06 08:00:00

The mean value theorem is a surprising Calculus result that states for any function $f$ differentiable on $(a,b)$¹ there exists $x(a,b)$ such that

${\displaystyle f^{\mathrm{\prime }}(x)=\frac{f(b)-f(a)}{b-a}}$

Here are three informal intuitions for what this means (all of them say the same thing in different ways):

1. Physical example. If you travel 60 miles in one hour, at some point you must have been traveling exactly 60 miles per hour.²
2. Geometric intuition. There exists a line tangent to $f$ parallel to the line between the endpoints (i.e. parallel to the line between $(a, f(a))$ and $(b, f(b))$). See figure 1 below for an illustration.
3. Algebraic intuition. There exists a point $x$ at which instantaneous rate of change of $f$ is equal to the average change of $f$ on $[a,b]$.

The proof is remarkably straightforward. You define a function $h$ that maps values between $a$ and $b$ to a height from $f$ to the line segment between the endpoints. This function $h$ turns out to be differentiable, and hence has a maximum value (and hence there is a point $a$ such that $h’(a)=0$). From there it’s an easy algebraic transformation to demonstrate the mean value theorem is true. See figure 2 for an illustration.

Mathematica

I won’t repeat the proof, but what I wanted to do is play with Mathematica to generate an interactive visualization of how the proof works (I generated above figures in Mathematica, but the final product has an interactive slider to make the proof more clear).

• Interactive visualization that you can play with is here.
• Mathematica notebook with the code is here.³

For tasks like this Mathematica is wonderful. Here I define a line at an angle, and another function $f$ that adds a sine to it. Because the visualization is interactive $s$ will allow the user to change the slope:

interpol[s_, a_, b_] := a + s*(b - a);

g[s_, x_] = interpol[s, 1/2, 0]*x + interpol[s, 1, 0];
f[s_, x_] = Sin[x - 1] + g[s, x];

These are symbolic definitions. We can plot them, take derivatives, integrate, and do all kinds of fancy computer algebra system operations. Here is an example. The vertical line in figure 2 comes down from the mean value of $f$– i.e. a point on $f$ where the tangent is parallel to the average change. In Mathematica code we can take the derivative of $f$ (using Mathematica function D), and then solve (using Solve) for all values where the derivative is equal to mean value:

fD[a_] := D[f[s, x], x] /. x -> a;

avgSlope[s_] = (f[s, Pi + 1] - f[s, 1])/Pi;
meanPoint[s_] = 
  Solve[fD[x] == avgSlope[s] && x > 1 && x < Pi + 1, x];

This is the core of the code. Most of the rest of the code is plotting, which Mathematica does exceptionally well. I exported the plots to figures above using the Export function. Another notable function is Manipulate– this is what makes the graph dynamic as the user drags a slider (by changing the variable s which the equations depend on). Finally I was able to publish the notebook in a few clicks, as well as publish the visualization itself using CloudDeploy. Instantaneous deployment of complex objects is very cool and useful.

Snags

There are a few things I don’t like, but it’s too early to say these are Mathematica’s flaws (more likely it’s my lack of familiarity):

• My sense is that the error messages aren’t very good. I don’t know how long it would take me to decipher them without ChatGPT.
• Cloud deployment is great, but on the web the slider is very laggy. That makes sense– my code is symbolically solving for a particular value of a derivative, and I wouldn’t expect Mathematica to implement all this in JavaScript. That means on the desktop client everything is instant, but on the web everything gets evaluated on the server. I could maybe restructure the code to not run the server-side solver with every slider drag, but it’s not obvious how to do this.
• Mathematica supports embedding cloud objects in web pages, but the slider doesn’t work. My guess is it’s because the visualization makes cross-domain solver calls, but I haven’t investigated enough to be sure.
• The Mathematica rules and evaluation engine is mysterious. I don’t have a good model for how it works, and often get surprised that my code doesn’t behave the way I’d like.

Normally I learn very unfamiliar/weird programming languages by writing a toy interpreter of the target language in a language I already know. The Mathematica rules engine is a great candidate. Putting this in my virtual shoebox of future projects. EDIT: this is now done here with follow-ups here and here.