The Rational Keyboard

January 8, 2012

While traveling in Vietnam, I wrote a little browser app to experiment with automated reasoning about harmony in just intonation. The resulting Rational Keyboard is kind of like a piano whose keys move around to make consonant notes & chords easy to play. One cool thing about an instrument with moving keys is that it can access all rational tones (a dense infinite set) with only a finite number of keys visible at any time.

The app currently only seems to run in Chrome (audio synthesis is a recent browser feature). If you’d like to see how it works, or help getting it working in other browsers, check out the github page or just

git clone git@github.com:fritzo/rationalkeyboard.git

C++ tips #1

February 9, 2011

Virtual Class Inheritance in C++

Java has notions of both class inheritance and interface inheritance, where interfaces are only sets of methods. To mimic this very useful behavior in C++ I often define classes with only a single method, such as

class Point;

struct PointSet
{
  virtual bool contains (const Point & const) const = 0;
};

class Point
{
  ...
public:
  inline bool in (const PointSet & point_set) const
  {
    return point_set.contains(*this);
  }
  ...
};

so that when defining objects which "are", among other things, sets of points, they can inherit as so:

class Environment
  : public PointSet
{
  ...
public:
  virtual bool contains (const Point & point) const { ... }
  ...
};

In complicated class hierarchies, it can be useful to aggregate such abstract interface classes, e.g.,

struct MetricSpace
  : public PointSet
{ ... };

struct VectorSpace
  : public PointSet
{ ... };

struct BanachSpace
  : public MetricSpace,
    public VectorSpace
{ ... };

But oops, BanachSpace is now a PointSet in two distinct ways, i.e. via VectorSpace::contains and via MetricSpace::contains. To avoid this so called "diamond problem"

          PointSet                  PointSet    PointSet
         /        \                     |           |
  VectorSpace  MetricSpace   vs   VectorSpace   MetricSpace
         \        /                      \         /
         BanachSpace                     BanachSpace

C++ designers invented virtual inheritance which allows a unique inheritance of each interface-like method, so that in

struct MetricSpace
  : public virtual PointSet
{ ... };

struct VectorSpace
  : public virutal PointSet
{ ... };

struct BanachSpace
  : public virtual MetricSpace,
    public virtual VectorSpace
{ ... };

References

C++ FAQ Lite,
Wikipedia

BanachSpace::contains is unique.

C++0x

Gcc 4.4 and later support nice C++0x features like hash tables via std::unordered_map and auto typed variables, as in

std::unordered_map<
  std::pair,
  std::vector<std::pair > > widgets = get_widgets();

for (auto i = widgets.begin(); i != widgets.end(); ++i) {
  std::swap(i->second.first, i->second.second);
}

The new standard also allows variadic initializer lists with a small speed penalty.

My favorite features are:


Roundup: music + interface + algorithms

May 12, 2010

(a deluge of links, after stumbling on echonest.com)

The Echo Nest
An MIT Media Labs spinoff that uses machine listening and web datamining technology to give structure social song-space.
Reactable
An electronic musical instrument with a tabletop Tangible User Interface, developed by the Music Technology Group at the Universitat Pompeu Fabra.
RJDJ
Music synthesizer that reacts to environmental sounds to create context-aware music, currently an iPhone app.
mufin
Another researchy company doing datamining to give structure to song-space.
Music HackDay
A roving hackathon focused on music software, hardware, and mashup.
ignorethecode
Lukas Mathis’ blog on user interface design.

Computational aesthetics for foundations of math

March 28, 2010

(this is a research abstract from 2008-09-29)

A foundation for mathematics is a formal system (language + logic) in which all other formal systems can be expressed and reasoned about. By Goedel’s first incompleteness theorem,
such systems are never logically complete (with finite axiomatizations). Thus any foundation of math leaves some questions unanswered. Logicians must ask the ongoing question “what new axioms should be assumed”. So let us ask,

What new axioms should be assumed [in any foundation of math]? Of course no algorithm can decide which axioms to add, otherwise we could simply add a finite axiomatization of the algorithm. Instead logicians, e.g. professional set theorists, employ the aesthetic rule: “good axioms lead to elegant theories”. So what is an elegant theory? In elegant theories, the world is simple: sensible things are easy to say, and senseless jabber is difficult to say. The mathematical literature itself serves as a data set of sensible statements, expressed as sets (as e.g. in a recent paper by Avigad et al.). So elegant theories should simply shrink the remaining [by contrast, senseless] part of the universe of sets to be as small as possible.

Which axioms shrink the remaining universe? What is a small model of the universe of sets? In our present application, we can formalize by defining a notion random set, and minimizing the universe’s entropy (a soft notion of size). Since we’re interested in writing simple math, let’s generate random sets by picking random expressions denoting sets. Formally, we define a probabilistic grammar, whose parameters are statistically fit to a corpus of real-world expressions (the mathematical literature). Then we can simply rank axiom candidates by the entropy change they induce on the universe of sets.

This aesthetic algorithm works in theory, but founding math in set theory leads to practical difficulties: sets have a complicated syntax (it’s even undecidable whether a given set expression is actually a set), and complicated reasoning principles. The grammatically-simplest foundation for computable mathematics is arguably Combinatory Logic, a language with two constants and a single binary operation. In fact combinatory algebra can be extended by a couple more constants, and a few more axioms, so that all mathematical questions can be posed as equations between these extended terms.

My Ph.D. research focussed on implementing and assessing the min-entropy aesthetic algorithm, and working on the particular foundation of an extended combinatory algebra.


Follow

Get every new post delivered to your Inbox.