gmane.culture.people.kragen.thinking

a possibly novel error-correction code with a relationship to theHadamard transform

Kragen Javier Sitaker — 2013-03-03T22:18:28

Last night, I encoded some messages in ASCII by hand, including
error-correction coding: like the printer dots Seth Schoen decoded,
matrices of 8 columns of 8 bits each, with an extra column and row for
parity.  (I used even parity, but odd would have been a better
choice.)  Matrix parity lets you correct single-bit errors: a
single-bit error will show up as a parity error in both the row parity
and the column parity.  And it's simple enough and spatial enough that
you can both detect and correct errors by hand.

This got me to thinking about what kind of more powerful
error-correction coding might be feasible to perform by hand, and I
think I came up with one, which at first glance appears to be related
to the Hadamard transform, but in the end seems to be something
simpler.

Existing Hadamard-code work is quite different
----------------------------------------------

For many years, Hadamard matrices have been used for error-correction
coding by the simple expedient of using a row of the matrix for each
c

a logarithmic-time alternative to summed-area tables for reducingarbitrary semigroup operations over arbitrary ranges (a generalizationof RMQ segment trees)

Kragen Javier Sitaker — 2012-12-06T08:37:01

# Summary #

There's an alternative to summed-area tables with a small, linear
space cost and linear construction time and space, providing worst-case
logarithmic-time reduction over arbitrary intervals under arbitrary
semigroup operations, and which supports updates efficiently, unlike
summed-area tables.  The algorithm is like twenty fricking lines of code
if you leave out the "update" and "small" parts.

I am surely not the original discoverer of any of this.

# Explanation #

## Introduction to abstract algebra ##

Abstract algebra is the study of what you can deduce from minimal sets
of axioms about some set of things and operations on them.  A lot of it
seems to be taxonomic, assigning names to particular sets of axioms.
This is cool because once you establish that, say, 32-bit bitstrings
form a semilattice under the bitwise-OR operation, you can apply every
theorem that anybody's ever proven about semilattices to 32-bit
bitstrings and OR.

In particular, as I think Stepanov first realized, the correct

decentralized chat using CouchDB

Kragen Javier Sitaker — 2012-11-24T03:21:04

I just sent this message to the CouchDB User mailing list instead of sleeping
like I ought to be doing.

----- Forwarded message from Kragen Javier Sitaker <kragen< at >canonical.org> -----

Date: Fri, 23 Nov 2012 22:14:18 -0500
From: Kragen Javier Sitaker <kragen< at >canonical.org>
To: user< at >couchdb.apache.org
Subject: decentralized chat
User-Agent: Mutt/1.5.20 (2009-06-14)

Hi.  I'm new to CouchDB, but I was just chatting with Noah on IRC about
how IRC sucks and we need to replace it and whether we could do that
using CouchDB.  He mentioned this thing Chris did four years ago called
Toast:

<http://jchrisa.net/drl/_design/sofa/_list/post/post-page?startkey=%5B%22Simple-Wins%22%5De>

Right now Skype chat is basically the best thing out there that I've
seen, but it's proprietary.  It has the following features I like:

* Real-time: people normally see your lines within less than a second
  after you send them.
* Peer-to-peer: you don't have to install or manage software on a server
  to make it work, and it knows how

impermanence of life

Kragen Javier Sitaker — 2012-09-13T07:37:01

I wrote this to a far-away acquaintance of mine who's been struggling
with her fears since coming abruptly face to face with her mortality
during a recent acute illness.

Sending you hugs; I'm reading this rather late. I will try to say
something that has not already been said.

The recognition of the impermanence of life and the recognition of the
inevitability of death are necessary foundations for truly beginning to
live.  We can't understand the preciousness of every moment of life
until we realize how very scarce those moments are.

Knowing you will die, you can begin to abstain from fear of death.
Suppose something might kill you; so what? You'll be dead in the long
run anyway. Death cannot harm you. What matters is not whether you die
but how you live. Don't waste your life by living it in fear. You may
not get another one.

Many people know they will die but still have faith that all will be
well. They are not foolish; they just have a definition of all being
well that is bigger than their own indivi

