Planet Scheme

July 07, 2015

Programming Praxis

Powerset

Sets are ubiquitous in programming; we have discussed sets in several previous exercises. One of the operations that can be performed on a set is to compute its powerset, which is a set of all the subsets of the original set. For instance, the powerset of (1 2 3) is the set (() (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3)) where neither the order of the subsets nor the order of the elements of the individual subsets matters.

Your task is to write a program that computes the powerset of a set. 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 07, 2015 09:00 AM

July 05, 2015

Grant Rettke

A Scheme Interpreter in Forth

This is an interpreter for a really simple dynamically scoped Scheme dialect. It only runs with Gforth, because it uses Gforth’s structs to implement its data structures.

by Grant at July 05, 2015 05:18 PM

Mastery, Questions, Hardware, Software, LISP, Forth, TI-99/4A

Over the last two years a few questions and ideas have visited me and the following is my attempt to piece them together…

This claim by Alan Kay has haunted me for the past seven months. So have these two works by Charles Moore. They make me wonder:

  • Can you be a master software craftsman without having completely mastered your
    tools?

    • Is this a natural part of the evolution of a programmer?
  • What are the surprisingly intuitive and non-obvious intersections between
    the Theory of Computation, Number Theory, and a CPU that help on that path to mastery of software development?

    • Does every mathematician require an intuitive sense of the value of the
      transistor?

It is time to start studying closer the bare metal. What is the best place to start? What are my requirements? There are only two requirements. First, I want to go through the process of learning and exploration interactively and quickly. Those are the traits of a LISP system. Second, I want it to be super inexpensive. Everyone with a television set and a keyboard should be able to follow the same approach. They shouldn’t even require the Internet. If they have Internet at work or school then they can use the Sneakernet. It should be trivial to sell this system for next to nothing. The computer will have video and sound too. It even has a beautiful HD screen. That is it. With that in mind I started looking.

The relationship between the programming language and hardware is tightly woven. Most of us don’t consider this today because we own machines that spend 99% of their time idle. Looking at languages and inexpensive hardware is a real treat because you start caring real quick! Quickly, too, I ended up on Armpit Scheme.

Every LISP programmer implements their own LISP! Or so the say, I never did. I still want to. This seems like the perfect project: C language, bare metal, and LISP, on some serious hardware. Doing some light reading about LISP on small devices, my imagination took over and quickly concluded that the next logical step was to rebuild a Lisp Machine from scratch! No, that is a little too far out of scope. Armpit seems like a fine place to start so I read about the development boards where it runs. Then the two things slowly effected this vector.

One of my best friends Bruce had loved to share with me his delight in programming FORTH. Scheme was my enlightenment tool, and his was FORTH. We would spend hours talking about both of them. Our conversations went something like this: “Me: In Scheme I explored X, and it was fun!” and then “Bruce: I explored that very idea in FORTH and this is how I did it and it was fun!”. FORTH was built to run on small CPUs. That got me learning more about FORTH.

There are a lot of distributions. There are great books about it. The community is passionate. One of the rights of passage is to write your own FORTH. It runs on a lot of CPUs. That was enough to convince me. Around the same time, something else was on my mind: Vintage Computers.

As a kid we had an Apple 2e. It was a delightful machine. Perhaps that is the right place to start? Watching craigslist and estate sales, there weren’t very many. The market is demanding them again, and on ebay they are making some money. Still, it has all the right traits now: simple, keyboard, video and sound and disk, and constrained. It ought to be inexpensive, but isn’t right now. That is OK. Months go by and I keep poking around at things. Two things jump out as possible options.

The TI Launchpad is a $9.99USD computer. It is 16-bit, has memory, and it is fast. It runs at least CamelForth, 4E4th, eForth, and 430eForth. Pay attention to the names involved. The community is small and tight knit. Implementing FORTH seems like a great way to learn/master Assembly, C, hardware, and FORTH. The source code and hardware are out there. I will go with 430eForth and the LaunchPad machine. Around the same time while learning more about FORTH I ended up back on a vintage machine option for FORTH.

