\documentclass{article}
\usepackage{graphics}
\usepackage{fancyheadings}
\usepackage{url}

\newcommand{\coursenumber}{131}
\newcommand{\coursetitle}{Principles of Programming Languages}

\topmargin  18pt        % 27pt
\headheight 12pt        % 12pt
\headsep    35pt        % 45pt
\textheight 8.0in
\textwidth  6.2in

\oddsidemargin   22pt      % Left margin on odd-numbered pages.
\evensidemargin  22pt      % Left margin on even-numbered pages.
\marginparwidth  72pt       % Width of marginal notes.
\marginparsep    11pt      % Horizontal space between outer margin and 
                           % marginal note

\pagestyle{fancy}
\lhead{CSCI \coursenumber}
\chead{}
\rhead{\semester}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\setlength{\headrulewidth}{0pt}
\setlength{\footrulewidth}{0pt}

\newcommand{\semester}[0]{
     \ifnum\month>7{Fall}\fi
     \ifnum\month<8{Spring}\fi\  \number\year
}

\begin{document}

\begin{center}{\Large Homework 1}\\ \vspace{1 ex} Due midnight,
Thursday, 9/11/2014 \end{center}

\vspace{2 ex}
\noindent
Please turn in your homework solutions online at  
\texttt{http://www.dci.pomona.edu/tools-bin/cs131upload.php}
by the due date. 

\vspace{2 ex}


\begin{enumerate}
    
    \item (9 points) \textbf{Partial and Total Functions}
    
    For each of the following function definitions, give the graph of
    the function.  (See the text for a definition of graph -- a set of
    ordered pairs, NOT a picture!)  Say whether this is a partial
    function or a total function on the integers.  If the function is
    partial, say where the function is defined and undefined.

    For example, the graph of \texttt{f(x) = if x > 0 then x + 2 else
    x/0} is the set of ordered pairs $\{\langle x, x + 2 \rangle\ |\ x > 0\}$.
    This is a partial function.  It is defined on all integers greater
    than 0 and undefined on integers less than or equal to 0.

    Functions:
    \begin{enumerate}
        \item \texttt{f(x) = if x + 2 > 3 then x + 5 else x/0} 
        \item \texttt{f(x) = if x < 0 then 1 else f(x - 2)} 
        \item \texttt{f(x) = if x = 0 then 1 else f(x - 2)} 
    \end{enumerate}
    
       \item (20 points) \textbf{Deciding Simple Properties of Programs}
    
    Suppose you are given a (\emph{magical}) function $\texttt{Halt}_{\emptyset}$ 
    that works with Java (or your favorite Turing-complete language) programs as follows.  
    $\texttt{Halt}_{\emptyset}$ takes as input a string representing an arbitrary
    program $P$ written in programming language L, and that requires no input.
    
    \begin{itemize}
    \item $\texttt{Halt}_{\emptyset}(P)$ returns true if program $P$ will
    halt without reading any input when executed.

    \item $\texttt{Halt}_{\emptyset}(P)$ returns false if program P will not
    halt when executed with no input.
    \end{itemize}

    You should not make any assumptions about the behavior of
    $\texttt{Halt}_{\emptyset}$ on arguments that do not consist of a
    syntactically correct program.
    
    \begin{enumerate}
    \item Show how to solve the (regular) halting problem using
    $\texttt{Halt}_{\emptyset}$.  More specifically, write a
    program \texttt{Halt} that reads a program text $P$ as input,
    reads a single integer $n$ as input, and then decides whether or not $P$ halts
    when it reads $n$ as input.  Such a \texttt{Halt} program would
    have the following form, and it would print �yes� if $P$ halts
    when it runs and reads input $n$ and �no� if $P$ does not halt
    when it runs and reads input $n$.

    \begin{verbatim}
	P = readString(); 
	n = readInteger(); 
	...
    \end{verbatim}
    You may assume that any program P you are given begins with a read
    statement that reads a single integer from standard input.  Thus P
    has the form

    \begin{verbatim}
	x = readInteger(); Q
    \end{verbatim}
    where $Q$ is the rest of the program text, and $Q$ does not
    perform any input.  
    
    Explain your solution by describing how a program solving the halting
    problem would work.  To do this, just describe what replaces
    \ldots in the \texttt{Halt} program definition above -- there is
    no need to write the program out fully.  
    
    \emph{Hint:  Remember the key is to start with a possible input P and n
    for the halting problem and to modify the program P to a program P' (whose
    text depends on both P and n) and show that using $\texttt{Halt}_{\emptyset}(P)$
    on P' will determine whether the original program P will halt on n.}
    
    \item  On the basis of the previous part, explain why $\texttt{Halt}_{\emptyset}$
    could not be written in Java (or again, any other Turing-complete language).
    \end{enumerate}
    
    \item (10 points) \textbf{Background} 
    
    Consider the compiler-based programming language that you have
    used the most.  Answer the following questions about it:

    \begin{enumerate}
        \item Describe two programming errors that the compiler
        identifies and reports while compiling a program in that
        language.

        \item Describe two programming errors that can cause your
        program to halt with an error message or crash after you
        compile and start to run it.

        \item What do you find to be the most difficult aspect of
        writing and debugging programs in that language?

        \item Does the language have any features that you rarely or
        never use?  If so, why do you not use them?
    \end{enumerate}

    
    \item (20 points) \textbf{Grace} 
    
    Read the Grace papers on the CS131 ``LInks to useful information''
    web page before attempting the following programs.  Use the Grace
    Draft Specification as a reference.
    
    The simplest way to run Grace programs is to use the minigrace 
    compiler that emits javascript code.  It can be obtained by 
    loading the web page at 
    \url{http://www.cs.pomona.edu/~kim/minigrace/}.
    I strongly urge you to use Firefox for this as different browsers
    render the pages differently and the software has been tested
    most extensively in Firefox.
    
    Start a new program by clicking on the green "New" button,
    and give it a name ending with ".grace".  Please use the names 
    suggested in the problem for the file so that we can easily test
    them.  While you should write test code for your programs,
    they should go in a separate file that you may name as you like.
    However, we will be using our own test code for your programs
    and it will expect your files and classes, methods, etc. to have
    exactly the names and types specified in the problem.  You will
    lose points if your code does not follow those conventions.
    
   Type your program in the editor pane in the top right
   portion of the window.  You can compile it by clicking on the
   "Build" button just below the editor pane.  When it changes to
   "Run", click on that to run your program.
   
   If you wish to load an existing program, click on "Upload"
   and select the file you wish to load.  To save your program
   right-click (e.g., on the Mac hold down the "control" key and press)
   the "Download" button.  From the pop-up menu, select "Save Link As ..."
   and then navigate to where you want to save your program.
   Be sure the name is correct before you click "save".
    
    Output from your program appears in the bottom right pane
    in the window (just below the build/run button).  
    Error messages appear in the same box.
       
    \emph{Warning:}  Minigrace files may not contain tabs.  The only 
    white spaces allowed are spaces and returns (generated by the 
    ``enter'' key).  You will receive error messages if your file 
    contains any other white space.
    
    \begin{enumerate}
        \item 
	Write a Grace program that defines a class representing
        mutable (updatable) sets of Numbers.  Your sets should
        implement the following type:
        \begin{verbatim}
    type NumberSet = {
        contains(n:Number) -> Boolean
        add(n:Number) -> Done
        union(s:NumberSet) -> Done
        intersection(s:NumberSet) -> Done
        isEmpty -> Boolean
        asString -> String
        do(action) -> Done
    }
        \end{verbatim}
	Notice that the operations \texttt{add}, \texttt{union}, and 
	\texttt{intersection} all modify the existing set rather than 
	create a new one.  Please name the file \texttt{Sets.grace}.  Your
	class should be named \texttt{aSet.new}, take no parameters,
	and should construct an empty list.
	
        Grace actually has a library to represent sets, but I don't want
        you to use it.  Your implementation should use an immutable list (use our
        implementation from class -- available on the class web page)
        as an instance variable to hold the elements of the list.  (Do
        NOT inherit from it.)  Remember that sets do not have duplicates
        of elements, so your list implementation should not include
        duplicates.
        
        Show that your program works by
        building a couple of sets, exercise the operations (showing
        corner cases work) and printing the results.
	
	\emph{Because this program represents mutable sets, there is 
	no need for separate representations for empty and non-empty 
	sets.  Those variations will be taken care of by the list 
	instance variable.}
        
        \item Write a Grace program that represents a tree holding 
        a number at each vertex.  I suggest that you emulate the 
        implementation of lists from class (remember that Grace does 
        not have a null element!).  Here is the type of the tree (and a
        type for arguments of the methods):
        \begin{verbatim}
        
     type UnaryFunction<T> = {
        apply(n:Number) -> T
     }

     type Tree = {
         size -> Number
         height -> Number
         isEmpty -> Boolean
         map(blk:UnaryFunction<Number>) -> Tree
         doInorder(blk:UnaryFunction<Done>) -> Done
      }
  \end{verbatim}
  
         Your program should define an empty tree object named \texttt{emptyTree}
         and contain a class \texttt{aTree.root(n:Number)left(l:Tree)right(r:Tree)}
         that constructs a new class with root \texttt{n} and left and right subtrees
         given by \texttt{l} and \texttt{r}.  Place your code in a file named
         \texttt{Trees.grace}
         
         As you can see from the operations in the type, the tree is immutable.
         
         As usual, write and include code to test it in a separate file.  In particular, build an 
         interesting tree \texttt{myTree} and then execute
         \begin{verbatim}
             myTree.doInorder {n -> print (n)}
             var count:Number := 0
             myTree.doInorder {n -> count := count +1}
             print(count)
         \end{verbatim}   
    
    \end{enumerate}
    

    
\end{enumerate}

\end{document}