Singpolyma

Technical Blog

Archive for the "Tech" Category

Rust Factory Without Box (Trait Object)

Posted on

I’ve been playing around a lot with Rust recently and it’s quickly becoming my second-favourite programming language. One of the things I’ve been playing with is some Object Oriented design concepts as they might apply. For example, consider this code:

fn format_year(n: i32) -> String {
	if n == 0 {
		"0 is not a year".to_string()
	} else if n < 0 {
		format!("{} BC", -n)
	} else {
		format!("{} AD", n)
	}
}

While maybe overkill for this small example, let’s go ahead and replace conditional with polymorphism:

fn format_year(n: Box<Year>) -> String {
	format!("{} {}", n.year(), n.era())
}

trait Year {
	fn year(&self) -> u32;
	fn era(&self) -> String;
}

impl Year {
	fn new(n: i32) -> Box<Year> {
		if n == 0 {
			Box::new(YearZero())
		} else if n < 0 {
			Box::new(YearBC(-n as u32))
		} else {
			Box::new(YearAD(n as u32))
		}
	}
}

struct YearZero();

impl Year for YearZero {
	fn year(&self) -> u32 { 0 }
	fn era(&self) -> String { "is not a year".to_string() }
}

struct YearBC(u32);

impl Year for YearBC {
	fn year(&self) -> u32 { self.0 }
	fn era(&self) -> String { "BC".to_string() }
}

struct YearAD(u32);

impl Year for YearAD {
	fn year(&self) -> u32 { self.0 }
	fn era(&self) -> String { "AD".to_string() }
}

This works, and really does seem to mimic the way this kind of design looks in a class-based Object Oriented language. It has a major disadvantage, however: all our objects are on the heap now (which is likely to cause performance issues). In some cases, this can be fixed by using CPS so that the trait objects could be borrowed references instead of boxed, but that’s both ugly and not always an option. One other design might be to use an enum:

fn format_year(n: Year) -> String {
	format!("{} {}", n.year(), n.era())
}

enum Year {
	YearZero,
	YearBC(u32),
	YearAD(u32)
}

impl Year {
	fn new(n: i32) -> Year {
		if n == 0 {
			Year::YearZero
		} else if n < 0 {
			Year::YearBC(-n as u32)
		} else {
			Year::YearAD(n as u32)
		}
	}

	fn year(&self) -> u32 {
		match self {
			YearZero => 0,
			YearBC(y) => y,
			YearAD(y) => y
		}
	}

	fn era(&self) -> u32 {
		match self {
			YearZero => "is not a year".to_string(),
			YearBC(y) => "BC".to_string(),
			YearAD(y) => "AD".to_string()
		}
	}
}

No more heap allocations! While this is obviously analogous, some might claim we haven’t actually “replaced conditional” at all, though we have at least contained the conditionals in a place where a type only knows about itself, and not about other things that might get passed in. Even if you accept adding match arms on self as “extension”, in terms of open/closed this requires a modification to at least the enum and the factory to add a new case, instead of just the factory as with the trait version.

What is it about the enum version that allows us to avoid the boxing? Well, an enum knows what all the possibilities are, and so the compiler can know the size that needs to be reserved to store any one of those. With the trait case, the compiler can’t know how big the infinite world of possibilities that might implement that trait could be, and so cannot know the size to be reserved: we have to defer that to runtime and use a box. However, the factory will always actually return only a known list of trait implementations… can we exploit that to know the size somehow? What if we create an enum of the structs from the trait version and have the factory return that?

enum YearEnum {
	YearZero(YearZero),
	YearBC(YearBC),
	YearAD(YearAD)
}

impl Year {
	fn new(n: i32) -> YearEnum {
		if n == 0 {
			YearEnum::YearZero(YearZero())
		} else if n < 0 {
			YearEnum::YearBC(YearBC(-n as u32))
		} else {
			YearEnum::YearAD(YearAD(n as u32))
		}
	}
}

impl std::ops::Deref for YearEnum {
	type Target = Year;

	fn deref(&self) -> &Self::Target {
		match self {
			YearEnum::YearZero(x) => x,
			YearEnum::YearBC(x) => x,
			YearEnum::YearAD(x) => x
		}
	}
}

