编译原理实战课
##############

.. raw:: html

   <details>
   <summary>目录</summary>

.. sidebar:: 目录

    .. contents::

.. raw:: html

   </details>


语法分析
========

两个基本功::

    1. 必须能够阅读和书写语法规则，也就是掌握「上下文无关文法」
        Context-Free Grammar
    2. 必须要掌握「递归下降算法」


两种算法思路::

    1. 一种是自顶向下的语法分析
    2. 一种是自底向上的语法分析

上下文无关文法
--------------

如何表达语法规则-示例::

    int a = 2;
    int b = a + 3;
    return b;


1. 扩展巴科斯范式（EBNF）::

    start：blockStmts ;               // 起始
    block : '{' blockStmts '}' ;      // 语句块
    blockStmts : stmt* ;              // 语句块中的语句
    stmt = varDecl | expStmt | returnStmt | block;   // 语句
    varDecl : type Id varInitializer？ ';' ;         // 变量声明
    type : Int | Long ;                              // 类型
    varInitializer : '=' exp ;                       // 变量初始化
    expStmt : exp ';' ;                              // 表达式语句
    returnStmt : Return exp ';' ;                    //return 语句
    exp : add ;                                      // 表达式       
    add : add '+' mul | mul;                         // 加法表达式
    mul : mul '*' pri | pri;                         // 乘法表达式
    pri : IntLiteral | Id | '(' exp ')' ;            // 基础表达式

    说明:
      冒号左边的叫做非终结符（Non-terminal），又叫变元（Variable）
      非终结符可以按照右边的正则表达式来逐步展开，
      直到最后都变成标识符、字面量、运算符这些不可再展开的符号，也就是终结符（Terminal）。
      终结符其实也是词法分析过程中形成的 Token。
    约定:
      非终结符以小写字母开头，终结符则以大写字母开头，或者是一个原始的字符串格式

2. 产生式（Production Rule），又叫做替换规则（Substitution Rule）::

    add -> add + mul
    add -> mul
    mul -> mul * pri
    mul -> pri

    标准写法: 不用能竖线、*号 等
    偷懒写法: 用竖线拼接一个变元的多个产生式

    说明:
      产生式的左边是非终结符（变元），它可以用右边的部分替代，中间通常会用箭头连接。
      产生式不用 “*” 和 “+” 来表示重复，而是用迭代，并引入 “ε”（空字符串）。
      所以 “blockStmts : stmt*” 可以写成下面这个样子:
        blockStmts -> stmt blockStmts | ε

    例:
      a[a-zA-Z0-9]*bc
    产生式:
      S0 -> aS1bc          
      S1 -> [a-zA-Z0-9]S1  
      S1 -> ε


上下文无关文法四个特点::

    1. 一个有穷的非终结符（或变元）的集合
    2. 一个有穷的终结符的集合
    3. 一个有穷的产生式集合
    4. 一个起始非终结符（变元）


.. note:: 学习编译原理，阅读和书写语法规则是一项基本功。针对高级语言中的各种语句，你要都能够手写出它们的语法规则来才可以。


递归下降算法
------------

示例-变量声明语句的规则::

    int a = 2;
    int b = a + 3;

方式1-EBNF::

    varDecl : types Id varInitializer？ ';' ;        // 变量声明
    varInitializer : '=' exp ;                       // 变量初始化
    exp : add ;                                      // 表达式       
    add : add '+' mul | mul;                         // 加法表达式
    mul : mul '*' pri | pri;                         // 乘法表达式
    pri : IntLiteral | Id | '(' exp ')' ;            // 基础表达式

方式2-产生式::

    varDecl -> types Id varInitializer ';' 
    varInitializer -> '=' exp              
    varInitializer -> ε
    exp -> add
    add -> add + mul
    add -> mul
    mul -> mul * pri
    mul -> pri
    pri -> IntLiteral
    pri -> Id
    pri -> ( exp )

基于这个规则做解析的算法如下::

    匹配一个数据类型(types)
    匹配一个标识符(Id)，作为变量名称
    匹配初始化部分(varInitializer)，而这会导致下降一层，使用一个新的语法规则：
       匹配一个等号
       匹配一个表达式(在这个步骤会导致多层下降：exp->add->mul->pri->IntLiteral)
       创建一个varInitializer对应的AST节点并返回
    如果没有成功地匹配初始化部分，则回溯，匹配ε，也就是没有初始化部分。
    匹配一个分号   
    创建一个varDecl对应的AST节点并返回

