One equality operator to rule them all

In a lot of programming languages there are two different concepts for equality: Reference equality (also called Identity) and Value equality.

Reference equality is the same as equality of memory addresses. Two objects are the same if they are the same instance (iif they occupy the same address in memory).

Value equality is semantic equality. Two objects are equal if the values in them mean the same thing. For example: two instances of IPAddress that represent the address “127.0.0.1” are equal even if they have been instantiated in different places.

My plan with this article is to convince you that there should only be one equality operator. Let me make my point.

First: There should be a null-safe equality operator.*

This means that a language should have some means of comparing objects which won’t throw when a null reference gets compared. For most languages this is the == operator. The Equals instance method is problematic because you have to null check your object first (and you will end up forgetting to do so eventually).

*: It would be much better if we removed null references from all modern languages for good, but let’s leave it at that for now.

Second: Boxing and two kinds of equality are a dangerous mix.

This is very clear when we realize that 1 == 1 but (object)1 != (object)1. This is just a problem waiting to happen, really.

*: Of course, you should really rethink your code if you’re operating on boxed objects. At least in C#, creating generic (as in polymorphic) code is almost certainly the better approach.

Third: In many cases, reference equality is simply misleading.

In C#, for instance, IPAddress.Parse(“127.0.0.1”) != IPAddress.Parse(“127.0.0.1”). Any type that conveys meaning will be thought of according to that assigned meaning. Unless you’re tracking instances, reference equality is far more confusing than it is useful.

Fourth: More generally and more importantly, having the same operator mean two different things is dangerous.

Why? Well, what does == really mean?

== means Maybe Reference Equality, Maybe Value Equality. == can mean two distinct things depending on what gets compared, but with one unique form/appearance.

And this can’t be good. + is addition for numbers and concatenating for strings, but the signatures are so different that it is hard to get it wrong. What would you think of + if it were addition for integral number types such as Int and Long but meant addition with rounding for fractionals such as Float and Double (we would make a proper Add method available, obviously)? I’m sure you would think it is an error waiting to happen.

All previous cases would be more or less solved if we created a clear separation of equality operators. Kotlin, for example, has == for value equality and === for reference equality. I would like to convince you, however, that we only need one kind of equality for general use, and that reference equality should only be used to implement this equality operator that I propose. For that, let us explore a more interesting case:

 

An interesting case: the Socket class

When working with multiple Sockets, it is often necessary to compare them to one another. Now, two sockets connected to the same address in the same port aren’t equal because they are independent communication channels, so wouldn’t value equality spoil that?

No, it wouldn’t. In fact these two sockets use different local ports. Even if the sockets aren’t connected nor have been modified yet, the operating system labels all these sockets to manage them internally. Of course, the operating system could use the memory address of the created socket internally, which would then be the socket’s label.

But even in that case, we only need one equality operator. It just happens to be the case that it may be implemented by comparing memory addresses in this case. Sockets just happen to be a case where it is desirable to make equality be Reference Equality. It is a case where semantics matches identity. So in our implementation of == for Socket we could then use object.ReferenceEquals. So do note that Reference equality would only be used to properly implement our beloved equality operator.

Ok.. These examples are good, but aren’t there exceptions?

I believe not. Although of course I can’t provide a formal proof, there is one thing I do know: there is only one kind of equality in Haskell, and Haskell has been used a lot already. I wouldn’t be surprised if other languages do the same.

How do we fix this in C# ?

Sadly, I don’t believe it is possible without changing the language substantially and breaking existing code. What I propose below is the least invasive set of changes I can think of for the language, and it is certainly not pretty. There are better ways around this problem.*

Proposed breaking change: We could make the == operator non overridable and make its implementation always use the Equals instance method of its left-most non null argument (after proper null checks).

One could argue that choosing the left-most argument would make this implementation asymmetric. However, any correct implementation for equality is necessarily symmetric (if a == b then b == a), so it wouldn’t matter if the implementation picked the left-most argument to call Equals on it. Also, we could go ahead and change == to a generic ==<T>(T a, T b) to make this a non-issue. This would break even more code and I’m not sure how all of this would sound to language designers, though.
Also, there is some concern over efficiency. Calling a virtual method like Equals would involve dynamic dispatch, bringing its associated costs with it. I believe this is unavoidable.*