The impl std::ops::Deref will allow us to call any method in the Year trait on the enum as returned from the factory, allowing this to effectively act as a trait object, but with no heap allocations! This seems like exactly what we want, but it’s a lot of boilerplate. Luckily, it’s very mechanical so creating a macro to do this for us is fairly easy (and I’ll throw in a bunch of other obvious trait implementations while we’re at it):

macro_rules! trait_enum {
	($trait:ident, $enum:ident, $( $item:ident ) , *) => {
		enum $enum {
			$(
				$item($item),
			)*
		}

		impl std::ops::Deref for $enum {
			type Target = $trait;

			fn deref(&self) -> &Self::Target {
				match self {
					$(
						$enum::$item(x) => x,
					)*
				}
			}
		}

		impl From<$enum> for Box<$trait> {
			fn from(input: $enum) -> Self {
				match input {
					$(
						$enum::$item(x) => Box::new(x),
					)*
				}
			}
		}

		impl<'a> From<&'a $enum> for &'a $trait {
			fn from(input: &'a $enum) -> Self {
				&**input
			}
		}

		impl<'a> AsRef<$trait + 'a> for $enum {
			fn as_ref(&self) -> &($trait + 'a) {
				&**self
			}
		}

		impl<'a> std::borrow::Borrow<$trait + 'a> for $enum {
			fn borrow(&self) -> &($trait + 'a) {
				&**self
			}
		}

		$(
			impl From<$item> for $enum {
				fn from(input: $item) -> Self {
					$enum::$item(input)
				}
			}
		)*
	}
}

And now to repeat the first refactoring, but with the help of this new macro:

fn format_year<Y: Year + ?Sized>(n: &Y) -> String {
	format!("{} {}", n.year(), n.era())
}

trait Year {
	fn year(&self) -> u32;
	fn era(&self) -> String;
}

trait_enum!(Year, YearEnum, YearZero, YearBC, YearAD);

impl Year {
	fn new(n: i32) -> YearEnum {
		if n == 0 {
			YearZero().into()
		} else if n < 0 {
			YearBC(-n as u32).into()
		} else {
			YearAD(n as u32).into()
		}
	}
}

struct YearZero();

impl Year for YearZero {
	fn year(&self) -> u32 { 0 }
	fn era(&self) -> String { "is not a year".to_string() }
}

struct YearBC(u32);

impl Year for YearBC {
	fn year(&self) -> u32 { self.0 }
	fn era(&self) -> String { "BC".to_string() }
}

struct YearAD(u32);

impl Year for YearAD {
	fn year(&self) -> u32 { self.0 }
	fn era(&self) -> String { "AD".to_string() }
}

We do still have two places with must be modified rather than extended (the macro invocation and the factory), but all other code can be written ignorant of those and in the same style as using a normal trait object. The normal trait objects can even be recovered using various implementations the macro creates, or even just by doing &* on the enum. Benchmarking these three styles on a somewhat more complex example actually found this last one to also be the most performant (though only marginally faster than the pure-enum approach), and the boxed-trait-object style to be more than three times slower.

So there you go, next time you ask yourself if you want the flexibility of a trait or the size guarantees and performance of an enum, maybe grab a macro and say: why not both!

Error Handling in Haskell

Posted on

When I first started learning Haskell, I learned about the Monad instance for Either and immediately got excited. Here, at long last, was a good solution to the error handling problem. When you want exception-like semantics, you can have them, and the rest of the time it’s just a normal value. Later, I learned that the Haskell standard also includes an exception mechanism for the IO type. I was horrified, and confused, but nothing could have prepared me for what I discovered next.

While the standard Haskell exception mechanism infects all of IO it at least has a single, well-defined type for possible errors, with a small number of known cases to handle. GHC extends this with a dynamically typed exception system where any IO value may be hiding any number of unknown and unknowable exception types! Additionally, all manner of programmer errors in pure code (such as pattern match failures and integer division by zero) are thrown into IO when they get used in that context. On top of everything, so-called exceptions can appear that were not thrown by any code you can see but are external to you and your dependencies entirely. There are two classes of these: asynchronous exceptions thrown by the runtime due to a failure in the runtime itself (such as a HeapOverflow) and exceptions thrown due to some impossible-to-meet condition the runtime detects (such as detectable non-termination). Oh, I almost forgot, manually killing a thread or telling the process to exit are also modeled as “exceptions” by GHC.

