Planet Scheme

April 20, 2015

Alaric Snell-Pym

Ugarit archive mode manifest maker

When I last wrote about Ugarit progress, I had developed archive mode to the point where one could import a list of files with metadata from a "manifest file", and then search for files based on the metadata from the manifest and stream out chosen files. I gave an example of using this to play […]

by alaric at April 20, 2015 08:37 PM

The Racket Blog

Scheme Workshop 2015

Call For Papers:

Scheme and Functional Programming Workshop 2015
Vancouver, British Columbia, Canada
(Co-located with ICFP 2015)
http://andykeep.com/SchemeWorkshop2015/

Submissions related to Scheme, Racket, Clojure, and functional programming are welcome and encouraged. Topics of interest include but are not limited to:
  • Program-development environments, debugging, testing
  • Implementation (interpreters, compilers, tools, benchmarks, etc.)
  • Syntax, macros, hygiene
  • Distributed computing, concurrency, parallelism
  • Interoperability with other languages, FFIs
  • Continuations, modules, object systems, types
  • Theory, formal semantics, correctness
  • History, evolution and standardization of Scheme
  • Applications, experience and industrial uses of Scheme
  • Education
  • Scheme pearls (elegant, instructive uses of Scheme)
We also welcome submissions related to dynamic or multiparadigmatic languages and programming techniques.


Important Dates:
May 22nd, 2015 - Paper deadline
June 26th, 2015 - Author notification
July 19th, 2015 - Camera-ready deadline
September 4th, 2015 - Workshop

Submissions must be in ACM proceedings format, no smaller than 9-point type (10-point type preferred). Microsoft Word and LaTeX templates for this format are available at: http://www.acm.org/sigs/sigplan/authorInformation.htm

Submissions should be in PDF and printable on US Letter.

To encourage authors to submit their best work, this year we are encouraging shorter papers (around 6 pages, excluding references). This is to allow authors to submit longer, revised versions of their papers to archival conferences or journals. Longer papers (10--12 pages) are also acceptable, if the extra space is needed. There is no maximum length limit on submissions, but good submissions will likely be in the range of 6 to 12 pages.

More information available at: http://andykeep.com/SchemeWorkshop2015/

Organizers:
Andy Keep, Cisco Systems Inc. (General Chair)
Ryan Culpepper, Northeastern University (Program Chair)

(Apologies for duplications from cross-posting.)

by Ryan Culpepper (noreply@blogger.com) at April 20, 2015 05:44 PM

April 17, 2015

Programming Praxis

Euler’s Sum Of Powers Conjecture

Fermat’s Last Theorem, which dates to the seventeenth century states that there are no solutions in integers to the equation xn + yn = zn for n > 2; the Theorem was finally proved a few years ago by Andres Wiles. In the eighteenth century, Euler conjectured that for any n > 2, it would take at least n terms of the form xin to sum to an n th power. That conjecture held until the age of computers, in 1967, when Lander and Parkin found the counter-example 275 + 845 + 1105 + 133 = 144.

Your task is to write a program that finds counter-examples to Euler’s Conjecture. 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 April 17, 2015 09:00 AM

April 14, 2015

Programming Praxis

Balanced Ternary Arithmetic

We studied mixed-radix arithmetic in a previous exercise. In today’s exercise we look at a different kind of non-standard positional notation: balanced ternary, which is a base-3 number system that uses -1, 0 and 1 as its “trits” rather than 0, 1 and 2. For instance, the number -47 is written as (-1 1 1 -1 1) in balanced ternary, which is equivalent to -34 + 33 + 32 – 31 + 30. No separate sign is needed when using balanced notation; the sign of the leading trit is the sign of the whole number.

Arithmetic on balanced ternary numbers is done using the grade-school algorithms. Addition is done right-to-left with a carry; it is easy and fun to work out the plus-table. Subtraction is done by adding the negative, which can be computed by changing the sign of every trit. Multiplication works trit-by-trit through the multiplier, shifting at each trit.

Your task is to write functions that perform arithmetic on balanced ternary integers. 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 April 14, 2015 09:00 AM

April 10, 2015

Programming Praxis

Backup And Restore Procedures

Today’s exercise won’t ask you to write code. Let me tell you why.

I bought a new printer to replace my old printer that had failed. Both the salesman at Micro Center and the printer manufacturer’s sales rep, who was in the store that day, assured me that the printer would work with my Debian Linux system, and the manufacturer’s sales rep even gave me the web page where I could download the driver. I bought the printer, took it home, and installed the driver.

It didn’t work. My computer would no longer boot. I took computer and printer to the Knowledge Bar at Micro Center, but they don’t have sufficient Linux experience to figure out what’s wrong. After a few days, I resigned myself to re-installing the operating system.

