新的确定性语言应运而生,用于在多核上运行的多线程软件的确定性执行,例如Cilk++Deterministic Parallel Java

现在我的问题是,这些语言可以用于实现任何类型的算法还是仅用于特定算法。换句话说,这些语言是否以任何方式限制了程序员?

最佳答案

最常见的“算法”定义不允许算法指定Turing machine无法执行的计算。假设您使用的是这些常规定义之一,

否。可以使用图灵完整语言指定所有图灵机(模资源限制)。这些确定性语言大体上是图灵完整的。

也就是说,由于硬件接口(interface)的原因,您可能无法编写某些类型的软件(而非算法),例如设备驱动程序,需要很好地处理volatile memory,而出于安全性的原因,某些特殊目的的软件有时会表现出不可预测的行为,例如, cryptographically strong键,盐或随机数的生成。有确定性强的加密PRNG,但是生成 key 的最佳方法是通过真正的随机性源。

例如,最小的JavaScript(并且只有JavaScript;没有DOM绑定(bind))解释器减去Math.randomDate.now以及其他一些非确定性来源将被视为确定性,因为其event-loop concurrency model指定了交织。 JavaScript是一种图灵完备的语言,可以表达Java之类的语言可以执行的任何算法。您可以在该基本JavaScript中包括setTimeout之类的工具,该工具仅允许0作为延迟,以允许确定性延迟评估,从而提供了丰富的确定性方式来节省时间。

Verilog是另一种事件循环并发语言,具有图灵完备的丰富表达确定性子集。

Joe-E是Java的图灵完整子集,旨在提供确定性保证,作为提供"Verifiable Functional Purity in Java"的一部分,尽管它努力支持Java的线程模型。

除了事件循环并发之外,还有多种actor model可以提供确定性,如What's *Deterministic concurrency*?所述

关于java - 确定性语言的适用性,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/7082349/

10-09 03:02