筆記

• 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

• 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. 來定義，後者走數學來定義

• 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 上去

• 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 了又不用..）

• 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，所以沒差

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