多线程是个不靠谱的东西

我这里指的指令并行，并不是说如何让一条指令在多个CPU上并行执行.而是说如何从语言层面上保证在并行部分不会出现竞争资源的代码。

如 T1 所说, 主要就是并行粒度的问题.

目前的多线程模型,主要用于多任务,多用户的问题.(任务粒度).
比如,多线程下载.Web静态页面应答. 这些是简单的同类同质线程任务.问题本身就是顺序无关的.

个人看法.
LZ给出的一些例子,都是顺序相关的, 后面的任务要依赖于前面的任务的状态. (任务粒度).
这本身就带有了顺序限制, 这就是更复杂的多线程协作模型. 如消费者/生产者,读写者等等.这些线程任务的角色不同, 类型也不同.这种复杂的数序相关的情况, 什么模型,什么体系都没用.问题本身就是顺序相关的.

关于多核, 最关键的确实是并行粒度的问题.
如果能够并行到指令(语句)级别,那当然最好.
程序员根本就不需要考虑任何多线程模型,同步模型.随便写出一串代码, 就是天生多核并行的.
但那是不可能的(也许可能,但我想象不出来).指令所描绘的任务,很难避免时间性和顺序性.

并行粒度,不一定要达到指令级别. 先达到函数级别应该就够了.
如果,一系列顺序的函数调用都是无状态的,那么这些函数的执行顺序就无关了.
同一个调用层次上的函数就可以并行分配到多核上运行.
这样一层层下去, 调用树所有的无状态函数都可以分配为多核并行.
编程上,也简单了许多.只要写出无状态的函数, 这些函数,就是天生可以多核并行的.

如果函数级别达到了，实际上这个函数的所生成的指令就不存在资源竞争.

这个函数内部的指令(语句)之间可能是要求顺序.后一句可能依靠前一句的结果.
纯函数(无状态无副作用)可以把这些语句隔离包装成一个类似原子操作的东西.里面的顺序相关语句不会被拆开到多个CPU运行.只在一个CPU上运行.
一大串的纯函数调用,可以随意拆分到多个CPU上并行.

-------------------------------

我想象了这样的情况.
先假设我们确实有一种机制(比如 Monad 什么的),能够隔离副作用,外部全局状态等.
所有的函数,从外面看起来, 都是纯函数.
这样, 我们只需要处理语句顺序依赖相关的问题 (这里面只涉及到很小的函数内部状态).
假设顺序依赖相关的语句,用 S1, S2 表示.
纯函数, 用 P1, P2 表示.

P1 () {
S1
S2
P2()
P3()
}

P2(){
P4()
S3
}

.....


这样的一种调用树 (calling tree), 可以依据是否顺序相关, 切分为多个Node.
Node只有两种, 一种是 Pure Node, 一种 顺序 Node.
如果一个Node的子Node 都是 Pure Node, 不用说, 天生就是多核的.
如果一个 Node的子Node 是混合的,既有Pure Node, 又有 顺序 Node.
那么就要有一个顺序, 先在某一个CPU 执行完顺序语句, 后面并列的Pure Node可以并行多核, 然后再回归到某个CPU, 执行顺序语句.

这那是扯多线程，往并行计算上扯。

二者本来就是本质相关的，多线程本身就是并行的一种最重要实现方式，有什么疑问吗？



这是三种函数的模式，同步，异步，和可迁移。分别是对应intra-process和inter-process两种情况。

纯粹的lambda函数求值本身就是顺序无关的, 这是由β规约决定的.

印象中, β规约的大意是, Referential Tranparent.同样的字符串表达式可自由替换.
这意味着, 后面的某些语句, 确实有可能在前面的语句之间进行.
我感觉, 这是在顺序无关的语句之间才可能发生这种自由替换和随意顺序执行的情况.
纯函数的内部, 应该是有可能包含顺序相关的语句. 后一条语句, 依赖于上一条语句的结果.
比如,
f (a ) {
b = a + 2
c = b + 3.
d = a + 2 * b + c
return d
}

除非所有用到局部变量的语句,都被替换为只用最基本参数变量的语句.
所有的非参数变量都会被替换掉.
比如,上述代码在编译的过程中就被替换为
f( a ) {
return  a + 2 * (a + 2) + ( a + 2 + 3)
}

这种替换是否具有普遍性?
是否所有的纯函数,最终都可以替换为一个多元公式?

--------------------------

纯函数内部, 不存在任何顺序相关的语句指令.
这种说法是正确的吗 ?

是否可以得出这样的结论.
既然纯函数内部的语句指令也都是顺序无关的.
那么调用树,执行树中所有的 Node 都是 Pure Node.
那么纯函数语言编写的程序天生就是可以多核任意拆分迁移的.
(只有Monad隔离的副作用部分是特例,必须要在某个特定CPU上顺序执行).

这只不过是假象而已


(lambda x:x+3) (x+2)

Apply alpha[x/y]: lambda z . (lambda y . y+z)) (x + 2)
Apply beta: (lambda y . y + x + 2) 3
Apply beta: 3 + x + 2.

对于任何一个纯函数，都能表达为lambda式。对lambda 式可以使用树规约或者图规约.
前者是串行的而后者是天然并行的
比如说这是一个典型的bottom up树规约
((2 + 2) + (2 + 2)) + (3 + 3)
= ((2 + 2) + 4) + (3 + 3)
= (4 + 4) + (3 + 3)
= (4 + 4) + 6
= 8 + 6
= 14
或者构造一个的top down树规约
((2 + 2) + (2 + 2)) + (3 + 3)
= ((2 + 2) + (2 + 2)) + (6)
= ((2 + 2) + 4) + 6
= (4 + 4) + 6
= 8 + 6
= 14
这两种规约都是一颗树

           +
       +           +
    +        +    3 3
 two  two two  two

树规约可以转化为图规约，图规约可以共享子表达式

           +
       +           +
    ?     ?        3 3
       +
    two  two 

因此在图规约下，2+2和3+3互不依赖，可以并行执行.

查了一下"图规约",没找到相关的资料.
能否给个图规约的相关link或者例子?

只看到一点有限信息. Haskell VM 是图规约的 (顺序无关).
图规约的英文是什么?