王垠：我和Google的故事

狗蛋

KanonInD 发表于 2012-08-14 11:57
(python的)鸭子类型有什么不好, 为何需要类型推导?

python的duck type本身没什么不好，不过它必须要在运行时环境里、运行到的那一刻才能知道被调用的方法存不存在、来自何处。

对编辑器及其用户（程序员）来说，他们看不到动态的东西，只能看到静态的代码。那么，具体到一个方法究竟由谁提供，哪怕是程序作者自己恐怕都无法立刻回答。

一般的编辑器实现类似正则表达式模式匹配：你调用了to_str()，它就找所有提供了to_str()的类；这样大多数情况下能工作，而且不需要多少代码就能实现。
但恰恰对to_str()，这个办法失效了。因为这个方法每个类都有，全列等于没有列；而对method proxy这类应用，它提供的很多方法根本不可能从代码上看到。这就相当于在静态分析时丢掉了一个关键环节。


为解决以上问题，字符串匹配法同样有可能解决；但这样就要穷举匹配各种可能，相当于人工分析代码、并通过前后对比以找到线索，去回答“哪些to_str和当前代码行无关”和“这个proxy究竟提供了哪些方法”问题。

这种做法可行，但非常笨拙，好像杀牛用了水果刀，代码量自然飕飕就上去了，bug也肯定是一出一大坨。


此文作者相当于实现了一个能静态推导运行时类型的预处理器；这个实现提供的能力类似运行时，但无须真正执行程序（那样代价就太大了）。
大概思路就是写一个编译器去检查类型如何“传染”出去。这样，当你查询某个对象的to_str()方法时，他就可以根据“传染逻辑”反推，告诉你这个方法只可能来自哪些类；类似的，对一个method proxy类，他也能回答“根据目前的程序逻辑，这个类能提供哪些方法、这些方法都来自何处”。

这样一来，动态类型的语言一样可以像静态强类型语言一样，在程序编写的同时就得到丰富的方法/类型/参数提示。这种功能，显然是基于模式匹配的手段绝对无法达到的。

这个“静态代码分析”的做法比起字符串模式匹配，起始代码量大，类似杀鸡用牛刀；但遇到棘手的to_str/method proxy之类情况时，反而非常轻松，因为用对了工具。

狗蛋

http://blog.sina.com.cn/s/blog_5d90e82f010177qx.html
我比较喜欢这篇。
——————————————————————————————————————————

对动态语言，如python，下面这个函数究竟返回什么？

def max(a, b):
     return a if a>b else b

如果局限于一点，至多能回答：返回的是一个有 > 方法的对象。


这个帖子里的大部分朋友，恐怕都是被锁死到这里了。




但是，众所周知，模板函数的返回类型无法确定，并不等于某段调用模板函数的代码所返回的类型无法确定。

x=max(1, 3)

现在x的类型知道不知道？

如果传给max的东西是经过N层函数调用才传过来的呢？
对一个大项目，能回答这个问题，显然是至关重要的；而这个问题的答案也是非常简单的：追溯传给max函数的那个对象的由来——它必然是有一个由来的——自然也就知道max返回值的类型了。

这个过程类似C++模板的实例化。

当然，如果传给max的东西无从追踪，就说明max这个“模板函数”没有被调用过（未实例化）。它就继续作为一个无类型的模板库而存在吧。
即便如此，语义分析仍然能告诉我们，这个模板库的参数需要满足什么性质——这只要看该参数在传递过程中被调用过哪些方法即可。


至于eval，它不过也是个“模板库”罢了。

甚至于：
x=eval
switch x.user_declared_type():
....

对以上结构，甚至可以针对每个switch分支，去分析该分支的x应该有什么性质（看它被传递到后端后，被调用的方法即知），从而在编程时给予恰当的提示。

这个过程类似C++模板的特化/偏特化。




很显然，以上种种，都不是什么神秘的高级技术，长了一副大众脸的C++模板相关技术而已。
换言之，所谓的动态类型语言、duck type，其实就是模板化的语言而已——只不过，念叨着这些概念的大多数人并不明白这点。

