CSCI 2041 Assignment 2: List Manager
- Due: 11:59pm Tue 10/2/2018
- Approximately 3.0-4.0% of total grade
- Submit to Canvas
- Projects are individual work: no collaboration with other students is allowed. Seek help from course staff if you get stuck for too long.
CODE DISTRIBUTION: a2-code.zip
TESTING CODE: a2-tests.zip (Instructions)
CHANGELOG:
- Fri Sep 28 14:49:58 CDT 2018
- Post 199 identified a bug with the
heros.txt
file which was not properly sorted (“Bumi” appeared before “Bolin”). This affects several tests on Problem 4. Download a fresh copy ofa2-tests.zip
or replace these two files individually: - Thu Sep 27 15:16:11 CDT 2018
- Post 180 reiterated the an issue on Mac OSX with the
process-mltest.awk
script which is part of the tests. A new version of this script which fixes the bugs is now part ofa2-tests.zip
or can be downloaded directly here: process-mltest.awkSome bugs were identified intest_listmanager_data.sh
which have been resolved. The current codepack is updated. You can get the updated file here: test_listmanager_data.sh. - Thu Sep 27 12:23:11 CDT 2018
- Automated tests have been added to the assignment. Download code at the top of the spec and follow the associated instructions.
- Wed Sep 26 10:32:16 CDT 2018
- Minor typo fixes reported on Piazza: Post 158, Post 163.
- Tue Sep 25 10:16:12 CDT 2018
- A correction was made to the examples syntax for when guards in the implementation notes for insert/remove. Originally this example misused the
x
variable as both a list and element. - Mon Sep 24 15:30:02 CDT 2018
- Minor typos corrected such as the duplicate
Sortedlist.insert
comments identified in Post 138. - Mon Sep 24 08:53:03 CDT 2018
- The original codepack did not contain the
util.ml
file which is part of the code provided. The codepack has been updated. You can also download the file directly here: util.ml
1 Rationale
OCaml provides immutable data such as singly linked lists as well as mutable references. This combination can prove extremely useful in implementing programs that require history tracking to enable operations to undone and redone. This project will involve implementing pure list operations to insert and remove elements which create new lists with the modifications made. These lists will be tracked using mutable refs to allow previous states to be restored.
OCaml also provides a suite of modern programming conveniences for handling file I/O and command line argument parsing. The code for these is mostly provided and can serve as a template to copy for future programs that require such tools.
2 Overview
The goal of the assignment is to produce listmanager
, a program which manages a list of unique items (strings). The architecture of the program is broken into several modules each corresponding to a single source file. Each source file contains some functions that are serve the ultimate ends of the application. Some of the code is provided such as for file I/O and to set up an interactive loop. However, the back-end functions to implement list manipulation are all need to be created. Examine the program structure below and how it relates to the assignment Problem ordering: it will be important to go in order for this assignment.
2.1 Assignment Files and Download
Download the code pack linked at the top of the page. Unzip this which will create a project folder. Create new files in this folder. Ultimately you will re-zip this folder to submit it.
NOTE: Tests Released Later: The tests for this assignment will not be released with the publication of the specification. They will be released sometime after once they have been completed. Further instructions on how to use them will be made available on release.
File | State | Prob# | Notes |
---|---|---|---|
Makefile |
Provided | All | Build file to compile all programs |
mltest.ml |
Provided | All | Testing utilities/main routine |
process-mltest.awk |
Provided | All | Awk script to add debug info to test files |
sortedlist.ml |
Create | 1/2 | Pure operations on sorted lists |
test_sortedlist1.ml |
Provided | 1 | Unit Tests for Problem 1 |
test_sortedlist2.ml |
Provided | 2 | Unit Tests for Problem 2 |
undolist.ml |
Create | 3 | Imperative operations on a list that track undo history |
test_undolist.ml |
Provided | 3 | Unit Tests for Problem 4 |
listmanager.ml |
Modify | 4 | Main program loop, modify to fill in missing code |
util.ml |
Provided | 4 | Utility functions for file I/O. |
test_listmanager.sh |
Provided | 4 | Application Tests for Problem 4 |
test_listmanager_data.sh |
Provided | 4 | Data for application tests |
Automated Testing Instructions
Unzip a2-tests.zip
to create the directory a2-tests/
. Copy all files in the a2-tests
directory to the project directory a2-code
. The following unix command should do this if a2-tests
and a2-code are in the same directory.
cp -r a2-tests/* a2-code/
The Makefile provided is a copy of Makefile.withtests. The original version is called Makefile.notests.
The new Makefile introduces the targets
make test-p1
: test problem 1make test-p2
: test problem 2make test-p3
: test problem 3make test-p4
: test problem 4make test
: test all problems
Test programs test_sortedlist1
, test_sortedlist2
, and test_undolist
associated with problems 1-3 can run individual tests by passing a test number as a command line argument as in
./test_sortedlist2 3 # run the 3rd tests only
Test program testlistmanager.sh associated with problem 4 also has this feature
./test_listmanager.sh 10 # run only the 10th test
2.2 General Grading Criteria GRADING
Weight | Criteria |
---|---|
5 | CORRECT SUBMISSION and STYLE |
All files submitted and properly zipped | |
make test compiles all code and runs tests |
|
Code is indented reasonably well to indicate scopes | |
Comments provide insight for intricate blocks |
2.3 Demo Session
listmanager
is demonstrated below. Study this demo session to gain an understanding of the direction of the program.
> make # build the program ocamlc -g -annot -c util.ml ocamlc -g -annot -c sortedlist.ml ocamlc -g -annot -c undolist.ml ocamlc -g -annot -c listmanager.ml ocamlc -g -annot -o listmanager str.cma unix.cma util.cmo sortedlist.cmo undolist.cmo listmanager.cmo > ./listmanager # start listmanager LM> help # ask for help LIST MANAGER Maintains a sorted list without duplicates No spaces allowed list data, use _ instead as in Lin_Beifong Commands: help : print this help message quit : quit the program show : print the current list to the screen clear : set the list to empty, preserves undo history add <elem> : add elem to the list remove <elem> : remove elem from list save <file> : save the current list to named file (not undoable) load <file> : discard the current list, load sorted list in named file (undoable) mergein <file> : load the sorted list in the named file and merge with current list (undoable) undo : undo the last operation restoring list to a previous state redo : redo the last undone operation restoring list to a previous state LM> show # show the current list --BEG LIST-- # it's empty --END LIST-- LM> add Korra # add some elements LM> add Mako LM> add Bolin LM> show # show it now --BEG LIST-- Bolin # all three present Korra Mako --END LIST-- LM> add Korra # adding existing elements LM> show # does not create duplicates --BEG LIST-- Bolin Korra Mako --END LIST-- LM> add Tenzin # add some more elements LM> add Asami LM> show # show current list --BEG LIST-- Asami Bolin Korra Mako Tenzin --END LIST-- LM> save heros.txt # save to a text file LM> clear # empty the list LM> show --BEG LIST-- --END LIST-- LM> add Amon # add some new elements LM> add Tonraq LM> add Kuvira LM> add Zaheer LM> show --BEG LIST-- Amon Kuvira Tonraq Zaheer --END LIST-- LM> save villains.txt # save into a different text file LM> load heros.txt # load from a file LM> show # overwrites existing list --BEG LIST-- Asami Bolin Korra Mako Tenzin --END LIST-- LM> mergein villains.txt # merge current list with contents of file LM> show # sorted order maintainted --BEG LIST-- Amon Asami Bolin Korra Kuvira Mako Tenzin Tonraq Zaheer --END LIST-- LM> remove Kuvira # removing elements LM> remove Tonraq LM> remove Zaheer LM> show --BEG LIST-- Amon Asami Bolin Korra Mako Tenzin --END LIST-- LM> remove Zaheer # removing more elements LM> show --BEG LIST-- Amon Asami Bolin Korra Mako Tenzin --END LIST-- LM> clear # empty the list LM> show --BEG LIST-- --END LIST-- LM> undo # undo the clear to restore it LM> show --BEG LIST-- Amon Asami Bolin Korra Mako Tenzin --END LIST-- LM> add Kuvira # perform to more alterations LM> remove Amon LM> show --BEG LIST-- Asami Bolin Korra Kuvira Mako Tenzin --END LIST-- LM> undo # undo the last operation: remove Amon LM> show --BEG LIST-- Amon Asami Bolin Korra Kuvira Mako Tenzin --END LIST-- LM> undo # undo the last operation: add Kuvira LM> show --BEG LIST-- Amon Asami Bolin Korra Mako Tenzin --END LIST-- LM> redo # redo add Kuvira LM> redo # redo remove Amon LM> show # list restored --BEG LIST-- Asami Bolin Korra Kuvira Mako Tenzin --END LIST-- LM> quit List managed! > # back to the unix prompt
3 Problem 1: Sorted Insert / Remove
The crux of listmanager
is to perform manipulations on lists of unique elements. These are implemented in sortedlist.ml
and are pure functions: the produce new lists with an element added, removed, or two lists merged together. The only imperative function is for printing. The problem implements basic adding and removing while the next deals with merging and printing.
3.1 sortedlist.ml
Top-Level Definitions
Create a source file sortedlist.ml
which will have the following bindings in it.
(* sortedlist.ml : Provides operations for sorted lists of any type. *) let rec insert list elem = ... ;; (* val insert : 'a list -> 'a -> 'a list PROBLEM 1: Insert elem into list which is sorted. The insertion preserves the sorted order of the list. No duplicates are allowed in the list: if elem is equal to an element of list, the resulting list is identical to the original list. Uses pattern matching, not tail recursive. Runs in linear time on length of list. REPL EXAMPLES # insert [1;3;5;7] 8;; - : int list = [1; 3; 5; 7; 8] # insert [1;3;5;7] 2;; - : int list = [1; 2; 3; 5; 7] # insert [1;3;5;7] 5;; - : int list = [1; 3; 5; 7] # insert ["b";"d";"f"] "a";; - : string list = ["a"; "b"; "d"; "f"] # insert ["b";"d";"f"] "g";; - : string list = ["b"; "d"; "f"; "g"] # insert ["b";"d";"f"] "b";; - : string list = ["b"; "d"; "f"] # insert [] "g";; - : string list = ["g"] *) let rec remove list elem = ... ;; (* val remove : 'a list -> 'a -> 'a list PROBLEM 1: Create a new list with elem removed from the parameter list. If elem is not present in list, the result is identical to the original list. Uses pattern matching, not tail recursive. Runs in linear time on length of list. REPL EXAMPLES # remove [1;3;5;7] 1;; - : int list = [3; 5; 7] # remove [1;3;5;7] 5;; - : int list = [1; 3; 7] # remove [1;3;5;7] 6;; - : int list = [1; 3; 5; 7] # remove ["b";"d";"f"] "b";; - : string list = ["d"; "f"] # remove ["b";"d";"f"] "z";; - : string list = ["b"; "d"; "f"] *) let rec print strlist = ... ;; (* val print_strlist : string list -> unit PROBLEM 1: Print all elements of a string list to standard output. Makes use of standard printing functions such as print_endline or printf to print. Uses pattern matching. This function IS tail recursive. Runs in linear time on length of list. REPL EXAMPLES # print ["apple";"orange";"banana"];; apple orange banana - : unit = () # print ["grape";"pear"];; grape pear - : unit = () *) let rec merge lista listb = ... ;; (* val merge : 'a list -> 'a list -> 'a list PROBLEM 2: Merge two sorted lists: lista and listb. Elemetns that appear in both lists appear only once in the result. Operates in linear time on the length of lists: does not do repeated insertion. Not tail recursive. May use pattern matching OR if/else clauses. Runs in linear time on combined length of lists. REPL EXAMPLES # merge [] [2;4;6];; - : int list = [2; 4; 6] # merge [1;3;5] [2;4;6];; - : int list = [1; 2; 3; 4; 5; 6] # merge [1;3;5] [];; - : int list = [1; 3; 5] # merge [1;3;5] [2;3;4;6;8];; - : int list = [1; 2; 3; 4; 5; 6; 8] # merge ["a";"c";"e"] ["b";"d"];; - : string list = ["a"; "b"; "c"; "d"; "e"] # merge ["a";"c";"e"] ["b";"c";"d";"e"];; - : string list = ["a"; "b"; "c"; "d"; "e"] *)
3.2 Implementing insert
and remove
While implement insert
and remove
keep the following in mind.
- For full credit, make use of pattern matching in your solution via the
match/with
construct. You may use someif/else
clauses as well within pattern matched cases. - A nice alternative to
if/else
is thewhen
guard in pattern matching which will be covered in lecture eventually briefly the syntax islet x = ... in match list with | [] -> result for empty list | a :: b when a=x -> some result | a :: b when a<x -> some other result | a :: b -> result when above don't apply
This allows application of a pattern matching case only when a condition is true.
- The function should be recursive as indicated by the signature
let rec
. However, the DO NOT need to be tail-recursive. - Ensure that no duplicate elements are created in lists: inserting an element that is already present returns a list equal to the original list (though it may be a somewhat different list)
- Exploit the fact that the list is sorted to gain some small efficiencies: on reaching an element larger than the element to be inserted or removed, there is no need to recurse further into the list.
3.3 Implementing print
- This is a simple function that prints the elements of any string list to the standard output which is usually the screen
- Each element of the list is printed on its own line
- Make use of
printf
for printing to show you understand its use - Pattern matching should be employed to destructure the list
- Ensure that the function is tail recursive by making the last action in the recursive case a function call.
3.4 Grading Criteria for insert/remove/print
in sortedlist.ml
GRADING
The following criteria will be checked in this problem.
Weight | Criteria |
---|---|
AUTOMATED TESTS | |
15 | make test-p1 correctly compiles and passes tests |
MANUAL INSPECTION for insert/remove in sortedlist.ml |
|
5 | insert |
Recursion is used effectively to traverse the list | |
Pure, side-effects free implementation: no use of refs/loops | |
Use of pattern matching to destructure the list | |
Avoids use of List.length in favor of pattern matching to detect cases |
|
Avoid use List.hd and List.tl in favor of pattern matching |
|
Further division of cases using either if/else or when guards |
|
Exploits sorted nature of list to recurse only as deeply as needed | |
5 | remove |
Recursion is used effectively to traverse the list | |
Pure, side-effects free implementation: no use of refs/loops | |
Use of pattern matching to destructure the list | |
Avoids use of List.length in favor of pattern matching to detect cases |
|
Avoid use List.hd and List.tl in favor of pattern matching |
|
Further division of cases using either if/else or when guards |
|
Exploits sorted nature of list to recurse only as deeply as needed | |
5 | print |
Makes use of pattern matching to destructure list | |
Makes use of printf to print to standard output |
|
Function is tail recursive |
4 Problem 2: Merging Sorted Lists
The other function in sortedlist.ml
involves merging two sorted lists to produce a combined sorted list. Refer to the earlier file structure of sortedlist.ml
to see documentation associated with its prototype. Implementation details are given below.
4.1 Implementing merge
- This is a classic exercise to merge two sorted lists in linear time on the length of the lists. It comes up when implementing algorithms such as Merge Sortthough usually that setting involves merging arrays rather than linked lists
- The central approach breaks the problem into some general cases based on the two inputs
lista
andlistb
- One list empty: the remainder of the merged list is the other non-empty list
- Both lists contain same element: the merged list has one copy of the element and the remainder is found by recursing on the tails of both lists
- lista has an element smaller than listb: the merged list has the head of
lista
followed by the result of recursing on the tail oflista
and all oflistb
- listb has an element smaller than lista: converse of the previous: one element from
listb
and recurse on tail oflistb
and all oflista
- The above process allows for progress through both lists simultaneously which results in a linear time complexity on the combined lengths of the lists.
- Since the case have to do with elements from both inputs, using pattern matching is a bit more intricate. For that reason, it is not required or this problem. Pure use of
if/else
will receive full credit. - If interested, one can pattern match on pair of values using syntax like the following.
match x,y with | [],(yh::yt) -> x empty, y has head and tail | (xh::xt),(yh::yt) when xh=yh -> both nonempty, heads equal ...
This technique will be covered in some detail in lecture at a future date.
4.2 Grading Criteria for merge
in sortedlist.ml
GRADING
The following criteria will be checked in this problem.
Weight | Criteria |
---|---|
AUTOMATED TESTS | |
5 | make test-p2 correctly compiles and passes tests |
MANUAL INSPECTION for merge in sumfuncs.ml |
|
10 | merge |
Recursion is used effectively to traverse both input lists | |
Pure, side-effects free implementation: no use of refs/loops | |
Cases are clearly delineated via if/else or match/with/when |
|
Avoids use of List.length |
|
Linear runtime complexity on the combined length of the input lists |
5 Problem 3: The Undo List
The listmanager
implements list operations that can be undone and redone. Our implementation will accomplish this by simply tracking all lists that have been created in the past in a list: undo history is a list of string lists. Similarly, every time an undo
command is issued, the current list is moved to a redo
list so that that state can be restored.
undolist.ml
provides a ref to a single “global” list called curr_list
. Add, remove, and merge operations in this file “wrap” those in sortedlist.ml
to perform imperative updates on the curr_list
and the undo/redo history. None of these are long functions but some are a bit tricky to get the state mutation correct.
5.1 undolist.ml
Top-Level Definitions
Create a source file undolist.ml
which will have the following bindings in it.
(* undolist.ml : This module manages a sorted list strings. add, remove, and merge operations are provided. undo/redo operations are provided to alter list. Type annotaions are required on the module-level values as refs to 'a list are not allowed due to weak typing. All functions in this file pertain to PROBLEM 3 *) let curr_list : string list ref = ... ;; (* The current list of strings. *) let undo_stack : string list list ref = ... ;; (* List of previous curr_lists to enable undo. *) let redo_stack : string list list ref = ... ;; (* List of undone curr_lists to enable redo. *) let reset_all () = ... ;; (* Reset curr_list, undo_stack, redo_stack to all be empty lists. Used only in testing, not in main programs. *) let set_to_list new_list = ... ;; (* curr_list is moved to the top of the undo_Stack. Then curr_list is set to the new_list. Empties redo_stack. *) let add_elem elem = ... ;; (* Add the given elem to curr_list producing a new_list. Calls set_to_list on result to unable undoing. *) let remove_elem elem = ... ;; (* Remove the given elem from curr_list producing a new list. Calls set_to_list on result to unable undoing. *) let merge_with_list list = ... ;; (* Merge the param list with the current list. Calls set_to_list on the result to enable undoing. *) let undo () = ... ;; (* If the undo_stack is not empty, undo the last operation. curr_list is moved to the redo_stack and the top element of undo_stack is removed and becomes curr_list. Returns true if changes are made and false if undo_stack is empty and no changes are made. Operates in constant time. *) let redo () = ... ;; (* If the redo_stack is not empty, redo the last operation. curr_list is moved to the undo_stack and the top element of redo_stack is removed and becomes curr_list. Returns true if changes are made and false if redo_stack is empty and no changes are made. Operates in constant time. *)
5.2 Conceptual vs. Fine-Grained View of Undo List Values
The standard lists provided OCaml are immutable. This means that most lists can be conceptualized as separate and distinct from one another. In reality, pure functions such as those implemented in sortedlists.ml
may create “new” lists with a combination of fresh and existing Cons boxes. Below is figure showing both the “conceptual” view of how curr_list, undo_stack, redo_stack
are related as well as a fine-grained view of their actual relations. The interlinking between lists could be intricate. This sharing saves memory but is not a concern to the program due to the lists being persistent: they cannot be changed moving forward.
5.3 Undo and Redo Semantics
Most programmers are acquainted with undo/redo in standard programs: discrete actions that are taken are can be undone to go back to a previous state. If undone, they can be redone to restore the “future” state. In simple implementations like ours, undoing actions then performing a new action “clobbers” the redo history so that those states are lost.
To implement this in listmanager
, actions progressively push new lists into the undo_stack
list of lists (Below Figure (A)). Calling undo
will pop an element from the top of this stack and set curr_list
to point to it while the state in curr_list
is moved to the redo_stack
(Figure (B)-(C)). Calling redo
will pop an element from redo_stack
off moving it the curr_list
which is moved to the undo_stack
(Figure (D)). Any new action taken will empty the redo_stack
so that lists there are lost (Figure (E)).
Study this diagram carefully to ensure that your implementation of undolist.ml
functions matches these semantics.
5.4 Implementing Undolist
Functions
- The file contains “global” refs
curr_list
to the current string list andundo_stack/redo_stack
which are lists of previous values ofcurr_list
. Functions will directly manipulate these refs to keep track of the history associated withcurr_list
. - The function
set_to_list new_list
is the work horse of the module. It moves thecurr_list
to theundo_stack
and setscurr_list
to the specifiednew_list
. Use the settolist in the other mutator functions such asadd_elem
andremove_elem
. - Remember that when working with OCaml refs, the following apply
- Assign using the
:=
operator as inaref := new_value;
- Access the value refs with
!aref
- Assign using the
- You will use a variety of functions from the
sortedlist.ml
such asinsert
here. Refer to these functions using the module reference syntax:Sortedlist.insert
orSortedlist.remove
etc. Examples are below.let new_list = Sortedlist.insert some_list new_elem in ... let smaller = Sortedlist.remove alist gone in ... listref := Sortedlist.merge xlist !listref; ...
- Do not use
open Sortedlist
in this module: practice addressing functions in another file using the module syntax above. - The
undo/redo
functions should manipulate the refs to accomplish semantics described the previous section. Note that these functions never throw exceptions. If it is not possible to undo or redo, nothing is done. Both functions return a boolean:true
when they make changes,false
otherwise due to an associated function being empty.
5.5 Grading Criteria for undolist.ml
GRADING
The following criteria will be checked in this problem.
Weight | Criteria |
---|---|
AUTOMATED TESTS for undolist.ml |
|
10 | make test-p3 correctly compiles and passes tests |
MANUAL INSPECTION for undolist.ml |
|
5 | set_to_list |
Proper use of ref syntax like := and ! | |
Simple code which manipulates curr_list, undo_stack, redo_stack |
|
5 | add_elem / remove_elem / merge_with_list |
Use of set_to_list to manipulate module fields like curr_list |
|
Use of functions from module Sortedlist via module address syntax |
|
No use of the open Sortedlist |
|
5 | undo / redo |
Proper manipulation of refs to accomplish undo/redo | |
Clear checking so that exceptions do not occur due to empty history | |
Clear return of true on successful operation and false otherwise |
6 Problem 4: Main Program listmanager
This problem addresses putting the previous functionality together into a working listmanager
program with an interactive loop. Various functionalities are already provided for this in the code distribution. What remains is the complete the main execute_command
function in listmanager.ml
.
6.1 Provided Code in util.ml
This file does not require modification. It provides two I/O routines to read and write lists in files. These are needed for associated listmanager
commands.
(* util.ml: utilities for splitting and file opeartions. All functions in this file are already implemented. *) let strlist_from_file filename = ... ;; (* Load a list of strings from a text file. Not particularly efficient as it is not tail recursive but gets the job done. *) let strlist_to_file strlist filename = ... ;; (* Write a list of strings to file filename. Tail recursive so reasonably efficient. *)
6.2 Modify listmanager.ml
This file has a variety of code in it already. It has the following features.
execute_command
needs to be defined. This function is called every time a user types a command. It calls functions from modulesSortedlist, Undolist
andUtil
to execute affect the program state. It is described in some detail later.- The two values
help_string
andquit_now
are used inexecute_command
and are thus defined above it. These definitions are provided. - Code is provided below
execute_command
to set up an interactive loop that reads user input. This code does not require modification but may provide interesting reading for folks that wonder about command line argument processing, exception handling, and other features in OCaml. This is not required now but will be covered by the end of the course
Below are the top-level bindings in the file.
(* listmanager.ml : main function to allow manipulation of a sorted list of unique elements. Makes use of functions provided in Sortedlist, Undolist, and Util. *) let debug = ... ;; (* debug printing on/off *) let help_string = ... ;; (* Help string to be printed for the "help" command. *) let quit_now = ... ;; (* When false, prompts for another command and continues interactive loop. When true, ends interactive loop and quits program. *) let execute_command tokens = ... ;; (* PROBLEM 4: Execute a single command for the listmanager program. Argument tokens is an array of strings at least 1 element long. The 0th element is the command to execute like "add" or "clear". Depending on the command, there may be subsequent arguments. Makes use of functions provided in Sortedlist, Undolist, and Util a well as values in this module like help_string and quit_now. *) let echo = ... ;; (* Code beyond this point should not require modification though it may be interesting to examine. *) let prompt = ... ;; let options = ... ;; (* Options accepted by the program *) let handle_extra_args arg = ... ;; (* Do nothing with extra command line arguments *) let usage = ... ;; (* Simple usage message for Arg.parse *) let _ = ... ;; (* main routine *)
6.3 Implementing execute_command
A good place to start in understanding how execute_command
works is to examine the help string associated with the program which is provided below.
Commands: help : print this help message quit : quit the program show : print the current list to the screen clear : set the list to empty, preserves undo history add <elem> : add elem to the list remove <elem> : remove elem from list save <file> : save the current list to named file (not undoable) load <file> : discard the current list, load sorted list in named file (undoable) mergein <file> : load the sorted list in the named file and merge with current list (undoable) undo : undo the last operation restoring list to a previous state redo : redo the last undone operation restoring list to a previous state
When execute_command tokens
is run, the argument tokens
array will have a string like help
or remove
as the 0th element. This is the command to execute. If the command requires another argument like a <file>
, it will be the 1th element in the array. This situation is set up by other code later in listmanager.ml
.
A good way to structure this function is pattern matching on the command being issued. Full credit solutions will do this
Below are notes on how to address each of the commands mentioned. Many of these mix functions from other modules like Undolist.add_elem
andSortedlist.print
. Refer to these functions using their full module address; do not add any open
statements.
help
Print the value of help_string
with a newline at the end.
quit
Set the quit_now
reference to true
which will cause the interactive loop to end.
show
Make use of Sortedlist.print
to print the value of Undolist.curr_list
.
clear
Make use of Undolist.set_to_list
to empty the list but retain undo history.
add elem / remove elem
Make use of functionality in Undolist
to modify the current list accordingly.
save <file>
Make use of functionality in util.ml
to save the list to the named file. Note that saving cannot be undone so does not affect the undo history.
load <file>
Make use of functionality in util.ml
to load a list from the named file. Replace the current list with this. Make use of Undolist.set_to_list
to ensure that this can be undone and redone.
Note: redoing a load does not re-read the file from disk so if it changes on disk, those changes will not be seen in the redo of a load. This means the standard functions for undo/redo can be used.
mergein <file>
Make use of functionality in util.ml
to load a list from the named file. Then merge this into the existing list using functionality in Sortedlist
. Replace the current list with this.
undo / redo
Make use of functions in Undolist
to affect the undo/redo history. Capture the return value of these and print a warning message if no changes were made as follows.
LM> undo WARNING: undo list empty, no changes made LM> redo WARNING: redo list empty, no changes made
Any Other Command
Use a catch-all and print a message indicating the command is not recognized as below.
LM> ls Unknown command 'ls' LM> make Unknown command 'make' LM> kerplow! Unknown command 'kerplow!'
6.4 Grading Criteria for execute_command
GRADING
The following criteria will be checked in this problem.
Weight | Criteria |
---|---|
AUTOMATED TESTS | |
15 | make test-p4 correctly compiles and passes tests |
MANUAL INSPECTION for listmanager.ml |
|
10 | execute_command |
Use of pattern matching to determine the command to execute | |
Clear division into cases to handle for each command | |
No use of open except for Printf |
|
Correct use of module address for functions like Undolist.add_elem |
|
Proper use of functions from provided Util module for file I/O |
|
Proper leveraging of functions from other implemented modules like Sortedlist and Undolist |
6.5 listmanger
Usage
listmanager
is set up to accept two options: -debug
and -echo
. Both of these require no implementation for this problem but are described below for completeness.
listmanager -debug
will set the ref Listmanager.debug
to true. This prints some additional info in the interactive loop. It can also be used for debug messages in execute_command
by doing something like the following.
if !debug then (* check if debugging is on *) begin printf "curr_list has %d elements\n" (List.length !Undolist.curr_list); printf "undo_stack has %d elements\n" (List.length !Undolist.undo_stack); printf "redo_stack has %d elements\n" (List.length !Undolist.redo_stack); end;
listmanager -echo
turns on command echoing: everything that is received as input is printed back on the screen. This allows for scripted behavior like the following which is used during testing to make output look more readable.
> cat input.txt # contents of file input.txt, commands for listmanager add D add R add B add S add F remove S show undo show quit > cat input.txt | listmanager -echo # pipe into listmanager echoing commands LM> add D LM> add R LM> add B LM> add S LM> add F LM> remove S LM> show --BEG LIST-- B D F R --END LIST-- LM> undo LM> show --BEG LIST-- B D F R S --END LIST-- LM> quit List managed! >
7 Zip and Submit
7.1 Zipping Files
If creating a zip file is unfamiliar to you, refer to the following guide: Making Zips (tutorial)
7.2 Submit to Canvas
Once your are confident your code is working, you are ready to submit. Ensure your folder has all of the required files. Create a zip archive of your lab folder and submit it to Canvas.
On Canvas:
- Click on the Assignments section
- Click on the appropriate link for this lab/assignment
- Scroll down to “Attach a File”
- Click “Browse My Computer”
- Select you Zip file and press OK
7.3 Late Policies
You may wish to review the policy on late project submission which will cost you late tokens to submit late or credit if you run out of tokens. No projects will be accepted more than 48 hours after the deadline.
http://www-users.cs.umn.edu/~kauffman/2041/syllabus.html#late-projects