Stack allocation for Java

In my previous post, I mentioned how useful stack allocation would be for Java, and expressed my surprise, bordering on exasperation, for why it is not available.

Since then, I've thought about how such a thing might work, and realized it is impossible to include without either breaking Java's security model, or throwing away any benefits through additional checks.

First, let me describe a possible implementation: We define a new stacknew operator which acts just like the new operator, except that it returns a reference to an object allocated in the current stack frame, instead of on the heap.

Now for a few design choices, what I would choose, and why:

1. During construction, should all instances of new act like stacknew? No, They should act like normal new. Although it might be convenient for such an automatic conversion to stacknew during construction, it would likely cause problems:
   1. It would encourage the use of stacknew to construct objects not intended for stack-frame lifetime, through behaviors like saving references to themselves in other objects.
   2. It would bring up the question of converting all new instances to stacknew when executed by the object, which would be impossible to get right. Should we convert method code? Static method code? Inherited code from superclasses? Taint all calls made by the object to other objects? It is too messy and not predictable.
   3. Therefore, stacknew must be intended for use on classes specifically designed for it.
2. Should it be possible to determine if the this object was allocated with stacknew? Yes. This will allow special-purpose code that is stacknew-aware to modify its behavior, using calls to stacknew instead of new when it is stack-allocated. Otherwise it would be difficult to write a general-purpose class without passing around a boolean flag indicating which new operator to use. In fact, Object should have a new method, isStackAllocated(), probably public.
3. What should happen when dereferencing a reference to a stack-allocated object whose stack frame returned? This should generate a NullPointerException, or similar. Maybe a new Error subclass would be called for. And this is where the trouble starts...

To fit with Java's model of simply disallowing any sort of unsafe memory access, it must not be possible to successfully dereference a reference to a stack-allocated object whose frame has returned. Well, that doesn't sound so hard! I hear people thinking. But it is hard. Surprisingly so.

So how do you know, when you try to dereference a pointer, whether it points to an allocation in an invalid stack frame? You cannot depend on any property of the memory in that frame. Here are the possible scenarios when trying to perform an access:

1. The object is still there and fine. This is what you would expect during a dereference operation.
2. The frame returned, but no new frame has overwritten that part of the stack yet. This could be considered lucky, but it would be a nasty bug to fix if something changed.
3. The frame returned, and a smaller function overwrote part of the memory but not all of it. This would likely produce some very indeterminate behavior; what if you grabbed a reference out of the corrupted object and then tried to dereference that? Some way be valid while others are not.
4. The frame returned, and other functions completely overwrote the object.

So how do we protect against this? As I said, we cannot trust any of the object's memory. Here is the solution I came up with:

1. Each stack frame containing any stack-allocated object will have a non-zero cryptographically secure identifier (random number) at a known offset from the beginning of the stack frame.
2. Every reference will have a type, either heapnew or stacknew. Probably a bit flag somewhere.
3. Every stacknew reference will contain, in addition to the object pointer, a pointer to the beginning of the stack frame and the value of the stack frame's identifier.
4. On every dereference, the JVM will check if it is a stacknew reference. If so, it will first verify that the frame still exists before finishing the dereference operation. If not, it will throw an exception or error. This verification is performed by matching the frame identifier in the reference to the value expected by looking at the location where the identifier would be if the frame was still alive.
5. Any time a stack frame returns, the identifier field in the frame is set to zero.

Why cryptographically secure? Because otherwise it would be theoretically possible for an attacker to guess what the identifier of a frame might be, and arrange to have a specific memory layout occur, resulting in successfully dereferencing a malicious pointer. This scheme makes it vanishingly unlikely to have a false positive match, malicious or otherwise.

I am reasonably confident that this solution will prevent accidental dereferencing of invalid memory, but it does not sound at all efficient, especially when you account for references needing to be three times their current size.

So, to conclude this surprisingly long-winded post, I am saddened to say that I seriously doubt Java could support a stacknew operator.