The old personal computers all either included or had available, FORTH. Most of them are available free in source form today. It could be fun to use and learn on a vintage box because that is all bare metal. Low and behold, I end up watching this video to learn about TurboForth.

TurboForth is a 2015 FORTH implementation for the TI-99/4A. Perfect. Perfect! Using a real PC, you get the fun of exploring a machine with video memory and making sounds. That is just included because it is a personal computer. TurboForth lets you explore the hardware, the machine, and even the implementation itself. That is just wonderful. There is another cool part: the TI-99/4A has a very active community.

They’ve got an active user group right down in Chicago. They’ve got a conference this October! There is hardware and software to connect your box to USB storage or a hard drive. There are loads of youtube videos about it. It helps that the machine is still available at a very reasonable price. To top it off, there are first class emulators out there. People are still writing games for this machine today, in FORTH nonetheless. There are lot of good games for it, too.

The TI-99/4A and the TI Launchpad seem like fine places to start. They meet all of the requirements. Without having dug into the details, the above are assumptions, and that is a fine place to start.

by Grant at July 05, 2015 04:17 PM

July 04, 2015

Greg Hendershott

Keyword structs, revisited

This revises my Keyword structs post to fix some mistakes, discuss the struct* match pattern, and rewrite the macro to use syntax-parse and support default arguments.


A good rule of thumb in Racket is to use a struct instead of list when you’re juggling more than two or three items.

For ad-hoc prototyping, you can use a list:

1
2
3
4
5
6
7
8
;; Return first name, last name, and age
(define (get-person)
  (list "John" "Doe" 32))

(define p (get-person))
(first p)  ; => "John"
(second p) ; => "Doe"
(third p)  ; => 32

Getting the stuff out is a bit cleaner using match, which lets you “destructure” the list and bind to identifiers in one swell foop:

1
2
3
4
5
6
(match (get-person)
  [(list first last age)
   (values first last age)])
; "John"
; "Doe"
; 32

But what if you need to add or delete list members later? It’s error-prone.

That’s where a real struct can help:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
(struct person (first last age))
(define (get-person)
  (person "John" "Doe" 32))

(define p (get-person))
(person-first p)
; "John"
(person-last p)
; "Doe"
(person-age p)
; 32

;; Or using `match`:
(match (get-person)
  [(person first last age)
   (values first last age)])
; "John"
; "Doe"
; 32

Now let’s say you add a social security number field, ssn:

1
2
3
(struct person (first last ssn age))
(define (get-person)
  (person "John" "Doe" "xxx-xx-xxxx" 32))

Everything still works fine when you access the fields by-name:

1
2
3
4
5
6
7
(define p (get-person))
(person-first p)
; "John"
(person-last p)
; "Doe"
(person-age p)
; 32

Although if you used match, which is by-position, that needs to be updated:

1
2
3
4
5
6
(match (get-person)
  [(person first last age)
   (values first last age)])
; match: wrong number for fields for structure person: expected 4 but got 3
;  at: (first last age)
;  in: (person first last age)

So you need to fix it:

1
2
3
4
5
6
7
(match (get-person)
  [(person first last ssn age)
   (values first last ssn age)])
; "John"
; "Doe"
; "xxx-xx-xxxx"
; 32

struct*

This is where the struct* match pattern can help. By getting the fields by-name, it is insulated from the addition of new fields:

1
2
3
4
5
6
(match (get-person)
  [(struct* person ([first first] [last last] [age age]))
   (values first last age)])
; "John"
; "Doe"
; 32

This needs to be updated only if/when you need the new ssn field. So although it’s more verbose, using struct* is more resilient.

