27 February 2012

How are dotted graphs second class?



I said that dotted graphs seem to be second class objects and John asked me to elaborate.

How are dotted graphs second class?

A number of combiners in the spec accept cyclic but not dotted lists. These are:

  • All the type predicates
  • map and for-each
  • list-neighbors
  • append and append!
  • filter
  • reduce
  • "Constructably circular" combiners like $sequence

So they accept any undotted graph, but not general dotted graphs. This occurs often enough that to make dotted graphs seem second-class.

Could it be otherwise?

The "no way" cases

For some combiners I think there is no sane alternative, like `pair?' and the appends.

The "too painful" cases

For others, like filter or list-neighbors, the dotted end could have been treated like an item, but it seems klugey and irregular, and they can't do anything sane with a "unary dotted list", ie a non-list.

$sequence etc seem to belong here.

map and for-each

For map and for-each, dotted lists at the top level have the same problem as above, but ISTM "secondary" dotted lists and lists of varying length could work.

Those could be accomodated by passing another combiner argument (proc2) that, when any list runs out, is given the remaining tails isomorphically to Args, and its return is used as the tail of the return list. In other words, map over a "rectangle" of list-of-list and let proc2 work on the irregular overrun.

The existing behavior could be recaptured by passing a proc2 that, if it gets all nils, returns nil, and otherwise raises error. Other useful behaviors seem possible, such as continuing with default arguments or governing the length of the result by the shortest list.


Reduce puzzles me. A cyclic list's cycle after it is collapsed to a single item resembles a dotted tail, and is legal. Does that imply that a dotted list should be able to shortcut to that stage?

25 February 2012




I have often blogged about Kernel, John Shutt's Scheme-like language.

Lisp becomes Digrasp?

One interesting thing about Kernel is that it treats pairs rather than lists as fundamental. Consequently, digraphs constructed from pairs have a certain fundamental status too. Most operations in Kernel allow arbitrary digraphs if they allow pairs. OK, dotted graphs seem to be second class objects. But as long as every cdr points to a pair or nil, you can pass it almost anywhere that accepts a pair.

So rather than LISt Processing, it's like DIrected GRAph ProceSsing. OK, the acronym's not perfect, but it sounds better than DIGRAP and echoes LISP.

24 February 2012

Review Beginning Of Infinity 3

Review Beginning Of Infinity 3

Been busy

I've been busy adding a major feature to Rosegarden, so I've let this go for a while. But I fixed the last known bug today, so I may already be done (or not).


So now that I have a little time again, this has been jangling around in my mind. Patchwork Zombie compared hard-to-vary to peaks on a fitness landscape, in order to make the concept more obvious.

How much is hard-to-vary like a fitness landscape?

A pointy landscape is definitely part of the picture. The layout of the landscape corresponds in the familiar way to the dimensions of variation.

But it's not a fitness landscape, because hard-to-vary is itself the fitness condition. Or to be tiresomely pedantic, Deutsch appeals to it as being the relevant fitness condition on various topics. So height can't also be the fitness condition.

That much I'm sure of. Now comes the part where I have to relate what he "surely must have meant". ISTM that height on the landscape corresponds to some perceptual dimension. Sharp peaks which fall off very steeply are hard to vary and rounded peaks aren't.

And I bet you noticed, where I said "some perceptual dimension", that there wasn't just one perceptual dimension in the previous posts. Right. A landscape could have many height dimensions / perceptual dimensions. Steepness on all of them would count; presumably it's something like the norm of the gradient.

Deutsch's motivating example

I'll relate how Deutsch introduced hard-to-vary, which may make it clearer.

He initially talks about hard-to-vary by comparing two ways of copying things. Both are like "telephone", the children's game where one person tells a secret to the next, who tells it to the next, to the next, and the last person tells it aloud, and you see how much it has changed.

Each person sees a picture of a Chinese junk, and draws it, and then shows that drawing to the next person. Every generation of copy is a little less faithful to the original. Probably no copy is very much worse than the previous, but the result at the end scarcely resembles the picture at the start of the chain.
Origami (paper-folding). Each person is shown how to fold a Chinese junk. If an intermediate guy makes a sloppy copy, the next guy may still understand what he was trying to do; his copy won't inherit the sloppiness. Or the next guy may fail to understand the intent, and then his copy will not be much like the original at all, and everyone further down the line will inherit his mistake. Every generation of copy is either basically the same as the original or very wrong.

The "digital" copying, Deutsch says, is the one that's hard to vary. Variations either disappear or they change the design into some grossly different design.

14 February 2012

"Hard To Vary" and personal identity

"Hard To Vary" and personal identity


I read and sorta-lightly-reviewed David Deutsch's The Beginning Of Infinity. But in this post I'm going to talk about a tangential question to which it suggested an answer. So this post is my thoughts evoked by Deutsch's book.

Transporters as abattoirs

As a way of introducing the question, I'm going to recount a conversation that I sometimes hear in nerdspace. It starts with someone observing that transporters a la Star Trek "are really death machines". Why? Because they make a copy and destroy the original. "They kill you and make an identical twin".

Someone else (usually me) asks socratically, if this twin is so completely identical, what have you lost? Describe any test for this lost thing, other than where the guy is now standing.

The next point in the usual exchange is fraught with exasperation. I'll paraphrase it as this: In our normal experience if the body that we walk around in and whose eyes we see out of is destroyed, that's the end of us.

Then someone observes that in the normal course of events, every atom in our bodies is periodically replaced. Some faster than others, but after a few months, we have been mostly replaced with new material.

"But that's different, it's gradual"

"What's so magical about change being gradual?"

"There's continuity."

"In the transporter, there's continuity too, of information. All the relevant information reaches the other end. Otherwise it wouldn't know to how rebuild the guy there."

"But you're always conscious"

"What about when you're asleep?"

"You're alive the whole time."

"With Heisenberg uncertainty, on a short enough time-scale you're not really continuously anything."

Various other points are made. Usually this debate gets repetitive and exasperated and ends without a meeting of minds, but with a feeling that "transporters kill you" is simplistic.

The question

And a question is left hanging in the air: Then what exactly is it that we want preserved? We value personal survival. What is X, that if we have it, we have this valuable personal survival, and if we don't have X, we don't?

It's not being materially unchanged. We change atoms all the time.

It's not physically breathing or heart-beating - we all know about coma patients.

It has something to do with being faithfully copied. But it isn't being 100% unchanged. If you could never learn anything new, that wouldn't be perfect, ideal personal survival, it'd be scarcely better than death.

Personal identity is the hardest to vary (to ourselves)

I've already given away a big chunk of the answer. We value the "hard to vary" parts of ourselves. Our atoms aren't hard to vary. Our good parts are. Almost any oxygen will do for breathing. No other set of friends or childhood memories are suitable replacements for our own.

With art, we had to ask what design terrain it was hard to vary in, and the answer seemed to be the audience's perceptive powers. But with personal identity, we are both the art and the audience.

So the criterion is self-referential. Art and explanation didn't have self-referentiality, at least not in the all-consuming way that personal identity does.

So our "hard to vary" criterion has a lot of chicken-and-egg-ness to it. We value aspects of ourselves because we appreciate them in contrast to the possible variants that we perceive - but those perceptions were in turn informed and molded by what we value. It's a path-dependent metric.

Does it fit?

It's a quick stab at a deep problem, so there's plenty of room for this idea to be misguided. But it seems about right. It doesn't fall into the trap of valuing our atoms or our continuous wakefulness, or making a frozen-in-carbonite body our ideal.

The path-dependency fits. Personal identity is full of path-dependent phenomena. Our friends and families are irreplacable to us, but we're not seriously under the impression that had our lives been different and we met another random-ish set of people, those putative other people would all have been second-rate unlike our actual friends and family.

It seems compatible with Wei Dai's observation (can't find the link) that people of all cultures have an abundance of apparently terminal values. At least, it's not obviously suspicious for there to be many hard-to-vary values. On the other hand it doesn't fall into the deontic trap of stipulating a list of terminal values, leaving us to ask "Why those?".

So I find this to be a promising theory of the value in personal identity.

04 February 2012

The Beginning Of Infinity

David Deutsch's The Beginning Of Infinity

images/boi_cover_large.jpg http://beginningofinfinity.com/

At first, I was disappointed in this book. I had liked his earlier book The Fabric Of Reality and I had high expectations. The Beginning Of Infinity seemed pedestrian after that - at first.

His main topic, the central intellectual value of good explanations, was interesting in principle, but I'd already got that from his earlier book. He describes good explanations as "hard to vary".

Then he examined themes that I was already familiar with: Evolution as unintelligent design (a la Dennett). Many-worlds. Memetics. Infinity (a la Cantor). It's hard to get excited about stuff I already knew.

Why Are Flowers Beautiful?

Chapter 14 "Why Are Flowers Beautiful?" was the first exciting offering in the book, at least to my eyes. Good art, he says is also hard to vary, just like explanation and design.

He makes his case by talking about flowers. You may think flowers peaceable creatures, but they are the product of a sort of arms race. Flowering plants are symbiotic with pollinating insects, which need to recognize them. But if their flower designs were too easy to imitate, other flowers with poorer nectar would look like them. The insects would sometimes visit the poorer flowers instead, undesirable for both the insects and the proper flowers, benefitting only the free-loading flowers.

So each flower species has an appearance that's hard to imitate. Since no flower has a monopoly on any color or shape, a free-loading flower could easily get the gross appearance right. So flowers have appearances that are "hard to vary". Getting the appearance kind of grossly right won't fool the pollinating insects.

patchworkZombie points out that this is unlikely, more likely the sincere flowers try to be memorable while free-loading flowers try to be forgettable

For flowering plants, it's a vital evolutionary design, for us, a pretty sight. This is the nexus Deutsch finds between design and art.

What does he mean, "hard to vary?"

I had to mentally fill in what he means by "hard to vary". By this point in the book I think I basically got what he meant, but he never says what he means by it in so many words. So here's my guess as to what he means by "hard to vary" as it applies to art.

What is it about art that he's saying is hard to vary? You could easily (say) play a wrong note in a Beethoven piano sonata or paint a stupid moustache on the Mona Lisa. That's not hard.

So is he saying it's hard to vary on the receiver's side? That by itself makes no sense. Of course art doesn't vary on the receiver's side, it's the artist who can make it vary, not the audience.

But if I understand rightly, it is nevertheless the audience that delineates what is "hard to vary". We can perceive some sensations and patterns easily, some with difficulty, and some not at all. Far more sophisticated than insects in many ways, but real perceptual powers and perceptual limitations nonetheless.

So an oeuvre is hard to vary if it has cornered a niche in perceptual space from which the easily-made variations produce something not much like the oeuvre. The easy variations give wrong notes and not new tunes, as it were.

It almost seems circular. Varying an oeuvre that's hard to vary produces one that is less hard to vary. That's not a good criterion for "hard to vary".

But it's really about the interaction between ease of variation and subtle perceptual powers. Varying an oeuvre in an easy way, say by changing the pitch of one note, produces something that our subtler perceptual powers see as grossly different, say, by messing up an otherwise good match to an established motif and not leading anywhere.

So if I understand right, he's saying that quality in art is precisely the same thing as being hard to vary in light of the audience's perceptual powers.

This is a good theory

It adds up to the first compelling theory of art that I have seen. It lets subjective perception into the picture, but avoids the post-modern notion that it's all subjective and "ugly is the new pretty". It's properly grounded; the concepts that it's built from are universal, not parochial, and can't be accused of being merely disguised synonyms for beauty. And most importantly, when I hold it in mind while listening to music, it seems to apply reasonably to what I'm hearing.