diff options
| author | muqiuhan <[email protected]> | 2024-10-18 15:45:18 +0000 |
|---|---|---|
| committer | muqiuhan <[email protected]> | 2024-10-18 15:45:18 +0000 |
| commit | 3c03c9b03a084984383b510f6b795df3bfaf5ca7 (patch) | |
| tree | 7daa9d22c80f8240066a0754c7716b2c38a2f1b2 /2024 | |
| parent | 4b590d57084adcd99c7b73b4485282bbb8455d01 (diff) | |
| download | blog-3c03c9b03a084984383b510f6b795df3bfaf5ca7.tar.gz | |
deploy: e8ad1ffc5e1b38c1ac5bb25141187398e15d1236
Diffstat (limited to '2024')
7 files changed, 1654 insertions, 8 deletions
diff --git a/2024/09/12/Functional-Reactive-Programming-in-F/index.html b/2024/09/12/Functional-Reactive-Programming-in-F/index.html index 301be807..f4eed15f 100644 --- a/2024/09/12/Functional-Reactive-Programming-in-F/index.html +++ b/2024/09/12/Functional-Reactive-Programming-in-F/index.html @@ -147,14 +147,14 @@ </span> <span class="post-tag"> - <a href="/tags/Archive/"> - Archive + <a href="/tags/F/"> + F# </a> </span> <span class="post-tag"> - <a href="/tags/F/"> - F# + <a href="/tags/Archive/"> + Archive </a> </span> diff --git a/2024/09/15/Advanced-C-binding-using-ocaml-ctypes-and-dune/index.html b/2024/09/15/Advanced-C-binding-using-ocaml-ctypes-and-dune/index.html index 781eeb0e..ebefbe58 100644 --- a/2024/09/15/Advanced-C-binding-using-ocaml-ctypes-and-dune/index.html +++ b/2024/09/15/Advanced-C-binding-using-ocaml-ctypes-and-dune/index.html @@ -147,14 +147,14 @@ </span> <span class="post-tag"> - <a href="/tags/OCaml/"> - OCaml + <a href="/tags/Archive/"> + Archive </a> </span> <span class="post-tag"> - <a href="/tags/Archive/"> - Archive + <a href="/tags/OCaml/"> + OCaml </a> </span> diff --git a/2024/10/06/Obsidian-Vault-的-obsidian-目录中的各文件作用/index.html b/2024/10/06/Obsidian-Vault-的-obsidian-目录中的各文件作用/index.html index 6052f4a3..298008ab 100644 --- a/2024/10/06/Obsidian-Vault-的-obsidian-目录中的各文件作用/index.html +++ b/2024/10/06/Obsidian-Vault-的-obsidian-目录中的各文件作用/index.html @@ -208,6 +208,11 @@ <nav class="post-nav"> <div class="prev-item"> + <div class="icon arrow-left"></div> + <div class="post-link"> + <a href="/2024/10/18/Dealing-with-complex-dependency-injection-in-FSharp/">Prev</a> + </div> + </div> <div class="next-item"> diff --git a/2024/10/18/10-Tips-for-Productive-FSharp-Scripting/index.html b/2024/10/18/10-Tips-for-Productive-FSharp-Scripting/index.html new file mode 100644 index 00000000..efff6f07 --- /dev/null +++ b/2024/10/18/10-Tips-for-Productive-FSharp-Scripting/index.html @@ -0,0 +1,425 @@ +<!DOCTYPE html> +<html lang="en"> + <head> + <meta charset="UTF-8"> +<meta name="viewport" + content="width=device-width, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0"> +<meta http-equiv="X-UA-Compatible" content="ie=edge"> + + <meta name="author" content="韩暮秋"> + + + <meta name="subtitle" content="暮秋小屋"> + + + <meta name="description" content="这里是暮秋小屋,思念和灵感的寄存处"> + + + <meta name="keywords" content="韩暮秋,MuqiuHan,'Muqiu Han', 'muqiu han', muqiuhan"> + + + + +<title>10 Tips for Productive FSharp Scripting | 暮秋小屋</title> + + + + <link rel="icon" href="/favicon.ico"> + + + +<style> + @import url('https://fonts.googleapis.com/css2?family=Inter:wght@300;400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&family=Roboto+Mono&display=swap'); +</style> + + + + <!-- stylesheets list from _config.yml --> + + <link rel="stylesheet" href="/css/style.css"> + + + + + + <!-- scripts list from _config.yml --> + + <script src="/js/frame.js"></script> + + + + + + <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script> + <script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script> + + + + + + + + <meta name="generator" content="Hexo 6.3.0"></head> + <body> + <div class="mask-border"> + </div> + + <div class="wrapper"> + + <div class="header"> + <div class="flex-container"> + <div class="header-inner"> + <div class="site-brand-container"> + <a href="/"> + + 暮秋小屋 + + </a> + </div> + <div id="menu-btn" class="menu-btn" onclick="toggleMenu()"> + Menu + </div> + <nav class="site-nav"> + <ul class="menu-list"> + + + <li class="menu-item"> + <a href="/">主页</a> + </li> + + + + <li class="menu-item"> + <a href="/categories/gallery/">日记本</a> + </li> + + + + <li class="menu-item"> + <a href="/tags/Medicine/">医学</a> + </li> + + + + <li class="menu-item"> + <a href="/tags/Technique/">计算机科学</a> + </li> + + + + <li class="menu-item"> + <a href="/tags/Life/">生活</a> + </li> + + + + <li class="menu-item"> + <a href="/about">关于</a> + </li> + + + + <li class="menu-item search-btn"> + <a href="#">Search</a> + </li> + + </ul> + </nav> + </div> + </div> +</div> + + + <div class="main"> + <div class="flex-container"> + <article id="post"> + + + <div class="post-head"> + <div class="post-info"> + <div class="tag-list"> + + + <span class="post-tag"> + <a href="/tags/Technique/"> + Technique + </a> + </span> + + <span class="post-tag"> + <a href="/tags/F/"> + F# + </a> + </span> + + <span class="post-tag"> + <a href="/tags/Archive/"> + Archive + </a> + </span> + + + </div> + <div class="post-title"> + + + 10 Tips for Productive FSharp Scripting + + + </div> + <span class="post-date"> + Oct 18, 2024 + </span> + </div> + <div class="post-img"> + + <div class="h-line-primary"></div> + + </div> +</div> + <div class="post-content"> + <p>Scott Hanselman recently had a <a target="_blank" rel="noopener" href="http://www.hanselman.com/blog/InteractiveCodingWithCAndFREPLsScriptCSOrTheVisualStudioInteractiveWindow.aspx">nice post on C# and F# REPLs</a>, which reminded me of the time I started using F# scripts. Over time, I found out a couple of small tricks, which helped make the experience productive. I found about them mainly by accident, so I figured, let’s see if I can list them in one place! Some of these are super simple, some probably a bit obscure, but hopefully, one of them at least will make your path towards scripting nirvana an easier one…</p> +<blockquote> +<p>Note: these tips are not necessarily ordered by usefulness. For that matter, there might or might not be exactly 10 of them :)</p> +</blockquote> +<h2 id="Tip-1-Use-fsx-Files-for-Interactive-Coding"><a href="#Tip-1-Use-fsx-Files-for-Interactive-Coding" class="headerlink" title="Tip 1: Use .fsx Files for Interactive Coding"></a>Tip 1: Use <code>.fsx</code> Files for Interactive Coding</h2><p>You can use the F# Interactive 2 ways: you can directly type code into FSI, the F# Interactive window, or you can write code in an <code>.fsx</code> file, and select pieces of the code you want to execute. I recommend the second approach, for at least two reasons. First, FSI is a very primitive environment, <code>.fsx</code> files provide a much richer experience (IntelliSense). Then this encourages writing clean scripts you can reuse later.</p> +<blockquote> +<p>This is not specific to scripts, but… if you are on Visual Studio, do yourself a service and install the <a target="_blank" rel="noopener" href="http://fsprojects.github.io/VisualFSharpPowerTools/">Visual F# Power Tools</a> - you’ll get nice things such as better code highlighting, refactoring, and more.</p> +</blockquote> +<p>To execute code interactively, simply type code in an <code>.fsx</code> file, select a block of code, and hit Alt + Enter. The selected code will be evaluated, and the result will show up in the FSI window. In Visual Studio, you can also select code and right-click “Execute in Interactive”, but shortcuts are way faster.</p> +<blockquote> +<p>You can also execute a single-line with Alt + ‘. I rarely use this option, but this can save you time because you don’t need to select the entire line of code.</p> +</blockquote> +<blockquote> +<p>In case the keyboard shortcuts to send code to FSI do not work anymore (ReSharper used to over-write them in the past), you can reset them in Visual Studio, by going to Tools / Options / Environment / Keyboard. The 2 commands you need to map are <strong>EditorContextMenus.CodeWindow.ExecuteInInteractive</strong> and <strong>EditorContextMenus.CodeWindow.ExecuteLineInInteractive</strong>.</p> +</blockquote> +<p>You can also use these shortcuts from a regular <code>.fs</code> file, which can be handy if you want to validate that a piece of code is behaving the way you want.</p> +<blockquote> +<p>Interactive coding is by far my main usage for scripts - I use it extensively to prototype designs, run dumb tasks, or explore data or libraries. I realized recently that a few of my C# friends use LinqPad for the same purpose.</p> +</blockquote> +<h2 id="Tip-2-What-is-it"><a href="#Tip-2-What-is-it" class="headerlink" title="Tip 2: What is it?"></a>Tip 2: What is <code>it</code>?</h2><p>While I encourage working primarily from <code>.fsx</code> files, the FSI window is also very helpful. I use it primarily for small verifications. For instance, I might have in my script file code like this:</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">let add x y =</span><br><span class="line"> x + y</span><br></pre></td></tr></table></figure> + +<p>Once I send it for evaluation into FSI, I will see the following show up in FSI:</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">val add : x:int -> y:int -> int</span><br><span class="line">></span><br></pre></td></tr></table></figure> + +<p>My function <code>add</code> is now in memory, in my FSI session; I can start typing in the FSI window and use it:</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">> add 1 2;;</span><br><span class="line">val it : int = 3</span><br><span class="line">></span><br></pre></td></tr></table></figure> + +<p>Enter does not trigger execution in FSI. The <code>;;</code> indicates to FSI “Please execute everything I just typed, up to that point”. This is useful if you want to type multiple lines of code in FSI, and execute them as a block.</p> +<blockquote> +<p><code>it</code>: in our <code>add 1 2</code> example, the result showed up as <code>it</code>. We simply ran add, but didn’t assign the result to anything. <code>it</code> now contains the result, until we run another expression. If you want to re-use that value, you can assign it in FSI, by doing for instance <code>let x = it;;</code>.′</p> +</blockquote> +<blockquote> +<p>Once a value is loaded in your FSI session, it will remain there, available to you until you shadow it (in the example above, <code>x</code> will remain available, until I run for instance <code>let x = 42;;</code>). This is extremely convenient: for instance, you can load a data file once <code>let data = File.ReadAllLines path</code>, and keep using <code>data</code> for as long as you want, without having to reload it between code changes.</p> +</blockquote> +<blockquote> +<p>FSI often shows an abbreviated version of values for large items. For instance, <code>[1..999]</code> will show up as <code>val it : int list = [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; ...]</code> - note the … at the end, which indicate that there is more.</p> +</blockquote> +<p>What if you inadvertently started a very long computation, or an infinite loop? In Visual Studio, you can either kill the session entirely, by right-clicking over the FSI window and selecting “Reset Interactive Session” or Ctrl + Alt + R, or cancel the latest evaluation you requested (“Cancel Interactive Evaluation”, or Ctrl + Break.).</p> +<h2 id="Tip-3-Run-Scripts-from-the-Command-Line"><a href="#Tip-3-Run-Scripts-from-the-Command-Line" class="headerlink" title="Tip 3: Run Scripts from the Command Line"></a>Tip 3: Run Scripts from the Command Line</h2><p>Besides interactive scripting, you can also run a script from the command line, by using <code>FSI.exe</code>:</p> +<p><code>>fsi.exe "C:\myscript.fsx"</code></p> +<blockquote> +<p><code>FSI.exe</code> is typically located at <code>C:\Program Files (x86)\Microsoft SDKs\F#\4.0\Framework\v4.0</code>. You can also install it separately, see <a target="_blank" rel="noopener" href="http://fsharp.org/">fsharp.org/use</a> section for instructions for various platforms.</p> +</blockquote> +<p>You can define different behaviors in your script, depending on whether it is run interactively or from the command line, like this:</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">#if INTERACTIVE</span><br><span class="line">let msg = "Interactive"</span><br><span class="line">#else</span><br><span class="line">let msg = "Not Interactive"</span><br><span class="line">#endif</span><br><span class="line"></span><br><span class="line">printfn "%s" msg</span><br></pre></td></tr></table></figure> + +<p><em>Updated, Sep 19: thanks Matt Klein for <a target="_blank" rel="noopener" href="http://stackoverflow.com/q/39581342/114519">pointing the issue</a>.</em></p> +<p>For more information on FSI from the command line, <a target="_blank" rel="noopener" href="https://msdn.microsoft.com/en-us/library/dd233175.aspx">check the reference page here</a>.</p> +<p><em>Updated, Feb 20: <a target="_blank" rel="noopener" href="https://twitter.com/genTauro42">Ramon Soto Mathiesen</a> points out that <a target="_blank" rel="noopener" href="https://twitter.com/genTauro42/status/696407757835132928">Tip 9 also applies to the command line</a>.</em></p> +<h2 id="Tip-4-Use-Relative-Paths"><a href="#Tip-4-Use-Relative-Paths" class="headerlink" title="Tip 4: Use Relative Paths"></a>Tip 4: Use Relative Paths</h2><p>Sometimes, your script will reference another resource; for instance, you need to read the contents of a <code>.txt</code> file somewhere. You can use absolute path, as in:</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">File.ReadAllLines @"C:/data/myfile.txt"</span><br></pre></td></tr></table></figure> + +<blockquote> +<p>Pre-pending a string with <code>@</code> makes it a verbatim string, and ignore escape sequences, such as <code>\</code>.</p> +</blockquote> +<blockquote> +<p>Use <code>/</code> rather than <code>\</code>, so that path work both on Windows and Mono.</p> +</blockquote> +<p>However, if that resource lives in a location relative to your script, consider using relative path, so that you can move your script folder around without breaking it.</p> +<p>Relative paths can be a bit tricky; for instance, running the following code interactively…</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">System.Environment.CurrentDirectory</span><br></pre></td></tr></table></figure> + +<p>… produces a potentially unexpected result in FSI:</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">val it : string = "C:\Users\Mathias Brandewinder\AppData\Local\Temp"</span><br><span class="line">></span><br></pre></td></tr></table></figure> + +<p>You can avoid these issues by using built-in constants, which refer respectively to the directory where the script lives, the script file name, and the current line of the script:</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">__SOURCE_DIRECTORY__</span><br><span class="line">__SOURCE_FILE__</span><br><span class="line">__LINE__</span><br></pre></td></tr></table></figure> + +<p>So if your folder structure was along these lines…</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">root</span><br><span class="line"> /src/script.fsx</span><br><span class="line"> /data/data.txt</span><br></pre></td></tr></table></figure> + +<p>… you could refer to the data file <code>data.txt</code> from your script like this:</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">let path = System.IO.Path.Combine(__SOURCE_DIRECTORY__,"..","data/data.txt")</span><br><span class="line">System.IO.File.ReadAllText path</span><br></pre></td></tr></table></figure> + +<h2 id="Tip-5-Including-Assemblies"><a href="#Tip-5-Including-Assemblies" class="headerlink" title="Tip 5: Including Assemblies"></a>Tip 5: Including Assemblies</h2><p>By default, FSI loads <code>FSharp.Core</code> and nothing else. If you want to use <code>System.DateTime</code>, you will need to first <code>open System</code> in your script. If you want to use an assembly that is not part of the standard .NET distribution, you will need to reference it first using <code>#r</code>. Imagine for instance that you installed the Nuget package <code>fsharp.data</code>; to use it in your script, you would do something like:</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">#r @"../packages/FSharp.Data.2.2.5/lib/net40/FSharp.Data.dll"</span><br><span class="line">open FSharp.Data</span><br></pre></td></tr></table></figure> + +<blockquote> +<p>When you execute <code>open System</code> in interactive, don’t worry if nothing seems to happen: the only result is a new <code>></code> showing up in FSI.</p> +</blockquote> +<p>For assemblies that are part of .NET but not referenced by default, you can use a shorter version:</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">#r @"System.Xaml"</span><br><span class="line">open System.Xaml</span><br></pre></td></tr></table></figure> + +<blockquote> +<p>In Visual Studio, you can right-click a reference from Solution Explorer, and send to F# interactive. You can then directly open it, and start using it in FSI.</p> +</blockquote> +<p><em>Updated, Feb 20: <a target="_blank" rel="noopener" href="https://twitter.com/sergey_tihon">Sergey Tihon</a> shared an interesting comment, explaining where Tip 5 can sometimes go wrong. I’d say, try Tip 5 first, but be aware that this might at times not quite work:</em></p> +<blockquote> +<p><a target="_blank" rel="noopener" href="https://twitter.com/brandewinder">@brandewinder</a> don’t load assemblies like in Tip 5 ) <a target="_blank" rel="noopener" href="https://t.co/Owft1NmPoo">https://t.co/Owft1NmPoo</a></p> +<p>— Sergey Tihon (@sergey_tihon) <a target="_blank" rel="noopener" href="https://twitter.com/sergey_tihon/status/696395229285523456">February 7, 2016</a></p> +</blockquote> +<p><em>Updated, Feb 20: <a target="_blank" rel="noopener" href="https://twitter.com/dsyme">F# open source contributor Don Syme</a> share a related nice trick:</em></p> +<blockquote> +<p><a target="_blank" rel="noopener" href="https://twitter.com/jeroldhaas">@jeroldhaas</a> <a target="_blank" rel="noopener" href="https://twitter.com/sergey_tihon">@sergey_tihon</a> <a target="_blank" rel="noopener" href="https://twitter.com/brandewinder">@brandewinder</a> Use <a target="_blank" rel="noopener" href="https://twitter.com/hashtag/I?src=hash">#I</a> <strong>SOURCE_DIRECTORY</strong>, it is wondrous, very satisfying. All relative paths then work</p> +<p>— Don Syme (@dsyme) <a target="_blank" rel="noopener" href="https://twitter.com/dsyme/status/696429115184955393">February 7, 2016</a></p> +</blockquote> +<h2 id="Tip-6-Use-Paket"><a href="#Tip-6-Use-Paket" class="headerlink" title="Tip 6: Use Paket"></a>Tip 6: Use <code>Paket</code></h2><p>The Nuget package manager is useful to consume existing packages. However, by default, Nuget stores assemblies in a folder that includes the package version number. This is very impractical for a script. In our example above, if <code>fsharp.data</code> gets an update, our script reference will be broken once we update the Nuget package:</p> +<p><code>#r @"../packages/FSharp.Data.2.2.5/lib/net40/FSharp.Data.dll"</code></p> +<p>Fixing the script requires manually editing the version number in the path, which quickly becomes a pain. <a target="_blank" rel="noopener" href="https://fsprojects.github.io/Paket/"><strong>Paket</strong></a> provides a better experience, because it stores packages without the version number, in this case, under:</p> +<p><code>#r @"../packages/FSharp.Data/lib/net40/FSharp.Data.dll"</code></p> +<p>Your scripts will now gracefully handle version number changes.</p> +<p>If you end up consuming numerous packages, you can make your life even easier, by referencing paths where assemblies might be searched for, using <code>#I</code>:</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">#I @"../packages/</span><br><span class="line">#r @"FSharp.Data/lib/net40/FSharp.Data.dll"</span><br></pre></td></tr></table></figure> + +<blockquote> +<p>If your primary goal is to “just script”, consider using <a target="_blank" rel="noopener" href="https://atom.io/">Atom</a> or <a target="_blank" rel="noopener" href="https://code.visualstudio.com/">VSCode</a>, with the <a target="_blank" rel="noopener" href="http://ionide.io/">Ionide plugin</a>. You can create and run free-standing F# scripts, with beautiful <a target="_blank" rel="noopener" href="http://ionide.io/#paket-integration">Paket integration</a>.</p> +</blockquote> +<h2 id="Tip-7-Include-Files"><a href="#Tip-7-Include-Files" class="headerlink" title="Tip 7: Include Files"></a>Tip 7: Include Files</h2><p>You might want to use the code from an existing file in your script. Suppose that we have a code file <code>Code.fs</code> somewhere, looking like this:</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">namespace Mathias</span><br><span class="line"></span><br><span class="line">module Common =</span><br><span class="line"> let hello name = sprintf "Hello, %s" name</span><br></pre></td></tr></table></figure> + +<p>You can use that code from your script, by using the <code>#load</code> directive:</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">#load "Code.fs"</span><br><span class="line">open Mathias.Common</span><br><span class="line">hello "World"</span><br></pre></td></tr></table></figure> + +<blockquote> +<p>You might have to close and re-open the script file if you end up changing the contents of the file.</p> +</blockquote> +<blockquote> +<p>If the file you are attempting to load contains references to other assemblies or files, you might get an error on the <code>#load</code> statement: “One or more errors in loaded files. The namespace or module … is not defined”. Simply reference the missing assemblies above the <code>#load</code> statement, so that your script uses the same dependencies as the file it refers to.</p> +</blockquote> +<h2 id="Tip-8-Profile-your-Code-with-time"><a href="#Tip-8-Profile-your-Code-with-time" class="headerlink" title="Tip 8: Profile your Code with #time"></a>Tip 8: Profile your Code with #time</h2><p>Another handy directive, <code>#time</code>, turns on basic profiling. Once it is executed, for every block of code you send for execution you will see timing and garbage collection information. For instance, running this code…</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">#time</span><br><span class="line">[| 1 .. 10000000 |] |> Array.map (fun x -> x * x)</span><br></pre></td></tr></table></figure> + +<p>… will produce the following in FSI:</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">--> Timing now on</span><br><span class="line"></span><br><span class="line">Real: 00:00:00.887, CPU: 00:00:00.828, GC gen0: 2, gen1: 2, gen2: 2</span><br><span class="line">val it : int [] =</span><br><span class="line"> [|1; 4; 9; 16; 25; 36; 49; // snipped for brevity</span><br></pre></td></tr></table></figure> + +<p>We get the wall time and CPU time it took, as well as some information about garbage collection in generations 0, 1 and 2. This would not replace a full-blown profiler, but this is an awfully convenient tool to figure out quickly if there are obvious ways to improve a piece of code.</p> +<p>Note that every time you execute <code>#time</code>, the timer will be switched from on to off, or vice-versa. This is not always convenient; you can also explicitly set it to the desired state, like this:</p> +<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">#time "on"</span><br><span class="line">// everything now is timed</span><br><span class="line">#time "off"</span><br></pre></td></tr></table></figure> + +<blockquote> +<p>If you are interested in profiling, you should take a look at <a target="_blank" rel="noopener" href="http://www.privateeye.io/">PrivateEye</a>; check out <a target="_blank" rel="noopener" href="https://twitter.com/gregyoung">Greg Young</a>’s <a target="_blank" rel="noopener" href="https://vimeo.com/131637366">talk at NDC Oslo 2015</a> to get a feel for what it does.</p> +</blockquote> +<h2 id="Tip-9-Turn-64-bits-on"><a href="#Tip-9-Turn-64-bits-on" class="headerlink" title="Tip 9: Turn 64-bits on"></a>Tip 9: Turn 64-bits on</h2><p>Hat tip to <a target="_blank" rel="noopener" href="https://twitter.com/rickasaurus">Rick Minerich</a> for that one. I’ll refer you to his blog post to see how to <a target="_blank" rel="noopener" href="http://richardminerich.com/2013/03/setting-up-fsharp-interactive-for-machine-learning-with-large-datasets/">set FSI to 64 bits to handle large datasets</a>.</p> +<h2 id="Tip-10-Bonus-Material"><a href="#Tip-10-Bonus-Material" class="headerlink" title="Tip 10: Bonus Material"></a>Tip 10: Bonus Material</h2><p>Did you know that you could…</p> +<ul> +<li><a target="_blank" rel="noopener" href="https://channel9.msdn.com/Events/Visual-Studio/Visual-Studio-2015-Final-Release-Event/Six-Quick-Picks-from-Visual-F-40">debug an F# script? (around 0:12:35 in)</a></li> +<li><a target="_blank" rel="noopener" href="http://www.swensensoftware.com/fseye">inspect the objects in your FSI session with <strong>FsEye</strong>?</a></li> +<li>change the FSI font size in Tools/Options/Environment/Fonts and Colors/Show Settings for/F# Interactive?</li> +<li>add your own pretty-printer to FSI, <a target="_blank" rel="noopener" href="https://github.com/mathnet/mathnet-numerics/blob/master/src/FSharp/MathNet.Numerics.fsx">like this</a>?</li> +<li>mess with your coworkers’ mental sanity, by executing <code>(*</code> (opening a multiline comment) in FSI? (credit: <a target="_blank" rel="noopener" href="https://twitter.com/tomaspetricek">Tomas</a>)</li> +<li>simplify loading references with Visual Studio and Power Tools? (credit: <a target="_blank" rel="noopener" href="https://twitter.com/kitlovesfsharp">Kit Eason</a>, see details in comments section).</li> +</ul> +<p>And again… if you are not using the <a target="_blank" rel="noopener" href="http://fsprojects.github.io/VisualFSharpPowerTools/">Visual F# Power Tools</a>, you are missing out:</p> +<blockquote> +<p>“Don’t let your friends try <a target="_blank" rel="noopener" href="https://twitter.com/hashtag/fsharp?src=hash">#fsharp</a> without installing <a target="_blank" rel="noopener" href="https://twitter.com/FSPowerTools">@FSPowerTools</a>.” <a target="_blank" rel="noopener" href="https://twitter.com/dsyme">@dsyme</a> at <a target="_blank" rel="noopener" href="https://twitter.com/hashtag/ndclondon?src=hash">#ndclondon</a></p> +<p>— Tomas Petricek (@tomaspetricek) <a target="_blank" rel="noopener" href="https://twitter.com/tomaspetricek/status/687934127627186176">January 15, 2016</a></p> +</blockquote> +<p>That’s what I got! I am sure I forgot some - do you have a useful or favorite trick to share?</p> + +</div> + +<script> + window.onload = detectors(); +</script> + <div class="post-footer"> + <div class="h-line-primary"></div> + <nav class="post-nav"> + <div class="prev-item"> + + <div class="icon arrow-left"></div> + <div class="post-link"> + <a href="/2024/10/18/Generalised-signature/">Prev</a> + </div> + + </div> + <div class="next-item"> + + <div class="icon arrow-right"></div> + <div class="post-link"> + <a href="/2024/10/18/Building-custom-fibers-library-in-FSharp/">Next</a> + </div> + + </div> + </nav> +</div> + + + <div class="post-comment"> + + + + + + + +</div> + + +</article> + </div> + </div> + + <div class="footer"> + <div class="flex-container"> + <div class="footer-text"> + + + | + + + 希望路过的人可以添点柴火让这里暖和点 + + </div> + </div> +</div> + + </div> + + + <div class="search-popup"> + <div class="search-popup-overlay"> + </div> + <div class="search-popup-window" > + <div class="search-header"> + <div class="search-input-container"> + <input autocomplete="off" autocapitalize="off" maxlength="80" + placeholder="Search Anything" spellcheck="false" + type="search" class="search-input"> + </div> + <div class="search-close-btn"> + <div class="icon close-btn"></div> + </div> + </div> + <div class="search-result-container"> + </div> + </div> +</div> + +<script> + const searchConfig = { + path : "/search.xml", + top_n_per_article: "1", + unescape : "false", + trigger: "auto", + preload: "false" + } +</script> +<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/search.js"></script> +<script src="/js/search.js"></script> + + + + </body> +</html> diff --git a/2024/10/18/Building-custom-fibers-library-in-FSharp/index.html b/2024/10/18/Building-custom-fibers-library-in-FSharp/index.html new file mode 100644 index 00000000..13709c45 --- /dev/null +++ b/2024/10/18/Building-custom-fibers-library-in-FSharp/index.html @@ -0,0 +1,463 @@ +<!DOCTYPE html> +<html lang="en"> + <head> + <meta charset="UTF-8"> +<meta name="viewport" + content="width=device-width, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0"> +<meta http-equiv="X-UA-Compatible" content="ie=edge"> + + <meta name="author" content="韩暮秋"> + + + <meta name="subtitle" content="暮秋小屋"> + + + <meta name="description" content="这里是暮秋小屋,思念和灵感的寄存处"> + + + <meta name="keywords" content="韩暮秋,MuqiuHan,'Muqiu Han', 'muqiu han', muqiuhan"> + + + + +<title>Building custom fibers library in FSharp | 暮秋小屋</title> + + + + <link rel="icon" href="/favicon.ico"> + + + +<style> + @import url('https://fonts.googleapis.com/css2?family=Inter:wght@300;400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&family=Roboto+Mono&display=swap'); +</style> + + + + <!-- stylesheets list from _config.yml --> + + <link rel="stylesheet" href="/css/style.css"> + + + + + + <!-- scripts list from _config.yml --> + + <script src="/js/frame.js"></script> + + + + + + <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script> + <script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script> + + + + + + + + <meta name="generator" content="Hexo 6.3.0"></head> + <body> + <div class="mask-border"> + </div> + + <div class="wrapper"> + + <div class="header"> + <div class="flex-container"> + <div class="header-inner"> + <div class="site-brand-container"> + <a href="/"> + + 暮秋小屋 + + </a> + </div> + <div id="menu-btn" class="menu-btn" onclick="toggleMenu()"> + Menu + </div> + <nav class="site-nav"> + <ul class="menu-list"> + + + <li class="menu-item"> + <a href="/">主页</a> + </li> + + + + <li class="menu-item"> + <a href="/categories/gallery/">日记本</a> + </li> + + + + <li class="menu-item"> + <a href="/tags/Medicine/">医学</a> + </li> + + + + <li class="menu-item"> + <a href="/tags/Technique/">计算机科学</a> + </li> + + + + <li class="menu-item"> + <a href="/tags/Life/">生活</a> + </li> + + + + <li class="menu-item"> + <a href="/about">关于</a> + </li> + + + + <li class="menu-item search-btn"> + <a href="#">Search</a> + </li> + + </ul> + </nav> + </div> + </div> +</div> + + + <div class="main"> + <div class="flex-container"> + <article id="post"> + + + <div class="post-head"> + <div class="post-info"> + <div class="tag-list"> + + + <span class="post-tag"> + <a href="/tags/Technique/"> + Technique + </a> + </span> + + <span class="post-tag"> + <a href="/tags/F/"> + F# + </a> + </span> + + <span class="post-tag"> + <a href="/tags/Archive/"> + Archive + </a> + </span> + + + </div> + <div class="post-title"> + + + Building custom fibers library in FSharp + + + </div> + <span class="post-date"> + Oct 18, 2024 + </span> + </div> + <div class="post-img"> + + <div class="h-line-primary"></div> + + </div> +</div> + <div class="post-content"> + <p>Over the course of last few months on this blog post, I’ve been sharing about internals and how-to of different concurrency patters. We discussed how to <a target="_blank" rel="noopener" href="https://www.bartoszsypytkowski.com/build-your-own-actor-model/">implement our own actors</a> and specific <a target="_blank" rel="noopener" href="https://www.bartoszsypytkowski.com/thread-safety-with-affine-thread-pools/">affinity-based thread pool</a>. Today we’ll focus of the most dominant pattern present in modern programming nowadays: fibers, also known as coroutines, futures, tasks, green threads or user-space threads.</p> +<p>The general idea is simple - we want a fine-grained concurrency primitive, that will let us easily compose chain of operations in sequential manner. Of course we could use threads here, but the question is: are threads fine-grained? In many managed languages with OS threads exposed, they can be quite heavy eg. by default in .NET each thread takes around 1MB of memory and requires calling kernel code to cooperate with other threads, which is an expensive operation on its own.</p> +<p>What we’re after, are more lightweight structures (less than 1kB), that can live fully in a user space, so that we can have even millions of them cooperating frequently with each other without heavy performance penalties.</p> +<p>Before we begin, I think it’s good to discuss different designs. We’ll cover several different topics to be able to make more informed decisions, that we’re up to apply to our own solution.</p> +<h3 id="Preemptive-vs-cooperative-scheduler"><a href="#Preemptive-vs-cooperative-scheduler" class="headerlink" title="Preemptive vs cooperative scheduler"></a>Preemptive vs cooperative scheduler</h3><p>Scheduler is a subsystem, which direct responsibility is to assign CPU core processing power to a particular fiber. It’s also responsible for coordinating fibers execution. The two most common categories of schedulers are preemptive and cooperative.</p> +<p>A <strong>preemptive</strong> scheduler is the one, that’s always in control of fiber execution. It’s able to decide on its own, when fiber can be started and stopped. The most obvious example of such is a thread scheduler existing on most operating systems.</p> +<p>Preemptive scheduler usually works in one of two ways:</p> +<ul> +<li>Time based scheduler takes a quant of CPU time and gives it to a given fiber, which ten can execute its logic until it reaches its execution time limit (of course, it can finish earlier). This is how OS thread scheduler, but also how Go goroutine scheduler works.</li> +<li>Another variant is step-based scheduler, which splits fiber’s function body into series of (more or less equal) steps. Then each fiber is given a number of steps to execute before preemption occurs. Example of such is Erlang’s BEAM - it simply allows each process to execute up to 2000 “reductions”, where each reduction is basically a function call. <em>And since in Erlang there are no loops, only tail-recursive functions, this approach works well for long-living iterative processes as well.</em></li> +</ul> +<p>One of the problems with preemptive schedulers is that they usually need some kind of involvement from the compiler or hosting virtual machine in order to work. For this reason, most of the fiber libraries use <strong>cooperative</strong> schedulers to perform their work.</p> +<p>A <strong>cooperative</strong> scheduler doesn’t have a concept of preemption - once started by the scheduler, a fiber will execute until it doesn’t give back the control willingly. This is often done with dedicated programming constructs, and often is known as yielding, parking or awaiting.</p> +<p>In cooperative variant, a fiber body is usually split into series of discrete steps, between which fiber gives control back to the scheduler.</p> +<p>Keep in mind that these two are not mutually exclusive - a preemptive scheduler often provides a way for a fiber to return control back to it when it’s known that fiber won’t be executing any longer eg. because it has been put to sleep for a while.</p> +<h3 id="Stackless-vs-stackful"><a href="#Stackless-vs-stackful" class="headerlink" title="Stackless vs. stackful"></a>Stackless vs. stackful</h3><p>A concept, that’s somewhat related to a topic above is the idea of stackless and stackful coroutines.</p> +<p>A stackful variant is aware of underlying execution stack and can preserve/restore parts of it when yielding/continuing a fiber. Examples of this approach could be Go, Lua, Python asyncio and in the future, also <a target="_blank" rel="noopener" href="https://www.youtube.com/watch?v=NV46KFV1m-4&ref=bartoszsypytkowski.com">Java Loom</a> project. Implementing such option (if it’s not implemented by a runtime already) usually requires diving deep into low-level internals, since execution stack is not something that most managed languages offers the users to play with, and doing so without coordination with runtime can cause problems - like determining liveness of objects for GC purposes.</p> +<p>Stackless coroutine usually captures locals that we want to preserve as part of callback object (lambda), that is allocated as an object on the heap and scheduled on yield continuation. These steps are usually visible directly in code (eg. await in C#, Rust and JavaScript, but also joints of Scala for-comprehensions, bang-suffix in F# or Haskell do-notation), but sometimes can be implicit like in case of Kotlin. Take into account that while many languages offer syntax support for those constructs, it’s not explicitly necessary to work - take a look at JavaScript and <code>Promise.then</code> as an example.</p> +<p>Stackless coroutines usually construct their logic around one of two concepts:</p> +<ol> +<li>Finite state machines - this variant is usually faster and can be encoded manually (example of such case is Akka actors), but for a human eye it usually doesn’t really read as a sequential step-by-step program execution, unless it has some support from the compiler itself (see: C# and Rust).</li> +<li>Monadic sequencing via bind/flatMap operator, which is very popular in functional languages. While we cover it in more details in the rest of this blog post, for now it’s enough to say that it’s a way to chain callback-based behaviors together in a way, that resembles standard sequential code.</li> +</ol> +<p>For sure one of the advantages of stackful coroutines is that they’re <em>mono-colored</em>: you can yield/continue coroutine execution from within any other function, while in the stackless variant splits your world into <em>two-colored</em> functions - synchronous and <strong>async</strong>hronous - where async one can be only called and yielded safely (without blocking underlying OS thread) from within another async function.</p> +<h3 id="Eager-vs-lazy-fibers"><a href="#Eager-vs-lazy-fibers" class="headerlink" title="Eager vs lazy fibers"></a>Eager vs lazy fibers</h3><p>We already mentioned two important events in fiber execution life cycle - starting and parking. Here I briefly discuss about different design decisions on when to start a fiber execution.</p> +<p><strong>Eager</strong> execution means, that fiber is started automatically after its creation. An example of such are Scala <code>Future[A]</code> and JavaScript <code>Promise</code>. Since execution process starts right away, we’re willingly resign from a certain degree of control over how or when to execute given fiber. Usually this is solved by wrapping a fiber creation into another function or lambda.</p> +<p><strong>Lazy</strong> execution is much more common and preferred way of work, as it allows us to separate place where we want to define our asynchronous sequence of steps from the place, where the execution details are defined. It’s used in C# TPL as well as pretty much in all functional languages implementations (excluding Scala futures mentioned earlier).</p> +<h3 id="Interruption"><a href="#Interruption" class="headerlink" title="Interruption"></a>Interruption</h3><p>There are also few decisions regarding premature escaping the fiber execution, also known as interruption/cancelation: one of them requires passing special object - a <strong>token</strong> - between method calls and explicit checking for its completion. It is how C# Tasks work. However putting such requirement onto the API user can be cumbersome and error-prone option. Therefore pretty much every other coroutine library either allows to direcly interrupt a fiber or (like in case of F# Async) passes cancelation tokens and check if they were triggered under the hood.</p> +<h2 id="Implementation"><a href="#Implementation" class="headerlink" title="Implementation"></a>Implementation</h2><p>Since we talked a bit about various approaches, let’s get to the meat of this blog post: implementing our own coroutine library in F#. So, what properties will it have?:</p> +<ol> +<li>We use cooperative scheduling (we don’t want to tweak the compiler) of stackless fibers with support from F# computation expression for nice syntax.</li> +<li>We use simple approach by defining custom <code>bind</code> operator with support from F# computation expressions. No state machines.</li> +<li>We’ll use lazy invocation.</li> +<li>We’ll make use of implicitly passed cancelation tokens. We’ll handle them directly inside the linking code.</li> +</ol> +<p>All of these give us in very similar approach to that found inside of native F# <code>Async</code> data type. To begin with, we’ll simply define the shape of our fiber.</p> +<p>Underneath, pretty much every cooperative stackless coroutine approach uses callbacks to drive the flow of synchronous segments of code to be executed one after another. So what we need is a callback which takes a result of previous coroutine and schedules in within some context of execution:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">type</span> <span class="title class_">Fiber</span><span class="operator"><</span><span class="symbol">'a</span><span class="operator">></span> <span class="operator">=</span> Fiber <span class="keyword">of</span> (ExecutionContext <span class="operator">-></span> FiberCallback<span class="operator"><</span><span class="symbol">'a</span><span class="operator">></span> <span class="operator">-></span> <span class="type">unit</span>)</span><br></pre></td></tr></table></figure> + +<p>Here we’ll represent Fiber as a simple single-case discriminated union. We could as well define other specialized cases, like:</p> +<ul> +<li>Situation when coroutine is executed immediately and doesn’t need to be awaited on: think about variant of <code>ValueTask</code> from C# Task Parallel Library.</li> +<li>Case when coroutine fails - in that case we might want to store an artificial tracing context that would allow us to create nicely-formatted “stack traces”: since .NET Core 2.1, C# already provides similar solution however AFAIK it’s been solved differently.</li> +</ul> +<p>Ok, but what are <code>ExecutionContext</code> and <code>FiberCallback<'a></code>? Let’s start from callback. We can represent it as follows:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">type</span> <span class="title class_">FiberCallback</span><span class="operator"><</span><span class="symbol">'a</span><span class="operator">></span> <span class="operator">=</span> FiberResult<span class="operator"><</span><span class="symbol">'a</span><span class="operator">></span> <span class="operator">-></span> unit</span><br></pre></td></tr></table></figure> + +<p>It’s just a simple function, which takes result of previous fiber execution and handles it. What’s the <code>FiberResult<'a></code> then?</p> +<p>Our fiber can complete successfully (returning a value) or fail with an exception. We’ll be conservative here and won’t go into more typed world of <a target="_blank" rel="noopener" href="http://degoes.net/articles/bifunctor-io?ref=bartoszsypytkowski.com">IO bifunctor</a>. We can easy define these possible outputs in F# using <code>Result<'a, exn></code>.</p> +<p>Question is: is that exhaustive? Well… no. As we already mentioned, there’s a 3rd state, often overlooked or conflated with failure: a canceled fiber. A canceled fiber doesn’t produce any output - since it was canceled before completion. In F# we already know how to represent an absence of value - simply use an option. Therefore our ultimate Fiber result type could look like this:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">type</span> <span class="title class_">FiberResult</span><span class="operator"><</span><span class="symbol">'a</span><span class="operator">></span> <span class="operator">=</span> Result<span class="operator"><</span><span class="symbol">'a</span>, exn<span class="operator">></span> option</span><br></pre></td></tr></table></figure> + +<p>Now, the <code>ExecutionContext</code>. While it can be compound of many different capabilities throughout the system - even to serve as functional equivalent of dependency injection - here I’ll use it only for implicit passing of specific scheduler info and cancelation tokens from one fiber to another.</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">type</span> <span class="title class_">ExecutionContext</span> <span class="operator">=</span> IScheduler <span class="operator">*</span> Cancel</span><br></pre></td></tr></table></figure> + +<p><code>IScheduler</code> interface is used to abstract component responsible for running our fibers. At the moment all we need is an ability to schedule fiber execution:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">[<Interface>]</span></span><br><span class="line"><span class="keyword">type</span> <span class="title class_">IScheduler</span> <span class="operator">=</span> </span><br><span class="line"> <span class="keyword">abstract</span> Schedule<span class="operator">:</span> (<span class="type">unit</span> <span class="operator">-></span> <span class="type">unit</span>) <span class="operator">-></span> <span class="type">unit</span></span><br></pre></td></tr></table></figure> + +<p>While the name and signature imply multithreaded execution model, it doesn’t have to be the case. We can even implement scheduler which will simulate everything on a single core.</p> +<p>For now, we can simply implement a scheduler API on top of our standard .NET thread pool:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> Scheduler</span><br><span class="line"></span><br><span class="line"><span class="keyword">open</span> System.Threading</span><br><span class="line"></span><br><span class="line"><span class="keyword">let</span> shared <span class="operator">=</span> </span><br><span class="line"> { <span class="keyword">new</span> ISchedule <span class="keyword">with</span></span><br><span class="line"> <span class="keyword">member</span> __.Schedule fn <span class="operator">=</span> </span><br><span class="line"> ThreadPool.QueueUserWorkItem(WaitCallback (<span class="keyword">fun</span> _ <span class="operator">-></span> fn())) <span class="operator">|></span> <span class="built_in">ignore</span> }</span><br></pre></td></tr></table></figure> + +<h3 id="Cancellation"><a href="#Cancellation" class="headerlink" title="Cancellation"></a>Cancellation</h3><p>Now it’s a time for cancellation tokens. Of course we could just make use of a flag - conceptually working like native .NET <code>CancellationToken</code>. However given implicit cancellation, it may not be enough. Example:</p> +<blockquote> +<p>Imagine, that inside our fiber we’re scheduling the race between two other fibers ie. one writing data to a file and other which will complete after timeout. Now, whenever one of them completes first, we want to cancel another one to stop wasting resources for result that no longer matters.</p> +</blockquote> +<p>This simple scenario is similar to what .NET <code>Task.WhenAny</code> is used - with a difference that, unlike TPL, we want to actually cancel other executing tasks instead of letting them run (potentially forever) :D</p> +<p>Now, since our cancellation is not explicit, we need to deal with few things:</p> +<ol> +<li>Whenever parent fiber is cancelled, all child fibers it spawned are also cancelled.</li> +<li>Whenever we cancel a fiber that loose the race, we <strong>don’t want</strong> to accidentally cancel a token of its parent.</li> +</ol> +<p>This behavior implies at least using two separate tokens, however in practice it will be more pragmatic to make our <code>Cancel</code> token work as a tree hierarchy - this way we can easily keep track of things and support more complex scenarios.</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">[<Sealed;AllowNullLiteral>]</span></span><br><span class="line"><span class="keyword">type</span> <span class="title class_">Cancel</span>(parent<span class="operator">:</span> Cancel) <span class="operator">=</span></span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">mutable</span> flag<span class="operator">:</span> <span class="type">int</span> <span class="operator">=</span> <span class="number">0</span></span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">mutable</span> children<span class="operator">:</span> Cancel <span class="type">list</span> <span class="operator">=</span> []</span><br><span class="line"> <span class="keyword">new</span>() <span class="operator">=</span> Cancel(<span class="literal">null</span>)</span><br><span class="line"> <span class="comment">/// Check if token was cancelled</span></span><br><span class="line"> <span class="keyword">member</span> __.Cancelled <span class="operator">=</span> flag <span class="operator">=</span> <span class="number">1</span></span><br><span class="line"> <span class="comment">/// Remove child token</span></span><br><span class="line"> <span class="keyword">member</span> <span class="keyword">private</span> __.RemoveChild(child) <span class="operator">=</span> </span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">rec</span> loop child <span class="operator">=</span></span><br><span class="line"> <span class="keyword">let</span> children' <span class="operator">=</span> children</span><br><span class="line"> <span class="keyword">let</span> nval <span class="operator">=</span> children' <span class="operator">|></span> List.filter ((<span class="operator"><></span>) child)</span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">not</span> (obj.ReferenceEquals(children', Interlocked.CompareExchange(<span class="operator">&</span>children, nval, children')))</span><br><span class="line"> <span class="keyword">then</span> loop child</span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">not</span> (List.isEmpty children) <span class="keyword">then</span> loop child</span><br><span class="line"> <span class="comment">/// Create a new child token and return it.</span></span><br><span class="line"> <span class="keyword">member</span> this.AddChild () <span class="operator">=</span></span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">rec</span> loop child <span class="operator">=</span></span><br><span class="line"> <span class="keyword">let</span> children' <span class="operator">=</span> children</span><br><span class="line"> <span class="keyword">if</span> (obj.ReferenceEquals(children', Interlocked.CompareExchange(<span class="operator">&</span>children, child<span class="operator">::</span>children', children')))</span><br><span class="line"> <span class="keyword">then</span> child</span><br><span class="line"> <span class="keyword">else</span> loop child</span><br><span class="line"> loop (Cancel this)</span><br><span class="line"> <span class="comment">/// Cancel a token</span></span><br><span class="line"> <span class="keyword">member</span> this.Cancel() <span class="operator">=</span></span><br><span class="line"> <span class="keyword">if</span> Interlocked.Exchange(<span class="operator">&</span>flag, <span class="number">1</span>) <span class="operator">=</span> <span class="number">0</span> <span class="keyword">then</span></span><br><span class="line"> <span class="keyword">for</span> child <span class="keyword">in</span> Interlocked.Exchange(<span class="operator">&</span>children, []) <span class="keyword">do</span> child.Cancel()</span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">not</span> (isNull parent) <span class="keyword">then</span> parent.RemoveChild(this)</span><br><span class="line"></span><br></pre></td></tr></table></figure> + +<p>The general idea is simple: every new cancellation token (except root) may have a parent and a list of children. Canceling parent means canceling its children as well. After cancellation, we need to unpin child from its parent (therefore need for <code>RemveChild</code> operation) to avoid memory leaks.</p> +<h5 id="Lock-free-updates"><a href="#Lock-free-updates" class="headerlink" title="Lock-free updates"></a>Lock-free updates</h5><p>What might be confusing for some in the code above, are recursive loops inside of <code>AddChild</code>/<code>RemoveChild</code> operations. This is a good place to introduce lock-free algorithms: we use atomic operations from <a target="_blank" rel="noopener" href="https://www.bartoszsypytkowski.com/building-custom-fibers-library-in-f/docs.microsoft.com/en-us/dotnet/api/system.threading.interlocked">Interlocked</a> class to make sure that we can replace field references within a single CPU instruction, therefore making such field update safe without synchronized access. This is also known as Compare-And-Swap semantics.</p> +<p>This alone however is not enough, as <code>Interlocked.CompareExchange(&field, new', old)</code> can only safely replace a single field with new value if it contained an old one. This means that you cannot safely add or remove element to the list. So what can we do?</p> +<ol> +<li>We’re taking a value from the field.</li> +<li>Update that value.</li> +<li>Conditionally put it back again. What if in the meantime the field was already replaced by another concurrently running thread? In that case <code>Interlocked.CompareExchange</code> will return field value other that the one we read in step 1. This is why we compare its result with the variable we expected.</li> +<li>If the expectation fails, we’ll retry - hence a recursive loop. Eventually even in high contention scenarios we should be able to complete after few retries. Given cheap and idempotent update operation, this still will be way faster than trying to call kernel code to obtain mutex/semaphore lock.</li> +</ol> +<p>While this may sound like something error prone - we can potentially add the same element multiple times - in practice it’s safe, because our collection here is an immutable data structure. Adding the same element multiple times without updating the reference will always produce the same result.</p> +<h3 id="Back-on-track…"><a href="#Back-on-track…" class="headerlink" title="Back on track…"></a>Back on track…</h3><p>Now we have pretty much all core structures. We’re ready to start building our fiber operators. Starting from the basic ones - a successfully completed fiber and the failed one:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> success r <span class="operator">=</span> Fiber <span class="operator"><|</span> <span class="keyword">fun</span> (_, c) next <span class="operator">-></span> </span><br><span class="line"> <span class="keyword">if</span> c.Cancelled <span class="keyword">then</span> next <span class="literal">None</span> <span class="keyword">else</span> next (<span class="literal">Some</span> (<span class="literal">Ok</span> r))</span><br><span class="line"></span><br><span class="line"><span class="keyword">let</span> fail ex <span class="operator">=</span> Fiber <span class="operator"><|</span> <span class="keyword">fun</span> (_, c) next <span class="operator">-></span> </span><br><span class="line"> <span class="keyword">if</span> c.Cancelled <span class="keyword">then</span> next <span class="literal">None</span> <span class="keyword">else</span> next (<span class="literal">Some</span> (<span class="literal">Error</span> ex))</span><br></pre></td></tr></table></figure> + +<p>Here, we simply pass a result/error to our Fiber callback:</p> +<ul> +<li>Cancelled fiber call <code>next</code> callback with <code>None</code> - as fibers cancelled before completion produce output .</li> +<li>Successful call results in passing <code>Some (Ok result)</code> to a callback…</li> +<li>… while failed result can be identified with <code>Some (Error exception)</code>.</li> +</ul> +<p>You’ll be able to see a cancellation check made here as preamble of pretty much every operator body, which we’ll define. While it may sound cumbersome remember: we do that so that users of our fibers won’t have to :)</p> +<p>Next very important operation is result mapping - we want to map result of one fiber into something else, returning another (lazy) fiber:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> mapResult (fn<span class="operator">:</span> <span class="type">Result</span><span class="operator"><</span><span class="symbol">'a</span><span class="operator">></span> <span class="operator">-></span> <span class="type">Result</span><span class="operator"><</span><span class="symbol">'b</span><span class="operator">></span>) (Fiber call) <span class="operator">=</span> Fiber <span class="operator"><|</span> <span class="keyword">fun</span> (s, c) next <span class="operator">-></span></span><br><span class="line"> <span class="keyword">if</span> c.Cancelled <span class="keyword">then</span> next <span class="literal">None</span></span><br><span class="line"> <span class="keyword">else</span> </span><br><span class="line"> <span class="keyword">try</span> </span><br><span class="line"> call (s, c) (<span class="keyword">fun</span> result <span class="operator">-></span></span><br><span class="line"> <span class="keyword">if</span> c.Cancelled <span class="keyword">then</span> next <span class="literal">None</span></span><br><span class="line"> <span class="keyword">else</span> next (Option.map fn result))</span><br><span class="line"> <span class="keyword">with</span> e <span class="operator">-></span> next (<span class="literal">Some</span> (<span class="literal">Error</span> e))</span><br></pre></td></tr></table></figure> + +<p>We can use this function to compose more traditionally-looking <code>map</code> function…</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> map (fn<span class="operator">:</span> <span class="symbol">'a</span> <span class="operator">-></span> <span class="symbol">'b</span>) fiber <span class="operator">=</span> mapResult (Result.map fn) fiber</span><br></pre></td></tr></table></figure> + +<p>… however <code>mapResult</code> is more powerful - you could easily imagine using to apply failure recovery (a.k.a <code>try</code>/<code>catch</code> semantics) by simply mapping <code>Error exception</code> → <code>Ok recoveredValue</code>:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> catch fn fiber <span class="operator">=</span> mapResult (<span class="keyword">function</span> <span class="literal">Error</span> e <span class="operator">-></span> fn e <span class="operator">|</span> ok <span class="operator">-></span> ok) fiber</span><br></pre></td></tr></table></figure> + +<p>Another must-have function is binding operator (also know as <code>flatMap</code> in other languages like Scala, or <code>Promise.then</code> in JavaScript). It gives us the ability to compose fibers together - we’ll also use it when we come up to building a computation expression for our fibers.</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> bind (fn<span class="operator">:</span> <span class="symbol">'a</span> <span class="operator">-></span> Fiber<span class="operator"><</span><span class="symbol">'b</span><span class="operator">></span>) (Fiber call) <span class="operator">=</span> Fiber <span class="operator"><|</span> <span class="keyword">fun</span> (s, c) next <span class="operator">-></span></span><br><span class="line"> <span class="keyword">if</span> c.Cancelled <span class="keyword">then</span> next <span class="literal">None</span> </span><br><span class="line"> <span class="keyword">else</span> </span><br><span class="line"> <span class="keyword">try</span></span><br><span class="line"> call (s, c) (<span class="keyword">fun</span> result <span class="operator">-></span></span><br><span class="line"> <span class="keyword">if</span> c.Cancelled <span class="keyword">then</span> next <span class="literal">None</span></span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">match</span> result <span class="keyword">with</span></span><br><span class="line"> <span class="operator">|</span> <span class="literal">Some</span> (<span class="literal">Ok</span> r) <span class="operator">-></span></span><br><span class="line"> <span class="keyword">let</span> (Fiber call2) <span class="operator">=</span> fn r</span><br><span class="line"> call2 (s, c) next <span class="comment">// pass `next` callback over to next fiber</span></span><br><span class="line"> <span class="operator">|</span> <span class="literal">None</span> <span class="operator">-></span> next <span class="literal">None</span></span><br><span class="line"> <span class="operator">|</span> <span class="literal">Some</span> (<span class="literal">Error</span> e) <span class="operator">-></span> next (<span class="literal">Some</span>(<span class="literal">Error</span> e)))</span><br><span class="line"> <span class="keyword">with</span> e <span class="operator">-></span> next (<span class="literal">Some</span>(<span class="literal">Error</span> e))</span><br></pre></td></tr></table></figure> + +<p>It’s simple - we execute one fiber from within another, passing the <code>next</code> callback from outer function as an argument to inner one.</p> +<h3 id="Fiber-computation-expressions"><a href="#Fiber-computation-expressions" class="headerlink" title="Fiber computation expressions"></a>Fiber computation expressions</h3><p>With these few functions we’re already prepared to build a basic computation expression, that will enable us programming with fibers in pleasant way:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">[<Struct>]</span></span><br><span class="line"><span class="keyword">type</span> <span class="title class_">FiberBuilder</span> <span class="operator">=</span></span><br><span class="line"> <span class="keyword">member</span> <span class="keyword">inline</span> __.Zero <span class="operator">=</span> Fiber.success (Unchecked.defaultof<span class="operator"><</span>_<span class="operator">></span>)</span><br><span class="line"> <span class="keyword">member</span> <span class="keyword">inline</span> __.ReturnFrom fib <span class="operator">=</span> fib</span><br><span class="line"> <span class="keyword">member</span> <span class="keyword">inline</span> __.Return value <span class="operator">=</span> Fiber.success value</span><br><span class="line"> <span class="keyword">member</span> <span class="keyword">inline</span> __.Bind(fib, fn) <span class="operator">=</span> Fiber.bind fn fib</span><br><span class="line"></span><br><span class="line"><span class="meta">[<AutoOpen>]</span></span><br><span class="line"><span class="keyword">module</span> FiberBuilder <span class="operator">=</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">let</span> fib <span class="operator">=</span> FiberBuilder()</span><br></pre></td></tr></table></figure> + +<p>While in F# <a target="_blank" rel="noopener" href="https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/computation-expressions?ref=bartoszsypytkowski.com">there are many more operators</a> we could pack into our computation expression, these are basic ones that will let it work. With such construct, we’ll be able to write programs like:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> <span class="keyword">inline</span> millis n <span class="operator">=</span> TimeSpan.FromMilliseconds (float n)</span><br><span class="line"></span><br><span class="line"><span class="keyword">let</span> program<span class="operator">:</span> Fiber<span class="operator"><</span><span class="type">int</span><span class="operator">></span> <span class="operator">=</span> <span class="keyword">fib</span> {</span><br><span class="line"> <span class="keyword">let</span> a <span class="operator">=</span> <span class="keyword">fib</span> {</span><br><span class="line"> <span class="keyword">do!</span> Fiber.delay (millis <span class="number">1000</span>) <span class="comment">// create some artificial delay</span></span><br><span class="line"> <span class="keyword">return</span> <span class="number">3</span></span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">let!</span> b <span class="operator">=</span> a <span class="operator">|></span> Fiber.timeout (millis <span class="number">3000</span>) <span class="comment">// execute task within specified timeout</span></span><br><span class="line"> <span class="keyword">return</span> b }</span><br></pre></td></tr></table></figure> + +<p>Sure, we have neither delay nor timeout operators at the moment, but at least you know where are we heading now :)</p> +<h3 id="Delayed-execution"><a href="#Delayed-execution" class="headerlink" title="Delayed execution"></a>Delayed execution</h3><p>In order to implement delays, we could theoretically just call <code>Thread.Sleep</code> and get over it, but this approach is devastating from any coroutine library point of view. Most user-space thread libraries work by using a predefined fixed pool of OS-level threads and scheduling coroutines on them - you can read more about building thread pools <a target="_blank" rel="noopener" href="https://www.bartoszsypytkowski.com/thread-safety-with-affine-thread-pools/">here</a>.</p> +<p>However, <code>Thread.Sleep(timeout)</code> doesn’t know thread pooling mechanism - all it knows about is that we called suspending current OS thread of execution. This means, that this thread will not be awoken by kernel until timeout completes. What it means, is that none of our fibers will be able to use that thread. This is bad, because usually thread pools are made to fit in-line with number of machine CPU cores. In practice, <code>Thread.Sleep</code> may keep one of our CPU cores idle, wasting machine power in the process.</p> +<p>For this reason we usually want to build a suspendable fibers, that will respect our thread pool. This however cannot be done without cooperation with scheduler itself. Therefore, we need to extend API of our scheduler:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">type</span> <span class="title class_">IScheduler</span> <span class="operator">=</span></span><br><span class="line"> <span class="keyword">abstract</span> Schedule<span class="operator">:</span> (<span class="type">unit</span> <span class="operator">-></span> <span class="type">unit</span>) <span class="operator">-></span> <span class="type">unit</span></span><br><span class="line"> <span class="keyword">abstract</span> Delay<span class="operator">:</span> TimeSpan <span class="operator">*</span> (<span class="type">unit</span> <span class="operator">-></span> <span class="type">unit</span>) <span class="operator">-></span> <span class="type">unit</span></span><br></pre></td></tr></table></figure> + +<p>And our simple implementation of it as well:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> shared <span class="operator">=</span> </span><br><span class="line"> { <span class="keyword">new</span> IScheduler <span class="keyword">with</span></span><br><span class="line"> <span class="keyword">member</span> __.Schedule fn <span class="operator">=</span> <span class="operator">....</span></span><br><span class="line"> <span class="keyword">member</span> this.Delay (timeout<span class="operator">:</span> TimeSpan, fn) <span class="operator">=</span> </span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">mutable</span> t <span class="operator">=</span> Unchecked.defaultof<span class="operator"><</span>Timer<span class="operator">></span></span><br><span class="line"> <span class="keyword">let</span> callback <span class="operator">=</span> <span class="keyword">fun</span> _ <span class="operator">-></span> </span><br><span class="line"> t.Dispose()</span><br><span class="line"> fn()</span><br><span class="line"> ()</span><br><span class="line"> t <span class="operator"><-</span> <span class="keyword">new</span> Timer(callback, <span class="literal">null</span>, int timeout.TotalMilliseconds, Timeout.Infinite)</span><br><span class="line"> }</span><br></pre></td></tr></table></figure> + +<p>We’ll use a .NET timers here to implement our delays. With these in our hands, our<code>Fiber.delay</code> operation is trivial to implement:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> delay (timeout)<span class="operator">:</span> Fiber<span class="operator"><</span><span class="type">unit</span><span class="operator">></span> <span class="operator">=</span></span><br><span class="line"> Fiber <span class="operator"><|</span> <span class="keyword">fun</span> (s, c) next <span class="operator">-></span></span><br><span class="line"> <span class="keyword">if</span> c.Cancelled <span class="keyword">then</span> next <span class="literal">None</span></span><br><span class="line"> <span class="keyword">else</span> s.Delay(timeout, <span class="keyword">fun</span> () <span class="operator">-></span> </span><br><span class="line"> <span class="keyword">if</span> c.Cancelled </span><br><span class="line"> <span class="keyword">then</span> next <span class="literal">None</span> </span><br><span class="line"> <span class="keyword">else</span> next (<span class="literal">Some</span> (<span class="literal">Ok</span> ())))</span><br></pre></td></tr></table></figure> + +<h3 id="Composing-parallel-fibers"><a href="#Composing-parallel-fibers" class="headerlink" title="Composing parallel fibers"></a>Composing parallel fibers</h3><p>We’re slowly getting to the end. What I left for this blog post was to implement two basic operators, that are prevalent in most coroutine libraries:</p> +<ul> +<li><code>Fiber.parallel</code> which will schedule multiple fibers to run in parallel and returns a fiber which aggregates their results.</li> +<li>Running two fibers in parallel and returning the result of whichever completes first, while cancelling a second one. We already discussed this approach before. Here I’ll call it <code>Fiber.race</code>.</li> +</ul> +<h4 id="Aggregating-parallel-results"><a href="#Aggregating-parallel-results" class="headerlink" title="Aggregating parallel results"></a>Aggregating parallel results</h4><p>We’ll start from building a parallel operator, which will change our array of fibers into fiber with an array of results. But let’s define the semantics of that operation first:</p> +<ul> +<li>Our result fiber completes only when all of the aggregated fibers completed with successful result.</li> +<li>If any of the fibers fails, the resulting fiber also fails.</li> +<li>If any of the fibers fails or get cancelled, all pending ones are also cancelled.</li> +</ul> +<p>The core skeleton of that operation could look like following:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> parallel (fibers<span class="operator">:</span> Fiber<span class="operator"><</span><span class="symbol">'a</span><span class="operator">></span>[])<span class="operator">:</span> Fiber<span class="operator"><</span><span class="symbol">'a</span>[]<span class="operator">></span> <span class="operator">=</span></span><br><span class="line"> Fiber <span class="operator"><|</span> <span class="keyword">fun</span> (s, c) next <span class="operator">-></span></span><br><span class="line"> <span class="keyword">if</span> c.Cancelled <span class="keyword">then</span> next <span class="literal">None</span></span><br><span class="line"> <span class="keyword">else</span> </span><br><span class="line"> <span class="keyword">let</span> child <span class="operator">=</span> c.AddChild()</span><br><span class="line"> <span class="keyword">let</span> successes <span class="operator">=</span> Array.zeroCreate remaining</span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">mutable</span> remaining <span class="operator">=</span> Array.length fibs</span><br><span class="line"> fibers <span class="operator">|></span> Array.iteri (<span class="keyword">fun</span> idx (Fiber call) <span class="operator">-></span></span><br><span class="line"> s.Schedule (<span class="keyword">fun</span> () <span class="operator">-></span> <span class="comment">(* to be defined *)</span>)</span><br><span class="line"> )</span><br></pre></td></tr></table></figure> + +<p>Here, we create a dedicated cancellation token, an array of results and a countdown counter - we’re going to decrement it every time one of our fibers completes to know when we’re ready to return a complete result. I’ve left a placeholder for a lambda body that we actually want to schedule. We’re going to fill it right away:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// defined above: s.Schedule <| fun () -></span></span><br><span class="line">call (s, child) (<span class="keyword">fun</span> result <span class="operator">-></span> </span><br><span class="line"><span class="keyword">match</span> result <span class="keyword">with</span></span><br><span class="line"><span class="operator">|</span> <span class="literal">Some</span> (<span class="literal">Ok</span> success) <span class="operator">-></span></span><br><span class="line"> <span class="comment">// fill the result array</span></span><br><span class="line"> successes.[idx] <span class="operator"><-</span> success</span><br><span class="line"> <span class="keyword">if</span> c.Cancelled <span class="operator">&&</span> Interlocked.Exchange(<span class="operator">&</span>remaining, <span class="number">-1</span>) <span class="operator">></span> <span class="number">0</span> <span class="keyword">then</span></span><br><span class="line"> next <span class="literal">None</span></span><br><span class="line"> <span class="keyword">elif</span> Interlocked.Decrement(<span class="operator">&</span>remaining) <span class="operator">=</span> <span class="number">0</span> <span class="keyword">then</span></span><br><span class="line"> <span class="comment">// if all results have been returned, call the `next` callback</span></span><br><span class="line"> <span class="keyword">if</span> c.Cancelled <span class="keyword">then</span> next <span class="literal">None</span></span><br><span class="line"> <span class="keyword">else</span> next (<span class="literal">Some</span> (<span class="literal">Ok</span> successes))</span><br><span class="line"><span class="operator">|</span> <span class="literal">Some</span> (<span class="literal">Error</span> fail) <span class="operator">-></span></span><br><span class="line"> <span class="keyword">if</span> Interlocked.Exchange(<span class="operator">&</span>remaining, <span class="number">-1</span>) <span class="operator">></span> <span class="number">0</span> <span class="keyword">then</span> </span><br><span class="line"> child.Cancel() <span class="comment">// we failed, cancel other fibers</span></span><br><span class="line"> <span class="keyword">if</span> c.Cancelled <span class="keyword">then</span> next <span class="literal">None</span></span><br><span class="line"> <span class="keyword">else</span> next (<span class="literal">Some</span> (<span class="literal">Error</span> fail))</span><br><span class="line"><span class="operator">|</span> <span class="literal">None</span> <span class="operator">-></span></span><br><span class="line"> <span class="keyword">if</span> Interlocked.Exchange(<span class="operator">&</span>remaining, <span class="number">-1</span>) <span class="operator">></span> <span class="number">0</span> <span class="keyword">then</span> next <span class="literal">None</span>)</span><br></pre></td></tr></table></figure> + +<p>As you probably noticed, we’re using <code>Interlocked</code> class again - that’s because now we have multiple fibers running in parallel, therefore our access to shared mutable values is not thread safe. This includes <code>remaining</code> counter decrement operation. This however doesn’t apply to <code>successes.[i] <- success</code> - since every fiber knows and touches only its own index within result array, there’s no worry that any other will try to push its result in the same place.</p> +<p>What you also can see, we’re using a <code>-1</code> here as a magic value - we’ll use it on the counter as a flag to determine if any of the fibers failed/was cancelled - and if so, which one of them will call the <code>next</code> callback.</p> +<h4 id="Racing-to-completion"><a href="#Racing-to-completion" class="headerlink" title="Racing to completion"></a>Racing to completion</h4><p>With first operator (<code>Fiber.parallel</code>) ready, now it’s the time to implement <code>Fiber.race</code>. Since I’ve discussed it behavior multiple times in this post already, let’s dive straight into the code:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> race (Fiber left) (Fiber right)<span class="operator">:</span> Fiber<span class="operator"><</span>Choice<span class="operator"><</span><span class="symbol">'a</span>, <span class="symbol">'b</span><span class="operator">>></span> <span class="operator">=</span></span><br><span class="line"> Fiber <span class="operator"><|</span> <span class="keyword">fun</span> (s, c) next <span class="operator">-></span></span><br><span class="line"> <span class="keyword">if</span> c.Cancelled <span class="keyword">then</span> next <span class="literal">None</span></span><br><span class="line"> <span class="keyword">else</span> </span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">mutable</span> flag <span class="operator">=</span> <span class="number">0</span></span><br><span class="line"> <span class="keyword">let</span> cancelChild <span class="operator">=</span> c.AddChild()</span><br><span class="line"> <span class="keyword">let</span> run fiber choice <span class="operator">=</span></span><br><span class="line"> <span class="comment">(* to be described *)</span></span><br><span class="line"> run left Choice1Of2</span><br><span class="line"> run right Choice2Of2</span><br></pre></td></tr></table></figure> + +<p>So again, we want to have shared mutable flag, which we’ll use to determine, which of the fibers finished as a first one to be able to call fiber’s callback safely and cancel the other. You may see, that our returned fiber uses <code>Choice<,></code> type - this means, that our left and right fibers can have results of different types. We’ll use that soon, but first we need to complete our <code>run</code> function body:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> run fiber choice <span class="operator">=</span></span><br><span class="line"> s.Schedule (<span class="keyword">fun</span> () <span class="operator">-></span></span><br><span class="line"> fiber (s, cancelChild) (<span class="keyword">fun</span> result <span class="operator">-></span></span><br><span class="line"> <span class="keyword">if</span> Interlocked.Exchange(<span class="operator">&</span>flag, <span class="number">1</span>) <span class="operator">=</span> <span class="number">0</span> <span class="keyword">then</span></span><br><span class="line"> cancelChild.Cancel()</span><br><span class="line"> <span class="keyword">if</span> c.Cancelled <span class="keyword">then</span> next <span class="literal">None</span></span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">match</span> result <span class="keyword">with</span></span><br><span class="line"> <span class="operator">|</span> <span class="literal">None</span> <span class="operator">-></span> next <span class="literal">None</span></span><br><span class="line"> <span class="operator">|</span> <span class="literal">Some</span>(<span class="literal">Ok</span> v) <span class="operator">-></span> next (<span class="literal">Some</span>(<span class="literal">Ok</span>(choice v)))</span><br><span class="line"> <span class="operator">|</span> <span class="literal">Some</span>(<span class="literal">Error</span> e) <span class="operator">-></span> next (<span class="literal">Some</span>(<span class="literal">Error</span> e))))</span><br></pre></td></tr></table></figure> + +<p>What we do here is simply trying to race to “reserve” out flag variable - the winner gets his result mapped to corresponding choice, while looser gets cancelled.</p> +<p>What’s interesting, we can now combine our <code>race</code> and <code>delay</code> functions to easily implement timeout mechanism:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> timeout (t<span class="operator">:</span> TimeSpan) fiber <span class="operator">=</span></span><br><span class="line"> Fiber <span class="operator"><|</span> <span class="keyword">fun</span> (s, c) next <span class="operator">-></span></span><br><span class="line"> <span class="keyword">let</span> (Fiber call) <span class="operator">=</span> race (delay t) fiber</span><br><span class="line"> call (s, c) (<span class="keyword">fun</span> result <span class="operator">-></span></span><br><span class="line"> <span class="keyword">if</span> c.Cancelled <span class="keyword">then</span> next <span class="literal">None</span></span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">match</span> result <span class="keyword">with</span></span><br><span class="line"> <span class="operator">|</span> <span class="literal">None</span> <span class="operator">-></span> next <span class="literal">None</span></span><br><span class="line"> <span class="operator">|</span> <span class="literal">Some</span>(<span class="literal">Ok</span> (Choice1Of2 _)) <span class="operator">-></span> next <span class="literal">None</span> <span class="comment">// timeout won</span></span><br><span class="line"> <span class="operator">|</span> <span class="literal">Some</span>(<span class="literal">Ok</span> (Choice2Of2 v)) <span class="operator">-></span> next (<span class="literal">Some</span>(<span class="literal">Ok</span> v))</span><br><span class="line"> <span class="operator">|</span> <span class="literal">Some</span>(<span class="literal">Error</span> e) <span class="operator">-></span> next (<span class="literal">Some</span>(<span class="literal">Error</span> e))</span><br><span class="line"> )</span><br></pre></td></tr></table></figure> + +<p>The one last thing left for us, is to be able to run out fibers on the main thread - otherwise we’d start our program, schedule fibers to run in the background and then close the program without waiting for the results.</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> blocking (s<span class="operator">:</span> IScheduler) (cancel<span class="operator">:</span> Cancel) (Fiber fn) <span class="operator">=</span></span><br><span class="line"> <span class="keyword">use</span> waiter <span class="operator">=</span> <span class="keyword">new</span> ManualResetEventSlim(<span class="literal">false</span>)</span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">mutable</span> res <span class="operator">=</span> <span class="literal">None</span></span><br><span class="line"> s.Schedule(<span class="keyword">fun</span> () <span class="operator">-></span> fn (s, cancel) (<span class="keyword">fun</span> result <span class="operator">-></span></span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">not</span> cancel.Cancelled <span class="keyword">then</span></span><br><span class="line"> Interlocked.Exchange(<span class="operator">&</span>res, <span class="literal">Some</span> result) <span class="operator">|></span> <span class="built_in">ignore</span></span><br><span class="line"> waiter.Set()))</span><br><span class="line"> waiter.Wait()</span><br><span class="line"> res.Value</span><br></pre></td></tr></table></figure> + +<p>It’s simple - we’ll use standard synchronization primitives provided by .NET runtime, to hold current OS thread until we complete. Sure it’s blocking an OS thread, but we’ll eventually need that if we don’t want our program’s main function to finish before all fibers inside the thread pool complete.</p> +<h3 id="Simulating-real-environment-in-tests"><a href="#Simulating-real-environment-in-tests" class="headerlink" title="Simulating real environment in tests"></a>Simulating real environment in tests</h3><p>In theory, we could be done here. But, if you managed to read up to this point, we may want to cover one last scenario. Imagine that we’d want to test our fibers. However running tests using standard thread pool scheduler can lead to funky issues:</p> +<ul> +<li>Sometimes you may trigger some race conditions in your code, that only happen in specific situations (like high CPU contention) and are almost impossible to reproduce during debug sessions.</li> +<li>Other times you may have some lengthy delays/timeouts in your code, like waiting for seconds or even minutes before continuing. Guess what: now your test will wait for just as long.</li> +</ul> +<p>These are not new problems. They are well known in world of concurrent and distributed systems. What we need, is a simulation of execution environment. If you want to listen more about that concept, I could recommend you <a target="_blank" rel="noopener" href="https://www.youtube.com/watch?v=4fFDFbi3toc&ref=bartoszsypytkowski.com">this presentaton</a>. To run our test predictably, we’ll create a dedicated test scheduler, which will run our code in deterministic fashion (on a single core) and in a way that’s detached from other invariants eg. actual physical clock and random number generator.</p> +<p>The idea here is simple - our scheduler will operate on notion of virtual timeline. When we’ll try to schedule a new function - to trigger either immediately or after some timeout - we’ll store it inside an ordered collection, a timeline. Some of the technical decisions we also made for purposes of this implementation:</p> +<ul> +<li>Whenever a fiber is going to schedule multiple parallel executions “at the same time”, we’ll put them all into a single bucket on a timeline. Later on I’ll cover, why this is useful.</li> +<li>We’ll assume, that single operation execution is instantaneous. It means, it doesn’t advance our scheduler’s clock. We do it only for delayed executions.</li> +</ul> +<p>After describing the concept behind the algorithm, the actual implementation really shouldn’t be that surprising:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">type</span> <span class="title class_">TestScheduler</span>(now<span class="operator">:</span> DateTime) <span class="operator">=</span></span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">mutable</span> running <span class="operator">=</span> <span class="literal">false</span></span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">mutable</span> currentTime <span class="operator">=</span> now.Ticks</span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">mutable</span> timeline <span class="operator">=</span> Map.empty</span><br><span class="line"> <span class="keyword">let</span> schedule delay fn <span class="operator">=</span> <span class="comment">(* to be defined *)</span></span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">rec</span> run () <span class="operator">=</span> <span class="comment">(* to be defined *)</span></span><br><span class="line"> <span class="keyword">interface</span> IScheduler <span class="keyword">with</span></span><br><span class="line"> <span class="keyword">member</span> this.Schedule fn <span class="operator">=</span> </span><br><span class="line"> schedule <span class="number">0</span>L fn</span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">not</span> running <span class="keyword">then</span></span><br><span class="line"> running <span class="operator"><-</span> <span class="literal">true</span></span><br><span class="line"> run ()</span><br><span class="line"> <span class="keyword">member</span> this.Delay (timeout<span class="operator">:</span> TimeSpan, fn) <span class="operator">=</span> schedule timeout.Ticks fn</span><br></pre></td></tr></table></figure> + +<p>We’re using a <code>running</code> flag here to not try to invoke <code>run</code> multiple times in nested manner - this would cause non-tailable recursion and potential stack overflow in more expensive tests.</p> +<p>The schedule function is pretty simple - calculate expected execution time for a function, then add that function to be executed at that point in time.</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> schedule delay fn <span class="operator">=</span> </span><br><span class="line"> <span class="keyword">let</span> at <span class="operator">=</span> currentTime <span class="operator">+</span> delay</span><br><span class="line"> timeline <span class="operator"><-</span></span><br><span class="line"> <span class="keyword">match</span> Map.tryFind at timeline <span class="keyword">with</span></span><br><span class="line"> <span class="operator">|</span> <span class="literal">None</span> <span class="operator">-></span> Map.add at [fn] timeline </span><br><span class="line"> <span class="operator">|</span> <span class="literal">Some</span> fns <span class="operator">-></span> Map.add at (fn<span class="operator">::</span>fns) timeline</span><br></pre></td></tr></table></figure> + +<p>Given all of the code we already survived in this blog post, run loop should be pretty simple:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> <span class="keyword">rec</span> run () <span class="operator">=</span></span><br><span class="line"> <span class="keyword">match</span> Seq.tryHead timeline <span class="keyword">with</span></span><br><span class="line"> <span class="operator">|</span> <span class="literal">None</span> <span class="operator">-></span> running <span class="operator"><-</span> <span class="literal">false</span></span><br><span class="line"> <span class="operator">|</span> <span class="literal">Some</span> (KeyValue(time, bucket)) <span class="operator">-></span></span><br><span class="line"> timeline <span class="operator"><-</span> Map.remove time timeline</span><br><span class="line"> currentTime <span class="operator"><-</span> time</span><br><span class="line"> <span class="keyword">for</span> fn <span class="keyword">in</span> List.rev bucket <span class="keyword">do</span> </span><br><span class="line"> fn () </span><br><span class="line"> run ()</span><br></pre></td></tr></table></figure> + +<p>We’ll try to pick the first entry from the timeline - since here we use F# map, which is sorted in ascending order, we know that first entry is the one with the shortest execution timeout. We update our “current” time to match the expected one we calculated earlier, and finally we execute all functions scheduled at that time and repeat the loop all over until we eventually run out of scheduled actions.</p> +<p>Now here’s the trick - we use <code>List.rev</code> to execute functions in the same order in which they were scheduled, because we want our tests to be deterministic and our bugs to be reproducible. However this is not the only strategy - <strong>since we know that functions in the same bucket could as well be executing in parallel, we could shuffle them around in different permutations for early discovery of some data races!</strong> I’ll won’t dive into it, but leave that idea as food for thoughts for you.</p> +<p>One last note about the test scheduler is that isolating it from the actual physical clock means, we cannot trust our time functions (like <code>DateTime.UtcNow</code>) any longer. This shouldn’t really be an issue though - because relying on physical time would potentially make our tests indeterministic, we didn’t want to use it anyway, right?</p> +<p>However, we need to be able to obtain current time from the scheduler, so we need to extend its API:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">type</span> <span class="title class_">IScheduler</span> <span class="operator">=</span></span><br><span class="line"> <span class="keyword">abstract</span> UtcNow<span class="operator">:</span> <span class="type">unit</span> <span class="operator">-></span> <span class="type">unit</span></span><br><span class="line"> <span class="comment">// ... other methods</span></span><br><span class="line"> </span><br><span class="line"><span class="keyword">type</span> <span class="title class_">TestScheduler</span>() <span class="operator">=</span></span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">mutable</span> currentTime <span class="operator">=</span> DateTime.UtcNow.Ticks</span><br><span class="line"> <span class="comment">// ... rest of the implementation</span></span><br><span class="line"> <span class="keyword">interface</span> IScheduler <span class="keyword">with</span></span><br><span class="line"> <span class="keyword">member</span> __.UtcNow() <span class="operator">=</span> DateTime(currentTime)</span><br><span class="line"> <span class="comment">// ... other methods</span></span><br></pre></td></tr></table></figure> + +<p>And that’s all. As always, if you got confused or have a problems along the way, you can get the entire code <a target="_blank" rel="noopener" href="https://gist.github.com/Horusiath/9c790691130150b524aaa9ab426ed982?ref=bartoszsypytkowski.com">here</a>. I wanted to thank to Anthony Lloyd for his initial work on porting Scala <a target="_blank" rel="noopener" href="https://zio.dev/?ref=bartoszsypytkowski.com">ZIO</a> library to F#, which brought me an inspiration to write this piece.</p> + +</div> + +<script> + window.onload = detectors(); +</script> + <div class="post-footer"> + <div class="h-line-primary"></div> + <nav class="post-nav"> + <div class="prev-item"> + + <div class="icon arrow-left"></div> + <div class="post-link"> + <a href="/2024/10/18/10-Tips-for-Productive-FSharp-Scripting/">Prev</a> + </div> + + </div> + <div class="next-item"> + + <div class="icon arrow-right"></div> + <div class="post-link"> + <a href="/2024/10/18/Dealing-with-complex-dependency-injection-in-FSharp/">Next</a> + </div> + + </div> + </nav> +</div> + + + <div class="post-comment"> + + + + + + + +</div> + + +</article> + </div> + </div> + + <div class="footer"> + <div class="flex-container"> + <div class="footer-text"> + + + | + + + 希望路过的人可以添点柴火让这里暖和点 + + </div> + </div> +</div> + + </div> + + + <div class="search-popup"> + <div class="search-popup-overlay"> + </div> + <div class="search-popup-window" > + <div class="search-header"> + <div class="search-input-container"> + <input autocomplete="off" autocapitalize="off" maxlength="80" + placeholder="Search Anything" spellcheck="false" + type="search" class="search-input"> + </div> + <div class="search-close-btn"> + <div class="icon close-btn"></div> + </div> + </div> + <div class="search-result-container"> + </div> + </div> +</div> + +<script> + const searchConfig = { + path : "/search.xml", + top_n_per_article: "1", + unescape : "false", + trigger: "auto", + preload: "false" + } +</script> +<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/search.js"></script> +<script src="/js/search.js"></script> + + + + </body> +</html> diff --git a/2024/10/18/Dealing-with-complex-dependency-injection-in-FSharp/index.html b/2024/10/18/Dealing-with-complex-dependency-injection-in-FSharp/index.html new file mode 100644 index 00000000..8195ce32 --- /dev/null +++ b/2024/10/18/Dealing-with-complex-dependency-injection-in-FSharp/index.html @@ -0,0 +1,370 @@ +<!DOCTYPE html> +<html lang="en"> + <head> + <meta charset="UTF-8"> +<meta name="viewport" + content="width=device-width, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0"> +<meta http-equiv="X-UA-Compatible" content="ie=edge"> + + <meta name="author" content="韩暮秋"> + + + <meta name="subtitle" content="暮秋小屋"> + + + <meta name="description" content="这里是暮秋小屋,思念和灵感的寄存处"> + + + <meta name="keywords" content="韩暮秋,MuqiuHan,'Muqiu Han', 'muqiu han', muqiuhan"> + + + + +<title>Dealing with complex dependency injection in FSharp | 暮秋小屋</title> + + + + <link rel="icon" href="/favicon.ico"> + + + +<style> + @import url('https://fonts.googleapis.com/css2?family=Inter:wght@300;400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&family=Roboto+Mono&display=swap'); +</style> + + + + <!-- stylesheets list from _config.yml --> + + <link rel="stylesheet" href="/css/style.css"> + + + + + + <!-- scripts list from _config.yml --> + + <script src="/js/frame.js"></script> + + + + + + <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script> + <script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script> + + + + + + + + <meta name="generator" content="Hexo 6.3.0"></head> + <body> + <div class="mask-border"> + </div> + + <div class="wrapper"> + + <div class="header"> + <div class="flex-container"> + <div class="header-inner"> + <div class="site-brand-container"> + <a href="/"> + + 暮秋小屋 + + </a> + </div> + <div id="menu-btn" class="menu-btn" onclick="toggleMenu()"> + Menu + </div> + <nav class="site-nav"> + <ul class="menu-list"> + + + <li class="menu-item"> + <a href="/">主页</a> + </li> + + + + <li class="menu-item"> + <a href="/categories/gallery/">日记本</a> + </li> + + + + <li class="menu-item"> + <a href="/tags/Medicine/">医学</a> + </li> + + + + <li class="menu-item"> + <a href="/tags/Technique/">计算机科学</a> + </li> + + + + <li class="menu-item"> + <a href="/tags/Life/">生活</a> + </li> + + + + <li class="menu-item"> + <a href="/about">关于</a> + </li> + + + + <li class="menu-item search-btn"> + <a href="#">Search</a> + </li> + + </ul> + </nav> + </div> + </div> +</div> + + + <div class="main"> + <div class="flex-container"> + <article id="post"> + + + <div class="post-head"> + <div class="post-info"> + <div class="tag-list"> + + + <span class="post-tag"> + <a href="/tags/Technique/"> + Technique + </a> + </span> + + <span class="post-tag"> + <a href="/tags/F/"> + F# + </a> + </span> + + <span class="post-tag"> + <a href="/tags/Archive/"> + Archive + </a> + </span> + + + </div> + <div class="post-title"> + + + Dealing with complex dependency injection in FSharp + + + </div> + <span class="post-date"> + Oct 18, 2024 + </span> + </div> + <div class="post-img"> + + <div class="h-line-primary"></div> + + </div> +</div> + <div class="post-content"> + <p>Today, we’re going to cover different ways of encapsulating capabilities and supplying them between functions using functional programming techniques which can be realized in F#.</p> +<p>Managing code dependencies in object oriented languages in 2020 is pretty much one sided problem: dependency injection has won, people use dedicated frameworks to handle that for them, which 99.9% of the time operate using runtime reflection. Of course now you need to learn them as well, potentially misconfigure them and fail at runtime or maybe even discover that not every problem is a stateless web service, but it still better (?) than what we had in the past, and what more can we possibly do anyway?</p> +<p>On the other side in functional space, there’s no one opinionated solution or approach - various things have been proposed, usually depending on features that languages and compiler have to offer. And since pretty much all functional languages offer this thing known as partial application, for many years it was the most common answer for the problem of managing dependencies.</p> +<p>In short we’re talking about dependency injection by function parameter, like:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// foo requires 2 dependencies to serve the incoming request</span></span><br><span class="line"><span class="keyword">let</span> foo bar baz request <span class="operator">=</span> <span class="operator">???</span></span><br><span class="line"><span class="comment">// we're providing dependencies by partial application</span></span><br><span class="line"><span class="keyword">let</span> wired <span class="operator">=</span> foo dependency1 dependency2</span><br><span class="line"><span class="comment">// now wired can serve request directly without calling </span></span><br><span class="line"><span class="comment">// dependencies every time</span></span><br><span class="line"><span class="keyword">let</span> response <span class="operator">=</span> wired request</span><br></pre></td></tr></table></figure> + +<p>It’s very simple, doesn’t require reflection or dedicated library. However there are several pain points coming with this approach - visible especially as our code base grows and become more complex. However latest approaches popularized by libraries like Scala <a target="_blank" rel="noopener" href="https://zio.dev/?ref=bartoszsypytkowski.com">ZIO</a> or Haskell’s <a target="_blank" rel="noopener" href="https://youtu.be/idU7GdlfP9Q?t=1394&ref=bartoszsypytkowski.com">Polysemy</a> challenge this approach.</p> +<h2 id="Partial-application"><a href="#Partial-application" class="headerlink" title="Partial application"></a>Partial application</h2><p>There are some design decisions, when partial application doesn’t always give a clear answer. Example:</p> +<blockquote> +<p>Imagine using a set of methods, that are closely related and - in object oriented world - encapsulated within a single object, like database query/execute or different logging methods (debug/info/warning/error).</p> +</blockquote> +<p>Now, given that our function needs to use potentially more than one of these, how should we pass our arguments?:</p> +<ol> +<li>Functional purist path - pass every dependency as a separate function parameter: <code>let doSmth logError logInfo = ??</code>. While it allows us to precisely describe what this function uses, it would of course lead to explosion of function parameters. Additionally every time you need new function in your existing code, you need to partially apply it at all call sites.</li> +<li>Describe operations using ADT (algebraic data types) and inject a function that will work as an interpreter for them: <code>let doSmth (log: LogEvent -> unit) = ??</code>. While it’s easy to mock (you don’t need to implement everything, only pattern match on cases that matter for a particular test) and reduces params affinity, it also comes with a lot of indirection, that may lead to harder to grasp, especially during debugging. Sometimes a performance penalty is also to be expected.</li> +<li>Fallback to objects/interfaces and pass them as methods: <code>let doSmth (logger: ILogger) = ??</code>. While interfaces may simplify dependency tree, it’s not always obvious when to use it. Mocking story is also more painful + interfaces are not inferred by F# compiler.</li> +</ol> +<p>These are quite common options I’ve seen in the wild - each having their own advantages and disadvantages. Which one to use? Good question, as in practice with codebases that are old enough, you usually see 2 or even all 3 of them mixed together. This can lead to some confusion and obscurity over time.</p> +<p>What’s worse, none of these cases really solves problem of dependency management - all they do is just try to reduce it to a manageable scope. Eventually you’ll end up manually wiring - by partial application - dozens of functions and managing all of the dependencies between them by hand.</p> +<h3 id="Example"><a href="#Example" class="headerlink" title="Example"></a>Example</h3><p>In order to get better understanding, we’ll use a fairly simple example - changing user password:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> fetchUser (db<span class="operator">:</span> IDbConnection) userId <span class="operator">=</span> </span><br><span class="line"> db.QueryFirstAsync(Sql.FetchUser, {<span class="operator">|</span> userId <span class="operator">=</span> userid<span class="operator">|</span> })</span><br><span class="line"> </span><br><span class="line"><span class="keyword">let</span> updateUser (db<span class="operator">:</span> IDbConnection) user <span class="operator">=</span> db.ExecuteAsync(Sql.UpdateUser, user)</span><br><span class="line"></span><br><span class="line"><span class="keyword">let</span> changePass (logger<span class="operator">:</span> ILogger) fetch update <span class="operator">=</span> <span class="keyword">fun</span> req <span class="operator">-></span> <span class="keyword">task</span> {</span><br><span class="line"> <span class="keyword">let!</span> user <span class="operator">=</span> fetch req.UserId</span><br><span class="line"> <span class="keyword">if</span> user.Hash <span class="operator">=</span> bcrypt user.Salt req.OldPass <span class="keyword">then</span></span><br><span class="line"> <span class="keyword">let</span> salt <span class="operator">=</span> generateSalt ()</span><br><span class="line"> <span class="keyword">let</span> user' <span class="operator">=</span> { user <span class="keyword">with</span> Salt <span class="operator">=</span> salt; Hash <span class="operator">=</span> bcrypt salt req.NewPass }</span><br><span class="line"> <span class="keyword">do!</span> update user'</span><br><span class="line"> logger.LogInformation <span class="string">"Password change: user %i"</span> user.Id</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">Ok</span> ()</span><br><span class="line"> <span class="keyword">else</span> </span><br><span class="line"> logger.LogError <span class="string">"Password change unauthorized: user %i"</span> user.Id</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">Error</span> <span class="string">"Old password is invalid"</span></span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure> + +<p>Here we have a fairly short snippet with some dependencies? But how many in practice?:</p> +<ul> +<li>Number of parameters suggest 3, but depending on our choices it could be 4 (if we decide to pass log error and info separately) or 2 (if we conflate fetch/update into dedicated interface).</li> +<li>It’s not hard to imagine that in the future our <code>bcrypt</code> hashing function may turn out to be configurable - maybe even per each user. That may need a configurable parameter.</li> +<li>Maybe aside of the logger we may be needing a separate telemetry mechanism to count number of incoming request or password validation failures? That means another parameter.</li> +<li>Salt generation is pseudo-random process - it we want our function to be deterministic, we should probably parametrize it over explicitly passed <code>Random</code> as well.</li> +</ul> +<p>As you see, what seemed to be simple task at the beginning can quickly blow up out of proportion. As the number of arguments grows, the more nasty our wiring code eventually becomes. Quite common pattern is to hide all of that nastiness under the carpet a.k.a. <strong>composition root</strong>. However this doesn’t have to be the case.</p> +<p>Below we’ll cover another approach for dealing with dependencies - inspired by Scala <a target="_blank" rel="noopener" href="https://medium.com/@pascal.mengelt/what-are-the-benefits-of-the-zio-modules-with-zlayers-3bf6cc064a9b?ref=bartoszsypytkowski.com">ZIO</a> library - using incremental steps, from first principles to monadic bindings.</p> +<h2 id="Managing-dependencies-beyond-partial-application"><a href="#Managing-dependencies-beyond-partial-application" class="headerlink" title="Managing dependencies beyond partial application"></a>Managing dependencies beyond partial application</h2><p>Let’s start from how our code from above will eventually look like at the end of this step:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> changePass env <span class="operator">=</span> <span class="keyword">fun</span> req <span class="operator">-></span> <span class="keyword">task</span> {</span><br><span class="line"> <span class="keyword">let!</span> user <span class="operator">=</span> Db.fetchUser env req.UserId</span><br><span class="line"> <span class="keyword">if</span> user.Hash <span class="operator">=</span> bcrypt user.Salt req.OldPass <span class="keyword">then</span></span><br><span class="line"> <span class="keyword">let</span> salt <span class="operator">=</span> Random.bytes env <span class="number">32</span></span><br><span class="line"> <span class="keyword">do!</span> Db.updateUser <span class="keyword">env</span> { user <span class="keyword">with</span> Salt <span class="operator">=</span> salt; Hash <span class="operator">=</span> bcrypt salt req.NewPass }</span><br><span class="line"> Log.info env <span class="string">"Changed password for user %i"</span> user.Id</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">Ok</span> ()</span><br><span class="line"> <span class="keyword">else</span> </span><br><span class="line"> Log.error env <span class="string">"Password change unauthorized: user %i"</span> user.Id</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">Error</span> <span class="string">"Old password is invalid"</span></span><br><span class="line">}</span><br></pre></td></tr></table></figure> + +<p>As you may notice, all of our partially applied parameters disappeared, replaced by some single cryptic <code>env</code> parameter. We’ll get there soon. We also packed similar capabilities into corresponding modules (<code>Db</code>/<code>Log</code>/<code>Random</code>). Lets start from defining them:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">[<Interface>]</span></span><br><span class="line"><span class="keyword">type</span> <span class="title class_">ILogger</span> <span class="operator">=</span></span><br><span class="line"> <span class="keyword">abstract</span> Debug<span class="operator">:</span> <span class="type">string</span> <span class="operator">-></span> <span class="type">unit</span></span><br><span class="line"> <span class="keyword">abstract</span> <span class="literal">Error</span><span class="operator">:</span> <span class="type">string</span> <span class="operator">-></span> <span class="type">unit</span> </span><br><span class="line"></span><br><span class="line"><span class="meta">[<Interface>]</span> <span class="keyword">type</span> <span class="title class_">ILog</span> <span class="operator">=</span> <span class="keyword">abstract</span> Logger<span class="operator">:</span> ILogger</span><br><span class="line"></span><br><span class="line"><span class="keyword">module</span> Log <span class="operator">=</span></span><br><span class="line"> <span class="keyword">let</span> debug (env<span class="operator">:</span> #ILog) fmt <span class="operator">=</span> Printf.kprintf env.Logger.Debug fmt</span><br><span class="line"> <span class="keyword">let</span> error (env<span class="operator">:</span> #ILog) fmt <span class="operator">=</span> Printf.kprintf env.Logger.<span class="literal">Error</span> fmt</span><br></pre></td></tr></table></figure> + +<p>Now we can say something more about <code>env</code>. The secret is in <code>#ILog</code> signature, which means that our environment can be any generic type implementing <code>ILog</code> interface. As soon you’ll see, this approach is highly composable, but before that we’ll need another module:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">[<Interface>]</span></span><br><span class="line"><span class="keyword">type</span> <span class="title class_">IDatabase</span> <span class="operator">=</span></span><br><span class="line"> <span class="keyword">abstract</span> Query<span class="operator">:</span> <span class="type">string</span> <span class="operator">*</span> <span class="symbol">'i</span> <span class="operator">-></span> Task<span class="operator"><</span><span class="symbol">'o</span><span class="operator">></span></span><br><span class="line"> <span class="keyword">abstract</span> Execute<span class="operator">:</span> <span class="type">string</span> <span class="operator">*</span> <span class="symbol">'i</span> <span class="operator">-></span> Task</span><br><span class="line"> </span><br><span class="line"><span class="meta">[<Interface>]</span> <span class="keyword">type</span> <span class="title class_">IDb</span> <span class="operator">=</span> <span class="keyword">abstract</span> Database<span class="operator">:</span> IDatabase</span><br><span class="line"></span><br><span class="line"><span class="keyword">module</span> Db <span class="operator">=</span> </span><br><span class="line"> <span class="keyword">let</span> fetchUser (env<span class="operator">:</span> #IDb) userId <span class="operator">=</span> </span><br><span class="line"> env.Database.Query(Sql.FetchUser, {<span class="operator">|</span> userId <span class="operator">=</span> userId <span class="operator">|</span>})</span><br><span class="line"> <span class="keyword">let</span> updateUser (env<span class="operator">:</span> #IDb) user <span class="operator">=</span> env.Database.Execute(Sql.UpdateUser, user)</span><br></pre></td></tr></table></figure> + +<p>Now what will happen if we use functions from both <code>Log</code> and <code>Db</code> modules? As it turns out, F# compiler can properly infer generic constraints over these interfaces. The result <code>env</code> type constraint is inferred to be an union - just like set union, which also means that it handles duplicates for us - of all constraints of other functions using <code>env</code> in its scope:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> foo env <span class="operator">=</span> <span class="comment">// env :> IDb and env :> ILog</span></span><br><span class="line"> <span class="keyword">let</span> user <span class="operator">=</span> Db.fetchUser env <span class="number">123</span> <span class="comment">// env :> IDb</span></span><br><span class="line"> Log.debug env <span class="string">"User: %A"</span> user <span class="comment">// env :> ILog</span></span><br></pre></td></tr></table></figure> + +<p>Now why did we use two separate interfaces (<code>ILog</code>/<code>ILogger</code>) instead of making environment implement <code>ILogger</code> directly? This is more practical approach that will let us isolate capabilities of particular modules rather than putting them flat into our environment. Example:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> Log <span class="operator">=</span></span><br><span class="line"> <span class="keyword">let</span> live <span class="operator">:</span> ILogger <span class="operator">=</span> <span class="operator">??</span> <span class="comment">// create logger interface</span></span><br><span class="line"></span><br><span class="line"><span class="meta">[<Struct>]</span></span><br><span class="line"><span class="keyword">type</span> <span class="title class_">AppEnv</span> <span class="operator">=</span> </span><br><span class="line"> <span class="keyword">interface</span> ILog <span class="keyword">with</span> <span class="keyword">member</span> _.Logger <span class="operator">=</span> Log.live</span><br><span class="line"> <span class="keyword">interface</span> IDb <span class="keyword">with</span> <span class="keyword">member</span> _.Database <span class="operator">=</span> Db.live connectionString</span><br><span class="line"> </span><br><span class="line">foo (AppEnv())</span><br></pre></td></tr></table></figure> + +<p>We cannot eagerly provide a specific implementation of <code>ILog</code>/<code>IDb</code>, because they’re yet to be defined as part of by our environment type (which may need to implement many interfaces). To maintain module encapsulation <code>Log</code> module shouldn’t be aware of existence or implementation of <code>IDb</code> interface and vice versa for <code>Db</code> module. What we can do however is to provide <code>live</code> implementation of <code>ILogger</code>, which encapsulates capabilities required by the <code>Log</code> module. This way we don’t need to know details of <code>ILogger</code> when defining our environment type.</p> +<p>Strong sides of this approach?:</p> +<ul> +<li>We only need to provide a single environment object instead of (potentially) unbounded list of parameters. Since it’s always one, it’s easier to generalize and compose other functions over it.</li> +<li>Unlike in reflection-based dependency injection frameworks - everything is still safe and checked by the compiler. If our environment type will not implement an interface required somewhere in the call chain, our code will simply not compile.</li> +<li>It’s still fairly easy to unit test - each function defines only the generic type constraints that it uses in its own call tree, NOT all of the constraints required by the application.</li> +<li>New dependencies are added implicitly - if your code uses module that requires additional capability, it will be automatically inferred by the compiler and bubble up to our environment type definition. No need to add new function parameters or to pass new argument. Also - unlike the object oriented IoC containers - there’s no need to add new dependency as a field or constructor argument.</li> +<li>It gives some opinionated approach on what should be a dependency - less thinking of <em>“should that be a function or interface?”</em> or <em>“if these two functions correspond to the same capability, should they be passed separately?”</em>, which arguably may be a good thing.</li> +<li>It doesn’t impose specific restrictions on libraries and frameworks.</li> +</ul> +<p>Now we could as well stop here - IMHO this approach is already good and useful for most cases. We can also try to push it further. As you’ve seen, our code now requires quite a lot of <code>env</code> passing around. Could we do something about this? It turns out that yes, we could.</p> +<h2 id="Reader-monad"><a href="#Reader-monad" class="headerlink" title="Reader monad"></a>Reader monad</h2><p>Before we continue: <strong>what we’re going to cover now is less useful in terms of current state of F# ecosystem for the reasons I’ll mention later</strong>.</p> +<p>The pattern we’ll use here is known as a <strong><a target="_blank" rel="noopener" href="https://fsharpforfunandprofit.com/posts/elevated-world-6/?ref=bartoszsypytkowski.com">Reader Monad</a></strong>. While it’s useful in certain situations, it’s not widely used - IMO it’s fault lies in the name itself, which somehow managed to sound both borderline meaningless and scary in ears of many developers.</p> +<p>The rest of this blog post will be introduction to this style in F#, however focused solely around problem of dependency management - we’ll ignore other aspects of monads.</p> +<p>We’ll going to reuse our environment type from above, but now encode it directly into another type we’ll call <code>Effect</code>. Since I’ve mentioned that our pattern has M-word in it, you can safely assume that our handler’s logic will be defined as a lazy sequence of steps to be executed (sounds almost like async/await). In F# we’ll sugar them by using custom computation expression (I’m going to call it <code>effect { ... }</code>) returning our effect type, which we’ll define as:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">[<Struct>]</span> <span class="keyword">type</span> <span class="title class_">Effect</span><span class="operator"><</span><span class="symbol">'env</span>, <span class="symbol">'out</span><span class="operator">></span> <span class="operator">=</span> Effect <span class="keyword">of</span> (<span class="symbol">'env</span> <span class="operator">-></span> <span class="symbol">'out</span>)</span><br></pre></td></tr></table></figure> + +<p>Where:</p> +<ul> +<li><code>env</code> is our environment type we already talked about above.</li> +<li><code>out</code> defines a returned value type of our effect.</li> +</ul> +<p>Eventually, with this type in hand our simple request handler will be looking like that:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> changePass req <span class="operator">=</span> <span class="keyword">effect</span> {</span><br><span class="line"> <span class="keyword">let!</span> user <span class="operator">=</span> Db.fetchUser req.UserId</span><br><span class="line"> <span class="keyword">if</span> user.Hash <span class="operator">=</span> bcrypt user.Salt req.OldPass <span class="keyword">then</span></span><br><span class="line"> <span class="keyword">let!</span> salt <span class="operator">=</span> Random.bytes <span class="number">32</span></span><br><span class="line"> <span class="keyword">do!</span> Db.<span class="keyword">updateUser</span> { user <span class="keyword">with</span> Salt <span class="operator">=</span> salt; Hash <span class="operator">=</span> bcrypt salt req.NewPass }</span><br><span class="line"> <span class="keyword">do!</span> Log.info <span class="string">"Changed password for user %i"</span> user.Id</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">Ok</span> ()</span><br><span class="line"> <span class="keyword">else</span> </span><br><span class="line"> <span class="keyword">do!</span> Log.error <span class="string">"Password change unauthorized: user %i"</span> user.Id</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">Error</span> <span class="string">"Old password is invalid"</span></span><br><span class="line">}</span><br></pre></td></tr></table></figure> + +<p>As you see, there’s no more <code>env</code> parameter being passed around. It’s now an implicit part of our effect expression. However at the moment we didn’t provide enough infrastructure in our code to make that thing work. What we’re going to need is a set of operators, we can use to make our computation expression happen.</p> +<p>First we’re going to need some <code>Effect<'env,'out></code> constructors:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> Effect <span class="operator">=</span></span><br><span class="line"> <span class="comment">/// Create value with no dependency requirements.</span></span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">inline</span> value (x<span class="operator">:</span> <span class="symbol">'out</span>)<span class="operator">:</span> Effect<span class="operator"><</span><span class="symbol">'env</span>,<span class="symbol">'out</span><span class="operator">></span> <span class="operator">=</span> Effect (<span class="keyword">fun</span> _ <span class="operator">-></span> x)</span><br><span class="line"> <span class="comment">/// Create value which uses depenendency.</span></span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">inline</span> apply (fn<span class="operator">:</span> <span class="symbol">'env</span> <span class="operator">-></span> <span class="symbol">'out</span>)<span class="operator">:</span> Effect<span class="operator"><</span><span class="symbol">'env</span>,<span class="symbol">'out</span><span class="operator">></span> <span class="operator">=</span> Effect fn</span><br></pre></td></tr></table></figure> + +<p>We also need some way to run our effect to be able to make it… well effectful:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> Effect <span class="operator">=</span></span><br><span class="line"></span><br><span class="line"> <span class="comment">(* ...other functions... *)</span></span><br><span class="line"> </span><br><span class="line"> <span class="keyword">let</span> run (env<span class="operator">:</span> <span class="symbol">'env</span>) (Effect fn)<span class="operator">:</span> <span class="symbol">'out</span> <span class="operator">=</span> fn env</span><br></pre></td></tr></table></figure> + +<p>And since we already mentioned <code>Effect</code> is monad, we also gonna need a <code>bind</code> function as well if we want to compose our effects together:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> Effect <span class="operator">=</span></span><br><span class="line"></span><br><span class="line"> <span class="comment">(* ...other functions... *)</span></span><br><span class="line"> </span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">inline</span> bind (fn<span class="operator">:</span> <span class="symbol">'a</span> <span class="operator">-></span> Effect<span class="operator"><</span><span class="symbol">'env</span>,<span class="symbol">'b</span><span class="operator">></span>) effect <span class="operator">=</span></span><br><span class="line"> Effect (<span class="keyword">fun</span> env <span class="operator">-></span></span><br><span class="line"> <span class="keyword">let</span> x <span class="operator">=</span> run env effect <span class="comment">// compute result of the first effect</span></span><br><span class="line"> run env (fn x) <span class="comment">// run second effect, based on result of first one</span></span><br><span class="line"> )</span><br></pre></td></tr></table></figure> + +<p>This is pretty much it. We’re just going to add compose all of these into builder type to make it usable as F# computation expression:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">[<Struct>]</span></span><br><span class="line"><span class="keyword">type</span> <span class="title class_">EffectBuilder</span> <span class="operator">=</span></span><br><span class="line"> <span class="keyword">member</span> <span class="keyword">inline</span> __.Return value <span class="operator">=</span> Effect.value value</span><br><span class="line"> <span class="keyword">member</span> <span class="keyword">inline</span> __.Zero () <span class="operator">=</span> Effect.value (Unchecked.defaultof<span class="operator"><</span>_<span class="operator">></span>)</span><br><span class="line"> <span class="keyword">member</span> <span class="keyword">inline</span> __.ReturnFrom (effect<span class="operator">:</span> Effect<span class="operator"><</span><span class="symbol">'env</span>, <span class="symbol">'out</span><span class="operator">></span>) <span class="operator">=</span> effect</span><br><span class="line"> <span class="keyword">member</span> <span class="keyword">inline</span> __.Bind(effect, fn) <span class="operator">=</span> Effect.bind fn effect</span><br><span class="line"> </span><br><span class="line"><span class="keyword">let</span> effect <span class="operator">=</span> EffectBuilder()</span><br></pre></td></tr></table></figure> + +<p>Of course this, we still need to adapt the modules we prepared earlier to now operate on effects rater than plain functions. We can make this easier by using our <code>Effect.apply</code> function, like:</p> +<figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> Log <span class="operator">=</span> </span><br><span class="line"> <span class="keyword">let</span> debug fmt <span class="operator">=</span></span><br><span class="line"> <span class="keyword">let</span> ap s <span class="operator">=</span> Effect.apply (<span class="keyword">fun</span> (x<span class="operator">:</span> #ILog) <span class="operator">-></span> x.Logger.Debug s)</span><br><span class="line"> Printf.kprintf ap fmt</span><br></pre></td></tr></table></figure> + +<p>So - as you may have noticed in final form of our effect-based <code>changePass</code> function - in result we almost fully erased all of the dependency-wiring code from our example. There are several downsides of this approach:</p> +<ul> +<li>We do a lot of more bindings (see <code>let!</code>/<code>do!</code> expressions), which means more lambda closures, indirection (wait to see call stacks) and more allocations.</li> +<li>Altogether we also erased <code>task { ... }</code> computation expression and with it an out-of-the-box ability to write asynchronous code. This is one of the downsides of using monads - cross-type composition is painful.</li> +</ul> +<p>Of course we could enrich our <code>Effect</code> type to be able to bind it with <code>Task</code>/<code>Async</code>. That however means, that our pattern grows in complexity and becomes more of a framework rather than something to be easily applied into existing code. Is that bad? Not necessarily, but for sure comes with a bigger commitment, as now you’re not only writing business logic but eventually maintain new effect library. Maybe in future this concept will grow into its own space in favor of the F# ecosystem.</p> +<h2 id="Summary"><a href="#Summary" class="headerlink" title="Summary"></a>Summary</h2><p>We came from partial application as tool for dependency injection, over more structured approach promoting single environment type with help of powerful F# type inference, up to encapsulating it into a Reader Monad. That’s a long way. I hope you’ll give it a try and it will help you determine the approach that works for you.</p> + +</div> + +<script> + window.onload = detectors(); +</script> + <div class="post-footer"> + <div class="h-line-primary"></div> + <nav class="post-nav"> + <div class="prev-item"> + + <div class="icon arrow-left"></div> + <div class="post-link"> + <a href="/2024/10/18/Building-custom-fibers-library-in-FSharp/">Prev</a> + </div> + + </div> + <div class="next-item"> + + <div class="icon arrow-right"></div> + <div class="post-link"> + <a href="/2024/10/06/Obsidian-Vault-%E7%9A%84-obsidian-%E7%9B%AE%E5%BD%95%E4%B8%AD%E7%9A%84%E5%90%84%E6%96%87%E4%BB%B6%E4%BD%9C%E7%94%A8/">Next</a> + </div> + + </div> + </nav> +</div> + + + <div class="post-comment"> + + + + + + + +</div> + + +</article> + </div> + </div> + + <div class="footer"> + <div class="flex-container"> + <div class="footer-text"> + + + | + + + 希望路过的人可以添点柴火让这里暖和点 + + </div> + </div> +</div> + + </div> + + + <div class="search-popup"> + <div class="search-popup-overlay"> + </div> + <div class="search-popup-window" > + <div class="search-header"> + <div class="search-input-container"> + <input autocomplete="off" autocapitalize="off" maxlength="80" + placeholder="Search Anything" spellcheck="false" + type="search" class="search-input"> + </div> + <div class="search-close-btn"> + <div class="icon close-btn"></div> + </div> + </div> + <div class="search-result-container"> + </div> + </div> +</div> + +<script> + const searchConfig = { + path : "/search.xml", + top_n_per_article: "1", + unescape : "false", + trigger: "auto", + preload: "false" + } +</script> +<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/search.js"></script> +<script src="/js/search.js"></script> + + + + </body> +</html> diff --git a/2024/10/18/Generalised-signature/index.html b/2024/10/18/Generalised-signature/index.html new file mode 100644 index 00000000..b5297985 --- /dev/null +++ b/2024/10/18/Generalised-signature/index.html @@ -0,0 +1,383 @@ +<!DOCTYPE html> +<html lang="en"> + <head> + <meta charset="UTF-8"> +<meta name="viewport" + content="width=device-width, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0"> +<meta http-equiv="X-UA-Compatible" content="ie=edge"> + + <meta name="author" content="韩暮秋"> + + + <meta name="subtitle" content="暮秋小屋"> + + + <meta name="description" content="这里是暮秋小屋,思念和灵感的寄存处"> + + + <meta name="keywords" content="韩暮秋,MuqiuHan,'Muqiu Han', 'muqiu han', muqiuhan"> + + + + +<title>Generalised signature | 暮秋小屋</title> + + + + <link rel="icon" href="/favicon.ico"> + + + +<style> + @import url('https://fonts.googleapis.com/css2?family=Inter:wght@300;400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&family=Roboto+Mono&display=swap'); +</style> + + + + <!-- stylesheets list from _config.yml --> + + <link rel="stylesheet" href="/css/style.css"> + + + + + + <!-- scripts list from _config.yml --> + + <script src="/js/frame.js"></script> + + + + + + <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script> + <script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script> + + + + + + + + <meta name="generator" content="Hexo 6.3.0"></head> + <body> + <div class="mask-border"> + </div> + + <div class="wrapper"> + + <div class="header"> + <div class="flex-container"> + <div class="header-inner"> + <div class="site-brand-container"> + <a href="/"> + + 暮秋小屋 + + </a> + </div> + <div id="menu-btn" class="menu-btn" onclick="toggleMenu()"> + Menu + </div> + <nav class="site-nav"> + <ul class="menu-list"> + + + <li class="menu-item"> + <a href="/">主页</a> + </li> + + + + <li class="menu-item"> + <a href="/categories/gallery/">日记本</a> + </li> + + + + <li class="menu-item"> + <a href="/tags/Medicine/">医学</a> + </li> + + + + <li class="menu-item"> + <a href="/tags/Technique/">计算机科学</a> + </li> + + + + <li class="menu-item"> + <a href="/tags/Life/">生活</a> + </li> + + + + <li class="menu-item"> + <a href="/about">关于</a> + </li> + + + + <li class="menu-item search-btn"> + <a href="#">Search</a> + </li> + + </ul> + </nav> + </div> + </div> +</div> + + + <div class="main"> + <div class="flex-container"> + <article id="post"> + + + <div class="post-head"> + <div class="post-info"> + <div class="tag-list"> + + + <span class="post-tag"> + <a href="/tags/Technique/"> + Technique + </a> + </span> + + <span class="post-tag"> + <a href="/tags/Archive/"> + Archive + </a> + </span> + + <span class="post-tag"> + <a href="/tags/OCaml/"> + OCaml + </a> + </span> + + + </div> + <div class="post-title"> + + + Generalised signature + + + </div> + <span class="post-date"> + Oct 18, 2024 + </span> + </div> + <div class="post-img"> + + <div class="h-line-primary"></div> + + </div> +</div> + <div class="post-content"> + <p>#ocaml #fp</p> +<blockquote> +<p><em>This post presents a technique for defining more reusable OCaml signatures, helping to maintain consistent APIs with minimal boilerplate. We’ll work through a few examples, which you can check out <a target="_blank" rel="noopener" href="https://github.com/CraigFe/generalised-signatures">on GitHub</a>.</em></p> +</blockquote> +<h2 id="Indexable-containers"><a href="#Indexable-containers" class="headerlink" title="Indexable containers"></a>Indexable containers</h2><p>Consider the following definition of an <code>iter</code> function for some container type <code>t</code>:</p> +<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> iter f t =</span><br><span class="line"> <span class="keyword">for</span> i = <span class="number">0</span> <span class="keyword">to</span> length t - <span class="number">1</span> <span class="keyword">do</span></span><br><span class="line"> f (get t i)</span><br><span class="line"> <span class="keyword">done</span></span><br></pre></td></tr></table></figure> + +<p><code>iter</code> requires only that <code>t</code> comes with functions <code>get</code> and <code>length</code>. Many useful operations can be derived in terms of such indexing functions. To take advantage of this, let’s move <code>iter</code> into a functor and provide some other useful operations too:</p> +<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> <span class="keyword">type</span> <span class="type">Indexable1</span> = <span class="keyword">sig</span></span><br><span class="line"> <span class="keyword">type</span> <span class="symbol">'a</span> t</span><br><span class="line"></span><br><span class="line"> <span class="keyword">val</span> get : <span class="symbol">'a</span> t -> <span class="built_in">int</span> -> <span class="symbol">'a</span></span><br><span class="line"> <span class="keyword">val</span> length : _ t -> <span class="built_in">int</span></span><br><span class="line"><span class="keyword">end</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">module</span> <span class="type">Foldable_of_indexable1</span> (<span class="type">I</span> : <span class="type">Indexable1</span>) : <span class="keyword">sig</span></span><br><span class="line"> <span class="keyword">open</span> <span class="type">I</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">val</span> iter : (<span class="symbol">'a</span> -> <span class="built_in">unit</span>) -> <span class="symbol">'a</span> t -> <span class="built_in">unit</span></span><br><span class="line"> <span class="keyword">val</span> iteri : (<span class="built_in">int</span> -> <span class="symbol">'a</span> -> <span class="built_in">unit</span>) -> <span class="symbol">'a</span> t -> <span class="built_in">unit</span></span><br><span class="line"> <span class="keyword">val</span> fold_left : (<span class="symbol">'acc</span> -> <span class="symbol">'a</span> -> <span class="symbol">'acc</span>) -> <span class="symbol">'acc</span> -> <span class="symbol">'a</span> t -> <span class="symbol">'acc</span></span><br><span class="line"> <span class="keyword">val</span> exists : (<span class="symbol">'a</span> -> <span class="built_in">bool</span>) -> <span class="symbol">'a</span> t -> <span class="built_in">bool</span></span><br><span class="line"> <span class="keyword">val</span> for_all : (<span class="symbol">'a</span> -> <span class="built_in">bool</span>) -> <span class="symbol">'a</span> t -> <span class="built_in">bool</span></span><br><span class="line"> <span class="keyword">val</span> is_empty : _ t -> <span class="built_in">bool</span></span><br><span class="line"> <span class="comment">(* ... *)</span></span><br><span class="line"><span class="keyword">end</span></span><br></pre></td></tr></table></figure> + +<p>For many types, including <code>array</code>, the <code>get</code>-based definitions are identical to their hand-optimised equivalents (modulo functor application). We can imagine avoiding a lot of standard-library boilerplate – and potential for API inconsistency – by using many such functors <a target="_blank" rel="noopener" href="https://www.craigfe.io/posts/generalised-signatures#fn-1">1</a>. We’d end up defining exactly one <code>iter</code> function that suffices for all <code>Indexable</code> types.</p> +<p>All good so far. Now, let’s consider the <code>string</code> type.</p> +<p>A <code>string</code> is also an indexable container with <code>length</code> and <code>get</code> functions, albeit one that can only contain <code>char</code> values. It’s natural to expect to be able to re-use <code>Foldable_of_indexable1</code> in some way: indeed, our definition of <code>iter</code> above is exactly equal to the one in <code>Stdlib.String.iter</code>. Unfortunately, our <code>Indexable1</code> module type can only describe parametric containers:</p> +<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> _ : (<span class="type">Indexable1</span> <span class="keyword">with</span> <span class="keyword">type</span> <span class="symbol">'a</span> t := <span class="built_in">string</span>) = <span class="type">Stdlib</span>.<span class="type">String</span></span><br></pre></td></tr></table></figure> + +<figure class="highlight text"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">Error: Signature mismatch:</span><br><span class="line"> ...</span><br><span class="line"> Values do not match:</span><br><span class="line"> val get : t -> int -> char</span><br><span class="line"> is not included in</span><br><span class="line"> val get : t -> int -> 'a</span><br><span class="line"> File "string.mli", line 52, characters 0-57: Actual declaration</span><br></pre></td></tr></table></figure> + +<p>We’re unable to tell the type system something like</p> +<blockquote> +<p><code>'a t = string</code> <em>implies</em> <code>'a = char</code></p> +</blockquote> +<p>as part of our substitution. This means that many types – including <code>string</code>, <code>bytes</code>, unboxed arrays and unboxed vectors – can’t benefit from our <code>Foldable_of_iterable1</code> definitions, even though their own definitions will be identical!</p> +<p>When we wrapped our code in the <code>Foldable_of_indexable1</code> functor, we needed to give it specific input and output module types, and the ones we picked artificially limited its usefulness. This is a hazard of functorising highly-generic code. As ever, we <em>could</em> solve the problem with copy-paste: a new <code>Indexable0</code> module type for non-parametric containers, and a new functor <code>Foldable_of_indexable0</code> with exactly the same implementations as our previous one.</p> +<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">(* Non-parametric indexable types *)</span></span><br><span class="line"><span class="keyword">module</span> <span class="keyword">type</span> <span class="type">Indexable0</span> = <span class="keyword">sig</span></span><br><span class="line"> <span class="keyword">type</span> t</span><br><span class="line"> <span class="keyword">type</span> elt</span><br><span class="line"></span><br><span class="line"> <span class="keyword">val</span> get : t -> <span class="built_in">int</span> -> elt</span><br><span class="line"> <span class="keyword">val</span> length : t -> <span class="built_in">int</span></span><br><span class="line"><span class="keyword">end</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">module</span> <span class="type">Foldable_of_indexable0</span> (<span class="type">I</span> : <span class="type">Indexable0</span>) : <span class="keyword">sig</span></span><br><span class="line"> <span class="comment">(* All with the same implementation as before... *)</span></span><br><span class="line"><span class="keyword">end</span></span><br></pre></td></tr></table></figure> + +<p>This definition suffers from the dual problem when we try to apply it to parameterised containers like <code>'a array</code>:</p> +<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> _ : (<span class="type">Indexable0</span> <span class="keyword">with</span> <span class="keyword">type</span> t := <span class="symbol">'a</span> <span class="built_in">array</span>) = <span class="type">Stdlib</span>.<span class="type">Array</span></span><br></pre></td></tr></table></figure> + +<figure class="highlight text"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">Error: The type variable 'a is unbound in this type declaration.</span><br></pre></td></tr></table></figure> + +<p>This time, we wanted to be able to say something like</p> +<blockquote> +<p><code>elt = 'a</code> <em>implies</em> <code>t = 'a array</code> (where <code>'a</code> is universally quantified),</p> +</blockquote> +<p>which is even more nonsensical than our previous attempt. Neither <code>Indexable0</code> nor <code>Indexable1</code> can be expressed in terms of the other. We need something more general.</p> +<h2 id="Something-more-general"><a href="#Something-more-general" class="headerlink" title="Something more general"></a>Something more general</h2><p>Interestingly, it’s possible to generalise <code>Indexable0</code> and <code>Indexable1</code> with <a target="_blank" rel="noopener" href="https://en.wikipedia.org/wiki/Fundamental_theorem_of_software_engineering">another layer of indirection</a> by making <code>elt</code> a type <em>operator</em>:</p> +<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> <span class="keyword">type</span> <span class="type">IndexableN</span> = <span class="keyword">sig</span></span><br><span class="line"> <span class="keyword">type</span> <span class="symbol">'a</span> t</span><br><span class="line"> <span class="keyword">type</span> <span class="symbol">'a</span> elt</span><br><span class="line"></span><br><span class="line"> <span class="keyword">val</span> get : <span class="symbol">'a</span> t -> <span class="built_in">int</span> -> <span class="symbol">'a</span> elt</span><br><span class="line"> <span class="keyword">val</span> length : _ t -> <span class="built_in">int</span></span><br><span class="line"><span class="keyword">end</span></span><br></pre></td></tr></table></figure> + +<p><code>elt</code> carries the type equalities needed for the <code>Indexable1</code> case, without forbidding the non-parametric implementation needed for the <code>Indexable0</code> case. Arrays can set <code>'a elt := 'a</code>, and strings can set <code>'a elt := char</code>. Indeed, we can do this in the general case:</p> +<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">(** [Indexable0] is a special-case of [IndexableN] *)</span></span><br><span class="line"><span class="keyword">module</span> <span class="type">Indexable0_to_N</span> = <span class="keyword">functor</span></span><br><span class="line"> (<span class="type">T</span> : <span class="type">Indexable0</span>) -></span><br><span class="line"> (<span class="type">T</span> : <span class="type">IndexableN</span> <span class="keyword">with</span> <span class="keyword">type</span> <span class="symbol">'a</span> t := <span class="type">T</span>.t <span class="keyword">and</span> <span class="keyword">type</span> <span class="symbol">'a</span> elt := elt)</span><br><span class="line"></span><br><span class="line"><span class="comment">(** [Indexable1] is a special-case of [IndexableN] *)</span></span><br><span class="line"><span class="keyword">module</span> <span class="type">Indexable1_to_N</span> = <span class="keyword">functor</span></span><br><span class="line"> (<span class="type">T</span> : <span class="type">Indexable1</span>) -></span><br><span class="line"> (<span class="type">T</span> : <span class="type">IndexableN</span> <span class="keyword">with</span> <span class="keyword">type</span> <span class="symbol">'a</span> t := <span class="symbol">'a</span> <span class="type">T</span>.t <span class="keyword">and</span> <span class="keyword">type</span> <span class="symbol">'a</span> elt := <span class="symbol">'a</span>)</span><br></pre></td></tr></table></figure> + +<p>Now we can define a single <code>Foldable_of_indexableN</code> functor (with exactly the same implementations as before), and it will work for polymorphic and monomorphic containers. Neat!</p> +<p><img src="https://www.craigfe.io/posts/generalised-signatures/dag-indexable.png" alt="A lattice showing Indexable0 and Indexable1 being generalised by IndexableN."></p> +<p>In the general case, when you notice that different signatures are sharing common functions, it’s often possible to unify them under a common interface with the following two steps:</p> +<ol> +<li><p><em><strong>generalise</strong></em>. Convert pure type variables into type operators (as in <code>'a</code> → <code>'a elt</code>), to support use-cases like instantiating those variables to fixed types. Add type parameters to existing types to carry type equalities between them (as in <code>'a t</code> / <code>'a elt</code>), to support use-cases where these types depend on each other.</p> +</li> +<li><p><em><strong>specialise</strong></em>. Use destructive substitution (<code>:=</code>) to eliminate those types and type parameters when they’re not needed. We’re taking advantage of the <a target="_blank" rel="noopener" href="https://github.com/ocaml/ocaml/pull/792">more powerful destructive substitution</a> offered by OCaml 4.06, which allows us to freely undo our generalisation step.</p> +</li> +</ol> +<p>The truly magical part of this trick is that – with better support for destructive type substitutions recently added to Odoc – it can be made <strong>completely invisible</strong><a target="_blank" rel="noopener" href="https://www.craigfe.io/posts/generalised-signatures#fn-2">2</a> in documentation!</p> +<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> <span class="keyword">type</span> <span class="type">Indexable1</span> = <span class="keyword">sig</span></span><br><span class="line"> <span class="keyword">type</span> _ t</span><br><span class="line"></span><br><span class="line"> <span class="keyword">val</span> get : <span class="symbol">'a</span> t -> <span class="built_in">int</span> -> <span class="symbol">'a</span></span><br><span class="line"> <span class="keyword">val</span> length : _ t -> <span class="built_in">int</span></span><br><span class="line"><span class="keyword">end</span></span><br><span class="line"></span><br><span class="line"><span class="comment">(** This module gets identical documentation to the one above! *)</span></span><br><span class="line"><span class="keyword">module</span> <span class="keyword">type</span> <span class="type">Indexable1'</span> = <span class="keyword">sig</span></span><br><span class="line"> <span class="keyword">include</span> <span class="type">IndexableN</span> <span class="keyword">with</span> <span class="keyword">type</span> <span class="symbol">'a</span> elt := <span class="symbol">'a</span> <span class="comment">(** @inline *)</span></span><br><span class="line"><span class="keyword">end</span></span><br></pre></td></tr></table></figure> + +<h2 id="What’s-the-cost"><a href="#What’s-the-cost" class="headerlink" title="What’s the cost?"></a>What’s the cost?</h2><p>One unavoidable limitation is in what sort of operations we can put in the <code>Foldable_of_indexable</code> functor. Suppose our initial attempt at generalising containers included a <code>sum</code> function:</p> +<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> sum : <span class="built_in">int</span> t -> t = fold_left ( + ) <span class="number">0</span></span><br></pre></td></tr></table></figure> + +<p><code>sum</code> requires a container that can hold <code>int</code> values, which is clearly not possible for strings as the type system will happily tell us:</p> +<figure class="highlight text"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"> | let sum = fold_left ( + ) 0</span><br><span class="line"> ^^^^^</span><br><span class="line">Error: This expression has type int -> int -> int</span><br><span class="line"> but an expression was expected of type int -> 'a elt -> int</span><br><span class="line"> Type int is not compatible with type 'a elt</span><br></pre></td></tr></table></figure> + +<p>To state the obvious, we can’t rely on parametricity in our container functions if we want them to work on non-parametric containers. The natural solution here would be to define such parametric-only functions in a separate functor.</p> +<h2 id="Other-examples"><a href="#Other-examples" class="headerlink" title="Other examples"></a>Other examples</h2><p>Indexable containers aren’t the only example of generalised signatures in the real world. Indeed, many other data-structures and design patterns have APIs that can be unified in this way. Consider the case of <em>hashtables</em>, which have a huge space of possible implementations:</p> +<ul> +<li><p><code>key</code> types can be left polymorphic by using a magic hash function like <code>caml_hash</code> (as in <a target="_blank" rel="noopener" href="https://caml.inria.fr/pub/docs/manual-ocaml/libref/Hashtbl.html"><code>Stdlib.Hashtbl</code></a>), or fixed by a user-specified hash function (as in <a target="_blank" rel="noopener" href="https://caml.inria.fr/pub/docs/manual-ocaml/libref/Hashtbl.Make.html"><code>Stdlib.Hashtbl.Make</code></a>).</p> +</li> +<li><p><code>value</code> types can be left polymorphic, fixed by the user (as in persistent hashtables like <a target="_blank" rel="noopener" href="https://mirage.github.io/index/index/Index/Make/index.html"><code>Index</code></a>), or even determined by the keys used to index them (as in universal maps like <a target="_blank" rel="noopener" href="https://erratique.ch/software/hmap/doc/Hmap"><code>Hmap</code></a>).</p> +</li> +</ul> +<p>Initially, it looks like these different hashtables will each require their own hand-written signature (and this is what the standard library does with its hashtables). However, with enough type parameters, these different implementations can all be unified under a single <code>Hashtbl_generalised</code> module type:</p> +<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> <span class="keyword">type</span> <span class="type">Hashtbl_generalised</span> = <span class="keyword">sig</span></span><br><span class="line"> <span class="comment">(** We have three types ([t], [key] and [value]) and three type variables:</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment"> - ['k]/['v] allow the hashtable to determine key/value types;</span></span><br><span class="line"><span class="comment"> - ['a] is carried from keys to corresponding values, allowing the key to</span></span><br><span class="line"><span class="comment"> determine the types of values. *)</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">type</span> (<span class="symbol">'k</span>, <span class="symbol">'v</span>) t</span><br><span class="line"> <span class="keyword">type</span> (<span class="symbol">'k</span>, <span class="symbol">'a</span>) key</span><br><span class="line"> <span class="keyword">type</span> (<span class="symbol">'v</span>, <span class="symbol">'a</span>) <span class="keyword">value</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">val</span> create : <span class="built_in">int</span> -> (_, _) t</span><br><span class="line"> <span class="keyword">val</span> replace : (<span class="symbol">'k</span>, <span class="symbol">'v</span>) t -> (<span class="symbol">'k</span>, <span class="symbol">'a</span>) key -> (<span class="symbol">'v</span>, <span class="symbol">'a</span>) <span class="keyword">value</span> -> <span class="built_in">unit</span></span><br><span class="line"> <span class="keyword">val</span> remove : (<span class="symbol">'k</span>, _) t -> (<span class="symbol">'k</span>, _) key -> <span class="built_in">unit</span></span><br><span class="line"> <span class="keyword">val</span> find_opt : (<span class="symbol">'k</span>, <span class="symbol">'v</span>) t -> (<span class="symbol">'k</span>, <span class="symbol">'a</span>) key -> (<span class="symbol">'v</span>, <span class="symbol">'a</span>) <span class="keyword">value</span> option</span><br><span class="line"> <span class="comment">(* ... *)</span></span><br><span class="line"><span class="keyword">end</span></span><br></pre></td></tr></table></figure> + +<p>We can then implement our different hashtable signatures as specialisations:</p> +<p><img src="https://www.craigfe.io/posts/generalised-signatures/dag-hashtables.png" alt="A lattice showing four different `Hashtbl` module types being generalised by `Hashtbl_generalised`."></p> +<p>For instance, for the regular polymorphic hashtable:</p> +<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> <span class="keyword">type</span> <span class="type">Poly_hash</span> = <span class="keyword">sig</span></span><br><span class="line"> <span class="keyword">include</span> <span class="type">Hashtbl_generalised</span></span><br><span class="line"> <span class="keyword">with</span> <span class="keyword">type</span> (<span class="symbol">'k</span>, _) key := <span class="symbol">'k</span></span><br><span class="line"> <span class="keyword">and</span> <span class="keyword">type</span> (<span class="symbol">'v</span>, _) <span class="keyword">value</span> := <span class="symbol">'v</span> <span class="comment">(** @inline **)</span></span><br><span class="line"><span class="keyword">end</span></span><br></pre></td></tr></table></figure> + +<p>The other specialisations are very similar (see <a target="_blank" rel="noopener" href="https://github.com/CraigFe/generalised-signatures/blob/main/examples/hashtbl.ml">here</a> for the specifics).</p> +<p>What is it that makes <code>Hashtable_generalised</code> a good parent interface for these four flavours of hashtable? To get some insight, we can notice that each of the type parameters (<code>'k</code>, <code>'v</code>, and <code>'a</code>) connects its own pair of types:</p> +<p><code>hashtbl_generalised</code></p> +<p><img src="https://www.craigfe.io/posts/generalised-signatures/dep-hashtbl_generalised.png"></p> +<p>Framed this way, the type parameter <code>'k</code> exists solely to carry type information between hashtables and their keys (using a type equality at call sites). Similarly, <code>'v</code> bridges between hashtables and values, and <code>'a</code> between keys and values. From here, each of our hashtable variants uses destructive subsitution (<code>:=</code>) to prune away unnecessary bridges and express some sort of dependency relation between the types:</p> +<table> +<thead> +<tr> +<th></th> +<th></th> +</tr> +</thead> +<tbody><tr> +<td><code>poly_hash</code><br><br><img src="https://www.craigfe.io/posts/generalised-signatures/dep-poly_hash.png"><br><br>Keys and value types constrain <code>t</code> at call-sites.</td> +<td><code>mono_hash</code><br><br><img src="https://www.craigfe.io/posts/generalised-signatures/dep-mono_hash.png"><br><br>The value type constrains <code>t</code>, but <code>key</code>is fixed by a functor.</td> +</tr> +<tr> +<td><code>persistent</code><br><br><img src="https://www.craigfe.io/posts/generalised-signatures/dep-persistent.png"><br><br>Both key and value types are fixed by a functor.</td> +<td><code>universal</code><br><br><img src="https://www.craigfe.io/posts/generalised-signatures/dep-universal.png"><br><br>Each key’s type constrains the corresponding value’s type.</td> +</tr> +</tbody></table> +<p>In this case, it’s not feasible for all these data structures to share the same implementation, but it’s still valuable for them to implement a common core API: it ensures consistency of the user-facing functions, allows sharing of documentation, and may even allow these implementations to share a common test suite.</p> +<h2 id="Conclusion"><a href="#Conclusion" class="headerlink" title="Conclusion"></a>Conclusion</h2><p>The full code for our <code>Indexable</code> and <code>Hashtbl</code> examples, including explicit definitions of each of the module types, can be found in the <a target="_blank" rel="noopener" href="https://github.(com/CraigFe/generalised-signatures)"><code>generalised-signatures</code> repository</a>. This repository also contains and a <a target="_blank" rel="noopener" href="https://github.com/CraigFe/generalised-signatures/blob/main/examples/monads.ml">third demonstration</a> of this technique being used to express monad-like signatures. The auto-generated documentation for these examples can be <a target="_blank" rel="noopener" href="https://craigfe.github.io/generalised-signatures/generalised_signatures/Generalised_signatures/index.html">viewed online</a>.x</p> +<p>Thanks for making it to the end; I hope you picked up something useful. If you think it would help others in your network, I’d appreciate it if you <a target="_blank" rel="noopener" href="https://twitter.com/share?url=NaN&text=%E2%80%9CGeneralised%20signatures%E2%80%9D,%20a%20post%20by%20Craig%20Ferguson.%20&via=_craigfe">shared it</a> with them.</p> +<hr> +<h4 id="Appendix-A-Haskell-suffers-too"><a href="#Appendix-A-Haskell-suffers-too" class="headerlink" title="Appendix A: Haskell suffers too"></a>Appendix A: Haskell suffers too</h4><p>The typeclasses in Haskell’s <a target="_blank" rel="noopener" href="https://hackage.haskell.org/package/base-4.14.0.0/docs/Data-Foldable.html">base</a> have the same “polymorphic-instances-only” property as our <code>Indexable1</code> signature (unsurprising, since it doesn’t provide any unboxed container types).</p> +<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="type">Indexable1</span> f <span class="keyword">where</span></span> <span class="comment">-- Polymorphic instances only</span></span><br><span class="line"> get :: f a -> <span class="type">Int</span> -> a</span><br><span class="line"> length :: f a -> <span class="type">Int</span></span><br></pre></td></tr></table></figure> + +<p>A similar trick can be performed there to generalise the typeclass instances for monomorphic containers like <code>Text</code>:</p> +<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">{-# LANGUAGE TypeFamilies #-}</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">type</span> <span class="keyword">family</span> <span class="type">Elt</span> container <span class="comment">-- Relate containers to their element type</span></span></span><br><span class="line"><span class="class"><span class="keyword">type</span> instance <span class="type">Elt</span> [a] = a</span></span><br><span class="line"><span class="class"><span class="keyword">type</span> instance <span class="type">Elt</span> <span class="type">Text</span> = <span class="type">Char</span></span></span><br><span class="line"><span class="class"></span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="type">IndexableN</span> c <span class="keyword">where</span></span></span><br><span class="line"> get :: c -> <span class="type">Int</span> -> <span class="type">Elt</span> c</span><br><span class="line"> length :: c -> <span class="type">Int</span></span><br><span class="line"><span class="class"></span></span><br><span class="line"><span class="class"><span class="keyword">instance</span> <span class="type">IndexableN</span> [a] <span class="keyword">where</span></span> <span class="comment">-- Polymorphic instance</span></span><br><span class="line"> get = (!!)</span><br><span class="line"> length = <span class="type">Prelude</span>.length</span><br><span class="line"><span class="class"></span></span><br><span class="line"><span class="class"><span class="keyword">instance</span> <span class="type">IndexableN</span> <span class="type">Text</span> <span class="keyword">where</span></span> <span class="comment">-- Monomorphic instance</span></span><br><span class="line"> get = <span class="type">Text</span>.index</span><br><span class="line"> length = <span class="type">Text</span>.length</span><br></pre></td></tr></table></figure> + +<p>As in the OCaml version, we use an <code>Elt</code> type operator to carry the equality needed for the monomorphic case. This time we used type families to specify the relations explicitly, but we could have used multi-parameter type classes for something more akin to the OCaml functor implementation. See the <a target="_blank" rel="noopener" href="https://hackage.haskell.org/package/mono-traversable">mono-traversable</a> package for more of this sort of trickery in Haskell.</p> +<hr> +<ol> +<li>This is the approach taken by Jane Street’s <a target="_blank" rel="noopener" href="https://github.com/janestreet/base">base</a>, and is very similar to the Haskell notion of building standard libraries from type-class instances.<a target="_blank" rel="noopener" href="https://www.craigfe.io/posts/generalised-signatures#fnref-1">↩</a></li> +<li>This example uses the <code>(** @inline *)</code> tag to ensure that Odoc doesn’t leak that <code>Indexable1'</code> is implemented in terms of <code>IndexableN</code>.<a target="_blank" rel="noopener" href="https://www.craigfe.io/posts/generalised-signatures#fnref-2">↩</a></li> +</ol> + +</div> + +<script> + window.onload = detectors(); +</script> + <div class="post-footer"> + <div class="h-line-primary"></div> + <nav class="post-nav"> + <div class="prev-item"> + + </div> + <div class="next-item"> + + <div class="icon arrow-right"></div> + <div class="post-link"> + <a href="/2024/10/18/10-Tips-for-Productive-FSharp-Scripting/">Next</a> + </div> + + </div> + </nav> +</div> + + + <div class="post-comment"> + + + + + + + +</div> + + +</article> + </div> + </div> + + <div class="footer"> + <div class="flex-container"> + <div class="footer-text"> + + + | + + + 希望路过的人可以添点柴火让这里暖和点 + + </div> + </div> +</div> + + </div> + + + <div class="search-popup"> + <div class="search-popup-overlay"> + </div> + <div class="search-popup-window" > + <div class="search-header"> + <div class="search-input-container"> + <input autocomplete="off" autocapitalize="off" maxlength="80" + placeholder="Search Anything" spellcheck="false" + type="search" class="search-input"> + </div> + <div class="search-close-btn"> + <div class="icon close-btn"></div> + </div> + </div> + <div class="search-result-container"> + </div> + </div> +</div> + +<script> + const searchConfig = { + path : "/search.xml", + top_n_per_article: "1", + unescape : "false", + trigger: "auto", + preload: "false" + } +</script> +<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/search.js"></script> +<script src="/js/search.js"></script> + + + + </body> +</html> |
