8   Qualifying Exam in Programming Languages and Compilers
                  _U_n_i_v_e_r_s_i_t_y _o_f _W_i_s_c_o_n_s_i_n
                         Fall 1988

9
_I_n_s_t_r_u_c_t_i_o_n_s

This exam contains seven questions, divided into two  parts.
All  students  taking  the exam should answer _a_l_l _f_o_u_r ques-
tions in Part I.  The answers to  these  questions  will  be
collected  after  two  hours.   Students  taking the exam to
satisfy the depth requirement will have  an  additional  two
hours to answer _a_l_l _t_h_r_e_e questions in Part II.

 If you are unable to provide a complete solution to a ques-
tion,  you  can earn partial credit by explaining techniques
for solving such problems, relating these problems to  known
similar  problems,  _e_t_c, so please give your best answer for
the required number of questions.


9
                           Part I



_Q_u_e_s_t_i_o_n _1

(a)  Explain what is meant by static and dynamic scoping  of
     non-local variables.  Give examples that illustrate the
     difference.

(b)  Outline how non-locals  are  accessed  at  run-time  in
     statically scoped languages.

(c)  Outline how non-locals  are  accessed  at  run-time  in
     dynamically scoped languages.

(d)  How can a programmer using a statically scoped language
     simulate  dynamic  scoping?  Can this technique also be
     used by the compiler for a dynamically scoped  language
     to  implement  access  to non-local variables?  If yes,
     compare  this  technique  with  the  technique(s)   you
     described in part (c).


_Q_u_e_s_t_i_o_n _2

A context-free grammar is said to be in Chomsky Normal  Form
if it contains only productions of the form




9







                           - 6 -


        @A~ ->~ a@               @|1@@A@ a nonterminal, @a@ a terminal
        @B~ ->~ C~ D@            @/1@@B@, @C@, @D@ nonterminals

9
(a)  Let G be any  context-free  grammar  that  contains  no
     lambda-productions (also known as epsilon productions).
     Can G always be rewritten into an  equivalent  context-
     free grammar in Chomsky Normal Form?
9
(b)  Let G be any context-free  grammar  in  Chomsky  Normal
     Form,  and  x  any  string of terminal symbols.  Give a
     general parsing algorithm that can parse x under G.


_Q_u_e_s_t_i_o_n _3

(a)  Pascal allows the type constructor, set of T,  where  T
     is  an  enumeration  or  subrange type.  Typically, the
     enumeration or subrange that T represents is restricted
     to  a  bounded number of values such as 32 or 64.  Sug-
     gest how such sets might be represented in memory.  How
     are in, + (union), and * (intersection) implemented?
9
(b)  Assume we generalize the set constructor so that a  set
     of _a_n_y enumeration or subrange is allowed.  Thus set of
     integer would be legal.   Suggest  how  these  extended
     sets might be represented in memory.  Now how are in, +
     (union), and * (intersection) now implemented?
9
(c)  Assume we generalize the  set  constructor  further  so
     that  sets of records and arrays are now allowed.  Thus
     set of array[1..10] of integer would be legal.  Suggest
     how these extended sets might be represented in memory.
     How are in, +  (union),  and  *  (intersection)  imple-
     mented?





_Q_u_e_s_t_i_o_n _4

(a)  What is boolean short circuiting?  Why is it desirable?
9
(b)  Write a procedure that generates code for short-circuit
     evaluation  of  boolean expressions.  The inputs to the
     procedure are: (1) an abstract-syntax tree  representa-
     tion  of  the  expression;  (2)  the  label to which to
     branch if the expression evaluates  to  true;  (3)  the
     label to which to branch if the expression evaluates to


9







                           - 7 -


     false.  Internal tree nodes contain  boolean  operators
     (_n_o_t, _a_n_d, _o_r); leaf nodes contain variable names.  The
     instruction set is as follows:

         branch_true         @|1@<var name>         @|2@<label>
         branch_false        @/1@<var name>         @/2@<label>
         branch              @/1@<label>
         noop

     Any instruction may be labeled and you may  assume  the
     existence  of  a  function  _n_e_w_l_a_b  that  generates new
     labels.








































9

9







                           - 8 -


                             Part II



_Q_u_e_s_t_i_o_n _5



This question is about _l_a_t_t_i_c_e_s  and  _c_o_n_s_t_a_n_t  _p_r_o_p_a_g_a_t_i_o_n.
Throughout, assume a language with scalar variables, assign-
ment statements, conditional statements, output  statements,
while  loops, and arbitrary gotos (including into and out of
conditionals and loops).  The language does not include pro-
cedures  or  functions.   Also  assume  that the language of
expressions for the right-hand sides of assignment is

"exp"~ ->~integer~roman "|"~ variable~roman "|"~ "exp" ~ + ~ "exp"


 In parts (b)-(d), it may be easier  if  you  think  of  the
nodes  of a program's control flow graph as corresponding to
individual predicates and assignments, rather than as  basic
blocks.   You  may wish to assume the existence of a special
entry node.

(a)  Let @D@ be a lattice with partial  order  @approx@  and
     meet  @meet@.   Let  @x@  and @y@ stand for elements of
     @D@, and let @f@ be a function from @D@ to @D@.

     Function @f@ is _m_o_n_o_t_o_n_i_c  iff  @x  approx  y@  implies
     @f(x) approx f(y)@.  Show that this is equivalent to:

         Function @f@ is monotonic iff @f(x meet y) approx f(x) meet f(y)@