*: Unless we are willing to go even further with our breaking changes. There is a proposal to implement type classes in C# (https://github.com/dotnet/csharplang/issues/110). Type classes enable a high level of ad-hoc polymorphism while maintaining static dispatch. They are a great feature and one I vouch for strongly. If you’re curious, read my article on it.
With type classes, we could make == an operator/function of some Equatable<T> type class. We would then make its default implementation like the one described above, while still being overridable so that we can override it for some types to avoid calling Equals.

 

So.. what are your thoughts on this? Do you have counter-examples or do you disagree on some issue? Can you think of more unintended consequences by changing the language as I proposed (I’m sure there are many!)?

 

EDIT (2018-01-06 14:40): I’m not sure how I missed this, but the new feature of nullable reference types makes my proposed language changes mostly unnecessary. It is also a breaking change, of course, but not only does it improve the language significantly, it also improves the state of equality. After opting in for this new feature, just make sure you never use == again. Stick to Equals and you should mostly be fine. I say “mostly” because not even Equals is always overridden to mean value equality. In the case of StringBuilder, for instance, its Equals(object) is inherited from Object and tests for reference equality while its IEquatable<StringBuilder>.Equals(StringBuilder) method tests for value equality. I believe this only strengthens the claim that there should be a single general purpose equality operator, keeping reference equality only as a means to implement equality in some cases.

Advertisements

Interfaces and typeclasses: Number APIs in C# and Haskell

In C# sometimes I sorely miss something like an INumber<T> interface with methods Add, Subtract, Multiply and others. The lack of this means it is cumbersome to write generic code on numbers. It means that instead of writing something like:

T Sum(IEnumerable<T> numbers) where T : INumber<T>;

We have to write all possible overloads:

double Sum(IEnumerable<double> numbers);
float Sum(IEnumerable<float> numbers);
decimal Sum(IEnumerable<decimal> numbers);

The implementation body of all these functions will be exactly the same, but we have to write it multiple times anyway. Some people work this out by creating generic methods for the operations they need while resorting to runtime type-checking:

T Add(T a, T b) {
  if (a is double) {
    return (double)a + (double)b;
  }
  else if (a is int) {
    return (int)a + (int)b;
  }
  // .. and so on
}

This is not a terribly good solution, however, since we have no compile-time guarantees that the type T is a number at all, not to mention the performance costs of runtime type-checking. What’s more, this solution can’t be extended to new types; what if someone writes a Complex class to represent complex numbers? The implementation of Add would have to be open for modification, so this code could never be packaged in a library.

Sadly, it is hard to solve this conundrum without changing the Base Class Libraries themselves. The only thing we could hope for is for the people at Microsoft to design numeric interfaces such as INumber<T> (or others) and make our well-known primitive numeric types implement these interfaces.

Enter Haskell.

Haskell is the programming language I’ve been playing with for the last year, and except for the steep learning curve, I have only good things to say. It can be extremely expressive and it is amusing to see that when my code builds it almost certainly works! It is also extremely terse, as you can easily see by this window manager’s less than 2000 lines of code, xmonad, and by the code on this post.

In Haskell, the problem shown above can be solved with typeclasses, which we can think of for now as something similar to interfaces, since they specify a contract that concrete types must obey. The big difference here is that when we create a typeclass, we can make types we don’t own implement (in Haskell: instantiate) it! This means we can design our numeric typeclasses and have Haskell’s standard numeric types, such as Data.Int and Data.Complex, instantiate them! What’s more: in Haskell we can create functions named “+”, “*”, “/”, “-” with infix application. No need to differentiate operators from regular functions: they are one and the same!

module Numeric where -- "Numeric" will be the namespace in which the definitions below will live

import qualified Prelude -- The prelude is a base set of types, typeclasses and functions that are used for common tasks

-- The "class" construct actually creates a typeclass (similar to an interface). Here we say that concrete types that instantiate this typeclass must implement functions called "+" and "*", both of them receiving two parameters of type "t" and returning an object of type "t" as well
class Number t where
  (+) :: t -> t -> t
  (*) :: t -> t -> t
  zero :: t

-- Specifies the type "Int", which we don't own, as an instance of "Number". The Add and Multiply functions already exist in Haskell inside the Prelude. We'll use those.
instance Number Prelude.Int where
  a + b = (Prelude.+) a b
  a * b = (Prelude.*) a b
  zero = 0

-- Now we can define a generic "sum" function with sums all numbers in a list. The following line says that type "t" must be an instance of the typeclass "Number", and that it receives a list of t and returns t. There are better ways to write this in Haskell, but that is not important right now
sum :: Number t => [t] -> t
sum [] = zero -- This is our base case: empty list sums to zero
sum (x:xs) = x + sum xs -- This separates the first element in the list, "x", from the remaining list, "xs"