boycotting Chick-Fil-A is authoritarian and evil

Kragen Javier Sitaker — 2012-08-02T07:37:01

Although I'm not actually gay --- I can't remember having had so much as
a dick in my mouth --- I'd certainly have an uphill battle proving that
if I were being indicted for gayness.  And if I were attracted
exclusively to men, I'd definitely have sex with men instead of living
celibate.  Finally, a lot of people close to me are gay, bi, or
transsexual.  Nevertheless, I think the current calls to boycott
Chick-Fil-A because of the anti-gay views of its president are
anti-liberal and authoritarian.

The liberal ideal of freedom of speech goes beyond a norm constraining
government actions; it's a norm about how public debate ought to be
carried out: with everyone free to speak their mind without fear of
suffering a backlash, and nobody intimidated into silence.  The liberal
ideal is that ideas stand or fall on their own merits, not on the
personal connections of their proponents. That's why we don't want the
government telling us what we can and can't say — there's no guarantee
that the ideas that the govern

language-model dimensionality reduction with Markov-chaindistribution medians

Kragen Javier Sitaker — 2012-07-30T23:00:33

In my kragen-tol post earlier this month about [predictive text input
methods][0], I wrote:


[0]: http://lists.canonical.org/pipermail/kragen-tol/2012-July/000961.html

But part-of-speech tagging is sort of hard, especially on incomplete and
possibly erroneous sentences containing words that aren't in the dictionary.
But it seems like you ought to be able to do a good enough job with simple
statistics to be useful.

Now, the rest of this post may be a case of "a few hours of hacking can save
you several minutes in the library", so take that under advisement.  I haven't
checked out the literature enough to know if this idea is already known, let
alone an improvement over what already exists.

One simple approach is to consider a Markov-chain model of text, and cluster
together words whose transition probabilities are similar, either for
in-transitions (what they tend to follow) or out-transitions (what they tend to
precede).

However, this runs into a practical problem immediately: even with a
first-order Ma

database query optimizers for simplifying software systems

Kragen Javier Sitaker — 2012-07-23T07:37:01

Another item that didn't make it into [my post on Monday][0]: database
queries are probably another powerful primitive which can simplify a
whole computing system.  

[0]: http://lists.canonical.org/pipermail/kragen-tol/2012-July/000962.html "choosing powerful primitives for a simplified computing system"

It’s a commonplace observation that complex SQL queries are
dramatically shorter, clearer, and sometimes more efficient than
imperative programs to evaluate the same queries — especially on a
database that wasn’t originally designed for those particular queries.
It’s less well known that reformulating those queries in Datalog or
Prolog makes them shorter and clearer still, while removing some of
the restrictions on SQL (at least ANSI SQL-92, which doesn’t support
any form of transitive closure), and providing dramatically superior
abstraction capabilities.  I have an [unfinished proposal tentatively
called Binate][Binate] for a database query language that is even
terser than Datalog and provides

a unified caching system for avoiding recomputation

Kragen Javier Sitaker — 2012-07-19T07:37:01

There’s an old saying that there are only two hard problems in computer
science: naming, caching, and off-by-one errors.  Caching of
computations is basically a classic time-space tradeoff, but caching is
also used for other purposes: for fault-tolerance, to trade off network
bandwidth against storage, for privacy, and to improve scalability by
minimizing the work done at a potential hotspot in a distributed system,
among other things.  

I propose that delegating almost all caching of computations to a
dedicated computation-caching subsystem would have substantial
benefits for computer system design, enabling transparent parallelism,
network transparency, and fault tolerance, while improving performance
and substantially simplifying application code.


Examples of caching of computation
----------------------------------

Current computer systems use many layers of caching, implemented in
many different ways, many of them just to cache computations.

### MVC ###

One broad generalization is that views in

choosing powerful primitives for a simplified computing system

Kragen Javier Sitaker — 2012-07-16T07:37:01

