7 ms·

SQL query to generate the Mandelbrot set as ASCII art

193 points by mmoez 7y ago

rajangdavis 7y ago
The sudoku solver is equally impressive, didn't realize that SQL could be bent to do these sorts of things.
- chaoticmass 7y ago
  When I was around 19 and messing around with Visual Basic 5, I made a Sudoku solver. I thought up an algorithm myself, coded it, and it worked. I was very proud of myself. Seeing how succinct this SQL solver is now, I am in awe.
- bawolff 7y ago
  I believe that recursive CTEs make sql a turing complete language.
  - cryptonector 7y ago
    Of course. You can easily build programs too difficult to prove terminate using CTEs. But even before CTEs, SQLite3 was Turing complete: you could write recursive triggers. Recursion == looping. Any looping construct, recursive or otherwise, that doesn't require a literal max iteration count implies Turing completeness.
    - kragen 7y ago
      > Recursion == looping. Any looping construct, recursive or otherwise, that doesn't require a literal max iteration count implies Turing completeness. There are other ways to restrict looping constructs other than literal max iteration counts to avoid Turing-completeness; structural induction in Coq, LEAN, and Total Functional Programming is one example.
      - anewvillager 7y ago
        True, but all such limitations serve to give an upper bound on the iteration count (which may not be a single constant but depend on the input). It can be demonstrated that if you don't have an upper bound then the language is Turing complete.
        kragen 7y ago
        You are speaking in such a sloppy way that I doubt that the reasoning you intend to express is sound; certainly what you have actually said is false. For example, a machine with only the instructions JMP, HLT, and NOP can express loops with no upper bound, but is not Turing-complete; it is computable in linear time whether a given program will halt or not. A more interesting kind of automaton that includes unbounded loops is a nondeterministic finite automaton, which can generate regular languages, but is not Turing-complete. It is true that you do not need to add very many constructs from the programming languages we're familiar with before you reach Turing-completeness; Fractran and Minsky's two-counter machine are two rather astonishing examples. But when we were talking about languages lacking an indefinite-looping construct, we were already outside the bounds of "ordinary programming languages", so we can't just take for granted our vague intuitive ideas of what other things they can do; we have to be specific, not vague, in order to make rigorous statements like "the language is Turing complete."
    - bawolff 7y ago
      > Recursion == looping. Any looping construct, recursive or otherwise, that doesn't require a literal max iteration count implies Turing completeness. I'm not a computability theory person, but that doesn't sound right. Afaik, linear bounded automata can loop infinitely, but are not turing complete. Edit: After googling. I guess the important bit is conditional looping and unbounded storage. I think including recursive triggers is cheating a bit because the impressive bit is the query itself is turing complete without any other setup. But anyways CTEs don't just provide looping, they also provide a means to store and retrieve an unbounded amount of intermediate values. Its not obvious to me that that was possible in single query in sql without CTEs
      - kragen 7y ago
        I think SQLite could store and retrieve an extremely large amount of data as TEXT even before adding recursive CTEs, and you could do LIKE '%FOO' || BAR || 'BAZ%' queries to retrieve substring data from them; nevertheless, as far as I know, you couldn't encode Turing-complete queries in a SQL query before recursive CTEs. Conditional looping is not strictly necessary if you're willing to accept an infinite loop with a "halted" flag set as halting. Moreover, conditional looping and unbounded storage is not strictly sufficient; the loop needs to be able to depend on an unbounded part of the unbounded storage, for example, although not necessarily within a single iteration (which is impossible in many Turing-complete models of computation). So, for example, a finite automaton that stores matched parts of its input string on an output printout, but cannot consult that printout, does not thereby achieve Turing-completeness. Moreover, nondeterministic pushdown automata with ε-productions have conditional looping and unbounded storage that they can actually consult during computation, but they are not Turing-complete; they can only recognize context-free languages. I don't think you can reduce Turing-completeness to a laundry list of language features in that way, because you can always construct an automaton that restricts the ways those features can be combined so as to avoid Turing-completeness. This is not, as it may seem, merely a perverse form of computational masochism; on the contrary, it is often considered highly undesirable for a program to unexpectedly enter an infinite loop or perform an arbitrary computation for an attacker, and this is in constant tension with our desire to make our systems simultaneously more powerful, more general and flexible, and less complicated. So work like Meredith Patterson's Language-Theoretic Security and Turner's Total Functional Programming represents important advances in the kinds of systems we can practically build.
