How I Installed a TV Antenna

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

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

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

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

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

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

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.

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. '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.

1. 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.
2. 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.
3. 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.
4. 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

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?

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

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

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

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)

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 A1 of A that first, if x∈A1 and y∈A1 then xRy, and second, if x∈A1 and xRy then y∈A1

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

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

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

Functions

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.