Homework 08

Principles of Functional Programming                Spring 2019

                        Out: Thursday, 28 March 2019

                            Due: Tuesday, 2 April 2019 at 23:59 EDT

0 Introduction

This homework will focus on the SML module system. By working with modules and writing them from scratch, you will hopefully better understand the relation- ship between signatures, structures, and functors, and the ways in which they can be meaningfully used.

0.1 Getting The Assignment

The starter files for the homework assignment have been distributed through our

git repository, as usual. To learn how to use it, read the documentation.

0.2 Collaboration

We have a homework collaboration policy.

In keeping with this policy, in the handout is a collab.txt file. In this file, please document your collaboration (in the manner specified in the course policy).

It is very important that you do this. If you appear to have collaborated with anyone not listed in your collab.txt file, this could be considered an academic integrity violation, and may result in disciplinary action.

0.3 Submission

Code submissions will be handled through Autolab and Gradescope.

To submit your code asignment, SSH into the unix andrew servers, and navigate to the hw/08 directory of the git repo. You can then run make submit and follow the prompts. It should make a .tar file containing your code, and submit it to Autolab. Please go to the Autolab webpage (linked above) and review the results of the checkscript (described below) and make sure your work was submitted properly. Please get help from the course staff immediately if this does not work for you.

When you upload your code submission to Autolab, the Autolab handin script will do some basic checks on your submission: making sure that the file names are correct, making sure that no files are missing, making sure that your code compiles cleanly. You can view the results of the handin script by clicking the number (usually either 41297.0 or 0.0) corresponding to the “check” section of your latest handin on the “Handin History” page. If this number is 41297.0, your submission failed the check script; if it is 0.0, it passed. Note that the handin script is not a grading script. If you passed the handin script, then your code will be graded, but will not necessarily receive full credit.

Your Autolab submission must contain all the code that you want to have graded for this assignment, and must compile cleanly in Autolab. We reserve the right to penalize or not grade any submission which does not pass the handin script, which does not compile on Autolab, or which does not obey the instructions in the handout.

Please submit your written solutions to Gradescope. Note that we only accept submissions in typed PDF form. We reserve the right to not grade your submission if you submit handwritten work or other formats besides PDF (e.g. MS Word files, images, etc.). When you submit, you will be asked to indicate which page of your submission each problem occurs on. Please put each problem on its own page, and use Gradescope to indicate which page the problem occurs on. If we cannot find your problem quickly, we reserve the right to not grade it.

Please contact course staff if you have any questions. If you attempt to contact us close to the deadline, please be aware that we may not be able to respond before the deadline.

0.4 Due Date

This assignment is due on Tuesday, 2 April 2019 at 23:59 EDT. Remember that you have a total of three late days this semester.

1 Hype for Types

Task 1.1 (1 pts).

What is the type of x in the following code? If it is not well-typed, explain why not.


Task 1.2 (8 pts).

State whether the following declarations/definitions belong in a structure, belong in a signature, or could be found in both.

1. val x : int

2. val x = 10

3. type t

4. type t = int

5. exception E

6. exception I of int

7. datatype t = Foo of int | Bar of bool

8. fun f x = x + 10

Task 1.3 (2 pts).

Does this piece of code typecheck? If so, give the type of y. If not, explain why not.


2 Filesystems

Afilesystemisadatastructurethatkeepstrackofandcontrolsaccessandnavi- gationtofilesstoredonadisk.Thefilesystemkeepstrackofthenestingstructure ofdirectoriesandthefilesinsidethem.Thoughtherearemanylowleveldetails involvedintheimplementationofallpracticalfilesystems,atahighlevel,afile systemisjustatree.Atthenodesofthistreearedirectories,andattheleaves areordinaryfiles.Forexample,iftherearetwodirectoriesinmyhomedirectory, 15150andmemes,andthe15150directorycontainshomeworksandlabs,andthe memes directory contains surprised-pikachu.jpg, then this can be represented as atree:


In this assignment, you’ll be creating a filesystem that can store, create, and delete files and directories, edit files, and navigate up and down between directories. At all times, the filesystem will keep track of a “current” node in its file tree: the current working directory of its user. It will allow fast (constant-time) access to the child and parent directories of that directory. For simplicity, it will only allow up to two files per directory.