- GuB-42 7y ago
  The most interesting part for me is that sudoku is a NP-complete problem, and it can do it rather quickly. I wonder how effective sqlite is effective at solving SAT or other similar problems. I mean, there are solvers that are certainly much better, but the advantage is that you may have sqlite for free in your work environment. The same can be said of regexes BTW. PCRE are NP-hard and have them solve SAT is relatively straightforward.
  - Twisol 7y ago
    Sudoku is only NP-complete if you generalize to arbitrary NxN boards. The standard 9x9 Sudoku gives a finite class of problem instances, so you could pre-generate a finite lookup table and get an O(1) algorithm on that class. It sounds like I'm nitpicking, but restrictions of any NP-Complete problem to a finite class automatically reduces the strength of the problem. To the point, an SQL statement on "small enough" SAT instances will probably also be rather fast.
    - chx 7y ago
      > you could pre-generate a finite lookup table and get an O(1) algorithm on that class. If I remember my numbers right there are ~6.67 * 10 ^ 21 valid puzzles so if you want to generate and store that table, I am afraid your Amazon S3 bill will be a bit on the higher side. According to https://www.bernardmarr.com/default.asp?contentID=1846 https://www.bernardmarr.com/default.asp?contentID=1846 , the ‘Global Datasphere’ in 2018 reached 18 zettabytes. IOW, your little lookup table would consume all the storage in the world. So yes in theory you are right of course, it's doable but in practice it's not.
      - hinkley 7y ago
        I'm not sure that's the finite lookup table he's talking about. Within the last year we talked about Peter Norvig's sudoku solver: https://norvig.com/sudoku.html https://norvig.com/sudoku.html He starts by generating a table where each cell is represented by a data structure that enumerates all of the legal values in that cell. The options. Then there is code that can find all the peers of a cell (same row, same column, same square). Turns out that most 'easy' and many 'moderate' puzzles can be solved by starting with a list of all cells with one option. For each cell: * solve the cell * for all peers, eliminate that value from their options * for all peers with one remaining option, recurse I believe that's quadratic time, and intuition tells me breadth-first converges faster. After that, Norvig reaches for brute force, under the theory that this has already gotten you so close to the solution that it's not worth implementing and debugging more complex constaint logic. But I think that despite his claims that Sudoku is a disease, I think this is a taunt; it simply encourages you to go into a more sophisticated process of elimination. Single elimination: Any option that only has one cell in a row, column or square: solved. Double elimination: If a pair of peers have only the same two options, then eliminate that option from all of their common peers. Solves nothing, but may solve other cells. Triple and Quadruple elimination: same thing, but progressively rarer. Quintuple elimination: I don't recall why, but it was asserted that since this is more than half of 9, any time this happens a simpler constraint is also true. I believe that covers all of the moderate difficulty puzzles and the occasional hard ones. From there there's a whole array of other constraints you can implement. You can either do it yourself as an exercise, or there are whole websites dedicated to these rules.
fsakura 7y ago
Wow, and here I thought writing sudoku solver in Java is a tough task.
- lvh 7y ago
  If you think Sudoku solvers are cool, check out (constraint) logic programming, e.g. https://github.com/clojure/core.logic/wiki/Examples#sudoku https://github.com/clojure/core.logic/wiki/Examples#sudoku You can take that pretty far! I used it to solve Regex Crossword [0]: https://www.lvh.io/posts/solving-regex-crosswords/ https://www.lvh.io/posts/solving-regex-crosswords/ https://regexcrossword.com/ https://regexcrossword.com/
ThePhysicist 7y ago
I solved the “eight queens” Problem in SQL once: https://gist.github.com/adewes/5e5397b693eb50e67f07 https://gist.github.com/adewes/5e5397b693eb50e67f07 Recursive common table expressions are quite powerful.
gfody 7y ago
and a 3D cube: https://observablehq.com/@pallada-92/sql-3d-engine https://observablehq.com/@pallada-92/sql-3d-engine
_aleph2c_ 7y ago
"Udo of Aachen" was the first fictional monk to find the "Mandelbrot" set: https://users.math.yale.edu/public_html/People/frame/Fractals/MandelSet/MandelMonk/MandelMonk.html https://users.math.yale.edu/public_html/People/frame/Fractal...
- dvt 7y ago
  Fantastic (and hilarious) read :) Thanks for sharing!
- bloopernova 7y ago
  oh wait, Wikipedia says it's an elaborate April Fools hoax: https://en.wikipedia.org/wiki/Udo_of_Aachen https://en.wikipedia.org/wiki/Udo_of_Aachen (I originally missed the "Fictional" part of the original comment. Time to try to wake up more)
doersino 7y ago
Since SQL (with recursive CTEs and window functions) is Turing complete [1], one can implement all kinds of algorithms with it. I've replicated an ancient handwriting recognizer in Postgres: https://github.com/doersino/handwriting https://github.com/doersino/handwriting [1]: https://stackoverflow.com/questions/900055/is-sql-or-even-tsql-turing-complete https://stackoverflow.com/questions/900055/is-sql-or-even-ts...

