Planet Scheme

May 01, 2016

Grant Rettke

Chez Scheme Now Open Source

The other night I was daydreaming about buying a Chez Scheme license so I checked up on their license costs.

They are now Apache Licensed OSS.

Funny timing as they opened up only days prior.

The issue board is already active.

#chez on Freenode is blessed though the channel doesn’t seem to be up yet.

This is all delightful.

by Grant at May 01, 2016 03:13 PM

April 29, 2016

Programming Praxis

Binary Search

I goofed.

While writing a program (it may appear in a future exercise) I needed to search a sorted array for a target value. I should have copied an existing binary search, but instead I wrote my own, since I’m a good programmer and can certainly write a simple function like that. You won’t have any trouble guessing what happened next.

Your task is to write a binary search function; do it yourself, without looking at any library implementations or searching the internet. You might also want to write a test script to give you confidence in your function. 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 29, 2016 09:00 AM

April 28, 2016

The Racket Blog

Racket v6.5

Racket version 6.5 is now available from http://racket-lang.org/
  • Typed Racket and the racket/contract library generate code with lower overhead, speeding up typed/untyped interaction in a number of gradual typing programs we studied.
  • Macros written using syntax-parse automatically emit more accurate error messages.
  • The contract profiler captures costs from more contract combinators, including all those in the main distribution.
  • Hash table and set iteration, via both existing and new non-generic sequences, is more performant, up to twice as fast on microbenchmarks.
  • The Racket optimizer detects many more optimization opportunities, including when variables always hold numbers.
  • The db library supports single-result CALL statements in MySQL.
  • The net/dns library supports SRV records.
  • The racket/unix-socket library supports listen and accept operations.

The following people contributed to this release:
Adrien Tateno, Alex Knauth, Alexander Shopov, Alexis King, Andrew Kent, Asumu Takikawa, Ben Greenman, Chen Xiao, Chris Jester-Young, Daniel Feltey, Eric Dobson, Georges Dupéron, Gustavo Massaccesi, Ian Harris, Jay McCarthy, Jens Axel Søgaard, John Clements, Leandro Facchinetti, Lehi Toskin, Leif Andersen, Łukasz Dąbek, Marc Kaufmann, Matthew Flatt, Matthias Felleisen, Michael McConville, Mike Sperber, Paul Stansifer, Philippe Meunier, Robby Findler, Rodrigo Setti, Ryan Culpepper, Sam Caldwell, Sam Tobin-Hochstadt, Sorawee Porncharoenwase, Spencer Florence, Stephen Chang, Tony Garnock-Jones, Vincent St-Amour, WarGrey Gyoudmon Ju, and William J. Bowman.

Feedback Welcome

by Ryan Culpepper (noreply@blogger.com) at April 28, 2016 07:55 PM

April 26, 2016

Programming Praxis

An Integer Formula For Fibonacci Numbers

Today’s exercise isn’t really an exercise but an astonishing integer formula for computing the nth Fibonacci number; here it is in Python:

def fib(n):
    return (4 << n*(3+n)) // ((4 << 2*n) − (2 << n) − 1) & ((2 << n) − 1)

You can see an explanation here and discussion here.

Your task is to translate the program to your favorite 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 April 26, 2016 09:00 AM

April 24, 2016

GNU Guix

GNU Guix welcomes four students for GSoC

We are glad to announce that four students will join GNU Guix for the 2016 Google Summer of Code (GSoC):

All four projects sound exciting to us and we are happy to see progress on these fronts. Happy hacking!

About GNU Guix

GNU Guix is a transactional package manager for the GNU system. The Guix System Distribution or GuixSD is an advanced distribution of the GNU system that relies on GNU Guix and respects the user's freedom.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. 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. GuixSD offers a declarative approach to operating system configuration management, and is highly customizable and hackable.

GuixSD 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 April 24, 2016 07:45 PM

April 22, 2016

Programming Praxis

GCD Sum

Today’s exercise is inspired by A018804: Find the sum of the greatest common divisors gcd(k, n) for 1 ≤ kn.

Your task is to write a function that finds the sum of the greatest common divisors. 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 22, 2016 09:00 AM

