CSc 262   Test 3   Wednesday  12 November 1997

 Closed book, closed notes.  Suggested answers available after test.

 1. (40 pts)  Below is a Pascal program to list the moves in solving
  the Towers of Hanoi problem.  Certain statements in the program have
  comment numbers (appearing inside (*  *) ) along with the address
  where the code generated by the compiler for the statement begins.
  Assume that the stack for the activation records starts at address
  8000, that every entry on the stack takes one memory location on
  the stack, and that the stack pointer increases as items are pushed
  on the stack.  Show the status of the stack and state the value of
  EP and SP when the call HANOI(3,2,1) is about to execute after the
  following calling sequence in the execution of the program:
  --(*6)-->HANOI(5,1,3)--(*4*)-->HANOI(4,2,3)--(*2*)-->HANOI(3,2,1)
  where the comment numbers indicate the statement where the call was
  made.  Whenever possible, you should enter the appropriate number
  in the stack entry: the address of a statement, the value of a
  variable, etc.

          PROGRAM ONE;
            PROCEDURE HANOI(DISKS,FROMPOST,TOPOST:INTEGER);
             BEGIN
              IF DISKS>0                                     (*1  1982*)
               THEN
                BEGIN
                 HANOI(DISKS-1,FROMPOST,6-FROMPOST-TOPOST);  (*2  2000*)
                 WRITE(FROMPOST,'--->',6-FROMPOST-TOPOST);   (*3  2034*)
                 HANOI(DISKS-1,6-FROMPOST-TOPOST,TOPOST);    (*4  2042*)
                    ;   (*EMPTY STATEMENT*)                  (*5  2052*)
                END;
             END;
           BEGIN
            HANOI(5,1,3);                                    (*6  1390*)
            WRITELN('DONE');                                 (*7  1400*)
           END.
  To further clarify the comments, note that the HANOI is called in the
  main program at statement labeled 6 and its code starts in memory at
  1390, HANOI is called from HANOI at statement 2, code starting at 2000,
  and at statement 4, code starting at 2042.


              8021 IP                        SP=8022
              8020 TOPOST       1            EP=8016
              8019 FROMPOST     2
              8018 DISKS        3
              8017 SL        8000
              8016 DL        8010
              8015 IP        2034
              8014 TOPOST       3
              8013 FROMPOST     2
              8012 DISKS        4
              8011 SL        8000
              8010 DL        8004
              8009 IP        2052
              8008 TOPOST       3
              8007 FROMPOST     1
              8006 DISKS        5
              8005 SL        8000
              8004 DL        8000
              8003 IP        1400
              8002 HANOI     1942
              8001 SL        ????
              8000 DL        ????



  2. (10 pts)  Discuss the difference(s) between the Static Link (SL)
  and the Dynamic Link (DL).

    The dynamic link points to the base address of the activation
    record of the function or procedure that called the current function
    or procedure (or main program).  The static link points to the base
    address of the activation record of the procedure or function (or
    main program) where the current procedure or function is defined.

  3. (15 pts)  Discuss the various ways to represent real numbers in
  ADA.
     There are three ways. FLOATs are predefined by the compiler, usually
     taking into account the architecture of the machine on which the
     compiler is running.  A "floating-point type" allows the user to
     specify the (minimum) precision of the numbers and their range and
     has the syntax
      type <identifier> is digits <int value> range <value>..<value>.
     A "fixed-point type" allows the user to specify the absolute error
     and range and has the syntax
      type <identifier> is delta <value> range <value>..<value>
     where the <value> following deltas specifies the absolute error.


  4. (15 pts)  Explain the "if" construct in ADA.  Discuss the advantages
  and drawbacks of the construct.

   The "if" construct has the following syntax
                                     *
       if <condition> then <statement>              * *
                [elseif <condition> then <statement> ]        *
                                             [else <statement> ] endif
   It differs only slight from Pascal in having the elseif construct.
   The latter construct makes for more readable if statements when a
   number of alternatives are being programmed.  The endif is an example
   of "fully bracketed syntax."  It eliminates the "dangling else" problem.


  5. (20 pts)  Explain what is meant by the problems of "overlapping
  definitions" and "indiscriminate access."  Explain how packages
  ameliorate these problems.

     Overlapping definitions refers to the problem of giving a number
     of procedures access to data unnecessarily so that pairs of
     procedures may share data.  For example, if procedures A and B
     need to share data X, and procedures B and C need to share data Y,
     then many languages only allow A and B to share all data or none,
     which means that A and B would have to share X and Y, even though
     A does not need access to X.  Packages eliminate the problem by
     allowing the user to create separate packages for X and Y, say PX
     and PY.  Then procedure A would usp PX, procedure B would use PX
     and PY, and procedure C would use PY.

     Indiscriminate access refers to giving a procedure access to more
     information than necessary, often the implementation details of a
     structure.  With packages, the details of a type or a function can
     be hidden in the private part of the specification or in the
     implementation, thus eliminating access of this information by the
     users of the package.  Users get access to what they need via
     functions and procedures defined in the package.