changes

6 files changed, 950 insertions, 2 deletions

diff --git a/.gitignore b/.gitignore
index f81310f..24b146d 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,5 +1,6 @@
 downloads
 reading
+toread*
 *.swp
 *~
 *.bak
diff --git a/from_athena.sh b/from_athena.sh
index 19929a5..213503d 100755
--- a/from_athena.sh
+++ b/from_athena.sh
@@ -1,3 +1,3 @@
 #!/bin/sh
 
-rsync -arv bnewbold@linux.mit.edu:4.602/* .
+rsync -arv bnewbold@linux.mit.edu:4.602/ps* .
diff --git a/ps01_grep/ps.txt b/ps01_grep/ps.txt
new file mode 100644
index 0000000..8f0efd4
--- /dev/null
+++ b/ps01_grep/ps.txt
@@ -0,0 +1,698 @@
+
+                MASSACHVSETTS INSTITVTE OF TECHNOLOGY
+      Department of Electrical Engineering and Computer Science
+
+                          6.945 Spring 2009
+                            Problem Set 1
+
+  Issued: Wed. 4 Feb. 2009                    Due: Wed. 11 Feb. 2009
+
+
+General instructions for problem sets:
+   A problem set for this class generally asks you to do some
+programming.  We usually give you a program to read and extend.  You
+should turn in your extensions, in the form of clearly annotated code
+and executions that demonstrate its effectiveness.  We may also ask
+for short essays explaining an idea.  Your answers to these questions
+must be clear and concise: good logic expressed in good English is
+required.  Thank you.
+
+Readings: 
+    Review SICP chapter 1 (especially section 1.3)
+    MIT/GNU Scheme documentation, section 5.6 (character sets)
+    Debian GNU/Linux info on regular expressions 
+      from the grep man page (attached).  This is sane.
+
+Code: 
+    regexp.scm, tests.txt (both attached)
+    Windows grep: http://gnuwin32.sourceforge.net/packages/grep.htm
+
+Documentation:
+ The MIT/GNU Scheme installation and documentation can
+    be found online at http://www.gnu.org/software/mit-scheme/
+    The reference manual is in:
+ http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/
+
+    The (Insane) POSIX manual page for regular expressions:
+ http://www.opengroup.org/onlinepubs/009695399/basedefs/xbd_chap09.html
+
+
+                         Regular Expressions
+
+Regular expressions are ubiquitous.  But the syntax of the regular-
+expression language is awful.  There are various incompatable forms of
+the language and the quotation conventions are baroquen [sic].
+Nevertheless, there is a great deal of useful software, for example
+grep, that uses regular expressions to specify the desired behavior.
+
+Part of the value of this problem set is to experience how bad things
+can be.  Although regular expression systems are derived from a
+perfectly good mathematical formalism, the particular choices made by
+implementers to expand the formalism into useful software systems are
+often disastrous: the quotation conventions adopted are highly
+irregular; the particularly egregious misuse of parenthesis, both for
+grouping and for backward reference, is a miracle to behold.  In
+addition, attempts to increase the expressive power and address
+shortcomings of earlier designs have led to a proliferation of
+incompatible derivative languages.
+
+In this problem set we will invent both a Lisp-friendly language for
+specifying regular expressions and a means of translating this
+language to conventional regular-expression syntax.  The application
+is to be able to use the capabilities of systems like grep from inside
+the Scheme environment.
+
+As with any language there are primitives, means of combination, and
+means of abstraction.  Our language allows the construction of
+patterns that utilities like grep can match against character-string
+data.  Because this language is embedded in Scheme we inherit all of
+the power of Scheme: we can use Scheme constructs to combine patterns
+and Scheme procedures to abstract them.
+
+Patterns are built out of primitive patterns.
+The primitive patterns are:
+
+ (r:dot)
+     matches any character except newline
+
+ (r:bol)
+     matches only the beginning of a line
+
+ (r:eol)
+     matches only the end of a line
+
+ (r:quote <string>)
+     matches the given string
+
+ (r:char-from <char-set>)
+     matches one character from the specified 
+     MIT/GNU Scheme character set
+
+ (r:char-not-from <char-set>)
+     matches one character not from the specified 
+     MIT/GNU Scheme character set
+
+     MIT/GNU Scheme provides a variety of character sets,
+     but you can make your own with the Scheme procedures
+     char-set and string->char-set.
+
+Patterns can be combined to make compound patterns:
+
+ (r:seq <pattern> ...)
+     This pattern matches each of the argument patterns in sequence,
+     from left to right
+
+ (r:alt <pattern> ...)  
+     This pattern tries each argument pattern from left to right,
+     until one of these alternatives matches.  If none matches then
+     this pattern does not match.
+
+ (r:repeat <min> <max> <pattern>)
+     This pattern tries to match the given argument pattern a minimum
+     of min times but no more than a maximum of max times.  If max is
+     given as #f then there is no maximum specified.  Note that if
+     max=min the given pattern must be matched exactly that many
+     times.
+
+Because these are all Scheme procedures (in the file regexp.scm) you
+can freely mix these with any Scheme code.
+
+Here are some examples:
+
+  Pattern:  (r:seq (r:quote "a") (r:dot) (r:quote "c"))
+  Matches:  "abc" and "aac" and "acc" 
+
+  Pattern:  (r:alt (r:quote "foo") (r:quote "bar") (r:quote "baz"))
+  Matches:  "foo" and "bar" and "baz" 
+
+  Pattern:  (r:repeat 3 5 (r:alt (r:quote "cat") (r:quote "dog")))
+  Matches:  "catdogcat" and "catcatdogdog" and "dogdogcatdogdog"
+            but not "catcatcatdogdogdog"
+
+  Pattern:  (let ((digit 
+                   (r:char-from (string->char-set "0123456789"))))
+              (r:seq (r:bol)
+                     (r:quote "[")
+                     digit
+                     digit
+                     (r:quote "]")
+                     (r:quote ".")
+                     (r:quote " ")
+                     (r:char-from (char-set #\a #\b))
+                     (r:repeat 3 5 (r:alt (r:quote "cat") (r:quote "dog")))
+                     (r:char-not-from (char-set #\d #\e #\f))
+                     (r:eol)))
+  Matches:  "[09]. acatdogdogcats" but not
+            "[10]. ifacatdogdogs" nor
+            "[11]. acatdogdogsme"
+
+In the file regexp.scm we define an interface to the grep utility,
+which allows a Scheme program to call grep with a regular expression
+(constructed from the given pattern) on a given file name.  The grep
+utility extracts lines that contain a substring that can match the
+given pattern.
+
+So, for example: given the test file test.txt (supplied) we can find 
+the lines in the file that contain a match to the given pattern.
+
+(pp
+ (r:grep (r:seq " "
+                (r:repeat 3 5 (r:alt (r:quote "cat") (r:quote "dog")))
+                (r:eol)) 
+         "tests.txt"))
+("[09]. catdogcat" "[10]. catcatdogdog" "[11]. dogdogcatdogdog")
+;Unspecified return value
+
+Note that the pretty-printer (pp) returns an unspecified value, after
+printing the list of lines that grep found matching the pattern
+specified.
+
+-------------
+Problem 1.1: Warmup
+
+In the traditional regular expression language the asterisk (*)
+operator following a subpattern means zero-or-more copies of the
+subpattern and the plus-sign (+) operator following a subpattern means
+one-or-more copies of the subpattern.  Define Scheme procedures r:*
+and r:+ to take a pattern and iterate it as necessary.  This can be
+done in terms of r:repeat.
+
+Demonstrate your procedures on real data in complex patterns.
+-------------
+
+
+
+     A Subtle Bug, One Bad Joke, Two Tweaks, and a Revelation
+
+Ben Bitdiddle has noticed a problem with our implementation of
+(r:repeat <min> <max> <pattern>).
+
+The use of (r:seq expr "\\|") at the end of the r:repeat procedure is
+a bit dodgy.  This code fragment compiles to an ERE Alternation
+regular expression of the form (expr|).  (See 9.4.7 of the POSIX
+regular expression document.)
+
+This relies on the fact that alternation with something and nothing is
+the equivalent of saying "one or none".  That is: (expr|) denotes one
+or no instances of expr.  Unfortunately, this depends on an
+undocumented GNU extension to the formal POSIX standard for REs.
+
+Specifically, section 9.4.3 states that a vertical line appearing
+immediately before a close parenthesis (or immediately after an open
+parenthesis) produces undefined behavior.  In essence, an RE must not
+be a null sequence.
+
+GNU grep just happens to Do The Right Thing (tm) when presented with
+(x|).  Not all grep implementations are as tolerant.
+
+Therefore, Ben asks his team of three code hackers (Louis, Alyssa and
+his niece Bonnie) to propose alternative workarounds.  Ultimately, he
+proposes his own patch, which you will implement.
+
+
+ * Louis Reasoner suggests that a simple, elegant fix would be to
+   replace the code fragment (r:seq expr "\\|") with a straight-
+   forward call to (r:repeat 0 1 expr).
+
+
+ * Alyssa P. Hacker proposes that an alternative fix would be to
+   rewrite the else clause of r:repeat to compile (r:repeat 3 5 <x>)
+   into the equivalent of (xxx|xxxx|xxxxx) instead of the naughty
+   xxx(x|)(x|) non-POSIX-compliant undefined regular expression.
+   She refers to section 9.4.7 of the POSIX regular expression doc.
+
+
+ * Bonnie Bitdiddle points to the question mark (?) operator in
+   section 9.4.6.4 and proposes that a better fix would be to
+   implement an r:? operator then replace (r:seq expr "\\|")
+   with (r:? expr).
+
+
+ * Meanwhile, Ben looks closely at the RE spec and has a revelation.
+   He proposes that r:repeat be re-implemented to emit Interval
+   expressions.  See section 9.3.6.5 of the POSIX documentation.
+   Please try not to get sick.
+
+-------------
+Problem 1.2: The Proposals
+
+Let's very briefly consider each proposal:
+
+a. Everyone in the room immediately giggles at Louis' silly joke.
+   What's so funny about it?  That is, what's wrong with this idea?
+
+   A one-sentence punchline will do.
+
+b. What advantages does Bonnie's proposal have over Alyssa's
+   in terms of both code and data?
+
+   A brief, concise yet convincing few sentences suffices.
+
+c. What advantage does Ben's proposal have over all the others?
+   Specifically, ponder which section of the POSIX document he cites
+   versus which sections the others cite, then take a quick peek at
+   Problem 1.5 below and consider the implications.  Also, consider
+   the size of the output strings in this new code as well as the
+   overall clarity of the code.
+
+   Again, a brief sentence or two is sufficient.
+
+d. Following Ben's proposal, re-implement r:repeat to emit Interval
+   expressions.  Hint: Scheme's number->string procedure should be
+   handy.  Caveat: beware the backslashes.
+
+   Show the output it generates on a few well-chosen sample inputs.
+   Demonstrate your procedure on real data in complex patterns.
+-------------
+
+
+                           Too Much Nesting
+
+Our program produces excessively nested regular expressions: it makes
+groups even when they are not necessary.  For example, the following
+simple pattern leads to an overly complex regular expression:  
+
+   (display (r:seq (r:quote "a") (r:dot) (r:quote "c")))
+   \(\(a\).\(c\)\)
+
+Another problem is that BREs may involve back-references.  (See
+9.3.6.3 of the POSIX regular expression documentation.)  A
+back-reference refers to a previously parenthesized subexpression.  So
+it is important that the parenthesized subexpressions be ones
+explicitly placed by the author of the pattern.  (Aargh! This is one
+of the worst ideas I (GJS) have ever heard of -- grouping, which is
+necessary for iteration, was confused with naming for later reference.
+What a crock!)
+
+-------------
+Problem 1.3: Optimization
+
+Edit our program to eliminate as much of the unnecessary nesting as
+you can.  Caution: there are subtle cases here that you have to watch
+out for.  What is such a case?  Demonstrate your better version of our
+program and show how it handles the subtleties.
+
+Hint: Our program uses strings as its intermediate representation as
+well as its result.  You might consider using a different intermediate
+representation.
+-------------
+
+-------------
+Problem 1.4: Back-references
+
+Add in a procedure for constructing back-references.
+Have fun getting confused about BREs.
+-------------
+
+                              Standards?
+
+                The best thing about standards is that 
+                there are so many to choose from.
+                              Tom Knight
+
+There are also Extended Regular Expressions (EREs) defined in the
+POSIX regular expression documentation.  Some software, such as egrep,
+uses this version of regular expressions.  Unfortunately EREs are not
+a conservative extension of BREs: ERE syntax is actually inconsistent
+with BRE syntax!  It is an interesting project to extend our Scheme
+pattern language so that the target can be either BREs or EREs.
+
+-------------
+Problem 1.5: Ugh!
+
+  a. What are the significant differences between BREs and EREs that
+  make this a pain?  List the differences that must be addressed.
+
+  b. How can the back end be factored so that our language can compile
+  into either kind of regular expression, depending on what is needed?
+  How can we maintain the abstract layer that is independent of the 
+  target regular expression language?  Explain your strategy.
+
+  c. Extend our implementation to have both back ends.
+
+Demonstrate your work by making sure that you can run egrep as well as
+grep, with equivalent results in cases that test the differences you
+found in part a.
+-------------
+
+           End of Problem Set.  Reference Material Follows.
+-----------------------------------------------------------------------
+
+The following is an excerpt from the Debian GNU/Linux man page on grep.
+
+REGULAR EXPRESSIONS
+    A  regular  expression  is a pattern that describes a set of strings.
+    Regular expressions are constructed analogously to arithmetic expres-
+    sions, by using various operators to combine smaller expressions.
+
+    Grep  understands three different versions of regular expression syn-
+    tax: "basic," "extended," and "perl."  In GNU grep, there is no  dif-
+    ference in available functionality using either of the first two syn-
+    taxes.  In other implementations, basic regular expressions are  less
+    powerful.   The  following  description  applies  to extended regular
+    expressions; differences for basic regular expressions are summarized
+    afterwards.   Perl  regular expressions add additional functionality,
+    but the implementation used here is undocumented and is not  compati-
+    ble with other grep implementations.
+
+    The  fundamental  building  blocks  are  the regular expressions that
+    match a single character.  Most characters, including all letters and
+    digits, are regular expressions that match themselves.  Any metachar-
+    acter with special meaning may be quoted by preceding it with a back-
+    slash.
+
+    A bracket expression is a list of characters enclosed by [ and ].  It
+    matches any single character in that list; if the first character  of
+    the  list  is  the  caret  ^ then it matches any character not in the
+    list.  For example, the regular expression [0123456789]  matches  any
+    single digit.
+
+    Within a bracket expression, a range expression consists of two char-
+    acters separated by a hyphen.  It matches any single  character  that
+    sorts  between the two characters, inclusive, using the locale's col-
+    lating sequence and character set.  For example,  in  the  default  C
+    locale,  [a-d] is equivalent to [abcd].  Many locales sort characters
+    in dictionary order, and in these  locales  [a-d]  is  typically  not
+    equivalent  to [abcd]; it might be equivalent to [aBbCcDd], for exam-
+    ple.  To obtain the traditional  interpretation  of  bracket  expres-
+    sions,  you  can  use  the C locale by setting the LC_ALL environment
+    variable to the value C.
+
+    Finally, certain named classes of characters  are  predefined  within
+    bracket  expressions,  as follows.  Their names are self explanatory,
+    and they are [:alnum:], [:alpha:], [:cntrl:],  [:digit:],  [:graph:],
+    [:lower:],    [:print:],   [:punct:],   [:space:],   [:upper:],   and
+    [:xdigit:].  For example, [[:alnum:]] means [0-9A-Za-z],  except  the
+    latter  form depends upon the C locale and the ASCII character encod-
+    ing, whereas the former is independent of locale and  character  set.
+    (Note that the brackets in these class names are part of the symbolic
+    names, and must be included in addition to  the  brackets  delimiting
+    the  bracket  list.)   Most metacharacters lose their special meaning
+    inside lists.  To include a literal ] place it  first  in  the  list.
+    Similarly,  to  include  a  literal  ^  place  it anywhere but first.
+    Finally, to include a literal - place it last.
+
+     The period .  matches any single character.  The symbol \w is a  syn-
+     onym for [[:alnum:]] and \W is a synonym for [^[:alnum]].
+
+     The  caret  ^  and  the dollar sign $ are metacharacters that respec-
+     tively match the empty string at the beginning and  end  of  a  line.
+     The  symbols  \<  and  \>  respectively match the empty string at the
+     beginning and end of a word.  The symbol \b matches the empty  string
+     at  the edge of a word, and \B matches the empty string provided it's
+     not at the edge of a word.
+
+     A regular expression may be followed by  one  of  several  repetition
+     operators:
+     ?      The preceding item is optional and matched at most once.
+     *      The preceding item will be matched zero or more times.
+     +      The preceding item will be matched one or more times.
+     {n}    The preceding item is matched exactly n times.
+     {n,}   The preceding item is matched n or more times.
+     {n,m}  The  preceding  item is matched at least n times, but not more
+            than m times.
+
+     Two regular expressions may be concatenated;  the  resulting  regular
+     expression  matches any string formed by concatenating two substrings
+     that respectively match the concatenated subexpressions.
+
+     Two regular expressions may be joined by the infix  operator  |;  the
+     resulting  regular  expression  matches  any  string  matching either
+     subexpression.
+
+     Repetition takes precedence over concatenation, which in  turn  takes
+     precedence  over  alternation.  A whole subexpression may be enclosed
+     in parentheses to override these precedence rules.
+
+     The backreference \n, where n is a single  digit,  matches  the  sub-
+     string  previously  matched by the nth parenthesized subexpression of
+     the regular expression.
+
+     In basic regular expressions the metacharacters ?, +, {, |, (, and  )
+     lose  their special meaning; instead use the backslashed versions \?,
+     \+, \{, \|, \(, and \).
+
+     Traditional egrep did not support the { metacharacter, and some egrep
+     implementations  support \{ instead, so portable scripts should avoid
+     { in egrep patterns and should use [{] to match a literal {.
+
+     GNU egrep attempts to support traditional usage by assuming that { is
+     not  special if it would be the start of an invalid interval specifi-
+     cation.  For example, the shell command egrep '{1' searches  for  the
+     two-character  string  {1  instead of reporting a syntax error in the
+     regular expression.  POSIX.2 allows this behavior  as  an  extension,
+     but portable scripts should avoid it.
+
+GNU Project                      2002/01/22                          GREP(1)
+
+;;;; Scheme Regular Expression Language Implementation -- regexp.scm
+
+(define (r:dot) ".")
+
+(define (r:bol) "^")
+
+(define (r:eol) "$")
+
+(define (r:quote string)
+  (r:seq
+   (call-with-output-string		; see RefMan section 14.3
+    (lambda (port)
+      (let ((end (string-length string)))
+        (do ((i 0 (+ i 1))) ((not (< i end))) ; see RefMan 2.9
+          (let ((c (string-ref string i)))
+            (if (or (char=? c #\.)
+                    (char=? c #\[)
+                    (char=? c #\\)
+                    (char=? c #\^)
+                    (char=? c #\$)
+		    (char=? c #\*))
+                (write-char #\\ port))
+            (write-char c port))))))))
+
+(define (r:char-from char-set)		; see RefMan section 5.6
+  (let ((members (char-set-members char-set)))
+    (cond ((not (pair? members))
+	   (r:seq))
+          ((not (pair? (cdr members)))
+	   (r:quote (string (car members))))
+          (else
+           (%char-from #f members)))))
+
+(define (r:char-not-from char-set)
+  (%char-from #t (char-set-members char-set)))
+
+(define (%char-from negate? members)
+  (let ((right? (memv #\] members))
+        (caret? (memv #\^ members))
+        (hyphen? (memv #\- members))
+        (others
+         (delete-matching-items members
+                                (lambda (c)
+                                  (or (char=? c #\])
+                                      (char=? c #\^)
+                                      (char=? c #\-))))))
+    (if (and caret?
+             hyphen?
+             (not right?)
+             (not negate?)
+             (null? others))
+        "[-^]"
+        (string-append "["
+                       (if negate? "^" "")
+                       (if right? "]" "")
+                       (list->string others)
+                       (if caret? "^" "")
+                       (if hyphen? "-" "")
+                       "]"))))
+
+;;; Means of combination for patterns
+
+(define (r:seq . exprs)
+  (string-append "\\(" (apply string-append exprs) "\\)"))
+
+(define (r:alt . exprs)
+  (if (pair? exprs)
+      (apply r:seq
+             (cons (car exprs)
+                   (append-map (lambda (expr)
+                                 (list "\\|" expr))
+                               (cdr exprs))))
+      (r:seq)))
+
+(define (r:repeat min max expr)
+  (if (not (exact-nonnegative-integer? min))
+      (error "Min must be non-negative integer:" min))
+  (if max
+      (begin
+        (if (not (exact-nonnegative-integer? max))
+            (error "Max must be non-negative integer:" max))
+        (if (not (<= min max))
+            (error "Min not less than max:" min max))))
+  (cond ((not max)
+	 (apply r:seq
+		(append (make-list min expr)
+			(list expr "*"))))
+	((= max min)
+	 (apply r:seq (make-list min expr)))
+	(else
+	 (apply r:seq
+		(append (make-list min expr)
+			(make-list (- max min)
+				   (r:seq expr "\\|")))))))
+
+;;; The following magic allows a program in MIT/GNU Scheme to call the
+;;; grep system utility, returning the list of grep output lines to
+;;; the caller.  You can make similar mechanisms to call other system
+;;; utilities.
+
+(load-option 'synchronous-subprocess)
+
+(define (r:grep expr filename)
+  (r:grep-like "grep" '() expr filename))
+
+(define (r:egrep expr filename)
+  (if (eq? microcode-id/operating-system 'nt)
+      (r:grep-like "grep" '("-E") expr filename)
+      (r:grep-like "egrep" '() expr filename)))
+
+(define (r:grep-like program options expr filename)
+  (let ((port (open-output-string)))
+    (and (= (run-synchronous-subprocess program
+	      (append options
+		      (list "-e" expr (->namestring filename)))
+	      'output port)
+            0)
+	 (r:split-lines (get-output-string port)))))
+
+(define (r:split-lines string)
+  (reverse
+   (let ((end (string-length string)))
+     (let loop ((i 0) (lines '()))
+       (if (< i end)
+	   (let ((j
+		  (substring-find-next-char string i end #\newline)))
+	     (if j
+		 (loop (+ j 1)
+		       (cons (substring string i j) lines))
+		 (cons (substring string i end) lines)))
+	   lines)))))
+
+#|
+;;; An alternate implementation using MIT/GNU Scheme's internal
+;;; regular-expression interpreter.
+
+(define (r:grep expr filename)
+  (call-with-input-file filename
+    (lambda (port)
+      (let loop ((lines '()))
+	(let ((line (read-line port)))
+	  (if (eof-object? line)
+	      (reverse lines)
+	      (loop (if (re-string-search-forward expr line #f)
+			(cons line lines)
+			lines))))))))
+|#
+
+#|
+;;; For example...
+
+;;; Note, the result of the next two requests were not in this file
+;;; when the requests were made!
+
+(pp (r:grep (r:quote "r:sex") "regexp.scm"))
+("(pp (r:grep (r:quote \"r:sex\") \"regexp.scm\"))")
+;Unspecified return value
+
+(pp (r:grep (r:quote "r:seq") "regexp.scm"))
+("  (r:seq"
+ "\t   (r:seq))"
+ "(define (r:seq . exprs)"
+ "      (apply r:seq"
+ "      (r:seq)))"
+ "\t (apply r:seq"
+ "\t (apply r:seq (make-list min expr)))"
+ "\t (apply r:seq"
+ "\t\t\t\t   (r:seq expr \"\\\\|\")))))))"
+ "(pp (r:grep (r:quote \"r:seq\") \"regexp.scm\"))"
+ "(pp (r:grep (r:seq (r:quote \"a\") (r:dot) (r:quote \"c\")) \"tests.txt\"))"
+ " (r:grep (r:seq \" \""
+ "    (r:seq (r:bol)")
+;Unspecified return value
+
+(pp (r:grep (r:seq (r:quote "a") (r:dot) (r:quote "c")) "tests.txt"))
+("[00]. abc"
+ "[01]. aac"
+ "[02]. acc"
+ "[03]. zzzaxcqqq"
+ "[10]. catcatdogdog"
+ "[12]. catcatcatdogdogdog")
+;Unspecified return value
+
+;;; And...
+
+(pp (r:grep (r:alt (r:quote "foo") (r:quote "bar") (r:quote "baz"))
+	    "tests.txt"))
+("[05]. foo" "[06]. bar" "[07]. foo bar baz quux")
+;Unspecified return value
+
+
+(pp (r:grep (r:repeat 3 5 (r:alt (r:quote "cat") (r:quote "dog")))
+	    "tests.txt"))
+("[09]. catdogcat"
+ "[10]. catcatdogdog"
+ "[11]. dogdogcatdogdog"
+ "[12]. catcatcatdogdogdog"
+ "[13]. acatdogdogcats"
+ "[14]. ifacatdogdogs"
+ "[15]. acatdogdogsme")
+;Unspecified return value
+
+(pp
+ (r:grep (r:seq " "
+		(r:repeat 3 5 (r:alt (r:quote "cat") (r:quote "dog")))
+		(r:eol)) 
+         "tests.txt"))
+("[09]. catdogcat" "[10]. catcatdogdog" "[11]. dogdogcatdogdog")
+;Unspecified return value
+
+(pp
+ (r:grep
+  (let ((digit 
+	 (r:char-from (string->char-set "0123456789"))))
+    (r:seq (r:bol)
+	   (r:quote "[")
+	   digit
+	   digit
+	   (r:quote "]")
+	   (r:quote ".")
+	   (r:quote " ")
+	   (r:char-from (char-set #\a #\b))
+	   (r:repeat 3 5 (r:alt "cat" "dog"))
+	   (r:char-not-from (char-set #\d #\e #\f))
+	   (r:eol)))
+  "tests.txt"))
+("[13]. acatdogdogcats")
+;Unspecified return value
+|#
+
+;;; This is the file tests.txt
+
+[00]. abc
+[01]. aac
+[02]. acc
+[03]. zzzaxcqqq
+[04]. abdabec
+
+[05]. foo
+[06]. bar
+[07]. foo bar baz quux
+[08]. anything containing them
+
+[09]. catdogcat
+[10]. catcatdogdog
+[11]. dogdogcatdogdog
+[12]. catcatcatdogdogdog
+
+[13]. acatdogdogcats
+[14]. ifacatdogdogs
+[15]. acatdogdogsme
diff --git a/ps01_grep/regexp.scm b/ps01_grep/regexp.scm
new file mode 100644
index 0000000..a7f2305
--- /dev/null
+++ b/ps01_grep/regexp.scm
@@ -0,0 +1,230 @@
+;;;; Scheme Regular Expression Language Implementation -- regexp.scm
+
+(define (r:dot) ".")
+
+(define (r:bol) "^")
+
+(define (r:eol) "$")
+
+(define (r:quote string)
+  (r:seq
+   (call-with-output-string		; see RefMan section 14.3
+    (lambda (port)
+      (let ((end (string-length string)))
+        (do ((i 0 (+ i 1))) ((not (< i end))) ; see RefMan 2.9
+          (let ((c (string-ref string i)))
+            (if (or (char=? c #\.)
+                    (char=? c #\[)
+                    (char=? c #\\)
+                    (char=? c #\^)
+                    (char=? c #\$)
+		    (char=? c #\*))
+                (write-char #\\ port))
+            (write-char c port))))))))
+
+(define (r:char-from char-set)		; see RefMan section 5.6
+  (let ((members (char-set-members char-set)))
+    (cond ((not (pair? members))
+	   (r:seq))
+          ((not (pair? (cdr members)))
+	   (r:quote (string (car members))))
+          (else
+           (%char-from #f members)))))
+
+(define (r:char-not-from char-set)
+  (%char-from #t (char-set-members char-set)))
+
+(define (%char-from negate? members)
+  (let ((right? (memv #\] members))
+        (caret? (memv #\^ members))
+        (hyphen? (memv #\- members))
+        (others
+         (delete-matching-items members
+                                (lambda (c)
+                                  (or (char=? c #\])
+                                      (char=? c #\^)
+                                      (char=? c #\-))))))
+    (if (and caret?
+             hyphen?
+             (not right?)
+             (not negate?)
+             (null? others))
+        "[-^]"
+        (string-append "["
+                       (if negate? "^" "")
+                       (if right? "]" "")
+                       (list->string others)
+                       (if caret? "^" "")
+                       (if hyphen? "-" "")
+                       "]"))))
+
+;;; Means of combination for patterns
+
+(define (r:seq . exprs)
+  (string-append "\\(" (apply string-append exprs) "\\)"))
+
+(define (r:alt . exprs)
+  (if (pair? exprs)
+      (apply r:seq
+             (cons (car exprs)
+                   (append-map (lambda (expr)
+                                 (list "\\|" expr))
+                               (cdr exprs))))
+      (r:seq)))
+
+(define (r:repeat min max expr)
+  (if (not (exact-nonnegative-integer? min))
+      (error "Min must be non-negative integer:" min))
+  (if max
+      (begin
+        (if (not (exact-nonnegative-integer? max))
+            (error "Max must be non-negative integer:" max))
+        (if (not (<= min max))
+            (error "Min not less than max:" min max))))
+  (cond ((not max)
+	 (apply r:seq
+		(append (make-list min expr)
+			(list expr "*"))))
+	((= max min)
+	 (apply r:seq (make-list min expr)))
+	(else
+	 (apply r:seq
+		(append (make-list min expr)
+			(make-list (- max min)
+				   (r:seq expr "\\|")))))))
+
+;;; The following magic allows a program in MIT/GNU Scheme to call the
+;;; grep system utility, returning the list of grep output lines to
+;;; the caller.  You can make similar mechanisms to call other system
+;;; utilities.
+
+(load-option 'synchronous-subprocess)
+
+
+(define (r:grep expr filename)
+  (r:grep-like "grep" '() expr filename))
+
+(define (r:egrep expr filename)
+  (if (eq? microcode-id/operating-system 'nt)
+      (r:grep-like "grep" '("-E") expr filename)
+      (r:grep-like "egrep" '() expr filename)))
+
+(define (r:grep-like program options expr filename)
+  (let ((port (open-output-string)))
+    (and (= (run-synchronous-subprocess program
+	      (append options
+		      (list "-e" expr (->namestring filename)))
+	      'output port)
+            0)
+	 (r:split-lines (get-output-string port)))))
+
+(define (r:split-lines string)
+  (reverse
+   (let ((end (string-length string)))
+     (let loop ((i 0) (lines '()))
+       (if (< i end)
+	   (let ((j
+		  (substring-find-next-char string i end #\newline)))
+	     (if j
+		 (loop (+ j 1)
+		       (cons (substring string i j) lines))
+		 (cons (substring string i end) lines)))
+	   lines)))))
+
+#|
+;;; An alternate implementation using MIT/GNU Scheme's internal
+;;; regular-expression interpreter.
+
+(define (r:grep expr filename)
+  (call-with-input-file filename
+    (lambda (port)
+      (let loop ((lines '()))
+	(let ((line (read-line port)))
+	  (if (eof-object? line)
+	      (reverse lines)
+	      (loop (if (re-string-search-forward expr line #f)
+			(cons line lines)
+			lines))))))))
+|#
+
+#|
+;;; For example...
+
+;;; Note, the result of the next two requests were not in this file
+;;; when the requests were made!
+
+(pp (r:grep (r:quote "r:sex") "regexp.scm"))
+("(pp (r:grep (r:quote \"r:sex\") \"regexp.scm\"))")
+;Unspecified return value
+
+(pp (r:grep (r:quote "r:seq") "regexp.scm"))
+("  (r:seq"
+ "\t   (r:seq))"
+ "(define (r:seq . exprs)"
+ "      (apply r:seq"
+ "      (r:seq)))"
+ "\t (apply r:seq"
+ "\t (apply r:seq (make-list min expr)))"
+ "\t (apply r:seq"
+ "\t\t\t\t   (r:seq expr \"\\\\|\")))))))"
+ "(pp (r:grep (r:quote \"r:seq\") \"regexp.scm\"))"
+ "(pp (r:grep (r:seq (r:quote \"a\") (r:dot) (r:quote \"c\")) \"tests.txt\"))"
+ " (r:grep (r:seq \" \""
+ "    (r:seq (r:bol)")
+;Unspecified return value
+
+(pp (r:grep (r:seq (r:quote "a") (r:dot) (r:quote "c")) "tests.txt"))
+("[00]. abc"
+ "[01]. aac"
+ "[02]. acc"
+ "[03]. zzzaxcqqq"
+ "[10]. catcatdogdog"
+ "[12]. catcatcatdogdogdog")
+;Unspecified return value
+
+;;; And...
+
+(pp (r:grep (r:alt (r:quote "foo") (r:quote "bar") (r:quote "baz"))
+	    "tests.txt"))
+("[05]. foo" "[06]. bar" "[07]. foo bar baz quux")
+;Unspecified return value
+
+
+(pp (r:grep (r:repeat 3 5 (r:alt (r:quote "cat") (r:quote "dog")))
+	    "tests.txt"))
+("[09]. catdogcat"
+ "[10]. catcatdogdog"
+ "[11]. dogdogcatdogdog"
+ "[12]. catcatcatdogdogdog"
+ "[13]. acatdogdogcats"
+ "[14]. ifacatdogdogs"
+ "[15]. acatdogdogsme")
+;Unspecified return value
+
+(pp
+ (r:grep (r:seq " "
+		(r:repeat 3 5 (r:alt (r:quote "cat") (r:quote "dog")))
+		(r:eol)) 
+         "tests.txt"))
+("[09]. catdogcat" "[10]. catcatdogdog" "[11]. dogdogcatdogdog")
+;Unspecified return value
+
+(pp
+ (r:grep
+  (let ((digit 
+	 (r:char-from (string->char-set "0123456789"))))
+    (r:seq (r:bol)
+	   (r:quote "[")
+	   digit
+	   digit
+	   (r:quote "]")
+	   (r:quote ".")
+	   (r:quote " ")
+	   (r:char-from (char-set #\a #\b))
+	   (r:repeat 3 5 (r:alt "cat" "dog"))
+	   (r:char-not-from (char-set #\d #\e #\f))
+	   (r:eol)))
+  "tests.txt"))
+("[13]. acatdogdogcats")
+;Unspecified return value
+|#
\ No newline at end of file
diff --git a/ps01_grep/tests.txt b/ps01_grep/tests.txt
new file mode 100644
index 0000000..62d2ec9
--- /dev/null
+++ b/ps01_grep/tests.txt
@@ -0,0 +1,19 @@
+[00]. abc
+[01]. aac
+[02]. acc
+[03]. zzzaxcqqq
+[04]. abdabec
+
+[05]. foo
+[06]. bar
+[07]. foo bar baz quux
+[08]. anything containing them
+
+[09]. catdogcat
+[10]. catcatdogdog
+[11]. dogdogcatdogdog
+[12]. catcatcatdogdogdog
+
+[13]. acatdogdogcats
+[14]. ifacatdogdogs
+[15]. acatdogdogsme
diff --git a/to_athena.sh b/to_athena.sh
index 6f34b24..fa45403 100755
--- a/to_athena.sh
+++ b/to_athena.sh
@@ -2,4 +2,4 @@
 
 for f in `find . -iname *~`; do rm $f; done
 for f in `find . -iname *.bak`; do rm $f; done
-rsync -arv * bnewbold@linux.mit.edu:6.945/
+rsync -arv ps* bnewbold@linux.mit.edu:6.945/