Sunday, July 15, 2018

The ROS Service/Topic abstractions

Although I quickly outlined the two messaging facilities of ROS (topics and services), I then focused on possible underlying I/O models, and said that a polling mechanism makes for a good primitive.

I think it's clear that without the ability to poll multiple event sources, it's hard to implement efficient asynchronous IO. On the other hand, the opposite direction is really easy. Let's take the code from last time:
rospy.poll(sub1, sub2)
data = sub1.receive()
if data is not None:
    rospy.loginfo(rospy.get_caller_id() + "I heard %s", data.data)
data = sub2.receive()
if data is not None:
    rospy.loginfo(rospy.get_caller_id() + "I heard %s", data.data)
To perform a blocking receive, all you have to do is write this:
rospy.poll(sub)
data = sub.receive()
So supporting polling does not push one into nonblocking IO, but not supporting it does push one into blocking IO.

Now let's look a level higher at the actual messaging. ROS provides us with two tools here:
  • topics allow multiple subscribers to receive all messages from multiple publishers;
  • services allow multiple clients to send requests and receive replies from a single server.
You will notice that both types of connections are asymmetric: topic subscribers and servers can't initiate communication (subscribers can't send messages at all). So this pushes us into a specific approach. These can't support arbitrary protocols, right?

Not on their own, but we could use a pair of topics or a pair of services to model a full-duplex connection:
Node 1          Node 2
   --- topic_12 -->    Node 1 publishes to node 2
   <-- topic_21 ---    Node 2 publishes to node 1
or
Node 1          Node 2
   -- service_12 ->    Node 1 is client of node 2
   <- service_21 --    Node 2 is client of node 1
In the first case, you basically send independent messages, in the second case each message gets a response as well. I also want to show a third topology:
Node 1          Node 2
   -- service_12 ->    Node 1 is client of node 2
   <-- topic_21 ---    Node 2 publishes to node 1
This is also full-duplex, and way better aligned to real-world needs. This approach comes rather naturally when designing a system:
  • I (Node 1) want to give my robot (Node 2) commands, for this I need a service.
  • I also want to know my robot's state, for this I need a topic.
  • (and this approach, unlike the others, is easily extended to multiple clients)
That's the value behind the topic/service abstraction: although it seems to constrain you, it actually helps with the patterns that appear in the real world. Another aspect: topics and services are constrained to a single message type (or request/reply message type pair). How do you work with that? Easy, use separate services and topics for different kinds of data. What seems like a constraint at first is actually just pushing you into separation of concerns!

Sunday, July 8, 2018

Approaches to IO

I'm currently looking at ROS which, despite its name (Robot Operating System), is neither an operating system nor at its core particularly specific to robotics. ROS includes libraries that help you model and program robots, but at its core, it is a framework for distributed applications.

A quick overview: a ROS application consists of several nodes (processes) that communicate via topics (broadcast) and services (remote procedure calls). Using a message definition language, you can define which data is sent between nodes. There's also a master node which provides name resolution, so that clients can find the topics and services they're interested in. Libraries can provide you with message definitions and utilities, and you will usually use third-party nodes in your application. I would say these nodes still count as libraries, but unlike a traditional library you don't call their code in the context of your process. Instead the node runs as its own process and you use topics and services for communication.

This may sound familiar because it's basically the same as a microservice architecture or probably dozens of other approaches to distributed applications. What follows is applicable to a lot of different systems, but I'll use ROS to present my code samples.

Topics, publisher:
import rospy
from std_msgs.msg import String

pub = rospy.Publisher('chatter', String, queue_size=10)
rospy.init_node('talker', anonymous=True)
rate = rospy.Rate(10) # 10hz
while not rospy.is_shutdown():
    hello_str = "hello world %s" % rospy.get_time()
    rospy.loginfo(hello_str)
    pub.publish(hello_str)
    rate.sleep()
Topics, subscriber:
import rospy
from std_msgs.msg import String

def callback(data):
    rospy.loginfo(rospy.get_caller_id() + "I heard %s", data.data)

rospy.init_node('listener', anonymous=True)
rospy.Subscriber("chatter", String, callback)

# spin() simply keeps python from exiting until this node is stopped
rospy.spin()
The code is simplified and taken from the ROS Wiki. It should be pretty easy to understand: the publisher sends a message to the chatter topic ten times a second, and the subscriber registers a callback to handle these messages. There can be any number of publishers and subscribers on the same topic.

A different approach to the same problem might be a more traditional blocking I/O API:
import rospy
from std_msgs.msg import String

rospy.init_node('listener', anonymous=True)
sub = rospy.Subscriber("chatter", String, callback)

while not rospy.is_shutdown():
    data = sub.receive()
    rospy.loginfo(rospy.get_caller_id() + "I heard %s", data.data)
