Comp 210 Lab 5: Mutual recursion; Emacs basics

Mutual Recursion, Emacs basics

Consider the following data definition, which describes the structure of a medieval kingdom:

<regent> := (general aide)
   where general is a <knight>, and aide is a <serf>.

<knight> := (private salary)
          | (officer fellow squire servant salary)
   where fellow is a <knight>, and squire and servant are <serf>s.
   salary is a number of potatoes.

<serf> := (simpleton potatoes)
        | (idiot)
        | (spy potatoes rebel)
   where potatoes is a number, and rebel is a <regent>.

• Q: How do we see that these are mutually recursive?
  
• A: There is a loop in the dependencies: regents are defined in terms of knights, which are defined in terms of serfs, which are defined in terms of regents.

• Q: Is there any other recursion?
• A: Sure, a kind of knights, officers, are defined in terms of knights.

Write the appropriate uses of define-structure.

• Q: How many uses do we need?
• A: 6. One for regents, two for knights, and three for serfs.

List the functions that these uses of define-structure make.

• Q: How many constructors, predicates, and selectors are there?
• A: 6 constructors, one for each define-structure. 6 predicates, one for each define-structure. 10 selectors, between zero and four for each define-structure.

Create all the program templates for functions of one input on these data types.

• Q: How many templates do we need?
• A: 3. One that takes a regent as input, one for a knight as input, and one for a serf as input.

Write a function that counts the number of potatoes grown in a kingdom. (Simpletons generate potatoes, idiots are too stupid to raise potatoes, spies steal potatoes. Knights and regents are too important to farm themselves.) The function should take a regent as its argument and return a number.

• Q: How many functions should you write in total for this?
• A: 3, one for each relevant data type. To write a function potatoes-of-regent, we need helper functions potatoes-of-knight and potatoes-of-serf.

Create test data for this function.

• Q: How many pieces of test data do we need?
• A1: Assume we test each of the three functions separately. We need at least three different serfs, one of each kind. We need at least two knights, one of each kind. We need at least one regent, of the only kind.
• A2: Assume we test only the main function potatoes-of-regent. We still need to test each of the cases of the helper functions. You could easily use six regents (= 3 * 2 * 1, or all combinations of the previous test cases). You could get away with fewer. Since an officer has two serfs, one regent with a general who is an officer could have two different kinds of serfs, thus testing multiple cases of potatoes-of-serfs at once. What's important to observe is that this requires more test data. It is much easier to test each function separately.

Write a function that checks if a kingdom has any spies working against it. The function should take a regent as its argument and return a boolean.

• Q: Do we need to write templates for this function?
• A: No, each function doesn't require a template, just each input data type, and we've already written templates for these datatypes.

• Q: How many functions should you write in total for this?
• A: 3, like before. To write a function has-spies-regent?, we need helper functions has-spies-knight? and is-spy-serf?.

Create test data for this function.

• Q: How many pieces of test data do we need?
• A: Assume we test each function separately since we know that is easier than testing just the main function. We need at least three different serfs, one of each kind. We need at least two knights, one of each kind. For completeness, we need nine (a private plus eight officers, each combination of his fellow possibly having a spy and his squire and servant possibly being spies). We need at least one regent, of the only kind. For completeness, we need four (each combination of his general possibly having a spy and his aide possibly being a spy). This would test all the cases of any reasonable implementation.

Emacs is a text editor. We'll be using it later in the semester and are easing you into it now. Go back to your home directory, and start emacs by either selecting it from the "editors" menu when you right-click on the root window, or typing emacs from the UNIX prompt.

There are several other text editors available. We recommend Emacs because it is the main standard in the Unix world. Also, it is the most flexible since, for better or worse, it has everything (including the kitchen sink!) in it (e.g., a mail reader, a newsreader, a web browser, games, and a fully programmable command language). Because of this flexibility, it isn't always the easiest editor to use.

Once Emacs is started, select the a built-in tutorial file via the ``Help'' menu. It's one of those things you can dabble at; we'll let you do this on your own time. In the long run, you'll find the control-keys more useful for moving around than the mouse or arrow keys.

Some common movement commands are repeated here. You can try them out immediately on the TUTORIAL file in emacs.

Emacs has the concept of "modes". For instance, when editing a file ending in ".ss", it is in Scheme-mode, and will treat certain command (such as indent) a little differently than if you are in (say) C mode or text mode.

An emacs window is a "view" into a file which you are editing. It can be handy to have different windows so you can deal with several files at once.

1. Split an existing window by typing C-x 2 (or choose Split-Window from the Files menu). You now have two different windows looking at the same file. Type a bit -- you'll see the change happening in both windows.
2. Go to the other window by typing C-x o (or use the menu command).
3. In this bottom window, let's open your homework file. Type C-x C-f if you don't want to select "Open File..." from the command window. The cursor will be on the bottom line, called the minibuffer. Note that you can use editing commands like C-a in the minibuffer. Also, if you type the first part of the file name and press Tab, emacs will complete the filename (as much as it can).
4. You should now see your homework assignment in the lower half of the screen. It is easy to transer text between the bottom and the top using cut-and-paste. You can also kill text in one window (with C-k), move to the ohter window (which is C-x o, or the menu) and yank (C-y) the text back there.

If you want a 2-page summary of these and other emacs commands, you can print out the emacs reference card. There is also a handout about Emacs available in Mudd.