狗蛋

OwnWaterloo 发表于 2012-08-17 12:57
回复 40# 狗蛋

你听说过模块化、分离编译、全局程序分析等概念么？

但是 Grok 的设计目标不只是检索和分析本机的某一种语言的代码，而是大规模的检索和分析 Google 的所有项目，所有语言，所有代码。这包括 Google 的“四大语言”：C++, Java, JavaScript, Python，一些工具性的语言：Sawzall，protobuf 等，还有一些“build file”和所有第三方的库。Grok 的初期设计目标是一个静态的代码索引服务，只要程序员点击任何一个变量或者函数名，就能“准确”的跳转到它定义的位置。动态的编辑功能稍后也在陆续加入。

无非是40楼帖子内容提到原则的递归应用而已。


甚至，假设X位于一个动态连接库，仍然可以通过分析“build file”把引用到这个库的代码识别出来，从而回答某个编译单元引用到的X究竟是什么。


PS： 我不认为名词很重要；说实在的，我的学习目标是“忘掉名词”，以免被名词晃花了眼，变成个字典。

狗蛋

回复 43# OwnWaterloo


    原来max(a,b)和eval单独都知道，放一块就抓瞎了啊……举一反三有这么难吗？

好吧，我什么都不懂，你说什么就是什么算了。

狗蛋

回复 45# OwnWaterloo


    看不懂不要紧，看不懂反而拿自己的狭隘来咬人，这连“狂妄”都谈不上。



谈起什么问题，都需要一个“前提”，都需要一个实用场景。忽视这种前提的抬杠就叫胡搅蛮缠。



比如，对未实例化的max，我认为它相当于一个模板。一旦被传入有明确类型的对象，它的类型就立刻得到确定——我把它叫做“传染”。

然后，对eval，我认为这相当于一个运行时实例化的模板，置之不理即可。

组合起来，eval到max参数，结果仍然不过是个未实例化的模板。




至于eval返回值的类型，这显然是必须在运行时解决的，只有傻子才以为别人连这个都拎不清。
因为它甚至可以接受命令行的手工输入，生成任意对象——这得多傻，才会一厢情愿的以为别人想解决这种问题？

能把别人看傻到这种程度的，要么是狂妄到不知道自己是谁了，要么是推己及人吧。






能做，就做，而且做了会带来很大的方便；不能做，果断放弃。这就叫智者。

至于那些完全摸不清情况、不知道何谓“应用场景”口出不逊的狂妄之徒，恕我懒得在他身上浪费时间。

狗蛋

事实上，我用c++的模板来举例子，就是为了怕一些人理解不了何谓运行时。结果，现身说法的果然就来了。


我们可以这样理解静态分析：

1. 
   
2.    ?1    ?2
   
3.    |      |
   
4.   ?3    ?4
   
5.       |
   
6. ?7 max(?5, ?6)
   
7.       |
   
8.   fun(?8)
   

复制代码

如上，max(a,b)是模板态，这也是静态所见。

当?5和?6取了某个不能应用 > 运算符的值时，c++的做法是置之不理（哪怕在编译时）；python也爱莫能助。直到运行时抛出异常甚至程序崩溃。

但，事实上，通过静态分析，完全可以在编译/运行前就发现?5甚至?3甚至?1是不兼容的类型，并提示代码编写者注意。


类似的，当?1和?2的类型可以静态确认时，?7的类型就得到了。那么，之后涉及?7的任何语句就都可以进行类型检查了。
比如，?8


很显然，除了eval这样极端的例子，动态语言的静态分析一样可以得到它的运行时类型。


————————————————————————————————

当然，有些人会这样玩（我的一个同事就这样做过）：
1、要求用户输入一个表达式或者一段脚本或者另外一个C/C++格式的函数
2、编译这个表达式/脚本成汇编代码
3、强制指针类型转换，以函数形式调用编译完的数据

这种能不能静态分析？
当然不能。

如果整个程序都以这种方式写成，C/C++部分只管编译和载入，怎么办？
凉拌。

所以，按照一些人的标准，C/C++也是“动态”语言，一样不能静态分析