CSC201Lecture Notes PDF

Preview

Summary

Entire course lecture notes...

Description

Dr. C. Zhang, CSc 201

CSc 201 Programming Language Principles

Lecture Notes1

Dr. Cui Zhang

Department of Computer Science California State University Sacramento

This is the outline of the lecture. Many materials come from the reference books as listed in the Course Syllabus. Please see more details from the reference books, class discussions, and handouts given in class. 1

1

Dr. C. Zhang, CSc 201

Introduction Background Material 1. The course coverage (see General Course Information) 2. Programming languages The abstractions of machines/computers – at various abstract levels Software tools The evolutionary development of language design/definition of language translation/implementation 3. Programming language design/definition Any language has an alphabetic and may be characterized by Syntax -- rules of forming phrases and sentences in the forms of various grammars/automata the mechanism of syntactic processing Semantics -- meaning of phrases and statements static and dynamic semantics (in various forms/notations) the mechanism of semantic processing Object language and meta language Example: BNF definition of programming languages Formal languages and natural languages Formal definition of programming languages and mechanized programming language processing 4. Programming language translation/implementation (Compilation vs. interpretation) Compiler: source program/code  object/target program/code Object/target code and input  output/execution result Interpreter: source program/code and input  output/execution result Main components of a compiler and their theoretical foundations: Lexical analyzer -- formal languages and automata Parser -- formal languages and automata Code generator – formal semantics (syntax directed) Code optimizer – formal semantics (syntax directed)

2

Dr. C. Zhang, CSc 201

5. Mathematical background  Basics about sets Relationship between sets and types Set definition by extension/enumeration Set definition by comprehension Example: even = {n: Z : exists k: Z. n = 2k} = {n: Z | exists k: Z. n = 2k} Set definition by operations on sets Basic operations on sets Power set Cartesian product Star-closure X*: the set of strings obtained by concatenating zero or more elements/symbols from X Positive-closure X+ = X* - {} X = {a, b} X* = Xo U X1 U X2 U … Xo = {} X1 = {a, b} X2 = {aa, bb, ab, ba} … Set definition by using data constructors (arbitrary structures) Data constructor: mechanism to build a new set from a set (could be an empty set) of known sets Examples: Define a set from scratch: fruit = apple | orange | watermelon | pineapple data constructors: apple, orange, watermelon, pineapple Define a set by recursive definitions (by using known sets): graduate-student = rs of resident-student | nrs of non-resident-student; data constructors: rs, nrs labeled-btree = empty | nonempty lable  labeled-btree  labeled-btree data constructors: empty, nonempty Pattern matching and/or recursive function definition on recursively defined sets: fee-structure (rs (student-x)) = … | fee-structure (nrs(student-y)) = … ; number-of-nodes (empty) = 0 | 3

Dr. C. Zhang, CSc 201

number-of-nodes (Nonempth (label, btree1, btree2)) = number-of-nodes (btree1) + number-of-nodes (btree2) +1;  Basics about relations r is a binary relation, a set of pairs domain of r: powerset of X

r: X  Y (signature of r) range of r: powerset of Y

Relation definition by extension/enumeration by comprehension by operations on relations (on sets) by recursion  Basics about functions Functions: special kind of relations Domain of f: power set of X

f: X  Y (signature of f) Range of f: power set of Y

Total function f: domain of f is X Partial function f: domain of f is a subset of X Signatures of functions (types of functions): domain  range Higher-order functions Xi can be a function, i = 1, 2, … n+1 f: X1  X2  …  Xn  Xn+1 Example: function composition o o: (XY)  (YZ) (XZ) f: XY, g: YZ, h = o(f , g) h: XZ Currying and partial evaluation curry: (X1  X2  …  Xn  Xn+1)  (X1  (X2  (…(Xn  Xn+1))))) --- n “)”s Examples: PascalInterpreter: PascalProgram  Input  Output PascalInterpreter (factorial, 3) = 6 PascalInterpreter (factorial, 4) = 24 PascalInterpreter(GCD, (5, 10)) = 5 PascalCompiler = curry (PascalInterpreter) PascalCompiler: PascalProgram  (Input  Output) PascalCompiler(factorial) = code1 code1(3) = 6 code1(4) = 24 PascalCompiler(GCD) =code2 code2 ((5,10)) = 5

4

