Harvey Mudd College
Computer Science 60
Assignment 1, Due Sunday, January 25, by 11:59 pm

Rex: the king of computation!

This homework is a chance to get familiar with two things:

1. A command-line environment -- in particular on the CS department's main compute server, named knuth.
2. A functional programming language named Rex that has a number of features that make it different than Python, CS 5's programming language.

The Problems

Problem 0:    Getting familiar with unix and Rex

[0 points ~ getting started]

You are welcome to obtain any and all help on this problem!

Why bother with the command line?

You may not have navigated/edited files and folders via the command-line before, or perhaps only a bit. Why, given today's dominance of the WIMP interface (Windows, Icons, Mouse, and Pointer), would one spend time at a text-based command line, sometimes called the shell?

There are at least two reasons. The first is that a great deal of computation outside of CS depends on a command-line interface. For instance, all of the interaction done in matlab occurs through a command line -- it just happens to be a command line wrapped in a matlab window. The same is true of mathematica, maple, and many statistical packages, as well. Transfering files from machine to machine and logging into machines remotely, especially if they are running different operating systems, are efficiently done via command line.

In a remarkable bout of procrastination, we took a survey of seven non-CS Profs in Olin (Profs. Levy, Adolph, Su, dePillis, Benjamin, Bush, and McFadden): everyone used command-line skills in their work; three did so extensively or almost exclusively. We look forward to extending our survey into Parsons and Jacobs -- perhaps when some unenjoyable deadlines are looming -- the results there are likely to be the same. So, the first reason for introducing command-line computation is that feeling comfortable at the shell/command line is a "resume-listable" skill that will make you far more effective with computation as used in all technical disciplines today.

The second reason, and certainly the one more in keeping with the philosophy of CS 60, is that basic familiarity with the command line provides an accurate, flexible, and powerful mental model of how computation is organized on today's machines. A graphical interface is wonderful for undertaking the tasks it was designed to handle. The command line, on the other hand, opens up all of the computational facilities of a particular machine. The command line provides a view into what is going on, quite literally, "behind the curtain," of modern interfaces.

Try it!

This problem includes instructions for using the command line to get around the main CS server named knuth (full name: knuth.cs.hmc.edu). Here are the steps:

• Logging in
• Navigating around, finding and copying files
• Editing files and writing Rex code

References

The first few links on the CS 60 references page provide much more detail on the unix operating system, using the command line, and a Rex reference.

Design, commenting, and formatting

Design and formatting account for roughly a quarter of the credit for each function or program you complete.

Design, here, means algorithm design, that is, how you break a problem down into smaller pieces and then compose those pieces into an overall solution. Large, convoluted functions are difficult to understand (and debug!). Use small, clear functions -- with helper functions of your own design, as needed or desired.

Formatting includes coding style: clean and clear structure, meaningful variable and function names, ample use of spacing, and indenting that reflects code structure. One-letter variable and other short variable names are OK for commonly-used idioms and small functions, such as [f|R] representing the first and rest of a list or fac(x), specifying the factorial of a number x. However, longer names that describe a variable more fully are an excellent form of "self-documenting" programs that are easy to understand!

As for commenting, in each assignment we ask you to include

• a top-of-file comment with
  • your name
  • your partner's name, if any
  • how long you spent on it (roughly)
  • any other comments
  Those additional comments are optional, but appreciated -- they are a good way to let the graders and us know about particular difficulties or thoughts about a problem. We encourage Any and all feedback/suggestions!
• a comment for each function describing
  • the function's input(s) and output(s)
  • briefly, in English, what it does.
  These help, in particular, in creating recursive functions. The example part1.rex file has a template you are welcome to follow for this.
• Comments within functions or data definitions are welcome, but not required unless something tricky is going on.

Important warning about function names!    Be sure to name your functions as indicated in the problem statements below -- including capitalization and punctuation! This helps our graders, who can automate the running of many tests using those function names. Helper functions may have any name you like, but they should be descriptive and appropriate. When graders have to manually change your function names to match the ones in the homework problem descriptions, it angers them -- and it's always a good rule of thumb to avoid angering the graders!

Testing your code

Computation in the form of software is useful to the extent that it works. But it only works to the extent that it has been tested! Testing your own software thoroughly is important -- we use test cases to check how well your functions work, and you will certainly want to do the same... .

Some test cases are indicated for each of the problems. These can be copied from this assignment site into your code. When you use auxiliary functions, it is good practice (and will save time in the long run) to include tests for them, too. We strongly recommend creating additional tests for the primary functions, because the tests provided do omit some of the cases you'll need to handle!