递归下降算法的特点是::

    1. 对于一个非终结符，要从左到右依次匹配其产生式中的每个项，包括非终结符和终结符
    2. 在匹配产生式右边的非终结符时，要下降一层，继续匹配该非终结符的产生式
    3. 如果一个语法规则有多个可选的产生式，那么只要有一个产生式匹配成功就行
        如果一个产生式匹配不成功，那就回退回来，尝试另一个产生式。
        这种回退过程，叫做回溯（Backtracking）

递归下降算法两个缺点::

    1. 第一个缺点，就是著名的左递归（Left Recursion）问题
      解决1: 引入add'，把左递归变成右递归:
        add -> mul add'
        add' -> + mul add' | ε
      解决2: 把递归调用转化成循环
    2. 第二个缺点，当产生式匹配失败的时候，必须要“回溯”，这就可能导致浪费
      解决: 预读后续的一个 Token，判断该选择哪个产生式
      对应算法: LL 算法家族


LL 算法
-------

.. note:: 计算 First 和 Follow 集合。

* First 集合: 每个产生式开头可能会出现的 Token 的集合
* Follow 集合: 对于某个非终结符后面可能跟着的 Token 的集合

LL(1) 中的::

    第一个 L，是 Left-to-right
    第二个 L，是 Leftmost 的缩写，意思是最左推导

LR 算法
-------

其中的关键之处在于如何“拼凑”。

与 LL 算法对比::

    优点: 不怕左递归
    缺点: 缺少完整的上下文信息，编译错误信息不友好

语义分析
========

语义规则可以分为两大类::

    1. 第一类规则与上下文有关。
    2. 第二类规则与类型有关。

在语义分析过程中，会使用两个数据结构::

    1. 一个是 AST，把语义分析时获得的一些信息标注在 AST 上，形成带有标注的 AST
    2. 另一个是符号表，用来记录程序中声明的各种标识符，并用于后续各个编译阶段

上下文相关的分析
----------------

场景 1：控制流检查::

    return、break 和 continue 等语句

场景 2：闭包分析::

    要正确地使用闭包，就必须在编译期知道哪些变量是自由变量。
    这里的自由变量是指在本函数外面定义的变量，但被这个函数中的代码所使用
    
    在运行期，编译器就会用特殊的内存管理机制来管理这些变量。
    所以，对闭包的分析，也是上下文敏感的。

场景 3：引用消解::

    引用消解是一种非常重要的上下文相关的语义规则

    作用域:
      第一个使用场景，指的是变量、函数等标识符可以起作用的范围
      第二个使用场景，是词法作用域（Lexical Scope）


符号表::

    对于变量 a 来说，符号表中的基本信息可以包括:
    1. 名称：a
    2. 分类：变量
    3. 类型：int
    4. 作用域：foo 函数体
    5. 其他必要的信息

类型分析和处理
--------------

.. note:: 【定义】在计算机语言里，类型是数据的一个属性，它的作用是来告诉编译器或解释器，程序可以如何使用这些数据。

属性计算::

    关于类型检查，编译器一般会采用属性计算的方法，
      来计算出每个 AST 节点的类型属性，然后检查它们是否匹配。

    1. 有些属性是通过子节点计算出来的，这叫做 S 属性
      （Synthesized Attribute，综合出来的属性）
        比如等号右边的类型。
    2. 有些属性是根据父节点或者兄弟节点计算而来，这种属性叫做 I 属性
      （Inherited Attribute，继承到的属性）
        比如等号左边的 b 变量的类型。

.. figure:: https://img.zhaoweiguo.com/knowledge/images/cores/compilers/annotated_ast1.jpeg

   带有标注信息的 AST


运行时机制
==========

.. figure:: https://img.zhaoweiguo.com/knowledge/images/cores/compilers/memory_layout1.jpeg

   C 语言的内存布局方式

.. note:: [定义]除了硬件支撑，程序的运行还需要软件，这些软件叫做运行时系统（Runtime System），或者叫运行时（Runtime）。如：垃圾收集器，就是一个运行时的软件。进行并发调度的软件，也是运行时的组成部分。

虚拟机有两种模型::

    1. 一种叫做栈机（Stack Machine）
    2. 一种叫做寄存器机（Register Machine）

    区别，主要在于如何获取指令的操作数
    栈机是从栈里获取，而寄存器机是从寄存器里获取。这两种虚拟机各有优缺点。


中间代码 IR
===========

基于抽象层次，IR 可以归结为::

    1. HIR(基于源语言做一些分析和变换)
    2. MIR(独立于源语言和 CPU 架构做分析和优化)
    3. LIR(依赖于 CPU 架构做优化和代码生成)