One of the basic principles of the [FONC/STEPS system] [STEPS] is that
you can reduce the overall complexity of software by choosing powerful
primitives that simplify many parts of a system.  OMeta is sort of their
poster child: a generic rewriting system powerful enough to write
simple, efficient parsers with, but also to write compiler optimizers
and code generators with.

[STEPS]: http://vpri.org/fonc_wiki/index.php/Glossary

Here are some candidates for other primitives which, in practice,
simplify other parts of a computing system by more than the complexity they
add.

LZ77 obsoletes curses and other things
--------------------------------------

Using zlib to compress your data streams and files greatly reduces the
performance penalty for not optimizing your file formats and protocols
to reduce file and message size.  Here are some exmaples.


### curses ###

At the Barracas [hacklab][] tonight, I was talking about why curses, the
programming library, is useless today.  Curses goes to a lot of effort
t

how to do a better predictive text input method for Android

Kragen Javier Sitaker — 2012-07-15T05:15:03

The SwiftKey X trial just expired on me on the Android phone loaner
I’m using from my work.  I still have the keyboard layout, but the
predictive text no longer works.  This makes it a real bummer to use
the machine.

I guess it serves me right for depending on proprietary software.  I
should have known better.

So it occurred to me to think about what would be needed to replace
it with free software.

The first thing to note is that SwiftKey X can result in major
disclosures of confidential information.  If you borrow someone else’s
Android phone to check your Facebook account or whatever, and you
start accepting the default suggestion over and over again, it will
frequently reproduce substantial chunks of text from their history.
If they used SwiftKey to enter confidential information into their
phone, you may end up seeing bits of it purely by accident if you use
some of the same words.

So, given that this is apparently acceptable, a quick-and-dirty input
method that works more or less the same way c

washing machines don't have to use energy to heat water

Kragen Javier Sitaker — 2012-07-03T23:24:19

I recently saw an article that claims that heating water to 40° for washing
laundry consumes around 5–10kWh per load.

However, it turns out that heating up water doesn't consume energy.  You need
energy to do it, to be sure — but that energy is still in the water after you
heat it up.  The Carnot limit prevents you from recycling most of that heat
into exergy to, say, drive the washing machine motor, but nothing is preventing
you from transferring that heat from dirty water into clean water, or into a
heat reservoir that holds it until your next wash.

First, is such a reservoir possible?  Most definitely.  You can buy
fractionated paraffin wax that melts at more or less whatever temperature you
want, to a few degrees of precision, with a heat of fusion near that of water
ice.  A big Thermos inside the washing machine, full of paraffin or another
phase-change material, could hold a laundry load's full of heat for several
days, if not a week.  But how to get the heat into it?

The key is a clever little

washing machines don't have to use energy to heat water

Kragen Javier Sitaker — 2012-07-03T23:24:19

I recently saw an article that claims that heating water to 40° for washing
laundry consumes around 5–10kWh per load.

However, it turns out that heating up water doesn't consume energy.  You need
energy to do it, to be sure — but that energy is still in the water after you
heat it up.  The Carnot limit prevents you from recycling most of that heat
into exergy to, say, drive the washing machine motor, but nothing is preventing
you from transferring that heat from dirty water into clean water, or into a
heat reservoir that holds it until your next wash.

First, is such a reservoir possible?  Most definitely.  You can buy
fractionated paraffin wax that melts at more or less whatever temperature you
want, to a few degrees of precision, with a heat of fusion near that of water
ice.  A big Thermos inside the washing machine, full of paraffin or another
phase-change material, could hold a laundry load's full of heat for several
days, if not a week.  But how to get the heat into it?

The key is a clever little

Meghan Saweikis on the development of human society

Kragen Javier Sitaker — 2012-06-28T01:49:47

Meghan Saweikis wrote the following; I thought it was really excellent,
so with her permission, I am posting it here.  Maybe it should go to
kragen-fw instead, but kragen-fw is mostly dead, really.

I think the issues touched on in this mail are among the most important
issues for every human being to think about.

---

