CS 342 Principles of Programming Languages Homework 8
Homework Solutions: TypeLang
Learning Objectives:
1. Understanding and implementing typing rules
Instructions:
• Total points 66 pt
• Early deadline: Apr 14 (Wed) at 11:59 PM; Regular deadline: Apr 16 (Fri) at 11:59 PM (or till TAs
start grading the homework)
• Download hw8code.zip from Canvas. Interpreter for Typelang is significantly different compared to
previous interpreters:
– Env in Typelang is generic compared to previous interpreters.
– Two new files Checker.java and Type.java have been added
– Type.java defines all the valid types of Typelang.
– Checker.java defines type checking semantics of all expressions.
– Typelang.g has changed to add type information in expressions. Please review the changes in file
to understand the syntax.
– Finally Interpreter.java has been changed to add type checking phase before evaluation of
Typelang programs.
• Set up the programming project following the instructions in the tutorial from hw2 (similar steps)
• Extend the Typelang interpreter for Q1 – Q5.
• How to submit:
– Please submit your solutions in one zip file with all the source code files (just zip the complete
project’s folder).
– Write your solutions to Q6 – Q7 in a HW8.scm file and store it under your code directory.
hw8code
typelang
src
main
java
Example
– Submit the zip file to Canvas under Assignments, Homework 8.
Spring 2021 page 1 of 10
CS 342 Principles of Programming Languages Homework 8
Questions:
1. (10 pt) [Implement type rules] Implement the type rules for memory related expressions:
(a) (5 pt) DerefExp: Let a deref expression be (deref e1), where e1 is an expression.
• if e1’s type is ErrorT then (deref e1)’s type should be ErrorT
• if e1’s type is RefT then (deref e1)’s type should RefT.nestType(). Note that nestType() is
method in RefT class.
• otherwise, (deref e1)’s type is ErrorT with message ”The dereference expression expect a
reference type ” + ”found ” + e1’s type + ” in ” + expression.
Note that you have to add e1’s and e2’s type and expression in the error message. Examples: $
(deref (ref : num 45))
45
// no explicit error cases
$ (deref 45)
Type error: The dereference expression expects a reference type, found num in (deref 45)
(b) (5 pt) AssignExp: Let a set expression be (set! e1 e2), where e1 and e2 are expressions.
• if e1’s type is ErrorT then (set! e1 e2)’s type should be ErrorT
• if e1’s type is RefT and nestedType of e1 is T then
– if e2’s type is ErrorT then (set! e1 e2)’s type should be ErrorT
– if e2’s type is typeEqual To T then (set! e1 e2)’s type should be e2’s type.
– otherwise (set! e1 e2)’s type is ErrorT with message ”The inner type of the reference
type is ” + nestedType T + ” the rhs type is ” + e2’s type + ” in ” + expression
• otherwise (set! e1 e2)’s type is ErrorT with message ”The lhs of the assignment expression
expect a reference type found ” + e1’s type + ” in ”+ expression.
Note that you have to add e1’s and e2’s type and expression in the error message. Examples:
$ (set! (ref : num 0) #t)
Type error: The inner type of the reference type is number the rhs type is bool in (set! (ref 0)
#t)
$ (set! (ref : bool #t) (list : num 1 2 3 4 5 6 ))
Type error: The inner type of the reference type is bool the rhs type is List
(ref #t) (list 1 2 3 4 5 6 ))
Sol
• DerefExp
1 public Type visit(DerefExp e, Env
2 Exp exp = e.loc_exp ();
3 Type type = (Type)exp.accept(this , env);
4 if (type instanceof ErrorT) { return type; }
5
6 if (type instanceof RefT) {
7 RefT rt = (RefT)type;
Spring 2021 page 2 of 10
CS 342 Principles of Programming Languages Homework 8
8 return rt.nestType ();
9 }
10
11 return new ErrorT(“The dereference expression expect a reference type ” +
12 “found ” + type.tostring () + ” in ” + ts.visit(e, null));
13 }
• AssignExp
1 public Type visit(AssignExp e, Env
2 Exp lhs_exp = e.lhs_exp ();
3 Type lhsType = (Type)lhs_exp.accept(this , env);
4 if (lhsType instanceof ErrorT) { return lhsType; }
5
6 if (lhsType instanceof RefT) {
7 Exp rhs_exp = e.rhs_exp ();
8 Type rhsType = (Type)rhs_exp.accept(this , env);
9 if (rhsType instanceof ErrorT) { return rhsType; }
10
11 RefT rt = (RefT)lhsType;
12 Type nested = rt.nestType ();
13
14 if (rhsType.typeEqual(nested)) { return rhsType; }
15
16 return new ErrorT(“The inner type of the reference type is ” +
17 nested.tostring () + ” the rhs type is ” + rhsType.tostring ()
18 + ” in ” + ts.visit(e, null));
19 }
20 return new ErrorT(“The lhs of the assignment expression expect a ”
21 + “reference type found ” + lhsType.tostring () + ” in ” +
22 ts.visit(e, null));
23 }
2. (10 pt) [Implement type rules] Implement the type rules for list expressions:
(a) (5 pt) CarExp: Let a car expression be (car e1), where e1 is an expression.
• if e1’s type is ErrorT then (car e1)’s type should be ErrorT
• if e1’s type is PairT then (car e1)’s type should be the type of the first element of the pair
• otherwise, (car e1)’s type is ErrorT with message ”The car expect an expression of type Pair,
found”+ e1’s type+ ”in” + expression
Note that you have to add e1’s type and expression in the error message. See some examples below.
$ (car 2)
Type error: The car expect an expression of type Pair, found num in (car 2)
$ (car (car 2))
Type error: The car expect an expression of type Pair, found num in (car 2)
(b) (5 pt) ListExp: Let a list expression be (list : T e1 e2 e3 … en), where T is type of list and e1,
e2, e3 … en are expressions
• if type of any expression ei, where ei is an expression of element in list at position i, is ErrorT
then type of (list : T e1 e2 e3 … en) is ErrorT.
Spring 2021 page 3 of 10
CS 342 Principles of Programming Languages Homework 8
• if type of any expression ei, where ei is an expression of an element of list, is not T then type
of (list : T e1 e2 e3 … en) is ErrorT with message ”The ” + index + ” expression should
have type ” + T + ” found ” + Type of ei + ” in ” + ”expression”. where index is the
position of expression in list’s expression list.
• else type of (list : T e1 e2 e3 … en) is ListT.
Note that you have to add ei’s type and expression in the error message. Some examples appear
below.
$ (list : bool 1 2 3 4 5 6 7)
Type error: The 0 expression should have type bool, found number in (list 1 2 3 4 5 6 7 )
$ (list : num 1 2 3 4 5 #t 6 7 8)
Type error: The 5 expression should have type number, found bool in (list 1 2 3 4 5 #t 6 7 8)
• carexp
1 public Type visit(CarExp e, Env
2 Exp exp = e.arg();
3 Type type = (Type)exp.accept(this , env);
4 if (type instanceof ErrorT) { return type; }
5
6 if (type instanceof PairT) {
7 PairT pt = (PairT)type;
8 return pt.fst();
9 }
10
11 return new ErrorT(“The car expect an expression of type Pair , found ”
12 + type.tostring () + ” in ” + ts.visit(e, null));
13 }
• listexp
1 public Type visit(ListExp e, Env
2 List
3 Type type = e.type();
4
5 int index = 0;
6 for (Exp elem : elems) {
7 Type elemType = (Type)elem.accept(this , env);
8 if (elemType instanceof ErrorT) { return elemType; }
9
10 if (! assignable(type , elemType)) {
11 return new ErrorT(“The ” + index +
12 ” expression should have type ” + type.tostring () +
13 ” found ” + elemType.tostring () + ” in ” +
14 ts.visit(e, null));
15 }
16 index ++;
17 }
18 return new ListT(type);
19 }
3. (5 pt) [Implement type rules] Implement the type rules for function calls.
CallExp: Let a call expression be (ef e1 … en) with type:
Spring 2021 page 4 of 10
CS 342 Principles of Programming Languages Homework 8
• if the type of ef is ErrorT, return ErrorT
• if the type of ef is not FuncT, the type of the call expression is ErrorT, reporting the message
”Expect a function type in the call expression, found ”+ef’s type+”in ”+ expression
• if any one of e1, e2, …en has ErrorT, the call expression has ErrorT
• given that ef has FuncT (T1 … Tn)->Tb, if the actual parameter ei does not have a type Ti, the
call expression has ErrorT, reporting the message ”The expected type of the ” + i + ”th actual
parameter is ” + Ti + ”, found ” + ei’s type +”in ”+expression
• otherwise, the type of call expression is Tb
Some examples appear below.
1 $(define add: (num num num -> num) (lambda (x: num y: num z: num) (+ x (+ y z
))))
$ (add 5 56 #t)
Type error: The expected type of the 2 argument is number found bool in (add 5.0 56.0 #t )
$ (3 4)
Type error: Expect a function type in the call expression, found number in (3 4)
Sol.
• CallExp
1
2 public Type visit(CallExp e, Env
3 Exp operator = e.operator ();
4 List
5
6 Type type = (Type)operator.accept(this , env);
7 if (type instanceof ErrorT) { return type; }
8
9 String message = “Expect a function type in the call expression , found ”
10 + type.tostring () + ” in “;
11 if (type instanceof FuncT) {
12 FuncT ft = (FuncT)type;
13
14 List
15 int size_actuals = operands.size();
16 int size_formals = argTypes.size();
17
18 message = “The number of arguments expected is ” + size_formals +
19 ” found ” + size_actuals + ” in “;
20 if (size_actuals == size_formals) {
21 for (int i = 0; i < size_actuals; i++) {
22 Exp operand = operands.get(i);
23 Type operand_type = (Type)operand.accept(this ,
env);
24
25 if (operand_type instanceof ErrorT) { return
operand_type; }
Spring 2021 page 5 of 10
CS 342 Principles of Programming Languages Homework 8
26
27 if (! assignable(argTypes.get(i), operand_type)) {
28 return new ErrorT("The expected type of
the " + i +
29 " argument is " + argTypes.get(i).
tostring () +
30 " found " + operand_type.tostring () + "
in " +
31 ts.visit(e, null));
32 }
33 }
34 return ft.returnType ();
35 }
36 }
37 return new ErrorT(message + ts.visit(e, null));
38 }
4. (18 pt) [Design and implement type rules] Design and implement the type rules for comparison ex-
pressions:
BinaryComparator: Let a BinaryComparator be (binary operator e1 e2), where e1 and e2 are expres-
sions.
(a) (4 pt) Describe the type rules (see the example type rules or test cases provided in the above
questions) to support the comparisons of two numbers (NumT)
(b) (4 pt) Describe the type rules to support the comparison of two lists (listT)
(c) (10 pt) Implement the type checking rules for number and list comparisons.
Sol
(a) • if e1’s type is ErrorT then (binary operator e1 e2)’s type should be ErrorT
• if e2’s type is ErrorT then (binary operator e1 e2)’s type should be ErrorT
• if e1’s type is not NumT then (binary operator e1 e2)’s type should be ErrorT with message
: ”The first argument of a binary expression should be num Type, found ” + e1’s type + ”
in ” + expression.
• if e2’s type is not NumT then (binary operator e1 e2)’s type should be ErrorT with message
: ”The second argument of a binary expression should be num Type, found ” + e2’s type +
” in ” + expression.
• otherwise (binary operator e1 e2)’s type should be BoolT.
(b) • if e1’s type is ErrorT then (binary operator e1 e2)’s type should be ErrorT
• if e2’s type is ErrorT then (binary operator e1 e2)’s type should be ErrorT
• if e1’s type is ListT and e2’s type is ListT then (binary operator e1 e2)’s type should be
ErrorT with message : ”arguments of the binary expression are of List Type, found ” + e1’s
type +” and ” + e2’s type ” in ” + expression.
• otherwise (binary operator e1 e2)’s type should be BoolT.
(c) BinaryComparator
Spring 2021 page 6 of 10
CS 342 Principles of Programming Languages Homework 8
1 private Type visitBinaryComparator(BinaryComparator e, Env
2 String printNode) {
3 Exp first_exp = e.first_exp ();
4 Exp second_exp = e.second_exp ();
5
6 Type first_type = (Type)first_exp.accept(this , env);
7 if (first_type instanceof ErrorT) { return first_type; }
8
9 Type second_type = (Type)second_exp.accept(this , env);
10 if (second_type instanceof ErrorT) { return second_type; }
11
12 if (( first_type instanceof ListT) & (second_type instanceof ListT)) {
13 return new ErrorT(“The arguments of the binary expression ”
14 + “are of List Type , found ” + first_type.tostring () + ” and ” +
second_type.tostring () +
15 ” in ” + printNode);
16 }
17
18 if (!( first_type instanceof NumT)) {
19 return new ErrorT(“The first argument of a binary expression ”
20 + “should be num Type , found ” + first_type.tostring () +
21 ” in ” + printNode);
22 }
23
24 if (!( second_type instanceof NumT)) {
25 return new ErrorT(“The second argument of a binary expression ”
26 + “should be num Type , found ” + second_type.tostring () +
27 ” in ” + printNode);
28 }
29
30 return BoolT.getInstance ();
31 }
5. (9 pt) [Design and implement type rules] Design and implement the type checking rules for condition
expressions.
IfExp: Let a IfExp be (if cond then else), where cond, then, else are expressions.
(a) (4 pt) Describe the type rules to support the condition expressions.
(b) (5 pt) Implement the type checking rules for condition expressions.
Sol
(a) • if cond’s type is ErrorT then (if cond then else)’s type should be ErrorT
• if cond’s type is not BoolT then (if cond then else)’s type should be ErrorT with message:
”The condition should have boolean type, found ” +cond’s type+ ” in ” + expression
• if then’s type is ErrorT then (if cond then else)’s type should be ErrorT
• if else’s type is ErrorT then (if cond then else)’s type should be ErrorT
• if then’s type and else’s type are typeEqual then (if cond then else)’s type should be then’s
type.
Spring 2021 page 7 of 10
CS 342 Principles of Programming Languages Homework 8
• else (if cond then else)’s type should be ErrorT with message: ”The then and else expressions
should have the same ” + ”type, then has type ” + then’s type + ” else has type ” +else’s
type+ ” in ” + expression.
• $ (if 5 56 67)
Type error: The condition should have boolean type, found number in (if 5 56 67)
$ (if #t #t 56)
Type error: The then and else expressions should have the same type, then has type bool
else has type number in (if #t #t 56)
(b) IfExp
1 public Type visit(IfExp e, Env
2 Exp cond = e.conditional ();
3 Type condType = (Type)cond.accept(this , env);
4 if (condType instanceof ErrorT) { return condType; }
5
6 if (!( condType instanceof BoolT)) {
7 return new ErrorT(“The condition should have boolean type , found
” +
8 condType.tostring () + ” in ” + ts.visit(e, null));
9 }
10
11 Type thentype = (Type)e.then_exp ().accept(this , env);
12 if (thentype instanceof ErrorT) { return thentype; }
13
14 Type elsetype = (Type)e.else_exp ().accept(this , env);
15 if (elsetype instanceof ErrorT) { return elsetype; }
16
17 if (thentype.typeEqual(elsetype)) { return thentype; }
18
19 return new ErrorT(“The then and else expressions should have the same ”
20 + “type , then has type ” + thentype.tostring () +
21 ” else has type ” + elsetype.tostring () + ” in ” +
22 ts.visit(e, null));
23 }
6. (8 pt) [Typelang programming] For all the above typing rules (total 8 of them) you implement, write
a typelang program for each type rule to test and demonstrate your type check implementation. (You
can use typelang.g in hw8code.zip as a reference for the syntax of TypeLang). For each expression,
put in comments which type rules the expression is exercising.
For example: $ (list: num 45 45 56 56 67) // test correct types for list expressions
$(> 45.0 #t) // test incorrect types for binary comparator expressions
1
2 $ (let ((x: bool (deref counter))) (if x 5 6)) // test incorrect types for if
expressions
3 $ Type error: The declared type of the 0 let variable and the actual type mismatch ,
expect bool found number in (let ( (x (deref counter))) (if x 5.0 6.0) )
4 $ (let ((x: num (deref counter))) (if (< x 4) x 6)) // test correct types for if, let and binary comparison expressions 5 $ 0 6 $ (define inc: (-> num) (lambda () (set! counter (+ 1 (deref counter))))) // test
correct types for set! expressions and lambda expressions
Spring 2021 page 8 of 10
CS 342 Principles of Programming Languages Homework 8
7 $ (inc 4) // test incorrect actual parameter types for call expressions
8 $ Type error: The number of arguments expected is 0 found 1 in (inc 4.0 )
9 $ (inc) // test correct call expression
10 $ 1
11 $ (define l2: List
12 $ Type error: The 2 expression should have type number found bool in (list 1.0 2.0 #t
)
13 $ (define l2: List
14 $(let (( first: num (car l2)) (second: num (car (cdr l2)))) (> first second))
15 // test correct types for car , cdr expressions and binary comparator
16 $ #f
7. (6 pt) [Typelang programming] In HW5, you have written a function processlists that takes three
arguments op, list1, list2, where op is a function that takes two pairs as parameters, and list1
and list2 are the two lists of pairs. The return value is the result of applying op on each pair oflist1
and list2. You have also written functions common and diff to test processlists.
Please refer to the examples below:
$ (define list1 (list (cons 1 3) (cons 4 2) (cons 5 6)))
$ (define list2 (list (cons 2 6) (cons 4 2) (cons 1 3)))
$ (processlists common list1 list2)
((-1,-1)(4,2)(-1,-1))
$ ((processlists diff list1 list2)
((1,3)(-1,-1)(5,6))
$ (processlists diff list2 list1)
((2,6)(-1,-1)(1,3))
In this problem, you are required to write common and diff and processlists in TypeLang. The
types of function arguments should be compatible with the types used in the above examples.
Note:
(a) You will need to modify your code from HW5 to output a default pair (-1,-1) when op is not
satisfied instead of empty list (), so that the output type is consistent.
(b) Assume TypeLang supports type checking for recursive functions as you answer this question.
Sol:
1
2
3 (define list1 : List <(num ,num)> (list: (num , num) (cons 1 3) (cons 4 2) (cons 5 6)))
4 (define list2 : List <(num ,num)> (list: (num , num) (cons 2 6) (cons 4 2) (cons 1 3)))
5
6
7 (define common: ((num , num) (num , num) -> (num , num))
8 (lambda (pair1: (num , num) pair2: (num , num))
9 (if (= (car pair1) (car pair2))
10 (if (= (cdr pair1) (cdr pair2))
11 pair1
12 (cons -1 -1))
Spring 2021 page 9 of 10
CS 342 Principles of Programming Languages Homework 8
13 (cons -1 -1))))
14
15
16 (define diff: ((num , num) (num , num) -> (num , num))
17 (lambda (pair1: (num , num) pair2: (num , num))
18 (if (= (car pair1) (car pair2))
19 (if (= (cdr pair1) (cdr pair2))
20 (cons -1 -1)
21 pair1)
22 pair1)))
23
24 (define processlists: (((num , num) (num , num) -> (num , num)) List <(num , num)> List <( num , num)> -> List <(num , num) >)
25 (lambda (op: ((num , num) (num , num) -> (num , num)) lst1: List <(num , num)>
lst2: List <(num , num) >)
26 (if (null? lst1)
27 lst2
28 (if (null? lst2)
29 lst1
30 (cons (op (car lst1) (car lst2))(processlists
op (cdr lst1) (cdr lst2)))))))
Spring 2021 page 10 of 10