That’s when I found out what had happened. At the point where the Linux installer asks you to specify the partition table, it told me that I had an invalid partition table and asked me to fix it, manually, before proceeding with the installation. Somehow, installing a printer driver corrupted the partition table. I won’t tell you the name of the printer manufacturer that was stupid enough to manage that trick, but it’s a big name that you would certainly recognize. Needless to say, I will be returning the printer and buying a different printer from a different manufacturer.

But before I do that, I have to fix my partition table, re-install my operating system, and restore my data from backups. As I write this on Thursday afternoon, I’m partway through that process, but I have already verified that I have a list of all installed software and that my file backup is readable.

Your task is to make sure that your backup and restore procedures are effective; if they aren’t, fix them. You should at least perform a single-file restore to demonstrate that your backup and restore procedure has at least a minimal chance of working when you need it. It looks like I will end up okay, but not without a lot of worry and a few choice words directed at a printer manufacturer that ought to know better.


by programmingpraxis at April 10, 2015 09:00 AM

April 07, 2015

Ben Simon

A Little Multi-Radix Programming Fun

I was sucked in by today's Programming Praxis Challenge: Pounds, Shillings, Pence. The goal was to create a couple math functions that worked with mixed radix values (for example, time which is specified in weeks, days, hours, minutes and seconds). Developing the API turned out to be some good fun. The exercise definitely reminded me of my very early days of programming, where you'd be given an assignment to make proper change (damn you pesky quarters, nickles and dimes!) and would have to div and mod your way to a solution. I recall being thoroughly stumped by these sort of tasks, so perhaps this was my way of slaying a very old dragon?

I ended up taking a page from Unix, and built my 'system' on the notion of converting multi-radix values to a single integer value. In the time example above, I convert all values to seconds (just like Unix does) to allow for easy math.

You could hardly call what I put together elegant, but I'm pleased with the results. It almost lets you think about the values you'd like to (in the case below, miles, yards, feet and inches) versus what the computer ideally works in.

