[HN Gopher] Show HN: Using SQL's Turing completeness to build Te...
___________________________________________________________________
Show HN: Using SQL's Turing completeness to build Tetris
Author : nffaria
Score : 313 points
Date : 2024-09-04 12:28 UTC (3 days ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| abhgh wrote:
| 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!
| jihadjihad wrote:
| 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.
| nffaria wrote:
| 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.
| tanelpoder wrote:
| 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-beyond wrote:
| I will admit that in the past I've used `RAISE NOTICE` quite
| frequently for debugging difficult to navigate PL/pgSQL
| procedures.
| otteromkram wrote:
| 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!
| foreigner wrote:
| This is great but even more impressive than the code is all the
| documentation and explanation of how it works. Well done!
| gigatexal wrote:
| This is really really cool. Very cool work and welcome to HN!
| fishtoaster wrote:
| 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.
| prng2021 wrote:
| Wow this is amazing. Makes me realize how elementary my SQL
| skills are.
| gfody wrote:
| 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.
| thih9 wrote:
| Loosely related https://wiki.c2.com/?TutorialDee
| tisdadd wrote:
| 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.
| firer wrote:
| This is awesome, great writeup.
|
| I never attempted these kinds of things with postgresql, so it
| was very interesting to contrast the problems and solutions with
| SQLite, which I'm more familiar with [1].
|
| If anyone is interested in more SQL Turing completeness, the
| Explain Extended blog is great [2].
|
| [1]: https://github.com/DanielFi/sqlite-vm/tree/feature/io
|
| [2]: https://explainextended.com/
| chaps wrote:
| Missed opportunity to call it "TetriSQL".
| johnwatson11218 wrote:
| 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.
| nffaria wrote:
| 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_e
| xpressi...), which makes the language Turing complete. Also,
| apart from the small function to print to stdout, there were no
| procedural languages used.
___________________________________________________________________
(page generated 2024-09-07 23:01 UTC)