'(scheme . info)

Some unix systems provide a system call getopt that provides a convenient interface for programs that parse their command-line arguments in a conventional manner. getopt usually takes three arguments: a string that describes the allowable arguments, an error message to be provided to the user in the event of an invalid argument, and the list of command-line arguments (or a vector and count). The option string gives all possible options; any that take an argument are followed by a colon. For instance, for the Unix V7 diff command, the option string is "befhnmD:". The parser recognizes options with a leading dash, stops at the first argument that doesn't start with a dash or with the "--" argument, and allows options without required arguments to be combined in a single option string; for instance, the command diff -eh -D string file1 file2 finds three options, e, h and D, including the string argument to the D option. The getopt function returns a list of option/argument pairs, with null argument for options that don't take an argument, and a list of the remaining non-option arguements.

Your task is to write the getopt 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.

Apple’s iOS SDK license agreement terms have always been source of disputes, discussions and many blog posts. Many accuse Apple of being too draconian and elitist, while being ineffective at barring bad applications from entering the store. The uproar just got fueled when Apple released the 4.0 version of the SDK with a new license agreement, changing

3.3.1 — Applications may only use Documented APIs in the manner prescribed by Apple and must not use or call any private APIs.

to

3.3.1 — Applications may only use Documented APIs in the manner prescribed by Apple and must not use or call any private APIs. Applications must be originally written in Objective-C, C, C++, or JavaScript as executed by the iPhone OS WebKit engine, and only code written in C, C++, and Objective-C may compile and directly link against the Documented APIs (e.g., Applications that link to Documented APIs through an intermediary translation or compatibility layer or tool are prohibited).

The intended effect is obviously to ban third-party abstraction layers, like then soon-to-be-released Adobe’s Flash for iPhone. But the wording is very broad and cover too many uses of other programming languages and technologies. Steve Jobs demoed himself the Tap Tap Revenge game for iPhone, which reportedly uses Lua. The backslash was too big to ignore, making Apple revise the agreement again. This time section 3.3.2 was changed from

3.3.2 – No interpreted code may be downloaded or used in an Application except for code that is interpreted and run by Apple’s Documented APIs and built-in interpreter(s).

to

3.3.2 – Unless otherwise approved by Apple in writing, no interpreted code may be downloaded or used in an Application except for code that is interpreted and run by Apple’s Documented APIs and built-in interpreter(s). Notwithstanding the foregoing, with Apple’s prior written consent, an Application may use embedded interpreted code in a limited way if such use is solely for providing minor features or functionality that are consistent with the intended and advertised purpose of the Application.

Although still requiring Apple’s prior written approval, it leaves the door open for the use of other programming languages on iOS devices. Apple Outsider believes this is all about Lua, and he may be right. But of course Lua is not the only game in town.

I always thought my use of Scheme in Reverso was ok with the previous version of the license agreement. No code is ever downloaded, and not interpreted either; Gambit-C compiles Scheme code to C which is compiled with Apple’s official tools to create a native library. But this changed with the new 3.3.1 section because my code was not originally written in one of the approved languages. James Long, who first compiled Gambit-C for the iPhone, claimed that Scheme was dead on the iPhone. But then Apple relented and changed section 3.3.2. What about now?

I believe that makes Scheme usable again, if used just like in Reverso: as a library. The application is written in Objective-C, but uses Scheme code (compiled to C) to only add features “that are consistent with the intended and advertised purpose of the Application”. Albeit it can be claimed that the code is not interpreted, this use follows the spirit of the law, even if it does not follow its letter.

Here is a photo of the 2005 Kawasaki Concours that I bought last week:

I can’t wait to get her cleaned up, my riding gear sorted out, and out on the road again.

Not having ridden for 12 years or so, I thought it would be good to get back in the saddle again with some off-street street-time and re-learning of good safety habits already under my belt. Luckily for me a slot opened up in Motorcycling Enterprises’ Safe Rider Course. It was a lot of fun.