Built-in functions

You're welcome to use any built-in functions for this week's assignment except remove_duplicates and pow, since we are implementing those two functions. In particular, some of these may be particularly useful:

append(L,M)     // concatenates two lists (inputs must be lists!)               
member(e,L)     // 0 if e is not in L; 1 if e is in L
reverse(L)      // reverses L
rmv1(e,L)       // not built-in; from class -- removes one e from L
length(L)       // returns the length of L         
max(x,y)        // returns the max of x and y 
min(x,y)        // returns the min of x and y
sort(L)         // returns a sorted version of L

part1.rex    Individual problems, #1 through #5

Submit definitions for these functions in a file named part1.rex. Each person should write these first five problems on their own. We encourage you to seek out help from us, from the grutors, or from other students as described in the syllabus.

Problem 1:    pwr

[10 points, individual]

For this problem define a function, pwr( b, p ) that outputs the value of b raised to the p power; b will be any numeric value, and p will be an integer. With all of your functions in rex, you do not have to check that the inputs are valid; we will test only with valid inputs.

Rex does have this function built-in; it's named pow - but using pow isn't allowed here! Instead, use recursion. You may want to build from the fac example already in part1.rex and that we tried in class.

Your pwr function should handle negative powers correctly. Warning: as in many languages, when you want floating-point division, be sure to make the numerator 1.0! If both the numerator and denominator are integers, it will make the result an integer by rounding down -- for this problem, you won't want that behavior.

