Computer Science Logo Style vol 2 ch 11: Example: Cryptographer's Helper (2024)

BrianHarvey University of California, Berkeley Download PDF version Back to Table of Contents BACKchapter thread NEXT MITPress web page for Computer Science Logo Style

Program file for this chapter: crypto

A cryptogram is a kind of word puzzle, like a crossword puzzle.Instead of definitions, though, a cryptogram gives you the actualwords of a quotation, but with each letter replaced with a differentletter. For example, each letter A in the original text might bereplaced with an F. Here is a sample cryptogram:

LB RA, BT YBL LB RA: LJGL CQ LJA FUAQLCBY: KJALJAT 'LCQ YBRXAT CYLJA DCYP LB QUSSAT LJA QXCYWQ GYP GTTBKQ BS BULTGWABUQ SBTLUYA, BTLB LGHA GTDQ GWGCYQL G QAG BS LTBURXAQ, GYP RM BIIBQCYW AYP LJAD?

The punctuation marks and the spaces between words are thesame in this cryptogram as they are in the original ("clear") text.

A cryptogram is a kind of secret code. The formal name for this particularkind of code is a simple substitution cipher. Strictly speaking,a code is a method of disguising a message that uses a dictionaryof arbitrarily chosen replacements for each possible word. A foreignlanguage is like a code. A cipher is a method in which a uniformalgorithm or formula is used to translate each word. A substitutioncipher is one in which every letter (or sometimes every pair of letters,or some such grouping) is replaced by a disguised equivalent. A simple substitution cipher is one in which each letter has a singleequivalent replacement, which is used throughout the message. (Amore complicated substitution cipher might be something like this:the first letter A in the message is replaced with F, the second Ais replaced with G, the third with H, and so on.)

Years ago, Arthur Conan Doyle and Edgar Allen Poe were able to writemystery stories in which simple substitution ciphers were used bycharacters who really wanted to keep a message secret. Today, partlybecause of those stories, too many people know how to "break" suchciphers for them to be of practical use. Instead, these ciphers areused as word puzzles.

The technique used for decoding a cryptogram depends on the fact thatsome letters are more common than others. The letter A is much morecommon in English words than the letter Z. If, in a cryptogram, theletter F occurs many times, it's more likely to represent a letterlike A in the original text than a letter like Z.

The most commonly used letter in English is E, by a wide margin. T is in second place, with A and O nearly tied for third. I, N, andR are also very commonly used. These rankings apply to largetexts. In the usual short cryptogram, the most frequent letter doesn'tnecessarily represent E. But the letter that represents E will probablybe among the two or three most frequent.

Before reading further, you might want to try to solve the cryptogramshown above. Make a chart of the number of times each letter appears,then use that information to make guesses about which letter is which.As you're working on it, make a note of what other kinds of informationare helpful to you.

This project is a program to help you solve cryptograms. The programdoesn't solve the puzzle all by itself; it doesn't know enough aboutEnglish vocabulary. But it does some of the more boring parts ofthe job automatically, and can make good guesses about some of theletters.

The top-level procedure is crypto . It takes one input, a listwhose members are the words of the cryptogram. Since these lists are longand easy to make mistakes in, you'll probably find it easier to type thecryptogram into the Logo editor rather than directly at a question markprompt. You might make the list be the value of a variable, then use thatvariable as the input to crypto. (The program file for thisproject includes four such variables, named cgram1 through cgram4, with sample cryptograms.)

Crypto begins by going through the coded text, letter by letter. It keeps count of how often each letter is used. You can keep trackof this counting process because the program draws a histogramon the screen as it goes. A histogram is a chart like the oneat the top of the next page.

 L B LAB LAB LAB LAB LAB L QAB L Q YAB G L Q T YAB G L Q T YAB G L Q T YABC G L Q T YABC G J L Q T YABC G J L Q TU YABC G J L QRSTU YABC G J L PQRSTU W YABCD G J L PQRSTU WXYABCD G IJKL PQRSTU WXYABCD FGHIJKLM PQRSTU WXY

Histogram

A-17-E B-18-  C-08- D-03- EF-01- G-11-A H-01- I-02- J-07-HK-02- L-19-T M-01- N OP-04- Q-13- R-05- S-05- T-11-U-06- V W-04- X-03- Y-12-Z ABCDEFGHIJKLMNOPQRSTUVWXYZLB RA, BT YBL LB RA: LJGT CQ LJAT E, T T E: THAT THEFUAQLCBY: KJALJAT 'LCQ YBRXAT CY LJA E T : HETHE 'T E THEDCYP LB QUSSAT LJA QXCYWQ GYP GTTBKQ T E THE A ABS BULTGWABUQ SBTLUYA, BT LB LGHA T A E T E, T TA EGTDQ GWGCYQL G QAG BS LTBURXAQ, GYPA A A T A EA T E , ARM BIIBQCYW AYP LJAD? E THE ?

Screen display