(define dist '(1760 3 12)); read: (yards-per-mile feet-per-yard inches-per-foot)

(define short    (make-mr dist '(5))          ; 5 inches
(define football (make-mr dist '(100 0 0))    ; 100 yards
(define marathon (make-mr dist '(26 385 0 0)) ; 1 marathon

(show (mr-add football marathon))
(show (mr-sub marathon football))
...

And here's the complete code:

;; Mixed Radix Math --
;; http://programmingpraxis.com/2015/04/07/pounds-shillings-pence/
;;

(define time-spec '(7 24 60 60))
(define dist-spec '(1760 3 12))
(define hms-spec '(60 60))
  
(define (mr-factors spec)
 (let loop ((spec (reverse spec)) (current 1) (result '(1)))
  (cond ((null? spec) result)
        (else
         (let ((x (* (car spec) current)))
          (loop (cdr spec) x (cons x result)))))))

(define (mr-normalize spec value)
 (cond ((= (length value) (+ (length spec) 1)) value)
       ((> (length value) (+ (length spec) 1))
        (error "Invalid value: " value spec))
       (else
        (mr-normalize spec (append (list 0) value)))))

(define (mr->int spec value)
 (let ((factors (mr-factors spec))
       (cleaned (mr-normalize spec value)))
  (apply + (map * factors cleaned))))
  
 (define (int->mr spec value)
  (let loop ((value value) (factors (mr-factors spec)) (mr '()))
   (cond ((null? factors) (reverse mr))
         (else
          (let* ((f (car factors))
                 (q (quotient value f))
                 (r (remainder value f)))
           (loop r (cdr factors) (cons q mr)))))))

(define (show . x)
 (for-each display x)
 (newline))

;;
;; Slightly higher level API
;;

(define (make-mr spec value)
 (cons spec value))

(define (mr-spec x) (car x))
 
(define (mr-value x) (cdr x))

 
(define (mr-op op)
 (lambda (x y)
   (let ((xv (mr->int (mr-spec x) (mr-value x)))
         (yv (mr->int (mr-spec y) (mr-value y))))
     (make-mr (mr-spec x) (int->mr (mr-spec x) (op xv yv))))))
   
(define mr-add (mr-op +))
(define mr-sub (mr-op -))

 
(define x (make-mr hms-spec '(3 19 45)))

by Ben Simon (noreply@blogger.com) at April 07, 2015 06:46 PM

Programming Praxis

Pounds, Shillings, Pence

Mixed-radix number systems have a base, or radix, that varies at each position. For instance, the old-style British pounds, shillings and pence form a mixed-radix system where there are twelve pence in a shilling and twenty shillings in a pound, and calendars form a mixed-radix system where there are sixty seconds in a minute, sixty minutes in an hour, twenty-four hours in a day, and seven days in a week.

Your task is to write a program that accepts a definition of a mixed-radix system — for instance, (7 24 60 60) for the calendar mentioned above — and performs addition and subtraction of numbers written in that system. 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 April 07, 2015 09:00 AM

April 03, 2015

Programming Praxis

Reluctant Search

Wednesday was April Fools’ Day, and I was feeling frisky, so I implemented the reluctant search algorithm from Pessimal Algorithms and Simplexity Analysis by Andrei Broder and Jorge Stolfi. Their algorithm takes time O(2n), which is worse than the naive brute force O(n), to find the index of a target x in a sorted array. We looked at a different algorithm that paper in a previous exercise. I’ll leave it to you to fetch the paper and enjoy the sincerity of the authors’ pessimality.

Your task is to implement the reluctant search algorithm. 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 April 03, 2015 09:00 AM

March 31, 2015

Programming Praxis

Identifying Palindromes

Today’s task sounds simple but leads to a little bit of complexity.

Given an array, determine if it is a palindrome. Given a linked list, determine if it is a palindrome. Make both tests as efficient, in both time and space, as possible.

Your task is to write two programs to identify palindromes. 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 March 31, 2015 09:00 AM

March 27, 2015

Programming Praxis

String Re-ordering

Today’s exercise is a fun little interview question:

You are given a string O that specifies the desired ordering of letters in a target string T. For example, given string O = “eloh” the target string T = “hello” would be re-ordered “elloh” and the target string T = “help” would be re-ordered “pelh” (letters not in the order string are moved to the beginning of the output in some unspecified order).

Your task is to write a program that produces the requested string re-ordering. 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 March 27, 2015 09:00 AM

March 24, 2015

Programming Praxis

Excellent Numbers

Today’s exercise channels our inner Project Euler:

An excellent number n has an even number of digits and, if you split the number into the front half a and the back half b, then b2a2 = n. For example, 3468 = 682 − 342 = 4624 − 1156 = 3468, so 3468 is an excellent number. The only two-digit excellent number is 48 and the only four-digit excellent number is 3468. There are eight six-digit excellent numbers, 140400, 190476, 216513, 300625, 334668, 416768, 484848, and 530901, and their sum is 2615199. What is the sum of the 10-digit excellent numbers?

Your task is to compute the sum of the 10-digit excellent numbers; in the spirit of Project Euler, your solution should take no more than one minute of computation time. 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 March 24, 2015 09:00 AM

March 20, 2015

Programming Praxis

Matrix Transpose

Transposing a matrix turns rows into columns and columns into rows; for instance the transpose of the matrix below left is the matrix below right:

11 12 13 14 11 21 31
21 22 23 24 12 22 32
31 32 33 34 13 23 33
14 24 34

That’s easy enough to do when everything fits in memory, but when the matrix is stored in a file and is too big to fit in memory, things get rather harder.

Your task is to write a program that transposes a matrix to large to fit in memory. 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 March 20, 2015 09:00 AM

March 19, 2015

Ben Simon

The "Funny, It Doesn't Look Like a Linux Server", Server

Check out the cutest edition to our Linux family:

What you're looking at is a TP-Link TL-WA850RE WiFi range extender. A while back, I was having WiFi woes, so I picked up this $30 WiFi extender from Amazon. Turns out, the extender didn't help matters much, so I decided to put it to use in another way.

I installed OpenWRT on the device. OpenWRT is a Linux distribution designed for routers and the like, and it caught my eye because it had confirmed support for this particular device. Installing OpenWRT was almost too easy. I grabbed the .bin file (it was in the ar71xx » generic subdirectory) and used the upload firmware option that was available in the built in web based UI.

In just a few minutes I turned this hunk of white plastic into a Linux box, which, well did nothing. Through some small miracle, I was able to hook it up to a cable and telnet to it.

The first order of business was to configure this device as a WiFi client (or station) rather than the default configuration of being an access point. My hope that was once the device was in client mode, I could plug it into the wall in a random spot in our house, it would then boot up and I'd be able to telnet/ssh to it.

I found this and this article handy is setting up client mode on the device. However, it was ultimately this bit of advice that made all the difference:

If the target network uses the 192.168.1.0/24 subnet, you must change the default LAN IP address to a different subnet, e.g. 192.168.2.1 . You can determine the assigned WAN address with the following command: ...

I had wanted to setup the lan (wired side) of the device to have a static IP and the wan (WiFi side) to have a DHCP picked up IP. It wasn't obvious, but attempting to have both the static IP and dynamic IP be on the same network caused it to fail. The static IP would be set, but the WiFi side wouldn't ever be properly configured. Here's the configuration that ended up working for me:

# /etc/config/wireless
config wifi-device 'radio0'
        option type 'mac80211'
        option channel 'auto'
        option hwmode '11g'
        option path 'platform/ar934x_wmac'
        option htmode 'HT20'
        option disable '0'

config wifi-iface
        option device 'radio0'
        option network 'wan'
        option mode 'sta'
        option ssid 'SSID_TO_CONNECT_TO_GOES_HERE'  # [1]
        option encryption 'wep'
        option key 'PASSWORD_GOES_HERE_SEE_BELOW'   # [2]


# /etc/config/network
config interface 'loopback'
        option ifname 'lo'
        option proto 'static'
        option ipaddr '127.0.0.1'
        option netmask '255.0.0.0'

config interface 'lan'
        option ifname 'eth0'
        option force_link '1'
        option proto 'static'
        option ipaddr '192.168.2.75'     # [3]
        option netmask '255.255.255.0'

# /etc/config/firewall

# ... trimmed ...
config zone
        option name             wan
        list   network          'wan'
        list   network          'wan6'
        option input            ACCEPT  # [4]
        option output           ACCEPT
        option forward          REJECT
# ... trimmed ...

Some notes from above:

[1] - This is where you specify your router's SSID to connect up with
[2] - For WEP encryption I entered a hex value here, versus text. I used this site to do the conversion.
[3] - This was key: my router will give a 192.168.1.x IP, so this needs to be off that network.
[4] - Once I got everything set up, I was getting a connection refused message when trying to telnet to the server. The wan firewall needed to be changed to allow access

Once this all got hashed out, I was able plug the device into a random spot on the wall and telnet to it. Success! And yet, where do I go from here?

Obviously this is useful for educational purposes. I've already had to brush up on my basic networking skills to get this far, and there's plenty more to learn. Heck, you could use this $30.00 router to learn about life on the command line and generally how to be a Unix geek.

OpenWRT, however, is more than just a learning platform. There's a large number of software packages available, and they can be installed using opkg with ease. Turning this bad boy into a web server or the like should be easy enough. I was even able to install a version of scheme, by grabbing an older sigscheme package:

root@pipsqueak:/# opkg install http://downloads.openwrt.org/attitude_adjustment/12.09/ar71xx/generic/packages/sigscheme_0.8.3-2_ar71xx.ipk
Downloading http://downloads.openwrt.org/attitude_adjustment/12.09/ar71xx/generic/packages/sigscheme_0.8.3-2_ar71xx.ipk.
Installing sigscheme (0.8.3-2) to root...
Configuring sigscheme.
root@pipsqueak:/# sscm 
sscm> (map (lambda (x) (* x 9)) '( 1 2 3 4 5 6))
(9 18 27 36 45 54)
sscm> (exit)

Ultimately, what will make this useful is if I can find an application for the device that leverages its near invisible profile and dirt cheap price. If I was in the security business, or a nerd-action-novel writer, then the uses would be pretty obvious. Walk in, plug in device, walk out. And bam! you've got a server that can try to worm it's way onto the network. But for myself, I'm going to have to think a little more on this. Perhaps the device should live in my car? Or maybe it'll be useful in a hotel room? Not sure, but the technology is just too cool to ignore.

by Ben Simon (noreply@blogger.com) at March 19, 2015 03:09 PM

March 17, 2015

Programming Praxis

Common Elements Of Three Arrays

We have another interview question today. There are several different ways to approach this task, so it makes for an interesting exercise:

Given three arrays of integers in non-decreasing order, find all integers common to all three arrays. For instance, given arrays [1,5,10,20,40,80], [6,7,10,20,80,100] and [3,4,15,20,30,70,80,120] the two common integers are 20 and 80. If an integer appears multiple times in each of the arrays, it should appear multiple times in the output, so with input arrays [1,5,5,5], [3,4,5,5,10] and [5,5,10,20] the correct output is [5,5].

Your task is to write a program to solve the interview question. 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 March 17, 2015 09:00 AM

March 13, 2015

GNU Guix

GNU Guix recruits for GSoC

This year again Guix participates in the Google Summer of Code under the umbrella of the GNU Project.

If you are an eligible student, your contributions to GNU's package manager and to the Guix System Distribution are welcome!

We have collected project ideas (see also related ideas for GNU dmd) touching a variety of topics. If you are a free software hacker passionate about GNU/Linux packaging, Scheme, functional programming, operating system development, or peer-to-peer networking, check out the proposed projects. The list is far from exhaustive, so feel free to bring your own!

Get in touch with us on the mailing list and on the #guix IRC channel.

Make sure to send your application to Google by March 27th.

About GNU Guix

GNU Guix is a functional package manager for the GNU system. The Guix System Distribution (GuixSD) is an advanced distribution of the GNU system that relies on GNU Guix.

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 Guix System 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 armv7.

by Ludovic Courtès at March 13, 2015 12:25 PM