Rice’s Theorem, proved in 1951, states that it is impossible to write a program that performs precisely any non-trivial analysis of the execution of other programs. More precisely, that’s impossible to code an analyzer for some non-trivial property that is able to decide whether an any given analyzed program has that property or not. And by “trivial property” we mean a property that either _all_ algorithms in the world have or _none_ has. So, yeah, “non-trivial property” is basically any property you can think of: “does it ever calculate 5 + 2”, “does it always use less than 10MB of memory”, “does it ever print something to the screen”, “does it ever access the network”?

At this point you might say “wait! I can write a program that checks if programs access the network or not! We can parse the code and if there are no calls whatsoever in it to any networking code such as connect(), then it doesn’t access the network!”. Sure, you can do that: but if the code has calls to connect(), you can’t decide for sure that it will access the network when it’s executed.

In 1936 Alan Turing proved that it is impossible to write a program that solves the Halting Problem, that is, to write an analyzer that checks programs and tells if it always terminates (”halts”) or it might enter an endless loop given some specific input. Okay, that’s a classic result, but that’s one property, how can Rice’s Theorem say we can’t make an analyzer for any property at all, even the silliest ones?

The proof for this amazingly powerful theorem is surprisingly simple. Turns out that if we had an analyzer for any silly property, we could use it to make a Halting Problem analyzer (which Turing proved to be impossible). Like this:

bool my_halting_problem_analyzer(Code analyzedProgram) {
   Code modifiedProgram = analyzedProgram + "; someCodeWithSillyProperty();"
   return my_silly_property_analyzer(modifiedProgram);
}

If the code in analyzedProgram always terminates, then the code in modifiedProgram will always reach the part that has the silly property, so my_silly_property_analyzer will return true, and my_halting_problem_analyzer returns true as well. If there is some input that makes the analyzedProgram hang in a loop, that means there’s some input that makes the silly property fail, resulting in false. Yay, we solved the Halting Problem using the silly property analyzer! Not.

Of course, this explanation is quite simplified¹ (in particular, (1) I’m ignoring in the pseudo code the input of the analyzedProgram, which should be an argument of my_halting_problem_analyzer; (2) Rice’s Theorem is formally stated about partially recursive functions, but the formalism maps to Turing Machines and therefore the result applies to programming languages in general; (3) I didn’t stress enough that the “non-trivial properties” should be on the functions themselves (that is, their input-output pairs) and not their specifications (their “code”), but I believe I conveyed the general idea), so head to Wikipedia and your favorite formal languages book for the precise details. But the point stands that general semantic analysis of programs is impossible.

In particular, you can’t write a program that takes versions 1.0 and 1.1 of any program X and answer the question: “do they behave the same?”. In other words, it’s impossible to write an analyzer that looks at your master branch before you make a release and answers the question “should your new release tag be a major, minor or tiny release” according to the rules of SemVer (or any other API-compatibility-bound set of rules, for that matter).

This is because API compatibility is not only based on syntactically-expressible issues (that is, type signatures for functions and data structures). Any semantic changes to the code also break compatibility. A function may change its behavior but not its type signature (it still returns a string, but it used to be lower-case and it’s now upper-case), a struct can change they way it is used but the fields remain the same (field foo returned numbers from 0 to 10 and -1 when executed on Sundays, now it returns -1 on Saturdays as well). An automated tool won’t catch all this.

So, it is possible only to write a “pessimistic” tool, that may detect lots of situations syntactically and give the bad news: “hey, you must increment the major version here!”. But you can’t write a tool that is always able to look at code semantically and say the good news: “I assure you that no API behaviors have changed, you can safely name this a tiny version increase.”²Edit: It was pointed out to me that I missed the “always” in the previous version of the last sentence. Yes, of course you can write an analyzer that checks for API-comptabiility between versions for some cases: a silly example would be an analyzer that detects if the code is identical save for carefully renamed local variables, or that has some no-op x = x; assignments sprinkled in it — yep, the code is different, but evidently behaves the same. It’s a silly example but it shows that it is possible to catch some cases. My point is that it is impossible to write a program that reaches a conclusive answer on API compatibility on all cases, so the conclusion stands that making versioning decisions fully automated is impossible. Further, writing one that would catch even a significant amount of positive cases would be impractical. There are hard limits to semantic analysis. However, given that lots and lots of API breakage happen in function signatures and data types, those are not hard to detect, as they are syntactically specified: that’s why the “pessimistic” tools are much more practical.