A histogram is a kind of graph, but it's different fromthe continuous graphs you use in algebra. Histograms are usedto show quantities of discrete things, like letters of the alphabet.

The main reason the program draws the histogram is that it needs toknow the frequencies of occurrence of the letters for later use. When I first wrote the program, it counted the letters without printinganything on the screen. Since this counting is a fairly slow process,it got boring waiting for the program to finish. The histogram displayis a sort of video thumb-twiddling to keep you occupied while theprogram is creating an invisible histogram inside itself.

By the way, since there are only 24 lines on the screen, the top partof the histogram may be invisible if the cryptogram is long enoughto use some letters more than 24 times.

The shape of this histogram is pretty typical. A few letters areused many times, while most letters are clumped down near the bottom.In this case, A, B, and L stand out. You might guess that they representthe most commonly used letters: E, T, and either A or O. But youneed more information to be able to guess which is which.

After it finishes counting letters, the program presents a screendisplay like the one shown above.The information provided in this display comes in threeparts. At the top is an alphabetical list of the letters in the cryptogram.For each letter, the program displays the number of times that letteroccurs in the enciphered text. For example, the letter P occurs fourtimes. The letter that occurs most frequently is highlighted byshowing it in reverse video characters, represented here withunderlined characters. Inthis example, the most frequently used letter is L, with 19 occurrences.Letters with occurrence counts within two of the maximum are alsohighlighted. In the example, A with 17 and B with 18 are highlighted.If a letter does not occur in the cryptogram at all, no count is given.In the example, there is no E in the enciphered text.

The top part of the display shows one more piece of information: ifeither the program or the person using it has made a guess as to theletter that a letter represents, that guess is shown after the frequencycount. For example, here the program has guessed that the letterL in the cryptogram represents the letter T in the clear text.(You can't tell from the display that this guess was made by the programrather than by the person using it. I just happen to know that that'swhat happened in this example!)

