动态语言的静态分析 | AI生成和翻译

Home 2025.12 English 中文

---

问题：PDF 文件“pysonar-slides.pdf”说了什么？

回答：

PDF 文件“pysonar-slides.pdf”似乎是印第安纳大学信息与计算学院的 王垠 的一份题为“使动态类型语言的静态分析变得容易”的演示幻灯片。它讨论了基于作者在 Google 2009 年和 2010 年实习期间的经验，在 Python 等动态类型语言上执行静态分析的挑战和解决方案。这项工作的灵感来自 Google 的 Grok 项目，该项目旨在静态分析 Google 的所有代码（包括 C++、Java、JavaScript、Python、Sawzall 和 Protobuf）。最初的目标是实现类似 IDE 的代码浏览，但这对 Python 来说很困难，导致了更高级的语义分析。

关键部分和内容

概述（第 1-2 页）

• 描述了实习和动机。
• 强调了 Grok 项目的范围。
• 指出虽然目标最初很简单（代码浏览），但 Python 的动态特性使其充满挑战。

实现的目标（第 3 页）

• 构建了高准确度的语义索引。
• 检测并报告了语义错误，例如：
  • 类型错误。
  • 缺少返回语句。
  • 不可达代码。
  • 以及其他。

静态分析面临的问题（第 5-23 页）

演示文稿概述了四个主要问题及其解决方案：

1. 动态类型问题（第 6-9 页）：
   • 动态类型使名称解析复杂化，尤其是在多态函数中（例如，def h(x): return x.z —— z 在哪里定义？它取决于 x 的类型）。
   • 解决方案：使用带过程间分析的静态类型系统来推断类型。

   Python 静态类型系统（第 10 页）：

   • 大多是标准类型，外加联合类型和字典类型。
   • 包括：
     • 基本类型：int, str, float, bool。
     • 元组：(int, float), (A, B, C)。
     • 列表：[int], [bool], [(int, bool)]。
     • 字典：{int => str}, {A => B}。
     • 类：ClassA, ClassB。

     • 联合类型：{int

       str}, {A

       B

       C}。

     • 递归类型：#1(int, +), #2(int -> 2)。
     • 函数：int -> bool, A -> B。
2. 控制流图（CFG）问题（第 11-13 页）：
   • 对于高阶程序（例如，作为参数传递的函数，如 def g(f, x): return f(x)），CFG 很难构建。
   • 引用了以前关于 CPS（Continuation-Passing Style）和 CFG 构建复杂性的研究（Shivers 1988/1991, Might & Shivers 2006/2007, Vardoulakis & Shivers 2010/2011）。
   • 解决方案：完全避免 CPS 和 CFG；使用直接风格的递归抽象解释器。
3. 动态字段创建/删除问题（第 14-21 页）：
   • 示例：class A: x = 1; obj = A(); obj.y = 3; print obj.x, obj.y。
   • 解决方案：在构造函数调用时创建“抽象对象”，并在添加/删除字段时修改它们。类不受影响。
4. 更强大的动态功能问题（第 22-23 页）：
   • 包括对 __dict__ 的操作（例如，setattr, delattr），动态重新父化，导入Hack，eval 等。
   • 解决方案：强制执行“Python 风格指南”以限制此类功能。

第 4 页和第 24-28 页似乎是空白或过渡页。

主解释器的实际代码（第 29-33 页）

• 提供了类型推断器（infer 函数）的 Python 代码片段。
• 处理模块、名称、lambda、调用等。
• 使用环境（env）和堆栈（stk）进行递归检测。
• 查找类型、记录信息/错误、创建闭包和调用函数。

第 34-39 页似乎是空白或过渡页。

递归检测（第 40-54 页）

• 使用阶乘示例（def fact(n): ...）进行说明。
• 假设：相同调用站点和相同参数类型产生相同输出类型（或不终止）。
• 通过检查 <call site, arg type> 对是否已存在于堆栈上来检测循环。
• 在检测到循环时返回“未知类型”，然后与已知类型统一（可能导致假阴性）。
• 最终推断出 fact :: int -> int 等类型。

递归检测的正确性（第 55-58 页）

• 将程序视为动态电路。
• 调用站点是具有确定性未来的“合取点”。
• 如果路径上重复出现 <call site, arg type>，则为循环。

相关工作（第 59 页）

• 类似于控制流分析（CFAs），但更简单（没有显式 CFG 或堆栈管理）。
• “CFG”是隐式和动态的。
• 不注释 AST；利用宿主语言递归。
• 比 Google 的 JSCompiler（需要注释）更简单。
• 类似于近乎具体解释（NCI），但递归检测不同。

与更深层理论的联系（第 60 页）

• 本质上是一种简单的超级编译。
• 类似于 ACL2 定理证明器技术。
• 仅跟踪类型信息；高效终止（没有同胚嵌入），但可能不那么准确（假阴性）。

局限性（第 61 页）

• 需要所有源代码（不处理字节码；内置函数被模拟）。
• 不对数字进行值/范围跟踪。
• 忽略堆副作用对类型的影响。
• 递归中可能存在假阴性。
• 最坏情况复杂度高（近似可以提供帮助，但会降低准确性）。
• 对深层错误的错误报告不友好。

适用性（第 62 页）

• 通用的类型推断/静态分析方法。
• 适用于任何语言，但对动态语言最有用（静态语言通过注释更容易/模块化）。
• 涉及权衡。

可用性（第 63 页）

• 2009 年：“Jython Indexer”（Java，开源；模块化统一，如 HM；快速但有限；在 Google 使用；贡献给 Jython）。
• 2010 年：“PySonar”（Java，非开源；过程间；解析大多数名称；检测深层错误；速度慢）。
• 2011 年：“mini-pysonar”（Python，GitHub 上开源；仅包含核心部分）。

可能的未来工作（第 64 页）

• 应用于其他（更简单）的语言。
• 发表关于该方法的论文。
• 衍生相关想法。

第 65 页似乎是空白。

幻灯片包括代码示例、图表（例如，问题旁的气泡）以及对学术论文的引用。有一个“演示时间”幻灯片（第 4 页），可能用于现场演示。总的来说，它通过类型推断、抽象解释和递归处理来解决动态类型挑战，从而提出了使 Python 的静态分析变得可行的实用方法。

---

Back

x-ai/grok-4.1-fast

Donate