HIR::

    最主要的功能包括:
      1. 发现语法错误
      2. 分析符号之间的依赖关系（以便进行跳转、判断方法的重载等）
      3. 根据需要自动生成或修改一些代码（提供重构能力）

    AST 也可以算作一种 IR:
      1. 开发 IDE
      2. 代码翻译工具（从一门语言翻译到另一门语言）
      3. 代码生成工具
      4. 代码统计工具
    HIR，还可以做一些高层次的代码优化，比如:
      5. 常数折叠
      6. 内联

    有些 HIR 并不是树状结构（比如可以采用线性结构）:
      但一般会保留诸如条件判断、循环、数组等抽象层次比较高的语法结构

MIR::

    大量的优化算法是可以通用的，没有必要依赖源语言的语法和语义，也没有必要依赖具体的 CPU 架构。
    这些优化包括:
      1. 部分算术优化
      2. 常量和变量传播
      3. 死代码删除等

    示例:
      int foo (int a){
        int b = 0;
        if (a > 10)
          b = a;
        else
          b = 10;
        return b;
      }
    对应的 TAC:
      BB1:
        b := 0
        if a>10 goto BB3   //如果t是false(0),转到BB3
      BB2:
        b := 10
        goto BB4
      BB3:
        b := a
      BB4:
        return b

    说明:
      TAC 用 goto 语句取代了 if 语句、循环语句这种比较高级的语句
        当然也不会有类、继承这些高层的语言结构。
      但是，它又没有涉及数据如何在内存读写等细节，书写格式也不像汇编代码，
        与具体的目标代码也是独立的。

LIR::

    Java 的 JIT 编译器输出的 LIR 信息，里面的指令名称已经跟汇编代码很像了，
      并且会直接使用 AMD64 架构的寄存器名称


.. figure:: https://img.zhaoweiguo.com/knowledge/images/cores/compilers/JIT_LIR1.jpeg

   Java 的 JIT 编译器的 LIR

IR 的数据结构::

    1. 线性结构
        类似 TAC 的线性结构（Linear Form）
        可以把代码表示成一行行的指令或语句，用数组或者列表保存就行了。
        其中的符号，需要引用符号表，来提供类型等信息。
        这种线性结构有时候也被称作 goto 格式
    2. 树结构
        AST 就是一种树结构
        缺点: 可能有冗余的子树
    3. 有向无环图（DAG）
        在树结构的基础上，消除了冗余的子树
    4. 程序依赖图（PDG）
        显式地把程序中的数据依赖和控制依赖表示出来，形成一个图状的数据结构
        基于这个数据结构，我们再做一些优化算法的时候，会更容易实现
    说明: 编译器会根据需要，选择合适的数据结构


IR 设计范式-SSA 格式::

    SSA: Static Single Assignment
    使用SSA的原因: 使用 SSA 的形式，体现了精确的“使用 - 定义（use-def）”关系。
      并且由于变量的值定义出来以后就不再变化，使得基于 SSA 更容易运行一些优化算法。

    示例: y = x1 + x2 + x3 + x4
    普通 TAC:
      y := x1 + x2;
      y := y + x3;
      y := y + x4;
      说明: y 被赋值了三次
    SSA 的形式:
      t1 := x1 + x2;
      t2 := t1 + x3;
      y  := t2 + x4; 

代码优化
========

常见的代码优化方法::

    1. 机器无关的优化
        如把常数值在编译期计算出来（常数折叠）
    2. 机器相关的优化
        利用某硬件特有的特征，比如 SIMD 指令可以在一条指令里完成多个数据的计算
    3. 优化的范围
        局部优化: 基本块内
        全局优化: 针对整个函数（或过程）
        过程间优化: 跨越多个函数（或过程）做优化

思路 1：把常量提前计算出来::

    常数折叠（Constant Folding）
    常数传播（Constant Propagation）
      稀疏有条件的常数传播（Sparse Conditional Constant Propagation）

思路 2：用低代价的方法做计算::

    代数简化（Algebra Simplification）
    强度折减（Strength Reduction）

思路 3：消除重复的计算::

    拷贝传播（Copy Propagation）
    值编号（Value Numbering）
    公共子表达式消除（Common Subexpression Elimination，CSE）
    部分冗余消除（Partial Redundancy Elimination，PRE）

思路 4：化零为整，向量计算::

     SIMD（Single Instruction Multiple Data）指令
     超字级并行（Superword-Level Parallelism，SLP)
     循环向量化（Loop Vectorization）

思路 5：化整为零，各个优化::

    聚合体的标量替换（Scalar Replacement of Aggregates，SROA）