The next section of the display is a single line showing all the lettersof the alphabet. In this line, a letter is highlighted if a guesshas been made linking some letter in the cryptogram with that letterin the clear text. In other words, this line shows the linkages inthe reverse direction from what is shown in the top section of thedisplay. For example, I just mentioned that L in the cryptogram correspondsto T in the clear text. In the top part of the display, we can findL in alphabetical order, and see that it has a T linked to it. Butin the middle part of the display, we find T, not L, in alphabeticalorder, and discover that something is linked to it. (It turnsout that we don't usually have to know which letter corresponds toT.)

Here is the purpose of that middle section of the display: SupposeI am looking at the second word of the cryptogram, RA. We've alreadyguessed that A represents E, so this word represents something-E.Suppose I guess that this word is actually HE. This just happensto be the first two-letter word I think of that ends in E. So I'dlike to try letting R represent H. Now I look in the middle sectionof the display, and I see that H is already highlighted. So someother letter, not R, already represents H. I have to try a differentguess.

The most important part of the display is the bottom section. Here,lines of cryptogram alternate with their translation into clear text,based on the guesses we've made so far. The cryptogram lines arehighlighted, just to make it easy to tell which lines are which. The program ensures that each word entirely fits on a single line;there is no wrapping to a new line within a single word.

There is room on the screen for eight pairs of lines. If the cryptogramis too big to fit in this space, only a portion of it will be visibleat any time. In a few paragraphs I'll talk about moving to anothersection of the text.

The program itself is very limited in its ability to guess letters.For the most part, you have to do the guessing yourself when you useit. There are three guessing rules in the program:

1. The most frequently occurring single-letter word is taken to representA.
2. Another single-letter word, if there is one, is taken to representI.
3. The most frequently occurring three-letter word is taken to representTHE, but only if its last letter is one of the ones highlighted inthe top part of the display.

In the example, the only single-letter word in the cryptogramis G, in the next-to-last line. The program, following rule 1, hasguessed that G represents A. Rule 2 did not apply, because thereis no second single-letter word. The most frequently used three-letterword is LJA, which occurs three times. The last letter of that word,A, is highlighted in the top section because it occurs 17 times. Therefore, the program guesses that L represents T, J represents H,and A represents E.

Of course you understand that these rules are not infallible; they'rejust guesses. (A fancy name for a rule that works most of the timeis a heuristic. A rule that works all the time is called analgorithm.) For example, the three-letter word GYP appearstwice in the cryptogram, only once less often than LJA. Maybe GYPis really THE. However, the appearance of the word THAT in the translationof the first line is a pretty persuasive confirmation that the program'srules have worked out correctly in this case.

If you didn't solve the cryptogram on your own, at my first invitation,you might want to take another look at it, based on the partial solutionyou now have available. Are these four letters (A, E, I, and T) enoughto let you guess the rest? It's a quotation you'll probably recognize.

Once this display is on the screen, you can make further guesses bytyping to the program. For example, suppose you decide that the lastword of the cryptogram, LJAD, represents THEM. Then you want to guessthat D represents M. To do that, type the letters D and M in thatorder. Don't use the RETURN key. Your typing will not be echoedon the screen. Instead, three things will happen. First, the entryin the top section of the display that originally said

D-03-

will be changed to say

D-03-M

Second, the letter M will be highlighted in the alphabetin the second section of the display. Finally, the program will typean M underneath every D in the cryptogram text.

If you change your mind about a guess, you can just enter a new guessabout the same cryptogram letter. For example, if you decide thatLJAD is really THEY instead of THEM, you could just type D and Y.Alternatively, if you decide a guess was wrong but you don't havea new guess, type the cryptogram letter (D in this example) and thenthe space bar.

If you guess that D represents M, and then later you guess that R alsorepresents M, the program will complain at you by beeping or by flashingthe screen, depending on what your computer can do. If you meantthat R should represent M instead of D representing M, you mustfirst undo the latter guess by typing D, space bar, R, and M.

The process of redisplaying the clear text translation of the cryptogramafter each guess takes a fairly long time, since the program has tolook up each letter individually. Therefore, the program is writtenso that you don't have to wait for this redisplay to finish beforeguessing another letter representation. As soon as you type any keyon the keyboard, the program stops retyping the clear text. Whateverkey you typed is taken as the first letter of a two-letter guess command.

If the cryptogram is too long to fit on the screen, there are threeother things you can type to change which part of the text isvisible. Typing a plus sign (+) eliminates the first four lines ofthe displayed text (that is, four lines of cryptogram and four correspondinglines of cleartext) and brings in four new lines at the end. Typinga minus sign (-) moves backwards, eliminating the four lines nearestthe bottom of the screen and bringing back four earlier lines at thetop. These windowing commands have no effect if you are alreadyseeing the end of the text (for +) or the beginning of the text (for-).

The third command provided for long cryptograms is the atsign(@) character. This is most useful after you've figured out all ofthe letter correspondences. It clears the screen and displays onlythe clear text, without the letter frequencies, table of correspondences,or the enciphered text. This display allows 23 lines of clear textto fit on the screen instead of only eight. If you don't have thesolution exactly right, you can type any character to return to thethree-part display and continue guessing.

The program never stops; even after you have made guessesfor all the letters, you might find an error and change your mindabout a guess. When you're done, you stop the program with control-Cor command-period or whatever your computer requires.

In the complete listing at the end of this chapter, there are a fewcryptograms for you to practice with. They are excerpted from oneof my favorite books, Compulsory Miseducation byPaul Goodman.

Program Structure

There are about 50 procedures in this program. These procedures can beroughly divided into several purposes:

• initialization
• frequency counting and displaying the histogram
• guessing letters automatically
• reading user commands
• keeping track of guesses
• top section of display (frequencies)
• middle section of display (alphabet)
• bottom section of display (cryptogram text and cleartext)
• windowing and full-text displays
• data abstraction and other helper procedures

The diagram on the next page shows superprocedure/subprocedure relationships withinthe main categories. (Helper procedures aren't shown, to make thediagram more readable.) The bottom half of the diagram has theprocedures that are concerned primarily with presenting informationon the screen. Redisplay, near the center of the diagram, iscalled whenever the entire screen display must be redrawn: when theinitialization part of the program is finished, and whenever the userchooses a new portion of the text to display. When the displaychanges slightly, because a new guess is made, procedures such asfixtop, light, and dark are used instead of redrawingeverything.

Bind is the most important procedure, because it records and displayseach new guess. As the diagram shows, it invokes several subprocedures toupdate the display; more importantly, it changes the values of severalvariables to keep track of the new guess. There is also a similar procedureqbind that's used when a guess is made by the program rather than bythe user. (The "Q" stands for either "quick" or "quiet," since thisversion never has to undo an old guess, omits some error checking, and can'tbeep because there are no errors in automatic guesses.) If you ignoreinitialization and displaying information, the entire structure of theprogram is that crypto calls parseloop, which repeatedly callsparsekey, which calls bind to record a guess.

Unfortunately, it's not so easy in practice to divide up theprocedures into groups, with a single purpose for each group. Severalprocedures carry out two tasks at once. For example, light anddark have those names because they switch individual lettersbetween normal and inverse video in the alphabet display in the middlepart of the screen. But those procedures also set variables to rememberthat a particular cleartext letter has or hasn't been guessed, so theyare also carrying out part of bind's job, keeping track of guesses.

Guided Tour of Global Variables

Crypto uses many global variables to hold the information it needs.This includes information about individual letters, aboutwords, and about the text as a whole.

There are several sets of 26 variables, one for each letter of thealphabet. For these variables, the last letter of the variable nameis the letter about which the variable holds information. In thetable that follows, the italic x in each name representsany letter.

These variables are set up initially by initvars, exceptfor the posn variables, which are set by showrow. Thevariables with single-letter names start out with a space character as theirvalue. This choice allows showclear to use thing :letteras the thing to type for every letter in the cryptogram.If no guess has been made for a letter, it will be displayed as ablank space in the partially-decoded version of the text.

Here are the variables that have to do with words in the cryptogramtext. These variables are needed for the part of the program thatautomatically makes guesses, by looking for words that might representA, I, and THE in the cleartext. In the following variable names,y represents either a one-letter word or a three-letter wordin the cryptogram text.

These variables are used only duringthe initial histogram counting, to keep track of which one-letterword and which three-letter word are the most frequent in each category.Once the most frequently occurring words have been determined, theactual count is no longer important.

Finally, there are some variables that contain information aboutthe text as a whole:

:Maxcount is used to know which letters should be highlightedin the top section of the display. :Text is used by showcode andshowclear to maintain the bottom section of the display. Fulltext, moretext, and textstack are part of the windowingfeature. At first, text is equal to fulltext, and textstack is empty. Moretext contains the portion of the textstarting on the fifth line that is displayed, providing there is some textat the end of the cryptogram that didn't fit on the screen. If the end ofthe text is visible, then moretext is empty. Here is what happens ifyou type the plus sign:

to moretextif emptyp :moretext [beep stop]push "textstack :textmake "text :moretextredisplay "trueend

If :moretext is empty, there is no more text to display,and the procedure stops with a complaint. Otherwise, we wantto remember what is now in :text in case of a later - command, andwe want to change the value of text to the version starting four lineslater that is already in :moretext.

In the solitaire project, I used a lot of local instructions in thetop-level procedures to avoid creating global variables. In this project,I didn't bother. There's no good reason why I was lazier here than there;you can decide for yourself whether you think it's worth the effort.

What's In a Name?

In revising this program for the second edition, I was struck by the waysin which bad choices of procedure or variable names had made it needlesslyhard to read. Changing names was one of the three main ways in which Ichanged the program. (The other two were an increased use of dataabstraction and the introduction of iteration tools to eliminate somehelper procedures.)

I'll start with a simple example. As I've mentioned, when I first wrotethe program it didn't draw the histogram on the screen during the initialcounting of letter frequencies. Since the top part of the screen displayis primarily a presentation of those frequencies, I thought of that toppart as the program's "histogram" even though it doesn't have the formof a real histogram. That's why, in the first edition, the proceduresthat maintain the top part of the display were called showhist,fixhist, and so on; when I added the histogram and histletprocedures that draw the real histogram, it was hard to keep track ofwhich "hist" names were part of the initial histogram and whichwere part of the letter frequency chart at the top of the program's normalscreen display. I've now changed showhist to showtop,fixhist to fixtop, and so on. The procedures with histin their names are about the real histogram, and the ones with topin their names are about the frequency chart.

Here's another example. In several parts of the program, I had todetermine whether a character found in the cryptogram text is a letteror a punctuation mark. The most straightforward way to do this wouldbe an explicit check against all the letters in the alphabet:

to letterp :charoutput memberp :char "ABCDEFGHIJKLMNOPQRSTUVWXYZend

But comparing the character against each of the 26 letterswould be quite slow. Instead, I took advantage of the fact that therehappen to be variables in the program named after each letter. That is,there's a variable A, a variable B, and so on, but therearen't variables named after punctuation characters. Therefore, I could usethe Logo primitive namep to see whether or not the character I'mconsidering is a variable name, and if so, it must be a letter. Thefirst edition version of crypto is full of instructionsof the form

if namep :char ...

This is clever and efficient, but not at all self-documenting.Someone reading the program would have no way to tell that I'm usingnamep to find out whether a character is a letter. The solutionwas to add an instruction to the initialization in crypto:

copydef "letterp "namep

The copydef primitive is used to give a new name toan existing procedure. (The old name continues to work.) The existingprocedure can be either primitive or user-defined. The new name is notsaved by the save command; that's why crypto performs thecopydef instruction each time.

Probably the worst example of bad naming was in the tally procedure.This procedure has a complicated job; it must keep track of the mostcommon one-letter and three-letter words, in preparation for the program'sattempts to make automatic guesses for A, I, and THE. Here is the versionin the first edition:

to tally :type :wordlocal "thismake "this word :type :wordif not memberp :word list. :type ~ [setlist. :type fput :word list. :type make :this 0]make :this sum 1 thing :thismake "this thing :thisif :this > (count. :type) ~ [setcount. :type :this make (word "max. :type) :word]end

