mimir.github.io/autodiff.html at master · mimir/mimir.github.io · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
<!-- HTML header for doxygen 1.9.3-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=11"/>
<meta name="generator" content="Doxygen 1.16.1"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>MimIR: The automatic differentiation Plugin</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<script type="text/javascript" src="doxygen-awesome-darkmode-toggle.js"></script>
<script type="text/javascript" src="doxygen-awesome-fragment-copy-button.js"></script>
<script type="text/javascript" src="doxygen-awesome-interactive-toc.js"></script>
<script type="text/javascript" src="doxygen-awesome-paragraph-link.js"></script>
<script type="text/javascript">
    DoxygenAwesomeDarkModeToggle.init()
    DoxygenAwesomeFragmentCopyButton.init()
    DoxygenAwesomeInteractiveToc.init()
    DoxygenAwesomeParagraphLink.init()
</script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript" src="cookie.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
<link href="doxygen-awesome.css" rel="stylesheet" type="text/css"/>
<link href="doxygen-awesome-sidebar-only.css" rel="stylesheet" type="text/css"/>
<link href="doxygen-awesome-sidebar-only-darkmode-toggle.css" rel="stylesheet" type="text/css"/>
<link href="doxygen-awesome-interactive-toc.js" rel="stylesheet" type="text/css"/>
<link href="custom.css" rel="stylesheet" type="text/css"/>
<link href="version-switcher.css" rel="stylesheet" type="text/css"/>
<link href="dotgraph.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- https://tholman.com/github-corners/ -->
<a href="https://github.com/mimir/mimir" class="github-corner" title="View source on GitHub">
    <svg viewBox="0 0 250 250" style="position: absolute; top: 0; border: 0; right: 0;" aria-hidden="true">
    <path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></a><style>.github-corner:hover .octo-arm{animation:octocat-wave 560ms ease-in-out}@keyframes octocat-wave{0%,100%{transform:rotate(0)}20%,60%{transform:rotate(-25deg)}40%,80%{transform:rotate(10deg)}}@media (max-width:500px){.github-corner:hover .octo-arm{animation:none}.github-corner .octo-arm{animation:octocat-wave 560ms ease-in-out}}</style>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr id="projectrow">
  <td id="projectlogo"><a href="https://github.com/mimir"><img alt="Logo" src="logo.svg"/></a></td>
  <td id="projectalign">
   <div id="projectname">MimIR
    <div id="projectnumber" class="version-switcher" data-manifest="versions.json">
     <button class="version-switcher__button" type="button" aria-expanded="false" aria-haspopup="true">0.3-dev</button>
     <div class="version-switcher__menu" hidden></div>
    </div>
    <script type="text/javascript" src="version-switcher.js"></script>
    </div>
   <div id="projectbrief">MimIR is my Intermediate Representation</div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.16.1 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search/",'.html');
</script>
<script type="text/javascript">
$(function() { codefold.init(); });
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
$(function() {
  initMenu('',true,false,'search.php','Search',true);
  $(function() { init_search(); });
});
</script>
<div id="main-nav"></div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;"
       class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
$(function(){initNavTree('autodiff.html','',''); });
</script>
<div id="container">
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<div id="MSearchResults">
<div class="SRPage">
<div id="SRIndex">
<div id="SRResults"></div>
<div class="SRStatus" id="Loading">Loading...</div>
<div class="SRStatus" id="Searching">Searching...</div>
<div class="SRStatus" id="NoMatches">No Matches</div>
</div>
</div>
</div>
</div>

<div><div class="header">
  <div class="headertitle"><div class="title">The automatic differentiation Plugin </div></div>
