Submission details have been added below

Problem 4 now includes numerous concrete examples.

  • Due: 5:00pm Friday 5 February

  • Relevant reading:
  • Tools:

  • Collaboration: All parts of this assignment fall under the standard Gilligan’s Island Rule collaboration policy. That is, you may discuss the problems and strategies for solving them with classmates and other, but all coding and written solutions must be your own individual work.

  • Submission:

    This semester, CS251 work will be submitted via a combination of submitting written work via Google Docs and submitting code files via a drop folder on cs.wellesley.edu. Here’s how to submit this pset.

    1. Begin by creating a Google Drive folder named yourFullName CS251 Spring 2016 Folder that you share with me, Sara Burns, and Sravanti Tekumalla with commenting privileges. During the course, you will create many Google Docs in this folder, and by default they will inherit these permissions.

    2. Within the folder from Step 1, create a Google Doc named yourFullName CS251 Portfolio. You will populate this document with links to each assignment that you submit.

    3. Within the folder from Step 1, create a Google Doc named yourFullName CS251 PS1.

    4. Add a link to your PS1 document from your Porfolio document.

    5. Now create a file folder on your computer named yourCSAccountName_ps1. Below you will be asked to populate this file folder with various files on the assignment that you will submit (in the final step) to a drop folder on cs.wellesley.edu.

    6. Submit your work as described below.

      • For Problem 1 (Concrete Syntax):

        • Put your updateScore.py and updateScore.js files in your yourCSAccountName_ps1 folder.

        • Copy the contents of these files into a Problem 1 section of your PS1 Google Doc. Make sure that code formatting is correct. In particular, Python code must be indented properly.

      • For Problem 2 (Array Semantics and Expressiveness):

        • Put your sortInts.py and sortInts.js files in your yourCSAccountName_ps1 folder.

        • Copy the contents of these files into a Problem 2 section of your PS1 Google Doc. Make sure that code formatting is correct. In particular, Python code must be indented properly.

        • Also include in the Problem 2 section your writeup comparing the features of the two languages.

      • For Problem 3 (YFPL), include your writeup in a Problem 3 section of your PS1 Google Doc.

      • For Problem 4 (Deciding Properties of Programs), include your writeup in a Problem 4 section of your PS1 Google Doc.

      • For Problem 5 (Racket Evaluation), in a Problem 5 section of your PS1 Google Doc, write one binding (or error) per line.

    7. Copy your final yourCSAccountName_ps1 folder to your ps01' cs251 drop folder on cs.wellesley.edu. This drop folder will be in acs251/drop/ps01` subfolder of your account. (I am still in the process of creating these.)

1. Concrete Syntax (10 points)

This problem explores how the same program can be written with different concrete syntax in different languages.

Consider the following App Inventor program, which consists of two global variable declarations and the declaration of an updateScore procedure. (This program is incomplete, since updateScore is never called.)

App Inventor updateScore procedure exanple

Create two files, updateScore.py and updateScore.js, that contain, respectively, (1) Python and (2) JavaScript versions of the App Inventor program.

Notes:

  • If you don’t know or can’t remember details of Python or JavaScript syntax, look it up on the Web!

  • The App Inventor example includes two global variable declarations (score and color), a local procedure parameter declaration (points), variable references (getters) for all of these, and variable assignments (setters) for the global variables. In one of your programs, you will need an extra declaration to distinguish global from local variables. Why? (You don’t need to answer this question in your solution, but should think about it.)

  • App Inventor includes both conditional statement blocks (the two left blocks below) and conditional expression blocks (the rightmost block below).

App Inventor conditional blocks

In general, a statement is a program phrase that performs an action while an expression is a program phrase that returns a value. In App Inventor, statements compose vertically to emphasize that their actions are performed sequentially from top to bottom, while expressions have plugs on their left side that denote the value returned by the expression. This value is used by the block whose socket the plug is connected to.