In order to implement such a filesystem, you will need to create a tree-like data structure that is capable of keeping track of a “current” node in the tree, finding that node’s parent and children in O(1) time, and creating or deleting children in O(1) time. The simple tree definition that we’ve seen in this class so far

 datatype   ’ a   tree   =   Empty   |   Node   of   ’ a   tree   *   ’ a   *   ’ a   tree

will not suffice, since, even if the tree is balanced, finding an arbitrary node can only be done in O(log(n)) time in the worst case. You’ll be implementing some- thing much better.

2.1 Zippers

A zipper is a classic functional data structure. A functional data structure is one that doesn’t require any destructive modification or state in its implementation. In other courses, you may have seen arrays, hash tables, and other data structures that involved modifying cells inside of them, removing elements, or keeping track of pointers. Functional data structures don’t need any of that. They can be defined using simple datatype declarations and clever implementations. Despite not using all the features that imperative data structures have, functional data structures are never more than O(log(n)) slower than their imperative counterparts, and are sometimes just as fast. In particular, zippers are just as efficient asymptotically as their imperative counterparts.

Zippers are augmentations of ordinary data structures (lists, trees, etc) that allow them to keep track of an element that is “in-focus” and easily access elements that are adjacent to that element. For this reason, they’re great for filesystems, which need to keep track of a current directory and navigate to and from it easily.

The zipper you’ll be implementing in this assignment is a tree zipper. It keeps track of the current “in-focus” node in the tree and allows easy access to the parent and children of that node. It does this by keeping track of a tuple whose first element is the subtree rooted at the in-focus node, and whose second element is a list whose elements are subtrees rooted at each of that node’s ancestors, in order from closest to furthest, all the way up to the root. Each ancestor has a placeholder, a “hole,” at its subtree where the previous tree in the list would have been. Let’s see an example using the following tree:


The first tree in the tuple is the tree in focus: labs. The first tree in the list is the subtree rooted at labs’s parent, but with a hole (o) where labs was. The second one is the parent of the second tree, with a hole where the second tree would go. Make sure you understand how you could reassemble this list into the original tree.

To navigate from a child to a parent in a tree zipper, cons off the first element in the list. If there isn’t one, you’re at the root of the tree and so can’t navigate to a parent. Replace the o in that first element with the first element of the tuple, and make that the new first element of the tuple. Make the tail of the list the new second element of the tuple. For example, this moves the focus from labs to 15150:


To navigate from a parent to a child, take the first element in the tuple and pick the child of it that you want to move to. Place a o where the child was and cons the resulting tree to the list in the tuple. Make the child the new first element of the tuple. If home were in focus, this would move the focus from home to memes:


2.2 Implementation

The datatype for a tree zipper involves two declarations: one for the tree structure and one for the tuple. Our particular tree zipper will be a named tree zipper with leaves, in which every node is labeled with a string, but only the leaves of the tree contain values. This is so that we can have directories, which contain either leaves (files) or nodes (other directories), and both directories and files will have names.


Associated with this type are invariants, facts about the structure that must always hold for it to be a valid treezipper. As you implement functions on treezippers, you may assume that the invariants hold for any input treezipper and you must maintain the invariants for any output treezipper. The invariants are:

        1. There are no Holes in the first element of the treezipper tuple.

        2. The first element of the treezipper tuple is either a Leaf or a Node.

        3. All elements in the second element of the treezipper tuple are Nodes that                  contain exactly one Hole. This Hole is the left or right child of their root.

You will be implementing part of the TREEZIPPER signature, which describes the operations that can be done on a treezipper. The full signature is reproduced on the next page. A partial implementation of this signature can be found in TreeZipper.sml. You’ll be implementing the remaining three functions: the nav- igation functions.


An explanation of what the functions in TREEZIPPER do can be found at the end of this homework PDF. You’ll need this explanation for later parts of the assignment.

Task 2.1 (5 pts). Implement the parent function with the behavior described above for navigating from child to parent. parent tz should return a treezipper representing with parent of the current node in focus if it has a parent and NONE otherwise. Make sure that you don’t remove or modify any ancestors in the list other than the parent. This function should have O(1) runtime.