Note to the reader: Haskell’s prelude already comes with a Num typeclass with more than just addition and multiplication, and existing numeric types already implement those.

And that’s it! The syntax up there really is that short, and it really is type-checked! Also, it only scratches the surface of Haskell is capable of. Believe me, just a tiny scratch.

It is important to notice here that in C# it is entirely possible to make new types that can be added to existing types by defining a public static T operator +(T a, T2 b) in the new type T. What we can’t do is specify generic type constraints that allow us to work with numeric types. In reality, this is not just about numeric APIs: it is just a consequence of the fact that we can’t make types we don’t own implement interfaces, combined to the fact that parametric polymorphism only allows restrictions based on subclassing or interface implementation (with the exception of the new(), struct and class constraints).

It is not hard to think of how useful typeclasses can be. Why doesn’t IList and ICollection implement IReadOnlyCollection anyways? Maybe we want both StringBuilder and System.String to implement IString, allowing for generic code that doesn’t need to convert between one and another. There are many possibilities out there.

Let’s take this a little further, because  it can get pretty interesting: how about subtraction? In C# we can subtract a TimeSpan from a DateTime and get another DateTime. Subtracting an int from an int, however, yields another int. Can we encode this information in Haskell in a way that is checked by the compiler itself, allowing us to write generic code that is able to subtract one object from another? The answer is yes.

More: can we develop a set of typeclasses that makes sure that arithmetic operations will NEVER overflow? This would really help us write banking software, for example, allowing us to add and subtract enormous values without worrying about it. With two language extensions called MultiParamTypeClasses and TypeFamilies we can!

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TypeFamilies #-}
module Numeric where

import qualified Prelude
import Prelude (Int, Integer, toInteger, negate) -- These types and functions will be available without the need to be prefixed by "Prelude."
import Data.Time

class Subtractive t1 t2 where
  type Difference t1 t2 :: * -- This is just a fancy way of saying that the combination of "Difference" and two types is meant to represent another type
  (-) :: t1 -> t2 -> Difference t1 t2

-- In Haskell the type "Integer" represents arbitrarily large integers. They are like "BigInteger" in .NET or Java. Our implementation of (-) is exactly the same as Prelude's in this case.
instance Subtractive Integer Integer where
  type Difference Integer Integer = Integer
  (-) = (Prelude.-)

instance Subtractive Int Int where
  type Difference Int Int = Integer;-- Here we say that the Difference between two Ints is an Integer, because no matter how small two Ints are, their difference is always representable as an Integer
  a - b = (toInteger a) - (toInteger b)

-- Let's just enjoy ourselves a little and put in some date and time types in the mix
instance Subtractive UTCTime NominalDiffTime where
  type Difference UTCTime NominalDiffTime = UTCTime
  a - b = addUTCTime (negate b) a

-- The function below works for any two types t1 and t2 which allow for (t1 - t2). It takes in a list of tuples and returns a list of the differences between the two elements in each tuple.
someGenericDifferenceFunction :: Subtractive t1 t2 => [(t1, t2)] -> [Difference t1 t2]
someGenericDifferenceFunction [] = []
someGenericDifferenceFunction ((a, b) : xs) = (a - b) : someGenericDifferenceFunction xs -- Quick reminder: ":" is a function that takes an element and a list and prepends the element into the list

The example above is still incomplete: we need instances of Subtractive Integer Int and Subtractive Int Integer for this API to become more practical. This is left to the reader, however. Meanwhile, let’s try this out in ghci:


terminal> ghci
ghci> :l Numeric.hs
*Numeric> let list = [(1, 2), (5, 5), (10, 3)] :: [(Int, Int)] -- We need to specify the type of "list" because literals could be any type that implements "Num", including Int and Integer.
*Numeric> let difs = someGenericDifferenceFunction list
*Numeric> difs
[-1,0,7]
*Numeric> :t difs
difs :: [Integer]

C# is great and a lot of what we achieved with Haskell could be achieved through an ISubtractive<T, T2, TResult>, if only we could make existing types implement it. We could also create structs that simply wrap existing types and write implicit coercion rules from (and to) them, making these new types implement our custom interfaces, and make a lot of things possible with that, but we wouldn’t be able to pass an instance of IEnumerable<WrapperType> as a replacement for a IEnumerable<WrappedType> without explicit casting, for example, and we’d also have to watch out and stay away from built-in arithmetic operators, since they might no longer obey the relations between types specified through the interfaces (we might want int + int = BigInteger).

