[Cl-monad-macros-cvs] r3 - trunk/doc
David Sorokin
dsorokin at common-lisp.net
Thu Jan 21 15:16:38 UTC 2010
Author: dsorokin
Date: Thu Jan 21 10:16:37 2010
New Revision: 3
Log:
Added documentation.
Added:
trunk/doc/
trunk/doc/monad-macros.htm
Added: trunk/doc/monad-macros.htm
==============================================================================
--- (empty file)
+++ trunk/doc/monad-macros.htm Thu Jan 21 10:16:37 2010
@@ -0,0 +1,3980 @@
+<html>
+
+<head>
+<meta http-equiv=Content-Type content="text/html; charset=windows-1251">
+<meta name=Generator content="Microsoft Word 12 (filtered)">
+<title>Monad Macros in Common Lisp</title>
+<style>
+<!--
+ /* Font Definitions */
+ @font-face
+ {font-family:Wingdings;
+ panose-1:5 0 0 0 0 0 0 0 0 0;}
+ at font-face
+ {font-family:"Cambria Math";
+ panose-1:2 4 5 3 5 4 6 3 2 4;}
+ at font-face
+ {font-family:Cambria;
+ panose-1:2 4 5 3 5 4 6 3 2 4;}
+ at font-face
+ {font-family:Calibri;
+ panose-1:2 15 5 2 2 2 4 3 2 4;}
+ at font-face
+ {font-family:Tahoma;
+ panose-1:2 11 6 4 3 5 4 4 2 4;}
+ /* Style Definitions */
+ p.MsoNormal, li.MsoNormal, div.MsoNormal
+ {margin-top:0cm;
+ margin-right:0cm;
+ margin-bottom:10.0pt;
+ margin-left:0cm;
+ line-height:115%;
+ font-size:11.0pt;
+ font-family:"Calibri","sans-serif";}
+h1
+ {mso-style-link:"Çàãîëîâîê 1 Çíàê";
+ margin-top:24.0pt;
+ margin-right:0cm;
+ margin-bottom:0cm;
+ margin-left:0cm;
+ margin-bottom:.0001pt;
+ line-height:115%;
+ page-break-after:avoid;
+ font-size:14.0pt;
+ font-family:"Cambria","serif";
+ color:#365F91;}
+h2
+ {mso-style-link:"Çàãîëîâîê 2 Çíàê";
+ margin-top:10.0pt;
+ margin-right:0cm;
+ margin-bottom:0cm;
+ margin-left:0cm;
+ margin-bottom:.0001pt;
+ line-height:115%;
+ page-break-after:avoid;
+ font-size:13.0pt;
+ font-family:"Cambria","serif";
+ color:#4F81BD;}
+p.MsoToc1, li.MsoToc1, div.MsoToc1
+ {margin-top:0cm;
+ margin-right:0cm;
+ margin-bottom:5.0pt;
+ margin-left:0cm;
+ line-height:115%;
+ font-size:11.0pt;
+ font-family:"Calibri","sans-serif";}
+p.MsoToc2, li.MsoToc2, div.MsoToc2
+ {margin-top:0cm;
+ margin-right:0cm;
+ margin-bottom:5.0pt;
+ margin-left:11.0pt;
+ line-height:115%;
+ font-size:11.0pt;
+ font-family:"Calibri","sans-serif";}
+p.MsoHeader, li.MsoHeader, div.MsoHeader
+ {mso-style-link:"Âåðõíèé êîëîíòèòóë Çíàê";
+ margin:0cm;
+ margin-bottom:.0001pt;
+ font-size:11.0pt;
+ font-family:"Calibri","sans-serif";}
+p.MsoFooter, li.MsoFooter, div.MsoFooter
+ {mso-style-link:"Íèæíèé êîëîíòèòóë Çíàê";
+ margin:0cm;
+ margin-bottom:.0001pt;
+ font-size:11.0pt;
+ font-family:"Calibri","sans-serif";}
+p.MsoTitle, li.MsoTitle, div.MsoTitle
+ {mso-style-link:"Íàçâàíèå Çíàê";
+ margin-top:0cm;
+ margin-right:0cm;
+ margin-bottom:15.0pt;
+ margin-left:0cm;
+ border:none;
+ padding:0cm;
+ font-size:26.0pt;
+ font-family:"Cambria","serif";
+ color:#17365D;
+ letter-spacing:.25pt;}
+p.MsoTitleCxSpFirst, li.MsoTitleCxSpFirst, div.MsoTitleCxSpFirst
+ {mso-style-link:"Íàçâàíèå Çíàê";
+ margin:0cm;
+ margin-bottom:.0001pt;
+ border:none;
+ padding:0cm;
+ font-size:26.0pt;
+ font-family:"Cambria","serif";
+ color:#17365D;
+ letter-spacing:.25pt;}
+p.MsoTitleCxSpMiddle, li.MsoTitleCxSpMiddle, div.MsoTitleCxSpMiddle
+ {mso-style-link:"Íàçâàíèå Çíàê";
+ margin:0cm;
+ margin-bottom:.0001pt;
+ border:none;
+ padding:0cm;
+ font-size:26.0pt;
+ font-family:"Cambria","serif";
+ color:#17365D;
+ letter-spacing:.25pt;}
+p.MsoTitleCxSpLast, li.MsoTitleCxSpLast, div.MsoTitleCxSpLast
+ {mso-style-link:"Íàçâàíèå Çíàê";
+ margin-top:0cm;
+ margin-right:0cm;
+ margin-bottom:15.0pt;
+ margin-left:0cm;
+ border:none;
+ padding:0cm;
+ font-size:26.0pt;
+ font-family:"Cambria","serif";
+ color:#17365D;
+ letter-spacing:.25pt;}
+a:link, span.MsoHyperlink
+ {color:blue;
+ text-decoration:underline;}
+a:visited, span.MsoHyperlinkFollowed
+ {color:purple;
+ text-decoration:underline;}
+p.MsoAcetate, li.MsoAcetate, div.MsoAcetate
+ {mso-style-link:"Òåêñò âûíîñêè Çíàê";
+ margin:0cm;
+ margin-bottom:.0001pt;
+ font-size:8.0pt;
+ font-family:"Tahoma","sans-serif";}
+p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
+ {margin-top:0cm;
+ margin-right:0cm;
+ margin-bottom:10.0pt;
+ margin-left:36.0pt;
+ line-height:115%;
+ font-size:11.0pt;
+ font-family:"Calibri","sans-serif";}
+p.MsoListParagraphCxSpFirst, li.MsoListParagraphCxSpFirst, div.MsoListParagraphCxSpFirst
+ {margin-top:0cm;
+ margin-right:0cm;
+ margin-bottom:0cm;
+ margin-left:36.0pt;
+ margin-bottom:.0001pt;
+ line-height:115%;
+ font-size:11.0pt;
+ font-family:"Calibri","sans-serif";}
+p.MsoListParagraphCxSpMiddle, li.MsoListParagraphCxSpMiddle, div.MsoListParagraphCxSpMiddle
+ {margin-top:0cm;
+ margin-right:0cm;
+ margin-bottom:0cm;
+ margin-left:36.0pt;
+ margin-bottom:.0001pt;
+ line-height:115%;
+ font-size:11.0pt;
+ font-family:"Calibri","sans-serif";}
+p.MsoListParagraphCxSpLast, li.MsoListParagraphCxSpLast, div.MsoListParagraphCxSpLast
+ {margin-top:0cm;
+ margin-right:0cm;
+ margin-bottom:10.0pt;
+ margin-left:36.0pt;
+ line-height:115%;
+ font-size:11.0pt;
+ font-family:"Calibri","sans-serif";}
+p.MsoTocHeading, li.MsoTocHeading, div.MsoTocHeading
+ {margin-top:24.0pt;
+ margin-right:0cm;
+ margin-bottom:0cm;
+ margin-left:0cm;
+ margin-bottom:.0001pt;
+ line-height:115%;
+ page-break-after:avoid;
+ font-size:14.0pt;
+ font-family:"Cambria","serif";
+ color:#365F91;
+ font-weight:bold;}
+span.1
+ {mso-style-name:"Çàãîëîâîê 1 Çíàê";
+ mso-style-link:"Çàãîëîâîê 1";
+ font-family:"Cambria","serif";
+ color:#365F91;
+ font-weight:bold;}
+p.a, li.a, div.a
+ {mso-style-name:Êîä;
+ mso-style-link:"Êîä Çíàê";
+ margin-top:6.0pt;
+ margin-right:0cm;
+ margin-bottom:16.0pt;
+ margin-left:0cm;
+ line-height:115%;
+ background:#DBE5F1;
+ border:none;
+ padding:0cm;
+ font-size:10.0pt;
+ font-family:"Courier New";}
+span.a0
+ {mso-style-name:"Êîä Çíàê";
+ mso-style-link:Êîä;
+ font-family:"Courier New";
+ background:#DBE5F1;}
+span.2
+ {mso-style-name:"Çàãîëîâîê 2 Çíàê";
+ mso-style-link:"Çàãîëîâîê 2";
+ font-family:"Cambria","serif";
+ color:#4F81BD;
+ font-weight:bold;}
+p.a1, li.a1, div.a1
+ {mso-style-name:"Êîä â òàáëèöå";
+ mso-style-link:"Êîä â òàáëèöå Çíàê";
+ margin-top:6.0pt;
+ margin-right:0cm;
+ margin-bottom:16.0pt;
+ margin-left:0cm;
+ font-size:10.0pt;
+ font-family:"Courier New";}
+span.a2
+ {mso-style-name:"Êîä â òàáëèöå Çíàê";
+ mso-style-link:"Êîä â òàáëèöå";
+ font-family:"Courier New";
+ background:#DBE5F1;}
+span.a3
+ {mso-style-name:"Òåêñò âûíîñêè Çíàê";
+ mso-style-link:"Òåêñò âûíîñêè";
+ font-family:"Tahoma","sans-serif";}
+span.a4
+ {mso-style-name:"Íàçâàíèå Çíàê";
+ mso-style-link:Íàçâàíèå;
+ font-family:"Cambria","serif";
+ color:#17365D;
+ letter-spacing:.25pt;}
+span.a5
+ {mso-style-name:"Âåðõíèé êîëîíòèòóë Çíàê";
+ mso-style-link:"Âåðõíèé êîëîíòèòóë";}
+span.a6
+ {mso-style-name:"Íèæíèé êîëîíòèòóë Çíàê";
+ mso-style-link:"Íèæíèé êîëîíòèòóë";}
+.MsoPapDefault
+ {margin-bottom:10.0pt;
+ line-height:115%;}
+ /* Page Definitions */
+ @page Section1
+ {size:595.3pt 841.9pt;
+ margin:2.0cm 42.5pt 2.0cm 3.0cm;}
+div.Section1
+ {page:Section1;}
+ /* List Definitions */
+ ol
+ {margin-bottom:0cm;}
+ul
+ {margin-bottom:0cm;}
+-->
+</style>
+
+</head>
+
+<body lang=RU link=blue vlink=purple>
+
+<div class=Section1>
+
+<div style='border:none;border-bottom:solid #4F81BD 1.0pt;padding:0cm 0cm 4.0pt 0cm'>
+
+<p class=MsoTitle><a name="_Toc251505251"></a><a name="_Toc251505163"></a><a
+name="_Toc251505060"><span lang=EN-US>Monad Macros in Common Lisp</span></a></p>
+
+</div>
+
+<p class=MsoNormal style='margin-bottom:72.0pt'><span lang=EN-US>David Sorokin </span><a
+href="mailto:david.sorokin at gmail.com"><span lang=EN-US>david.sorokin at gmail.com</span></a><span
+lang=EN-US>, Jan 2010</span></p>
+
+<p class=MsoTocHeading><a name="_Toc251505164"></a><a name="_Toc251505061"></a><span
+lang=EN-US>Contents</span></p>
+
+<p class=MsoToc1><a href="#_Toc251846352"><span lang=EN-US>Introduction</span><span
+style='color:windowtext;display:none;text-decoration:none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>2</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846353"><span lang=EN-US>General Case</span><span
+style='color:windowtext;display:none;text-decoration:none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>2</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846354"><span lang=EN-US>Bind Macros</span><span
+style='color:windowtext;display:none;text-decoration:none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>6</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846355"><span lang=EN-US>The Identity Monad</span><span
+style='color:windowtext;display:none;text-decoration:none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>7</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846356"><span lang=EN-US>The List Monad</span><span
+style='color:windowtext;display:none;text-decoration:none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>8</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846357"><span lang=EN-US>The Maybe Monad</span><span
+style='color:windowtext;display:none;text-decoration:none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>10</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846358"><span lang=EN-US>The Reader Monad</span><span
+style='color:windowtext;display:none;text-decoration:none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>12</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846359"><span lang=EN-US>The State Monad</span><span
+style='color:windowtext;display:none;text-decoration:none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>15</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846360"><span lang=EN-US>The Writer Monad</span><span
+style='color:windowtext;display:none;text-decoration:none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>19</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846361"><span lang=EN-US>Monad Transformers</span><span
+style='color:windowtext;display:none;text-decoration:none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>25</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846362"><span lang=EN-US>Inner Monad Macros</span><span
+style='color:windowtext;display:none;text-decoration:none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>27</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846363"><span lang=EN-US>The Reader Monad
+Transformer</span><span style='color:windowtext;display:none;text-decoration:
+none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>29</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846364"><span lang=EN-US>The State Monad
+Transformer</span><span style='color:windowtext;display:none;text-decoration:
+none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>32</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846365"><span lang=EN-US>The Writer Monad
+Transformer</span><span style='color:windowtext;display:none;text-decoration:
+none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>37</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846366"><span lang=EN-US>Reducing Monad
+Macros</span><span style='color:windowtext;display:none;text-decoration:none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>42</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846367"><span lang=EN-US>Loops</span><span
+style='color:windowtext;display:none;text-decoration:none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>44</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846368"><span lang=EN-US>Other Monad Macros</span><span
+style='color:windowtext;display:none;text-decoration:none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>45</span></a></p>
+
+<p class=MsoToc1><a href="#_Toc251846369"><span lang=EN-US>Conclusion</span><span
+style='color:windowtext;display:none;text-decoration:none'>. </span><span
+style='color:windowtext;display:none;text-decoration:none'>46</span></a></p>
+
+<p class=MsoNormal> </p>
+
+<span lang=EN-US style='font-size:11.0pt;line-height:115%;font-family:"Calibri","sans-serif"'><br
+clear=all style='page-break-before:always'>
+</span>
+
+<p class=MsoNormal><b><span lang=EN-US style='font-size:14.0pt;line-height:
+115%;font-family:"Cambria","serif";color:#365F91'> </span></b></p>
+
+<h1><a name="_Toc251846352"><span lang=EN-US>Introduction</span></a></h1>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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 <i>return</i>. The
+second one is known as the <i>bind</i> function and it is denoted in Haskell as
+operator (>>=):</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>class Monad m where<br>
+ return :: a -> m a<br>
+ (>>=) :: m a -> (a -> m b) -> m b</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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 <i>do</i>-notation which is a syntactic sugar
+for monads. The macros I will create will provide similar facilities as well.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>Also I created a new project with name <b>cl-monad-macros</b>.
+It is available by the following link: </span><a
+href="http://common-lisp.net/project/cl-monad-macros"><span lang=EN-US>http://common-lisp.net/project/cl-monad-macros</span></a><span
+lang=EN-US>. The corresponded package contains definitions of all monad macros
+described in this article.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The package and all examples were
+successfully tested on the following Lisp systems:</span></p>
+
+<p class=MsoListParagraphCxSpFirst style='text-indent:-18.0pt'><span
+lang=EN-US style='font-family:Symbol'>·<span style='font:7.0pt "Times New Roman"'>
+</span></span><span lang=EN-US>Steel Bank Common Lisp (SBCL);</span></p>
+
+<p class=MsoListParagraphCxSpMiddle style='text-indent:-18.0pt'><span
+lang=EN-US style='font-family:Symbol'>·<span style='font:7.0pt "Times New Roman"'>
+</span></span><span lang=EN-US>Clozure CL (CCL);</span></p>
+
+<p class=MsoListParagraphCxSpMiddle style='text-indent:-18.0pt'><span
+lang=EN-US style='font-family:Symbol'>·<span style='font:7.0pt "Times New Roman"'>
+</span></span><span lang=EN-US>CLISP;</span></p>
+
+<p class=MsoListParagraphCxSpMiddle style='text-indent:-18.0pt'><span
+lang=EN-US style='font-family:Symbol'>·<span style='font:7.0pt "Times New Roman"'>
+</span></span><span lang=EN-US>LispWorks;</span></p>
+
+<p class=MsoListParagraphCxSpLast style='text-indent:-18.0pt'><span lang=EN-US
+style='font-family:Symbol'>·<span style='font:7.0pt "Times New Roman"'>
+</span></span><span lang=EN-US>Allegro CL.</span></p>
+
+<h1><a name="_Toc251846353"></a><a name="_Toc251505165"></a><a
+name="_Toc251505062"></a><a name="_General_Case"></a><span lang=EN-US>General
+Case</span></h1>
+
+<p class=MsoNormal><span lang=EN-US>Let’s suppose that some monad is defined
+with help of two hypothetical functions UNITF and FUNCALLF:</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defun unitf (a)<br>
+ ;; evaluate as in Haskell: return a<br>
+ …)<br>
+<br>
+(defun funcallf (k m)<br>
+ ;; evaluate as in Haskell: m >>= k<br>
+ …)</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The UNITF function is the return function.
+Function FUNCALLF is an analog of the idiomatic bind<i> </i>function but only
+the order of arguments is opposite. Further I call namely this new function a <i>bind</i>
+function. Please take care.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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. </span></p>
+
+<p class=MsoNormal><span lang=EN-US>Therefore I offer to use the following
+macros:</span></p>
+
+<table class=MsoTableGrid border=1 cellspacing=0 cellpadding=0
+ style='border-collapse:collapse;border:none'>
+ <tr>
+ <td width=319 valign=top style='width:239.25pt;border:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal align=center style='margin-bottom:0cm;margin-bottom:.0001pt;
+ text-align:center;line-height:normal'><span lang=EN-US>Common Lisp</span></p>
+ </td>
+ <td width=319 valign=top style='width:239.3pt;border:solid black 1.0pt;
+ border-left:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal align=center style='margin-bottom:0cm;margin-bottom:.0001pt;
+ text-align:center;line-height:normal'><span lang=EN-US>Haskell</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=319 valign=top style='width:239.25pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>(unit <i>a</i>)</span></p>
+ </td>
+ <td width=319 valign=top style='width:239.3pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>return <i>a</i></span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=319 valign=top style='width:239.25pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>(funcall! <i>k</i> <i>m</i>)</span></p>
+ </td>
+ <td width=319 valign=top style='width:239.3pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><i><span lang=EN-US>m</span></i><span lang=EN-US> >>= <i>k</i></span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=319 valign=top style='width:239.25pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>(progn! <i>m1</i> <i>m2</i> … <i>mn</i>)</span></p>
+ </td>
+ <td width=319 valign=top style='width:239.3pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><i><span lang=EN-US>m1</span></i><span lang=EN-US> >> <i>m2</i>
+ >> … >> <i>mn</i></span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=319 valign=top style='width:239.25pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>(let! ((<i>x1</i> <i>e1</i>)<br>
+ (<i>x2</i> <i>e2</i>)<br>
+ …<br>
+ (<i>xn</i> <i>en</i>))<br>
+ <i>m</i>)</span></p>
+ </td>
+ <td width=319 valign=top style='width:239.3pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>do <i>x1</i> <- <i>e1</i><br>
+ <i>x2</i> <- <i>e2</i><br>
+ …<br>
+ <i>xn</i> <- <i>en</i><br>
+ <i>m</i></span></p>
+ </td>
+ </tr>
+</table>
+
+<p class=MsoNormal><span lang=EN-US> </span></p>
+
+<p class=MsoNormal><span lang=EN-US>The UNIT macro is equivalent to a call of
+the <i>return</i> function. The FUNCALL! macro is expanded to a call of the
+bind function. Macro PROGN! is equivalent to the monadic <i>then</i> 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.</span></p>
+
+<table class=MsoTableGrid border=1 cellspacing=0 cellpadding=0
+ style='border-collapse:collapse;border:none'>
+ <tr>
+ <td width=319 valign=top style='width:239.25pt;border:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal align=center style='margin-bottom:0cm;margin-bottom:.0001pt;
+ text-align:center;line-height:normal'><span lang=EN-US>Source form</span></p>
+ </td>
+ <td width=319 valign=top style='width:239.3pt;border:solid black 1.0pt;
+ border-left:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal align=center style='margin-bottom:0cm;margin-bottom:.0001pt;
+ text-align:center;line-height:normal'><span lang=EN-US>Reduction form</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=319 valign=top style='width:239.25pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>(progn! <i>m</i>)</span></p>
+ </td>
+ <td width=319 valign=top style='width:239.3pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>m</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=319 valign=top style='width:239.25pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>(progn! <i>m1</i> <i>m2</i>)</span></p>
+ </td>
+ <td width=319 valign=top style='width:239.3pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>(funcall!<br>
+ #’(lambda (<i>#:gen-var</i>)<br>
+ (declare (ignore <i>#:gen_var</i>))<br>
+ <i>m2</i>)<br>
+ <i>m1</i>)</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=319 valign=top style='width:239.25pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>(progn! <i>m1</i> <i>m2</i> … <i>mn</i>)</span></p>
+ </td>
+ <td width=319 valign=top style='width:239.3pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>(progn! <i>m1</i> (progn! <i>m2</i> … <i>mn</i>))</span></p>
+ </td>
+ </tr>
+</table>
+
+<p class=MsoNormal><span lang=EN-US> </span></p>
+
+<p class=MsoNormal><span lang=EN-US>Here <i>#:gen-var</i> means an
+automatically generated unique variable name with help of GENSYM.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>Macro LET! is somewhere an alternative to
+the arrow symbol from the <i>do</i>-notation of Haskell. It is also based on
+the FUNCALL! macro. It binds computations <i>e1</i>, <i>e2</i>, …, <i>en</i>
+with values <i>x1</i>, <i>x2</i>, …, <i>xn,</i> which can be then used in
+computation <i>m</i>.</span></p>
+
+<table class=MsoTableGrid border=1 cellspacing=0 cellpadding=0
+ style='border-collapse:collapse;border:none'>
+ <tr>
+ <td width=319 valign=top style='width:239.25pt;border:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal align=center style='margin-bottom:0cm;margin-bottom:.0001pt;
+ text-align:center;line-height:normal'><span lang=EN-US>Source form</span></p>
+ </td>
+ <td width=319 valign=top style='width:239.3pt;border:solid black 1.0pt;
+ border-left:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal align=center style='margin-bottom:0cm;margin-bottom:.0001pt;
+ text-align:center;line-height:normal'><span lang=EN-US>Reduction form</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=319 valign=top style='width:239.25pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>(let! ((<i>x</i> <i>e</i>)) <i>m</i>)</span></p>
+ </td>
+ <td width=319 valign=top style='width:239.3pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>(funcall!<br>
+ #’(lambda (<i>x</i>) <i>m</i>)<br>
+ <i>e</i>)</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=319 valign=top style='width:239.25pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>(let! ((<i>x1</i> <i>e1</i>)<br>
+ (<i>x2</i> <i>e2</i>)<br>
+ …<br>
+ (<i>xn</i> <i>en</i>))<br>
+ <i>m</i>)</span></p>
+ </td>
+ <td width=319 valign=top style='width:239.3pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>(let! ((<i>x1</i> <i>e1</i>))<br>
+ (let! ((<i>x2</i> <i>e2</i>)<br>
+ …<br>
+ (<i>xn</i> <i>en</i>))<br>
+ <i>m</i>))</span></p>
+ </td>
+ </tr>
+</table>
+
+<p class=MsoNormal><span lang=EN-US> </span></p>
+
+<p class=MsoNormal><span lang=EN-US>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:</span></p>
+
+<table class=MsoTableGrid border=1 cellspacing=0 cellpadding=0
+ style='border-collapse:collapse;border:none'>
+ <tr>
+ <td width=319 valign=top style='width:239.25pt;border:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal align=center style='margin-bottom:0cm;margin-bottom:.0001pt;
+ text-align:center;line-height:normal'><span lang=EN-US>Common Lisp</span></p>
+ </td>
+ <td width=319 valign=top style='width:239.3pt;border:solid black 1.0pt;
+ border-left:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal align=center style='margin-bottom:0cm;margin-bottom:.0001pt;
+ text-align:center;line-height:normal'><span lang=EN-US>Haskell</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=319 valign=top style='width:239.25pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>(let! ((<i>x</i> <i>e</i>))<br>
+ (progn! <i>m1</i> <i>m2</i> … <i>mn</i>))</span></p>
+ </td>
+ <td width=319 valign=top style='width:239.3pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>do <i>x</i> <- <i>e</i><br>
+ <i>m1</i><br>
+ <i>m2</i><br>
+ …<br>
+ <i>mn</i></span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=319 valign=top style='width:239.25pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>(let ((<i>x</i> <i>a</i>))<br>
+ (progn! <i>m1</i> <i>m2</i> … <i>mn</i>))</span></p>
+ </td>
+ <td width=319 valign=top style='width:239.3pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=a1><span lang=EN-US>do let <i>x</i> = <i>a</i><br>
+ <i>m1</i><br>
+ <i>m2</i><br>
+ …<br>
+ <i>mn</i></span></p>
+ </td>
+ </tr>
+</table>
+
+<p class=MsoNormal><span lang=EN-US> </span></p>
+
+<p class=MsoNormal><span lang=EN-US>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:</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(with-monad (<i>return-func</i> <i>funcall-func</i>)<br>
+ ;; Here we can use UNIT, FUNCALL!, PROGN! and LET!<br>
+ <i>body1</i> … <i>bodyN</i>)</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The first sub-parameter <i>return-func</i>
+defines a name of the return function. The second sub-parameter <i>funcall-func</i>
+defines a name of the bind function. This macro is expanded to a MACROLET
+saving the same body.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-monad ((unit-func funcall-func)
+&body body)<br>
+ `(macrolet<br>
+ ((unit (a) (list ',unit-func a))<br>
+ (funcall! (k m) (list ',funcall-func k m))<br>
+ (progn! (&body ms) (append '(generic-progn!) '(,funcall-func) ms))<br>
+ (let! (decls m) (list 'generic-let! ',funcall-func decls m)))<br>
+ , at body))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Here the GENERIC-LET! macro is used to process
+the LET! expression in accordance with the stated above definition.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro generic-let! (funcall-func decls m)<br>
+ (reduce #'(lambda (decl m)<br>
+ (destructuring-bind (x e) decl<br>
+ `(,funcall-func #'(lambda (,x) ,m) ,e)))<br>
+ decls<br>
+ :from-end t<br>
+ :initial-value m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The PROGN! expression is processed already
+by the GENERIC-PROGN! helper macro.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro generic-progn! (funcall-func &body
+ms)<br>
+ (reduce #'(lambda (m1 m2)<br>
+ (let ((x (gensym)))<br>
+ `(,funcall-func <br>
+ #'(lambda (, x)<br>
+ (declare (ignore ,x))<br>
+ ,m2)<br>
+ ,m1)))<br>
+ ms<br>
+ :from-end t))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Then the following test expression</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (with-monad (unitf funcallf)<br>
+ (let! ((x1 e1)<br>
+ (x2 e2))<br>
+ (progn! m1 m2<br>
+ (unit (list x1 x2)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>is expanded ultimately to</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (FUNCALLF<br>
+ #'(LAMBDA (X1)<br>
+ (FUNCALLF<br>
+ #'(LAMBDA (X2)<br>
+ (FUNCALLF<br>
+ #'(LAMBDA (#:G983)<br>
+ (DECLARE (IGNORE #:G983))<br>
+ (FUNCALLF<br>
+ #'(LAMBDA (#:G982)<br>
+ (DECLARE (IGNORE #:G982))<br>
+ (UNITF (LIST X1 X2)))<br>
+ M2))<br>
+ M1))<br>
+ E2))<br>
+ E1)</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<table class=MsoTableGrid border=1 cellspacing=0 cellpadding=0 width=650
+ style='width:487.35pt;border-collapse:collapse;border:none'>
+ <tr>
+ <td width=325 valign=top style='width:243.65pt;border:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><span lang=EN-US>Monad</span></p>
+ </td>
+ <td width=325 valign=top style='width:243.7pt;border:solid black 1.0pt;
+ border-left:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><span lang=EN-US>Monad Macro</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=325 valign=top style='width:243.65pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><a href="#_General_Case"><span lang=EN-US>General Case</span></a></p>
+ </td>
+ <td width=325 valign=top style='width:243.7pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><span lang=EN-US>WITH-MONAD</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=325 valign=top style='width:243.65pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><a href="#_The_Identity_Monad"><span lang=EN-US>The Identity Monad</span></a></p>
+ </td>
+ <td width=325 valign=top style='width:243.7pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><span lang=EN-US>WITH-IDENTITY-MONAD</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=325 valign=top style='width:243.65pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><a href="#_The_List_Monad"><span lang=EN-US>The List Monad</span></a></p>
+ </td>
+ <td width=325 valign=top style='width:243.7pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><span lang=EN-US>WITH-LIST-MONAD</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=325 valign=top style='width:243.65pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><a href="#_The_Maybe_Monad"><span lang=EN-US>The Maybe Monad</span></a></p>
+ </td>
+ <td width=325 valign=top style='width:243.7pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><span lang=EN-US>WITH-MAYBE-MONAD</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=325 valign=top style='width:243.65pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><a href="#_The_Reader_Monad"><span lang=EN-US>The Reader Monad</span></a></p>
+ </td>
+ <td width=325 valign=top style='width:243.7pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><span lang=EN-US>WITH-READER-MONAD</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=325 valign=top style='width:243.65pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><a href="#_The_State_Monad"><span lang=EN-US>The State Monad</span></a></p>
+ </td>
+ <td width=325 valign=top style='width:243.7pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><span lang=EN-US>WITH-STATE-MONAD</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=325 valign=top style='width:243.65pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><a href="#_The_Writer_Monad"><span lang=EN-US>The Writer Monad</span></a></p>
+ </td>
+ <td width=325 valign=top style='width:243.7pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><span lang=EN-US>WITH-WRITER-MONAD</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=325 valign=top style='width:243.65pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><a href="#_The_Reader_Monad_1"><span lang=EN-US>The Reader Monad
+ Transformer</span></a></p>
+ </td>
+ <td width=325 valign=top style='width:243.7pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><span lang=EN-US>WITH-READER-MONAD-TRANS</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=325 valign=top style='width:243.65pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><a href="#_The_State_Monad_1"><span lang=EN-US>The State Monad
+ Transformer</span></a></p>
+ </td>
+ <td width=325 valign=top style='width:243.7pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><span lang=EN-US>WITH-STATE-MONAD-TRANS</span></p>
+ </td>
+ </tr>
+ <tr>
+ <td width=325 valign=top style='width:243.65pt;border:solid black 1.0pt;
+ border-top:none;padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><a href="#_The_Writer_Monad_1"><span lang=EN-US>The Writer Monad
+ Transformer</span></a></p>
+ </td>
+ <td width=325 valign=top style='width:243.7pt;border-top:none;border-left:
+ none;border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;
+ padding:0cm 5.4pt 0cm 5.4pt'>
+ <p class=MsoNormal style='margin-bottom:0cm;margin-bottom:.0001pt;line-height:
+ normal'><span lang=EN-US>WITH-WRITER-MONAD-TRANS</span></p>
+ </td>
+ </tr>
+</table>
+
+<p class=MsoNormal><span lang=EN-US> </span></p>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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:</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-my-monad (&body body)<br>
+ `(with-monad (unitf funcallf)<br>
+ , at body))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>where UNITF and FUNCALLF were used as an
+example.</span></p>
+
+<h1><a name="_Toc251846354"></a><a name="_Toc251505166"></a><a
+name="_Toc251505063"><span lang=EN-US>Bind Macros</span></a></h1>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro universal-progn! (&body ms)<br>
+ (reduce #'(lambda (m1 m2)<br>
+ (let ((x (gensym)))<br>
+ `(funcall!<br>
+ #'(lambda (,x)<br>
+ (declare (ignore ,x))<br>
+ ,m2)<br>
+ ,m1)))<br>
+ ms<br>
+ :from-end t))</span></p>
+
+<p class=a><span lang=EN-US>(defmacro universal-let! (decls m)<b><br>
+</b> (reduce #'(lambda (decl m)<b><br>
+</b> (destructuring-bind (x e) decl<b><br>
+</b> `(funcall! #'(lambda (,x) ,m) ,e)))<b><br>
+</b> decls<b><br>
+</b> :from-end t<b><br>
+</b> :initial-value m)) </span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Nevertheless, there is one subtle
+optimization issue related to the order of arguments of the FUNCALL! macro.
+During the macro expansion of expression</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (let! ((x e)) m)</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>macro UNIVERSAL-LET! will generate
+ultimately for the most of monads described in this article something like</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (let ((k #’(lambda (x) m))) ; save the first
+argument of FUNCALL! <br>
+ …<br>
+ (let ((a (f e))) ; use the second argument of FUNCALL!<br>
+ (funcall k a))<br>
+ …)</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>But I’m not sure that any Lisp compiler is
+able to optimize it to the following equivalent code that would be more
+efficient</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> …<br>
+ (let ((x (f e)))<br>
+ m)<br>
+ …</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> …<br>
+ (let ((a (f e)))<br>
+ (funcall<br>
+ #’(lambda (x) m)<br>
+ a))<br>
+ …</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<h1><a name="_Toc251846355"></a><a name="_Toc251505167"></a><a
+name="_Toc251505064"></a><a name="_The_Identity_Monad"></a><span lang=EN-US>The
+Identity Monad</span></h1>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-identity-monad (&body body)<br>
+ `(with-monad (identity funcall)<br>
+ , at body)</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>But there is a much more efficient
+implementation:</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-identity-monad (&body body)<br>
+ `(macrolet<br>
+ ((unit (a) a)<br>
+ (funcall! (k m) (list 'funcall k m))<br>
+ (progn! (&body ms) (append '(progn) ms))<br>
+ (let! (decls m) (list 'let* decls m)))<br>
+ , at body))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Remembering about this monad, it is easy to
+memorize names FUNCALL!, PROGN! and LET!.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>Our test expression</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (with-identity-monad<br>
+ (let! ((x1 e1)<br>
+ (x2 e2))<br>
+ (progn! m1 m2<br>
+ (unit (list x1 x2)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>is expanded to</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (LET* ((X1 E1) (X2 E2))<br>
+ (PROGN M1 M2 (LIST X1 X2)))</span></p>
+
+</div>
+
+<h1><a name="_Toc251846356"></a><a name="_Toc251505168"></a><a
+name="_Toc251505065"></a><a name="_The_List_Monad"></a><span lang=EN-US>The
+List Monad</span></h1>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>A monad value is just a list. Following the
+idiomatic definition, we can write the UNIT and FUNCALL! macro prototypes:</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro list-unit (a)<br>
+ `(list ,a))<br>
+<br>
+(defmacro list-funcall! (k m)<br>
+ `(reduce #’append (mapcar ,k ,m)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Please note that NIL is also a value of the
+list monad. We’ll use this fact further.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>Here is a definition of the PROGN! macro
+prototype.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro list-progn! (&body ms)<br>
+ (reduce <br>
+ #'(lambda (m1 m2)<br>
+ (let ((x (gensym)))<br>
+ `(loop for ,x in ,m1 append ,m2)))<br>
+ ms<br>
+ :from-end t))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The LET! macro prototype can be implemented
+similarly and also without use of the lambda.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro list-let! (decls m)<br>
+ (reduce <br>
+ #'(lambda (decl m)<br>
+ (destructuring-bind (x e) decl<br>
+ `(loop for ,x in ,e append ,m)))<br>
+ decls<br>
+ :from-end t<br>
+ :initial-value m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Here we replace each variable binding with
+the corresponded loop. It should generate an efficient enough code.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>Macros UNIT, FUNCALL!, PROGN! and LET! actually
+are defined in a MACROLET implemented by the WITH-LIST-MONAD macro.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-list-monad (&body body)<br>
+ `(macrolet<br>
+ ((unit (a) `(list ,a))<br>
+ (funcall! (k m) `(reduce #'append (mapcar ,k ,m)))<br>
+ (progn! (&body ms) (append '(list-progn!) ms))<br>
+ (let! (decls m) (list 'list-let! decls m)))<br>
+ , at body))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The same test example</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (with-list-monad<br>
+ (let! ((x1 e1)<br>
+ (x2 e2))<br>
+ (progn! m1 m2<br>
+ (unit (list x1 x2)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>is now expanded to</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(LOOP FOR X1 IN E1<br>
+ APPEND (LOOP FOR X2 IN E2<br>
+ APPEND (LOOP FOR #:G1030 IN M1<br>
+ APPEND (LOOP FOR #:G1029 IN M2<br>
+ APPEND (LIST (LIST X1 X2))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>We can ask for something more practical:</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>CL-USER> (with-list-monad<br>
+ (let ((numbers '(1 2 3 4 5 6 7 8 9 10)))<br>
+ (let! ((x numbers)<br>
+ (y numbers)<br>
+ (z numbers))<br>
+ (if (= (+ (* x x) (* y y)) (* z z))<br>
+ (unit (list x y z))))))<br>
+<br>
+((3 4 5) (4 3 5) (6 8 10) (8 6 10))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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 <i>numbers</i> were an empty list then the
+topmost loop would immediately return NIL.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>Also we can define the following function <i>perms</i>
+that produces a list of permutations of a given list.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defun perms (xs)<br>
+ (with-list-monad<br>
+ (if (null xs)<br>
+ (unit nil)<br>
+ (let! ((y xs)<br>
+ (ys (perms (remove y xs :count 1))))<br>
+ (unit (cons y ys))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Now we can test it.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>CL-USER> (perms '(1 2 3))<br>
+((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))</span></p>
+
+</div>
+
+<h1><a name="_Toc251846357"></a><a name="_Toc251505169"></a><a
+name="_Toc251505066"></a><a name="_The_Maybe_Monad"></a><span lang=EN-US>The
+Maybe Monad</span></h1>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The constructor, getters and predicates for
+this data type are defined below.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro make-maybe (&key (just nil
+just-supplied-p))<br>
+ (if just-supplied-p `(cons ,just nil)))<br>
+<br>
+(defmacro maybe-just (a)<br>
+ `(car ,a))<br>
+<br>
+(defmacro maybe-nil ()<br>
+ nil)<br>
+<br>
+(defmacro maybe-just-p (m)<br>
+ `(consp ,m))<br>
+<br>
+(defmacro maybe-nil-p (m)<br>
+ `(null ,m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The prototypes of the basic return and bind
+macros can be defined in the following way.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro maybe-unit (a)<br>
+ `(make-maybe :just ,a))<br>
+<br>
+(defmacro maybe-funcall! (k m)<br>
+ (let ((xk (gensym))<br>
+ (xm (gensym)))<br>
+ `(let ((,xk ,k)<br>
+ (,xm ,m))<br>
+ (if (maybe-nil-p ,xm)<br>
+ (make-maybe)<br>
+ (funcall ,xk (maybe-just ,xm))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The key point is the IF expression that
+cuts the further computation if the result of the former one is NIL.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>Based on these macros we can build their
+counterpart PROGN!.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro maybe-progn! (&body ms)<br>
+ (reduce <br>
+ #'(lambda (m1 m2)<br>
+ `(if (maybe-nil-p ,m1)<br>
+ (make-maybe)<br>
+ ,m2))<br>
+ ms<br>
+ :from-end t))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The LET! macro is similar but it allows the
+programmer to bind variables within one computation.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro maybe-let! (decls m)<br>
+ (reduce <br>
+ #'(lambda (decl m)<br>
+ (destructuring-bind (x e) decl<br>
+ (let ((xe (gensym)))<br>
+ `(let ((,xe ,e))<br>
+ (if (maybe-nil-p ,xe)<br>
+ (make-maybe)<br>
+ (let ((,x (maybe-just ,xe)))<br>
+ ,m))))))<br>
+ decls<br>
+ :from-end t<br>
+ :initial-value m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>In the three cases we see the cutting IF
+expressions. They stop immediately the computation right after discovering a
+failure.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-maybe-monad (&body body)<br>
+ `(macrolet<br>
+ ((unit (a) (list 'maybe-unit a))<br>
+ (funcall! (k m) (list 'maybe-funcall! k m))<br>
+ (progn! (&body ms) (append '(maybe-progn!) ms))<br>
+ (let! (decls m) (list 'maybe-let! decls m)))<br>
+ , at body))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Our old example</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (with-maybe-monad<br>
+ (let! ((x1 e1)<br>
+ (x2 e2))<br>
+ (progn! m1 m2<br>
+ (unit (list x1 x2)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>is expanded to</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (LET ((#:G1051 E1))<br>
+ (IF (NULL #:G1051) NIL<br>
+ (LET ((X1 (CAR #:G1051)))<br>
+ (LET ((#:G1050 E2))<br>
+ (IF (NULL #:G1050) NIL<br>
+ (LET ((X2 (CAR #:G1050)))<br>
+ (IF (NULL M1) NIL<br>
+ (IF (NULL M2) NIL (CONS (LIST X1 X2) NIL)))))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Now we can consider something more
+illustrative</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>CL-USER> (with-maybe-monad<br>
+ (progn! (progn <br>
+ (format t "Step 1.")<br>
+ (make-maybe :just 'OK))<br>
+ (make-maybe) ; NIL – failure<br>
+ (progn <br>
+ (format t "Step 2.")<br>
+ (make-maybe :just 'OK))))<br>
+<br>
+Step 1.<br>
+NIL</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Moreover, SBCL will warn about an unreachable
+code during compilation if we’ll try to define such a function!</span></p>
+
+<h1><a name="_Toc251846358"></a><a name="_Toc251505170"></a><a
+name="_Toc251505067"></a><a name="_The_Reader_Monad"></a><span lang=EN-US>The
+Reader Monad</span></h1>
+
+<p class=MsoNormal><span lang=EN-US>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</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>import Control.Monad<br>
+<br>
+newtype Reader r a = Reader {runReader :: r -> a}<br>
+<br>
+instance Monad (Reader r) where<br>
+<br>
+ return a = Reader (\r -> a)<br>
+<br>
+ m >>= k = Reader (\r -> <br>
+ let a = runReader m r<br>
+ m' = k a<br>
+ in runReader m' r)<br>
+<br>
+read :: Reader r r<br>
+read = Reader (\r -> r)</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>In accordance with this definition I’ll
+create a monad macro WITH-READER-MONAD.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The UNIT macro prototype is simple enough.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro reader-unit (a)<br>
+ (let ((r (gensym)))<br>
+ `#'(lambda (,r)<br>
+ (declare (ignore ,r))<br>
+ ,a)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The FUNCALL! macro prototype is crucial for
+understanding the monad macro.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro reader-funcall! (k m)<br>
+ (let ((r (gensym))<br>
+ (a (gensym))<br>
+ (kg (gensym)))<br>
+ `#'(lambda (,r)<br>
+ (let ((,kg ,k)<br>
+ (,a (funcall ,m ,r)))<br>
+ (funcall (funcall ,kg ,a) ,r)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>There is a subtle thing. Parameter <i>k</i>
+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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>Also please note that value <i>m</i>, 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</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (funcall #’(lambda (x) f) r)</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>which can be efficiently optimized by the
+compiler to</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (let ((x r)) f)</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The LET! macro prototype is more efficient
+than FUNCALL! as one of the FUNCALLs becomes unnecessary.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro reader-let! (decls m)<br>
+ (reduce #'(lambda (decl m)<br>
+ (destructuring-bind (x e) decl<br>
+ (let ((r (gensym)))<br>
+ `#'(lambda (,r)<br>
+ (let ((,x (funcall ,e ,r)))<br>
+ (funcall ,m ,r))))))<br>
+ decls<br>
+ :from-end t<br>
+ :initial-value m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Here like expression <i>e</i> expression <i>m</i>
+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 <i>m</i> 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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The PROGN! macro prototype is more simple
+as we don’t bind variables.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro reader-progn! (&body ms)<br>
+ (reduce #'(lambda (m1 m2)<br>
+ (let ((r (gensym)))<br>
+ `#'(lambda (,r)<br>
+ (funcall ,m1 ,r)<br>
+ (funcall ,m2 ,r))))<br>
+ ms<br>
+ :from-end t))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Again, if the s-expression for <i>m1</i>
+and <i>m2</i> will be accessible then the Lisp compiler will have good chances
+to generate a more optimal code.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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 <i>read</i> value
+defined above in Haskell. The macro prototype is as follows.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro reader-read! ()<br>
+ (let ((r (gensym)))<br>
+ `#'(lambda (,r) ,r)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro reader-run! (m r)<br>
+ `(funcall ,m ,r))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The value returned is a result of the monad
+computation.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>Macros READ!, RUN!, UNIT, FUNCALL!, PROGN!
+and LET! are implemented as a MACROLET defined by the WITH-READER-MONAD macro.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-reader-monad (&body body)<br>
+ `(macrolet<br>
+ ((unit (a) (list 'reader-unit a))<br>
+ (funcall! (k m) (list 'reader-funcall! k m))<br>
+ (progn! (&body ms) (append '(reader-progn!) ms))<br>
+ (let! (decls m) (list 'reader-let! decls m))<br>
+ (read! () (list 'reader-read!))<br>
+ (run! (m r) (list 'reader-run! m r)))<br>
+ , at body))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Now we can take our old test example</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (with-reader-monad<br>
+ (let! ((x1 e1)<br>
+ (x2 e2))<br>
+ (progn! m1 m2<br>
+ (unit (list x1 x2)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>and look at the result of the macro
+expansion.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> #'(LAMBDA (#:G788)<br>
+ (LET ((X1 (FUNCALL E1 #:G788)))<br>
+ (FUNCALL<br>
+ #'(LAMBDA (#:G787)<br>
+ (LET ((X2 (FUNCALL E2 #:G787)))<br>
+ (FUNCALL<br>
+ #'(LAMBDA (#:G790)<br>
+ (FUNCALL M1 #:G790)<br>
+ (FUNCALL<br>
+ #'(LAMBDA (#:G789)<br>
+ (FUNCALL M2 #:G789)<br>
+ (FUNCALL<br>
+ #'(LAMBDA (#:G791)<br>
+ (DECLARE (IGNORE #:G791))<br>
+ (LIST X1 X2))<br>
+ #:G789))<br>
+ #:G790))<br>
+ #:G787)))<br>
+ #:G788)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>We can see that there are many LAMBDAs and
+FUNCALLs bound together. A good Lisp compiler must generate a rather efficient
+code.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>Here is a small test</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defun reader-test ()<br>
+ (with-reader-monad<br>
+ (run!<br>
+ (let! ((x (read!)))<br>
+ (progn<br>
+ (format t "x=~a~%" x)<br>
+ (unit 'ok)))<br>
+ 10)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>and this is its output.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>CL-USER> (reader-test)<br>
+x=10<br>
+OK</span></p>
+
+</div>
+
+<h1><a name="_Toc251505171"></a><a name="_Toc251505068"></a><a
+name="_Toc251846359"></a><a name="_The_State_Monad"></a><span lang=EN-US>The
+State Monad</span></h1>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>I’ll use the next definition written in
+Haskell.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>import Control.Monad<br>
+<br>
+newtype State st a = State {runState :: st -> (a, st)}<br>
+<br>
+instance Monad (State st) where<br>
+<br>
+ return a = State (\st -> (a, st))<br>
+<br>
+ m >>= k = State (\st -> <br>
+ let (a, st') = runState m st<br>
+ m' = k a<br>
+ in runState m' st')<br>
+<br>
+get :: State st st<br>
+get = State (\st -> (st, st))<br>
+<br>
+put :: st -> State st ()<br>
+put st' = State (\_ -> ((), st'))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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 <i>get</i> function.
+The PUT! macro will be an analog of the <i>put</i> function. The RUN! macro
+will play a role of the <i>runState</i> function.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>First of all, I define utility macros.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro make-state (a st)<br>
+ `(cons ,a ,st))<br>
+<br>
+(defmacro state-value (m)<br>
+ `(car ,m))<br>
+<br>
+(defmacro state-state (m)<br>
+ `(cdr ,m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The UNIT macro prototype is simple.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro state-unit (a)<br>
+ (let ((st (gensym)))<br>
+ `#'(lambda (,st)<br>
+ (make-state ,a ,st))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Please note that we evaluate <i>a</i>
+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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The FUNCALL! macro prototype follows the
+definition of the bind function.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro state-funcall! (k m)<br>
+ (let ((st (gensym))<br>
+ (p (gensym))<br>
+ (a (gensym))<br>
+ (kg (gensym)))<br>
+ `#'(lambda (,st)<br>
+ (let ((,kg ,k))<br>
+ (let ((,p (funcall ,m ,st)))<br>
+ (let ((,a (state-value ,p)))<br>
+ (funcall (funcall ,kg ,a)<br>
+ (state-state ,p))))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>All notes that I did for the FUNCALL! macro
+of the Reader monad are applicable here. Being a monad value, expression <i>m</i>
+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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The LET! macro prototype generates a more
+optimal code than FUNCALL!.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro state-let! (decls m)<br>
+ (reduce #'(lambda (decl m)<br>
+ (destructuring-bind (x e) decl<br>
+ (let ((st (gensym))<br>
+ (p (gensym)))<br>
+ `#'(lambda (,st)<br>
+ (let ((,p (funcall ,e ,st)))<br>
+ (let ((,x (state-value ,p)))<br>
+ (funcall ,m (state-state ,p))))))))<br>
+ decls<br>
+ :from-end t<br>
+ :initial-value m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>If we create a multi-level LET! expression
+then <i>m</i> 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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The PROGN! macro prototype is more simple.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro state-progn! (&body ms)<br>
+ (reduce #'(lambda (m1 m2)<br>
+ (let ((st (gensym))<br>
+ (p (gensym)))<br>
+ `#'(lambda (,st)<br>
+ (let ((,p (funcall ,m1 ,st)))<br>
+ (funcall ,m2 (state-state ,p))))))<br>
+ ms<br>
+ :from-end t))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro state-run! (m init-st)<br>
+ (let ((p (gensym)))<br>
+ `(let ((,p (funcall ,m ,init-st)))<br>
+ (list (state-value ,p)<br>
+ (state-state ,p)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro state-get! ()<br>
+ (let ((st (gensym)))<br>
+ `#'(lambda (,st)<br>
+ (make-state ,st ,st))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro state-put! (new-st)<br>
+ (let ((st (gensym)))<br>
+ `#'(lambda (,st)<br>
+ (declare (ignore ,st))<br>
+ (make-state nil ,new-st))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Macros RUN!, GET!, PUT!, UNIT, FUNCALL!,
+LET! and PROGN! are implemented as a MACROLET defined by the WITH-STATE-MONAD
+macro.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-state-monad (&body body)<br>
+ `(macrolet<br>
+ ((unit (a) (list 'state-unit a))<br>
+ (funcall! (k m) (list 'state-funcall! k m))<br>
+ (progn! (&body ms) (append '(state-progn!) ms))<br>
+ (let! (decls m) (list 'state-let! decls m))<br>
+ (get! () (list 'state-get!))<br>
+ (put! (new-st) (list 'state-put! new-st))<br>
+ (run! (m init-st) (list 'state-run! m init-st)))<br>
+ , at body))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>For our old test example</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (with-state-monad<br>
+ (let! ((x1 e1)<br>
+ (x2 e2))<br>
+ (progn! m1 m2<br>
+ (unit (list x1 x2)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>the macro expansion looks like</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> #'(LAMBDA (#:G1696)<br>
+ (LET ((#:G1697 (FUNCALL E1 #:G1696)))<br>
+ (LET ((X1 (CAR #:G1697)))<br>
+ (FUNCALL<br>
+ #'(LAMBDA (#:G1694)<br>
+ (LET ((#:G1695 (FUNCALL E2 #:G1694)))<br>
+ (LET ((X2 (CAR #:G1695)))<br>
+ (FUNCALL<br>
+ #'(LAMBDA (#:G1700)<br>
+ (LET ((#:G1701 (FUNCALL M1 #:G1700)))<br>
+ (FUNCALL<br>
+ #'(LAMBDA (#:G1698)<br>
+ (LET ((#:G1699 (FUNCALL M2 #:G1698)))<br>
+ (FUNCALL<br>
+ #'(LAMBDA (#:G1702)<br>
+ (CONS (LIST X1 X2) #:G1702))<br>
+ (CDR #:G1699))))<br>
+ (CDR #:G1701))))<br>
+ (CDR #:G1695)))))<br>
+ (CDR #:G1697)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defun state-test (tree)<br>
+ (labels<br>
+ ((order (tree)<br>
+ (with-state-monad<br>
+ (cond ((null tree) (unit nil))<br>
+ ((consp tree)<br>
+ (let! ((t1 (order (car tree)))<br>
+ (t2 (order (cdr tree))))<br>
+ (unit (cons t1 t2))))<br>
+ (t <br>
+ (let! ((n (get!)))<br>
+ (let ((new-n (+ n 1)))<br>
+ (progn!<br>
+ (put! new-n)<br>
+ (unit (cons tree new-n))))))))))<br>
+ (destructuring-bind (new-tree new-state)<br>
+ (with-state-monad<br>
+ (run! (order tree) 0))<br>
+ (format t "Item count=~a~%" new-state)<br>
+ (format t "New tree=~a~%" new-tree))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Now we can launch a test.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>CL-USER> (state-test '(((5 2) 7 4) 5 9))<br>
+Item count=6<br>
+New tree=((((5 . 1) (2 . 2)) (7 . 3) (4 . 4)) (5 . 5) (9 . 6))<br>
+NIL</span></p>
+
+</div>
+
+<h1><a name="_Toc251846360"></a><a name="_The_Writer_Monad"></a><span
+lang=EN-US>The Writer Monad</span></h1>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>I will use the following definition written
+in Haskell.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>import Control.Monad<br>
+<br>
+newtype Writer w a = Writer (a, [w] -> [w])<br>
+<br>
+runWriter :: Writer w a -> (a, [w])<br>
+runWriter (Writer (a, f)) = (a, f [])<br>
+<br>
+write :: w -> Writer w ()<br>
+write w = Writer ((), \xs -> w : xs)<br>
+<br>
+writeList :: [w] -> Writer w ()<br>
+writeList ws = Writer ((), \xs -> ws ++ xs)<br>
+<br>
+instance Monad (Writer w) where<br>
+<br>
+ return a = Writer (a, id)<br>
+<br>
+ (Writer (a, f)) >>= k =<br>
+ let Writer (a', f') = k a<br>
+ in Writer (a', f . f')</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Actually, I will use a more efficient
+representation of the functions. We can note that the return function uses <i>id</i>,
+but the bind function always creates a composition of two functions (<i>f . f’</i>).
+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 <i>write</i> and <i>writeList</i> functions are called
+rarely, i.e. when <i>f’</i> is just the <i>id</i> function.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>I’ll begin with utilities.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro make-writer (a fun)<br>
+ `(cons ,a ,fun))<br>
+<br>
+(defmacro writer-value (m)<br>
+ `(car ,m))<br>
+<br>
+(defmacro writer-fun (m)<br>
+ `(cdr ,m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The next macro creates a composition of the
+two specified nullable functions, where NIL means the IDENTITY function.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-compose (f g)<br>
+ ;; There are high chances that g is NIL<br>
+ (let ((fs (gensym))<br>
+ (gs (gensym)))<br>
+ `(let ((,fs ,f)<br>
+ (,gs ,g))<br>
+ (cond ((null ,gs) ,fs) ; check it first<br>
+ ((null ,fs) ,gs)<br>
+ (t #'(lambda (x)<br>
+ (funcall ,fs<br>
+ (funcall ,gs x))))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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 <i>write</i> and <i>writeList</i> functions respectively
+and they will be used for writing a log. The RUN! macro will be an analog of
+the <i>runWriter</i> 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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The WRITE! macro saves the specified values
+in the log. It returns NIL wrapped in the monad like that how the <i>write</i>
+function returns <i>Writer w ()</i>. Its prototype is as follows.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-write! (&body ws)<br>
+ (if (= 1 (length ws))<br>
+ ;; An optimized case<br>
+ (let ((w (nth 0 ws))<br>
+ (v (gensym)))<br>
+ `(make-writer nil<br>
+ (let ((,v ,w))<br>
+ #'(lambda (xs) (cons ,v xs)))))<br>
+ ;; A general case<br>
+ (let ((vs (gensym)))<br>
+ `(make-writer nil<br>
+ (let ((,vs (list , at ws)))<br>
+ #'(lambda (xs)<br>
+ (append ,vs xs)))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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 <i>shows</i> function from Haskell.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-write-list! (&body wss)<br>
+ (if (= 1 (length wss))<br>
+ ;; An optimized case<br>
+ (let ((ws (nth 0 wss))<br>
+ (vs (gensym)))<br>
+ `(make-writer nil<br>
+ (let ((,vs ,ws))<br>
+ #'(lambda (xs) (append ,vs xs)))))<br>
+ ;; A general case<br>
+ (let ((vss (gensym)))<br>
+ `(make-writer nil<br>
+ (let ((,vss (list , at wss)))<br>
+ #'(lambda (xs)<br>
+ (reduce #'append ,vss<br>
+ :from-end t<br>
+ :initial-value xs)))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-run! (m)<br>
+ (let ((x (gensym))<br>
+ (fun (gensym)))<br>
+ `(let ((,x ,m))<br>
+ (list (writer-value ,x)<br>
+ (let ((,fun (writer-fun ,x)))<br>
+ (if (not (null ,fun))<br>
+ (funcall ,fun nil)))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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!</span></p>
+
+<p class=MsoNormal><span lang=EN-US>We consider NIL as an optimized
+representation of the IDENTITY function. The UNIT macro prototype uses this
+fact as the log remains unmodified.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-unit (a)<br>
+ `(make-writer ,a nil))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The FUNCALL! macro is more complicated.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-funcall! (k m)<br>
+ (let ((ks (gensym))<br>
+ (ms (gensym))<br>
+ (a (gensym))<br>
+ (ka (gensym)))<br>
+ `(let* ((,ks ,k) ; save it first<br>
+ (,ms ,m)<br>
+ (,a (writer-value ,ms))<br>
+ (,ka (funcall ,ks ,a)))<br>
+ (make-writer (writer-value ,ka)<br>
+ (writer-compose (writer-fun ,ms)<br>
+ (writer-fun ,ka))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>As usual, based on this macro we can write
+a more optimal definition of the LET! macro prototype which has no FUNCALL at
+all.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-let! (decls m)<br>
+ (reduce <br>
+ #'(lambda (decl m)<br>
+ (destructuring-bind (x e) decl<br>
+ (let ((es (gensym))<br>
+ (ms (gensym)))<br>
+ `(let* ((,es ,e)<br>
+ (,x (writer-value ,es))<br>
+ (,ms ,m)) ; depends on x!<br>
+ (make-writer (writer-value ,ms)<br>
+ (writer-compose (writer-fun ,es)<br>
+ (writer-fun ,ms)))))))<br>
+ decls<br>
+ :from-end t<br>
+ :initial-value m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The PROGN! macro prototype is even more
+simple as there is no variable binding. But we have to compose the log
+functions, though.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-progn! (&body ms)<br>
+ (reduce <br>
+ #'(lambda (m1 m2)<br>
+ (let ((m1s (gensym))<br>
+ (m2s (gensym)))<br>
+ `(let ((,m1s ,m1)<br>
+ (,m2s ,m2))<br>
+ (make-writer (writer-value ,m2s)<br>
+ (writer-compose (writer-fun ,m1s)<br>
+ (writer-fun ,m2s))))))<br>
+ ms<br>
+ :from-end t))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Macros WRITE!, WRITE-LIST!, RUN!, UNIT,
+FUNCALL!, PROGN! and LET! are implemented as a MACROLET defined by macro
+WITH-WRITER-MONAD.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-writer-monad (&body body)<br>
+ `(macrolet<br>
+ ((unit (a) (list 'writer-unit a))<br>
+ (funcall! (k m) (list 'writer-funcall! k m))<br>
+ (progn! (&body ms) (append '(writer-progn!) ms))<br>
+ (let! (decls m) (list 'writer-let! decls m))<br>
+ (write! (&body ws) (append '(writer-write!) ws))<br>
+ (write-list! (&body wss) (append '(writer-write-list!) wss))<br>
+ (run! (m) (list 'writer-run! m)))<br>
+ , at body))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Now we can take our old example</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (with-writer-monad<br>
+ (let! ((x1 e1)<br>
+ (x2 e2))<br>
+ (progn! m1 m2<br>
+ (unit (list x1 x2)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>and look at its macro expansion.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (LET* ((#:G1297 E1)<br>
+ (X1 (CAR #:G1297))<br>
+ (#:G1298<br>
+ (LET* ((#:G1295 E2)<br>
+ (X2 (CAR #:G1295))<br>
+ (#:G1296<br>
+ (LET ((#:G1301 M1)<br>
+ (#:G1302<br>
+ (LET ((#:G1299 M2) (#:G1300 (CONS (LIST X1 X2) NIL)))<br>
+ (CONS (CAR #:G1300)<br>
+ (LET ((#:G1303 (CDR #:G1299))<br>
+ (#:G1304 (CDR #:G1300)))<br>
+ (IF (NULL #:G1304) (PROGN #:G1303)<br>
+ (IF (NULL #:G1303) (PROGN #:G1304)<br>
+ (THE T<br>
+ (PROGN<br>
+ #'(LAMBDA (X)<br>
+ (FUNCALL #:G1303<br>
+ (FUNCALL #:G1304<br>
+
+X))))))))))))<br>
+ (CONS (CAR #:G1302)<br>
+ (LET ((#:G1305 (CDR #:G1301)) (#:G1306 (CDR
+#:G1302)))<br>
+ (IF (NULL #:G1306) (PROGN #:G1305)<br>
+ (IF (NULL #:G1305) (PROGN #:G1306)<br>
+ (THE T<br>
+ (PROGN<br>
+ #'(LAMBDA (X)<br>
+ (FUNCALL #:G1305<br>
+ (FUNCALL #:G1306<br>
+ X))))))))))))<br>
+ (CONS (CAR #:G1296)<br>
+ (LET ((#:G1307 (CDR #:G1295)) (#:G1308 (CDR #:G1296)))<br>
+ (IF (NULL #:G1308) (PROGN #:G1307)<br>
+ (IF (NULL #:G1307) (PROGN #:G1308)<br>
+ (THE T<br>
+ (PROGN<br>
+ #'(LAMBDA (X)<br>
+ (FUNCALL #:G1307<br>
+ (FUNCALL #:G1308 X))))))))))))<br>
+ (CONS (CAR #:G1298)<br>
+ (LET ((#:G1309 (CDR #:G1297)) (#:G1310 (CDR #:G1298)))<br>
+ (IF (NULL #:G1310) (PROGN #:G1309)<br>
+ (IF (NULL #:G1309) (PROGN #:G1310)<br>
+ (THE T<br>
+ (PROGN<br>
+ #'(LAMBDA (X)<br>
+ (FUNCALL #:G1309 (FUNCALL #:G1310 X))))))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The next example illustrates the use of the
+WITH-WRITER-MONAD macro.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defun writer-test ()<br>
+ (destructuring-bind (a log)<br>
+ (with-writer-monad<br>
+ (run!<br>
+ (progn!<br>
+ (write! 1)<br>
+ (write! 2 3 4)<br>
+ (write-list! '(5 6))<br>
+ (write-list! '(7) '(8) '(9))<br>
+ (unit 'ok))))<br>
+ (format t "Computed value = ~a~%" a)<br>
+ (format t "Written log = ~a~%" log)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>This is its output.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>CL-USER> (writer-test)<br>
+Computed value = OK<br>
+Written log = (1 2 3 4 5 6 7 8 9)<br>
+NIL</span></p>
+
+</div>
+
+<h1><a name="_Toc251846361"></a><a name="_Toc251505172"></a><a
+name="_Toc251505069"></a><a name="_Monad_Transformers"></a><span lang=EN-US>Monad
+Transformers</span></h1>
+
+<p class=MsoNormal><span lang=EN-US>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 <i>lift</i> function
+in Haskell.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>class MonadTrans where<br>
+ lift :: (Monad m) => m a -> t m a</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>For example, we can write:</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(with-reader-monad-trans (with-writer-monad)<br>
+ <br>
+ ;; It works within the WITH-READER-MONAD-TRANS macro<br>
+<br>
+ (let! ((x (read!)))<br>
+<br>
+ ;; It calls WRITE! within the WITH-WRITER-MONAD macro<br>
+<br>
+ (lift!<br>
+ (with-writer-monad<br>
+ (write! x)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>For this case we can create a separate
+monad macro and define the WRITE! macro on more high level using LIFT!</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-reader-writer-monad (&body body)<br>
+ `(with-reader-monad-trans (with-writer-monad)<br>
+ (macrolet<br>
+ ((write! (&body bs) <br>
+ `(lift!<br>
+ (with-writer-monad<br>
+ (write! , at bs)))))<br>
+ , at body)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The monad transformer macros can be nested.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(with-reader-monad-trans <br>
+ (with-writer-monad-trans<br>
+ (with-maybe-monad))<br>
+<br>
+ (progn!<br>
+<br>
+ ;; It evaluates (f x) within<br>
+ ;; the WITH-WRITER-MONAD-TRANS macro<br>
+<br>
+ (lift!<br>
+ (with-writer-monad-trans (with-maybe-monad)<br>
+ (f x)))<br>
+<br>
+ ;; It evaluates (g x) within<br>
+ ;; the WITH-MAYBE-MONAD macro<br>
+<br>
+ (lift!<br>
+ (lift!<br>
+ (with-maybe-monad<br>
+ (g x))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>In the next sections you will see how the
+monad transformer macros can be implemented. All examples follow a common
+pattern.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-some-monad-trans <br>
+ (inner-monad &body body)<br>
+<br>
+ `(with-monad-trans<br>
+ (with-some-monad-trans ,inner-monad)<br>
+<br>
+ (macrolet<br>
+ ;; Definitions of UNIT, FUNCALL!, PROGN!, LET!<br>
+ ;; and possibly some other macros<br>
+<br>
+ , at body)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Note how the definition of
+WITH-SOME-MONAD-TRANS recursively refers to itself. It is important.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(with-some-monad-trans (with-inner-monad)<br>
+<br>
+ ;; Here the WITH-SOME-MONAD-TRANS macro is active<br>
+<br>
+ (with-inner-monad-trans (unique-id)<br>
+<br>
+ ;; Here the WITH-INNER-MONAD macro is active, i.e.<br>
+ ;; a macro specified in the parameter<br>
+<br>
+ (with-outer-monad-trans (unique-id)<br>
+<br>
+ ;; Here the WITH-SOME-MONAD-TRANS macro <br>
+ ;; is active again<br>
+ <br>
+ ...)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>This scheme allows the implementer to
+switch between the outer and inner monad macros.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The WITH-MONAD-TRANS macro has the
+following definition.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-monad-trans (outer-monad &body
+body)<br>
+ (let ((inner-monad (cadr outer-monad)))<br>
+ `(macrolet<br>
+ ((with-inner-monad-trans (id &body bs)<br>
+ (append '(with-inner-monad-prototype)<br>
+ (list ',outer-monad)<br>
+ (list ',inner-monad)<br>
+ (list id)<br>
+ bs))<br>
+ (with-outer-monad-trans (id &body bs)<br>
+ (append id bs)))<br>
+ , at body)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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 <i>id</i>. 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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-inner-monad-prototype <br>
+ (outer-monad inner-monad id &body body)<br>
+ `(macrolet ((, at id (&body bs) (append ',outer-monad bs)))<br>
+ (, at inner-monad<br>
+ , at body)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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 <i>id</i>. 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 <i>id</i> parameter is supposed to be unique.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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. </span></p>
+
+<p class=MsoNormal><span lang=EN-US>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 </span><a href="#_Minimizing_a_Compilation"><span
+lang=EN-US>Reducing Monad Macros</span></a><span lang=EN-US>.</span></p>
+
+<h1><a name="_Toc251846362"></a><a name="_Toc251505173"></a><a
+name="_Toc251505070"><span lang=EN-US>Inner Monad Macros</span></a></h1>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>So, the INNER-UNIT macro prototype is as
+follows.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro generic-inner-unit (a)<br>
+ (let ((id (gensym)))<br>
+ `(with-inner-monad-trans (,id)<br>
+ (unit <br>
+ (with-outer-monad-trans (,id)<br>
+ ,a)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Please note that expression <i>a</i> is
+evaluated within the outer monad. It will be a general rule.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The INNER-FUNCALL! macro prototype is
+similar.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro generic-inner-funcall! (k m)<br>
+ (let ((id (gensym)))<br>
+ `(with-inner-monad-trans (,id)<br>
+ (funcall!<br>
+ (with-outer-monad-trans (,id) ,k)<br>
+ (with-outer-monad-trans (,id) ,m)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The INNER-LET! macro prototype is
+analogous.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro generic-inner-let! (decls m)<br>
+ (reduce <br>
+ #'(lambda (decl m)<br>
+ (destructuring-bind (x e) decl<br>
+ (let ((id (gensym)))<br>
+ `(with-inner-monad-trans (,id)<br>
+ (let! ((,x (with-outer-monad-trans (,id) ,e)))<br>
+ (with-outer-monad-trans (,id) ,m))))))<br>
+ decls<br>
+ :from-end t<br>
+ :initial-value m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The INNER-PROGN! macro prototype is more
+optimal.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro generic-inner-progn! (&body ms)<br>
+ (let ((id (gensym)))<br>
+ (let ((outer-ms (loop for m in ms collect<br>
+ `(with-outer-monad-trans (,id) ,m))))<br>
+ `(with-inner-monad-trans (,id)<br>
+ (progn! , at outer-ms)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-monad-trans (outer-monad &body
+body)<br>
+ (let ((inner-monad (cadr outer-monad)))<br>
+ `(macrolet<br>
+ ((with-inner-monad-trans (id &body bs)<br>
+ (append '(with-inner-monad-prototype)<br>
+ (list ',outer-monad)<br>
+ (list ',inner-monad)<br>
+ (list id)<br>
+ bs))<br>
+ (with-outer-monad-trans (id &body bs)<br>
+ (append id bs))<br>
+ ;;<br>
+ (inner-unit (a) (list 'generic-inner-unit a))<br>
+ (inner-funcall! (k m) (list 'generic-inner-funcall! k m))<br>
+ (inner-progn! (&body ms) (append '(generic-inner-progn!) ms))<br>
+ (inner-let! (decls m) (list 'generic-inner-let! decls m)))<br>
+ , at body)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<h1><a name="_Toc251846363"></a><a name="_Toc251505174"></a><a
+name="_Toc251505071"></a><a name="_The_Reader_Monad_1"></a><span lang=EN-US>The
+Reader Monad Transformer</span></h1>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>In Haskell the Reader monad transformer can
+be defined in the following way.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>import Control.Monad<br>
+import Control.Monad.Trans<br>
+<br>
+newtype ReaderTrans r m a = <br>
+ ReaderTrans {runReader :: r -> m a}<br>
+<br>
+instance (Monad m) => Monad (ReaderTrans r m) where<br>
+<br>
+ return a = <br>
+ ReaderTrans (\r -> return a)<br>
+<br>
+ m >>= k = <br>
+ ReaderTrans (\r -><br>
+ do a <- runReader m r<br>
+ let m' = k a<br>
+ runReader m' r)<br>
+<br>
+instance MonadTrans (ReaderTrans r) where<br>
+ lift m = ReaderTrans (\r -> m)<br>
+<br>
+read :: (Monad m) => ReaderTrans r m r<br>
+read = ReaderTrans (\r -> return r)</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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 <i>m</i>. It says that we
+need helper macros INNER-UNIT, INNER-FUNCALL!, INNER-LET! and INNER-PROGN!
+introduced above.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>I’ll define macro WITH-READER-MONAD-TRANS
+based on the WITH-MONAD-TRANS macro. Therefore the specified helper macros will
+be accessible.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The UNIT macro prototype uses INNER-UNIT.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro reader-trans-unit (a)<br>
+ (let ((r (gensym)))<br>
+ `#'(lambda (,r)<br>
+ (declare (ignore ,r))<br>
+ (inner-unit ,a))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Please note that expression <i>a</i> 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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The FUNCALL! macro prototype is also
+similar to its non-parameterized version.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro reader-trans-funcall! (k m)<br>
+ (let ((r (gensym))<br>
+ (a (gensym))<br>
+ (kg (gensym)))<br>
+ `#'(lambda (,r)<br>
+ (let ((,kg ,k))<br>
+ (inner-let! ((,a (funcall ,m ,r)))<br>
+ (funcall (funcall ,kg ,a) ,r))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>As before, the LET! macro prototype is more
+efficient.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro reader-trans-let! (decls m)<br>
+ (reduce #'(lambda (decl m)<br>
+ (destructuring-bind (x e) decl<br>
+ (let ((r (gensym)))<br>
+ `#'(lambda (,r)<br>
+ (inner-let! ((,x (funcall ,e ,r)))<br>
+ (funcall ,m ,r))))))<br>
+ decls<br>
+ :from-end t<br>
+ :initial-value m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>We only replaced LET with INNER-LET! to
+take a value from the inner computation.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The PROGN! macro prototype uses
+INNER-PROGN! to bind the inner computations.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro reader-trans-progn! (&body ms)<br>
+ (reduce #'(lambda (m1 m2)<br>
+ (let ((r (gensym)))<br>
+ `#'(lambda (,r)<br>
+ (inner-progn!<br>
+ (funcall ,m1 ,r)<br>
+ (funcall ,m2 ,r)))))<br>
+ ms<br>
+ :from-end t))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The READ! macro prototype uses already the
+INNER-UNIT macro to wrap the environment value in the inner monad.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro reader-trans-read! ()<br>
+ (let ((r (gensym)))<br>
+ `#'(lambda (,r) <br>
+ (inner-unit ,r))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The RUN! macro prototype is the same, but
+now it returns a computation result wrapped in the inner monad.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro reader-trans-run! (m r)<br>
+ `(funcall ,m ,r))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro reader-trans-lift! (m)<br>
+ (let ((r (gensym)))<br>
+ `#'(lambda (,r) <br>
+ (declare (ignore ,r))<br>
+ ,m)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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 </span><a
+href="#_Monad_Transformers"><span lang=EN-US>Monad Transformers</span></a><span
+lang=EN-US>.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-reader-monad-trans (inner-monad
+&body body)<br>
+ `(with-monad-trans (with-reader-monad-trans ,inner-monad)<br>
+ (macrolet<br>
+ ((unit (a) (list 'reader-trans-unit a))<br>
+ (funcall! (k m) (list 'reader-trans-funcall! k m))<br>
+ (progn! (&body ms) (append '(reader-trans-progn!) ms))<br>
+ (let! (decls m) (list 'reader-trans-let! decls m))<br>
+ (read! () (list 'reader-trans-read!))<br>
+ (run! (m r) (list 'reader-trans-run! m r))<br>
+ (lift! (m) (list 'reader-trans-lift! m)))<br>
+ , at body)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(with-reader-monad-trans (with-maybe-monad)<br>
+ (let! ((x e)) m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>After removing all the MACROLETs (with help
+of CLISP), the code expansion looks like</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>#'(LAMBDA (#:G4207)<br>
+ (LET ((#:G4209 (FUNCALL E #:G4207))) (IF (NULL #:G4209) NIL (LET ((X
+(CAR #:G4209))) (FUNCALL M #:G4207)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Here is a test of the monad macro.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defun reader-trans-test ()<br>
+ (destructuring-bind (a log)<br>
+<br>
+ (with-writer-monad<br>
+ (run!<br>
+<br>
+ (with-reader-monad-trans (with-writer-monad)<br>
+ (run!<br>
+<br>
+ (let! ((x (read!)))<br>
+ (progn!<br>
+<br>
+ (lift!<br>
+ (with-writer-monad<br>
+ (write! x)))<br>
+<br>
+ (unit 'ok)))<br>
+ 10))))<br>
+<br>
+ (format t "Computed value=~a~%" a)<br>
+ (format t "Written log=~a~%" log)))<br>
+<br>
+</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>This is its output.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>CL-USER> (reader-trans-test)<br>
+Computed value=OK<br>
+Written log=(10)<br>
+NIL</span></p>
+
+</div>
+
+<h1><a name="_Toc251505175"></a><a name="_Toc251505072"></a><a
+name="_Toc251846364"></a><a name="_The_State_Monad_1"></a><span lang=EN-US>The
+State Monad Transformer</span></h1>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>I’ll use the following definition of the
+State monad transformer written in Haskell.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>import Control.Monad<br>
+import Control.Monad.Trans<br>
+<br>
+newtype StateTrans st m a = StateTrans {runState :: st -> m (a, st)}<br>
+<br>
+instance (Monad m) => Monad (StateTrans st m) where<br>
+<br>
+ return a = StateTrans (\st -> return (a, st))<br>
+<br>
+ m >>= k = StateTrans (\st -> <br>
+ do (a, st') <- runState m st<br>
+ let m' = k a<br>
+ runState m' st')<br>
+<br>
+instance MonadTrans (StateTrans st) where<br>
+ lift m = StateTrans (\st -> do a <- m; return (a, st))<br>
+<br>
+get :: (Monad m) => StateTrans st m st<br>
+get = StateTrans (\st -> return (st, st))<br>
+<br>
+put :: (Monad m) => st -> StateTrans st m ()<br>
+put st' = StateTrans (\_ -> return ((), st'))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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 <i>m</i>.
+Hence we need macros INNER-UNIT, INNER-FUNCALL!, INNER-LET! and INNER-PROGN!
+provided by the WITH-MONAD-TRANS macro.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>I’ll define a new macro
+WITH-STATE-MONAD-TRANS based on WITH-MONAD-TRANS in accordance with the general
+pattern described in section </span><a href="#_Monad_Transformers"><span
+lang=EN-US>Monad Transformers</span></a><span lang=EN-US>. 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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The UNIT macro prototype is similar but it
+uses INNER-UNIT to wrap a pair in the inner monad.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro state-trans-unit (a)<br>
+ (let ((st (gensym)))<br>
+ `#'(lambda (,st)<br>
+ (inner-unit<br>
+ (make-state ,a ,st)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>As before, expression <i>a</i> is evaluated
+inside LAMBDA, i.e. the evaluation is delayed. This strategy will be applied to
+all other macros defined further.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The FUNCALL! macro prototype is similar
+too, but now it uses INNER-LET! to get a raw value from the inner monad.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro state-trans-funcall! (k m)<br>
+ (let ((st (gensym))<br>
+ (p (gensym))<br>
+ (a (gensym))<br>
+ (kg (gensym)))<br>
+ `#'(lambda (,st)<br>
+ (let ((,kg ,k))<br>
+ (inner-let! ((,p (funcall ,m ,st)))<br>
+ (let ((,a (state-value ,p)))<br>
+ (funcall (funcall ,kg ,a)<br>
+ (state-state ,p))))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The notes that I did earlier for the State
+monad are applicable now as well. Expression <i>m</i> 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 <i>m</i> is available then <i>m</i>
+will be expanded to the LAMBDA expression. These LAMBDA and FUNCALL can be
+reduced by the smart compiler.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>As usual, the LET! macro prototype
+generates a more efficient code than FUNCALL!.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro state-trans-let! (decls m)<br>
+ (reduce #'(lambda (decl m)<br>
+ (destructuring-bind (x e) decl<br>
+ (let ((st (gensym))<br>
+ (p (gensym)))<br>
+ `#'(lambda (,st)<br>
+ (inner-let! ((,p (funcall ,e ,st)))<br>
+ (let ((,x (state-value ,p)))<br>
+ (funcall ,m (state-state ,p))))))))<br>
+ decls<br>
+ :from-end t<br>
+ :initial-value m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Here expressions <i>e</i> and <i>m</i> are
+monad values, i.e. anonymous functions. Moreover, if we create a multi-level
+LET! expression then the s-expression for <i>m</i> 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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The PROGN! macro prototype doesn’t bind
+variables but it passes the state through the computation like the previous
+macros.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro state-trans-progn! (&body ms)<br>
+ (reduce #'(lambda (m1 m2)<br>
+ (let ((st (gensym))<br>
+ (p (gensym)))<br>
+ `#'(lambda (,st)<br>
+ (inner-let! ((,p (funcall ,m1 ,st)))<br>
+ (funcall ,m2 (state-state ,p))))))<br>
+ ms<br>
+ :from-end t))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro state-trans-run! (m init-st)<br>
+ (let ((p (gensym)))<br>
+ `(inner-let! ((,p (funcall ,m ,init-st)))<br>
+ (inner-unit<br>
+ (list (state-value ,p)<br>
+ (state-state ,p))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The GET! macro prototype returns the
+current state wrapped in the outer monad.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro state-trans-get! ()<br>
+ (let ((st (gensym)))<br>
+ `#'(lambda (,st)<br>
+ (inner-unit<br>
+ (make-state ,st ,st)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro state-trans-put! (new-st)<br>
+ (let ((st (gensym)))<br>
+ `#'(lambda (,st)<br>
+ (declare (ignore ,st))<br>
+ (inner-unit<br>
+ (make-state nil ,new-st)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro state-trans-lift! (m)<br>
+ (let ((st (gensym))<br>
+ (a (gensym)))<br>
+ `#'(lambda (,st) <br>
+ (inner-let! ((,a ,m))<br>
+ (inner-unit<br>
+ (make-state ,a ,st))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-state-monad-trans (inner-monad
+&body body)<br>
+ `(with-monad-trans (with-state-monad-trans ,inner-monad)<br>
+ (macrolet<br>
+ ((unit (a) (list 'state-trans-unit a))<br>
+ (funcall! (k m) (list 'state-trans-funcall! k m))<br>
+ (progn! (&body ms) (append '(state-trans-progn!) ms))<br>
+ (let! (decls m) (list 'state-trans-let! decls m))<br>
+ (get! () (list 'state-trans-get!))<br>
+ (put! (new-st) (list 'state-trans-put! new-st))<br>
+ (run! (m init-st) (list 'state-trans-run! m init-st))<br>
+ (lift! (m) (list 'state-trans-lift! m)))<br>
+ , at body)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The code generation can be illustrated on
+the following example.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(with-state-monad-trans (with-maybe-monad)<br>
+ (let! ((x e)) m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>After removing all MACROLETs (with help of
+CLISP), the code is expanded to</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>#'(LAMBDA (#:G4372)<br>
+ (LET ((#:G4375 (FUNCALL E #:G4372)))<br>
+ (IF (NULL #:G4375) NIL (LET ((#:G4373 (CAR #:G4375))) (LET ((X (CAR
+#:G4373))) (FUNCALL M (CDR #:G4373)))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defun state-trans-test (tree)<br>
+ (labels<br>
+ ((order (tree)<br>
+ (with-state-monad-trans (with-writer-monad)<br>
+ (cond ((null tree) (unit nil))<br>
+ ((consp tree)<br>
+ (let! ((t1 (order (car tree)))<br>
+ (t2 (order (cdr tree))))<br>
+ (unit (cons t1 t2))))<br>
+ (t <br>
+ (let! ((n (get!)))<br>
+ (let ((new-n (+ n 1)))<br>
+ (progn!<br>
+<br>
+ (lift! <br>
+ (with-writer-monad<br>
+ (write! tree)))<br>
+<br>
+ (put! new-n)<br>
+ (unit (cons tree new-n))))))))))<br>
+<br>
+ (destructuring-bind ((new-tree new-state) saved-log)<br>
+ (with-writer-monad<br>
+ (run!<br>
+ (with-state-monad-trans (with-writer-monad)<br>
+ (run! (order tree) 0))))<br>
+<br>
+ (format t "Item count=~a~%" new-state)<br>
+ (format t "New tree=~a~%" new-tree)<br>
+ (format t "Written log=~a~%" saved-log))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Now we can launch a test.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>CL-USER> (state-trans-test '(5 4 (1 2 (3))))<br>
+Item count=5<br>
+New tree=((5 . 1) (4 . 2) ((1 . 3) (2 . 4) ((3 . 5))))<br>
+Written log=(5 4 1 2 3)<br>
+NIL</span></p>
+
+</div>
+
+<h1><a name="_Toc251846365"></a><a name="_The_Writer_Monad_1"></a><span
+lang=EN-US>The Writer Monad Transformer</span></h1>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>I will use the next definition written in
+Haskell.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>import Control.Monad<br>
+import Control.Monad.Trans<br>
+<br>
+newtype WriterTrans w m a = WriterTrans (m (a, [w] -> [w]))<br>
+<br>
+runWriter :: (Monad m) => WriterTrans w m a -> m (a, [w])<br>
+runWriter (WriterTrans m) = do (a, f) <- m<br>
+ return (a, f [])<br>
+<br>
+write :: (Monad m) => w -> WriterTrans w m ()<br>
+write w = WriterTrans (return ((), \xs -> w : xs))<br>
+<br>
+writeList :: (Monad m) => [w] -> WriterTrans w m ()<br>
+writeList ws = WriterTrans (return ((), \xs -> ws ++ xs))<br>
+<br>
+instance (Monad m) => Monad (WriterTrans w m) where<br>
+<br>
+ return a = WriterTrans (return (a, id))<br>
+<br>
+ (WriterTrans m) >>= k =<br>
+ WriterTrans (do (a, f) <- m<br>
+ let WriterTrans m' = k a<br>
+ (a', f') <- m'<br>
+ return (a', f . f'))<br>
+<br>
+instance MonadTrans (WriterTrans w) where<br>
+ lift m = WriterTrans (do a <- m; return (a, id))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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 <i>WriterTrans</i>. Others are related to monad <i>m</i>. 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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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 </span><a
+href="#_Monad_Transformers"><span lang=EN-US>Monad Transformers</span></a><span
+lang=EN-US>. 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 <i>lift</i> function from Haskell.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The WRITE! macro uses now the INNER-UNIT
+macro as we have to wrap a CONS-pair created with help of MAKE-WRITER.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-trans-write! (&body ws)<br>
+ (if (= 1 (length ws))<br>
+ ;; An optimized case<br>
+ (let ((w (nth 0 ws))<br>
+ (v (gensym)))<br>
+ `(inner-unit<br>
+ (make-writer nil<br>
+ (let ((,v ,w))<br>
+ #'(lambda (xs) (cons ,v xs))))))<br>
+ ;; A general case<br>
+ (let ((vs (gensym)))<br>
+ `(inner-unit<br>
+ (make-writer nil<br>
+ (let ((,vs (list , at ws)))<br>
+ #'(lambda (xs)<br>
+ (append ,vs xs))))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The WRITE-LIST! macro prototype is similar.
+It also returns NIL in the outer monad.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-trans-write-list! (&body wss)<br>
+ (if (= 1 (length wss))<br>
+ ;; An optimized case<br>
+ (let ((ws (nth 0 wss))<br>
+ (vs (gensym)))<br>
+ `(inner-unit<br>
+ (make-writer nil<br>
+ (let ((,vs ,ws))<br>
+ #'(lambda (xs) (append ,vs xs))))))<br>
+ ;; A general case<br>
+ (let ((vss (gensym)))<br>
+ `(inner-unit<br>
+ (make-writer nil<br>
+ (let ((,vss (list , at wss)))<br>
+ #'(lambda (xs)<br>
+ (reduce #'append ,vss<br>
+ :from-end t<br>
+ :initial-value xs))))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Please note that in the both macros we
+evaluate the values <i>ws</i> and <i>wss</i> first and then return new
+functions. The real writing operation will be delayed.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-trans-run! (m)<br>
+ (let ((x (gensym))<br>
+ (fun (gensym)))<br>
+ `(inner-let! ((,x ,m))<br>
+ (inner-unit<br>
+ (list (writer-value ,x)<br>
+ (let ((,fun (writer-fun ,x)))<br>
+ (if (not (null ,fun))<br>
+ (funcall ,fun nil))))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The UNIT macro prototype also uses the
+INNER-UNIT macro to wrap a value in the inner monad.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-trans-unit (a)<br>
+ `(inner-unit<br>
+ (make-writer ,a nil)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Please note that expression <i>a</i> is
+expanded within the outer monad macro, i.e. within WITH-WRITER-MONAD-TRANS, for
+which the INNER-UNIT macro is responsible.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>The FUNCALL! macro prototype is also
+similar to its non-parameterized counterpart.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-trans-funcall! (k m)<br>
+ (let ((ks (gensym))<br>
+ (ms (gensym))<br>
+ (a (gensym))<br>
+ (ka (gensym)))<br>
+ `(let ((,ks ,k))<br>
+ (inner-let! ((,ms ,m))<br>
+ (let ((,a (writer-value ,ms)))<br>
+ (inner-let! ((,ka (funcall ,ks ,a)))<br>
+ (inner-unit <br>
+ (make-writer (writer-value ,ka)<br>
+ (writer-compose (writer-fun ,ms)<br>
+ (writer-fun ,ka))))))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>As usual, the LET! macro prototype is more
+optimal.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-trans-let! (decls m)<br>
+ (reduce <br>
+ #'(lambda (decl m)<br>
+ (destructuring-bind (x e) decl<br>
+ (let ((es (gensym))<br>
+ (ms (gensym)))<br>
+ `(inner-let! ((,es ,e))<br>
+ (let ((,x (writer-value ,es)))<br>
+ (inner-let! ((,ms ,m))<br>
+ (inner-unit<br>
+ (make-writer (writer-value ,ms)<br>
+ (writer-compose (writer-fun ,es)<br>
+ (writer-fun ,ms))))))))))<br>
+ decls<br>
+ :from-end t<br>
+ :initial-value m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The PROGN! macro prototype was also
+slightly modified.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-trans-progn! (&body ms)<br>
+ (reduce <br>
+ #'(lambda (m1 m2)<br>
+ (let ((m1s (gensym))<br>
+ (m2s (gensym)))<br>
+ `(inner-let! ((,m1s ,m1)<br>
+ (,m2s ,m2))<br>
+ (inner-unit<br>
+ (make-writer (writer-value ,m2s)<br>
+ (writer-compose (writer-fun ,m1s)<br>
+ (writer-fun ,m2s)))))))<br>
+ ms<br>
+ :from-end t))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro writer-trans-lift! (m)<br>
+ (let ((a (gensym)))<br>
+ `(inner-let! ((,a ,m))<br>
+ (inner-unit<br>
+ (make-writer ,a nil)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-writer-monad-trans (inner-monad
+&body body)<br>
+ `(with-monad-trans (with-writer-monad-trans ,inner-monad)<br>
+ (macrolet<br>
+ ((unit (a) (list 'writer-trans-unit a))<br>
+ (funcall! (k m) (list 'writer-trans-funcall! k m))<br>
+ (progn! (&body ms) (append '(writer-trans-progn!) ms))<br>
+ (let! (decls m) (list 'writer-trans-let! decls m))<br>
+ (write! (&body ws) (append '(writer-trans-write!) ws))<br>
+ (write-list! (&body wss) (append '(writer-trans-write-list!)
+wss))<br>
+ (run! (m) (list 'writer-trans-run! m))<br>
+ (lift! (m) (list 'writer-trans-lift! m)))<br>
+ , at body)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>Let’s take the following sample</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(with-writer-monad-trans <br>
+ (with-reader-monad-trans <br>
+ (with-maybe-monad))<br>
+<br>
+ (let! ((x e)) m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>After removing the MACROLETs (with help of
+CLISP) the macro expansion looks like this</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>#'(LAMBDA (#:G4325)<br>
+ (LET ((#:G4327 (FUNCALL E #:G4325)))<br>
+ (IF (NULL #:G4327) NIL<br>
+ (LET ((#:G4322 (CAR #:G4327)))<br>
+ (FUNCALL<br>
+ (LET ((X (CAR #:G4322)))<br>
+ #'(LAMBDA (#:G4329)<br>
+ (LET ((#:G4331 (FUNCALL M #:G4329)))<br>
+ (IF (NULL #:G4331) NIL<br>
+ (LET ((#:G4323 (CAR #:G4331)))<br>
+ (FUNCALL<br>
+ #'(LAMBDA (#:G4333)<br>
+ (DECLARE (IGNORE #:G4333))<br>
+ (CONS<br>
+ (CONS (CAR #:G4323)<br>
+ (LET ((#:G4335 (CDR #:G4322)) (#:G4336
+(CDR #:G4323)))<br>
+ (COND ((NULL #:G4336) #:G4335) ((NULL
+#:G4335) #:G4336)<br>
+ (T<br>
+ #'(LAMBDA (X)<br>
+ (FUNCALL #:G4335 (FUNCALL
+#:G4336 X)))))))<br>
+ NIL))<br>
+ #:G4329))))))<br>
+ #:G4325)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Here is a test.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defun writer-trans-test ()<br>
+ (let ((m (with-writer-monad-trans (with-maybe-monad)<br>
+ <br>
+ (run!<br>
+ (progn!<br>
+ (write! 1)<br>
+ (write! 2 3)<br>
+ (lift! (make-maybe)) ; FAIL<br>
+ (write-list! '(4 5 6))<br>
+ (unit 'ok))))))<br>
+<br>
+ (if (maybe-just-p m)<br>
+<br>
+ (progn<br>
+ (destructuring-bind (a log) (maybe-just m)<br>
+ (format t "Computed value=~a~%" a)<br>
+ (format t "Written log=~a~%" log)))<br>
+<br>
+ (format t "Computation was interrupted~%"))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>If you’ll try to compile it with help of
+SBCL, then the compiler will warn about an unreachable code!</span></p>
+
+<p class=MsoNormal><span lang=EN-US>This is an output of the test.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>CL-USER> (writer-trans-test)<br>
+Computation was interrupted<br>
+NIL</span></p>
+
+</div>
+
+<h1><a name="_Toc251846366"></a><a name="_Minimizing_a_Compilation"></a><span
+lang=EN-US>Reducing Monad Macros</span></h1>
+
+<p class=MsoNormal><span lang=EN-US>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!</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>I’ll illustrate the method on the
+parameterized twice macro WITH-WRITER-MONAD-TRANS (WITH-READER-MONAD-TRANS
+(WITH-MAYBE-MONAD)).</span></p>
+
+<p class=MsoNormal><span lang=EN-US>First, we create a short name for our
+source macro, lifting the READ! macro from the Writer monad transformer.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-opt-proto (&body body)<br>
+ `(with-writer-monad-trans<br>
+ (with-reader-monad-trans <br>
+ (with-maybe-monad))<br>
+ (macrolet<br>
+ ((read! ()<br>
+ `(lift!<br>
+ (with-reader-monad-trans <br>
+ (with-maybe-monad)<br>
+ (read!)))))<br>
+ , at body)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defun opt-read! ()<br>
+ (with-opt-proto<br>
+ (read!)))</span></p>
+
+<p class=a><span lang=EN-US>(defun opt-write! (&rest ws)<br>
+ (with-opt-proto<br>
+ (if (= 1 (length ws))<br>
+ (write! (nth 0 ws))<br>
+ (write-list! ws))))<br>
+<br>
+(defun opt-write-list! (&rest wss)<br>
+ (with-opt-proto<br>
+ (if (= 1 (length wss))<br>
+ (write-list! (nth 0 wss))<br>
+ (reduce #'(lambda (ws m)<br>
+ (progn! (write-list! ws) m))<br>
+ wss<br>
+ :from-end t<br>
+ :initial-value (unit nil)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>In the last function we create a sequence
+of the computations and always return NIL wrapped in the monad.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defun opt-run! (m r)<br>
+ (with-reader-monad-trans (with-maybe-monad)<br>
+ (run! (with-opt-proto<br>
+ (run! m))<br>
+ r)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defun opt-lift! (m)<br>
+ (with-opt-proto<br>
+ (lift! <br>
+ (with-reader-monad-trans (with-maybe-monad)<br>
+ (lift! m)))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>Now we can define the return and bind
+functions.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defun opt-unit (a)<br>
+ (with-opt-proto<br>
+ (unit a)))<br>
+<br>
+(defun opt-funcall! (k m)<br>
+ (with-opt-proto<br>
+ (funcall! k m)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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 <i>reduction
+form</i> 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!.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defmacro with-opt-monad (&body body)<br>
+ `(with-monad (opt-unit opt-funcall!)<br>
+ (macrolet<br>
+ ((read! () `(opt-read!))<br>
+ (write! (&body bs) `(opt-write! ,@ bs))<br>
+ (write-list! (&body bs) `(opt-write-list! , at bs))<br>
+ (run! (m r) `(opt-run! ,m ,r))<br>
+ (lift! (m) `(opt-lift! ,m)))<br>
+ , at body)))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>This is a small test with the new monad.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>(defun opt-test ()<br>
+ (let ((m (with-opt-monad<br>
+ (run!<br>
+ (progn!<br>
+<br>
+ (write! 1)<br>
+ (write! 2 3)<br>
+ (write-list! '(4 5 6))<br>
+<br>
+ (let! ((x (read!)))<br>
+ (lift! (make-maybe :just x))))<br>
+<br>
+ 10))))<br>
+<br>
+ (if (maybe-just-p m)<br>
+<br>
+ (progn<br>
+ (destructuring-bind (a log) (maybe-just m)<br>
+ (format t "Computed value=~a~%" a)<br>
+ (format t "Written log=~a~%" log)))<br>
+<br>
+ (format t "Computation was interrupted~%"))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>The test returns the following results.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US>CL-USER> (opt-test)<br>
+Computed value=10<br>
+Written log=(1 2 3 4 5 6)<br>
+NIL</span></p>
+
+</div>
+
+<h1><a name="_Toc251846367"><span lang=EN-US>Loops</span></a></h1>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<h1><a name="_Toc251846368"><span lang=EN-US>Other Monad Macros</span></a></h1>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>In general case we can define a prototype
+for the functor map function, which I’ll call FMAP.</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (defmacro generic-fmap (f m)<br>
+ ;; an analog of the fmap function from Haskell<br>
+ (let ((fun (gensym))<br>
+ (x (gensym)))<br>
+ `(let ((,fun ,f))<br>
+ (let! ((,x ,m))<br>
+ (unit (funcall ,fun ,x))))))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>It’s obvious that in case of the List monad
+the following definition will be much more efficient:</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (defmacro list-fmap (f m)<br>
+ ;; fmap for the List monad<br>
+ `(mapcar ,f ,m))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>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 <i>sequence</i> function from
+Haskell</span></p>
+
+<div style='border:solid windowtext 1.0pt;padding:1.0pt 4.0pt 1.0pt 4.0pt;
+background:#DBE5F1'>
+
+<p class=a><span lang=EN-US> (defmacro list! (&body ms)<br>
+ (reduce<br>
+ #’(lambda (x xs)<br>
+ (let ((y (gensym))<br>
+ (ys (gensym)))<br>
+ `(let! ((,y ,x)<br>
+ (,ys ,xs))<br>
+ (unit (cons ,y ,ys)))))<br>
+ ms<br>
+ :from-end t<br>
+ :initial-value (unit ())))</span></p>
+
+</div>
+
+<p class=MsoNormal><span lang=EN-US>In case of the WITH-IDENTITY-MONAD macro
+the LIST! macro can be replaced with function LIST, which corresponds to the
+rule of thumb.</span></p>
+
+<h1><a name="_Toc251846369"></a><a name="_Toc251505177"></a><a
+name="_Toc251505074"><span lang=EN-US>Conclusion</span></a></h1>
+
+<p class=MsoNormal><span lang=EN-US>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.</span></p>
+
+<p class=MsoNormal><span lang=EN-US>Also I think that my approach is somewhere
+similar to the F# <i>workflows</i>. Only the monad macros play a role of the
+workflow builders.</span></p>
+
+</div>
+
+</body>
+
+</html>
More information about the cl-monad-macros-cvs
mailing list