This code is of course only hypothetical. The idea is that receive() would block until a new message arrived. What are the up- and downsides? One upside is that it is perfectly clear how the message is handled: right in the main thread. The original code only had a callback, and we had basically no idea where that is called. Does each subscription spawn a new thread? Are the callbacks called inside spin()? If so, what happens when we replace spin() by a busy loop? (for the record, my tests suggest one thread per subscription, but maybe ROS is smarter when the number of subscriptions rises. Or maybe not - another downside of the original approach?)

But of course there are upsides to the original code: for one, it hides the logic of receiving messages from the user. What you're interested in is the message payload, not the control flow you have to use to get it! And the most serious consideration: what if you have two subscriptions? You can't simply call receive for both, because it blocks. When subscription A doesn't get new messages, it won't let subscription B receive its messages, no matter how many there are.

This is a classic problem in blocking I/O, and the naive solution is multithreading: just block a dedicated thread that doesn't have to process anything else. For robotics, this is probably fine, but spawning and switching between operating system threads is relatively expensive and so not that appropriate for servers that operate under high load.

One step in the right direction would be a nonblocking receive:
import rospy
from std_msgs.msg import String

rospy.init_node('listener', anonymous=True)
sub1 = rospy.Subscriber("chatter", String, callback)
sub2 = rospy.Subscriber("gossip", String, callback)

while not rospy.is_shutdown():
    data = sub1.receive()
    if data is not None:
        rospy.loginfo(rospy.get_caller_id() + "I heard %s", data.data)
    data = sub2.receive()
    if data is not None:
        rospy.loginfo(rospy.get_caller_id() + "I heard %s", data.data)
Here, instead of blocking, receive will immediately return None if there is no message yet. If you haven't spotted it, the downside is that this is a busy loop: no matter whether there are messages or not, the CPU will constantly iterate through this code. In the blocking code, the operating system would just put the thread aside until the socket that receive is waiting for has new bytes. Now this is not the case and the OS will run the thread, even though it's actually blocked.

What we really want is some kind of multi-source polling. Let me show just one possible variant:
import rospy
from std_msgs.msg import String

rospy.init_node('listener', anonymous=True)
sub1 = rospy.Subscriber("chatter", String, callback)
sub2 = rospy.Subscriber("gossip", String, callback)

while not rospy.is_shutdown():
    rospy.poll(sub1, sub2)
    data = sub1.receive()
    if data is not None:
        rospy.loginfo(rospy.get_caller_id() + "I heard %s", data.data)
    data = sub2.receive()
    if data is not None:
        rospy.loginfo(rospy.get_caller_id() + "I heard %s", data.data)
here we still assume receive is nonblocking, but before running the loop, we use poll. poll will block until data on either subscription is available. Afterwards, we still need to check the subscriptions ourselves, but performance-wise this works.

It turns out that this - at least the principle - is a rather useful primitive for the operating system to provide. It allows to build many different abstractions efficiently. receive is not enough, but poll is.

Sunday, July 1, 2018

Software tooling

Learning a new programming language is hard. For the obvious reasons, but also because of tooling. (This post is mostly going to be a rant, ignore it if you're looking for practical information.)

I think nothing is more frustrating when learning a new language than not being sure where errors come from. Do you need to install another library that you're building against? Do you need to add paths to your environment? Are you passing incorrect flags to the compiler? Is your project definition missing some configuration?

And it goes on: What IDEs have good integration? Is the language or its community opinionated on project layout, documentation, testing? If not, are there still any best practices to follow? All this makes it hard to effectively use a new language at first, even if the language's syntax and semantics are familiar from the start. But all this should be trivial to take care of.

When I started programming (with Java), it was (as far as I could tell) the time of Ant build scripts. In its functionality, Ant is similar to Make, in that it defines rules for building specific parts of a project, and dependencies between rules to deduce which rules should fire and in which order. Unlike Make, Ant is Java based and its build files are XML (thus making Ant ugly to read or write).

When I heard about Maven, it was a huge revelation. Not because it made expressing build processes so much easier (or because it was less ugly - Maven still used XML build files), but because unlike Ant, Maven included what I consider the most important part of language infrastructure: dependency management! Tell Maven what libraries your project depends on, and it will download them and configure all paths so they're found. Nice!

So there's dependency management, there's building your project, and also importantly, there's installing the tools in the first place. I usually don't want to pollute my operating system by installing stuff when I have no idea what I'm actually doing.

Let's leave Java behind and look at Python. One major problem is the split between Python 2 and 3. They are largely incompatible and Python 3 has lots of cool stuff, but some software still requires Python 2. On the plus side, there are pyenv and virtualenv which let you install Python without root and Python libraries for specific projects, respectively.

Normally, your Python package will have a file setup.py which contains your project's description: name, version, dependencies, etc. As this is a Python file, you could think this is meant to contain build instruction, but that's not really the case. The file should contain a single call to setup(...), which uses the data provided in its parameters in a fairly declarative way. Further, in "modern" usage, you will likely use pip to handle dependencies. For example, pip install -e ./myproject will find ./myproject/setup.py and install the package (as editable, -e) as well as all missing dependencies.

So pip handles dependencies. What about building? Well, Python is interpreted, so normally not much. To make a "distribution" of your package, you can call python setup.py sdist and/or python setup.py bdist_wheel to make a source or binary distribution.

In JavaScript, the situation is more confusing. There are tools like bower, grunt, gulp, browserify, webpack, npm, yarn, etc. that all enter the picture, and tomorrow there will be even more. Also, there's three major ways to execute JavaScript: in a Browser, in Node and in Internet Explorer. But despite that, if you specify a package.json and use e.g. npm, you have a pretty good chance of distributing your packages to your users. (Does it show that I have not used JS as much as Python?^^)

My last look will be at Rust, because it's cool and is in a rather special situation: Rust is new, and its build tool, cargo, was developed from the beginning with the language and the rest of the tooling. It handles dependencies, building code and documentation, testing and publishing packages all in one. For installing Rust, there is the rustup tool, which fits approximately pyenv's profile: it lets you install and choose different versions of Rust. This is especially important as Rust has a six-week release cycle and a nightly channel that allows to use new unstable features.

Cargo is not required to build Rust, you can use the compiler rustc on its own as well, but usually there's no reason to go that way. That means that Rust is a rather homogenous environment (as long as you're not using unstable features) and you can focus on getting your code to compile at all; the rest of your environment will most likely work out of the box.

