

        <cite>Tristan Brindle</cite>
      <time>0:00</time>
      <p>
          I   I   have   this   idea   for   a   talk   that   I   I   might   flesh   out   at   some   point.   It&#39;s   like,   what   is   the   most   powerful   algorithm   in   the   STL?   And   just   to   give   away   the   punchline,   so   uh   my   my   conjecture   is   that   it&#39;s   standard   find   if.   So   I   think,   yeah.
      </p>

        <cite>Bryce</cite>
      <time>0:17</time>
      <p>
          I   mean   he   he&#39;s   not   he&#39;s   not   wrong   because   a   find   if   is   essentially   just   a   reduction,   and   redu   and   the   correct   the   correct   answer   is   a   reduction.
      </p>

        <cite>Conor</cite>
      <time>0:24</time>
      <p>
          I   was   like,   there&#39;s   no   way   Bryce&#39;s   answer   is   instead   reduced. Welcome   to   ADSP   the   podcast,   episode   126,   recorded   on   April   5th,   2023.   My   name   is   Connor.   Today   with   my   co-host   Bryce,   we   interviewed   Tristan   Brindle.   This   is   part   two   of   a   three-part   interview,   and   today   we   talk   about   his   library&#39;s   flux   and   flow.
      </p>

        <cite>Tristan Brindle</cite>
      <time>0:56</time>
      <p>
          So,   okay,   so   at   this   point,   it&#39;s   worth   mentioning   Barry   Rizvin   Ridsvin   has   this   uh   amazing   talk   that   you&#39;ve   you&#39;ve   probably   seen.   I   think   he   gave   it   a   keynote   in   C   Paris,   where   he   compares   the   iteration   schemes   uh   of   uh   various   languages,   right?   Yeah,   Rust   D,   C.   He   also   mentions   like   C   sharp   and   Java   and   Python   and   stuff.   Uh   and   it&#39;s   an   amazing   talk.   So   if   anybody&#39;s   interested   in   this   stuff,   like   really   do   go   and   watch   this.   I   can&#39;t   I   can&#39;t   recommend   it   highly   enough.   Um   but   I   I   so   I   was   kind   of   interested   in   like   how   before   Barry&#39;s   talk,   but   uh   how   how   do   other   languages   do   this?   Um   and   I   started   writing   a   new   library   that   was   uh   implementing   Rust   style   iterators   in   C.   So   for   the   maybe   people   who   know   C   but   don&#39;t   know   Rust,   the   Rust   iteration   scheme   is   really   quite   different   to   how   it&#39;s   done   in   C.   So   what   they   do   is   they   have   this   object   called   an   iterator,   and   the   iterator   has   a   function   called   next.   And   what   next   does   is   it   returns   you   an   optional   with   the   next   value   in   the   sequence.   Right?   So   you   call   next   the   first   time,   it   returns   you   the   first   object,   an   optional   containing   the   first   object   in   the   sequence.   Call   next   again,   it   returns   you   the   second   object   in   the   sequence,   and   so   on   until   eventually   the   sequence   is   exhausted,   and   at   that   point   it   returns   you   uh   an   empty   optional,   which   tells   you   that   uh   the   iteration   is   complete.   So   it&#39;s   an   alternative   way   of   doing   iteration.   Um   there   are   pros   and   cons   to   it.   The   pro   being   it&#39;s   very,   very   much   simpler   than   the   C   model.   Right?   Um   the   downside   is   that   uh   it&#39;s   quite   more   limited,   it&#39;s   not   as   powerful   as   what   you   can   do   with   C,   where   you   can   go   all   the   way   to   random   access.   Um   writing   this   library,   it&#39;s   called   uh   that&#39;s   quite   a   big   limitation.
      </p>

        <cite>Bryce</cite>
      <time>2:55</time>
      <p>
          Um   especially   once   you   start   thinking   about   um   wanting   to   have   uh   implementations   of   your   algorithms   that   consume   iterables   that   that   are   optimized   for   parallelism   and   for   vectorization.   If   you   don&#39;t   have   a   way   to   do   random   access,   that&#39;s   uh   that&#39;s   kind   of   a   problem.
      </p>

        <cite>Tristan Brindle</cite>
      <time>3:18</time>
      <p>
          Yeah,   um   well   this   was   so   I   you   know   I&#39;m   absolutely   by   no   means   a   Rust   expert,   and   I&#39;m   sure   the   Rust   people   will   say,   no,   no,   no,   you   do   it   this   way   instead,   right?   So   I   don&#39;t   I   don&#39;t   want   to   step   on   anybody&#39;s   gonna   be   able   to   do   that.
      </p>

        <cite>Bryce</cite>
      <time>3:32</time>
      <p>
          There   must   be   some   something   that   we&#39;re   missing   here,   is   my   guess.
      </p>

        <cite>Tristan Brindle</cite>
      <time>3:36</time>
      <p>
          Yeah,   yeah.   Um   as   I   say,   not   my   not   my   not   my   sort   of   field   of   expertise   for   how   all   this   parallelism   stuff   is   is   done   in   Rust.   Um   but   for   me,   so   I   I   did   this,   I   wrote   this   this   library,   uh   it&#39;s   actually   uh   on   on   GitHub,   uh   it&#39;s   called   Flow   that   uh   kind   of   does   this   Rust   iteration   scheme   in   C.   Uh   just   kind   of   for   my   own   like   just   for   fun,   really,   just   to   kind   of   see   how   this   was   done.   Uh   but   I   found   this   this   limitation   of   not   being   able   to   go   all   the   way   to   random   access.   Uh   you   know,   this   this   bothered   me.   So   I   was   like,   okay,   is   there   a   way   we   can   extend   the   Rust   iteration   scheme   or   Rust-like   iteration   scheme?   It&#39;s   actually   used   in   a   couple   of   other   languages   as   well.   Uh   we   can   extend   this   to   do   something   like   Rust,   uh   something   like   random   access.   And   it   turns   out   that   the   way   you   actually   implement   these   uh   iterators   in   the   Rust,   or   the   way   I   implemented   these,   is   you   have   like   uh   your   iterator   uh   object   and   it   holds   a   uh   a   cursor   to   the   underlying   uh   sequence   vector,   let&#39;s   say.   So   your   your   cursor   could   be   just   uh   an   integer   index.   And   every   time   someone   calls   next,   you   bump   the   index   and   you   return   then   the   next   element.   So   I   was   like,   okay,   well,   what   if   we   provided   an   API   to   expose   these   cursors   to   the   user   so   that   you   could   then   move   the   cursor   an   arbitrary   uh   you   know   amount   as   you   need   to   for   random   access.   Um   and   then   I   I   did   some   experiments   with   this,   and   I   was   like,   you   know,   this   this   works.   Uh   but   actually,   if   you   do   this   thing,   if   you   expose   these   cursors   to   the   user   and   allow   them   to   manipulate   cursors,   you   really   don&#39;t   need   this.next   function   at   all.   You   can   do   it   all   with   cursors.   Um   so   that   was   my   starting   point   for   this   new   library   that   um   I&#39;ve   been   working   on   called   flux.   So   uh   I   was   like,   okay,   scrap   everything   I&#39;ve   done.   I&#39;m   just   gonna   start   again   from   the   beginning,   and   we&#39;re   gonna   have   this   API   based   on   cursors.   So   what   is   a   cursor?   So   this   is   this   is   getting   into   flux   now,   this   is   the   the   new   thing,   right?   What   is   a   cursor?   A   cursor   is   no   more   and   no   less   than   a   position   in   a   sequence,   right?   So   the   most   general   kind   of   cursor   is   just   an   integer   index   into   an   array,   right?   Cursors   are   a   generalization   of   array   indices.
      </p>

        <cite>Bryce</cite>
      <time>6:15</time>
      <p>
          It&#39;s   it&#39;s   it&#39;s   it&#39;s   so   funny   that   that   you   say   that   because   I&#39;ve   I&#39;ve   been   using   the   same   term   for   the   same   for   the   same   thing   in   this   like   multidimensional   indices   library   that   I&#39;ve   been   playing   around   with.   I   must   have   heard   you   say   it   before   or   something.   Because   I   think   I&#39;ve   I   I   I   recall   hearing   somebody   use   this   terminology.   I   just   don&#39;t   remember   who.
      </p>

        <cite>Tristan Brindle</cite>
      <time>6:39</time>
      <p>
          Maybe   we   were   having   like   a   chat   at   a   conference   or   something,   but   I   can&#39;t   remember   talking   about   it   before.   But   um,   yeah,   so   a   curse   is   like   a   like   a   generalization   uh   of   an   index   in   the   same   way   that   uh   an   STL   iterator   is   a   generalization   of   an   array   pointer.   But   really   the   key   thing   is   that   you   can&#39;t   independently   manipulate   cursors.   So   if   you   think   about   STL   iterators,   STL   iterators   are   smart,   right?   STL   iterators   know   how   to   increment   themselves,   they   know   how   to   dereference   themselves.   Cursors   don&#39;t.   So   a   cursor   just   represents   a   position   in   a   sequence   and   nothing   else.   And   if   you   want   to   increment   the   cursor,   you   have   to   say   to   the   sequence,   please   will   you   increment   this   for   me.   Uh   if   you   want   to   access   the   element,   if   you   want   to   like   dereferencing   in   for   iterators,   you   have   to   say   to   the   sequence,   please   will   you   give   me   the   element   at   this   position.   And   this   doesn&#39;t   seem   like   a   very   big   change   compared   to   iterators,   but   it   turns   out   this   has   pretty   far   reaching,   and   that&#39;s   that&#39;s   the   core   of   flux,   right?   That&#39;s   that&#39;s   the   difference   between   flux   and   ranges.   Uh   but   it   turns   out   this   has   pretty   far-reaching   consequences.   Uh,   number   one   is   that   it   pretty   dramatically   uh   improves   safety,   which   is   kind   of   a   big   deal   at   the   moment,   right?   Like,   because   there   are   so   many   ways   that   you   can   accidentally   stumble   into   undefined   behavior   when   you&#39;re   using   iterators.   Dereferencing   a   past-the-end   iterator   is   undefined   behavior,   incrementing   a   past-the-end   iterator   is   undefined   behavior.   Uh   bidirectional   sequence,   decrementing   a   uh   begin   iterator   is   undefined   behavior,   right?   Um   if   you&#39;re   holding   on   to   an   iterator   and   you   change   the,   if   it&#39;s   a   vector   and   you   change   the   underlying   vector,   you   you&#39;re   gonna   have   uh   you   can   have   a   dangling   iterator.   Uh   well,   you   can   have   dangling   iterators   because   you&#39;re   holding   on   to   this   iterator   and   the   vector   dies,   but   you&#39;ve   still   got   the   iterator.   You   know,   there   are   many   ways   in   which   you   can   stumble   into   undefined   behavior.   This   is   much   more   difficult.   If   a   cursor   just   represents   a   position,   this   you   it&#39;s   much   more   difficult   to   accidentally   stumble   into   undefined   behavior   land,   right?   Because   to   give   you   an   example,   if   the   cursor,   let&#39;s   just   think   of   it   as   a   as   an   integer   index.   If   you&#39;re   holding   on   to   an   integer   index   and   your   vector   goes   out   of   scope,   like   there&#39;s   no   danger   there,   because   you   can&#39;t   do   anything   with   the   index   without   the   original   vector   to   like   try   and   access   it.
      </p>

        <cite>Conor</cite>
      <time>9:14</time>
      <p>
          Right.
      </p>

        <cite>Tristan Brindle</cite>
      <time>9:15</time>
      <p>
          Right?   So   just   immediately   uh   dangling   iterators   like   return   from   functions,   let&#39;s   say,   are   no   longer   a   problem,   like   by   design.   Um,   we   can   also   do,   because   we&#39;ve   always   got   the   sequence   object   available,   we   can   do   uh   cheap   bounds   checking.   So   this   is   something   that   is   quite   expensive   to   do   with   iterators   because   it   means   iterators   need   to   like   have   a   reference   to   the   parent   array   or   to   the   to   the   parent   range,   whereas   with   influx,   we   do   bounds   checking   universally   and   unless   you   specifically   request   uh   request   uh   unchecked   access.   We   will   check   and   make   sure   that   the   uh   that   the   your   cursor   is   in   bounds   before   we   do   the   dereference,   and   otherwise   um   well,   depends   on   the   configuration   what   happens,   either   we   crash   or   we   throw   an   exception.   But   uh   so   we&#39;ve   got   um   bounds   checked   access.   So   this   is   like   I   I   think   I   mean   for   me,   I   think   that&#39;s   really   important.   Um   it&#39;s   something   that   languages   like   Swift   and   and   Rust   and   many   languages   do   everywhere.   Um   so   we&#39;ve   got   bounds   checking,   we&#39;ve   got   uh   um   no   dangling.   There   are   various   other   things   that   turn   out   to   be   uh   better,   like   um   in   C   we   have   to   worry   about   iterators   versus   const   iterators,   uh   which   is   uh   you   know   just   uh   kind   of   a   burden   on   the   programmer   to   uh   particularly   if   you&#39;re   implementing   ranges,   you   have   to   worry   about   um   bad   iterators   and   const   iterators,   and   they&#39;re   not   quite   the   same   thing,   but   you   have   to   be   able   to   convert   from   one   to   the   other,   and   it&#39;s   just   a   pain.   Whereas   with   cursors,   because   a   cursor   is,   you   know,   you   can   think   of   it   as   just   being   like   an   index,   you   can   have   the   same   index   whether   you&#39;re   you   have   a   const   vector   or   a   non-cons   vector,   it   doesn&#39;t   matter.   Right?   We   we   make   the   decision   about   const   or   non-const   access   based   on   the   sequence   that   you   pass   in.   Um   there   are   uh   a   few   other   benefits   as   well   when   you   get   to   writing   adapters.   So   um   when   you   are   actually   implementing   range   adapters,   things   like   map,   things   like   transform,   the   way   that   these   uh   the   iterators   for   these   things   work   is   that   you   have   to   wrap   the   iterator   of   the   underlying,   you   have   to   wrap   the   underlying   iterator,   if   you   see   what   I   mean.   So,   like   uh   in   general,   anyway,   uh   if   you   think   about   the   filter,   um,   the   iterator   for   filter   view,   it   needs   to   contain   the   iterator   for   the   underlying   range,   but   also   uh   have   a   pointer   back   to   the   filter   view   object   so   that   it   can   access   the   predicate.   Um,   and   so   when   you   build   up   one   of   these   ranges   pipelines,   your   iterators,   the   size   of   your   iterators   grows.   Um,   like   for   each   added   stage   of   your   pipeline,   in   general,   your   iterator   object   gets   bigger   and   bigger.   And   since   C   algorithms,   we   assume   that   iterators   really   cheap   to   copy,   you   know,   it&#39;s   not   a   big   deal,   but   it   it   it   you   know   it&#39;s   not   ideal.   Whereas   in   the   the   flux   model   with   cursors,   we   there   is   less   need   to   wrap   these   uh   cursor   objects   and   have   them   get   bigger   and   bigger.   Um,   so   that   I   think   is   uh   is   good.   And   also   the   what&#39;s   also   quite   nice   about   this   is   we   can   provide   compatibility   with   ranges   code   because   if   we   need   to   form   an   iterator,   we   can   form   uh   a   C20   compatible   iterator   by   having   effectively   like   a   pointer   to   a   sequence   and   a   cursor   as   a   pair,   and   then   provide   all   of   the   you   know   the   whatever   it   is,   like   20   odd   functions   you&#39;ve   got   to   you&#39;ve   got   to   write   for   an   iterator.   So   we   can   be   compatible.   In   some   sense,   this   is   this   is   even   more   fundamental   than   than   iterators   because   we   can   we   can   provide   compatibility   uh   with   existing   with   existing   iterators.   So   um   I&#39;m   I&#39;m   very   excited   about   this.   I   I   think   it&#39;s   uh   I   think   it&#39;s   pretty   good.   Um   this   is   I&#39;ve   never   talked   about   this   before   anywhere.   I&#39;ve   like   tease   it   on   Twitter   a   couple   of   times   with   um   like,   hey,   look   at   this,   you   can   do   this   with   my   code,   doesn&#39;t   it   look   awesome?   But   I&#39;ve   never   actually   talked   to   talked   about   this   uh   anywhere.   So   um   yeah.
      </p>

        <cite>Conor</cite>
      <time>13:52</time>
      <p>
          Announcing   to   the   world.   Well,   like   first   part   of   this   episode   will   be   like   uh,   you   know,   nano   nano   ranges,   implementing   nano   ranges,   and   how   you   can   too,   and   then   the   the   second   part   will   be   uh   flux,   and   then   in   parentheses   and   flow,   but   mostly   about   flux.
      </p>

        <cite>Tristan Brindle</cite>
      <time>14:08</time>
      <p>
          Uh   yeah,   that&#39;s   the   other   thing   to   mention,   and   I   didn&#39;t   know   this   when   I   didn&#39;t   know   this   when   I   started   out,   but   we   uh   we   we   were   talking   about   Swift   before.   It   turns   out   that   the   Swift   collection   API   is   pretty   much   the   same   as   what   I&#39;m   doing   in   Flux.   So   I   didn&#39;t   know   this   when   I   started,   right?   Because   I   I   don&#39;t   really   know   much   about   Swift   at   all.   I   only   found   this   out   later.   But   the   so   I   I   mentioned   before   Swift   has   like   these   two   uh   different   protocols,   but   the   collection   protocol   is   this   same   abstraction   of   the   idea   of   an   index.   They   use   different   terminology,   they   use   different   function   names,   but   the   kind   of   the   fundamental   design   is   the   same,   which   actually   gives   me   quite   a   lot   of   confidence   that   I&#39;m   I&#39;m   I&#39;m   going   in   the   right   direction,   if   you   know   what   I   mean.   Like   because   Swift   is   a   safe   language   in   all   the   same   ways   that   Rust   does   a   safe   language,   and   if   it   works   for   them,   well,   you   know,   there&#39;s   a   good   chance   it&#39;ll   work   for   us   as   well.
      </p>

        <cite>Conor</cite>
      <time>15:01</time>
      <p>
          From   what   I&#39;ve   heard   too,   uh   Dave   Abrahams   is   you   know,   he&#39;s   a   pretty   a   pretty   novice   programmer   that   doesn&#39;t   have   too   many   years   of   experience,   right?   Uh   yeah,   we&#39;ll   just   email   it.   Um   Wow,   that&#39;s   uh   that&#39;s   quite   interesting.   Well,   so   obviously   we&#39;ll   definitely   link   to   this.   And   and   I   mean   a   a   a   couple   I   mean   we   never   got   back   to   the   tweet   of   why   you   ended   up   here,   but   the   second   tweet   Oh   um   Yeah.   Actually,   did   I   link   it?
      </p>

        <cite>Bryce</cite>
      <time>15:26</time>
      <p>
          But   before   before   we   move   on,   I   just   gotta   say   I   think   I   think   uh   you&#39;re   you&#39;re   on   the   right   track   with   this   uh   uh   with   this   model.   Um   and   I   think   that   it   it   opens   up   a   lot   of   things,   um,   especially   related   to   loop   optimization   that   um   are   challenging   with   the   iterator   model.   And   and   I   think   um,   especially   like   in   in   in   like   numeric   in   comp   in   computational   science   spaces,   this   cursor   model   is   um   is   potentially   a   much   better   fit.
      </p>

        <cite>Tristan Brindle</cite>
      <time>15:54</time>
      <p>
          Yeah,   yeah.   So   that&#39;s   actually   one   thing   I   I   didn&#39;t   mention   is   that   we   have   um   an   extra   customization   point   that   is   not   in   ranges,   uh,   but   we   but   uh   in   Flux   we   have   this   customization   point   for   doing   internal   iteration.
      </p>

        <cite>Bryce</cite>
      <time>16:09</time>
      <p>
          Oh,   that&#39;s   interesting.   That&#39;s   that&#39;s   similar   to   what   I&#39;ve   been   messing   around   with   in   uh   yeah.
      </p>

        <cite>Conor</cite>
      <time>16:14</time>
      <p>
          This   episode&#39;s   not   out,   but   the   the   one   unreleased   episode   is   basically   Bright.   I   mean,   all   the   listeners   have   heard   it   now   if   they&#39;re   listening   to   this   one,   because   it   was   like   two   episodes   ago   now,   but   it&#39;s   Bryce   trying   to   convince   me   that   like   filter   is   broken   for   the   purposes   of   parallelization   and   then   coming   up   with   like   a   new   filter,   and   then   I&#39;m   like,   my   point   is   Bryce,   that&#39;s   not   a   filter,   that&#39;s   a   transform.   But   anyway.
      </p>

        <cite>Bryce</cite>
      <time>16:35</time>
      <p>
          Did   we   talk   in   that   episode   about   the   my   my   spaces   idea?   Which   is   which   is   solved,   it   tackles   this   problem   of   internal   iteration.
      </p>

        <cite>Conor</cite>
      <time>16:43</time>
      <p>
          You   did   end   up   screen   sharing   because   I   was   asking   for   a   more   motivating   example.   Yeah,   because   your   example   I   said   was   unmotivating,   and   then   we   got   into   an   argument.   You   were   like,   that&#39;s   your   problem,   not   my   problem.   And   I   was   like,   it   seems   like   a   you   problem,   and   then   you   showed   me   a   motivating   example,   and   then   I   said,   Oh,   I   can&#39;t.
      </p>

        <cite>Bryce</cite>
      <time>16:58</time>
      <p>
          So,   Tristan,   tell   me   how   your   model   for   internal   iteration   works.
      </p>

        <cite>Tristan Brindle</cite>
      <time>17:03</time>
      <p>
          Okay,   so   we   have   um   a   function   that   uh   it&#39;s   called   I   called   it   for   each   while,   which   I   don&#39;t   necessarily   think   that&#39;s   a   great   name.   Um   But   the   the   idea   is   that   uh   a   sequence   has   this   fundamental   um   uh   uh   customization   point   that&#39;s   called   for   each   while,   and   you   pass   it   a   predicate,   and   you   say   uh   iterate   all   of   iterate   over   the   sequence   in   the   way   the   best   way   that   you   know   how,   iterate   over   every   element   uh   until   the   predicate   returns   false.   And   at   that   point   it   returns   us   the   cursor   uh   for   the   the   element   that   for   which   the   predicate   returned   false.   And   it   turns   out   that   for   things   like   filter   uh   and   map   and   things   like   that,   and   really   an   enormous   number   of   these   adapters,   you   can   do   internal   iteration   in   a   way   that   is   more   efficient   than   just   stepping   through   and   doing   increment   dereference,   increment   dereference,   uh,   you   know,   etc.   etc.   Um,   and   this   makes   a   real   difference   when   it   comes   to,   although   the   algorithmic   complexity   is   the   same,   it   makes   a   real   difference   in   terms   of   the   generated   code.   Like   the   compiler   can   see   through   this.   Yeah,   this   was   literally   our   discussion   last   episode.
      </p>

        <cite>Conor</cite>
      <time>18:13</time>
      <p>
          We&#39;re   two   episodes   now   for   the   listener.
      </p>

        <cite>Tristan Brindle</cite>
      <time>18:15</time>
      <p>
          Uh   so   for   the   benefit   of   the   part   one   of   the   of   the   of   the   discussion   on   views   filter,   and   then   you   left   me   hanging,   right?   You   were   like,   we&#39;re   just   gonna   go   and   share   the   screen,   and   that&#39;s   the   end   of   the   episode.   So   I   I   have   not   heard   the   conclusion   of   that.   But   yeah.   So   um,   in   particular,   um   one   of   the   the   I   don&#39;t   want   to   call   it   a   problem,   but   one   of   the   things   that   you   have   to   bear   in   mind   with   C   ranges,   and   this   is   true   of   flux   as   well,   uh,   and   Barry   talks   about   this   in   this   this   fantastic   talk,   is   when   you   have   transform   and   then   filter,   then   you   have   this   issue   of   double   dereference   because   you   have   to   uh   when   you&#39;re   filtering,   you   have   to   see   whether   the   element   uh   matches   the   filter.   You   do   that   in   the   the   increment   operation,   and   so   that   requires   dereferencing   the   underlying   iterator,   and   then   when   the   user   comes   to   dereference   your   filter   iterator,   you   have   to   uh   like   again   dereference   the   underlying   iterator.   So   you   get   this   uh   double   dereference   happening   that   doesn&#39;t   occur   in   the   Rust   model,   for   example,   but   there   are   other   uh   equivalent   problems   with   the   Rust   model.   But   um   it   turns   out   when   you   do   internal   iteration,   you   don&#39;t   need   to   do   this   double   dereference,   right?   Um   so   right   away,   you&#39;re   you   know,   that   this   is   a   tremendous   benefit.   And   there   are   a   huge   number   of   algorithms   that   can   be   written   in   terms   of   uh   internal   iteration.   Um   I   I   have   this   idea   for   a   talk   that   I   I   might   flesh   out   at   some   point.   It&#39;s   like   what   is   the   most   powerful   algorithm   in   the   STL?   And   just   to   give   away   the   punchline,   so   uh   my   my   conjecture   is   that   it&#39;s   standard   find   if.   Really?   So   I   think,   yeah.
      </p>

        <cite>Bryce</cite>
      <time>20:04</time>
      <p>
          I   mean,   he   he&#39;s   not   he&#39;s   not   wrong   because   a   find   if   is   essentially   just   a   reduction,   and   the   correct   the   correct   answer   is   a   reduction.
      </p>

        <cite>Conor</cite>
      <time>20:12</time>
      <p>
          I   was   like,   there&#39;s   no   way   Bryce&#39;s   answer   isn&#39;t   std   reduce   or   or   std   accumulator   one. Okay,   so   so   um   Ben   Dean   has   this,   uh   has   a   great   talk   where   he   std   accumulate   an   algorithmic   empire.
      </p>

        <cite>Tristan Brindle</cite>
      <time>20:26</time>
      <p>
          Yes,   yes.   And   he   talks   about   how   you   know   all   the   things   you   can   write   in   terms   of   um   standard   accumulates,   which   is   like   our   funny   way   of   spelling   fold.   Um   but   it   turns   out   that   you   can   write   a   full   you   can   write   um   accumulate   in   terms   of   finding.   Well,   yes,   I   I   guess   they&#39;re   equivalent,   it   depends   if   you&#39;re   happy   to   have   a   stateful   thing   that   you   put.
      </p>

        <cite>Conor</cite>
      <time>20:54</time>
      <p>
          Wait,   wait,   wait.   You&#39;re   saying   you   can   implement   accumulate   in   terms   of   find   if   or   find   if   in   terms   of   accumulate?   You   can   I   think   you   I   think   you   can   do   either.   Well,   what   we   first   what   was   what   we   did.
      </p>

        <cite>Tristan Brindle</cite>
      <time>21:06</time>
      <p>
          But   you   have   to   have   some   way   of   terminate   you   have   to   have   some   way   of   terminating   the   iteration   early.   That&#39;s   the   key,   right?   So   that&#39;s   what   find   if   does.
      </p>

        <cite>Bryce</cite>
      <time>21:12</time>
      <p>
          Yeah,   well,   well,   okay.   So   we   we   we   could   have   a   whole   discussion   here   now   about   uh   You&#39;re   coming   we&#39;re   you&#39;re   coming   back   again,   Tristan,   and   we&#39;re   gonna   have   a   find   if   versus   the   advantages   and   disadvantages   of   uh   of   uh   having   a   a   find   if   that   is   required   to   terminate   early.
      </p>

        <cite>Conor</cite>
      <time>21:27</time>
      <p>
          So   but   what   what   what   was   it   that   you   initially   said   though?   What   would   do   you   said   that   you   can   implement   accumulate   in   terms   of   find   if?   Because   that   one   seems   easier   than   the   other   way   around,   if   the   other   way   around   is   even   possible.
      </p>

        <cite>Tristan Brindle</cite>
      <time>21:40</time>
      <p>
          That&#39;s   so   that   is   what   uh   I   do   in   in   Flux   because   I&#39;m   not   worried   about   parallelism,   which   um   you   know   I   this   is   all   just   uh   Connor.
      </p>

        <cite>Bryce</cite>
      <time>21:49</time>
      <p>
          Are   you   suggesting   that   we   can   implement   find   if   in   terms   of   accumulate? Yes. I   think   you   just   said   that   backwards.
      </p>

        <cite>Conor</cite>
      <time>21:55</time>
      <p>
          No.   Why?   And   why   is   the   what   what   is   the   number   one   reason   that   it&#39;s   trickier?   And   you   Should   know   this   because   I   know   you&#39;ve   tried   this   and   you   literally   DM   me   on   Twitter.   How   do   you   do   this   thing   to   get   around   this?   I   don&#39;t   know.   One   returns   an   iterator   and   one   returns   a   value.   And   trying   to   implement   uh   algorithms   that   return   iterators.
      </p>

        <cite>Bryce</cite>
      <time>22:14</time>
      <p>
          I   don&#39;t   care   about   I   don&#39;t   I   I&#39;m   not   interested   in   the   per   yeah,   I&#39;m   not   interested   in   the   particular   in   the   particulars   of   the   interface.   My   my   my   point   is   that   we&#39;re   we&#39;re   we&#39;re   we&#39;re   talking   about   these   algorithms   in   the   abstract.
      </p>

        <cite>Conor</cite>
      <time>22:26</time>
      <p>
          I   think   when   we   were   spelling   out   std   colon   colon   findif   and   std.   We   were   being   pretty   specific,   Bryce.   Um   but   like   we   will   we&#39;ll   we&#39;ll   table   this   because   this   definitely   could   be   like   a   whole   60-minute   discussion.   But   so   what   you   initially   said   was   that   implementing   accumulate   in   terms   of   find   if   is   basically   what   you   do   in   flux,   and   it   is   your   opinion   that   because   find   if   then   therefore   becomes   the   in   the   hierarchy   of   what   is   built   on   top   of   what,   because   accumulate   is   a   child   of   find   if   find   if   is   the   most   basically   uh   important   or   fundamental   algorithm   that   everything   else   is   built   on   top   of.
      </p>

        <cite>Tristan Brindle</cite>
      <time>23:03</time>
      <p>
          That   is   my   conjecture   until   Bryce   convinces   me   otherwise.   Yes.   So   just   about   every   algorithm,   just   about   well,   a   lot   of   algorithms   that   operate   on   a   single   that   the   the   boil   down   to   some   sort   of   reduce   operation,   or   things   like   uh   all   or   any   and   none   and   all   of   those   um   you   can   you   can   write   in   terms   of   find   if.   So   if   you   can   do   a   find   if   more   efficiently,   um,   for   example,   by   using   internal   iteration,   um   then   that&#39;s   uh   that   that   has   tremendous   uh   benefits   in   terms   of   it.
      </p>

        <cite>Bryce</cite>
      <time>23:38</time>
      <p>
          Well,   I   mean   the   the   in   in   serial   you   always   will   want   to   have   a   specialized   version   of   uh   of   a   find   if   because   you   want   to   do   it   in   early   termination.   But   in   in   parallel,   the   way   that   you   implement   a   reduction   is   um   uh   is   to   just   do   it   with   a   or   the   in   parallel   the   way   that   you   implement   a   find   if   is   just   to   do   uh   uh   a   reduction   at   least   on   something   like   a   GPU.
      </p>

        <cite>Tristan Brindle</cite>
      <time>23:59</time>
      <p>
          Yeah,   for   sure.   I   I   I   mean   it&#39;s   it&#39;s   not   my   not   my   field   of   expertise,   but   the   the   yeah.   One   day   perhaps   we   will   look   I&#39;ll   I&#39;ll   look   at   a   parallel   version   of   flux,   but   uh   many   years   from   now   probably.   I   need   to   get   the   serial   version   working   first.
      </p>

        <cite>Conor</cite>
      <time>24:13</time>
      <p>
          So   what&#39;s   interesting   is   that   um   you   probably   I&#39;m   not   sure   if   you&#39;ve   even   seen   uh   I   think   you   have   seen   the   talk,   but   at   the   end   of   my   intuition,   algorithm   intuition   talk,   I   present   this   table,   and   I   present   find   if   and   accumulate   as   like   two   of   the   most   important,   but   the   stat   the   distinguishing   difference   is   that   accumulate   is   a   reduction   that   carries   state   with   it,   and   a   find   if   is   a   reduction   that   does   not   carry   state   with   it.   And   so   then   what   do   you   do   for   that   then?
      </p>

        <cite>Tristan Brindle</cite>
      <time>24:46</time>
      <p>
          Do   you   have   like   a   uh   So   okay,   so   you&#39;re   absolutely   right,   and   in   this   standard   model,   you&#39;re   not   actually   allowed   to   pass   uh   the   I   can&#39;t   remember   the   exact   term.   It&#39;s   a   quote   uh   anyway,   you&#39;re   not   allowed   to   pass   a   stateful   thing   to   find   if.   So   we   have   to   slightly   for   in   in   flux,   we   slightly   uh   um   weaken   this   requirement   to   allow   it.
      </p>

        <cite>Bryce</cite>
      <time>25:08</time>
      <p>
          And   you&#39;re   giving   me   a   hard.
      </p>

        <cite>Conor</cite>
      <time>25:11</time>
      <p>
          He&#39;s   doing   it   in   flux,   though.   We   were   talking   about   the   standard   library.
      </p>

        <cite>Bryce</cite>
      <time>25:14</time>
      <p>
          I   I   I   I   understand,   but   we   were   having   that   was   a   different   conversation   than   the   conversation   we   were   having   now.
      </p>

        <cite>Tristan Brindle</cite>
      <time>25:20</time>
      <p>
          Yeah,   so   so   the   basically   all   of   the   functional   objects   that   you   ever   pass   to   almost   all   of   the   functional   objects   you   pass   to   standard   library   uh   algorithms   have   this   requirement   that   they   give   you   the   same   answer   given   the   same   input.   Which   is   not   quite   the   same   thing   as   being   stateless,   like   you&#39;re   you&#39;re   allowed   to   have   side   effects,   right?   But   they   can&#39;t   give   you   the   however   many   times   you   call   them,   they   have   to   give   you   the   same   answer.   Uh   if   we   slightly   weaken   that,   or   not   slightly,   if   we   just   if   we   weaken   that,   um   then   you&#39;re   allowed   to   pass   a   stateful   thing   into   this.   That&#39;s   why   I   call   it   for   each   while   and   not   um   and   not   find   if,   because   it&#39;s   it&#39;s   more   akin   to   for   each   than   um   than   the   strict   stricter   requirements   that   are   on   find   if.
      </p>

        <cite>Conor</cite>
      <time>26:06</time>
      <p>
          Oh,   so   this   weakened   find   if   is   what   is   what   is   for   each   while.
      </p>

        <cite>Tristan Brindle</cite>
      <time>26:12</time>
      <p>
          Yeah,   exactly.   And   I&#39;m   I&#39;m   you   know,   if   someone   can   come   up   with   a   better   name   than   than   for   each   while,   then   uh   then   uh   you   know,   let   me   know.   Naming   is   not   something   I&#39;m   good   at.
      </p>

        <cite>Conor</cite>
      <time>26:25</time>
      <p>
          You   know   what&#39;s   great   at   naming?   Chat   GPT.   Uh   oh,   oh   well.
      </p>

        <cite>Bryce</cite>
      <time>26:35</time>
      <p>
          I&#39;ve   drunk   the   Kool-Aid   in   the   past   week.   It&#39;s   gonna   be   a   whole   separate   episode.
      </p>

        <cite>Conor</cite>
      <time>26:40</time>
      <p>
          Yeah,   we&#39;ll   we&#39;ll   we&#39;ll   table   that   as   well.
      </p>

        <cite>Bryce</cite>
      <time>26:42</time>
      <p>
          But   uh   yeah,   for   each   while   actually,   well,   there&#39;s   uh   here,   I&#39;m   gonna   I&#39;m   gonna   link   a   relevant   a   relevant   tweet.   Um   well   but   before   I   go   there,   before   before   we   go   there,   let   me   let   me   show   uh   Tristan   the   uh   uh   this   is   my   multidimensional   uh   iteration   thing,   um   which   is   that   you   have   this   notion   of   a   space,   which   is   essentially   just   a   collection   of   ranges,   and   then   um   you   know   you   have   these   like   space   aware   algorithms   that   um   uh   recursively   unpack   them.   Um   and   one   of   the   key   insights   that   I   had   was   that   if   each   inner   loop   needs   to   have   the   value   of   the   induction   variable   at   the   outer   loop.   So,   you   know,   if   you   have   if   you   have   a   an   a   nested   loop   of   you   know   k   where   you   iterate   over   k   and   uh   where   you   where   you   like   the   first   the   first   for   loop   is   a   for   loop   over   some   something   and   it   gives   you   you   know   an   element   k   and   the   second   the   innermost   for   loop   is   uh   an   element   j   when   you   uh   um   when   you   call   this   space   thing   when   you   extract   the   range   from   the   space   thing   in   the   inner   loop,   you   have   to   give   it   the   the   value   of   whatever   element   you&#39;re   at   in   the   outer   loop.   Um   and   that   lets   you   incrementally   build   up   your   position   as   you   go. Yeah. I   did   a   very,   very   poor   job   of   explaining   that,   but   they&#39;re   able   to   look   at   codes.
      </p>

        <cite>Tristan Brindle</cite>
      <time>28:16</time>
      <p>
          I&#39;m   getting   like   eerie,   um   like   uh   just   remembering   uh   university   lectures   about   tensors   and   stuff,   and   um   yeah   so   uh   horrible   flashbacks   to   things   I   didn&#39;t   really   understand   at   the   time.
      </p>

        <cite>Conor</cite>
      <time>28:31</time>
      <p>
          Be   sure   to   check   the   show   notes   either   in   your   podcast   app   or   at   adsphepodcast.com   for   links   to   any   of   the   things   that   we   talked   about   in   today&#39;s   episode,   as   well   as   a   link   to   a   GitHub   discussion   where   you   can   leave   comments,   questions,   or   thoughts   that   you   have   on   this   episode.   Thanks   for   listening.   We   hope   you   enjoyed   and   have   a   great   day.
      </p>