Writing an Interpreter in SQL for Fun and No Profit [video] | Hacker News Reader

Writing an Interpreter in SQL for Fun and No Profit [video]

youtube.com

55 pointsmalisper11 comments

Speaker here. If you liked the talk, you may also like the other talk I've given on generating fractals with SQL[0]. You can also find it blog post form[1].

Originally, before I had given the fractal talk, I had wanted to make a compiler from a low level imperative programming language to SQL. I had done a similar thing in the past to write FizzBuzz in the esoteric programming language Fractran[2]. By doing that, you can fairly easily produce SQL queries that perform arbitrary computations. When I was brainstorming what examples to give, I thought it would be really cool to generate fractals. After thinking for a bit, I realized it would be easier to write the SQL queries directly than it would be to write a compiler to SQL. That's how the fractal talk came about.

After I gave that talk, I revisited the idea of compiling to SQL. After playing around with for a bit, I discovered it wouldn't be too hard to write a programming language interpreter in SQL which is how this talk came about.

If you have any questions, feel free to ask.

[0] https://www.youtube.com/watch?v=xKoYIvMFnoQ

[1] https://malisper.me/generating-fractals-with-postgres-escape...

[2] https://malisper.me/building-fizzbuzz-fractran-bottom/

Are you informed by any general work on using relational algebra + one or two other things (recursion via CTE and environments, I guess, in this case) as general purpose programming languages, or did this mostly start by thinking about hacking your way to the specific goal of an interpreter or fractal generator using postgres facilities at hand?

I'm not aware of any general work. I initially tried to directly port Paul Graham's interpreter into SQL. I immediately ran into problems because it wasn't possible to map the recursive function calls into SQL. After thinking about it in the background for a day, I figured out I could use the CTE +_stack approach instead of recursion. Once I figured that out, it only took me a few hours to port the interpreter.

The SQLite official documentation lists examples of using SQL to generate the Mandelbrot plot and to solve Sudoku.

https://sqlite.org/lang_with.html

I ran the query before and it was a lot of fun.

Super cool hack! The author uses defunctionalised continuations to build an abstract machine directly as a CTE. I guess the fixed point of the transition function is returned by the CTE ... He also alludes to using the Y combinator to build recursion in the toy language being constructed. Ace abuse of SQL.

I love the JSON-as-a-parser hack.

In TSQL (MS SQL Server) it would run into the CTE recursion limit; I'm not sure if Postgres is any different in this regard. I suspect that this could be solved and optimized with a WHILE loop and, most likely, something similar to ORDPATH[1].

[1]: http://www.dbis.informatik.hu-berlin.de/fileadmin/lectures/W..., https://github.com/mejedi/libordpath

FWIW in MSSQL there’s always the `option (maxrecursion 0)` trick

Also other cursors, and GOTO statements :)

I have implemented SQL parsers 4 times in my life, and for the life of me I still have to look at the spec everytime i write a query.

He is not parsing SQL, he has written a Lisp interpreter in SQL.

Reply on news.ycombinator.com