DEV Community: Vsevolod

GoF Functionalized

Vsevolod — Mon, 22 Apr 2024 16:25:43 +0000

As a programmer with an object-oriented Java background, I'm used to thinking in terms like aggregation and inheritance. These and other OO concepts do not have direct counterparts in the functional world. Thus, the conversion, if you require one, might pose a challenge. Today, I'm going to tackle this, by providing you with a simple tool set for performing this mapping.

\rarr FP

Why the hell the article is named GoF then? ~~Heh, just wanted it to sound gravely.~~ Gang of Four patterns are the globally adopted set of the object-oriented best practices. My thought process was the following: if I can map GoF to FP, I'll be able to map any OO code to FP. I might be wrong here, but that's a solid foundation to say the least.

Are you going to explain GoF? No, I'm not. There are tons of other resources out there, which did this explanation better than I ever could. My favorite one being the Refactoring Guru. In fact, I've honestly stolen pattern usage examples from there to showcase below. On top of that, I will only cover the subset of GoF patterns to highlight the core techniques, which in turn should be enough to convert other patterns. So, to keep up with an article, you should be pretty fluent with the OOP version of GoF. At the beginning of each chapter, I'll link the object-oriented pattern that will be discussed. If you feel uncertain about some of them, take a pause there to rehearse.

Are you going to begin already? Yes, yes, right away, my patient reader.

Construction

To whet our appetite, let's start with an extremely simple pattern and an extremely simple conversion. The Builder one. Any object we create in our applications eventually should be used as an argument to something. Otherwise, it shouldn't be created in the first place (which is in fact true for lazy languages, eager ones create such objects and then just discard them). Thus, we could narrow down the core use case of any Builder to a representation of default and, more importantly, named arguments in an arbitrary order. Languages without all these three features require Builder to emulate them. For example, in Java default property is achieved by using method overloading. However, the other two features have no direct representation, therefore Builder is highly popular in Java code.

void drive(
    CarBuilder.createCar()
        .seats(2)
        .engine(new ElectricEngine())
        .build()
)

The same example in Kotlin, which possesses all three features:

fun drive(
    Car(
        seats = 2,
        engine = ElectricEngine(),
    )
)

The latter code does not look considerably more concise comparing to the former one, until you remember all the boilerplate required for the first one to compile and work. Anyway, being arguably cleaner, this is a mapping from OOP to FP, since the Kotlin example directly produces an immutable record from the provided values, while Java one mutates CarBuilder state in order to produce a Car object.

Ornamentation

Guessing from the title, the next pattern we are going to convert is The Decorator. This one contains the OOP bread and butter - inheritance and aggregation. I need to make a side note here: I'm intentionally using the term aggregation instead of the terms composition or association. Since the first one could be easily confused with the functional composition and the second one is quite a broad concept even in the object-oriented world.

The original shortened (and thus non-compilable) Java/OOP version looks like the following:

interface Notifier {
    void send(String message);
}

class BaseDecorator implements Notifier {
    BaseDecorator(Notifier notifier) { ... }

    void send(String message) {
        this.notifier.send(message);
    }
}

class SlackDecorator extends BaseDecorator {
    void send(String message) {
        super.send(message);
        sendSlackMessage(message);
    }
}

Since send is essentially a function $\rarr Unit$ , this hierarchy boils down to a single function:

fun slackNotification(
    baseNotification: (String) -> Unit = {},
): (String) -> Unit = { message ->
    baseNotification(message)
    sendSlackMessage(message)
}

And is usable as:

val notifier = slackNotification(
    facebookNotification(
        smsNotification()
    )
)
notifier("Hello World!")

As you might have grasped already, the functional tool we used here is named currying. Although Kotlin's currying looks less elegant than the one from the truly functional languages, the result is still much more concise than the original approach.

Reinforcing my point that these two tools can be reduced to one, in OOP there is already a known morphism from inheritance to aggregation. Additionally, it's not only known but is quite popular in a sense that for the most cases it's recommended to choose aggregation between the two. Functional paradigm removes this choice and leaves you with a single option, which can be considered as a form of inheritance, since more specific functions close over arguments passed to a more abstract ones. Rephrasing slightly, returned closure is a child of the parent function. Even more easily, we can convince ourselves that currying is a form of aggregation, since a curried function aggregates data and behavior and then at some point in time performs computations based on those aggregations.

Enumeration

From the title, you might have assumed that we're going to discuss The Iterator now. However, I'm proposing to review the more specific kind of enumeration, the enumeration of the tree leafs. I'm talking about The Composite. This one is essentially a tree of data and functional languages are famous for dealing with tree-like data structures. The original pattern has an interface with two children and a method to execute some logic for all off them:

interface Component {
    fun execute()
}

class Leaf(val value: String) : Component {
    override fun execute() = println()
}

class Composite(val components: List<Component>) : Component {
    override fun execute() = components.forEach(Component::execute)
}

In OOP code, we see here an inheritance relation. But this inheritance has one distinctive property in comparison to the one we saw above in a Decorator - all children are defined in the same place and thus are known at the compile time. In the object-oriented world, this relation is usually called sealed inheritance. To contrast with an open one in Decorator. The difference is that in Decorator children aren't known beforehand, they might be added later in some library using your library, providing base decorator. In its core, a parent in the sealed inheritance is a sum of all children (i.e. in our example there are only two possible Components - Leaf or Composite). This is how the same hierarchy is written functionally:

data Component a = Leaf a | Composite [Component a]

And this is how to execute our functional Composite:

execute :: Component String -> IO ()
execute (Leaf x) = putStrLn x
execute (Composite xs) = forM_ xs execute

