Description
1. Frank Rubin used the following exam ple (rewritten here in C)to argue in favorofa goto statem ent:
i n t
f i r s t _ z e r o _ r o w
=
– 1 ;
/ *
a s s u m e
n o
s u c h
r o w
* /
i n t
i ,
j
;
f o r
( i
=
0
;
i
<
n ;
i + + )
{
/ *
f o r
e a c h
r o w
* /
f o r
( j
=
0 ;
j
<
n ;
j + + )
{
/ *
f o r
e a c h
e n t r y
i n
t h e
r o w
* /
}
i f
( A [ i ] [ j ] )
g o t o
n e x t ;
/ *
i f
n o n – z e r o
g o
o n
t o
t h e
n e x t
r o w
* /
f i r s t _ z e r o _ r o w
=
i ;
/ *
w e n t
a l l
t h r o u g h
t h e
r o w ,
y o u
g o t
i t !
* /
b r e a k ;
/ *
g e t
o u t
o f
t h e
w h o l e
t h i n g
* /
}
n e x
t
:
;
/ *
f i r s t _ z e r o _ r o w
i s
n o w
s e t
* /
The intentofthe code is to setfirst_zero_row to the index ofthe firstall-zero row,ifany,ofan n × n
m atrix,or-1 ifno such row exists.Do you find the exam ple convincing? Is there a good structured alternative in C? In any language? G ive answers in the form ofa shortessay.Include a good introductory section,a background section describing views on the goto statem entthroughouthistory,a beefy section analyzing alternatives to Rubin’s problem ,and a good concluding section.Talk aboutsolutions in atleastthree languages.
2. Foreach ofthe following sets ofstrings,write functions orm ethods in two languages chosen from {Python, JavaScript,Java,Ruby,Clojure,C++}to return whethera given string is in the set,using regularexpression m atching.You willlikely find,forsom e ofthe problem s,thatgiving a finite state m achine forthe setis helpful. You m ay include a diagram ofyourm achine in yoursubm ission butitwillnotaffectyourgrade.
a. Strings ofcharacters beginning and ending with a double quote character,thatdo notcontain control characters,and forwhich the backslash is used to escape the nextcharacter.(These are sim ilarto,but notexactly the sam e as,string literals in C.)
b. The paren-starform ofcom m ents in Pascal:strings beginning with (* and ending with *) thatdo not contain *).Note com m ents “don’tnest”.
c. Num bers in JSO N.
d. Allnon-em pty sequences ofletters otherthan “read”,”red”,and “real”.
3. W rite a tail-recursive function to com pute the m inim um value ofan array in Python,C,JavaScript,and G o. O bviously these languages probably already have a m in-value-in-array function in a standard library,butthe purpose ofthis problem is foryou to dem onstrate yourunderstanding oftailrecursion.Yoursolution m ustbe in the classic functionalprogram m ing style,thatis,itm ustbe stateless.Use param eters,notnonlocal variables,to accum ulate values.
4. Here’s som e code in som e language thatlooks exactly like C++.It’s sortoflike G o,also,exceptthe pointer types are kind ofbackwards.Itis defining two m utually recursive types,A and B.
https://cs.lmu.edu/~ray/classes/pl/assignment/5/ 1/4
1/30/2014
CM SI386:Programming Languages:Homework #5
s t r u c t
A
{ B *
x ;
i n t
y ; } ;
s t r u c t
B
{ A *
x ;
i n t
y ; } ;
Suppose the rules forthis language stated thatthis language used structuralequivalence fortypes.How would you feelifyou were a com pilerand had to typecheck an expression in which an A was used as a B? W hatproblem m ightyou run into?
5. W rite a program in C++,JavaScript,Python,Ruby,Scala,orClojure thatdeterm ines the orderin which subroutine argum ents are evaluated.
6. Considerthe following (erroneous)program in C:
v
o
i
d
f
o
o
(
)
{
i
n
t
i
;
}
p r i n t f ( ” % d
” ,
i + + ) ;
i
n
t
m
a
i
n
(
)
{
i
n
t
j
;
}
f o r
( j
=
1
;
j
< =
1 0
;
j + + )
f o o ( ) ;
Localvariable i in subroutine foo is neverinitialized.O n m any system s,however,the program willdisplay
repeatable behavior,printing 0 1 2 3 4 5 6 7 8 9 .Suggestan explanation.Also explain why the behavioron othersystem s m ightbe different,ornondeterm inistic.
7. Considerthe following pseudocode:
v a r
x
=
1
0
0 ;
f u n c t i o n
s e t X ( n )
{ x
=
n ; }
f u n c t i o n
p r i n t X ( )
{ c o n s o l e . l o g ( x ) ; }
f u n c t i o n
f o o ( S ,
P ,
n )
{
v a
r
x
;
i f
( n
= = =
1
| |
n
= = =
3
)
{ s e t X ( n ) ; }
e l s e
{ S ( n ) ; }
i f
( n
= = =
1
| |
n
= = =
2
)
{ p r i n t X ( ) ; }
e l s e
{ P ( ) ; }
}
s e t X ( 0 ) ;
f o o ( s e t X ,
p r i n t X ,
1
) ;
p r i n t X ( ) ;
s e t X ( 0
) ;
f o o ( s e t X ,
p r i n t X ,
2
) ;
p r i n t X ( ) ;
s e
t
X
(
0
)
;
f
o
o
(
s
e
t
X
,
p
r
i
n
t
X
,
3
)
;
p
r
i
n
t
X
(
)
;
s
e
t
X
(
0
)
;
f
o
o
(
s
e
t
X
,
p
r
i
n
t
X
,
4
)
;
p
r
i
n
t
X
(
)
;
Assum e thatthe language uses dynam ic scoping.W hatdoes the program printifthe language uses shallow binding? W hatdoes itprintwith deep binding? W hy?
8. In som e im plem entations ofan old language called Fortran IV,the following code would printa 3.Can you suggestan explanation? (Hint:Fortran passes by reference.)M ore recentversions ofthe Fortran language don’thave this problem .How can itbe thattwo versions ofthe sam e language can give differentresults even though param eters are officially passed “the sam e way”? Note thatknowledge ofFortran is notrequired for this problem .
c
a
l
l
f
o
o
(
2
)
p
r
i
n t
*
2
s
t
o
p
e
n
d
s u b
r o
u t
i n
e
f o o ( x )
x
=
x
+
1
e
n
d
r
e
t
u
r
n
https://cs.lmu.edu/~ray/classes/pl/assignment/5/
2/4
1/30/2014 CM SI386:Programming Languages:Homework #5
9. Considerthe problem ofdeterm ining whethertwo trees have the sam e fringe:the sam e setofleaves in the sam e order,regardless ofinternalstructure.An obvious way to solve this problem is to write a function fringe thattakes a tree as argum entand returns an ordered listofits leaves.Then we can say
d e f
s a m e _ f r i
n
g
e
(
t
1
,
t
2 )
:
r e t u r n
f
r
i
n
g
e
(
t
1 )
=
=
f r i n g e ( t 2 )
a. W rite a straightforward version offringe in Python orJavaScript.
b. G iven yourstraightforward code in part(a),how efficientis same_fringe when the trees differin their firstfew leaves?
c. Ifyou answered part(b)correctly,you know thatwhatyou need forefficiency is laziness.W rite an efficient(lazy)version ofsame_fringe in Python.
d. W rite an efficient(lazy)version ofsame_fringe in JavaScriptorG o.
10. Explain whatis printed under(a)callby value,(b)callby value-result,(c)callby reference,(d)callby nam e.
x
=
1
;
y
=
[
2
,
3
,
4
]
;
s u b
f ( a ,
b )
{
b
+ + ;
a
=
x
+
1 ; }
f
(
y
[
x
]
,
x
)
;
p
r
i
n
t
x ,
y
;
11. I’ve written a sim ple JavaScriptqueue type thatdoes notuse encapsulation.Can we achieve encapsulation using the m odule system in node.js? Ifso,im plem entit.Ifnot,state why not.
12. Itis certainly possible to m ake a Person class,then subclasses ofPerson fordifferentjobs,like M anager, Em ployee,Student,M onitor,Advisor,Teacher,O fficerand so on.Butthis is a bad idea,even though the IS-A testpasses.W hy is this a bad idea and how should this society ofclasses be built?
13. W rite in Java,Python,JavaScript,and C++,a m odule with a function called nextOdd (ornext_odd or next-odd depending on the nam ing conventions ofthe language’s culture.The firsttim e you callthis subroutine you getthe value 1.The nexttim e,you geta 3,then 5,then 7,and so on.Show a snippetofcode thatuses this subroutine from outside the m odule.Is itpossible to m ake this m odule hack-proof? In other words,once you com pile this m odule,can you be sure thatm alicious code can’tdo som ething to disruptthe sequence ofvalues resulting from successive calls to this function?
14. W hathappens to the im plem entation ofa class ifwe “redefine”a field in a subclass? Forexam ple,suppose we have:
c l a s s
F o o
{
p u b l i c
i n t
a ;
p u b l i c
S t r i n g
b ;
}
. . .
c l a s s
B a r
e x t e n d s
F o o
{
p u b l i c
f l o a t
c ;
p u b l i c
i n t
b ;
}
Does the representation ofa Bar objectcontain one b field ortwo? Iftwo,are both accessible,oronly one? Underwhatcircum stances? AnswerforC++,Java,and Python.