Once the initial decision to have a dynamically typed exception system was made, everything that could make use of an exception-like semantic in any case was bolted on. What am I going to do, though? Write my own ecosystem and runtime that works how I would prefer? No, I’m going to find a way to make the best of the world I’m in.

When dealing with this situation, there are two separate and equally important things to consider: exception safety, and error handling. Exception safety describes the situation when you are, for example, acquiring and releasing resources (such as file handles). You want to be sure you release the resource, even if the exception system is going to abort your computation unceremoniously. You can never know if this will happen or not, since the runtime can just throw things at you, you always need to wrap resource acquisition/release paths in some exception safety. There are a lot of complex issues here, but it’s not the subject of this post so suffice to say the main pattern of interest for dealing with this is bracket.

Error handling is totally different. This is where you want to be able to recover from possible recoverable errors and do something sensible. Retry, save the task for later, alert the user that their request failed, read from cache when the network is down, whatever.

The first move in this area that I saw that I liked, was the errors package. Many helpers for dealing with error values, and in earlier versions a helper that would exclude unrecoverable errors and convert the rest to error values. I liked this pattern, but wanted more. This is Haskell! I wanted to know, at a type level, when recoverable errors had already been handled. Of course, programmer errors in pure code and unrecoverable errors from the runtime are always possible, so we can’t say anything about them at the type level, but recoverable errors we could know something about. So I wrote a package, iterated a few times, and eventually became a dependency for the helper in the errors package that I had based my whole idea on. Until very recently, errors and unexceptionalio were the two ways I was aware of to handle recoverable errors (and only recoverable errors) reliably, and know at a type level that you had done so. Recently errors decided to change the semantic to fit the previously-misleading documentation of the helper and so unexceptionalio now stands alone (to my knowledge) in this area.

In light of this new reality, I updated the package to make it much more clear (both in documentation and at a type level) what hole in the ecosystem this fills. I exposed the semantic in a few more ways so it can be useful even to people who don’t care about type-level error information. I also named the unrecoverable errors. Things you might want to be safe from, or maybe log and terminate a thread because of, but never recover from. For now, I call these PseudoException.

UnexceptionalIO (when used on GHC) now exposes four instances of Exception that you can use even if you have no use for the rest of the package: ExternalError (for things the runtime throws at you, asynchronously or not), ProgrammerError (for things raised from mistakes in pure code), PseudoException (includes the above and also requests for the process to exit), and SomeNonPseudoException (the negation of the above). All of these will work with the normal GHC catch mechanisms to allow you to easily separate these different uses for the exception system.

From there, the package builds up a type and typeclass with entry and exit points that ensure that values in this type contain no SomeNonPseudoException. The type is only ever used in argument position, all return types are polymorphic in the typeclass (implemented for both UIO and IO, as well as for all monad transformers in the unexceptional-trans package) so that you can use them without having to commit to UIO for your code. If you use the helpers in a program that is all based on IO still, it will catch the exceptions and continue just fine in that context.

Finally, the latest version of the package also exposes some helpers for those cases where you do want to do something with PseudoException. For exception safety, of course, there is bracket, specialized to UIO. For knowing when a thread has terminated (for any reason, success or failure) there is forkFinally, specialized to UIO and PseudoException. Finally, to make sure you don’t accidentally swallow any PseudoException when running a thread, there is fork which will ignore ThreadKilled (you assumedly did that on purpose) but otherwise rethrow PseudoException that terminate a thread to the parent thread.

This is hardly the final word in error handling, but for me, this provides enough sanity that I can handle what I need to in different applications and express my errors at a type level when I want to.

Haskell2010 Dynamic Cast

Posted on

This post is not meant to be a suggestion that you should use this code for anything. I found the exploration educational and I’m sharing because I find the results interesting. This post is a Literate Haskell file.

Programmers often mean different things when they say “cast”. One thing they sometimes mean is to be able to use a value of one type as another type, converting as possible.

We’ll use dynamic typing to allow us to check the conversions at runtime.

