Writing an Interpreter in SQL for Fun and No Profit [video]
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...
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
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.