Both Python and JavaScript have different syntax for conditional statements vs. conditional expressions. In your programs, you should use the appropriate syntax for each one. (If you don’t know it, look it up!) In particular, do not use the conditional statement syntax to translate App Inventor’s conditional expression block!

BTW #1, App Inventor also has top-level declarations (blocks that introduce top-level named entities, like procedures and global variables). These are blocks that do not have any plugs or sockets and so cannot be connected to other blocks.

BTW #2, Racket only has declarations and expressions; it does not have statements. So Racket’s if is a condtional expression and not a conditional statement. What’s it like to program in a language without statements? You’ll find out!

  • What App Inventor calls a “procedure” is called a “function” in Python and JavaScript. The term “function” often implies that callers for the entity can return a value (i.e., function calls are expressions), whereas “procedure” often implies that callers for the entity perform an action but do not return a value (i.e., procedure calls are statements). But the usage is rather inconsistent between languages.

  • It is strongly recommended that you test your updateScore functions to verify that they work correct. E.g., you can use Canopy to test updateScore.py and a browser JavaScript interpreter to test updateScore.js.

2. Array Semantics and Expressiveness (15 points)

All general-purpose programming languages are Turing-complete, which means that they all can be used to define the same set of computable functions.

However, PLs differ in their “expressiveness”, an informal notion that attempts to capture how easy it is to write a program in one language vs. another.

This problem explores the notion of expressiveness by asking you (1) to express the same high-level computation in two different languages, Python and Java, and (2) to compare the resulting programs. Here is a specification of the high-level computation:

  • The progam takes as its single input the name of a file that contains any number of integers in any order, one per line.

  • The program opens the file exactly once, and reads all of the integers line-by-line into an (initially unsorted) array-like data structure that maintains their order from the file. So if the file begins with the integers

    251
-273
17

    the first three slots of the unsorted array-like data structure should contain the integers 251, -273, and 17. (These should be integers, not strings.)

  • The program then sorts the integers in the array-like structure “in place” so that they are sorted from low to high. No new array-like structure should be created; rather, the order of the elements in the existing array-like structure should be changed.

  • Finally, the program displays the integers of the sorted array-like structure, one per line, in their sorted order. For example, suppose the file ints.txt has the following contents:

    251
-273
17
111
42
240
-19
304
231
-1729
110
220
-23
235
342
230
112

    Then running the program should display the following lines in the console:

    -1729
-273
-23
-19
17
42
110
111
112
220
230
231
235
240
251
304
342

Your tasks in this problem are (1) to create a Python program sortInts.py and a Java program sortInts.java that express the computation described above and (2) to reflect on the differences between the two programs. Follow these notes:

  • For sortInts.py, use the following skeleton for your program:

    import sys

def sortIntsInFile (filename): 
    try: 
        '''Flesh out this part of this function.'''
    except IOError:
        print("There is no file named " + filename);

if __name__ == '__main__':
    if len(sys.argv) != 2:
        print("Usage: python sortInts <intFileName>")
    else: 
        sortIntsInFile(sys.argv[1])

    Pay attention to the following notes in fleshing out this skeleton:

    • The portion of the program beginning if __name__ == '__main__': is the way of passing command-line arguments to a Python program. You can review what this means by studying slides 21-28 though 21-32 in these CS111 slides.

    • You should test your program, which should work not only on small cases like ints.txt, but on files contain a very large number of integers.

  • For sortInts.java, use the following skeleton for your program:

    import java.io.*; // Needed to use File and FileNotFoundException classes
import java.util.*; // Needed to use Scanner, ArrayList, and Collections classes

public class sortInts {

  public static void sortIntsInFile(String filename) {
    try {
      // Flesh out this part of this method
    } catch (FileNotFoundException e) {
      System.out.println("There is no file named " + filename);
    }
  }