193 points by mmoez 7y ago

rajangdavis 7y ago

The sudoku solver is equally impressive, didn't realize that SQL could be bent to do these sorts of things.

chaoticmass 7y ago
When I was around 19 and messing around with Visual Basic 5, I made a Sudoku solver. I thought up an algorithm myself, coded it, and it worked. I was very proud of myself. Seeing how succinct this SQL solver is now, I am in awe.
bawolff 7y ago
I believe that recursive CTEs make sql a turing complete language.
- cryptonector 7y ago
  Of course. You can easily build programs too difficult to prove terminate using CTEs. But even before CTEs, SQLite3 was Turing complete: you could write recursive triggers. Recursion == looping. Any looping construct, recursive or otherwise, that doesn't require a literal max iteration count implies Turing completeness.
  - kragen 7y ago
    > Recursion == looping. Any looping construct, recursive or otherwise, that doesn't require a literal max iteration count implies Turing completeness. There are other ways to restrict looping constructs other than literal max iteration counts to avoid Turing-completeness; structural induction in Coq, LEAN, and Total Functional Programming is one example.
    - anewvillager 7y ago
      True, but all such limitations serve to give an upper bound on the iteration count (which may not be a single constant but depend on the input). It can be demonstrated that if you don't have an upper bound then the language is Turing complete.
      - kragen 7y ago
        You are speaking in such a sloppy way that I doubt that the reasoning you intend to express is sound; certainly what you have actually said is false. For example, a machine with only the instructions JMP, HLT, and NOP can express loops with no upper bound, but is not Turing-complete; it is computable in linear time whether a given program will halt or not. A more interesting kind of automaton that includes unbounded loops is a nondeterministic finite automaton, which can generate regular languages, but is not Turing-complete. It is true that you do not need to add very many constructs from the programming languages we're familiar with before you reach Turing-completeness; Fractran and Minsky's two-counter machine are two rather astonishing examples. But when we were talking about languages lacking an indefinite-looping construct, we were already outside the bounds of "ordinary programming languages", so we can't just take for granted our vague intuitive ideas of what other things they can do; we have to be specific, not vague, in order to make rigorous statements like "the language is Turing complete."
  - bawolff 7y ago
    > Recursion == looping. Any looping construct, recursive or otherwise, that doesn't require a literal max iteration count implies Turing completeness. I'm not a computability theory person, but that doesn't sound right. Afaik, linear bounded automata can loop infinitely, but are not turing complete. Edit: After googling. I guess the important bit is conditional looping and unbounded storage. I think including recursive triggers is cheating a bit because the impressive bit is the query itself is turing complete without any other setup. But anyways CTEs don't just provide looping, they also provide a means to store and retrieve an unbounded amount of intermediate values. Its not obvious to me that that was possible in single query in sql without CTEs
    - kragen 7y ago
      I think SQLite could store and retrieve an extremely large amount of data as TEXT even before adding recursive CTEs, and you could do LIKE '%FOO' || BAR || 'BAZ%' queries to retrieve substring data from them; nevertheless, as far as I know, you couldn't encode Turing-complete queries in a SQL query before recursive CTEs. Conditional looping is not strictly necessary if you're willing to accept an infinite loop with a "halted" flag set as halting. Moreover, conditional looping and unbounded storage is not strictly sufficient; the loop needs to be able to depend on an unbounded part of the unbounded storage, for example, although not necessarily within a single iteration (which is impossible in many Turing-complete models of computation). So, for example, a finite automaton that stores matched parts of its input string on an output printout, but cannot consult that printout, does not thereby achieve Turing-completeness. Moreover, nondeterministic pushdown automata with ε-productions have conditional looping and unbounded storage that they can actually consult during computation, but they are not Turing-complete; they can only recognize context-free languages. I don't think you can reduce Turing-completeness to a laundry list of language features in that way, because you can always construct an automaton that restricts the ways those features can be combined so as to avoid Turing-completeness. This is not, as it may seem, merely a perverse form of computational masochism; on the contrary, it is often considered highly undesirable for a program to unexpectedly enter an infinite loop or perform an arbitrary computation for an attacker, and this is in constant tension with our desire to make our systems simultaneously more powerful, more general and flexible, and less complicated. So work like Meredith Patterson's Language-Theoretic Security and Turner's Total Functional Programming represents important advances in the kinds of systems we can practically build.
