Show HN: Using SQL's Turing completeness to build Tetris (opens in new tab)

(github.com)

338 pointsnffaria1y ago19 comments

19 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.

nffariaOP1y ago

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.

tanelpoder1y ago

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

written-beyond1y ago

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

abhgh1y ago

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!

foreigner1y ago

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

fishtoaster1y ago

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.

gfody1y ago

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.

thih91y ago

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

otteromkram1y ago

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!

chaps1y ago

Missed opportunity to call it "TetriSQL".

jamiehewitt1y ago

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

nffariaOP1y ago

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.

jamiehewitt1y ago

Yeah, fair enough. It's an interesting project

gigatexal1y ago

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

tisdadd1y ago

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.

prng20211y ago

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

johnwatson112181y ago

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.

nffariaOP1y ago

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.

j / k navigate · click thread line to collapse

19 comments

jihadjihad1y ago

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.

nffariaOP1y ago

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.

tanelpoder1y ago

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

written-beyond1y ago

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

abhgh1y ago

foreigner1y ago

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

fishtoaster1y ago

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.

gfody1y ago

thih91y ago

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

otteromkram1y ago

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!

chaps1y ago

Missed opportunity to call it "TetriSQL".

jamiehewitt1y ago

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

nffariaOP1y ago

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.

jamiehewitt1y ago

Yeah, fair enough. It's an interesting project

gigatexal1y ago

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

tisdadd1y ago

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.

prng20211y ago

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

johnwatson112181y ago

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.

nffariaOP1y ago

j / k navigate · click thread line to collapse