The input named type is either the word single orthe word triple. One thing that makes this procedure hard to readis the local variable named this. What a vague name! This what?Is it this word, or this letter, or this word length, or this guess? Tomake things worse, partway through the procedure I recycled the samename to hold a different value. At first, :this is a word thatwill be used as the name of a variable, counting the number of timesa given word appears. For example, if the word YBL appears in thecryptogram, then tally will create a variable named tripleyblwhose value will be the number of times that YBL occurs in the text.The value of this will be the word tripleybl, so theexpression thing :this represents the actual number. Then,near the end of the procedure, I used the instruction

make "this thing :this

From then on, :this is the number itself, not thevariable name! It's really hard to read a procedure in which thesame name is used to mean different things in different instructions.

Here's the new version:

to tally :type :wordlocalmake "countvar word :type :wordif not memberp :word list. :type ~ [setlist. :type fput :word list. :type make :countvar 0]localmake "count (thing :countvar)+1make :countvar :countif :count > (count. :type) ~ [setcount. :type :count setmax. :type :word]end

The name this is gone. Instead, I've first createda local variable named countvar whose value is the name of thecount variable. Then I create another local variable named countthat contains the actual count. These names are much more descriptiveof the purposes of the two variables.

Another change in the new version is a more consistent use ofdata abstraction. The original version used the constructorsetlist. and the selector list. to refer to thelist of all known cryptogram words of the appropriate length (thevariable list.single or list.triple), butused the instruction