Dr. C. Zhang, CSc 201

 Graph and trees  Proof techniques Proof by contradiction Proof by induction Structural induction, special case: induction on natural numbers basic step, induction step (inductive assumption) Logic reasoning 6. Languages, grammars, and automata A grammar G = (V, T, S, P) V, T, S P are all finite sets V: variables/non-terminal symbols T: terminal symbols S: start symbol, an element in V P: productions x  y or ::= y A language generated/defined by a G: L(G) = {w T* : S =>* w} Generation side: derivation (“programming”) Analysis side: acceptance of membership If w L(G), then the sequence S=>w1=>w2=> … =>wn=>w is a derivation of the sentence w. An automaton -- an abstract model of a digital computer, a special kind of state transition systems Main components: input file, storage, control unit, internal states of the control unit Transition function (table/graph/diagram): next state = Transition function (current state, current input, current storage) the current configuration Accepters: output -- yes/no Transducers: output – string of symbols Formal language hierarchy (Chomsky hierarchy) Type 0: phrase-structured language (recursively enumerable language) Type 1: context-sensitive language Type 2: context-free languages Type 3: regular languages

5

Dr. C. Zhang, CSc 201

Background Material -- Formal Languages and Automata (Syntactic Definition and Processing) 1. Regular languages A regular language can be defined by a deterministic finite accepter, a regular grammar, and a regular expression. These are the 3 equivalent ways for regular language definitions but with different applications. 1.1 Regular languages and finite automata Deterministic finite accepters (dfa) & nondeterministic finite accepters (nfa) M = (Q,   , q0, F) Q: a finite set of internal states  a finite set of symbols called the input alphabet a total transition function Q   Q q0: the initial state F: a set of final states, a subset of Q Deterministic fa: (qi, a) = qj (only one qj) A language accepted by a dfa

L = L(M) = {w  * : * (q0, w)  F}

Regular languages: the language accepted by all possible finite automata Generation side: derivation (“programming”) Analysis side: acceptance of membership (“lexical analysis”) Deterministic finite automata and lexical analyzers One dfa accepts one regular language, one regular language could be accepted by more than one dfa. To show a language is regular, we need to find a dfa for it. Equivalence of deterministic and nondeterministic finite accepters Nondeterministic finite automata and lexical analyzers, backtracking in decision/choice making, parallel processing, etc. 1.2 Regular languages and regular expressions Regular expressions: a more concise way of describing regular languages

6

Dr. C. Zhang, CSc 201

 Formal definition of a regular expression over  , , and a   are all primitive regular expressions; If r1 and r2 are regular expressions, so are r1+r2, r1.r2, r1*, and (r1) and finite steps of using operators +, ., *, and ( ). Parenthesized regular expression to avoid possible ambiguity  Formal definition of the language L(r) denoted by a regular expression r  denotes empty set;  denotes {}; any a   denotes {a}; If r1 and r2 are regular expressions, then L(r1+r2) = L(r1) U L(r2); L(r1.r2) = L(r1)L(r2); L((r1)) = L(r1); L(r1*) = (L(r1))*. Relationship between a regular language and a regular expression: 1-to-1 1.3 Regular languages and regular grammars A grammar G = (V, T, S, P) is a regular grammar when it is either right-linear or left-linear. Forms of productions in a right-linear grammar A  x B or A  x A, B  V, x  T* Forms of productions in a left-linear grammar A  B x or A  x A, B  V, x  T* A left-linear grammar can be changed/rewritten as a right-linear grammar Equivalence of regular languages and regular grammars If G = (V, T, S, P) be a right-linear, then L(G) is a regular language. If L is a regular language on , then there exists a right-linear grammar 1.4 Properties of regular languages  Closure properties of regular languages Closure under simple set operations (languages as sets) Closure under some other operations  The following can be determined by algorithms a string w is a member of a regular language L a regular language is empty, finite, and infinite

7

Dr. C. Zhang, CSc 201

 Identifying non-regular languages Any finite language is regular. Any finite accepter has a finite numbers internal states and does not have the memory of input symbol counts -- limitations For any infinite language, is it regular? (i.e., can it be accepted by a fa?) Identify infinite languages using Pigeonhole principle Putting n objects into m containers (n > m) ends that at least one container must have more than one object in it. Pumping lemma (another form of pigeonhole principle) 2. Context-Free Languages 2.1 Context-free languages and grammars A language L is context-free if and only if there is a context-free grammar. A grammar G = (V, T, S, P) is context-free when all productions in P are of the form Ax A  V and x  (V U T)* The family of regular languages is a proper subset of context-free languages (with more restrictions). Generation side: derivation (“programming”) left-most/right-most derivations tree derivations (order-irrelative) total/partial derivation trees Analysis side: acceptance of membership (parsing – efficiency concern) Parsing: finding a sequence of productions by which a w in L(G) is derived. bottom-up parsing (limitations) top-down parsing exhaustive search parsing (efficiency and termination problems) To address the parsing efficiency and termination, we can add some restrictions to context-free grammars context-free grammars without productions of forms A   and A  B, A  V (for termination problem) s-grammars (simple context-free grammars) with productions of the form A  ax , A  V, a  T, x  V*, and any (A, a) occurs once in P If G is a s-grammar, then any string w in L(G) can be parsed with an effort proportional to |w|.