April 19, 2016

Programming Praxis

Interview Timing

I came across an interesting interview question recently. I’ll tell you the question shortly. What made it interesting was that the same question was given to all candidates, and they were timed in getting a solution; candidates with shorter times were given higher scores than candidates with longer times.

Your task is to write the requested program, which you can access HERE after you are set up for timing.


by programmingpraxis at April 19, 2016 09:00 AM

April 15, 2016

Programming Praxis

Ten-Digit Pandigital Numbers Divisible By 1 Through 9

Today’s exercise solves somebody’s homework problem — but not too much, since he had to write his program in Java:

Find the two smallest ten-digit pandigital numbers (numbers that contain all the digits from 0 through 9) that are divisible by the numbers 1 through 9. Then find the two largest pandigital numbers that are divisible by the numbers 1 through 9.

Your task is to solve the homework problem. 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 15, 2016 08:59 PM

April 12, 2016

Programming Praxis

Titlecase

A string is titlecased when the first letter of each word is capitalized and the remaining letters are lower case. For instance, the string “programming PRAXIS” becomes “Programming Praxis” when titlecased.

Your task is to write a function that takes a string and returns it in titlecase. 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 12, 2016 09:00 AM

April 08, 2016

Programming Praxis

Google Interview Question

Today’s exercise is an interview question from Google:

Given a list of words, find the maximum value of the product of the lengths of two words from the list, subject to the constraint that the two words cannot share any letters. For instance, given the words ABCW, BAZ, FOO, BAR, XTFN, and ABCDEF, the pair FOO BAR has a product of 9, the pair BAZ XFTN has a product of 12, and the pair ABCW XTFN has a product of 16, which is the maximum. Note that the pair ABCW ABCDEF doesn’t work because the two words share three letters.

Your task is to write a program to solve Google’s 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 April 08, 2016 09:00 AM

April 05, 2016

Programming Praxis

Java Interview Question

We have an interview question today:

Input comes from a file containing pipe-delimited records with three fields: student id (a positive integer), course title (a string), and score (a positive integer). You may assume that any combination of student id and course is unique. Here’s an example input file:

22|Math|45
23|English|52
22|English|51
26|Math|72
23|Math|61
21|English|81

The file may have any number of records, and there is no limit on the number of unique courses. You should write a program to read the file and write a list of all courses in the file, combined with the score of the lowest-numbered student in the course. Thus, the correct output for the input shown above is:

Math 45
English 81

Your task is to write a program to solve the interview question; the original question specified a Java solution, but you are free to use any 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 April 05, 2016 09:00 AM

April 01, 2016

Programming Praxis

SUM And XOR

I don’t know the origin of it, but today’s exercise must be either a homework problem or an interview question:

Assume there are two positive integers a and b that have sum s and XOR x. Given an s on the range [2, 1012] and x on the range [0, 1012], find a list of possible values of the ordered pairs (a, b). For instance, given s = 9 and x = 5, there are four possible pairs: (2, 7), (7, 2), (3, 6) and (6, 3).

Your task is to write a program that finds the pairs. 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 01, 2016 09:00 AM

March 29, 2016

GNU Guix

GNU Guix & GuixSD 0.10.0 released

We are pleased to announce the new beta release of GNU Guix and GuixSD, version 0.10.0!

The release comes with USB installation images to install the standalone GuixSD, and with tarballs to install the package manager on top of a running GNU/Linux system, either from source or from binaries.

It’s been almost 5 months since the previous release, and many things happened! The highlights include:

See https://lists.gnu.org/archive/html/guix-devel/2016-03/msg01241.html for details.

About GNU Guix

GNU Guix is a functional package manager for the GNU system. The Guix System Distribution or GuixSD is an advanced distribution of the GNU system that relies on GNU Guix and respects the user's freedom.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. 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. GuixSD offers a declarative approach to operating system configuration management, and is highly customizable and hackable.

GuixSD 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 29, 2016 12:52 PM

Programming Praxis

Multi-Way Merge

A multi-way merge takes two or more sorted input lists and creates a single output list that contains all the elements of the various input lists in sorted order.