> module DynamicCast (DynamicCastable(..), dynamicCast, Opaque) where
> import Data.Dynamic
> import Data.Void
> import Control.Applicative
> import Control.Monad
> import Data.Typeable
> import Text.Read (readMaybe)
> import Data.Traversable (sequenceA)

But we don’t want to expose the dynamic typing outside of this module, in case people become confused and try to use a Dynamic they got from elsewhere. Really we’re just using the Dynamic as an opaque intermediate step.

> newtype Opaque = Opaque Dynamic

Types can define how they both enter and exit the intermediate representation. This both allows casting existing types to new types, but also can allow casting new types to existing types without changing the instances for those existing types.

> class (Typeable a) => DynamicCastable a where
> 	toOpaque :: a -> Opaque
> 	toOpaque = Opaque . toDyn
>
> 	fromOpaque :: Opaque -> Maybe a
> 	fromOpaque (Opaque dyn) = fromDynamic dyn

And finally the cast itself.

> dynamicCast :: (DynamicCastable a, DynamicCastable b) => a -> Maybe b
> dynamicCast = fromOpaque . toOpaque

Let’s see some examples.

We’ll say that Integer and simple lists (including String) represent themselves and define no specific conversions.

> instance DynamicCastable Integer
> instance (Typeable a) => DynamicCastable [a]

Int is represented however Integer represents itself.

Anything that can convert to Integer can convert to Int.

Any String that parses using read as an Int can also convert to an Int.

> instance DynamicCastable Int where
> 	toOpaque = toOpaque . toInteger
> 	fromOpaque o = fromInteger <$> fromOpaque o <|> (readMaybe =<< fromOpaque o)

And now

dynamicCast (1 :: Int) :: Maybe Integer
Just 1

dynamicCast (1 :: Integer) :: Maybe Int
Just 1

This is pretty obvious and boring, but perhaps it gives us confidence that this is going to work at all. Let’s try something fancier.

Void is the type with no inhabitants, so it can never be converted to.

> instance DynamicCastable Void where
> 	fromOpaque _ = Nothing

Either is represented as just the item it contains, and any item can be contained in an Either.

> instance (DynamicCastable a, DynamicCastable b) => DynamicCastable (Either a b) where
> 	toOpaque (Left x) = toOpaque x
> 	toOpaque (Right x) = toOpaque x
>
> 	fromOpaque o = Left <$> fromOpaque o <|> Right <$> fromOpaque o

And now

dynamicCast 1 :: Maybe (Either Int Void)
Just (Left 1)

dynamicCast 1 :: Maybe (Either Void Int)
Just (Right 1)

dynamicCast (Left 1 :: Either Int Void) :: Maybe Int
Just 1

Maybe is very similar, store the Just as the unwrapped value, and store Nothing as Void.

> instance (DynamicCastable a) => DynamicCastable (Maybe a) where
> 	toOpaque (Just x) = toOpaque x
> 	toOpaque Nothing = toOpaque (undefined :: Void)
>
> 	fromOpaque = fmap Just . fromOpaque

dynamicCast (Left 1 :: Either Int Void) :: Maybe (Maybe Int)
Just (Just 1)

To be able to cast the contents of a Functor, the possible failure also lives in the Functor, so we need a wrapper.

> newtype FunctorCast f a = FunctorCast (f (Maybe a))

> mkFunctorCast :: (Functor f) => f a -> FunctorCast f a
> mkFunctorCast = FunctorCast . fmap Just

> runFunctorCast :: FunctorCast f a -> f (Maybe a)
> runFunctorCast (FunctorCast x) = x

> runTraversableFunctorCast :: (Traversable f) => Maybe (FunctorCast f a) -> Maybe (f a)
> runTraversableFunctorCast = join . fmap (sequenceA . runFunctorCast)

> instance (Functor f, DynamicCastable a, Typeable f) => DynamicCastable (FunctorCast f a) where
> 	toOpaque = Opaque . toDyn . fmap toOpaque . runFunctorCast
> 	fromOpaque (Opaque dyn) = FunctorCast . fmap fromOpaque <$> fromDynamic dyn