Sunday, June 24, 2018

Interoperability

Looking back at my earlier posts, I'm surprised how utterly Java-centric everything I did was. Never mind things like bytecode instrumentation, of course that's JVM specific, and it's cool stuff!

But for other things, I think I would try to achieve more interoperability these days. Specifically, I'm looking at JGroups. It has some nice features in terms of consensus, making sure that all known nodes have the same view of the system, but looking at it purely as a networking library, it shockingly limits you to implement all your nodes in a JVM language.

I think there are generally three layers of interoperability. The JGroups example is one extreme, basically no interoperability. It has one Java implementation and its network protocols are specific to that implementation. I don't know the specifics of JGroups, but the protocol used may well be tailored to transmit very specific manipulations of JGroups nodes' states. In other word, there are lots of assumptions that make JGroups easy to implement in Java, but very, very hard to port to another language.

One kind of interoperability comes through dynamic linking. For example, through native methods, Java can call code written in C or another language that is compiled into machine code. As long as the JVM uses the ABI and calling conventions of the native library, access is no problem. The native code is executed in the calling process, so this kind of interoperability is strictly for libraries, not for client/server communication.

So if it was CGroups instead - written in C - then there could simply be a Java binding and a .Net binding etc., and all platforms using these bindings could cooperate. Unfortunately the reverse isn't true: the JVM is, quite obviously, a virtual machine, and you can't simply call code targeted at a VM. That VM first has to run, and then you have to interface with the VM before finally getting access to the library. This is true for all languages requiring a runtime environment (i.e. interpreted languages), but it gets worse the more complicated the runtime gets.

Which leads me to the third kind of interoperability: wire protocols, which solve the issue of having a protocol that is full of assumptions from the original implementation. Instead, the first step to designing the application or library is to design a binary or text based encoding and to clearly states what kinds of communication are allowed, in what order, at what time, etc. The protocol has to be simple and explicit enough to write down, so it should also be possible to implement in different languages. That doesn't allow you to use one library in different contexts, but it makes it feasible to port the library for different platforms.

If it weren't for that last kind of interoperability, the Internet would be a very different place. Imagine if websites used a browser-specific protocol instead of HTTP! Microservice architectures also rely on well-defined protocols to connect otherwise incompatible systems: of course, a service written in Java can expose some JGroups-derived functionality via, say, HTTP, and then any other application can access that service.

Sunday, June 17, 2018

Blogging on a Time Budget

I've never been regular in writing blog posts, and in the past years I never found the time necessary to do serious Magic programming. I enjoy thinking about general ways to model the Magic rules in a program, but without a serious amount of time, it will always remain tinkering. It's an interest, but not serious enough to resolve to put out thousands of lines of code to make it work.

However, I'm still a passionate programmer and learner. While most of my posts so far have had a Magic context, they were always about programming. And this is where I want to shift the focus: non-MtG posts aren't off-topic, and that should encourage me to write more about what I'm currently doing. I know I won't start spewing out post after post, but as long as I find the time, I shouldn't run out of topics.

So what have I learned about in the three years since my last blog post?

I have shortly continued with Scala, but got demotivated by the compile times. A lot of time was spent working with Python, and it's currently my most fluent language. I have written web applications with Django, learned about generators and async/await, and constructed protocols and servers using ZeroMQ.