The teachers provided excellent in-classroom and on-the-track training; balancing good exercises with 1-on-1 attention that made a big difference in how quickly you acquired the skill(s).

Unfortunately for others I’m sad to see that they are retiring this year. While there are plenty of MSF certified classes out there, I’m still hoping that their trainers decide to take over their business.

In relational databases, the natural join of two tables is an operator that takes two tables as input and returns a new table that combines the two input tables on their common keys. If the input tables are sorted, the join simply scans the two tables, writing records for the cross-product of all records with equal keys. For instance, the join of the two tables

Key  Field1  Field2               Key  Field3
 A      w       p                  A      1
 B      x       q        and       A      2
 B      y       r                  B      3
 C      z       s

is the table

Key  Field1  Field2  Field3
 A      w       p       1
 A      w       p       2
 B      x       q       3
 B      y       r       3

We represent a table as a file; each line is a record, and fields are separated by tabs. For simplicity, we’ll assume that the first field in each record is the key.

Your task is to write a program that takes two input files representing tables (you may assume they are sorted) and produces their natural join as output. 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.

Since I'm pretty new to C++, I wasn't too deeply familiar with RAII; like most Schemers I just thought of it as "C++'s version of dynamic-wind."

This week I learned an important distinction between C++ destructors and Java's finally. The latter, of course, unilaterally executes when the body terminates, regardless of how or when it terminates. The thing that gives destructors more expressiveness for dealing with cleanup is that they only execute for the objects that have been initialized. This means that if control exits a block after only half of the stack-local objects have been constructed, only those half of the objects have their destructors invoked. With finally, all that bookkeeping is the responsibility of the programmer.

(That said, I still see RAII used all over the place to construct awkward, special-purpose classes whose sole purpose is to run some cleanup code. In these cases, having to create a named object and a named class to go along with it is pretty perverse.)

Steve suggested: For this to work like you want, Java style, you'd have to add a Class member to the Box class, to represent the type of Box at runtime.

Like this:

public final class Box<E> {

  private final Class<E> type;
  private final E value;

  public Box (Class<E> type, E value) {
    this.type = checkNotNull(type, "type");
    this.value = value;
  }

  public E getValue() {
    return value;
  }

  public boolean isType (Class<?> specific) {
    return specific == this.type;
  }

  @SuppressWarnings("unchecked")
  public <X> Box<X> asType (Class<X> specific) {
    if (isType(specific)) {
      return (Box) this;
    } else {
      throw new ClassCastException();
    }
  }
}

You could then write a static generic filter taking an Iterable of generic Boxes and a Class object to filter by, and returning an Iterable of the correct type fairly simply.

Sort of like this (assuming appropriate definitions of map and filter):

// The essential code is in a bold green face.

public <X> Iterable<Box<X>> boxesOfType (final Class<X> type,
                                         Iterable<Box<?>> boxes) {
  return
      map (
          filter (
              boxes,
              new Predicate<Box<?>> () {
                @Override
                public boolean apply (Box<?> box) {
                  return box.isType(type);
                }
              }),
          new Function<Box<?>, Box<X>> () {
            @Override
            public Box<X> apply (Box<?> box) {
              return box.asType(type);
            }
          });
}

Dunno if that floats your boat, tho.

It definitely floats my boat (thanks, Steve) in that I can now, in a typesafe manner, take a bunch of heterogeneous boxes and select and downcast them to a subset of homogeneous boxes.

I'll discuss the leaks in the boat in the next post.
Addendum

mquander offered a C# solution to the same problem:

internal interface IBox { }
 
public class Box<T> : IBox
{
    public T Value;
}
 
public static class BoxManipulators
{
    public static int MinimumIntegerInBox(IEnumerable<IBox> boxes)
    {
        return boxes.OfType<Box<int>>().Min(x => x.Value);
    }
}

