Thursday, June 24, 2010

Dr Scheme name change

I put together a page that compares the various names of Dr. Scheme by how often people search for them in Google.

Friday, June 11, 2010

Buoyancy

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);
    }
}

Thursday, June 10, 2010

An Illustrative Problem (Part II) correction

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?

Wednesday, June 9, 2010

An illustrative problem (part II)

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.

Tuesday, June 8, 2010

An illustrative problem.

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.

Monday, June 7, 2010

International Lisp Conference 2010 - Call for Papers

***********************************************************************
*                                                                     *
*                  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

Friday, June 4, 2010

It was quiet..... too quiet.....

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.

Choose and perish

I chose ok...

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