runTraversableFunctorCast $ dynamicCast (mkFunctorCast ["1"]) :: Maybe [Either Void Integer]
Just [Right 1]

Awesome Voicemail for Android

Posted on

Most phone carriers these days have pretty poor voicemail capabilities. You have to call in to “check” your voicemail, your voicemail box can fill up, and voicemails just play in order without any good way to see what you want.

There have been some advancements in so-called “visual voicemail”, but they are not available to all of us. In this post I will show you how to set up an amazing voicemail for your Android-powered device that only requires your carrier support call forwarding (a pretty standard feature, these days). You will be able to get your voicemails instantly (or, if you don’t have cell data, whenever you have wifi), see immediately who they are from and keep them sorted by the sender, and also read a text approximation of the content so that you don’t always have to listen to it!

All services and technologies referenced in this post are Free Software or Open standards.

You’ll need a Jabber (also called XMPP) account

If you already know you have one, and know what your Jabber ID is, you can skip to the Movim login below. For everyone else, I suggest you register with Movim. Do this part from your computer (not from your phone or tablet). If you click that link, you’ll see a screen like this:

Register with Movim

Fill it in. Your Jabber ID will be whatever username you choose, plus “@movim.eu”. Don’t forget your Jabber ID or password! Push “Create” and you’ll see a page like this:

After Registering with Movim

Click the link that I have circled in red to be taken to the Movim login page, which looks like this:

Movim Login

Enter your full Jabber ID (username you selected followed by “@movim.eu”) and password. Congratulations, you are a part of the Jabber network!

Leave the logged-in Movim tab open while you do the next part.

Get a phone number with the voicemail service

The way this voicemail is going to work, you’re going to set call forwarding to another number. So you’ll get a number with the voicemail service that is in your local area so that the forwarding is a “local call”. The numbers cost $2.99 USD/month right now, but the first 30 days is free so you can try it without risk or handing over your credit card or anything like that.

Head to cheogram.com and you’ll see something like this:

Cheogram

If one of the displayed phone numbers is in your local area, you can click that. Otherwise click the “…” and you can search by area code for a local number. Write down the number you select, you will need it later. Once you have selected a number, you will see a screen like this:

JMP Register: fill out JID

Fill in your Jabber ID as shown and click “Submit” to continue. The registration process will send you a verification code as a message. So head back to your logged-in Movim tab.

Movim Chats Screen

If necessary, click the icon I’ve circled in red to go to the “Chats” screen. Then, select the conversation I’ve circled in blue to get your verification code. It will look like this:

Movim chat showing JMP verification code

That part I’ve circled in red is your verification code. Cut-and-paste that back into the registration process in the other tab, like so:

Entering the verification code for JMP registration

Press submit, and scroll all the way to the bottom of the next page. Here you will fill out and verify your real phone number (the one people use to call your cell phone already). We will use this later to record your voicemail greeting. The filled in page should look like this:

Set JMP forwarding number

When you press “Submit” you will receive a phone call at the phone number you entered. A voice will read you a verification code, which you must type into the form that will look like this:

JMP verification code from phone call

Press submit, and you’re done this part!

Set up the voicemail

Head back to your logged-in Movim tab:

Back in Movim, Cheogram wants to talk

If necessary, click the icon I’ve circled in red to go to your “Contacts” screen, then click the green checkmark I’ve circled in blue to allow cheogram.com to talk to you.

Click the cheogram contact

Then, click your newly-added Cheogram contact, which I have circled in red.

Select the "configure calls" action

Now we want to configure the call behaviour of your new number to always go to voicemail. So select the “Configure Calls” action, which I have circled above in red.

Set it to go to voicemail after 0 seconds

We want it to go to voicemail right away, so set it to 0 seconds and press “Submit”.

Message showing configuration has been saved

You should see a message indicating the configuration has been saved, as above. You can just click “Close” on this message.

Select the "record voicemail greeting" action

Your voicemail is working now, but the greeting on the mailbox will be a robot voice. Probably you want to record a greeting in your own voice, so click the “Record Voicemail Greeting” action, which I’ve circled in red above. You will receive a call on your phone, and a message will tell you to say your desired greeting at the beep. When you are done with your greeting, hang up, and it will be set automatically.

You can just close this one