But that doesn't stop me from wanting one...

C++ vs. Java

I'm not trying to start any sort of religious war here; I'm writing this because I've been programming in C++ for the past six or seven months after more than three years of professional Java (and more than ten years in personal projects). So I feel like I have an informed opinion.

Unfortunately, my opinion may incense some: Programming in C++ after being used to Java is like slogging through mud. And here's why:

• Auto-completion. Eclipse does it badly for C++, and neither Emacs nor Vim will do it automatically. I'm sure I could set it up, but it still would not be as good at it as Java in Eclipse. I am unaware of other choices (don't even try to suggest Visual Studio; nobody uses Windows for real software development).
• Header files. I need to write one of these, with ancient C include guards around it, for almost every interesting piece of code.
• Prototypes. I need to repeat myself. I need to repeat myself. It's 2014!
• Surprisingly, flexibility of where classes can be written. In Java, if I want to write a new class, it pretty much always gets its own new file, and the name of the file is the name of the class. But in C++? It can go anywhere, including in whatever file I'm writing when I decide I want it. And there is no naming requirement for linking headers with source files.
• Threading is a special case in C++.
• Memory management. I wish there were more options in Java (stack allocation, for example), but it requires too much extra effort in C++, including destructors. Rust has some interesting ideas around this, but it adds to the number of indirect reference types.
• Boilerplate code. Java has some, certainly, but C++ has so much more. Refer back to header files and prototypes. And memory management (std::unique_ptr<actualtype> anyone?). And how many times have you written "virtual ~ClassName() {}"? Or, even worse, "virtual ~ClassName();" in a header and "ClassName::~ClassName() {}" (with its multiple instances of repetition) in a source file?
• Namespaces. Not only do I need to include something, but I still need to either type out the namespace every time, or add a using directive. And then we get back to problems with header files; can't put a using directive there without screwing everything up when someone includes the header. Oh, and they're not implicit based on the file path, so at a minimum I'll need to write each new one twice. Is it obvious yet how much I hate to repeat myself?

But, to be fair, there are a few areas where Java is severely lacking:

• Memory  management. It is really hard to write a no-gc Java program, and it may be impossible without abusing class fields and sacrificing immutable types. Stack allocation would go a long way here. Seriously. Why is this still missing? You could probably do it with a single new keyword, or by overloading the meaning of one of the operators.
• Const. I really miss this in Java. Really, really </Shrek voice>.
• Templates. C++ mostly got this right with weak typing. Java requires strong typing, and you can't really specialize. And they're erased, so you're doubly... Triply screwed.
• Macros and conditional compilation. Less important (to me) than anything else here, but sometimes I really wish I could define a macro that would evaluate into some repetitive multi-line construct that, instead, I need to type out (usually with the help of block-selection and editor macros). Oh, look at that, more repetition...

It's entirely possible that most of this boils down to how expressive the language is. Either way, maybe it's time to learn Go...

Insta-gin

The insta-gin bitters are coming out much better than I expected. I tested them today, and was beyond pleasantly surprised.

First I used a chopstick like I described in my last post, to smell and get a little taste. It was so much more gin-ey than expected that I just had to try a bit more.

I used a small spoon to put a few drops into the bottom of a shot glass, and then topped with vodka. It really tasted like gin! A little bit weak (easily remedied next time), but surprisingly good.

Then I made it into a gin-and-tonic, which was a mistake. It was a little weak already, and it could not stand up to the other flavors in the glass.

Next up (probably tomorrow): A gin martini.

Which reminds me that we're out of olives...

Tasting bitters

