http://racket-lang.org/
append(c(H,T), B, c(H,TB)) <= append(T, B, TB). append(nil, B, B).This code describes relationship of appending lists, but it doesn't specify how to accomplish the appending. Is the first clause an ‘instruction’ to build a list, or to take one apart? Are the clauses to be run in any particular order? Is there a deterministic ‘answer’?
Long ago, Carl Hewitt created the same-fringe problem as a demonstration of the simplest problem that requires concurrency to implement efficiently: Given two binary trees, determine if they have the same leaves in the same order, regardless of their internal structure. A solution that simply flattens both trees into lists and compares them element-by-element is unacceptable, as it requires space to store the intermediate lists and time to compute them even if a difference arises early in the computation.
Your task is to write a function that tests if two trees have the same fringe. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
One of the first functions taught to programmers who are just learning about recursion is the function to compute the fibonacci numbers. The naive function takes exponential time, as each recursive call must compute the values of smaller fibonacci numbers, so programmers are next taught how to remove the recursion by explicitly storing state information, giving a linear-time iterative algorithm. The upshot is that programming students are left with the impression that recursion is bad and iteration is good.
It is actually possible to improve the performance with a logarithmic-time algorithm. Consider the matrices
Each time the matrix is multiplied by itself, the number in the lower left-hand corner is the next fibonacci number; for instance, F4=3 (F0=0 is a special case). Of course, powering can be done using a binary square-and-multiply algorithm, as in the ipow and expm functions of the Standard Prelude, giving a logarithmic algorithm for computing the nth fibonacci number.
Your task is to write the three fibonacci functions — exponential, linear, and logarithmic — described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Back in the 1970s, David Ahl wrote a new game program each month for Creative Computing magazine. Those were the days of all-caps teletypes (if you were rich you could get a new-fangled “glass teletype”) and punched paper tapes (it was fun to play with the confetti they made). MS-BASIC permitted twenty-six single-letter variable names; later they also allowed a single letter followed by a single digit. There were no user-defined functions and no recursion. GOTO was common, resulting in a phenomenon called “spaghetti code.” There was good news, however: it was acceptable programming practice to GOTO the middle of a FOR loop and run the code there, as long as you jumped back out of the loop before the corresponding NEXT — try to do that in your favorite functional language!
One of Ahl’s most memorable games was Hamurabi, in which the player took the role of the administrator of the ancient city of Sumeria, managing the grain and land resources of the city and trying to keep the residents from starvation. It is typical of the genre, with simple numeric input and scrolling text output. Here is a description and sample game, and the original BASIC source code is reproduced on the next page. By my count, there are fourteen lines that are unreachable except by an IF…THEN, GOSUB or GOTO, forty-three lines that redirect control flow away from the line below, and four instances (line 555 to 215, bypassing line 210, 453 and 479 to 440, bypassing 430, 441 to 511, bypassing 510, and 880 and 885 to 565, bypassing 560) of jumping into the middle of a block of code; that’s a fine bowl of spaghetti, considering the entire program is only 120 lines. Variable P represents the current population, S is the number of bushels in stores, and A is the number of acres of farmland owned by the city, but other variables are used inconsistently — for instance D sometimes represents the number of deaths in the current year, but other times it represents the current input value, and other times Q is used to represent the current input value.
Your task is to reimplement HAMURABI.BAS in a more modern computer language. Don’t peek at the solution unless you want to deprive yourself of the sheer joy of working out the spaghetti code and figuring out what the variables really stand for. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
While waiting for the Roadcrafter suit to arrive; I decided to get my old leather coat out of storage. Purchased at the flea market in Orange County, CA sometime in the mid-nineties, I’d somehow managed never to wear it. While some may lament the 90’s shoulder-pad styling, it is hard not to like the southwestern influenced design.
Thus far it has been pretty comfortable, the leather seems sturdy, and you know… I don’t mind the smitten looks that I receive while wearing it one bit ;).

My Concours has a little rust-spot on the gas tank. The bike was recently serviced and they didn’t see any rust inside of the gas tank, so you know, I’ve got warm-fuzzies about that but I still need to do something about the rust. Here are some progressively more detailed photos of the bike and the rust-spot (click to zoom):
Talking to four different friends and co-workers, their advice is split two ways:
What would you do and why would you do that?