Planet Scheme

September 21, 2014

Grant Rettke

Announce: PicoLisp in Hardware (PilMCU)

PilMCU is an implementation of 64-bit PicoLisp directly in hardware. A
truly minimalistic system. PicoLisp is both the machine language and the
operating system:

Via help-gnu-emacs.

by Grant at September 21, 2014 01:18 AM

September 19, 2014

Jeremy Kun

Occam’s Razor and PAC-learning

So far our discussion of learning theory has been seeing the definition of PAC-learning, tinkering with it, and seeing simple examples of learnable concept classes. We’ve said that our real interest is in proving big theorems about what big classes of problems can and can’t be learned. One major tool for doing this with PAC is the concept of VC-dimension, but […]

by Jeremy Kun at September 19, 2014 03:00 PM

Programming Praxis

Diophantine Reciprocals

Career Cup claims that Amazon asked this as an interview question; it is also Problem 108 at Project Euler:

In the following equation x, y and n are positive integers: 1 / x + 1 y = 1 / n. For n = 4 there are exactly three distinct solutions: 1/5 + 1/20 = 1/6 + 1/12 = 1/8 + 1/8 = 1/4. What is the least value of n for which the number of distinct solutions exceeds one thousand?

Your task is to solve Amazon’s question; you might also like to make a list of the x, y pairs that sum to a given n. 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 September 19, 2014 09:00 AM

September 18, 2014

Joe Marshall

A useful, if somewhat pointless, trick with homographic functions

In my previous posts I showed that if you are applying a homographic function to a continued fraction, you can partly evaluate the answer before you completely apply the function. Instead of representing homographic functions as lambda expressions, I'll represent them as a list of the coefficients a, b, c, and d in (lambda (t) (/ (+ (* a t) b) (+ (* c t) d))). I'll represent a simple continued fraction as a stream of the integer terms in the denominators.
Here is how you partly apply a homographic function to a continued fraction:
(define (partly-apply hf cf)
  (let ((a (first  hf))
        (b (second hf))
        (c (third  hf))
        (d (fourth hf)))
    (if (empty-stream? cf)
        (values (list a a
                      c c)
                cf)
        (let ((term (head cf)))
          (values (list (+ (* a term) b) a
                        (+ (* c term) d) c)
                  (tail cf))))))
