Show HN: Using SQL's Turing completeness to build Tetris | Hacker News Reader

Show HN: Using SQL's Turing completeness to build Tetris

github.com

338 pointsnffaria19 comments

It seems at first to be a toy or silly intellectual exercise, but after reading the whole thing it really feels like an example of how constraints can lead to creative solutions. Can't log to stdout in the recursive CTE's loop? Maybe `RAISE NOTICE` will work. Can't take user input from the query itself? What if we stored the input in a table locally and read from that instead with `dblink`?

It's just a lot of fun, kudos for hacking this together, this is the sort of thing that makes me love software so much.

Thanks for the kind words, it was exactly like you described. Many times I thought it would not be possible after hitting some of those walls, but luckily there was always a way around them.

I once wrote a top-like tool in Oracle's sqlplus client, that is not designed for building self-refreshing terminal UI display apps. Just to see if I could do it, had to get creative too. Used pipelined PL/SQL functions with never-ending output stream and a sleep function within it and had to carefully match the sqlplus "fetch array size" with number of rows returned in a batch from the pipelined function. Called it MOATS - the Mother of All Tuning Scripts - and then someone took the idea further and built v2.0 with added colors and charts, etc:

The v2.0 UI GIF is here: https://github.com/dbsid/moats_rac

I will admit that in the past I've used `RAISE NOTICE` quite frequently for debugging difficult to navigate PL/pgSQL procedures.

Cool project! I remember I had coded a Reinforcement Learning (RL) assignment long ago back in college with just SQL (I was familiar with Oracle back then, so that's what I had used). The course instructor was amused, more so when he saw how loops were implemented: I had a "loop" table with a sequence of N numbers in a column, and used to join with it to "loop" N times!

This is great but even more impressive than the code is all the documentation and explanation of how it works. Well done!

This is hilarious and amazing. But moreso than most such cool hack projects, it has a great writeup. The author really did a great job walking through how it worked. Love it.

I think a general purpose programming language that was just SQL with some provisions for user input and rendering would be really cool. Having to model all your state relationally and implement all your logic declaratively ultimately leads to some very nice code.

Loosely related https://wiki.c2.com/?TutorialDee

This is awesome. I did linear regression in T-SQL once and it's a fun way to figure out what you can do with the language (eg - if you're unfamiliar with CTEs or cursors).

I'll definitely be checking this out later. Thanks for the post!

Missed opportunity to call it "TetriSQL".

This is a cool project. Just wondering... why did you build it?

Mainly to see if it was possible. I have been wondering for quite some time how far can you push SQL, given it is Turing complete.

Yeah, fair enough. It's an interesting project

This is really really cool. Very cool work and welcome to HN!

Nice, I remember my boss telling me not to do that when I was an intern for routing services, always wanted to see a working example. Well done.

Wow this is amazing. Makes me realize how elementary my SQL skills are.

The article you linked, "tetris-sql," appears to be using database extensions to overcome SQL's limitations. While the core SQL language itself is not Turing complete, these extensions, such as Common Table Expressions (CTEs) and procedural languages, can provide the necessary constructs for iterative execution and conditional logic.

By leveraging these extensions, the author has effectively created a Turing complete environment within the database system, allowing them to implement Tetris. However, it's important to note that the implementation would be more convoluted and less efficient compared to a traditional programming language designed for game development.

Essentially, the article is demonstrating how to create a Turing complete environment using SQL and its extensions, but it's not a direct representation of SQL's inherent capabilities.

While there were some workarounds needed to implement the game, such as handling input and output, the core of the game logic uses regular SQL. Even recursive CTEs are part of the SQL standard (https://en.wikipedia.org/wiki/SQL:1999#Common_table_expressi...), which makes the language Turing complete. Also, apart from the small function to print to stdout, there were no procedural languages used.

Reply on news.ycombinator.com