We present today a classic exercise that has been on my to-do list since the start of Programming Praxis.

The n-queens problem is to find all possible ways to place n queens on an n × n chess board in such a way that no two queens share a row, column, or diagonal. The diagram at right shows one way that can be done on a standard 8 × 8 chess board.

Your task is to write a program to find all such placements. 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.

Check it out; can’t read it myself.

(via gauche)

Blogger really munged Mike's code, so here is the relevant part correctly formatted:

public static int minimumIntegerInBox(Collection<Box<?>> boxes) {
  Iterable<Box<?>> intBoxes = filter(boxes,
      new Function<Box<?>, Boolean>() {
        @Override
        public Boolean of(Box<?> domainItem) {
          return domainItem.get() instanceof Integer;
        }
      });
  Iterable<Integer> ints = map(
      intBoxes,
      new Function<Box<?>, Integer>() {
        @Override
        public Integer of(Box<?> domainItem) {
          return Integer.class.cast(domainItem.get());
        }
      });
  return minimumElement(ints);
}

public static int minimumElement(Iterable<Integer> items) {
  return best(
      new Function<Pair<Integer, Integer>, Boolean>() {
        @Override
        public Boolean of(Pair<Integer, Integer> domainItem) {
          return domainItem.second() < domainItem.first();
        }
      },
      items);
}

This is similar to what I started with, but I didn't like this solution for two reasons.

1. The test for whether the Box<?> is a Box<Integer> relies on extracting the contents of the Box and testing to see if it is an integer. In other words, rather than relying on the type of the container, we explicitly look at the contents of the container. This is an important distinction, but it might be hard to see it in this context. Just because the box happens to contain an integer at this point doesn't mean that it is a Box<Integer>. It could be a Box<Number> or a Box<Object> that currently has an integer in it, but could just as well have some non-integer in it. Conversely, it could be a Box<Integer> that happens to have a null in it. For the purposes of finding the minimum element, a null would be an issue, but if the task were to “fill all the Box<Integer> with zero,” then this method of testing the box type would miss the Box<Integer> with null.
   
   
2. The type of intBoxes is wrong. It really ought to be Iterable<Box<Integer>>.
   
   

Anyone care to offer a fix?

Mike Coffin took the bait. (Thanks, Mike!) Unfortunately, pasting code into the blog comments is a very poorly supported feature. Blogs about Python must be interesting. I'll recopy some of Mike's code here.

Mike said: While I prefer this:

int minimumIntegerInBox (Collection<Box> boxes) {
    int result = Integer.MAX_VALUE;
    for (Box box : boxes) {
        if (box.get() instanceof Integer) {
            result = Math.min (result, Integer.class.cast (box.get()));
        }
    }
    return result;
}

that would be cheating.

It isn't cheating, but it isn't answering the question I posed, either. It's more or less the obvious thing to do in Java or Lisp. But conceptually it is pretty primitive. I don't care about the machinery involved in traversing a list (the looping construct). I want to take a binary operation like Math.min and make it n-ary.

Mike gave a very complete solution, but I'm only going to reformat the relevant part:

public static int minimumIntegerInBox(Collection<Box> boxes) {
    Iterable<Box> intBoxes = 
        filter (boxes,
                new Function<Box, Boolean>() {
                    @Override
                    public Boolean of(Box domainItem) {
                        return domainItem.get() instanceof Integer;
                    }
                });

    Iterable ints = 
        map (intBoxes,
             new Function<Box, Integer>() {
                 @Override
                 public Integer of(Box domainItem) {
                     return Integer.class.cast(domainItem.get());
                 }
             });

    return minimumElement(ints);
}

public static int minimumElement(Iterable items) {
    return best(
        new Function<Pair, Boolean>() {
            @Override
            public Boolean of(Pair domainItem) {
                return domainItem.second() < domainItem.first();
            }
        },
        items);
}

That's a lot closer to what I had in mind, but these are untyped Boxes. I want to use parameterized Boxes.