思路 6：针对循环，重点优化::

    在编译器中，对循环的优化从来都是重点，因为程序中最多的计算量都是被各种循环消耗掉的
    方法:
      1. 归纳变量优化（Induction Variable Optimization）
      2. 边界检查消除（Unnecessary Bounds-checking Elimination）
      3. 循环展开（Loop Unrolling）
      4. 循环向量化（Loop Vectorization）
      5. 重组（Reassociation）
      6. 循环不变代码外提（Loop-Invariant Code Motion，LICM）
      7. 代码提升（Code Hoisting，或 Expression Hoisting）

思路 7：减少过程调用的开销::

    当程序调用一个函数的时候，开销是很大的，比如:
      保存原来的栈指针、保存某些寄存器的值、保存返回地址、设置参数，等等

    1. 尾调用优化（Tail-call Optimization）和尾递归优化（Tail-recursion Elimination）
    2. 内联（inlining）
    3. 内联扩展（In-Line Expansion）
    4. 叶子程序优化（Leaf-Routine Optimization）

思路 8：对控制流做优化::

    1. 不可达代码消除（Unreacheable-code Elimination）
    2. 死代码删除（Dead-code Elimination）
    3. If 简化（If Simplification)
    4. 循环简化（Loop Simplification）
    5. 循环反转（Loop Inversion）
    6. 拉直（Straightening）
    7. 反分支（Unswitching）

有些优化，就需要比较复杂的分析方法做支撑才能完成。这些分析方法包括::

    1. 控制流分析
        帮助我们建立对程序执行过程的理解，比如:
          哪里是程序入口，哪里是出口，
          哪些语句构成了一个基本块，基本块之间跳转关系，
          哪个结构是一个循环结构（从而去做循环优化）
    2. 数据流分析
        帮助我们理解程序中的数据变化情况
    3. 依赖分析
        分析出程序代码的控制依赖（Control Dependency）和数据依赖（Data Dependency）关系。
        这对指令排序和缓存优化很重要。
    4. 别名分析

代码生成
========

寄存器分配的算法::

    1. 寄存器染色算法
        计算结果比较优化，但缺点是计算量比较大
    2. 线性扫描算法
        计算速度快，但缺点是有可能不够优化，适合需要编译速度比较快的场景，比如即时编译

::

    public enum CompileState {
        INIT(0),          // 初始化
        PARSE(1),         // 词法和语法分析 
        ENTER(2),         // 建立符号表
        PROCESS(3),       // 处理注解
        ATTR(4),          // 属性计算
        FLOW(5),          // 数据流分析
        TRANSTYPES(6),    // 去除语法糖：泛型处理
        TRANSPATTERNS(7), // 去除语法糖：模式匹配处理
        UNLAMBDA(8),      // 去除语法糖：LAMBDA 处理 (转换成方法)
        LOWER(9),         // 去除语法糖：内部类、foreach 循环、断言等。
        GENERATE(10);     // 生成字节码
        ...
    }

数据流分析框架的 5 个要素(以活跃性分析为例)::

    1. V: 代表被分析的值，这里是 alive，代表了控制流是否会到达这里。
    2. I: 是 V 的初始值，这里的初始值是 LIVE；
    3. D: 指分析方向。这个例子里，是从上到下扫描基本块中的代码；而有些分析是从下往上的。
    4. F: 指转换函数，也就是遇到每个语句的时候，V 如何变化。
        这里是在遇到 return 语句的时候，把 alive 变为 DEAD。
    5. Λ: meet 运算，也就是当控制流相交的时候，从多个值中计算出一个值。

数据流分析包括::
    
    1. 活跃性分析
    2. 异常分析
    3. 赋值分析
    4. 本地变量捕获分析


解析树和 AST 的区别
===================

.. note:: 解析树又可以叫做 CST（Concrete Syntax Tree，具体语法树），与 AST（抽象语法树）是相对的：一个具体，一个抽象。它俩的区别在于：CST 精确地反映了语法规则的推导过程，而 AST 则更准确地表达了程序的结构。



.. figure:: https://img.zhaoweiguo.com/knowledge/images/cores/compilers/CST1.jpeg

   CST 的特点

.. figure:: https://img.zhaoweiguo.com/knowledge/images/cores/compilers/AST1.jpeg

   对应的 AST

Golang
======

词法分析&语法分析::

    cmd/compile/internal/syntax:
      词法分析器是 scanner.go
      语法分析器是 parser.go

语义分析::

    cmd/compile/internal/gc:
      typecheck.go    // 主要程序，处理: 类型检查，名称消解（Name Resolution）和类型推导

