Sometime during me being a student, I wanted to move to a new calculator from a Casio fx991ES and a Texas Instruments TI-68. Both of which are great calculators, and I still have them. Though the TI68 has fallen victim to a common problem with columns of its display giving up. My eye was on the TI-89 Titanium. But I was saved by a then grml project member, setting me onto the one true path of RPN supremacy, by going with the then new HP50g. Thanks gebi! :)
All jokes aside, it is an awesome machine. It has all the features you want, and so much more. And it has an extension SD card slot, that accepts SD cards up to 2GiB in storage space. Basically infinite storage for extensions you may want. I never used it much for graphing the values of expressions. I loved the huge screen, because it allowed me to see many levels of the system's stack. One of its killer features is that it's keyboard can be totally customised, and the six function keys on the top of the keyboard that usually operate built-in soft-menus, can also be made to host custom soft-menus. Which means you can implement your own commands that implement whatever tasks you often need to perform, link them into soft-menus and thus invoke your most common tasks with ease. It's a pretty awesome input system.
The HP calculators have a bit of a cult-like following. And people over the years have written unbelievable tools for it. One such tool is keyman by professor Wolfgang Rautenberg, which extends the customisability of the HP50g's keyboard quite a bit compared to what HP's standard features offer. In particular, you can bind actions to long-presses on any key of the keyboard. Very nice! I use that for all my custom bindings.
I still own that HP50g and it is indeed on my desk at work. And I also have a copy of that calculator via the absolutely awesome Emu48 android application. But most of the time I also have a computer in front of me. Which means I have access to all sorts of desktop calculators (which I thought all sucked, until I was recently made aware of Qalculate which looks pretty neat), as well as GNU Octave and Maxima. I still believe that the input method popularised by the classic HP calculators is pretty unrivaled, especially when it comes to quick numeric calculations. Much to my delight, Emacs comes with GNU Calc, which is a rather advanced scientific calculator1, whose interface was loosely based on the HP calculators of the time. And it is awesome, sometimes dubbed the poor-man's-mathematica. :)
When loaded, it looks very unassuming, here is how it looks after calculating
5+6*7 = 47 using its stack:
Compared to the real HP calculators however, I am always missing that soft-menu feature so I can have my most used functions at my fingertips, with a friendly hint on what to press on a label of a button in my screen. Fear not, though! Since it's Emacs, there should be a way to add something like that. Right!? Yes. Yes, there is. Here's how it might looks with default configurartion and a soft-menu full of useful constants loaded into it:
It was pretty straight forward too. I had the basics going in a couple of hours, and over a bunch of evenings I had the system working mostly like I wanted, including supporting calc's algebraic entry mode. Finally it took me a couple of hours to turn the code I had into a well-behaved minor mode for calc, that can be enabled and disabled at the user's behest. The basic idea is to hijack calc's mode-line to display an HP-style soft-menu, and offer a command to fill the menu with life.
With that it is very easy to construct calculations built upon custom variables as well as function calls. Here's just a silly example with a multiplication of a bunch of constants from the active soft-menu. Level two has a copy of the original expression, and level one holds the numeric evaluation:
The minor-mode also patches calc's algebraic entry mode, so triggering a softkey will insert a variable or function name into the algebraic entry, similar to how the real HP calculators do it.
This brings me one step closer to having a plan-b when my HP50g inevitably expires.
The implementation of calc-softmenu-mode in
calc-softmenu.el
is part of my Emacs configuration.
Nothing positive going on, so lets have another listen…
This time, Richard David James aka. AFX aka. Aphex Twin. One of my absolute favourite electronic artists. There's tons to choose from. But — again — if I'd have to make one choice among his creations, it would be Donkey Rhubarb. That's the title song of a 1995 EP, that I bought ridiculously over-priced via import… Worth it, of course. ;)
- Full EP Version
- Video Edit — Iconic Video, but the track fades out. Probably due to time restrictions.
This time it's playful, heavy Deathcore from Canada. The band was formed in 2018, taking their name from a pretty dark manga. They have put out a number of excellent pieces in their relatively short history. This might be my favourite:
If you're one of those people who still use IRC, you've probably heard of the sort of meltdown that freenode has been experiencing. Despite all that, I was still on the network, partly because I had been since forever, but mostly because one of my favourite projects still has their community channel on there.
This evening I noticed that my IRC client was disconnected from freenode and since can't reconnect. I've set up automatic SASL authentication into the nickname I had registered on the network for some — oh… I don't know — fifteen years or so. That authentication fails and therefore irssi drops the connection.
Weird right? So I connected to freenode without authentication and asked the network's nickserv service about my previous account. Looks like it's not registered anymore. Fantastic! No prior warning. No nothing.
Strictly speaking, I have no right to the account of course. So I guess there's little point in complaining, and this post is enough of that.
Just in case somebody who knew me on freenode as ft is wondering: Should the
nickname appear again in the future, you're not talking to me any more. A
network like this is not worth the hassle.
In today's episode of songs you should have heard, we'll go with some post-punk. Specifically the classic Joy Division track “Love will tear us apart”. Gorgeous in every way.
There was a talk at Remote Chaos by Michael
Sperber
about using syntax-parse, which is Racket's most advanced system to express
syntactic extensions, that is one of the important cogs for implementing new
programming languages on top of Racket. Anything that promotes awesome Scheme
technology is cool with me. ;)
In this episode of songs you should have heard, let's have some metal, shall we? In particular, the Devin Townsend Band. Some people are flooding youtube with reaction videos to Devin's performance of Kingdom, which is a good one, but let's have this one instead:
Devin Townsend Band — Accelerated Evolution — Deadhead
One of the esoteric programming languages that a fair number of people have heard of, is “Whitespace”. I'm sure this has nothing at all to do with jokes like its source code being so fantastically efficient when being printed out. The language was actually meant as a joke (at least that's how one of its creators puts it when he mentions the language in some of his talks). But even though people are aware of the language's existence, they rarely know how it works. Let's change that, because it's really not all that hard.
At its core, the language describes operations on a stack machine, that has
access to a heap. The only data type of the machine are integer values of
arbitrary size. There are operations for the machine, that use these values to
encode characters as well. And that's about it. The rest is just a peculiar way
to encode operations and values using three ASCII whitespace characters (TAB,
SPACE and LINEFEED).
Operations are grouped by function. These groups determine an operation's encoding prefix, that the language spec calls “Instruction Modification Parameter”. Many of the operations have no arguments, as they create and consume arguments on the machine's stack. Some however do take an argument: Integers and Labels. Label arguments are used by flow control operations; and integer arguments are used by some of the stack manipulation operations.
Their encoding is similar: Both use strings of spaces and tabs, that are terminated by linefeeds. In labels, the spaces and tabs have no special semantics. At least not within the language specification; more on that later. In integers, tabs encode ones and spaces encode zeroes. Something to note about such integer literals is that they do not use two's complement to encode negative numbers. Instead, they use the literal's leftmost bit as a signedness bit: Tab means negative number, space means positive number. That makes encoding arbitrarily wide integers straight-forward.
When you take a look at actual whitespace programs, you'll sometimes notice extremely long labels. Oftentimes with that, there seems to be a silent convention to use chunks of eight characters to encode eight bits (same semantics as in number literals as to what characters encode ones and zeroes) that are turned into a positive number, which is then mapped to the ASCII encoding (seven would have sufficed, but that's not what the programs I've seen use).
When you try and implement this language, you'll notice a couple of things your
machine implementation needs: A stack obviously, since whitespace is a
stack-manipulating language. Another stack, used as a callstack, since the
language has Call and Return operations. It also needs a heap, mapping
addresses to integers. Finally you'll need program memory and a program counter
register. You might want a jump-table too, to deal with translating labels to
addresses. That's not strictly required, though: You could just translate all
labels to addresses before loading the program into your machine.
When I digged deep enough into the language spec to figure this out, I was
intrigued enough to actually do yet another implementation of the language.
It's called SpaceMan and it is available at
gitlab.com/ft/spaceman as well as
github.com/ft/spaceman.
I've added an org-mode conversion of the original language
homepage,
because that one is currently only available via archive.org. When trying some
of the more complex examples you can find on the net, I was running into
problems. My implementation failed to even parse them. I was verifying my code
for quite some time, until I concluded that it was implementing the parser
correctly. So I looked at other implementations. And it turned out most of them
implemented two additional stack-manipulating operations: Copy and Slide.
Apparently, they were added to a later specification of the language. I
couldn't find such a spec on the net, though (not that I invested a lot of time
— see the update at the end of the post for a resolution to this). However,
after implementing these two, spaceman could run the most elaborate examples
that I could find online, like a sudoku solver. I've added those two additional
operations to the included version of the language
spec.
I'm using Megaparsec for parsing purposes. And with a couple of utilities put in place, writing the parser becomes rather pleasant:
stackParser :: Parser StackOperation
stackParser = do
( try $ imp [ space ])
( try $ Push <$> number [ space ])
<|> (try $ operation [ linefeed, space ] Duplicate)
<|> (try $ operation [ linefeed, tabular ] Swap)
<|> (try $ operation [ linefeed, linefeed ] Drop)
<|> (try $ Copy <$> number [ tabular, space ])
<|> (try $ Slide <$> number [ tabular, linefeed ])
When implementing the language's operations, you'll find that you're facing lots of common instructions that manipulate the virtual machine. You put those common tasks into functions, of course, and like any designer of an assembly language worth their salt, you obviously give your instructions slightly cryptic three letter names. With those, implementing the stack-manipulating operations looks like this:
eval :: WhitespaceMachine -> StackOperation -> IO WhitespaceMachine
eval m (Push n) = return $ pci $ psh [n] m
eval m Duplicate = return $ pci $ psh h m where h = peek 1 m
eval m Swap = return $ pci $ psh [b,a] $ drp 2 m where [a,b] = peek 2 m
eval m Drop = return $ pci $ drp 1 m
eval m (Copy i) = return $ pci $ psh [n] m where n = ref i m
eval m (Slide n) = return $ pci $ psh h $ drp (n+1) m where h = peek 1 m
Implementing the other groups of operations looks similar. I sort of like it. Each of them would basically fit onto an overhead slide.
As it turns out, editing whitespace programs is tough work. Doing it directly is best done in an hex-editor. But spaceman has a feature, that makes it dump the programs syntax-tree to stdout. And those program dumps are actually executable programs. So if you'd like to edit a whitespace program, you can dump it into a file, edit its AST and then run that program to yield the changed whitespace program.
“Yet another whitespace implemention created” achievement unlocked, I guess.
[Update] Andrew Archibald informs me, that if you spend a little more time
looking for the language specification, that includes Slide and Copy, you
will find http://compsoc.dur.ac.uk/whitespace/index.php (via
archive.org),
that contains v0.3 of the whitespace specification, that adds these operations.
Not too many programming languages have the concept of first-class continuations built into them. Scheme is one that does1, so it will be our vehicle for today's adventure. Now what really is a continuation? In order to get an idea, consider the following simple expression:
(+ 5 4)
Remember that Scheme uses prefix notation2, where the first item in a
parenthesised list is the operator, that is applied to the list of arguments,
which is the rest of the list. + is the sum-operator, so the above expression
evaluates to 9. So far, so good. How does this help with continuations? Well,
a continuation is a way of bundling up “what's left to do” with respect to an
arbitrary sub-expression within a program.
Imagine the perspective of the literal 5 in the expression above. If you are
this five, look around you and try to come up with a function, that would
represent the rest of the computation after you are done evaluating3. So
in the expression above, after 5 evaluates to five, what is left to be done
in order to finally evaluate to 9? Here's a suggestion:
(define (kont v)
(+ v 4))
Indeed, after evaluating the 5 literal, the rest of the expression can be
represented as a function, that takes one value and adds 4 to it. And if you
stick the value of 5 into that function, it will return 9, like it must.
Once you realise that you need to take the perspective of a part of an expression in order to figure out what the continuation does, it is not hard to figure out these functions for arbitrarily complex expressions. It just takes a little bit of practice. But thus far, this is just a theoretical idea. How would you work with continuations? How to you get to them?
In Scheme (and also Standard ML), there is an operator called call/cc, which
is short for call-with-current-continuation. Its purpose is to capture the
continuation at a certain point in a program and make it available to the
programmer. The name call-with-* suggests, that the operator needs something
that it can call. That would be a function. This function has to take one
argument and call/cc will call that function with the continuation it
captured as the function's only argument. This function parameter is the only
argument that call/cc expects and the return value of the call/cc
invocation is the value of the the supplied function applied to the captured
continuation. Here are simple examples, that use call/cc:
(call/cc (lambda (k) 5)) → 5
(+ (call/cc (lambda (k) 5)) 4) → 9
Since these don't use the continuation at all, it is straight forward to tell the values these expressions evaluate to. Now for something more interesting: Since Scheme allows us to mutate memory4, we can just store the continuation in a parameter for later use:
(define kont #f)
(+ (call/cc (lambda (k)
;; Store the continuation k in the global
;; parameter kont, that we defined before.
(set! kont k)
;; Ignore the continuation otherwise, and
;; just return 5; so this expression boils
;; down to (+ 5 4); though we used call/cc
;; to extract the continuation from the
;; perspective of our value 5.
5))
4) → 9
;; Take a look at ‘kont’ — this is how Racket pretty prints it.
kont → #<continuation>
(kont 10) → 14
Remember when we defined a function called kont earlier? We figured out
that the continuation right after evaluating the 5 is a function that adds
4 to its one and only argument. Now applying the continuation (stored in
kont) to a value of 10 results in: 14 — just as we predicted.
The captured continuation has a special property, that sets it apart from being a simple function: When it is invoked, it resurrects its execution context entirely and abandons the current one, no matter where the program went in the meantime. This property can be used to implement all sorts of useful high-level control flow facilities. A simple, easily understood one is “early exit”. Consider this:
(fold * (*) '(1 2 3 4 0 6 7 8 9 10)) → 0
This is an expression that computes the product of all values in the list, that
is the last argument to fold5. Since any integer being multiplied by
zero results in zero, the computation could stop at the fifth element of the
input list. However, fold has no concept of exiting early. Since we have
call/cc, we can easily add that:
(call/cc (lambda (return)
(fold (lambda (x acc)
(if (zero? x)
(return 0)
(* x acc)))
(*)
'(1 2 3 4 0 6 7 8 9 10)))) → 0
It's the same expression as before, but it's executed inside the function, that
is passed to call/cc. That way, we have access to the surrounding
continuation. In the call to fold we pass a function that's more complex than
the direct reference to multiplication function. fold will hand the current
element of the list as the first argument of its function argument and the
current value of its accumulator as the second one. What we need to do is
straight-forward: Check if the current argument is zero, and if that is the
case, just invoke the surrounding continuation with 0 as its argument. As
mentioned earlier, this resurrects the continuations execution context and
abandons the current one.
Now in order to see if you understood continuations, at this point in other texts on the subject, you get confronted with mind-benders like the following, which is from TSPL page 646:
(((call/cc identity) identity) "Hey!")
If you evaluate this at a Scheme prompt, it will return the string "Hey!".
This might be guessable, but the question is: Why? Let's analyse the
expression's form first: At its most primitive, this expression can be
summarised like this:
(operator operand)
The operand has the value "Hey!", trivilly. And since we know the result of
the final evaluation is that same value, we can (barring side effects) reason
that operator has to be the identity function7. Since that function
appears twice in the original expression, it feels like we are on the right
track! A guess would be, that the second incarnation of identity somehow gets
transposed into the operator spot. Maybe we can just replace it with something
else, like string-upcase. But if you try, you will notice that things are not
quite as easy is they seemed8:
(((call/cc identity) string-upcase) "Hey!")
→ string-upcase: contract violation
expected: string?
given: #<procedure:string-upcase>
…and not "HEY!" like one might have guessed. Time to take a look at the
expression, that is our operand:
((call/cc identity) identity)
With our previous strategy we need to look at (op identity), put ourselves in
the perspective of op and ask: What function represents the rest of the
computation after I am done evaluating myself? And you can follow that strategy
pretty mechanically:
(define (k v)
(v identity))
This is what gets handed in as the argument to identity in (call/cc
identity). And since it is identity, all it does is return the continuation
it is handed. That is all it does. Which means, we end up with this:
((lambda (op) (op identity)) identity)
;; Which can be reduced to:
(identity identity)
;; Which can be further reduced to:
identity
Let's come back to our guess-work from earlier, where we naïvely used
string-upcase instead of identity: It would reduce to this: (string-upcase
string-upcase). And now all of the sudden the error message makes sense too:
It says string-upcase expected a string argument, but instead got a
procedure; and not any procedure but string-upcase itself.
To summarise the above: The call/cc uses its identity argument to feed the
right identity into itself, ultimately returning itself. So (((call/cc
identity) identity) "Hey!") reduces to (identity "Hey!") which evaluates to
"Hey!".
It's a fair bit mind-bendy if you think it all through, but managable if you follow the strategy that was presented earlier. What remains to examine is what continuations are useful for beyond clever puzzles. Well, they are a primitive that allows the implementation of a lot of high-level control structures such as early-exit (as we have seen earlier), exceptions, co-routines, generators, and more. In a language with first-class continuations all these features can be implemented in a library without further language support.
Finally, let's not overlook that there are problems with full, unbounded
continuations as well: For details on that, see [Kis12]. To alleviate most of
these concerns, we might take a look at delimited continuations. That is,
however, a story for another day.
Footnotes
1 See [R4RS] p.28f
2 See [SICP] p.8f
3 Number literals evaluate to themselves — but in general, the subexpression that would be picked could be arbitrarily complex.
4 I know, I know.
5 The * symbol evaluates to the multiplication function and (*) evaluates to the identity element of multiplication, namely 1.
6 According to the author it is “probably the most confusing Scheme program of its size”, a Confusion Desity Maximum, if you will.
7 (lambda (x) x)
8 As we will see later, this intuition is not completely wrong, but there is a twist!
References
[SICP] Harold Abelson and Gerald J. Sussman. Structure and Interpretation of Computer Programs. 2nd ed. The MIT Press, 1996. isbn: 0262011530.
[R4RS] William Clinger, Jonathan Rees, et al. R4RS, The revised4 report on the algorithmic language Scheme. New York, NY, USA: ACM Lisp Pointers, 1991, pp. 1–55.
[TSPL] R. Kent Dybvig. The Scheme Programming Language. 4th ed. MIT Press, 2009, pp. I–XII, 1–491. isbn: 978-0-262-51298-5.
[Kis12] Oleg Kiselyov. An argument against call/cc. 2012. url: http://okmij.org/ftp/continuations/against-callcc.html.
Haven't done one of these in a while. So here goes…
Nine Inch Nails — And All That Could Have Been — Leaving Hope
NIN have a couple of amazing instrumental tracks on their résumé, some very quiet ones too, and it's hard to pick a favourite. But if pressed for an answer, I'd pick this.
After being the most horrible package maintainer imaginable for at least the past two years, I've been putting some work into the Debian package for the MRA/MDA combination that is fdm. That package now captures a new version control snapshot from upstream (releases happen seldom, the project is pretty much in maintenance only mode), that fixes a couple of things and adds some features, like being able to use SSL with Google's IMAP without turning off all kinds of verifications.
I've been using different iterations of the new package for a while now and am experiencing zero issues in day to day use. So even though this is the first package update in a while, and a couple of things (like the build system) have changed upstream; I'm fairly confident this is an improvement over the previous versions of the Debian package.
Internally, the packaging is pretty much a complete rewrite. It uses modern debhelper features and implements pretty much all items on Debian's wish list (like machine readable debian/copyright format and stuff like that).
Thanks go out to Axel, who patiently reviewed my changes and helped me get this package out of the door before buster goes into freeze. This update would not have happened without him.
In my dayjob, I'm an electrical engineer. Though, I'm mostly involved in writing firmware that runs on baremetal systems. If you're designing electrical circuits for a living or just tinkered with them, you will have heard of E-Series preferred values. In particular, resistors, capacitors and inductors are generally available in ratings derived from these numbers. The basic idea is to fit a number of values into one order of magnitude. For examples in E3, there are three values in the same decimal power: 100, 220 and 470. The next value would be 1000 in the next decimal power. Likewise in E12 there are twelve such values.
Roughly, E-Series follow an exponential definition. The series generally don't follow the exact mathematical expression. For an actual implementation you either adjust to the specified values or you simply use the actual tables from the spec.
Now looking up values in tables is a boring task; especially if the tables are relatively small. Finding combinations, though, is more interesting. For example, if you'd like a resistor rated at 50Ω (which is a rather important value in radio frequency design), you'll notice that the exact value is not available in any of the E-Series. But it's easy to combine two 100Ω resistors in parallel to produce a value of 50Ω. …sure, in an actual design you might use 49.9Ω from E96 or E192, or use a specially made resistor of the desired rating. But you get the idea. Combining components in parallel and series circuits allows the parts from E-Series to cover lots of ground.
I've written a library that implements E-Series in Scheme. Its main modules are (e-series adjacency), which allows looking up values from an E-Series that are in the vicinity of a given value. Then there's (e-series combine) which produces combinations of values from a certain E-Series to approximate a given value. And finally there's the top-level (e-series) module, that implements frontends to the other mentioned modules, to make it possible to easily use the library at a Scheme REPL.
To see if the library finds a combination from E12 that matches 50Ω:
scheme@(guile-user)> (resistor 12 50)
------------+-------------------------+-------------+-------------+--------------
Desired | Actual (Error) | Part A | Part B | Circuit
------------+-------------------------+-------------+-------------+--------------
50.0000Ω | 50.0000Ω ( exact ) | 100.000Ω | 100.000Ω | parallel
50.0000Ω | 50.0380Ω (+7.605E-4) | 56.0000Ω | 470.000Ω | parallel
50.0000Ω | 49.7000Ω (-6.000E-3) | 47.0000Ω | 2.70000Ω | series
50.0000Ω | 50.3000Ω (+6.000E-3) | 47.0000Ω | 3.30000Ω | series
------------+-------------------------+-------------+-------------+--------------
Those aren't all the combinations that are possible. By default the module produces tables, that contain combinations that match the desired value at least as well as 1%. Now, to see values in the vicinity of 50Ω all E-Series, you can do this:
scheme@(guile-user)> (resistor 50)
---------+--------------------------+-------------+--------------------------
Series | Below (Error) | Exact | Above (Error)
---------+--------------------------+-------------+--------------------------
E3 | 47.0000Ω (-6.000E-2) | | 100.000Ω (+1.000E+0)
E6 | 47.0000Ω (-6.000E-2) | | 68.0000Ω (+3.600E-1)
E12 | 47.0000Ω (-6.000E-2) | | 56.0000Ω (+1.200E-1)
E24 | 47.0000Ω (-6.000E-2) | | 51.0000Ω (+2.000E-2)
E48 | 48.7000Ω (-2.600E-2) | | 51.1000Ω (+2.200E-2)
E96 | 49.9000Ω (-2.000E-3) | | 51.1000Ω (+2.200E-2)
E192 | 49.9000Ω (-2.000E-3) | | 50.5000Ω (+1.000E-2)
---------+--------------------------+-------------+--------------------------
And here you see that E96 and E192 have pretty close matches as single components.
With combinations, the library allows the for user to specify arbitrarily complex predicates to choose from the generated combinations. For example, to only return parallel circuits that approximate 50Ω from E12:
scheme@(guile-user)> (resistor 12 50 #:predicate (circuit 'parallel))
...
And to limit those results to those that have an eror of 0.001 or better, here's a way:
scheme@(guile-user)> (resistor 12 50 #:predicate (all-of (max-error 1e-3)
(circuit 'parallel)))
------------+-------------------------+-------------+-------------+--------------
Desired | Actual (Error) | Part A | Part B | Circuit
------------+-------------------------+-------------+-------------+--------------
50.0000Ω | 50.0000Ω ( exact ) | 100.000Ω | 100.000Ω | parallel
50.0000Ω | 50.0380Ω (+7.605E-4) | 56.0000Ω | 470.000Ω | parallel
------------+-------------------------+-------------+-------------+--------------
There are frontends for inductors and capacitors as well, so you don't have to mentally strain yourself too much about with combination corresponds to which circuit. To find a 9.54μF capacitor approximation from E24 with an error better than 0.002:
scheme@(guile-user)> (capacitor 24 #e9.54e-6 #:predicate (max-error #e2e-3))
------------+-------------------------+-------------+-------------+--------------
Desired | Actual (Error) | Part A | Part B | Circuit
------------+-------------------------+-------------+-------------+--------------
9.54000µF | 9.53000µF (-1.048E-3) | 9.10000µF | 430.000nF | parallel
9.54000µF | 9.55102µF (+1.155E-3) | 13.0000µF | 36.0000µF | series
9.54000µF | 9.52381µF (-1.697E-3) | 10.0000µF | 200.000µF | series
------------+-------------------------+-------------+-------------+--------------
The test-suite and documentation coverage could be better, but the front-end module is easy enough to use, I think.