CS 342 Principles of Programming Languages Homework 5
Homework Solutions: FuncLang (Part II)
Learning Objectives:
1. Functional programming
2. Understand and expand FuncLang interpreter
Instructions:
• Total points: 54 pt
• Early deadline: Mar 24 (Wed) at 11:59 PM; Regular deadline: Mar 26 (Fri) at 11:59 PM (you can
continue working on the homework till TA starts to grade the homework).
• We will grade functional programming based on our tests
• Download hw5code.zip from Canvas
• Set up the programming project following the instructions in the tutorial from hw2 (similar steps)
• How to submit:
– For questions 1–2, please submit one pdf that contains all the source code
– For questions 3–4, please submit your solutions in one zip file with all the source code files (just
zip the complete project’s folder).
– Submit the zip file and one pdf file to Canvas under Assignments, Homework 5 submission.
Questions:
1. (8 pt) Write FuncLang programs to process a list of strings. Here, a string is a list of characters and
each character is represented using a number.
(a) (4 pt) Given a character and a list of strings, find strings that do not contain the given character.
See the example below.
$ (find 88 (list (list 77 73) (list 89)))
((77 73) (89))
$ (find 88 (list (list 77 73) (list 88) (list 88 90 76)))
((77 73))
Sol.
Spring 2021 page 1 of 3
CS 342 Principles of Programming Languages Homework 5
( d e f i n e f i n d
( lambda (n l s t )
( i f ( n u l l ? l s t )
( l i s t )
( i f ( i s P r e s e n t n ( car l s t ) )
( f i n d n ( cdr l s t ) )
( appendChar ( car l s t ) ( f i n d n ( cdr l s t ) ) )
)
)
)
)
( d e f i n e i s P r e s e n t
( lambda (n l s t )
( i f ( n u l l ? l s t )
#f
( i f (= ( car l s t ) n)
#t
( i s P r e s e n t n ( cdr l s t ) )
)
)
)
)
( d e f i n e appendChar
( lambda ( l s t 1 l s t 2 )
( i f ( n u l l ? l s t 1 ) l s t 2
( i f ( n u l l ? l s t 2 ) l s t 1
( l i s t l s t 1 l s t 2 )
)
)
)
)
(b) (4 pt) Given a list of strings, return a string that concatenates all the strings in the list and
characters are sorted in ascending form. See the example below.
$ (sort (list (list 1 2) (list 3 4) (list 5)))
(1 2 3 4 5)
$ (sort (list (list 1 2) (list 5 4) (list 5)))
(1 2 4 5 5)
$ (sort (list (list 1 2) (list 4 3) (list 5)))
(1 2 3 4 5)
Sol.
( d e f i n e append
Spring 2021 page 2 of 3
CS 342 Principles of Programming Languages Homework 5
( lambda ( l s t 1 l s t 2 )
( i f ( n u l l ? l s t 1 ) l s t 2
( i f ( n u l l ? l s t 2 ) l s t 1
( cons ( car l s t 1 ) ( append ( cdr l s t 1 ) l s t 2 ) ) ) ) ) )
( d e f i n e Concatenate
( lambda ( l s t )
( i f ( n u l l ? l s t )
( l i s t )
( i f ( n u l l ? ( cdr ( cdr l s t ) ) )
( append ( car l s t ) ( car ( cdr l s t ) ) )
( Concatenate
( cons ( append ( car l s t ) ( car ( cdr l s t ) ) )
( cdr ( cdr l s t ) ) ) ) ) ) ) )
( d e f i n e sma l l e r ( lambda ( x y )
( i f (< x y ) x y ) ) )
( d e f i n e minimum ( lambda ( l s t )
( i f ( n u l l ? l s t ) ( l i s t )
( i f ( n u l l ? ( cdr l s t ) )
( car l s t )
( sma l l e r ( car l s t ) (minimum ( cdr l s t ) ) ) ) ) ) )
( d e f i n e remove f roml i s t ( lambda ( e l e l s t )
( i f ( n u l l ? l s t ) ( l i s t )
( i f (= e l e ( car l s t ) )
( cdr l s t )
( cons ( car l s t ) ( r emove f roml i s t e l e ( cdr l s t ) ) ) ) ) ) )
( d e f i n e s o r t l i s t ( lambda ( l s t )
( i f ( n u l l ? l s t )
( l i s t )
( l e t ( ( x (minimum l s t ) ) ) ( cons x ( s o r t l i s t ( r emove f roml i s t x l s t ) ) ) ) ) ) )
( d e f i n e s o r t ( lambda ( l s t )
( s o r t l i s t ( Concatenate l s t ) ) ) )
2. (6 pt) Write a function, triangle, which takes a number and produces a list ; each element of the list
is a list of symbols. When triangle is called with a non-negative integer, n, it returns a list containing
n number of lists. The first inner list has n elements, the second inner list has n-1 element, and so on
until you reach the top with only one element list, which forms the shape of a triangle. Each of the
inner lists contain only the numbers 0 and 1 and they alternate across lists. The result always has the
0 as the first element of the first inner list, if any. In the following examples, we have formatted the
Spring 2021 page 3 of 3
CS 342 Principles of Programming Languages Homework 5
output to show the result more clearly, but your output will not look the same; it is sufficient to just
get the outputs that are equal to those shown. Spaces in the lists are just for displaying purposes and
you are not required to print them.
$ (triangle 0)
()
$ (triangle 1)
((0))
$ (triangle 2)
((0 1)
(1))
$ (triangle 3)
((0 1 0)
(1 0)
(0))
$ (triangle 4)
((0 1 0 1)
(1 0 1)
(0 1)
(1))
$ (triangle 5)
((0 1 0 1 0)
(1 0 1 0)
(0 1 0)
(1 0))
(0))
Sol.
( d e f i n e a l t ( lambda (n)
( i f (= n 0) 1 0 ) ) )
( d e f i n e a l t e r n a t e ( lambda ( x y )
( i f (= x 0) ( l i s t )
( cons y ( a l t e r n a t e (− x 1) ( a l t y ) ) ) ) ) )
( d e f i n e he lpe r ( lambda ( l s t )
( i f ( n u l l ? l s t ) ( l i s t )
( cons l s t ( he lpe r ( cdr l s t ) ) ) ) ) )
( d e f i n e t r i a n g l e ( lambda (n)
( he lpe r ( a l t e r n a t e n 0 ) ) ) )
3. (20 pt) Extend the FuncLang interpreter by supporting ”>” and ”<” and ”=” on strings and lists,
supporting ”=” on boolean values. For ”=”, we return true if the two strings have the exact length and
Spring 2021 page 4 of 3
CS 342 Principles of Programming Languages Homework 5
content. Two list values are considered equal if they have the same size and each element of the list
is equal to corresponding element in the other list. For ”<” and ”>”, the string and list comparison
is done using the length of the strings and lists. That is, ”> first second” returns true if the first
string/list is longer than the second string/list; and ”< first second” returns true if the first string/list
is shorter than the second string/list.
For example,
$ (= ”abc” ”abc”)
#t
$ (= ”abc” ”abcdef”)
#f
$ (> ”abc” ”abcd”)
#f
$ (< ”abc” ”abcdef”)
#t
$ (= #t #t)
#t
$ (= #t #f)
#f
$ (= (list) (list))
#t
$ (= (list 1 2 3 4) (list 1 2 3 4))
#t
$ (= (list 1 2 3 4) (list 1 2 3 4 5))
#f
$ (= (list 1 2 3 4 (list)) (list 1 2 3 4 (list)))
#t
$ (= (car (list 1 2 3)) 1)
#t
$ (= (car (list 1 2 3)) 2)
#f
$ (= (cdr (list 1 2 3)) 2)
#f
$ (= (cdr (list 1 2 3)) (list 2 3))
#t
$ (= (cdr (list 1 2 3)) (cdr (list 4 2 3)))
#t
$ (= (cons 0 (list 1 2)) (list 0 (list 1 2)))
#f
$ (= (cons 0 (list 1 2)) (list 0 1 2))
#t
$ (> (list 1 2) (list))
#t
$ (> (list) (list 1))
Spring 2021 page 5 of 3
CS 342 Principles of Programming Languages Homework 5
#f
$ (< (list 1 2) (cdr (list 2 3 4 5)))
#t
Sol.
The logic in this answer can vary, but, be sure to check that the given tests hold. We made the
method isList in PairV al public to use it in the comparison and also created size to return the
size of the list (2 for pairs). Then, we defined the methods equalV alue that checks for equality and
compareV alue which returns 0 for equal, −1 for less and 1 for greater. This logic can change and
perhaps done using just one method.
Value (5 pt):
s t a t i c c l a s s PairVal implements Value {
// make i s L i s t pub l i c
pub l i c boolean i s L i s t ( ) {
i f ( snd i n s t a n c e o f Value . Nul l ) r e turn true ;
i f ( snd i n s t a n c e o f Value . PairVal &&
( ( Value . PairVal ) snd ) . i s L i s t ( ) ) re turn true ;
r e turn f a l s e ;
}
// d e f i n e s i z e
pub l i c i n t s i z e ( ) {
i f ( ! i s L i s t ( ) ) re turn 2 ;
i n t r e s u l t = 0 ;
i f ( ! ( f s t i n s t a n c e o f Value . Nul l ) ) {
r e s u l t += 1 ;
}
Value next = snd ;
whi l e ( ! ( next i n s t a n c e o f Value . Nul l ) ) {
r e s u l t += 1 ;
next = ( ( PairVal ) next ) . snd ;
}
re turn r e s u l t ;
}
}
Evaluator (15 pt):
pub l i c c l a s s Evaluator implements V i s i t o r
pub l i c s t a t i c boolean equalValue ( Value v1 , Value v2 ) {
Spring 2021 page 6 of 3
CS 342 Principles of Programming Languages Homework 5
i f ( v1 i n s t a n c e o f NumVal && v2 i n s t a n c e o f NumVal) {
NumVal f i r s t = (NumVal) v1 ;
NumVal second = (NumVal) v2 ;
r e turn Double . compare ( f i r s t . v ( ) , second . v ( ) ) == 0 ;
} e l s e i f ( v1 i n s t a n c e o f Str ingVal && v2 i n s t a n c e o f Str ingVal ) {
St r ing s1 = ( ( Str ingVal ) v1 ) . v ( ) ;
S t r ing s2 = ( ( Str ingVal ) v2 ) . v ( ) ;
r e turn s1 . equa l s ( s2 ) ;
} e l s e i f ( v1 i n s t a n c e o f PairVal && v2 i n s t a n c e o f PairVal ) {
boolean b1 = equalValue ( ( ( PairVal ) v1 ) . f s t ( ) , ( ( PairVal ) v2 ) . f s t ( ) ) ;
boolean b2 = equalValue ( ( ( PairVal ) v1 ) . snd ( ) , ( ( PairVal ) v2 ) . snd ( ) ) ;
i f ( b1 && b2 ) return true ;
r e turn f a l s e ;
} e l s e i f ( v1 i n s t a n c e o f BoolVal && v2 i n s t a n c e o f BoolVal ) {
re turn ( ( BoolVal ) v1 ) . v ( ) == ( ( BoolVal ) v2 ) . v ( ) ;
} e l s e i f ( v1 i n s t a n c e o f Nul l && v2 i n s t a n c e o f Nul l ){
// l i s t
r e turn true ;
} e l s e {
re turn f a l s e ;
}
}
pub l i c s t a t i c i n t compareValue ( Value v1 , Value v2 ) {
i f ( equalValue ( v1 , v2 ) ) {
re turn 0 ;
}
i f ( v1 i n s t a n c e o f NumVal && v2 i n s t a n c e o f NumVal) {
NumVal f i r s t = (NumVal) v1 ;
NumVal second = (NumVal) v2 ;
r e turn Double . compare ( f i r s t . v ( ) , second . v ( ) ) ;
} e l s e i f ( v1 i n s t a n c e o f Str ingVal && v2 i n s t a n c e o f Str ingVal ) {
St r ing s1 = ( ( Str ingVal ) v1 ) . v ( ) ;
S t r ing s2 = ( ( Str ingVal ) v2 ) . v ( ) ;
r e turn s1 . compareTo ( s2 ) ;
} e l s e i f ( v1 i n s t a n c e o f PairVal && v2 i n s t a n c e o f PairVal ) {
PairVal p1 = ( PairVal ) v1 ;
PairVal p2 = ( PairVal ) v2 ;
i f ( p1 . i s L i s t ( ) && p2 . i s L i s t ( ) ) {
// we d e f i n e a s i z e method in PairVal
re turn I n t e g e r . compare ( p1 . s i z e ( ) , p2 . s i z e ( ) ) ;
} e l s e i f ( ! p1 . i s L i s t ( ) && ! p2 . i s L i s t ( ) ) {
// t h i s case can be omitted in hw
// i f they are both pa i r s ,
// the r e s u l t cannot be app l i ed
Spring 2021 page 7 of 3
CS 342 Principles of Programming Languages Homework 5
return 0 ;
}
}
// d e f a u l t case can be 1 or −1 to d e f i n e d i f f e r e n t
re turn −1;
}
@Override
pub l i c Value v i s i t ( LessExp e , Env env ) { // New f o r func lang .
Value f i r s t = ( Value ) e . f i r s t e x p ( ) . accept ( th i s , env ) ;
Value second = ( Value ) e . second exp ( ) . accept ( th i s , env ) ;
r e turn new Value . BoolVal ( compareValue ( f i r s t , second ) < 0 ) ;
}
@Override
pub l i c Value v i s i t ( EqualExp e , Env env ) { // New f o r func lang .
Value v1 = ( Value ) e . f i r s t e x p ( ) . accept ( th i s , env ) ;
Value v2 = ( Value ) e . second exp ( ) . accept ( th i s , env ) ;
r e turn new BoolVal ( equalValue ( v1 , v2 ) ) ;
}
@Override
pub l i c Value v i s i t ( GreaterExp e , Env env ) { // New f o r func lang .
Value f i r s t = ( Value ) e . f i r s t e x p ( ) . accept ( th i s , env ) ;
Value second = ( Value ) e . second exp ( ) . accept ( th i s , env ) ;
r e turn new Value . BoolVal ( compareValue ( f i r s t , second ) > 0 ) ;
}
}
4. (20 pt) Extend the syntax and semantics of the Funclang language to add support for a switch
expression. The signature of switch-case is following:
(switch (e0)
(case e1 body)
(case e2 body)*
(default body)
)
The switch expression will check whether the value of e0 is equal to the following cases from one by
one. If equal, value of the corresponding body expression is returned as the result. If no matching
is found, the value of the body of default is returned. There must be at least one case clause and
exactly one default. Some examples:
$ (define x 0)
Spring 2021 page 8 of 3
CS 342 Principles of Programming Languages Homework 5
$ (switch (x) (case 0 3) (case 1 4) (case 2 2))
error
$ (switch (x) (case 0 3) (case 1 4) (default 2))
3
$ (define foo (lambda (var) (switch (var) (case 1 (+ var 2)) (case 2 (- var 2)) (case 3 (* var 2)) (case
4 (/ var 2)) (default var))))
$(foo 1)
3
$ (foo 2)
0
$ (foo 3)
6
$ (foo 4)
2
$ (foo 5)
5
Sol.
Found in hw5code-sol.zip.
Files to modify: (The functions or classes that include modification are following):
Grammar file (6pt) Evaluator (10pt) AST (2pt) Printer (2pt)
Grammar file (Funclang.g)
exp r e tu rn s [ Exp as t ] :
. .
| sw=switchexp { $ast = $sw . a s t ; } //added f o r switch
;
switchexp re tu rn s [ SwitchExp as t ]
l o c a l s [ ArrayList
’ ( ’ Switch
’ ( ’ e0=exp ’ ) ’
( ’ ( ’ ’ case ’ e1=exp e2=exp { $ca s e s . add ( $e1 . a s t ) ; $body . add ( $e2 . a s t ) ;
} ’ ) ’ )+
’ ( ’ ( ’ de fau l t ’ e3=exp ) ’ ) ’
’ ) ’ { $ast = new SwitchExp ( $e0 . ast , $cases , $body , $e3 . a s t ) ; }
;
Switch : ’ switch ’ ;
AST.java
pub l i c s t a t i c c l a s s SwitchExp extends Exp {
Exp e0 ;
Spring 2021 page 9 of 3
CS 342 Principles of Programming Languages Homework 5
List
L i s t
Exp e3 ;
pub l i c SwitchExp (Exp e0 , L i s t
e0 = e0 ;
c a s e s = ca s e s ;
body = body ;
e3 = e3 ;
}
pub l i c Exp e0 ( ) { re turn e0 ; }
pub l i c L i s t
pub l i c L i s t
pub l i c Exp e3 ( ) { re turn e3 ; }
pub l i c Object accept ( V i s i t o r v i s i t o r , Env env ) {
re turn v i s i t o r . v i s i t ( th i s , env ) ;
}
}
pub l i c i n t e r f a c e V i s i t o r
// This i n t e r f a c e should conta in a s i g n a t u r e f o r each concre t e AST node .
. . .
pub l i c T v i s i t (AST. SwitchExp e , Env env ) ; //Added f o r switch
Evaluator.java
pub l i c Value v i s i t ( SwitchExp e , Env env ) { // New f o r switch .
NumVal e0 = (NumVal) e . e0 ( ) . accept ( th i s , env ) ;
L i s t
L i s t
NumVal e3 = (NumVal) e . e3 ( ) . accept ( th i s , env ) ;
L i s t
L i s t
f o r (Exp exp : ca s e s )
c a s e v a l u e s . add ( (NumVal) exp . accept ( th i s , env ) ) ;
f o r (Exp exp : body )
body values . add ( (NumVal) exp . accept ( th i s , env ) ) ;
f o r ( i n t i =0; i< c a s e v a l u e s . s i z e ( ) ; i ++){
Spring 2021 page 10 of 3
CS 342 Principles of Programming Languages Homework 5
i f ( c a s e v a l u e s . get ( i ) . v ( ) == e0 . v ( ) ){
re turn body values . get ( i ) ;
}
}
re turn e3 ;
}
Printer.java
pub l i c S t r ing v i s i t (AST. SwitchExp e , Env env ) {
St r ing r e s u l t = ”( switch ( ” ;
r e s u l t+= e . e0 ( ) . accept ( th i s , env ) + ” ) ” ;
L i s t
L i s t
i n t num decls = ca s e s . s i z e ( ) ;
f o r ( i n t i = 0 ; i < num decls ; i++) {
r e s u l t += ” ( case ” ;
r e s u l t += cas e s . get ( i ) + ” ” ;
r e s u l t += body . get ( i ) . accept ( th i s , env ) + ” ) ” ;
}
r e s u l t +=” ( d e f a u l t ” ;
r e s u l t += e . e3 ( ) . accept ( th i s , env ) + ” ) ” ;
r e turn r e s u l t + ” ) ” ;
}
Spring 2021 page 11 of 3