* [[http://www.csie.ntu.edu.tw/~lcwu/Courses/Spring2005/PL.htm|課程網頁]]



====== 筆記 ======


===== Chapter 1 =====
  * Domains: scientific (floating point), business (report,  decimal), AI (symbolic), system programming (efficiency), scripting, special-purpose
  * evaluation criteria: readability (most importnat), writability, reliability, cost, portability, generality, well-definess
  * architecture: Von Neumann
    * data / instruction in memory
    * CU, ALU
  * category
    * impertive (variables, assigment, statements, iteration)
    * functional (function, function, and functions)
    * logic (rule-based)
    * object-oriented (encapsulation, inheritance, dynamic type binding)
  * Compilation
    * Programs are translated into machine language
  * Pure Interpretation
    * Programs are interpreted by another program known as  an     
      interpreter
  * Hybrid Implementation Systems
    * A compromise between compilers and pure interpreters




===== Chapter 3 =====
  * syntax: structure of a language
  * semantic: meanings
  * lexeme: smallest syntactic unit
  * recognizer 是給一篇文章，要辨識是不是這個語言 / generator 是給文法，要你生一篇文章
  * grammar: _finite_ nonempty set of rules
  * sentential form: derivation 裡的每一句的都算是 (including non-terminals and terminals)
  * precedence 高的會在樹下面
  * EBNF 中 {} 是 0 or more times
  * Attribute Grammar
    * 每個 node X 都有一些 attributes A(X)
    * X -> X_1 ... X_n
    * synthesized attribute of X 是用 X_1 .. X_n 的 A() 組成的，也就是只跟 children 有關（因為他們的是你傳下去的）
    * inherited attribute of X_j 則是用 X, X_1 ... X_{j-1} 組成的，也就是只跟 parent 還有 left sibling 有關
    * predicated function used to ensure syntax and static sementics rules are obeyed
    * intrinsic attribute 是 left nodes 的 synthesized attribute（照定義，會跑出樹）
  * operational semantics
  * axiomatic semantics: proving correctness
    * rule of inference
    * (I and B) S {I} => {I} while B do S end {Q} 重點是 I 要滿足 P => I / \{I and B\} S \{I} / (I and not B)) => Q / loop termination
  * denotational semantics: based on recursion function
    * 對每個 entity 定義一個 mathematical object 然後定義把每個 entity 對應到 mathematical object 的 function
    * 跟 operational semantics 的差別是，前者用 code algo. 來定義，後者走數學來定義



===== Chapter 5 =====
  * names
    * length
    * case
    * keyword (context sensitive) / reserve words
  * variable
    * (name, addr, value, type, lifetime, scope)
  * binding, an association
    * static (before runtime and cannot change) / dynamic (at runtime or changeable)
    * lifetime 只要還在 memory 中就算，即使你摸不到也可以（在 scope 外）
    * stack-dynamic 是說那種在 stack 上長的變數，有這種才有辦法做 recursion
    * implicit heap-dynamic 是說像是 Perl/JavaScript string (or array) 那種
     * explicit heap-dynamic 執行中產生出來的變數  例如 new
  * strong typing 是說所有 type errors 都可以抓出來
    * 有 union or record 的就不是了
    * Java 跟 Ada 幾乎算是，但是像是 Java 把 int 跟 floating 做運算，因為 int 會被強迫轉 floating 所以不算
  * type compatibility
    * name type compatibility: type name 一樣才算
    * structure type compatibility: 兩個 type  有一樣個 structure 就算，比較寬，但是很難做
  * scope
    * static, often encourages global
    * dynamic, convenient but poor readability
  * referencing enviroment 是說你現在可以摸到的所有 variables
  * named constant 是說它的 value *只*有在它 bind 到 storage 的時候才會 bind，換句話說，之後就不能改
  * initialization 則是說 value 在 variable bind 到 storage 的時候，一起 bind 上去


===== Chapter 6 =====
  * primitive data type, not defined by other types
  * ordinal type, 可以跟正整數有一個對應的東東
  * subrange type: 不是新的 type，增加 readibility 跟 error detection
  * array
    * static: subscript ranges 跟 storage 都是 static binding
    * fixed stack dynamic: subscript static binding, storage 在宣告的時候才 bind
    * stack dynamic: subscript 跟 storage 都 dynamic binding，但是好了就不能改
    * heap-dynamic: 同上，但是之後可以改
    * row/column major
  * union
    * Ada 的有用 tag 來分實際上的 type, discriminated union
    * C 之類的則沒有, free union
  * pointer
    * dangling pointer :o
      * tombstone: 透過這個來指 memory，當 delete 的時候設成 nil，如果有人又指到 nil 那就可以抓出來
      * locks-and-keys: pointer 多記一個 key，memory 多塞一個 lock，在 new 的時候把 lock = key，delete 的時候去看 lock 跟 key 一不一樣
      * best solution is left deallocation of heap-dynamic vars to system
    * heap management
      * 比較勤勞的是 reference counter，懶惰的是 garbage collection
    * losing space（new 了又不用..）

===== Chapter 7 =====
  * operators 的 precedence 跟 associativity
    * 影響到的是相鄰的 operator，也就是中間只差一個 operand
    * 解決 function side affects 的方法
      * 不准寫！可是這樣子太苦了（不能玩 two-way parameters）
      * 固定 evaluation 順序，但是一些 optimization 就不能做了，像是 common subexpression elimation (CSE)
  * coercion 是指 implicit type conversion，會減少 compiler detect type error 的機會
  * short-circuit 會被 expression 的 side effect 影響，比如說 (a>b) || (b++/3)，因為有 short-circuit，你不能確定 b 到底有沒有 +1
  * (C, C++, Jave) (a>b) ? a : b = 0，反正左邊是拿 l-value，所以沒差

===== Chapter 8 =====
  * 所有的 control statements 都可以只用 two-way selection 跟 pretest 的 loop 幹掉
  * dangling else
  * Dijkstra, 1975, Guarded Commands
    * 在 selection 的時候，你不應該假設每個條件的順序
    * 主要是希望曾在寫程式的時候，就可以去驗證