Tag Archives: Programming

Erlangers! USE LABELS! (aka “Stop Writing Punched-in-the-Face Code Blocks”)

Do you write lambdas directly inline in the argument list of various list functions or list comprehensions? Do you ever do it even though the fun itself, or the other arguments or return assignment/assertion for the call are too long and force you to scrunch that lambda’s definition up into an inline-multiline ball of wild shit? YOU DO? WTF?!?!? AHHHH!

First off, realize this makes you look like a douchebag for not being polite to other people or your future self whenever you do it. There is a big difference for the human reading between:

%%% From shitty_inline.erl

do_whatever(Keys, SomeParameter) ->
    lists:foreach(fun(K) -> case external_lookup(K) of
                  {ok, V} -> do_side_effecty_thing(V, SomeParameter);
                  {error, R} -> report_some_failure(R)
                end
          end, Keys
    ).

and

%%% From shitty_listcomp.erl

do_whatever(Keys, SomeParameter) ->
    [fun(K) -> case external_lookup(K) of
        {ok, V} -> do_side_effecty_thing(V, SomeParameter);
        {error, R} -> report_some_failure(R) end end(Key) || Key <- Keys],
    ok.

and

%%% From less_shitty_listcomp.erl

do_whatever(Keys, SomeParameter) ->
    ExecIfFound = fun(K) -> case external_lookup(K) of
            {ok, V} -> do_side_effecty_thing(V, SomeParameter);
            {error, R} -> report_some_failure(R)
        end
    end,
    [ExecIfFound(Key) || Key <- Keys],
    ok.

and

%%% From labeled_lambda.erl

do_whatever(Keys, SomeParameter) ->
    ExecIfFound =
        fun(Key) ->
            case external_lookup(Key) of
                {ok, Value}     -> do_side_effecty_thing(Value, SomeParameter);
                {error, Reason} -> report_some_failure(Reason)
            end
        end,
    lists:foreach(ExecIfFound, Keys).

and

%%% From isolated_functions.erl

-spec do_whatever(Keys, SomeParameter) -> ok
    when Keys          :: [some_kind_of_key()],
         SomeParameter :: term().

do_whatever(Keys, SomeParameter) ->
    ExecIfFound = fun(Key) -> maybe_do_stuff(Key, SomeParameter) end,
    lists:foreach(ExecIfFound, Keys).

maybe_do_stuff(Key, Param) ->
    case external_lookup(Key) of
        {ok, Value}     -> do_side_effecty_thing(Value, Param);
        {error, Reason} -> report_some_failure(Reason)
    end.

Which versions force your eyes to do less jumping around? How about which version lets you most naturally understand each component of the code independently? Which is more universal? What does code like this translate to after erlc has a go at it?

Are any of these difficult to read? No, of course not. Every version of this is pretty darn basic and common — you need a listy operation by require a closure over some in-scope state to make it work right, so you really do need a lambda instead of being able to look all suave with a fun some_function/1 type thing. So we agree, taken by itself, any version of this is easy to comprehend. But when you are reading through hundreds of these sort of things at once to understand wtf is going on in a project while also remembering a bunch of other shit code that is laying around and has side effects while trying to recall some detail of a standard while the phone is ringing… things change.

Do I really care which way you do it? In a toy case like this, no. In actual code I have to care about forever and ever — absolutely, yes I do. The fifth version is my definite preference, but the fourth will do just fine also.

(Or even the third, maybe. I tend to disagree with the semantic confusion of using a list comprehension to effect a loop over a list of values only for the side effects without returning a value – partly because this is semantically ambiguous, and also because whenever possible I like every expression of my code to either be an assignment or an assertion (so every line should normally have a = on it). In other words, use lists:foreach/2 in these cases, not a list comp. I especially disagree with using a listcomp when we the main utility of using a list comprehension is normally to achieve a closure over local state, but here we are just calling another closure — so semantic fail there, twice.)

But what about my lolspeed?!?

I don’t know, but let’s see. I’ve created five modules, based on the above examples:

  1. shitty_inline.erl
  2. shitty_listcomp.erl
  3. less_shitty_listcomp.erl
  4. labeled_lambda.erl
  5. isolated_functions.erl

These all call the same helpers that do basically nothing important other than having actual side effects when called (they call io:format/2). What we are interested in here is the generated assembler. What is the cost of introducing these labels that help the humans out VS leaving things all messy the way we imagine might be faster for the runtime?

It turns out that just like with using assignments to document your code, there is zero cost to label functions. For example, here is the assembler for shitty_inline.erl side-by-side with labeled_lambda.erl:

Oooh, look. The exact same stuff!

(This is a screenshot, a text file with the contents shown is here: label_example_comparison.txt)

See? All that annoying-to-read inline lambdaness buys you absolutely nothing. You’re not helping the compiler, you’re not helping the runtime, and you are hurting your future self and anyone you want to work with on the same code later. (Note: You can generate precompiler output with erlc -P and erlc -E, and assembler output with erlc -S. Here is the manpage. Play around with it a bit, BEAM and EVM are amazing platforms, wide open for exploration!)

So use labels.

As for execution speed… all of these perform basically the same, except for the last one, isolated_functions.erl. Here is the assembler for that one: isolated_functions.S. This outperforms the others, though to a relatively insignificant degree. Of course, it is only an “insignificant degree” until that part of the program is the most critical part of whatever your program does — then even a 10% difference may be a really huge win for you. In those cases it is worth it to refactor to test the speed of different representations against each version of the runtime you happen to be using — and all thoughts on mere style have to take a backseat. But this is never the case for the vast majority of our code.