In addition, it should return 1.0 whenever p is zero, and it should return 0.0 whenever b is zero, except when p is also zero. (It can do anything for zero-to-the-zeroth power; we won't test that case.)

As an example of a suitable pre-function comment, feel free to use these lines:

//  pr: #1
// fun: pwr(b,p)
//  in: b - the numeric base, p - an integer power
// out: b**p (floating point!)

 ... your rules here ...

Here are a couple of tests to try -- feel free to copy-and-paste these under your definition of pwr.

test( pwr(3,5),   243 );
test( pwr(2,-2),  0.25 );

Problem 2:    lg2

[10 points, individual]

Mathematicians define logarithms in lots of ways: as an exponent, as the inverse of a power function, as sums of certain series, ... .

To compuer scientists, by far the most common definition of lg2(x) is this: it's the number of times you can repeatedly divide x by 2 until you're ≤ 1.. For example, lg2(8) returns 3, because dividing by two repeatedly yields 8 -> 4 -> 2 -> 1 for a total of three divisions.

Using this idea - and recursion - write the function lg2(x), which takes in x, a floating-point value greater than or equal to 1. It should output an integer which is the number of times that x can be divided by two before the result is ≤ 1. Thus, for x ≤ 1, the function lg2(x) should output zero.

Another floating-point warning: I found it easier to write this function using x/2.0 rather than x/2 within the recursive step. Remember that the former is floating-point division; the latter is integer-only division and always yields integer output when x is an integer

Here are a few tests to check:

test( lg2(7),  3 );
test( lg2(8),  3 );
test( lg2(9),  4 );

Problem 3:    twiddle

[10 points, individual]

Write a function twiddle( L ) taking as input any list L. Then, twiddle( L ) should return a list identical to L, but with the first two elements reversed. If L has fewer than two elements, then twiddle should output a list identical to its input.

Here are some example tests:

test( twiddle( [1,2,3,4] ),    [2,1,3,4] );
test( twiddle( [1,2] ),        [2,1] );
test( twiddle( [ [1,2] ] ),    [[1,2]] );  // L has only 1 element!

Problem 4:    superreverse

[10 points, individual]

This problem asks you to write a different variant of reverse. You are welcome and encouraged to use the built-in reverse function to help with superreverse( L ) here and duperreverse( L ) in the next problem. Both superreverse and duperreverse take any list L as input.

Your function superreverse( L ) should return a list like L except that all top-level lists that are elements of Lshould be reversed.. Here are two examples:

test( superreverse( [ [1,2], 42, "string", [5,4,3] ] ),
      [ [2,1], 42, "string", [3,4,5] ] );

test( superreverse( [ [1,2], [3,4,[5,6],7], 8, [[9]] ] ),
      [ [2,1], [7,[5,6],4,3], 8, [[9]] ] );

Problem 5:    duperreverse

[10 points, individual]

The function duperreverse( L ) should return a list like L, but with all list structure - top-level and nested - reversed! Again, use is_list. Here are some examples:

test( duperreverse( [ [1,2], 42, "string", [5,4,3] ] ),
      [ [3,4,5], "string", 42, [2,1] ] );

test( duperreverse( [ [1,2], [3,4,[5,6],7], 8, [[9]] ] ),
      [ [[9]], 8, [7,[6,5],4,3], [2,1] ] );

Hints and warnings: it is important to use the functions list (or []), cons (or [|]), and append(L,M) in a composition that preserves the nesting-depth of all of the elements of L. Note that you can't use cons to put things at the end -- for that, use append! But note that append(L,M) always takes two lists as input. You'll want to be sure that top-level elements stay as top-level elements, and that sublists stay as sublists.

part2.rex    Pair or individual problems, #6 through #10 and ex. cr.

You're welcome to work on the second half of this week's problems on your own, but we'd encourage you to do so with a partner, if you'd like. If you do work in a pair, be sure to work at the same physical place and to trade off at the keyboard/debugging roles, as described in the syllabus.

Whether you work on your own or with a partner, you should submit your definitions for these functions in a file named part2.rex.

Problem 6:    our informal CS 60 questionnaire, online

[10 points, pair or individual]

For this problem, you'll create a webpage whose URL is

http://www.cs.hmc.edu/~yourloginid/cs60q.html

First, feel free to peruse
http://www.cs.hmc.edu/~hadas/cs60q.html
http://www.cs.hmc.edu/~zdodds/cs60q.html

Creating your own such page will reinforce some of the unix commands you've already used and it will introduce a couple more, as well.

• At knuth's command prompt, go to your home directory with cd ~.
• If you use ls -F to examine the contents of your home directory, you should see a subdirectory named public_html/.
• Go into that subdirectory with cd public_html.
• Copy one of the above webpage files to your own directory:

         cp /home/zdodds/public_html/cs60q.html .
     of  cp /home/hadas/public_html/cs60q.html .
    

• Edit that file to customize it for yourself... the basic questions are
  • your name
  • What's a place outside of HMC/Claremont that you do (or have) considered home?
  • Your favorite _________ is __________ ?
  • Your least favorite _________ is _________ ?
  • Mention if you have any programming background (Python is probably part of it, but there may be more...)
  
  
• Once that file is edited and in place, it still will not be viewable until you change its permissions. The file needs to be world-readable, and the command to allow everyone access to it is this:

          chmod ugo+r cs60q.html
         

• Now, you should be able to point any browser to the URL

          http://www.cs.hmc.edu/~yourloginid/cs60q.html
    

  and it will be visible.
• If you have experience building web pages/applications, feel free to add bells and whistles. But, there's no need to do so. Also, if you'd prefer not to have this page hanging around, feel free to get rid of it -- but we'd ask you to wait until this hw has been graded... .

Note that, although you're certainly welcome to work on this with a partner, do create these personalized webpages for each person.

Problem 7:    enum

[10 points, pair or individual]

Write a function enum( L ), taking any list L as input. Then, enum( L ) should return a list of two-element lists, or pairs that enumerates the elements of L, starting from zero. These examples will show the intent:

test( enum( ["jan","feb","mar"] ),
      [ [0,"jan"], [1,"feb"], [2,"mar"] ] );

test( enum( [2008,2009,2010,2011] ),
      [ [0,2008], [1,2009], [2,2010], [3,2011] ] );

test( enum( [] ),
      [] );   

Hint!: Write a helper function of two inputs that does all of the work. Then, have enum delegate its work to that helper function with suitable arguments. That is, write

     enum( L ) => enumHelper( two inputs here! );

Problem 8:    removeAll

[10 points, pair or individual]

Write a function removeAll( e, L ) taking as inputs any datum e and any list L. Then, removeAll( e, L ) should return a list identical to L, but with all top-level instances of e removed.

Here are some examples:

test( removeAll( 1, [1,1,42,1] ),    [42] ); 
test( removeAll( 1, [[1,1], 1] ),    [[1,1]] );
test( removeAll( 1, [2,3,5,7]  ),    [2,3,5,7] );

A good place to start for this is the rmv1 function we examined in class...

Problem 9:    uniq

[10 points, pair or individual]

Write a function uniq( L ) taking in any list L as input. The output should be a list like L, with all top-level, later-appearing duplicate elements removed. For example,

test( uniq( [1,2,3,1] ),   [1,2,3] );

test( uniq( [1,1,2,1,1,2,1,2,3,2,1,3] ),    [1,2,3] );

Hint: the built-in member function could be helpful, and you're welcome to use that one... . Except in cases where you're actually implementing a built-in function, you're welcome to use Rex's built-in functions.

Problem 10:    wordScore

[10 points, pair or individual]

This problem introduces the action-packed built-ins, explode and implode, as well as the useful built-in assoc function. In addition, you'll use the ability to import files with the *i command within a Rex source code file. You'll compose these pieces in order to create a scrabble-scoring function named wordScore.

You'll want the data in the file scrabbleScores.rex: it maps characters to their Scrabble point values. You should get that file by copying to your current directory with the following command:

    cp /cs/cs60/hwfiles/a1/scrabbleScores.rex .

Either at the rex prompt or at this point in your part2.rex file, you can include the line

*i scrabbleScores.rex

Association lists, or "A-lists," are lists-of-lists like scrabbleScores. They're often used as data repositories, accessed by the built-in function assoc, usually pronounced "a sock." assoc( e, AL ) simply looks up the datum e in an association list AL. It returns the first member of AL whose first element is e, if one is present, or the empty list [], if not. For example,

rex > assoc( 1, [ [0,"jan"], [1,"feb"], [2,"mar"], [1,"apr"] ] );
[1, feb]

rex > assoc( 42, [ [0,"jan"], [1,"feb"], [2,"mar"] ] );
[]

rex > *i scrabbleScores.rex      // loads in the file
read file scrabbleScores.rex        // we can now use scrabbleScores

rex > assoc( 'q', scrabbleScores );
[q, 10]

rex > assoc( 't', scrabbleScores );
[t, 1]

With this as background, write a function wordScore( w ) that takes in a string named w and returns that string's scrabble score, i.e., the sum of the scores of its individual characters. For example,

test( wordScore( "zap" ), 14 );
test( wordScore( "zzz" ), 30 );   // We ignore the fact that Scrabble has limited tiles...
test( wordScore( "aah" ), 6 );
test( wordScore( "twelve" ), 12 );
test( wordScore( "fortytwo" ), 17 );

Notes on strings vs. characters: explode and implode

Unlike Python, Rex (and almost every other computer language: Java, Prolog, C, C++, ...) distinguishes between characters and strings. Characters are always a single item and are surrounded by single quotes, such as 'a', 'b', or ' ' (the space character). Strings are a collection of zero or more characters and are surrounded by double quotes, such as "this is a string!", "" (the empty string), or "a" (a string with one character). Double-quoted strings are not the same as single-quoted characters, even if the string contains only one character!

You can convert back and forth between strings and lists of characters with explode and implode. For instance,

rex > explode( "star" );  // a supernova?
['s', 't', 'a', 'r']         // note: rex doesn't print the single quotes here!

rex > implode( [ 's', 't', 'a', 'r' ] );   // a black hole?
"star"                       // rex won't print these double-quotes, either

rex > explode( "a" );
['a']                

rex > implode( [] );
""

Hint: writing a function that returns the value of a single character will help here. The assoc function is useful, but not exactly what is needed... .

Totally optional extra credit...

You're welcome to try these on your own or in a pair. They've been described as "challenging and fun" by unbiased reviewers (Prof. Ran).

In addition, the first problem below, #11, will be on the HW next week. If you succeed at it this week, you earn credit for it both times... .

Optional extra credit ~ problem #11:    bestWord

[up to +10 points, pair or individual]

This problem is a larger task: it asks you to write bestWord( rack, Words ), where rack is a string representing one's available scrabble tiles and Words is a list of legal words. Then, bestWord should output a [word, score] pair, where word is the highest-scoring member of Words such that word can be formed from the letters in rack. Use the previous problem's wordScore function. If Words has no elements that can formed from rack, your function should return ["no word", -1]. You may break ties however you like, but should return only one [word, score] pair.

Here are some examples:

test( bestWord( "abcdefg", [ "bbb", "bag" ] ), [ "bag", 6 ] );
test( bestWord( "abcdbbg", [ "bbb", "bag" ] ), [ "bbb", 9 ] );
test( bestWord( "a", [ "bbb", "bag" ] ),       [ "no word", -1 ] );
test( bestWord( "abcdefg", ospd3 ),            [ "fed", 7 ] );
test( bestWord( "zabcdefg", ospd3 ),           [ "fez", 15 ] );

   *i threeLets.rex

Planning out a strategy for this problem before diving in to the coding is a good thing! You will want to define and use a number of helper-functions to keep your definition of bestWord simple and elegant. You'll want to keep the helper-functions short, as well! Our solution's functions use a total of six rules, not including wordScore and rmv1, which are helpful. If you're getting toward 15 or more rules, you might consider redesigning your solution!

Optional extra credit ~ problem 12:    multLists and mult

[up to +15 points, pair or individual]

I have always considered the infinite-precision integer arithmetic that some languages offer to be a neat (if not always useful) feature. Although rex does not offer infinite-precision integer arithmetic, it's surprisingly succinct to implement!

For this extra credit problem, your task is to write two functions that perform integer-precision multiplication of positive integers: mult( str1, str2 ) takes in two strings representing positive decimal integers and should output a string that is the product of those input integers. For example,

test( mult( "6", "7" ), "42" );

test( mult( "123456789", "987654321" ), "121932631112635269" );

En route to the mult function, you will find it helpful to write multLists, which does the same thing for reversed lists of single-digit integers:

test( multLists( [6], [7] ), [2, 4] );

test( multLists( [1,2,3,4,5,6,7,8,9], [9,8,7,6,5,4,3,2,1] ), 
      [9,6,2,5,3,6,2,1,1,1,3,6,2,3,9,1,2,1] );

Certainly, you'll use explode and implode here. Also, you might consider writing addLists (similar to multLists). We also found functions for converting back-and-forth between characters and single-digit integers helpful. The built-in make_number( c ) returns an integer when given a character c. Going the other way, we used

// from single-digit integer x to a character, by indexing into a list:
chr(x) => ['0','1','2','3','4','5','6','7','8','9'](x);

Warning!    The built-in function make_string does not work -- this is why we make the chr suggestion, above (from which you'll be able to create your own make_string...).

Submitting your work

Submission of your part1.rex and part2.rex files provides an opportunity to get comfortable with file-transfer to and from from servers like knuth.

Password?    Remember that your default password to the submission site is the default four-letter one mentioned in class (drop us an email if you don't remember it...). Once you get into the submission system, you can change your password to be whatever you'd like (such as your ordinary password!)

Submitting pair programs:    Partners who have created one file together should each submit that file, under their own names. You may have to close the browser and then re-open it, in order to log in as the other person.

Friendly warning: be sure you've tested your files after adding any final comments or notes... it's amazing how often a comment character gets omitted accidentally and then code fails to work unless its was tested just before submitting!

    Submitting a file from the CS Lab Macs    If you are on a lab machine, you can simply submit using our online site -- skip down to the "Web submission" instructions below.

On the other hand, if you're onyour own machine, you'll need to transfer your files from knuth to your machine. The instructions differ based on your operating system:

    Copying a file from knuth to a local Mac    First, while on knuth, type pwd in order to see the full path name to your part1.rex and part2.rex files. For example, if your login were penguin, then your path might be

/home/penguin/cs60

From that local terminal (now at your Desktop), use the secure-copy program, scp, by typing

scp penguin@knuth.cs.hmc.edu:/home/penguin/cs60/part1.rex .

Just as an aside, you can copy files to knuth with scp, too. It would look like this:

scp myfile.txt penguin@knuth.cs.hmc.edu:/home/penguin

    Copying a file from knuth to a Windows PC    This is even easier than on a Mac because of the convenient free program named WinSCP, available for download from http://winscp.net/eng/download.php -- I always use the "portable executable" link a little way down on the left.

Once you've downloaded that program, perhaps to your desktop, double-click it and then input knuth.cs.hmc.edu as the "Host name" and then hit "Login" button at the bottom. The program will prompt you for your login name on knuth and then your password. After that, you will be presented with a two-panel view of your local files as well as your remote files (the ones on knuth). Dragging and dropping between the panels (or to your local desktop) works as you'd expect.

Web submission

Once your file is on your local desktop (or a subfolder), navigate to the CS 60 submission page and log in. You should then be able to click on the "Submit a File" button, choose your file (from its spot on your local machine), and upload it. You can check on your submitted files (and, later, grades) from the "Browse Files" button.

Be sure to submit both part1.rex and part2.rex under Week 1 at the submission site.

You may submit your work multiple times -- only the file submitted latest (before the deadline) will be graded, but all of them will be saved in case you or we need to access them for any reason.

Problems submitting? Feel free to email your files/questions/concerns to dodds@cs.hmc.edu.