If there are only two input lists, this is easy; run through the lists in order, at each step moving the smaller of the two elements at the heads of the lists to the output.

Things get harder if there are k input lists with k > 2. The easiest approach is to merge the first two lists, then merge that with the third list, and so on, performing k − 1 merges.

The “tournament” approach first merges input lists pairwise, forming a new set of k / 2 lists each twice as long as the originals, then recurs. Thus input lists 1 and 2 are merged, then 3 and 4 are merged, and so on, then merged list 1/2 is merged with merged list 3/4, and so on, until at the end only one merged list remains.

The best approach is to arrange all the input lists in a priority queue based on their smallest element. At each step the element at the head of the priority queue is written to the output, that element is removed from the list at the head of the priority queue, and the priority queue is reformed to put the new smallest element at its head.

Your task is to write the three versions of multi-way merge 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 March 29, 2016 09:00 AM

March 23, 2016

GNU Guix

GNOME in GuixSD

It’s a feature that many users were waiting for: proper GNOME support in GuixSD. Good news: the forthcoming Guix and GuixSD release will give you exactly that! Don’t miss the obligatory screenshot!

You would think adding GNOME is routine distro work involving a lot of packaging and bits of plumbing that’s already been done a hundred times, which is probably true! Yet, adding GNOME support turned out to be interesting in many ways: it’s a good test for GuixSD’s declarative operating system configuration framework, it’s a way to formalize how this whole software stack fits together, and it’s been an insightful journey into GNU/Linux desktop plumbing!

Of course, a lot of software needs to be packaged to begin with. This had been on-going for some time, culminating with the addition of a gnome meta-package thanks to the hard work of 宋文武 (Sou Bunnbu) and other hackers. On the way, we added an auto-updater for GNOME packages, because all these package recipes need love.

The more interesting parts were system integration. Modern GNOME/Freedesktop environments rely on a number of daemons, most of which talk over D-Bus, and extending each other’s functionality: udev, udisks, upower, colord, geoclue, and polkit, to name a few. Being able to compose all these system services was one of the driving use cases behind the design of GuixSD’s new service composition framework. With this design, we knew we were able to have fine control over the service composition graph. Challenge #1 overcome!

Since GuixSD uses the GNU Shepherd and not systemd as its init system, we needed a way to provide the “logind” functionality that systemd implements, and which allows GNOME to know about users, sessions, and seats.

So Andy Wingo courageously started by extracting logind from systemd, leading to “elogind”. At this point, we had this daemon that could keep track of logged-in users and active sessions, and which GNOME could talk to over D-Bus… provided all the relevant PAM services would use the pam_elogind module so that elogind knows when a user logs in and out, as Andy nicely explained it.

This pam_elogind thing is a typical example of a cross-cutting concern: if you use elogind, then you want all the relevant login-related PAM services (mingetty, the X login manager, commands such as su, the SSH daemon, etc.) to use pam_elogind. To achieve that, we updated our PAM service such that it could be extended with such cross-cutting modules. At last, we had proper logind support!

At this point, the brave could start using GNOME on GuixSD but would soon realize that, for example, the “power off” button wouldn’t have the desired effect, or that changing a laptop’s backlight wouldn’t work because polkit, the daemon that allows unprivileged users to perform privileged operations like that one, was missing essential policy files.

You would think you can finally change the brightness of your screen, but no! Turns out that polkit would refuse to run gnome-setting-daemon’s backlight helper program because elogind happened to fail to map PIDs to sessions. Whatever.

Of course there were still a bunch of embarrassing glitches such as GNOME suspending right after it wakes up from suspend, failure to start in QEMU, or the lack of GNOME’s favorite font. Well, it seems that all these are gone now!

GuixSD users can now enable GNOME by adding one line in their operating system configuration. Overall, this has been a nice experience involving a variety of areas.

About GNU Guix

GNU Guix is a functional package manager for the GNU system. The Guix System Distribution or GuixSD is an advanced distribution of the GNU system that relies on GNU Guix and respects the user's freedom.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. 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. GuixSD offers a declarative approach to operating system configuration management, and is highly customizable and hackable.

GuixSD 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 23, 2016 01:48 PM