(I’ve read reports in the past that indicate 99% of our performance bottlenecks tend to reside in less than 1% of our code by line count — but I can’t recall the names of any just now. If you happen to find a reference, let me know so I can update this little parenthetical blurb with some hard references.)

My point here is that breaking every lambda out into a separate named functions isn’t always worth it — sometimes an in-place lambda really is more idiomatic and easier to understand simply because you can see everything right there in the same function body. What you don’t want to see is multi-line lambdas squashed into argument lists that make things hard to read and give you the exact same result once compiled as labeling that lambda with a meaningful variable name on another line in the code and then referring to it where it is invoked later.

The most basic Erlang service ⇒ worker pattern

There has been some talk about identifying “Erlang design patterns” or “functional design patterns”. The reason this sort of talk rarely gets very far (just refer to any of the thousands of aborted ML and forums threads on the subject) is because generally speaking “design patterns” is a phrase that means “things you have to do all the time that your language provides both no primitives to represent, and no easy way to write a library function behind which to hide an abstract implementation”. OOP itself, being an entire paradigm built around a special syntax for writing dispatching closures, tends to lack a lot of primitives we want to represent today and has a litany of design patterns.

NOTE: This is a discussion of a very basic Erlang implementation pattern, and being very basic it also points out a few places new Erlangers get hung up on, like what context a specific call is made in — because that’s just not obvious if you’re not already familiar with concurrency at the level Erlang does it. If you’re already a wizard, this article probably isn’t for you.

But what about Erlang? Why have so few design patterns (almost none?) emerged here?

The main reason is what would have been design patterns in Erlang have mostly become either functional abstractions or OTP (“OTP” in this use generally referring to the framework that is shipped with Erlang). This is about as far as the need for patterns has needed to go in the most general case. (Please note that it very often is possible to write a framework that implements a pattern, though it is very difficult to make such frameworks completely generic.)

But there is one thing the ole’ Outlaw Techno Psychobitch doesn’t do for us that quite a few of us do have a common need for but we have to discover for ourselves: how to create a very basic arrangement of service processes, supervisors, and workers that spawn workers according to some ongoing global state or node configuration. (Figuring this out is almost like a rite of passage for Erlangers.)

The case I will describe below involves two things:

  • There is some service you want to create that is represented by a named process that manages it and acts as its sole interface.
  • There is some configurable state that is relevant to the service as a whole, should be remembered, and you should not be forced to pass in as arguments every time you call for this work to be done.

For example, let’s say we have an artificial world written in Erlang. Let’s say its a game world. Let’s say mob management is abstracted behind a single mob manager service interface. You want to spawn a bunch of monster mobs according to rules such as blahlblahblah… (Who cares? The game system should know the details, right?) So that’s our task: spawning mobs. We need to spawn a bunch of monster mob controller processes, and they (of course) need to be supervised, but we shouldn’t have to know all the details to be able to tell the system to create a mob.

The bestiary is really basic config data that shouldn’t have to be passed in every time you call for a new monster to be spawned. Maybe you want to back up further and not even want to have to specify the type of monster — perhaps the game system itself should know generally what the correct spawn/live percentages are for different types of mobs. Maybe it also knows the best way to deal with positioning to create a playable density, deal with position conflicts, zone conflicts, leveling or phasing influences, and other things. Like I said already: “Who cares?”

Wait, what am I really talking about here? I’m talking about sane defaults, really. Sane defaults that should rule the default case, and in Erlang that generally means some sane options that are comfortably curried away in the lowest-arity calls to whatever the service functions are.  But from whence come these sane defaults? The service state, of course.

So now that we have our scenario in mind, how does this sort of thing tend to work out? As three logical components:

  • The service interface and state keeper, let’s call it a “manager” (typically shortened to “man”)
  • The spawning supervisor (typically shortened to “sup”)
  • The spawned thingies (not shortened at all because it is what it is)

How does that typically look in Erlang? Like three modules in this imaginary-but-typical case:

  • game_mob_man.erl
  • game_mob_sup.erl
  • game_mob.erl

The game_mob_man module represents the Erlang version of a singleton, or at least something very similar in nature: a registered process. So we have a definite point of contact for all requests to create mobs: calling game_mob_man:spawn_mob/0,1,... which is defined as

spawn_mob() ->
    spawn_mob(sane_default()).

spawn_mob(Options) ->
    gen_server:cast(?MODULE, {beget_mob, Options}).

 

Internally there is the detail of the typical

handle_cast({beget_mob, Options}, State) ->
    ok = beget_mob(Options, State),
    {noreply, State};
%...

and of course, since you should never be putting a bunch of logic or side-effecty stuff in directly in your handle_* function clauses beget_mob/2 is where the work actually occurs. Of course, since we are talking about common patterns, I should point out that there are not always good linguistic parallels like “spawn” ⇒ “beget” so a very common thing to see is some_verb/N becomes a message {verb_name, Data} becomes a call to an implementation do_some_verb(Data, State):

spawn_mob(Options) ->
    gen_server:cast(?MODULE, {spawn_mob, Options}).

%...

handle_cast({spawn_mob, Options}, State) ->
    ok = do_spawn_mob(Options, State),
    {noreply, State};

% ...