Once you’ve recorded a greeting, just press “Close” to get rid of the notice on your screen. If you want to change your greeting at any time, just select the action again.

Setting up call forwarding

Of course, you need to actually set up your phone so that your carrier will forward calls you don’t answer to the voicemail service. Every Android version is slightly different, but I’ll walk you through a generic process and it should be fairly similar on your device.

Go to Android call settings

Go to your dialler app, tap the three-dots menu in the top right, and select “Settings”. This may also be under “Call Settings” in your global device settings menu.

Android dialler settings screen

If necessary, tap “Calls” to go into call settings.

Tap "Call forwarding"

Tap “Call forwarding” to go to forwarding-specific settings.

Call forwarding settings

There are often various call forwarding settings available, set everything (except for “Always forward”, you don’t want that) to the phone number you selected from the voicemail service, which you wrote down earlier.

Getting Voicemails on the Go

Your voicemail is all set up and working now! But, probably you want to be notified of new voicemails on your cell phone, and not through the Movim web interface on your computer. So you’ll need a Jabber app for your phone. I suggest getting Conversations which you can get for a couple bucks from Google Play, Amazon Apps, or F-Droid.

Conversations first launch screen

When you first start Conversations, it may ask if you want to create a new account. You already have an account, so choose “Use my own provider” which I have circled in red.

Convensations Login

You will then see a login screen, very similar to the Movim login screen. Enter your full Jabber ID (remember: your username plus “@movim.eu”) and password, then tap “Next”.

That’s it! You’re all set up to receive your amazing new voicemails directly to your Android phone!

UX Stability

Posted on

When I help friends and family with technical issues, or listen to them complain generally about their tech issues, one big theme comes up often: the upgrade treadmill. I don’t just mean that they complain that they have to always buy a new computer (though this is certainly an issue), but when they get a new computer they don’t know how it works. Every time an update for any piece of software installs, they have to learn their system all over again. And they feel like they didn’t really have a great handle on it to begin with.

This, I believe, actually leads to users being less willing to learn in the first place, since they (often rightly) believe that any knowledge they gain will be obliterated by changes to their User eXperience in short order. Software systems are, in this way, very user-hostile.

One way to solve this problem might be to simply not install updates, but this leads to a whole host of issues. The first one technical people will talk about is that not installing updates means your computer is even more full of security holes than usual. Enterprise-focused solutions involve so-called “Long Term Support”, where security fixes are backported to older versions of software for some support window. This can help in the short-term, but faces its own dilemma: if the support term is too short, then users are still upgrading fairly often, and the longer you make the support term, the longer users have to wait for new features and (sometimes) bugfixes.

But wait! Don’t the users not want new features? Isn’t this a good thing? Wrong. Users want updates what they don’t want is change. When Firefox gains the ability to play a new kind of video, users want that, because they want the webpages they visit to work. When Libreoffice improves support for a popular file format, users want that, because they want to be able to open files they get sent. Even straight-up new functionality may be welcome in certain cases. So long as the new feature does not invalidate the user’s existing workflow. This is the key. A user that can trust their workflow will keep working (and you won’t replace all their menus with new menus, or worse, non-menus) is (I think) more willing to learn to begin with. Certainly more happy in the long run.

So keeping a system stable in the way that, say, Debian or RHEL or Ubuntu LTS do is a very useful start, but it’s not the whole story. We need a system that stays the same (or at least, whose core components change very little) while also receiving bug fixes and new functionality. Backporting, from time to time, bugfixes and new features in a way that preserves the user’s experience. For what support window? This is a big task, and starting with shorter timeframes may be needed, but ultimately? Forever. Or for the life of the users at least. A user should never be put into a position where they are forced to re-learn their system just to keep using it. Computers are tools that many people find essential to their daily lives, and there is a duty to provide them with systems that keep working, not just technically, but for the user.

Obviously, we cannot achieve this with proprietary software, so software freedom is an important part of this. And also, we cannot easily achieve it with any application that delivers the UI remotely (such as a “web app”), so native clients for popular web applications and similar technology may be needed in order to be able to provide this kind of stability. This is not a small task that we can accomplish overnight, but I believe it is part of the essential solution to the problems our society faces with their daily computing needs.