Partly evaluating a homographic function involves looking at the limits of the function as t starts at 1 and goes to infinity:
(define (partly-evaluate hf)
  (let ((a (first hf))
        (b (second hf))
        (c (third hf))
        (d (fourth hf)))

    (if (and (same-sign? c (+ c d))
             (let ((limit1 (quotient      a       c))
                   (limit2 (quotient (+ a b) (+ c d))))
               (= limit1 limit2)))
        (let ((term (quotient a c)))
          (let ((new-c (- a (* c term)))
                (new-d (- b (* d term))))
            (values term (list c d new-c new-d))))
        (values #f #f))))
We can combine these two steps and make something useful. For example, we can print the value of applying a homographic function to a continued fraction incrementally, printing the most significant digits before computing further digits.
(define (print-hf-cf hf cf)
  (call-with-values (lambda () (partly-evaluate hf))
    (lambda (term hf*)
      (if (not term)
          (call-with-values (lambda () (partly-apply hf cf))
            print-hf-cf)
          (begin
            (display term) 
            ;; take reciprocal and multiply by 10
            (let ((a (first hf*))
                  (b (second hf*))
                  (c (third hf*))
                  (d (fourth hf*)))
              (print-hf-cf (list (* c 10) (* d 10)
                                 a        b)
                           cf)))))))
But how often are you going to apply a homographic function to a continued fraction? Fortunately, the identity function is homographic (coefficients are 1 0 0 1), so applying it to a continued fraction doesn't change the value. The square root of 2 is a simple continued fraction with coefficients [1 2 2 2 ...] where the 2s repeat forever. We apply the identity homographic function to it and print the results:
(printcf (list 1 0 0 1) sqrt-two)
14142135623730950488016887242096980785696718^G
; Quit!
As you can see, we start printing the square root of two and we don't stop printing digits until the user interrupts.

A fancier version could truncate the output and print a decimal point after the first iteration.

by Joe Marshall (noreply@blogger.com) at September 18, 2014 07:06 PM

September 16, 2014

Programming Praxis

Torn Numbers

In 1917, Henry Ernest Dudeney published a book Amusements in Mathematics of arithmetic puzzles. Today’s exercise solves puzzle 113 from that book:

A number n is a torn number if it can be chopped into two parts which, when added together and squared, are equal to the original number. For instance, 88209 is a torn number because (88 + 209)2 = 2972 = 88209.

Your task is to write a program to find torn numbers. 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 September 16, 2014 09:00 AM

GNU Guix

Join us for a Guix hackathon on Sep. 27-28!

The GNU Guix project is organizing a hackathon on September 27th and 28th, 2014. The hackathon will take place primarily on-line, on the #guix IRC channel on Freenode. We have started collecting a list of hacking ideas. Feel free to stop by and make more suggestions!

The hackathon is accessible to anyone with experience in GNU/Linux packaging or systems hacking. Scheme programmers will find additional things to work on in the tool set. Finally, we will also be welcoming newcomers and helping them get started.

This is a followup to last year's hackathon, organized for GNU's 30th anniversary.

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, with Guile Scheme programming interfaces.

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.

by Ludovic Courtès at September 16, 2014 07:58 AM

September 12, 2014

Programming Praxis

Levenshtein Distance

In a previous exercise we computed the edit distance between two strings where the allowable operations were insert or delete characters; we made the calculation by determining the longest common subsequence. A different definition of edit distance allows substitutions as well as insertions and deletions, and is called the Levenshtein distance, since it was studied by Vladimir Levenshtein in 1965. For example, the edit distance between “hill” and “hilt” is 2 (delete the “l” and insert the “t”) but the Levenshtein distance is 1 (replace “l” by “t”).

The basic algorithm is recursive: if either string is empty, the Levenshtein distance is the length of the other string, otherwise it is the minimum of the Levenshtein distance computed by deleting the first character from the first string, by deleting the first character from the second string, or by deleting the first characters of each of the two strings (adding 1 if the two characters differ), plus the Levenshtein distance of the remaining substrings. That computation takes exponential time as it recomputes the same substring Levenshtein distances many times. A better algorithm uses dynamic programming to build up the substring distances, so they are always available as they are needed.

Your task is to write two functions to compute the Levenshtein distance between two 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 September 12, 2014 09:00 AM

September 10, 2014

Christian Kellermann

Fractals Invaders in doodle

Inspired by jtarbell's original fractal invaders, I took the liberty of implementing this in CHICKEN Scheme using doodle.

(use doodle matchable (srfi 1))

(define block-width 3)
(define block-height 3)
(define block-rows 5)
(define block-cols 6)

(new-doodle width: 840
            height: 420
            background: solid-white)

(define (block x y row col)
  (let*  ((x0 (+ x (* col block-width)))
          (y0 (+ y (* row block-height)))
          (x1 (+ x0 block-width))
          (y1 (+ y0 block-height)))
    (list x0 y0 block-width block-height)))

(define (color v)
  (if (= v 0) solid-black solid-white))

(define (mirror grid)
  (map (lambda (lst)
         (append lst (cdr (reverse lst)))) grid))

(define (draw-blocks x y blks color-chooser)
  (let loop ((bs (mirror blks))
             (row 0))
    (cond ((null? bs) #t)
          (else
           (fold (lambda (b col)
                   (apply filled-rectangle `(,@(block x y row col)
                                             ,(color-chooser b)))
                   (add1 col))
                 0
                 (car bs))
           (loop (cdr bs)
                 (add1 row))))))

(define (random-blocks)
  (list-tabulate block-rows
                 (lambda _
                   (list-tabulate (/ block-cols 2)
                                  (lambda _ (random 2))))))


(define (random-critter! x y)
  (draw-blocks x y (random-blocks) color))

(define (invaders)
  (let outer ((x 3))
    (if (< x doodle-width)
        (begin
          (let inner ((y 3))
            (if (< y doodle-height)
                (begin
  
                  (random-critter! x y)
                  (inner (+ y (* 2 block-width block-cols))))))
          (outer (+ x (* 2 block-height block-rows))))))
  (show!))

(define *painting* #t)

(world-inits (lambda ()
                (invaders)))

(world-changes (lambda (events dt exit)
                 (for-each
                  (lambda (e)
                    (match e
                           (('key 'pressed #\esc)
                            (exit #t))
                           (('key 'pressed #\space)
                            (set! *painting* (not *painting*)))
                           (else (void))))
                  events)
                 (when *painting*
                       (invaders))))

(run-event-loop)

It turned out to be a nice coffee break hack and the resulting images leave a lot of room for imagination. Maybe this is a nice way to create sprites for the next retro arcarde game procedurally? Try tuning the block rows and columns!

Enjoy!

by Christian Kellermann at September 10, 2014 10:30 AM

September 09, 2014

Programming Praxis

Drawing Diamonds

Given a small positive integer n, write a function that draws a diamond, either filled or in outline as specified by the user. For instance, here are filled and outline diamonds for n = 5:

    *              *
   * *            * *
  * * *          *   *
 * * * *        *     *
* * * * *      *       *
 * * * *        *     *
  * * *          *   *
   * *            * *
    *              *

Note that there is a single space between asterisks in the filled version of the diamond.

Your task is to write a program that draws diamonds as 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.


by programmingpraxis at September 09, 2014 09:00 AM

September 05, 2014

Joe Marshall

Another stupid homographic function trick

In my last post I showed that if you take a homographic function and apply it to a fraction, you can partly apply the function to the integer part of the fraction and get a new homographic function. The new function can be applied to the non-integer part of the fraction to generate an answer equivalent to the original function applied to the original fraction.

It turns out that you can go in the other direction as well. You can partly evaluate a homographic function. For example, consider this homographic function:
((lambda (t)
   (/ (+ (* 70 t) 29)
      (+ (* 12 t)  5))) n)
Which we intend to apply to some positive number n. Even if all we know is that n is positive, we can deduce that the value of the homographic function is between 29/5 (when t is 0) and 70/12 (as t goes to infinity). The integer part of those values are the same, so we can factor that out:
(+ 5 (/ 1 ((lambda (t)
               (/ (+ (* 12 t) 5)
                  (+ (* 10 t) 4))) n)))
The partial answer has an integer value of 5 and a fractional part that contains a new homographic function applied to our original n. We can do it again:
(+ 5 (/ 1
        (+ 1 (/ 1
                ((lambda (t)
                   (/ (+ (* 10 t) 4)
                      (+ (* 2 t) 1))) n)))))
The fractional part of the answer can itself be factored into another integer and a new homographic function applied to our original n.

A generalized continued fraction is a number of the form:
If all the bi are 1, then it is a simple continued fraction. You can turn generalized continued fractions into a simple continued fraction by doing the algebra.

What happens if you partly apply a homographic function to a continued fraction? The algebra is tedious, but here's what happens:
((lambda (t)
   (/ (+ (* 2 t) 1)
      (+ (* 1 t) 3))) (+ 3 (/ 1 (+ 7 (/ 1 16)))))

;; after one step
((lambda (t)
   (/ (+ (* 7 t) 2)
      (+ (* 6 t) 1))) (+ 7 (/ 1 16)))

;; after two steps
((lambda (t)
   (/ (+ (* 51 t) 7)
      (+ (* 43 t) 6))) 16)
By partly apply a homographic function to a continued fraction, we can process the integer part separately and before the fractional part. By partly evaluating the application of a homographic function, we can often determine the integer part without fully evaluating the argument to the function. For example, after step one above, we could instead partially evaluate the application:
;; after one step
((lambda (t)
   (/ (+ (* 7 t) 2)
      (+ (* 6 t) 1))) (+ 7 (/ 1 16)))

;; Alternatively, partially evaluate first term
(+ 1 (/ 1
       ((lambda (t)
           (/ (+ (* 6 t) 1)
              (+ (* 1 t) 1))) (+ 7 (/ 1 16)))))

by Joe Marshall (noreply@blogger.com) at September 05, 2014 02:53 PM

Programming Praxis

Skyline Puzzle

The Skyline Puzzle is a classic programming exercise; it draws a silhouette of a city skyline by blocking out portions of buildings that are masked by taller buildings. A city is a list of buildings specified as triples containing left edge, height, and right edge. For instance, the list of triples (1 11 5) (2 6 7) (3 13 9) (12 7 16) (14 3 25) (19 18 22) (23 13 29) (24 4 28) encodes the eight buildings shown at the left of the diagram, and the path 1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0 encodes the skyline shown at the right of the diagram, where the odd-indexed elements of the output are the x-coordinate of the skyline and the even-indexed elements of the output are the y-coordinate of the skyline. (It makes more sense to me that the output should look like (1 11) (3 13) (9 0) (12 7) (16 3) (19 18) (22 3) (23 13) (29 0) but that’s not the way the puzzle is ever specified.) Notice that the second (2 6 7) and eighth (24 4 28) buildings are not part of the skyline.

Your task is to write a program that takes a list of buildings and returns a skyline. 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 September 05, 2014 09:00 AM

September 04, 2014

GNU Guix

Emacs as a general-purpose package manager

GNU Guix, the package manager written for the GNU system, now has a neat Emacs user interface! It offers a visual, user-friendly alternative to the guix package command-line interface.

For those familiar with package.el, the main user interface is quite similar: commands like guix-newest-available-packages, guix-search-by-regexp, and guix-installed-packages present a browsable list of packages. Individual packages can be selected, which displays additional details and presents a button to install or delete them. It is also possible to mark a set of packages for installation, upgrade, or deletion, and execute the set of operations in a single transaction.

The interface has been developed by Alex Kost and was merged in Guix a day ago. It uses Geiser, the beloved Guile/Emacs interface and development environment, to communicate with the underlying Guile process. That Guile process, in turn, simply uses Guix and the whole distribution as libraries—the goodness of embedding the packaging DSL in a general-purpose language.

Try it out and let us know what you think!

by Ludovic Courtès at September 04, 2014 08:30 AM

September 03, 2014

Joe Marshall

Stupid homographic function trick

A function of the form
is called a homographic function.  Here is one in Scheme:
(lambda (t)
   (/ (+ (* 3 t) 4)
      (+ (* 5 t) 2)))
And here is what it's graph looks like:
If you multiply all the coefficients (a, b, c, and d) by the same number, it doesn't change the function. For instance, this homographic function:
(lambda (t)
   (/ (+ (* 21 t) 28)
      (+ (* 35 t) 14)))
is the same as the one above. If one of your coefficients isn't an integer, don't worry, you can multiply everything by the denominator and get an equivalent homographic function. On the other hand, you can divide all your coefficients by their greatest common divisor and get an equivalent homographic function with smaller coefficients. We'll keep our homographic functions in smallest integer form.

A rational number can be written as the sum of an integer and a fraction less than one. For example, 23/5 = 4 + 3/5.

Let's apply a homographic function to a rational number:
((lambda (t)
   (/ (+ (* a t) b)
      (+ (* c t) d))) (+ x y/z))

;; substitute
(/ (+ (* a (+ x y/z)) b)
   (+ (* c (+ x y/z)) d))

;; distribute the multiplication
(/ (+ (* a x) (* a y/z) b)
   (+ (* c x) (* c y/z) d))

;; multiply top and bottom by z/y
(/ (* z/y (+ (* a x) (* a y/z) b))
   (* z/y (+ (* c x) (* c y/z) d)))

;; distribute the multiplication
(/ (+ (* a x z/y) (* a y/z z/y) (* b z/y))
   (+ (* c x z/y) (* c y/z z/y) (* d z/y)))

;; simplify
(/ (+ (* a x z/y) a (* b z/y))
   (+ (* c x z/y) c (* d z/y)))

;; rearrange terms
(/ (+ (* a x z/y) (* b z/y) a)
   (+ (* c x z/y) (* d z/y) c))

;; factor out z/y
(/ (+ (* (+ (* a x) b) z/y) a)
   (+ (* (+ (* c x) d) z/y) c))

Now we do something tricky. We abstract out the z/y term:
((lambda (t)
   (/ (+ (* (+ (* a x) b) t) a)
      (+ (* (+ (* c x) d) t) c))) (/ z y))
If introduce a let form, we can see something interesting:
((lambda (t)
   (let ((a1 (+ (* a x) b)) 
         (b1 a)
         (c1 (+ (* c x) d))
         (d1 c))
     (/ (+ (* a1 t) b1)
        (+ (* c1 t) d1)))) (/ z y))
We find a new homographic function being applied to a new rational number. The new homographic function has coefficients related to the original one, and the new rational number is the reciprocal of the fractional part of the original rational number. So if we have a homographic function hf applied to a fraction of the form x + y/z, we can easily find a new homographic function hf' that when applied to z/y will produce the same answer as the original. Applying a homographic function to a fraction has the effect of "eating" the integer part of the fraction, which generates a new homographic function that is applied to the reciprocal of the fractional part.

by Joe Marshall (noreply@blogger.com) at September 03, 2014 05:32 PM

September 02, 2014

Programming Praxis

Longest Increasing Subsequence

A sequence is a list of integers (or any other ordered type, but we’ll use integers to keep things simple). A subsequence is any, possibly non-consecutive, list drawn from the parent sequence with items in the same order as the parent sequence. An increasing subsequence is a subsequence with all the items in increasing order. A longest increasing subsequence (there may be more than one with the same length) is an increasing subsequence of a parent sequence of the greatest possible length. For instance, the sequence (3 2 6 4 5 1) has longest increasing subsequences (2 4 5) and (3 4 5).

The algorithm to find the longest increasing subsequence is similar to the algorithm for patience sorting of a previous exercise, with a small modification. When dealing the cards, each time a card is placed on a pile, a back-pointer to the top card on the previous pile is placed along with the card. Then, when all the cards are dealt, the number of piles is the length of the longest increasing subsequence, and the longest increasing subsequence can be recovered by taking the top card from the last pile and following the back-pointers to previous piles.

For instance, with sequence (3 2 6 4 5 1) the cards are dealt with 3 and 2 on the first pile, 6 and 4 on the second pile, 5 on the third pile, and 1 on the first pile, so the longest increasing subsequence has length 3. The 5 on the third pile ends the longest increasing subsequence, it points to the 4 which was on the top of the second pile when 5 was added to the third pile, and 4 points to the 2 which was on the top of the first pile when 4 was added to the second pile; even though 1 was later added to the first pile, is wasn’t yet on the pile when 4 was added to the second pile, so it’s not part of the longest increasing subsequence.

Your task is to write a program to find the longest increasing subsequence of a sequence. 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 September 02, 2014 09:00 AM

August 31, 2014

Jeremy Kun

A Rook Game

Problem: Two players take turns moving a rook on an 8×8 chessboard. The rook is only allowed to move south or west (but not both in a single turn), and may move any number of squares in the chosen direction on a turn. The loser is the player who first cannot move the rook. What is the optimal play […]

by Jeremy Kun at August 31, 2014 10:51 PM