make (word "max. :type) :word

to construct the variable containing the most frequentlyappearing word of that length. The new version uses a constructornamed setmax. that's analogous to the setlist. constructor.

Rethinking the names of procedures can reorganize your ideas about howto group the procedures into categories. For example, in the firstedition I was upset about the fact that historgram, whose jobis to count letter frequencies and draw the histogram of those counts,also invokes prepare.guess, whose job is to count word frequenciesin preparation for automatic guessing.

The reason for this mixture of tasks is efficiency. To preparethe histogram, the program must extract the letters (omitting punctuation)from each word of the text, and count them. To prepare for guessingwords, the program must extract the letters from each word, and countthe occurrences of the letters-only words. I could have done thesethings separately:

to histogram :textforeach :text [foreach (filter "letterp ?) "histlet]endto count.words :textforeach :text [prepare.guess (filter "letterp ?)]end

But it seemed better to scan the words of the text justonce, and extract the letters from each word just once:

to histogram :textforeach :text [localmake "word filter "letterp ? foreach :word "histlet prepare.guess :word]end

But the punch line of this story is that I could avoid theconfusing jump between boxes--the feeling of mixing two tasks--merelyby changing the name of the histogram procedure to somethingneutral like preprocess. Then the structure would be

Now we have one initialization procedure that includes invocationsfor two separate kinds of preprocessing. It's notreally the program structure that is inappropriate, but only using thename histogram for a procedure whose job includes more than thecreation of the histogram.

Flag Variables

Procedure redisplay has the job of redrawing the entire screen whenthere is a major change to what should be shown, like moving to a differentwindow in the cryptogram text.

to redisplay :flagcleartextshowtopalphabetshowcode :textif :flag [showclear :text]end

The input to redisplay is a flag variable. It musthave the value true or false. (The name comes from the flags onmailboxes, which are either up or down to indicate whether or not there ismail in the box.) It's there because redisplayhas two slightly differentjobs to do at two different points in the program. First, redisplayis invoked by crypto, the top-level procedure, to draw the screeninitially. At this time, no letters have been guessed yet. Therefore, itis not necessary to invoke showclear (which indicatesthe guessed letters in the bottom part of the display).Crypto executes the instruction

redisplay "false

to avoid that unnecessary work. Redisplay is also invokedby moretext, lesstext, and showclear. Each of theseprocedures uses the instruction

redisplay "true

to include showcode. If the flag variableweren't used, there would have to be two different versionsof redisplay.

I used the latter technique in the procedures bind and qbind. These could also have been one procedure with a flag variableinput. The advantage of the technique used in redisplay is that itmakes the program easier to read by reducing the number of procedures, andkeeping similar purposes together. The advantage of using two procedures isthat it's a little faster, because you don't have to test the flag variablewith if.

A flag variable is somewhat analogous to a predicate, aprocedure that always outputs true or false. Theadvantage of using these particular values for flag variables is thatthey're easy to test; you can say

if :flag [do.something]

whereas, if you used some other pair of values like yes andno, you'd have to say

if equalp :flag "yes [do.something]

Some people like to give flag variables names ending with p,as in the convention for predicates. (The special variable redefpthat controls redefinition of primitives in some versions of Logo,including Berkeley Logo, is anexample.) I'm somewhat uncomfortable with that practice because to me itraises a confusion about whether a particular word is the name of a variableor the name of a procedure. I'd rather put flag in the names of flagvariables.

The 26 boundx variables in this program are also flagvariables; each is true if the corresponding letter has beenguessed as the cleartext half of a binding. They don't have "flag"in their names, but their names aren't used directly in most of theprogram anyway. Instead they are hidden behind data abstraction procedures.Setbound and setunbound are used to set any such variabletrue or false, respectively; the selector boundp alertsyou by the P in its name that it's a predicate.

Iteration Over Letters

One of the ways in which I simplified the program for this edition wasto replace some recursive helper procedures with invocations of foreach. At several points in the program, some action must be takenfor each letter in a word, or for each word in the text.

Another kind of iteration problem that was not so easily solved bythe standard higher order procedures in Berkeley Logo was one in whichsome action must be taken, not for each letter in a word, but foreach letter in the alphabet, or for some subset of the alphabet, asin the case of showrow, which displays one row of the top partof the screen, with information about five consecutive letters.Of course these problems could be solved with instructions like

foreach "ABCDEFGHIJKLMNOPQRSTUVWXYZ [...]

but that seemed unaesthetic to me. I wanted to be able tospecify the starting and ending letters, as in this example:

to alphabetsetcursor [6 6]forletters "A "Z [ifelse boundp ? [invtype ?] [type ?]]end

(The job of alphabet is to generate the middlepart of the screen display, which is all of the letters of thealphabet, in order, with each letter in inverse video if thatletter has been guessed as part of the cleartext.)

The difficulty in implementing forletters is to get from oneletter to the next. How does a program know that the letter afterA is B? Here is my solution:

to forletters :from :to :actionfor [lettercode [ascii :from] [ascii :to]] ~ [apply :action (list char :lettercode)]end

The operation asciitakes a letter (or other character)as input. Its output is the number that represents that letter inthe computer's memory. Most computers use the same numbers to representcharacters; this standard representation is called ASCII, forAmerican Standard Code for Information Interchange. (It'spronounced "ask E.") By using ascii to translate the startingand ending letters into numeric codes, I've transformed the probleminto one that can be solved using the standard for tool thatallows an action to be carried out for each number in a given range.

But in the template input to forletters, I want the question markto represent a letter, not its numeric code.Char is the inverse operation to ascii. Givena number that is partof the ASCII sequence, char outputs the character that that numberrepresents. For example:

?print ascii "A65?print char 65A

Forletters applies the template input to the charactercorresponding to the number in the lettercode variable controlled bythe for.

Adding 1 to an ASCII code to get the code for the next letter dependson the fact that the numbers representing the letters are in sequence.Fortunately, this is true of ASCII. A is 65, B is 66, C is 67, andso on. Not all computer representations for characters have thisproperty. The code that was used in the days of punched cards hadthe slash (/) character in between R and S!

By the way, the lower case letters have different ASCII codes from thecapitals. In this program I've used the primitive operationuppercase to translate every character that the program readsinto upper case, just to be sure that each letter has only onerepresentation.

Computed Variable Names

Another programming technique that is heavily used in this projectis the use of word to compute variable names dynamically. Ordinarily,you assign a value to a variable named var with an instruction like

make "var 87

and you look at the value of the variable with the expression

:var

But in this project, there are variables for each letter,with names like posna, posnb, posnc,and so on. To assign a value tothese variables, the program doesn't use 26 separate instructionslike

make "posna [0 0]

(Each of these variables contains a list of screen coordinates foruse with setcursor to find the corresponding letter in the top part ofthe display.) Instead, the procedure showrow, which draws thatsection of the display, contains the instruction

forletters :from :to [setposn ? cursor onetop ?]

Setposn is a data abstraction procedure:

to setposn :letter :thingmake (word "posn :letter) :thingend

When the variable letter contains the letter a,the make instructionhas the same effect as if it were

make "posna :thing

Similarly, the dots notation (:posna) isn't used to examine the valuesof these variables. Instead, thing is invoked explicitly:

to posn :letteroutput thing (word "posn :letter)end

Another point to consider is that I could have used a different approachaltogether, instead of using word to piece together a variable name.For instance, I could have used property lists:

to setposn :letter :thingpprop "posn :letter :thingendto posn :letteroutput gprop "posn :letterend

As it happens, I first wrote this project in Atari 800 Logo, whichdidn't have property list primitives. So the question didn't arise forme. In a version of Logo that does support property lists, I see nostylistic reason to prefer one approach over the other. It'sentirely a question of which is more efficient. Which is faster, searchingthrough a list of 26 times 2 members (times 2 because each property has aname and a value) or concatenating strings with word to generate thename of a variable that can then be examined quickly? I'd have toexperiment to find out. Alternatively, instead of using posn as thename of a property list and the letters as names of properties, I couldreverse the two roles. That would give me more lists, but shorter lists.

What is a stylistic issue is that using procedures like posnand setposn to isolate the storage mechanism from the rest of theprogram makes the latter easier to read.

Further Explorations

I have three suggestions about how to extend this project. The firstis to put in more rules by which the program can make guesses automatically.For example, a three-letter word that isn't THE might be AND. Sequencesof letters within a word can also be tallied; TH is a common two-lettersequence, for example. A double letter in the cryptogram is morelikely to represent OO than HH.

If you have many rules in the program, there will be situations inwhich two rules lead to contradictory guesses. One solution is justto try the most reliable rule first, and ignore a new guess if itconflicts with an old one. (Qbind applies this strategy by meansof the instruction

if letterp thing :from [stop]

which avoids adding a guess to the data base if the cryptogramletter is already bound to a cleartext letter.)

Another solution would be to let the rules "vote" about guesses.If the program had many rules, it might happen that three rules suggestthat F represents E, while two rules suggest that W represents E.In this case, three rules outvote two rules, and the program wouldguess that F represents E.

The second direction for exploration in this program is to try tomake it more efficient. For example, every time you make a guess,showclear is invoked to redisplay the partially decoded text. Muchof this redisplay is unnecessary, since most of the guesses haven'tchanged. How can you avoid the necessity to examine every letterof the cryptogram text? One possibility would be to keep a list,for every letter in the text, of the screen positions in which thatletter appears. Then when a new guess is made, the program couldjust type the corresponding cleartext letter at exactly those positions.The cost of this technique would be a lot of storage space for thelists of positions, plus a slower version of showcode, which wouldhave to create these position lists.

The third direction for further exploration is to find out about morecomplicated ciphers. For example, suppose you started with a simplesubstitution cipher, but every time the letter A appeared in the cleartextyou shifted the corresponding cryptogram letters by one. That is,if E is initially represented by R, the first time an A appears you'dstart using S to represent E. The second time A appears you'd switchto T representing E. And so on. The effect of this technique wouldbe that a particular cleartext letter is no longer represented bya single cryptogram letter all the way through. Therefore, you can'tjust count the frequencies of the cryptogram letters and assume thatfrequently-used letters represent E and T. How could you possiblydecipher such a message?

Program Listing

to crypto :textmake "text map "uppercase :textmake "fulltext :textmake "moretext []make "textstack []if not procedurep "letterp [copydef "letterp "namep]forletters "A "Z "initvarsmake "maxcount 0initcount "singleinitcount "triplecleartexthistogram :textredisplay "falseif or guess.single guess.triple [showclear :text]parseloopend;; Initializationto initcount :typesetlist. :type []setcount. :type 0endto initvars :lettersetcnt :letter 0make :letter "| |setunbound :letterend;; Histogramto histogram :textforeach :text [localmake "word filter "letterp ? foreach :word "histlet prepare.guess :word]endto histlet :letterlocalmake "cnt 1+cnt :lettersetcursor list (index :letter) (nonneg 24-:cnt)type :lettersetcnt :letter :cntif :maxcount < :cnt [make "maxcount :cnt]end;; Guessing lettersto prepare.guess :wordif equalp count :word 1 [tally "single :word]if equalp count :word 3 [tally "triple :word]endto tally :type :wordlocalmake "countvar word :type :wordif not memberp :word list. :type ~ [setlist. :type fput :word list. :type make :countvar 0]localmake "count (thing :countvar)+1make :countvar :countif :count > (count. :type) ~ [setcount. :type :count setmax. :type :word]endto guess.singleif emptyp (list. "single) [output "false]if emptyp butfirst (list. "single) ~ [qbind first (list. "single) "A output "true]qbind (max. "single) "Aqbind (ifelse equalp first (list. "single) (max. "single) [last (list. "single)] [first (list. "single)]) ~ "Ioutput "trueendto guess.tripleif emptyp (list. "triple) [output "false]if :maxcount < (3+cnt last (max. "triple)) ~ [qbind first (max. "triple) "T qbind first butfirst (max. "triple) "H qbind last (max. "triple) "E output "true]output "falseend;; Keyboard commandsto parseloopforever [parsekey uppercase readchar]endto parsekey :charif :char = "@ [fullclear stop]if :char = "+ [moretext stop]if :char = "- [lesstext stop]if not letterp :char [beep stop]bind :char uppercase readcharend;; Keeping track of guessesto bind :from :toif not equalp :to "| | [if not letterp :to [beep stop] if boundp :to [beep stop]]if letterp thing :from [dark thing :from]make :from :tofixtop :fromif letterp :to [light :to]showclear :textendto qbind :from :toif letterp thing :from [stop]make :from :tofixtop :fromlight :toend;; Maintaining the displayto redisplay :flagcleartextshowtopalphabetshowcode :textif :flag [showclear :text]end;; Top section of display (letter counts and guesses)to showtopsetcursor [0 0]showrow "A "Eshowrow "F "Jshowrow "K "Oshowrow "P "Tshowrow "U "Yshowrow "Z "Zendto showrow :from :toforletters :from :to [setposn ? cursor onetop ?]print []endto onetop :letterlocalmake "count cnt :letterif :count = 0 [type word :letter "| | stop]localmake "text (word :letter "- twocol :count "- thing :letter)ifelse :maxcount < :count+3 [invtype :text] [type :text]type "| |endto twocol :numberif :number > 9 [output :number]output word 0 :numberendto fixtop :lettersetcursor posn :letteronetop :letterend;; Middle section of display (guessed cleartext letters)to alphabetsetcursor [6 6]forletters "A "Z [ifelse boundp ? [invtype ?] [type ?]]endto light :lettersetcursor list 6+(index :letter) 6invtype :lettersetbound :letterendto dark :lettersetcursor list 6+(index :letter) 6type :lettersetunbound :letterend;; Bottom section of display (coded text)to showcode :textmake "moretext []showcode1 8 0 :textendto showcode1 :row :col :textif emptyp :text [make "moretext [] stop]if :row > 22 [stop]if and equalp :row 16 equalp :col 0 [make "moretext :text]if (:col+count first :text) > 37 [showcode1 :row+2 0 :text stop]codeword :row :col first :textshowcode1 :row (:col+1+count first :text) butfirst :textendto codeword :row :col :wordsetcursor list :col :rowinvtype :wordend;; Bottom section of display (cleartext)to showclear :textshowclear1 8 0 :text 2endto showclear1 :row :col :text :deltaif emptyp :text [stop]if :row > 23 [stop]if keyp [stop]if (:col+count first :text) > 37 ~ [showclear1 :row+:delta 0 :text :delta stop]clearword :row :col first :textshowclear1 :row (:col+1+count first :text) butfirst :text :deltaendto clearword :row :col :wordsetcursor list :col :row+1foreach :word [ifelse letterp ? [type thing ?] [type ?]]end;; Windowing commandsto fullclearcleartextshowclear1 0 0 :fulltext 1print []invtype [type any char to redisplay]ignore readcharredisplay "trueendto moretextif emptyp :moretext [beep stop]push "textstack :textmake "text :moretextredisplay "trueendto lesstextif emptyp :textstack [beep stop]make "text pop "textstackredisplay "trueend;; Iteration tool for lettersto forletters :from :to :actionfor [lettercode [ascii :from] [ascii :to]] ~ [apply :action (list char :lettercode)]end;; Data abstraction (constructors and selectors)to setbound :lettermake word "bound :letter "trueendto setunbound :lettermake word "bound :letter "falseendto boundp :letteroutput thing word "bound :letterendto setcnt :letter :thingmake (word "cnt :letter) :thingendto cnt :letteroutput thing (word "cnt :letter)endto setposn :letter :thingmake (word "posn :letter) :thingendto posn :letteroutput thing (word "posn :letter)endto setcount. :word :thingmake (word "count. :word) :thingendto count. :wordoutput thing (word "count. :word)endto setlist. :word :thingmake (word "list. :word) :thingendto list. :wordoutput thing (word "list. :word)endto setmax. :word :thingmake (word "max. :word) :thingendto max. :wordoutput thing (word "max. :word)end;; Miscellaneous helpersto index :letteroutput (ascii :letter)-(ascii "A)endto beeptone 440 15endto invtype :texttype standout :textendto nonneg :numberoutput ifelse :number < 0 [0] [:number]end;; Sample cryptogramsmake "cgram1 [Dzynufqyjulli, jpqhq ok yr hoxpj qnzeujory qceqwj xhrtoyx zw oyjr u trhjptpolq trhln. oynqqn, rzh qceqkkogq eryeqhy tojp whrvlqfk rd qnzeujory uj whqkqyj kofwli fquyk jpuj jpq |xhrty-zwk| nr yrj pugq kzep u trhln. u nqeqyj qnzeujory uofk uj, whqwuhqk drh, u frhq trhjptpolq dzjzhq, tojp u noddqhqyj erffzyoji kwohoj, noddqhqyj reezwujoryk, uyn frhq hqul zjoloji jpuy ujjuoyoyx kjujzk uyn kuluhi.]make "cgram2 [Lvo vfkp lfzj md opaxflimn iz lm gitokflo fnp zlkonblvon f hmalv'z inilifliuo, fnp fl lvo zfyo liyo lm zoo lm il lvfl vo jnmwz wvfl iz noxozzfkh lm xmco wilv lvo mnbminb fxliuilioz fnp xaglako md zmxiolh, zm lvfl viz inilifliuo xfn to kogoufnl. il iz ftzakp lm lvinj lvfl lviz lfzj xfn to fxxmycgizvop th zm yaxv zillinb in f tms dfxinb dkmnl, yfnicagflinb zhytmgz fl lvo pikoxlimn md pizlfnl fpyinizlkflmkz. lviz iz kflvok f wfh lm kobiyonl fnp tkfinwfzv.]make "cgram3 [Pcodl hbdcx qxdrdlh yihcodr, hbd rzbiier gxd lih ziyqdhdlh hi hdgzb gwhbdlhcz echdxgzf, xdgnclp gr g ydglr ia ecudxghcil gln zwehcoghcil. gln c niwuh hbgh yirh ia wr jbi rdxciwref xdgn gln jxchd hbd dlpecrb eglpwgpd dodx edgxldn ch uf hbd xiwhd ia "xwl, rqih, xwl" hi rcegr ygxldx.]make "cgram4 [Jw btn xnsgsyp ejke gfebbcg, dtyjbn fbccsksg, ryu fbccsksg nswcsfpsu pes usgjns, wnssuba, ryu wtptns bw pes qbtyk, pesns zbtcu ls yb knrujyk, yb psgpjyk svfsxp rg r psrfejyk aspebu, ryu yb lcrfilbrnu dtykcsg. jy wrfp, zs rns ksppjyk cbfigpsx gfesutcjyk ryu knrujyk pb pes xbjyp bw pbnptns.]

(back to Table of Contents)

BACKchapter thread NEXT