CIS 252   —   SPRING 2008

INFORMATION ON QUIZ 6

When: Tuesday, April 29 in class.

How: Closed book, closed notes.

Coverage: Haskell: The Craft of Functional Programming, Chapters 1–18 and The New Turing Omnibus, Chapter 31, by A.K. Dewdney.

Along with the topics from Quiz 5, you should be familiar with the following basic topics.

• You should understand the following notions and be able to provide a definition and/or example:
  • anonymous functions
  • higher-order functions
  • currying and uncurrying
  • overloading
  • polymorphism & polymorphic types (Know the difference between overloading & polymorphism!)
• You should be familiar with the following built-in Haskell functions/constructs:
  • concatMap
  • filter
  • foldr
  • getChar
  • getLine
  • map
  • print
  • putChar
  • putStr
  • return (as part of the do notation)
  • the do notation
  • zip
  • zipWith
  • . (function composition)
• You should be familiar with Turing machines:
  • Be able to determine how a given Turing machine behaves on a given input.
  • Be able to write a Turing machine to do something.
  • Be able to translate a table description of a TM into a state-transition diagram, and vice versa.

Click here for answers to the questions below

Some Questions from Last Year

1. (8 points) Consider the following Turing machine:

   flip2 :: Prog
   flip2 = [
            (("A",'0'), ('0',Rght,"B0")),
            (("A",'1'), ('1',Rght,"B1")),
            (("A",' '), (' ',Lft,"Z") ),
            (("B0",'0'),('0',Rght,"A")),
            (("B0",'1'),('0',Lft,"C1")),
            (("B0",' '),(' ',Lft,"Z") ),
            (("B1",'1'),('1',Rght,"A")),
            (("B1",'0'),('1',Lft,"C0")),
            (("B1",' '),(' ',Lft,"Z") ),
            (("C1",'0'),('1',Rght,"D")),
            (("C0",'1'),('0',Rght,"D")),
            (("D",'0'), ('0',Rght,"A")),
            (("D",'1'), ('1',Rght,"A")),
            (("Z",'0'), ('0',Lft,"Z") ),
            (("Z",'1'), ('1',Lft,"Z") )
           ]
   

   that has the bubble diagram

   

   Assume the initial tape consists of 10010001 and that the tape head starts on the string's leftmost symbol.

   Your Problem: What is the final string on the tape? For full credit, also indicate where the final tape head rests. Assume that the initial tape contains the string 0101000 and that the tape head starts on the leftmost symbol of the string.

   Problem: What is the final string on the tape?

   ---

2. (8 points) Write a Turing machine that takes a nonempty 0-1-string beginning with 1, representing a binary number, and decrements (i.e., subtracts one from) that number. You should assume that the tape head is initially set on the leftmost symbol of the string. The final tape head may rest any old place.

   Give your answer either as a state-transition (bubble) diagram or as a table, whichever you prefer. However, make sure all necessary information is included in whichever format you use.

   Suggestion: Work out a couple examples by hand before writing your Turing machine.

   ---

3. (7 points) Do one of the following two problems. If you try both, indicate which one you want me to grade.

   1. Give a Haskell definition of

         odds :: [Integer]

      which consists of the infinite list of all odd positive integers.

   2. Write a Haskell function

         rep :: Int -> String -> IO ()

      such that (rep n str) results in the String str being printed n-many times when n > 0.. If n ≤ 0, then the empty string is printed (just once).

Here are a few more IO problems

1. Write an interactive Haskell program that calculates the a dog's age in human years (using the not-very-good rule: 1 human year = 7 dog years). That is,

   dogAge :: IO ()

   show prompt the user with the string How old is your dog? and then print the dog's age in human-years. E.g.,

   > dogAge
   How old is your dog? 12
   In human years your dog is 84
   >  
   

   You many use the getInt function from homework 11.

2. Write a Haskell function

    printSuf :: String -> IO () 

   which takes a string str and prints the (nonempty) suffixes of str one per line. For example,

   > printSuf "plum" 
   plum
   lum
   um
   m
   > 
   

3. Write a Haskell function

    printBack :: Int -> IO () 

   such that (printBack n) reads n lines from input and then prints them out in reverse order. If n<1, then nothing is printed. For example, printBack could be used as follows. (The lines in blue are the user's input.)

   > printBack 3
   First line
   second line
   third line
   third line
   second line
   First line 
   

4. Write a Haskell function

    shoutBack :: IO () 

   that reads a line and echoes it back IN ALL UPPER CASE. For example, printBack could be used as follows. (The lines in blue are the user's input.)

   > shoutBack
   how are you?
   HOW ARE YOU?