</div><!--header-->
<div class="contents">
<div class="toc"><h3>Table of Contents</h3>
<ul>
  <li class="level1">
    <a href="#autotoc_md143">Dependencies </a>
  </li>
  <li class="level1">
    <a href="#autotoc_md144">Types </a>
  </li>
  <li class="level1">
    <a href="#autotoc_md145">Operations </a>
    <ul>
      <li class="level2">
        <a href="#autotoc_md146">%autodiff.AD </a>
      </li>
      <li class="level2">
        <a href="#autotoc_md147">%autodiff.ad </a>
      </li>
      <li class="level2">
        <a href="#autotoc_md148">%autodiff.zero </a>
      </li>
      <li class="level2">
        <a href="#autotoc_md149">%autodiff.add </a>
      </li>
      <li class="level2">
        <a href="#autotoc_md150">%autodiff.sum </a>
      </li>
    </ul>
  </li>
  <li class="level1">
    <a href="#autotoc_md151">Phases </a>
  </li>
  <li class="level1">
    <a href="#autotoc_md152">Registered translations </a>
    <ul>
      <li class="level2">
        <a href="#autotoc_md153">%core.icmp.xYgLE (eq) </a>
      </li>
      <li class="level2">
        <a href="#autotoc_md154">%core.wrap.add </a>
      </li>
      <li class="level2">
        <a href="#autotoc_md155">%core.wrap.mul </a>
      </li>
    </ul>
  </li>
