Homework 12
Due Date: Sunday April 18, 9pm
Purpose To practice some accumulator functions; to finish the course project
Expectations
This is a pair assignment. Remember that working in pairs means that you both work on the problems together, ideally by one person developing the solution, while the other person observes and comments. After a while, you switch roles. Working in pairs does not mean to divvy up the work between the two of you.
As with all assignments, you must upload one .rkt file (for the entire pair/team), in the language specified at the top of the assignment to the Handin Server. Using the wrong language will invalidate your submission and result in a score of 0, so please be careful.
Unless otherwise stated, all data and functions you design must be designed according to the data and function design recipes, resp., following all four steps in each case.
Your code must conform to the guidelines outlined in the style guide on the course website. The style guide will be updated as the semester progresses so please remember to read it before submitting each assignment.
-------------------------------------------------------------------
The main objective of this homework is to finish the project. As before, we provide you with our solution of the project so far, so you can choose to use that as your starting point for Part III. But this is not a requirement. Part III will be graded in isolation, and only the fraction of your submission that pertains to Part III.
Warm-up: Accumulator functions
For the warm-up exercises, do not use list abstractions or any other
"abbreviations" of recursive functions—
Exercise 1 Design a function positions (with a parametric signature) that takes an x, a list lox, and an equality predicate x=? and returns the list of positions in lox where x occurs. As always, we count positions starting from 0.
Use plain recursion for this exercise, i.e. no accumulators.
Exercise 2 Design the same function as above (call it positions.v2), but this time you must use recursion with an accumulator that accumulates the list of positions found so far. The signature and purpose statement remain, and you can reuse the same check-expects, or design/add new ones.
Important: You will find that implementing this functionality using a position accumulator naturally results in the list of positions returned in reverse. Therefore, when you call the accumulator helper function from your main function positions.v2, wrap this call in a call to reverse (built-in to ISL+). Do not call reverse from inside your accumulator helper function (why not?).
Hint: you will find that the accumulator helper function needs two additional arguments: the accumulator, and another one that tracks info for you without which you cannot design the function.
Which of the two functions do you think is more efficient: the original positions, or positions.v2, which involves an additional operation that reverses the order in the output list?
Project: Part III (final)
In this part of the homework we extend our Editor by one advanced user-facing feature: the ability to search for a string in the buffer text, possibly across linebreaks, and possibly with multiple occurrences. Real-life editors don’t do much more than that!
Exercise 3 (easy) In Part II you prepared the search feature, by adding a SEARCH mode to your buffer. If you haven’t done that yet, bind a suitable key to the action of switching into this mode, and document the meaning of this key in your HELP menu. We will assume here this is the "f3" key (keys "f1" and "f2" are used to change the font size).
Also, if not done already: set up the functionality of the SEARCH mode, by having your main drawing and key processing functions call specialized routines for this mode (just like you should have specialized routines for drawing/key processing in all other modes of the buffer). We will define these functions later.
Exercise 4 (moderate) Extend your key processing functions to handle the SEARCH mode. This mode supports a simplified way of inputting the search string. Ignore most control keys here, like cursor keys, most function keys, escape, or any kind of mouse activity (define a list constant containing these keys). The World program should only process the following keys:
printable characters: they are simply added to the search string;
the return key "\r": this key is processed like a printable character, i.e. you add it to the search string, namely as "\n" (not "\r": that is only a key event!). When the search string is rendered (by your draw function), it will be echoed as a newline. The point of this is so we can search for text that is broken across lines;
the backspace key "\b": this has the expected effect of deleting characters from the search string, so we can correct mistakes while entering the string. This function should behave like backspace in EDIT mode; and
the function key "f3" (which takes me from EDIT mode to SEARCH mode): pressing it ends the input of the search string and launches the actual search. This functionality is the objective of Exercise 7 below.
For example, in SEARCH mode, the key sequence "a" "b" "c" "\b" "d" "f3" should launch the search for the string "abd", place the cursor at the appropriate location in the buffer, and return the buffer in EDIT mode.
We need to make one important design decision: where do we store the search string? The World must update it across key strokes. We could extend the buffer data again and add a search string field to it. But this is rather involved, and would require a lot of annoying changes to the rest of the code.
Fortunately, there is a trick: we abuse the list-of-line data designed to hold the buffer text and add the search string as the first element of this list (as if it was the first buffer line). This trick is only used in SEARCH mode, so it will not affect the buffer text. You must set this up when entering SEARCH mode, initializing the SEARCH string to "". Conversely, after the search, you must clean up, by removing the search string from the list of lines in the buffer.
Exercise 5 (harder; read the instructions carefully) Design a function string-search that takes two strings s and t and a position p and finds the position of the first occurrence of s in t, if it occurs; o/w your function should return the length of t plus 1. The search should start at position p, i.e. only matches from p or later are accepted. However, the match position must be reported relative to position 0 in t, not relative to position p.
This is complex, so here are examples, with explanatory comments:
(check-expect (string-search "pattern" "pattern string test" 0) 0) ; an easy search (check-expect (string-search "pattern" "pattern string test" 1) 20) ; not found at pos. >= 1 (check-expect (string-search "pattern" "pattern string test" 30) 20) ; bad start position: 30 (check-expect (string-search "string" "pattern string test" 0) 8) ; found at pos. 8 (check-expect (string-search "string" "pattern string test" 8) 8) ; same answer as previous! (check-expect (string-search "string" "pattern string test" 9) 20) ; not found at pos. >= 9 (check-expect (string-search "" "pattern string test" 0) 0) ; "" always matches (check-expect (string-search "paddern" "pattern string test" 0) 20) ; note "...dd...": not found (Note that the built-in function string-contains? returns a Boolean [whether found]—
this is not enough: we need the position.) Hint: use recursion over a string. But which one of the two? We haven’t done this often—
be creative! Bonus question: if s is not found in t, why can we not just return the length of t, call it lt, instead of lt plus 1 as suggested above? Since valid positions in t range from 0 to lt-1, lt is an out-of-bounce position value that could be used to indicate "not found", right?
No, that would be ambiguous. For 5 bonus points, find an example that demonstrates this.
Exercise 6 (harder) Design the function that carries out the search. Our goal is to search the buffer text for the search string starting from the current cursor position, not from the beginning of the buffer. This allows us to find multiple occurrences of the search string: after finding the first, I can move the cursor 1 character to the right and search again. This would not be possible if the search always started from the beginning of the buffer.
Here is how this works. We return the buffer, except that (i) the cursor position may change (if the search string is not found, the cursor position is not changed), and (ii) the buffer mode is reset to EDIT.
In SEARCH mode, our search string is stored as the first ("fake") line in the list-of-lines of the buffer. Retrieve it—
this will be your first argument of the string-search function. The second argument is the whole buffer text as a single string, i.e. a Text— use the lol->text function from HW10 (Exercise 9). The third argument to string-search is the start position for the search, which is the current cursor position. But wait—
the cursor position is given as line and column numbers; we need the position of the cursor in the flattened string returned by lol->text! Write a helper function that accomplishes the conversion; let’s call it lnum-cnum->pos. It takes a [NEList-of Line] and line and column numbers, and returns a Nat. The idea is that each line contributes "its length" to the flattened position, until you reach the line where the cursor is. Make sure that, in the total position tally, you account for the LINE-SEP characters inserted by lol->text. When string-search returns, inspect the returned position whether it indicates "failure". In that case, the cursor position stays what it is. Otherwise we need to convert this flat cursor position in the Text version of the buffer back into line- and column numbers. For this, you need the inverse of lnum-cnum->pos, call it pos->lnum-cnum. This function takes a Nat (the flat position) and a NEList-of Line, and returns a Posn with the line and column number. Put these into your buffer and return it.
Exercise 7 (easy) Design your SEARCH mode drawing function. In this mode, display simple instructions to the user how to enter the string, which keys are recognized, and how to end the search string input and launch the search. In addition to these instructions, also display a prompt for the user to enter the search string.