Sunday, January 20, 2019

Monad in imperative languages

TLDR: Monad is a design pattern to encapsulate a complicated sequence of actions. A monad M has two main attributes: a constructor to wrap a value of type T into a monadic value of type M<T>, and a function that takes a monadic function which transforms a value of type T into a monadic value of type M<U>, which is of the same monadic type M.

Introduction

Most articles about monads are illustrated with functional languages such as Haskell. Yet, most programmers are probably coming from imperative background. This mismatch creates an extra burden for the developers to learn the syntax and semantic of such functional languages to understand a simpler concept of a monad. This post is going to look at monad from an imperative/object oriented vantage.

What is a monad?

According to Wikipedia,

In functional programming, a monad is a design pattern that allows structuring programs generically while automating away bookkeeping code needed by the program logic.

The emphasis here is that a monad is a design pattern in the same Gang of Four sense. More specifically, a monad is a structural design pattern, the same category that adapter, composite, or decorator, for example, are in.

Why use a monad?

As with any design pattern, monad has a purpose.

With a monad, a programmer can turn a complicated sequence of functions into a succinct pipeline that abstracts away additional data management, control flow, or side-effects.

The main keyword in that sentence is sequence. Monad is most often used to chain a sequence of functions together. In other words, the main use of monad is in function composition.

This allows monads to simplify a wide range of problems, like handling potential undefined values (with the Maybe monad), or keeping values within a flexible, well-formed list (using the List monad)

Construction

Let us now dissect the components that make up a monad. As a whole, this is what Wikipedia says:

Given any well-defined, basic types T, and U, a monad consists of three parts:

  1. A type constructor M that builds up a monadic type M T

  2. A type converter, often called unit or return, that embeds an object x in the monad:

    unit(x) : T → M T
    
  3. A combinator, typically called bind (as in binding a variable) and represented with an infix operator >>=, that unwraps a monadic variable, then inserts it into a monadic function/expression, resulting in a new monadic value:

    (mx >>= f) : (M T, T → M U) → M U
    

Some of us might be scared away by the sheer number of jargons used in the above description. But read slowly, and we will find that they are pretty simple. A point by point translation is as followed.

  1. M is a generic type so that M<T> is also a type.

  2. M has a constructor that can take an argument of type T and return an object of type M<T>. This object is a monadic value. The signature of such a constructor could be:

    public static <T> M<T> unit(T value);
    

    Other common names are return, result, of.

  3. There is a method in type M that takes a function which takes a value of type T and returns a monadic value of type M<U>. This function is called monadic function. Below is one possible declaration:

    public <U> M<U> bind(java.util.function.Function<? super T, M<U>> f);
    

    Other common names are then, flatMap. It is important to note that the returned monadic value is of the same monadic type M. The parameter type U could be the same as T.

It can be seen that the constructor in the second bullet is also a monadic function. This repetitiveness allows us to sequence monadic functions.

                                    bind                      bind
T --monadic function-> M<T> --monadic function-> M<U> --monadic function-> M<Z>...

One more point to note here is the evaluation of f does not have to be immediate. In other words, bind may return a lazy monadic value that encapsulates both the current monadic value, and the passed-in monadic function for on-demand evaluation.

Example use case

This section looks at one example use of a very popular monad, the Maybe monad. We will start out with the problem statement and look at how it helps with code structure. We will be illustrating this example in Java.

Binary tree is a common data structure where one node has links to at most two children (named left and right), and at most one parent (named parent). Our example is a method that returns the sibling node to the current node, or null if the current node does not have any sibling.

/** Returns the sibling of this, or null if there is no sibling. */
public Node getSibling() {
  if (parent == null) {
    return null
  }
  return (this == parent.left) ? parent.right : parent.left;
}

With java.util.Optional, the above code could be written as followed.

/** Returns the sibling of this, or null if there is no sibling. */
public Node getSibling() {
  return Optional.ofNullable(parent)
      .flatMap(p -> Optional.ofNullable((this == p.left) ? p.right : p.left))
      .orElse(null);
}

Comparing the two versions, we can see that:

  1. The second version abstracts away the null check. The fact that parent, parent.left, and parent.right might be undefined is handled uniformly by Optional.
  2. The above behavior allows us to express the whole method as a sequence of actions: First go up to the parent, then go down to the appropriate branch.

If you have guessed that Optional is a monad, you are right! Optional is Java's equivalence of Haskell's Maybe. Line 3 shows the construction of an Optional object via its static factory method ofNullable. Line 4 demonstrates how one Optional is chained to another via the flatMap method.

And that is practically all there is to a monad.

Summary