SSA::

    cmd/compile/internal/ssa:
      1. 值（Value）:
          Value 是 SSA 的最主要构造单元，它可以定义一次、使用多次
          在定义一个 Value 的时候，需要:
              一个标识符（ID）作为名称、
              产生该 Value 的操作码（Op）、
              一个类型（Type，就是代码中 <> 里面的值），
              以及一些参数
          a. 操作码有两类:
            一类是机器无关的，其定义在 gen/genericOps.go
            一类是机器相关的，它是面向特定的 CPU 架构的，其定义在 gen/XXXOps.go 中。
              比如，AMD64Ops.go 中是针对 AMD64 架构 CPU 的操作码信息。
          b. 类型信息
            通常就是 Go 语言中的类型。
            但有几个类型是只会在 SSA 中用到的特殊类型:
              内存 (TypeMem) 类型: 代表的是全局的内存状态。
                如果一个操作码带有一个内存类型的参数，那就意味着该操作码依赖该内存状态。
                如果一个操作码的类型是内存类型，则意味着它会影响内存状态。
              TypeFlags类型，也就是 CPU 的标志位类型。
      2. 基本块（Block）
          Go 编译器中的基本块有三种:
          a. 简单（Plain）基本块，它只有一个后继基本块；
          b. 退出（Exit）基本块，它的最后一个指令是一个返回指令；
          c. 还有 if 基本块，它有一个控制值，并且它会根据该值是 true 还是 false，跳转到不同的基本块。
      3. 函数（Func）
          函数是由多个基本块构成的。
          它必须有一个入口基本块（Entry Block），但可以有 0 到多个退出基本块，就像一个 Go 函数允许包含多个 Return 语句一样。

    Go 的 IR 在运行时就是保存在 Value、Block、Func 等内存结构中，就像 AST 一样


优化::

    Pass: cmd/compile/internal/ssa/compile.go
      寄存器分配（regalloc.go）

cmd/compile/internal/ssa 目录::

    1. cse.go 里面是消除公共子表达式的算法
    2. nilcheck.go 是被用来消除冗余的 nil 检查代码


* Go 语言的另外两个编译器，gccgo 和 GoLLVM

* https://go.dev/ref/spec
* 官方文档，介绍了 gc 的主要结构: https://github.com/golang/go/blob/release-branch.go1.14/src/cmd/compile/README.md
* 官方文档，介绍了 gc 的 SSA: https://github.com/golang/go/blob/release-branch.go1.14/src/cmd/compile/internal/ssa/README.md
* 在这两篇博客里，作者做了一个实验：如果往 Go 里面增加一条新的语法规则，需要做哪些事情。你能贯穿性地了解一个编译器的方法: 
    * https://eli.thegreenplace.net/2019/go-compiler-internals-adding-a-new-statement-to-go-part-1/
    * https://eli.thegreenplace.net/2019/go-compiler-internals-adding-a-new-statement-to-go-part-2/

* gc 编译器采用的汇编语言是它自己的一种格式，是 “伪汇编”。这两篇文章中有 Go 汇编的细节

  - https://github.com/teh-cmc/go-internals/blob/master/chapter1_assembly_primer/README.md
  - https://go.dev/doc/asm

* https://studygolang.com/topics/491

Erlang
======

Actor 模式 VS OOP::

    面向对象语言之父阿伦・凯伊（Alan Kay），Smalltalk 的发明人，在谈到面向对象时是这样说的:
      对象应该像生物的细胞，或者是网络上的计算机，它们只能通过消息互相通讯。
      对我来说 OOP 仅仅意味着消息传递、本地保留和保护以及隐藏状态过程，并且尽量推迟万物之间的绑定关系。

      I thought of objects being like biological cells and/or individual computers on a network, only able to communicate with messages (so messaging came at the very beginning – it took a while to see how to do messaging in a programming language efficiently enough to be useful)
      …
      OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things. It can be done in Smalltalk and in LISP.

      Alan 对面向对象的理解，强调消息传递、封装和动态绑定，没有谈多态、继承等。
      对照这个理解，你会发现 Actor 模式比现有的流行的面向对象编程语言，更加接近面向对象的实现。


采用 Actor 模式，会有两方面的问题::

    1. 由于 Actor 之间不共享任何数据，因此不仅增加了数据复制的时间，还增加了内存占用量
      这也不完全是缺点:
        a. 通过在编写程序时，尽量降低消息对象的大小，从而减少数据复制导致的开销
        b. 另一方面，消息传递的方式对于本机的 Actor 和集群中的 Actor 是一样的
          这就使得编写分布式的云端应用更简单，从而在云计算时代可以获得更好的应用
    2. 基于消息的并发机制，基本上是采用异步的编程模式，这就和通常程序的编程风格有很大的不同