do_spawn_mob(Options, State = #s{stuff = Stuff}) ->
    % Actually do work in the `do_*` functions down here

The important thing to note above is that this is the kind of registered module that is registered under its own name, which is why the call to gen_server:cast/2 is using ?MODULE as the address (and not self(), because remember, interface functions are executed in the context of the caller, not the process defined by the module).

Also, are the some_verb/N{some_verb, Data}do_some_verb/N names sort of redundant? Yes, indeed they are. But they are totally unambiguous, inherently easy to grep -n and most importantly, give us breaks in the chain of function calls necessary to implement abstractions like managed messaging and supervision that underlies OTP magic like the gen_server itself. So don’t begrudge the names, its just a convention. Learn the convention so that you write less annoyingly mysterious code; your future self will thank you.

So what does that have to do with spawning workers and all that? Inside do_spawn_mob/N we are going to call another registered process, game_mob_sup. Why not just call game_mob_sup directly? For two reasons:

  1. Defining spawn_mob/N within the supervisor still requires acquisition of world configuration and current game state, and supervisors do not hold that kind of state, so you don’t want data retrieval tasks or evaluation logic to be defined there. Any calls to a supervisor’s public functions are being called in the context of the caller, not the supervisor itself anyway. Don’t forget this. Calling the manger first gives the manager a chance to wrap its call to the supervisor in state and pass the message along — quite natural.
  2. game_mob_sup is just a supervisor, it is not the mob service itself. It can’t be. OTP already dictates what it is, and its role is limited to being a supervisor (and in this particular case of dynamic workers, a simple_one_for_one supervisor at that).

So how does game_mob_sup look inside? Something very close to this:

-module(game_mob_sup).
-behavior(supervisor).

%%% Interface
spawn_mob(Conf) ->
    supervisor:start_child(?MODULE, [Conf]).

%%% Startup
start_link() ->
    supervisor:start_link({local, ?MODULE}, ?MODULE, []).

init([]) ->
    RestartStrategy = {simple_one_for_one, 5, 60},
    Mob = {game_mob,
           {game_mob, start_link, []},
           temporary,
           brutal_kill,
           worker,
           [game_mob]},
    Children = [Mob],
    {ok, {RestartStrategy, Children}}.

(Is it really necessary to define these things as variables in init/1? No. Is it really necessary to break the tuple assigned to Mob vertically into lines and align everything all pretty like that? No. Of course not. But it is pretty darn common and therefore very easy to catch all the pieces with your eyes when you first glance at the module. Its about readability, not being uber l33t and reducing a line count nobody is even aware of that isn’t even relevant to the compiled code.)

See what’s going on in there? Almost nothing. That’s what. The interesting part to note is that very little config data is going into the supervisor at all, with the exception of how supervision is set to work. These are mobs: if they crash they shouldn’t come back to life, better to leave them dead and signal whatever keeps account of them so it can decide what to do (the game_mob_man, for example, which would probably be monitoring these). Setting them as permanent workers can easily (and hilariously) result in a phenomenon called “highly available mini bosses” — where a crash in the “at death cleanup” routine or the mistake of having the mob’s process retire with an exit status other than 'normal' causes it to just keep coming back to life right there, in its initial configuration (i.e. full health, full weapons, full mana, etc.).

But what stands above this? Who supervises the supervisor?

Generally speaking, a component like mob monsters would be a part of a larger concept of world objects, so whatever the world object “service” concept is would sit above mobs, and mobs would be one component of world entities in general.

To sum up, here is a craptastic diagram:

Yes, my games involve wildlife and blonde nurses.

Yes, my games involve wildlife and blonde nurses.

The diagram above shows solid lines for spawn_link, and dashed lines to indicate the direction of requests for things like spawn_link. The diagram does not show anything else. So monitors, messages, etc. are all just not there. Imagine them. Or don’t. That’s not the point of this post.

“But wait, I see what you did there… you made a bigger diagram and cut a bunch of stuff out!”

Yep. I did that. I made an even huger, much crappier, more inaccurate diagram because I wasn’t sure at first where I wanted to fit this into my imaginary game system.

And then I got carried away and diagrammed a lot more of the supervision tree.

And then I though “Meh, screw it, I’ll just push this up to a rough imagining of what it might look like pushed all the way back to the SuperSup”.

Here is the result of that digression:

It wouldn't look exactly like this, so use your imagination.

It wouldn’t look exactly like this, so use your imagination.

ALL. THAT. SUPERVISION.

Yep. All that. Right there. That’s why its called a “supervision tree” instead of a “supervision list”. Any place in there you don’t have a dependency between parts, a thing can crash all by itself and not bring down the system. Consider this: the entire game can fail and chat will still work, users will still be logged in, etc. Not nearly as big a deal to restart just that one part. But what about ItemReg? Well, if that fails, we should probably squash the entire item system (I’ve got guns, but no bullets! or whatever) because game items are critical data. Are they really critical data? No. But they become critical because gamers are much more willing to accept a server interruption than they are losing items and having bad item data stored.

And with that, I’m out! Hopefully I was able to express a tiny little bit about one way supervision can be coupled with workers in the context of an ongoing, configured service that lives within a larger Erlang system and requires on-the-fly spawning of supervised workers.

(Before any of you smarties that have been around a while and point out how I glossed over a few things, or how spawning a million items as processes might not be the best idea… I know. That’s not the point of this post, and the “right approach” is entirely context dependent anyway. But constructive criticism is, as always, most welcome.)

zUUID: An Example Erlang/OTP Project

I was talking with a friend of mine yesterday about how UUID v2 seems to have evaporated. We looked into things further and found its not actually included in RFC 4122! One thing led to another and I wound up writing an example project that is yet another UUID generator/utility in Erlang — but this time it actually has duplicate v1 and v2 detection/correction and implements as close to what I can find is defined as UUID version 2 values.

As there are already plenty of UUID projects around I focused on making this one as readable as I possibly could — to include exported documentation, in-source documentation, obvious variable names, full typespecs, my silly little “pure” notation, blatantly obvious bitstring syntax, and the obligatory github presence.

Hopefully some folks newish to Erlang will come along and explain to me what confuses them about that code, the process of writing it, the documentation conventions, etc. so that I can become a better literate programmer. Of course, since the last thing the world needs is another UUID implementation I suppose I would have had better luck with something at least peripherally related to the web. (>.<)

Iterators? We Don’t NEED No Stinking Iterators!

Every so often a request for “implementation of iterators for maps” over hashes/maps/dicts or some other K-V data structure appears on mailing list for a functional langauge. I’ve spent years making heavy use of iterators in imperative languages, and the way they fit into Python is really great. For Python. I totally understand where some of these folks are coming from, they just don’t realize that functional languages are not where they came from.

So… “Is this post the result of some actual event”? Yeah, you got me. It is. On the erlang-questions mailing list someone asked “Are maps ever going to get an iterator?” Again.

Erlang is definitely not Kansas, but people thinking either that it is or (more dangerously) that it should be and then trying to influence the maintainers to make it that way (and then the powers-that-be getting in a panic over “market share” and doing horrible things to the language…) worries me a bit.

There is no faster way to paint a functional language into a corner than to try making it occasionally imperative. Conversely, consider the syntactic corner C++ and Java have painted themselves into by trying to include functional features as after-thoughts where they really didn’t belong.

(I know, I know, death-by-kitchen-sink is a proud C++ tradition. It is becoming one for Java. Even though I hate Java there is no sense in making it worse by cluttering its syntax and littering it with gotchas and newbie-unfriendly readability landmines in the interest of providing features few Java coders understand the point of, especially when the whole concept of state management in a bondage-and-discipline OOP language like Java is to keep everything in structs with legs (not anonymous closures over state that is temporarily in scope…). The lack of such problems were previously one of the main points that favored Java over C++… well, that and actual encapsulation. Hopefully Rust and D can resist this temptation.)

This frustrates me. It is almost as if instead of picking a tool that matches a given job, people learn one tool and then try over time to make a super-powered Swiss Army knife of it. This never turns out well. The result is more Frankenstein’s Monster than Swiss Army knife and in the best case it winds up being hard to learn, confusing to document and crap at everything.

What’s worse, people assume that the first tool they learned well is the standard by which everything else should be judged (if so, then why are they learning anything else?). It follows, then, that if a newly studied LangX does not have a feature of previously used LangY then it must be introduced because it is “missing”. (I do admit, though, to wishing other languages had pattern matching in function heads… but I don’t bring this up on mailing lists as if its a “missing feature”; I do, however, cackle insanely when overloading is compared with matching.)

Let’s say we did include iterators for maps into Erlang — whatever an “iterator” is supposed to mean in a list-are-conses type functional language. What would that enable?

-spec foreach(fun(), map()) -> ok.

That sort of looks pointless. Its exactly the same as lists:foreach(Fun, maps:to_list(Map)) or maybe lists:foreach(Fun, maps:values(Map)). Without knowing whether we’re trying to build a new map based on the old one or get some side effect out of Fun then its hard to know what the point is.

Maybe:

-spec map(fun(), OldMap :: map()) -> {ok, NewMap :: map()}.

But… wait, isn’t that just maps:map/2 all over again?

I think I know where this is going, though. These people really wish maps were ordered dictionaries, because they want keys to be ordered. So they want something like this:

-spec side_effects_in_order_dammit(fun(), map()) -> ok.
side_effects_in_order_dammit(F, M) ->
    Ordered = [{K, maps:get(K, M)} || K <- lists:sort(maps:keys(M))],
    ok = lists:foreach(F, Ordered).

But wait, what order should the keys be in, anyway?

This is a slow, steady march to insanity. “Give me iterators” begets “Let’s have ordered maps” begets “Let’s have ordered iterators for maps” and so on, and eventually you wind up with most of the Book of Genesis in the Devil’s Bible of Previously Decent Functional Languages. All the while, totally forgetting that these things already exist in another form. There are more data structures than just maps for a reason.

This just gets ridiculous, and it isn’t even what hashes are about to begin with.

XML: Xtensively Mucked-up Lists (or “How A Committee Screwed Up Sexps”)

Some folks are puzzled at why I avoid XML. They just can’t understand why I avoid it whenever I can and do crazy things like write ASN.1 specs, use native language terms when possible (like Python config files consisting of Python dicts, Erlang configs consisting of Erlang terms, etc.), consider YAML/JSON a decent last resort, and regard XML as a non-option.

I maintain that XML sucks. I believe that it is, to date, the most perfectly horrible corruption of one of the most universal and simple concepts in computer science: sexps.

ZOMG! Someone screwed up sexps!

Let that one sink in. What a thing to say! How in the world would one even propose to screw up such a simple idea? Let’s consider an example…

Can you identify the semantic difference among the following examples?
(Inspired by the sample XML in the Python xml.etree docs)

Verson 1

<country name="Liechtenstein">
  <rank>1</rank>
  <year>2008</year>
  <gdppc>141100</gdppc>
  <neighbor name="Austria" direction="E"/>
  <neighbor name="Switzerland" direction="W"/>
</country>

Version 2

<country>
  <name>Liechtenstein</name>
  <rank>1</rank>
  <year>2008</year>
  <gdppc>141100</gdppc>
  <neighbor>
    <name>Austria</name>
    <direction>E</direction>
  </neighbor>
  <neighbor>
    <name>Switzerland</name>
    <direction>W</direction>
  <neighbor>
</country>

Version 3

<country name="Liechtenstein" rank="1" year="2008" gdppc="141100">
  <neighbor name="Austria" direction="E"/>
  <neighbor name="Switzerland" direction="W"/>
</country>

Version 4

And here there is a deliberate semantic difference, meant to be illustrative of a certain property of trees… which is supposedly the whole point.

<entries>
  <country rank="1" year="2008" gdppc="141100">
    <name>Liechtenstein</name>
    <neighbors>
      <name direction="E">Austria</name>
      <name direction="W">Switzerland</name>
    </neighbors>
  </country>
</entries>

Which one should you choose for your application? Which one is obvious to a parser? From which could you more than likely write a general parsing routine that could pull out data that meant something? Which one could you turn into a program by defining the identifier tags as functions somewhere?

Consider the last two questions carefully. The so-called “big data” people are hilarious, especially when they are XML people. There is a difference between “not a large enough sample to predict anything specific” and “a statistically significant sample from which generalities can be derived”, certainly, but that has a lot more to do with representative sample data (or rather, how representative the sample is) than the sheer number of petabytes you have sitting on disk somewhere. “Big Data” should really be about “Big Meaning”, but we seem to be so obsessed over the medium that we miss the message. Come to think of it, this is a problem that spans the techniverse — it just happens to be particularly obvious and damaging in the realm of data science.

The reason I so hate XML is because the complexity and ambiguity introduced in an effort to make the X in XML mean something has crippled it in terms of clarity. What is a data format if it confuses the semantics of the data? XML is unnecessarily ambiguous to the people who have to parse (or design, document, discuss, edit, etc.) XML schemas, and makes any hope of readily converting some generic data represented as XML into a program that can extract its meaning without going to the extra work of researching a schema — which throws the entire concept of “universality” right out the window.

Its all a lie. A tremendous amount of effort has been wasted over the years producing tools that do nothing more than automate away the mundane annoyances dealing with the stupid way in which the structure is serialized. These efforts have been trumpeted as a major triumph, and yet they don’t tell us anything about the resulting structure, which itself is still more ambiguous than plain old sexps would have been. Its not just that its a stupid angle-bracket notation when serialized (that’s annoying, but forgiveable: most sexps are annoying paren, obnoxious semantic whitespace, or confusing ant-poop delimited — there just is no escape from the tyranny of ASCII). XML structure is broken and ambiguous, no matter what representation it takes as characters in a file.

Why OTP? Why “pure” and not “raw” Erlang?

I’ve been working on my little instructional project for the last few days and today finally got around to putting a very minimal, but working, chat system into the ErlMUD “scaffolding” code. (The commit with original comment is here. Note the date. By the time this post makes its way into Google things will probably be a lot different.)

I commented the commit on GitHub, but felt it was significant enough to reproduce here (lightly edited and linked). The state of the “raw Erlang” ErlMUD codebase as of this commit is significant because it clearly demonstrates the need for many Erlang community conventions, and even more significantly why OTP was written in the first place. Not only does it demonstrate the need for them, the non-trivial nature of the problem being handled has incidentally given rise to some very clear patterns which are already recognizable as proto-OTP usage patterns (without the important detail of having written any behaviors just yet). Here is the commit comment:

Originally chanman had been written to monitor, but not link or trap exits of channel processes [example]. At first glance this appears acceptable, after all the chanman doesn’t have any need to restart channels since they are supposed to die when they hit zero participants, and upon death the participant count winds up being zero.

But this assumes that the chanman itself will never die. This is always a faulty assumption. As a user it might be mildly inconvenient to suddenly be kicked from all channels, but it isn’t unusual for chat services to hiccup and it is easy to re-join whatever died. Resource exhaustion and an inconsistent channel registry is worse. If orphaned channels are left lying about the output of \list can never match reality, and identically named ones can be created in ways that don’t make sense. Even a trivial chat service with a tiny codebase like this can wind up with system partitions and inconsistent states (oh no!).

All channels crashing with the chanman might suck a little, but letting the server get to a corrupted state is unrecoverable without a restart. That requires taking the game and everything else down with it just because the chat service had a hiccup. This is totally unacceptable. Here we have one of the most important examples of why supervision trees matter: they create a direct chain of command, and enforce a no-orphan policy by annihilation. Notice that I have been writing “managers” not “supervisors” so far. This is to force me to (re)discover the utility of separating the concepts of process supervision and resource management (they are not the same thing, as we will see later).

Now that most of the “scaffolding” bits have been written in raw Erlang it is a good time to sit back and check out just how much repetitive code has been popping up all over the place. The repetitions aren’t resulting from some mandatory framework or environment boilerplate — I’m deliberately making an effort to write really “low level” Erlang, so low that there are no system or framework imposed patterns — they are resulting from the basic, natural fact that service workers form constellations of similarly defined processes and supervision trees provide one of the only known ways to guarantee fallback to a known state throughout the entire system without resorting to global restarts.

Another very important thing to notice is how inconsistent my off-the-cuff implementation of several of these patterns has been. Sometimes a loop has a single State variable that wraps the state of a service, sometimes bits are split out, sometimes it was one way to begin with and switched a few commits ago (especially once the argument list grew long enough to annoy me when typing). Some code_change/N functions have flipped back and forth along with this, and that required hand tweaking code that really could have been easier had every loop accepted a single wrapped State (or at least some standard structure that didn’t change every time I added something to the main loop without messing with code_change). Some places I start with a monitor and wind up with a link or vice versa, etc.

While the proper selection of OTP elements is more an art than a science in many cases, having commonly used components of a known utility already grouped together avoids the need for all this dancing about in code to figure out just what I want to do. I suppose the most damning point about all this is that none of the code I’ve been flip-flopping on has been essential to the actual problem I’m trying to solve. I didn’t set out to write a bunch of monitor or link or registry management code. The only message handler I care about is the one that sends a chat message to the right people. Very little of my code has been about solving that particular problem, and instead I consumed a few hours thinking through how I want the system to support itself, and spent very little time actually dealing with the problem I wanted to treat. Of course, writing this sort of thing without the help of any external libraries in any other language or environment I can think of would have been much more difficult, but the commit history today is a very strong case for making an effort to extract the common patterns used and isolate them from the actual problem solving bits.

The final thing to note is something I commented on a few commits ago, which is just how confusing tracing message passage can be when not using module interface functions. The send and receive locations are distant in the code, so checking for where things are sent from and where they are going to is a bit of a trick in the more complex cases (and fortunately none of this has been particularly complex, or I probably would have needed to write interface functions just to get anything done). One of the best things about using interface functions is the ability to glance at them for type information while working on other modules, use tools like Dialyzer (which we won’t get into we get into “pure Erlang” in v0.2), and easily grep or let Emacs or an IDE find calling sites for you. This is nearly impossible with pure ad hoc messaging. Ad hoc messaging is fine when writing a stub or two to test a concept, but anything beyond that starts getting very hard to keep track of, because the locations significant to the message protocol are both scattered about the code (seemingly at random) and can’t be defined by any typing tools.

I think this code proves three things:

  • Raw Erlang is amazingly quick for hacking things together that are more difficult to get right in other languages, even when writing the “robust” bits and scaffolding without the assistance of external libraries or applications. I wrote a robust chat system this afternoon that can be “hot” updated, from scratch, all by hand, with no framework code — that’s sort of amazing. But doing it sucked more than it needed to since I deliberately avoided adhering to most coding standards, but it was still possible and relatively quick. I wouldn’t want to have to maintain this two months from now, though — and that’s the real sticking point if you want to write production code.
  • Code convention recommendations from folks like Joe Armstrong (who actually does a good bit of by-hand, pure Erlang server writing — but is usually rather specific about how he does it), and standard set utilities like OTP exists for an obvious reason. Just look at the mess I’ve created!
  • Deployment clearly requires a better solution than this. We won’t touch on this issue for a while yet, but seriously, how in the hell would you automate deployment of a scattering of files like this?

Source or Satire?

From time to time I encounter openly discoverable code that is so wild in nature that I can’t help but wonder if the author was writing a machine function or a satirical statement.

Groovy source: ArrayUtil.java

After spending a few days plowing through Java code at the outset of a new Android project I found myself checking around for practical alternatives. In the course of that search (which netted Scala, Groovy and Clojure, in descending order of easy tooling for Android) I stumbled across this gem of a source file in the Groovy codebase. At first I couldn’t really tell if this was a joke about Java’s expressiveness or a functioning bit of code, but then I realized it is actually both — all the more funny because its expressing a cumbersome optimization that will execute on the same JVM either way:

ArrayUtil.java

Breach: A browser as practical satire

Someone from the Erlang world was kind enough to paste a link to Breach — a browser written in node.js. Its so full of meta fail and manifests the very essence of hipster circular logic that… I can only assume it is satire in the same vein as INTERCAL.

breach.cc

IBM SDK for Node.js on System Z

The going question at IBM has, for the last few decades at least, not been “Is it a good idea?” but “Are people deluded enough to pay for this?” This stands in heavy contrast to the countless bouts of genius that have peppered their research and development over the last century.

But IBM is a business, after all, and we’ve all got to eat. IBM was late recognizing that the majority of programmers and other IT professionals had left the world of engineering behind for the greener pastures of pop culture and fansterish tech propaganda, and to play catch up IBM had to innovate. Actually, this is a sort of business genius: IBM realized that tech doesn’t sell as well as bullshit and buzz when it watched Motorola get steamrolled by Intel’s marketing efforts around the original 286.

Intel pitched a bad chip design to tech illiterate execs, deliberately avoiding customers’ engineering departments, and prevailed against Motorola’s vastly superior designs — brilliant, if you don’t mind being a charlatan. Fortunately, Intel has at least occasionally made up for it since then (having been the only ones serious about SSD reliability early on, for example).

IBM has gone one further. I think this must have started as a practical joke at IBM, and then someone realized “Wait! Holy shit! This could be the hipster coup of the century and get us back in the web game!” Har har har. Joke’s on… all of us.

IBM SDK for Node.js v1.1 on System Z

“Process scope variables” in Erlang

I couldn’t have written a more concise satire-by-demonstration on what sucks about bringing the Java-style OOP thinking process as mental/emotional baggage when one starts using Erlang than this short message that appeared on the Erlang-Questions mailing list one day:

> So much time spent for removing one State variable from a few function calls.

much more time will be saved when refactoring from now on.

imagine:
most funs will now have signature:

-spec a(pid()) -> ok.

and most function bodies will look like:
check(Pid),
update(Pid),
return(Pid).

it will be a breeze now.

Like… whoa. That just happened. And it wasn’t sarcastic.

A gloriously sarcastic response can be found here.

A Technically Inaccurate Explanation of Monads

I’ve come across a multitude of technically inaccurate explanations of monads on the web, all intending to explain them in simple terms to FP newbies, most revolving around their use in Haskell. They all suck. This is mine. It also sucks, but I hope it sucks less.

[NOTE: I have no intent here to explain the mathematical concept of monads, the semantic gap between the way the term is used in set theory and in some flavors of functional programming, or any of that high-minded magic. My purpose is to explain what a monad is in terms of a computing utility to a functional programmer. This is a discussion about the sort of tool it is, not the theory behind that tool.]


Imagine using a purely functional language where side effects are verboten and we can’t do IO or anything else useful because of this. The host environment can clearly do IO just fine, otherwise our environment couldn’t do things like read memory locations (or our code) and our program would be useless. So it is obvious the host environment can do things externally that our program itself cannot do directly. This does not prevent us from describing what we wish it would do on behalf of our program, however.

In this way the host environment is sort of like a pantheon of gods and our programs are mere mortal blips of disembodied consciousness — capable of thought, desire and expression but powerless to touch the physical world in any way. All we can do is express our desires as regard the results of our thoughts and appeal to the gods to pity us and take action in accordance with our desires. Whether they take actions on our behalf is entirely up to them.*

With this in mind…
Imagine a function written in SomeLanguage:

int f(x): return x

It takes an integer and returns an integer. So what? The system doesn’t do anything with it so it is practically useless.

Now imagine a wrapper function:

tuple w(int x):
    tuple t = (f(x), "Please put this in STDOUT")
    return t

So w() has taken the output of f() and wrapped it in a tuple that contains the value returned by f() and a prayer to the system gods to “Please put this in STDOUT”. Pretty straight forward. Now the system gods can do whatever they want with it, but our language itself can’t — because talking to STDOUT would be a side effect and that’s strictly forbidden on Planet Functon. What we can do, however, is pray that the gods take mercy on us and act according to our wishes as regard the value that accompanies the prayer.

If this is the best model of a monad you can muster at the moment, then just stop here. This model is sufficient to make the concept of monads useful to you as you write programs that do useful work. (Which is the whole point. Unless you’re an academic, in which case your point is to write a lengthy article in a peer reviewed journal in which your explanation of monads is prefaced with a demonstration of your deep knowledge of set theory and type theory and esoteric discussion of things like monoids and thus make it appear that unfamiliarity with these subjects precludes the ability to use monads in a useful way in functional programs.)

But there are a few unresolved issues above, most of which I won’t address below, but the glaring issue of typing is relevant… (The other glaring issue of the undefined and imaginary syntax of SomeLanguage won’t be addressed at all.)

The type tuple is pretty ambiguous for this use (we could be talking about coordinates or relational values or immutable strings or whatever). How are the gods to know that we have a prayer for them? Should they inspect every tuple, or even every value we dream up, just checking for a “prayer” type? Of course not, they are busy doing immaculate things. We need a more clear signal.

One way to clear this up is to make a function that takes a function, its arguments and a request specification and returns a type prayer whose existence is itself a magical signal to get the attention of the gods. So ultimately a prayer is a type whose definition is a combined value composed of a thingy plus a prayer request regarding that thingy:

prayer p(function z, list l, request r):
    return (z(*l), r())

And then define an action of type request and rewrite w() in a way that returns a prayer:

request q = "Print to STDOUT"

prayer w(int x):
    return p(f, x, q)

Here we have defined a request for the system to perform, passed a reference/pointer/label to the function f() along with its arguments to the prayer maker function p(), which has executed f() along with its argument and returned a bundle of type prayer that contains the original integer return value along with a request to the system gods to do something regarding the bundled value.

Note that in Haskell it is common to define the underlying function (represented here by f()) and its monadic version (represented here as w()) separately. I suppose this isn’t strictly necessary — one could define monads in terms of lambdas — but this is the way things are done.

So we have specified a side effect, but we are only praying that the system takes an action based on our specification. Nothing more. Obviously I’m glossing over the details of how a request object itself is actually defined, but this is the general idea behind how monads are used to write programs in purely functional languages that have side effects.

An interesting consequence of this idea of a program specifying actions instead of actually taking them is that it is now trivial to write a host environment that deliberately ignores all prayers. In this way writing a host environment purely for the purpose of examining the behavior is also trivial. Its the ultimate sandboxing tool. It is equally easy to write a host environment that selectively observes requests, taking only some and ignoring all others, or ignoring some and taking all others.

I believe the abundance of confusing monad explanations to be a side effect of the Haskell community being disproportionately populated with mathematicians, type theorists and set theorists (“for real” or self-educated) and their explanations assume a knowledge base and vocabulary that is foreign and intimidating to most newcomers. The Clojure community doesn’t seem to have this problem, at least not as deeply.

[*It is easy to reverse this metaphor, of course, and imagine that we are uncorporeal gods, capable of thought and expression of our command to the slavish host to do whatever we specify. But I like the “program as mortals, host as gods” way better, because it extends to include the very real case of writing a test host that takes no action and merely observes (or even checks for the correctness of) the program’s behavior.]

Binary Search: Random Windowing Over Large Sets

Yesterday I came across a blog post from 2010 that said less than 10% of programmers can write a binary search. At first I thought “ah, what nonsense” and then I realized I probably haven’t written one myself, at least not since BASIC and Pascal were what the cool kids were up to in the 80’s.

So, of course, I had a crack at it. There was an odd stipulation that made the challenge interesting — you couldn’t test the algorithm until you were confident it was correct. In other words, it had to work the first time.

I was wary of fencepost errors (perhaps being self-aware that spending more time in Python and Lisp(s) than C may have made me lazy with array indexes lately) so, on a whim, I decided to use a random window index to guarantee that I was in bounds each iteration. I also wrote it in a recursive style, because it just makes more sense to me that way.

Two things stuck out to me.

Though I was sure what I had written was an accurate representation of what I thought binary search was all about, I couldn’t actually recall ever seeing an implementation, having never taken a programming or algorithm class before (and still owning zero books on the subject, despite a personal resolution to remedy this last year…). So while I was confident that my algorithm would return the index of the target value, I wasn’t at all sure that I was implementing a “binary search” to the snob-standard.

The other thing that made me think twice was simply whether or not I would ever breach the recursion depth limit in Python on really huge sets. Obviously this is possible, but was it likely enough that it would occur in the span of a few thousand runs over large sets? Sometimes what seems statistically unlikely can pop up as a hamstring slicer in practical application. In particular, were the odds good that a random guess would lead the algorithm to follow a series of really bad guesses, and therefore occasionally blow up. On the other hand, were the odds better that random guesses would be occasionally so good that on average a random index is better than a halved one (of course, the target itself is always random, so how does this balance)?

I didn’t do any paperwork on this to figure out the probabilities, I just ran the code several thousand times and averaged the results — which were remarkably uniform.

binsearch

I split the process of assignment into two different procedures, one that narrows the window to be searched randomly, and another that does it by dividing by two. Then I made it iterate over ever larger random sets (converted to sorted lists) until I ran out of memory — turns out a list sort needs more than 6Gb at around 80,000,000 members or so.

I didn’t spend any time rewriting to clean things up to pursue larger lists (appending guaranteed larger members instead of sorting would probably permit astronomically huge lists to be searched within 6Gb of memory) but the results were pretty interesting when comparing the methods of binary search by window halving and binary search by random window narrowing. It turns out that halving is quite consistently better, but not by much, and the gap may possibly narrow at larger values (but I’m not going to write a super huge list generator to test this idea on just now).

It seems like something about these results are exploitable. But even if they were, the difference between iterating 24 instead of 34 times over a list of over 60,000,000 members to find a target item isn’t much difference in the grand scheme of things. That said, its mind boggling how not even close to Python’s recursion depth limit one will get, even when searching such a large list.

Here is the code (Python 2).

from __future__ import print_function
import random

def byhalf(r):
    return (r[0] + r[1]) / 2

def byrand(r):
    return random.randint(r[0], r[1])

def binsearch(t, l, r=None, z=0, op=byhalf):
    if r is None:
        r = (0, len(l) - 1)
    i = op(r)
    z += 1

    if t > l[i]:
        return binsearch(t, l, (i + 1, r[1]), z, op)
    elif t < l[i]:
        return binsearch(t, l, (r[0], i - 1), z, op)
    else:
        return z

def doit(z, x):
    l = list(set((int(z * random.random()) for i in xrange(x))))
    l.sort()

    res = {'half': [], 'rand': []}
    for i in range(1000):
        if x > 1:
            target = l[random.randrange(len(l) - 1)]
        elif x == 1:
            target = l[0]
        res['half'].append(binsearch(target, l, op=byhalf))
        res['rand'].append(binsearch(target, l, op=byrand))
    print('length: {0:>12} half:{1:>4} rand:{2:>4}'\
                    .format(len(l),
                            sum(res['half']) / len(res['half']),
                            sum(res['rand']) / len(res['rand'])))

for q in [2 ** x for x in range(27)]:
    doit(1000000000000, q)

Something just smells exploitable about these results, but I can’t put my finger on why just yet. And I don’t have time to think about it further. Anyway, it seems that the damage done by using a random index to make certain you stay within bounds doesn’t actually hurt performance as much as I thought it would. A perhaps useless discovery, but personally interesting nonetheless.

Don’t Get Class Happy

If you find yourself writing a class and you can’t explain the difference between the class and an instance of that class, just stop. You should be writing a function.

This antipattern — needless classes everywhere, for everything — is driving me crazy. Lately I see it in Python and Ruby a good bit, where it really shouldn’t occur. I feel like its a mental contagion that has jumped species from Java to other languages.

In particular I see classes used as inter-module namespaces, which is odd since its not like there is a tendency to run out of meaningful names within a single source file (of reasonable length). Importing the module from outside can either import * from foo,or import foo, or from foo import filename, or even import foo as bar (ah ha!) and make flexible use of namespacing where it is needed most — in the immediate vicinity of use.

So don’t write useless, meaningless, fluffy, non-state&behavior classes. Any time you can avoid writing classes, just don’t do it. Write a function. Its good discipline to see how far you can get writing zero classes in an implementation, and then write it with some classes and see which is actually less complex/more readable. In any case writing two solutions will give you a chance to examine the problem from multiple angles, and that’s nearly always an effort that results in better code since it forces you to value grokness over hacking together a few lines that sort of cover the need for the moment (and forgetting to ever come back and do it right).

Or maybe I should be admonishing people to seek flatness in namespaces, since this implies not writing classes that are stateless containers of a bunch of function definitions which incidentally get referred to as “methods” even though they don’t belong to a meaningful object in the first place.

Or maybe I should be railing against the oxymoronic concept of “stateless objects/classes”.

Or maybe I should be screaming about keeping our programming vocabulary straight so that we can finally say what we mean and mean what we say. (Sound advice in all walks of life.)

This last idea is perhaps the most indirect yet powerful of all. But it implies “standards” and so far in my experience “standards” and “computing” don’t tend to turn out very well once we get beyond, say, TCP/IP or ANSI and Unicode.