<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Nimalan on Medium]]></title>
        <description><![CDATA[Stories by Nimalan on Medium]]></description>
        <link>https://medium.com/@nimalan854?source=rss-571b24ff626d------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*yVHaaApuO4N_KOwj</url>
            <title>Stories by Nimalan on Medium</title>
            <link>https://medium.com/@nimalan854?source=rss-571b24ff626d------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 13:23:01 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@nimalan854/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[APL — The Evil Twin of Function Programming]]></title>
            <link>https://medium.com/@nimalan854/apl-the-evil-twin-of-function-programming-3e446006fc9e?source=rss-571b24ff626d------2</link>
            <guid isPermaLink="false">https://medium.com/p/3e446006fc9e</guid>
            <category><![CDATA[functional-programming]]></category>
            <category><![CDATA[apl]]></category>
            <category><![CDATA[code-golf]]></category>
            <dc:creator><![CDATA[Nimalan]]></dc:creator>
            <pubDate>Sun, 19 Jul 2026 13:24:39 GMT</pubDate>
            <atom:updated>2026-07-19T13:24:39.188Z</atom:updated>
            <content:encoded><![CDATA[<h3>APL — The Evil Twin of Function Programming</h3><p>Donald Knuth had famously said that <strong>“programs are meant to be read by humans and only incidentally for computers to execute”</strong>. The APL family of languages have something different in mind….</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*QoHzU4ce-u_xk5iu" /><figcaption>Photo by <a href="https://unsplash.com/@gustavo0351?utm_source=medium&amp;utm_medium=referral">Gustavo Sánchez</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>APL is a programming language developed in the 1960s with a focus centrally on arrays. At it’s core verbs are composted together to form new verbs resembling a bit of functional programming in a different way. While the common consensus in programming languages is readability and maintainability of code, APL is generally very terse and intense to anyone new to the language. Hence I say APL is the “The evil twin of functional programming”</p><p>A k6 program to print a circle in stdout</p><pre>`0:&quot;\n&quot;/,/&#39;(&quot;  &quot;;&quot;oo&quot;)@c&#39;(c:{x,|x})t{11&gt;%(x*x)+(y*y)}/:t:|!13;</pre><p><strong>Result</strong></p><pre><br><br>                oooooooooooooooooooo<br>            oooooooooooooooooooooooooooo<br>          oooooooooooooooooooooooooooooooo<br>        oooooooooooooooooooooooooooooooooooo<br>      oooooooooooooooooooooooooooooooooooooooo<br>      oooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>      oooooooooooooooooooooooooooooooooooooooo<br>      oooooooooooooooooooooooooooooooooooooooo<br>        oooooooooooooooooooooooooooooooooooo<br>          oooooooooooooooooooooooooooooooo<br>            oooooooooooooooooooooooooooo<br>                oooooooooooooooooooo<br><br></pre><p>This seems like gibberish or something written for a code golf, trust me by the end of this article I’ll explain clearly how this program works. The same program in C</p><pre>#include &lt;stdio.h&gt;<br>#include &lt;math.h&gt;<br><br>int main(void) {<br>    int n = 13;          // half-axis length (coords 0..12)<br>    double r = 11.0;     // radius threshold<br><br>    // Full axis: mirror the half-range into a symmetric whole.<br>    // Half runs 12,11,...,0  then its reverse 0,...,11,12 -&gt; 26 values.<br>    int size = 2 * n;<br>    int axis[2 * 13];<br>    for (int i = 0; i &lt; n; i++) axis[i] = (n - 1) - i;          // 12..0<br>    for (int i = 0; i &lt; n; i++) axis[n + i] = i;                // 0..12<br><br>    for (int yi = 0; yi &lt; size; yi++) {<br>        for (int xi = 0; xi &lt; size; xi++) {<br>            int x = axis[xi];<br>            int y = axis[yi];<br>            int inside = sqrt((double)(x * x + y * y)) &lt; r;<br>            // double-width cell to fix character aspect ratio<br>            fputs(inside ? &quot;oo&quot; : &quot;  &quot;, stdout);<br>        }<br>        putchar(&#39;\n&#39;);<br>    }<br>    return 0;<br>}</pre><p>The C version is much more clear. The question is why do we need a language that look so terse? APL argues <strong>that smaller code where the entire logic which can fit within screen makes it easier to work with and less prone to mistake. </strong>How do I modify unknown code then? <strong>Well you don’t modify foreign code unless you know exactly how it works.</strong></p><blockquote>Donald Knuth: Programs are meant to be read by humans and only incidentally for computers to execute</blockquote><p>Not many people are fans of the APL family of languages. Famously Dijkstra agreed that APL is a “cult” in 1982 and criticised it</p><blockquote><strong>Dijkstra:</strong> I think that a major reason for shunning APL is that many people are repelled by the influence APL has on its devotees. They implement the prayer “Dear Lord, don’t let me become like them” by ignoring it.</blockquote><blockquote>Dijkstra: A typical characteristic of the APL devotee is, for instance, his closeness to an implementation of it.</blockquote><p>So beyond all the APL devotees and cults is this a practically language?</p><h3>The K programming language</h3><p>K is a proprietary array processing programming language from Arthur Whitney but before I get into K I would want to talk a bit about the Arthur Whitney’s Code Style</p><h4>Arthur Whitney Code Style</h4><p>The following is the Arthur Whitney Code Style version of the first program we saw. Excluding the macros the core logic is a single line of code.</p><pre>#include&lt;stdio.h&gt;<br>#include&lt;math.h&gt;<br>#define R(n,e) for(i=0;i&lt;n;++i){e;}<br>i;main(j){R(25,R(25,j=i,fputs(sqrt((i-12)*(i-12)+(j-12)*(j-12))&lt;11?&quot;oo&quot;:&quot;  &quot;,stdout))putchar(10))}</pre><p>The AW code style differs from pure Obfuscated C like the code you might find in IOCC (<a href="https://www.ioccc.org/">https://www.ioccc.org/</a>). It’s intension is to use shortcuts and tricks to squeeze all logic in one place.</p><p>Interestingly there is also AW style in Rust the following code is from a rust binding to K, note the macro usage and tight code style.</p><pre>macro_rules! mV {($a:expr,$b:expr)=&gt;{$a.iter().map(|x| $b(x)).collect::&lt;Vec&lt;String&gt;&gt;()}}<br>macro_rules! cV {($a:expr)=&gt;{$a.clone().as_mut_ptr()}}<br>macro_rules! Vc {($a:ty,$va:ident,$vb:ident)<br>    =&gt;{Vec::from_raw_parts($vb,NK($va)/size_of:: &lt;$a&gt;(),0)} }<br>macro_rules! Kmf {($name:ident,$ta:ty,$tb:ty,$a:ident,$($arg:expr),*)=&gt;{pub fn $name($a:$ta)-&gt;$tb{unsafe{raw::$name($($arg),*)}}}}<br>macro_rules! KVt {($name:ident,$t:ty)<br>    =&gt;{pub fn $name(a:K)-&gt;Vec&lt;$t&gt;{let L=NK(a);let mut O:Vec&lt;$t&gt;=Vec::with_capacity(L);<br>                                  unsafe { raw::$name(O.as_mut_ptr(),a);O.set_len(L); } O}}}<br>macro_rules! Cs {($a:expr)=&gt;{$a.as_ptr()as*const i8}}<br>macro_rules! Ns {($a:expr)=&gt;{(&amp;CString::new($a).expect(&quot;CStr&quot;)).as_ptr()}}<br>pub type K=raw::K;pub type V=raw::V;<br>fn NS(a:&amp;String)-&gt;String{format!(&quot;{}\0&quot;,a)}<br>fn i8C(a:i8)-&gt;char{a as u8 as char}<br>Kmf![Kc, char,K, a,a as i8]; Kmf![Ks, &amp;&#39;static str,K, a,String::from(a).as_mut_ptr()as*mut i8];<br>Kmf![Ki, i32,K, a,a]; Kmf![Kf, f64,K, a,a];<br>Kmf![KC, Vec&lt;char&gt;,K, a,cV![a]as*mut i8,a.len()]; Kmf![KS, Vec&lt;String&gt;,K, a,mV![a.clone(),NS].as_mut_ptr()as *mut*mut i8,a.len()];</pre><h4>Arthur Whitney’s K</h4><p>K is a proprietary language made by Arthur Whitney used in KX Systems and powers <a href="https://kx.com/products/kdb/">kdb+</a>, which is a remarkable real time analytics engine. So behind this terse language there is commercial success. Let’s look at K and understand what exactly is there in it.</p><h3>K at a glance</h3><p>The version of K which I will be taking about is ngn/k or growler/k which is an OpenSource implementation of the K9 standard.</p><p><a href="https://codeberg.org/growler/k">k</a></p><h4><strong>Basics in K</strong></h4><p>K is interpreted from right to left, and K verbs(operators) are heavily overloaded. Depending on the number of arguments the same operator can mean something different. A monadic version of verb uses a single argument and a dyadic version of a verb uses two arguments.</p><pre>Dyadic + is Sum eg) a + b<br>Monodic + is array transpose eg) +a</pre><p>Adverbs apply a given function over an array, they are similar to the map, scan, fold we see in functional programming.</p><p>That’s actually all there is to K, a couple of overloaded verbs, adverbs, array and a couple of special verbs for IO. The entire cheatsheet of K</p><pre>: SET      RETURN    :[c;t;f]     COND<br>+ add      flip<br>- subtract negate    &#39;  each|slide|bin<br>* multiply first     /  fold|join |dec|comment<br>% divide   sqrt      \  scan|split|enc|trace<br>! mod|dict enum|key  &#39;: eachprior<br>&amp; min|and  where     /: eachright<br>| max|or   reverse   \: eachleft<br>&lt; less     ascend<br>&gt; more     descend   /<br>= equal    group     multiline comment<br>~ match    not       \<br>, concat   enlist<br>^ without  null      0: lines i/o<br># reshape  length    1: bytes i/o<br>_ drop|cut floor<br>$ cast     string<br>? find|rnd uniq      ?[a;i;b]     splice<br>@ apply(1) type      @[x;i;[f;]y] amend<br>. apply(n) eval      .[x;i;[f;]y] drill<br>grammar:  E:E;e|e e:nve|te| t:n|v v:tA|V n:t[E]|(E)|{E}|N<br>limits:   8args 16locals 256globals 256bytecode 2048stack</pre><h4><strong>Understanding our first example</strong></h4><pre>`0:&quot;\n&quot;/,/&#39;(&quot;  &quot;;&quot;oo&quot;)@c&#39;(c:{x,|x})t{11&gt;%(x*x)+(y*y)}/:t:|!13;</pre><p>Which K looks daunting there is only one single rule to keep in mind.</p><blockquote><strong>Interpretation is done from right to left</strong></blockquote><p>Reading right to left</p><pre>▷ !13      - monadic ! is sequence, !13 is (0..12)<br>0 1 2 3 4 5 6 7 8 9 10 11 12<br><br>▷ |(!13)   - monadic | is reverse, so (12..0)<br>12 11 10 9 8 7 6 5 4 3 2 1 0<br><br>t:       - Assign the result to variable t<br><br>t       - Return the result to the rest of the expression<br><br>t{f}/:t  - Each right adverb, applying the function f, on t<br><br>{11&gt;%(x*x)+(y*y)} - Monodic % is sqrt, this is doing sqrt(x*x + y*y) &lt; 11<br>                     the equation of a square<br><br>The t{f}/:t create a single quadrant of the circle<br>▷ t{11&gt;%(x*x)+(y*y)}/:t:|!13<br>0 0 0 0 0 0 0 0 0 0 0 0 0<br>0 0 0 0 0 0 0 0 0 0 0 0 0<br>0 0 0 0 0 0 0 0 1 1 1 1 1<br>0 0 0 0 0 0 1 1 1 1 1 1 1<br>0 0 0 0 0 1 1 1 1 1 1 1 1<br>0 0 0 0 1 1 1 1 1 1 1 1 1<br>0 0 0 1 1 1 1 1 1 1 1 1 1<br>0 0 0 1 1 1 1 1 1 1 1 1 1<br>0 0 1 1 1 1 1 1 1 1 1 1 1<br>0 0 1 1 1 1 1 1 1 1 1 1 1<br>0 0 1 1 1 1 1 1 1 1 1 1 1<br>0 0 1 1 1 1 1 1 1 1 1 1 1<br>0 0 1 1 1 1 1 1 1 1 1 1 1<br><br>(c:{x,|x}) is stores a lambda {x,|x} in the variable c.<br>{x, |x} adds x to the reverse of x<br><br>This gives us 2 quadrants of the circle<br><br>▷ (c:{x,|x})t{11&gt;%(x*x)+(y*y)}/:t:|!13<br>0 0 0 0 0 0 0 0 0 0 0 0 0<br>0 0 0 0 0 0 0 0 0 0 0 0 0<br>0 0 0 0 0 0 0 0 1 1 1 1 1<br>0 0 0 0 0 0 1 1 1 1 1 1 1<br>0 0 0 0 0 1 1 1 1 1 1 1 1<br>0 0 0 0 1 1 1 1 1 1 1 1 1<br>0 0 0 1 1 1 1 1 1 1 1 1 1<br>0 0 0 1 1 1 1 1 1 1 1 1 1<br>0 0 1 1 1 1 1 1 1 1 1 1 1<br>0 0 1 1 1 1 1 1 1 1 1 1 1<br>0 0 1 1 1 1 1 1 1 1 1 1 1<br>0 0 1 1 1 1 1 1 1 1 1 1 1<br>0 0 1 1 1 1 1 1 1 1 1 1 1<br>0 0 1 1 1 1 1 1 1 1 1 1 1<br>0 0 1 1 1 1 1 1 1 1 1 1 1<br>0 0 1 1 1 1 1 1 1 1 1 1 1<br>0 0 1 1 1 1 1 1 1 1 1 1 1<br>0 0 1 1 1 1 1 1 1 1 1 1 1<br>0 0 0 1 1 1 1 1 1 1 1 1 1<br>0 0 0 1 1 1 1 1 1 1 1 1 1<br>0 0 0 0 1 1 1 1 1 1 1 1 1<br>0 0 0 0 0 1 1 1 1 1 1 1 1<br>0 0 0 0 0 0 1 1 1 1 1 1 1<br>0 0 0 0 0 0 0 0 1 1 1 1 1<br>0 0 0 0 0 0 0 0 0 0 0 0 0<br>0 0 0 0 0 0 0 0 0 0 0 0 0</pre><p>Finally,</p><pre>c&#39;Y is the for each adverb applying this gives us a complete circle<br><br>▷ c&#39;(c:{x,|x})t{11&gt;%(x*x)+(y*y)}/:t:|!13<br>0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0<br>0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0<br>0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0<br>0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0<br>0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0<br>0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0<br>0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0<br>0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0<br>0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0<br>0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0<br>0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0<br>0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0<br>0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0<br>0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0<br>0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0<br>0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0<br>0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0<br>0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0<br>0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0<br>0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0<br>0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0<br>0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0<br>0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0<br>0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0<br>0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0<br>0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0<br><br>The remaining code is for the pretty printing to the output stream<br><br>(&quot;  &quot;;&quot;oo&quot;)@X we use the @ indexing to choose &quot; &quot; for 0 and &quot;oo&quot; for 1<br><br>&quot;\n&quot;/,/&#39; is used to combine the array into a single line joined by a &quot;\n&quot;<br><br>`0: is a special verb to print to stdout<br><br>▷ `0:&quot;\n&quot;/,/&#39;(&quot;  &quot;;&quot;oo&quot;)@c&#39;(c:{x,|x})t{11&gt;%(x*x)+(y*y)}/:t:|!13;<br><br><br>                oooooooooooooooooooo<br>            oooooooooooooooooooooooooooo<br>          oooooooooooooooooooooooooooooooo<br>        oooooooooooooooooooooooooooooooooooo<br>      oooooooooooooooooooooooooooooooooooooooo<br>      oooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>    oooooooooooooooooooooooooooooooooooooooooooo<br>      oooooooooooooooooooooooooooooooooooooooo<br>      oooooooooooooooooooooooooooooooooooooooo<br>        oooooooooooooooooooooooooooooooooooo<br>          oooooooooooooooooooooooooooooooo<br>            oooooooooooooooooooooooooooo<br>                oooooooooooooooooooo</pre><p>And there you have it that’s how this one works.</p><h3>My Experience with K</h3><p>I have been using K from a couple of months now and I quite understand why APL is a “cult”. In the past I have always wanted to use an alternative language like Guile, OCaml, Haskell for my pet projects but nothing ever seemed to kickoff for me. K on the other hand is simple to learn and is quite productive surprisingly and instantly gratifying to work use. Well guess I’m part of the “cult” now.</p><h3>References</h3><ol><li><a href="https://www.jsoftware.com/papers/Dijkstra_Letter.htm">https://www.jsoftware.com/papers/Dijkstra_Letter.htm</a></li><li>Experiments which I have tried with K</li></ol><p><a href="https://github.com/Mark1626/Paraphernalia/tree/master/kexp">https://github.com/Mark1626/Paraphernalia/tree/master/kexp</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3e446006fc9e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[SQL Rewrite Stories— 2x Perf with a Projection after Aggregation]]></title>
            <link>https://medium.com/@nimalan854/sql-rewrite-stories-2x-perf-with-a-projection-after-aggregation-c40812d6e9b7?source=rss-571b24ff626d------2</link>
            <guid isPermaLink="false">https://medium.com/p/c40812d6e9b7</guid>
            <category><![CDATA[database]]></category>
            <category><![CDATA[query-optimization]]></category>
            <category><![CDATA[sql]]></category>
            <category><![CDATA[apache-datafusion]]></category>
            <dc:creator><![CDATA[Nimalan]]></dc:creator>
            <pubDate>Thu, 14 May 2026 01:31:43 GMT</pubDate>
            <atom:updated>2026-05-14T01:31:43.523Z</atom:updated>
            <content:encoded><![CDATA[<p>This series about query rewrites for OLAP SQL engines and in this article we look at a case of a simple query with a group-by and a projection expression</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/738/1*Y4vtsSrFlSwqq0-tnc9G-Q.png" /></figure><p>We will be looking at the following query on the Clickbench dataset, the SQL engine used is Datafusion (v53.0.0) and the query is run on a Macbook Pro M4. The initial runtime of this query is <strong>~12.1 s</strong> (sum of all elapsed compute across CPUs, wall clock time is 2.2s)</p><pre>SELECT CONCAT(<br>  CONCAT(<br>    CAST(hits.&quot;CounterID&quot; AS STRING),<br>    &#39;_&#39;<br>  ),<br>  CAST(hits.&quot;UserID&quot; AS STRING)<br>)<br>FROM hits<br>GROUP BY 1<br>ORDER BY calculation_1 ASC</pre><p>This query looks simple enough, a full table scan reading “CounterID” and “UserID”, the projection combines both the columns in the projection and uses this result “calculation_1” in the GROUP BY. The explain analyse of the query is as follows</p><pre>SortPreservingMergeExec: [calculation_1@0 ASC NULLS LAST], metrics=[output_rows=20.80 M, elapsed_compute=1.32s, output_bytes=466.2 GB, output_batches=2.54 K]<br>   SortExec: expr=[calculation_1@0 ASC NULLS LAST], preserve_partitioning=[true], metrics=[output_rows=20.80 M, elapsed_compute=1.20s, output_bytes=43.1 GB, output_batches=2.55 K, spill_count=0, spilled_bytes=0.0 B, spilled_rows=0]<br>     ProjectionExec: expr=[concat(concat(hits.CounterID,Utf8(&quot;_&quot;)),hits.UserID)@0 as calculation_1], metrics=[output_rows=20.80 M, elapsed_compute=1.05ms, output_bytes=172.0 GB, output_batches=2.55 K, expr_0_eval_time=635.38µs]<br>       AggregateExec: mode=FinalPartitioned, gby=[concat(concat(hits.CounterID,Utf8(&quot;_&quot;)),hits.UserID)@0 as concat(concat(hits.CounterID,Utf8(&quot;_&quot;)),hits.UserID)], aggr=[], metrics=[output_rows=20.80 M, elapsed_compute=1.48s, output_bytes=172.0 GB, output_batches=2.55 K, spill_count=0, spilled_bytes=0.0 B, spilled_rows=0, peak_mem_used=3.37 B, aggregate_arguments_time=14ns, aggregation_time=14ns, emitting_time=35.42µs, time_calculating_group_ids=1.48s]<br>         RepartitionExec: partitioning=Hash([concat(concat(hits.CounterID,Utf8(&quot;_&quot;)),hits.UserID)@0], 14), input_partitions=14, metrics=[output_rows=21.53 M, elapsed_compute=373.06ms, output_bytes=2.9 GB, output_batches=2.63 K, spill_count=0, spilled_bytes=0.0 B, spilled_rows=0, fetch_time=8.72s, repartition_time=137.86ms, send_time=525.17ms]<br>           AggregateExec: mode=Partial, gby=[concat(concat(CAST(CounterID@0 AS Utf8View), _), CAST(UserID@1 AS Utf8View)) as concat(concat(hits.CounterID,Utf8(&quot;_&quot;)),hits.UserID)], aggr=[], metrics=[output_rows=21.53 M, elapsed_compute=7.74s, output_bytes=184.1 GB, output_batches=2.63 K, spill_count=0, spilled_bytes=0.0 B, spilled_rows=0, skipped_aggregation_rows=0, peak_mem_used=1.84 B, aggregate_arguments_time=14ns, aggregation_time=14ns, emitting_time=52.62µs, time_calculating_group_ids=2.43s, reduction_factor=21.53% (21.53 M/100.00 M)]<br>             DataSourceExec: file_groups={14 groups: [[path/to/hits/hits_0.parquet:0..122446530, ...]}, projection=[CounterID, UserID], file_type=parquet, metrics=[output_rows=100.00 M, elapsed_compute=3.95ms, output_bytes=1145.7 MB, output_batches=12.31 K, files_ranges_pruned_statistics=113 total → 113 matched, row_groups_pruned_statistics=325 total → 325 matched, row_groups_pruned_bloom_filter=325 total → 325 matched, page_index_pages_pruned=0 total → 0 matched, page_index_rows_pruned=0 total → 0 matched, limit_pruned_row_groups=0 total → 0 matched, batches_split=0, bytes_scanned=270.5 M, file_open_errors=0, file_scan_errors=0, files_opened=113, files_processed=113, num_predicate_creation_errors=0, predicate_evaluation_errors=0, pushdown_rows_matched=0, pushdown_rows_pruned=0, predicate_cache_inner_records=0, predicate_cache_records=0, bloom_filter_eval_time=5.08µs, metadata_load_time=2.51ms, page_index_eval_time=226ns, row_pushdown_eval_time=226ns, statistics_eval_time=226ns, time_elapsed_opening=17.72ms, time_elapsed_processing=354.72ms, time_elapsed_scanning_total=8.69s, time_elapsed_scanning_until_data=225.51ms, output_rows_skew=0.3%, scan_efficiency_ratio=168.79% (270.5 M/160.3 M)]</pre><p>A lot of time ~7.7s is spent in the partial aggregation (AggregateExec mode=Partial), we have a good amount of reduction the output from (100M-&gt;20.8M) , output of partial aggregation is around <strong>184.1 GB</strong>.</p><p>Being a simple query it doesn’t seem as if there can be anything done to improve this, so what’s missing?</p><h3>Performance — The Cost of Shuffle</h3><p>In the above explain analyze in addition to the time taken in the partial aggregation, you can also see that in RepartitionExec the fetch_time is <strong>8.72s </strong>and the output of repartition exec is <strong>2.9 GB</strong>. The major cost is in computing the projection expression CONCAT(CONCAT(CAST(hits.&quot;CounterID&quot; as STRING), &#39;_&#39;), CAST(hits.&quot;UserID&quot; AS STRING)), and subsequently using it in the GROUP BY and shuffling it around.</p><h4>How can we reduce the cost of shuffle?</h4><p>Since this is a full table scan there isn’t much that can be done in the scan. However if we move the projection expression out of the GROUP BY the cost involved reduces as we are working on the columns directly and the expression is applying on the final result of the GROUP BY</p><p>Our query is of the form</p><pre>SELECT f(x, y)<br>  FROM table<br>  GROUP BY f(x, y)<br>  ORDER BY 1</pre><p>can be rewritten as</p><pre>SELECT f(x, y)<br>FROM (<br>    SELECT x, y<br>    GROUP BY x, y<br>) t<br>ORDER BY 1</pre><h3>Final Rewrite and Stats</h3><p>Rewriting our Clickbench query</p><pre>SELECT CONCAT(CONCAT(CAST(hits.&quot;CounterID&quot; AS STRING), &#39;_&#39;), CAST(hits.&quot;UserID&quot; AS STRING)) AS calculation_1<br>FROM (<br>    SELECT hits.&quot;CounterID&quot;, hits.&quot;UserID&quot;<br>    FROM hits<br>    GROUP BY hits.&quot;CounterID&quot;, hits.&quot;UserID&quot;<br>) t<br>ORDER BY calculation_1 ASC</pre><p><strong>Explain Analyse</strong></p><pre>SortPreservingMergeExec: [calculation_1@0 ASC NULLS LAST], metrics=[output_rows=20.80 M, elapsed_compute=1.30s, output_bytes=144.0 GB, output_batches=2.54 K]<br>   SortExec: expr=[calculation_1@0 ASC NULLS LAST], preserve_partitioning=[true], metrics=[output_rows=20.80 M, elapsed_compute=1.23s, output_bytes=16.1 GB, output_batches=2.55 K, spill_count=0, spilled_bytes=0.0 B, spilled_rows=0]<br>     ProjectionExec: expr=[concat(concat(CAST(CounterID@0 AS Utf8View), _), CAST(UserID@1 AS Utf8View)) as calculation_1], metrics=[output_rows=20.80 M, elapsed_compute=1.17s, output_bytes=1059.1 MB, output_batches=2.55 K, expr_0_eval_time=1.17s]<br>       AggregateExec: mode=FinalPartitioned, gby=[CounterID@0 as CounterID, UserID@1 as UserID], aggr=[], metrics=[output_rows=20.80 M, elapsed_compute=846.52ms, output_bytes=59.7 GB, output_batches=2.55 K, spill_count=0, spilled_bytes=0.0 B, spilled_rows=0, peak_mem_used=1.53 B, aggregate_arguments_time=14ns, aggregation_time=14ns, emitting_time=11.83µs, time_calculating_group_ids=844.10ms]<br>         RepartitionExec: partitioning=Hash([CounterID@0, UserID@1], 14), input_partitions=14, metrics=[output_rows=21.52 M, elapsed_compute=63.79ms, output_bytes=246.8 MB, output_batches=2.63 K, spill_count=0, spilled_bytes=0.0 B, spilled_rows=0, fetch_time=2.61s, repartition_time=103.84ms, send_time=402.32ms]<br>           AggregateExec: mode=Partial, gby=[CounterID@0 as CounterID, UserID@1 as UserID], aggr=[], metrics=[output_rows=21.52 M, elapsed_compute=1.68s, output_bytes=61.7 GB, output_batches=2.63 K, spill_count=0, spilled_bytes=0.0 B, spilled_rows=0, skipped_aggregation_rows=0, peak_mem_used=794.6 M, aggregate_arguments_time=14ns, aggregation_time=14ns, emitting_time=18.96µs, time_calculating_group_ids=1.68s, reduction_factor=21.52% (21.52 M/100.00 M)]<br>             DataSourceExec: file_groups={14 groups: [[path/to/hits/hits_0.parquet:0..122446530, ...], ...]}, projection=[CounterID, UserID], file_type=parquet, metrics=[output_rows=100.00 M, elapsed_compute=4.25ms, output_bytes=1145.7 MB, output_batches=12.31 K, files_ranges_pruned_statistics=113 total → 113 matched, row_groups_pruned_statistics=325 total → 325 matched, row_groups_pruned_bloom_filter=325 total → 325 matched, page_index_pages_pruned=0 total → 0 matched, page_index_rows_pruned=0 total → 0 matched, limit_pruned_row_groups=0 total → 0 matched, batches_split=0, bytes_scanned=270.5 M, file_open_errors=0, file_scan_errors=0, files_opened=113, files_processed=113, num_predicate_creation_errors=0, predicate_evaluation_errors=0, pushdown_rows_matched=0, pushdown_rows_pruned=0, predicate_cache_inner_records=0, predicate_cache_records=0, bloom_filter_eval_time=4.93µs, metadata_load_time=2.38ms, page_index_eval_time=226ns, row_pushdown_eval_time=226ns, statistics_eval_time=226ns, time_elapsed_opening=10.72ms, time_elapsed_processing=301.30ms, time_elapsed_scanning_total=2.60s, time_elapsed_scanning_until_data=260.00ms, output_rows_skew=1.36%, scan_efficiency_ratio=168.79% (270.5 M/160.3 M)]</pre><p>With the rewrite time elapsed in Partial Aggregate is now <strong>1.68s - 4x</strong> faster, and the output size is down to <strong>61.7 GB</strong> a <strong>3x</strong> reduction. In the RepartitionExec the fetch time is now <strong>2.6s - 3.3x faster</strong>, and the output size is down to <strong>246.8 MB a ~12x</strong> smaller shuffle. The projection expression is also run on fewer rows. Overall the cost of the shuffle and the projection expression has reduced. As a result of this the total elapsed compute is now <strong>~6.3s a</strong> <strong>2x improvement.</strong></p><h3>Will this always work?</h3><p>This rewrite works only when the projection expression f is injective (distinct input values output distinct output values) on the input and is also costly so this isn’t a general rewrite. However as seen by the stats this is a useful rewrite in reducing the cost of shuffle</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c40812d6e9b7" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Code Golf — Ikeda map]]></title>
            <link>https://medium.com/@nimalan854/code-golf-ikeda-map-a34466e81072?source=rss-571b24ff626d------2</link>
            <guid isPermaLink="false">https://medium.com/p/a34466e81072</guid>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[dwitter]]></category>
            <category><![CDATA[chaos-theory]]></category>
            <category><![CDATA[code-golf]]></category>
            <dc:creator><![CDATA[Nimalan]]></dc:creator>
            <pubDate>Fri, 08 May 2026 14:36:08 GMT</pubDate>
            <atom:updated>2026-05-08T14:36:08.767Z</atom:updated>
            <content:encoded><![CDATA[<h3>Code Golf — <strong>Ikeda map</strong></h3><p>Let’s golf a strange attractor within 140 characters of Javascript</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*v1RcG9zVK4pnCnDCITX1gQ.png" /><figcaption>Ikeda map, By Accelerometer — Own work, CC BY-SA 3.0, <a href="https://commons.wikimedia.org/w/index.php?curid=33235463">https://commons.wikimedia.org/w/index.php?curid=33235463</a></figcaption></figure><h3>Dwitter.net</h3><p><a href="https://www.dwitter.net/">dwitter.net</a> is a platform for JS code golf where you have 140 characters of Javascript and a canvas to use your creativity.</p><p>The rules of dwitter are</p><pre>u(t) is called 60 times per second.<br>t: Elapsed time in seconds.<br>S: Shorthand for Math.sin.<br>C: Shorthand for Math.cos.<br>T: Shorthand for Math.tan.<br>R: Function that generates rgba-strings, usage ex.: R(255, 255, 255, 0.5)<br>c: A 1920x1080 canvas.<br>x: A 2D context for that canvas.</pre><p>There are a lot of interesting things that can be done within 140 characters and one thing in particular which I was interested in are strange attractors. I was particularly fond of dwitter user <a href="https://www.dwitter.net/u/rodrigo.siqueira">rodrigo.siqueira</a>’s work which uses a lot of chaos theory. (He’s also on Medium <a href="https://medium.com/@rodrigo.siqueira">https://medium.com/@rodrigo.siqueira</a>).</p><p>I tried remixed existing ones, mostly I was unsuccessful but when it works it’s rewarding. I wanted to make one from scratch for a attractor no one had tried before which is when I found the ikeda map attractor.</p><h3>Ikeda Map</h3><p>The ikeda map is a strange attractor defined by the following equations</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*oFqpzOL94mgVO8R1IEwUMA.png" /><figcaption>Ikeda map equations— From Wikipedia</figcaption></figure><p>It can be created with the following Javascript code. This is <strong>846 characters!! </strong>and our target is <strong>140 characters, </strong>we need to roughly make the code <strong>6x smaller</strong></p><pre><br>const SCALE = 0.9;<br><br>function draw(x, y, depth) {<br>    // Compute rotation angle based on distance from origin<br>    const angle = 0.4 - 6 / (1 + x*x + y*y);<br>    <br>    if (depth &gt; 0) {<br>        // Recursive call: rotate (x,y) by `angle`, scale by 0.9, translate by +1 on x<br>        const newX = 1 + SCALE * (x * Math.cos(angle) - y * Math.sin(angle));<br>        const newY =     SCALE * (x * Math.sin(angle) + y * Math.cos(angle));<br>        <br>        draw(newX, newY, depth - 1);<br>        <br>        // Plot a single pixel, mapping world coords to screen (1920x1080 center)<br>        ctx.fillRect(960 + x * 400, 540 + y * 400, 1, 1);<br>    }<br>}<br><br>// Seed 1000 starting points around a circle of radius 5, iterate 80 deep each<br>for (let i = 0; i &lt; 1000; i++) {<br>    const seedX = Math.sin(i + t) * 5;<br>    const seedY = Math.cos(i + t) * 5;<br>    draw(seedX, seedY, 80);<br>}<br></pre><h3>Code Golfing</h3><p>Dwitter makes us skip the Math.cos and Math.sin with S and C, lets start there and also bring some basic golfing tricks</p><ol><li>0.9, 0.4 can be be just .9 and .4 this save the characters for 0</li><li>Instead of defining our core logic in ` function draw(X,Y,step)` we can make this a lambda f=(x,y,n)</li><li>We can save characters in the for loop for(let i=0; i&lt;1000; i++) with for(i=1e3;i--;) , the i-- serves as both the condition as well as the decrement</li><li>newX and newY can be inlined as it’s not used else where</li><li>instead of the if(depth&gt;0) we can just do a n&amp;&amp;</li></ol><p>I have intensionally kept some space in the call of f, but with this we have</p><pre>u=.9,f=(X,Y,n)=&gt;{T=.4-6/(1+X*X+Y*Y);n&amp;&amp;(<br>f(<br>    1+u*(X*C(T)-Y*S(T)),<br>    u*(X*S(T)+Y*C(T)),<br>    n-1<br>),x.fillRect(960+X*400,540+Y*400,1,1))}<br>for(i=1e3;i--;)f(S(i+t)*5,C(i+t)*5,80)</pre><p>Without the spaces this is <strong>161 characters, </strong>better than before but not quite there yet we need to trim 20 characters</p><h3>The last 20 characters</h3><pre>u=.9,f=(X,Y,n)=&gt;{T=.4-6/(1+X*X+Y*Y);n&amp;&amp;(f(1+u*(X*C(T)-Y*S(T)),u*(X*S(T)+Y*C(T)),n-1),x.fillRect(960+X*400,540+Y*400,1,1))}<br>for(i=1e3;i--;)f(S(i+t)*5,C(i+t)*5,80)</pre><p>The initial values of X, Y in f(S(i+t)*5,C(i+t)*5,80) can be f(i+t,i,90) without modifying the output that much bringing the count to <strong>149 characters</strong></p><pre>u=.9,f=(X,Y,n)=&gt;{T=.4-6/(1+X*X+Y*Y);n&amp;&amp;(f(1+u*(X*C(T)-Y*S(T)),u*(X*S(T)+Y*C(T)),n-1),x.fillRect(960+X*400,540+Y*400,1,1))}<br>for(i=1e3;i--;)f(i+t,i,90)</pre><p>Interestingly we don’t save characters with the u=.9 outside we endup using 7 characters including a , inlining it makes us use 4 character, so that’s down to <strong>146 characters</strong></p><p>Let’s get more aggressive</p><ol><li>We can get rid of the { and }</li><li>We do a n&amp;&amp; and later do a n-1 , instead a single n--&amp;&amp; can save a single char</li><li>I also ended up changing the initial X and Y again to just f(i,t,90)</li></ol><pre>f=(X,Y,n)=&gt;n--&amp;&amp;(T=.4-6/(1+X*X+Y*Y),f(1+.9*(X*C(T)-Y*S(T)),.9*(X*S(T)+Y*C(T)),n),x.fillRect(960+X*400,540+Y*400,1,1))<br>for(i=1e3;i--;)f(i,t,90)</pre><p>We are now at <strong>142 characters. </strong>There is another interesting rewrite, we can keep the declaration of f inside the for loop while having the initial call to it saving one character ie) From f=(X,Y,n)=&gt;...;for(;;)f(i,t,90) to for(;;f(i,t,90))f=(X,Y,n)=&gt;...</p><p>This puts us at <strong>141 characters. </strong>Finally I reused the same constant v=125 for different parts of the code to reach <strong>140 characters</strong></p><h3>The final version</h3><pre>v=125;for(i=v;i--;f(i,t,v))f=(X,Y,n)=&gt;n--&amp;&amp;(T=.4-6/(1+X*X+Y*Y),f(1+.9*(X*C(T)-Y*S(T)),.9*(X*S(T)+Y*C(T)),n),x.fillRect(3*v+X*v,3*v+Y*v,1,1))</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*so2wd1T5XDP4bfU_h0Ddrw.png" /><figcaption>Golfed Ikeda map</figcaption></figure><p><a href="https://www.dwitter.net/d/35346">ikeda map by mark1626 | Dwitter</a></p><h3>Final Thoughts</h3><p>After reaching the 140 character I realised there is one golfing idea which I missed. JS hoists variables even from function calls so T=123;S(T) is equal to S(T=123) , we save two characters by doing this</p><pre>v=125;for(i=v;i--;f(i,t,v))f=(X,Y,n)=&gt;n--&amp;&amp;(f(1+.9*(X*C(T=.4-6/(1+X*X+Y*Y))-Y*S(T)),.9*(X*S(T)+Y*C(T)),n),x.fillRect(3*v+X*v,3*v+Y*v,1,1))</pre><p>It also seems that removing u from the equation for Y doesn’t change the visual that much. Bringing the character count to 135 characters</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3qhxUNTHgcoPGPNH9KzdAQ.png" /><figcaption>Ikeda equation without u in equation for Y</figcaption></figure><pre>v=125;for(i=v;i--;f(i,t,v))f=(X,Y,n)=&gt;n--&amp;&amp;(f(1+.9*(X*C(T=.4-6/(1+X*X+Y*Y))-Y*S(T)),(X*S(T)+Y*C(T)),n),x.fillRect(3*v+X*v,3*v+Y*v,1,1))</pre><p>If your interested to learn more about golfing ideas like these, let me know in the comments.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a34466e81072" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Bringing SQL to GNU Recfiles with DataFusion]]></title>
            <link>https://medium.com/@nimalan854/bringing-sql-to-gnu-recfiles-with-datafusion-6e31a77e185e?source=rss-571b24ff626d------2</link>
            <guid isPermaLink="false">https://medium.com/p/6e31a77e185e</guid>
            <category><![CDATA[rust]]></category>
            <category><![CDATA[database]]></category>
            <category><![CDATA[apache-datafusion]]></category>
            <category><![CDATA[sql]]></category>
            <dc:creator><![CDATA[Nimalan]]></dc:creator>
            <pubDate>Thu, 30 Apr 2026 04:49:05 GMT</pubDate>
            <atom:updated>2026-04-30T04:49:05.504Z</atom:updated>
            <content:encoded><![CDATA[<p>GNU Recfiles are a human readable plain text database format. Can we query them with SQL?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*5-kNkSy4lvrne8JM" /><figcaption>Photo by <a href="https://unsplash.com/@jankolar?utm_source=medium&amp;utm_medium=referral">Jan Antonin Kolar</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h3>Human Readable Databases</h3><h4>Why are human readable databases needed?</h4><p>A human-readable database stores data in formats that people can directly read, edit, and understand without specialised tools. The commonly used CSV format is also a human readable data format. Human-readable data formats are useful for capturing information and analysis for small scale data that can fit within memory.</p><h3>GNU Recfiles</h3><p>GNU Recfiles are a plain text database format. A recfile holds a sequence of records, where each record is a block of Field: value lines, and records are separated by a blank line. Multi line fields are allowed by using a + at the start of a line.</p><pre>Title: Refactoring<br>Author: Martin Fowler<br>Year: 1999<br><br>Title: Domain-Driven Design<br>Author: Eric Evans<br>Year: 2003<br><br># A comment in a recfile<br>Title: The C Programming Language<br>Author: Kernighan<br>Author: Ritchie<br>Notes: Originally published 1978;<br>+ second edition added the ANSI C revisions.</pre><h4>CSV Import/Export</h4><pre># Export from Recfile to CSV<br>rec2csv books.rec &gt; books.csv<br><br># Import from CSV to Recfile<br>csv2rec books.csv &gt; books.rec</pre><p>Compared to a CSV, a recfile is a bit easier to edit given the one field per line and white space separation between records. There are also utilities to import/export Recfiles to/from CSV. Where Recfiles start to show their edge is when you start tags records with metadata. A record set is introduced by a %rec: line, which identifies the type of records present below the rec tag. In the following example the same file contains two record sets <strong><em>Book</em></strong> and <strong><em>Author</em></strong></p><pre>%rec: Book<br><br>Title: Refactoring<br>Author: Martin Fowler<br><br>%rec: Author<br><br>Name: Martin Fowler<br>Born: 1963</pre><p>The record sets metadata can also contain field type information, allowed values and defaults. All records added through the recutils tools are auto validated, `<strong><em>recfix — check</em></strong>` can be used on self edited files for validation.</p><pre>%rec: Book<br>%key: ISBN<br>%type: Year int<br>%type: ISBN regexp /^[0-9-]+$/<br>%type: Status enum new used reading retired<br>%type: InPrint bool<br><br>Title: Refactoring<br>Year: 1999<br>ISBN: 978-0201485677<br>Status: reading<br>InPrint: yes</pre><h3>Recutils</h3><p>The GNU Recutils are a set of tools for working on Recfiles. We’ll see a quick summary about them before moving on to SQL.</p><h4>recins</h4><p>Inserts a record into a file, the fields are validated before being inserted into a file</p><pre>  # Append one record<br>  recins -t Book \<br>    -f Title -v &quot;Clean Code&quot; \<br>    -f Author -v &quot;Robert Martin&quot; \<br>    -f Year -v 2008 \<br>    books.rec</pre><h4>recfix</h4><p>For records manually edited recfix can be used to fix missing fields in them</p><pre>recfix --check books.rec        # validate against the descriptor<br>recfix --sort books.rec         # sort per %sort:<br>recfix --auto books.rec         # fill in %auto fields</pre><h4>recsel</h4><p>Records can be selected with recsel, which has a <strong>selection expression </strong>DSL to define expression to filter records. This is a very rich and powerful feature in recutils allow for structure querying of data in a recfile</p><pre># All Book records<br>recsel -t Book books.rec<br><br># Filter with a &quot;selection expression&quot; (sex)<br>recsel -t Book -e &#39;Year &gt; 2000&#39; books.rec<br><br># Project specific fields, like SQL SELECT<br>recsel -t Book -e &#39;Year &gt; 2000&#39; -p &#39;Title,Author&#39; books.rec<br><br># Count matches<br>recsel -t Book -e &#39;Author ~ &quot;Martin&quot;&#39; -c books.rec</pre><h4>SQL like capabilities of Selection Expressions</h4><p>Recfiles can have primary keys to uniquely identify records as well as foreign keys to lookup other records in a different record set. In the following example both record sets <strong><em>Author</em></strong> and <strong><em>Book</em></strong> have their own primary keys. Book references Author with a foreign key AuthorId which points to a record in Author.</p><pre>%rec: Author<br>%key: Id<br>%type: Id int<br>%auto: Id<br>%mandatory: Name<br><br>Id: 1<br>Name: Martin Fowler<br><br>Id: 2<br>Name: Eric Evans<br><br>%rec: Book<br>%key: Id<br>%type: Id int<br>%auto: Id<br>%type: AuthorId rec Author<br>%mandatory: Title AuthorId<br><br>Id: 1<br>Title: Refactoring<br>AuthorId: 1<br>Year: 1999<br><br>Id: 2<br>Title: Domain-Driven Design<br>AuthorId: 2<br>Year: 2003<br><br>Id: 3<br>Title: Patterns of Enterprise Application Architecture<br>AuthorId: 1<br>Year: 2002</pre><p>This foreign key can be used to join records when selecting them. Each -j can follow one foreign key and can be chained to fetch different records sets. However -j only follows one jump so no transitive jumps eg) Book -&gt; Author -&gt; &lt;Other&gt; is possible.</p><pre>&gt; recsel -t Book -j AuthorId books.rec test1.rec<br>Id: 1<br>Title: Refactoring<br>Year: 1999<br>AuthorId_Id: 1<br>AuthorId_Name: Martin Fowler<br><br>Id: 2<br>Title: Domain-Driven Design<br>Year: 2003<br>AuthorId_Id: 2<br>AuthorId_Name: Eric Evans<br><br>Id: 3<br>Title: Patterns of Enterprise Application Architecture<br>Year: 2002<br>AuthorId_Id: 1<br>AuthorId_Name: Martin Fowler</pre><p>While recutils comes with structured querying the syntax of recsel is quite different from common SQL. Further things like aggregations are not supported. Something that I wanted to experiment was to see if I can create an SQL query layer for recutils which still uses the Selection Expression API behind the scenes.</p><h3>On a quest to query Recfiles with SQL</h3><h4>Apache DataFusion</h4><p>Apache DataFusion is an extensible query engine written in Rust that uses Apache Arrow as its in-memory format. If we expose a Recfile as a table in DataFusion, we can leverage Datafusion’s existing parser, query optimiser, execution primitives and query recfiles directly with SQL.</p><h4>Rust FFI</h4><p>To begin with recutils is in C while DataFusion is in Rust, so we need FFI bindings tolibrec. We can use the <a href="https://rust-lang.github.io/rust-bindgen/">bindgen</a> crate to create the Rust FFI bindings. Next, since we are making FFI calls this introduces <strong>unsafe code</strong>, we need proper abstractions so that unsafe blocks are exposed outside unnecessarily.</p><pre><br>unsafe extern &quot;C&quot; {<br>    fn free(ptr: *mut c_void);<br>}<br><br>// Wrapper struct to limit the exposure of unsafe<br>pub struct Db {<br>    ptr: rec_db_t,<br>}<br><br>impl Db {<br>    pub fn parse_str(text: &amp;str) -&gt; Result&lt;Self, Error&gt; {<br>        let c_text = cstring(text, &quot;rec source&quot;)?;<br>        unsafe {<br>            let parser = rec_parser_new_str(c_text.as_ptr(), c&quot;input&quot;.as_ptr());<br>            if parser.is_null() {<br>                return Err(Error::new(&quot;rec_parser_new_str returned NULL&quot;));<br>            }<br>            let mut db: rec_db_t = ptr::null_mut();<br>            let ok = rec_parse_db(parser, &amp;mut db);<br>            rec_parser_destroy(parser);<br>            if !ok || db.is_null() {<br>                if !db.is_null() {<br>                    rec_db_destroy(db);<br>                }<br>                return Err(Error::new(&quot;rec_parse_db failed&quot;));<br>            }<br>            Ok(Db { ptr: db })<br>        }<br>    }<br>}<br><br>impl Drop for Db {<br>    fn drop(&amp;mut self) {<br>        unsafe { rec_db_destroy(self.ptr) }<br>    }<br>}</pre><p>We introduce wrappers for all existing types in recutils so that when we use them later we wouldn’t have to worry about managing unsafe blocks and the code is much cleaner the new wrapper. The following is an example to count the total number of records in a recfile using the wrapper.</p><pre>// Example using the wrapped bindings to count the total number of <br>// records in a recfile<br>// No unsafe blocks used<br>use std::fs;<br><br>use recutils_rs::Db;<br><br>fn main() {<br>    let path = std::env::args().nth(1).expect(&quot;usage: count_records &lt;file.rec&gt;&quot;);<br>    let text = fs::read_to_string(&amp;path).expect(&quot;read file&quot;);<br><br>    let mut db = Db::parse_str(&amp;text).expect(&quot;parse&quot;);<br>    let n_rsets = db.num_rsets();<br>    let total: usize = (0..n_rsets)<br>        .map(|i| db.rset_at(i).expect(&quot;rset by index&quot;).num_records())<br>        .sum();<br>    println!(&quot;{}: {} records across {} record set(s)&quot;, path, total, n_rsets);<br>}</pre><h4>Recfiles -&gt; Arrow Record Batches</h4><p>At the heart of Datafusion is Apache Arrow, to expose our recfiles as tables we need to be able to represent them in Arrow RecordBatches. This is relatively easy for recfiles as the fields are already typed. We would have to map recfile types to arrow types and use that to create the arrow schema. With the schema recfiles read can be made into Arrow RecordBatches.</p><pre>pub fn map_rec_type(t: &amp;str) -&gt; DataType {<br>    match t.split_whitespace().next().unwrap_or(&quot;&quot;) {<br>        &quot;int&quot; | &quot;range&quot; =&gt; DataType::Int64,<br>        &quot;real&quot; =&gt; DataType::Float64,<br>        &quot;bool&quot; =&gt; DataType::Boolean,<br>        _ =&gt; DataType::Utf8,<br>    }<br>}<br><br>pub fn rec_to_record_batch(<br>    db: &amp;mut Db,<br>    record_type: &amp;str,<br>) -&gt; Result&lt;(Arc&lt;Schema&gt;, RecordBatch), Box&lt;dyn std::error::Error&gt;&gt; {<br>    // Fetch type information of record set from librec<br>    let declared_types = get_field_types(db, record_type)?;<br><br>    // Fetch data<br>    let (column_order, rows) = collect_rows(db, record_type)?;<br>    <br>    // Create Arrow schema<br>    let schema = build_schema(&amp;column_order, &amp;declared_types);<br>    <br>    // Create record batch<br>    let columns = build_columns(&amp;schema, &amp;rows);<br>    let batch = RecordBatch::try_new(Arc::clone(&amp;schema), columns)?;<br>    Ok((schema, batch))<br>}</pre><h4>Datafusion TableProvider</h4><p>A TableProvider represents a source of data and produces an execution plan when queried. In our case where we already have the Recfile as Arrow RecordBatches, Datafusion recommends starting with a MemTable. A MemTable is an in memory datasource, we need the schema that we created earlier for our MemTable</p><pre>async fn scan(<br>    &amp;self,<br>    state: &amp;dyn Session,<br>    projection: Option&lt;&amp;Vec&lt;usize&gt;&gt;,<br>    filters: &amp;[Expr],<br>    limit: Option&lt;usize&gt;,<br>) -&gt; DfResult&lt;Arc&lt;dyn ExecutionPlan&gt;&gt; {<br>    let batches = self.batches_for(filters)?;<br>    let mem = MemTable::try_new(Arc::clone(&amp;self.schema), vec![batches])?;<br>    mem.scan(state, projection, filters, limit).await<br>}</pre><p>Now all that’s needed is to register this TableProvider in a DataFusion session to be able to query recfiles with SQL</p><pre>let providers: Vec&lt;TableProvider&gt; = RecTableProvider::open_all(&amp;opts.input)?;<br><br>let ctx = SessionContext::new_with_config(<br>    SessionConfig::new().with_information_schema(true),<br>);    <br><br>for (name, provider) in providers {<br>    ctx.register_table(name.as_str(), Arc::new(provider))?;<br>}</pre><h4>Filter Pushdown</h4><p>Filter pushdown is the process of passing the filter information to the Datasource so that when reading from disk, data not matching the filters can be skipped. Implementing filter pushdown is not strictly necessary and in this case as librec holds the data in-memory before applying the Selection Expression so there may not be any performance benefits in this case. But for the sake of completion let’s see how we can pushdown the SQL filters into librec.</p><p>The function supports_filters_pushdown has to be implemented in the TableProvider trait to indicate if filters can be pushed down. Since not all SQL filter expressions can be made into Selection Expression we mark the pushdown type as Exact when every filter maps down to Selection Expression, as Inexact when there is a partial match and Unsupported when there is no match.</p><pre>fn supports_filters_pushdown(<br>    &amp;self,<br>    filters: &amp;[&amp;Expr],<br>) -&gt; DfResult&lt;Vec&lt;TableProviderFilterPushDown&gt;&gt; {<br>    Ok(filters<br>        .iter()<br>        .map(|f| match pushdown_for(f, self.schema.as_ref()) {<br>            Some((_, true)) =&gt; TableProviderFilterPushDown::Exact,<br>            Some((_, false)) =&gt; TableProviderFilterPushDown::Inexact,<br>            None =&gt; TableProviderFilterPushDown::Unsupported,<br>        })<br>        .collect())<br>}<br><br>// Function to convert DataFusion&#39;s expression to Selection expression<br>fn expr_to_selection_expression(expr: &amp;Expr, schema: &amp;Schema) -&gt; Option&lt;String&gt; {<br>    match expr {<br>        Expr::BinaryExpr(BinaryExpr { left, op, right }) =&gt; match op {<br>            Operator::And =&gt; {<br>                let l = expr_to_selection_expression(left, schema)?;<br>                let r = expr_to_selection_expression(right, schema)?;<br>                Some(format!(&quot;({l}) &amp;&amp; ({r})&quot;))<br>            }<br>            Operator::Or =&gt; {<br>                let l = expr_to_selection_expression(left, schema)?;<br>                let r = expr_to_selection_expression(right, schema)?;<br>                Some(format!(&quot;({l}) || ({r})&quot;))<br>            }<br>            Operator::Eq<br>            | Operator::NotEq<br>            | Operator::Lt<br>            | Operator::LtEq<br>            | Operator::Gt<br>            | Operator::GtEq =&gt; binary_compare(left, *op, right, schema),<br>            _ =&gt; None,<br>        },<br>        Expr::Not(inner) =&gt; {<br>            let s = expr_to_selection_expression(inner, schema)?;<br>            Some(format!(&quot;!({s})&quot;))<br>        }<br>        _ =&gt; None,<br>    }<br>}</pre><h3>Putting it all together — recsql</h3><pre>&gt; recsql library.rec -q &#39;SHOW TABLES&#39;<br>+---------------+--------------------+-------------+------------+<br>| table_catalog | table_schema       | table_name  | table_type |<br>+---------------+--------------------+-------------+------------+<br>| datafusion    | public             | book        | BASE TABLE |<br>| datafusion    | public             | loan        | BASE TABLE |<br>| datafusion    | public             | author      | BASE TABLE |<br>+---------------+--------------------+-------------+------------+<br><br><br>&gt; recsql library.rec -q &#39;<br>    SELECT b.&quot;Title&quot;, b.&quot;Year&quot;, a.&quot;Country&quot;<br>    FROM book b<br>    JOIN author a ON b.&quot;Author&quot; = a.&quot;Name&quot;<br>    ORDER BY b.&quot;Year&quot;&#39;<br>+-----------------------------+------+---------+<br>| Title                       | Year | Country |<br>+-----------------------------+------+---------+<br>| TAOCP Vol 1                 | 1968 | USA     |<br>| TAOCP Vol 2                 | 1969 | USA     |<br>| The C Programming Language  | 1978 | Canada  |<br>| SICP                        | 1985 | USA     |<br>| Compilers                   | 1986 | Canada  |<br>| The Practice of Programming | 1999 | Canada  |<br>+-----------------------------+------+---------+</pre><p>Datafusion unlocks us to do thinks which were previously not possible with recsel like Aggregation and non inner joins (Left, Anti, Semi, etc) and much more</p><pre># Aggregations<br>&gt; recsql library.rec -q &#39;<br>    SELECT a.&quot;Country&quot;,<br>           COUNT(*) AS books,<br>           AVG(b.&quot;Pages&quot;)::INT AS avg_pages<br>    FROM book b<br>    JOIN author a ON b.&quot;Author&quot; = a.&quot;Name&quot;<br>    GROUP BY a.&quot;Country&quot;<br>    ORDER BY books DESC&#39;<br>+---------+-------+-----------+<br>| Country | books | avg_pages |<br>+---------+-------+-----------+<br>| Canada  | 3     | 501       |<br>| USA     | 3     | 665       |<br>+---------+-------+-----------+<br><br># Left Joins<br>&gt; recsql library.rec -q &#39;<br>    SELECT b.&quot;Title&quot;, COUNT(l.&quot;Borrower&quot;) AS times_borrowed<br>    FROM book b<br>    LEFT JOIN loan l ON b.&quot;Title&quot; = l.&quot;Book&quot;<br>    GROUP BY b.&quot;Title&quot;<br>    ORDER BY times_borrowed DESC, b.&quot;Title&quot;&#39;<br>+-----------------------------+----------------+<br>| Title                       | times_borrowed |<br>+-----------------------------+----------------+<br>| SICP                        | 2              |<br>| The C Programming Language  | 2              |<br>| Compilers                   | 1              |<br>| TAOCP Vol 1                 | 1              |<br>| TAOCP Vol 2                 | 0              |<br>| The Practice of Programming | 0              |<br>+-----------------------------+----------------+</pre><h3>Summary</h3><p>Recfiles are a decent alternative to CSVs with structuring and field typing, they can also be exported to CSVs. DataFusion is a powerful and extensible query engine and allows you to connect to any datasource of your choice. By making our datasource Arrow compatible we were able to treat Recfiles as tables in DataFusion which allows to query Recfiles with all the SQL features DataFusion provides</p><h4>Further Reading</h4><ol><li>Source code of recsql and recutils-rs <a href="https://github.com/Mark1626/recutil-tools">https://github.com/Mark1626/recutil-tools</a></li><li>GNU Recutils — <a href="https://www.gnu.org/software/recutils/">https://www.gnu.org/software/recutils/</a></li><li>DataFusion TableProviders — <a href="https://datafusion.apache.org/library-user-guide/custom-table-providers.html">https://datafusion.apache.org/library-user-guide/custom-table-providers.html</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6e31a77e185e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[NewType Pattern and Dependent Type Theory]]></title>
            <link>https://medium.com/@nimalan854/newtype-pattern-and-dependent-type-theory-20432e9b6283?source=rss-571b24ff626d------2</link>
            <guid isPermaLink="false">https://medium.com/p/20432e9b6283</guid>
            <category><![CDATA[rust]]></category>
            <category><![CDATA[functional-programming]]></category>
            <dc:creator><![CDATA[Nimalan]]></dc:creator>
            <pubDate>Tue, 29 Jul 2025 11:31:54 GMT</pubDate>
            <atom:updated>2025-07-29T11:31:54.004Z</atom:updated>
            <content:encoded><![CDATA[<p>The NewType pattern in Rust is something that just clicks and makes you wonder why we haven’t been doing this before. What if I told you, that magic behind this pattern is it’s roots in Type Theory.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*lM_Nwm67cQki2a0t" /><figcaption>Photo by <a href="https://unsplash.com/@brett_jordan?utm_source=medium&amp;utm_medium=referral">Brett Jordan</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h3>The NewType pattern</h3><p>Let’s say I want to model my user data in a struct like so</p><pre>#[derive(Debug)]<br>pub struct User {<br>  username: String,<br>  password: String,<br>}</pre><p>All the fields are of type String, does that mean that all these values are the same? The fields password is confidential, deriving the debug trait here would mean that logging the User struct would reveal the user’s password.</p><p>This is where the NewType pattern helps, by creating new types for the username and password we <em>“refine” </em>how these types are to be handled. This could be though adding validations or in our case by adding a custom Debug trait implementation to mask the PII.</p><pre>struct UserName(String);<br>struct Password(String);<br><br>impl std::fmt::Debug for Password {<br>  fn fmt(&amp;self, f: &amp;mut std::fmt::Formatter&lt;&#39;_&gt;) -&gt; std::fmt::Result {<br>    f.debug_struct(&quot;Password&quot;)<br>      .field(&quot;secret_key&quot;, &amp;&quot;******&quot;)<br>  }<br>}<br><br>#[derive(Debug)]<br>pub struct User {<br>  username: UserName,<br>  password: Password,<br>}</pre><p>For the PII scenario there are crates for doing this, for example the redact crate where you use a wrapper Secret to define which fields are PII.</p><pre>use redact::Secret;<br><br>#[derive(Debug)]<br>struct User {<br>    password: Secret&lt;String&gt;,<br>    username: String,<br>}</pre><p>Well why does this click? I like to say that good ideas always stem from mathematics. The <em>“refined”</em> types from the NewType pattern can be seen as a simpler form of Dependent Type Theory</p><h3>Dependent Type Theory</h3><p>A dependent type is a type defined by the underlying value inside it</p><p>For example, email is a dependent type where by having a parsing logic in the constructor we restrict/refine the underlying value</p><pre>struct Email(String);<br><br>impl Email {<br>  fn new(raw: String) {<br>    // Parsing logic, will make it so that only valid emails can be used<br>  }<br>}</pre><p>The struct User is a dependent type, and certain constraints are added on the Debug logic for this by the Secret</p><pre>#[derive(Debug)]<br>struct User {<br> password: Secret&lt;String&gt;,<br> username: String,<br>}</pre><p>These examples are a small subset of dependent types. You can use dependent type to create functions where the return type is dependent on the argument passed in, for example</p><pre>// Scala 3<br>// Example from https://wheaties.github.io/Presentations/Scala-Dep-Types/dependent-types.html<br>trait DepValue{<br>  type V<br>  val value: V<br>}<br><br>def magic(that: DepValue): that.V = that.value</pre><p>Or create functions that accept only values that satisfy a certain condition. In the following example at compile time we can get an error if the argument to the function f is not even.</p><pre>// Scala 2<br>// Example from stackoverflow<br>// https://stackoverflow.com/questions/9338709/what-is-dependent-typing<br>case class Integer(v: Int) {<br>  object IsEven { require(v % 2 == 0) }<br>  object IsOdd { require(v % 2 != 0) }<br>}<br><br>def f(n: Integer)(implicit proof: n.IsEven.type) =  { <br>  // do something with n safe in the knowledge it is even<br>}<br><br>val `42` = Integer(42)<br>implicit val proof42IsEven = `42`.IsEven<br><br>val `1` = Integer(1)<br>implicit val proof1IsOdd = `1`.IsOdd<br><br>f(`42`) // OK<br>f(`1`)  // compile-time error</pre><p>Hmm, in the last example we were passing in proofs for our arguments. A program made with dependent types can be used as a mathematical proof. This relationship between programs and mathematical proofs is known as the Curry-Howard correspondence. There is a set of languages that Lean, Agda, Idris, Rocq which do formal reasoning using dependent types.</p><p>This sort of formal reason with types can also be used to for logical puzzles. I wrote an article in the past where I used Agda to solve logical puzzles</p><pre>// You meet two inhabitants: Zoey and Mel. Zoey tells you that Mel <br>// is a knave. Mel says, “Neither Zoey nor I are knaves<br>//<br>// Types representing Knights and Knaves<br>data Person : Set where<br>  knight : Person<br>  knave  : Person<br><br>says : Person → Set → Set<br>says knight p = p<br>says knave  p = ¬ p<br><br>// The type Solution represents this puzzle<br>data Solution : Set where<br>    soln : (Zoey : Person) → (Mel : Person) →       -- Two people Zoey Mel<br>      (says Zoey (Mel ≡ knave)) →                   -- Zoey&#39;s statement<br>      (says Mel ((Zoey ≢ knave) × (Mel ≢ knave))) → -- Mel&#39;s statement<br>      Solution<br><br>// And this is the solution<br>¬-elim : {A : Set} → ¬ A → A → ⊥<br>¬-elim ¬x x = ¬x x<br><br>// Proving Zoey is a Knight and Mel is a Knave by creating a function <br>// of that type<br>answer : Solution<br>answer = soln knight knave<br>  refl<br>  λ{ ⟨ knv≢kni , knv≢knv ⟩ → ¬-elim knv≢knv refl}</pre><p><a href="https://medium.com/e4r/solving-logic-puzzles-with-dependently-typed-functional-programming-675959eef957">Solving Logic Puzzles with Dependently Typed Functional Programming</a></p><h3>Conclusion</h3><p>I started with Rust’s NewType pattern and went into a rabbit hole talking about dependent types, formal reasoning with dependent type and solving logical puzzles. In conclusion ideas such as theNewType pattern bounded with strong fundamentals are always solid to use and are interesting to explore.</p><h3>Reading</h3><ol><li><a href="https://doc.rust-lang.org/rust-by-example/generics/new_types.html">https://doc.rust-lang.org/rust-by-example/generics/new_types.html</a></li><li><a href="https://www.worthe-it.co.za/blog/2020-10-31-newtype-pattern-in-rust.html">https://www.worthe-it.co.za/blog/2020-10-31-newtype-pattern-in-rust.html</a></li><li><a href="https://en.wikipedia.org/wiki/Dependent_type">https://en.wikipedia.org/wiki/Dependent_type</a></li><li><a href="https://stackoverflow.com/questions/9338709/what-is-dependent-typing">https://stackoverflow.com/questions/9338709/what-is-dependent-typing</a></li><li><a href="https://wheaties.github.io/Presentations/Scala-Dep-Types/dependent-types.html">https://wheaties.github.io/Presentations/Scala-Dep-Types/dependent-types.html</a></li><li><a href="https://cstheory.stackexchange.com/questions/53728/isnt-it-misleading-for-scala-3-to-claim-it-has-dependent-function-types">https://cstheory.stackexchange.com/questions/53728/isnt-it-misleading-for-scala-3-to-claim-it-has-dependent-function-types</a></li><li><a href="https://medium.com/e4r/solving-logic-puzzles-with-dependently-typed-functional-programming-675959eef957">https://medium.com/e4r/solving-logic-puzzles-with-dependently-typed-functional-programming-675959eef957</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=20432e9b6283" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solving Logic Puzzles with Dependently Typed Functional Programming]]></title>
            <link>https://medium.com/e4r/solving-logic-puzzles-with-dependently-typed-functional-programming-675959eef957?source=rss-571b24ff626d------2</link>
            <guid isPermaLink="false">https://medium.com/p/675959eef957</guid>
            <category><![CDATA[type-theory]]></category>
            <category><![CDATA[logic]]></category>
            <category><![CDATA[functional-programming]]></category>
            <category><![CDATA[agda]]></category>
            <dc:creator><![CDATA[Nimalan]]></dc:creator>
            <pubDate>Fri, 15 Mar 2024 04:21:21 GMT</pubDate>
            <atom:updated>2024-03-15T13:51:26.289Z</atom:updated>
            <content:encoded><![CDATA[<p>Agda is a dependently typed functional programming language and a proof assistant. Agda uses the <a href="https://ncatlab.org/nlab/show/proofs+as+programs">Programs as Proof</a> paradigm in which logical propositions are defined as types, and a proof for a given proposition is a function of the same type signature. The relationship between programs and mathematical proofs between is known as the <a href="https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence">Curry-Howard correspondence</a>.</p><h3>Dependently Typed Functional Programming</h3><p>Puzzles are essentials logical propositions and solving a puzzle would involve proving that a solution is valid. Before we get into how this can be applied, let’s first understand what “logic propositions as types” and “programs as proof” mean. We also need types that represent logical reasoning. If you know a bit about Agda then you can skip to the next section.</p><h4>Agda</h4><p>Agda has a similar syntax to Haskell. In the following example we are defining the rules to create natural numbers. Base case, zero is a natural number. If m is natural number then it’s successor is also a natural number.</p><blockquote>data is similar to a Haskell type-class.</blockquote><p>For creating a function to add two natural numbers we pattern match and define each case separately. Zero plus n is n, successor of m plus n is equal to successor of m plus n (this will inductively become zero plus n).</p><pre>data Nat : Set where<br>  zero : Nat<br>  suc  : Nat → Nat<br><br>one   = (suc zero)<br>two   = (suc one) -- or (suc (suc zero))<br>three = (suc two) -- or (suc (suc (suc zero)))<br><br>add : Nat → Nat → Nat<br>add zero    n = n<br>add (suc m) n = suc (add m n)</pre><p>Agda has unicode support, and typically you will find most Agda code written in unicode. The same example but with unicode.</p><blockquote>The emacs-mode for Agda comes with a convenient way to enter unicode, and a way to check how what the character is</blockquote><pre>data ℕ : Set where<br>  zero : ℕ<br>  suc  : ℕ → ℕ<br><br>_+_ : ℕ → ℕ → ℕ<br>zero    + n = n<br>(suc m) + n = suc (m + n)</pre><h4>Equality</h4><blockquote>These are quite deep topics, please refer to the book Programming Language Foundations in Agda [2] for a more detailed explanation</blockquote><p>An operator equality can be defined as follow. For a type A and x of type A we say that x is equal to itself. This is a reflexive relation refl .</p><pre>data _≡_ {A : Set} (x : A) : A → Set where<br>  refl : x ≡ x</pre><p>With this be can create our first proof, let’s prove 1 + 2 ≡ 3. Our proof is a type correct function defined in the type 1 + 2 ≡ 3 . There can be several different functions/proof for a given proposition.</p><p>We can prove 1 + 2 ≡ 3, either with a chain of equality statements or prove it to be a reflexive relation.</p><pre>proof₁ : one + two ≡ three<br>proof₁ =<br>  begin<br>    (suc zero) + two<br>  ≡⟨⟩<br>    (suc (zero + two))<br>  ≡⟨⟩<br>    (suc two)<br>  ≡⟨⟩<br>    (suc (suc (suc zero)))<br>  ≡⟨⟩<br>    three<br>  ∎<br><br>proof₂ : one + two ≡ three<br>proof₂ = refl</pre><h4>Negation</h4><p>Agda relies on Intuitionistic or Constructive logic. In Intuitionistic we say that if assuming <strong>A</strong> is absurd then <strong>¬A </strong>is valid.</p><pre>-- Empty or An absurdity<br>data ⊥ : Set where<br><br>-- Negation<br>¬_ : Set → Set<br>¬ A = A → ⊥</pre><p>A logical statement: “The glass is not empty” is intuitionistic logic means that a proof for the statement “The glass is empty” is absurd.</p><p>We can say</p><pre>impossible₁ : ¬ (zero ≡ 2)<br>impossible₁ ()<br><br><br>impossible₂ : (zero ≢ 1)<br>impossible₂ ()</pre><h4>Connectives</h4><p>Connectives are used to connect logical formula’s together. Given two propositions <strong>A</strong> and <strong>B</strong>, a <strong>conjuction<em> </em>A × B </strong>holds if both A holds and B holds. <strong>A × B </strong>is refered to as the <em>cartesian product</em> in set theory.</p><p>We can represent the statement “A’s cost is greater than 10 and less than 50” as</p><pre>statement : (cost &gt; 10) × (cost &lt; 50)</pre><p>Given two propositions <strong>A</strong> and <strong>B</strong>, a disjunction <strong>A ⊎ B </strong>holds if either A holds or B holds. In set theory <strong>A ⊎ B </strong>is called the <em>disjoint union</em>.</p><p>We can represent the statement “Either A is a knight or B is a knight” as</p><pre>statement : (A ≡ knight) ⊎ (B ≡ knight)</pre><p>With these we have some essentials to approach logical puzzles</p><h3>Knights and Knaves</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*lMygTlKWV0TN8xcj" /><figcaption>Photo by <a href="https://unsplash.com/@thatbangaloreanguy?utm_source=medium&amp;utm_medium=referral">Karthik B K</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>For <strong><em>“Knights and Knaves”</em></strong><em> </em>the primary information is</p><blockquote>A very special island is inhabited only by knights and knaves. Knights always tell the truth, and knaves always lie.</blockquote><p>First create a datatype to represent a Person. A person can be either a knight or a knave. Now, we create a function says to describe a conversation. Any proposition said by a knight is valid, any proposition said by a knave is negated.</p><pre>data Person : Set where<br>  knight : Person<br>  knave  : Person<br><br>says : Person → Set → Set<br>says knight p = p<br>says knave  p = ¬ p</pre><blockquote>Note: In intuitionistic logic, a negation statement</blockquote><blockquote>¬ (A ≡ knight)</blockquote><blockquote>does not automatically mean that (A ≡ knave)</blockquote><h4>Puzzle 1</h4><blockquote>You meet two inhabitants: Zoey and Mel. Zoey tells you that Mel is a knave. Mel says, “Neither Zoey nor I are knaves.”</blockquote><p>Puzzle Credits: <a href="https://philosophy.hku.hk/think/logic/knights.php">https://philosophy.hku.hk/think/logic/knights.php</a></p><p>To start of with we can model Zoey and Mel as variable of type Person</p><pre>Zoey : Person<br>Mel  : Person</pre><p>We can represent the “Zoey tells you that Mel is a knave” as</p><pre>says Zoey (Mel ≡ knave)</pre><p>and the statement <em>“Mel says, ‘Neither Zoey nor I are knaves.’ ”</em> as a conjuction of two statements <em>“Zoey is not a knave” </em>and <em>“Mel is not a knave”.</em></p><pre>says Mel ((Zoey ≢ knave) × (Mel ≢ knave))</pre><p>To form the problem statement we need to define a type that captures all the information. This is done as follows</p><pre>data Solution : Set where<br>    soln : (Zoey : Person) → (Mel : Person) →       -- Two people Zoey Mel<br>      (says Zoey (Mel ≡ knave)) →                   -- Zoey&#39;s statement<br>      (says Mel ((Zoey ≢ knave) × (Mel ≢ knave))) → -- Mel&#39;s statement<br>      Solution₃</pre><h4>Solution</h4><p>Now to solve this we need to create a function with this type</p><pre>answer : Solution<br>answer = ?</pre><p>Proof can be created interactively in Agda in Emacs. A ? create a hole, which is basically a placeholder. First let’s expand this, this using the command C-c C-r</p><pre>answer : Solution<br>answer = soln {}1 {}2 {}3 {}4</pre><p>Now we try different possibilities for Zoey and Mel and also prove Zoey and Mel’s statement. You might ask how this is different from doing this puzzle in pen and paper? The answer is the Agda’s type system ensures that your answer is correct, Agda is assisting your to prove your solution.</p><p>Agda also comes with an auto proof search utility, entering C-c C-a in a hole tries to automatically find a proof. Let try seeing if Agda can find a proof from hole 3 (statement <em>“Zoey tells you that Mel is a knave”</em>)</p><pre>answer : Solution<br>answer = soln₃ knight knave refl {}4</pre><p>Agda automatically filled in that Zoey is a knight and Mel is a knave. As a knight Zoey is telling the truth, the proof is that it is a simple reflexive relation.</p><p>Proving Mel’s statement is a bit different because it involves negation. Mel says “Neither Zoey nor I are knaves”, we need to prove that at-least one of these statements is absurd.</p><p>We define a property called <strong>¬-elim</strong> to eliminate absurd statements. <strong>¬-elim</strong> means, “If you have a statement that a glass is not empty ¬-x and a statement that the glass is empty x, then the existence of both the statement together in absurd”. So how does this property apply for us?</p><p>In our case when Mel is knave, Mel’s statement implies that “Zoey a knight not a knave” and “Mel a knave is not a knave”. “A Knave is a Knave” is established by a reflexive relation. The existance of the second statement “Mel a knave is not a knave”, when reflexive relation is established is absurd by our property ¬-elim. QED Mel’s statement is negated.</p><pre>¬-elim : {A : Set} → ¬ A → A → ⊥<br>¬-elim ¬x x = ¬x x<br><br>answer : Solution<br>answer = soln knight knave<br>  refl<br>  λ{ ⟨ knv≢kni , knv≢knv ⟩ → ¬-elim knv≢knv refl}</pre><p>This can be compiled with C-c C-l , Agda’s typechecker validates it indicating that the solution to our Puzzle is that <strong>Zoey is a Knight and Mel is a Knave.</strong></p><h4>Puzzle 2</h4><blockquote>You meet two inhabitants: Peggy and Zippy. Peggy tells you that “of Zippy and I, exactly one is a knight’. Zippy tells you that only a knave would say that Peggy is a knave.</blockquote><p>Puzzle Credits: <a href="https://philosophy.hku.hk/think/logic/knights.php">https://philosophy.hku.hk/think/logic/knights.php</a></p><p>Let’s look at the second statement “Zippy tells you that only a knave would say that Peggy is a knave”. n this case Zippy is statement is nested, we be modelled as a nested say</p><pre>(says Zippy (says knave (Peggy ≡ knave)))</pre><p>The first statement “of Zippy and I, exactly one is a knight”, can be said as “Either “zippy is a knight and peggy is not a knight” or “zippy is not a knight and peggy is a knight””. The “either-or” is a disjoint union, the “and” is a cartesian product. So together it can be said</p><pre>(Zippy ≡ knight × Peggy ≢ knight) ⊎ (Zippy ≢ knight × Peggy ≡ knight)</pre><p><strong>Model</strong></p><p>The final model for this puzzle can be given as</p><pre>data Solution₂ : Set where<br>  soln₂ : (Peggy : Person) → (Zippy : Person)<br>    → (says Peggy ((Zippy ≡ knight × Peggy ≢ knight) ⊎ (Zippy ≢ knight × Peggy ≡ knight)))<br>    → (says Zippy (says knave (Peggy ≡ knave)))<br>    → Solution₂</pre><p>I wasn’t able to use the auto solver in this case, but I was able to validate my hypothesis with Agda.</p><p><strong>Possibility 1:</strong></p><p>Assuming Zippy is a knight, the second statement “Zippy tells you that only a knave would say that Peggy is a knave”, implied that Peggy should be knight. Using auto-complete on the second statement, Agda auto-fills a proof and that Peggy is a knight. However the first statement cannot be satisfied as it says that only one of them is a knight, hence Zippy is a knave.</p><pre>possibility₁ : Solution₄<br>possibility₁ = soln₄ knight knight<br>  {!!}<br>  λ ()</pre><p><strong>Possibility 2:</strong></p><p>Using what we learnt Zippy is knave, we can auto-search for a proof for the first statement, this gives us that Peggy is a knight. This cannot satisfy the second statement as it would mean that Zippy is telling the truth that a knave will lie that Peggy is a knave. Hence Peggy is also a knave.</p><pre>possibility₂ : Solution₄<br>possibility₂ = soln₄ knight knave<br>  (inj₂ ⟨ (λ ()) , refl ⟩)<br>  {!!}</pre><p><strong>Answer:</strong></p><p>If we assume that both Peggy and Zippy are knave, then we can prove the both the statements are absurd. None of them are knights so the first statement is absurd. Zippy’s statement is absurd as “it is absurd for a knave to say the truth that Peggy is a knave”. QED Peggy is a knave and Zippy is a knave.</p><pre>answer₂ : Solution₂<br>answer₂ = soln₂ knave knave<br>  (λ{ (inj₁ ()) ; (inj₂ ())})<br>  (λ knv≢knv → ¬-elim knv≢knv refl)</pre><p><strong>Why is this one complex?</strong></p><p>Solving the second puzzle where both people where knaves was more difficult compared to the first one. And at first sight it might look as if we are just considering both the statements to be absurd without constructing from a known valid proposition.</p><p>In the second puzzle the second statements’ proof is case of inverse of double negation. In intuitional logic double negation is not provable but the inverse of it is provable. The valid statement that a “knave ≡ knave” implies that the double negation of the statement is valid.</p><pre>-- Not provable in intuitional logic<br>postulate<br>  ¬¬-elim : {A : Set} → ¬ ¬ A → A<br><br>¬¬-intro : ∀ {A : Set} → A → ¬ ¬ A<br>¬¬-intro x  =  λ{¬x → ¬x x}<br><br>answer₃ : Solution₂<br>answer₃ = soln₂ knave knave<br>  (λ{ (inj₁ ()) ; (inj₂ ())})<br>  (¬¬-intro refl)</pre><h3>Conclusion</h3><p>In this article we say a very brief introduction to the dependently typed functional programming language Agda. We looked at an example of how to represent the “knights and knaves” puzzle’s statements/propositions as types and how to prove a solution.</p><p>If you are interested to know more about this topic or which to see other example, let me know in the comments.</p><h3>References</h3><ol><li><a href="https://agda.readthedocs.io/en/latest/getting-started/a-taste-of-agda.html">https://agda.readthedocs.io/en/latest/getting-started/a-taste-of-agda.html</a></li><li><em>Wadler, Philip, Wen Kokke, and Jeremy G. Siek. </em>Programming Language Foundations in Agda<em>. Available at </em><em>https://plfa.inf.ed.ac.uk/22.08/. 2022.</em></li><li>Proposition as Types, Numberphile, <a href="https://www.youtube.com/watch?v=SknxggwRPzU">https://www.youtube.com/watch?v=SknxggwRPzU</a></li><li>Proposition as Types, Wadler, <a href="https://www.youtube.com/watch?v=IOiZatlZtGU">https://www.youtube.com/watch?v=IOiZatlZtGU</a></li><li><a href="https://pwparchive.wordpress.com/2012/09/06/logical-puzzles-in-agda/">https://pwparchive.wordpress.com/2012/09/06/logical-puzzles-in-agda/</a></li><li><a href="https://math.stackexchange.com/questions/2400914/why-do-i-keep-running-into-contradictions-in-this-problem-knights-and-knaves-va">https://math.stackexchange.com/questions/2400914/why-do-i-keep-running-into-contradictions-in-this-problem-knights-and-knaves-va</a></li></ol><p><em>Disclaimer: The statements and opinions expressed in this blog are those of the author(s) and do not necessarily reflect the positions of Thoughtworks.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=675959eef957" width="1" height="1" alt=""><hr><p><a href="https://medium.com/e4r/solving-logic-puzzles-with-dependently-typed-functional-programming-675959eef957">Solving Logic Puzzles with Dependently Typed Functional Programming</a> was originally published in <a href="https://medium.com/e4r">Thoughtworks: e4r™ Tech Blogs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Algebra of Pretty Printing]]></title>
            <link>https://medium.com/e4r/the-algebra-of-pretty-printing-b354b9ad0b17?source=rss-571b24ff626d------2</link>
            <guid isPermaLink="false">https://medium.com/p/b354b9ad0b17</guid>
            <category><![CDATA[functional-programming]]></category>
            <category><![CDATA[compilers]]></category>
            <category><![CDATA[scala]]></category>
            <dc:creator><![CDATA[Nimalan]]></dc:creator>
            <pubDate>Wed, 14 Feb 2024 18:31:45 GMT</pubDate>
            <atom:updated>2024-02-15T04:33:04.655Z</atom:updated>
            <content:encoded><![CDATA[<p>Pretty printing is the problem of printing structured data in a user friendly manner with some constraints. Linters, code transformers and debuggers all have some form of pretty printers present in them. Pretty printing can be seen as the dual of parsing, and they both share similar complexities when trying to make reusable libraries.</p><p>Functional programming has a rather interesting take on pretty printing. Exploring a functional design of a pretty printer will be the primary focus of this article.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*f0OsjCXTNwc8nldy" /><figcaption>Photo by <a href="https://unsplash.com/@bernardhermant?utm_source=medium&amp;utm_medium=referral">Bernard Hermant</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h3>Functional Pretty Printing</h3><blockquote>On what does the power of functional programming depend? Why are functional programs so often a fraction of the size of equivalent programs in other languages? Why are they so easy to write? I claim: because functional languages support software reuse extremely well — Hughes, J. (1995). The Design of a Pretty-printing Library</blockquote><p>As the icon of functional programming languages, Haskell has influenced pretty printing quite well. Hughes Jones’ [1] pretty printer used an algebraic approach and advanced the general design of pretty printing, this design was part of the Glasgow Haskell Compiler (GHC) distribution for some time as well. It also influenced future variants such as the Lindig’s variant [2] and the Wadler’s variant [3]. Other functional programming languages line ML, Scala [4] have also used variants of the Hughes’ pretty printer as well.</p><h4>Design of a Functional Pretty Printer</h4><p>All the variants mentioned above share a common approach to the problem. Pretty printing results in the creation of a “document”. A document is defined using an Algebraic structure with following objects.</p><ol><li>DocNil — the identity element</li><li>DocText — string literals</li><li>DocBreak — line breaks</li><li>DocCons — composed elements or can be seen as Lists</li><li>DocNest — nested documents</li><li>DocGroup — logical groups in the document</li></ol><p>Additional objects of can be derived the existing objects. Example DocSpace defining a space in the document can be derived as DocText “ “.</p><p>The &lt;&gt; is an endomorphism that combines different objects together. The string “Hello World” can be created using DocText &quot;Hello&quot; &lt;&gt; DocSpace &lt;&gt; DocText &quot;World&quot;.</p><pre>// Document Algebraic Data in Scala 3<br>enum Doc:<br>  case DocNil<br>  case DocBreak<br>  case DocSpace<br>  case DocText(txt: String)<br>  case DocCons(hd: Doc, tl: Doc)<br>  case DocNest(indent: Int, doc: Doc)<br>  case DocGroup(doc: Doc)<br><br>  def &lt;&gt;(hd:Doc): Doc = (this, hd) match<br>    case (_, DocNil) =&gt; this<br>    case (DocNil, _) =&gt; hd<br>    case _ =&gt; DocCons(this, hd)</pre><p>With these building blocks documents can be created. Optionally we can define extra morphisms/functions for convenience. Example &lt;@&gt; and &lt;+&gt; are wrappers on &lt;&gt; to combine objects with line-breaks and spaces respectively.</p><pre>def &lt;@&gt;(hd: Doc): Doc = hd match<br>  case DocNil =&gt; this<br>  case _ =&gt; this &lt;&gt; DocBreak &lt;&gt; hd<br><br>def &lt;+&gt;(hd: Doc): Doc = this &lt;&gt; DocSpace &lt;&gt; hd<br><br>def folddoc(ds: Iterable[Doc], f: (Doc, Doc) =&gt; Doc) = ds.isEmpty match<br>  case true =&gt; emptyDoc<br>  case false =&gt; ds.tail.foldLeft(ds.head)(f)<br><br>def hsep(ds: Iterable[Doc]): Doc =<br>  folddoc(ds, _ &lt;+&gt; _)<br><br>def vsep(ds: Iterable[Doc]): Doc =<br>  folddoc(ds, _ &lt;@&gt; _)</pre><h3>Algebra of Layouts</h3><p>Hughes’ paper “The Design of a Pretty-printing Library” also define the algebra of the layouts when composing documents. These are useful when we have additional constraints when pretty printing such as line length, etc. In which case we can derive an alternative layout by reordering the structure according to the rules of the layout algebra.</p><pre>                              Layout Algebra<br>                 ------------------------------------------<br>                      (x &lt;&gt; y) &lt;&gt; z = x &lt;&gt; (y &lt;&gt; z)<br>                    (x &lt;@&gt; y) &lt;@&gt; z = x &lt;@&gt; (y &lt;@&gt; z)<br>                        x &lt;&gt; DocNil = x<br>                DocNest k (x &lt;@&gt; y) = DocNest k x &lt;@&gt; DocNest k y<br>                 DocNest k (x &lt;&gt; y) = DocNest k x &lt;&gt; DocNest k y<br>                   x &lt;&gt; DocNest k y = x &lt;&gt; y<br>              DocNest k (DocNest k&#39; x) = DocNest (k + k&#39;) x<br>                        DocNest 0 x = x<br>                     (x &lt;@&gt; y) &lt;&gt; z = x &lt;@&gt; (y &lt;&gt; z)<br>DocText s &lt;&gt; ((DocNil) &lt;&gt; y) &lt;@&gt; z) = (DocText s &lt;&gt; y) &lt;@&gt; DocNest (len s) z<br>             DocText s &lt;&gt; DocText t = DocText (s ++ t)</pre><h3>ToyLang — A Case Study</h3><p>Let’s look at a practical example. We will design a pretty printer for a custom language we call “ToyLang”. Toylang has the following features</p><ol><li>All literal are integers</li><li>Variable are supported</li><li>Binary arithmetic operators are supported</li><li>Conditional statements are supported</li><li>ToyLang supports nested scopes</li></ol><p>An example program in ToyLang</p><pre>{<br>  x = 5;<br>  z = 35;<br>  a = 25;<br>  {<br>    y = 10;<br>    x = x + y;<br>    if ( x &gt; 10 )<br>    {<br>      y = 5;<br>    }<br>  }<br>}</pre><p>The AST and the pretty printer will be implemented in Scala 3, we will not be implementing the parser. Scala had a pretty printer until version <em>2.11.0 </em>implemented by Michel Schinz [4] based on Lindig’s strict version of Wadler’s adaptation of Hughes’ pretty printer. The design will be based on the Scala 2 pretty printer Document.scala</p><h4>Abstract Syntax Tree of ToyLang</h4><p>Algebraic Data Types (ADT) are a good choice to for creating ASTs. Scala 3 enums are ADTs. We can define ToyLang as follows.</p><pre>enum BOp:<br>  case Add<br>  case GT<br><br>enum Expr:<br>  case EVar(id: String)<br>  case EInt(v: Int)<br>  case EBinop(op: BOp, e1: Expr, e2: Expr)<br><br>enum Statement:<br>  case SAssign(lhs: Expr, rhs: Expr)<br>  case SPar(stmts: Seq[Statement])<br>  case SIf(cond: Expr, cons: Statement, alt: Statement)<br>  case SEmpty</pre><p>With the defined AST, the example program of ToyLang should look something like this after parsing. Our goal now is to pretty print this structure.</p><pre>val prog: Statement = SPar(Seq(<br>  SAssign(EVar(&quot;x&quot;), EInt(5)),<br>  SAssign(EVar(&quot;z&quot;), EInt(35)),<br>  SAssign(EVar(&quot;a&quot;), EInt(25)),<br>  SPar(Seq(<br>    SAssign(EVar(&quot;y&quot;), EInt(10)),<br>    SAssign(EVar(&quot;x&quot;), EBinop(BOp.Add, EVar(&quot;x&quot;), EVar(&quot;y&quot;))),<br>    SIf(<br>      EBinop(BOp.GT, EVar(&quot;x&quot;), EInt(10)),<br>      SPar(Seq(<br>        SAssign(EVar(&quot;y&quot;), EInt(5))<br>      )),<br>      SEmpty)<br>  ))<br>))</pre><h4>Pretty Printing ToyLang</h4><p>The basic elements of the AST can be pretty printed as string literals and &lt;&gt; compositions of string literals. We use extensions to add an emit method to the AST classes.</p><pre>extension (op: BOp)<br>  def emit: Doc = op match<br>    case Add =&gt; text(&quot;+&quot;)<br>    case GT =&gt; text(&quot;&gt;&quot;)<br><br>extension (expr: Expr)<br>  def emit: Doc = expr match<br>    case EVar(id) =&gt; text(id)<br>    case EInt(v) =&gt; text(v.toString)<br>    case EBinop(op, e1, e2) =&gt; e1.emit &lt;+&gt; op.emit &lt;+&gt; e2.emit</pre><p>For the nested scoping and conditional statements we define an abstraction to wrap blocks.</p><pre>def parens(d: Doc) = enclose(text(&quot;(&quot;), d, text(&quot;)&quot;))<br><br>def scope(<br>  doc: Doc,<br>  left: Doc = lbrace,<br>  right: Doc = rbrace,<br>  indent: Int = 2<br>): Doc =<br>  left &lt;&gt; nest(emptyDoc &lt;@&gt; doc, indent) &lt;@&gt; right<br><br>extension (stmt: Statement)<br>  def emit: Doc = stmt match<br>    case SAssign(lhs, rhs) =&gt; lhs.emit &lt;+&gt; equal &lt;+&gt; rhs.emit &lt;&gt; semi<br>    case SPar(stmts) =&gt; scope(vsep(stmts.map(stmt =&gt; stmt.emit)))<br>    case SIf(cond, cons, alt) =&gt; text(&quot;if&quot;) &lt;+&gt; parens(cond.emit) &lt;@&gt; cons.emit<br>    case SEmpty =&gt; text(&quot;&quot;)</pre><p>The AST can be converted into a Document by calling the emit method.</p><h4>Document to String</h4><p>Finally we need to export the Document to a String. We use the StringWriter to construct the string. The method fmt defines how each document type has to be appended into the StringWriter.</p><pre>  def pretty: String =<br>    val writer = new java.io.StringWriter()<br>    format(writer)<br>    writer.toString<br><br>  def format(writer: Writer): Unit =<br>    type FmtState = (Int, Doc)<br><br>    def spaces(n: Int): Unit =<br>      var rem = n<br>      while (rem &gt;= 16) { writer write &quot;                &quot;; rem -= 16 }<br>      if (rem &gt;= 8) { writer write &quot;        &quot;; rem -= 8 }<br>      if (rem &gt;= 4) { writer write &quot;    &quot;; rem -= 4 }<br>      if (rem &gt;= 2) { writer write &quot;  &quot;; rem -= 2 }<br>      if (rem &gt;= 1) { writer write &quot; &quot; }<br><br>    def fmt(state: List[FmtState]): Unit = state match<br>      case List() =&gt; ()<br>      case (_, DocNil) :: z =&gt; fmt(z)<br>      case (i, DocCons(h, t)) :: z =&gt; fmt((i, h) :: (i, t) :: z)<br>      case (_, DocText(t)) :: z =&gt;<br>        writer.write(t)<br>        fmt(z)<br>      case (i, DocNest(ii, d)) :: z =&gt; fmt((i+ii, d):: z)<br>      case (i, DocBreak) :: z =&gt;<br>        writer.write(&quot;\n&quot;)<br>        spaces(i)<br>        fmt(z)<br>      case (_, DocSpace) :: z =&gt;<br>        writer.write(&quot; &quot;)<br>        fmt(z)<br>      case _ =&gt; ()</pre><p>To conclude, with these blocks we have designed a pretty printer and have also demonstrated an example of using this to pretty print an Abstract Syntax Tree.</p><h3>Conclusion</h3><p>Excluding the example the pretty printer was about ~100 lines of code. For any AST once it is converted into the Document type the pretty printer can be reused. In a future article we will explore on how constraints can be added to pretty printing.</p><p>The full code is available as a <a href="https://gist.github.com/Mark1626/1221c1750e38d55fe605225cf877356c">Github Gist</a></p><h3>References</h3><ol><li>Hughes, J. (1995). The Design of a Pretty-printing Library. <em>Advanced Functional Programming</em>.</li><li>Wadler, P., &amp; Kilmer, J. (2002). A prettier printer.</li><li>Lindig, C. (2000). Strictly Pretty.</li><li><a href="https://github.com/scala/scala/blob/v2.11.8/src/library/scala/text/Document.scala">https://github.com/scala/scala/blob/v2.11.8/src/library/scala/text/Document.scala</a></li><li><a href="https://jyp.github.io/posts/towards-the-prettiest-printer.html">https://jyp.github.io/posts/towards-the-prettiest-printer.html</a></li></ol><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/68bbb909716fee87eb98b57830b55f44/href">https://medium.com/media/68bbb909716fee87eb98b57830b55f44/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b354b9ad0b17" width="1" height="1" alt=""><hr><p><a href="https://medium.com/e4r/the-algebra-of-pretty-printing-b354b9ad0b17">The Algebra of Pretty Printing</a> was originally published in <a href="https://medium.com/e4r">Thoughtworks: e4r™ Tech Blogs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Accelerating an Lorenz ODE Solver with Dahlia]]></title>
            <link>https://medium.com/e4r/accelerating-an-lorenz-ode-solver-with-dahlia-48ec675ecb59?source=rss-571b24ff626d------2</link>
            <guid isPermaLink="false">https://medium.com/p/48ec675ecb59</guid>
            <category><![CDATA[fpga]]></category>
            <category><![CDATA[high-level-synthesis]]></category>
            <category><![CDATA[accelerated-computing]]></category>
            <category><![CDATA[hpc]]></category>
            <dc:creator><![CDATA[Nimalan]]></dc:creator>
            <pubDate>Wed, 10 Jan 2024 05:53:49 GMT</pubDate>
            <atom:updated>2024-01-31T04:14:05.469Z</atom:updated>
            <content:encoded><![CDATA[<p>In this article, we will design a Lorenz ODE Solver in Dahlia, exploring the use of Dahlia records, functions, and single-precision floats. The target backend will be Vitis HLS.</p><p>This is part of a series of articles on the Dahlia programming language. The accompanying code for the example can be found in <a href="https://github.com/Mark1626/dahlia-cookbook/blob/master/lorenz/README.md">Github</a>, the fixed point variant of the same design is <a href="https://github.com/Mark1626/dahlia-cookbook/tree/master/lorenz-fp">available here</a>.</p><p><a href="https://medium.com/@nimalan854/list/918a8f92baeb">Dahlia HLS</a></p><h3>Background</h3><h4>Lorenz System</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/475/1*YHc-xqd2xItU3ypN9f3CAg.png" /><figcaption>Lorenz System</figcaption></figure><p>An<strong> Ordinary differential equation (ODE) </strong>is a differential equation that is dependent on only a single independent variable. The Lorenz system is given by the following three differential equations.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/1*3T9ZT2_doCbY1e_k0kt4Wg.png" /><figcaption>Lorentz system</figcaption></figure><p>It has chaotic solutions for certain parameters. The above plot is the solution for <em>ρ</em> = 28, <em>σ</em> = 10, and <em>β</em> = 8/3.</p><p>For solving the Lorenz ODE we will be using the Runge-Kutta method.</p><h4>Runge-Kutta method</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*aqotGmS_KeqJix-EJrr0-A.png" /><figcaption>Euler method</figcaption></figure><p>Runge-Kutta methods propagate a solution over an interval by combining the information from several Euler-style step, and then using the information obtained to match a Taylor series expansion up to some higher order [1].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*s0zlxgFZR3hvPYTnDOS31Q.png" /><figcaption>Second order Runge Kutta</figcaption></figure><p>Typically a fourth order RK is used for ODEs. For this design we will be creating an accelerator for a second order RK.</p><h3>Accelerator Design</h3><h4>State of the System</h4><p>We start by using a <strong>record</strong> to define <em>x</em>, <em>y</em> and <em>z </em>values. Records are custom types in Dahlia. These can contain simple primitives or other records, they cannot contain arrays.</p><pre>record state {<br>    x: float;<br>    y: float;<br>    z: float<br>}</pre><p>Next we define functions to work on the state. Functions in Dahlia are inlined at their application.</p><pre>def st_scale(h: float, s: state): state = {<br>    let ns: state = { x=h*s.x; y=h*s.y; z=h*s.z };<br>    return ns;<br>}<br><br>def st_add(a: state, b: state): state = {<br>    let c: state = { x=a.x+b.x; y=a.y+b.y; z=a.z+b.z };<br>    return c;<br>}</pre><h4>Lorentz ODE</h4><p>Since RK will involve multiple Euler steps, we will define <strong><em>f</em></strong> as a function. This will take a state and return the next state.</p><pre>def f(s: state, t: float): state = {<br>    let sigma: float = 10.0;<br>    let beta: float = 8.0 / 3.0;<br>    let rho: float = 28.0;<br><br>    let nx = sigma * (s.y - s.x);<br>    let ny = s.x * (rho - s.z);<br>    let nz = s.x * s.y - beta * s.z;<br>    let next_state: state = { x=nx; y=ny; z=nz };<br><br>    return next_state;<br>}</pre><h4><strong>Runge Kutta Step</strong></h4><p>RK steps are defined using a for loop with a predefined MAX_ITERATION ( in this case 16384). To step the iteration only to N iterations we add a conditional block.</p><p>The <strong><em>decor </em></strong>keyword in Dahlia is to add inline decorative pragmas/labels. In this case the <strong><em>decor</em></strong> adds a label to the loop, so the in the final Vitis HLS synthesis report we can identify it.</p><pre>def rk2(ys: state[16384], dt: float, N: ubit&lt;32&gt;) = {<br>    let h = dt;<br>    let h_2 = dt * 0.5;<br>    let offset: ubit&lt;32&gt; = 1;<br>    let current_y = ys[0];<br><br>    ---<br><br>    decor &quot;rk_loop:&quot;<br>    for (let i=1..16384) {<br>        if (i &lt; N) {<br>            let idx = i + offset;<br>            let t = dt * (idx as float);<br><br>            let k1: state = st_scale(h, f(current_y, t));<br><br>            let k2_y: state = st_add(current_y, st_scale(0.5, k1));<br>            let k2_x: float = t + h_2;<br>            let k2: state = st_scale(h, f(k2_y, k2_x));<br><br>            let next_y = st_add(current_y, st_scale(1.0/6.0, st_add(k1, k2)));<br><br>            current_y := next_y;<br>            ys[i] := next_y;<br>        }<br>    }<br>}</pre><h4><strong>Interface</strong></h4><p>In the top interface we accept the <strong><em>initial state, N </em></strong>and<strong><em> dt. ys</em></strong><em> </em>is a list of the output states.</p><pre>decl init_int: float[3];<br>decl ys_int: float[MAX_STEPS][3];<br>decl N: ubit&lt;32&gt;;<br>decl dt: float;<br><br>{<br>    let ys: state[MAX_STEPS];<br><br>    // Load initial state<br>    let init_x: float = init_int[0];<br>    ---<br>    let init_y: float = init_int[1];<br>    ---<br>    let init_z: float = init_int[2];<br>    let initial_st: state = { x=init_x; y=init_y; z=init_z };<br><br>    ---<br><br>    ys[0] := initial_st;<br>    ---<br><br>    // Compute<br>    rk2(ys, dt, N);<br><br>    // Store<br>    decor &quot;out_loop:&quot;<br>    for (let i=0..MAX_STEPS) {<br>        if (i &lt; N) {<br>            ys_int[i][0] := ys[i].x;<br>            ---<br>            ys_int[i][1] := ys[i].y;<br>            ---<br>            ys_int[i][2] := ys[i].z;<br>        }<br>    }<br>}</pre><h3>Validation</h3><p>The following testbench is used for CSimulation and Cosimulation. The lorenz method is called and the output states are written to a file.</p><pre>int main() {<br>    int N = 16384;<br>    float ys[N][3];<br>    float dt = 0.03;<br>    float init_state[3] = { 1.0, 1.0, 1.0 };<br><br>    std::ofstream out_dat(&quot;out.dat&quot;, std::ios::binary);<br><br>    assert(N &lt;= LORENZ_MAX_STEPS);<br><br>    lorenz(init_state, ys, N, dt);<br><br>    for (int i = 0; i &lt; N; i++) {<br>        out_dat &lt;&lt; ys[i][0] &lt;&lt; &quot;, &quot; &lt;&lt; ys[i][1] &lt;&lt; &quot;, &quot; &lt;&lt; ys[i][2] &lt;&lt; std::endl;<br>    }<br><br>    return 0;<br>}</pre><p>Plotting the CSimulation result we can see the attractor, this verifies the functional working of the accelerator. CoSimulation will verify the generated RTL and capture information about the average latency of the design.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/627/1*1P0zDAXHrutcZJC340xjeg.png" /><figcaption>Lorenz system (plotted using the output from the design)</figcaption></figure><h3>Conclusion</h3><p>In this article, we explored the creation of an ODE solver using Dahlia records and functions and single precision floats. A Fixed Point variant of the same design is also <a href="https://github.com/Mark1626/dahlia-cookbook/tree/master/lorenz-fp">available</a>. In the next article, we will examine memory banks and loop unrolling in Dahlia.</p><h3>Acknowledgement</h3><p>This work was done as a part of the Engineering for Research (e4r™) initiative by Thoughtworks.</p><h3>References</h3><ol><li>Press, William, et al. “Chapter 15: Integration of Ordinary Differential Equations.” <em>Numerical Recipes in C: The Art of Scientific Computing</em>, Cambridge University, 1988, pp. 569–573.</li><li><a href="https://en.wikipedia.org/wiki/Lorenz_system">https://en.wikipedia.org/wiki/Lorenz_system</a></li></ol><p><em>Disclaimer: The statements and opinions expressed in this blog are those of the author(s) and do not necessarily reflect the positions of Thoughtworks.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=48ec675ecb59" width="1" height="1" alt=""><hr><p><a href="https://medium.com/e4r/accelerating-an-lorenz-ode-solver-with-dahlia-48ec675ecb59">Accelerating an Lorenz ODE Solver with Dahlia</a> was originally published in <a href="https://medium.com/e4r">Thoughtworks: e4r™ Tech Blogs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Dahlia Part 1: Affine types for  High Level Synthesis]]></title>
            <link>https://medium.com/e4r/dahlia-part-1-affine-types-for-high-level-synthesis-7bb611c5267d?source=rss-571b24ff626d------2</link>
            <guid isPermaLink="false">https://medium.com/p/7bb611c5267d</guid>
            <category><![CDATA[high-level-synthesis]]></category>
            <category><![CDATA[accelerated-computing]]></category>
            <category><![CDATA[vitis]]></category>
            <category><![CDATA[mlir]]></category>
            <category><![CDATA[fpga]]></category>
            <dc:creator><![CDATA[Nimalan]]></dc:creator>
            <pubDate>Thu, 28 Dec 2023 17:09:32 GMT</pubDate>
            <atom:updated>2024-01-31T04:15:11.203Z</atom:updated>
            <content:encoded><![CDATA[<h3>Dahlia: Affine types for High Level Synthesis</h3><p>In this article we will be looking at the affine type system and it’s application in FPGA based accelerator design using Dahlia. This is part of a series around the Dahlia programming language.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*LqOLU6OP8TTxEm3K" /><figcaption>Dahlia. Photo by <a href="https://unsplash.com/@lotusflowur?utm_source=medium&amp;utm_medium=referral">Mihika</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h3>Affine Type System</h3><p>An affine type system ensures that every resource is used at most once. A common use, Rust language’s move semantics are affine in nature. It ensures that if a type isn’t marked with the Copy trait it can only be moved not copied. As an example let’s look at <a href="https://en.wikipedia.org/wiki/Linear_logic#The_resource_interpretation">Hoare’s vending machine</a>.</p><pre>/*<br>English: A coin can buy you<br>a piece of candy, a drink,<br>or go out of scope.<br>*/<br><br>// Logic<br>Coin ⊸ Candy<br>Coin ⊸ Drink<br>Coin ⊸ ⊤<br><br>// Rust<br>let coin = Coin{}<br>let candy = buy_candy(coin) // Lifecycle of the resource coin ends here<br><br>// Compilation error: This will fail as the resource coin is already consumed<br>let drink = buy_drink(coin)</pre><p>Affine types are useful for constraining access when handling files, locks and memory. In the following example an affine type system would prevent a <em>double free</em> from occurring.</p><pre>let f: File = open()<br>close(f)<br>close(f) // Not allowed</pre><h3>Affine Types for Accelerator Design</h3><h4>High Level Synthesis</h4><p>High Level Synthesis (HLS) is a technique that converts an annotated subset of a general purpose programming language like (C, C++, MATLAB) into Register Transfer Logic (RTL). This technique is a promising solution for building hardware accelerators for algorithms as it abstracts the complexity which would arise in the implementation of scheduling, bus protocols and RAM controllers.</p><p>We will look at some examples of using Xilinx Vitis HLS. In the following C code matmul is the top-level function. This can be converted to RTL with HLS. There are several abstractions here; one, arrays are accessed by the kernel from DRAM, HBM, or other memory using a Master AXI interface, the control of the kernel is handled by a AXI Lite Slave. Two, since the kernel using floating point operations a Floating Point IP will be instantiated.</p><pre>void matmul(float a[128][128], float b[128][128], float c[128][128]) {<br>  float sum;<br>  for (int i = 0; i &lt; 128; i++) {<br>    for (int j= 0; j &lt; 128; j++) {<br>      sum = 0.0f;<br>      for (int k= 0; k &lt; 128; k++) {<br>        sum += a[i][k] * b[k][j];<br>      }<br>      c[i][j] = sum;<br>    }<br>  }<br>}</pre><p>Optimising HLS designs broadly involves focussing on the three following areas.</p><p><strong>Pipelining: </strong>For compute bound operations we try to achieve an Iteration Interval (<em>II=1 cycle) </em>ie. each iteration starts to process a new data point.</p><p><strong>Scaling: </strong>To reduce total number of cycles needed, the design is scaled to increase the parallelism of the design eg) by loop unrolling.</p><p><strong>Memory: </strong>Scaling and pipelining can only be achieved if the pipelines are saturated with data. Multi-port memories and banked memory are typically used to provide parallel access to data.</p><blockquote>Mostly optimising memory is biggest challenge as both pipelining and scaling depend on data availability.</blockquote><p>However since HLS depends on software languages which are very bad at representing memory and data access, there are several pitfalls that lead to inefficient design.</p><h4>Pitfalls with memory</h4><p>Consider the following example a UNROLL pragma has been added to execute two iteration in parallel each cycle. However this will not achieve a II=1 factor. When loops are unrolled, they need either a multi-ported memory or memory banking to be able to access data needed for it’s iteration. A separate pragma has to be added to define that the variable a and b to be mapped to parallel memory.</p><pre>int a[1024;<br>int b[1024];<br>for (int i = 0; i &lt; 1024; i++) {<br>  #pragma HLS UNROLL FACTOR=2<br>  a[i] = b[i] * 2;<br>}</pre><p>If the <strong>memory only support single access per clock cycle</strong>, the loop body <strong>will execute the loop sequentially</strong>. But since an unroll pragma is given <strong>the loop is still unrolled and it occupies space</strong> in the design.</p><p>While this will be reported as a warning by Vitis HLS in the synthesis report, this is a domain specific problem that has to be prevented to ensure “correctness” of the design.</p><h3>Dahlia: Time sensitive affine type</h3><p><a href="https://github.com/cucapra/dahlia">Dahlia</a> is a programming language to generate FPGA based accelerators. It supports Vitis HLS and the Calyx dialect of MLIR as backends. Dahlia addresses some of the short comings in High Level Synthesis by being domain specific and tackles the challenges with representing memory through affine types with time-sensitivity, complex access patterns have to be explicitly define in the source code.</p><h4>Affine Memory Types</h4><p>The following is a rewrite of the previous example in Dahlia. The memories a and b are defined with a banking factor of 2 and the loop in also unrolled by the same factor. Dahlia’s type checker will fail to compile the code if the unroll was not supported by the memory.</p><pre>let a: float[1024 bank 2];<br>let b: float[1024 bank 2]; // Compilation will fail if bank was not given<br>for (let i = 0 .. 1024) unroll 2 {<br>  a[i] := b[i] * 2.0;<br>}</pre><h4><strong>Time sensitivity</strong></h4><p>While resources in hardware can be defined as affine types, they can be reusable across time steps. Dahlia adds time-sensitivity to it’s affine types system, a logical time step is defined using ---.</p><h4>Views</h4><p>A view in Dahlia captures the access pattern of a memory. Views let Dahlia captures the complexity memory access in the source code. This would mean that person designing the accelerator will have to explicitly represent access patterns and there will be no surprises in the generated hardware.</p><h4>Wrapping up with an example</h4><p>The typical structure for a kernel using in Vitis HLS would have the following structure.</p><ol><li>Declaration of the top level interface to the kernel</li><li>Creation of local arrays bound to appropriately suitable storage types and partitions (banks)</li><li>Load data from the input arrays into local memories</li><li>A compute loop which is pipelined or parallelised or both. To enable this the storage has to accommodate parallel access</li><li>Store data from local memory into output arrays</li></ol><p>The following is a vector add example in Dahlia with the above points highlighted.</p><pre>// 1. Declaration of the interface<br>decl a_interface: float[2048];<br>decl b_interface: float[2048];<br>decl c_interface: float[2048];<br><br>// 2a. Creation a local banked array<br>// Banking factor is 4 as later there is a loop<br>// that is unrolled by a factor of 4<br>let a: float[2048 bank 4];<br>let b: float[2048 bank 4];<br>let c: float[2048 bank 4];<br><br>// 2b. A view with a banking factor 1.<br>// This view is needed when loading data to the local memory<br>view a_sh = a[_: bank 1];<br>view b_sh = b[_: bank 1];<br>view c_sh = c[_: bank 1];<br><br>{<br>  // 3. Load data into the local array.<br>  // Top interfaces are unbanked<br>  for (let i = 0..2048) {<br>    a_sh[i] := a_interface[i];<br>    b_sh[i] := b_interface[i];<br>  }<br>  ---<br>  // 4. Main logic loop. In this case loop unrolling in done by a factor of 4<br>  // The banked memory created earlier enables the parallelism<br>  for (let i = 0..2048) unroll 4{<br>    c[i] := a[i] + b[i];<br>  }<br>  ---<br>  // 5. Store data from the local array into the resultant array<br>  // We are again using a view with a banking factor of 1<br>  for (let i = 0..2048) {<br>    c_interface[i] := c_sh[i];<br>  }<br>}</pre><p>The key takeaway in the code is that Dahlia adds emphasis on memory and access patterns in the source code itself. So unless specified by the developer there are no complex access pattern preventing unintended consequences arising from memory.</p><h3>Conclusion</h3><p>Dahlia is still in early development, however it is interesting and promising to see a language enforcing the developer to think about memory at the source code. In the next part of this series we will be look at a more practical example and go over design considerations when building an accelerator.</p><h3>References</h3><ol><li><a href="https://users.rust-lang.org/t/what-are-affine-types-in-rust/23755">https://users.rust-lang.org/t/what-are-affine-types-in-rust/23755</a></li><li><a href="https://gist.github.com/ttsiodras/e59c5ea4090a11f69073dcc10809d647">https://gist.github.com/ttsiodras/e59c5ea4090a11f69073dcc10809d647</a></li><li><a href="https://circt.llvm.org/docs/Charter/">https://circt.llvm.org/docs/Charter/</a></li><li>de Fine Licht, J., Besta, M., Meierhans, S., &amp; Hoefler, T. (2018). Transformations of High-Level Synthesis Codes for High-Performance Computing. <em>IEEE Transactions on Parallel and Distributed Systems, 32</em>, 1014–1029.</li><li>Nigam, R., Atapattu, S., Thomas, S., Li, Z., Bauer, T., Ye, Y., Koti, A., Sampson, A., &amp; Zhang, Z. (2020). Predictable accelerator design with time-sensitive affine types. <em>Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation</em>.</li></ol><p><em>Disclaimer: The statements and opinions expressed in this blog are those of the author(s) and do not necessarily reflect the positions of Thoughtworks.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7bb611c5267d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/e4r/dahlia-part-1-affine-types-for-high-level-synthesis-7bb611c5267d">Dahlia Part 1: Affine types for  High Level Synthesis</a> was originally published in <a href="https://medium.com/e4r">Thoughtworks: e4r™ Tech Blogs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Building a hardware accelerated simulation using JAX]]></title>
            <link>https://medium.com/e4r/building-a-hardware-accelerated-simulation-using-jax-00437d562002?source=rss-571b24ff626d------2</link>
            <guid isPermaLink="false">https://medium.com/p/00437d562002</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[simulation]]></category>
            <category><![CDATA[jax]]></category>
            <category><![CDATA[hpc]]></category>
            <category><![CDATA[physics]]></category>
            <dc:creator><![CDATA[Nimalan]]></dc:creator>
            <pubDate>Fri, 15 Dec 2023 13:19:00 GMT</pubDate>
            <atom:updated>2024-01-31T04:11:54.312Z</atom:updated>
            <cc:license>http://creativecommons.org/licenses/by/4.0/</cc:license>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*oRJxQCp8R8QI4qi0O1dQ0Q.png" /></figure><p>In this article we will looking at how to build a hardware accelerated simulation with <a href="https://github.com/google/jax">JAX</a>.</p><p>You can find the accompanying code in <a href="https://github.com/Mark1626/finitevolume-jax">Github</a>.</p><h3>JAX</h3><p><a href="https://github.com/google/jax">JAX</a> is a high performance numerical computation library with composable transforms. JAX is built on top of the <a href="https://www.tensorflow.org/xla">XLA</a> linear algebra compiler, which is capable of running code on CPUs, GPUs and TPUs. XLA is able to run on multiple platforms as it leverages <a href="https://mlir.llvm.org/">MLIR</a>.</p><p>Although most common use cases of JAX is in machine learning, JAX can model Linear Algebra computation closer to the domain. This allows for building high performant applications, that can easily target hardware accelerators.</p><h3>The Problem Statement</h3><p>We will be using the code of a finite volume simulation from this article as reference and we will create a hardware accelerated version of it.</p><p><a href="https://levelup.gitconnected.com/create-your-own-finite-volume-fluid-simulation-with-python-8f9eab0b8305">Create Your Own Finite Volume Fluid Simulation (With Python)</a></p><h3>Modelling in JAX</h3><p>The jax.numpy module in JAX is a drop in replacement for numpy and has most of the numpy API. The key thing to remember is that JAX requires you to use pure functions: all the input data is passed through the function parameters, all the results are output through the function results. A pure function will always return the same result if invoked with the same inputs.</p><pre># Numpy<br>f_dx = ( np.roll(f,R,axis=0) - np.roll(f,L,axis=0) ) / (2*dx)<br>f_dy = ( np.roll(f,R,axis=1) - np.roll(f,L,axis=1) ) / (2*dx)<br><br># JAX<br>f_dx = ( jnp.roll(f,R,axis=0) - jnp.roll(f,L,axis=0) ) / (2*dx)<br>f_dy = ( jnp.roll(f,R,axis=1) - jnp.roll(f,L,axis=1) ) / (2*dx)</pre><p>The code from the tutorial already used pure functions, so the only change needed to port from numpy to JAX was to change numpy function calls from np to jnp. This demonstrates how easy it is to migrate existing python code into JAX.</p><p>Keep in mind that numpy is executed on the host machine and JAX functions are compiled and executed on the device (GPU/TPU). We need to be aware about when we transfer data from the host (CPU) to device and vice-versa. Data transfer from device to host is expensive and will down down the execution.</p><h3>Simulations in JAX</h3><p>JAX operates on pure functions however a simulation is an iterative stateful process.</p><p>The State Monad in functional programming can be used to solve this problem. Each iteration of the simulation can be seen represented as a function that takes in a state, performs computation and return a new state.</p><pre>iteration: s -&gt; (s, a)</pre><p>We create the initial state of the system, pass it to the iteration function a number of times with lax.fori_loop and we get the final state of the system. An advantage that we get from this pattern is that we can save the state of simulation at a particular iteration and replay from that point.</p><h4>Dataclasses</h4><p>For a physics simulation such as this, there are a lot of variables in the state. To encapsulate them we create immutable dataclasses. Typically for working with classes in JAX we need to define how the class has to be flattened and unflattened. <a href="https://github.com/google-deepmind/chex">chex</a> is a library in the JAX ecosystem with a convenient utilities, we can use it’s dataclass decorator to simplify this for us.</p><pre>@chex.dataclass<br>class State:<br>  Mass: jax.Array<br>  Momx: jax.Array<br>  Momy: jax.Array<br>  Energy: jax.Array<br><br>@chex.dataclass<br>class Environment:<br>  courant_fac: jnp.float32<br>  dx: jnp.float32<br>  gamma: jnp.float32<br>  vol: jnp.float32</pre><p>In this case the variables that change with each iteration are part of the <strong>State </strong>dataclass and the constant variables that describe the environment are part of the <strong>Environment</strong> dataclass.</p><h4>Simulation Step</h4><p>A simulation iteration takes the Environment, State and returns the next state. We add the jit annotation here to tell JAX to perform Just-in-Time compilation of the function and all the other functions called withing the iteration function. The iteration function is a good candidate for JIT as it does not change. Performing JIT on this function will speed up the execution significantly.</p><pre>@jit<br>def iteration(environment: Environment, state: State) -&gt; State:<br>  <br>  # Logic of the simulation<br><br>  # Create a new state for the next iteration<br>  return state.replace(<br>      Mass = Mass,<br>      Momx = Momx,<br>      Momy = Momy,<br>      Energy = Energy<br>  )<br><br>@jit<br>def multi_step(environment: Environment, state: State, count: int):<br>  return lax.fori_loop(0, count, lambda i, s: iteration(environment, s), state)</pre><h4>Capturing results</h4><p>We would want to capture the results of the simulation periodically, however the simulation happens on an accelerator where data transfer to host is expensive. So we will have to minimise the number of times we perform data transfer.</p><p>To do this we periodically store the results in a separate variable on the device, and when the execution is done we send it back to the host. For simulations with large number of snapshots we will have to periodically send the data back to the device.</p><pre>from jax import tree_util<br>import numpy as np<br><br>def run_simulation(<br>    environment: Environment,<br>    state: State,<br>    count: int,<br>    nr_snapshots: int = 10<br>):<br>  nr_iter_per_snapshot = count // nr_snapshots<br><br>  # For large simulations following steps will have to be repeated periodically<br><br>  results = [state]<br>  for i in range(nr_snapshots):<br>    state = multi_step(environment, state, nr_iter_per_snapshot)<br>    results.append(state)<br>  <br>  # Get data from device<br>  results = jax.device_get(results)<br>  <br>  return tree_util.tree_map(lambda *xs: np.stack([np.array(x) for x in xs]), *results)</pre><h3>Running the Simulation</h3><p>To run the simulation we need to create a environment and state instance and call the run_simulation method we created.</p><pre>environment = Environment(<br>  courant_fac=courant_fac,<br>  dx=dx,<br>  gamma=gamma,<br>  vol=vol<br>)<br><br>initial_state = State(<br>    Mass=Mass,<br>    Momx=Momx,<br>    Momy=Momy,<br>    Energy=Energy<br>)<br><br>nr_iterations = 1000<br>nr_snapshots = 100<br>results = run_simulation(environment, initial_state, nr_iterations, nr_snapshots)</pre><p>The execution time is dependent on the number of snapshots, frequent snapshots will slow the execution time and also increase the memory consumption. Running the simulation on a Google Collab T4 GPU runtime produced this results.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/128/1*LLF3ry6thLkvQqHv1FsGaA.gif" /><figcaption>Results of running the simulation</figcaption></figure><h3>Summary</h3><p>We saw how JAX can be used to model a finite volume fluid simulation. This pattern can be used to create simulations in other domains as well. Porting existing python code to JAX is easy while also being high performant. By using JAX we also were able to target GPUs.</p><p>The code can be found in <a href="https://github.com/Mark1626/finitevolume-jax">Github</a>, you can also try this simulation out in <a href="https://colab.research.google.com/github/Mark1626/finitevolume-jax/blob/main/Finite_Volume_Fluid_Simulation_in_JAX.ipynb">Google Collab</a></p><h3>References</h3><ol><li><a href="https://github.com/pmocz/finitevolume-python/blob/master/finitevolume.py">https://github.com/pmocz/finitevolume-python/blob/master/finitevolume.py</a></li><li><a href="https://github.com/google/jax/blob/main/cloud_tpu_colabs/Wave_Equation.ipynb">https://github.com/google/jax/blob/main/cloud_tpu_colabs/Wave_Equation.ipynb</a></li></ol><p><em>Disclaimer: The statements and opinions expressed in this blog are those of the author(s) and do not necessarily reflect the positions of Thoughtworks.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=00437d562002" width="1" height="1" alt=""><hr><p><a href="https://medium.com/e4r/building-a-hardware-accelerated-simulation-using-jax-00437d562002">Building a hardware accelerated simulation using JAX</a> was originally published in <a href="https://medium.com/e4r">Thoughtworks: e4r™ Tech Blogs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>