Actor 模式
----------

Erlang有两个显著的优点::

    1. 首先，对并发的支持非常好，所以它也被叫做面向并发的编程语言（COP）
    2. 第二，用 Erlang 可以编写高可靠性的软件，可以达到 9 个 9

这两个优点都与 Actor 模式有关::

    1. Erlang 的软件由很多 Actor 构成
    2. 这些 Actor 可以分布在多台机器上，相互之间的通讯跟在同一台机器上没有区别
    3. 某个 Actor 甚至机器出现故障，都不影响整体系统，可以在其他机器上重新启动该 Actor
    4. Actor 的代码可以在运行时更新


并发调度机制
------------

1. 什么时候调度比较好::

    一个可选的调度时机，就是让 Actor 每处理完一条消息，就暂停一下，让别的 Actor 有机会运行。
    如果处理一条消息所花费的时间太短，比如有的消息是可以被忽略的，
      那么处理多条消息，累积到一定时间再去调度也行。

2. 能否实现抢占式的调度呢::

    对 Reduction 做计数

3. I/O 与调度的关系::

    在 Erlang 的最底层，所有的 I/O 都是用事件驱动的方式来实现的。
    系统收到了一块数据，就调用应用来处理，整个过程都是非阻塞的



内存管理机制
------------

.. figure:: https://img.zhaoweiguo.com/knowledge/images/cores/compilers/erlang1.jpeg

   Erlang 的内存模型

.. note:: Erlang 的堆与其他语言有很大的区别，它的每个 Actor 都有自己的堆空间，而不是像其他编程模型那样，不同的线程共享堆空间。

由于每个 Actor 都有自己的堆，因此会给垃圾收集带来很大的便利::

    1. 因为整个程序划分成了很多个 Actor，每个 Actor 都有自己的堆
        所以每个 Actor 的垃圾都比较少，不用一次回收整个应用的垃圾，所以回收速度会很快。
    2. 由于没有共享内存，所以垃圾收集器不需要停下整个应用，而只需要停下被收集的 Actor。
        这就避免了 “停下整个世界（STW）” 问题，而这个问题是 Java、Go 等语言面临的重大技术挑战。
    3. 如果一个 Actor 的生命周期结束，那么它占用的内存会被马上释放掉。
        这意味着，对于有些生命周期比较短的 Actor 来说，可能压根儿都不需要做垃圾收集。


并发
====

.. figure:: https://img.zhaoweiguo.com/knowledge/images/cores/compilers/thread1.jpeg

   进程的共享资源和线程私有的资源


* Python 的 Async io 和协程的关系: https://realpython.com/async-io-python/



元编程-Meta-Programming
=======================

.. note:: 元编程是一种把程序当做数据来处理的技术。因此，采用元编程技术，你可以把一个程序变换成另一个程序。

.. note:: 元编程的基本特征：把程序当做数据去处理。在计算机语言里说的元编程技术，通常是指用这门语言本身提供的功能，就能处理它自己的程序。


.. figure:: https://img.zhaoweiguo.com/knowledge/images/cores/compilers/meta1.webp

   元编程处理的对象是程序

广义元编程::

    1. 编译器
    2. 静态分析工具
    3. 动态分析工具

.. figure:: https://img.zhaoweiguo.com/knowledge/images/cores/compilers/meta2.webp

   各种不同的元编程技术起作用的时机


Meta 的含义
-----------

Meta 来自希腊文，意思是 “在…… 之后（after）” 和 “超越……（beyond）”。加上这个词缀后，Meta-Somthing 所形成的新概念就会比原来的 Somthing 的概念的抽象度上升一层。

例::

    Physics   => Metaphysics
    Data      => Metadata
    Language  => Metalanguage


Meta 的层次
-----------

关系数据库::

    M0: 数据
    M1: 表结构
    M2: 关系模型
    M3: MOF

程序::

    M0: 程序中的对象
    M1: 程序中的类
    M2: 计算机语言，包括: 词法规则、语法规则、语义规则
    M3: 产生式、EBNF




元编程技术的分类
----------------

根据处理对象的不同::

    1. 语义层对象，如: 类
    2. AST
    3. 程序的文本
    4. 字节码

元编程技术起作用的时机::

    1. 静态元编程技术只在编译期起作用
        C++ 的模板技术
        Java 注解技术
        一旦编译完毕以后，元程序跟普通程序一样，都会变成机器码
    2. 动态元编程技术会在运行期起作用
        Java 的反射机制
        Java 程序能在运行期进行类型判断，也是基于同样的原理