We could reduce the verbosity, by allowing either [field pat] or just field — where the latter expands to use the same symbol for both the field and pattern, as we wrote out in the example above. This would be a nice enhancement to the official struct* in racket/match. Meanwhile here’s a struct** match expander that wraps struct* to do so:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#lang racket/base

(require racket/match
         (for-syntax racket/base
                     syntax/parse))

(define-match-expander struct**
  (λ (stx)
    (define-syntax-class field
      (pattern [id:id pat:expr])
      (pattern id:id #:with pat #'id))
    (syntax-parse stx
      [(_ struct-id:id (field:field ...))
       #'(struct* struct-id ([field.id field.pat] ...))])))

(module+ test
  (require rackunit)
  (struct foo (a b c))
  (define x (foo 1 2 3))
  (check-equal? (match x [(struct** foo (a b [c x])) (list a b x)])
                x)
  (check-equal? (match x [(struct*  foo ([a a][b b][c c])) (list a b c)])
                (match x [(struct** foo (a    b    [c c])) (list a b c)])))

Making structs

Creating an instance of a struct has exactly the same form/shape as creating a list:

1
2
(list   "John" "Doe" 32)
(person "John" "Doe" 32)

It’s just person instead of list. Either way, you’re specifying the fields by-position, not by-name. If you have a struct with more than a few fields:

1
(struct foo (a b c d e f g h))

Then creating the struct is itself error-prone. You will probably start jotting down comments to help you keep track of what field you’re on:

1
2
3
4
5
6
7
8
(foo 10     ;a
     "foo"  ;b
     13     ;c
     "bar"  ;d
     "baz"  ;e
     #f     ;f
     "x"    ;g
     42)    ;h

It would help if we could turn those comments into actual keywords. Using keyword arguments is helpful for any function with more than a few arguments. We’d like to write:

1
2
3
4
5
6
7
8
(foo #:a 10
     #:b "foo"
     #:c 13
     #:d "bar"
     #:e "baz"
     #:f #f
     #:g "x"
     #:h 42)

That way, Racket could help us catch mistakes. Even better, we’re free to supply the arguments in a different order, and it’s OK. It’s by-name, not by-position.

As a bonus, it would be great to have optional arguments, with a default value. (Especially since structs #:auto option requires all fields to share the same default value.)

Certainly we could define a foo/keyword function like this, which calls the plain foo struct constructor. I’ve done this many times. Admittedly, if you change the foo struct, you have to change this function, too. But usually they’re adjacent in the source code, and anyway it’s only the one place to make the mistake.

Even so, it would be neat if Racket had an option to create such keyword argument constructors for structs automatically.

A macro

Well, this is Racket. Any sentence that starts with, “It would be neat if Racket could ___”, can be answered with, “And I can add that to Racket myself!”

Here’s what we’d be writing by hand:

1
2
3
4
(struct foo (a b c ...))

(define (foo/kw #:a a #:b b #:c [c 42] ...)
  (foo a b c ...))

We’re defining a function whose name is the struct name with "/kw" appended. For each struct field, we want a keyword argument, where the keyword is similar to the field name. Also, we’d like to support optional arguments.

So here’s a macro:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#lang racket/base

(require (for-syntax racket/base
                     racket/list
                     racket/syntax
                     syntax/parse))

(begin-for-syntax
 (define syntax->keyword (compose1 string->keyword symbol->string syntax->datum)))

(define-syntax (struct/kw stx)
  (define-syntax-class field
    (pattern id:id
             #:with ctor-arg #`(#,(syntax->keyword #'id) id))
    (pattern [id:id default:expr]
             #:with ctor-arg #`(#,(syntax->keyword #'id) [id default])))
  (syntax-parse stx
    [(_ struct-id:id (field:field ...) opt ...)
     (with-syntax ([ctor-id (format-id #'struct-id "~a/kw" #'struct-id)]
                   [((ctor-arg ...) ...) #'(field.ctor-arg ...)]) ;i.e. append*
       #'(begin
           (struct struct-id (field.id ...) opt ...)
           (define (ctor-id ctor-arg ... ...) ;i.e. append*
             (struct-id field.id ...))))]))

;;; Example usage:

;; Define a struct type
(struct/kw foo (a b [c 42]) #:transparent)

;; Use normal ctor
(foo 1 2 3)                ; => (foo 1 2 3)

;; Use keyword ctor
(foo/kw #:a 1 #:b 2 #:c 3) ; => (foo 1 2 3)

;; Use keyword ctor, taking advantage of default arg for #:c field
(foo/kw #:a 1 #:b 2)       ; => (foo 1 2 42)

Lines 2–6 require some modules that aren’t part of the racket/base environment that macros run in.

Lines 8–9 define a helper function that can be used by a macro. To do that, the function must be define in a begin-for-syntax form.

Line 11 onward is the macro definition.

Lines 12–16 define a syntax class to use with syntax-parse. The class matches struct fields, which can be either an identifier alone or an [identifier default-value] form. In both cases, the syntax class defines an extra bit of syntax, ctor-arg. For each field, this is the arg spec to use in the definition of our special constructor function. This will be something like #:id id in the first case or #:id [id default] in the second case.

Lines 17–24 are the syntax-parse form. The pattern is:

1
    [(_ struct-id:id (field:field ...) opt ...)

This means there will be an identifier for the struct, followed by a list of zero or more fields, and finally zero or more options.

Lines 19–20 use with-syntax to create a couple pattern variables:

1
2
     (with-syntax ([ctor-id (format-id #'struct-id "~a/kw" #'struct-id)]
                   [((ctor-arg ...) ...) #'(field.ctor-arg ...)]) ;i.e. append*

The first, ctor-id, is simply the name of our constructor function — append /kw to the user’s struct identifier.

The second, ctor-arg, is our list of arg specs for the constructor function. We’ll need to append* these — “flatten” them one level, from a list of lists into a list. That’s the reason for the funny nested ellipses: ((ctor-arg ...) ...) — it sets us up to say ctor-arg ... ... down on line 23.

Finally lines 21–24 are the template — the syntax we’re returning. This is simply a struct definition plus the definition of our special constructor function. Again, the business with the double ellipses is how we append* a list of lists like this:

1
'((#:a a) (#:b b) (#:c [c 42]))

down to:

1
'(#:a a #:b b #:c [c 42])

Which is the argument list we want for our constructor.

And that’s it. Although this macro doesn’t exhaustively cover all possible struct options, it’s an example of something you could use in a project to write code that is less repetitive and more resilient.

by Greg Hendershott at July 04, 2015 05:15 PM

July 03, 2015

Programming Praxis

Assign Y

I’m sorry I missed Tuesday’s exercise; I’ve been very busy at work. Today’s exercise is an interview question of the kind I don’t like: it’s tricky, you either know the answer or you don’t, and it’s unlikely to be useful in any real programming situation:

You are give four integers x (which must be either 0 or 1), y, a and b. Your first task is to assign a to y if x = 0, or assign b to y if x = 1, without using any conditional operator, including the ternary operator. Your second task is to perform the same assignment without using any arithmetic operators.

Your task is to complete the two-part puzzle given 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 03, 2015 09:00 AM

July 01, 2015

GNU Guix

Reproducible and User-Controlled Software Environments in HPC with Guix

Our paper entitled Reproducible and User-Controlled Software Environments in HPC with Guix was accepted for RepPar, a workshop on reproducibility in parallel computing:

Support teams of high-performance computing (HPC) systems often find themselves between a rock and a hard place: on one hand, they understandably administrate these large systems in a conservative way, but on the other hand, they try to satisfy their users by deploying up-to-date tool chains as well as libraries and scientific software. HPC system users often have no guarantee that they will be able to reproduce results at a later point in time, even on the same system—software may have been upgraded, removed, or recompiled under their feet, and they have little hope of being able to reproduce the same software environment elsewhere. We present GNU Guix and the functional package management paradigm and show how it can improve reproducibility and sharing among researchers with representative use cases.

The paper can be thought of as a followup to the recent experience report by Ricardo Wurmus.

We believe package management and reproducibility are key topics for HPC research. We are glad to have this opportunity to discuss the subject with researchers of the field.

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 July 01, 2015 10:05 AM

June 26, 2015

Programming Praxis

Find The Missing Number

Today’s exercise is a tricky little homework problem:

Given a string consisting only of digits, find the missing number. For instance, given the string 596597598600601602 the missing number is 599. You may assume all the numbers are positive integers and the sequence increases by one at each number except the missing number. The numbers will have no more than five digits and the string will have no more than two hundred characters.

Your task is to write a program to find the missing number. 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 June 26, 2015 09:00 AM

June 23, 2015

Programming Praxis

Closest Two-Sum To Zero

Given a random array of integers, both positive and negative, find the pair with sum closest to zero. For instance, in the array [45, -29, -96, -7, -17, 72, -60], the two integers with sum closest to zero are -60 and 72.

Your task is to write a program that finds the two-sum closest to zero. 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 June 23, 2015 09:00 AM

June 20, 2015

The Racket Blog

Racket v6.2

Racket version 6.2 is now available from http://racket-lang.org/

With this release we are taking a major step forward to get our user community even more involved than in the past. Over the past six months, we have re-organized the Racket code base into a small core code repo and many other package repos, all found on GitHub. If you have time and if you wish to get involved, please take a look at the GitHub repos and find your favorite places to learn, fix, and enhance our world.

The core repo is at https://github.com/plt/racket, and the package repos are listed at https://github.com/racket/.

core repo
  • The package manager supports a direct references to Git repositories via "git://[...]", "http://[...].git", and "https://[...].git" URLs. (Previously, only references to GitHub were supported.)
  • A --clone option for raco pkg install or raco pkg update facilitates Git-based package development. If a package X has a Git repository source, installing and updating the package pulls from the repository in a read-only mode. Using raco pkg update --clone X switches the local installation to a repository checkout that is suitable for modifying the package implementation, issuing pull requests, pushing changes, and so on.
    Using raco pkg update --lookup X switches the package back to the default installation mode.
drracket
  • Its on-line check syntax works with graphical content.
  • Increased availability of DrRacket's blueboxes, including method and constructor information.
  • The "Open Require Path" menu item supports ".." in relative pathnames.
data
  • Added data/enumerate, a library that supports efficient enumeration of data structures
redex
  • Its redex-check facility uses data (in addition to random) enumeration to try to find counter-examples.
  • Its generate-term function accepts additional arguments to return the "i"-th member of a pattern using data/enumerate (meaning it efficiently supports very large values of "i").
  • The examples collection includes Launchbury's 1993 big-step lazy semantics.
htdp
  • 2htdp/image's polygon may be built out of bezier curves instead of just straight lines (see the docs for pulled-point).
  • 2htdp/abstraction is a teachpack for instructors and students who wish to use for/* loops, match, define-type and type-cases in ISL and ISL+.
  • 2htdp/universe programs can be exported using DrRacket's executable creation mechanism and they behave properly when run independently.
typed-racket
  • Typed Racket in DrRacket displays tooltips that show the types of expressions. Tooltips are also displayed for type errors.
  • Typed Racket loads generated contracts only when needed. This reduces memory use and startup time for Typed Racket programs.
  • Typed Racket has improved support for prefab structures, future semaphores, and async channels.
  • Typed Racket understands when two different variables refer to the same thing, and updates types accordingly. This particularly improves the type checking of macros such as match.

Feedback Welcome

by Ryan Culpepper (noreply@blogger.com) at June 20, 2015 03:14 AM

June 19, 2015

Programming Praxis

Nines And Zeros

We have today an interview question that so stumped an interviewee that he asked for help on the internet:

Given an integer n, find the smallest number consisting only of the digits zero and nine that is divisible by n. For instance, given n = 23, the smallest number consisting only of the digits zero and nine that is divisible by 23 is 990909.

Your task is to write a program that finds the number 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 June 19, 2015 09:00 AM

June 16, 2015

Programming Praxis

Karate Chop

Dave Thomas has a Code Kata in which he challenges programmers to write five different implementations of binary search (also known as the “binary chop” or, in Thomas’ kata-lingo, the “karate chop”). He doesn’t define “different” except to use phrases such as “totally different technique” and “totally unique implementations” and to suggest the traditional iterative approach, a recursive approach, a functional style passing array slices around, and so on.

Your task is to write five different implementations of binary search, returning the index of a target value in a sorted array of integers, or -1 if the target is not present. 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 June 16, 2015 09:00 AM

June 13, 2015

Alaric Snell-Pym

Ugarit 2.0 released

Unless I messed up the release process, Ugarit version 2.0 is now available from the Chicken Scheme egg repository. What does this mean to you, dear reader? Not a huge amount; you can go and read the release notes at the bottom of the Ugarit documentation page for the fine detail. But, to summarise: The […]

by alaric at June 13, 2015 07:25 PM

June 12, 2015

Programming Praxis

Random Total

Our task today is to generate a set of k random positive integers that add up to a given totaln. For instance, if we want 4 random numbers that add up to 9, there are six possible results (not counting permutations of them): {6,1,1,1}, {5,2,1,1}, {4,3,1,1}, {4,2,2,1}, {3,3,2,1} and {3,2,2,2}.

An easy way to do that is to choose k−1 random numbers r with 0 ≤ r < nk, sort them, calculate the differences between them, calculate the difference between 0 and the smallest, calculate the difference between nk and the largest, shuffle the differences, and add 1 to each; subtracting k and adding 1 ensures that all the numbers are positive. For our example above, choose three random non-negative integers less than nk = 5, say 1, 3, and 3, the differences are 1, 2, 0 and 2, and the four resulting numbers are 2, 3, 1 and 3, which form the fifth of the six sets shown above.

Your task is to write the program that generates a random set of integers that adds to a given total, 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 June 12, 2015 09:00 AM

June 09, 2015

Programming Praxis

Leonardo Numbers

The Leonardo numbers A001595 are defined as L0 = 1, L1 = 1, Ln = Ln−2 + Ln−1 + 1; Dijkstra discusses Leonardo numbers in EWD797, and uses them in the analysis of smoothsort. Leonardo numbers are similar to Fibonacci numbers, and are related by the formula Ln = 2 Fn+1 − 1.

Your task is to write a function that computes Leonardo 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 June 09, 2015 09:00 AM

June 05, 2015

Programming Praxis

Most Living People

We have today an exercise inspired by those “programming challenge” websites where you upload code and an automated judge tells if you pass or fail and how your time compares to other programmers. I haven’t seen this particular problem at one of those sites, but it feels like something they would do; this would also make a good interview question:

You are given a list of people’s lifespans with birth and death years; for instance, a person lived from 1924 to 1991. Some people have only a birth year because they are still living. You are to find the year in which the most people of a set of people were alive.

Input: A number n on a line by itself indicating the number of input cases, followed by n sets of lines containing a number m indicatingthe number of people in this particular input case, followed by m lines indicating birth and, possibly, death years.

Output: For each input case, the year (or years) in which the most people were alive.

Example: For the input:

2
3
1910 1948
1948 2011
1927 1995
3
1910 1948
1927 1995
1945

You should produce the following output:

1948
1945 1946 1947 1948

Your task is to write the indicated 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 June 05, 2015 09:00 AM