I’ve been thinking a lot about what you said and about how I quantify
“net positive” vs. “net negative” impact on the world. I agree with
you that the objective level of suffering may be decreasing. I agree
that there is increasing literacy, autonomy and access to basic health
care services. I agree that these are positive things. I agree with
you that humanity as a whole has accomplished these positive
things. But, I think humanity as a whole has also created some
significant problems (both for other humans and for the
ecosystem). I’m not sure I think the benefits you mention are positive
enough to suggest that humanity in general is a “net positive.” And
even if humanity in

FeML: a skeleton of a femto-ML with nothing but polymorphicvariants and functions

Kragen Javier Sitaker — 2012-06-14T07:37:01

A year or two ago, Darius Bacon and I were talking about making a sort
of variant of Scheme with ML-like pattern-matching as the basic
primitive.  You have a slightly more complicated lambda, but you don’t
need cond, car, cdr, eq, or null? in the base language, just cons or
quasiquote, plus the pattern-matching lambda and either labels or
define.

For example:

    (define assoc 
      (lambda (key ((key . value) . more)) (cons key value)
              (key (x . more))             (assoc key more)
              (key ())                     '()))

Here `lambda` takes an arbitrary set of pattern-action pairs and
matches the patterns in order against the argument list, evaluating
and returning the action expression for the pattern that matches.  In
this case, first we check to see if the key is the caar of the list of
key-value pairs, and if so, we return its (reconstructed) car;
otherwise, if there are more items in the list, we recurse down the
list; otherwise, if the list is the empty list, we return the e

short-term predictions: 2014, 2017, 2022

Kragen Javier Sitaker — 2012-06-12T10:39:58

The release of Meteor in April reminded me about an abandoned project of my own
called Kogluktualuk, which was basically Meteor, but never implemented to any
significant extent. It was kind of obvious that something like Meteor needed to
exist. So I thought I would record some other predictions about things that
haven't happened yet, to see if my foresight is really as good as it seems in
hindsight. After all, it's easy to fool yourself into thinking about only your
correct predictions, forgetting the stupid ones. So this is, like debugging, a
sort of exercise in therapeutically feeling stupid. 

---

Two years from now, most iOS applications will be written in Cordova (formerly
PhoneGap) or a successor, rather than in ObjC. This is both because JS is a much
more productive language than ObjC and in order to target Android as well. 

Within 5 years, P2P protocols will resurge in importance. This is despite the
massive move from desktop and laptop computers to handheld computers running
iOS and Android and us

math for 3-D printers without any linear actuators

Kragen Javier Sitaker — 2012-04-26T07:37:01

How do you control a polar 3-D printer?

Like, you have a turntable with your workpiece on it, and another
turntable that moves your tool, that can swing it over the center of
the first turntable.  And you can move your other turntable up and
down.  Now how do you convert x and y coordinates into angular
positions?

Perhaps a handy thing to know is that the polar equation r = sin θ
produces a circle running through the origin, retracing the same
circle when θ is in [0, π] and in [π, 2π], with its center at r = ½, θ
= ½π.  So, given the radius r at which a point is located on the
workpiece turntable, you can rotate the workpiece turntable to any θ
such that sin θ = r, such as sin⁻¹ θ, to give the tool turntable a
chance to hit the point.  Then it’s just a matter of finding the angle
for the tool turntable, a simple atan2.

In short, starting from x, y on the workpiece turntable, scaled so
that the distance between turntable centers is 1:

    θw = sin⁻¹ √(x² + y²)
    s = sin θw

printing microfilm on ordinary laser printers on paper

Kragen Javier Sitaker — 2012-04-23T20:42:30

#!/usr/bin/python
# -*- coding: utf-8 -*-
"""Compute proportional-font print size of a text.

The laser printer at my new workplace is 600dpi in both directions.
It prints on A4 or similar paper: 216×279mm.

Simple multiplication yields a capacity of 33.6 megabits per page, or
about 4 megabytes.

At 600dpi, a 4×6 pixel character cell like the one I use in
<http://canonical.org/~kragen/sw/dofonts-1k.html> gives you an 80×66
page of 13.5 mm × 16.8 mm.  (Janne Kujala designed the font.) If you
can successfully control every pixel, the result should be clearly
readable with a magnifying glass.  (If we consider 5-point text as the
lower limit of comfortable readability, and these 6-pixel-tall
characters are 1/100 inch, you need 7× magnification to make the text
comfortably readable.)

Further calculation suggests that the A4 page will contain an array
fitting 16 such reduced pages horizontally and 16.6 of them
vertically; practically this is probably 15 horizontally and 16
vertically, or 240 pages, 480 pages

apologies for repetition (Re: parsing, PEG parsers, andbacktracking HTML templating: toward a bright parsing future (examplesin OCaml, C++, and Ruby))

Kragen Javier Sitaker — 2012-04-19T11:16:36

Sorry about that.  I edited the message in the outgoing queue with Emacs, and
Emacs made a backup and an autosave file, which the outgoing-mail-queue system
interpreted as two more messages to be sent out on schedule.

parsing, PEG parsers,and backtracking HTML templating: toward a bright parsing future(examples in OCaml, C++, and Ruby)

Kragen Javier Sitaker — 2012-04-16T07:37:01

On Fri, Apr 13, 2012 at 10:19:36PM -0400, Kragen Javier Sitaker wrote (on
kragen-discuss):

(in
<http://lists.canonical.org/pipermail/kragen-discuss/2012-April/001227.html>,
referring to
<http://lists.canonical.org/pipermail/kragen-tol/2012-April/000951.html>.)

So this isn’t a parser either, but it’s some directions for parsing
research to go in.

A PEG for the backtracking HTML templating language
---------------------------------------------------

Here’s a PEG grammar for the template language, leaving out the 
`<if a == b>` construct for now until I can figure out how `a` and `b`
should be delimited. I wrote it down in my notebook waiting for the
bus home on Saturday night:

    doc <- seq loop?.
    loop <- loopstart doc ('<,>' doc)?.
    seq <- alt , '<;>'.
    alt <- jux , '<|>'.
    jux <- atom*.
    atom <- '<{>' doc '<}> / var / lit.

    lit <- ('\\' byte / !special byte)+.
    special <- '<' [{},;|] '>' / var / loopstart.

    var <- '$' name.
    loopstart <- '<< at >' name '>'.
    name <- (!

backtracking HTML templating

Kragen Javier Sitaker — 2012-04-13T04:30:44

This is an idea originally from 2010-04-08 that I just never got
around to publishing until now.

Now that I’ve written the below, I’m tempted to try to hack this
together tonight, but I think I should probably sleep instead, and
maybe do this on the weekend.

Motivation
----------

This week I’ve been working on a bibliographic website, which, among
other things, renders citations into HTML.  And this is resulting in
me writing a lot of HAML templates that say things like:

    - if < at >publication.booktitle?
      In #{publication.booktitle}.
    - if < at >publication.month?
      #{< at >publication.month} #{< at >publication.year}.

The general pattern here is that there are one or more properties that
need to be present, and if they’re present, we format them together,
along with some other window dressing intended to format them
properly.  But this involves a lot of very local duplication in the
code, and even though that duplication is local, it is still
error-prone; consider what happens in the above case if

potential applications of Taylor's Image Fidelity Assessor andsimilar models

Kragen Javier Sitaker — 2012-04-09T16:12:39

I've been thinking about this a lot more.  The 1998 dissertation expanding this
work is called "IMAGE QUALITY ASSESSMENT BASED ON A HUMAN VISUAL SYSTEM MODEL";
he calls his algorithm the "Image Fidelity Assessor", and as he explains in the
dissertation:


That is, it tells you how perceptually different two images are, pixel by
pixel.  He validated his model with a bunch of psychovisual experiments on
humans and supposedly found that it predicted well.

What could you do given an efficient algorithm to produce such a map?  In my
previous post I suggested that you could do much better halftoning, but here's
a list of additional possible applications, some of which were proposed by
Taylor:

- JPEG or JPEG2000 compression: improve the visual quality per bit by using
  bits on the parts of the image, and the frequencies, that really need it
- generating line-art representations of images (e.g. pencil portraits).  This
  requires that Taylor's algorithm continues to provide useful values for
  images that are ve