GuB-42 7y ago
The most interesting part for me is that sudoku is a NP-complete problem, and it can do it rather quickly. I wonder how effective sqlite is effective at solving SAT or other similar problems. I mean, there are solvers that are certainly much better, but the advantage is that you may have sqlite for free in your work environment. The same can be said of regexes BTW. PCRE are NP-hard and have them solve SAT is relatively straightforward.
- Twisol 7y ago
  Sudoku is only NP-complete if you generalize to arbitrary NxN boards. The standard 9x9 Sudoku gives a finite class of problem instances, so you could pre-generate a finite lookup table and get an O(1) algorithm on that class. It sounds like I'm nitpicking, but restrictions of any NP-Complete problem to a finite class automatically reduces the strength of the problem. To the point, an SQL statement on "small enough" SAT instances will probably also be rather fast.
  - chx 7y ago
    > you could pre-generate a finite lookup table and get an O(1) algorithm on that class. If I remember my numbers right there are ~6.67 * 10 ^ 21 valid puzzles so if you want to generate and store that table, I am afraid your Amazon S3 bill will be a bit on the higher side. According to https://www.bernardmarr.com/default.asp?contentID=1846 https://www.bernardmarr.com/default.asp?contentID=1846 , the ‘Global Datasphere’ in 2018 reached 18 zettabytes. IOW, your little lookup table would consume all the storage in the world. So yes in theory you are right of course, it's doable but in practice it's not.
    - hinkley 7y ago
      I'm not sure that's the finite lookup table he's talking about. Within the last year we talked about Peter Norvig's sudoku solver: https://norvig.com/sudoku.html https://norvig.com/sudoku.html He starts by generating a table where each cell is represented by a data structure that enumerates all of the legal values in that cell. The options. Then there is code that can find all the peers of a cell (same row, same column, same square). Turns out that most 'easy' and many 'moderate' puzzles can be solved by starting with a list of all cells with one option. For each cell: * solve the cell * for all peers, eliminate that value from their options * for all peers with one remaining option, recurse I believe that's quadratic time, and intuition tells me breadth-first converges faster. After that, Norvig reaches for brute force, under the theory that this has already gotten you so close to the solution that it's not worth implementing and debugging more complex constaint logic. But I think that despite his claims that Sudoku is a disease, I think this is a taunt; it simply encourages you to go into a more sophisticated process of elimination. Single elimination: Any option that only has one cell in a row, column or square: solved. Double elimination: If a pair of peers have only the same two options, then eliminate that option from all of their common peers. Solves nothing, but may solve other cells. Triple and Quadruple elimination: same thing, but progressively rarer. Quintuple elimination: I don't recall why, but it was asserted that since this is more than half of 9, any time this happens a simpler constraint is also true. I believe that covers all of the moderate difficulty puzzles and the occasional hard ones. From there there's a whole array of other constraints you can implement. You can either do it yourself as an exercise, or there are whole websites dedicated to these rules.

fsakura 7y ago

Wow, and here I thought writing sudoku solver in Java is a tough task.

lvh 7y ago
If you think Sudoku solvers are cool, check out (constraint) logic programming, e.g. https://github.com/clojure/core.logic/wiki/Examples#sudoku https://github.com/clojure/core.logic/wiki/Examples#sudoku You can take that pretty far! I used it to solve Regex Crossword [0]: https://www.lvh.io/posts/solving-regex-crosswords/ https://www.lvh.io/posts/solving-regex-crosswords/ https://regexcrossword.com/ https://regexcrossword.com/

ThePhysicist 7y ago

I solved the “eight queens” Problem in SQL once: https://gist.github.com/adewes/5e5397b693eb50e67f07 https://gist.github.com/adewes/5e5397b693eb50e67f07 Recursive common table expressions are quite powerful.

gfody 7y ago

and a 3D cube: https://observablehq.com/@pallada-92/sql-3d-engine https://observablehq.com/@pallada-92/sql-3d-engine

_aleph2c_ 7y ago

"Udo of Aachen" was the first fictional monk to find the "Mandelbrot" set: https://users.math.yale.edu/public_html/People/frame/Fractals/MandelSet/MandelMonk/MandelMonk.html https://users.math.yale.edu/public_html/People/frame/Fractal...

dvt 7y ago
Fantastic (and hilarious) read :) Thanks for sharing!
bloopernova 7y ago
oh wait, Wikipedia says it's an elaborate April Fools hoax: https://en.wikipedia.org/wiki/Udo_of_Aachen https://en.wikipedia.org/wiki/Udo_of_Aachen (I originally missed the "Fictional" part of the original comment. Time to try to wake up more)

doersino 7y ago

Since SQL (with recursive CTEs and window functions) is Turing complete [1], one can implement all kinds of algorithms with it. I've replicated an ancient handwriting recognizer in Postgres: https://github.com/doersino/handwriting https://github.com/doersino/handwriting [1]: https://stackoverflow.com/questions/900055/is-sql-or-even-tsql-turing-complete https://stackoverflow.com/questions/900055/is-sql-or-even-ts...