Per my taste, this looks strikingly more powerful than the OOP version (even in a quite concise Kotlin code). But that's debatable. What's not debatable is the fact that we have a one-to-one mapping between sealed inheritance and sum type.

Instead of stopping here, I would like to discuss one more notable conversion technique required for the Composite to become fully functional. In the purely OOP version of the pattern, the components of the Composites are stored in a mutable private field:

private List<Component> components;

void add(Component component) { 
    components.add(component); 
}

void remove(Component component) {
    components.remove(component);
}

In the functional approach, a mutable private state is replaced by an immutable public value. I'm stressing on public here to underline the difference. In reality, these values are just passed from the outside, thus aren't "owned" by the receiver at all. The same functions in Haskell:

add :: (Eq a) => a -> [a] -> [a]
add x xs = if x `elem` xs then xs else xs ++ [x]

remove :: (Eq a) => a -> [a] -> [a]
remove x xs = [y | y <- xs, y /= x]

The pattern here is the function $\rarr NewState$ , i.e. we're accepting some "state" and returning a new one without modifying the received argument. The first reaction of the OOP brain is usually "Wow, this might be cumbersome to use", however:

let a = Leaf "Hello"
    b = Leaf "World"
    c = Composite $ add b $ add a []

Looks approximately as readable as the object-oriented analog.

Abstraction

The next conversion is quite obvious, but nevertheless required to be mentioned in order to cover the topic in its entirety. All (or almost all, being too lazy to verify this statement) GoF patterns use interfaces to provide useful abstractions for outside users. In OOP, an interface is a group of method signatures for the single receiver. The same idea in functional languages is represented by type classes. The expected and obvious difference being methods replaced by functions. Let's take The Chain of Responsibility as an example. Its handler can be roughly represented in Haskell as follows:

class Handler h where
  type Request h
  type Response h
  canHandle :: h -> Request h -> Bool
  handle :: h -> Request h -> Response h

Note that receiver is now passed as a first argument to the handle and canHandle functions. In fact, similar convention is as well used in some languages featuring object-oriented paradigm (e.g. Python). So, it should be quite familiar. Next, let's define the chain itself:

chain :: (Handler h) => [h] -> Request h -> Response h
chain hs r = handle h r
  where
    h = fromJust $ find (`canHandle` r) hs

You can again spot an immutable sequence of handlers as an argument instead of a mutable private collection in an object-oriented version.

To utilize our chain, we would need to create an instance of some handler. Keeping things simple, I'll use the one that works on plain integers:

newtype IntHandler = IntHandler Int

instance Handler IntHandler where
  type Request IntHandler = Int
  type Response IntHandler = String
  canHandle (IntHandler i) r = i == r
  handle (IntHandler i) _ = "Hello " ++ show i ++ "!"

Finally, the client-side of the pattern:

chain [IntHandler 0, IntHandler 1] 0

We're passing multiple handlers and then the actual value as a request.

While this looks familiar for an object-oriented brain, functional brains tend to study and adopt much more abstract type classes, commonly borrowed from mathematics. Different sources even separate this kind of abstractions into the so-called categorical programming. In our specific example, we could re-write the whole code above into a single line, using Foldable, Alternative and Applicative classes:

chain fs x = asum $ fs <*> pure x

Neat, but quite crazy. In case you're not familiar with those three type classes, I'll leave you a homework to understand this ~~functional~~ categorical Chain of Responsibility totaling to thirty-three(!) characters in length.

The Ultimate Conversion

By this moment, we've covered all the techniques I had in my pocket. However, I want to quickly revise all of them with a single(!) pattern. The ultimate one. The one so popular that its use cases can easily cover the whole topic of our discussion... Tried guessing? Yes (or no, depending on your guess), it's The Singleton.

The most popular use case of it is to create a single instance of some interface. Let's say we have Named interface:

class Named n where
  name :: n -> String

And then we create the unique noble counting duck, which has the unique noble name:

data CountingDuck = CountingDuck

instance Named CountingDuck where
  name _ = "Archibald The Counting Duck"

A similar object-oriented use case of a Singleton is to inherit some open abstract class. Continuing with our example, Archibald can serve as a child to an abstract duck with a template for quaking behavior:

quack :: Named n => n -> String
quack duck = name duck ++ " quacking!"

A bit different usage of a Singleton is to serve as a marker in the sealed hierarchy:

data Duck = Duck String | CountingDuck

quack :: Duck -> String
quack (Duck name) = name ++ "quacking!"
quack CountingDuck = "Noble quacking!"

Same as in open hierarchy, Singleton CountingDuck always quacks the same way.

An interesting observation here, is an isomorphism between methods and pattern matching branches. In OOP, related functionalities are grouped with a single type, while in FP related types are grouped with a single function. In other words, FP is behavior-centric (i.e. to add a new behavior you need to change a single place and adding behaviors preserves backward-compatibility), while OOP is type-centric (i.e. to add a new type to a hierarchy you need to change a single place and adding new types to a hierarchy preserves backward-compatibility).

object DomesticDuck : Duck {
    fun name() ...
    fun quack() ...
}

object CountingDuck : Duck {
    fun name() ...
    fun quack() ...
}

Becomes:

data Duck = DomesticDuck | CountingDuck

name DomesticDuck = ...
name CountingDuck = ...

quack DomesticDuck = ...
quack CountingDuck = ...

This is the same controversy between a method and a function we saw several times already, but from a slightly different angle.

Lastly, I need to cover the use case, due to which in some circles Singleton is considered an anti-pattern. The global mutable state:

object CountingDuck {
    private var counter = 1

    fun count() {
        counter++
    }
}
// ... later on ...
CountingDuck.count()

The direct conversion in Haskell, as expected, completely removes the notion of state:

module CountingDuck (count) where

count :: Int -> Int
count = succ

