PPL知识点图：

principle of programming language

Intro

Imperative

Functional

Logic

History

  • Lexical analysis: converts characters in the source program into lexical unit

  • Syntax analysis: transforms lexical units into parse trees which represent syntactic structure of program

  • Semantics analysis: generate intermediate code

  • Code generation: machine code is generated

  • Link and load

Most important criteria for evaluating programming languages include:
Readability, writability, reliability, cost
Major influences on language design have been application domains, machine architecture and software development methodologies
The major methods of implementing programming languages are: compilation, pure interpretation, and hybrid implementation

Syntax

Syntax: 语法 the form or structure of the expressions, statements, and program units

Semantics: 语义 the meaning of the expressions, statements, and program units

​ What programs do, their behavior and meaning

Subprogram

In-Out Mode

JVM

JAVA 的 JVM 的内存可分为 3 个区：堆 (heap)、栈 (stack) 和 方法区 (method)
堆区:

  1. 存储的全部是对象，每个对象都包含一个与之对应的 class 的信息。(class 的目的是得到操作指令)

  2. jvm 只有一个堆区 (heap) 被所有线程共享，堆中不存放基本类型和对象引用，只存放对象本身

栈区:

  1. 每个线程包含一个栈区，栈中只保存基础数据类型的对象和自定义对象的引用 (不是对象)，对象都存放在堆区中

  2. 每个栈中的数据 (原始类型和对象引用) 都是私有的，其他栈不能访问。

  3. 栈分为 3 个部分：基本类型变量区、执行环境上下文、操作指令区 (存放操作指令)。

方法区:

  1. 又叫静态区，跟堆一样，被所有的线程共享。方法区包含所有的 class 和 static 变量。
  2. 方法区中包含的都是在整个程序中永远唯一的元素，如 class，static 变量。

Parallelism

  • 并发：一个程序的多个任务同时执行
  • 并行：一个任务分解为多个子任务同时执行，协作完成一个问题
  • 分布式：并行的计算在不同的计算机上进行

加速比：在p个核上的程序的加速比S=T串行/T并行

Amdahl’s Law

  • speedup <= work/span

  • q = fraction of sequential work

  • speedup <= 1/q

结构并行

  • Folk/Join 框架
1
2
3
4
5
6
7
if (任务足够小){
  直接执行该任务;
}
else{
  将任务一分为二;
  执行这两个任务并等待结果;
}

函数并行

  • Future
  • Memorization

循环并行

  • Forall 框架
  • 栅栏问题

Recursion

线性递归和迭代

  • 牛顿逼近平方根
1
2
3
4
5
6
7
8
9
def sqrt(x):
  threshold = 0.0001
  return sqrt_iter(1.0, x, threshold)

def sqrt_iter(guess, x, threshold):
  if abs(guess*guess -x) < threshold:
    return guess
  else:
    return sqrt_iter((guess + x/guess)/2, x, threshold)
  • 阶乘