CS 131: Programming Languages Week 4 : Midterm Review
Agenda • Sample midterm review
• Midterm overview
Copyright By PowCoder代写 加微信 powcoder
Midterm Range
• Text book: 1~11 (ML for OCaml); 13, 15, 17 (Java)
• Homework: 1, 2 (OCaml); No HW3 details but still Java on exam
• Lectures: all
– C/C++ basis, type & inheritance etc. are also included
• There might be some open-ended questions with no fixed answer
Knowledge points include (not restricted to)
– Reading and writing code, figuring out types – Higher order functions, Currying
– Concept of OOP features
– Java types, generics, subtypes, etc.
– Java Memory Model, Race condition, Concurrency
• Grammar (Syntax)
– Representations: BNF, EBNF, Syntax diagrams, … – Derivation and ambiguity
Sample midterm
• Already posted on CCLE
– Spring 2008, Fall 2017 and Fall 2020 – On CCLE, on Sample Exams
OCaml: Write a function • Example: 2020F Q7
• Questions of the same type: 2017F 1a, 2008S 7a/b
OCaml: Write a function
let rec adjdup l = match l with
| hd::tl ->
let eq_l = List.filter ((=) hd) l and ne_l = List.filter ((<>) hd) l in eq_l @ (adjdup ne_l)
• or, even more concisely
let rec adjdup l = match l with [] -> []
| hd::tl ->
let (eq_l, ne_l) = List.partition ((=) hd) l in eq_l @ (adjdup ne_l)
OCaml: Write a function
• Advice for this type of question:
– Try to have a clear description of algorithm before writing code
– Take advantage of OCaml language features and allowed library functions to make your code expressive
– Focus on clarity; efficiency is often secondary (but not unimportant) – Make your code compile!
OCaml: Write a function • More open-ended ones, e.g. 2020F Q1
• The command:
– tr -cs ‘A-Za-z’ ‘[\n*]’ | sort | uniq -c | sort -rn
OCaml: Write a function
• The key: specify the interface (and the type) clearly
– Considerations: How to express command line arguments? I/O? – Multiple ways possible. Acceptable as long as it makes sense.
– No need to worry how the “commands” are implemented.
• 2020F Q3b
OCaml: Typing
• Context: Create a higher-order function r3 that reverses the sequence of arguments of 3-arguments function
– e.g.let rf = r3 f
– Then(rf c b a)shouldactlike(f a b c) – Answer: let r3 f a b c = f c b a
• Can you create a generalized version (called rn) that works for any number of arguments in OCaml?
– e.g. r3 could be implemented as let r3 = rn 3, similar for r2, r4, … 13
• 2020F Q3b
OCaml: Typing
• Can you create a generalized version (called rn) that works for any number of arguments in OCaml?
– e.g. r3 could be implemented as let r3 = rn 3, similar for r2, r4, … • No, type is inconsistent
Ocaml: Tail Recursion
Ocaml: Tail Recursion
Ocaml: Tail Recursion
Ocaml: Tail Recursion
Ocaml: Tail Recursion
Ocaml: Tail Recursion
OCaml: Homework++ • 2017F Q6 (referring to the old version of HW2)
• Also, 2020F Q4
Java: subtype and inheritance • 2017Fall 3a, 3b
Java: subtype and inheritance • 2017Fall 3a, 3b
• Yes, Java extends subtypes, implements same interface
• If only object types, then yes -> No multiple inheritance
But consider Interface type, class inherit multiple interfaces, have multiple ancestors. No common interface ancestors
• 2020F Q6
Java: Concurrency
• 2020F Q6
Java: Concurrency
• In JVM, a single thread can freely reorder the sequence if it wants. Thus, it can happen.
Grammar: Basic Concepts • 2017Fall 4a, 4e, 2008 3d
Grammar: Ambiguity
Grammar: Ambiguity
• Ambiguous because of associativity
• 2020F Q5a
Grammar: Ambiguity
If the question has a short “suggested time” but you cannot easily find the answer, perhaps it is a good idea to move on and revisit it later.
• 2020F Q5a
Grammar: Ambiguity
• Terminal string, character definition -> any ASCII character – Quote inside a string
Grammar: What you need to know
• The grammar definition style appeared in HW1/2 • Parse Tree / Abstract Syntax Tree
• BNF, EBNF
• Syntax Diagram
– a.k.a Syntax Chart, Syntax Graph, “railroad diagram” etc.
• A BNF Grammar contains:
– The set of tokens (= terminal symbols in HW1/2)
– The set of non-terminal symbols (= nonterminal symbols in HW1/2) – The start symbol (non-terminal)
– The set of productions (= rules in HW1/2)
• left-hand-size ::= right-hand-side
• LHS should be non-terminal symbol, RHS is a sequence of token or non-terminal
• Several additional syntax to make grammar look simpler, e.g. – {x}: zero or more repetitions of x (also written as “x*”)
– [x]: zero or one occurrence of x (also written as “x?”)
– ‘+’: Kleene closure, i.e. one or more occurrences
– ( ): grouping / precedence – =: definition
– (* … *): comments
Syntax Diagram • Starting from simple examples:
Diagram Bypasses
Repetition
Alternatives
Abstract Syntax Tree
• Abbreviated version of parse tree
• Details are implementation-dependent
• Usually a node for every operation, with subtrees being corresponding operands
Questions?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com