Life, Programming, Everything

Either OOP or Liskov (choose one)

2011-08-24T17:09:00.000-07:00

A while ago I read some Abadi-Cardelli, and illustrated what I learned by an example how Java does not have subsumptions principle (that is, if A is a subtype of B, an instance of A can be safely substituted everywhere where an instance of A is required).

So I had posted a blog entry with the example.

There's another post on this on blogger.

A deeper look into the issue can be found in "Is the Java Type System Sound? by Sophia Drossopoulou and Susan Eisenbach.
The paper shows that no, it is not, and also builds a sublanguage of Java where subsumption holds.

From this article I've got the following demonstration sample:


    class A {}

    class A1 extends A {}

    class B {

          char f(A x) { System.out.println("f(A." + x + ")"); return 'f'; }

          int f(A1 y) { System.out.println("f(A1." + y + ")"); return 12345; }

          void g(A1 z) { System.out.println("Called g"); System.out.println(f(z)); System.out.println("out of g"); }

          void h(A u, A1 v) { System.out.println("Called h"); System.out.println(f(u)); System.out.println(f(v)); System.out.println("out of h"); }

    }



    @Test

    public void testJavaSubsumption() {

        new B().g(new A1());

        new B().h(new A1(), new A1());

   }

The output is here:


Called g

f(A1.pigi.examples.library.tests.QueriesTest$A1@6526804e)

12345

out of g

Called h

f(A.pigi.examples.library.tests.QueriesTest$A1@42b1b4c3)

f

f(A1.pigi.examples.library.tests.QueriesTest$A1@20d2906a)

12345

out of h

I wonder though how long will the Earth population hold to the popular belief that one can have both OOP, with reasonable enough "dispatch", and substitution principle. One cannot.

Questions?

P.S. Actually, the issue was discussed in details By Oleg Kiselyov a while ago: http://okmij.org/ftp/Computation/Subtyping/.

Generic Data Model

2011-07-30T10:11:00.001-07:00

Generic Data Model

Introduction

15 Years ago I had a problem designing a database that was supposed to hold data from various questionnaires; the questions were slightly varying every time and had no
regular structure, reflecting the weird ways of thinking of marketing people. The solution was to produce something more or less generic, storing “entities” and “attributes” separately.

(there was some discussion of xml and corba, now totally irrelevant)

Tables

The model consists of three tables: ENTITY, ATTRIBUTE, CONTEXT.

`ENTITY` Table

This is the main table in the database:

create table ENTITY (PK long, CLASS varchar, CREATED timestamp);

All the entities that we are going to have stored in our database have a representative in ENTITY table. An entity represents an object of our model. An object has an inalienable property, class. The term ‘type’ would probably suit better. An entity cannot change its class; actually, all the fields in entity record are read-only.

`ATTRIBUTE` Table

This table contains attributes of the entities. Records consist of name-value pairs and reference ENTITY table:

create table ATTRIBUTE (ENTITY long, NAME varchar, VALUE varchar);

The usage of this table is probably obvious. Note that if NAME is null, it means that the attribute contains the value of the entity itself. Two other fields are non-null.

`CONTEXT` Table

On one hand, this table can be considered as containing all the collections of the database; but on the other hand, the purpose of this table is wider. It contains all the naming contexts, and it can be used for navigation as well as for storing master-detail relationships.

create table CONTEXT (NAME varchar, OWNER long, MEMBER long, MEMBERID varchar);

Here NAME is the name of the context. If you are interested in collections, it is probably the name of collection owned by OWNER. OWNER is obviously the entity that owns the context, the “master”. MEMBER points to the member of the collection; in this case MEMBERID is irrelevant. But we can consider this as a Hash, in which case MEMBERID becomes a key, and MEMBER is the corresponding value. In the Naming Service paradigm, MEMBERID is the name of the entity MEMBER in the context NAME.

Conclusion

These days the idea of key-value pairs has become ubiquitous; it was not so in 1996 or in 2001 when I wrote this. So I'm dropping the argument in favor of this, now obvious, solution.

Chain Calls in Java - a better solution

2011-07-15T23:22:00.000-07:00

A while ago I wrote "Java Solutions: inheriting chain calls"; it was about what to do if we want to make it possible to write calls like


return new StringBuffer().append("Now is ").append(new Date()).append(", and ticking...").toString();

and be able to subclass at the same time.

See, the problem is that if you setter returns this:


  MyBaseEntity withExcitingNewFeature(ExcitingNewFeature f) {
    features.add(f);
    return this;
  }

and then you subclass MyBaseEntity, like MyDerivedEntity extends MyBaseClass, you won't be able to write


  MyDerivedEntity mde = new MyDerivedEntity(entityId).withExcitingNewFeature(feature);

Since, well, the class is different.

So in my previous post I suggested to make MyBaseEntity type-dependent (that is, have a generic):


 public abstract class MyBaseEntity<T extends MyBaseEntity>

and declare a method


   abstract T self();

So that every subclass declaration would look like this:


  public class MyDerivedEntity extends MyBaseEntity<MyDerivedEntity>

and would define


  MyDerivedEntity self() {
    return this;
  }

Yes, it works. And probably for 2008, with is now ancient history, when slow people slowly typed their slow code, not caring about the speed of development... in short, it was long ago.

Now there's a better solution. No need to redefine self() in all possible subclasses. That was just stupid. The only place where it should be defined is the base class:


  T self() {
    return (T) this;
  }

And no need to declare MyBaseEntity abstract.

There's also a bug in that old post; the generic type should have been bounded, as Ran noted in his comment.

Of course all setters should look like this:


  MyBaseEntity withExcitingNewFeature(ExcitingNewFeature f) {
    features.add(f);
    return self();
  }

2 eggs and 100 floors

2011-06-19T20:00:00.000-07:00

Everybody seems to know this "Google Interview Problem": (quoting )

"There is a 100-story building and you are given two eggs. The eggs (and the building) have an interesting property that if you throw the egg from a floor number less than X, it will not break. And it will always break if the floor number is equal or greater than X. Assuming that you can reuse the eggs which didn't break, you need to find X in a minimal number of throws. Give an algorithm to find X in minimal number of throws."

A naive programmer would first apply binary search for the first egg, then linear search for the second egg; a less naive one would try to apply Fibbonacci sequence.

Now what would happen if we just start with floor 50? We will waste the first egg, most probably, then walk up with the second one, trying each floor. What would be the number of throws in this case? We Don't Know. One would say it would be 51, but there's no reason to believe it. The only case you'll need to throw 51 times is if the first egg does not break, but we will start throwing the second egg from floor 51, 52, etc, all the way to floor 100. Would anybody do it? No.
We would divide it into halves again, right?

The other reason is that, hmm, maybe we find the right floor earlier? But what's the probability?

Right. To calculate the number of drops, we need to know the probability distribution. It is not specified in the problem. More, the problem does not even specify what exactly we are optimizing. Suppose we have a million of such buildings (and 2 million eggs, 2 per each building); what would be the good strategy? Of course we would like to minimize the average search time, not the maximum possible. If we want to apply this kind of solution to real-life problems, we need to minimize the average.

But we don't know the probability distribution! One possible (real-life) distribution is that the egg breaks at the height of an inch, so the first floor is already out of luck. But then we can modify the problem, using Faberge eggs and a 100-floor doll house.

Well, but an interviewee would not go there right away. Another good choice is to take a square root of 100, and try the first egg with the step of 10 floors, and the second egg with the step of 1 floor. A popular (and wrong) answer would give 18 to 20 as the maximum number of attempts, and 10 as an average number of attempts. Actually, the average number of tries would be 11.

The popular "right" answer that you can find on the web gives this sequence of floors to try:
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

I will not repeat the proof here, since the proof assumes we know the problem we are solving, and I state that we don't. I mean, if we are talking about the maximum number of attempts, then 14 might be a good choice, but the problem never says this is about minimizing the maximum number of attempts, right? As somebody noticed, the minimal number of throws is either 0 (for real-life eggs and floors) or 1, for the lucky ones that are not allowed in Vegas casinos.

What I suggest to do is try to minimize the average number of throws, in the assumption of uniform distribution.

So, strictly speaking, we have values from 1 to 101, and the probability of the egg to break at floor n but not at n-1 is 1/101. Why 101? We are still not sure about floor 100, but if we had values 1..100, then it would follow that we'll have a breakage at floor 100, just because the sum of all probabilities should be 1.

Now, with this distribution, we can calculate an average number of attempts for the run of n floors (in the assumption that the egg breaks at floor n): it is (n+1)/2 - 1/n. You can calculate the formula yourself. In Scala, the calculation looks like this:


def linear(n: Int) = (n + 1.) / 2

For the first suggestion, that is, trying floor 51 and then going linear, we would have 27.(2277) attempts on average (you could also try first floor 50 and see that this is a little bit worse).

How did I calculate this? See, this strategy involves:
- throwing 1 egg;
- with the probability p1=51/101 going linear from floor 1 to floor 50;
- with the probability p2=50/101 going linear from floor 52 to floor 100.

The average number of tries is 1 + linear(51) * p1 + linear(50) * p2.

We can extend this formula for a sequence of attempts, using the following Scala code:


def forSequence(s: List[Int]) = ((0., 0) /: s.reverse) ((a,b) => { val c = a._2 + b; (a._1 * a._2 / c + 1 + linear(b) * b / c, c)})

That is, taken a list of steps, we calculate the average using recursive formula, combining the previous average with the formula for linear seach.

If we try it for the "square root search", forSequence(List(10,10,10,10,10,10,10,10,10,11)) gives 11.0; for the scientifically recommended sequence 14,13,..., forSequence(List(14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 1)) gives 10.47 as an average number of attempts. Not bad; and makes sense.

But can we do better? To figure out what's the optimal sequence, we need to apply dynamic programming... unless we know the right formula; I don't. By the way, did you notice this last jump from 4 to 1 in the "scientific" sequence? Looks suspicious; it might be better to spread this jump throughout the sequence.

My solution is this: we have the right answers for the very short sequences, like 1, 2, or 3 floors; now we will need, for each subsequent number, to find the right first step, how many floors to skip; the next step is already optimized. Since this involves a lot of backtracking, I had to introduce caching of the intermediate results, splits and averages. This is Scala, and caching function is very easy to write:


def cached[K,V](f: K => V) : K => V = {
       val cache = new scala.collection.mutable.HashMap[K,V]
       k => cache.getOrElseUpdate(k, f(k))
     }

the f() in the code is evaluated lazily - on the need-to-know basis.

Honestly, one would need to use Y-combinator, but I made a shortcut, and wrote the solution like this:


val best: Int => (Double, Int) = cached((n: Int) =>
                          if (n < 4) (linear(n), 0) else
                                          (for (k <- 2 to (n/2)) yield
                                              (1 // for the first ball
                                               + linear(k) * k / n 
                                               // average number of throws if 
                                               // the first ball breaks, with the probability of this, k/n
                                               + best(n-k)._1 * (n-k) / n, 
                                               // avg number of throws if 
                                               // the first ball does not break, with the probability
                                               k // this is the step at which we throw the first ball
                                            )).min) // minimize using default pair comparator

Here best is a function; it takes building height and returns two numbers: the average number of tries and the floor to try with the first ball. It uses cache. For the case of less than 4 floors the answer is linear. Otherwise, we try steps between 2 and half the height and see which one gives the best result.

To dump all intermediate steps, I had to write this:


def bestSteps(height: Int): (Double, List[Int]) = {
  val first = best(height)
  (first._1, if (height < 4) Nil
             else first._2 :: bestSteps(height - first._2)._2)
}

What we do here is collecting the steps; it returns the price (average number of throws) for a given building height, as well as the list of steps between floors in case the first egg does not break. The result is this:


(10.43,List(14, 12, 11, 10, 9, 9, 7, 7, 6, 5, 4, 3))

See, we beat the "scientific" (but cheap) result, and the steps suggested are more in harmony with the nature of things, are not they?

Q.E.D.

Monad Genome, part 1

2011-05-05T19:56:00.000-07:00

Intro

Recently I started looking into the origin of computer science monad, and found out that at least some of them originate in pretty simple things. Like segments of simplicial category Δ (for a better explanation/definition, see MacLane, p.175). Here I'll give a couple of examples, Option and Reader monads, how they derive from a very simple subcategory of Δ.

0, 1, 1+1

I'm going to introduce a very simple category, consisting of three, well, sets: empty, singleton and a union of two singletons (1+1), together with two arrows, 0 → 1 and 1+1 → 1:

There's not much to talk about this category; you can think of it as living in the category of all sets, but actually any category with finite limits and colimits contains it.

Now I'll show how it generates two popular monads.

Option Monad

Given an object X, if we add X to each part of the diagram (a), we get this:

which is exactly Option Monad.

Exception Monad

First, we multiply the diagram (a) by E:

Then we can do the same trick as in Option Monad, add an X:

This is Exception Monad.

Reader Monad

Given an X, we can build the following diagram by applying X^- functor to the diagram (a):

Which is, simply speaking, just

Now this can be used to build the following diagram, for any A:

Do you see Reader diagram? It is the functor , with all the natural properties that follow from the naturality of the morphisms above.

This post is work in progress; comments are very welcome.

Church Numerals in Scala

2011-04-28T12:13:00.000-07:00

As everyone knows (see http://en.wikipedia.org/wiki/Church_encoding), in pure lambda one can define natural numbers out of nothing, like this:

0 ≡ λ f λ x . x
1 ≡ λ f λ x . f x
2 ≡ λ f λ x . f (f x)
3 ≡ λ f λ x . f (f (f x))
etc.

At our BACAT meeting yesterday, there was a question, for typed lambda, how can one express natural numbers, and also how can one interpret them in a Cartesian-closed category?

The answer to this question turned out to be trivial, but we also had managed to express it in Scala:

class TypedLambda[T] {
  type TT = T => T
  type Church = TT => TT
  val cero: Church = f => x => x
  def succ(n: Church) = f => n(f) compose f
  val uno = succ(cero)
  val dos = succ(uno)
  val tres = succ(dos)
}

Looks neat, eh?

The alternative approach can be found in Jim McBeath's post.

Notes on my relations with CT

2011-01-02T13:49:00.001-08:00

Zaki suggested me to write something on this topic...

So, what happened to me... In several stages.

1. I'm 19, a student in Leningrad University (that's USSR, now called Russia), and I attend a special course on homological algebra. Professor Yakovlev starts it with a short intro into category theory, a topic nobody heard of. I was overwhelmed. The thing that generalizes groups and sets and whatever. Diagrams, wow. Commutative diagrams, diagram chasing, wow. The rest was not so interesting; abelian categories, exact diagrams, hom, tensor product, ext and tor... oh whatever. In a couple of years I decided not to go into algebra.

2. I am 24, working as a programmer, trying to pick up some "science". Somewhere (where?) I see a title of a paper, "Applying Category Theory to Computer Science". Wow. My eyes are open. Here it is; database structures, they are just pullbacks. Programs, they are diagrams, are no they? Okay, nobody hears me; and more, there's no way I can get the paper. So just have to guess.

3. I am 27; me and my friends are camping somewhere in the forests of Novgorod region. Vodka, talks... I mention category theory as a good tool for perceiving comp. sci. Andrey responds by inviting me to a category seminar that they have at Technological Institute in Leningrad. Wow! I join them.

4. Several years of studying categories and toposes; MacLane's Categories for the Working Mathematician - I get the microfilm, and print it, samizdat style, in tinest possible print, for the participants. It costs 10 roubles each (like 3 bottles of vodka, if you know what I mean).

5. Andrey's friend is married to a relative of Vonnegut. So this friend, he is an otkaznik, and his American wife stays with him for several years, raising a kid, painting, just being patient. Meanwhile, after one of her trips back to US she brings Johnstone's Topos Theory... and on another trip she brings "Lolita". I devour both books. Have made hand copies of Topos Theory. Twice.

6. Andrey suggests to try to calculate topologies (and, of course, logics), over some specific finite categories; he is specifically interested in Delta3, the initial segment of simplicial category. I write code first in Basic, then figure out that the calculation for delta3 would take 2 weeks. Rewrite it into Fortran; now it's just a couple of days. So I rewrite the core parts (like enumerating subsets, calculating cones and limits) into Assembler. We have the list of 31 Grothendieck topologies over delta3 in just four hours. Meanwhile we calculate topologies for simple categories, like linear segments, commutative squares... a strange thing is discovered, on many occasions the number of topologies is 2^n, where n is the number of objects. That's for posets.

7. I prove it that for finite posets this is the case, and a little bit more. Then I spend months trying to find a typewriter with English letters (KGB is watching); used one in Hungarian trade mission, and one in the Institute of Hydrology (where global warming was then starting). Then I spend some time figuring out how to send the paper, then a KGB colonel suggests a solution, and I use it. It's published in Cah.Topo.Geom.Diff. The hardest part was deciphering French written notes on proofs.

8. I meet Yakovlev; for him, it is all a) "abstract nonsense", and b) it can't be that the result is not known yet.

9. I generalize this stuff to Karoubian categories over Boolean toposes (Booleanness is necessary) and send it to Johnstone. Johnstone, it turned out, was working on a similar problem, from the other end. So I spend the next 15 years trying to get the proof in the opposite direction - that if... then the category is Karoubian. That's how I did not do anything else. At least I tried.

10. The seminar meanwhile had died out - the guy, Stepanov (can I call him professor? something like that... he was not), had married and moved to Novorossiysk, a pretty criminal place; there he died in strange circumstances.

11. Now here in California, the word "monad" rings the bell. So I honesty try to put it in the proper perspective, writing some kind of "tutorials" and "talks", writing again the code that calculates stuff, opening presheaf.com, and ready to talk to anybody willing to listen.

12. And now we have BACAT, a category seminar where we can discuss things. And this is great.

my codecamp talk here

2010-10-16T19:36:00.000-07:00

Monads, Functors, Functions, Java/Scala on Prezi

Running with SBT

2010-09-19T00:04:00.000-07:00

So, you are tired of your slow and half-dumb ides, ok, what can you do to make your scala dev cycle more agile? Use sbt.

First go to that website, and download the jar. Store it somewhere. Write a shell script or a bat file with the only command:


java -Xmx512M -jar wherever you store the jar/sbt-launch-0.7.4.jar

Go to your project directory and run your sbt there. It will ask you some questions regarding what version of Scala you want to order, the name of your project, the like. Then it will create an sbt project in that directory. Now the project expects the directory structure to follow maven rules of the game. You don't have to. Go to the directory named project, create a directory named build, and within that directory create a scala file Project.scala, that looks something like this:


import sbt._

class CategoriesProject(info: ProjectInfo) extends DefaultProject(info)
{
//  lazy val hi = task { println("Categories in Scala"); None } // that's for fun
  override def mainScalaSourcePath = "src" // your source directory
  override def mainResourcesPath = "resources" // fiik what is this for

  override def testScalaSourcePath = "tests" // your tests directory
  override def testResourcesPath = "test-resources" // fiik what is this for
  override def outputDirectoryName = "bin" // your output directory
}

Additionally, check out lib directory in your project; it probably contains already some stuff that sbt believes it needs - that is, scala-compiler.jar, and scala-library. Copy over there the other jars you believe you need. There should be a way to reference them where they are, but I have not figured it out yet.

Now start sbt again.

If you give it a command ~test, it will cycle through compiling the code and running the tests, automatically detecting what to compile and guessing what tests to run. As soon as you save a source file, sbt wakes up and does the job.

So... I love it... as do many other scala people.

Dealing with Infinities in Your Code - 3

2010-09-12T21:19:00.000-07:00

Here I had introduced countable sets, and here I had demonstrated how we can build a union of two countable sets. Now is time for Cartesian products.

Suppose we have two sets, {'A', 'B'} and {1, 2, 3}. Their product will look like this: {('A',1), ('A',2), ('A',3), ('B',1), ('B',2), ('B',3)}. It is pretty easy to build: iterate over the first set, and for each element iterate over the second set. In Scala it is pretty easy:


for (a <- setA;
     b <- setB) yield (a, b)

The problem is that if the second component (setB) is infinite, we will never be able to iterate over all elements. Let setB be, for instance, the set of all natural numbers, N. In this case the product setA x setB will be yielding ('A',0), ('A',1), ('A',2),..., and will never switch to pairs like ('B',i). We have to do something about it.

Say, in the case when only one component is infinite, we could think about changing the order of the loop, first iterating over the infinite component.

That won't work actually. We cannot always know for sure if a set is finite or not. Halting problem, you know. So we have to figure out how to do it in a general way, without losing common-sense efficiency for the finite case.

The solution has been known for over 100 years, and is called Kantor Pairing Function.
In this picture: you see this function enumerating pairs of natural numbers in the following order: (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0)... - you got it.

In our case we have two essential differences: first, the sets we have are not necessarily finite, and second, elements are not retrievable by their "sequential numbers"... meaning, it's possible, but it is horribly ineffecient: to reach element #1000, we need to rescan all the elements from #1 (or rather #0, since natural numbers and array indexes start with 0). So we also do not need a fancy formula for Kantor Pairing Function (see link above), the formula that calculates product elements by their sequential numbers. All we need is a way to iterate over elements in the right order.

Okay, let's first write the factory method for Cartesian products:

def product[X, Y](xs: Set[X], ys: Set[Y]): Set[(X, Y)] = {
    val predicate = (p: (X, Y)) => xs.contains(p._1) && ys.(p._2)
    setOf(
      kantorIterator(xs, ys),
      xs.size * ys.size,
      predicate
    )
  }

The predicate definition is extracted just for readability purposes. What's important here is kantorIterator that is supposed to work with any combination of finite and infinite countable sets.

Since we do not have direct access to the elements of the sets by their indexes, we will, instead, keep the rows in iterators. Note that we can build a queue of such iterators. Let's call them rows. What the algorithm does is this:
- push row0 to the iterator queue
- yield (row0.next, y0)
- push row1 to the iterator queue
- yield (row0.next, y0) (first iterator from iterator queue)
- yield (row1.next, y1) (second (last) iterator from iterator queue)
- push row2 to the iterator queue
- yield (row0.next, y0) (that is, (x2,y0))
- yield (row1.next, y1) (that is, (x1,y1))
- yield (row2.next, y2) (that is, (x0,y2))

and so on: every time we reach the end of the queue, we push the next row iterator into the queue, reset the vertical iterator, and start all over.

The problem arises when one of the iterators is out of elements.