So that’s it. I hope you’ve enjoyed your reading, but most of all I hope any C# or Java (or any other mainstream language) developer that reads this gives Haskell a shot. It really is an amazing language.

Any comments and corrections are very welcome!

Mono ASP.NET project deployment with Web.config XDT transformations

One thing that I’ve always wanted in the Mono stack was the ability to deploy ASP.NET MVC applications from a terminal, and to get Web.config xdt transformations along the way (how great would that be!?). Today I managed to cook something! It is not perfect, but it works pretty well for my needs and will probably be fine by most people’s standards. Let’s get to it already!

You will need a target for xbuild (Mono’s MSBuild replacement) and a MSBuild Task called TransformXml, responsible for XDT transformations. To build this Task you will also need a library called Microsoft.Web.Xdt. Let’s do it step by step.

First, create a library project called WebTasks (you can actually choose whichever name you prefer, just remember to change it in the target file later) in Monodevelop and add the following class to it:

using System;
using Microsoft.Build.Utilities;
using Microsoft.Build.Framework;
using Microsoft.Web.XmlTransform;

namespace MSBuildTasks
{
  public class TransformXml : Task
  {
    [Required]
    public ITaskItem Source { get; set; }

    [Required]
    public ITaskItem Transform { get; set; }

    [Required]
    public ITaskItem Destination { get; set; }

    public override bool Execute () {
      var originalFileXml = new System.Xml.XmlDocument();
      originalFileXml.Load(Source.ItemSpec);

      using (var xmlTransform = new XmlTransformation(Transform.ItemSpec)) {
        if (xmlTransform.Apply(originalFileXml) == false)
        return false;

        // originalFileXml is now transformed
        originalFileXml.Save(Destination.ItemSpec);
      }

      return true;
    }
  }
}

Grab a copy of Microsoft.Web.Xdt, add a reference to it, add references to Microsoft.Build.Utilities and Microsoft.Build.Infrastructure too (these should be in the GAC) and build this library, holding on to the generated assembly file.
* Warning: This is most likely not a complete implementation of the TransformXml Task. Since I couldn’t find any decents docs on it and it serves its purpose, I’ll leave it at that.

Now, this is the target I created to actually deploy my files to a specified destination (copy and paste it to a file called WebDeploy.targets or whatever name you want!):

<?xml version="1.0" encoding="utf-8"?>
<Project ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
  <UsingTask TaskName="TransformXml" AssemblyFile="WebTasks.dll" />
  <Target Name="Deploy" Condition="'$(DeployDir)' != '' And !$(SkipCopyUnchangedFiles)" DependsOnTargets="Build">
    <Copy SourceFiles="@(FileWrites)" DestinationFolder="$(DeployDir)\%(RelativeDir)" />
    <Copy SourceFiles="@(Content)" DestinationFolder="$(DeployDir)\%(RelativeDir)" />
    <TransformXml Source="Web.config" Transform="Web.$(Configuration).config" Destination="$(DeployDir)\Web.config" Condition="Exists('Web.$(Configuration).config')"/>
  </Target>
</Project>

* Important: Microsoft.Web.Xdt.dll, WebTasks.dll and WebDeploy.targets must all be in the same directory!
* Monodevelop insisted in trying to import a targets file from $(MSBuildExtensionsPath)\Microsoft\VisualStudio\v10.0\WebApplications\Microsoft.WebApplication.targets, resulting in an error everytime I tried to build my project, since the v10.0 folder didn’t exist in my Mono installation. To solve it, I just symlinked it to v9.0.

We are almost there! This is our last step. Open your ASP.NET project’s file and add the following line to it (you can add it near the other imports for elegance’s sake):

<Import Project="RelativePathTo\Deploy.targets" />

Now that everything is set up, just run:

$ xbuild ASPNETProject.csproj /t:Deploy /p:Configuration=Release /p:DeployDir=deployDirRelativeToProjectFile /p:SkipCopyUnchangedFiles=false

And the files are now correctly deployed!
* Caveats:
– I have only tested this with MY ASP.NET MVC project. Although the only bad thing I’ve noticed so far is that the “obj” folder and mdb files inside the bin directory get copied too, it certainly needs more testing.
– You have to set SkipCopyUnchangedFiles to false or you will run into trouble in the future. We rely on a property called FileWrites set by one of the targets used in the build process. If you set SkipCopyUnchangedFiles to true, FileWrites will not include files from your project’s dir if they haven’t been modified, which could lead to some files not being deployed if you, for instance, keep building with the IDE and after many consecutive builds decide to deploy with this script. In fact, the target I wrote will not run if you don’t set it to false.

