Java: if you have trouble declaring a static hashmap…
Java (as of version 6, aka 1.6) does not allow you to declare a static HashMap as conveniently as an array. Still, you have the alternative of using a static block in your class to add fields. Take this example:
import java.util.HashMap;
public class StaticHashMapTest {
private final static HashMap constants = new HashMap();
static
{
constants.put("A", "The Letter A");
constants.put("B", "The Letter B");
constants.put("C", "The Letter C");
}
/* Rest of your class that needs to know the consts */
}
This works fine. But then you want to map something a little more complex than a string to another string. And I don't mean something very complex... just, say, a string to a string and an integer (yes, you'd like to use some kind of "pair object", but it looks like Java does not have it).
So you go and try to do things The Java Way (tm) and create a tiny class just to hold your two values:
import java.util.HashMap;
public class StaticHashMapTest {
private class Pair {
final String name;
final int number;
public Pair(String name, int number) {
this.name = name;
this.number = number;
}
}
private final static HashMap constants = new HashMap();
static
{
constants.put("A", new Pair("The Letter A", 123));
constants.put("B", new Pair("The Letter B", 456));
constants.put("C", new Pair("The Letter C", 789));
}
/* Rest of your class that needs to know the consts */
}
This should suffice, right? I even made the Pair class private to my class, to ensure good information hiding (that's what Java is all about, right?). Turns out this fails to compile:
StaticHashMapTest.java:18: non-static variable this cannot be referenced from a static context
constants.put("A", new Pair("The Letter A", 123));
^
StaticHashMapTest.java:19: non-static variable this cannot be referenced from a static context
constants.put("B", new Pair("The Letter B", 456));
^
StaticHashMapTest.java:20: non-static variable this cannot be referenced from a static context
constants.put("C", new Pair("The Letter C", 789));
^
3 errors
The error messages say that my "new" operators are failing due to the use of the "this" variable, which is not there at all! But hey, we can call "new" from a static context, can't we? We just did that when declaring the HashMap itself.
It turns out that the problem is that we're using an inner class. Objects from inner classes hold a "this" reference to their parent object (yes, as in myInnerObject.this.myParentAttribute... go figure), hence the trouble with the implicit "this" reference.
You have to make it a static inner class, which means it doesn't know anything about the enclosing class. Yes, that's yet another meaning for the word "static" in programming. Due to this peculiar meaning, inner classes are the only context where you can use the "static" qualifier to a class declaration in Java.
This, therefore, works:
import java.util.HashMap;
public class StaticHashMapTest {
private static class Pair {
final String name;
final int number;
public Pair(String name, int number) {
this.name = name;
this.number = number;
}
}
private final static HashMap constants = new HashMap();
static
{
constants.put("A", new Pair("The Letter A", 123));
constants.put("B", new Pair("The Letter B", 456));
constants.put("C", new Pair("The Letter C", 789));
}
/* Rest of your class that needs to know the consts */
}
And that's Java for you.
Lua’s and-or as a ternary operator
The same is true for Python, just replace “true”, “false” and “nil” with “True”, “False” and “None”.
Lua is a nice programming language, which allows for readable and concise code. One of my favorite idioms in the language is this:
x = a and b or c
which usually works like the C ternary operator, “a ? b : c”, but in a more readable fashion. This works in Lua because the “and” and “or” operators return their matching value when they get a “true” value (anything other than false and nil).
One thing to keep in mind though, is that this is really “and and b or c” and not “a then b else c”. There’s one big difference: when you want to have nil or false in your “then” value.
Lua 5.1.4 Copyright (C) 1994-2008 Lua.org, PUC-Rio > = true and 10 or 20 10 > = false and 10 or 20 20 > = true and nil or 20 20
An ugly alternative is to do “not a and c or b”, like this:
> = not true and 20 or 10 10 > = not false and 20 or 10 20 > = not true and 20 or nil nil
But at this point it’s better just to use an “if” statement. (This hack works around the then-as-nil case, but not else-as-nil, of course.)
So, keep in mind that you should use the “a and b or c” construct as if-then-else only if you know that your “b” value is not nil or false.
It’s better, however, to use this construct for what it is. This behavior is not flawed, it is just different, and it has its own uses. For example, it is very useful to check if a table exists:
x = tbl and tbl.key
And to define fallback values:
x = tbl and tbl.key or "missing!"
Note that the above line reads naturally, and you wouldn’t be able to do that with one “?:” operator in C.
Programming language research is a Human Science
Some people often tell me that, due to my various interests, they actually find it weird that I ended up studying Computer Science and not some of the Humanities. I try to explain them that my specific field of interest, programming languages, is actually a Human Science. And that is so for one simple reason: if there was no people, if computing was restricted to computers and there was no human factor, machine language — the binary code that processors actually run — would be enough. Programming languages exist because of people, not because of computers.
This quote puts it rather nicely:
“Programming is a science dressed up as art, because most of us don’t understand the physics of software, and it’s rarely if ever taught. The physics of software is not algorithms, data structures, languages and abstractions. These are just tools we make, use, throw away. The real physics of software is the physics of people.
Specifically, our limitations when it comes to complexity, and our desire to work together to solve large problems in pieces. This is the science of programming: make building blocks that people can understand and use easily, and people will work together to solve the very largest problems.” — Peter Hintjens et al., ØMQ - The Guide
Programming languages are the bridge we use to communicate our ideas to the machine, but also to communicate our ideas among our fellow programmers, and even to ourselves. Like natural languages, programming languages are constantly evolving (at a much faster pace, even!), as we try to balance the tension between being precise and unambiguous and being understandable and eloquent; to be able, in the same piece of prose, to tell a machine what to do and to tell another person what we mean. And this is by no means a matter of numbers.
Understanding, at last, the Y Combinator - a programmer-friendly perspective
This post is aimed towards comp sci students who studied lambda calculus but never really “got” the Y Combinator, the best-known fixed point combinator. Lambda calculus does not feature recursion, but using fixed point combinators, we can easily produce recursive functions, making it able to describe all computable functions (in other words, equivalent to a universal Turing machine). Here’s our friend Y:
Y = λf·(λx·f (x x)) (λx·f (x x))
With it, you can write a non-recursive version of a function, apply Y to it, and you get the equivalent recursive functionality, even though lambda calculus does not provide recursive functions. It’s not hard to understand what it does, but the mystery for me was always how it does it.
In my experience, a major barrier to understanding it was having to deal with several unfamiliar things at the same time, each of which makes a different part of my brain uncomfortable: the semantics of lambda calculus, the syntax of lambda calculus, and the problem at hand.
So, to focus on the problem at hand, let’s get rid of the rest.
Semantics of lambda calculus: untyped lambda calculus amounts (roughly speaking) to a very simple functional language with call-by-name evaluation. All we have is functions, but through smart encodings we can represent numbers and booleans with nicely crafted chains of functions. To simplify things, then, let’s just assume we have numbers, arithmetic, if/then/else. Next, let’s get rid of call-by-name and switch to call-by-value, which is what we’re used to use in modern programming languages. To do this, we’ll have to use the call-by-value variant of Y, which is called Z:
Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))
Yes, it is longer, but believe me, it’s easier to understand, and once you get this, it’s just a matter of recalling call-by-name from those old classes and applying the same logic to Y.
Next, the syntax: lambda calculus is made of terms, abstractions and applications, which in programming language parlance are just variables, function declarations and function calls. Therefore, we can simply rewrite it using some familiar notation and get rid of the weird syntax and precedence rules for now. I won’t even use a functional language: let’s take a restricted form of Lua, using only features provided by lambda calculus to make the syntax clearer:
Z = function(f)
return (function(x)
return f(function (y)
return (x(x))(y)
end)
end)(function(x)
return f(function (y)
return (x(x))(y)
end)
end)
end
All right, it’s not exactly readable. But we’ll get there. Assuming you’re comfortable with functions as first-class values that can be returned and passed as arguments, the weirdest thing here is that in the first return we have a function being declared and called “inline”, receiving as a parameter another function identical to itself. Let’s make this flow a bit clearer by using local variables, but strictly as “aliases” (that is, it won’t run any different, so we don’t use any features that’s not part of lambda calculus — note that the our use of variables will be equivalent to macro substitution:
Z = function(f)
local f1 = function(x)
return f(function (y)
return (x(x))(y)
end)
end
local f2 = function(x)
return f(function (y)
return (x(x))(y)
end)
end
return f1(f2)
end
Ok, so this is the function we want to understand. It still makes no sense, but we can see that Z calls one function (f1) passing to it an identical function (f2), which on its turn returns another function that uses something that calls itself (x(x)). A strong scent of self-reference in this function — no wonder, as we know the key to recursion is in there somewhere. But let’s stop trying to reverse-engineer it. Let’s build it instead.
First, let’s recall what this function is good for. What we’d like to have is recursive functions, like this one that calculates the factorial:
fact = function(n)
if n == 0 then
return 1
else
return arg * fact(n-1)
end
end
But we can’t have this in lambda calculus. In fact all of it is fine, except for the recursive call to fact(). We don’t have recursion yet.
The best we can do is to write a function that does one step of the recursion and leaves the next step to be done by someone else. Like this:
stepper = function(next_step, n)
if n == 0 then
return 1
else
return arg * next_step(n-1)
end
end
However, I said we would only use features provided by lambda calculus, which means we don’t have multiple arguments. Fortunately, through currying, we can get the equivalent to multiple arguments. This is one aspect of lambda calculus which I won’t hide in Lua syntax because it will come handy in our understanding. We’ll need to make stepper like this:
stepper = function(next_step)
return function(n)
if n == 0 then
return 1
else
return n * next_step(n-1)
end
end
end
The difference is that now, instead of doing stepper(some_next_step, 5), we have to do stepper(some_next_step)(5).
What this stepper construction makes clear is that we now have a “factory” function that returns our would-be-recursive function, except it only runs one step and uses another function that knows how to run the next step. You can think that stepper(next_step) actually returns a “step”, which is then run by calling it with (5).
But we need a function to run the next step to pass to stepper. How to obtain it? We call the factory to get the next step. Yes, like stepper(stepper).
Indeed, note that if we run stepper(stepper(stepper(stepper(stepper(stepper())))))(5), we get the equivalent result as fact(5). (You can try it in the Lua interpreter!)
Of course, we don’t want to write it like that. The plan, therefore, is to get a function that combines all these calls. It’s time for the combinator:
combinator = function(stepper)
-- ?
end
This function is meant to return something to replace all these nested stepper()s, so we want it to return a function that accepts our input argument:
combinator = function(stepper)
return function(arg)
-- ?
end
end
And it needs to run stepper() on the argument, of course, so it computes our desired function. But what will we pass as the next step?
combinator = function(stepper)
return function(arg)
return stepper( --[[ ? ]] )(arg)
end
end
Well, if what we want to produce is stepper(stepper(stepper(stepper(... then maybe what we need is to pass it stepper() again?
combinator = function(stepper)
return function(arg)
return stepper(stepper)(arg) -- no!
end
end
This is wrong because it will only run stepper twice (and of course we know the combinator doesn’t look like this). Think of stepper(stepper) function as it runs. If we pass 5 as the argument we get stepper(stepper)(5). It will get 5 as n and stepper as the next_step argument. It will eventually call next_step(n-1), that is stepper(4). But stepper expects a function as the argument, and not a number. In fact, if we run this in the Lua interpreter we get a type error. (In untyped lambda calculus we have no notion of “type error”, of course: what we get is just a lambda expression that makes no sense for us.)
We need to give stepper a function, so looks like we’ll have to make one.
combinator = function(stepper)
local some_function = function()
-- ?
end
return function(arg)
return stepper(some_function)(arg)
end
end
(Again, I’m using a local variable here strictly as a “macro substitution”, just to make things more readable.)
To find out what to put in some_function, let’s think of what it will be used for. It will be passed to stepper, and therefore be used as the
combinator = function(stepper)
local some_function = function(arg)
-- ?
end
return function(arg)
return stepper(some_function)(arg)
end
end
If we’re receiving a parameter, it’s fair to assume we’ll have to do something with it. What we want to do with our input arguments is to run steps on them, so let’s get a step with stepper and do it.
combinator = function(stepper)
local some_function = function(arg)
return stepper( --[[ ? ]] )(arg)
end
return function(arg)
return stepper(some_function)(arg)
end
end
Oh-oh, we’re back to the problem of what to give stepper! Does this mean we got into a loop? Well, note that if we just kept on doing the same, we would get the equivalent to stepper(stepper(stepper(...))):
combinator = function(stepper)
local and_yet_another_step = -- ... !!!
local yet_another_step = function(arg)
return stepper(and_yet_another_step)(arg)
end
local another_step = function(arg)
return stepper(yet_another_step)(arg)
end
return function(arg)
return stepper(another_step)(arg)
end
end
But no, it does not mean we’re stuck in a loop. It means we’re getting close.
What we missed is that when we considered what to pass to the first stepper, we simply said it had to be a function taking the numeric argument. But what we want is a function that returns the result of stepper’s computation, but also produces the function for the next step! What we need is another factory-style function like when we transformed fact into stepper, that not only goes down one step, but captures the whole notion of making a function that goes down one step, while at the same time getting rid responsibility of figuring out how to descend to the next level, like when we did when we got read of the recursion — just assume you get what you need as a parameter:
combinator = function(stepper)
local make_step = function(next_step)
return function(arg)
return stepper(next_step)(arg)
end
end
return function(arg)
return stepper(make_step)(arg)
end
end
With a function like make_step, we can produce as many steps as we want. If you are mathematically inclined, by now you may be thinking of induction: yes, have we just constructed a way of solving one step of our problem assuming we have the solution for the next. That’s the spirit.
So, are we there yet? Does this work?
Not yet. Remember when we tried to do stepper(stepper)? It didn’t work because stepper doesn’t want a factory as an argument. It wants an actual step (remember that in our example it will use it to get the factorial of n-1). In other words, we don’t want to pass it a factory like make_step. We want make_step to make us a step. So let’s call it!
combinator = function(stepper)
local make_step = function(next_step)
return function(arg)
return stepper(next_step)(arg)
end
end
return function(arg)
return stepper(make_step( --[[ ? ]] ))(arg)
end
end
Ok, we’ll call it, but what will we give it? Let’s look at what the argument of make_step is used for.
Wait a second, it is used to make a step as well! So, do we just give it… itself?
combinator = function(stepper)
local make_step = function(next_step)
return function(arg)
return stepper(next_step(next_step))(arg)
end
end
return function(arg)
return stepper(make_step(make_step))(arg)
end
end
Yes, we pass it to itself. And we do the same with next_step too, since we’re doing the exact same thing. You see, here is where everything comes together: to have recursion, we need to have self-reference; and in lambda calculus, while a lambda term cannot reference itself in an abstraction (function definition), we have that a lambda term, when bound to a variable, can be applied to itself. The function above is indeed a fixed point combinator.
You may be finding strange that make_step passes itself as a parameter, then calls itself passing itself as a parameter… is this an infinite loop? Not necessarily, because in between each step, we don’t run stepper(next_step(next_step)) right away. It is “packed” inside a function(arg)...end. (These are the extra lambdas that the Z combinator has compared to the Y combinator.)
Speaking of that, is this code the same as the straight Lua translation of the Z combinator I presented above? Let’s recap:
Z = function(f)
return (function(x)
return f(function (y)
return (x(x))(y)
end)
end)(function(x)
return f(function (y)
return (x(x))(y)
end)
end)
end
Doesn’t look much like it, does it? But let’s take a closer look at our combinator. Turns out that in that final return, instead of building that step function explicitly, we can simply call make_step and get the same results:
combinator = function(stepper)
local make_step = function(next_step)
return function(arg)
return stepper(next_step(next_step))(arg)
end
end
return make_step(make_step)
end
(In compiler terms, it is as if the first iteration had been “unrolled” before.)
Remember when I said the local variables were just macro substitutions? If we expand the two instances of make_step, we get this:
combinator = function(stepper)
return (function(next_step)
return function(arg)
return stepper(next_step(next_step))(arg)
end
end)(function(next_step)
return function(arg)
return stepper(next_step(next_step))(arg)
end
end)
end
Now, the only difference is that stepper is being called inside function(arg)...end, while in the other one it’s being called outside. It works the same, because the purpose of function(arg)...end there is just to “hold” the expansion of arguments between each call of stepper. We need this because Lua does not use call-by-name. To make our function just like Z, we do this:
combinator = function(stepper)
return (function(next_step)
return stepper(function(arg)
return next_step(next_step))(arg)
end)
end)(function(next_step)
return stepper(function(arg)
return (next_step(next_step))(arg)
end)
end)
end
There we are! The exact same function, only with different variable names.
As we can see, there’s nothing magical about the Y combinator: it produces recursion by using the only form of self-reference provided by the lambda calculus, which is self-application of variables. To get the loop started, since there’s no way to bind the outermost abstraction (function) to a term (variable) so it can apply to (call) itself, it is simply written down twice.
I tried to explain this this as clearly I could (given the assumptions I made about prior knowledge about programming languages and basic lambda calculus). This was actually the flow of thought I followed when understanding the combinator. It clearly follows a “programmer” mindset, which may not be the best method for everyone, but I hope it may be useful for others as it was for me. Corrections, comments and suggestions are welcome.