CS 3723, Final Exam Answers (Partial), Fall 2013

1. First get a new integer j=next_int() for use in while
Location 0: generate a label, looking like
  WhileStart + j:
  (code to evaluate while expression here, result in offset res=E())
Location 1:
  In MIPS compare location in res with 0
  Code to branch to WhileEnd + j, if res == 0, 
  (code for body of while loop. repeatedly calling S().)
Location 2:
  First a MIPS instruction to branch to WhileStart+j
  Then a label looking like
  WhileEnd + j:

=================================
2. Take off 1/2 point for each mistake
> (car '((a b) c d (e)))
(A B)
> (cdr '(a (b c d)))
((B C D))
> (cdr (car '((a b) c d)))
(B)
> (cons '(a b) '(c))
((A B) C)
> (list '(a) '(b c))
((A) (B C))
> (append '(a) '(b c))
(A B C)
> (cond ((= 6 (* 2 3)) 47)  (t 54))
47

> (defun cubes (n)
   (cond ((= n 1) 1)
         (t (+ (* n n n) (cubes (- n 1)))) ))
> (cubes 5)
225

> (defun addpos (x)
   (cond ((null x) 0)
         ((> (car x) 0) (+ (car x) (addpos (cdr x))))
         (t (addpos (cdr x))) ))
> (addpos '(1 -4 -6 19))
20

;;;;;;;;;;;;;;;;;;;;;; notes about the function:
; If you try to write (cond ( (null l) nil), returning nil for a null list,
; then it becomes one of the "numbers" added up, but Lisp won't let
; you use nil as part of a sum, because "NIL is not a number".
; 
; If you don't have the first condition check ( (null l) 0) at all,
; then again the function tries to add in nil when it gets to the end of the list.
; 
;  ((< (car l) 0) 0) will not work because 0 would be returned by the
; function immediately at that point, without finishing the list.

;;;;;;;;;;;;;;;;;;;;;; here's another longer method:
> (defun drop-negs (l)
   (cond ( (null l) nil)
         ( (< (car l) 0) (drop-negs (cdr l)))
         ( t  (append (list (car l)) (drop-negs (cdr l)))) ))
DROP-NEGS
> (drop-negs '(4 -2 0 -3 1 7 -1))
(4 0 1 7)
> (defun addpos (l)
   (apply '+ (drop-negs l) ))
ADDPOS
> (addpos '(4 -2 0 -3 1 7 -1))
12
=================================
3.
#!/usr/bin/ruby
re = /(\d+)\s+([a-zA-Z]+)/
while line = gets 
   m = re.match(line)
   print m[1], ":" , m[2]
   print "\n"
end

3 a.i.    /(\d+)\s+([a-zA-Z]+)/
  a.ii.   2143:ralph
  a.iii.  print m[0], "\n"
          print m, "\n" # also works

3 b.
#!/usr/bin/ruby
re = /^([a-zA-Z]+)\s+([a-zA-Z]+),\s+"([ a-zA-Z]+)"\s+\([ a-zA-Z]+(\d+)\)$/
while line = gets 
   m = re.match(line)
   if m != nil
      print m[3], " by ", m[2], ", ", m[1], ". Released ", m[4], "."
      print "\n"
   end
end
=================================
4. a.
%!PS-Adobe-2.0
/Times-Bold findfont 50 scalefont setfont
/inch {72 mul} def
/name {
   8.5 inch 2 div % halfway across the page
   (Wagner) stringwidth pop 2 div sub % backup half the lengh of string 
   % x coord now complete
   11 inch 2 div % y coord complete
   % (the y coord can be anything, but here it's halfway up)
   moveto
   (Wagner) show
} def
name
showpage

4 b. Black box 20 pts by 20 points with lower left corner as origin,
     and with white question mark inside.
     (The entire 40 by 40 box is centered at the origin, but all
      except the above is outside the page.)
   
%!PS-Adobe-2.0
/Times-Bold findfont 20 scalefont setfont
/box {
  newpath
  20 20 moveto
  -40 0 rlineto
  0 -40 rlineto
  40 0 rlineto
  closepath
} def

/fillbox {
  box fill
  gsave
    1 setgray % white
    0 0 moveto
    (?) show
  grestore
} def

306 396 translate
-90 rotate
3 3 scale
fillbox
showpage
=================================
5. Carry out the following steps: (which can be illustrated with diagrams)
  1. Calculate actual paramters: The program which which will
call gcd calculates or obtains the actual parameters.
  2. Insert actual parameters into space (on a stack) where the activation
record (AR) will be.  These are inserted as a double values.
  3. Call gcd by doing a jal instruction, to jump to it, which also
saves the return address in the register $ra.
  4. Now the code after the gcd label starts executing.
  5. gcd allocates the activation record (AR) by changing the stack
pointer.  The AR includes the locations where the actual
paramters were placed.  These locations become the formal
parameters for gcd.
  6. gcd inserts the value of the return address into the newly
allocated AR.
  7. gcd does its computation, in this case to calculate the greatest
common divisor of the two formal parameter values.  It might call
itself recursively (which would overwrite the return address in $ra).
  8. When gcd is done, it places the value to be returned into
the AR.
  9. gcd accesses the return address from the AR.
 10. gcd deallocates the AR that it allocated.
 11. As its last action, gcd executes a "jump register" instruction to
the return address.  Thus control passes to the instruction after
the call to gcd.
 12. The function that called gcd can access and retrieve the return
value in the storage where the AR had been.
=================================
6. Readily available

7.  :- does NOT mean "if and only if", and it does NOT mean "then",
  but instead it means "if", or "in case", etc.