Yes, you can use test suites as an approximation for detecting semantic changes in API behaviors beyond type signatures and data structures. That would certainly improve your pessimistic analyzer — you’d be able to detect more situations where “you must increment major”. But even then it can only go so far, because in practice one can’t test for every possible input/output combination, so you still can’t be 100% sure. fuzz testing has uncovered bugs and unexpected behaviors even in programs with extensive test suites; as Dijkstra famously said, “Testing shows the presence, not the absence of bugs.” — likewise, test suites can show inconsistencies to the API specification, but not their adherence. So they can’t be taken to represent the semantics of a program entirely.

Anyway, in the end of the day, Rice’s Theorem shows us that general bullet-proof analysis of program behavior is not attainable, so no tool will ever be able to compare codebases and always tell us precisely that a new release is really “tiny-safe”. Semantic versioning just can’t be automated.

A list of notes on my first experience with OpenBSD:

* It wasn’t obvious at first which file to download, navigating their FTP site. I ended up with cd58.iso, which was the right choice. A tiny 7.8MB ISO!
* As soon as I typed “OpenBSD” as the VM name in VirtualBox, it gave me OpenBSD defaults. It defaulted to 64MB of RAM (only!), but I chose 256M, and the default 2G disk image.
* The first boot gave me a few options, including “Install” and “Autoinstall”. I chose “Autoinstall” since I thought that would install with the defaults, but it looked for an installation script in the local network (and obviously didn’t find it). Reboot, “Install” and off we go.
* No Dvorak options in the list of keyboards in the installer.
* I went with the default options and installed all offered packages (it offered me a list of coarse-grained bundles). It asked me about creating users, partitions, configuring network and if I wanted to run sshd by default.
* To enable Dvorak, the internet told me to do kbd us.dvorak nice.
* To make it permanent, I just grepped /etc for kbd and found out that cat us.dvorak > /etc/kbdtype would suffice.
* To install things, become root and then use pkg_add. For example: pkg_add wget
* By default it includes df but not free.
* To get color in the terminal, set TERM=wsvt25. htop showed in its usual colors!
* The default PATH includes the current (.) directory! Take that, Linux status quo!
* iconv is installed under /usr/local, and its library exports symbols with names such as libiconv_open instead of the usual iconv_open, which fools the typical AC_CHECK_LIB test in Autoconf. (In the source code, iconv_open works, so I guess iconv.h uses #define to translate the name. Added a hack to Dit to make it build cleanly out-of-the-box.

This week I finally released htop 2.0.0!

• htop-2.0.0.tar.gz
• MD5 06f76c7d644ce8ae611c9feb10439a30
• SHA-256 d15ca2a0abd6d91d6d17fd685043929cfe7aa91199a9f4b3ebbb370a2c2424b5

What’s new in htop 2.0

Since version 2.0, htop is now cross-platform!
Check out the video and slides of my presentation at FOSDEM 2016
about how this came to be. This release includes code supporting Linux, FreeBSD, OpenBSD and Mac OS X.

There are also, of course, some new features:

• If you’re using NCurses 6, htop will also support your mouse wheel for scrolling.
• Moving meters and columns around in the setup screen is a lot more comfortable now.
• You can now press “e” to see the set of environment variables for a process.
• The “graph” mode for meters was revamped, inspired by James Hall’s vtop.

…And of course, lots of other tweaks and fixes!

Changelog

The changelog with the main new changes follows below. Special thanks
to everyone who contributed for this release, through bug reports, bug
fixes, new features and financial support for the platform abstraction
layer project!

• Platform abstraction layer
• Initial FreeBSD support
• Initial Mac OS X support
  (thanks to David Hunt)
• Swap meter for Mac OSX
  (thanks to Ștefan Rusu)
• OpenBSD port
  (thanks to Michael McConville)
• FreeBSD support improvements
  (thanks to Martin Misuth)
• Support for NCurses 6 ABI, including mouse wheel support
• Much improved mouse responsiveness
• Process environment variables screen
  (thanks to Michael Klein)
• Higher-resolution UTF-8 based Graph mode
  (Thanks to James Hall from vtop for the idea!)
• Show program path settings
  (thanks to Tobias Geerinckx-Rice)
• BUGFIX: Fix crash when scrolling an empty filtered list.
• Use dynamic units for text display, and several fixes
  (thanks to Christian Hesse)
• BUGFIX: fix error caused by overflow in usertime calculation.
  (thanks to Patrick Marlier)
• Catch all memory allocation errors
  (thanks to Michael McConville for the push)
• Several tweaks and bugfixes
  (See the Git log for details and contributors!)

It’s impressive to see David Bowie’s foresight on the cultural impact of the internet back in 1999, and how the interviewer was completely oblivious to it:

« Bowie: [When I was really young,] it still produced sighs of horror from people when you said “I’m in rock’n'roll”. Now it’s a career opportunity. And the internet now carries that flag, from the subversive and possibly rebellious, and chaotic, and nihilistic… Forget about the Microsoft element: the monopolies do not have a monopoly — maybe on programs.

Interviewer: What you like about it is that anyone can say anything, or do anything?

Bowie: From where I am, by virtue of the fact that I am a pop singer and writer, I really embrace the idea that there’s a new demystification process going on between the artist and the audience. If you look back at this last decade, there hasn’t been a single entity, artist or group that personified or became the brand of the 90s. It started to fade in the 80s… in the 70s there were definitely such artists, in the 60s… the Beatles, and Hendrix… in the 50s there was Presley.

Now it’s sub-groups, it’s genres: it’s hip-hop, it’s girl-power, it’s a communal kind of thing. It’s about a community, it’s becoming more and more about the audience. Because the point of having someone who led the forces has dissapeared, because the vocabulary of rock is too well-known. It’s a currency that is not devoid of meaning anymore, but it’s become only conveyor of information, not a conveyor of rebellion, and the internet has taken on that, as I said. So I find that a terribly exciting era.

So, from my standpoint, being an artist, I’d like to see what the new construction is between artist and audience. There is a breakdown, personified I think about rave culture, where the audience is at least as important as the person who is playing at the rave. It’s almost like the artist is to accompany the audience and what the audience is doing. And that feeling is very much permeating music. And permeating the internet. »

Lua is known for having a very lean standard library, and for providing mechanisms to do things instead of a ton of features.

String interpolation isn’t available out of the box, but doing it in Lua isn’t a new trick. In fact, the manual includes it as an example of string.gsub:

local t = {name="lua", version="5.3"}
x = string.gsub("$name-$version.tar.gz", "%$(%w+)", t)
--> x="lua-5.3.tar.gz"

This applies to members of a table only, though. Python is introducing a general string-interpolation syntax:

a = "Hello"
b = "World"
f"{a} {b}"
f"{a + ' ' + b}"

Given that Lua supports the f"str" syntax for functions with a single string argument, I thought it would be nice to put its Lua-provides-the-mechanisms ethos to test by trying to write my own Python-like f-string formatter.

And here it is, in all its 28-line glory (and I went for readability, and not to write it as short as possible):

function f(str)
   local outer_env = _ENV
   return (str:gsub("%b{}", function(block)
      local code = block:match("{(.*)}")
      local exp_env = {}
      setmetatable(exp_env, { __index = function(_, k)
         local stack_level = 5
         while debug.getinfo(stack_level, "") ~= nil do
            local i = 1
            repeat
               local name, value = debug.getlocal(stack_level, i)
               if name == k then
                  return value
               end
               i = i + 1
            until name == nil
            stack_level = stack_level + 1
         end
         return rawget(outer_env, k)
      end })
      local fn, err = load("return "..code, "expression `"..code.."`", "t", exp_env)
      if fn then
         return tostring(fn())
      else
         error(err, 0)
      end
   end))
end

It works just like the Python example:

a = "Hello"
b = "World"
print(f"{a} {b}")

Unlike the one-liner from the Lua manual, it also works with local variables:

local c = "Hello"
local d = "World"
print(f"Also works with locals: {c} {d}")

do
   local h = "Hello"
   do
      local w = "World"
      print(f"Of any scope level: {h} {w}")
   end
end

Some more demos:

print(f"Allows arbitrary expressions: one plus one is {1 + 1}")

local t = { foo = "bar" }
print(f"And values: t.foo is {t.foo}; print function is {_G.print}")

local ok, err = pcall(function()
   print(f"This fails: { 1 + } ")
end)
print("Errors display nicely: ", err)

If there’s interest, I can make this a module in LuaRocks (probably calling it F rather than f).

Update! This is now available in LuaRocks as a module! Install it with:

luarocks install f-strings

More info at the f-strings GitHub page. Enjoy!