- 主题:python终于要支持case语句了
pattern match 对编译器并不友好
https://niedzejkob.p4.team/rust-np/
【 在 poocp 的大作中提到: 】
:
: match那里进行了范围约束。
: 下面无论多少个case，也只能在上述框架内跳舞了。
: 而elif后面能跟的东西就太过天马行空了。
:
#发自zSMTH@Moto Z3 Play
--
FROM 37.33.57.*
rust 或者其它主流语言不会用 smt solver 来编译 pattern match ，因为这个依赖太强，而且 smt solver 也很不稳定。
我只是想说从静态分析和优化的角度来看， if-else 远比 pattern match 容易，因为 if-else 就是生成两个新的 basic block ，然后加几条 phi ，没了，之后的优化都是经典 ssa 分析，跟其它 control flow 没有区别。而 pattern match 分析，等同于解一组布尔值方程，算法不好的话很容易死在只有几条方程的情况下。
【 在 poocp 的大作中提到: 】
:
: 还是以最终实现为准吧，哪个快用哪个，当然我是指rust。
: 至于python其实无所谓，我更看重代码的可读性。
:
: 【 在 philbloo 的大作中提到: 】
#发自zSMTH@Moto Z3 Play
--
FROM 37.33.57.*
你说的表驱动是给 c 那种 switch case 用的，那种最简单，就一 jmp table ，可以直接 lower 到 ISA 上。但 pattern match 是 np hard，跟 switch case 不是一个问题，跟泛型也没有关系。
【 在 poocp 的大作中提到: 】
:
: 抛开泛型的复杂情况，单一类型单纯数值的pattern match由于是有界的，所有case可以放入数值范围表格来进行优化，而这种用法是最常见的方式。
:
: 【 在 philbloo 的大作中提到: 】
: : rust 或者其它主流语言不会用 smt solver 来编译 pattern match ，因为这个依赖太强，而且 smt solver 也很不稳定。
#发自zSMTH@Moto Z3 Play
--
FROM 37.33.57.*
当然，pattern match __可以__ 应用在泛型上，但这个问题的本质与泛型无关，开始那个链接里的例子就完全与泛型无关。因为这个问题在于要找出所有 case 是否 exhaustive，以及是否存在不可解的 contradiction，换句话说，是做 constraints based analysis 。
而你的这个 if-else 的复杂度等于 pattern match 的推论也是错的。因为 if-else 的编译不需要 exhaustive ，也不需要分析 contradict，但 pattern match 需要。
【 在 poocp 的大作中提到: 】
:
: 按这个推论，那么所有if else也都是np hard，因为所有 pattern match都能表达为等价的if else。
:
: 【 在 philbloo 的大作中提到: 】
: : 但 pattern match 是 np hard
#发自zSMTH@Moto Z3 Play
--
FROM 37.33.57.*
我没有钻牛角尖，我最近在写 Python 的 parser 和 compiler，所以对这方面的问题知道的多一点。
从你这个回答，我认为你把编译的过程和结果弄混了。编译结果是什么，不管是不是 jmp table ，在这个讨论里并不重要。因为我们讨论的是编译过程的复杂度。
而一旦遇到了 pattern match 的语法，就必须做 constraints 分析，哪怕最终的结果是整个语法块都可以去除。所以，pattern match 是为了更容易优化，或者 pattern match 可以导致更优化的 target ，都不成立。事实上，if-else 同样可以编译出 jmp table 的 target 。
【 在 poocp 的大作中提到: 】
:
: 为啥我觉得你是在钻牛角尖。case的最好优化结果就是jmp table，最坏优化结果就是等价的if else。
:
: 【 在 philbloo 的大作中提到: 】
: : 当然，pattern match __可以__ 应用在泛型上，但这个问题的本质与泛型无关，开始那个链接里的例子就完全与泛型无关。因为这个问题在于要找出所有 case 是否 exhaustive，以及是否存在不可解的 contradiction，换句话说，是做 constraints based analysis 。
#发自zSMTH@Moto Z3 Play
--
FROM 37.33.57.*
你又弄错了，一个问题是否是 np hard 是 intrinsic 的。也就是说，在任何条件下，分析 pattern match 都是 np hard。
你强调的这点，也是错的，因为存在无穷数量的 pattern match 实例，这些实例不存在等价的 if-else 。而编译器的任务是要鉴定当前实例是否可以转换为 if-else ，并针对否定的答案给出合理的出错信息。事实上，给出合理的出错信息比证否更难。
【 在 poocp 的大作中提到: 】
:
: 那你也不能以某种特定条件下最坏情况是np hard来以偏概全，拿来当结论吧。
: 怎么优化是你的事，我只强调一点，case必然具有等价的if else表达方式。
: 所以case最坏的结果就是等价的if else。
:
#发自zSMTH@Moto Z3 Play
--
FROM 37.33.57.*
我做的是 compiler ，不是 interpretation 也不是 virtual machine，所以可以放开手优化。我们这的要求是 target 必须是 optimal ，也就是说，任何算法的实际运行速度必须达到 arch 的理论上限。
【 在 javaboy 的大作中提到: 】
:
: 我打个岔。。。你们在说优化？python？
:
: 【 在 poocp (慢速随机指标) 的大作中提到: 】
: : 那你也不能以某种特定条件下最坏情况是np hard来以偏概全，拿来当结论吧。
#发自zSMTH@Moto Z3 Play
--
FROM 37.33.57.*
没那么厉害，也就是借这个产品发了接近十个美国专利，外加一篇顶会文章。甲方没有能力提这么细的要求，我们自己玩的开心而已。
【 在 xiaoju 的大作中提到: 】
:
: 你们甲方太猛了，还是直接拿个图灵奖容易点吧
:
: 【 在 philbloo (philbloo) 的大作中提到: 】
: : 我做的是 compiler ，不是 interpretation 也不是 virtual machine，所以可以放开手优化。我们这的要求是 target 必须是 optimal ，也就是说，任何算法的实际运行速度必须达到 arch 的理论上限。
#发自zSMTH@Moto Z3 Play
--
FROM 37.33.57.*
那你肯定没看我最开始给的链接。里面有非常简单的例子。
【 在 poocp 的大作中提到: 】
:
: 那就举几个实例让我学习一下吧。
:
: 【 在 philbloo 的大作中提到: 】
: : 因为存在无穷数量的 pattern match 实例，这些实例不存在等价的 if-else 。
#发自zSMTH@Moto Z3 Play
--
FROM 37.33.57.*
不想暴露真名实姓
一个新算法 不是很难 但是 soundness 的证明依赖 Extended Riemann Hypothesis
【 在 xiaoju 的大作中提到: 】
:
: 什么文章？
:
: 【 在 philbloo (philbloo) 的大作中提到: 】
: : 没那么厉害，也就是借这个产品发了接近十个美国专利，外加一篇顶会文章。甲方没有能力提这么细的要求，我们自己玩的开心而已。
#发自zSMTH@Moto Z3 Play
--
FROM 85.76.102.*