If you use it and have any problems, I’d really like to know!

C# Interop with C bitfields

Recently I have been writing a small ASP.NET module with Mono for Nginx. I know there is a FastCGI module for hosting ASP.NET with Mono, but I’m doing this mostly with the purpose of learning.

What I am writing is not a FastCGI module, but rather one that embeds Mono within Nginx, working far more closely to the webserver than the FastCGI module probably can.

One of the most interesting things in all this is doing Interop between managed C# code and unmanaged C code. Just to illustrate, one of the C structs found in Nginx I have to deal with is this:

ngx_buf_s from https://github.com/nginx/nginx/blob/master/src/core/ngx_buf.h:

struct ngx_buf_s {
  u_char *pos;
  u_char *last;
  off_t file_pos;
  off_t file_last;

  u_char *start; /* start of buffer */
  u_char *end; /* end of buffer */
  ngx_buf_tag_t tag;
  ngx_file_t *file;
  ngx_buf_t *shadow;

  /* the buf's content could be changed */
  unsigned temporary:1;

  /*
  * the buf's content is in a memory cache or in a read only memory
  * and must not be changed
  */
  unsigned memory:1;

  /* the buf's content is mmap()ed and must not be changed */
  unsigned mmap:1;

  unsigned recycled:1;
  unsigned in_file:1;
  unsigned flush:1;
  unsigned sync:1;
  unsigned last_buf:1;
  unsigned last_in_chain:1;

  unsigned last_shadow:1;
  unsigned temp_file:1;
  /* STUB */ int num;
};
The problem is how to write a struct in C# that possesses the same memory layout as the struct above. The answer is actually quite simple: mostly, it is not possible.
The major problem lies in the bitfields: there is a lot of room to compilers in the C standard as to how they should layout bitfields in memory. How do we deal with this in a manner that is not compiler dependant? We leave the setting and getting of those bits to unmanaged code. In the end, this is what I got in C#:
[StructLayout(LayoutKind.Sequential)]
public struct NginxResponseBuffer
{
   #region Internal calls to set and read data from the struct
   [MethodImpl(MethodImplOptions.InternalCall)]
   private static extern void SetInMemoryBuf(ref NginxResponseBuffer buf, bool flag);

   [MethodImpl(MethodImplOptions.InternalCall)]
   private static extern void SetLastBuf(ref NginxResponseBuffer buf, bool flag);
   #endregion

   public IntPtr pos;
   public IntPtr last;
   public long file_pos;
   public long file_last;

   public IntPtr start;
   public IntPtr end;
   public IntPtr tag;
   public IntPtr file;
   public IntPtr shadow;

   // There are eleven bits that compose a bitfield from now on.
   // Since the C standard does not guarantee how these will be layed out in memory,
   // it is better to just have a 32 bits property here (11 bits will hopefully be padded to 32 bits).
   // After that, getter and setter methods will invoke unmanaged code that knows how to deal with these fields.
   // Disable unused field warning
   #pragma warning disable 0169
   private readonly byte b1, b2, b3, b4;
   #pragma warning restore 0169

   public bool Memory {
     set
     {
       SetInMemoryBuf(ref this, value);
     }
   }
   public bool LastBuf {
     set
     {
       SetLastBuf(ref this, value);
     }
   }

   public int num;
}

The internal methods are mapped to call unmanaged code that will set the bits accordingly (I mapped them using mono_add_internal_call, but you can also do this with the DllImportAttribute if you are on Windows or if you are not embedding mono), and the 4 bytes should never be used, even inside the code in the struct itself. Although I could have specified an explicit layout for the struct to skip these bytes without declaring them, I would then sacrifice 32bit/64bit portability, since pointers could assume different sizes. These are the methods that do the setting on the unmanaged side (please note that ngx_buf_t is just a typedef’d ngx_buf_s):

void set_in_memory_buf(ngx_buf_t *buf, bool flag)  {
   buf->memory = flag ? 1 : 0;
}

void set_last_buf(ngx_buf_t *buf, bool flag)  {
   buf->last_buf = flag ? 1 : 0;
}

I only added setters to two fields – Memory and LastBuf – because these are the only two I need right now. So far, getters aren’t needed for any of those.
I will keep you posted as to how the development of this module for Nginx goes, posting something interesting now and then. I still haven’t got it working, as apparently the call to HttpRuntime.ProcessRequest never returns.