  public static void main (String[] args) {
    if (args.length != 1) { 
      System.out.println("Usage: java sortInts <intFileName>");
    } else {
      sortIntsInFile(args[0]);
    }
  }

}

    Pay attention to the following notes in fleshing out this skeleton:

    • The Scanner class is useful for reading lines from a file in Java. See slide 18-8 these Java I/O notes for how to use the Scanner class.

    • Java’s built-in arrays are not a good way to read in the lines from the file (why not?).
      Instead, use the ArrayList class for this purpose. If you’ve never used ArrayList before,
      check out an online tutorial, like this one.

    • You will need to figure out how to sort an instance of the ArrayList class. Do not implement
      a sorting algorithm on your own; instead use existing sorting functionality in the Java library.

    • The Java wrapper class Integer is also useful here. If you’re unfamiliar with wrapper classes,
      read this.

    • You should test your program, which should work not only on small cases like ints.txt, but on files contain a very large number of integers.

  • Once you have implemented and tested your two programs, reflect on aspects of Python and Java that made them easy or hard to write. For each of the two languages, list the all the features that either (1) helped you write the program or (2) got in the way of you writing the program, justifying each of your claims.

3. YFPL (5 points)

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

  1. What features does YFPL have that make it your favorite?

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

  3. 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?

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

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

4. Deciding Properties of Programs1 (10 points)

An earlier version of this problem incorrectly mentioned an undefined function takesNoInput. All occurrences of takesNoInput have been replaced by takesArguments.

There is now a new subsection of this problem named Some Examples that contains several concrete examples intended to help you thing about this problem.

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

To be more precise, assume that:

  1. You are given an implementation of a Python function takesArguments(q, n) that takes a string q and a nonnegative integer n, and returns True if q is the string representation of a legal declaration of a Python function p that takes n arguments and does not invoke any code that might read input from the user through the console. If q does not satisfy all these conditions, takesArguments(q, n) returns False. The takesArguments function is definitely decidable, since such a function is indeed writable in Python. (But you are not expected to write it in this problem; you may simply assume it is given to you!)

  2. You are given an implementation of a Python function haltsNoInput(r) that takes, as a string, a declaration for a Python function r that takes no inputs, and returns a boolean. haltsNoInput(r) has the following behavior:

    • haltsNoInput(r) returns True if takesArguments(r,0) is True and the Python function described by r terminates when called on zero inputs. (Note that a function may terminate by returning a value or by throwing an exception.)
    • haltsNoInput(r) returns False if either (1) takesArguments(r,0) is False or (2) takesArguments(r,0) is True, but the Python function described by r does not terminate when called on zero inputs.

The question you are investigating is whether haltsNoInput can actually be written. I.e., does it describe a decidable mathematical function?

Given the above two Python functions, is it possible to write a Python function halts(p, s) that decides whether a legal one-argument Python function described by a string p would terminate when called on a string argument s? That is:

  • halts(p,s) returns True if takesArguments(p,1) returns True, s is a string, and the Python function described by p terminates when called on s.
  • halts(p,s) returns False if either (1) takesArguments(p,1) returns False, (2) s is not a string, or (3) takesArguments(p,1) returns True, s is a string, and the Python function described by p does not terminate when called on s.

Some examples:

Many of the above descriptions are rather abstract and can be hard to understand. Here are some concrete examples that are intended to clarify things.

Consider the following Python strings definitions:

PString1 = \
'''def P(x):
    return len(x)'''

PString2 = \
'''def P(x):
    while True:
        pass'''

PString3 = \
'''def P(x):
    inputFromUser = raw_input()
    return len(x + inputFromUser)'''

PString4 = \
'''def P():
    return 17'''

PString5 = \
'''def P():
    while True:
        pass'''

SString = 'bunny'