Getting a feel for how bitters taste is important, especially when making your own (but also I am realizing I should have done more with the ones I've purchased).

The difficulty, though, is that bitters are, well, bitter. And they are strong! Strong enough that you can't really taste background flavors.

So here are three ways to get an idea of the flavor of bitters:

1. Put a drop onto your palm (use a chopstick if you are macerating your own in a wide-mouthed jar). Rub your palms together, and then cup them and smell.
2. Put a little into some unflavored soda water and taste that.
3. Just taste a little straight. This might give you an idea of the strength, but you probably won't get much out of it, though, and it will probably wreck your ability to taste anything for a few minutes.

As my bitters macerate (steep), I am tasting them with methods one and three every day. I use a chopstick to get a drop to smell, and then I lick the chopstick. So far, the insta-gin has too much orange, so I removed the bit of peel, and the gentian root is really really bitter; the longer it sits, the stronger it gets and the longer it lingers.

Mason Jars

Mason jars are ideal for making bitters. They are non-reactive, food-safe, lidded (to prevent excessive evaporation), and clear (well, you can get other colors, but I like the clear ones). So I just went out and bought a few more, which is apparently a difficult task on New Years Day. The phrase "The City that Never Sleeps" apparently does not include New Years Day. I guess everyone is nursing their New Years Eve hangovers.

But luckily, there is a pharmacy not far from the apartment that is open, and they had 12oz jars, which are perfect. I don't plan to make large batches of bitters (some recipes call for entire 750ml bottles of vodka), and I really just need a place to store the extra liquid that won't fit in the dropper bottles. I'm using a couple of large jars for macerating (the fancy bitter-making term analogous to steeping when making tea), but these small jars should be much easier to store in a drawer or other dark and out-of-the-way spot.

Here is a picture of my two currently macerating batches, with the new empty jars in between. The jar on the left is the "Essence of Gin" (or maybe I will call it "Insta-gin," depending on how good it is). The jar on the right is just Gentian root. I think I may have made too much of that one...

Homemade Bitters

In April, my wife and I (and our pets) moved from Schenectady to Brooklyn so I could take a new job with Google. Unfortunately, my beer brewing equipment could not accompany us on this journey.

To put this into perspective, I've been brewing beer since late 2008. We moved in early 2013. That's about four and a half years. It was my main hobby, at least through the warmer months.

Luckily, my awesome wife noticed that I'd lost my main hobby, and came up with a replacement. For Christmas she gave me a binder with about twenty recipes for homemade bitters, along with some dropper bottles and Gentian root (more on this later).

Recently, I've been getting more into trying bitters. There is a kitchen store not far from our apartment that has a large selection. Of course they have the standards (Angostura and Peychaud's), but they also have a large number of less well-known items. At least, they are to those of us new to the bittering world. I've purchased a few bottles from them, but each is around $20, which is a little beyond my impulse purchase price. Especially for a bottle smaller than my hand.

So, coming back around, my wife decided that homemade bitters might be a good substitute for beer brewing while we are living in an apartment. Her recipe book, assembled from Google searches, came with a few easy recipes and a few complex ones. I, of course, chose not to follow any of them (yet). To me, recipes are for inspiration.

But before I describe my current concoctions, I will cover the bittering base ingredients, as I've discovered from various search queries. I do not yet know much about these herbs and spices, beyond what the packages say and how they smell:

• Angelica root: Smells sweet, like a picturesque morning on the shore of a mountain lake, condensed into something that looks like sawdust.
• Cinchona bark: A very mild smell, like peppery wood. This is the main flavoring in Tonic water (quinine).
• Gentian root: Seems to be the most common modern bittering agent (similar to how hops replaced virtually everything else used for bittering beer). Smells like peppery wood, but much stronger than Cinchona bark.
• Quassia chips: Smells very clean, mixed with something like a Tibetan store that burns incense, but very weak.
• Wormwood: Smells like chamomile tea.

And, of course, there needs to be some kind of liquid. I am using Spirytus grain alcohol (96% ABV) because I could not find overproof vodka at the local liquor store. But they had this, and I think I can mix it with vodka if I want something in between. The higher the alcohol content, the more efficient (fast) the flavor extraction from the flavoring ingredients.