8

Dr. C. Zhang, CSc 201

Many features of a typical programming language can be defined by a sgrammar. But some features cannot be defined by a s-grammar. 2.2 Context-free grammars and programming languages A context-free grammar models the syntax of a programming language (language definition and language translation/processing) The commonly used meta-language for syntactic definitions of programming languages is BNF (Backus-Naur Form) Not all syntactically correct programs are semantically correct. Static semantics -- context-related typing issues Dynamic semantics -- dynamic logical issues 2.3 Ambiguity in grammars and languages A context-free grammar is of ambiguity if there exists some w  L(G) which has more than one distinct derivations trees. If L is a context-free language for which there exists an unambiguous grammar, then L is said to be unambiguous. If every grammar that generates L is ambiguous, then the language is called inherently ambiguous. Syntactic definition for expressions in programming languages a grammar with ambiguity  a grammar without ambiguity adding a variable/non-terminal for each precedence level enforcing associativity 2.4 Nondeterministic pushdown automata Nondeterministic pushdown accepters (npda) M = (Q, , q0, z, F) Q: a finite set of internal states of the control unit;  : the input alphabet;  : a finite set of symbols called the stack alphabet;  : the nondeterministic transition function Q  ( U {})  *  finite subsets of Q  *  (current state, input symbol, current top symbol of the stack) = {(new state, string to replace the current top symbol of the stack)} q0: in Q, the initial state of the control unit 9

Dr. C. Zhang, CSc 201

z: in , the stack start symbol F: the set of final states, a subset of Q State transition diagram for a npda input read, stack top popped ; stack top pushed state1 ----------------------------------------------------------- state2 A language accepted by an nondeterministic pushdown accepter M is L(M) = {w  *: (q0, w, z) |--* (p, , u), p  F, u *) For any context-free language L, there exists an npda M such that L = L(M). Construct M from L’s grammar in Greibach normal form G(V, T, S, P) A deterministic pushdown accepter (dpda) is a pushdown automaton that never has a choice in its move. A language L is a deterministic context-free language if and only if there exists a dpda M such that L = L(M). The family of deterministic context-free languages is a proper subset of all context-free languages (Efficient parsing with less or without backtracking involved). In general, for the efficiency of parsing strings of context-free languages, we need to know how to choose the “right” production rule, and how to avoid backtracking. Look ahead principle: LL grammar and parser (scan from left to right, leftmost derivations) LL(k) grammar and parser A grammar is called LL(K) grammar, if we can always uniquely identify the correct production rule given the currently scanned symbol and a “look-ahead” of the next k-1 symbols. 2.5 Properties of context-free languages  Closure properties of context-free languages Closed under union concatenation and star-closure Not closed under intersection and complementation.  The following can be determined by algorithms by a given grammar G L(G) is empty, finite, infinite  Identifying languages that are not context-free For any infinite language, is it context-free? (i.e., can it be accepted by a npda?) Memory capability of push-down accepters 10

Dr. C. Zhang, CSc 201

Two pumping lemmas 3. Turing machine 3.1 Standard Turing machine has a tape that is unbounded in both directions, allowing any number of left and right moves; is deterministic in the sense that the transition function defines at most one move for each configuration; has no special input and output files; is said to halt whenever it reaches a configuration for which the transition function is not defined. There are other models or variations of Turing machines. A transition function is a program  halt/terminate does not halt/terminate (infinite loop) needs decisions on the data represented by the tape, the “input” and “output” (result of the computation) the “algorithm”, the “logic” of the computation  (current state, current tape symbol being read) = (next state, the new tape symbol replacing the one read, move symbol) 3.2 Turing machines as language accepters 3.3 Turing machine as transducers The concept of Turing computable or computable: All the common mathematical functions, no matter how complicated, are Turing computable. Combining Turing machines for complicated tasks by refinement (programs and their subprograms) 3.4 Turing thesis Turing thesis is more properly viewed as a definition of what constitute a mechanical computation -- if and only if it can be performed by some Turing machine. Having accepted Turing’s thesis, we have a precise definition of an algorithm. 11

