Planet Scheme

January 23, 2015

Programming Praxis

Fibonacci Conjecture

The sequence of Fibonacci numbers is defined as F0 = 0, F1 = 1, Fn = Fn−2 + Fn−1. It has been conjectured that for any Fibonacci number F, F2 + 41 is composite.

Your task is to either prove the conjecture to be true or find a counter-example that demonstrates it is false (hint: this is not a blog about proving math theorems). 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.


by programmingpraxis at January 23, 2015 09:00 AM

January 20, 2015

Programming Praxis

Largest Forward Difference

In an array of integers, the forward difference between any two elements is the rightmost integer less the leftmost integer. The largest forward difference is the greatest value of all forward differences between elements of the array. If there are no positive forward differences, the largest forward difference is taken to be zero, as if an integer is subtracted from itself.

For instance, in the array [1,5,7,2,9] the largest forward difference is 9 – 1 = 8, and in the array [4, 3, 2, 1] the largest forward difference is 0.

Your task is to write a program that finds the largest forward difference in an array. 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.


by programmingpraxis at January 20, 2015 09:00 AM

January 16, 2015

Programming Praxis

Gödel Numbering

Gödel numbering is a system that assigns a natural number to each symbol and expression in a logical system, invented in 1931 by Kurt Gödel for the proofs of his incompleteness theorems. Consider the logical system where symbols are letters and expressions are words; for instance, the word PRAXIS consists of six symbols P, R, A, X, I, and S. Gödel numbering would assign numbers to the letters, say A=1 … Z=26, then assign each letter as the exponent of the next prime, so PRAXIS would be numbered 216 × 318 × 51 × 724 × 119 × 1319 =

83838469305478699942290773046821079668485703984645720358854000640

The process is reversible; factor the Gödel number and decode the exponents.

Your task is to write functions that encode strings as Gödel numbers and decode Gödel numbers as strings. 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.


by programmingpraxis at January 16, 2015 09:00 AM

January 13, 2015

Programming Praxis

Essay: Building A Security Camera With A Raspberry Pi

We have today our fourth essay: Building a Security Camera with a Raspberry Pi. An essay isn’t an exercise; it doesn’t present a task for you to perform, but instead provides extended discussion and complete source code. Though essays may be based on exercises, the idea is that an essay can delve more deeply into a topic than is possible in the limited space and time of an exercise.

My daughter recently had a thief enter her apartment and steal her laptop computer. Later, when I asked her what she wanted for Christmas, her answer was immediate: a security camera, so in case she is robbed again she will have pictures of the thief to give to the police. But commercial security cameras are expensive, often several hundred dollars, and many are tied to security services with expensive monthly fees, which she wasn’t interested in paying. So I built a security camera using a Raspberry Pi, and wrote this essay describing how I did it.

Please read the essay, and feel free to comment on it below; comments on the essay itself are closed. Let me know if you see any errors. And feel free to link to the essay on the internet if you know of places where it is appropriate.


by programmingpraxis at January 13, 2015 09:00 AM

Ben Simon

The Most Powerful Computer You'll Never Own

Inspired by the movie the Imitation Game, I just had build my own Turing Machine (I know, I should have built one of these! Some day). While folks have built actual physical machines, I took the programmer's way out and made mine strictly virtual.

A Turing Machine is the theortical device Alan Turing devised in his 1936 paper on computability. To this day, Computer Science students are made to do battle with this machine and the theories that stem from it.

While it's been years since I've done any CS homework that involved Turing Machines, I can't recall actually ever implementing one. What a shame.

The web is filled with such simulators including: here, here and here. These were invaluable for refreshing my memory as to how a Turing Machine operates.

Implementing a Turing Machine was oddly satisfying. One has to contend with the fact that a program handed to a Turing Machine may never complete. I dealt with this by allowing the user to execute the machine in terms of blocks of cycles. So you create the machine, run it for 100 cycles, and if you want, run it 100 more.

Here's the code to create a machine. The program is actually Alan Turing's first example:

(define r1 '(((b _) (c 0 >))
             ((c _) (e _ >))
             ((e _) (f 1 >))
             ((f _) (b _ >))))