(b)  A stronger  property  than  monotonicity  is  _d_i_s_t_r_i_b_u_-
     _t_i_v_i_t_y, defined as follows:

         Function @f@ is distributive iff @f(x meet y)~=~f(x) meet f(y)@.

     The constant-propagation  problem  computes,  for  each
     program  point, the set of variables guaranteed to have
     constant values and what those values  are.   It  is  a
     classic  example  of a data-flow problem with functions
     that are monotonic but not distributive.

     Define the  constant-propagation  dataflow  problem  by
     (i) defining  a  lattice  @D@  for  the  problem  (_i._e.
     specify the value space, the partial  order,  and  meet
     operation),  and  (ii) giving the functions from @D@ to
     @D@ that are associated with  the  nodes  of  the  flow










                           - 9 -


     graph (see part (c) below).

(c)  Show that (i) each function you defined in part (b)  is
     monotonic,  and  (ii) at  least one of them fails to be
     distributive.

(d)  Give an example program and its control flow graph that
     demonstrates   how  non-distributivity  contributes  to
     imprecision; that is, the values  computed  by  solving
     the  program's equations (for the greatest fixed point)
     indicates that at some point @p@ a variable is  noncon-
     stant when in fact it is constant on all paths.  (NOTE:
     in your example, the imprecision must be  due  to  non-
     distributivity  and not simply to some graph paths that
     are infeasible execution paths.)





































9

9







                           - 10 -


_Q_u_e_s_t_i_o_n _6

Consider the iterative algorithm given below for solving the
equations  of  a  forward  data-flow problem.  (Assume flow-
graph nodes are numbered 1 to k, that information  for  node
@i@  is  stored  in  @in@[@i@]  and @out@[@i@], and that the
function associated with node @i@ is @f sub i@.)

for @i@ := 1 to k do
        @in@[@i@] := @top@
        @out@[@i@] := @top@
od
while changes to any @out@ occur do
        for @i@ := 1 to k do
                @in@[@i@] := @top meet {size +4 } from {p member "predecessor set of node i"}~~~out[p]@
                @temp_out@[@i@] := @{f sub i}(in roman "[" i roman "]" )@
        od
        for @i@ := 1 to k do
                @out@[@i@] := @temp_out@[@i@]
        od
od

Assuming that (i) the functions @f sub i@ are monotonic, and
(ii) the  lattice over which the computation takes place has
no infinite descending  chains,  prove  that  the  algorithm
given above computes the greatest fixed point of the associ-
ated set of equations.

























9

9







                           - 11 -


_Q_u_e_s_t_i_o_n _7

This question is about a garbage-collection method known  as
_d_e_f_e_r_r_e_d  _r_e_f_e_r_e_n_c_e  _c_o_u_n_t_i_n_g.   In  a  deferred  reference-
counting scheme,  each  reference  falls  into  one  of  two
categories: _a_c_t_u_a_l _r_e_f_e_r_e_n_c_e_s and _s_h_a_d_o_w _r_e_f_e_r_e_n_c_e_s.  Actual
references are similar to the ordinary references that arise
in  a conventional reference-counting scheme, in that actual
references to a node are reflected in the node's  reference-
count field.  At any given moment (except during collection)
the reference-count field of a node contains the  number  of
actual  references to the node.  All references that emanate
directly from the stack are shadow references; shadow refer-
ences  to  a node are not reflected in the node's reference-
count field.

 Operations that introduce or remove actual references  per-
form the appropriate operation to increment or decrement the
node's (actual) reference count.  For  example,  whenever  a
new  actual  reference to node @n@ is created by a construc-
tion operation, operation rc_incr(@n@)  is  performed.   The
actual   reference   count  of  @n@  is  decremented  by  an
rc_decr(@n@) operation; if rc_decr(@n@) drops  @n@'s  refer-
ence  count  to zero then @n@ is a candidate for reclaiming.
However, it is  not  possible  to  reclaim  @n@  _i_m_m_e_d_i_a_t_e_l_y
because   there  may  be  shadow  references  to  the  node.
Instead, @n@ is placed in the _z_e_r_o-_c_o_u_n_t _s_e_t (a set of loca-
tions  maintained  by the storage manager) and reclaiming is
deferred until the moment when the  zero-count  set  reaches
its  capacity.   Operation  rc_alloc(@n@),  performed  on  a
newly-created node @n@, sets the reference count of the node
to zero and inserts @n@ into the zero-count set.

 When invoked, reclaiming is performed in three stages:

_S_t_a_g_e _1:
     In the first stage, the  stack  is  traversed  and  the
     reference  count is incremented for every shadow refer-
     ence to a node.

_S_t_a_g_e _2:
     The second stage empties the zero-count set; every node
     in  the  zero-count  set whose reference count is still
     zero is immediately reclaimed, together with  all  des-
     cendants  whose  reference  counts  drop  to  zero as a
     result.

_S_t_a_g_e _3:
     In the third stage, the reference count of  every  node
     referred  to from the stack is decremented.  If, in the
     process, a node's reference count drops back  to  zero,
     the node is again inserted into the zero-count set.
9

9







                           - 12 -


(a)  What conditions are guaranteed to hold at  the  end  of
     each of the three stages?

(b)  Explain the advantages and  disadvantages  of  deferred
     reference counting when compared to conventional refer-
     ence counting and the mark-and-sweep  collection  algo-
     rithm.

(c)  Why does rc_alloc(@n@) insert @n@ into  the  zero-count
     set?

(d)  Suppose there is insufficient  information  to  distin-
     guish integers on the stack from pointers on the stack.
     Explain how each of the three steps must be changed  so
     as  to  guarantee  that  no  non-garbage  is  collected
     (although some garbage may remain uncollected).  Do _n_o_t
     devise   a   scheme  for  distinguishing  integers  and
     pointers.


































9

9