My first batch is just Gentian root and Spirytus. A bunch of the recipes call for drops of Gentian extract, so I am making my own. I went with 200ml Spirytus with 15g Gentian root, ground up in my spice grinder. I expect it will need to sit for ~1 week, with daily agitation.

Because I could not wait, though, I am also making something I will call Essence of Gin, if it comes out well. I am reluctant to post the recipe because I have no idea how it will turn out, but hopefully anybody that finds it will read this paragraph first.
Ingredients:

• 50ml Grain Alcohol
• 1/2 tbsp (about 30) Dried Juniper Berries
• Pinch of Angelica Root Powder
• Pinch of Cinchona Bark Powder
• Pinch of Celery Seed
• 2 Fennel Seeds
• 1in² Fresh Orange Peel, with the pith scraped off

I plan to agitate this daily, and I expect it will be ready in ~2 weeks. But I honestly have no feel for making bitters yet, so please don't try this recipe unless you know what you're doing and it actually looks good to you. And if you do know what you're doing, please leave suggestions in the comments.

Oh, and something I have yet to see on bitter recipes: The reasons I chose the ingredients:

• Juniper berries: Because this is the main flavoring of Gin, and I want a bitter that I can add to vodka to make it taste reminiscent of gin, or add to gin to make it even more gin-ey.
• Angelica root: Because the package of Juniper berries said that they were a substitute for Angelica, and because the Angelica package said it adds some sweetness, and because it smelled good. I used very little because I am pretty sure it is also quite bitter.
• Cinchona bark: Because gin-and-tonic tastes good, and this might add a little bit of tonic flavor.
• Celery seed: Because I like them, and think it might add a clean flavor.
• Fennel seeds: I looked at a gin recipe, and it used licorice root to cover up any bitterness. I don't have licorice root, but fennel has an anise flavor. Hopefully this won't do much but add a hint in the background (I don't really like anise).
• Orange peel: The gin recipe also used orange peel, and I thought it sounded like a good idea. Hopefully a weak citrusey background flavor.

Scientific Theories

Earlier today, my sister-in-law asked me about science, and evolution specifically. She described how this morning, after going to church with her husband's family, she told her sister-in-law that she had some questions about how the bible fits with evolution. She used the phrase, "Since evolution is basically a fact." Her sister-in-law responded with, "It's really more of a theory."

As soon as I heard her say, even secondhand, "It's really more of a theory," I could feel myself starting to get worked up. As you can see, I haven't rambled in a long while (as I write this, I'm hoping that my blog hasn't been garbage-collected). But this brief conversation inspired me to compose a response.

The phrase, "It's really more of a theory," (and its cousin, "It's just a theory,") is evidence of a general misunderstanding of science. So I'm going to write a basic tutorial of the scientific method and how it produces theories.

So, for starters, here is a simplified version of the scientific method:

1. Observe an event.
2. Come up with a general rule that describes what you observed. It needs to predict the behavior of similar events that you have not yet observed. Call it a hypothesis.
3. Invent a way to test the predictions of your hypothesis.
4. Apply your test to one or more thus-untested events.
5. If you disproved your hypothesis, then that really sucks. You can give up and throw it out, or you can modify it to match your new observations and jump back to step 3.
6. If you get here, then congratulations, you may now call your hypothesis a theory!

Now let's try this out: I'm going to invent a theory (you may know of a similar one, some guy named Isaac Newton came up with it back in the late 1600s):

• Observation (1): I dropped a baseball, and it fell to the floor.
• Hypothesis (2): The floor possesses something which I will call gravity, which attracts baseballs.
• Test (3): I will drop another baseball (to make sure that this gravity affects all baseballs, and not just the first one), and a bowling ball (to make sure that gravity does not affect any other objects).
• Application (4): The second baseball also fell to the floor. Great, so far so good! But the bowling ball also fell... That means my hypothesis is either incomplete, or simply wrong.
• Modification (5): The floor possesses something which I will continue to call gravity, which attracts all objects.
• Test (3): I will drop a book and an egg. I can't test all objects, but at least I can be sure it will work for these.
• Application (4): The book fell to the ground. The egg did too, and it broke. That's interesting... I wonder if it would have broken if I dropped it from a smaller height, like half an inch?
• Modification (5): My hypothesis is accurate so far, but I could modify it to describe acceleration... Maybe tomorrow.
• Theory (6): Yay! I have just invented the theory of gravity!

You may notice that my theory is incomplete (it only says that the floor attracts objects, and it does not describe how that attraction affects things; do they fall at a constant rate? Do they accelerate? Do heavier objects fall faster than lighter objects?). That's fine. It only needs to describe my observations. It's now up to others to test with other floors, other objects, etc. They can expand my theory as necessary to fit their own observations.

So what does this mean? You may be familiar with gravity yourself. Is it a theory, or is it a fact? Or is it a law?

What's a law? In science, a law is a really old and well-proven theory (usually with some mathematical formulas attached to it). It has stood the test of time. No experiment has falsified (disproved) it. As for facts, that's a more interesting (i.e. difficult) distinction. Theories can be facts, but the problem is that if any experiment disproves the theory at any time in the future, then it must not have been a fact.

Gravity is all of these. It is a theory because it predicts the behavior of as-yet unobserved events, based on previous observations. It is also a law, because the theory has not been disproved after more than three hundred years. Based on this, it is safe to call gravity a fact.

But, if you drop a cantaloupe tomorrow and it does not fall, then you have just disproved the theory of gravity. That does not falsify all of the other observations about gravity up until now, though. Somebody will need to come up with a new theory that not only explains three hundred years of experiments proving gravity, it will also need to explain why your kooky cantaloupe floats.

So how does this relate to evolution and the bible? Well, I was hoping I could just stop here and let you extrapolate from the discussion about gravity so I wouldn't have to touch that topic. I strongly believe that religion is an extremely personal choice, and should therefore be extremely private. I don't like to talk about it, and I especially don't like the idea of one person telling another what to believe. I'm already about to step beyond my comfort zone. But here we go:

Evolution (driven by natural selection) is a theory. It was first described in detail by Charles Darwin about a hundred and fifty years ago. It provides a method for predicting how species came to be in their current form. Fossil evidence adds weight by showing the intermediate species that existed in the past. Until evolution was accepted by scientists, the prevailing theory was that all species were fixed at the time of creation, part of a divine plan that laid out all life on Earth.

So how could we disprove evolution? Scientists ask themselves this kind of question every day, about all sorts of different theories. A scientist's job is to look at a theory and try to figure out new ways to disprove it. Every time somebody fails to disprove a theory, the theory becomes stronger and closer to being considered a law; for example, NASA is still performing experiments to try to disprove parts of Einstein's theory of special relativity (take a look at LISA on Wikipedia).

But really, what would it take to disprove evolution? That's a hard question. The only thing I can think of would be to find a species that exists in multiple places, which could not have been transported from one place to the other. This is difficult on Earth, mostly because people move things around, but also because Pangaea and continental drift mess up the fossil record. But, for example, if the first ship from Earth to an Earth-like planet in another star system discovered Earth plants and animals, of identical species to those that exist here on Earth, that would disprove evolution as it currently exists.

What would that mean? We would need a new theory that explains why Earth life is all related to each other, and also how planet-X had the same types of life. Panspermia would be a start, but then perhaps evolution would be back in the game.

Before closing, I want to emphasize this point: Disproving evolution is a hard... not enough emphasis... HARD task. At this point, it is at about the same order of difficulty as disproving gravity. I would even say that we are past the point where it could be disproved completely; any contrary evidence would just be used to make minor modifications, resulting in a stronger theory.

So don't ever let somebody tell you, "Evolution is just a theory."