(define tm1 (make-tm 'b '() '() r1))

The rules specified by r1 are in the format:

 (((current-state current-symbol) (new-state new-symbol new-direction))
  ...)

Invoking make-tm creates the new Turing Machine. You provide as arguments the initial state, initial tape-contents, list of halting states and the transition rules.

Once you've got the machine (tm1, above), you can invoke it with an integer to say how many cycles of the machine should execute (e.g., (tm1 10)).

Scheme truly shined as a host language: I was trivially able to make the machine operate on arbitrary states and tape contents. Also sexpr's were ideal for defining the state transition rules.

All of this may seem fairly unimpressive until you ponder this thought:

However odd it may sound for so simple a machine, the Turing Machine is the most powerful computing model known to computer scientists. In this context, "powerful" refers only to what it is capable of doing, not to how fast or efficiently it does it. It has been proven that a TM is capable of performing any computation that a modern computer can, given enough time. Infact, it is technically MORE powerful than modern computers, since it has no storage limitations.

Here's the complete source code for my simulator.

Update: Programming Praxis tackled the Turing Machine almost 5 years ago. I've updated my code below with their example.

; A Turing Machine Impl

(define (range lower upper)
 (if (>= lower upper) '()
     (cons lower (range (+ 1 lower) upper)))) 

(define (show . words)
 (for-each display words))

(define tape-cell '#(_))
(define tape-padding '#(_ _ _ _ _))

(define (make-tape contents)
 (cons 0 (vector-append (list->vector contents) tape-padding)))

(define (tape-head t)
 (car t)) 
(define (tape-items t)
 (cdr t))
 
(define (tape-read t)
 (vector-ref (tape-items t) (tape-head t)))
 
(define (tape-write t x)
 (vector-set! (tape-items t) (tape-head t) x)
 t)
 
(define (tape-move t direction)
 (let ((index (+ (tape-head t)
                 (case direction
                  ((< L) -1)
                  ((> R) 1)
                  ((- N) 0)
                  (else (error "Unknown tape movement: " direction))))))
  (cond ((= index -1)
         (set-cdr! t (vector-append tape-cell (tape-items t)))
         (set! index 0))
        ((= index (vector-length (tape-items t)))
         (set-cdr! t (vector-append (tape-items t) tape-padding))))
  (set-car! t index)
  t))

(define (display-tape t)
 (for-each (lambda (i)
            (let ((v (vector-ref (tape-items t) i)))
              (cond ((= i (tape-head t))
                     (show "[" v "]"))
                    (else (show v)))
              (show " ")))
           (range 0 (vector-length (tape-items t)))))

(define (tm-find state tape rules)
 (let ((needle (list state (tape-read tape))))
  (let loop ((rules rules))
   (cond ((null? rules) #f)
         ((equal? needle (caar rules)) (cadar rules))
         (else
          (loop (cdr rules))))))) 
            
(define (make-tm initial-state initial-tape halting-states rules)
 (let ((state initial-state)
       (tape (make-tape initial-tape)))
 (lambda (cycles)
  (let loop ((cycle 0))
   (show state ": ")
   (display-tape tape)
   (newline)
   (cond ((= cycle cycles) #t)
         ((member state halting-states) state)
         ((tm-find state tape rules) =>
          (lambda (dest)
           (let* ((new-state (car dest))
                  (new-symbol (cadr dest))
                  (new-direction (caddr dest)))
             (set! state new-state)
             (tape-write tape new-symbol)
             (tape-move tape new-direction)
             (loop (+ 1 cycle)))))
          (else 'no-matching-rules))))))

; Binary Counting - http://aturingmachine.com/examples.php
(define r0 '(((walk  0) (walk  0 >))
             ((walk  1) (walk  1 >))
             ((walk  _) (count _ <))
             ((count 0) (walk  1 >))
             ((count 1) (count 0 <))
             ((count _) (walk  1 >))))
             
(define tm0 (make-tm 'walk '(0) '() r0))

; Turing's First Example 
;  http://en.m.wikipedia.org/wiki/Turing_machine_examples
(define r1 '(((b _) (c 0 >))
             ((c _) (e _ >))
             ((e _) (f 1 >))
             ((f _) (b _ >))))
(define tm1 (make-tm 'b '() '() r1))

; http://programmingpraxis.com/2009/3/27/a-turing-machine-simulator/
(define r2 '(((0 1) (0 1 R))
             ((0 +) (1 1 R))
             ((1 1) (1 1 R))
             ((1 _) (2 _ L))
             ((2 1) (H 1 N))))
(define tm2
 (make-tm 0
         '(1 1 1 + 1 1 1 1)
         '(H)
         r2))

by Ben Simon (noreply@blogger.com) at January 13, 2015 01:24 AM

January 09, 2015

Programming Praxis

One-Time Pad

In a previous exercise Ben Simon showed us how to use a trigraph for secret communication. For illustration, he used a one-time pad based on a simple random number generator, but that is not sufficient for proper cryptographic secrecy. In today’s exercise we build a secure one-time pad.

We need two things. One is a cryptographically-secure source of random bits. Solutions include counting the clicks of a geiger counter or reading the background radiation, but being a software guy rather than a hardware guy I suggest the Blum-Blum-Shub cryptographically-secure random number generator of a previous exercise. The second is a way to convert bits to letters. The method we choose is to take 26 consecutive bits from the Blub-Blub-Shum generator, form them into a number, and take the result mod 26, discarding the four largest numbers from the set in order to make all letters equally likely to be chosen, which is similar to the calculation of a previous exercise. Given those two things, it is easy to generate random letters and build a pad of any desired size.

Your task is to write a program to generate one-time pads. 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.


by programmingpraxis at January 09, 2015 09:00 AM

GNU Guix

GNU Guix ported to ARM and other niceties of the new year

A new port of GNU Guix to ARM using the "hard float" ABI has just landed, thanks to the hard work of Mark H Weaver and John Darrington. This makes it the fourth supported architecture after x86_64, i686, and mips64el. We are looking for ARM hardware donations that would allow us to add this architecture to our continuous integration build farm; your help is welcome!

In other news, there has been work to improve Linux module handling, the addition of session support in the login manager, more tooling in 'guix lint', an nscd configuration interface, many new packages (Xfce, NumPy, SciPy, and Clang, to name a few), and many bug fixes. Getting closer to a new release!

About GNU Guix

GNU Guix is the functional package manager for the GNU system, and a distribution thereof.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. It also offers a declarative approach to operating system configuration management. Guix uses low-level mechanisms from the Nix package manager, except that packages are defined as native Guile modules, using extensions to the Scheme language.

At this stage the distribution can be used on an i686 or x86_64 machine. It is also possible to use Guix on top of an already installed GNU/Linux system, including on mips64el and armhf.

by Ludovic Courtès at January 09, 2015 08:18 AM

January 06, 2015

Programming Praxis

Lucas-Carmichael Numbers

We start the new year with a simple task from number theory. A Lucas-Carmichael number is a positive composite integer n, odd and square-free, such that p + 1 divides n + 1 for all prime factors p of n. For instance, 2015 is a Lucas-Carmichael number because 2015 = 5 × 13 × 31 and 5 + 1 = 6, 13 + 1 = 14, and 31 + 2 = 32 all divide 2015 + 1 = 2016. The restriction that n be square-free prevents the cubes of prime numbers, such as 8 or 27, from being considered as Lucas-Carmichael numbers.

Your task is to write a program to find all the Lucas-Carmichael numbers less than a million. 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.


by programmingpraxis at January 06, 2015 09:00 AM

December 30, 2014

Ben Simon

Forth in Racket, Mind-bending and Beautiful

Jay McCarthy's efficient implementation of Forth in 85 lines of Racket is beautiful. It demonstrates how you can integrate two different programming paradigms in one environment, and it does so with some impressive macro-fu. Consider his goals:

  1. We must be able to define functions in Forth that are callable from Forth, always.
  2. We must be able to give functions stack effect annotations to enable them to be called from Racket.
  3. We must be able to lift Racket functions to Forth so they are oblivious to the stack, like turning + into :+.
  4. We must be able to lower Racket functions to Forth so they can directly affect the stack, like writing :over.
  5. We must be able to enter Forth from Racket arbitrarily, such as to write testing forms like check-forth.

Meeting all those goals is an impressive feat.

As a functional tool, I'm not sure I see much of a use for it (yet). As a novel case study and series of examples, it's fantastic.

by Ben Simon (noreply@blogger.com) at December 30, 2014 06:28 PM

December 23, 2014

Programming Praxis

Ancient Algorithms

[ Today’s exercise is a Christmas stocking stuffed with six little exercises. I wish all my readers a Merry Christmas and a Happy New Year! I’ll be taking a few days with family, so the next exercise will appear on January 6, 2015. ]

We tend to think of algorithms as procedures used by computers, but algorithms actually have a long and distinguished history. Today’s exercise discusses six algorithms that pre-date the Christian era, arranged roughly in chronological order. Despite their antiquity, all these algorithms are still in use today.

Peasant Multiplication: This algorithm has been independently invented by most societies as they progress to numeracy, so it is called the Egyptian method, the Ethiopian method, the Russian method, the Ukranian method, and so on for many different peoples; we simply call it the Peasant method. It is known that the Egyptians used this algorithm during the construction of the pyramids.

The algorithm starts by writing the two numbers to be multiplied at the heads of two columns. Then, on successive rows, the number in the left column is halved, discarding any remainder, and the number in the right column is doubled, until the left column is reduced to one. Then the sum of the numbers in the right column that correspond to odd numbers in the left column is the desired product. The ancients use pairs of pebbles to halve numbers and determine parity; we find it simpler to sum the odds as we go along.

function product(left, right)
    prod := 0
    while left > 0
        if left is odd
            prod := prod + right
        left := halve(left)
        right := double(right)
    return prod

In the United States we torment eight-year-old kids with the times tables, but school children in the rest of the world learn this method, which is simpler and, if you’ve ever taught third-grade math, more likely to be done correctly. Additionally, all computers do arithmetic in binary, and use this algorithm deep in the microcode that is stamped into the silicon chip that runs them, shifting bits to perform the halving and doubling operations. The only improvement is that computers nowadays process multiple bits at the same time, instead of just a single bit, reducing the number of steps in the loop.

Babylonian Square Roots: Mathematical historians know that the Babylonians invented a method of calculating square roots because a clay tablet with the calculations etched into it (ancient “scrap paper”) exists, but the method was first described by Hero of Alexandria in the first century after Christ. Hero (his name is sometimes spelled Heron) invented the jet engine (a hollow metal ball filled with water, heated over a fire to convert the water to steam, which exited by two nozzles on opposite sides of the globe; the rotational motion could be captured by gears or belts), the windmill (he used it to power a variety of machines, including a grain grinder), and the vending machine (you dropped a coin into a slot, which caused a balance beam to rise, opening a valve and filling a small vessel with holy water; when the vessel was full, it tipped to deliver the holy water, the coin was tipped into the safe, the balance beam fell, the valve closed, and the machine reset for the next purchase).

Hero observed that if x is an approximation of the square root of n, a better approximation is given by the average of x and n /x; we say x ′ = (x + n /x) / 2. The initial value of x can be anything on the range 1 ≤ xn, though the process converges more quickly if x is somewhat closer to n. In the version of the function given below, we bound n on the range 1 ≤ n < 4 so we can fix the number of iterations required for double-precision accuracy; an alternative is to iterate until the difference between two successive approximations is less than some desired epsilon.

function sqrt(n)
    if n < 1 return sqrt(n * 4) / 2
    if 4 <= n return sqrt(n / 4) * 2
    x = (n + 1) / 2
    repeat 5 times
        x = (x + n / x) / 2
    return x

The only improvement since the Babylonians is the initialization of x, which nowadays is done by some kind of black magic operating on the internal representation of the number (for integers, it’s generally one less than the number of bits in the binary representation of the number, for floating point it’s generally half the mantissa of the number with the exponent reduced by one), usually reducing the number of iterative steps to two or three.

Pythagorean Triples: Pythagoras, who lived about five centures before Christ, was a mathematician, philosopher and mystic. When he discovered that the square root of 2 could not be expressed as the ratio of two integers (we now say that it is irrational), he thought he had discovered some impossible flaw in the perfection of the World, and swore his followers to secrecy; legend tells us that one of his disciples, Hippasus, was murdered when he divulged the secret (another legend has it that Hippasus, not Pythagoras, who discovered the irrationality of the square root of 2).

Pythagoras proved that for any right triangle the square of the length of the hypotenuse is equal to the sum of the squares of the other two sides. He also discovered that given any coprime m and n, a primitive right triangle (all sides coprime to each other) has sides m2n2, 2mn, m2 + n2; for instance, with m = 2 and n = 1, the triangle is 22 − 12 = 2, 2 × 2 × 1 = 4, and 22 + 12 = 5.

function triple(m, n)
    return m*m - n*n, 2*m*n, m*m + n*n

An alternative method is to take any primitive Pythagorean triple {a, b, c} and generate three new primitive Pythagorean triples as {a-2b+2c, 2a-b+2c, 2a-2b+3c}, {a+2b+2c, 2a+b+2c, 2a+2b+3c}, {−a+2b+2c, −2a+2b+3c}; the process starts from {3, 4, 5}. Of course, non-primitive triples can be generated by multiplying all three elements of a primitive triple by some constant k.

Greatest Common Divisor: Euclid was either a Greek mathematician of the third century before Christ or, as some historians suggest, the conglomerate name of several mathematicians. Euclid wrote Elements, a textbook of geometry and number theory which has been in continuous publication since it was written, which is famous for its method of starting with five axioms and deriving all of geometry from them.

Euclid’s Elements, Book VII, Proposition 2, gives an algorithm for computing the greatest common divisor of two integers. Euclid’s algorithm works by repeatedly subtracting the smaller number from the larger, which reduces the magnitude of the numbers, thus guaranteeing termination of the algorithm, without affecting the greatest common divisor, since both the smaller number and the difference between the two numbers must be multiples of the greatest common divisor.

function gcd(m, n) # ancient
    if m < n return gcd(m, n-m)
    if n < m return gcd(m-n, n)
    return m
function gcd(m, n) # modern
    if n == 0 return m
    return gcd(n, m % n)

Euclid used repeated subtraction; nowadays we use modular arithmetic. Knuth calls this the “grand-daddy” of all algorithms, even though it isn’t the oldest, because it was the first to be written in rigorous form.

Approximation of Pi: Archimedes of Syracuse (on the island of Sicily) was a famous inventor of the third century before Christ: the screw pump, block-and-tackle pulley, odometer (it dropped a ball every time the wheel completed a turn), and numerous devices of war were among his inventions. He didn’t invent the lever, but was the first to explain how it worked, and he famously stated “Give me a lever and a place to stand, and I can move the world.” His most famous discovery was that objects float when they weigh less than the water they displace, which he used to prove that the king’s crown, thought to be pure gold, was actually an amalgam with silver; it is said that he discovered the principle while bathing, whereupon he ran naked through the street shouting “Eureka!”

The ratio of the circumference of a circle to its diameter is the mathematical constant known as π, which is approximately 3.141592654. Archimedes bounded the value of π in the range 223/71 < π < 22/7 by calculating the perimeters of two hexagons, one inscribed inside a circle and one circumscribing it, then successively doubling the number of sides of the inscribed and circumscribed regular polygons through the series 6, 12, 24, 48, and 96.

function pi(n) # archimedes used 6
    outer := 3 * sqrt(3)
    inner := outer / 2
    for i from 1 to n
        outer = 2 / (1/outer + 1/inner)
        inner = sqrt(outer * inner)
    return inner, outer

Archimedes’ approximation 22/7 is still frequently used today, but his method of computing the approximation has been replaced by a series expansion due to Srinivasa Ramanujan, or some similar series expansion, which converges in just a few steps; by contrast, Archimedes’ algorithm requires 27 steps for double-precision accuracy.

Prime Numbers: Eratosthenes, who measured the circumference of Earth, the distance from Earth to Sun, and the tilt of Earth’s axis, devised a system of latitude and longitude and was third chief librarian of the great library at Alexandria, succeeding Ptolemy and Apollonius, invented a method of enumerating prime numbers about 200BC; his writing has been lost, but we know of his invention through the writings of Nicomachus two centuries later.

The Sieve of Eratosthenes identifies primes by striking out multiples and keeping what’s left; the image is that composites fall through the sieve but primes remain. Initialize a list of numbers, from 2 to the desired limit n all marked as prime, then consider each number in turn; if it has not been marked as composite, report it as prime, then mark all its multiples as composite, starting from the square of the prime (since all smaller multiples will have already been marked composite by smaller primes).

function primes(n)
    sieve := makeArray(2..n, True)
    for p from 2 to n
        if sieve[p]
            output p
            for i from p*p to n step p
                sieve[i] = False

Modern mathematicians have optimized the basic Sieve of Eratosthenes shown above by eliminating the small primes that, because they have so many multiples, take most of the time; eliminating multiples of 2 is easy, and “wheels” can be used to eliminate multiples of 3, 5, 7, and so on, though increasingly large wheels quickly become cumbersome to operate. Still, an optimized Sieve of Eratosthenes is faster than any of its many modern alternatives.

Your task it to translate these seven programs into your favorite programming language. 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.


by programmingpraxis at December 23, 2014 09:00 AM

December 19, 2014

Programming Praxis

Diana Cryptosystem

[ Today’s exercise comes from the blog of long-time reader Ben Simon, after he declined my offer to guest-author the exercise and told me to steal it. The code and most of the text is his, so he gets the credit, not me. ]

It’s been a while since we had an exercise from our cryptography topic. Today’s exercise is the Diana Cryptosystem, also known as the trigraph cipher, which was used militarily by US forces during the Vietnam War and is theoretically unbreakable when used properly.

There are two pieces to the system: the trigraph itself, which is pictured at right, and a one-time pad, like this:

WHTVI AUCFU RETFK OMSAL
MYMNE ZIEGP UKVTF WZHOK
GORWY WETFR COYET OOWHY
ZPDDA CMMXT VYTJI RRQGU

To use the cipher, a section of the one-time pad is chosen and the two five-character groups that begin the section are transmitted unchanged. Thereafter, the key character is looked up on the trigraph, the next plaintext character is on the top row, and the corresponding ciphertext character is read off the bottom row. Decryption is the inverse operation. For instance, the message ATTACK AT DAWN is encoded like this, starting from the third group on the second row of the one-time pad:

UKVTF WZHOK GORWY WETFR COYET
            ATTAC KATDA WNXYZ
UKVTF WZHOK TSPDZ TVNRI BYEXH

Then UKVTF WZHOK TSPDZ TVNRI BYEXH is transmitted by Morse code. The recipient looks up the first two groups on the one-time pad then decrypts as follows:

UKVTF WZHOK GORWY WETFR COYET
UKVTF WZHOK TSPDZ TVNRI BYEXH
            ATTAC KATDA WNXYZ

The cipher is unbreakable without the one-time pad.

We said earlier that the cipher was used militarily. Ben points to this description of its use:

Special Forces were one of (if not the only) units in Vietnam to utilize Morse code on a regular basis. We used a method of encryption called the Diana Cryptosystem.

The basis of these “One-Time Pads”, is that there were only two matching pads in existence, and they would only be used one time. They were booklets that contained randomly generated groups of 5-letter “words;” 30 words to a page. The person sending a message would first write the letters to the message, over these random groups of words. Included in the front of each one-time pad was a one-page encryption table. If I wanted to send the letter “P”, and the letter under the “P” was an “A”, then I would send a “K”. The person listening on the frequency at the other end, would have the other matching pad. They would write the letter they received (a “K”) over the letter in their one-time pad (an “A”), and decipher it based on the table, yielding the original letter “P”.

Each communication site in Vietnam (we had over 100 A-Camps along the Cambodian / Laotian border, and some 20 B-detachment sites spread over the country) had a different pad, depending on the location they were having the commo-check with. It obviously was very important that both people were using the appropriate matching pads, or the deciphered messages would not make any sense.

After a while, most of us became so proficient with the system, that we actually learned the deciphering matrix by heart. No matter what pads anyone had, the combinations always were the same. i.e. Any 3 letters always went together, regardless of the order; “BKO”/”KOB”/”OBK”/”BOK”. After listening to thousands and thousands of transmissions, it really got quite simple. If I was listening to code, and a letter “B” was sent (now remember, we usually sent around 20-25 “words” (5 letters per word) a minute, hence the importance of the “speed” keys!), and the letter it was associated with was an “O”, most of us would decipher as we heard it, and just write the “K”. That may sound like quite a yarn, but it is absolutely true.

Your task is to write a program that implements the trigraph cipher. 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.


by programmingpraxis at December 19, 2014 09:00 AM

December 16, 2014

Programming Praxis

Find Two Added Integers

I saw this question at a popular interview-question site and got mad at the suggested answer:

You are given two lists containing identical sets of integers except that the first list contains two additional integers not present in the second set. For instance, with a = {1 4 9 2 7 3} and b = {9 7 4 1}, the two additional integers are 2 and 3. Write a program to find the two additional integers.

Your task is to write the requested program. 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.


by programmingpraxis at December 16, 2014 09:00 AM

December 12, 2014

Programming Praxis

Magic Squares

Magic squares are an arrangement of consecutive counting numbers starting from 1 into rows and columns in which every row, column and the two main diagonals all sum to the same number. Magic squares are an important element of recreational mathematics, and have been known since antiquity; this magic square of order 3, with magic sum 15, was published in China in 650BC:

4 9 2
3 5 7
8 1 6

That magic square was constructed by the “start bottom, move down and right, else up” rule: Starting from either of the center cells on the bottom row, enter a 1, then move to the next square diagonally down and right (wrapping around the sides of the square if necessary), then enter the next number in sequence, 2, and so on. However, if the next square is occupied, move instead to the next square up from the current square, then continue the sequence. Various rules like “start left, move down and right, else up” and “start top, move up and right, else down” also work, but rules like “start top, move down and left, else up” don’t; I’ll let you have the pleasure of figuring out which rules work and which don’t. This method works only for odd orders; there are other methods for even orders, which we may examine at some other time.

In the example square, the starting cell is the center cell on the bottom edge, where you see 1. Moving down and right and wrapping to the top of the next column, enter 2. Then moving down and right and wrapping to the left of the next row, enter 3. The next cell down and right already contains 1, so instead move up from the current cell and enter 4. Then moving down and right, enter 5. Then moving down and right, enter 6. The next cell down and right, wrapping both the row and column, already contains 4, so instead move up from the current cell and enter 7. Then moving down and right and wrapping to the left of the next row, enter 8. Finally, moving down and right and wrapping to the top of the next column, enter 9.

Your task is to write a program that takes an odd order n, one of the four starting cells and a rule and generates the indicated magic square. 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.


by programmingpraxis at December 12, 2014 09:00 AM

December 10, 2014

The Racket Blog

The Racket package system and Planet

We have recently moved the majority of Racket's code base into packages and repositories separate from the main core repository. This has given the Racket package system another cycle of attention. Whenever this happens, there are often questions and confusion about how to solve various distribution problems with the package system. A natural point of comparison is the older Planet system provided by Racket that appears to solve similar problems. In this blog post, I attempt to explain the purpose of the package system and its relation to Planet.


The package system and Planet do not solve the same problem and don't exist for the same reason.


Planet is:

  1. A file distribution mechanism for source code.


    Via .plt files that are installed into a particular place on your machine and then raco setup'd.

  2. A mechanism for automatically downloading and installing source code just before it is needed by programs.


    Via the (planet ...) require form.

  3. A centralized database of libraries


    Via the Planet website and its server & protocol which were undocumented and proprietary for the majority of Planet's life

  4. A prescriptive model of how programs and libraries should be composed.


    Specifically the system of major/minor versions, tagging packages by author name, and embedding the names of packages in source code.


In contrast, the package system is:

  1. A file distribution mechanism for source code, byte code, and documentation.

    Via the raco pkg command.


In this way, the package system is almost identical to an operating system package system like Debian's dpkg and apt systems. The problem is very finely tailored and becomes more flexible as a result (notice that we can now distribute byte code and documentation.) This design aspires to follow the admonition of holy writ: "Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary."


Furthermore, it was intended to solve practical problems throughout the Racket ecosystem. In particular, one of the common complaints people had and have about Planet is the very long install times because of long builds. The package system allows this problem to be solved by distributing pre-built code.


Since the package system specifically does not address jobs 2, 3, or 4 of Planet, we have to ask, "Do they need to be solved?" and if so, "How can we solve them on top of the package system, i.e. as a library in honor of the design principle?".


In particular, 2 and 3 are very painful for people wanting to just use the file distribution mechanism of Planet. 2 causes unpredictability, because you don't know if running a program will start a long invocation of "raco setup", require Internet access, and start running un-vetted code. 3 requires you to share your code if you want to use the file distribution mechanism and is a single point of failure for doing installation.


By not mandating how to address 2 and 3 in the package system, we offer flexibility. Here is where the solutions to these jobs are now:


2. There is currently no way to get automatic installs of packages. However, both DrRacket and xrepl offer advice about which packages you might want to install to compile and run the program. It would be natural to extend this advice to be automatic and patches are welcome. Given the experiences of operating systems which merely make suggestions (nethack: command not found, provided by nethack-console), I personally feel like we are at the sweet spot.


3. The file distribution mechanism's flexible package sources combine with a very simple protocol for package catalogs (Take a URL, add/pkg/, add a string, get a read-able hash table) to look up packages you don't yet have. As a service, we run a few catalogs (one for each release, plus pkgs.r-l.o). But we expect that users with special needs (such as sensitive installations that need exactly certain tested and trusted versions, especially with proprietary software) will build their own catalogs on private Web sites.


Clearly, however, job 4 is where Planet and the package system differ the most.


With the package system, we follow the precedent of operating systems. An OS package's job is to get files into the right spot. An OS package contains a binary and instructions to install it as /usr/bin/zsh. It is not typical in OSes to be able to install multiple packages (such as different "versions" of the "same" package) that both provide /usr/bin/zsh. When you're at a Unix prompt, you don't have to write zsh-5.0.5/usr/bin/zsh. It's possible that many consider this is a big problem with OSes and indeed we do observe that it is fairly common to provide packages that provide binaries and libraries with embedded names such as how on my machine I have python2.6, python2.7, and python3.2 all in my $PATH. It is important to realize, however, that the deb format and the apt tool didn't need to change to support this change or future changes in perspective in how to compose code.


I hope this analogy helps understand the Racket package system. In the package system, a package doesn't install "binaries", "man pages", and "init scripts", but installs similar things, such as "module paths", "documentation manuals", and "raco commands". Each of these has a notion of conflict: can't have two zshs or two racket/lists; can't have two zsh.1 pages or two docs named doc; can't have two modules trying to provide raco neo-tokyo-is-about-to-explode. If you find a random .deb on the Internet, can you predict what binaries it will contain from its name? No. The same goes for Racket packages. However, if you are egregiously weird, then people probably won't want to install your packages, just like for random debs.


However, clearly rules are helpful. In the world of operating systems, you know that basically all packages distributed by Debian can be installed at the same time, except for "virtual packages" that do stuff like selecting whether postfix or sendmail should be responsible for the sendmail command. These rules are not enforced through technology, though. Instead, the Debian maintainers have a social process that enforces them, with information being provided by technology (such as regression systems that identify unintended conflicts.) The catalog server that the Racket team provides helps facilitate a similar process with the concentric rings (all ring <=1 packages can be installed at once and ring 1< packages can do anything.)


Non-conflicting sets of packages is the simplest rule to define and enforce. Other rules about backwards compatibility are much more complicated to define and enforce. I do not believe there is much precedent in the world of OSes, although we can see a little bit of what they do through things like libgtk, libgtk2, and libgtk3, where generally code written for one libgtk2 package is compatible with all libgtk2 packages made in the future, but libgtk3 is effectively a totally different package and introduces totally separate binaries like gtk3-config.


The most that the Racket team attempts to do here is to say, "Here are the rules we will follow and we think you should follow them too." Specifically, that we will maintain backwards compatibility or make a new package. We can't and won't enforce this, nor do we always live up to it with our own work (but we feel really bad about it when we do.)


Although my main goal of this section has been to explain my solution to (4), a great thing about the package system is that it is not binding at all. You can decide to follow the same rules as Planet. It is easy to do so:


  • Always name your packages $AUTHOR-$PACKAGE-$MAJOR
  • Always provide modules from only the collection, $AUTHOR-$PACKAGE-$MAJOR
  • Maintain backwards compatibility within releases of $AUTHOR-$PACKAGE-$MAJOR
  • Update the 'version metadata in the package info.rkt to reflect the $MINOR version.

And, boom!, you've recreated the rules of Planet to a T except for two things: (a) you'll still need to put a dependency on $AUTHOR-$PACKAGE-$MAJOR on the outside of code in a package info.rkt file rather than just inside files and (b) you can't use $AUTHOR-$PACKAGE to refer to "whatever the current $MAJOR" is.


The first compromise of adding something to the info.rkt is fairly modest, as it requires O(1) line modifications.


The second compromise is more severe, although actually you could just maintain such a package and deal with the breakage that occurs when you try to upgrade. Such breakage, however, was present in Planet too, as when a package was installed based on $AUTHOR-$PACKAGE only the local machine would cache the version used, so if you took the requiring module to another machine, it would download a new version and, potentially, have a backwards incompatibility problem. Using the package system in the most naive way (i.e. installing the $AUTHOR-$PACKAGE at some point and programming to that) would work exactly the same as Planet, except that the package system was designed to be able to port installations from one machine to another with raco pkg migrate.


I hope this blog post has helped explain the package system and shown that it does not prevent you from doing anything that Planet let you do, it only allows you to do more.

by Jay McCarthy (noreply@blogger.com) at December 10, 2014 05:58 PM

December 09, 2014

Programming Praxis

Every Possible Fraction

When I saw this web page a few days ago, I knew it would make a great exercise, simple but fascinating. Starting with x = 1, every fraction in lowest terms is generated by x ′ = 1 / (ny + 1), where n = ⌊ x ⌋ and y = x − n. The underlying math is known as the Stern-Brocot tree, and has been known since the ancient Greeks, who used terms of the Stern-Brocot tree to design the gear ratios in the Antikythera mechanism.

Your task is to write a program that generates the fractions in lowest terms. 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.


by programmingpraxis at December 09, 2014 09:00 AM