We have two possible cases.

Case 1. The vertical iterator halts. In this case we stop pushing new iterators into the queue, so that the size of the queue is the size of the vertical component.
Case 2. the horizontal iterator halts. The vertical one may be infinite or not, we have to shift it. E.g. if we build {'A', 'B','C'} x N, we will be producing ('A',0), ('B',0), ('A',1), ('C',0), ('B',1), ('A',2), ('C',1), ('B',2), ('A',3).... Note that after ('C',1) row0 is out of elements, and this row should be dropped from the queue. At the same time the beginning element of the vertical iterator should be shifted, so that the next loop will be not 0,1,2, but 1,2,3. In such a way we go all along the vertical iterator.

Here's the code:

def kantorIterator[X, Y](xs: Iterable[X], ys: Iterable[Y]): Iterator[(X, Y)] =
    new Iterator[(X, Y)] {
    var iterators: Queue[Iterator[Y]] = Queue()
    var xi = xs.iterator
    var yi: Iterator[Iterator[Y]] = Iterator.empty
    var shift = 0
      
    def next = {
      if (!yi.hasNext) {
        if (xi.hasNext) {
          iterators enqueue ys.iterator
        }
        yi = iterators.iterator
        xi = xs.iterator.drop(shift)
      }
      
      val yii = yi.next
      val y = yii.next
      val res = (xi.next, y)

      if (!iterators.isEmpty && yii.isEmpty) {
        iterators.dequeue
        shift += 1
      }

      res
    }

    def hasNext = !xs.isEmpty && !ys.isEmpty &&
      (xi.hasNext || (!iterators.isEmpty && iterators(0).hasNext))
  }

hasNext covers all the cases of empty components.

I probably have to mention that you won't be always able to iterate over all the subsets of a countable set. If the set is finite, it's okay, its powerset is finite; but if it is not, here you can find Kantor's proof that the powerset of an infinite countable set is not countable.

Dealing with Infinities in Your Code - 2

2010-09-12T18:42:00.000-07:00

In this post I had introduced the idea of having countable sets in your code. Next I want to show how we can combine countable sets producing new countable sets.

We have two operations, union and Cartesian product. Let's start with disjoint union - the union of non-intersecting sets.

If we expect our sets to be both finite, there's nothing special here. The predicate checks whether an element belongs to one set or another; the iterator iterates over the first set, then the second.

What if one or both of our sets is/are infinite? The predicate seems to be still okay: we just check whether the element belongs to one of the sets. But the iterator... if the first set is infinite, our naive iterator will never reach the second set. I mean, not in this universe; we will need transfinite numbers readily available, which is well beyond the power of modern computers or most of modern humans. What can we do then? Well, we can alternate over two iterables.

Let's look at the code:

def union[X, X1 <: X, X2 <: X](set1: Set[X1], set2: Set[X2]): Set[X] = {
    lazy val parIterable = new ParallelIterable(set1, set2)
    lazy val size = if (set1.size == Integer.MAX_VALUE ||
                        set2.size == Integer.MAX_VALUE) {
                      Integer.MAX_VALUE
                    } else {
                      set1.size + set2.size
                    }
    setOf(parIterable,
          size,
          (x: X) => (x.isInstanceOf[X1] && (set1 contains x.asInstanceOf[X1]))||
                    (x.isInstanceOf[X2] && (set2 contains x.asInstanceOf[X2]))
    )
  }

What we have here? A new iterable, a new size evaluator, a new predicate. We can ignore the size evaluator; nothing is calculated here until someone requests it. The predicate is obvious; the only new thing is ParallelIterable. We need it to iterate over the union of two countable sets (rather, over two iterables) in a smart way:


class ParallelIterator[X, X1 <: X, X2 <: X](
          iterator1: Iterator[X1],
          iterator2: Iterator[X2]) extends Iterator[X] {
    var i2 : (Iterator[X], Iterator[X]) = (iterator1, iterator2)
    def hasNext = iterator1.hasNext || iterator2.hasNext
    def next = {
      i2 = (i2._2, i2._1)
      if (i2._1.hasNext) i2._1.next else i2._2.next 
    }
  }

Note that we flip i2, so it changes from (iterator1, iterator2) to (iterator2, iterator1) and back every cycle.

As a result, in the output we just interleave members from the first component with the members of the second component. What is important here is that we do not make any assumptions regarding which iterator is finite and which is infinite; if one component does not have more elements, fine, we continue scanning the other one.

This was probably pretty simple; now we have to deal with Cartesian products, that is, the set of all pairs (x: A, y: B) where x is from the first set and y is from the second set; with no assumptions regarding the finiteness of the said sets.

That would be the next part.

Dealing with Infinities in Your Code - 1

2010-09-09T23:12:00.000-07:00

These days it is not unusual to have an infinite sequence in a computer system. The idea is that while the sequence grows, the system upgrades, and there's no limit unless we make certain assumptions like accepting non-standard arithmetics. Then even sequences that we expect to be finite may turn out to be infinite - like Goodstein's sequence.

Still, it seems like in a foreseeable future we will only encounter countable sets. They are not necessarily infinite; any finite set is traditionally considered countable, that is, equal in size to a subset N, the set of natural numbers. The set of all real numbers, R, is a typical example of an uncountable set (it is a continuum). (Whether there is a set of intermediate size, between N and R, depends on what axiom we assume. If we assume it exists, it exists; if we assume it does not exist, it does not. Quite an eye-opener for people that use to treat Mathematics as a provider of absolute truths, right?)

What's good in a countable set is that (assuming set-theoretical axioms) one can list its element in such a way that any arbitrary element may be eventually reached. (That's due to another axiom, the Axiom of Choice - it says that we can introduce linear order in any set. If we don't assume this axiom - then we cannot.)

When I worked in Google, one of my favorite interview questions was "given an alphabet, write a code that would produce all words that сan be built based on this alphabet". Then I had to explain that when words are built out of alphabet, it does not mean each letter is used at most once. It does not. Then I had to explain that by "producing all words" I mean writing a code that could reach any word that can be built out of the alphabet. For instance, given {A,B}, the sequence "A", "AA", "AAA", etc would be infinite, but it won't constitute a solution: it will never reach letter 'B'.

In my work I limit myself with sets as they are presented in Java or Scala.

One particular problem is that, usually, an implementation of Set is supposed to have a method that returns the set's size. Not sure I know why. Probably it has something to do with array reallocations... some technical stuff. Because see, if you know that your set is infinite, you are safe, you can always return, by the rules of Java, Integer.MAX_VALUE; but what if you do not know? Say you have a function that takes another function, calls it subsequently until it halts (e.g. fails), and records the times it takes each call. What would be the size? We have to solve Halting Problem to know the answer.

On the other hand, isEmpty is a pretty decent method; it could easily belong to Iterable: to check if an Iterable is empty, one has to just get its Iterator and call its hasNext.

Also, it would be good to supply a set with a predicate, similar to what they do in Zermelo-Fraenkel Set Theory: according to the Extensionality Axiom, two sets are equal iff they consist of the same elements. Not having to count to infinity (or futher) to check if an element belongs would be a good advantage. E.g. for the set of all odds the predicate would not have to scan through all odd numbers from 1 to the given one; just check its last bit.

So that's why I came with a set that is defined by its

iterable that enumerates the elements;

predicate that "efficiently" checks if a value belongs to the set

size evaluator that, when called, tries to evaluate the size of the set

I use Scala for coding these days; hope it is reasonably pretty:

private def setForIterator[X](sourceIterator: => Iterator[X], sizeEvaluator: => Int, predicate: X => Boolean): Set[X] = {
      new Set[X] {
        override def contains(x: X) = predicate(x)
        override def size = sizeEvaluator
        override def iterator = sourceIterator filter predicate
        override def isEmpty = !iterator.hasNext
        override def -(x:X) = requireImmutability
        override def +(x:X) = requireImmutability
        def map[Y] (f: Functions.Injection[X,Y]) : Set[Y] = f.applyTo(this)
        def map[Y] (f: Functions.Bijection[X,Y]) : Set[Y] = f.applyTo(this)
        override def filter(p: X => Boolean) = filteredSet(sourceIterator, (x: X) => predicate(x) && p(x))
      }
    }

  def setOf[X](source: Iterable[X], sizeEvaluator: => Int, predicate: X => Boolean) =
    setForIterator(source.iterator, sizeEvaluator, predicate)

Had to override a bunch of methods declared in trait Set, to avoid any immediate calls of size evaluator or assuming that the size is known.

Here's how, using this class, we can define the set of natural numbers:

val N = setOf(new Iterable[Int] {
    def iterator = new Iterator[Int] {
      private var i: Int = -1
      def hasNext = true
      def next = {i += 1; i}
    }
  },
  Integer.MAX_VALUE,
  (x: Any) => x.isInstanceOf[Int] && x.asInstanceOf[Int] >= 0)

That's it for now. In the next part I'll talk about how to combine two countable sets. It is an old fact that a union and a product of two countable sets are countable; we will need a code that behaves according to this knowledge.

iterable, tree, monad, foundation axiom

2010-07-20T11:08:00.001-07:00

Everybody knows now that linear data are bad for performance. But in Java everything is based on Iterable, with the idea, deeply rooted in math, that we can only visit the content of X if we iterate over it (enumerable sets etc), that is, have an epimorphism from N to that X.

Well, that's stupid. All we need is foundation axiom to hold.

In plain words, a tree is good as well, but a tree can be scanned in parallel.

But programmers of the world were trained to write a loop every time they see a plurality of something.

But the loop does not actually mean it should be interpreted sequentially.

If you write

for (x <- container) {
}

it only means that the job is done inside a monad.

That's why you should think monad, eh. That's why enumerables are XX century. Foundation axiom is way more powerful.

I actually can even prove it, but only for a Boolean base topos.

(oneof the sources)

A Better Option for Java

2010-05-08T14:49:00.001-07:00

Just posted an article, A Better Option for Java

How I Installed a TV Antenna

2010-04-18T21:48:00.000-07:00

I live in South San Jose; recently we have discovered that now that we have fast Internet, WII and Netflix, we already have access to hundreds of movies, so what do we need a tv for? Local news. Okay, but they are being broadcast for free, in hdtv, just install an antenna on the roof and go.

Started with looking up our area on antennaweb: entered my address and it gave me directions and this map.

The site also say that frequency ranges have colors, and that I have to choose an antenna that has the right colors.

Since there's over 60 miles from my home to San Francisco, the only reasonable choice was ChannelMaster 4228D - they sell it at Fry's.

Turned out that to install it I need more than just this box. I need a pole and the stuff to attach the pole to the roof. Below I explain what I did.

I bought a 5-foot piece of "black pipe" at Lowe's (here on the picture the end of the pipe), a cap for the pipe and the piece which I want to attach to the roof.

You need a cap on top so that rain won't penetrate the pipe.
Before attaching the bottom piece to the roof, I had patched the area below with roof coating, to avoid leaks:

Now we need these things from OSH (electric department and bolts and nuts department) to attach to the pole the guy wire that will hold it.

This is how the top of the pole looks like with all the stuff attached:

I have attached two eye screws to the sides of my roof, and two went straight into the roof:

After I drilled the hole for the screw, I patched it so the rain won't get in:

Now I have to attach the guy wire to the pole and to the eye screws; for this I use clams:

The guy wire does not go all the way through from the top of the pole to the screws. I cut the wire and attached turnbuckles that allow me to tighten the wires later:

This is how it looks with antenna attached to the pole using brackets, and the guy wires tightened with turnbuckles.

Now it's time to get the cable into the house. I bought a 25-foot white coaxial cable, connected it to the antenna's amplifier, got it along the roof and the wall.

I had measured the position of an existing tv socket inside the room, and used a long drill to drill through the wall to get to the socket as close as possible.

I used this bushing for the cable to get through. Bought it at Lowe's.

Had to cut the bushing, or else how would I get the cable through?

When I got the cable through the wall, I applied a good amount of clear caulk to make sure no water gets through.

I was lucky, the cable got exactly where I wanted it.

So all I had to do is connect my tv, scan the 56 channel it found and enjoy the show.

And you know what? It sucks. I don't have a dvr on those channels, so there's no way I can pause it, or get any information regarding what is it about... no recording. And the channels... what nonsense people watch, omg.

So, was it all worth it? Probably. I had fun with my antenna.

Here's a photo I took from a digital channel:

Hidden Monads in Scala

2010-03-29T15:14:00.001-07:00

Actually, not monads, just functorial stuff. But programmers seems to be unaware of the fact that a monad is a special kind of functor, so...

In Scala, one can define a functor something like this:

  trait Functor[X] { 
    def map[Y](f: X => Y): Functor[Y]
  }

All we need here is map. Lists have map, Options have map... The natural use of a map is to apply it to a function. Like this:


  def loop[X,Y](f: Functor[X], a: X=>Y) = f.map(a)

In Scala, loops can work as maps. And if you are a Haskell programmer, you'll immediately recognize your monadic notation:

  
  def loop[X,Y](f: Functor[X], a: X=>Y) = for (x <- f) yield a(x)

These two are exactly the same.

Praise Scala!

Update: see recent blog entry on monads by Luc Duponchel for a lot more details.

Topics in Coding Style

2010-03-24T15:22:00.000-07:00

While at Google, I believed in two things: peer code review and unacceptability of ascii art in the code.

Peer code review means you are supposed to show your stuff to somebody in your team before submitting it. So, when you want to submit the stuff in the end of the day (yes, all unittests pass), you are supposed to hold on, wait for half a day (the next day), not touching the code, get into a discussion, and then, eventually get through with it. Which means the code should be pretty solid. No way you would go ahead submitting something working but halfway through, or something that is in the process of being formed, in transition, work in progress.

That's bad. I found myself spending several days forming my ideas regarding how I can possibly specify binary output format in JSON, so that the format can be sent From Above to the client when requirements change (say, a new format is eventually implemented by busy/lazy server guys). If I had to submit a fully-implemented, fully thought-out, neat-looking code, it would take a couple of weeks. Thinking, prototyping, discussing, including three days of explaining how the stuff works and what JSON is, and why it is okay to use strings as keys, etc.

That's about pair programming too. Imagine pair theorem proving. Two guys are placed together by a senior mathematician, say, Grisha and Misha, and told to prove a theorem by the end of the week.

What I want to say: get the fuck off programmers' backs. If they want to work together, let them work together. If they want to work alone, let them work alone. If they want to be agile, let them be agile; if they want to be locally-convex, let them be locally-convex. On the other hand, if you, the manager, know better how to write code, how come you cannot produce in a week anything comparable to what a junior programmer can easily concoct in 30 minutes? Just kidding.

Now ascii art. Programming is art. Ascii art is a part of programming art. If a programmer thinks that his or her code reads better formatted the way the programmer formatted it, challenge this, the fact that it is, not the fact that it does not follow Coding Style Guide Laws.

A Brief History Of Single Exit

2010-03-08T14:59:00.001-08:00

Many many years ago people were writing their code mostly in FORTRAN, but also in PL/I. They were told by their teachers not to use too many functions or subroutines, because each call and return is very expensive, compared to plain goto statement.

So the brave programmers managed to write functions or subroutines several thousand lines long; these people were considered smart and very important, compared to the junior kind who only could write a hundred or two lines in one function or subroutine.

Then something bad started happening: the code did not work. Or it did work until you start changing it. As a result, two philosophies were born:
1. Do not change anything;
2. Write structured code.

Structured programming consisted of using functions of reasonable sizes with reasonable structures. No jumps into the middle of a loop, no jumps out of looks into another loop or into a conditional statement; no exits out of the middle of your subroutine.

Then, later, it was discovered that it is just goto statement that should be blamed. So people started setting limitations, depending on their taste and creativity.

- do not goto inside another subroutine;
- do not goto into a loop or a condition;
- do not goto upstream.

The idea of totally abandoning goto was considered too extremist: how else can we make sure that we have only one exit out of a subroutine or a function?

Well then, why do we need just one exit? There were two reasons:
- it was really hard to set breakpoints on all the exits scattered over half a thousand lines;
- how about releasing resources, like closing files, etc?

So it was decided, more or less unanimously, that we have to a) maintain some kind of "response" or "result" code, and b) goto the bottom of our subroutine and exit from there, using the "result code" to decide whether we should do something to close up our activity.

Since later goto was more and more discouraged (although you can find a goto in Java libraries source code), the kosher solution was suggested that was keeping some kind of integer shitLevel flag; everywhere in your code you are supposed to check the level, and if it is close to the fan, you should proceed without doing anything.

This ideology penetrated into Pascal, C, C++, and, later, Java. And only later people started thinking about structuring their code better.

Like making it smaller.

Besides, some languages have finally block that can be used to neatly close all the streams that may remain open.

These two changes, much smaller code and finally block make "single exit" ideology meaningless. Why does one need a specific variable to pass around if we can just return it? If the whole method is half a screen, is it really hard to find other exit points? Is not it safer to use finally that will release your resources in any case, as opposed to that bottom of the method that may never be reached. Just look at this:


   public final static void doit() {
        try {
            throw new NullPointerException("npe");
        } finally {
            System.out.println("Finally!");
        }
    }

Here is basically the same argument, specifically for Java.

Dispatch by Return Type: Haskell vs Java

2010-01-20T15:55:00.000-08:00

If you are a Haskell programmer, this is all trivial for you; but if you are a Java programmer, you would ask yourself two questions:

is it possible?!
is it safe?!

Let's start with Java. In Java, we have pretty nice polymorphism which includes method overloading: using the same method name with different lists of parameters:

int length(Iterable i);
int length(Collection c);
int length(String s);
int length(T[] array);

Not that we need these specific methods, but for the sake of argument. What happens when compiler/JVM finds the right method to call: it finds the method that matches best the list of parameters, and in the case of confusion will either show an error message or (during runtime) throws an exception.

One thing is impossible, though: defining two methods that differ only in return type, something like

int parse(String source);
long parse(String source);
boolean parse(String source);

In principle, we could, in most cases, deduce which method we want, by the context: if we write

int n = parse("123");

the compiler could guess, of course, what exactly we mean... but no, it is not allowed.

So, a Java programmer, given a method name, expects to always get the same return type (even if signatures are different, we are used to expecting the same return type anyway).

Now, how about generics? What if we define

interface Ubiq {
   T parse(String s);
}

then implement the interface and apply it to the strings?

Now we have a problem. If we define

class UbiqInt implements Ubiq<Integer> {
 ...
}

then we explicitly specify the type, and will be forced to write

int n = ubiqInt.parse("12345");

then all the polymorphisms is gone now.

What if we define a class that is still parameterized by T?

class UbiqImpl<T> implements Ubiq<T> {
 ...
}

Then the question is, how exactly can we have several different implementation of parse(String) in one class? We cannot, and we are stuck.

Now, what is different in Haskell that makes it possible? Let's take a look at Haskell code:

class Ubiq a where
  parse :: String → a

instance Ubiq Bool where
  parse ('T':cs) = True
  parse _        = False

instance Ubiq Integer where
  parse ('0':cs) = 2 * parse(cs)
  parse ('1':cs) = 2 * parse(cs) + 1
parse _ = 0

check :: Bool → Integer → String
check b n = if b then show n else "no nothing"

tryme = check (parse "Tautology") (parse "1001")

What happens here? We defined a typeclass Ubiq, which is a vague analog of Java interface; and then we have a couple of implementations. But both implementations define known types, Integer and Bool to be implementing Ubiq. So that, from now on, if we have an expression parse(String) in a position where is expected to have an Integer type, then the compiler finds the appropriate implementation and "calls" it when needed. How does it happen? We just know the expected return type, so it is not hard to figure out. In cases when the compiler is confused, like in an expression show(parse("something")), the compiler will need a hint:

*Main> let x = parse("T")

:1:8:
    Ambiguous type variable `a' in the constraint:
      `Ubiq a' arising from a use of `parse' at :1:8-17
    Probable fix: add a type signature that fixes these type variable(s)

(please do not hesitate to write your comments, questions, objections)

Subclass and Subtype in Java

2009-11-30T18:29:00.000-08:00

Here I just want to get together a pretty much widely-known information; somehow it escapes you if you just read Java books or google the internets. And what I was looking for was an example (hence a proof) that subclassing in Java is not always subtyping, or some kind of proof that it is.

I am talking specifically about the state of affairs in Java. We may try to do the same trick in Scala; my point here though was to have a real-life, although contrived, example of how subclassing is different from subtyping, and Java is a easy target.

First, definitions (informal, as well as the rest of this post).

Types in Java.
Java has the following kinds of types:

primitive (e.g. char)
null
interfaces (declared with interface keyword)
classes (declared with class keyword)
array (declared with [square brackets])
type variables (used in generics)

Subclassing: declaring one class to be a subclass of another (class ... extends ...) - this allows a subclass to inherit functionality from its superclass

Subtyping: A is a subtype of B if an instance of A can be legally placed in a context where an instance of B is required. The understanding of "legally" may vary.

Many sources state firmly that in Java, a subclass is always a subtype. Opinions that a subclass is not always a subtype are also widespread; and that's obviously true for some languages: Self type is a good source of subclass not being a subtype confusion; we do not have Self type in Java.

In Java 5 a covariant return type inheritance was added: if class A has a method that returns X, and its subclass B declares a method with the same name and parameter list (meaning, parameter types), and returning a subclass of X, then this method overrides the method in A.

In addition to this, arrays are also covariant: if A is a subtype of B, then A[], in Java, is a subtype of B[].

This last feature allows us to create an example showing that no! Subclasses in Java are not always subtypes! See:



public class Subtyping
{
    interface A
    {
        A[] m();
        void accept(A a);
    }

    interface B extends A // subtype of A
    {}
    
    public static void main(String[] args) {
        A a = new AImpl(); // see AImpl below 
        B b = new BImpl(); // see BImpl below
        // now note that B is a subtype of A.
        a.accept(a); // this works; substitution is trivial
        b.accept(a); // this works too (substitution is trivial too)
        a.accept(b); // oops, this fails! b, being a subtype of a, is not accepted at runtime
    }

    static class AImpl implements A {
        public A[] m()
        {
            return new A[]{this};
        }
        
        public void accept(A a)
        {
            a.m()[0] = this;
        }
    }

    static class BImpl extends AImpl implements B{
        public B[] m()
        {
            return new B[]{this};
        }
    }
}

So there, this code demonstrates a subclass that is not legally a subtype. By 'legally' here I mean that the code always throws a Java runtime exception without adding any client precondition predicates.

