Homework 3
ENE4014 Programming Languages, Spring 2022 due: 5/2(Mon), 24:00
• You must write your code by yourself and must not look at someone elses code. An automatic code clone detector (SW tool) will be used to detect any violation of the rule.
• Do not use any external libraries. You can use only the OCaml standard library (https://ocaml.org/api/index.html).
Copyright By PowCoder代写 加微信 powcoder
Exercise 1 Consider the following OCaml data type for propositional formulas
type formula = TRUE | FALSE
| NOT of formula
| ANDALSO of formula * formula
| ORELSE of formula * formula
| IMPLY of formula * formula
| LESS of expr * expr
and expr = NUM of int
| PLUS of expr * expr
| MINUS of expr * expr
Considering the above definition, write a function eval : formula → bool
that computes the truth value of a given formula. For example,
eval (IMPLY (IMPLY (TRUE, FALSE), TRUE))
evaluates to true, and
eval (LESS (NUM 5, PLUS (NUM 1, NUM 2)))
evaluates to false.
Exercise 2 Consider the following OCaml data type for Boolean circuits
type circuit = IN
| AND of circuit * circuit
| OR of circuit * circuit
where IN denotes input. For example, the following circuit
can be described as
OR (AND (IN, IN), IN)
The AND depth of a circuit is the maximum number of sequential AND gates from input to output. For example, the following circuit has the AND depth of 4.
Write a function
that takes a circuit and returns its AND depth.
Exercise 3 Write a function
(iter n f)=f◦···◦f
The function returns the identity function (fun x → x) when n = 0.
For example, returns 2 × n.
(iter n (fun x -> x + 2)) 0
and_depth : circuit -> int
Exercise 4 Write a function
sigma : int * int * (int -> int) -> int.
such that sigma(a,b,f) returns Σbn=af(n).
Exercise 5 Write a function
diff : ae ∗ string → AE
that differentiates the given algebraic expression with respect to the variable given as the second argument. The ae type is defined as follows:
type ae = CONST of int
| VAR of string
| POWER of string * int
| TIMES of ae list
| SUM of ae list
For example, x2 + 2x + 1 is represented by
SUM [POWER (“x”, 2); TIMES [CONST 2; VAR “x”]; CONST 1]
and differentiating it (w.r.t. “x”) gives 2x + 2, which can be represented by SUM [TIMES [CONST 2; VAR “x”]; CONST 2]
Exercise 6 Suppose we are interested in if someone gets COVID-19. The fol- lowing image describes people who are talking to someone else in a party at a moment.
The type talkingto is for representing whom is each person talking to: type talkingto = (string * string) list
For example, the above situation can be represented as
let party = [(“A”, “B”); (“B”, “A”); (“A”, “D”); (“B”, “C”); (“C”, “E”)]
Suppose no one is wearing a mask, and if person A talks to B and A gets COVID- 19, B also gets infected immediately. For example, in the above situation, E gets infected if A got COVID because A talks to B, who talks to C, who talks to E.
Write a function
infected : talkingto -> string -> string -> bool
that determines if a person (3rd argument) gets infected when another person (2nd argument) got COVID. For example, the function should behave as follows:
infected party “A” “E” = true
infected party “B” “D” = true
infected party “C” “D” = false
infected party “C” “B” = false
Exercise 7 As an extension of the previous exercise, suppose people who get vaccinated never get COVID. Write a function
infected_vaccine : talkingto -> string list -> string -> string -> bool
that additionally gets a list of people who get vaccinated as the second argument. For example,
infected_vaccine party [“A”; “C”] “B” “D” = false
as if A and C get vaccinated, E is free from COVID even if B got infected because C is blocking the way from B to E.
The followings are other example behaviors.
infected_vaccine party [“A”; “C”] “B” “E” = false
infected_vaccine party [“A”] “B” “E” = true
infected_vaccine party [“C”] “A” “E” = false
Exercise 8 Write a function
calculate : exp → float
that returns a result of a given arithmetic formula. The exp type is defined as follows:
type exp = X | INT of int
| REAL of float
| ADD of exp * exp
| SUB of exp * exp
| MUL of exp * exp
| DIV of exp * exp
| SIGMA of exp * exp * exp
| INTEGRAL of exp * exp * exp
For example, the following arithmetic formulas can be written in the exp type: 10 (x × x − 1) SIGMA(INT1, INT10, SUB(MUL(X, X), INT1))
10.0 (x × x − 1)dx INTEGRAL(REAL1.0, REAL10.0, SUB(MUL(X, X), INT1))
When you compute integrals, dx should be 0.1.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com