不同语言的元编程技术
--------------------

1. Java 的元编程技术::

    注解:
        注解处理过程自始至终都借助了编译器提供的能力：
          先是通过编译器查询被注解的程序的元数据，
          然后生成的新程序也会被编译器编译掉。
        所以你能得出一个结论：所谓元编程，某种意义上就是由程序来调用编译器提供的能力。
    反射机制:
        短板: 性能比较低。
        基于反射机制编写的程序的效率，比同样功能的静态编译的程序要低好几倍。
        所以，如何提升运行期元编程功能的性能，是编译技术研究的一个重点。

2. Python、JavaScript 等脚本语言的元编程技术::

    a. 程序文本生成和 eval
        就是动态生成程序的文本字符串，然后动态编译并执行。
        这种方式虽然简单粗暴，容易出错，有安全隐患，但在某些特殊场景下还确实很有用。
    b. 动态获取程序信息、动态修改程序
      特点:
      1. 就是用程序可以很方便地获取对象的元数据，比如某个对象有什么属性、什么方法
      2. 就是可以很容易地为对象添加属性和方法，从而修改对象


3. 类 Lisp 语言的元编程技术::

    本来就是一个嵌套的树状结构，其实跟 AST 没啥区别
    这种能够直接操纵 AST 的能力让 Lisp 特别灵活

4. C++ 的元编程技术::

    C++ 的模板元编程（Template Metaprogramming）技术


泛型
====

具体实现机制上，有::

    1. 类型擦除
    2. 具体化
    3. 模板元编程

  
函数式编程
==========

计算模型其实不仅仅可以用图灵机来表达。早在图灵机出现之前，阿隆佐・邱奇（Alonzo Church）就提出了一套 Lambda 演算的模型。并且，计算机科学领域中的很多人，其实都认为用 Lambda 演算来分析可计算性、计算复杂性，以及用来编程，会比采用图灵机模型更加简洁。而 Lambda 演算，就是函数式编程的数学基础。

.. note:: 实际上，邱奇是图灵的导师。当年图灵发表他的论文的时候，编辑看不懂，所以找邱奇帮忙，并推荐图灵成为他的学生，图灵机这个词也是邱奇起的。所以师生二人，对计算机科学的发展都做出了很大的贡献。

函数式编程的几个特点::

    1. 函数作为一等公民
        函数可以像一个数值一样，被赋给变量，也可以作为函数参数。
        如果一个函数能够接受其他函数作为参数，或者能够把一个函数作为返回值，那么它就是高阶函数。
    2. 纯函数（Pure Function）
        在函数式编程里面，有一个概念叫做纯函数。
        纯函数是这样一种函数，即相同的输入，永远会得到相同的输出。
        对于纯函数来说，它不依赖外部的变量，这个叫做引用透明（Reference Transparency）。
        纯函数的这种 “靠谱”、可预测的特征，就给我们的编程工作带来了很多的好处。
          可以延迟求值（Lazy Evaluation）。
          纯函数没有副作用（Side Effect）。
    3. 不变性（Immutability）
        程序会根据需要来创建对象并使用它们，但不会去修改对象的状态。
        如果有需要修改对象状态的情况，那么去创建一个新对象就好了。
        好处:
          由于函数不会修改对象的状态，所以就不存在并发程序中的竞争情况，进而也就不需要采用锁的机制。
          所以说，函数式编程更适合编写并发程序。
          这个优势，也是导致这几年函数式编程复兴的重要原因。
    4. 声明式（Declarative）的编程风格
        体现: 递归函数的大量使用

    总体思想:
      像数学那样去使用函数和值，使可变动部分最小化，让软件的结构变得简单、可预测，
        从而获得支持并发、更简洁的表达等优势


.. note:: 在函数式编程中，会希望函数像数学中的函数那样纯粹，即不依赖外部（引用透明），也不改变外部（无副作用），从而带来计算时间、运行时替换等灵活性的优势。

编程风格::

    1. 命令式（Imperative）编程
    2. 声明式（Declarative）编程

远程办公
========

* 我曾经接触过一个芬兰公司的 CEO，他们主要做嵌入式 Linux 的技术服务。一百多人的公司，平常办公室是没什么人的。据说他们公司有的员工，可以一边上班，一边去全世界旅游。
* WordPress 的母公司 Automattic 有上千名员工，分布在全球 75 个国家，全部都是远程办公。

好处::

    1. 员工可能会在工作上做更多的投入
    2. 没有了地域限制，公司也就可以充分任用全球各地的人才
    3. 没有了地域的限制，公司也可能更容易拓展自己的市场

