4 ms·

SQL is not Prolog though. SQL, at least the parts mapping to relational algebra, is not Turing-complete, Prolog is. I'm pretty sure Prolog not specifying an exe

by _yosefk 10y ago

SQL is not Prolog though. SQL, at least the parts mapping to relational algebra, is not Turing-complete, Prolog is. I'm pretty sure Prolog not specifying an execution strategy would mean that your program terminates under one interpreter but not under another, not to mention their asymptotic complexity, which I think is not as bad with SQL. In other words, it's not a lie to promise that you can specify a query over tables in a declarative way, but it's sort of a lie to promise that you can spell out predicates describing a solution and the machine will find a solution satisfying these predicates, because sometimes it can't. Specifying an execution strategy doesn't make it less of a lie but it lets you write a working program kinda looking as if it weren't a lie.

catnaroek 10y ago
> I'm pretty sure Prolog not specifying an execution strategy would mean that your program terminates under one interpreter but not under another, not to mention their asymptotic complexity, which I think is not as bad with SQL. Yup! But it's not as bad as it seems. In a pure logic language, the changing the execution strategy can only change three things: (0) Whether a query terminates, in which case it returns the entire soution set. (1) If the query doesn't terminate, which subset of the solution set is returned. (2) How fast it runs, of course. Which is a lot better than the subtle things that can go wrong when optimizing imperative programs by hand. Selecting an execution strategy for a declarative program is no different from tuning a garbage collector: if you do it wrong, bad things can still happen, but they won't be as bad as if you manage things by hand and do it wrong. > it's sort of a lie to promise that you can spell out predicates describing a solution and the machine will find a solution satisfying these predicates, because sometimes it can't. Yup! Which leads (IMO) to the conclusion that general-purpose languages must always include some imperative (explicit control) component. Declarative languages really shine as DSLs, though.
garyclarke27 10y ago
SQL is turing complete, at least on Postgres. Case statements provide control of flow and WITH Recursive CTEs provide looping/iteration/recursion. Pure SQL functions can accomplish nearly anything (except dynamic execution, think macros) that procedural PL/pgSQL can, WITH statements provide variables and temp tables. SQL is the most declarative language I'm aware of.

by _yosefk 10y ago

catnaroek 10y ago

> I'm pretty sure Prolog not specifying an execution strategy would mean that your program terminates under one interpreter but not under another, not to mention their asymptotic complexity, which I think is not as bad with SQL. Yup! But it's not as bad as it seems. In a pure logic language, the changing the execution strategy can only change three things: (0) Whether a query terminates, in which case it returns the entire soution set. (1) If the query doesn't terminate, which subset of the solution set is returned. (2) How fast it runs, of course. Which is a lot better than the subtle things that can go wrong when optimizing imperative programs by hand. Selecting an execution strategy for a declarative program is no different from tuning a garbage collector: if you do it wrong, bad things can still happen, but they won't be as bad as if you manage things by hand and do it wrong. > it's sort of a lie to promise that you can spell out predicates describing a solution and the machine will find a solution satisfying these predicates, because sometimes it can't. Yup! Which leads (IMO) to the conclusion that general-purpose languages must always include some imperative (explicit control) component. Declarative languages really shine as DSLs, though.

garyclarke27 10y ago

SQL is turing complete, at least on Postgres. Case statements provide control of flow and WITH Recursive CTEs provide looping/iteration/recursion. Pure SQL functions can accomplish nearly anything (except dynamic execution, think macros) that procedural PL/pgSQL can, WITH statements provide variables and temp tables. SQL is the most declarative language I'm aware of.