Planet Scheme

August 23, 2019

Programming Praxis

Sexy Primes

A sexy prime is a prime number p for which p + 6 is also prime. Such primes are called sexy because the Latin word for six is sex.

Your task is to write a program that counts the sexy primes between one billion and two billion. 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 August 23, 2019 09:00 AM

August 20, 2019

Programming Praxis

Sum Distinct Items

We have an interview question today:

In a list of integers, find the sum of the integers that appear only once. For instance, in the list [4 2 3 1 7 4 2 7 1 7 5], the integers 1, 2, 4 and 7 appear more than once, so they are excluded from the sum, and the correct anser is 3 + 5 = 8.

Your task is to write a program to find the sum of the distinct integers in a list. 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 August 20, 2019 09:00 AM

August 16, 2019

Programming Praxis

Last Man Standing

Today’s exercise is a fun task for a lazy summer Friday:

Given a circular array X of positive integers and a starting index k of the array, delete the element at k and jump X[k] steps in the circular array. Repeat until only a single element remains. Find the last remaining element.

For example, with array 6 2 3 1 4 7 5 and k = 3, the last man standing is 3, computed as shown below, with the item to be deleted at each step marked with brackets and the list rotated at each step to bring the new head of the list to the front:

6 2 3 [1] 4 7 5
4 [7] 5 6 2 3
5 6 [2] 3 4
3 4 [5] 6
6 3 [4]
[6] 3
3

Your task is to write a program to find the last remaining element. 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 August 16, 2019 09:00 AM

August 13, 2019

Programming Praxis

Round To 5

Every morning when I drive to work the highway signs display commute information: 7 minutes to Manchester Road, 11 minutes to Olive Blvd, speed ahead 55 mph. That’s little comfort when I’m sitting still on the highway. The “speed ahead” calculation is always rounded to the nearest 5 mph; the Department of Transportation takes a bunch of speed readings from sensors buried in the pavement and averages them.

Your task is to take a list of speed readings and average them to the nearest 5 mph. 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 August 13, 2019 09:09 AM

August 09, 2019

Programming Praxis

A Triangular Sequence

Consider the triangle:

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
...

When the triangle is flattened, it produces the sequence (1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 …).

Your task is to write a program to generate the flattened sequence, and a second program to calculate the nth item in the 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 August 09, 2019 09:00 AM

August 06, 2019

Programming Praxis

Program Cross-Referencing

I’ve been writing a lot of Awk code at work lately; Awk is an acceptable language where I work, Scheme is not. One of my Awk programs got big enough that I needed a cross-referencer, so I pulled out the one on the next page from my dusty archives. It’s thirty years old, and still works! I was amazed. Though I guess I’ll have to update the list of keywords, because Gawk, which we use where I work, has many more keywords than Awk did thirty years ago.

Your task is to write a cross-referencer for 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 August 06, 2019 09:00 AM

August 02, 2019

Programming Praxis

Friday Fun

I wish I thought of this:

I came up with a single pass O(n) sort algorithm I call StalinSort. You iterate down the list of elements checking if they’re in order. Any element which is out of order is eliminated. At the end you have a sorted list.

Your task is to implement StalinSort. 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 August 02, 2019 09:00 AM

July 30, 2019

Programming Praxis

CsvSplit

There was a question the other day on Reddit or Stack Overflow or someplace about handling CSV files with awk. We’ve done that in a previous exercise, but today I decided to handle CSV files in a different way. Specifically, I wrote an awk function csvsplit that works the same way as awk’s built-in split function except that it handles CSV strings instead of splitting on a regular expression:

n = csvsplit(str,arr)

Csvsplit takes a string and an array, deletes any current contents of the array, splits the string into fields using the normal CSV rules, stores the fields in arr[1] .. arr[n], and returns n. The splitting rules are: every comma splits a field, except that double-quotes around a field protect commas inside the field, and double-quotes may appear in a quoted field by doubling them (two successive double-quotes).

Your task is to write a csvsplit function for awk. 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 July 30, 2019 09:00 AM

July 28, 2019