Task 2.2 (6 pts). Implement the leftChild and rightChild functions with the behavior described above for navigating from parent to child. leftChild tz should return a treezipper with the left child of the current node in focus, if it has a non-Empty left child, and NONE otherwise. This function should maintain the invariant that if tz has a left child, Option.map parent (leftChild tz))=  SOME  tz and  if  tz is  itself  a  left  child  of  its  parent1,  Option.map  leftChild (parent  tz))  =  SOME  tz.  rightChild  tz  should  return  a  treezipper  with  the right child of the current node in focus, if it has a non-Empty right child, and NONE otherwise. This function should maintain the invariant that if tz has a right child, Option.map  parent  (rightChild  tz))  =  SOME  tz  and  if  tz  is  itself  a  right child  of  its  parent,  Option.map  rightChild  (parent  tz))  =  SOME  tz.  These functions should have O(1) runtime.

2.3 Testing

You can test your zipper code in the same way we’ve been testing functions all semester. Then, to run your code, type

                          smlnj TREEZIPPER.sig TreeZipper.sml

When creating test cases for your functions, you may encounter a warning about the value restriction. Don’t worry about what this means. To make it (and any associated errors) go away, just type annotate your treezipper (i.e., val tz : int treezipper  =  …).

2.4 Style

Warning: You cannot get style points back on this homework. Every style deduction you get from this point forward is permanent.

Additionally, we have a new style rule for this homework:

You will lose style points for using the open keyword at top level.

If you don’t know what this is, don’t worry about it! If you do, avoid using it, as it clutters up the namespace immensely.

1Remember that Option.map  f  (SOME  x) = SOME  (f  x) and Option.map  f  NONE = NONE

3 A Functional Filesystem

With the TreeZipper structure, you now have everything you need to implement apurelyfunctionalfilesystem!Thefilesystemyou’llbeimplementingisdescribed by the FILESYSTEMsignature.


The signature has navigation functions, styled after typical bash commands that perform similar functions, and functions to create and show the contents of files. All files are plain text files, and their contents are represented by strings. Each directory can contain up to two files or directories.

We’ve already implemented the start, createFile, and showFileContents func- tions for you, and defined the datatypes and exceptions at the top of FileSystem.sml. Do not change these!

3.1 Implementation

For this section, you’ll be implementing some of the functions in FileSystem.sml. Make sure to make good use of the functions in the TreeZipper structure. A reference page explaining what all the functions do can be found at the end of this homework assignment.

Tip: It may become tedious to rewrite the name of the TreeZipper structure over and over again. We’ve given you an alias for the TreeZipper structure at the top of the file:                             structure TZ = T reeZ ipper

Task 3.1 (2 pts). Define the mkdir function. A call to mkdir fs name should create a directory in the current directory with the given name, at the leftmost available spot. If the current directory already has two non-empty children, it should raise DirectoryFull.

Task 3.2 (3 pts). Define the rm function. A call to rm fs name should delete the child of the current directory with the given name or raise NoSuchFileOrDirectory if no child of that name exists. This function should only search for the filename within the current directory. It should not look in any subdirectories.

Task 3.3 (4 pts). Define the cd function. A call to cd fs UP should navigate to the parent directory or raise NoSuchDirectory if already at the root. A call to cd fs (DOWN filename) should navigate to the child directory with the name given or raise NoSuchDirectory if no child of that name exists or a child with that name is not a directory. This function should only search for a filename within the current directory. It should not look in any subdirectories.

Task 3.4 (4 pts). Define the ls function. A call to ls fs should return a list of the names of the children of the current working directory of fs. It should list only the working directory’s children – not any of it’s children’s children. The children listed by ls should be listed in order from left to right.

Task  3.5 (5 pts). Define the pwd function. A call to pwd fs should return a   list of the “path” to the current working directory. This is a list of names of all directories in the filesystem along the path from the root to the current directory. The first element of the list should be the root node and the last should be the current directory.

3.2 Testing the Filesystem

For fun and for ease of testing, we’ve given you an interactive shell in which you can type in commands to perform the filesystem operations you defined above.

To run it, type

             smlnj -m sources.cm