The concept of monad is often illustrated and explained with a functional language and mathematical rigor. This post dissects the same concept in a more familiar imperative setting and simplified analysis.

At a high level, a monad is a structural design pattern that hides additional control flow, and state management from a complicated sequence of actions. At a low level, a monad is a generic type with 1) a constructor that wraps a plain value into a monadic value, and 2) a method that unwraps and feeds the plain value into a passed-in monadic function.

The real advantage of monads is that you can do use the do notation. That's all there is to it.

—Erik Meijer, from his FP101x class

Sunday, March 11, 2018

Pre-declaration of tasks

Recently, I've noted some old ideas being used at the core of more modern frameworks. One of them is the pre-declaration of all the tasks before they are executed. This is similar to entering the floor you want to reach before you enter an elevator. This allows for more optimizations.

For example, in TensorFlow, the computation graph is built and given to the framework. The framework then optimizes the graph, assigns the computing nodes, and starts the computation. Imagine your graph has constant * input1 + constant * input2 + ... + constant * inputn, it could be optimized into constant * (input1 + input2 + ... + inputn), a 50% reduction in computation! This optimization would not be possible if the framework wasn't given the whole expression to work with. Moreover, given a fuller picture, the framework could also more intelligently rearrange the inputs to be closer to each other, taking advantage of locality.

Another cute example is in Ray distributed framework. Ray cleverly uses Object ID (similar to Future) to abstract a result of a computation. When another computation depends on an Object ID, a dependency graph is built and known. Any suitable node can take on appropriate computing task as long as it can obtain required inputs.

This idea is exactly what a compiler is. After all, you tell the compiler about all the tasks that you are going to execute in a high level language, and it translate them into the most optimized native form it could.

I am fascinated by simple and commonsensical ideas like this one. It reinforces the core theme of a spiral evolution of technologies. Hope to see more of those smart elevators.

Sunday, November 8, 2015

Explaining Python Concepts: Iterable, Iterator, and Generator

A few days ago, some colleagues at work brought up a discussion about several closely-related concepts in Python: Iterable, Iterator, Generator. And I thought it might be a good blog post to explain them all, down to the words in the PEPs, and just not hand-waving over them.

Duck typing

Before we all go deep, let's quickly remember that Python is a dynamically typed language. Many people use the term duck typing to refer to Python's type system. Colloquially speaking, if it walks like a duck, quacks like a duck, it must be a duck. That is to say an object is considered a particular type if it behaves in accordance to the defined behavior of that type.

In other words, we are usually talking about interface rather than implementation in Python. The mentioned topics are in fact concepts, not any concrete implementation, as we shall see later.

Iterable

Iterable is the easiest one to explain. If an object has either __iter__ or __getitem__ method, it's an iterable.

The main purpose of an iterable object is it can be used in a for loop. Let's take a look at how for loop works.

>>> import dis
>>> def f():
...   for x in o:
...     pass
... 
>>> dis.dis(f)
  2           0 SETUP_LOOP              14 (to 17)
              3 LOAD_GLOBAL              0 (o)
              6 GET_ITER            
        >>    7 FOR_ITER                 6 (to 16)
             10 STORE_FAST               0 (x)

  3          13 JUMP_ABSOLUTE            7
        >>   16 POP_BLOCK           
        >>   17 LOAD_CONST               0 (None)
             20 RETURN_VALUE

As you can see, the for loop itself is converted into two main instructions: a GET_ITER followed by a FOR_ITER. The first instruction obtains an iterator from an iterable object. The next instruction grabs the next item from that iterator.

You can also tell that I have simplified things a little bit up there to not get into another term that we're getting to next

Iterator

An iterator object has a next method (or __next__ in Python 3). This method returns the next item in a stream, or raises StopIteration when there is no more item.

Now, if there is only next method, the iterator will not be usable in a for loop. In order for "code receiving an iterator can use a for-loop over the iterator", "iterators are currently required to support both protocols.". The other "protocol" referred in that direct quote is iterable concept. That is, iterators are required to have an __iter__ method returning itself. The two concepts, however, are distinct.

So, by now, I hope that it is clear that iterators are iterable, and iterable objects produce iterators.

To illustrate the point, let's consider this example:

>>> seq = [1, 2, 3, 4, 5]
>>> iter1 = seq.__iter__()
>>> for x in iter1:
...   print x
...   if x == 3: break
... 
1
2
3
>>> iter2 = seq.__iter__()
>>> for x in iter1:
...   print x
... 
4
5
>>> for x in iter2:
...   print x
... 
1
2
3
4
5

