CS 320 Theory Assignment #3
Problem 1 : polymorphism and high-order function
let f x = [([x], x)]
let rec foo (g, n) =
match n with
| 0 -> [(g 1, g 0)]
| n -> (g n, g (n –
let res = foo(f, 2) Whatisthetypeoff ?
1)) :: foo (g, n – 1)
Assume the type of input x is ‘a, then
[x] would be of type ‘a list
([x], x) would be of type ‘a
[([x], x)] would beoftype(‘a list * ‘a) list
list * ‘a Thereforethetypeoffis‘a -> (‘a list * ‘a) list
Whatisthetypeoffoo ?Youalsoneedtoprovidetheevidencesyouused while deriving the answer.
From the pattern matching on n, we know that n is an integer.
From the application of g on 1, 0, n, and n-1 we know that g is a function that take in
aninteger.Assumeg’stypetobeint -> ‘a
From the return [(g 1, g 0)] in the first case (and also the second case) we know
thereturnoffoois‘a * ‘a list.
Sincethetypeofgisint -> ‘a,andtypeofnisint,theinputtypeoffoois(int -> ‘a) * int
Thereforethetypeoffoois(int -> ‘a) * int -> (‘a * ‘a) list
Whatisthevalueofres ?
When f is sent in as the first element of foo, the type variable ‘a in f is specialized to int
o Then f becomes the type int -> (int list * int) list
Therefore specialize the type variable ‘a in foo to (int list * int) list
Then the type of foo becomes (int -> (int list * int) list) * int -> ((int list * int) list * (int list * int) list) list
Therefore the return of foo (res) will have type ((int list * int) list * (int list * int) list) list
Problem 2 : data type Consider the following program:
type fruit
type veggie
type salad
= Apple | Pear | Grape | Banana
= Carrot | Cucumber | Cabbage
= ____????____
let rec foo (a:salad) c =
match a with
| [] -> c
| s::ss -> let c1, c2 = c in
(match s with
| Apple, _ -> foo ss (c1+1,c2)
| _ , Cabbage -> foo ss (c1, c2+1)
| _ -> foo ss c)
Whatisthetypeofsalad ?
By the patterns for a, we know that the type salad is some list.
By the pattern of s, we know that elements in the list a needs to be of type fruit * veggie
Thereforesalad(thetypeofa)is(fruit * veggie) list
Problem 3 : Data type
type symbol = A | B | C
type op = ___???___
let apply1 (operation: op) (ls: symbol list) = match operation with
| Un a -> List.map a ls
| Bi b ->
( match ls with
| h1::h2::tl -> b h1 h2 :: tl
| _ -> [A])
let rec apply2 (two_op : op * op ) (ls: symbol list) =
match two_op with
| S s , Out o -> o ls s
| Out o, S s -> apply2 (S s, Out o) ls
| S s , Un a -> let _ = a s in 1
op has exactly four constructors. Write down the definition of op
From the match on operation, we know that op have two constructor Un and Bi
o For Un, its input a can be mapped onto ls, which is a symbol list. Therefore aneedstohavetypesymbol -> ‘aforsome‘a,wherethereturnofapply1
is‘a list
o ForBi,itsinputb canbeappliedtotwoelementsofls(b h1 h2)thereforeb
havetypesymbol -> symbol -> a’.
o FromtheBicase,weknowthatthereturnwillbeasymbol list,(finalreturn
[A]), therefore ‘a will be symbol,
o therefore Un takes in symbol -> symbol, and Bi takes in symbol ->
symbol -> symbol
From the match on two_op, we know that op has two constructors S and Out
o From the first case we assume the type of s to be ‘s, then Out will take in a functionoftypesymbol list -> ‘s -> ‘b,wheretheretrunofapply2 is of type ‘b
o From the third case we know the input of Un, a, which is of type symbol -> symbol can take in the input of S, therefore the type variable ‘s should be
symbol,andfromtheend(in 1),weknowthereturnofapply2isainteger,
therefore the type variable ‘b should be int
o ThereforeS willtakeinasymbol,andOut willtakeinasymbol list ->
symbol -> int
Since op has exactly 4 constructors, therefore its constructors are Un, Bi, S and Out:
op = Un of symbol -> symbol | Bi of symbol -> symbol -> symbol |
S of symbol | Out of symbol list -> symbol -> int
Provide an argument myarg for apply2 such that given ls, apply2 myarg lswouldreturnanint,indicatingthenumberofoccurrencesofA in ls.
Define the following function first (this works for a general symb_to_find, they can also write a function that just work for symbol A)
let rec count_symb (symb_lst: symbol list) (symb_to_find:
symbol): int =
match symb_lst of
| [] -> 0
| symb :: tail -> if symb = symb_to_find
then 1 + count_symb tail symb
else count_symb tail symb
There are two acceptable answer:
myarg = (S A, Out count_symb) myarg = (Out count_symb, S A)
Problem 4 : Grammar Consider the following grammar:
Draw the parse tree for generating the expression -2 + 1 * 2 + 0 from
this grammar:
Is the grammar ambiguous or unambiguous? If it is ambiguous, use parse trees to explain why.
This grammar is ambiguous, since there are two possible parse tree for this expression.
::=
–
Design a grammar where * has precedence over +, such that every string can be parsed with the given precedence in the original language, it will be able to be parsed with your new grammar.
Problem 5 : Grammar Consider the following grammar:
Are the following sentences can be generated by the grammar defined above? If so, draw their parse tree.
(1). c * d / 1 – 1 Thiscannotbegenerated,since/onlytakesa
as
(2). 0 + d * c + c
::=
::=
c|d
(3). 0 + d * c – c
Is the grammar ambiguous? If it is ambiguous, use parse trees to explain why.
This grammar is ambiguous, since (2) has more than 1 way to parse.
Design a grammar where * has precedence over all the other operation, / has precedence over + and -, and + has precedence over -, such that every string can be parsed with the given precedence in the original language, it will be able to be parsed with your new grammar.