to load your code. Then, in the REPL type


This will bring up a little prompt in the shape of a capital lambda. In there, you can type commands to test your filesystem. Here is a list of all the commands you can use and an example of how to use them:

pwd: prints the current working directory.

                   / pwd


mkdir <name>: creates a directory with the name given

                   / mkdir 15150

ls: prints the contents of the current directory

                   / ls


cd <filename>: navigates down to a child directory

                   / cd 15150

cd  ..: navigates up to the parent directory

                   / cd ..

rm <filename>: removes a child directory

                   / rm 15150

To quit the interactive system, type Ctrl-c.


4 Text Editor

One thing this interactive file system is missing is the ability to edit files. The FileSystem structure has the ability to create, show, and delete files, but we haven’t given you commands to do that in the interactive shell. Instead, you’ll be implementing a very simple text editor for editing files.

A text editor, at it’s simplest, is a piece of software that allows you to place a cursor into a string, and modify the string by inserting and deleting characters at the location of the cursor. The cursor can be moved to different parts of the string to create new edits.

Because a text editor may deal with very large files, it is important that it can perform its insert, delete, and cursor movement functions in constant time.

4.1 Implementation

TheTEXTEDITORsignaturedescribesalloftheserequiredoperationsforatext editor.


A potential implementation of this TEXTEDITOR signature is given in the file NaiveTextEditor.sml. Take a look before continuing to read.

The problem with this implementation is that it takes O(n) time to insert, delete, and move. We can do better. We can create a datatype that does all these things in constant time. Your task will be to come up with this datatype and implement a faster version of the same signature, with behavior described below

moveRight: Moves the cursor one place to the right in O(1) time. If it is already at the right, it should not move.

                               moveRight (Hel|lo) ==> SOME (Hell|o)

                               moveRight (Hello|) ==> NONE

moveLeft: Moves the cursor one place to the left in O(1) time. If it is already at the left, it should not move.

                               moveLeft (Hel|lo) ==> SOME (He|llo)

                               moveLeft (|Hello) ==> NONE

insert: Places a character to the left of the cursor. This should take O(1) time.

                                insert (H|ello) #”i” ==> Hi|ello