Greg Hendershott

Future of Racket

Future of Racket

:: Racket

For most of the last decade I’ve made things in Racket — including making tools and tutorials to support other people making things in Racket.

At RacketCon 2019, Aaron Turon gave the keynote about the Rust community.

That afternoon, I had a talk about Racket Mode for Emacs.

The next morning?

Matthew Flatt gave his State of Racket talk. He said the community is growing well. Next, he proposed, let’s change the surface syntax away from lispy s-expressions, to something that will be a lower barrier of entry to new users.

He said it’s just a proposal. It would probably take a couple years. #lang racket programs would continue to work meanwhile and after the change. But eventually, in his proposal, the Racket culture should use this new syntax. (“Culture” meaning documentation, discussions, books, tutorials, tools.)

To be fair, he gave people a lot of time to share their initial reactions and answer their questions.

Also to be fair, if you have some mileage on your odometer, your pattern-recognition machinery will quickly assign high probabilities to various outcomes.

I’m concerned the change won’t help grow the community; instead hurt it. I’ve explained why in a few racket-users posts.1 I won’t here. I don’t think it matters. All you can say is, “Hey, that stove is hot, you might not want to touch it.”

I don’t regret contributing things and trying to help the community grow. I learned a lot! I had fun! On the other hand, if I’ll no longer learn or have fun? I’m not getting any younger. There are other things to do.

In the near future, I’m spending more time with other programming languages (currently Rust and Haskell). Possibly less time programming, at all. We’ll see.

Who cares? Why write this post?

  • To have a background explanation I can simply link to from things like README files, as needed from time to time.

  • Emotionally, I can’t quite bring myself to say, “So Long and Thanks for All the Standard-Fish!” That feels too abrupt. But it’s probably realistic about my current level of mental separation. So if there are a few people making plans, in part based on my own plans, I want to be up-front.

Finally, I sincerely wish all the best for the Racket core team and the community, which in my experience consists of amazing people with good intentions, open hearts, and sharp brains.

  1. Update 2019–08–10: Now that some people are linking to this blog post? Here are links to my racket-users posts: blah, blah, blah, blah, and blah. Also I updated this to “linkify” some other things and add Haskell to the list of languages I’m mostly focusing on now. 

by Greg Hendershott at July 28, 2019 12:00 AM

July 26, 2019

Programming Praxis

Twin Primes

According to number theory:

m is the base of a twin-prime pair (m, m+2) if and only if 4((m−1)! + 1) == –m (mod m (m+2)).

Your task is to write a program that implements the criterion given above, then calculate the twin primes less than a thousand. 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 July 26, 2019 09:00 AM

Göran Weinholt

Announcing Akku.scm 1.0.0

I am happy to announce the general availability of Akku.scm 1.0.0, a language package manager for R6RS and R7RS Scheme. It can be downloaded from GitLab and GitHub.

Akku is a package manager with features specially designed for Scheme. The library systems of R6RS and R7RS, where libraries are fully self describing, make it possible to automatically analyze source code to find libraries and imports.

asciicast

Akku installs libraries to a per-project library directory that works across all supported Scheme implementations. On top of this there is a traditional package index and a dependency solver. Packages are manually vetted before they are published in the index.

To increase the portability of R7RS code, Akku also performs an automatic conversion from the R7RS define-library form to the R6RS library form.

Akku supports Chez Scheme, Chibi Scheme, GNU Guile, Gauche Scheme, Ikarus Scheme, IronScheme, Larceny Scheme, Loko Scheme, Mosh Scheme, Racket (plt-r6rs), Sagittarius Scheme, Vicare Scheme and Ypsilon Scheme. It has been tested on Cygwin, FreeBSD, GNU/Linux, MSYS2, OpenBSD and macOS.

Akku has been in development for 21 months.

Further reading

July 26, 2019 12:00 AM

July 23, 2019

Programming Praxis

Homework

Today’s exercise comes from somebody’s homework assignment:

Write a program that fills a 50-element array with random numbers from 1 to 10. Print the array. Calculate and print the sum of the random numbers in the array. Calculate and print the number of times that a particular number appears in the array.