We have a seq sequence. This sequence is iterable because it has __iter__ method. We obtain the first iterator iter1. We then run a for loop over iter1, breaking out at value 3. The fact that we can run for loop over iter1 confirms that iter1 is iterable. But unlike seq, iterating over iter1 again continues from where it left off, not from the beginning. We also see that iter2 (which is created at the same time we restarts iteration over iter1) is totally different from iter1.

I hope the example makes sense. When iterating over a sequence, you would want to iterate over all its items. When iterating over an iterator, you want to iterate over the items left in that iterator, not items that have been consumed. Put it differently, the __iter__ method defines how the items are iterated over while the next method simply returns the next item in that order. Therefore, an iterator is almost always assumed to be used once only, and an iterable is often iterated over many times.

So we have seen the relationship between iterator and iterable, let's get to the last topic.

Generator

Quoting PEP 255: Python generator is a kind of Python iterator, but of an especially powerful kind.

Generator is more powerful because it has these other methods on top of next: send, throw, and close. Therefore, it should be clear that if an object does not accept any of these methods, it is not a generator. Conversely, an object that provides all of these methods can be treated as a generator.

Due to duck typing, it is wrong to use isinstance(x, types.GeneratorType) to check if x exhibits generator behavior. That type is only defined for object returned from a generator function or generator expression.

Speaking of generator function and generator expression, they should not be confused with generator. Generator function is any function that has the yield keyword somewhere in its body. Invoking this function does not run its body, but returns a generator object which PEP 255 calls generator-iterator. Calling next on the returned generator will execute the function body. Generator expression is similar in concept but with a more familiar list comprehension syntax.

The easiest way to exercise the advanced features of generators is to take advantage of yield from keyword introduced in PEP 380 -- Syntax for Delegating to a Subgenerator, and available since CPython 3.3.

>>> class MyGenerator(object):
...     def next(self):
...         return 42
...     __next__ = next
...     def send(self, *args):
...         print('Received', args)
...     def throw(self, *args):
...         pass
...     def close(self, *args):
...         pass
... 
>>> class MyIterable(object):
...     def __iter__(self):
...         return MyGenerator()
... 
>>> def test_my_generator():
...     yield from MyIterable()
... 
>>> def test_list():
...     yield from [1, 2, 3]
... 
>>> def test_genexp():
...     x = (i for i in (1, 2, 3))
...     yield from x
... 
>>> g = test_genexp()
>>> next(g)
1
>>> g.send('Yup, genexp is a generator.')
2
>>> 
>>> g = test_my_generator()
>>> next(g)
42
>>> g.send('Surprised! This is also a generator.')
Received ('Surprised! This is also a generator.',)
>>> 
>>> g = test_list()
>>> next(g)
1
>>> g.send('Oops, not a generator')
Traceback (most recent call last):
  File "", line 1, in 
  File "", line 2, in test_list
AttributeError: 'list_iterator' object has no attribute 'send'

The above code shows that the return value from a generator expression and generator function is, as expected, a proper generator. The code also shows that MyGenerator is indeed a generator because it fulfills the generator concept, it can be used as a subgenerator in a yield from statement. Lastly, it shows that a regular iterator is not a generator.

On a side note, the example makes it clear that iterable and iterator/generator are two distinct concepts. MyIterable does not produce next item, and MyGenerator is not iterable, but when combined they can be used in for loop.

Summary

To summarize it all up, iterable object produces iterators and therefore control how the items are iterated over. Iterator produces next item in a defined order and usually consumed once. For iterator to be used in a for loop (no pun intended), iterator is required to define an __iter__ method that returns itself. Generator is an enhanced iterator with additional semantics such as send, throw, and close.

Practically speaking, if an object can be fully iterated over with for loop more than once, it's an iterable. If an object has next (or __next__ in Python 3), it is an iterator. And if a value can be sent to an iterator, it is a generator.

Thursday, November 13, 2014

A short joke

Thought of this joke on the way home (based on another religiously-themed version from a colleague at work).

How can computer scientists help NASA find the next habitable planet? They do a star search.

Saturday, July 26, 2014

Quick and easy "software diversification"

The Economist published an article Divided we stand about the work that Full Professor Michael Franz did at University of California at Irvine to further secure software applications.

The gist of the technique is to compile the same source code into many variant binaries that perform the same function, but differ structurally, at the machine instruction level. For example: the sequence MOV EAX, EBX; XOR ECX, EDX can be rearranged into XOR ECX, EDX; MOV EAX, EBX, or made into MOV EAX, EBX; NOP; XOR ECX, EDX without affecting any functionality of the sequence. The team modified compilers (both LLVM clang and GCC) to automatically (and deterministically) introduce diversity (randomness) in the instruction scheduler. As such, exploit writers will have a harder time targeting all variants.