Here's a good discussion of this issue:


public boolean lspHolds(Object o) {
  return o.toString().contains("@");
}

Not Just Subtyping

2009-11-16T23:32:00.000-08:00

I've been trying to figure out how come the only relationship between types we use to encounter is "sub". Type a is a subtype of type b. Validated by subsitution principle.

If we limit ourselves with "sub", we'll have infinite arguments on whether a square can be considered as a subtype of rectangle; whether a colored-point can be considered a subtype of point; whether an int can be considered, under certain conditions, as a subtype of float; whether, in Java, if A implements B, A is a subtype of B. Opinions differ.

I think we should look deeper and maybe consider this case by case.

Is square a rectangle? Seems so; the objection being that when we start stretching the rectangle, not every square remains a rectangle. Modification is a weird thing. Even in simple cases, i = 1, then (i == 1) becomes true; but it is not actually true, because next moment i = 2, and the expression is false. No temporal logic transforms true into false, there's something wrong there. But if we discard modification, we can state this: each square 'is a' rectangle. We have an injection. Two different squares treated as rectangles remain different.
Is colored-point a point? This is a totally different case. The world of colored-points is different from the world of points: it is bigger. Yes, a colored-point can be used instead of a point in a substitution. So, in a sense, it 'is a' point. But two different colored-points can become the same point if we forget about their color. Each point 'is a' projection of a colored-point, and eachcolored-point can be treated as a point. So what we have here is a projection here.
Let's try to implement an unordered-pair. We can do it by taking a pair type and then defining equality in such a way that (a, b) == (b, a). Again, we have a projection, but in this case we went the other way around: not building a new type by adding a dimension, but discovered a new type by defining an equivalence relationship between pairs. So what we have here is a factorization.
In the case of int -> float, we have a more general case. Not all operations are preserved; not all floats come from ints, and not all two different ints map to two different floats. Still, it is a legal type transformation, done usually by default, called coercion.
In Java-like languages, if a class implements an interface, it thus declares that it can be used in any context where the interface is required. It projects itself into the realm of the given interface, and that's all we know; the "true nature" of the class implementing an interface remains obscure.
In the context of 5., the Java keyword "extends" is meaningless. That is, in reality it has many meanings: "borrows the functionality", "implements the same set of interfaces", "has access to internal namespace". Non of this has anything to do with types relationships.
'is a' actually has many meanings too. We probably never can be sure whether A 'is a' B: we should always ask: "in which contexts" (that is, "what do you mean?"). If we look at this:

the pyramid here is neither a square nor a triangle. But when projected, it can be percieved as one. If we say "he's a soldier", it does not mean that's all the person is; what we mean is just a projection.

So, how about substitution? We can substitute A with B if we know the mapping that maps B into the context where A should be present. If we are talking about coercion (and we know that an int is not a subtype of float), for instance, we can substitute a float with an int value if coercion is legal. In this and other cases, our ability to substitute means we know a canonical mapping.

Now examples.

Injection. Take types A and B; build A+B, a union. Some languages support unions, some don't. Some support them implicitly, like Scala with its case classes. By definition, there are canonical inclusions from A and B into A+B; so it would be logical to call A and B subtypes of A+B.
Projection. Take types A and B, and their product, A×B. One can represent A×B as the type of pairs (a, b), with a of type A and b of type B. There are two projections from A×B to A and B. Neither A nor B can be seriously called a subtype of A×B, of course. They can be considered as a special case of factor-types. Below is another example of factor-type.
Surjection. Given A×A, a type of pairs (a1, a2), we can build a type of unordered pairs by equalizing (a1, a2) with (a2, a1). This gives us an equivalence relationship, and a projection from A×A to A×A /2, the type of unordered pairs.
Enum surjection. Suppose we build an enum class for Rainbow. It turns out in different cultures the number of colors is different. In China, Japan, Russia, there are seven colors, while in some other countries (US for instance) there are 6. Two colors, light-blue and dark-blue, in Asian rainbow, both map to just blue in US rainbow. So every time we pass a US rainbow instance to a function, we can as well coerce an Asian rainbow ("substitute") into US version, using the standard mapping. It is similar to projection, where the receiving side has no clue about the hidden multiplicity of possible parameter values.

In computer science there is a variety of terms that are supposed to denote this variety of "-typing", but somehow they either are all called kinds of subtyping or declared not to belong to the "-typing" realm. I suggest to apply pretty simple categorical notions, so that things just look simpler and more manageable.

a sample comonad

2009-08-31T21:10:00.000-07:00

Comonads still look a little bit enigmatic to programmers; I'm going to show a practical example from which one can start perceiving the notion.

First, definition. A comonad is dual to monad; which may or may not be a good explanation. So, okay, a formal definition.

A comonad is a functor T: A → A

ε_x: T(x) → x

and

Δ_x: T(x) → T(T(x))

together with three conditions similar to monadic conditions:

a) For Δ_x: T(x) → T(T(x)) and ε_{_T(x)}: T(T(x)) → T(x) we should have ε_{_T(x)} _° Δ_x = Id_T(x)

b) For Δ_x: T(x) → T(T(x)) and T(ε_x): T(T(x)) → T(x) we should have T(ε_x) _° Δ_x = Id_T(x)

c) For Δ_x: T(x) → T(T(x)), Δ_{_T(x)}: T(T(x)) → T(T(T(x))), T(Δ_x): T(T(x)) → T(T(T(x))) we should have T(Δ_x) _° Δ_x = Δ_{_T(x)} _° Δ_x

Here's a nice compact comonad implementation in Haskell; I hope the author won't mind my quoting the code:


class Functor w => Comonad w where
extract :: w a -> a
duplicate :: w a -> w (w a)
extend :: (w a -> b) -> w a -> w b

So, in this notation, the axioms will look like this:


extract . duplicate      == id
fmap extract . duplicate == id
duplicate . duplicate    == fmap duplicate . duplicate

The author of the code also specifies axioms for extend, but I find it superfluous; it is enough to have functoriality and the comonad laws actually.

I wanted to bring a good example of comonad. Here how one could be produced.

If we have a monoid M, we can have a comonad of functions from a given M to sets. A monoid is a... okay, a set that has associative multiplication and unit defined: 1: → M, m: M×M → M, such that m(a, 1) = m(1, a) = a.

So, let's take the functor which to each set X maps a set of functions from a given monoid M to X. It is known to be a functor; now, how come functions from a monoid to a set form a comonad? I would not go into details here, and will just demonstrate how we have a comonadic structure for one specific monoid, ℕ, the monoid of natural numbers: [0..∞).

So what we have is a functor that, given a set X, builds the set of all sequences in X. I plan to demonstrate that this functor is a comonad.

X ↦ {(x₀, x₁, ...)}