delete: Removes the character to the right of the cursor and returns the new text editor and the character deleted in O(1) time. If there is no character to the right of the cursor, it should return NONE.

                                delete (H|ello) ==> SOME (H|llo, #”e”)

                                delete (Hello|) ==> NONE

fromString: Creates a text editor from the input string with the cursor at the front. This should take O(n) time.

toString: Creates a string from the text in the editor. This should take O(n) time.

toStringWithCursor: Creates a string from the text in the editor, but in- serts the character #”|” where the cursor is. This should take O(n) time.

Task 4.1 (1 pts). In the file TextEditor.sml, create a structure called TextEditor that opaquely ascribes to TEXTEDITOR and define the type t that will allow you to implement the functions of the structure in the specified time bounds. Hint: You will not need a treezipper for this task, but you may want something conceptually similar.

Task 4.2 (12 pts). Implement the functions in the TextEditor structure, with the behavior and runtimes described above. You may find the built-in functions implode : char list -> string and explode  : string  ->  char  list help- ful. They take a char list and turn it into the corresponding string and vice versa. They both have O(n) runtime. Additionally, you may assume that the standard list library functions rev and length have O(n) runtime.

4.2 Testing

To load your code, type smlnj -m sources.cm. Then run the interactive filesys- tem with your text editor by typing

        – structure Interactive = MkSimpleInteractive(TextEditor);

        – Interactive.start();

        / edit <filename>

If you’d like to compare the behavior of your implementation with the provided naive implementation, run the following after running smlnj -m sources.cm

        – structure Interactive = MkSimpleInteractive(NaiveTextEditor);

        – Interactive.start();

        / edit <filename>

Remember that your implementation should differ from the naive implementation only in performance, not behavior.

4.3 Representation Independence

One of the things that makes ML’s module system special is opaque ascription. In ML, types in an opaquely ascribed structure that are not defined in a signature are truly abstract and must be used as such: there are no ways to violate the interface, no typecasts, no secret backdoors into the structure’s internal represen- tation.

Because of this, to prove that two different definitions of the same type in a signature are equivalent, we just have to prove that they behave in the same way with respect to the functions and other values defined in the structure. To do this, we define a relation between the two types, and then show that each function in the structure, when given equivalent inputs, produces equivalent outputs. This type of proof is called a representation independence proof.

For example, consider the following signature for the naturalnumbers:


To prove that NormalNat.nat and SillyNat.nat are actually equivalent under this relation, we’d have to prove that corresponding functions in the two structures that take in inputs that are equivalent according to our relation have the same behavior. More formally, we must prove the following things:

For all values i : int, R(NormalNat.fromInt i, SillyNat.fromInt i)

If R(n, s) then NormalNat.toInt  n = SillyNat.toInt  s

If R(n, s) then R(NormalNat.increment n, SillyNat.increment s)

While this is just a small example, representation independence can be used to prove equivalence of more complex structures – text editors, for example.

Task 4.3 (5 pts). Define a relation R between NaiveTextEditor.t and your TextEditor.t. Hint: You should  not  need  the  toString,  toStringWithCursor,  or fromString functions from either editor for this task.

Task 4.4 (7 pts). List what you must prove in order to prove that the equivalence holds. Your solution should be in the same format as the bulleted list given for nat. You should not write the proof; just write what you would need to prove.

5 A Better Editor

The text editor you implemented in the last section is not a very useful text editor. Sure, you can add and delete characters and move around in the string, but you can’t even perform simple operations like backspace—or very important ones, like copy and paste.

5.1 Functors!

To make the text editor slightly more usable, you’ll be implementing a functor that takes a text editor as an argument and outputs a better editor with more features.Thesefeatureswillbebackspace,textselection,andcopyandpaste.The signatureforthebettereditorisgivenbelow:


The include keyword means that all the type and value declarations in the TEXTEDITOR signature are also part of the ENHANCEDEDITOR signature.

Backspace is the same as delete, but removes the character to the left the cursor rather than to the right.

Text selection works by setting a mark at a particular cursor location, and then moving the cursor to a new location. Everything between the mark and the cursor location is selected. Cutting removes the selected text and puts it in the clipboard, a data structure that keeps track of copied text. Pasting places whatever text was in the clipboard to the left of the cursor.

To implement these operations, we’ll need a new type for our editor. In particular, we’ll need a type that keeps track of three things:

                1. The cursor and text in the editor, as before

                2. How far we’ve gone to the right or left of the mark (so we know how                             much we’ve selected)

                3. The clipboard

The input to the functor will be a structure called TextEditor which ascribes to the TEXTEDITOR signature. Our new text editor type will be


where the TextEditor.t represents the current text in the editor, as before. The new datatype selected tells us whether there is NoMark, whether our cursor is At the mark, or how many characters (n > 0) to the Right or Left of the mark the cursor is.

For  example, if I set a mark when the state of the text editor is Functi|ons,  and then move the cursor to the left four times (Fu|nctions), then the selected value would be would be Left 4 and the text I’ve selected is ncti.

The char list is the string of characters currently in the clipboard. It should start out as [], and doesn’t change when we select text—only when we cut text.

Task 5.1 (1 pts). Define a functor called MkEnhancedEditor in the file MkEnhancedEditor.sml. It should take a structure called TextEditor ascribing to the TEXTEDITOR signature as an argument and return a structure opaquely ascribing to ENHANCEDEDITOR. Copy the definition of the type t into the func- tor.

There are multiple ways to define a functor. This particular functor should create a structure ascribing to ENHANCEDEDITOR when called in the following way:


Task 5.2 (3 pts). Define the toString, toStringWithCursor and fromString functions. The toString and toStringWithCursor functions should return the same strings that the original TextEditor structure would have, regardless of what is marked or in the clipboard. The fromString function should return a TextEditor.t in the same way the original TextEditor structure would  have, and should have NoMark set and nothing in the clipboard.

Task 5.3 (4 pts). Define the insert and delete functions. These should maintain the fact that the user cannot edit and select text at the same time. If there is no mark set, these function should have the same behavior as before. If there is a mark set, insert should return the same text editor it was given and delete should return NONE.

Task 5.4 (4 pts). Define the backspace function. It should have the same behavior as delete, except it should remove and return the character to the left of the cursor instead of to the right. It should return NONE if there is no such character or if there is a mark set.

          backspace (He|llo, NoMark, clipboard) ==> SOME ((H|llo, NoMark,                          clipboard), #”e”)

          backspace (|Hello, NoMark, clipboard) ==> NONE

          backspace  (He|llo,  Left  n,  clipboard) ==>  NONE

Task 5.5 (10 pts). Define the moveLeft and moveRight functions. These should affect the position of the cursor in the same way as before and should also update what text is selected if there is a mark set.

          moveLeft (He|llo, At, clipboard) ==> (H|ello, Left 1,  clipboard)

          moveLeft (He|llo, Right 1, clipboard) ==> (H|ello, At, clipboard)

          moveLeft (He|llo, Left 2, clipboard) ==> (H|ello, Left 3, clipboard)

          moveLeft (He|llo, NoMark, clipboard) ==> (H|ello, NoMark, clipboard)

          moveRight (He|llo, At, clipboard) ==> (Hel|lo, Right 1,  clipboard)                              moveRight (He|llo, Left 1, clipboard) ==>  (Hel|lo,  At,  clipboard)                              moveRight (He|llo, Right 2, clipboard) ==> (Hel|lo, Right 3, clipboard)                      moveRight (He|llo, NoMark, clipboard) ==> (Hel|lo, NoMark, clipboard)

Task 5.6 (2 pts). Define the setMark and removeMark functions. The setMark function should modify selection to be At the current cursor. The removeMark function should modify the selection to be NoMark.

Task 5.7 (7 pts). Define the cut function. It should delete all highlighted text and move it to the clipboard, replacing any text that is currently in the clipboard. It should also remove the mark. If there is NoMark, cut should do nothing. Hint: You may want to take advantage of the fact that delete/backspace return the character they delete.

          cut (He|llo, NoMark, clipboard) ==> (He|llo, NoMark, clipboard)

          cut (He|llo, At, clipboard) ==> (He|llo, NoMark, [])

          cut (He|llo, Left 2, clipboard) ==> (He|o, NoMark, [#”l”, #”l”])

          cut (He|llo, Right 2, clipboard) ==> (|llo, NoMark, [#”H”, #”e”])

Task 5.8 (4 pts). Define the paste function. It should place the text in the clipboard to the left of the cursor. It should not modify the text in the clipboard. If a mark is set, paste should do nothing.

          paste (He|llo, NoMark, [#”h”, #”i”]) ==> (Hehi|llo, NoMark, [#”h”, #”i”])

          paste (He|llo, At, [#”h”, #”i”]) ==> (He|llo, At, [#”h”, #”i”])

          paste (He|llo, NoMark, []) ==> (He|llo, NoMark, [])

5.2 Testing

To load your code, type smlnj -m sources.cm. Then run the interactive filesys- tem with your enhanced text editor by typing

          – structure Interactive = MkInteractive(MkEnhancedEditor(TextEditor));

          – Interactive.start();

          / edit <filename>

As before, you can use NaiveTextEditor instead of TextEditor to test with the provided naive implementation instead.

5.3 I’m a real editor!

If you’d like, we have provided code to run your editor in a more editor-like graphical interface. We recommend only doing this after ensuring your code works with the simple interface.

We have provided a script sml_editor.sh that you must use to launch the graphi- cal interface. It will not work if you launch it with smlnj  -m  sources.cm.

Simply run ./sml_editor.sh, then type the following. Note the use of the editTui command instead of edit.

Note that when the editor says C-<character> for a certain command, this means


          – structure Interactive = MkInteractive(MkEnhancedEditor(TextEditor));

          – Interactive.start();

          / editTui <filename>

Note: There are a few caveats to running the editor in this way.

          1. You will not be able to use the arrow keys at the SML/NJ REPL. This is                       necessary to make the editor read input correctly.

          2. You won’t be able to type ”—” characters due to the way cursor tracking is                   done.

          3. You may notice some intermittent flashing when typing. This is a conse-                     quence of the interface’s design and has nothing to do with your code.

                              This assignment has a total of 100 points.