定义问题而不是解决方案的编程语言？

Question

是否有任何编程语言旨在定义给定问题的解决方案，而不是定义解决问题的指令？ 因此，人们将定义解决方案或最终结果应该是什么样子，而语言解释器将确定如何得出该结果。 看看编程语言列表，我不知道如何开始研究这个。

我目前能想到的最好的例子是 SQL 和 MapReduce，尽管它们都是旨在检索数据的小型语言，但它们有助于说明我想要问的问题。 但是，在编写 SQL 或 MapReduce 语句时，您定义最终结果，并且数据库决定获得最终结果集的最佳操作方案。

我可以看到这些类型的语言（如果存在的话）被用于处理大量数据或寻找一组方程的解决方案。 理想的语言将是一种能够解释定义的问题、识别哪些部分是可并行的、并跨多个进程/核心/框执行解决方案的语言。

Answer 1

这些语言通常称为“第五代编程语言”。 我链接到的维基百科条目中有一些示例。

Answer 2

最接近这样的事情是使用逻辑语言，例如 Prolog。 在这些语言中，您可以对问题的逻辑进行建模，但这并不是魔法。

Answer 3

这听起来像是对声明性语言（特别是逻辑编程语言）的描述，其中最著名的例子是 Prolog。 不过，我不知道 Prolog 是否可并行。

根据我的经验，Prolog 非常适合解决约束满足问题（必须满足一组条件的问题）——您定义输入集，定义约束（例如，必须对先前无序的数据强加的排序）输入）——但病理情况是可能的，有时逻辑推演过程需要很长时间才能完成。

如果您可以用布尔公式定义问题，则可以使用 SAT 求解器来解决它，但请注意，3SAT 问题（三变量子句上的布尔变量赋值）是 NP 完全问题，并且其一阶逻辑大兄弟，量化布尔公式问题（使用存在量词和全称量词）是 PSPACE 完备的。

有一些非常好的定理证明器是用 OCaml 和其他 FP 语言编写的； 这里是一大堆。

当然，总是有通过单纯形法的线性规划。

Answer 4

声明式编程怎么样？ 摘自维基百科文章（已添加重点）：

在计算机科学中，声明式
编程是一种编程范式
表达了一个逻辑
计算而不描述其
控制流程。 多种语言
应用这种风格尝试
最大限度地减少或消除副作用
描述程序应该做什么
完成，而不是描述如何完成
去实现它。 这
与命令式相反
编程，这需要一个
明确提供的算法。

Answer 5

我也会说 Objective Caml (OCaml)...

Answer 6

这可能看起来很轻率，但从某种意义上说，这就是 stackoverflow 的本质。 您声明一个问题和/或预期结果，社区通常以代码形式提供解决方案。

将动态开放系统建模为有限数量的解决方案似乎非常困难。 我认为大多数编程语言都是命令式的，这是有原因的。 更不用说潜伏在黑暗中的大量 P = NP 问题将使这样的系统难以设计。

尽管有趣的是，如果有一个正式的框架可以利用人类输入来“处理数字”并提供解决方案，也许是命令式代码生成。 互联网和谷歌搜索引擎就是这种工具，但非常原始。

大问题和软件基本上只是用代码解决的小问题的集合。 因此，任何生成代码的系统都需要相当明确的问题集，这些问题集可以映射到或多或少的原子解决方案。

Answer 7

让我尝试回答...也许 Prolog 可以满足您的需求。

Answer 8

LINQ 也可以被视为另一种声明性 DSL（避免认为它与 SQL 太相似的论点）。 同样，您声明您的解决方案是什么样的，然后 LINQ 决定如何找到它。

这类语言的美妙之处在于，像 PLINQ（我刚刚发现的）这样的项目可以围绕它们涌现。 与 PLINQ 开发人员一起观看此视频（WMV 直接链接）关于他们如何在不修改 LINQ 语言（太多）的情况下并行化解决方案查找。

Answer 9

虽然数学证明并不构成编程语言，但它们确实形成了一种形式语言，您可以在其中简单地定义解决方案（只要您允许非构造性证明）。 当然，它不是算法，所以“数学”可能不是一个可接受的答案。

Answer 10

元讨论

问题或解决方案的构成并不是绝对的，取决于您作为参考点的抽象级别。

我们来比较以下 3 种语言：SQL、C++ 和 CPU 指令。

C++ 与 CPU 指令

如果您选择数组操作作为所需的抽象级别，那么 C++ 允许您“定义问题”而不是解决方案：

array[i * 2 + 3] = 5;
array[t] = array[k - m] - 1;

请注意此 C++ 代码段没有说明的内容：内存如何布局、有多少位每个数组元素都使用哪些 CPU 寄存器保存数据，甚至算术运算将按什么顺序执行（只要结果相同）。

然而，C++ 编译器会将此代码转换为包含所有这些细节的较低级别的 CPU 指令。

在数组操作的抽象级别，C++ 是声明式的，而 CPU 指令是命令式的。

SQL 与 C++

如果您选择排序算法作为所需的抽象级别，那么 SQL 允许您“定义问题”而不是解决方案：

select *
from table
order by key

这段代码对于排序算法的抽象级别而言是声明性的，因为它声明了输出排序时不使用较低级别的概念（如数组操作）。

如果您必须在 C++ 中对数组进行排序（不使用库），则该程序将用特定排序算法的数组操作步骤来表示。

void sort(int *array, int size) {
   int key, j;
   for(int i = 1; i < size; i++) {
      key = array[i];
      j = i;
      while(j > 0 && array[j-1] > key) {
         array[j] = array[j-1];
         j--;
      }
      array[j] = key;
   }
}

此代码片段对于排序算法的抽象级别而言不是声明性的，因为它使用作为排序算法组成部分的概念（例如数组操作）。

总结

总而言之，一种语言是否定义问题或解决方案取决于您所指的问题和解决方案。

这里的许多答案都提出了示例：SQL、LINQ、Prolog、Lisp、OCaml。 我确信这些语言有许多有用的抽象级别是声明性的。

但是，不要忘记您可以在它们之上构建具有更高抽象级别的语言。

Answer 11

口齿不清。 有很多 Lisp 系统是根据规则而不是命令式命令来定义的。 谷歌啊嘿...

Answer 12

有各种基于 Java 的规则引擎允许声明式编程 - Drools 是我玩过的一个，看起来很有趣。

Answer 13

许多语言定义的问题多于解决方案（不要认真对待这个问题）。

严肃地说：对 Prolog 和不同类型的 DSL 设计为声明性的又一票。

Answer 14

我记得上大学时读过一些关于使用 DNA 进行计算的内容。 您可以将 DNA 片段放入代表问题片段的解决方案中，并以这样的方式定义它：如果 DNA 组合在一起，那么它就是一个有效的解决方案。 然后，您让化学品的特性为您解决问题，并寻找代表解决方案的成品线。 听起来有点像你所指的。

不过，我不记得这是理论上的还是已经完成的。

Answer 15

谷歌创建了一个名为 FunSearch 的东西，它的功能与您所要求的类似。