-- ... later on in another module ...
import CountingDuck (count)

CountingDuck.count 1

After this, the anti part of the pattern is automatically annihilated. Although, in this example, using the associated function looks pointless, namespacing might improve readability in a scenario of using a Singleton for storing some global values:

object ServerSettings {
    val port = 8080
}
// ... later on ...
ServerSettings.port

Since this is not really an object-oriented use case, in Haskell it looks almost the same way:

module ServerSettings (port) where

port = 8080

-- ... later on in another module ...
import ServerSettings (port)

ServerSettings.port

The most notable difference being missing val qualifier: indeed, you don't need one, when vals are all you have.

Summary

As a conclusion, here is the proposed mapping from OOP to FP:

Sealed Inheritance  ==>  Sum Type
-------------------------------------------------
Open Inheritance    ==>  Currying
-------------------------------------------------
Aggregation         ==>  Currying
-------------------------------------------------
Interface           ==>  Type Class
-------------------------------------------------
a.method()          ==>  function(a)
-------------------------------------------------
state.change()      ==>  change :: State -> State

If you think that there are some uncovered object-oriented features, I would be glad to see them in the comments for the discussion.

Hoping that the article was somewhat entertaining and maybe even useful. Wish to meet you again in the future ones!

Expanding Horizons

Vsevolod — Wed, 27 Sep 2023 14:40:11 +0000

As stated at the end of the previous chapter, today we're going to abstract out the notion of an "absent value" even more. I'll use a bit of math with a mix of programming languages, mostly JVM-based as usual.

As a first step of generalizing null value, let's try to answer a simple question: is null really different to NullPointerException?

Firstly, let's introduce two singleton sets: $N u ll$ (set of $n u ll$ value) and $N u llP o in t er E x ce pt i o n$ (set of $n u llP o in t er E x ce pt i o n$ object instance):

\begin{aligned} & Null = \lbrace null \rbrace \cr & NullPointerException = \lbrace nullPointerException \rbrace \end{aligned}

Next, let's create two functions:

\begin{aligned} & nullable: \lbrace * \rbrace \rightarrow U \cup Null \cr & npeable: \lbrace * \rbrace \rightarrow U \cup NullPointerException \end{aligned}

Re-written in Java:

<T> T nullable()
<T> T npeable() throws NullPointerException

While as far as Java is concerned these functions are not equal, from the mathematical standpoint we can state that the results of their computations form a bijection, which in turn means that the two sets under question are equivalent. In other words, they can be expressed in terms of each other without losing any information.

$\rightarrow nullable$ :

<T> T nullable() {
    try {
        return npeable();
    } catch (NullPointerException e) {
        return null;
    }
}

$\rightarrow npeable$ :

<T> T npeable() throws NullPointerException {
    var result = nullable();
    if (result == null) {
        throw new NullPointerException();
    }
    return result;
}

Now, since we proved that:

\equiv NullPointerException

And by definition:

\subset Exception

Then, each value in the $N u ll$ set corresponds to a value in the $E x ce pt i o n$ set:

\exist e \in Exception : null \equiv e

Which means, that we can consider null pointer as an exceptional return type. And this is completely rational! It is basically an error that says "Value not found". So, the difference between null and NPE is just a matter of programming style, application performance, and other non-mathematical things. From the pure logical view, these can be seen as equivalent things.

At this point, we generalized null. Subsequently, we can generalize Maybe. We will need one more utility function, though:

\cup Null \rightarrow U \cup NullPointerException

Which is definitely possible, since we can map $U$ to itself and we already know how to map $N u ll$ to $N u llP o in t er E x ce pt i o n$ . Now we can state that "for each value in a nullable set, there will be a corresponding value in an exceptional set":

\forall a \in (U \cup Null), npe(a) \in (U \cup Exception)

And is there a monad that represents exceptional context?.. Yes, there is. Different languages have different naming for it. But I prefer to use Result<T,E>. Which either (pun intended) returns value T or error E. So, today we'll take a mental leap from Maybe to Result, from null pointer to any error.

The Bottom Part

Before getting into our target compiler-controlled safe territory, let's discuss the unsafe one. As the program executes, numerous different unexpected errors can happen. In order not to pollute our codebase, we generally do not try to cover all of those. Moreover, it's assumed that all return types always include those errors in themselves. This assumed value is named bottom and denoted as $⊥\bot$ . It may sound now that bottom is a non-functional, evil thing. But it has its value.

To understand that, we can group errors by their importance in the specific scope. Simply speaking, some errors are important locally (i.e. at the caller site) and some globally (i.e. on the application/library level). For example, FileNotExists could be important locally: we know which file we tried to open, and we might know what to do if it doesn't exist. On the other hand we could always expect the file to be present, in that case the same exception becomes a global one. The best thing we could do is just re-throw it up the call stack. Without $⊥\bot$ approach, we would have to add this meaningless exception to function signatures throughout our application, up to the main one. Code pollution without any value. Another example could be OutOfMemory error. Can you come up with a scenario when it's important locally? It would be some non-standard use case to say the least. Almost always, we assume that the caller can't handle it. In which case, why adding it to the signature at all? Moreover, exceptions of such kind theoretically can happen in any possible function. Does it mean that to be strict, we should annotate each function with it? Obviously not. Unchecked exceptions are useful for a clean separation of a happy path.

