SMiLe and Tetris

• **Due:** 11:00pm Tuesday, April 21
• Checkpoint: 11:00pm Tuesday, April 21: submit one of the two parts
• Due: 11:00pm Tuesday, April 28: full assignment due
• Files:
  • fork wellesleycs251 / cs251-tetris, share with bpw
  • Programming answers in smile.sml, tetris_assignment.rb
  • Time estimates in time.txt
• Submission: commit and push your completed work to your Bitbucket fork.
• Relevant reading:
  • SML and Ruby References
  • Especially SML notes on evaluation rules for pattern-matching, etc.
• Tools:
  • Mercurial
  • SML/NJ
  • Ruby
• Collaboration:
  • All problems fall under the group collaboration policy. You may work with one or zero partners to produce one solution for this assignment. You may discuss ideas with other groups but your group’s writing and code must be due to your group members only.
• Advice:
  • Smiling and playing Tetris are both fun. Playing too much Tetris can make the assignment take longer than necessary; smiling too much cannot! :)

1. SMiLe Interpreter [50 points]

In class, we have been building an interpreter for our (currently) dynamically-typed subset of ML (alternately called SMiLe and SortaML). In this assignment, you will answer some questions about the cases we have completed and you will complete the interpreter by finish the last cases of the eval function: Fun bindings and the Case expression, i.e., pattern-matching.

1. Understanding Environments and Closures (Again)

   Add English descriptions at each (* Describe *) comment in smile.sml to document precisely what the steps of the Fn and Apply cases do and how they interact with each other.

2. Fun Bindings

   We implemented Val bindings in Let expressions together in class. You will add support for Fun bindings.

   A Fun(f,x,e) binding has three pieces: a string giving the name for the function (f), a string giving the name for the parameter (x), and an expr for the body (e). Evaluating a Fun binding as part of a Let expression should produce an environment that extends the current environment with an association of f and a closure for the SMiLe function defined. The closure must support recursion, meaning that the environment it saves must have a mapping from f to the closure itself. It is legal for the SMiLe expression Var f to appear inside e, and this must work when an application of the closure is evaluated. (Hint, this is where the ref in the type held by ClosureV becomes important.) See the factorial programs included in smile.sml for examples.

   Make sure to document and test your code.

3. Case Expressions

   Implement Case expressions for SMiLe following the semantics of case expressions in ML. A Case expression carries an expression, e, to evaluate and match against a pattern list. The pattern datatype is given in smile.sml. Altogether, the whole section of eval that handle the SMiLe Case expression takes about 30 lines of ML code in our sample solution, as a ball-park figure. To accomplish pattern-matching for SMiLe, we added three ML helper functions, and suggest you do similarly:

   • match is a recursive function that checks to see if the evaluated expression’s value matches a single pattern. If the pattern and value match, match returns SOME of a list of (string * value) pairs representing all the bindings that the pattern introduces. If it does not match, match returns NONE. The implementation uses ML pattern-matching to match simultaneously on a given pattern constructor and value constructor.

     Given a value v and pattern p, either p matches v or not. If it does, the match produces a list of string * value pairs; order in the list does not matter. Assume that one pattern binds each possible variable at most once. In other words, no pattern will include VarP "x" more than once. Make sure to respect this assumption in your test code … or implement a check if you prefer.

     The rules for matching should be unsurprising:

     • Wildcard matches everything and produces the empty list of bindings.
     • VarP s matches any value v and produces the one-element list holding (s,v).
     • UnitP matches only UnitV and produces the empty list of bindings.
     • BoolP false matches only BoolV false and produces the empty list of bindings (and similarly for other booleans).
     • IntP 17 matches only IntV 17 and produces the empty list of bindings (and similarly for other integers).
     • StringP "smile" matches only StringV "smile" and produces the empty list of bindings (and similarly for other strings).
     • TupleP ps matches a value of the form TupleV vs if ps and vs have the same length and for all i, the ith element of ps matches the ith element of vs. The list of bindings produced is all the lists from the nested pattern matches appended together.
     • TagP(s1,p) matches TagV(s2,v) if s1 and s2 are the same string (you can compare them with =) and p matches v. The list of bindings produced is the list from the nested pattern match. We call the strings s1 and s2 the constructor name.
     • Nothing else matches.
   • tuplematch is a recursive helper function used when matching tuple patterns recursively in match.
   • evalcase is a recursive function that iterates through the list of (pattern * expr) cases given in the Case expression, applying match to each pattern. For the first pattern that matches, evalcase then evaluates the associated result expr from the list, using the current environment extended with all the bindings introduced by the pattern. If no pattern matches, raise NoMatch.

   In addition to implementing the matching code, write SMiLe programs to test it.

4. Optional Extension (0 points)

   As an optional extension, change Val, Fun and Fn to support arbitrary binding-introducing patterns instead of just a parameter name. This will involve changing the type of arguments to these constructors from sym to pattern and using the same pattern-matching code you built for Case in every function application.

5. Optional Challenge (0 points)

   As an optional challenge problem, implement basic type-checking for SMiLe:

   • Define an ML datatype, typ, describing types of SMiLe expressions. Many of its constructors will mirror the constructors of the value datatype. Start without type variables – add those later if you get a simpler type-checker working. Also start without support for type-checking patterns or constructors. If you succeed in type-checking these simpler programs, consider adding explicit DataType bindings to the SMiLe language, and accompanying support in typ for datatypes.
   • Define an ML function, typecheck : expr -> typ -> bool, that takes a SMiLe expression and a SMiLe type and checks whether that expression has that type. Follow the type-checking rules we have established for ML. (Again, start without type variables, patterns, or constructors.) Remember, your job here is only to check the given type, not to infer it. (Naturally, to test your typecheck implementation, you will have to manually infer types to pass to typecheck.)

2. Tetris [50 points]

This assignment is adopted from CSE 341 at the University of Washington.

See intructions for installing or using ruby and irb, an interpreter and a REPL for the Ruby language. There is minor configuration to do on tempest (cs.wellesley.edu – one line to a configuration file). There are also instructions for installing on your own machine. [Windows instructions may currently include a broken link.]

Please see the PDF tetris instructions, also distributed with the starter code.