Dr. C. Zhang, CSc 201

Lambda Calculus It is a theory about the definition and manipulation of math functions, a way to express computation, and a “programming” language. 1. Advantages High order functions -- Functions (function definitions) are first class citizens/values (ordinary objects) that can be used as operands in expression without referring constantly to their arguments. Distinguishing f and f(a). Example: add (x, y) = x + y add =  x .  y . x + y

add (5, 6) = 11 ( x .  y . x + y) (5) (6) = 11

Anonymous functions, e.g., the right hand side of the above function definition 2. expressions Three forms (a recursive definition) Constant function: an identifier Function definition/abstraction:  x . e x: identifier; e:  expression Function application: f(e) f, e:  expressions Curry-formed function definitions  x, y, z . e =  x . ( y . ( z . e)) =  x .  y .  z . e Example: composition of any two functions f: X  Y and g: Y  Z H =  F .  G .  X . G(F(X)) h = f o g (or f ; g, or g o f) H (f) (g) = h =  X . g(f(X)) h: X  Z h(x) = g(f(x)) 3. Free and bound occurrences of identifiers Closely corresponding to that of block-structured programming languages. Example:  x .  z . ( x ( y )) ( z ) ---------------------- E2 ---------------------------- E1 Id E1 E2 x bound free -- the same x but different occurrences y free free -- the same y and the same occurrence z bound -- z is local to E2 only

12

Dr. C. Zhang, CSc 201

Example:  y . x ( x . y ( x ) ) ---------------- E3 -------------------- E2 --------------------------- E1 Id E1 E2 E3 x free free bound -- the x in E1, E2 and the x in E3 are different. y bound free free -- the same y but different occurrences 4. Lambda conversion  -conversion (name change for function definitions):  v . E   v’ . E Any abstraction of the form  v . E can be converted to the right hand side provided that the substitution of v’ for v in E is valid – no name crash that changes the meaning of the expression. Validity rule1: v’ is not free originally in E. Example:  x .  z . a ( x ( z ))   a .  z . a ( a ( z )) “a” is free before but now bound. Validity rule2: v’ is not originally bound in E. Example:  x .  z . a ( x ( z ) )   z .  z . a ( z ( z ) ) No way to distinguish the two “z”s now. -conversion (function application – formal parameters are replaced by actual

parameters). Any application of the form ( v . E1) (E2) can be converted to E1 [E2/v] provided that the substitution of E2 for v in E1 is valid. The substitution is recursively defined. Validity rule1: substitute E2 only for free occurrences of v in E1. Example: ( y . y (u ( y . u ( y)))) ( x . x (a))  ( x . x (a)) ( u ( y . u(y))) Validity rule2: no free occurrences of v’ in E2 become bound after substitution. Example: (y .  a . a ( y )) ( x . x (a ))   a . a ( x . x ( a )) This “a” was free. The “a” should be renamed before the substitution.

13

Dr. C. Zhang, CSc 201

5. Contraction (evaluation, reduction) -expression e  -expression E’

(many steps of conversions) E’ is called a normal form if there is no any redex ( reducible expression). The normal form is the denotation (value, meaning, semantics) of E. Assume ( x . E1) (E2), E1, and E2 are all redexes, Inner-most contraction order (application order):  convert E1 and E2 first – eager evaluation, call by value Left-most contraction order (normal order):  convert ( x . E1) (E2) first – lazy evaluation Example: ( y. y) (( x . x) (1))  ( y . y ) (1)  1 inner-most contraction ( y. y) (( x . x) (1))  ( x . x) (1)  1 left-most contraction Some sequence of contraction/evaluation may never terminate. But if an expression E is evaluated by applying two different sequence of reductions until two normal forms E1 and E2 are obtained, Church-Rosser theorem shows that E1 and E2 will be the same except for possibly having different names of bound variables (e.g.,  x, y . x + y is equivalent to  s, t . s + t). There is related research on parallel processing of disjoint redexes. The normalization theorem: If E has a normal form, then repeatedly reducing the left-most redex will terminate with an expression in normal form. 6. Typed lambda calculus Contraction/reduction is used for simplifying expressions, but does not always simplify expressions. Example (self-self): ( x ...