挑战::

    公司的角度:
    1. 对于管理体系，有着更高的要求
      很多工作是难以直接度量绩效的，比如说研发工作就比销售工作更难衡量绩效。
    2. 如何能保证采用远程办公模式，不会让企业变成一团散沙，纪律涣散、效率低下

    员工的角度:
    1. 自我管理能力
      管理自己这件事情，也是消耗注意力的
      例: 直播编码。为了帮助管理自己的行为，因为这时候你必须更加集中注意力在自己的工作上
    2. 办公环境的因素
    3. 心理上的挑战
      白天晚上都在家里，会容易心理疲劳
    4. 降低沟通的效率

准备::

    从公司的角度出发:
    1. 企业管理者要建立一个意识：远程办公是企业必须要面对的管理考验
    2. 从看住人，转换到管绩效
    3. 建立拥抱远程办公的文化，给员工授权和赋能 
      知识密集型的，对员工的绩效评估比较难，人员更换的成本也相对较高。
      对于这类工作，可以多向那些开源软件公司学习:
      建立一个拥抱远程办公的公司文化，去吸引那些对工作充满兴趣和热爱的人
    4. 充分利用 IT 技术

    从员工的角度出发:
    1. 员工也要建立一个意识：无论是否远程办公，都要向绩效负责，管理好自己的工作
    2. 正视远程办公对自我管理的高要求，养成良好的工作习惯
    3. 建立激进的协作习惯
    4. 最重要的：为兴趣而工作，为自己而工作

如何学习
========

从心理的角度看待学习技术的过程::

    1. 学习的目的和动力问题:
        我为什么要学习这么难的技术？学一些比较容易的、应用层面的技术不就行了吗？
    2. 自信心和勇气的问题:
        以我的能力，能学会这么难的技术吗？
    3. 学习过程中的心态调节和习惯养成问题
        如何看待学习中经常遇到的挫折？总是找不到时间怎么办？等等。

* 用出世的态度，做入世的事情
* 一个缺乏美学素养、哲学素养和沟通能力等素质的软件工程师，潜力可能是有限的。
* 一个人的基础素质，决定了他的思维方式、思维质量和眼光，那些看上去没用的基础知识、基础原理，其实是真正做大事、承担重任所需要的素质
* 如果你的目标是持续进步，那要培养自己另一种习惯，就是习惯于获得那些艰难的乐趣，这种乐趣是真正的充实的乐趣
* 写技术博客: 因为你要写出东西来，所以会逼迫自己把思路理清楚
* 涌现（Emergence）:把很多个体连接起来，构成一个更高级的存在的现象(蜂群, 人类的大脑)
* 复杂系统破除了对还原论的迷信。也就是，即使你把一个系统分割成一个个的 “零件”，并且完全理解了每个 “零件”，你也可能无法理解整体系统。因为整体不等于部分的简单相加，比如说，就算你理解了一个社会的经济体中的每个企业和消费者的行为，你也无法准确掌控宏观经济。

思想或理论::

    系统论、控制论和信息论三大论
    协同学、博弈论、突变论、混沌理论、分型理论、耗散结构和复杂性理论
    复杂系统: 三体现象、蝴蝶效应、混沌系统
    复杂系统: 软件领域、天气系统、生态系统、经济系统、社会系统，甚至包括人体本身

采用复杂系统的思维做研究。比如::

    采用演化的思维做心理学的研究，就形成了进化心理学的分支
    （其实更恰当的翻译方法是演化心理学，因为演化是没有方向性的）。
    这个学科的基本逻辑，就是:
      现在人类具有的某种心理特质（比如为什么恋爱中男人更主动，女人更矜持），都是在进化中形成的。
    因为凡是没有这种心理特质的人类，都已经在进化过程中被淘汰了






收集
====

SQL 解析::

    MySQL 是用 Bison 生成 Parser 的
    MySQL Workbench 使用 Antlr 生成 Parser
    阿里的一个开源中间件 OpenCat 则使用了完全手写的 Parser，叫 Druid
    Flink 的 SQL 解析似乎是基于 Apache 的另一个项目 calsite


Schema::

    XML
    JSON
    DTD
    EBNF
    ASDL


参考
====

* https://astexplorer.net/

编辑器的 incremental parsing
----------------------------

1. Incremental Parsing: https://dl.acm.org/doi/abs/10.1145/357062.357066
2. A simple and efficient incremental LL(1) parsing https://link.springer.com/chapter/10.1007%2F3-540-60609-2_24
3. Efficient and Flexible Incremental Parsing https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.7015&rep=rep1&type=pdf