As a proof that this statement holds, we could take languages keen about checked errors, like Rust. Instead of wrapping checked exceptions in unchecked ones, rustaceans tend to annotate all possible errors and explicitly propagate them up to the entry point. However, even there tools to make this propagation as unnoticeable as possible are in high demand: language itself has an operator ? specifically to propagate error higher. Moreover, for applications those global errors are generally coerced to the umbrella Error type (analog of Java's Exception). Libraries that help to do this cleanly (for example, anyhow) are extremely popular. As a result, we have a codebase with, essentially, a cleaner version of throws Exception all over the place.

Returning to our muttons, NullPointerException makes no sense on the global level. The best thing an application can do globally is to show some generic error message to the user. On the other hand, we clearly know what and where we received locally. Thus, we are always sure, which pointer was missing and how to meaningfully handle it. That is the root reason why Optional is found to be so useful.

To be fair, I would mention that there is one specific error, that falls out of our handling approaches above, but, nevertheless, is a part of the bottom type. The infinite execution one. It differs drastically from the other ones, due to the fact that most of the time nor the compiler, nor the runtime signals about it. Developers can add some timeouts to handle it gracefully, but this is a completely different approach to error handling. Which is why it is out of our scope today.

Java's type system is not really a sophisticated one, so it doesn't arm us with the bottom type. However, there are two popular JVM languages that include it. Guess which ones? Instead of answering, I'll just leave two examples below.

@tailrec
def runsForever(): Nothing = runsForever()

fun alwaysThrows(): Nothing = throw RuntimeException()

Results in Jeneral

As already mentioned, foo() -> Result<String, Error> is isomorphic (mathematically equal) to String foo() throws Exception. Moreover, we can easily model the library APIs with both of them, enumerating all possible domain-specific errors. Why is then Results are beloved (in some circles at least) and checked exceptions hated (in most circles at least)?

The more popular and obvious part of the answer lies on the surface. As usual with a lot of things in programming, it's about sugaring our code (and eyes). As a Monad, Result in different languages can produce clean declarative pipelines, while checked exceptions in Java require imperative handling with catch blocks.

The bigger problem lies in the space of generics. Checked exceptions just aren't part of the generic system. Your T type is different to T throws CharacterCodingException and they both are different to T throws AccessDeniedException. The parent one to the last two is T throws IOException, which still can't be used where generic T is expected. As a quite radical answer to that, Java 8 lambdas doesn't allow checked exceptions as a return type. This in turn led to the fact, that nowadays most of the time checked exceptions are considered a bad practice in Java world. Compare that to Result, which is a lawful type system citizen. Thus, can be used as a generic return type wherever needed.

In Java, there is no built-in Result, but there is the mighty Try in the mighty Vavr library. It covers both problems discussed above. And is good enough for most application scenarios (i.e. scenarios similar to Rust anyhow::Result, scenarios where you just pass error up the stack). If, on the other hand, you are developing a library you can utilize Vavr's Either, which is good for modelling custom checked exceptions. The obvious problem with Either approach in external library lies in the fact, that your users will be forced to use Vavr, while they might prefer to use something else (those silly users, you know better what is good for them, right?).

In Scala, both Either and Try are built-in. Ten points to Gryffindor, as usual!

The Controversy

To be completely fair, I have to touch one debatable point between throws Exception and Result. The point with no clear winner. It is the fact that uncaught exceptions terminate the program, and unhandled results just lazily wait for someone to pick them up. This sounds like an easy win for the exceptions' party, since happy ignorance is never a good option. We should always be somehow notified about all unexpected errors, even if it means failing the entire execution. However, let's consider the same property for the scenario when we're processing sequences of data and require collecting all the outputs, be it values or errors. The lazy result is the only way to achieve this. The failing fast exceptions just never want to wait for us to finish, they blow up that stack. Therefore, even imperative languages are forced to collect some kind of union between values and processing errors. For example, you might have seen something like this:

var inputs, outputs, errors;
for (var input : inputs) {
  try {
    outputs.add(
      process(input)
    );
  } catch (Exception e) {
    errors.add(e);
  }
}

Here process might throw an exception, but we don't want to fail fast, we want to process every item in the list before deciding what to do next. Even though such code doesn't use some kind of explicit result structure, semantically it creates the same unions split in two separate lists (i.e. all successes to outputs and all failures to errors). By showing this example, I'm underlining that fail-fast nature is not a 100% win. Thus, the controversy.

The Union Way

To be consistent across chapters, I would try to model Result as a proper mathematical union. Firstly, this will help us with backward compatibility described in chapter one. Secondly, it is just interesting for me to see how it will work out.

Here is Try-like implementation:

extension[A: Typeable] (m: A | Throwable)
 def map[B](f: A => B): B | Throwable = m match
   case e: Throwable => e
   case a: A => f(a)

 def flatMap[B](f: (=> A) => B | Throwable): B | Throwable = m match
   case e: Throwable => e
   case a: A => f(a)

 def withFilter(f: A => Boolean): A | Throwable = m match
   case e: Throwable => e
   case a: A => if f(a) then a else Exception("Value filtered")

We can update our example functions from chapter two to return exceptions instead of nulls:

def fetchEntityFromDb(id: String): Entity | EntityNotFoundException
def populateMeta(entity: Entity): EntityWithMeta | AccessDeniedException

After that, our old for-comprehension will work. The first problem arises when we add our Maybe union to the equation:

|An extension method was tried, but could not be fully constructed:
|
|    flatMap(fetchEntityFromDb(id))    failed with
|
|        Ambiguous overload. The overloaded alternatives of method flatMap with types
|         [A](m: A | Throwable)[B](f: (=> A) => B | Throwable)(implicit evidence$2: scala.reflect.Typeable[A]): B | Throwable
|         [A](m: A | Null)[B](f: (=> A) => B | Null): B | Null
|        both match arguments (Entity | Null)(<?> => <?>)

Obviously, we need single extension for flatMap and family:

extension[A: Typeable] (m: A | Throwable | Null)
  def map[B](f: A => B): B | Throwable | Null = m match
    case null => null
    case e: Throwable => e
    case a: A => f(a)

  def flatMap[B](f: A => B | Throwable | Null): B | Throwable | Null = m match
    case null => null
    case e: Throwable => e
    case a: A => f(a)

  def withFilter(f: A => Boolean): A | Throwable | Null = m match
    case null => null
    case e: Throwable => e
    case a: A => if f(a) then a else null

Now, for-comprehension works for both Maybe and Try scenarios. For example, it could be:

def fetchEntityFromDb(id: String): Entity | Null
def populateMeta(entity: Entity): EntityWithMeta | AccessDeniedException

The harder problem for me was to simulate Either case instead of a Try. I mean, the case when we want enumeration of possible known errors, instead of a generic Throwable. Intuitively, I tried something like this:

extension[A: Typeable, E <: Throwable : Typeable] (m: A | E)
 def map[B](f: A => B): B | E = m match
   case e: E => e
   case a: A => f(a)

 def flatMap[B](f: A => (B | E)): B | E = m match
   case e: E => e
   case a: A => f(a)

We have generic sides of a union and the right side bounded by Throwable. The idea is that the right side could take any specific error (or enumeration of ones).

The first thing to note is that by generifying error type, we automatically lost withFilter method. And that's expected. There can be no mempty/mzero for Either, since we, as library developers, can't know the type user expects beforehand (i.e. we can't supply a default value). To get a more thorough explanation of the matter, search for Either and MonadPlus relations.

The other problem was less expected for me. Let's say we have a custom exception hierarchy:

sealed class CustomException(message: String) extends Exception(message)

case class EntityNotFoundException(id: String) extends CustomException(id)

case class AccessDeniedException(resource: String) extends CustomException(resource)

And, again, the same functions which return those exceptions:

def fetchEntityFromDb(id: String): Entity | EntityNotFoundException =
  Entity(id)

def populateMeta(entity: Entity): EntityWithMeta | AccessDeniedException =
 EntityWithMeta(entity.id)

def toDto(entity: EntityWithMeta): Dto = Dto(entity.id)

Then our for-comprehension (without if this time):

def fetchDto(id: String) = for {
  entity <- fetchEntityFromDb(id)
  entityWithMeta <- populateMeta(entity)
  dto <- toDto(entityWithMeta)
} yield dto

Yields the following compiler error:

|  entityWithMeta <- populateMeta(entity)
|                                 ^^^^^^
|                                 Found:    (entity : Entity | EntityNotFoundException)
|                                 Required: Entity

It seems, that compiler unpacks the whole union as our A (aka, Left) and passes it further down the chain. Instead, we wanted it to substitute Entity for A and EntityNotFoundException for E. I've spent some time trying to fix it to no avail. Although, I admit that my Scala knowledge is quite superficial. So, I would like to hear propositions/solutions to this error in comments below.

All in all, I would state that my attempt at unionizing types felt quite unsatisfactory.

Refining Further

The classical non-union Results have their cost. Foremost, it's a mental price of monadic code usage. Haskellers would argue here, but nevertheless this is a cost for common imperative Java developers. And even for functional guys out there, the application runtime pays the price of wrapping the values for both happy and faulty scenarios. Can we do better?

Unchecked exceptions is the efficient answer in a lot of languages. For use cases, where in most attempts a function will not fail, we're optimizing happy path with exceptions. Which sounds reasonable. Also, as discussed previously, exceptions fail fast and force us to fix the root cause. Let's take a simple head function as an example:

head :: [a] -> a
head [] = error "Empty list"
head (x:_) = x

In Scala, the same implementation with a slightly better tooling support is achieved through PartialFunction:

def head[A]: PartialFunction[Seq[A], A] = {
  case xs if xs.nonEmpty => xs(0)
}

I'm saying "slightly better", because for happy path it could be called as usual function head(List("John")), but for error handling it has several utility methods, like head.applyOrElse(List(), _ => "default"), which is arguably better than try/catch. Also, PartialFunction could be considered a specific variant of a Result, it even provides a method lift to prove their affinity.

In Java, the above example conventionally would look like this:

<T> T head(@NotEmpty List<T> xs) {
  return xs.get(0);
}

Note the NotEmpty part, which adds expressiveness to our errors. We'll return to it shortly.

All these examples add a contract to a function. The thing is that instead of making developers remember to abide to this contract, it can be checked by a compiler. There are different examples of compilers that can do that. But I will give you a taste of a specific one, GHC plugin called LiquidHaskell:

{-@ head :: { v:[a] | len v > 0 } -> a @-}
head (x:_) = x

The predicate len v > 0 is checked at a compile time. Thus, we're forced to either prove that our argument adheres to contract or propagate this contract up the call hierarchy. The predicate refines our type, thus this tool is called refinement types. Please, check out more examples out in the wild.

This propagation is an extremely powerful property. Imagine a common use case of an HTTP endpoint accepting JSON value with some array, for which we set a rule to be non-empty:

data class Input(
    @NotEmpty val names: List<String>,
)

With this reflection-based approach, we lose our knowledge about the real type of names right after successful deserialization. However, usually this contract is actually needed somewhere inside the layers of a service. For example, in a database access layer. Let's imagine that Kotlin compiler adds refinement types someday:

data class Input(
    val names: List<String> { it.isNotEmpty() },
)

The notion that we received a non-empty list will be engraved by the compiler as far down the call stack as it is required. The necessary pre-condition for this to work, is that JSON marshaller does respect the type system. But if it's a standard language feature, chances for tools' support are several degrees higher. Yes-yes, I'm looking at you right now, refined!

I have touched refinement types, because they are actually part of our "absent values" puzzle. Results are about post-processing, while type refinement is about pre-processing, which can lead to a cleaner and more strongly constrained code. Despite all those benefits, type refinement has its limitations. One being lesser adoption, which is fixable in the long-run. Another one is a conceptual limitation of purity. Obviously, we can't execute IO during compilation. E.g. can you imagine getting a database record from a production environment during compilation on your local machine?.. We need our beloved Maybe for that one for sure.

This was planned as the last part of the series. The chapter became bigger than the previous ones, but that is kind of expected from the one named "expanding horizons", right? All in all, we've covered a broad ground of error handling approaches from the bottom up the compilation ladder. And if you read up to this point, it means that the reading was probably somewhat interesting and hopefully somewhat useful for you (or you're just my friend or relative, who is trying not to offend me). Anyway, thanks for reading, hoping we'll meet again!

Maybe Strikes Back

Vsevolod — Sat, 01 Jul 2023 13:29:05 +0000

In the end of the previous chapter, we've stated that Kotlin's Any? is a proper union type. Also, multiple handy operators and functions to work with Any? exist as part of the standard library. So, based on these two statements, Kotlin's null handling has been inferred to be "the best". Today I'm going to review its weaker points. Again, we'll be looking at Haskell and its Maybe type for inspiration. A lot of language designers do this anyway, why can't we?

Universal Interface

With a risk of sounding like a broken record, I would state that the main power of Maybe comes from the universal Monad type class. Maybe itself may not be the best answer to nullability question, but its interface answers to dozens of other questions at the same time. This leads to a unified usage and thus to more readable and re-usable code. And it's completely reasonable from the OOP developer point of view. We all have heard the popular mantra of "code to interface". And here Haskell does exactly that.

The key function of monad, bind, has signature m a -> (a -> m b) -> m b. Rewriting this using Java-like types may look clearer: Monad<A> -> Function<A, Monad> -> Monad. Or even more Javishly: Monad bind(Monad<A> m, Function<A, Monad> m). Does this look familiar? It should. It's a quite popular method among Java codebases, commonly known as flatMap. But where is the problem with such a popular method?

Let's see 3 core examples of it:

Optional<A>.flatMap(Function<A, Optional<B>>) -> Optional<B>

Stream<A>.flatMap(Function<A, Stream<B>>) -> Stream<B>

CompletableFuture<A>.thenCompose(Function<A, CompletableFuture<B>>) -> CompletableFuture<B>

I'm cleaning up some type noise for brevity here
A lot more examples exist in the wild, but to showcase the idea these are enough
CompletableFuture is my favorite: to make matters worse, it doesn't even try to conform to usual naming

Kinds of Types

My OOP training screams to abstract a common parent out of the same type signatures. To achieve this, we need an interface looking like the following one:

interface Monad<A> {
    Monad<B> flatMap(Function<A, Monad<B>> f);
}

The problem here is that it's not generic enough. It will return us Monads where we would want Optionals and Streams. For example, expression optional.flatMap(...) will have parent's type of Monad not child's Optional. So, after such flatMap we wouldn't be able to chain Optional-specific methods anymore (without unholy casts, obviously).

If we go back to Haskell:

class Monad m where
  (>>=) :: m a -> (a -> m b) -> m b

We'll spot that Haskell declares container itself as a generic type parameter (note the m in m a). Can Java do the same? I wasn't able to achieve it. If you succeed, you can destroy the reasoning of this article. Please go ahead.

No point in showing all the different type signature combinations I've tried. They either do not compile, or (as with initial "naive" Monad<A>) do not return child type. The prettiest example, just to illustrate my thought-flow:

interface Monad<A, C extends Monad<A, C>>

Can be extended by:

sealed interface Maybe<A> extends Monad<A, Maybe<A>> permits Just, Nothing

Which narrows our Monad parent type to proper Maybe child type and compiles using Java 17. The problem arises when we want to return Maybe from Maybe<A> method. Our Monad.flatMap could look like the following (note that we're using the same trick of D extends Monad we used successfully on class level):

<B, D extends Monad<B, D>> D flatMap(Function<A, D> f)

And, consequently, Maybe.flatMap:

<B> Maybe<B> flatMap(Function<A, Maybe<B>> f)

Which doesn't compile with: flatMap(Function<A, Maybe>)' in 'Maybe' clashes with 'flatMap(Function<A, D>)' in 'Monad';. Even though Maybe extends Monad<B, Maybe, the compiler doesn't substitute D with it, as it did with C on class level previously.

Generally speaking, it's a known limitation of the Java compiler (as well as Kotlin's). To get more information on the matter, search for higher-kinded types. There are multiple Java libraries trying to add HKT, but at the moment of writing all of them introduce themselves as "not production-ready" ones. Also, it sounds like HKT should be part of a language itself to be efficient enough. So, unfortunately for now we are stuck with "code to implementation" in Java-world.

Imperative Paradigm

In Haskell, the universal monadic interface allows us to write both declarative and (surprisingly for a purely functional language) imperative code. Let's look at a simple example. Two ways of fetching some entity from some database, populating some metadata from some external API, and then mapping the result to a DTO.

Declarative:

fetchDto id = fetchEntityFromDB id >>= populateMeta <&> toDto

Imperative:

fetchDto id = do
  entity <- fetchEntityFromDB id
  entityWithMeta <- populateMeta entity
  let dto = toDto entityWithMeta
  return dto

Which code looks more familiar and thus more readable for Java developers without no functional background (i.e. for an average coder prior to Java 8)? If you are not familiar with Haskell, take your time to comprehend and compare both examples, they are really simple.

So?.. Right you are. The first one! At least, that is what we've got in Java 8. Am I hearing some weak voices for the second approach? Fear no more, you're not alone in this. There are examples of imperative handling of Monads on the JVM. Not in Java itself, but Kotlin's suspend/await lets you write monadic code imperatively, exactly like do in Haskell (to be fair, similarly to lots of other async/await implementations). Yes, we are stepping out of our cozy Maybe-only shell to a wider land of different Monads here. But we'll return, promise.

Java 8:

CompletableFuture<Dto> fetchDto(String id) {
  return fetchEntityFromDb(id)
      .thenCompose(this::populateMeta)
      .thenApply(this::toDto);
}

Kotlin:

suspend fun fetchDto(id: String): Dto {
    val entity = fetchEntityFromDb(id)
    val entityWithMeta = populateMeta(entity)
    val dto = toDto(entityWithMeta)
    return dto
}

In Kotlin, we can shorten this function to a single line by using extension methods. That's not the point. The point is that we have a choice between imperative and declarative paradigms for asynchronous logic.

That's cool, but let's say that we want to add support for some other monadic type. For example, our beloved T?. How much code would we need to change in Kotlin?

fun fetchDto(id: String): Dto? {
    val entity = fetchEntityFromDb(id)
    val entityWithMeta = entity?.let { populateMeta(it) }
    val dto = entityWithMeta?.let { toDto(it) }
    return dto
}

Huh, not DRY at all! How many lines we would need to change in Haskell?.. Zero, since we aren't using anything implementation-specific. Coding to an interface, remember that one?

The Union Way

As we already know, another mathematically correct nullable type resides in Scala. Does it adhere to the monadic interface? Can we implement one?

Scala lacks an explicit trait for Monad, however has an implicit interface that is used by for-comprehensions, which in turn are extremely similar to Haskell's do blocks we've already seen. Here is one possible implementation for unionized Maybe type:

extension[A] (m: A | Null)
  def map[B](f: A => B): B | Null = m match
    case null => null
    case _ => f(m.nn)

  def flatMap[B](f: (=> A) => B | Null): B | Null = m match
    case null => null
    case _ => f(m.nn)

  def withFilter(f: A => Boolean): A | Null = m match
    case null => null
    case _ => if f(m.nn) then m.nn else null

Next is our good ol' sample function:

def fetchDto(id: String) = for {
  entity <- fetchEntityFromDb(id)
  entityWithMeta <- populateMeta(entity)
  dto <- toDto(entityWithMeta)
} yield dto

And guess what? We can change our Maybe Monad to any other type implementing the same contract and this code will not change.

Let's re-check backward compatibility rules from the previous chapter. In this example, we can narrow down the return type in the signature of the populateMeta from Entity -> EntityWithMeta | Null to Entity -> EntityWithMeta. And as expected, client code is not broken. The same function compiles and works correctly!

This actually leads us to the interesting side effect. We now can work with non-nullable types using monadic pipelines:

val i: Int = 5
val j: Int | Null = i.map(_ - 3)

The one major drawback of our A | Null type I see is that if we want to make it actually useful, we need to re-invent the wheel (i.e. re-implement all the functionality, like zip and orElse, from the Option type). Can you spot any other problems?

All in all, by this moment we've covered quite an interesting evolutionary path from Java 7 to Scala 3 union types. From a theoretical standpoint, the latter now seem superior to the available alternatives (which doesn't mean that it's ideal, does it?). In the next chapter (if it ever gets published), I'm planning to abstract out the notion of an "absent value" even more. Null is too specific. "Code to interface", still remember that one?

Optionality in Java 8 and beyond

Vsevolod — Wed, 17 May 2023 14:45:41 +0000

This is a theoretical look at optionality of values. We'll discuss different approaches to handling "the billion-dollar mistake". I'll be using extremely simple (mostly) JVM examples. Thus, to better feel my pain, at least basic Java knowledge is recommended.

Note that I'm not pretending to be useful here. These are just my structured thoughts on the matter. However, I would be happy if someone finds them valuable or at least entertaining. Without further ado, let's start!

Java before 8

In Java 7 and below, all objects are nullable:

\textcolor{red}{\lbrace null \rbrace \cup} U

By $U$ here, I mean Universal set of all possible objects in Java.

As a more specific example, let's take Integer type:

\begin{aligned} & int = \lbrace~ x~ |~ -2^{31} \le x \le 2^{31}-1 ~\rbrace \cr & Integer = \lbrace null \rbrace \cup int \end{aligned}

Due to this, compiler doesn't help us with possible null instead of a value. For example (and yes, here a primitive int could be used, but I want to keep the code as simple as possible):

Integer square(Integer i) {
    return i * i;
}

Later in the code, someone mistakenly calls this function with null value:

square(null);

Boom! A runtime exception for our clients: NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because "<parameter1>" is null. We've all seen this one.

Haskell

In theory, compiler can distinguish nullable values. At the time of Java 7 one example of such a compiler was GHC (The Glasgow Haskell Compiler). In Haskell, types aren't nullable by default. And for possibly absent values, a special Maybe type is declared:

data Maybe a = Nothing | Just a

In such a system, we have compiler guarantees that Nothing couldn't possibly be passed instead of a value, since those are two distinct types. Using Int as an example:

\begin{aligned} & Int = \lbrace ~x~ |~ -2^{29} \le x \le 2^{29}-1 ~\rbrace \cr & Nothing \notin Int \end{aligned}

The same square function as before:

square :: Int -> Int
square = (^ 2)

And later in the code we try to pass Nothing to it:

square Nothing

Our code doesn't compile: Couldn't match expected type ‘Int’ with actual type ‘Maybe a0’. Wow!

Java 8

Today, all devs in Java world know "the best way" to deal with nullable types. The new (eh, not really new in 2023) and shiny Optional class. Since we already know a Maybe type, we can see clear similarity between the two. Let's try using it in our simple example:

Optional<Integer> square(Optional<Integer> o) {
    return o.map(i -> i * i);
}

And then:

square(null);

Huh: NullPointerException: Cannot invoke "java.util.Optional.map(java.util.function.Function)" because "<parameter1>" is null.

The obvious problem here is that we want our Optional<Integer> to be:

\lbrace empty() \rbrace \cup int

But in reality it is:

\textcolor{red}{\lbrace null \rbrace \cup} \lbrace empty() \rbrace \cup int

Not good!

I'm not saying that Optional is bad. It's good. It's a good convention. By using optionals, library developers clearly communicate to library users where they can provide or receive no value. However, in statically typed languages, we generally want more. We want dat compiler guarantee (at least I do)!

Scala 2

When Java devs want something from Haskell, where do they go? Right. They check out Scala. So did I.

Scala Option is closer to Haskell Maybe, since it's an algebraic sum type. It is None | Some a in terms of Haskell. Thus, you can do pattern matching and other cool things with it. But...

def square(o: Option[Int]): Option[Int] = 
  o match {
    case Some(i) => Some(i * i)
    case None => None
  }

square(null) // java.lang.ExceptionInInitializerError: Caused by: scala.MatchError: null

Runtime exception due to the same problem:

\textcolor{red}{\lbrace null \rbrace \cup} \lbrace None \rbrace \cup Int

The Project Valhalla

Several years ago, when I checked Project Valhalla for the first time, the code worked like so:

inline class Point {
    private int x;
    private int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int x() { return x; }
    public int y() { return y; }

    public Point add(Point other) {
        return new Point(x + other.x, y + other.y);
    }
}

point.add(null); // error: compilation failed: 
                 // incompatible types: <null> cannot be converted to Point

Compiler guarantees were finally there!

However, in the newest version, even though the Point itself looks neater:

value record Point(int x, int y) {
    public Point add(Point other) {
        return new Point(x + other.x, y + other.y);
    }
}

We are back with our good ol' NPE:

point.add(null); // NullPointerException: Cannot read field "x" because "<parameter1>" is null

Frankly, I am not aware "why", probably reasoning for this is buried somewhere in Valhalla-related discussions. But the sad fact is that even with Valhalla in place, we're still left with no null-safety compiler guarantees.

The Problem with Maybe

For now, it looks like Haskell's Maybe is right as rain. But it has the following problem:

\textcolor{red}{\not\subset} Maybe~ Int

Maybe Int should form a ${Nothing}∪Int\lbrace Nothing \rbrace \cup Int$ set, but it doesn't. Due to this, theoretically compatible changes become incompatible in Haskell. Let's say we have such a (strange) square function:

square :: Int -> Maybe Int
square 0 = Nothing
square i = Just $ i ^ 2

At some point in time, we decide to return Int:

square :: Int -> Int
square = (^ 2)

Or accept Maybe Int:

square :: Maybe Int -> Maybe Int
square = fmap (^ 2)

Both cases are an ease of requirements, so theoretically should be backward compatible. But in Haskell they aren't. Compilation is broken for our clients.

The idea for this chapter was stolen from the Maybe Not talk by Rich Hickey.

The Union Way

Can something be better than Haskell? For our use case - "yes".

Returning to the JVM, we could find the type we were looking for. Kotlin's Int?:

\lbrace null \rbrace \cup Int

Firstly, non-nullable Int gives us compiler guarantees that it is actually $}\lbrace~ x~ |~ -2^{31} \le x \le 2^{31}-1 ~\rbrace$ :

