Computer Science 3675
Summer 2001
Answers to practice questions for quiz 2

  1. Write a clearly legible T to the left of each of the following that is true, and a clearly legible F to the left of each that is false.
    1. Pattern matching can be used to bind names by solving simple equations. true
    2. Sometimes a pattern match can fail. true
    3. In C++, every block begins at the start of a function, and ends at the end of the function. false

  2. What is shadowing, and how can it occur? Give an example.

    Shadowing occurs when one binding takes precedence over another, making the former binding invisible. Shadowing puts a hole in the scope of a binding.

  3. Given the definition 
          f([])   = []
      f(h::t) = (h*h)::f(t)  when h > 10
      f(h::t) = f(t)         when h <= 10
    show an inside-out evaluation of expression f([4,12,15,6,11]). Assume that arithmetic is done as soon as possible. 
        f([4,12,15,6,11]) = f([12,15,6,11])      (since 4 <= 10)
                      = 144::f([15,6,11])    (since 12 > 10 and 12*12=144)
                      = 144::225::f([6,11])  (since 15 > 10 and 15*15=225)
                      = 144::225::f([11])    (since 6 <= 10)
                      = 144::225::121::f([]) (since 11 > 10 and 11*11=121)
                      = 144::225::121::[]
                      = 144::225::[121]
                      = 144::[225,121]
                      = [144,225,121]
    Remarks. Be sure to follow the rules exactly. Do not forget about the [] at the end.

  4. Write an equational definition of a function called smallest so that smallest(n,x) is the smallest member of list n::x. For example, smallest(3, [6,4,7]) = 3 and smallest(8, [2,5]) = 2. You may presume that you have a function called min that takes the minimum of two numbers. For example, min(7,4) = 4. Here are two solutions.

    Definition 1: does not use min. 

        smallest(n,[])   = n
    smallest(n,h::t) = smallest(n,t) when n <= h
    smallest(n,h::t) = smallest(h,t) when n > h

    Definition 2: uses min. 

        smallest(n,[])   = n
    smallest(n,h::t) = smallest(min(n,h),t)

  5. In a purely functional language, is it ever possible to compute the same expression twice in the same context and get different values? For example, if E is an expression, and you compute E two times, one right after another, could the first computation yield a different result from the second computation? Why or why not?

    Two evaluations of the same expression in the same context must always yield the same value. This is because there are no variables that can be changed.