Assignment 11, Solutions

Part of the homework for 22C:60, Fall 2010
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Homework

  1. Background: Here is the description of a logic circuit in purely equational terms:
    inputs: a and b
    outputs: e and f
    intermediate values: c and d
    c = a + b
    d = ab
    e = cf
    f = d + e

    a) Draw the logic circuit in schematic form with the inputs on the left and outputs on the right. (0.5 points)

    b) Draw a timing diagram for this circuit showing how the outputs change as the inputs move through the following sequence of 13 changes: (0.5 points)
      [a,b] = [0,0],[0,1],[0,0],[1,0],[1,1],[1,0],[0,0],[1,0],[1,1],[0,1],[1,1],[1,0],[0,0]

    logic diagram and timing diagram

    The topology of the diagram given for part a only appears natural after answering part c, realizing that it is an RS flipflop of some kind, and then redrawing it with the logic gates arranged as they are in an RS latch. First attempts to answer part a would typically be topologically equivalent to the answer given, but with different layouts.

    c) Is this circuit a kind of flipflop? If so, what input combination causes it to remember a value, how do you set it, and how do you reset it?

    Yes. To set the outputs e and f to one, put a one on the a input and apply a positive pulse to the b input. To reset the outputs e and f to zero, put a zero on the a input and apply a positive pulse to the b input.

    In effect, this is a type D latch, with a as the data input, b as the clock input, e as the Q output, and f as an inverted Q output, which is to say, e and f will tend to stay identical, except during the set and reset operations, at which time they may differ briefly.

  2. Background: The solution to MP4 distributed on line doesn't contain any checking for errors. If the input string were "zuuuuuuuuuuuuuuu*", for example, it will try to put an asterisk fifteen lines above the top of the screen, probably resulting in a bus trap error. If the input string contains unbalanced parentheses, such as "((((((((((", things also begin to go wrong.

    An obvious way to deal with such errors is to raise an exception when the interpreter discovers something irregular. It would be easy, for example, to check, before outputting a character, to see if the x and y coordinates are on the screen, and raise an exception if not.

    a) Where should the handler be? (0.5 points)

    In the main program, or in whatever code calls the code to interpret strings in this language.

    b) What would you check for, and where in the code, to detect unbalanced parentheses as illustrated above? Hint: There is no need to count the parentheses. (0.5 points)

    If you use an explicit stack for begin and end paren, you can check that the stack pointer is zero when you hit a null and make sure it never goes negative. In effect, the stack pointer is the parenthesis pointer.

    If you use recursion to handle parentheses, you can check to see how string terminates. If the first call to the interpreter terminates with an end paren, there were too many end parens. If a recursive call terminates with a null, there were too many begin parens.

  3. Background: Look at the code in Chapter 13 for raising an exception in the general case. Suppose a program includes error checks that raise large numbers of different exceptions. Duplicating different versions of this 4-instruction block of code each time an exception is raised seems wasteful.

    A Problem: Suggest a way to compact the code for raising exceptions by putting most of the code in one place with just one or two instructions that must be duplicated in each place the exception is raised. Your code might take one or two extra instructions to raise an exception, but it should be more compact if there are enough exceptions raised in the program. (0.5 points)

    First, put this code somewhere:

    RAISE_EXCEPTION:
            LOAD    R2,R1,EXAR      ; AR = exception.exar
            LOAD    R1,R1,EXHAND
            JUMPS   R1              ; PC = exception.exhand
    

    Now, wherever you want to raise a constraint error exception, put this code:

            LIL     R1,CONSTRAINT_ERROR
            JUMP    RAISE_EXCEPTION
    

    Or if there are many constraint error and stack overflow exceptions being raised, in many parts of the program, put this code somewhere:

    RAISE_CONSTRAINT_ERROR:
            LIL     R1,CONSTRAINT_ERROR
            BR      RAISE_EXCEPTION
    RAISE_STACK_OVERFLOW:
            LIL     R1,STACK_OVERFLOW
    RAISE_EXCEPTION:
            LOAD    R2,R1,EXAR      ; AR = exception.exar
            LOAD    R1,R1,EXHAND           
            JUMPS   R1              ; PC = exception.exhand

    Now, to raise a constraint error, you just use:

            JUMP    RAISE_CONSTRAINT_ERROR