fun square(i: Int): Int = i * i

square(null) // error: null can not be a value of a non-null type Int

Secondly, ease of requirements works without breaking our clients (they'll only get warnings from the compiler):

fun square(i: Int): Int? = when (i) {
    0 -> null
    else -> i * i
}

Guaranteeing to return value:

fun square(i: Int): Int = i * i

Or accepting nulls as well as values:

fun square(i: Int?): Int? = i?.let { it * it }

Doesn't break clients. For example, square(2)?.let { it + 1 } works for all three functions.

Scala 3

While I was thinking to publish or not to publish, Scala 3 was released (yes-yes, the first draft of this writing was written several years ago). Dotty has built-in support for union types and the opt-in flag -Yexplicit-nulls to enable null safety.

My previous example from Scala 2 now (in version 3.2.2) gives a compile-time error: Found: Null, Required: Option[Int].

Backward compatibility is in place as well:

square(3).nn + 1 // works for all examples below

def square(i: Int): Int | Null = i match
  case 0 => null
  case _ => i * i

def square(i: Int): Int = i * i

def square(i: Int | Null): Int | Null = i match
  case null => null
  case _ => i * i

Yep! Right what we wanted.

Although... Compare Kotlin code for Int? -> Int? function with the above Int | Null -> Int | Null definition in Scala. One-liner transformed into match/case expression. Scala lacks operators like ?. or ?:, which makes working with nullable types awkward. Also, since the feature is new and optional (pun intended), it's an order of magnitude less spread around Scala codebases. So, for now, I would give a point to Kotlin using a pen and to Scala using a pencil. That said, the future regarding proper null safety looks bright in Scala world.

Today, we've reviewed existing ways of handling nulls in different languages (mostly on the JVM). To sum up, let's assign points to each approach discussed:

No compiler guarantees at all (Java).
Compiler guarantees (Haskell).
Proper union type (Scala, Kotlin).
- Kotlin gets an extra 0.5 for a better standard null-handling utilities.

Am I promoting Kotlin here? Probably not. Encouraging Java developers to try it and make their own weighted decision? Definitely yes.

In the following article (if it ever gets published), I am planning to discuss the cons of Kotlin's implementation by leveraging such power means as abstraction and composition. Thanks for reading!