The first five definitions are string representations of Python functions named P. Here are some notes on these functions:

  • Calling the function represented by PString1 on the contents of SString would return 5 (since bunny has 5 characters).

  • Calling the function represented by PString2 on any argument would loop infinitely.

  • Calling the function represented by PString3 on the contents of SString would wait for the user to enter an input string at the console, and would return the length of that string plus 5.

  • Calling the function represented by PString4 on zero arguments would return 17.

  • Calling the function represented by PString5 on zero arguments would loop infinitely.

  • takesArguments(PString1, 1) will return True since PString1 is the string representation of a legal one-argument Python function. But takesArguments(PString1, n) for any nonnegative integer n that is not 1 will return False since PString1 is the string representation of a legal one-argument Python function, and it does not take n arguments for any n other than 1.

  • takesArguments(PString2, 1) will return True since PString2 is the string representation of a legal one-argument Python function; takesArguments(PString2, n) for any nonnegative integer n that is not 1 will return False since PString2 is the string representation of a legal one-argument Python function, and it does not take n arguments for any n other than 1.

  • takesArguments(PString3, n) will return False for any nonnegative integer n. Although PString3 is the string representation of a legal one-argument Python function, that function reads user input from the console, so it will still return False when n is 1.

  • takesArguments(PString4, 0) will return True since PString4 is the string representation of a legal zero-argument Python function. takesArguments(PString4, n) for any nonnegative integer n that is not 0 will return False since PString2 is the string representation of a legal zero-argument Python function, and it does not take n arguments for any n other than 0.

  • takesArguments(PString5, 0) will return True since PString5 is the string representation of a legal zero-argument Python function. takesArguments(PString5, n) for any nonnegative integer n that is not 0 will return False since PString2 is the string representation of a legal zero-argument Python function, and it does not take n arguments for any n other than 0.

  • takesArguments(SString, n) will return False for any nonnegative integer n since SString is not the string representation of a Python function.

  • If halts could be written, the following would all return True:

    • halts(PString1, SString)
    • halts(PString1, PString1) (and similarly for second argument PString2 through PString5)
  • If halts could be written, the following would all return False:
    • halts(PString2, s) for any string input s, because the function denoted by PString2 loops on all arguments.
    • halts(PString3, s) for any string input s, because the takesArguments(PString3, 1) returns False
    • halts(PString4, s) for any string input s, because the takesArguments(PString4, 1) returns False
    • halts(PString5, s) for any string input s, because the takesArguments(PString5, 1) returns False
    • halts(SString, v) for any value v, because takesArguments(SString, 1) returns False (it does not represent a Python function)
    • halts(PString1, n) for any number input n, because a number n is not a string

  • If haltsNoInput could be written, then haltsNoInput(PString4) would return True:

  • If haltsNoInput could be written, then all the following would return False:
    • haltsNoInput(PString5), because the function denoted by PString5 loops infinitely when called on zero arguments.
    • haltsNoInput(PString1), because takesArguments(PString1, 0) returns False
    • haltsNoInput(PString2), because takesArguments(PString2, 0) returns False
    • haltsNoInput(PString3), because takesArguments(PString3, 0) returns False
    • haltsNoInput(SString), because takesArguments(SString, 0) returns False (it does not represent a Python function)

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 halts(p, 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.

5. Racket Evaluation (10 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 d (+ a b c))

(define e (+ a))

(define f (+))

(define g (*))

(define h b)

(define i (if (< a 0) 7 (quotient 43 a)))

(define j (if (= a 0) 11 (remainder 43 a)))

(define k (/ i j))

(define l (< a b))

(define m (= b c))

(define n (< b c d))

(define o (+ a m))

(define p (< a m) )

(define q (if a b c))

(define r (if l m n))

(define s (if (if (< i j) m l)
              (if (> a c) (+ a c) (* a c))
              (if (< a b) (+ a b) (* a b))))            

(define t (= (if (< b c)
                 (* (remainder (- (* a b) (* 2 a)) c) (- (quotient d b)))
                 (* (- (+ d (* (* a b) (quotient d a))))))
             (- (* (/ (- c a) (- a 1)) (quotient b (if (> a c) i j))))))

(define u (if (> i j) (< a 0) (< (< b c) a)))

(define v (if (<= i j) (< a 0) (< (< b c) a)))

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