I'm working on a fairly simple problem and I think it illustrates something interesting. Here is the problem statement:

A `box' is an object that has a name and can hold another object of a particular type (that is, there are boxes for integers, boxes for strings, boxes for floats, etc.) You are given an unordered collection of various boxes and must find the smallest integer among the subset of boxes that contain integers.

To make it a tiny bit more challenging, we won't just write an ad-hoc loop. We'll use map, filter, and fold-left. Since fold-left is a bit scary, I'll write that part:

(define (best better? list)
  (fold-left (lambda (best-so-far candidate)
               (if (or (null? best-so-far)
                       (better? candidate best-so-far))
                   candidate
                 best-so-far))
             '()
             list))

(define (minimum-element list)
  (best < list))

So assuming that *box-list* is a variable containing our list of boxes, Exercise 1 is to write a program in Scheme or Lisp using map, filter, and minimum-element that finds the smallest integer (fixnum) in the boxes.
Too easy? Let's make it a bit trickier: Code up the identical solution in Java.

Assume that Box is a generic (that is, parameterized) type, so Box<Integer> would contain an Integer and Box<String> contains a String, etc. The variable BoxList would be declared as Collection<Box<?>>, so we want a method with this signature: int minimumIntegerInBox (Collection<Box<?>> boxes)

I don't think it can be done without getting at least one Unchecked conversion warning, but a cleverly placed @SuppressWarnings("unchecked") will permit you to downcast a Box<?> to a specific type, and then everything else should type check.

[Makers ] is a distribution of libraries for R6RS Scheme implementations. In the paper:

“Keyword and Optional Arguments in PLT Scheme“. Matthew Flatt and Eli Barzilay. 2009 Workshop on Scheme and Functional Programming.

the authors discuss ways to provide functions and macros with a mix of fixed and optional arguments to better organise abstractions. This package humbly proposes an alternative for R6RS implementations, without the use of “keywords” as disjoint type of values.

(via comp.lang.scheme)

The unix program diff identifies differences between text files; it is most useful for comparing two versions of a program.

Given the longest common subsequence between two files, which we computed in a previous exercise, it is easy to compute the diff between the two files; the diff is just those lines that aren’t part of the lcs.

Your task is to write a program that finds the differences between two files. 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.

***********************************************************************
*                                                                     *
*                  International Lisp Conference 2010                 *
*                         October 19-21, 2010                         *
*                    John Ascuaga's Nugget (Casino)                   *
*              Reno/Sparks, Nevada, USA (near Lake Tahoe)             *
*                                                                     *
*           Collocated with SPLASH 2010 (OOPSLA & DLS & more)         *
*               see also http://splashcon.org as well as              *
*          http://www.dynamic-languages-symposium.org/dls-10/         *
*                                                                     *
*              In association with ACM SIGPLAN (PENDING)              *
*                                                                     *
*********************************************************************** 


The Association of Lisp Users is pleased to announce that the 2010
International Lisp Conference will be held in Reno, Nevada, in
collocation with SPLASH 2010.  The scope includes all areas related to
the Lisp family of programming languages.

Accepted papers will be published in the ACM Digital Library (PENDING).

Extended Abstracts and Papers must be written in English and submitted
electronically at http://www.easychair.org/conferences?conf=ilc2010 in
PDF or WORD format. If an Extended Abstract is submitted, it must be 
between 2 and 4 pages, with full paper to follow before final deadline.

Final submissions must not exceed 15 pages and need to use the ACM 
format, for which templates which can be found at:
    http://www.acm.org/sigs/pubs/proceed/template.html.


Important Dates:
****************

* Deadline for Abstract Submission      August      1, 2010
* Deadline for Paper Submission         September   6, 2010
* Author notification                   September  20, 2010
* Final paper due (in electronic form)  October     5, 2010
* Conference                            October 19-21, 2010


Scope:
******

Lisp is one of the greatest ideas from computer science and a major
influence for almost all programming languages and for all
sufficiently complex software applications.

The International Lisp Conference is a forum for the discussion of
Lisp and, in particular, the design, implementation and application of
any of the Lisp dialects.  We encourage everyone interested in Lisp to
participate.

We invite high quality submissions in all areas involving Lisp
dialects and any other languages in the Lisp family, including, but
not limited to, ACL2, AutoLisp, Clojure, Common Lisp, ECMAScript,
Dylan, Emacs Lisp, ISLISP, Racket, Scheme, etc.

Topics may include any and all combinations of Lisp and:

* Language design and implementation
* Language critique
* Language integration, inter-operation and deployment
* Applications (especially commercial)
* 'Pearls' (of wisdom)
* Experience reports and case studies
* Reflection, meta-object protocols, meta-programming
* Domain-specific languages
* Programming paradigms and environments
* Parallel and distributed computing
* Software evolution
* Theorem proving
* Scientific computing
* Data mining
* Semantic web

We also encourage submissions about known ideas as long as they are
presented in a new setting and/or in a highly elegant way.

Authors concerned about the appropriateness of a topic may communicate
by electronic mail with the program chair prior to submission.

Each paper should explain its contributions in both general and
technical terms, identifying what has been accomplished, explaining
why it is significant, and comparing it with previous work. Authors
should strive to make their papers understandable to a broad audience.
Each paper will be judged according to its significance, novelty,
correctness, clarity, and elegance.

The official language of the conference is English.  Some further
information is available at the conference web site, with more details
added later.  See: http://www.international-lisp-conference.org

Technical Program:
******************

Original submissions in all areas related to the conference themes are
invited for the following categories.

* Papers: Technical papers of up to 15 pages that describe original
   results or explain known ideas in new and elegant ways, or extended
   abstracts of 4 pages soon followed by the corresponding full paper.

* Demonstrations: Abstracts of up to 4 pages for demonstrations of
   tools, libraries, and applications.

* Tutorials: Abstracts of up to 4 pages for in-depth presentations
   about topics of special interest for at least 90 minutes and up to
   180 minutes. 

* Workshops: Abstracts of up to 4 pages for groups of people who
   intend to work on a focused topic for half a day.

* Panel discussions: Abstracts of up to 4 pages for discussions about
   current themes. Panel discussion proposals must mention panel
   members who are willing to partake in a discussion.

* Lightning talks: Abstracts of up to one page for talks to last for
   no more than 5 minutes.

Depending on the technical content, each submitted paper will be
classified by the program committee as either a technical paper or as
an experience paper; and authors will be informed about this
classification.  Note that all interesting submissions are considered
valuable contributions to the success of the ILC series of
conferences.  As in past ILC's since 2007, accepted papers in both
categories will be presented at the conference, included in the
proceedings, and submitted to the ACM digital library.


Organizing Committee:
*********************

* General Chair:
   JonL White          The Ginger IceCream Factory of Palo Alto, ALU

* Program Chair:
   Antonio Leitao      Instituto Superior Tecnico/INESC-ID

* Conference Treasurer:
   Duane Rettig        Franz, Inc., ALU Director

* Publicity Chair:
   Daniel Herring      ALU Director

* ALU Treasurer:
   Rusty Johnson       TASC, Inc., ALU Director


Program Committee:
******************

* Antonio Leitao      Instituto Superior Tecnico/INESC-ID, Portugal
* Alex Fukunaga       University of Tokyo, Japan
* Charlotte Herzeel   Vrije Universiteit Brussel, Belgium
* Christophe Rhodes   Goldsmiths College, University of London, UK
* Didier Verna        EPITA Research and Development Laboratory, France
* Duane Rettig        Franz, Inc., USA
* Giuseppe Attardi    University of Pisa, Italy
* Jeff Shrager        Symbolic Systems Program, Stanford University, USA
* Joe Marshall        Google, Inc., USA
* Julian Padget       University of Bath, UK
* Keith Corbet        Clozure Associates, USA
* Kent Pitman         PTC, USA
* Manuel Serrano      INRIA Sophia Antipolis, France
* Marc Feeley         University of  Montreal, Canada
* Marie Beurton-Aimar University of Bordeaux 1, France
* Mark Stickel        SRI International, USA
* Matthias Felleisen  Northeastern University, USA
* Scott McKay         ITA Software, USA


Contacts:
*********

* Questions:         ilc10-organizing-committee at alu.org

* Program Chair:     ilc2010 at easychair.org

For more information, see http://www.international-lisp-conference.org

PLT is happy to announce the release of Racket, available from

  http://racket-lang.org/

With Racket, you can script command shells and web servers; you can quickly prototype animations and complex GUIs; regexps and threads are here to serve you. To organize your systems, you can mix and match classes, modules or components. Best of all, you start without writing down types. If you later wish to turn your script into a program, equip your Racket modules with explicit type declarations as you wish. And Racket doesn't just come as a typed variant; you can also write your modules in a purely functional and lazy dialect.

Racket comes in so many flavors because Racket is much more than a standard scripting language or a plain programming language. Racket supports language extensibility to an unequaled degree. A Racket programmer knows that making up a new language is as easy as writing a new library.

To help you start quickly, Racket includes batteries in all shapes and sizes, most importantly, extensive documentation and all kinds of libraries.

Racket occupies a unique position between research and practice. It inherits many major ideas from language research, among them type safety (when the type system says that x is a number, then at runtime it always is a number) and memory safety (when some memory is reclaimed by the garbage collector it is impossible to still have a reference to it). At the same time, user demand governs rigid adherence to purely theoretical principles.

Racket, formerly PLT Scheme, is a product of over 15 years of development. Although Racket starts with a mature software base and an established user community, its new name reflects our view that this is just the beginning of Racket's evolution.

PLT is happy to announce the release of Racket, available from

  http://racket-lang.org/

With Racket, you can script command shells and web servers; you can quickly prototype animations and complex GUIs; regexps and threads are here to serve you. To organize your systems, you can mix and match classes, modules or components. Best of all, you start without writing down types. If you later wish to turn your script into a program, equip your Racket modules with explicit type declarations as you wish. And Racket doesn't just come as a typed variant; you can also write your modules in a purely functional and lazy dialect.

Racket comes in so many flavors because Racket is much more than a standard scripting language or a plain programming language. Racket supports language extensibility to an unequaled degree. A Racket programmer knows that making up a new language is as easy as writing a new library.

To help you start quickly, Racket includes batteries in all shapes and sizes, most importantly, extensive documentation and all kinds of libraries.

Racket occupies a unique position between research and practice. It inherits many major ideas from language research, among them type safety (when the type system says that x is a number, then at runtime it always is a number) and memory safety (when some memory is reclaimed by the garbage collector it is impossible to still have a reference to it). At the same time, user demand governs rigid adherence to purely theoretical principles.

Racket, formerly PLT Scheme, is a product of over 15 years of development. Although Racket starts with a mature software base and an established user community, its new name reflects our view that this is just the beginning of Racket's evolution.

I've been fooling around with clojure a bit lately. Something fun: a dotimes-like macro, but it completely unrolls your loop at compile time: (defmacro dotimes-unroll "Just like dotimes, but completely unrolls the given loop. The number of iterations must read as a number." [[i n] & body] (assert (number? n)) (if (= n 0) `nil `(let [~i ~(- n 1)] (dotimes-unroll [~i ~(- n

Things seemed a bit quiet here until I looked at some older posts and discovered comments I hadn't seen before. It seems that gmail had gotten into its head that forwarded posts were spam. Wonderful. My apologies for not responding to people.

I chose ok...

(I had to retouch the buttons because the camera overexposed them.)