c/c++代写,java代写,python代写,matlab代写,作业代写,留学生作业代写
Homework 2: Type Systems and Dataflow Analysis
Due Wednesday, February 13, 2019
Reminders
- Please submit your homework on Canvas.
- Collaboration is permitted, but you must write the solutions by yourself without assistance. Getting solutions from outside sources such as the Web or students not enrolled in the class is forbidden.
1.Consider the information flow type system that you studied in the paper “A Sound Type System for Secure Flow Analysis”, by Volpano, Smith, and Irvine. Now suppose that you have a functional rather than imperative language. The grammar of programs e in the language is given by
e ::= x | c | (e 1 e 2 ) | λx.e 1 | e 1 + e 2 | e 1 ≥ 0 | let x = e 1 in e 2 | if e 1 then e 2 else e 3
where x represents variables and c represents constants. Present a type system for information flow analysis of programs in this language. Your answer should clarify the following points.
(a) What is the form of a type judgment in this setting?
(b) What does a type environment look like?
(c) Does the grammar of the language need to be augmented with additional type annotations? Recall that while type-checking t-he λ-calculus, we needed to add a type annotation to the input variable x in λ-terms.
(d) What are the typing rules? Please present the rules formally, and also write a sentence or two explaining each rule.
2.Define a data flow analysis that can be used to compute two sets of variables for each statement in a program: those which are definitely not defined before use, and those which may not be defined before use. These sets can be used to provide extra error checking of programs. Your answer should answer the following questions.
(a) What is the dataflow lattice for this setting?
(b) What are the dataflow equations?
(c) Why does your analysis terminate?
(d) How do you use the information computed by your analysis to construct the two sets specified above for output to the user?
(e) How does your dataflow analysis operate on the following program, and what are the variable sets of interest for the label c in the code?
1s := 0
c: while (i < n) {
s := s + i
i := i + 1
}
3.Consider any lattice L = (S, v, t, u) where S is a set, v is a partial order, and t and u are respectively the join and meet operators. Show that the following identities hold:
(a) For all x, y, z, x t (y t z) = (x t y) t z
(b) For all x, y, (x t y) u x = x.
留学生作业代写,cs作业代写,cs代写,作业代写,北美cs作业代写,澳洲cs作业代写,加拿大cs作业代写,cs作业代写价格,靠谱cs作业代写,程序代写