Writing an Interpreter in SQL for Fun and No Profit!
summary
Claims a working Lisp-like interpreter implemented entirely in Postgres SQL using JSON for the AST and recursive CTEs plus CASE to emulate a stack and control flow. Implements a calculator, arithmetic and comparison ops, list primitives, if, lambdas with environments and a self-pass trick for recursion. The full implementation fits about 100 lines of SQL and successfully computes examples — e.g. returns 37 for a small program and generates the first 10 Fibonacci numbers.
AI-written summary · about
chapters (23)
- 0:00Intro
- 0:32Lisp is a great place to start!
- 1:37Evaluating an Expression
- 1:54An Example
- 3:33Sketch of How the Interpreter Will Work
- 4:04Basic State Manipulations
- 4:40Interpreter Skeleton
- 5:09The CASE Statement Does All The Work
- 5:24Self-Evaluating Expressions
- 5:34Function Calls
- 5:47Second Case: Argument Evaluation Stack Frames
- 6:04Recursive Case: Evaluate one argument
- 6:29Last Stack Frame: Eval Call Frames
- 6:42Terminating Condition of the Interpreter
- 7:24Example: Fibonacci Numbers
- 8:09Implementation
- 8:26One Last Feature: Lambda Functions
- 8:43Variables
- 9:24Define a lambda function
- 9:43Calling a Lambda Function
- 10:14Example: First 10 Fibonacci Numbers
- 10:43Actual Logic
- 11:11Full Code
related talks
47mLearning advanced SQL the weird (and hard) way
44mPostgreSQL for Developers
41mHow types can turn a SQL interpreter into a SQL compiler
46mSQL for Nerds
07mInterview of Lætitia Avrot
27mBuilding Tetris in a SQL Query!
32mBecause SQL is everywhere but you don't want to use it
27mFunctional Programming on Top of SQL Engines