• Due: 11:00pm Wednesday 9 September [UPDATED from Monday the 7th since I forgot about Labor Day]
  • Submission:
    • Instructions for submitting work can be found in the Mercurial tutorial linked below.
    • Write your answers in a text file called halt-racket.txt and add, commit, and push it to your Bitbucket repository for this assignment.
  • Starter files: fork wellesleycs251 / cs251-halt and add bpw as admin.
  • Relevant reading:
  • Tools:
  • Collaboration: All graded parts of this assignment fall under the standard collaboration policy. You may discuss the problems and strategies for solving them, but your solutions must be your own work. All ungraded parts allow unlimited collaboration.
  • Updated: 6:00pm Thursday 3 September.
    • Added Racket expression practice (will cover in lecture tomorrow) and some clarification in the haltsNoInput problem.

0. Introductions and Tools

This part is required, but not graded.

Introductions

Visit Ben within one week of our first class meeting to introduce yourself and chat for a couple minutes about:

  • your preferred name and pronouns;
  • CS courses you have taken, are taking, or hope to take in the future;
  • excitement, concerns, or questions about this course;
  • anything else you deem conversation-worthy, including one fact about yourself that is not about CS.

Scheduling

Complete the scheduling poll (link coming soon) to help us schedule the best times for office hours with Ben and the tutors.

Tools

The tools you need for this assignment are a text editor, Mercurial (see below), and (optionally) DrRacket. These are all pre-installed on the CS Linux machines and the wx appliance. Please read the tools page for more information.

Mercurial Tutorial

This part is not graded, but you will need it to submit your work.

Complete this Mercurial tutorial up through the Mercurial Solo Basics section. (Complete the rest of the tutorial as needed if you find yourself collaborating on a team assignment.) The sample repository from this tutorial will become your means of submitting this assignment. Future assignments will use separate repositories.

Using Linux Machines or the wx Appliance

If you need a crash course or refresher on using the shell (command line), check out the relevant links on the tools page. For example, try Scott Anderson’s Unix help page. (Ignore the section about drop.) The commands in the latter document are applicable in Linux (in a terminal window) and Mac OS X (in the Terminal application). Scott’s Introduction to Unix and the X Window System says a little bit more about the GUI on the CS Linux machines. You might also find http://linuxsurvival.com/ (modules 1 and 2) helpful.

1. Deciding Properties of Programs1 (10 points)

Travel for a moment to a magical land. Assume you are given the code for a method haltsNoInput. haltsNoInput decides whether a given program halts, but it works only on programs that do not read any input. Can you implement a solution for the general halting problem using haltsNoInput?

To be more precise, assume you are given an implementation of a Java method boolean haltsNoInput(String p) that takes a string representation of the source code of a program, p, and returns a boolean, with the following behavior:

  • haltsNoInput(p) returns true if program p will halt without reading any input when executed.
  • haltsNoInput(p) returns false if program p will not halt when executed.

The behavior of haltsNoInput is not defined on arguments p that are not syntactically correct programs that read no input. For example, haltsNoInput may run forever, crash, or return an incorrect answer given such a program.

Is it possible to write a method boolean halts(String p, String s) that decides whether program p would halt if p were run with string s as input? The halts method must halt and return:

  • true if p will halt when it runs and reads input s; and
  • false if p will not halt when it runs and reads input s.

Assume that any program p passed to halts begins with a statement that reads a single string as input, and then performs operations that do not read input. That is, all arguments p to halts have the form:

void main() {
    String input = readInput();
    ... // rest of the program does not readInput()
}

How to answer:

A formal proof is not required.

  • If the halting problem can be solved assuming you are given haltsNoInput as described, give a pseudocode implementation of boolean halts(String p, String s) and describe in prose how it works.
  • If the halting problem cannot be solved using haltsNoInput, explain in prose why not.
  • Finally, does your answer imply anything about the possibility of implementing haltsNoInput? Answer in prose.

2. Racket Evaluation (5 points)

For each of the following Racket definitions, write the value to which the variable will be bound, or “error” if evaluating this binding would result in an error.

Write your answers, with one line per definition, in order, in the form:

x --> 7
y --> 3
z: divide-by-zero error

meaning that variable x is bound to value 7, variable y is bound to value 3, and evaluating the binding for z results in a divide-by-zero error.

Predict the answers without running the code. You may find it useful to write evaluation derivations, leaving blanks for the result values as you build the derivation, and then filling in the results once you begin to reach values, but you do not need to submit derivations. You may also check your manually evaluated answers by running each binding in order in the DrRacket REPL. (Instructions on using DrRacket are here.)

#lang racket
(define a 5)

(define b (* a a))

(define c (+ (* 2 a) (- b a)))

(define f b)

(define i (if (< a 0) 3 (quotient 3 a)))

(define j (if (= a 0) 3 (quotient 3 a)))

(define k (quotient i j))

(define m (= (if (< b c)
                 (* (- (+ f (* (* b c) (quotient j f)))))
                 (* (- (+ f (* (* b c) (quotient j a))))))
             (* (- (+ f (* (* b c) (quotient j (if (< b c) f a))))))))

(define n (if (< i j) (< a 0) (< (< b c) m)))

3. YFPL (5 points)

Answer the following questions about your favorite programming language (YFPL):

  1. What kinds of programming errors do you make most frequently in YFPL? Name at least three. (Errors? Me?!)

  2. For each of your most common kinds of programming errors in YFPL, do the tools you use with YFPL programs detect these errors before the YFPL program is run, while it is running, or not at all/only sometimes?

  3. What is the most difficult aspect of debugging YFPL programs?

  4. What YFPL features do you use rarely or not at all? Why?

  1. This problem is adapted from a problem by Stephen Freund at Williams College, by permission. ↩