There has also been a considerable amount of JavaScript and some TypeScript, mostly using Vue.js to create reactive frontends for my web applications. I have also looked at web-technologies, such as Webpack and, although briefly, Websockets, PWAs (particularly service workers) and WebAssembly.

Recently, I re-discovered Rust after playing with it years ago. In terms of languages-to-use-if-you-want-to-get-things-done-in-a-reasonable-amount-of-time, Rust is about as far away from Python and JS as you can get (yes, there's also C and C++, but I don't think they're farther away, just slightly worse at getting things done... just my opinion though).

I intend to write about most of these things, if they're still relevant when I get around to them. If there be still readers here, let me know with what to start.

Oh, and I have watched tons of programming videos on YouTube! There's lots of great content. But there are also videos that suffer from what I call "boring tutorial syndrome": they try to teach good programming style (or something), but actually don't go far beyond how to write an idiomatic Hello World program (or whatever the basics of the respective topic are). The problem is that by starting from scratch, these tutorials don't manage to reach a reasonable depth. So whatever I write, don't expect start-at-zero tutorials, expect food for thought and self-study!

PS: if you're looking for videos that don't suffer from the boring-tutorial-syndrome, try LiveOverflow

Saturday, March 7, 2015

Looking at IntelliJ - not the best start...

In a recent blog post, I wrote that IntelliJ IDEA is a popular choice for Scala developers. I wanted to try for myself, but had no luck - just as many others. While there are people who successfully code in Scala using IDEA 12, the most recent version 14 seems to have major problems in this regard. The bug I encountered was this one - unfortunately a show stopper; I can't even properly add the Scala SDK to IntelliJ. Others, who probably upgraded their install from a previous version of IDEA, seem to come a little further, and then run into other problems, like Gradle integration - which I want as well.

So, no trying IntelliJ with Scala for now. I still want to give it a try, however. With Laterna being Scala-only now, it will stay with Eclipse for a while though.

I think I'll try it with Android, as the official IDE for Android was recently migrated from Eclipse to IntelliJ. So it can't be just bad ;)

Thursday, February 12, 2015

What is a card?

This post is about ambiguity, but this post is not about Ambiguity. (Don't forget to look at the card topsy turvy as well. And don't forget to look at the card Topsy Turvy as well)

Okay, enough with the puns... at least if I don't find any others while writing... what I really want to write about is how overloaded the term "Card" is in Magic. Let's see how many different meanings I can come up with.

Cards are those things that Wizards designs. For example, Grizzly Bears is a card, and Llanowar Elves is as well.

What about two Grizzly Bears? A card can also mean the physical object, sold in boosters and put in decks. But you can't even simply say that the physical card is "a Grizzly Bears", because there's a few different ones. And there's foil as well, and probably other things I'm forgetting. So the physical card is actually not an instance of what Wizards R&D designed, but of one translation of one printing of such a card, either in foil or not.

Getting to the actual game, cards are a kind of object, in contrast with tokens and copies of cards, which are not cards but serve almost the same purpose.

Noncard objects exist in a few different forms: emblems are always in the command zone; tokens can only exist on the battlefield; ability objects exist on the stack; copies of spells exist on the stack; casting a copy of a card creates that copy in the original card's zone, which in then put onto the stack as a spell while casting.

Permanents are objects that can be either cards or tokens, so another thing a card can be. Compared to other objects, permanents have state:  tapped/untapped, flipped/unflipped, face up/face down, and phased in/phased out.

The comprehensive rules on spells are worded a little strangely: "A spell is a card on the stack", "A copy of a spell is also a spell", "if the player does [cast a copy of a card], that copy is a spell as well". It sounds contradictory at first, but it's manageable.

So what have we got here:
  • What Oracle says a card is, identified by the English name of the card.
  • A printing of such a card, identified by English name together with an expansion. This extends the Oracle card by rarity, artist, illustration, collector number, card frame style, guild symbols and similar in the text box, ...
  • A translation of a printing, identified by a multiverse ID, or alternately by English name, expansion and language; I wouldn't trust that the translated name is unique. The translation adds obviously anything language specific about a card. This includes printed, non-oracle wording including reminder text, as well as flavor text.
  • A piece of cardboard that has a Magic card printed on it. To my understanding, this interpretation of "card" can be uniquely identified by a function defined on an interval of the timeline that maps every instant in that interval to the volume of space that is occupied by the card at that time. Or, a card is a card.
  • A digital representation of such can also be considered a card in that sense.
  • A card is an object that can be in a zone in a game of Magic.
  • Some permanents are (represented by) cards.
  • Some spells are (represented by) cards.
You can imagine that all this ambiguity makes it quite hard to come up with a proper software model for a game of Magic!