We need to define ε_{_X} (extract and Δ_x (duplicate).

ε_{_X} can be defined like this: ε_{_X}(x₀,...) is x₀;

Why so? A general definition of extract for the case of monoid is taking f(0) for a function f: M → X (a composition 1 → M → X ).

and Δ_x can be defined like this: Δ_x(x_i,j) = x_i+j

Again, this is because T(T(X)) in our case is the set of functions M → M → X, which is equivalent to the set of functions from M×M → X. For each f: M → X we can define M×M → M → X by composing the monoid multiplication (which is addition if we are talking about natural numbers) and f.

Or, in other words, duplicate (x0, x1, ...} == ((x0, x1, ...), (x1, x2, ...), ...); (extract . duplicate) (x0, x1, ...) will return the first element, (x0, x1, ...), that is, it is the same as id.

If we apply fmap extract to ((x0, x1, ...), (x1, x2, ...), ...), we will get a sequence of first elements of each sequence, that is, again, (x0, x1, ...).

Conclusion

In my view, Haskell community, probably for the sake of being closer to the people, oversimplifies IO.

In my view, while output is a monad, input can be interpreted as a comonad. When a machine is taking input, it has no control over external environment, it just consumes; the input acts on the machine. To make the input comonad look like a monad, the authors use tricks, forcing the whole evaluation happen inside not the main Haskell category, but its image under a certain functor... but I don't think this is the right place and time to discuss adjoint functors here.

Why Monoids?

2009-06-23T16:43:00.000-07:00

I sincerely plan to explain in simple terms what's all this fuss about monoids, why we suddenly need these primitive structures, and how to make them available in Java.

A monoid is one of the simplest notions of algebra. Slightly oversimplifying, it consists of elements that have a multiplication operation a*b defined on them, and a neutral element e, such that e*a == a*e. Multiplication should be associative (a*b)*c == a*(b*c), but not necessarily commutative (a*b != b*a). If you can't imagine non-commutative multiplication, think of matrices... or of spatial rotations. The order counts.

A simpler example would consist of integer numbers and addition playing the role of multiplication. 0 is the neutral element with respect to addition, so there.

Now why would we need this structure? It turned out that if you have to add up a billion, or a quadrillion of integers, you may be interested in doing it by distributing the operation over several (or ~700 000, in the case of Google) machines. Adding up a quadrillion of integers may be not that interesting; but multiplying a billion of matrices is a different, and more challenging, story.

And why can we distribute it among the thousands of computers? We can do it all thanks to the associativity. (m₁*m₂*...*m_k1*m_k1+1*m_k1+2..*m_k2*...*m_n) is the same as

(m₁*m₂*...*m_k1)*(m_k1+1*m_k1+2..*m_k2)*(...*m_n), and we can calculate intermediate results (shown in parentheses here) on different machines, then aggregating them together; we can do it in cascade, whatever we choose. The strategy does not influence the result.

The following Java class defines, or rather declares the necessary functionality:

public abstract class Monoid<X>
{
abstract X unit();
abstract X m(X x, X y);

public X fold(Iterable<X> source) {
   X result = unit();
   for (X x : source) {
       result = m(result, x);
   }
   return result;
}

public X fold(X[] source) {
   X result = unit();
   for (X x : source) {
       result = m(result, x);
   }
   return result;
}
}

We can use it to add numbers, strings, matrices; to multiply numbers or matrices; to concatenate lists and join sets.

Monoid<Set<T>> setMonoid = new Monoid<Set<T>> {
   public Set<T> unit() {
       return Set<T>.EMPTY;
   }

   public Set<T> m(Set<T> a, Set<T> b) {
       Set<T> c = a.clone();
       c.addAll(b);
       return c;
   }

Of course using all this for the data that we have in memory of one single machine. But, as I said before, we can actually delegate the monoid's fold operation to the computing cloud, and have the list deployed somewhere in the big file system, and let the cloud partition it. The result will be the same; and all this due to the monoidal properties of our concrete classes and operations.

on Variance

2009-06-14T10:29:00.000-07:00

I'll try to explain to practicing programmers what this variance means, and how it is related to the famous and frequently misunderstood "Liskov principle".

Say we have the following types: A, B, A1 and B1, where A1 is a subtype of A, and B1 is a subtype of B. In Java it would look like this:


class A {
  ...
}

class A1 extends A {
  ...
}

class B {
  ...
}

class B1 extends B {
  ...
}

Now let's build a class of pairs:


class Pair<X, Y> {
  X first;
  Y second;
}

If we compare Pair<A, B> ab; and Pair<A1, B1> a1b1; we see that it is natural to expect that a1b1 should be assignable to ab, but not vice versa: the components can be cast in one direction only. A1 is a specialization of A; B1 is specialization of B, and so the Pair<A1,B1> is a specialization of Pair<A,B>. This is what is called covariance: specialization transforms into specialization.

And if you are a fan of "Liskov's substitution principle", you can see that a Pair<A1, B1> can always be used ("substitute") where a Pair<A, B> is required.

Now the opposite case, contravariance. Suppose we have two functions declared like this:


  B f(A a);
  B f1(A1 a1);

(I use Java syntax; the two lines above mean that both functions return B).

Which one can replace which? See, f1 cannot be used instead of f: what if we pass something that is not A1? f1 does not know what to do with it. But the opposite is okay: we can always use f where f1 is required: any A1 can be viewed as an A.

When we deal with object methods, not just plain functions, one hidden parameter is always present: the object itself. So that a method declared as


  class A {
    ...
    C f(B b);
    ...
  }

actually is a function defined on pairs (A, B), and takes values in C. This function is contravariant in both parameters. Contravariance in the first (hidden) parameter is an essential part of OOP. Take a look at the following code snippet:


  class A1 extends A {
    ...
    C f(B b) {
      println(getClass().getName() + " called with " + b.getClass().getName());
    }
  }
  ...
  A instanceOfA = new A1();
  ...
  instanceOfA.f(b);
  ...
}

This is Java, and Java uses dynamic dispatch (that is, all methods are virtual), and so the method of A1 is called in place of method f of A. Method f of A is substituted with a method of A1; contravariance made it possible.

Note that, since a method is always contravariant on its owner object, all getters, for instance, are contravariant: a superclass can call them, and the owner object, which is an instance of a subclass, can substitute the superclass in any context.

(Many thanks to M.Abadi and L.Cardelli's "A Theory of Objects" for explaining the OOP part to me.)

inheritance, delegation, decoration, gravitation

2009-04-04T18:07:00.000-07:00

I think I have some ideas regarding what is the problem with inheritance and, specifically, multiple inheritance. Let's start with geometry.

A plain pedestrian perceives 2-dimensional space as some kind of lawn, where you can walk back and forth, and know your position by measuring the distance towards the fence. (That's like the Bible's universe, except that the Bible universe is 3d, 100 miles by 100 miles by 5 miles.) So people think, aha, I can describe the ball as a point in space, 10 feet from the back fence ('x'), 30 feet from the left fence ('y').

Then 3d comes into the picture. We programmers don't deal with 3d. We deal with element's position in the window. But there's 3d out there. And the third dimension is spectacularly different. If you place a point somewhere, it will fall to the surface. The height from which it falls is called 'z'. It is like the other two coordinates, but it's different, because it falls if you don't hold it. So the point in space is the point on the lawn decorated by the height at which it is currently held. Be real, the force of gravitation will drag it to the surface anyway, it is not natural for an average point to have a height.

In your code you write it like this:


class Point {
  double x;
  double y;
}

class ThreeDPoint extends Point {
  double z;
}

The software design purists tell us that we should write


class ThreeDPoint {
  Point point;
  double z;
}

This way we won't be mixing the two kinds of points and, say, checking whether an instance of ThreeDPoint lies between two Points... even equality checking may be problematic, where the Point(1, 2).equals(ThreeDPoint(1, 2, 3)) but not vice versa. Josh Bloch told us in his books that equality should be symmetrical.

I don't know if you read in some other book that it does not make any sense to define equality for objects of different types. Let me try to show why. You have one function that takes user name and returns user age (doing some magic, like guessing that a Sue should be over 70 and a Ryan should be under 35); the other function takes an integer number and returns its decimal representation. Can you seriously discuss the idea of checking whether these two function can have a common value for a certain argument? (In a sense they actually can: a one-year-old Japanese boy named Ichi, for instance).

But let's return to the three-dimensional space. Now that we have successfully (double-successfully, since we have two solutions) defined a three-dimensional point, let's thing about rotating the coordinates. Not that we do it here on our flat Earth, but on the space station they do it all the time. Have you heard, they have no gravitation! There's no special 'z'; all three dimensions are made equal. And the idea that a three-dimensional point is some kind of extension of the idea of a two-dimensional point does not fly in space. What do you think is the location of, say, Mars? What is the height of Mars? Mars does not have height. Even our Earth does not have height.

To switch from one coordinate system to another we need to do what? Shift and rotate. Now it turns out that the three dimensions are made equal; the space is (actually it is not, but that's the latest news from astrophysics) homogeneous and isotropic (or else we would be able to save the energy, according to a certain theorem).

Our representation of a 3-d point as a decoration of a 2-d point just does not work.

For a mathematician I'll express it like this: R³ is isomorphic to Rx(R×R) but not equal. See the difference? For a programmer, it looks like this:

(x, y, z) can be modeled as (x, (y, z)), or as ((x, y), z), or as (y, (z, x)), or as ((z, 42), (y, 55, x)) - but they are all different things. Only gravitation was forcing us, earthlings, to think of (x, y, z) as of ((x, y), z).

There are relations between 2d and 3d, though. A 3d point can be projected to 2d. (x, y), and (x, z), and (y, z) are all projections to the appropriate planes.

But what I wanted to say is this. If you are thinking of decorating your class with some more attributes, think again. Probably what you actually need is another class with natural projections (they are called views in SQL) to your old class. We tend to think that some attributes are more "external" than the "internal" attributes. Say, an object id is in the heard of your design, right? Are objects "decorations" of their ids? We don't think so, do we?

Oh, and about the "diamond inheritance problem". Do you know how relational databases solve this problem? Check it out. It's called "normalization".

Cursor vs Flyweight

2009-03-15T14:29:00.000-07:00

It is a pretty frequent problem: you need a million instances (ok, a billion if you are on a larger machine), and all the data are available, but you are not sure about overloading your Garbage Collector (I'm talking about Java, but in C you also have to deal with pesky memory issues... I guess). Will the GC handle a million (or a billion) of records that just come and go?

A known Flyweight Design Pattern, in its Java incarnation, suggests to do this: create an instance and cache it in a WeakReferenceMap, as if the weakness of the reference saves any memory at any given moment. No; we still have to create all those instances:


for (Record r : allMyRecords) {
  // do something
  // forget about record r
}

A typical implementation would be like this:


RecordSet allMyRecords;

where


class RecordSet implements Iterable<Record> {
  ...
  Iterator<Record> iterator() {
    ...
    Record next() {
      // get the record from somewhere and return it:
      Record theRecord = new Record(...);
      return theRecord;
    }
    ...
  }
  ...
}

Say, we assume that all the data are actually in memory, but have a different form, so that for a record class like


interface Record {
  long id();
  String firstName();
  String lastName();
  String phone();
  String email();
}

we actually have some kind of storage that keeps the data:


Map<Long, String> names;
Map<Long, String> phones;
Map<Long, String> emails;

If we implement the class Record so that it stores first/last name, phone and email, we duplicate a lot of data; so maybe it would be enough to store just something, just an id, and retrieve the rest on demand. For this, we will have a more-or-less lightweight implementation:


class LightRecord implements Record {
  long id;
  String phone() { return phones.get(id);}
  String email() { return emails.get(id);}
  String firstName() { return names.get(id).split(" ")[0];} // not very smart
  String firstName() { return names.get(id).split(" ")[1];} // not very smart either
}

So we will store at least million (a billion) longs, and probably more. Wasting our memory, even if GC takes care of it. On a cellphone you probably should not count on gc.

So what can we do? Here's a solution that does not take any extra memory. It's like a cursor. It points to an imaginary record. Of course this record changes all the time, so if you want to really save an instance, do it via copy constructor. Otherwise, use it and forget it:


class RecordSet implements Iterable<Record> {
  long currentId;
  Record currentRecord = new Record() {
    String phone() { return phones.get(currentId);}
    String email() { return emails.get(currentId);}
    String firstName() { return names.get(currentId).split(" ")[0];}
    String firstName() { return names.get(currentId).split(" ")[1];}
  }    
  ...
  Iterator<Record> iterator() {
    ...
    Record next() {
      currentId = ...;
      return currentRecord;
    }
    ...
  }
  ...
}

So, the only time a constructor is called is when the iterator is created. Neat, eh?

The solution is not new. It is probably 50 years old. It is just properly rephrased in Java.

Incrementally calculating factorsets (Java class)

2009-01-07T16:13:00.001-08:00

Recently I encountered a problem of calculating a factorset, given a set and a binary relationship. If you ask wtf is binary relationship, it is a predicate defined on pairs of elements:

interface BinaryRelationship<X, Y> extends Predicate<Pair<X, Y>> {}

Well, of course Java does not have type variables, so that one cannot interchange these two definitions... poor, poor Java programmers, poor, poor me.

But anyway.

Oh, and if you ask wtf a factorset is, let me introduce.

Definition
A binary relationship R on set A is called reflexive if aRa for all a∈A.

Definition
A binary relationship R on set A is called symmetric if aRb => bRa for all a∈A, b∈A.

Definition
A binary relationship R on set A is called transitive if aRb && bRc => aRc for all a∈A, b∈A, c∈A.

Definition
Given a set A and a reflexive, symmetric, transitive binary relationship R on A, an equivalence class over R is any such subset A₁ of A that first, if x∈A₁ and y∈A₁ then xRy, and second, if x∈A₁ and xRy then y∈A₁

Definition
Given a set A and a reflexive, symmetric, transitive binary relationship R on A, a factorset A/R is defined as a set of all equivalence classes over R.

Example
Take integer numbers, and let nRm if n - m is divisible by 2. We'll have just two equivalence classes, odd numbers and even numbers. By the way, guess why two equivalence classes never intersect.

Anyway.

One can calculate a factorset even if the relationship is not symmetric, reflexive or transitive. Just produce a symmetric, reflexive transitive closure, and factor over it. The problem is, calculating a transitive closure may be costly. So, for practical reasons, I have implemented factorsets in a non-lazy way. And then I realized that, on some occasions, to provide the necessary relationship, I had to build a set of pairs, and then provide the relationship that checks if a pair is in that set, and then calculate the factorset that transitively closes the relationship. Pretty stupid, why not just do it incrementally?

That's how I got this class:

public static class FactorSet<X> {
  Set<X> set;
  Map<X, Set<X>> equivalenceClasses;

  /**
   * Builds an initial factorset, given the domain set.
   *
   * @param set domain set.
   */
  public FactorSet(Set<X> set) {
    this.set = set;
    equivalenceClasses = new HashMap<X, Set<X>>();
    for (X x : set) {
      equivalenceClasses.put(x, Set(x));
    }
  }

  /**
   * Builds a factorset of a given set, by the transitive closure of a given relationship.
   *
   * @param set base set
   * @param r binary relationship
   */
  public FactorSet(Set<X> set,  BinaryRelationship<X, X> r) {
    this(set);
    factorByRelationship(r);
  }

  /**
   * Given a <code>BinaryRelationship r</code>, merges equivalent classes if they
   * contain elements that are in <code>r</code>.
   *
   * @param r the binary relationship. Does not have to be symmetrical or transitive.
   */
  public void factorByRelationship(BinaryRelationship<X, X> r) {
    for (X x1 : set) {
      for (X x2 : set) {
        if (x1 == x2) {
          continue; // skip same value
        }
        if (equivalenceClasses.get(x1) == equivalenceClasses.get(x2)) {
          continue; // skip same class
        }
        if (r.eval(x1, x2) || r.eval(x2, x1)) {
          merge(x1, x2);
        }
      }
    }
  }

  /**
   * Merges equivalence classes for two elements
   * @param x1 first element
   * @param x2 second element
   */
  public void merge(X x1, X x2) {
    Set<X> class1 = equivalenceClasses.get(x1);
    Set<X> class2 = equivalenceClasses.get(x2);
    Set<X> merged = new HashSet<X>(class1);
    merged.addAll(class2);
    for (X x3 : merged) {
      equivalenceClasses.put(x3, merged);
    }
  }

  /**
   * @return the latest version of factorset built here.
   */
  public Set<Set<X>> factorset() {
    return new HashSet<Set<X>>(equivalenceClasses.values());
  }

  /**
   * @return the function from the domain set to the factorset.
   */
  public Function<X, Set<X>> asFunction() {
    return Functions.forMap(equivalenceClasses);
  }

  /**
   * @return the domain set.
   */
  public Set<X> domain() {
    return set;
  }
}

Neat, right? Look at this unittest:

public void testFactorSet_incremental() {
  Set<Integer> set = Set(1, 2, 3, 4, 5);
  FactorSet<Integer> factorset = new FactorSet<Integer>(set);
  factorset.merge(1, 3);
  factorset.merge(3, 5);
  factorset.merge(4, 2);
  Set<Set<Integer>> expected = Set(Set(1, 3, 5), Set(2, 4));
  assertEquals(expected, factorset.factorset());
}

(Don't get confused by the functional-programming style of set constructors. Just open The Scala Book, they do it everywhere!

If you find a better way to do this thing, please let me know.

Inner Class in Java: Unexpected Volatility

2008-12-25T14:39:00.000-08:00

You probably know that if you use a value in an inner class, the evil Java compiler wants you to write "final"; people do all kinds of trick to bypass it - store date in arrays, for instance.

But relax, you do not have to write "final" if it is a member field. Look at this code:

package experimental;

import java.util.AbstractSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class VolatileConstant {

  public static void main(String[] args) {
    Iterable<Set<String>> iss = new Iterable<Set<String>>() {

      public Iterator<Set<String>> iterator() {
        return new Iterator<Set<String>>() {
          int i = 0;
          public boolean hasNext() {
            return i < 3;
          }

          public Set<String> next() {
            i++;

            return new AbstractSet<String>() {
              public Iterator<String> iterator() {
                return new Iterator<String>() {
                  int j = 0;
                  public boolean hasNext() {
                    return j < i;
                  }

                  public String next() {
                    j++;
                    return "" + i + "." + j;
                  }

                  public void remove() {
                    throw new UnsupportedOperationException();
                  }
                };
              }

              public int size() {
                return i;
              }
            };
          }

          public void remove() {
            throw new UnsupportedOperationException();
          }
        };
      }
    };

    Set<Set<String>> sss = new HashSet<Set<String>>();

    for (Set<String> ss : iss) {
      sss.add(ss);
      System.out.println(ss);
    }
    System.out.println(sss);
  }
}

You know what it prints? It's in the next line, in white color so that you have a choice not to see it.


[1.1]
[2.1, 2.2]
[3.1, 3.2, 3.3]
[[3.1, 3.2, 3.3], [3.1, 3.2, 3.3], [3.1, 3.2, 3.3]]

I am sure you can explain it, after a while, but is not it really amusing?

categories: new part posted

2008-12-14T21:30:00.000-08:00

Just posted a new part, "Category of Java Sets", in Easy Categories For Programmers.

Functions

2008-12-13T21:25:00.000-08:00

An Excuse

Well, I decided to gather all the code related to Function class in one "universe" container class, Functions. The other option would be to have a separate "package". I do not see any reason for using packages instead of container classes.

My idea regarding container classes is that it is a theory - we have constants, types, rules, axioms, all in one place. An element of theory is meaningless outside of its theory. A set does not make sense without a Set Theory.

So here we have some kind of "Functions Theory". Since functions are defined on types, which vaguely are like classes, which vaguely are like unlimited sets, we can define set-theory-like notions of Injection and Bijection. A Surjection would be nice to have too, but it has no functional influence on current programming practice: nobody knowingly builds factorsets.

Overview

Three abstract classes are defined:

Function - general functionality;
Injection - a special kind of Function, not mapping different values to one;
Bijection - invertible Function

and several useful extra classes:

Inclusion, - a Function that includes one set into another;
Id - an identity Function,
PairsToMap - takes a set of pairs, turns it into a Map;
IterableToSet - takes an iterable, turns it into a Set.

Also there are several static methods. Don't be afraid of static methods, they all belong to Functions Theory, and there's hardly a reason to override or polymorph them in any way.

Function

A Function<X, Y> declares an abstract method Y apply(X x), which obviously determines the function's behavior. In addition, Function has methods for mapping an Iterator, an Iterable, a Collection, a List. Note that there's no method that maps a Set. Why? Because if you apply a Function to a Collection, you can have repeating values.

Method toMap(Set<X) converts a Function into a Map; method forMap(Map<X, Y>) turns a Map into a Function. Static compose(f, g) method composes two Functions.

Injection

Injection is a special kind of Function: it maps different arguments to different values. Not that we can verify it; we just trust the declaration. Since a composition of two Injections is an Injection, this case is taken care of. It is.

An Injection maps a Set to a Set, so this method is there.

Inclusion is a special kind of Injection: it includes one class (set) into its superclass (superset). It maps a value to itself, casting.

Bijection

Bijection<X, Y> is a special kind of Injection: it has an inverse. So, additionally, it declares a method X unapply(Y). A composition of two Bijections is a Bijection.

Here is a sample code, where Schwartzian transform is defined:

/**
 * Given a function f, builds another function that for each x
 * builds Map.Entry(x, f(x))
 *
 * @param f function to apply
 * @return a function that builds pairs.
 */
public static <X, Y> Bijection<X, Pair<X, Y>> schwartzianTransform(final Function<X, Y> f) {
  return new Bijection<X, Pair<X, Y>>() {
    public Pair<X, Y> apply(final X x) {
      return math.cat.LazyPair.LazyPair(x, f);
    }

    public X unapply(Pair<X, Y> p) {
      return p.x();
    }
  };
}

Oh, and the code is here.

Java Solutions: inheriting chain calls

2008-12-11T21:35:00.000-08:00

Recently chain builder calls in Java have been gaining popularity, look, e.g. at this.

The idea is that you have a builder that has small configuration methods and in the end builds the right stuff. StringBuffer works like this:

 return new StringBuffer().append("Now is ").append(new Date()).append(", and ticking...").toString();

Or, more typically, something like this code:


 new TestBuilder().limitTime(1000).forPackage(this.getClass().getPackage()).skipFlaky().build().run();

This way we, first, annotate our parameters, and second, bypass the boring law that demands writing each statement on a separate line.
And of course it makes the process more flexible.

Actually, the fact that it is a builder is unimportant. We can just chain calls if every method that in the previous life was returning void would start returning this.

But there's a problem here... what if our builder is not the ultimate version, but a subclass of a superbuilder? Look at an example below:


public class ChainCalls {
 public static class A {
   A do1(String s) {
     System.out.println("A.1 " + s);
     return this;
   }

   A do2(String s) {
     System.out.println("A.2 " + s);
     return this;
   }
 }

 public static class B extends A {
   B do0(String s) {
     System.out.println("B.0 " + s);
     return this;
   }

   B do1(String s) {
     System.out.println("B.1 " + s);
     return this;
   }

   B do3(String s) {
     System.out.println("B.3 " + s);
     return this;
   }
 }

 public static void main(String[] args) {
   ((B)(new B().do0("zero").do1("one").do2("two"))).do3("three");
 }
}

See how we have to cast the result of do2()? That's because the method of class A has no knowledge that it actually works in the context of class B.

How can we deal with this? One cheap solution is to duplicate all the methods in B and call the delegate, that is, super.do1() etc. Feasible, but not very nice, not very scalable, and not very Java5-ish.

Because we have generics, and we have a so-called covariant inheritance, so that - because we can!

An anonymous contributor in livejournal.com has suggested the following solution:

public class ChainCallsCovariant {
 public static abstract class SuperA<T> {
   abstract T self();

   T do1(String s) {
     System.out.println("A.1 " + s);
     return self();
   }

   T do2(String s) {
     System.out.println("A.2 " + s);
     return self();
   }
 }

 public static class A extends SuperA<A> {
   A self() { return this; }
 }

 public static abstract class SuperB<T> extends SuperA<T> {
   T do0(String s) {
     System.out.println("B.0 " + s);
     return self();
   }

   T do1(String s) {
     System.out.println("B.1 " + s);
     return self();
   }

   T do3(String s) {
     System.out.println("B.3 " + s);
     return self();
   }
 }

 public static class B extends SuperB<B> {
   B self() { return this; }
 }

 public static void main(String[] args) {
   new B().do0("zero").do1("one").do2("two").do3("three");
 }
}

The main trick here is to encapsulate "return this", and make it generic, so that we always, in the eyes of the compiler, return the instance of the right class.

P.S. Here I've posted a better solution.

Java Compiler Warnings 2

2008-12-04T09:24:00.000-08:00

Say, somewhere in your test code, you need a list of nulls:

List<Direction> directionsWithNullValues = Lists.newArrayList(null, null, null);

Ouch! Compiler warning: unchecked generic array creation of type E[] for varargs parameter

What's going on here? An array can be created, but Java is confused regarding the type. Just cannot deduce it.

The solution is simple (although awkward):

List<Direction> directionsWithNullValues = Lists.newArrayList((Direction)null, null, null);

Java Compiler Warnings 1

2008-12-04T08:54:00.000-08:00

Since out of the 5 million Java programmers there's hardly 100 that actually know Java (I do not count myself in that holy hundred), we probably have to join our efforts (like people do at javaranch and help each other.

Here I'm going to post typical Java Compiler warnings that I encounter and fix.

So this chain letter is something like "effective java for dummies", so to say.

1. Creating generic arrays.

Out of your best intentions, you decide that instead of manually concatenating your collections, you'll have something like this:

Collection<T> concat(Collection<T>... collections) {
  Collection<T> result = new ArrayList<T>();
  for (Collection<T> collection : collections) {
    result.addAll(collection):
  }
  return result;
}

Let's forget the dubious decision of making a live arraylist out of collections of unknown nature, instead of just having a lazy collection or iterable. What's the problem here? Will our compiler complain? No. But if we try to use it, like this:

Collection<Integer> newCollection(oldCollection1, oldCollection2);

we will get a compiler warning: "generic array creation" warning. What's wrong? Here's what. When you pass around a vararg list of parameters, implicitly an array is being created. But Java does not like creating arrays of elements which type is generic. Hence the warning.

To avoid, we can just write a simpler version:

Collection<T> concat(Collection<T> collection1, Collection<T> collection2) {
  Collection<T> result = new ArrayList<T>(collection1);
  result.addAll(collection2):
  return result;
}
...
Collection<Integer> newCollection(oldCollection1, oldCollection2);

Not that I neither condone nor discuss the idea of building an arraylist - this deplorable issue is just outside of the narrow boundaries of this topic.

Keyboard Bookmarklets

2008-11-23T21:33:00.000-08:00

Find your language below, and drag the grey square to bookmarks tab in your browser.

Next time you open a page with edit field (e.g. blogger), click the bookmark in the bookmarks tab,
and here you go, the keyboard pops up.

So far it works only on Firefox, Google Chrome and Safari, though.

sq Albanian	hu Hungarian	ro Romanian
ar Arabic	il Israel(Ar,En,He,Ru)	ru Russian
hy Armenian	is Icelandic	sr Serbian
az Azeri	kn Kannada	si Sinhalese
be Belarussian	kk Kazakh	sk Slovak
bn Bengali	km Khmer	special Special (Arrows etc)
bg Bulgarian	lv Latvian	tg Tajik
hr Croatian	lt Lithuanian	ta Tamil
cs Czech	mk Macedonian	tt Tatar
et Estonian	ml Malayalam	te Telugu
fa Farsi	mr Marathi	th Thai
fi Finnish	mn Mongolian	tr Turkish
ka Georgian	no Norwegian	tk Turkmen
gu Gujarati	ps Pashto	ug Uighur
hi Hindi	pl Polish	ua Ukraine (Ua,Ru)

Questions? Write me.

What To Do with Dispatch of Static Methods for Java

2008-11-16T07:41:00.000-08:00

A problem with Java that everybody encounters from time to time is the following: static methods cannot override each other. If class A has static method m, and class B has static method m, with the same signature, there is no automatic way to figure out which method should be called.

Look at these two classes:

public class A {
  String x;

  public A(String x) {
    this.x = x;
  }
  public String toString() {
    return "A(" + x + ")";
  }

  public static A combine(A a1, A a2) {
    return new A(a1.x + " + " + a2.x);
  }
}

and

public class B extends A {

  public B(String x) {
    super(x);
  }
  public String toString() {
    return "B(" + x + ")";
  }

  public static B combine(B b1, B b2) {
    return new B(b1.x + " * " + b2.x);
  }
}

I would be nice if the right combine method would be called in each case. But no, the following code

import static A.*;
import static B.*;

public class Test {
  public static void main(String[] args) {
    A a1 = new A("a1");
    A a2 = new A("a2");
    B b1 = new B("b1");
    B b2 = new B("b2");
    A c = new B("c");
    System.out.println(combine(a1, a2));
    System.out.println(combine(b1, b2));
    System.out.println(combine(a1, b2));
    System.out.println(combine(b1, c));
  }
}

will print
A(a1 + a2) B(b1 * b2) A(a1 + b2) A(b1 + c)

Why does the second call prints B(b1 * b2)? Just because the method combine that takes two arguments of type B is available via static import B.*.

Interesting, we know the objects types, but dispatch is done statically. Can we fix it?

One awkward solution is to use reflection: add the following to A

public static A smartCombine(A a1, A a2) {
  Class class1 = a1.getClass();
  try {
    Method method = class1.getMethod("combine", class1, a2.getClass());
    System.out.println(method);
    return (A)method.invoke(null, a1, a2);
  } catch (NoSuchMethodException e) {
    throw new RuntimeException(e);
  } catch (InvocationTargetException e) {
    throw new RuntimeException(e);
  } catch (IllegalAccessException e) {
    throw new RuntimeException(e);
  }
}

then call it like this:

System.out.println(smartCombine(b1, c));

and we'll get

B(b1 * c)

Okay, not the best solution anyway. We won't seriously add a "smart" version to each static method.

So maybe we should not use static? Should we hate static? Let's define instance methods, in class A:

public A combineWith(A other) {
  return new A(this.x + " | " + other.x);
}

and in class B:

public A combineWith(A other) {
  return new A(this.x + " & " + other.x);
}

public B combineWith(B other) {
  return new B(this.x + " && " + other.x);
}

Now let's try this:

System.out.println(b1.combineWith(b2));
System.out.println(b1.combineWith(c));
System.out.println(c.combineWith(b1));

We well see the following:


B(b1 && b2)
A(b1 & c)
A(c & b1)

What went wrong? The first case is ok, but how about others? The second case is due to the simple fact that the dispatch is done statically. So the compiler sees the parameter is an A, and calls the method that takes an A.
How about the next one, we use two instances of B, but still? It is trickier. The compiler sees an instance of A, and calls a method combineWith of class A; this method takes an A as a parameter. At runtime, since c is an instance of B an appropriate method of B is called; but the signature still is combineWith(A), and this sad truth destroys our plans.

So, what can we do? double dispatch should help, right? Here is a good example of how to use double dispatch in in Java.

Unless you do not know already, the trick is this. We have class A and and its subclass B, and a parallel hierarchy, X and its subclass Y. These two hirerachies interoperate, and we want to make sure that if, say, an instance of B works with an instance of Y, it would recognize this even if the instances are passed around as instances of A and X.

For double dispatch to work, class A should be aware of classes X and Y; similarly, class X should be aware of A and B.

Not so in our case; we have just one hierarchy, and of course our A is not aware of its subclass B.

So our naive attempt of using double dispatch will fail.

First, add to A the following:

static A combine(A a1, A a2) {
  return a1.combineFollowedBy(a2);
}

A combineFollowedBy(A other) {
  return other.combinePrecededBy(this);
}

A combinePrecededBy(A other) {
  return new B(this.x + " | " + other.x);
}

and add to B a similar code:

A combineFollowedBy(A other) {
  return other.combinePrecededBy(this);
}

A combineFollowedBy(B other) {
  return other.combinePrecededBy(this);
}

A combinePrecededBy(B other) {
  return new A(this.x + " && " + other.x);
}

A combinePrecededBy(A other) {
  return new A(this.x + " & " + other.x);
}

As I already said, this won't bring happiness in this world:


A(a2 | a1)
A(b2 & b1)
A(b2 & a1)
A(c & b1)

The reason is obvious: nowhere in our call sequence for, say, c and b1 we have a chance to call B.combineX(B)

So, what should we do? For a case like this I have only one suggestion: use instanceof.

We don't need double dispatch. Let's simplify A:

static A combine(A a1, A a2) {
  return a1.combineFollowedBy(a2);
}

A combineFollowedBy(A other) {
  return new A(this.x + " | " + other.x);
}

And make B a little bit less kosher:

A combineFollowedBy(A other) {
  return other instanceof B ?
      combineFollowedBy((B)other) :
      super.combineFollowedBy(other); 
}

A combineFollowedBy(B other) {
  return new B(this.x + " & " + other.x);
}

Now it works. A small stylistic sacrifice for fixing the lack of functionality.

Java's Strong Typing

2008-10-24T21:15:00.000-07:00

In a typical case of user application dealing with some kind of "apache javabean properties access", we still want to have generics help us with strong typing, to keep code safe. For this, we introduce a parameterized class Property<T>. And write something like this:

public class ClientCode {
  Object model;
  public ClientCode(Object model) {
    this.model = model;
  }

  public void businessLogic() {
    Property<String> name = new Property<String>("userName", model);
    Property<Date> dob = new Property<Date>("dateOfBirth", model);
    Property<Boolean> isGood = new Property<Boolean>("isGood", model);

    if (isGood.value() && dob.value().before(new Date(1990, 10, 24))) {
      System.out.println("One good adult user: " + name.value());
    }
  }

  public static void main(String[] args) {
    new ClientCode("ignore me").businessLogic();
  }
}

Naive but natural. And now the implementation of Property<T>:

package common;

public class Property<T> {
  String name;
  T value;

  public Property(String name, Object container) {
    this.name = name;
    this.value = (T) "hello world";
//        org.apache.common.weird.helper.util.BeanAccessUtil.
//            getProperty(container, name);
  }

  public T value() { return value; }
}

Looks pretty convincing, right? But surprise! Do you think this code will throw a ClassCastException from within Property<T>? Seems like it should; we even have a variable that, in case of it being type Date, cannot accept a string in assignment. Right?

Wrong...

As you know, generic type information is lost in compilation. As a result, all the compiled class knows about value type is that it is something. It is actually an Object, and can accept whatever is assigned. More, the method value() also returns an Object. But the client is sure, due to generic parameterization, that it returns the expected type. But it does not. And the exception is thrown right in the client code.

Experimenting with Covariance and Contravariance in Java Generics

2008-10-20T08:07:00.000-07:00

Here I'll just publish the code that demonstrates what is accepted and what is not by the compiler when you use generics. Not many comments, since most of the code is extremely trivial.

Oh, and definitions. An expression is contravariant in variable x of class X if x can be substituted with an instance y of class Y which is a subclass of X. An expression is covariant in variable x of class X if x can be substituted with an instance y of class Y which is a superclass of class X.

E.g. (a = f(b)) is contravariant in b and covariant in a.

Let's have the following class inheritance diagram ('=>' means iheritance):

E => C, D => C, C => B, B => A

In details,


  class A {
    String id;

    A(String id) { this.id = id; }
  }

  class B extends A {
    B(String id) { super(id); }
  }

  class C extends B {
    C(String id) { super(id); }
  }

  class D extends C {
    D(String id) { super(id); }
  }

  class E extends C {
    E(String id) { super(id); }
  }

And let's have an interface and a class, something similar to Map and HashMap:


  interface M<X, Y> {
    void put(X x, Y y);
    Y get(X x);
  }

  class M1<X, Y> implements M<X, Y> {
    M1() {};
    public void put(X x, Y y){};
    public Y get(X x){ return null; }
  }

The following code demonstrates a ubiquitous and pretty legal usage of covariance and contravariance.

First, the example where we vary the second parameter ("the value"), and provide an exact knowledge of its type on declaration (and instantiation):


  void testParameter2() {
    M<String, B> mSB = new M1<String, B>();
    mSB.put("", new B(""));
    mSB.put("", new C(""));
    B aa = mSB.get("");
    M<String, C> mSC = new M1<String, C>();
    mSC.put("", new C(""));
    B b = mSC.get("");
    C c = mSC.get("");
  }

Now let's try a contravariant version of wildcard in the second parameter of M. Turns out that using wildcard duly blocks some of the "expected" functionality.


  void testParameter2WithExtendsWildcard() {
    M<String, ? extends C> mSCx = new M1<String, D>();
    mSCx = new M1<String, E>();
    // Actually, only E should be accepted, but this information is lost on assignment.
    // So the next line won't compile:
    mSCx.put("", new C(""));
    // put(java.lang.String,capture#660 of ? extends common.VarianceTest.C) in
    // common.VarianceTest.M<java.lang.String,capture#660 of ? extends common.VarianceTest.C> 
    // cannot be applied to (java.lang.String,common.VarianceTest.C) 
    //
    // And we don't know if it is D (it is not).
    // So the next line won't compile:
    mSCx.put("", new D(""));
    // put(java.lang.String,capture#511 of ? extends common.VarianceTest.C) 
    // in common.VarianceTest.M 
    // cannot be applied to (java.lang.String,common.VarianceTest.D)

    B b = mSCx.get("");
    C c = mSCx.get("");
  }

Trying the same, but 'super' instead of 'extends':



  void testParameter2WithSuperWildcard() {
    M<String, ? super C> mSCs = new M1<String, C>();
    mSCs = new M1<String, B>();
    // We don't know what's hiding behind 'super', maybe it's Object
    // So the next line won't compile:
    mSCs.put("", new B(""));
    // put(capture#701 of ? extends common.VarianceTest.C,java.lang.String) 
    // in common.VarianceTest.M 
    // cannot be applied to (common.VarianceTest.C,java.lang.String)

    mSCs.put("", new C(""));
    mSCs.put("", new D(""));
    // We don't know what's hiding behind 'super', maybe it's Object
    // So the next line won't compile:
    B b = mSCs.get("");
    // incompatible types found   
    // : capture#222 of ? super common.VarianceTest.C  required: common.VarianceTest.B    

    Object any = mSCs.get("");
  }

The same with parameter 1. No surprises here:


  void testParameter1() {
    M<B, String> mBS = new M1<B, String>();
    mBS.put(new B(""), "");
    mBS.put(new C(""), "");
    String s = mBS.get(new B(""));
    s = mBS.get(new B(""));
    M<C, String> mCS = new M1<C, String>();
    mCS.put(new C(""), "");
    mCS.put(new D(""), "");
    s = mCS.get(new C(""));
    s = mCS.get(new D(""));
  }

The following example shows that it is totally useless to specify 'extends' wildcard in contravariant position:


  void testParameter1WithExtendsWildcard() {
    String s;
    M<? extends C, String> mCxS = new M1<C, String>();
    mCxS = new M1<D, String>();
    // Who knows what is the actual type of param1...
    // The following two lines do not compile:
    mCxS.put(new C(""); 
    // put(capture#701 of ? extends common.VarianceTest.C,java.lang.String) 
    // in common.VarianceTest.M 
    // cannot be applied to (common.VarianceTest.C,java.lang.String)

    mCxS.put(new D(""), "");
    // put(capture#701 of ? extends common.VarianceTest.C,java.lang.String) 
    // in common.VarianceTest.M 
    // cannot be applied to (common.VarianceTest.D,java.lang.String)


    // Same here, parameter type unknown
    // The following two lines do not compile either:
    s = mCxS.get(new C(""));
    // get(capture#897 of ? extends common.VarianceTest.C) in common.VarianceTest.M    // of ? extends common.VarianceTest.C,java.lang.String> 
    // cannot be applied to (common.VarianceTest.C)

    s = mCxS.get(new D(""));
    // get(capture#897 of ? extends common.VarianceTest.C) in common.VarianceTest.M    // of ? extends common.VarianceTest.C,java.lang.String> 
    // cannot be applied to (common.VarianceTest.D)


  }

Now let's try the same with 'super' instead of 'extends'. This means that an instance of any superclass instance can show up (down to Object), we just have no way to know which one it is:


  void testParameter1WithSuperWildcard() {
    M<? super C, String> mCsS = new M1<C, String>();
    mCsS = new M1<B, String>();
    // Who knows what should be the actual type of param1...
    // The following line does not compile:
    mCsS.put(new B(""), "");
    // put(capture#248 of ? super common.VarianceTest.C,java.lang.String) in 
    // common.VarianceTest.M 
    // cannot be applied to (common.VarianceTest.B,java.lang.String)

    // C can be cast to any superclass of C
    mCsS.put(new C(""), "");
    mCsS.put(new D(""), "");
    String s = mCsS.get(new C(""));
    s = mCsS.get(new D(""));
    s = mCsS.get(new C(""));
    // Who knows what should be the actual type of param1...
    // The following line does not compile:
    s = mCsS.get(new B(""));
    // get(capture#330 of ? super common.VarianceTest.C) in common.VarianceTest.M    // of ? super common.VarianceTest.C,java.lang.String> 
    // cannot be applied to (common.VarianceTest.B)

  }

Generics with wildcards are not broken. The lack of understanding on how they work stems from the lack of understanding of covariant and contravariant substitution. Once you grasp it, the rest is easy.

And there's something specific about wildcards. If it is ? extends A, it does not mean that anything extending A can substitute. It means that there is something that extends A, and there' no way to figure out what.

Unlimited Cartesian Product in Java - part 2

2008-10-06T21:11:00.000-07:00

(This is the second part, see part 1).

Here is the code that implements Cartesian product in Java. The implementation amounts to providing the following methods of class Cartesian:

 
    public static <X, XS extends Iterable<X>>
        Iterable<Iterable<X>> product(final XS... xss) {
      return product(Arrays.asList(xss));
    }

    public static <X, XS extends Iterable<X>>
        Iterable<Iterable<X>> product(final Iterable<XS> xss) {
      return new Cartesian<X, XS>().calculateProduct(xss);
    }

So we could write code like this:


  Iterable<Iterable<Integer>> theProduct = 
      Cartesian.product(Arrays.asList(
          Arrays.asList(1, 2, 3), 
          Arrays.asList(4, 5, 6)));
    assertEquals(9, Set(actual).size());

and like this:


  Iterable<Iterable<Integer>> theProduct = 
    Cartesian.product(
        Arrays.asList(1, 2, 3), 
        Arrays.asList(4, 5, 6));

Note that we could not use Iterable<Iterable<X>>, since, imagine, in this case we could not even build a product of Set<Set<X>>.

How do we calculateProduct? The idea is that we define it by recursion. If we have X₀, X₁,..., X_n, we define product(X₀, X₁,..., X_n) as X₀ x product(X₁, X₁,..., X_n); and if the sequence is actually empty, we return a singleton,

new ArrayList<Iterable>() {{
            add(Collections.EMPTY_LIST);
          }};

(I use crazybob's contraption to build the singleton).


  private Iterable<Iterable<X>>
      calculateProduct(final Iterable<XS> xss) {
    if (xss.iterator().hasNext()) {
      Pair<XS, Iterable<XS>> pair = split(xss);
      XS head = pair.x();
      Iterable<XS> tail = pair.y();
      return appendComponentToProduct(head, calculateProduct(tail));
    } else {
      return new ArrayList<Iterable<X>>() {{
        add(Collections.EMPTY_LIST);
      }};
    }
  }

Here I use two methods, split and appendComponentToProduct. The first one is obvious (okay, it's an exercise if you are a beginner); the second one is here. See what it does: we have a component, X₀, say,

[1, 2, 3]

, and a product of previous components X₁ x ... x X_n, which is an iterable of iterables, e.g. [[4, 5], [5, 6]]; we need to append elements of X₀ to all elements of the partial product. That appendage function is called consWith: it takes an x and appends it to all partial product elements. We apply this function to the whole X₀; what we receive has to be flattened to produce a list of tuples [x0, x1, ..., xn]


  private Iterable<Iterable<X>>
      appendComponentToProduct(
        XS component, 
        Iterable<Iterable<X>> partialProduct) {
      // E.g. [1, 2, 3], [[4, 6], [5, 6]] -> 
      // [[[1, 4, 6], [1, 5, 6]], [[2, 4, 6], [2, 5, 6]], [[3, 4, 6], [3, 5, 6]]] ->
      // [[1, 4, 6], [1, 5, 6], [2, 4, 6], [2, 5, 6], [3, 4, 6], [3, 5, 6]] 
      return flatten(consWith(partialProduct).map(component));

Flattening is, again, a trivial exercise; let's take a look at our consWith. It is a method that returns a function (which we apply to the component X₀:


    public <ElementOfProduct extends Iterable<X>>
        Function<X, Iterable<Iterable<X>>>
        consWith(final Iterable<ElementOfProduct> pxs) {
      return new Function<X, Iterable<Iterable<X>>>() {
        // takes an x, returns a function appending x to sequences
        public Iterable<Iterable<X>> apply(final X x) {
          // Takes a sequence [x1, x2, ...], returns [x, x1, x2, ...]
          return new Function<ElementOfProduct, Iterable<X>>() {
            public Iterable<X> apply(ElementOfProduct y) {
              return concat(Arrays.asList(x), y);
            }
          }.map(pxs);
        }
      };
    }

A little bit dizzy? It's okay. We have arrived to the summit.

This is Higher Order Java!

Unlimited Cartesian Product in Java - part 1

2008-10-01T20:15:00.000-07:00

You probably know what Cartesian product is. Take two sets, A and B, their product, A x B, is a set of all pairs (a, b), where a belongs to A and b belongs to B. Something like that.

Here I am going to show how to build a Cartesian product for an unlimited collection of sets, or rather for an Iterable of Iterables. Unlimited means any number starting from 0. Due to limitations of Java, all these component sets (or rather component Iterables, will have the same element type.

More formally, given a sequence of sets (or of sequences), A₀, A₁, ... A_n, we will produce A = A₀ x A₁ x ... x A_n, whose elements are sequences (a₀, a₁, ..., a_n), where each a_i belongs to A_i.

So, for instance if we have just A₀ and A₁, their product will be the following: {(a₀, a₁}.

With this definition, we, with some confusion, have to admit that the Cartesian product of just one A₀ is a set of singletons, {(a)} for all a in A. Of course there is a canonical one-to-one correspondence between A and its "product".

More curious is the question what exactly is the product of 0 of components. In a category with limits it is a terminal object, 1. But how about JVM? There's no such thing as a terminal object.

No problem. We can use our definition, and take the set of empty sequences. There's just one empty sequence, so our canonical singleton has the following form:
{{}}. Did you notice the underlying type is not even mentioned. We have an Iterable of one single empty iterable of what type? Actually, Java deduces it from the type of the variable the product is assigned to. That's the safest way to pass the type knowledge into the executing code.

So, the solution I propose is to have something like this:


    Iterable<Iterable<Integer>> actual = Cartesian.product(Arrays.asList(Arrays.asList(1, 2, 3), Arrays.asList(4, 5, 6)));
    assertEquals(9, Set(actual).size());

Note the funny function name: Cartesian.product. Why do we need the special class named Cartesian? For two reasons. One, it is a neat way to provide type parameterization; second, calculating the product is not an elementary operation, so we need a bunch of private methods to help us. In JavaScript this can be accomplished by defining functions within our function; in Haskell we could comfortably add to our main definition the auxiliary "where" definitions. In Java, the "where" become class or instance methods.

So, we are introducing a special class named Cartesian, with just one exposed method, product:


  public static class Cartesian<X, XS extends Iterable<X>> {
  ...
    public static <X, XS extends Iterable<X>> Iterable<Iterable<X>> product(final Iterable<XS> xss) {
      return new Cartesian<X, XS>().calculateProduct(xss);
    }
    ...

You've noticed the IT parameter type. The reason for having this parameter is that we can pass for product calculations all kinds of Iterables of Iterables: Sets of Lists, Lists of Sets... any combination would work.

First, the algorithm. Here's how lj user=_navi_ defines it:


    product :: [[a]] -> [[a]]
    product [] = [[]]
    product (xs:xss) = product' xs (product xss)
      where
        product' xs pxs = concat $ map (\x -> map (x:) pxs) xs

In plain words, for us, Java pdestrians, it means this:

Say, we have an Iterable consisting of the first component, and the tail. And suppose we already have a product (call it pxs) built for the tail.
Then we do the following: scan the first component, A₀ attaching its elements a_i to the head of each element of the already built product.

We do this by having a function (let's call it f(a0, as) that concatenates an element a₀ with the tail [a₁, ..., a_n], producing a new sequence [a₀, ..., a_n].
Having function f, we build another function, g(a) that builds a list of all [a₀, ..., a_n] - by mapping the product of the tail, pxs using the function f: g returns, for each a₀, a list of concatenations built by f.

So, for each element a the function g produces a list. Now let's apply this to all the elements of the first component, A₀: that is, transform the component... to what? To a sequence of sequences of sequences.

We do not need such a deep structure. We just need the sequences of the lower level, listed in some order or in no order. So we do what is known as flattening the list.

The important thing is that the product we build should be lazy. As an example, suppose we build all permutations of N elements. This is equivalent to building a cartesian product of [0..N-1] x [0..N-2] x ... x [0..1] x [0]; there's N! elements in the product. We do not want to fill our whole memory with these elements before we start processing them.

(the code is published and commented in the second part)

class Function

2008-09-29T18:35:00.000-07:00

As we all know, functions are not a part of Java language; and closures are banished to the North, to Microsoft. What do we, humble Java programmers, do? We invent a Function class. Not that it suddenly makes Java a functional programming language, but it gives us the opportunity to express things in a more concise way, using higher level terminology.

In this article I use Pair class, see details here.


public abstract class Function<X, Y> {
  public abstract Y apply(X x);
}

If that were all that we wanted, we could as well make it an interface. There is a certain trend to first introduce an interface, and then an abstract base class implementing this interface and providing the base functionality. But... how many different ways of defining a composition of two functions do we know? Exactly one, right? See, there are certain rules and properties, without which a function would not be a function. Let's make them a part of the abstract class, since there's no choice anyway.


  public static <X, Y, Z> Function<X, Z> 
      compose(final Function< f, final Function<Y, Z> g) {
    return new Function<X, Z>() {
      public Z apply(X x) {
        return g.apply(f.apply(x));
      }
    };
  }

  public static <T, T1 extends T> Function<T1, T> id() {
    return new Function<T1, T>() {
      public T apply(T1 t) { return t; }
    };
  }

We will be tempted to apply a Function to an Iterable, a Collection, a Set, a List.

The naive way would be to write something like this:


  Function<X, Y> f = ....
  ....
  List<X> xs = ...
  ...
  List<Y> ys = new ArrayList<Y>();
  for (X x : xs) {
    ys.add(x);
  }
  // good job!

I have three problems with this kind of code.

Problem 1. It runs an explicit loop. Did you ever ask yourself what is the reason programmers have been using loops in their code? Are not all the use cases already known, so that we could just mention the case, and the loop is magically applied? Want an example? String concatenation. Nobody writes a loop to concatenate two strings.

Problem 2. We may not even need all the results in the new array, ys - why bother calculating the values? Would be cool to calculate them when needed.

Problem 3. Although an average computer these days has more memory than an average programmer can fill, it can happen that the source array is exceptionally long; and if we fill each temporary array with data, we may be soon out of memory. And for what reason? For no reason, just because we don't know better.

But we do.

The transformed set can be virtual. Built on demand. Let's start with applying a Function to an Iterator. What are we going to obtain? Another Iterator, with exactly the same number of values, but the values are different.


  public Iterator<Y> map(final Iterator<X> source) {
    return new Iterator<Y>() {

      public boolean hasNext() {
        return source.hasNext();
      }

      public Y next() {
        return apply(source.next());
      }

      public void remove() {
        source.remove();
      }
    };
  }

Iterators rarely materialize themselves in the code; they use to be returned by Iterables; so let's apply the same trick to Iterables.


  public Iterable<Y> map(final Iterable<X> source) {
    return new Iterable<Y>() {
      public Iterator<Y> iterator() {
        return map(source.iterator());
      }
    };
  }

We may not feel comfortable if the resulting Iterable's iterator() is called multiple times; but in this case we can eventually decide to cache the values. Or maybe not, if there's a billion of them, and the function is inexpensive to calculate.

The only difference between a Collection and an Iterable is that in the case of Collection we know the size. So there.


  public Collection<Y> map(final Collection<X> source) {
    return new AbstractCollection<Y>() {
      public Iterator<Y> iterator() {
        return map(source.iterator());
      }

      public int size() {
        return source.size();
      }
    };
  }

For List, we throw in one more method, get(int):


  public List<Y> map(final List<X> source) {
    return new AbstractList<Y>() {
      public Y get(int index) {
        return apply(source.get(index));
      }

      public Iterator<Y> iterator() {
        return map(source.iterator());
      }

      public int size() {
        return source.size();
      }
    };
  }

I wonder if anybody can come up with a solution that does not involve copy-pasting iterator() implementation.

Now, you have probably noticed that all these transformation methods are not static "util", but are a part of Function class definition. As a result, if you have a Function f, you can write in your code List<Y> results = f.map(souceList);

Applying the same trick to a Set is not exactly fair. Set "contract" say that we should not have repeating values; and in our case there is no guarantee that we would not:


  public Set<Y> map(final Set<X> source) {
    return new AbstractSet<Y>() {
      public Iterator<Y> iterator() {
        return map(source.iterator());
      }

      public int size() {
        return source.size();
      }
    };
  }

On certain occasions, though, the uniqueness of the function values is guaranteed, like in the case of Schwartzian Transform. Schwartzian transform consists of producing pairs (x, f(x)) for a given collection of x's. This operation is known to be useful in the times of Perl language; I found it useful in Java too.


  private static <X, Y> Function<X, Pair<X, Y>> schwartzianTransform(final Function<X, Y> f) {
    return new Function>() {
      public Pair<X, Y> apply(final X x) {
        return LazyPair(x, f);
      }
    };
  }

It is kind of funny that I have to define this method as static; one of us (me or java) is not smart enough to build new functions inside instance methods. Feel free to go ahead and try.

All of this allows us, given a Function and a Set, build a Map:


  public Map<X, Y> toMap(final Set<X> keys) {
    // this innocent function makes a Pair look like a Map.Entry
    Function<Pair<X, Y>, Map.Entry<X, Y>> fromPairToMapEntry = id();
    final Function<X, Map.Entry<X, Y>> pairBuilder =
        compose(schwartzianTransform(this), fromPairToMapEntry);
    return new AbstractMap<X, Y>() {
      public Set<Entry<X, Y>> entrySet() {
        return pairBuilder.map(keys);
      }
    };
  }

Java Pair: a closer look

2008-09-22T18:46:00.000-07:00

Who did not implement a Pair class, he did not write code yet. Or she.

People tired of implementing it, beg Sun to add Pair to the library (bugs 6229146, 4947273, 4983155, 4984991). Sun decided not to fix it. So the whole world under the Sun does.

A cheap solution would be to have a record with two fields, first and second, and implement equals() to compare both fields, and hashCode() as something like (first * 31) ^ second (computer people believe in magic "randomizing" properties of xor and number 31) so that one would be able to freely change the values.

Convenient, but wrong. What if you want to use pairs as keys in a map? You put an entry in the map, then change the key content, and kaboom! entry not found. A funny but working solution could be to freeze the hashCode on creation, getting them from another source of randomness in Java world, System.currentTimeMillis(): one can easily build half a million records within one milliseconds these days.

A better solution would be to have your pair immutable: take constructor parameters, store them, and only return them, but never change them. This, with a decent implementation of hashCode() and toString() is a good candidate to enter the imaginary World of Ideal Code.

But there's a nuisance. It would be great if it implemented Map.Entry< - that is, have aliases for getFirst() and getSecond(); first and second are now also known as key and value. Makes life easier if you already have a set of pairs and want to expose it as a map... yes, uniqueness of keys is required.

As an example, imagine that we have a Function<X, Y>, and a set of arguments; to expose this as a map, we have choices: either to instantiate a regular HashMap and fill it with the data; instantiate a Map as an AbstractMap where entrySet() is a prebuilt Set<Pair<X, Y>>, or do something smarter. See, if the key set is really huge, and/or evaluating the function takes some time/resources, we probably do not want to duplicate the keys and run the function over all of them. Who knows how many entries in this map will be needed by the client code.

Things can be even worse: the key set maybe large and/or virtual, so that building a set of pairs is an impossible task. What if it is a set of Natural Number, like this:


public class N extends AbstractSet<Integer> {
  public Iterator iterator() {
    return new Iterator() {
      int n = 0;
      public boolean hasNext() {
        return true;
      }

      public Integer next() {
        return n++;
      }

      public void remove() {
        throw new UnsupportedOperationException();
      }
    };
  }

  public int size() {
    return Integer.MAX_VALUE;
  }
}

I am sure you do not want to build a set of pairs on such a set.

So let us not assume anything. One pair may be lazy, the other one just instantiate from two given values. We need an abstract class to generalize this.


/**
 * Abstract pair class.
 * Implementations should implement two methods, 
 * and may be lazy or regular.
 * But in any case this is an unmodifiable pair.
 */
public abstract class Pair<X, Y> 
    implements Map.Entry<X, Y> {
  public abstract X x();
  public abstract Y y();

  public X getKey() {
    return x();
  }

  public Y getValue() {
    return y();
  }

  public Y setValue(Y value) {
    throw new UnsupportedOperationException();
  }

  private boolean equal(Object a, Object b) {
    return a == b || a != null && a.equals(b);
  }
  
  public boolean equals(Object o) {
    return o instanceof Pair && 
           equal(((Pair) o).x(), x()) && 
           equal(((Pair) o).y(), y());
  }

  private static int hashCode(Object a) {
    return a == null ? 42 : a.hashCode();
  }

  public int hashCode() {
    return hashCode(x()) * 3 + hashCode(y());
  }

  public String toString() {
    return "(" + x() + "," + y() + ")";
  }
}

From this class we can build a couple of concrete classes:


public class BasePair<X, Y> extends Pair<X, Y> {
  private final X x;
  private final Y y;
  
  public X x() { return x; }
  public Y y() { return y; }

  private BasePair(X x, Y y) {
    this.x = x;
    this.y = y;
  }

  public static <X> BasePair<X, X> Pair(X[] source) {
    assert source.length == 2 :
        "BasePair should be built on a two-element array; got " +
        source.length;
    return new BasePair(source[0], source[1]);
  }
}

BasePair is built from either two values or a two-element array; do we need a list-based constructor? It's possible.


public class LazyPair<X, Y> extends Pair<X, Y> {
  private final X x;
  private final Function<X, Y> f;
  private Y y;
  boolean haveY = false;

  private LazyPair(X x, Function<X, Y> f) {
    this.x = x;
    this.f = f;
  }

  public X x() {
    return x;
  }

  public Y y() {
    if (!haveY) {
      y = f.apply(x);
      haveY = true;
    }
    return y;
  }

  @Override
  public boolean equals(Object o) {
    return o instanceof LazyPair ? 
        equal(x(), ((LazyPair)o).x()) : o.equals(this);
  }

  @Override
  public int hashCode() {
    return hashCode(x);
  }
}

LazyPair calculates the function value only once, and caches it.

This seems to be all on this trivial issues. Thanks for reading!

Java: have a set of pairs, need a map

2008-09-17T20:14:00.000-07:00

In Java, as in may other discourses, maps and sets of pairs with unique keys are more or less the same thing. The problem is that Map in Java is represented as a set of Map.Entry<X, Y>; and Map.Entry is not the best way to represent pairs in your code.

Personally I, probably like the best half of Java programmers, have my own class named Pair<X, Y>; the components are called, yes, x and y. In Map.Entry they are called key and value.

So I had to make Pair<X, Y> implement Map.Entry<X, Y>, so that I would not need to recreate a Map.Entry<X, Y> every time I have a Pair<X, Y>.

Now, if I have a Set<Pair<X, Y>>, what should I do to produce a Map<X, Y>, without replicating all my data? I will need an AbstractMap<X, Y>, and provide a method, entrySet(). I already have a set; the trouble is, this set is a set of pairs, Set<Pair<X, Y>>. Should I replicate it? No way; what if there's 50 million records? Can I cast it? No... it is just impossible. should I wrap it somehow? Yes, kind of.

Luckily, I have some cool classes and methods already that would help me to do the job.

The cool class is called Function<X, Y>. The traditional approach is to declare it as an interface with one method, Y apply(X x). I thought it would be cool to implement additional methods. First, having an Iterator<X>, one would like to map this iterator using a function, right? That's what the method in Function<X, Y>, Iterator<Y> map(Iterator<X> iteratorX is for:


  public Iterator<Y> map(final Iterator<X> iteratorX) {
    return new Iterator<Y>() {
      public boolean hasNext() {
        return iteratorX.hasNext();
      }

      public Y next() {
        return apply(iteratorX.next());
      }

      public void remove() {
        iteratorX.remove();
      }
    };
  }

This was the biggest chunk of code.

Now that we can map an iterator, we can as well map an iterable, a collection, a list... but we need a set. Here we go:


  public Set<Y> map(final Set<X> setX) {
    return new AbstractSet<Y>() {
      public Iterator<Y> iterator() {
        return map(setX.iterator());
      }

      public int size() {
        return setX.size();
      }
    };
  }

How does it all help me? I just want to map my Set<Pair<X, Y>> to a Set<Map.Entry<X, Y>> without multiplying entities. So we need a function that returns the same pair, but shows it as a map entry. This is an identity function. Let's define it in Function class:


  public static <T, T0 super T> Function<T, T0> id() {
    return new Function<T, T0>() {
      public T0 apply(T t) { return t; }
    };
  }

See, while it returns the same instance, but, in the eyes of compiler, casts it to some superclass. Now that we have it, let's apply it to solve our problem:


  public static <X, Y> Map<X, Y> Map(final Set<Pair<X, Y>> pairs) {
    final Function<Pair<X, Y>, Map.Entry<X, Y>> idmap = Function.id();

    return new AbstractMap<X, Y>() {
      public Set<Entry<X, Y>> entrySet() {
        return idmap.map(pairs);
      }
    };
  }

One little note. We had to introduce the variable, idmap - thus mentally "reifying" our identity function; it would not work if we just called Function.id() on spot - Java compiler would be too confused.

How Do You Test JavaScript Loading?

2008-08-25T21:06:00.000-07:00

I had a problem: in my JavaScript unittests I wanted to check the behavior of my scripts when they are reloaded multiple times. That's kind of challenging: scripts are loaded in a background thread, and unittests run in the foreground test.

There seems to be no way to synchronize these two processes, to have either an event listener or a wait function that would make sure assertions in the test cases are called after a certain script is reloaded.

Here is what I was looking for:


function loadScript(path) {
  var script = document.createElement("script");
  script.src = path;
  document.body.appendChild(script);
  JS_TOOLS.sleep(500);
}

function loadScripts(var_args) {
  for (var i = 0; i < arguments.length; i++) {
    loadScript(arguments[i]);
  }
}

function testReloading_justOne() {
  loadScript('scriptToLoad.js');
  assertFalse(A_CERTAIN_VARIABLE_FROM_THE_SCRIPT === undefined);
}

The trick is to put the thread to sleep... for a little while.

I looked around on the internet, and found some cheap and some dear advices. In two words: Use Applet.

So I did. I wrote an applet, looking like this:


public class JsTools extends Applet {

  /**
   * Sleeps given number of milliseconds.
   *
   * @param timeToSleep time to sleep (ms)
   */
  public void sleep(long timeToSleep) {
    for (long wakeupTime = System.currentTimeMillis() + timeToSleep;
         timeToSleep > 0;
         timeToSleep = wakeupTime - System.currentTimeMillis()) {
      try {
        Thread.sleep(timeToSleep);
      } catch (InterruptedException ie) {
        // ignore it, just repeat until done
      }
    }
  }
}

The idea is that I may want to add more functionality to this applet some time later.

Now, I compile this applet, and store it in jsapplet.jar (with the right directory structure, so that it could be found by the browser's jvm. Then I wrote some JavaScript code that loads the applet and exports a function, sleep():


function jstools(location) {
  var JSTOOLS_ID = "JSTOOLS_ID";
  var userAgent = navigator.userAgent.toLowerCase();
  var isIE = userAgent.indexOf('msie') != -1 &&
              userAgent.indexOf('opera') < 0;

  function _(var_args) {
    for (var i = 0; i < arguments.length; i++) {
      document.write(arguments[i]);
    }
  };

  function openElement(name, attributes) {
    _('<', name);
    for (var id in attributes) {
      _(' ', id, '="', attributes[id], '"');
    }
    _('>');
  }

  function closeElement(name) {
    _('');
  }

  function addParameters(parameters) {
    for (var name in parameters) {
      openElement('param', {name: name, value: parameters[name]});
    }
  }

  openElement('object',
    isIE ?
      {
        classid: "clsid:8AD9C840-044E-11D1-B3E9-00805F499D93",
        style: "border-width:0;",
        codebase: "http://java.sun.com/products/plugin/autodl/jinstall-1_4_1-windows-i586.cab#version=1,4,1",
        name: JSTOOLS_ID,
        id: JSTOOLS_ID
      } :
      {
        type: "application/x-java-applet;version=1.4.1",
        name: JSTOOLS_ID,
        id: JSTOOLS_ID
      });

  addParameters({
    archive: (location ? (location + '/') : '') + 'jstools.jar',
    code: "com.google.javascript.keyboard.JsTools",
    mayscript: "yes",
    scriptable: "true",
    name: "jsapplet"});

    closeElement('object');

  return {
    sleep: function sleep(n) {
             document[JSTOOLS_ID].sleep(n);
           }
  };
};

This is kind of sad that I have to run it before the document ocntent is finalized; there must be a way to use DOM to build the applet element when it is needed - but the straightforward solution does not seem to be working, and what the heck, it is a unittest, where, according to josh kerievsky, everything is allowed.

There's a tricky parameter that one has to pass to tools(): applet location; we may later decide to store it somewhere else, outside our main directory. So, in my unittests, I instantiate my JS_TOOLS variable like this:


var JS_TOOLS = jstools("tools"); // the jar is in tools directory

Well, that's it. The script loads, and the variable instantiates.

Someone would complain about 0.3 second delay in running the test, right? Not clean, not "small", and flaky. Okay, suggest something else if you are really worried about .3 second delay in getting your test results.

P.S. You can try it here.

Java Style. Iterating over collections

2008-08-05T20:48:00.000-07:00

Suppose you decide to concatenate collections; it should of course look something like this:


  Collection<A> cat(Collection<A>... collections);

What you need to do is return an instance of anonymous class extending AbstractCollection<A>; and you will need to implement two methods, iterator() and size().


  Collection<A> cat(final Collection<A>... collections) {
    return new AbstractCollection<A>() {
      public Iterator<A> iterator() {
        ...
      }
   
      public int size() {
        ...
      }
    };
  }

Implementing size() is almost trivial: we can start with this naive code


      public int size() {
        int size = 0;
        for (Collection<A> c : collections) {
          size += c.length;
        }
        return size;
      }

Now raise your hAnds who think this is the correct solution... Wrong.

The problem is that for a large collection the result may be not precise. Quoting Collectio.size javadoc: "Returns the number of elements in this collection. If this collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE."

So, let's rewrite size():


      public int size() {
        int size = 0;
        for (Collection<A> c : collections) {
          if (c.size() == Integer.MAX_VALUE) return Integer.MAX_VALUE; 
          size += c.size();
          if (size < 0) return Integer.MAX_VALUE;
        }

        return size;
      }

If you find an error in the code above, let me know.

Now, iterator(). Not that I doubt you can implement it; what I want to say is that in this exercise minute details turn out to be important.

Here's our first attempt:


  Collection<A> cat(final Collection<A>... collections) {
    return new AbstractCollection<A>() {
      public Iterator<A> iterator() {
        private int i = -1;
        private Iterator<A> current = null;


        public boolean hasNext() {
          while (i < collections.size()) {
            if (current != null && current.hasNext()) return true;
            current = collections[++i].next().iterator();
          }
          return false;
        }

        public A next() {
          if (hasNext()) return current.next();
          throw new NoSuchElementException();
        }

        public void remove() {
          if (current != null) current.remove();
        }
      }
      ...
    }
  }

Here we are trying to be smart, bypassing empty collections, and getting to the one that has something; this will also work if the argument list is empty.

The problem is, it won't work if the argument list is not empty: see we are doing this assignment,


current = collections[++i].next().iterator();

- when i reaches collections.length - 1, we will go overboard. So we have to fix this, replacing the line with


if (i < collections.length) current = collections[++i].next().iterator();

This does look disgusting! In addition to checking for null, we are checking the same condition twice!

Null... can we get rid of null? Let's try this: set the initial value of current to an empty iterator:


Iterator<A> current = Collections.EMPTY_SET.iterator();

So that now we can say just


   if (current.hasNext()) return true;

instead of


   if (current != null && current.hasNext()) return true;

Good, good. How about index checking?

I have this idea: replace an array with a list (actually, an iterator). We take the array of arguments and turn it into a list, like this:


      public Iterator<A> iterator() {
        return new Iterator<A>() {
          // Top iterator
          private Iterator<Collection<A>> i = Arrays.asList(collections).iterator();
          // Bottom iterator
          private Iterator<A> j = Collections.EMPTY_SET.iterator();

          public boolean hasNext() {
            for (;!j.hasNext() && i.hasNext(); j = i.next().iterator());
            return j.hasNext();
          }

          public A next() {
            if (hasNext()) return j.next();
            throw new NoSuchElementException();
          }

          public void remove() {
            j.remove();
          }
        };
      }

Amazing, heh? Where's double index checking? It's gone. It's all hidden inside the delegate iterator.
That's final.

русская клавиатура для вашего браузера

2008-07-24T13:18:00.000-07:00

Перетащите вот этот линк: Рус туда, где у вас в браузере сидят закладки (bookmark bar). И потом, когда вам надо будет что-нибудь написать по-русски, скажем, в ЖЖ, просто кликните на эту закладку, и бабац - вот вам клавиатура.

Oh, and here's an Israeli version:

Kbd

internet is half dead

2007-07-24T16:12:00.000-07:00

From valleywag.com:

365 Main, a datacenter on the edge of San Francisco's Financial District, is popular with Soma startups for its proximity and its state-of-the-art facilities. Or it used to be, anyway, until a power outage took down sites including Craigslist, Six Apart's TypePad and LiveJournal blogging sites, local listings site Yelp, and blog search engine Technorati. The cause? You won't believe it.

A source close to the company says:

Someone came in shitfaced drunk, got angry, went berserk, and fucked up a lot of stuff. There's an outage on 40 or so racks at minimum.

Whoever it is, while we like how you roll in theory, in practice, we'd appreciate it if you laid off the servers running websites we actually use.

We're sure 365 Main will deny that such a thing could ever happen. And, conveniently, the neighborhood is having power troubles, too. But here's a question: When you have several levels of redundant power, what could bring your customers' servers down other than something like an employee physically ripping the plugs out of the wall?

==========================

Now, add to this that netflix has been dead for over 24 hours now. An amazing day!

Taming The Wildcard Generics

2006-06-02T12:15:00.000-07:00

Have you ever tried to work with List<? extends Number>? You get this list from some smart program, and then try to do something with this collection. Only to find out that you cannot add anything to it. Why cannot you? You open books, you look up on Google, you go to java.sun.com, and finally you figure out that it is not a “generics bug”, but a regular, normal behavior. Here is the reason why:

Suppose some method produced an ArrayList<Integer>, and returns it disguised as List<? extends Number> - there is nothing wrong with it. But then the receiver, knowing only that it is a List of something extending Number, tries to add a Number to the list, namely, a Double – can it be legal? Of course not, because the original container expects only Integers, You cannot legally do it – some other method still expects this to be a List of Integers.

When the code is executed, all the generics information is erased, so that this kind of checking is done during compilation time. And during compilation time there seems to be no way, in the code that receives List<? extends Number>, to figure out what is the actual type of elements inside. We just do not know; all we know is that if you extract an element, you will get a superclass of Number. That’s why it is impossible to allow to add anything at all to such a list.

Interesting, right? One can easily remove elements from such a collection, but cannot add anything. You are not allowed, for List<? extends T> list to do list.add(T t) – but it is okay to remove elements from the list. The same is true for a Collection<T>, for a Map<K,V>.

I had a slightly different problem to solve: having a collection of collections, produce a virtual collection that lists all the component collections.

What does it mean that the collection is virtual? It means that no collection object exists – it may be a view into some other collection, or a class that behaves as if it contains elements, while actually it does not. Take a look at Collections.synchronizedList() – it returns a synchronized (thread-safe) list backed by the specified list. No significant amount of additional memory is allocated when you wrap a list using this method; and if the original list changes, the synchronized list will change accordingly – and vice versa.

Note that this kind of wrapper does not in any way influence the objects contained in the list – they are the same objects; the changes are in the methods that we use to access them.

The Problem

So, this is what I wanted to accomplish: having a Collection<? extends Collection<? extends T>>, produce a virtual Collection<T> - a collection that would change when components are changing, from which we could remove elements and to which we could add elements.

The desired collection should contain all the elements from the component collections; I want to be able to remove the elements (meaning, they are removed from components); I want to find a way to add elements to my resulting collection.

Note that this is not a flat collection produced from a tree represented as a collection of collections of collections, etc. Flattening happens on just one level: we had a collection of collections of type T, and produce a collection of type T.

One more natural requirement is that, when I list the elements of the resulting collection, they will be listed in a natural order: first, elements of the first component are listed, as if we were scanning the component itself, then the second one, etc., till the last element of the last component.

The functional difference between an Iterable<T> and a Collection<T> is essentially that with a Collection one can get its size and add elements. Of course, to calculate the size of a compound collection one has to add up the sizes of its components. Yes, the size can be changing while we count – but the same can happen to an ordinary collection as well, so we should not be too surprised.

A Collection<T> has actually two addition methods: add(T element) and addAll(Collection<? extends T>). Remember, the intention is to create a virtual, live collection, which means that we are not interested in making a copy of the collection passed to addAll() method. We want to use the collection itself.

But when we add an individual element, T element, we cannot add it to any original component.

It is easy to introduce a compound collection class that can shrink but cannot grow; let’s call it ShrinkingCompoundCollection. It works as described above, by scanning through individual components; deletion as I said above, is fine, but addition cannot be implemented..

The Solution

Let’s denote the original upper level collection of collections as A, and its components as A_i. Since we cannot touch neither any of A_i, nor the original collection A, we have to have two “overflow” collections. One, upper level, collection will receive all the collections that are being added using addAll() method. Let’s denote this upper level collection as B, and its components as B_k. When listing elements of the whole compound collection or calculating the size of the compound collection, we have to scan through all the A_i, and then through all the B_j.

The first component of B, Collection<T> B0, has to be added when B is created. This component will accept all individual elements added by calling add(T element).

So, we have the following structure: a collection C consisting of A and B; each one consists of “elementary” collections with elements of type either T or ? extends T. Now, have not you noticed that we have tree levels, instead of two. How do we handle this? By iteration. Let’s denote as F the operation of removing one layer of indirection, that is, the conversion of Collection<? extends Collection<? extends T>> to Collection<T>. Applying this operation to C, which is a Collection<Collection<? extends Collection<? extends T>>>, we get a Collection<Collection<? extends T>>; applying F to the resulting collection, we get the required Collection<T>.

How do we do it, if we are supposed to use a constructor? I never heard of recursive constructors yet. Well, actually we do not need much of recursion.

Watch my hands. Having a Collection<? extends Collection<? extends T>> A, and having created an “overflow” LinkedList<? extends Collection<? extends T>>, produce a collection out of these two, and pass it to a ShrinkingCollection constructor. The constructor returns a new Collection<? extends Collection<? extends T>>, the first element of which we know, it is our LinkedList.B. Add to it an “individual overflow list”, LinkedList<T> B0, and pass the resulting parameter again to super.constructor. We have built a Collection<T>, which is an instance of ShrinkingCompoundCollection<T>, and we know how to add to it collections and individual instances of T.

Q.E.D.

Две Черные Ласты

2006-06-02T12:12:00.000-07:00

У нас в Архангельске вообще практически никто ни с кем не дрался. Я прожил там 15 лет, и не было случая, чтобы с кем-то там драться, чтобы кто-то напал. Ну разве с соседкой по парте Ниной Киселёвой, так и то – мы не друг друга мутузили, а она бросала на пол и топтала моё пальто, а я – её шапку. Чисто символически выражали свои чувства. Нет; один раз я присутствовал при драке – Лёнька Карельский с Серёгой Гермашевым поссорились из-за Сталина. Простак Лёнька сказал, что если бы Ленин был жив, то не дал бы Сталину устраивать репрессии; Серёга на это, цинично усмехнувшись, процедил, что Ленин и Сталин – едины; мы говорим Ленин – подразумеваем партия, говорим Сталин – подразумеваем тоже партия. Хоть у меня по русскому была вечная тройка, но меня слегонца бесило, когда Серёга нарочно вот так вот коверкал язык. Но не настолько меня бесило, чтобы из-за русского языка ещё драться – хватало мне дуры училки Валентины Александровны, которая даже не верила, что у Маяковского есть такое слово «земшар» - а я-то Маяковского уж всяко получше её знал. Да и ни из-за чего я не стал бы драться... ну разве если бы придурок Бармин вдруг обидел бы мою одноклассницу Валю К, так я бы вязл кирпич и убил бы его тут же, на это я был морально готов. А так драться – нет, не в моём вкусе.

А Лёнька с Серёгой как сцепились из-за Сталина, так и валялись, пыхтя и ругаясь, по школьному двору, пока совсем уж не стемнело. Я сидел на корточках и лениво уговаривал их: «кончайте вы, ребя», но кто ж в таких случаях прислушивается к голосу разума. Голос желудка – другое дело. Лёнька оголодал, вырвался из объятий Серёги, и полез через забор домой (Лёнька через забор от школы жил, так его дорога в школу и из школы в этом и состояла, в перелезании забора. А сразу за школьным забором стоял Лёнькин сарай, и в этом сарае, кстати, лежало полное собрание сочинений Сталина; мы эту гадость потом вместе с Лёнькой в школу на макулатуру стаскали – конечно, перекидывая тоже через забор.

Лёнька полез на забор, а мы с Серёгой двинулись в сторону наших домов, и Лёнька, сидя на заборе, обозвал меня предателем, потому что если я против Сталина, то не должен я с Серёгой ходить. Как будто Гермашев был за Сталина: ему просто смешна была наша глупость. Плюс, горячий астраханский характер. Серёга из Астрахани был, чердак называл «подловкой» и т.д. И своего младшего брата Вовку он иной раз бил так, что я уже был готов милицию вызывать. Не любил я Серёгу Гермашева за эти вот жестокость и цинизм; так и раздружились. В девятом классе, увидев его на остановке автобуса, я отвернулся – как и он от меня. А больше встретиться и не довелось – его застрелили через пару лет в Соломбале. Спасал кого-то от хулиганов, его и застрелили.

И кроме этой драки, ничего и не было. Мы во дворе жили себе своей жизнью, и никто никого пальцем не тронул. Люди были разного достатка – моряки, ходившие в загранку и привозившие диковинную одёжку для своих детей – а также чуингам, который, по словам наших учительниц, был вреден для организма и вызывал непрерывное слюноотделение. Жил шофёр Фёдоров с двумя глупыми дочками, погодками. Сёстры Фёдоровы любили верещать, когда их пугают, и в наши игры, «десять палочек» и «ваш чин», играть не любили. Были ещё у нас во дворе пенсионеры, один даже парализованный. Парализованный – но умный, научил нас всех делать воздушных змеев. Ну и наша вот семья тоже, не пришей не пристегни, не в квартире, как все остальные, а в отдельном домишке без газа и водопровода.

Нас соседи считали за очень бедных, и ко мне относились сочувственно. А я этой разныцы не ощущал; что с того, что у тебя телевизор дома, от этого умнее, что ли, станешь. Нет, я этого не ощущал; и городская библиотека была доступна всем, и еды тоже хватало в общем-то; хоть я, хоть Мишка Сорванов, хоть Колька Афонин - выходили иной раз на улицу с одинаковым бутербродом в виде посоленного куска свежего черного хлеба, и делились этой едой с налетавшими окружающими.

Вот этой дворовой кодлой иы и ходили летом на пляж, а иной раз и бегом бегали. В Архангельске в мои времена было три пляжа. Большой городской, тянулся километров на пять, от улицы Энгельса до яхтклуба, широкий, с хорошим песком; на нём в жаркую погоды толпился народ. Пляж с бонами, до которых в прилив было доплысть не сразу, а в отлив можно было пешком дойти. С бонов хорошо нырять. Если ловкий, то можно и на столб забраться, к которым эти боны привязаны на тросах, и со столба, с высоты метра полтора, нырять в Двину. В Двине вода летом тёплая, и течение не сильное в районе городского пляжа. Но вода мутная, видимость примерно метр; до дна надо донырнуть ещё, чтобы что-нибудь там увидеть. Особое развлечение – нырнуть с бонов и проплыть под водой до такого места, где стоять уже можно, где мелко. Кстати, срать в воду разрешалось только за бонами. Там – река унесёт. Вот ещё один повод сплавать до бонов.

Так как летом вода тёплая, то мы были избалованы, и в холодной воде купаться не тянуло. Раз только один, по инициативе шебутного Мишки Сорванова сходили в конце мая на городской пляж, искупаться среди плывущих льдин. Нет, не люблю. Кости ломит; яйца как доской прищемило. Кому нужно такое удовольствие?

Второй пляж был на месте строящегося речного вокзала, Речнухи. На Речнухе стояли горы привозного песка, настолько огромные, что зимой мы туда ходили кататься на лыжах, устраивали трамплины внизу... даже на уроках физкультуры нас туда гоняли, когда проходили катание с гор. Лыжи были главным предметом на физре, понятное дело.

На Речнухе, если честно признаться, пляжа-то никакого не было; был просто песок, была река, валялись вынесенные рекой брёвна, и выброшенные кем-то шины. То и то нам годилось – на бревне можно было прокатиться по реке, пытаясь удержаться на нём сидя; шины жгли на берегу, для жару, чтоб согреться, потому что на Речнуху ходили уже когда довольно холодно было. Дикий был пляж, эта Речнуха.

Ещё один пляж, оборудованный, но очень маленький, был у моста через Двину. Боны, выгороженная зона для плавания, вышка для ныряния. Здесь берег был очень крутой, и течение быстрое, так как место узкое. Самое узкое место Двины – восемьсот метров всего. Полмили.

Вот мы и пошли на этот пляж всей кодлой – Валерка Колодкин, Мишка Сорванов, Колька Афонин, Валерка Ожогин и его старший брат Сашка, а также Сашка Зуев. Такое количество Валерок я объяснить не в состоянии, а вот аномально высокая концентрация Сашек в первой волне бумеров объясняется просто – популярностью фильма «Александр Невский». Гордый профиль артиста Николая Черкасова, его арийская челюсть, плащ с кровавым подбоем, стальная будённовка вдохновляли вернувшихся с войны Отцов, мол, и их Сашка тоже вырастет таким. Победителем. Ожидания такого рода не всегда сбываются; некоторые из Сашек, выросши, вдруг стали Шуриками. Отцы не виноваты, виновата эпоха.

Валерка Ожогин, как и Мишка Сорванов, на год младше меня. Мне тогда нравилось это весёлое, незамороченное поколение – не то что Колька Афонин, на год старше; у Кольки в голове бродили очень странные для тех мест и того времени мысли... нынче бы – нормально, ну гомик и гомик, чё такого-то. Валерка Ожогин был мордаст и черноволос; у его брата Сашки тоже черные волосы, зачесаны гладко назад; Сашка худ, мускулист. Сашка был стилягой – только причёска не стиляжья. Иной раз, в субботу вечером, можно было его встретить в узких брючатах, с галстуком-верёвкой на пестрой «гавайской» рубахе. Про такой галстук моя тётя Лиза говорила, мол так бы и удавила этих стиляг на этих их галстуках. Не то чтобы тётя Лиза служила в обществе лимфоцитом, нет, она работала электриком на ТЭЦ – но она была передовик труда и искренне разделяла взгляды выписываемых ею журналов «Крокодил» и «Огонёк». Нет, до вступления в партию ей было далеко – во-первых, она была твёрдая христианка, во-вторых, родственники были слишком антисоветские - как соберутся два дедушки, отец и свёкор, да да как начнут «провергать коммунистов»... хоть и смеялись над дедушками, но всё ж уважали.

От Сашки Валерка Ожогин подхватывал модные иностранные песни, «рок, раунд зе клок», «твист энд шаут», и «абессамэ, абессамэ мучо» - на загадочном испанском, через много лет вдруг ставшем мне почти родным. Английский в наших местах хоть тоже был экзотикой, но встречался чаще; Лёнька Карельский ещё в третьем классе сообщил нам, что по-английски «кто отсутствует» будет «хуйзэпсэн» - и мы ждали, ухмыляясь, когда дорастём до пятого класса и услышим это своими ушами от Маргариты Иосифовны.

Да Сашку Ожогина, может быть, кто-то даже и побаивался, типа возьмёт да зарежет – такой стиляга-то! Колькина мать многое за ним подозревала. Она и за мной подозревала, что я губы крашу. Ничего семейка была. Подозревать двенадцатилетнего парня в сапогах и сером ватнике, что он губы красит!

Кодлой, конечно, весело купаться – по очереди с вышки ныряли; проплывали под водой (по течению) весь «бассейн»; ныряли по двое, под водой пугая друг друга всякими страшными жестами и рожами... У Сашки Ожогина были ласты, и он в них заныривал глубоко, до дна. У меня была маска, а ластов не было (да шутка ли, ласты стоили 7 рублей 10 копеек в магазине, чуть дешевле моего фотоаппарата, на который я два года копил, экономя на пирожках.

И вот, прыгнув с вышки в моей маске и в сашкиных ластах, я вынырнул в маске и одной ласте. Другой не было. Как бы это вам объяснить, в масштабе... Ну примерно как если у вас угнали незастрахованную машину, которую вы у приятеля взяли прокатиться.

Остаток дня я провёл, ныряя в своей маске в этот «бассейн». Не каждый раз удавалось донырнуть до дна - не хватало дыхания. Глубоко там всё-таки, метров пять; да и холодно на глубине. И темно. И эта мутная вода, которая тебя несёт над дном, пока ты по нему шаришь, пытаясь найти хоть какую-то неровность или что-нибудь тёмное... Наконец Сашка мне сказал «хватит», чтобы я перестал, что её всё равно уже не найдёшь.

Дома рассказал матери... мать дала денег, и я пошел к Ожогиным и пытался вручить им семь рублей. Зажиточная квартира, интеллигентные люди. Родителей Ожогиных я видел первый раз, и довольно-таки стеснялся. Они, конечно, никаких денег не взяли у меня – да и кто бы на их месте взял?

Это чувство, чувство отсутствущей ласты на правой ноге, чувство отчаяния, с которым ты шаришь руками по дну, в полумраке, а мутная вода сносит тебя вниз по течению, и ты пытаешься вернуться... эта густая холодая вода над серым дном, за которое я пытаюсь уцепиться, эта вода мне всё ещё снится – и я думаю, а куда же вот делась эта ласта? Куда?

Вторая ласта пропала 26 лет спустя. Моему сыну было столько, сколько мне тогда на пляже у моста.

Мы болтались по Вуоксе большой туснёй – Кротовы с детьми, Пихтины, Шура Холоимов. Наконец удалось нам добраться до моей заветной стояночки на Холмистом, на скале, где мы с Андрюшкой Кротовым даже выдолбили шлямбуром в скале канавку, чтобы вода не хастаивалась у камня, за которым мы пили чай и играли в ап-энд-даун, а стекала, и место чтобы оставалось сухим, только мох. Мы там вообще пообосновались; я даже примеривался сажать картошку и укроп на лугу на острове Фиалка, это напротив Холмистого.

В июле вода в Вуоксе теплющая; так что мы только и делали что купались. Дети ещё пытались ловить какую-то рыбу, чтоб кормить нашу знакомую чайку Чуку, но в жару рыба не особо спешит на крючок – а если попробовать рано утром, в пять часов – так это ж слишком холодно, и дураков нет вылезать из палатки мёрзнуть над неподвижной водой... так что пути наши и рыбьи не пересекались. У детей любимое место для рыбалки было – скала напротив, небольшая скала, высотой метра два – на ней можно сидеть рыбу ловить, анекдоты травить, а можно нырять, только надо знать куда, чтобы в ил не запилиться с головой: ил в нашей заводи знатный.

Дети вздумали гонять вплавь на время до скалы и обратно. К детям присоединились взрослые, начиная с Кротова. Я-то стоял на берегу и усмехался – никогда я не умел быстро плавать; я предпочитаю плыть не спеша, будь это хоть час, хоть два. А Шура – парень спортивный, и тут же присоединился к Кротову. Шура нас всех лет на десять этак моложе был. Худой, жилистый, небольшого роста, круглое лицо, весёлые карие глаза, глубокое понимание жизни и всех её поверхностных вещей; и с иронической улыбочкой ташит хоть какой тяжести рюкзак. Меня пробовал учить плавать кролем, да меня учить физкультуре – примерно как учителя физкультуры языку Лисп. Так что я стоял на бережку и засекал по часам время, рекорд 54 секунды в один конец.

Потом Шура решил ешё смерять, ну а сколько же будет если с ластами плыть; взял надел мои ласты и поплыл. И бац – свалилась с его маленькой ноги моя большая ласта, аккурат посредине между берегом и скалой. Взял я маску, стали мы с Шурой по очереди нырять. Да чего там нырять – хоть видимость и есть кое-какая, но на глубине два метра упираешься в слизистый жидкий ил, который при любом прикосновении вздымается облаком; и сколько там этого ила – неизвестно. Ну да и вода в Вуоксе только на поверхности тёплая, а там, ближе к дну – ледянющая. И ничего не нашли, конечно. Отметили только это место, мол, вот, здесь покоится чёрная ласта.

И в следующие заезды я своим гостям место показывал: так и так, мол, здесь Шура ласту утопил. А вот здесь чайка Чука жила. А здесь к нам однажды вышел беглый солдат с большим ножом и попросил перевезти на тот берег. А здесь Ник с Фаей лося как-то утром встретили. А у этого нашего камня снимались «Особенности». А здесь раньше был фарватер, теплоход ходил. А здесь когда-то избушка стояла, и в ней жил парень, и этот парень угощал нас чаем из чаги. А вот хутор Пёйлякаллио, и сосна, которую тихуанский колдун Ч назвал дубом, и намерял у этого дуба биополе - 8 метров в диаметре.

Через восемь лет Шура Холоимов умер от рака.

Ну это нам так легко говорить, мол, взял да умер. Это вот если ты, скажем, едешь по 85-й дороге в левом ряду, включил радио Пуро Мехико, да орёшь вместе с ними: Besame, besame mucho, como si fuera esta noche la ultima vez… oh shit! – и всё. Твои последние слова были «оу щит». Всё очень просто – для тебя. А с раком непросто. Сначала же надо вернуться от доктора, набраться сил, и твёрдым голосом, слегка, правда, задыхаясь, сказать: «мама, у меня рак.» Потом операция. Потом химия. Потом, после химии, облучение, рвота, облысение, тоска и бессилие. Если повезёт – без болей, а не повезёт – боли, с каждым днём всё неутолимей.

Потом койка.

Лежишь, глядишь в белый потолок.

Ждёшь.

Ныряя Глубоко - 1

2006-01-14T21:35:00.000-08:00

Мой родной дом... мне невероятно повезло в жизни - я провёл детство в отдельном доме. Ни соседей сверху, ни соседей снизу, ни слева, ни справа. А так как бабушка с дедушкой были довольно глухие, то я привык вытворять всё, что мне в голову взбредёт, уже в семь лет вставляя жучки в пробки, перегоравшие из-за моей любви к электричеству...

Пятистенка, построена в начале 20-го века; серые стены, общая площадь где-то метров тридцать пять - сорок.

Материна комната занимала полдома. Окнами на юг, на восток и на запад. Моя выкрашенная светло-голубой краской кроватка стояла у восточного окна. Пока не сняли решетку, я, просыпаясь ночью, вставал к окну и глядел на золотисто-голубое небо архангельской белой ночи. Ещё не были выстроены ни двухэтажные брусчатые дома через дорогу, ни высокие, с антресолями, дровяные сараи к этим домам - и открывался вид ну почти что на тундру - в июне пушок, потом иван-чай... Метрах в ста стоял старый двухэтажный дом на сваях; этот дом таинственная сила вымораживания выталкивала из земли и поднимала всё выше, так что мы с матерью, идя в гости к дальним родственникам Вяткиным (взяв с собой в качестве гостинца кулёк с желтыми конфетами), проходили, как и все, прямо под домом, чтобы потом подняться на находящееся с обратной стороны крыльцо.

Однажды, холодным летом 53-го, часов около пяти утра, этот дом вдруг со страшным грохотом просел, так что стены встали на землю, а пол первого этажа оказался на расстоянии меньше метра от потолка. В те времена было принято спать в железных кроватях с железными спинками с шариками, и вот эти спинки с шариками, эти крепкие стальные трубы и спасли людей - никто не погиб и не был даже ранен, все как-то выползли, как выросшая Алиса, из ставшего маленьким домика.

Облако пыли разлетелось в стороны, и медленно осело на землю.

А так, из моей стратегически расположенной кроватки, если идти по часовой стрелке с севера, были видны следующие вещи и предметы:

- Светлый фанерный гардероб, с двумя ящиками старой обуви, с вешалкой, с кусочком нафталина в целлофановом пакетике, с портупеями, ремнями, сумками... Что было на крыше того гардероба, мне было совершенно не видно.

- Голубые в широкую светло-пурпурную "цветочку" обои, отстающие по верху и по низу, несмотря на то, что по верху был проложен широкий бордюр. Это была отдельная работа - резать ножницами на полоски рулон бордюра, перед поклейкой.

- Затем уже упомянутое выше окно.

- Затем выкрашенная голубой краской тумбочка, на которой стояла огроменная эмалированная кастрюля (очевидно, списанная из детского сада, где работала мать), в которой рос огромный же, почти до потолка, фикус.

- Прямо над фикусом - мраморный щиток, на котором электрический счетчик и две пробки; меня гипнотизировало жужжание счетчика, неугомонное вращение горизонтального колёсика с меткой, и, время от времени, тиканье цифр. Туго скрученные провода идут под потолком от щитка на кухню, к выключателю, к лампе на потолке... провода примотаны стальной проволокой к маленьким изящным фарфоровым катушкам, то ввинченным в стены ржавыми шурупами, то прибитыми на толстый гвоздь. 127 вольт было тогда бытовое напряжение; уже под конец царствования Хрущёва нам поменяли напряжение на 220.

Справа от электросчётчика висит портрет великомученицы Екатерины, чей духовный подвиг давал моей матери какие-то силы выносить все эти тяготы, что выпали на её долю - мне иногда кажется, что всю удачу, которая могла бы достаться на её долю при честном распределении, она оставила, сама того не ведая, мне, баловню, которого она родила в сорок лет, чтобы не оставаться одной... ну это потом, сейчас мы просто обводим любопытным взором, с высоты кроватки, мою вселенную, как я её впервые увидел.

- Справа от фикуса ещё одно окно, на юг. За ним - стройка, строят двухэтажный брусчатый дом, куда потом въедут наши будущие соседи. Афонины, Сорвановы, Колодкины; капитан Иван Севастьянович, чья взрослая дочка была первой шахматисткой города Архангельска; она же научила меня привезённым с Кавказа песням только что вылупившегося Визбора: "а друг рисует горы, далёкие, как сон..."... не будем спешить, это всё в будущем, соседи, капитан... всего в той стене три окна, это фасад дома. На зиму окна покрываются сначала инеем, а потом и сантиметровым слоем льда, и мне не разрешают протапливать дырку, так как от неравномерности нагрева стекло может запросто треснуть... но и это потом.

- Ещё одна табуретка, на которой стоит желтый патефон; пластинки в пожелтевших бумажных конвертах на полу рядом, прислонены к табуретке. Апрелевский Завод Грампластинок. Русланова, "Собака на Сене" Лопе де Вега, "12-я ночь" Шекспира. Я лучше патефон сейчас пропущу; это отдельная большая тема, с его иголками, головками, регуляторами, большой пружиной, внутренним рупором, и т.д.

- Затем комод; комод выглядит свежее, и сверху на нём лежит кружевная скатерть (живя в Архангельске, мать не плела больше вологодские кружева, хотя и умела, и подушка с коклюшками, а также и трафареты для кружев, пылились на чердаке. На скатерти стоят зеркало побольше и зеркало поменьше, а также две розовые гетинаксовые шкатулки с разной ерундой. Но до ерунды дотянуться ещё надо - залезть на табуретку, например. Ну и будильник, большой, бежевый, с блестящим никелированным звонком сверху, внутри которого цилиндрический молоточек на толсткой стальной проволочке.

Над комодом висят два портрета, Лёнюшка, мой брат, которого я никогда не видел, и смерти которого я обязан своей жизнью: если б Лёнюшка не погиб, четырнадцати лет, мать не стала бы заводить себе на старости лет ещё одного ребёнка... а рядом с Лёнюшкой - Лёша, мой дядя, в военной форме.

Лёша выстрелил себе в лоб, будучи в карауле. Служил он под Мурманском, в Североморске, и однажды полярной ночью не выдержал этого всего. Лёша всегда был одиночкой; он был слишком мягок, слишком честен и прост, как и все, кому посчастливилось вырасти под руководством моей бабушки. Плюс маленький рост - сволочные мурманские девки, с золотым зубом, со взбитым коком, в крепдешиновых платьях, избалованные ходившими в загранку моряками, над ним ну просто смеялись.

Ему и с самоубийством не очень повезло - не умер сразу же, а в недоумении встал, пошел к двери караульного помещения, и уже у двери рухнул навзничь.

Военное начальство в ту послевоенную пору и в тех неавантажных местах было благородным; они списали на несчастный случай, и поэтому выписали бабушке с дедушкой пенсию, 350 рублей, которой им вполне хватало... ещё одна смерть, сделавшая возможным моё существование. Лёшины записные книжки я одно время почти наизусть помнил.

На портрете Лёше 26 лет, и в моих глазах, с течением времени, он из пожилого дяденьки превращался в почти ровесника, молодого офицера, а потом и в несчастного мальчика, которого мне до сих пор жалко.

За комодом стоит табуретка, а за табуреткой стоит трюмо с мутным старым зеркалом; трюмо тоже мутноватое, сосна, покрытая морилкой и лаком, потёртое, старое. Над трюмо висит большой черный плоский конус: Репродуктор, радиоточка. У Репродуктора в середине расположен трансформатор и катушка; есть также маленькая ручка, позволяющая регулировать громкость. Так как Репродуктор висит под самым потолком, то и достают до него только взрослые, а я лишь слушаю. Песни Руслановой, Последние Известия, Архангельские Новости ("стивидоры Соломбалы досрочно завершили.."). Репродуктор учил меня Правильному Русскому Языку. Это благодаря ему я перестал говорить "радево" (радио), "пошто" (почему), употреблять послелоги "-то", "-та", "-ту", "-те".

Тут мы уже подходим к западной стенке, у которой стоит материна кровать. Большая железная кровать, шарики на спинках (половины нету - часть, похоже, откручена ещё до меня). На железной сетке положен пружинный матрас, а на нём толстый пуховый матрас. Темно-розовые подушки с рисунком "огурец"; темно-синее одеяло всё в тот же "огурец". Попасть туда ночевать - это надо было или хорошо себя вести или заболеть. Я чаще практиковал второе. Лежишь, водя глазами по потолку; болезнь накатывается на тебя как тяжелая густая волна какого-то сиропа; всё становится вдруг медленным и тёмно-медовым... и потом эта волна откатывает, и становишься лёгким, пустым, кажется, всплывёшь вместе с одеялом к белёному потолку в загадочных, полных скрытого смысла и тайных букв трещинах - но мокрая, вспотевшая голова липнет к подушке, и не оторвать. Попросишь "пить", и мать спешит с большой чашкой с золотым ободочком; в чашке чай с молоком, с маслом, с пенкой, с мёдом: "пей!". Я ничего не имею против пенки, но в больное горло она не лезет.

А в хорошие времена залезешь бывалоча на спинку кровати и валишься плашмя на матрас, аж подпрыгиваешь потом. Страшно, но здорово.

У кровати висит густой короткошерстный красный ковёр, очень чесучий, если к нему прислониться. Лучше под одеялом. Конечно, хорошо, когда разрешают там спать. Можно разговаривать, спрашивать про всё, или попросить сказку рассказать - да только она никаких сказок не знает, я сам лучше почитаю. А вот рассказать из жизни что-нибудь, как она в школу ходила, как учитель иной раз придёт утром и скажет: "ребята идите вы домой, я за охотой пошел" - и всё. Как после революции "боже царя храни" петь в школе перестали, а стали петь песню про берёзку. Мать училась недолго, четыре класса всего окончила. А больше и школы в деревне не было. И то неплохо; бабушке пришлось самой выучиться грамоте, чтобы потом Толстого да Гоголя читать. Дедушка же, хоть и служил в Финляндии, а даже расписываться не особо-то умел, норовил всё крестик поставить. Книги для него были - ничто. Пустое место. На цигарку да подтереться. Ну примерно вот как вам - AJAX-технология или интуиционистская семантика Крипке-Жуаяля.

Мой начальник Мыкола Гомец

2005-12-18T21:56:00.000-08:00

Date: Tue, 04 Apr 2000 18:24:25

У меня есть начальник, Мыкола Гомец. Он по-испански, правда, не очень, его родной язык шведский. Ну и еще сантакрузский – "beer dudette", скажем. И мы с ним карпулились. И вот он спрашивает у меня, как по-русски будет "shit!" Ну, подумав, сказал – "бля!". И вот заходит Мыкола вечером в кафе в Санта Крузе, видит Лену, тыкает в нее пальцем и орет: "бля!". Ну лааадно... через неделю спрашивает у меня Мыкола, как по-русски с днем рождения поздравляют. Смотря как. Неформально. Смотря какого пола. Девочку. "Расти большая". Едем-едем. А как, спрашивает, спросить "how's your nose?". "Как твой нос?", отвечаю. И вот он приходит от вечером в кафе в Санта Крузе, подходит к Лене и, в присутствии ее родителей, говорит ей торжественно: "расти большая, как твой нос!".

Больше я его русскому не учил, выучил он только имя свое – Мыкола, да и то Лена ему впаривает, что это означает, что он redneck – а я говорю, не реднек, не реднек, просто Украина и Швеция – близнецы-братья, недаром Мазепа пытался оную к оной присоединить, у них и флаги у обоих жовто-блакитные (бло-гюль, по-шведски), и фразу "хай, добро, так" швед поймет примерно адекватно. Можете попробовать, это приличная фраза.

Понедельник

2005-12-18T21:55:00.000-08:00

Date: Mon, 15 May 2000 18:36:53

Да неделя как неделя была, токмо что жара и засуха до октября, которые мы с Бредом Жилетом так дружно обещали швейцарцу Урсу Шпюхеру, сменились густыми облаками и проливными дождями. От Миши "эль ниньо" ничего, однако, не слышно. Непонятно.

В пятницу, в связи с производственным визитом в город Сан Матео, зашел в родную школу, поздороваться с учителем Василием Ивановичем. В классе было полно народу, все заорали, увидев меня, и стали дружно поправлять мой английский – мой английский был любимчиком этого класса. Датчанка Лада обняла меня и чуть не прослезилась. Радостно орала, увидев меня, мексиканка Арасели; она на днях получила гринкарду и стала работать в аэропорту, смена с трех тридцати утра, она даже не знает, какую ей зарплату положили, по знакомству устроили; устраивается на работу и Хайм, колумбиец, через две недели он будет в Оракле, что-то в маркетинге, солидный паренек. Загадочный мексиканец Мартин, с огромной золотой цепью на шее, улыбался молча. Чилийка Маривель приплясывала за своей партой – Маривель в субботу летит к себе в Чили со своим мужем, свадьба у них была на миллениум в Лас Вегасе, сидит и напевает странную песенку – ми энд ю, ю энд ми, хомо-секшу-алити... Маривель недавно тоже устроилась работать – корреспонденткой в "Нуэво Мундо", испанское приложение к "Сан Озе Меркури Нуз". Появились в классе две новые японки, внешне похожие скорее на тайванек. Пришел директор Тешара, который недавно вернулся из Вьетнама, и все сначала заорали "Алла Тешара", а потом переключились на Василия и стали привычно орать "Алла Василий". Директор Тешара устроил рафл из принесенных сувениров; мне досталась голова медведя Смоки, каковую я и прицепил к автомобильной антенне. Голова небольшая, размером с яйцо.

(Примечание. Медведь Смоки, как известно, родом со Сьерры. Уже в июне нас как-то понесло на Сьерру погуляти – и теперь нам от этой Сьерры уже и не оторваться. Голова Смоки, наверное, оказывает этакое трансцендентальное влияние.)

Потом Вася велел всем рассказывать про страшные случаи, которые с ними были. Народ-то разный собрался. Кого в заложники брали, к кому домой вооруженные бандиты на родине забирались. Японки в детстве тонули и с тех пор боятся воды. Колумбиец Хайм рассказал, как он служил в армии, в 16 лет его забрали; уточнили, что не урожаи охраняли, а в государственной армии служил – и там ребятишкам выдали оружие, и все стали целиться друг в друга, одного убили, другого ранили, с тех пор они с оружием осторожно. У чеха Томаша месяц назад взорвался его красный конвертибл, прямо как в кино – они с персом Али сели в машину, и Томаш стал заводить – и тут сначала полыхнуло, Томаш крикнул Али – "get the fuck outa here!", они токо выскочили – и взорвалось. Менты приехали через минуту. Где-то за углом сторожили, видимо.

Я свою историю начал – "когда мне было пять месяцев..." – все сразу заржали. Вах, какой народ у нас в классе!

А в субботу мы с утра поехали на великах прокатиться, взяли три банана, три пряника и немножко соку. Проехали по парку, боринг, подъехали к лексингтонскому вдхр, въехали на дамбу, ну что, объедем вокруг пруда? Да ну, далеко тащиться, давай домой – ну давай. Только другой дорогой поедем. Ну хорошо. Дорога на Черную Гору, туда и поперлись. Часа через два (а часов у нас тоже нету, и карты нету, и денег, и телефона) подъем кончился. Питье мы берегли. И пряники берегли. Откусывали по маленькому кусочку, как Зиганшин с Поплавским. Пуще всего мы берегли бананы. Во-первых, после бананов тяжело ехать на велике. Во-вторых, это стратегический запас. До тридцать пятой дороги оставалась пара миль, когда увидели въезд в парк Санборн. А этот парк мы знали – точнее, знали противоположный из него выезд. Туда и попилили, хотя на велосипедах нельзя – да что поделаешь, у нас имердженси, можно сказать. Места там странные, глухие – никто туда не забредает – и вот, глухое лесное озеро, тишь, травка, луга, как на Карельском, только деревья раз в пять повыше будут. У озера мы съели первый банан. Солнце стояло еще высоко, но и ехать нам было так, ничего... порядочно. Впрочем, нам повезло – если бы не парк, была бы еще пара подъемом на 2000 футов, а так – все вниз, по крутой дорожке, правда, не близко это. Что странно – когда езды оставалось часа на полтора, появилось ощущение, что нам все вообще по фиг дым, и мы хоть двое суток можем так пилить.

Вернулись задолго до заката, хватило сил даже доползти до бассейна и джакузи, поговорить о жилищных проблемах с бразилкой, сидевшей в той же джакузи – и все, и дальше мы рухнули на диван и уже не сползали с него, смотрели всякую чушь типа Пекинской Пули. До компьютера доползти не было сил. До сейфуэя доползти не было сил – ели, что есть в холодильнике.

А сегодня ливень, ливень. Хочется спать, а не работать.

И еще сегодня сорок лет, как умер мой дедушка Башаров Василий Константинович. Родился он в 1876 году. Служил в Финляндии, потом налаживал домашнее хозяйство, потом его посадили, потому что слишком хорошо работал, но на канал не послали по возрасту, и он с бабушкой жил у нас в доме за заборкой, и дедушка время от времени собирался пойти косить сено. Дедушка научил меня курить, пить водку и материться (а я уже учил учеников старшей группы детского сада, за что был очень популярен). Курил я, правда, не вдыхая – как Буш. Зато пил ничего, однажды хлопнул в гостях стопарик водки – и бух на пол, скорую вызывать боялись, так оклемался. Сколько мне было... три, наверное, или даже два. Читать еще не умел, точно. Если бы прочитал, что водка – пить не стал бы, не любил я водку. А сегодня выпью.

Перед смертью к дедушке приходил поп, исповедовать, соборовать, не знаю уж точно. Я, убежденный к тому времени атеист, написал на картонке текст: "бога нет!" и, когда поп оделся и ушел, побежал за ним, и, регулярно его обгоняя, молча вставал на дороге и демонстрировал ему мой плакат. Так мы с попом дошли до трамвайной остановки на углу Выучейского и Ломоносова, где и расстались. Поп тоже не сказал мне ни слова.

Саке

2005-12-18T21:49:00.000-08:00

понедельник, 9 июня 2003 г.

Плохую саке пьют теплой, хорошую пьют холодной. Хорошую саке отличить в магазине легко: по ценнику. Но и плохая не так уж плоха, ее вполне можно пить и холодной, если не выпендриваться, не корчить из себя японца, и не говорить "кэмпей", а просто.

Когда пьешь саке, становится грустно. Проверено. Интересный эффект получается, если сочетать с чешским пивом Уркель или с примерно одинаково разгильдяйским и веселым напитком текиля. Только текилю надо пить хорошую, плохая текиля, нагревай ее или остужай, пей ее с лимоном и солью или с таком, все равно остается плохой.

Почему сочетать? Потому что тогда грусть не переходит в мерзкую тоску, а становится основой творческой мысли. Во-первых, всех жалко. Бабку, которой в 88-м году на рынке в Йошкар-Оле показал фигу; травинку, которая росла сорок с лишним лет назад у столба около моего дома, и которую я обломил в коленке и стал покусывать, из них еще такой сок, немножко сладкий... а ей же тоже больно было.

И при этом кажешься себе умным и понимающим. Идешь к компьютеру, начинаешь писать статью какую-то; потом приходят в голову многозначительные вещи, вроде диссертации на тему сравнительных размеров апельсина и его кожуры, в аспекте дизайн паттернов.

Лето; носились вечером дети, и двери веранды были открыты - и теперь в темноте на монитор слетаются разные ночные зверки - мотылек, моль, карамора. Каждый зверок скромно присаживается в нижней части экрана, а потом начинает медленно продвигаться наверх. По дороге остановится, почешет этак ногу за ногу, оглянется. Вот мол я каков, уже полпути прошел. Половину светлого пути. И дальше двинет. Каково же будет его удивление, когда он дойдет до верхнего края экрана, а дальше, собственно, ничего и нет. Возвращаться восвояси? А где они, эти свояси? Свои веси? Ночью хрен их найдешь, да ведь и съедят там запросто, зря, что ли, улетели... Каждая такая карамора считает себя ужасно умной. Она всего достигла, нашла луч света в темном царстве, и добралась до вершины. Куда уж дальше.

Голоса

2005-12-18T21:26:00.000-08:00

Date: Monday, August 27, 2001

Сегодня у Лёлика праздник – милая дала в рот.

Я думала, он с честными намерениями пришел, а он – пообедать.

Очень мне нравилось причесывать ее длинные, пушистые волосы; пока она в это время делала мне минет.

Ты со мной всю жизнь что-то не то делал.

Он все хвалит мою фигуру, а я не понимаю – ну так давай, можно же и потрогать!

Если бы не ее волосатая грудь, я бы с ней надольше связался.

Жена меня как-то раз спрашивает: «а ты с ней какими-нибудь сексуальными извращениями занимаешься?» Я ей ничего, дурочке, не сказал.

Все ревновал ее к Мишке, пока вдруг не понял, что Мишка больше интересуется мной.

Я знаю, ты со мной разводишься потому, что я тебе всю жизнь не давала.

У них ребенку уже два года, но он все ещё боится позвать ее замуж.

Я как взглянула на его дряблую шею, чуть не заплакала - это вот с кем я два года переписывалась!

Кому нравится поповская дочка, кому попадья, а кому и поп.

Viagra, My Friend

2005-12-18T21:24:00.000-08:00

Date: Monday, August 27, 2001

Меня зовут Давид, и мне 62 года. А девчонке моей – 26. Я пишу сюда на условиях полной анонимности. Мне не хотелось бы, чтобы меня кто-то узнал, у меня дети и внуки, спасибо.

В СССР я, наверное, копался бы на грядках, замешивал бы удобрения и радовался приезду внуков. Но обстоятельства меня всего этого лишили. Восемь лет назад у меня умерла от пиелонефрита жена. Но дело не в этом. Это, в принципе, не мешает угощать внуков клубникой. Нет, дело в другом. Все разрушилось. Не до дачи уже. Мы летели оттуда, как ошпаренные, боялись, что захлопнется калитка, и нас прихлопнет. Да нас ведь кто угодно может прихлопнуть.

Мы на бреющем пролетели мимо исторической родины и попали в Америку. Ну, у меня ведь тут двоюродный брат уже, так что мне попроще было. Я ничего, на велфере, как дорогие соотечественники, не сидел, а почти с первого дня нашел работу. С английским у меня хорошо, не терял время в СССР.

И все равно, несмотря на удачу, остался на старости лет один. А в Америке ведь понятия такого нет - "старость лет". Все живут и радуются.

Чего бы мне не радоваться, когда один остался. Я так думаю, это у меня отпечаток детства. Желание всем нравиться какое-то. Наш папа не вернулся с войны. У папы вообще-то была бронь, инженер на Уралмаше; но в сорок третьем пошел добровольцем, и вот не вернулся. Нет, с войны он вернулся, но не к нам, а поехал со своей новой на Север. Потом, в сорок восьмом, его посадили. К маме приходили, но она же ничего не знает про него. А потом, в пятьдесят четвертом, папа вышел, но не вернулся, а так и стал на Севере жить со своей.

И мы с сестрой выросли какими-то немножко детдомовскими: всем улыбаемся, от всех добра и ласки ждем, всем хотим понравиться. Сестру три мужа бросили. Слишком мягкий характер, никогда никому ничего не приказывала. Так и живет, кстати, в Свердловске, теперь Екатеринбург, ехать уже никуда не хочет

Ну это же я все анонимно пишу, по интернету.

Тогда уж признаюсь. Я нашел свою Марицу тоже по интернету. Ну и что? Грубо говоря, мои проблемы. Да и дело-то не в этом, мы же встретились в конце концов, и все у нас нормально. Она только наполовину филиппинка, мать у нее мексиканка из Чиуауы… не знаю, как выговорить, такая провинция.

Ну я же не молодой жеребец, я не стал к ней лезть с намерениями в первую же встречу, или даже в первый вечер. Стали жить вместе, она готовит, убирает, я ее развлекаю, катаю. У ней даже водительских прав не было. А то сядем и в четыре руки бренчим что-нибудь. Элизе. Полонез Огинского на этой стороне шарика не учат, а Бетховену учат. И Шопен, конечно.

С тещей я так и не виделся ни разу. Видел фотографию, худая, крепкая баба. Живет в этой своей… Чиуауе, у нее там дом и бизнес, где-то под Хуаресом, Марица не рассказывает, какой бизнес. Да Марице и дела нет. Марица на медсестру училась, чтобы в Америку попасть - это им в Мексике голову морочат, что медсестер Америка ввозят пачками. А…

Марица сначала что, сама не понимала, радоваться ей новой ее семейной жизни или нет. Днем смеялась и напевала, ночью плакала. Да, ей интересно все было - а грустила, по молодости своей загубленной. Ну что я тут ей сделаю.

Ну привыкла. Дошло у нас и до этого дела, а как же. Ну еще бы. Такая молодая деваха вокруг вертится. Не устоишь. В смысле - наоборот, само встанет.

В моем возрасте лучше занятия не придумаешь, чем секс; я как заново родился. В первые недели, как начали, так мы целыми днями кувыркались в постели, не вылазили. С женой мы такого не выделывали, что с ней делали; да и мне повезло, что она наполовину мексиканка, наполовину филиппинка. Была бы на 100% мексиканка - я б у ней живым из постели не ушел; была бы на 100% филиппинка - и десятой доли не испытал бы того, что мне досталось. Филиппинки же скромные, как китайки. Моя тоже сначала все норовила отвернуться, когда лифчик снимает - но мексиканская кровь взяла свое, и такие штуки, такие штуки… наши такого не умеют, или не хотят. А может быть, у наших просто питание другое.

Я Марице не говорю, что уже давно на виагру подсел. Потому что, наверное, в моем возрасте и с моей физической подготовкой, без виагры никак. Ну и что, кто знает? Зато она-то как счастлива. Любимое занятие у нее.

Да… кто бы мне сказал сорок лет назад. Это я лежу, улыбаюсь, смотрю в потолок и рассуждаю сам с собой.

А потом, потом, на следующий день после таблетки, наступает страшная тоска. Как дементор под окном прошел. Хочется умереть просто. Но умереть - легко, забыться, легче чем сон, потому что и сна-то никакого нет. Жить, жить, вот что самое-то ужасное. Жить, и помнить всё, всё, что в жизни было, и понимать, что все это ну совершенно никому не нужно, и мне тоже не нужно, и что лучше бы ничего этого на свете никогда и не было, и не надо было бы никому страдать. Той же девчонке моей. Не соблазнилась бы, вышла бы замуж за какого-нибудь горячего придурка, нарожала бы ему детишек, он бы ее бросил, она бы плакала, и была бы счастлива. А тут – на концерты со мной ходи, да в кино. А в гости – к кому мы в гости пойдем? К соседке Арасели? Ага, здрасьте. У Арасели муж на нас на обоих косо смотрит. Ну типа я – русский мафиозо, она – продажная шкура. Ну уж если араселин муж на нас так смотрит, так что сказать о моих знакомых да родственниках? Для тех я вообще с ума сошел. Поэтому и не хочу ни с кем дела иметь.

И вот такой вот отходняк весь следующий день. На работе вообще стараюсь молчать, чтобы не врезать кому-нибудь.

Нет, постепенно я привык, это только первые месяцы так остро было, почти до суицида. Почти до суицида. Ведь на самом-то деле мысли о суициде, о которых, конечно, не надо бы говорить никому, ни врачам, ни медсестрам, ни друзьям, ни товарищам, от них, если вдуматься хорошенько, удовольствия не меньше, чем от чтения хорошей книжки. Чем они хороши? Да тем, что адреналинчик играет, и понимаешь, что ничего такого ты с собой делать не будешь, и что интересно, в результате чувствуешь себя героем, не потому, что смелый такой, а потому, что сам себе жизнь спас, приняв важное жизненное решение не предпринимать ничего такого. Как заново родился. Главное –ничего не предпринимать, а то затянет на хрен. А может, оно и к лучшему бы. Неизвестно же, что там впереди, есть такое подозрение, что ничего уже хорошего.

Впрочем, проходит этот сплин; заглотну опять таблеточку, и к Марице. Поразительная у нее фигура, ноги худющие, талия тонкая, у нас таких не делают, грудь – ну просто в самый раз по моему вкусу. Наглядеться на нее не могу, какая она у меня красотка. Мне, конечно, здорово повезло с моим сокровищем. Уберечь бы только.

Глаз да глаз нужен, конечно. Проходит мимо дома Арасели, Марица выйдет с ней поболтать, а я смотрю. К Арасели недавно брат приехал из Тихуаны. Этот Рамон так и сверкает глазом да зубами на мою Марицу, мне кажется, дай ему волю – живьем сожрет. По тихуанской визе приехал, на месяц якобы. Эта тихуанская виза – странная какая-то штука. Дают ее якобы тихуанским жителям, для посещения пограничных населенных пунктов, не дальше 25 миль. Сан Диего, то есть. Ну где Сан Диего, там и Лос Анжелес, а где ЛА, там и Сан Франциско. Этих тихуанцев, мне кажется, у нас тут больше, чем в самой Тихуане. Виза дается на год, работать нельзя – но они все работают. Год проработает такой, едет домой в Тихуану. Там берет паспорт двоюродного брата, тоже Рамона, но уже не Санчеса, а Карлоса, и в тот же день обратно. А где двоюродный брат? Да этот двоюродный брат и был-то в Тихуане только раз, когда на него мексиканские документы оформляли, а вообще-то он у нас тут в Сан Карлосе живет.

Стою у окна, смотрю. Арасели уходит в одну сторону, моя Марица направляется к ее дому, ей открывает дверь Рамон, дверь закрывается, все. На улице пусто, в моей голове поднимается какой-то звон. И слегка подташнивает. Что делать, что делать? Смотрю на соседскую дверь не отрываясь, планирую свои дальнейшие действия – вдруг шаги, оборачиваюсь – Марица ходит поливает цветы. Что это было? Показалось мне все? Что показалось? Что мне показалось, и сколько времени прошло? Если три минуты – тогда показалось, а если прошло три часа? Я ж ничего не помню, я просто стоял окаменевший и глядел в окно. На часы ж я не глядел, не до часов.

Потом, к вечеру, до меня доходит, что это опять побочные эффекты. Надеюсь, я не сумасшедший. Надеюсь, нет. Потому что нормально, когда я ничего такого не употребляю, у меня вообще-то вполне трезвый взгляд на вещи. Я как бы прекрасно понимаю цену вещам, да и людям тоже. Поэтому у меня все в общем-то без напряга и получается. Жизнь и вообще.

Поэтому мы живем, как живется, не зарываемся, но и не пригибаемся. Много ездим; не в Европу, конечно, Европу нам не потянуть – нет, но по стране мы поездили порядочно, от Сиэтла до мыса Кеннеди и от Бостона до Сан Диего; любой дешевый мотель с ейчбио нам как второй дом. Иногда кажется, вот так вот поездишь недельку, что ты вообще как бы перестаешь существовать на белом свете.

Привет Родине Первомая!

2005-12-18T20:27:00.000-08:00

Date: Mon, 01 May 2000 11:16:43

Как известно, пролетарии стали праздовать Первомай как день, когда чикагская полиция перемочила некоторое количество чикагских трудящихся. Как и негритянский понедельник в зоопарке, это стало международным праздником.

Интересно другое – а что праздновали чикагские трудящиеся? Собственные похороны? Нет, товарищи! Чикагские трудящиеся праздновали Первомай, первобытный европейский праздник, на который украшают майское дерево, и в ночь на который, вальпургиеву, ведьмы беснуются на своей горе – эти ведьмы, как я понимаю, в эпоху матриархата были жрицами, и их все боялись, когда они праздновали, тем более, что были и человеческие жертвы – например, Снегурочку пожарили же и съели (а родителям соврали, что, мол, улетела, вознеслась, как Христос, каковой, кстати, сам свое мясо и кровь якобы предлагал перед тем, как тоже вознестись).

Прав, прав был Визбор: коммунизм – это молодость мира, забытая, сидящая где-то в подсознании, и выползающая оттуда ночью, когда сон разума и рождает чудовищ.

А зачем его, по Визбору, нужно было воспроизводить молодым? Затем ли, что эти самые "молодые" частенько поставлены в такое положение, что и деться больше некуда, или просто потому что онтогенез повторяет филогенез?

Повторения

2005-12-18T20:26:00.000-08:00

(так; не стоит публикации)

Date: Fri, 21 Jan 2000 09:47:22

А, повторения, повторения... повторения... у наших мозгов такое свойство – замечать рифмы. Обезьянка радуется – это уже было, дежавю, дежавю. В "Матриксе" дежавю – доказательство искусственности окружающей среды – когда кот проходит дважды – значит, карта жизни неровно сшита. Зарифмованная реальность легче интерпретируется, если ж она не зарифмована, возникает ощущение стохастичности, возможно, ложное. Если в течение одного года электростанция, с который ты затребовал дополнительную энергию, взрывается, а пароход, на который ты махнул рукой, мол, не нужен от мне, тонет – это уже рифма и заставляет задумываться, кто, собственно, кем машет.

Life, Programming, Everything

Either OOP or Liskov (choose one)

Generic Data Model

Generic Data Model

Introduction

Tables

ENTITY Table

ATTRIBUTE Table

CONTEXT Table

Conclusion

Chain Calls in Java - a better solution

2 eggs and 100 floors

Monad Genome, part 1

Intro

0, 1, 1+1

Option Monad

Exception Monad

Reader Monad

Church Numerals in Scala

Notes on my relations with CT

my codecamp talk here

Running with SBT

Dealing with Infinities in Your Code - 3

Dealing with Infinities in Your Code - 2

Dealing with Infinities in Your Code - 1

iterable, tree, monad, foundation axiom

A Better Option for Java

How I Installed a TV Antenna

Hidden Monads in Scala

Topics in Coding Style

A Brief History Of Single Exit

Dispatch by Return Type: Haskell vs Java

Subclass and Subtype in Java

Not Just Subtyping

a sample comonad

Why Monoids?

on Variance

inheritance, delegation, decoration, gravitation

Cursor vs Flyweight

Incrementally calculating factorsets (Java class)

Inner Class in Java: Unexpected Volatility

categories: new part posted

Functions

Java Solutions: inheriting chain calls

Java Compiler Warnings 2

Java Compiler Warnings 1

Keyboard Bookmarklets

What To Do with Dispatch of Static Methods for Java

Java's Strong Typing

Experimenting with Covariance and Contravariance in Java Generics

Unlimited Cartesian Product in Java - part 2

Unlimited Cartesian Product in Java - part 1

class Function

Java Pair: a closer look

Java: have a set of pairs, need a map

How Do You Test JavaScript Loading?

Java Style. Iterating over collections

русская клавиатура для вашего браузера

internet is half dead

Taming The Wildcard Generics

The Problem

The Solution

Две Черные Ласты

Ныряя Глубоко - 1

Мой начальник Мыкола Гомец

Понедельник

Саке

Голоса

Viagra, My Friend

Привет Родине Первомая!

Повторения

`ENTITY` Table

`ATTRIBUTE` Table

`CONTEXT` Table