This immediately reminds me of a simply trick I used many years ago to achieve a similar effect: Randomizing the linking order of object files. Consider this, if you have object main.o, strcpy.o, and puts.o, you can create 6 (3 factorial) variants by linking them in different permutation orders:

  1. main strcpy puts
  2. main puts strcpy
  3. strcpy main puts
  4. strcpy puts main
  5. puts main strcpy
  6. puts strcpy main
$ gcc -o t1 f1.o main.o
$ gcc -o t2 main.o f1.o
$ nm t1
0000000100001040 S _NXArgc
0000000100001048 S _NXArgv
0000000100001058 S ___progname
0000000100000000 T __mh_execute_header
0000000100001050 S _environ
                 U _exit
0000000100000ec0 T _f1
0000000100000ed0 T _main
0000000100001000 s _pvars
                 U dyld_stub_binder
0000000100000e80 T start
$ nm t2
0000000100001040 S _NXArgc
0000000100001048 S _NXArgv
0000000100001058 S ___progname
0000000100000000 T __mh_execute_header
0000000100001050 S _environ
                 U _exit
0000000100000ef0 T _f1
0000000100000ec0 T _main
0000000100001000 s _pvars
                 U dyld_stub_binder
0000000100000e80 T start

In the first variant, f1 is at ~EC0 and main is at ~ED0. In the second variant, f1 is at ~EF0 and main is at ~EC0. There is a clear difference in the structure of the binaries but no functionality is affected.

This trick is performed at the final stage (linking) in the whole build process. Therefore, intermediate object files can be reused without recompilation. Furthermore, no source code is required for this "diversification" process to happen.

Clear tradeoffs are in the granularity of the diversification. In the context of Prof Franz's work, which is mainly in defense against ROP exploit, I'll happily ignore such granularity.

Oh, by the way, I did not use this trick to "secure" the application. It seems like a wrong tool for that purpose due to distribution and debugging problems it creates.

Friday, March 7, 2014

Functor optimization

I have this piece of code that can be compiled with -On (n > 0) but cannot be compiled with -O0.

#include <iostream>

class Functor1 {
public:
    void operator()() const {
        std::cout << "Functor 1" << "\n";
    }
};

class Functor2 {
public:
    void operator()() const {
        std::cout << "Functor 2" << this << "\n";
    }
};

template <typename FunctorType>
class TemplateWithStaticMember {
public:
    TemplateWithStaticMember() {
        functor_();
    }
private:
    static const FunctorType functor_;  // THIS LINE!!!
};

/* Incomplete fix:
template <typename FunctorType>
const FunctorType TemplateWithStaticMember<FunctorType>::functor_; */

int main(int argc, char* argv[]) {
    TemplateWithStaticMember<Functor1> f1;
    // TemplateWithStaticMember<Functor2> f2;
}

Under GCC 4.8, when compile with -O0, we get this error:

/tmp/ccFIY33S.o: In function `TemplateWithStaticMember::TemplateWithStaticMember()': main.cpp:(.text._ZN24TemplateWithStaticMemberI8Functor1EC2Ev[_ZN24TemplateWithStaticMemberI8Functor1EC5Ev]+0xd): undefined reference to `TemplateWithStaticMember::functor_' collect2: error: ld returned 1 exit status

At other optimization levels, the code can be compiled and executed just fine.

If we uncomment the second functor, the code always fails, regardless of optimization levels.

The reason is our template declares a static constant variable functor_ (at the line marked with THIS LINE!!!). At high level optimization, the compiler finds out that we only use the functor object to execute a function so the compiler inlines the function and optimizes away the functor object. Without optimization, the compiler requires a definition of functor_ and fails to find one.

When we use f2, its functor_'s operator() refers back to itself via this. That requires the functor object to actually be allocated. But because we have not defined any such functor object, the compiler will fail to compile our code.

I find this piece of code interesting because usually higher (not lower) optimizations make code fail. For example: Prof. John Regehr initially blogged about undefined behavior under optimizations, and STACK team at MIT published a paper about optimization-safe code.

Wednesday, December 11, 2013

BrowsePass as a Chrome app

I am pleased to announce the availability of BrowsePass Chrome app.

This is an easier way to set BrowsePass up on the Google Chrome browser (as well as its open source cousin Chromium). The Chrome app alleviates the most cumbersome steps in setting up BrowsePass: finding a web host for the source code. Everything else remains the same, including the convenience of opening your password database with a browser.

Though there is not yet extension/add-on/app for other browsers (such as Firefox, Safari, Opera), they can still run BrowsePass normally.

As usual, the source code (including the Chrome app) is at BitBucket.