</ul>
</div>
<div class="textblock"><p><a class="anchor" id="md_build_2docs_2plug_2autodiff"></a></p>
<dl class="section see"><dt>See also</dt><dd><a class="el" href="namespacemim_1_1plug_1_1autodiff.html" title="The automatic differentiation Plugin">mim::plug::autodiff</a></dd></dl>
<h1 class="doxsection"><a class="anchor" id="autotoc_md143"></a>
Dependencies</h1>
<div class="fragment"><div class="line">plugin mem;</div>
<div class="line">import compile;</div>
</div><!-- fragment --><p> For derivatives: </p><div class="fragment"><div class="line">plugin core;</div>
</div><!-- fragment --><h1 class="doxsection"><a class="anchor" id="autotoc_md144"></a>
Types</h1>
<div class="fragment"><div class="line">axm %autodiff.Tangent: * → *, normalize_Tangent;</div>
</div><!-- fragment --><h1 class="doxsection"><a class="anchor" id="autotoc_md145"></a>
Operations</h1>
<h2 class="doxsection"><a class="anchor" id="autotoc_md146"></a>
%autodiff.AD</h2>
<p>Computes the augmented type of a function type: <span class="tt">(T → U) =&gt; (T → U × (U → T))</span>.</p>
<div class="fragment"><div class="line">axm %autodiff.AD: * → *, normalize_AD;</div>
</div><!-- fragment --><h2 class="doxsection"><a class="anchor" id="autotoc_md147"></a>
%autodiff.ad</h2>
<p>Yields the augmented term of a closed term (function, operator, higher-order argument, registered axiom, etc.). The augmented term <span class="tt">f'</span> returns the result together with the pullback: <span class="tt">autodiff f = f' = λ args. (f args, f*)</span></p>
<div class="fragment"><div class="line">axm %autodiff.ad: {T: *} → T → %autodiff.AD T, normalize_ad;</div>
</div><!-- fragment --><h2 class="doxsection"><a class="anchor" id="autotoc_md148"></a>
%autodiff.zero</h2>
<p>Represents universal zero such that <span class="tt">(zero T) +_T t = t</span>.</p>
<div class="fragment"><div class="line">axm %autodiff.zero: [T: *] → T, normalize_zero;</div>
</div><!-- fragment --><h2 class="doxsection"><a class="anchor" id="autotoc_md149"></a>
%autodiff.add</h2>
<p>A universal addition that consumes zeros and defaults to normal addition for scalar types. It lifts addition over structured types and special-cases types that do not allow addition.</p>
<p>TODO: how do we handle summations that need memory? (grab current memory?) </p><div class="fragment"><div class="line">axm %autodiff.add: {T: *} → [T, T] → T, normalize_add;</div>
</div><!-- fragment --><h2 class="doxsection"><a class="anchor" id="autotoc_md150"></a>
%autodiff.sum</h2>
<p>Performs %autodiff.add over a list of terms.</p>
<div class="fragment"><div class="line">axm %autodiff.sum: [n: Nat, T: *] → «n; T» → T, normalize_sum;</div>
</div><!-- fragment --><h1 class="doxsection"><a class="anchor" id="autotoc_md151"></a>
Phases</h1>
<div class="fragment"><div class="line">axm %autodiff.zero_repl: %compile.Phase;</div>
<div class="line">axm %autodiff.eval:      %compile.Phase;</div>
</div><!-- fragment --><h1 class="doxsection"><a class="anchor" id="autotoc_md152"></a>
Registered translations</h1>
<p>In this section, we define translations for axioms of other plugins. This would best be done using a register mechanism in a third plugin or at least in a separate file.</p>
<p>The general concept is that a call to an axiom is replaced with a call to the augmented axiom. The augmented axiom needs a wrapper for meta arguments (a higher-order function). Appropriate cps2ds wrappers are introduced to handle that the augmented axioms are in CPS whereas the original axioms are in direct style. Example: </p><div class="fragment"><div class="line">mul&#39; =&gt; args → result*pullback</div>
<div class="line">call: r    = mul  (m,w) (a,b)</div>
<div class="line">res : r,r* = mul&#39; (m,w) (a,b)</div>
</div><!-- fragment --><p> The types (with <span class="tt">Int</span> for <span class="tt">(Int w)</span>) are: </p><div class="fragment"><div class="line">mul : [m:Nat,w:Nat] → [a:Int,b:Int] → Int</div>
<div class="line">r   : Int</div>
<div class="line">r*  : cn[Int,cn[Int,Int]]</div>
</div><!-- fragment --><p> The pullback has to be in cps for compliance. </p><div class="fragment"><div class="line">mul* := λ s. (s*b,s*a)</div>
<div class="line">mul&#39;_cps : [m:Nat,w:Nat] → cn[[Int,Int],cn[Int,   cn[Int,cn[Int,Int]]]]</div>
<div class="line">r,r* = (cps2ds (mul&#39;_cps (m,w))) (a,b)</div>
</div><!-- fragment --><p>The pullback is the derivative with respect to the input (weighted with the output tangent). For arithmetic operations, <span class="tt">s</span> is simply multiplied onto each input tangent: <span class="tt">∂_i f(x1,...,xn) * s</span> It follows that the applied partial pullback needs to be: <span class="tt">sum x_i*(∂_i f(x1,...,xn) * s) = sum x_i*(•)</span> with <span class="tt">•</span> as the formula from above. This is a direct result of the chain-rule composition with the partial pullback of a tuple. The tuple pullback transports the partial pullbacks of the operands and handles the sums. By its nature the pullback of a tuple needs to be a sum.</p>
<h2 class="doxsection"><a class="anchor" id="autotoc_md153"></a>
%core.icmp.xYgLE (eq)</h2>
<p>The comparison pullback exists formally but is not used.</p>
<div class="fragment"><div class="line">fun extern internal_diff_core_icmp_xYgLE {s: Nat} (ab: «2; Idx s»)@tt: [Bool, Cn[Bool, Cn«2; Idx s»]] =</div>
<div class="line">    return (%core.icmp.sle ab, fn [Bool]@tt: «2; Idx s» = return ‹2; 0:(Idx s)›);</div>
</div><!-- fragment --><h2 class="doxsection"><a class="anchor" id="autotoc_md154"></a>
%core.wrap.add</h2>
<p>s ↦ (s, s)</p>
<div class="fragment"><div class="line">fun extern internal_diff_core_wrap_add {s: Nat} (m: Nat) (ab: «2; Idx s»)@tt: [Idx s, Cn[Idx s, Cn«2; Idx s»]] =</div>
<div class="line">    return (%core.wrap.add m ab, fn (i: Idx s)@tt: «2; Idx s» = return ‹2; i›);</div>
</div><!-- fragment --><h2 class="doxsection"><a class="anchor" id="autotoc_md155"></a>
%core.wrap.mul</h2>
<p>s ↦ (s*b, s*a)</p>
<div class="fragment"><div class="line">fun extern internal_diff_core_wrap_mul {s: Nat} (m: Nat) (a b: Idx s) as ab@tt: [Idx s, Cn[Idx s, Cn«2; Idx s»]] =</div>
<div class="line">    return (%core.wrap.mul m ab, fn (i: Idx s)@tt: «2; Idx s» = return (%core.wrap.mul m (i, b), %core.wrap.mul m (i, a)));</div>
</div><!-- fragment --> </div></div><!-- contents -->
</div><!-- PageDoc -->
</div><!-- doc-content -->
</div><!-- container -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
  <ul>
    <li class="footer">Generated by <a href="https://www.doxygen.org/index.html"><img class="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.16.1 </li>
  </ul>
</div>
</body>
</html>