Your task is to complete the homework problem 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 July 23, 2019 09:00 AM

July 17, 2019

Ben Simon

Don't Fear the x, and other lessons from Shamir Secret Sharing

Consider these facts about this 3rd degree polynomial:

f(x) = 1822 + 3x + 19x2 + 2x3

Fact 1. This is considered a 3rd degree polynomial because the largest exponent value is 3. While looking at this equation gives me a burst of High School Math PTSD, it need not. Upon further reflection, it's just a bit of terse code. I could program the above as:

(define f (lambda (x)
            (+ 1822 
               (* 3 x)
               (* 19 (expt x 2))
               (* 2  (expt x 3)))))

Because all polynomials have the same shape, it's easy to make a function that generates polynomials:

(define (make-poly coeffs)
  (lambda (x)
    (let loop ((coeffs coeffs)
               (i 0)
               (sum 0))
      (cond ((null? coeffs) sum)
            (else
             (loop (cdr coeffs)
                   (+ i 1)
                   (+ sum (* (car coeffs) (^ x i)))))))))

With this 'make' function, I can replace the above code with the following:

(define f (make-poly '(1822 3 19 2)))

I can call f with as many values of x as I wish:

> (for-each (lambda (x) (show (cons x (f x)))) (range 0 10))
((0 . 1822))
((1 . 1846))
((2 . 1920))
((3 . 2056))
((4 . 2266))
((5 . 2562))
((6 . 2956))
((7 . 3460))
((8 . 4086))
((9 . 4846))
((10 . 5752))

Fact 2. Evaluating a polynomial at x = 0 always returns the value of the first constant term. We see this above, as 0 maps to 1822. This will continue to hold true no matter how ugly and complex the polynomial is.

Fact 3. Using Lagrange Interpolating polynomials we can use degree + 1 values of a polynomial to construct a function which will return values equivalent to the original polynomial. That is, if we feed any four values above into make-lagr-poly we end up with a new function fg which computes the same values as f.

(define fg (make-lagr-poly '((3 . 2056)
                            (6 . 2956)
                            (7 . 3460)
                            (10 . 5752))))

> (for-each (lambda (x) (show (cons x (fg x)))) (range 0 10))
((0 . 1822))
((1 . 1846))
((2 . 1920))
((3 . 2056))
((4 . 2266))
((5 . 2562))
((6 . 2956))
((7 . 3460))
((8 . 4086))
((9 . 4846))
((10 . 5752))

The how and why of Lagrange polynomials will have to wait for another blog post. But for now, trust me that this bit of math-magic works.

Cryptographer Adi Shamir combined the above facts to create something quite useful: a way to securely share a secret among a group.

Consider this problem:

You need to distribute a vault code to bank executives, however you'd like to avoid a number of pitfalls. For one, you want to make sure that a single lost or stolen code doesn't allow an attacker into the vault. You'd also like to insure that at least 4 executives need to agree on the requirement of opening the vault before it can be accessed. This reduces the chances that a small number of executives will coordinate to steal from the vault.

Shamir used the above math to create Shamir Secret Sharing. Here's how it works. First, note your secret, which in this case is the vault code. We'll use 12345 as our code. Then decide on your threshold, that is the number of executives that are required before the secret can be revealed. We'll use 4 as suggested above. Finally, decide on how many shares you want to give out. Let's assume there are 10 executives, so we'll generate 10 shares.

Step one is to form a polynomial of threshold - 1 degree, where the first term is the secret:

;; values 4, 19 and 103 are random numbers, and should be
;; generated in a secure and truly random way.
(define secret (make-poly '(12345 4 19 103))) 

Step two is to generate the 10 shares, one for each executive:

> (for-each (lambda (x) (show (cons x (secret x)))) (range 1 10))
((1 . 12471))
((2 . 13253))
((3 . 15309))
((4 . 19257))
((5 . 25715))
((6 . 35301))
((7 . 48633))
((8 . 66329))
((9 . 89007))
((10 . 117285))

Note how we start x at 1 and not 0. Calling this function with 0 reveals our secret.

We give each pair of numbers to an executive and instruct them to keep the pair private. If an attacker obtains less than 4 shares, then the secret remains safe and no clues about the it are revealed.

When the vault needs to be opened, 4 executives pool their shares to calculate a function equivalent to the original polynomial:

(define soln (make-lagr-poly '((1 . 12471)
                               (5 .  25715)
                               (9 . 89007)
                               (10 . 117285))))

Finally, to derive the secret we pass 0 to the solution function:

> (soln 0)
12345

While the above implementation captures the essence of Shamir Secret Sharing, it's missing an important step to make it truly secure. I may cover that in a future post.

I had two takeaways from my experience implementing Shamir Secret Sharing. First, it's fascinating to see how mathematical properties can be combined to solve everyday problems

And Second, I found the math behind this scheme to be initially quite overwhelming. I struggled to both understand the mathematical notation, as well as how to convert it to code. And then it hit me: I've got a programming language that let's me directly implement polynomial and Lagrange interpolations functions; I don't need to think of them as purely symbolic expressions like so many of the examples on the web do. Putting this in terms of code and not math made all the difference for me.

What a joy it was to untangle what initially appeared to be so complex.

Find my implementation of Shamir Secret Sharing here. Find the original paper by Adi Shamir here. Enjoy!

by Ben Simon (noreply@blogger.com) at July 17, 2019 08:45 PM

July 12, 2019

GNU Guix

Towards Guix for DevOps

Hey, there! I'm Jakob, a Google Summer of Code intern and new contributor to Guix. Since May, I've been working on a DevOps automation tool for the Guix System, which we've been calling guix deploy.

The idea for a Guix DevOps tool has been making rounds on the mailing lists for some time now. Years, in fact; Dave Thompson and Chris Webber put together a proof-of-concept for it way back in 2015. Thus, we've had plenty of time to gaze upon the existing tools for this sort of thing -- Ansible, NixOps -- and fantasize about a similar tool, albeit with the expressive power of Guile scheme and the wonderful system configuration facilities of Guix. And now, those fantasies are becoming a reality.

"DevOps" is a term that might be unfamiliar to a fair number of Guix users. I'll spare you the detour to Wikipedia and give a brief explanation of what guix deploy does.

Imagine that you've spent the afternoon playing around with Guile's (web) module, developing software for a web forum. Awesome! But a web forum with no users is pretty boring, so you decide to shell out a couple bucks for a virtual private server to run your web forum. You feel that Wildebeest admirers on the internet deserve a platform of their own for discussion, and decide to dedicate the forum to that.

As it turns out, C. gnou is a more popular topic than you ever would have imagined. Your web forum soon grows in size -- attracting hundreds of thousands of simultaneous users. Despite Guile's impressive performance characteristics, one lowly virtual machine is too feeble to support such a large population of Wildebeest fanatics. So you decide to use Apache as a load-balancer, and shell out a couple more bucks for a couple more virtual private servers. Now you've got a problem on your hands; you're the proud owner of five or so virtual machines, and you need to make sure they're all running the most recent version of either your web forum software or Apache.

This is where guix deploy comes into play. Just as you'd use an operating-system declaration to configure services and user accounts on a computer running the Guix System, you can now use that same operating-system declaration to remotely manage any number of machines. A "deployment" managing your Wildebeest fan site setup might look something like this:

...

;; Service for our hypothetical guile web forum application.
(define guile-forum-service-type
  (service-type (name 'guile-forum)
                (extensions
                 (list (service-extension shepherd-root-service-type
                                          guile-forum-shepherd-service)
                       (service-extension account-service-type
                                          (const %guile-forum-accounts))))
                (default-value (guile-forum-configuration))
                (description "A web forum written in GNU Guile.")))

...

(define %forum-server-count 4)

(define (forum-server n)
  (operating-system
    (host-name (format #f "forum-server-~a" n))
    ...
    (services
     (append (list (service guile-forum-service-type
                            (guile-forum-configuration
                             "GNU Fan Forum!")))
             %base-services))))

(define load-balancer-server
  (operating-system
    (host-name "load-balancer-server"
    ...
    (services
     (append (list (service httpd-service-type
                            (httpd-configuration
                             ...)))
             %base-services)))))

;; One machine running our load balancer.
(cons (machine
       (system load-balancer-server)
       (environment manged-host-environment-type)
       (configuration (machine-ssh-configuration
                       ...)))

      ;; And a couple running our forum software!
      (let loop ((n 1)
                 (servers '()))
        (if (> n %forum-server-count)
            servers
            (loop (1+ n)
                  (cons (machine
                         (system (forum-server n))
                         (environment manged-host-environment-type)
                         (configuration (machine-ssh-configuration
                                         ...)))
                        servers)))))

The take-away from that example is that there's a new machine type atop the good ol' operating-system type, specifying how the machine should be provisioned. The version of guix deploy that's currently on the master branch only supports managed-host-environment-type, which is used for machines that are already up and running the Guix System. Provisioning, in that sense, only really involves opening an SSH connection to the host. But I'm sure you can imagine a linode-environment-type which automatically sets up a virtual private server through Linode, or a libvirt-environment-type that spins up a virtual machine for running your services. Those types are what I'll be working on in the coming months, in addition to cleaning up the code that's there now.

And yes, you did read that right. guix deploy is on the Guix master branch right now! In fact, we've already done a successful deployment right here on ci.guix.gnu.org. So, if this sounds as though it'd be up your alley, run guix pull, crack open the manual, and let us know how it goes!

About GNU Guix

GNU Guix is a transactional package manager and an advanced distribution of the GNU system that respects user freedom. Guix can be used on top of any system running the kernel Linux, or it can be used as a standalone operating system distribution for i686, x86_64, ARMv7, and AArch64 machines.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. When used as a standalone GNU/Linux distribution, Guix offers a declarative, stateless approach to operating system configuration management. Guix is highly customizable and hackable through Guile programming interfaces and extensions to the Scheme language.

by Jakob L. Kreuze at July 12, 2019 07:00 PM

Programming Praxis

Interactive Diff

[ There will be no exercises next week, as my daughter is visiting from out-of-town and I will be spending time with her. ]

One of my favorite books is The Unix Programming Environment by Brian Kernighan and Rob Pike, which I have recently been re-reading; the spine of my copy broke long ago, so I must be careful turning the pages, and I wrap the book in a rubber band every time I put it back on my shelf. It is an excellent introduction to Unix, still relevant today even though it was published in 1984. The recent exercise Remind was inspired by a program in Section 4.4, and today’s exercise is a rewrite of the program in Section 6.8.

NAME

    idiff -- interactive diff

USAGE

    idiff file1 file2 -- interactively merge file differences

DESCRIPTION

    idiff takes two files file1 and file2, diffs them, and presents
    the difference to the user interactively. At each difference,
    the user may accept the text from file1 by responding <, or     accept the text from file2 by responding >, or edit the difference
    by responding e (in which case whatever the user saves from the
    editor is entered into the output file), or execute a command
    by typing !cmd, in which case the user must then respond when
    the prompt is repeated. The assembled output with the selected
    differences is placed in file idiff.out.

EXAMPLE

    $ cat file1
    This is
    a test
    of
    your
    skill
    and comprehension.
    $ cat file2
    This is
    not a test
    of
    our
    ability.
    $ diff file1 file2
    2c2
    < a test     ---     > not a test
    4,6d4,5
    < your
    < skill
    < and comprehension.     ---     > our
    > ability.
    $ idiff file1 file2
    2c2
    < a test     ---     > not a test
    ? >
    4,6c4,5
    < your
    < skill
    < and comprehension.     ---     > our
    > ability.
    ? <
    $ cat idiff.out
    This is
    not a test
    of
    your
    skill
    and comprehension.

[ WordPress is determined not to render less-than and greater-than signs properly. Look at https://ideone.com/nI9CNB if you can’t make sense of what you see. ]

Your task is to write idiff. 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 July 12, 2019 09:00 AM