David Sorokin firstname.lastname@example.org, Jan 2010
A monad can be defined with help of two functions, one of which is higher-order. Direct working with them is tedious and error-prone. In this article I’ll describe an approach that greatly simplifies the use of monads in Common Lisp. It is possible due to macros.
I suppose that the reader is familiar with Haskell’s definition of the Monad type class. To create a monad instance, we have to define the mentioned two functions. The first of them is called return. The second one is known as the bind function and it is denoted in Haskell as operator (>>=):
This definition actually allows the programmer to use common names return and (>>=) for very different functions. I’ll try to create similar Lisp macros that will be common for all monads. Also Haskell provides a useful do-notation which is a syntactic sugar for monads. The macros I will create will provide similar facilities as well.
Also I created a new project with name cl-monad-macros. It is available by the following link: http://common-lisp.net/project/cl-monad-macros. The corresponded package contains definitions of all monad macros described in this article.
The package and all examples were successfully tested on the following Lisp systems:
· Steel Bank Common Lisp (SBCL);
· Clozure CL (CCL);
· Allegro CL.
Let’s suppose that some monad is defined with help of two hypothetical functions UNITF and FUNCALLF:
The UNITF function is the return function. Function FUNCALLF is an analog of the idiomatic bind function but only the order of arguments is opposite. Further I call namely this new function a bind function. Please take care.
We could limit ourselves to using only these functions, but it would be tedious. Please take into account that the first argument of the bind function must be a function, most probably an anonymous function. Moreover, we can use a sequence of monad values in one computation, which complicates the matter significantly.
Therefore I offer to use the following macros:
(funcall! k m)
m >>= k
(progn! m1 m2 … mn)
m1 >> m2 >> … >> mn
(let! ((x1 e1)
do x1 <- e1
The UNIT macro is equivalent to a call of the return function. The FUNCALL! macro is expanded to a call of the bind function. Macro PROGN! is equivalent to the monadic then function, which is denoted in Haskell as (>>). It allows the programmer to create a sequence of computations. Internally, it is based on more primitive FUNCALL! macro.
(progn! m1 m2)
(progn! m1 m2 … mn)
(progn! m1 (progn! m2 … mn))
Here #:gen-var means an automatically generated unique variable name with help of GENSYM.
Macro LET! is somewhere an alternative to the arrow symbol from the do-notation of Haskell. It is also based on the FUNCALL! macro. It binds computations e1, e2, …, en with values x1, x2, …, xn, which can be then used in computation m.
(let! ((x e)) m)
(let! ((x1 e1)
(let! ((x1 e1))
Please note that the LET! macro accepts only two arguments, the last of which is the monad value. It was made intentionally for similarity with the LET and LET* operators in the following sense. If we want to propagate a sequence of computations then we have to apply the PROGN! macro in all cases:
(let! ((x e))
do x <- e
(let ((x a))
do let x = a
Thus, macros UNIT, FUNCALL!, PROGN! and LET! provide an unified common way of working with the monads. To distinguish different monads from each other, we can implement these macros as a MACROLET defined by global macro WITH-MONAD that has the following application form:
The first sub-parameter return-func defines a name of the return function. The second sub-parameter funcall-func defines a name of the bind function. This macro is expanded to a MACROLET saving the same body.
Here the GENERIC-LET! macro is used to process the LET! expression in accordance with the stated above definition.
The PROGN! expression is processed already by the GENERIC-PROGN! helper macro.
Then the following test expression
is expanded ultimately to
The expanded code is generic enough. Actually, macro WITH-MONAD satisfies some abstract contract providing definitions for macros UNIT, FUNCALL!, PROGN! and LET!. As we’ll see later, there are other specialized macros that are like WITH-MONAD and that satisfy the same contract but generate a more efficient code for their monads. Moreover, in case of the monad transformers new macros are necessary.
It’s important that macros like WITH-MONAD can be nested, which allows the programmer to work with different monads in the same s-expression. Each new application of the WITH-MONAD macro shadows the previous definition of macros UNIT, FUNCALL!, PROGN! and LET!. It means that at any moment only one monad can be active.
Although we can always use directly the WITH-MONAD macro, it is more convenient to create a short name for each monad in accordance with the following pattern:
where UNITF and FUNCALLF were used as an example.
In the rest of the article you’ll see a lot of definitions of the LET! and PROGN! macros. Actually, all them can be reduced to the following two macros that will work with any monad.
Nevertheless, there is one subtle optimization issue related to the order of arguments of the FUNCALL! macro. During the macro expansion of expression
macro UNIVERSAL-LET! will generate ultimately for the most of monads described in this article something like
But I’m not sure that any Lisp compiler is able to optimize it to the following equivalent code that would be more efficient
Please note that there would be no such problem if the FUNCALL! macro had another order of parameters, i.e. an idiomatic order as in Haskell. Then FUNCALL and LAMBDA would alternate with each other directly in the code and the compiler most probably could reduce them.
But I think that a similarity with the standard FUNCALL function is more important and I’m ready to provide optimized versions of the LET! and PROGN! macros whenever it makes sense.
The Identity monad is the simplest case. The return function is IDENTITY. The bind function is FUNCALL. Then UNIT macro becomes an acronym of the IDENTITY function, FUNCALL! becomes the ordinary FUNCALL, PROGRN! is equivalent to PROGN, but LET! is transformed to LET*. This coincidence in names can be considered as a rule of thumb. Only the LET! macro is a small exception.
But there is a much more efficient implementation:
Remembering about this monad, it is easy to memorize names FUNCALL!, PROGN! and LET!.
Our test expression
is expanded to
This section is devoted to the List monad. I’ll introduce macro WITH-LIST-MONAD that will implement a contract of the WITH-MONAD macro but that will do it in its own optimized way.
A monad value is just a list. Following the idiomatic definition, we can write the UNIT and FUNCALL! macro prototypes:
Please note that NIL is also a value of the list monad. We’ll use this fact further.
Here is a definition of the PROGN! macro prototype.
At each reduction step we introduce a loop that appends the second argument as many times as the length of the first list. If the first list is NIL then the result of the loop is NIL as well.
The LET! macro prototype can be implemented similarly and also without use of the lambda.
Here we replace each variable binding with the corresponded loop. It should generate an efficient enough code.
Macros UNIT, FUNCALL!, PROGN! and LET! actually are defined in a MACROLET implemented by the WITH-LIST-MONAD macro.
The same test example
is now expanded to
We can ask for something more practical:
Please note that here we use the fact that NIL is a legal value of the List monad. Therefore we can omit the else-part of the IF operator. Moreover, if numbers were an empty list then the topmost loop would immediately return NIL.
Also we can define the following function perms that produces a list of permutations of a given list.
Now we can test it.
The next monad is the Maybe monad. It allows efficiently stopping a complex sequence of computations right after discovering a failure. If there is no failure then a full chain of computations is performed.
The constructor, getters and predicates for this data type are defined below.
The prototypes of the basic return and bind macros can be defined in the following way.
The key point is the IF expression that cuts the further computation if the result of the former one is NIL.
Based on these macros we can build their counterpart PROGN!.
The LET! macro is similar but it allows the programmer to bind variables within one computation.
In the three cases we see the cutting IF expressions. They stop immediately the computation right after discovering a failure.
Actually, these last four macros are implemented as a MACROLET defined by macro WITH-MAYBE-MONAD. As always, we could implement the latter with help of generic macro WITH-MONAD providing the necessary return and bind functions which are trivial for this monad. But macro WITH-MAYBE-MONAD is much more efficient.
Our old example
is expanded to
Now we can consider something more illustrative
Moreover, SBCL will warn about an unreachable code during compilation if we’ll try to define such a function!
The Reader monad is a rather complicated thing. The monad value is a function that returns a result of the computation by the given environment value. In Haskell it can be defined like this
In accordance with this definition I’ll create a monad macro WITH-READER-MONAD.
The UNIT macro prototype is simple enough.
The FUNCALL! macro prototype is crucial for understanding the monad macro.
There is a subtle thing. Parameter k is evaluated inside the anonymous function returned. In other words, its evaluation is delayed. I think that the user will expect namely such a behavior. Moreover, it allows the Lisp compiler to optimize the code in case of the PROGN! and LET! macros as it will be shown.
Also please note that value m, being a monad value, is actually an anonymous function. If its s-expression will be accessible during the macro expansion then we’ll receive something similar to
which can be efficiently optimized by the compiler to
The LET! macro prototype is more efficient than FUNCALL! as one of the FUNCALLs becomes unnecessary.
Here like expression e expression m is evaluated inside FUNCALL. It’s also a monad value, i.e. an anonymous function. If we’ll create a LET! expression with many variable bindings then the s-expression of m will be accessible during the macro expansion for all bindings but probably the last. It will allow the Lisp compiler to optimize the LET! expression essentially. We’ll see an example in the end of this section.
The PROGN! macro prototype is more simple as we don’t bind variables.
Again, if the s-expression for m1 and m2 will be accessible then the Lisp compiler will have good chances to generate a more optimal code.
The Reader monad was created for one purpose – to pass some value through all the computations. Let it be macro READ! that gets this value and puts in the monad. It corresponds to the read value defined above in Haskell. The macro prototype is as follows.
A computation in the Reader monad must be started somewhere. We take some value and pass it to the computation. This monad computation is passed in the first parameter. The environment value is passed in the second parameter. The corresponded macro has name RUN! and its prototype is defined below.
The value returned is a result of the monad computation.
Macros READ!, RUN!, UNIT, FUNCALL!, PROGN! and LET! are implemented as a MACROLET defined by the WITH-READER-MONAD macro.
Now we can take our old test example
and look at the result of the macro expansion.
We can see that there are many LAMBDAs and FUNCALLs bound together. A good Lisp compiler must generate a rather efficient code.
Here is a small test
and this is its output.
The State monad allows us to manage some state during a computation. We can put a new value or request for the current value of the state.
I’ll use the next definition written in Haskell.
I’ll create the corresponded monad macro WITH-STATE-MONAD. It will define macros GET!, PUT! and RUN! as a part of its MACROLET definition. The GET! macro will correspond to the get function. The PUT! macro will be an analog of the put function. The RUN! macro will play a role of the runState function.
First of all, I define utility macros.
The UNIT macro prototype is simple.
Please note that we evaluate a inside LAMBDA, i.e. the evaluation is delayed until the anonymous function is called. I’ll apply this strategy to all macros for this monad. In other words, any computation in this monad does nothing until it is explicitly started with help of macro RUN!, which will be defined further. By the way, the same strategy was true for the Reader monad.
The FUNCALL! macro prototype follows the definition of the bind function.
All notes that I did for the FUNCALL! macro of the Reader monad are applicable here. Being a monad value, expression m is actually an anonymous function. If its s-expression is available at the time of macro expansion then the corresponded FUNCALL and LAMBDA can be reduced by the smart compiler.
The LET! macro prototype generates a more optimal code than FUNCALL!.
If we create a multi-level LET! expression then m will be expanded to the LAMBDA expression in all cases but probably the last. It will allow the Lisp compiler to optimize the expanded code as you will see later in the example.
The PROGN! macro prototype is more simple.
To start a computation in the State monad, we can use the RUN! macro which accepts two arguments. The first argument specifies the computation. The second argument is an initial state. The RUN! macro returns a list of two values. The first value is the result of the computation itself. The second value of this list is a final state.
To manage the state during the computation, we can use macros GET! and PUT!. The GET! macro returns the current state wrapped in the monad.
The PUT! macro allows setting a new value for the state. This value is passed as a parameter. The macro returns NIL wrapped in the monad.
Macros RUN!, GET!, PUT!, UNIT, FUNCALL!, LET! and PROGN! are implemented as a MACROLET defined by the WITH-STATE-MONAD macro.
For our old test example
the macro expansion looks like
We can note that many LAMBDAs and FUNCALLs can be reduced. The bigger is our source expression, the more such constructs can the compiler reduce. The code should be rather cheap.
The next test enumerates items of the tree and creates a new tree, where each item is replaced with the CONS-pair consisting of the item itself and its sequence number.
Now we can launch a test.
This section describes the Writer monad. This monad allows writing a log during the computation. Then this log can be requested along with the computed result.
I will use the following definition written in Haskell.
Actually, I will use a more efficient representation of the functions. We can note that the return function uses id, but the bind function always creates a composition of two functions (f . f’). This is unnecessary. In Common Lisp we can use NIL to denote the identity function. It will be a detail of the implementation about which the user may not know. But this approach can help the compiler to generate a more efficient code in cases if the write and writeList functions are called rarely, i.e. when f’ is just the id function.
I’ll begin with utilities.
The next macro creates a composition of the two specified nullable functions, where NIL means the IDENTITY function.
Let our monad macro will have name WITH-READER-MONAD and will define three additional macros WRITE!, WRITE-LIST! and RUN!. The first two will be analogs of the write and writeList functions respectively and they will be used for writing a log. The RUN! macro will be an analog of the runWriter function and will be used for running a computation. The RUN! macro will return a list of two values. The first value will be a result of the computation itself. The second value will be a log written during the computation.
The WRITE! macro saves the specified values in the log. It returns NIL wrapped in the monad like that how the write function returns Writer w (). Its prototype is as follows.
Please note that we don’t add new records. We return a function that knows how to add them. This a very efficient technique. Please compare with the shows function from Haskell.
The WRITE-LIST! macro prototype takes the value lists and saves their values in the log. The macro returns NIL in the monad as well.
The RUN! macro accepts one argument, a monad computation. It returns a list consisting of the computed value and a log written during this computation. The prototype is defined below.
Here we take into account that the log function can be actually represented by value NIL. In such a case we return an empty list as a result log. If the function is defined then we ask it to create a log based on the initial empty log. It works fast, although the log is constructed starting from the end.
Also we can see a weakness of the method. If macros WRITE! and WRITE-LIST! were too often called then we would have a compound function consisting of a lot of nested functions. It might lead to the stack overflow. Be careful!
We consider NIL as an optimized representation of the IDENTITY function. The UNIT macro prototype uses this fact as the log remains unmodified.
The FUNCALL! macro is more complicated.
As usual, based on this macro we can write a more optimal definition of the LET! macro prototype which has no FUNCALL at all.
The PROGN! macro prototype is even more simple as there is no variable binding. But we have to compose the log functions, though.
Macros WRITE!, WRITE-LIST!, RUN!, UNIT, FUNCALL!, PROGN! and LET! are implemented as a MACROLET defined by macro WITH-WRITER-MONAD.
Now we can take our old example
and look at its macro expansion.
Although the expanded code looks long, it’s straightforward enough. It mainly consists of the IF conditions and creations of the short-living CONS-pairs at each step. The anonymous functions are created only in case of need. The compiled code should be rather cheap. Moreover, it can be efficient if the compiler can optimize the short-living CONS-pairs.
The next example illustrates the use of the WITH-WRITER-MONAD macro.
This is its output.
It’s possible to create a macro analog of the monad transformer in Common Lisp. Such a macro must be parameterized and it must define macro LIFT! that has the same meaning as the lift function in Haskell.
In the next sections are defined macros WITH-READER-MONAD-TRANS, WITH-WRITER-MONAD-TRANS and WITH-STATE-MONAD-TRANS. They are examples of the monad transformer macros. Each of them accepts the first parameter which must be a name of some monad macro in parentheses.
For example, we can write:
For this case we can create a separate monad macro and define the WRITE! macro on more high level using LIFT!
The monad transformer macros can be nested.
The LIFT! macro must know a name of the inner monad macro to call the corresponded inner return and bind functions. This is a crucial point. It is applied to macros UNIT, FUNCALL!, PROGN! and LET! as well.
In the next sections you will see how the monad transformer macros can be implemented. All examples follow a common pattern.
Note how the definition of WITH-SOME-MONAD-TRANS recursively refers to itself. It is important.
WITH-MONAD-TRANS s a utility macro that allows the monad transformer implementer to use two auxiliary macros WITH-INNER-MONAD-TRANS and WITH-OUTER-MONAD-TRANS in accordance with the following scheme.
Here the WITH-INNER-MONAD-TRANS macro must precede the WITH-OUTER-MONAD-TRANS macro. UNIQUE-ID is some unique identifier which must be different for each occurrence. Usually, it is a generated value with help of function GENSYM.
This scheme allows the implementer to switch between the outer and inner monad macros.
The WITH-MONAD-TRANS macro has the following definition.
Please note that an implementation of the WITH-OUTER-MONAD-TRANS macro is common and doesn’t depend on additional parameters, which allows us to switch to the outer monad even if case of the deep nested calls of WITH-MONAD-TRANS. The WITH-OUTER-MONAD-TRANS macro is expanded to a call of the macro represented by parameter id. The last macro must be already created by WITH-INNER-MONAD-PROTOTYPE before the inner monad macro is activated - this is why an order of precedence is important.
The key point is that the WITH-INNER-MONAD-PROTOTYPE macro, i.e. WITH-INNER-MONAD-TRANS, creates a new macro that is expanded already to the outer monad macro, which name was passed as a parameter of WITH-MONAD-TRANS if you remember. The name of this new generated macro is defined by the value of parameter id. But WITH-OUTER-MONAD-TRANS macro has a common implementation and it is always expanded namely to that new macro, which is expanded in its turn to the outer monad macro regardless of that how deeply the WITH-MONAD-TRANS macros are nested, for the value of the id parameter is supposed to be unique.
It’s worthy to note that if the monad macros consist of MACROLETs then macros WITH-MONAD-TRANS, WITH-INNER-MONAD-TRANS and WITH-OUTER-MONAD-TRANS add nothing but MACROLETs to the expanded code. Such a code should be rather efficient. All monad macros described in this article consist of MACROLETs only. It should be a general rule.
Nevertheless, in practice the Lisp compilers cannot process complex expressions, where the nested monad transformer macros are directly applied, although the simplest expressions are still compilable. There is a simple workaround for this problem. The approach is described in section Reducing Monad Macros.
In absence of the type classes in the language we have to distinguish somehow the operations performed in the inner and outer monads if we speak about the monad transformers. Now I will introduce prototypes for macros INNER-UNIT, INNER-FUNCALL!, INNER-LET! and INNER-PROGN! that will be counterparts to macros UNIT, FUNCALL!, LET! and PROGN!. Only the first macros call the corresponded operations in the inner monad with one important exception. Their parameters are always evaluated lexically within the outer monad. It allows us to safely call these macros within the outer monad macro.
So, the INNER-UNIT macro prototype is as follows.
Please note that expression a is evaluated within the outer monad. It will be a general rule.
The INNER-FUNCALL! macro prototype is similar.
The INNER-LET! macro prototype is analogous.
Please note how carefully we restore the outer monad lexical context. It’s very important. As we already discussed, it has no performance penalty for the generated code, although it creates a high load for the compiler because of numerous MACROLETs that are generated during the macro expansion.
The INNER-PROGN! macro prototype is more optimal.
Macros INNER-UNIT, INNER-FUNCALL!, INNER-LET! and INNER-PROGN! are implemented as a part of the MACROLET construct defined by macro WITH-MONAD-TRANS.
In most cases these new macros INNER-UNIT, UNNER-FUNCALL!, INNER-LET! and INNER-PROGN! cover all the needs and make low level macros WITH-INNER-MONAD-TRANS and WITH-OUTER-MONAD-TRANS unnecessary for the practical use in your code.
The Reader monad transformer is a parameterized version of the Reader monad but which can also act as the monad specified in the parameter. This is a very powerful abstraction. For example, we can combine the Reader monad transformer with the Writer monad. Then we can write a log and read an external value passed to the computation at the same time.
In Haskell the Reader monad transformer can be defined in the following way.
Please note that the return and bind functions are mixed. Some of them are related to the ReaderTrans monad itself. Others are related already to the parameter monad m. It says that we need helper macros INNER-UNIT, INNER-FUNCALL!, INNER-LET! and INNER-PROGN! introduced above.
I’ll define macro WITH-READER-MONAD-TRANS based on the WITH-MONAD-TRANS macro. Therefore the specified helper macros will be accessible.
The UNIT macro prototype uses INNER-UNIT.
Please note that expression a is evaluated in the context of the WITH-READER-MONAD-TRANS macro, not in the context of the inner monad. It will be true for all next definitions as well.
The FUNCALL! macro prototype is also similar to its non-parameterized version.
It corresponds to the definition written in Haskell. Only the order of parameters is different. Also all notes that I did for the non-parameterized version remain true. The generated code can be optimized by the compiler under some circumstances.
As before, the LET! macro prototype is more efficient.
We only replaced LET with INNER-LET! to take a value from the inner computation.
The PROGN! macro prototype uses INNER-PROGN! to bind the inner computations.
Being applied in complex nested expressions, all macros are expanded to a code that can be efficiently optimized by the compiler because of LAMBDAs and FUNCALLs that alternate with each other.
The READ! macro prototype uses already the INNER-UNIT macro to wrap the environment value in the inner monad.
The RUN! macro prototype is the same, but now it returns a computation result wrapped in the inner monad.
So far, the macros defined replicate the interface of the WITH-READER-MONAD macro. Now I’ll define the LIFT! macro that will allow us to perform any computation in the inner monad. This is namely that thing that allows the parameterized monad transformer to act as a monad specified in its parameter.
Macros LIFT!, READ!, UNIT, FUNCALL!, LET! and PROGN! are implemented as a MACROLET defined by the WITH-READER-MONAD-TRANS macro, which in its turn follows a common pattern described in section Monad Transformers.
Now the monad macro generates much code. Even after removing the MACROLETs that mean nothing for the execution time but that may slow down the compilation process, the macro expansion may be still long depending on the specified inner monad. Therefore I will use a simpler example to illustrate the code generation.
After removing all the MACROLETs (with help of CLISP), the code expansion looks like
Here is a test of the monad macro.
This is its output.
The State monad transformer is a parameterized version of the State monad but which can also behave like a monad specified in the parameter. For example, we can create a version of the State monad transformer parameterized by the Writer monad. Then we can manage the state and write a log during the computation simultaneously.
I’ll use the following definition of the State monad transformer written in Haskell.
We see that the return and bind functions are mixed as it was in case of the Reader monad transformer. Some functions correspond to the StateTrans monad. Others correspond to the inner monad m. Hence we need macros INNER-UNIT, INNER-FUNCALL!, INNER-LET! and INNER-PROGN! provided by the WITH-MONAD-TRANS macro.
I’ll define a new macro WITH-STATE-MONAD-TRANS based on WITH-MONAD-TRANS in accordance with the general pattern described in section Monad Transformers. Also the new macro will be similar to its non-parameterized counterpart WITH-STATE-MONAD. The WITH-STATE-MONAD-TRANS macro will define macros GET!, PUT! and RUN!. Only the latter will return a value wrapped in the inner monad.
The UNIT macro prototype is similar but it uses INNER-UNIT to wrap a pair in the inner monad.
As before, expression a is evaluated inside LAMBDA, i.e. the evaluation is delayed. This strategy will be applied to all other macros defined further.
The FUNCALL! macro prototype is similar too, but now it uses INNER-LET! to get a raw value from the inner monad.
The notes that I did earlier for the State monad are applicable now as well. Expression m is used as the first argument of the FUNCALL function. This expression is a monad value, i.e. an anonymous function. If the s-expression for m is available then m will be expanded to the LAMBDA expression. These LAMBDA and FUNCALL can be reduced by the smart compiler.
As usual, the LET! macro prototype generates a more efficient code than FUNCALL!.
Here expressions e and m are monad values, i.e. anonymous functions. Moreover, if we create a multi-level LET! expression then the s-expression for m is available for all cases but probably the last. This s-expression is started with LAMBDA. Therefore LAMBDAs and FUNCALLs can be reduced by the compiler too.
The PROGN! macro prototype doesn’t bind variables but it passes the state through the computation like the previous macros.
The RUN! macro launches a computation specified in the first parameter. The second parameter defines an initial state. The macro returns a list wrapped in the inner monad. The first value of the list is a result of the computation itself. The second value is a final state.
The GET! macro prototype returns the current state wrapped in the outer monad.
The PUT! macro prototype has one parameter that specifies a new value for the state. It allows us to modify the state. The new value will be then passed to the rest part of the computation. The macro returns NIL wrapped in the outer monad.
The LIFT! macro endows the parameterized monad transformer with an ability to act as a monad specified in the parameter. The macro accepts any computation in the inner monad. This inner computation becomes a part of the outer computation.
Macros GET!, PUT!, RUN!, LIFT!, UNIT, FUNCALL!, LET! and PROGN! are implemented as a MACROLET defined by the WITH-STATE-MONAD-TRANS macro that follows a common pattern of the monad transformer macros.
The code generation can be illustrated on the following example.
After removing all MACROLETs (with help of CLISP), the code is expanded to
The next test enumerates all items of the tree. It creates a new tree, where each item is replaced with a CONS-pair, consisting of the item itself and its sequence number. Also the test function saves all enumerated items in the list and shows it as a log.
Now we can launch a test.
The Writer monad transformer is a parameterized version of the Writer monad but which can also act as a monad specified in the parameter. For example, we can parameterize this transformer by the Maybe monad. As a result, we’ll receive a new monad that will allow us to write a log and cut all computations immediately in case of need.
I will use the next definition written in Haskell.
As in case of the Reader monad transformer we can see a lot of the mixed functions return and bind. Some of them are related to WriterTrans. Others are related to monad m. Therefore we need again the WITH-MONAD-TRANS macro that contains definitions of INNER-UNIT, INNER-LET!, INNER-FUNCALL! and INNER-PROGN! that allow us to work with the parameter monad.
So, I’ll define macro WITH-WRITER-MONAD-TRANS that will be based on the WITH-MONAD-TRANS macro in accordance with the general pattern described in section Monad Transformers. This new macro will be similar to the WITH-WRITER-MONAD macro. It will be only parameterized and it will also contain macro LIFT!, an analog of the lift function from Haskell.
The WRITE! macro uses now the INNER-UNIT macro as we have to wrap a CONS-pair created with help of MAKE-WRITER.
The WRITE-LIST! macro prototype is similar. It also returns NIL in the outer monad.
Please note that in the both macros we evaluate the values ws and wss first and then return new functions. The real writing operation will be delayed.
Now the RUN! macro returns a list of two values, where the list is wrapped in the inner monad. The first value of the list is a result of the computation. The second value is a log written during this computation.
The UNIT macro prototype also uses the INNER-UNIT macro to wrap a value in the inner monad.
Please note that expression a is expanded within the outer monad macro, i.e. within WITH-WRITER-MONAD-TRANS, for which the INNER-UNIT macro is responsible.
The FUNCALL! macro prototype is also similar to its non-parameterized counterpart.
As usual, the LET! macro prototype is more optimal.
The PROGN! macro prototype was also slightly modified.
As in case of the Reader monad transformer macro we can define the LIFT! macro that will allow us to perform any computation in the inner monad. This is that thing that allows the parameterized monad transformer to act as a monad specified in its parameter.
Macros LIFT!, WRITE!, WRITE-LIST!, UNIT, FUNCALL!, LET! and PROGN! are implemented as a MACROLET defined by macro WITH-WRITER-MONAD-TRANS, which in its turn follows a common pattern of the monad transformer macros.
This monad macro generates a lot of MACROLETs. They don’t impact the performance of the executed code, although the compilation becomes a more difficult task for the Lisp system.
Let’s take the following sample
After removing the MACROLETs (with help of CLISP) the macro expansion looks like this
Here is a test.
If you’ll try to compile it with help of SBCL, then the compiler will warn about an unreachable code!
This is an output of the test.
The ordinary monad macros are expanded to a construct that contains a single MACROLET. Therefore the expressions that use these monad macros are compiled fast. The monad macros built on the monad transformers are not that case. They are expanded already to a construct that may contain a lot of nested MACROLETs. It becomes a real problem for the Lisp compiler. Not any expression consisting of the nested monad transformer macros can be even compiled!
Below is described an approach that allows the Lisp system to compile monad transformer macros of any complexity and to do it relatively fast. The main idea is to replace the macros with functions. The drawback of this method is that an executable code becomes a little bit slower than it could be in case of the pure macro expansion.
I’ll illustrate the method on the parameterized twice macro WITH-WRITER-MONAD-TRANS (WITH-READER-MONAD-TRANS (WITH-MAYBE-MONAD)).
First, we create a short name for our source macro, lifting the READ! macro from the Writer monad transformer.
This new macro provides macros READ!, WRITE!, WRITER-LIST!, RUN!, LIFT!, UNIT, FUNCALL!, LET! and PROGN!. Now we’ll create functions for them, i.e. all macros will be expanded only once.
In the last function we create a sequence of the computations and always return NIL wrapped in the monad.
The top level RUN! macro returns a list wrapped in the inner monad WITH-READER-MONAD-TRANS (WITH-MAYBE-MONAD). This list contains two values. The first is a result of the computation. The second value is a log written during this computation. The inner RUN! macro returns already a value in the Maybe monad. Therefore we can unite two RUN! macros and return the list of two values in the Maybe monad.
We also have two LIFT! macros. We can unite them too. We pass some computation in the Maybe monad, for example, a value created with help of the MAKE-MAYBE function, and the new function returns the corresponded computation wrapped in the outer monad WITH-OPT-PROTO.
Now we can define the return and bind functions.
We have all functions to define a new monad macro with help of the WITH-MONAD macro. I’ll call this new monad macro a reduction form of the source macro. It contains only two nested MACROLETs, which makes the code with the new macro easily compilable regardless of that how complex are the expressions built with help of macros UNIT, FUNCALL!, LET! and PROGN!.
In difficult cases the reduction can be applied many times. For example, to receive a monad macro with the same behavior, we could first reduce macro WITH-READER-MONAD-TRANS (WITH-MAYBE-MONAD) to new macro WITH-READER-MAYBE-MONAD. Then we could reduce macro WITH-WRITER-MONAD-TRANS (WITH-READER-MAYBE-MONAD) to form WITH-ALTOPT-MONAD, which would be equivalent to the WITH-OPT-MONAD macro. Only the more reduction steps we apply the less efficient code is generated by the compiler. But sometimes the reduction is a single possible way to make the code compilable.
This is a small test with the new monad.
The test returns the following results.
The monad macros can perfectly coexist with the standard constructions IF, COND, PROGN, LET, LET*, FLET, LABELS, MACROLET, SYMBOL-MACROLET, LAMBDA, FUNCALL, DESTRUCTURING -BIND and some others in one expression. On the contrary, the standard loop macros DO, DOLIST, DOTIMES and LOOP are not so simple. If we perform monad computations in some loop then, generally speaking, we have to connect all the intermediate monad computations into one with help of something like the PROGN! macro. This is a key point.
I won’t dwell on this subject, but I want to say that some monad macros could be implemented as a MACROLET defining macros DO!, DOLIST! and DOTIMES! that would be monadic counterparts to the standard loop macros. Here we would probably have to add some monad representation of an empty loop, i.e. an empty monad computation. It could be a macro named ZERO!, for example. Also I think that the LOOP macro is more difficult case and I’m not sure that a monadic counterpart can be created for it.
In Haskell we can define a small set of polymorphic functions that will work with any monad. Here in Common Lisp we can partially implement the same idea but in another way. Taking into account that the number of such common functions is relatively small and they are usually simple, we can try to implement them with help of a MACROLET that would be supplied together with the monad macro like WITH-MONAD.
In general case we can define a prototype for the functor map function, which I’ll call FMAP.
It’s obvious that in case of the List monad the following definition will be much more efficient:
It’s easy to provide each monad macro with its own optimized version of the FMAP macro. Moreover, such a technique has no almost performance overhead.
The approach can be generalized for other monad functions. But the task of their creation deserves a separate article. Now I will only provide a naïve non-optimized version of another useful macro LIST!, which is an expanded version of the sequence function from Haskell
In case of the WITH-IDENTITY-MONAD macro the LIST! macro can be replaced with function LIST, which corresponds to the rule of thumb.
I tried to introduce the monads in the Lisp Way. I know that there were other attempts. They are mainly based on using generic functions that allow the programmer to write a polymorphic code but at the cost of some lost of the performance. My approach, on the contrary, allows the Lisp compiler to generate an efficient code but it lacks some flexibility.
Also I think that my approach is somewhere similar to the F# workflows. Only the monad macros play a role of the workflow builders.