<?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 Matthew Paletta on Medium]]></title>
        <description><![CDATA[Stories by Matthew Paletta on Medium]]></description>
        <link>https://medium.com/@mattpaletta?source=rss-ea25e3a9f50d------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*cy-ACTh-F47sDkV56hVLRA@2x.jpeg</url>
            <title>Stories by Matthew Paletta on Medium</title>
            <link>https://medium.com/@mattpaletta?source=rss-ea25e3a9f50d------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 09:57:38 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@mattpaletta/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[Sticky Wars VI: Return of the sticky note — A Personal Organization System]]></title>
            <link>https://medium.com/@mattpaletta/sticky-wars-vi-return-of-the-sticky-note-a-personal-organization-system-9d4b7c0ece6e?source=rss-ea25e3a9f50d------2</link>
            <guid isPermaLink="false">https://medium.com/p/9d4b7c0ece6e</guid>
            <category><![CDATA[system]]></category>
            <category><![CDATA[new-year]]></category>
            <category><![CDATA[self-improvement]]></category>
            <category><![CDATA[organization]]></category>
            <category><![CDATA[personal-growth]]></category>
            <dc:creator><![CDATA[Matthew Paletta]]></dc:creator>
            <pubDate>Fri, 06 Jan 2023 20:38:00 GMT</pubDate>
            <atom:updated>2023-01-06T20:38:00.517Z</atom:updated>
            <content:encoded><![CDATA[<h3>Sticky Wars VI: Return of the sticky note — A Personal Organization System</h3><p>It’s the start of a new year. I wanted to do an update to my last post describing my <a href="https://medium.com/@mattpaletta/sticking-with-it-a-personal-organization-system-2b1c5b262c6c">sticky note organization</a> system from last year.</p><h4>System Updates</h4><p>Early on last year, I felt that my wall of sticky notes had become just a giant pile (wall) of things I had done. But everything had the same weight, or importance. I did not feel this was an accurate representation of my life.</p><p>I started using big sticky notes to write the things I was especially excited about or I had a lot of fun at. Things that were outside of my normal routine. I wrote big sticky notes about doing a 10km run with a friend. I wrote one about seeing my parents. I wrote one about taking a cooking class to learn how to make donuts. I wrote one about watching the Apple conference.</p><p>On each of the big sticky notes, I made sure to write down what it was in big bold letters, the date(s) it took place, and any people that were there with me.</p><p>For me, I really liked having the big stickies. There weren’t that many of them, especially compared all of the small routine sticky notes. But isn’t that how life works? In between all of the taking a shower, going for a run, cooking dinner, are some memories that you look back on that make you happy.</p><p>The original idea of this is shown in this short film. Search “Is the jar full?” for other articles on this idea.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FSqGRnlXplx0%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DSqGRnlXplx0&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FSqGRnlXplx0%2Fhqdefault.jpg&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/cca28967d04e2f16eb4dec0b0802671d/href">https://medium.com/media/cca28967d04e2f16eb4dec0b0802671d/href</a></iframe><p>If you ever figure out how to make as many of those memories as showers (and please keep showering regularly), please let me know! Maybe even write a book.</p><p>Also as a minor update, in about October I ran out of sticky notes and never bought more, so my wall of stickies has remained static since then.</p><h4>Goals for next year</h4><p>This year was a really good year for me. I entered a new relationship and am trying to get better at taking time for myself. A few goals for next year include:</p><ul><li>Be more consistent with exercise</li><li>Be more consistent with my sleep schedule</li><li>Continue to plan things to do for myself regularly out of the house (going to events, talks, meetups, etc.)</li><li>Continue to dedicate time to my projects</li></ul><h4>Reflection</h4><p>Over the last year I think I’ve shifted from being very (perhaps too) planning-oriented to trying to be more relaxed, and more flexible. That doesn’t mean there isn’t planning, just less rigid. There’s still a lot I want to do, it just feels less single-mindedly focused on my projects and more balanced. Sometimes I miss feeling like I’m making as much progress in a given month as I used to on my project(s) but I’m also really enjoying all of the other things I’m now also doing that I wasn’t before.</p><p>In light of this more flexible lifestyle, I’m thinking I might stop the sticky note wall this coming year. I think for me it has served its purpose. I like the ‘big things’ part, and I might continue to do that. But I think I’m going to stop writing out my to-do tasks on individual post-its and instead write out lists on paper, in a calendar, or in the reminders app on my phone.</p><p>Thank you very much for reading. I wish you a great year!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9d4b7c0ece6e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Building a database in Metal]]></title>
            <link>https://medium.com/@mattpaletta/building-a-database-in-metal-b1b7cf280ba2?source=rss-ea25e3a9f50d------2</link>
            <guid isPermaLink="false">https://medium.com/p/b1b7cf280ba2</guid>
            <category><![CDATA[cpp]]></category>
            <category><![CDATA[database]]></category>
            <category><![CDATA[metal]]></category>
            <dc:creator><![CDATA[Matthew Paletta]]></dc:creator>
            <pubDate>Sun, 27 Nov 2022 20:49:26 GMT</pubDate>
            <atom:updated>2022-11-27T20:49:26.599Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>Overview</strong></h3><p>A few months ago I started working on a prototype of a relational database in Metal. Apple had just released the M1 Max and M1 Ultra a few months prior with as much as 128GB of unified memory (in the Mac Studio).</p><p>I saw this as an opportunity to do something with very heavy processing that required a lot of GPU memory: processing large relational tables on a GPU.</p><p>I was not the first to think about writing a relational database on a GPU. Databases like <a href="https://github.com/BlazingDB/blazingsql">BlazingSQL</a>, a GPU relational database built on <a href="https://github.com/rapidsai">Rapids.AI</a>. Rapids.AI is a Python library from NVIDIA that mirrors the functionality of many popular Python libraries, such as Pandas, but runs the equivalent functions on the GPU. NVIDIA has been investing heavily in the data centre and helping to develop more tools that run on their cards, especially for machine learning and large data processing.</p><p>From watching the Apple conferences lately, I have felt there is a lot of potential performance that isn’t really being used. From what I’ve seen, developers are taking advantage of the new graphics capabilities of the new chips. On the compute side, the demos and open source software built with Metal have been lacking. Apple made a sample project of a particle simulation, I presume to show the equivalent of the CUDA sample. They show how you can use compute in CUDA and rendering in OpenGL on the GPU without having to go back to the CPU in between. The other place that Apple has been using the GPU heavily is for AI tasks. Anytime the Neural Engine does not support an operation in a model, CoreML will automatically fallback on the GPU for more performance. While this is very useful and fascinating, this does not allow the end-developer to really get into the details of GPU programming or hands-on experience with other real-world examples.</p><p>I picked a relational database as I happen to really love databases and have thought about a number of designs for them, some of which I’ve built prototypes for over the years. Relational databases are also interesting since they use strings and null values. Both the AI example and the particle simulator, while very impressive, use only floats and integers.</p><p>The implementation that I built can be found here: <a href="https://github.com/mattpaletta/metaldb">MetalDB Github</a></p><h3><strong>Design ideas</strong></h3><p>I don’t remember if it was right at the beginning or somewhere in the middle of the process, however I was inspired by the documentation from <a href="https://cloud.google.com/bigquery/docs/query-plan-explanation">BigQuery Query Plans</a> which talked about a graph of query stages that make up a query execution plan.</p><p>One of the major design limitations with Metal is that all of the memory has to be statically sized at compile time. This presented challenges because I could not copy a string as I didn’t know how many strings there were in a database row, or how long each string would be at compile time.</p><p>I figured using a prefix sum algorithm to copy all of the data back from the GPU to the CPU in an efficient manner would be simplest if each thread processed one row. I also needed to use the largest available synchronizable block, which in Metal is a ThreadGroup.</p><p>Partially as an optimization, and partially as a personal challenge, I wanted to maximize the amount of work done on the GPU. For those reasons, I opted to start with reading CSV files on the CPU, and doing the CSV parsing on the GPU.</p><p>While implementing, I also wanted to be able to test the database on the CPU so that unit tests could be stepped through in a debugger. For this reason, I setup the build pipeline to have all of my Metal kernels written as headers. As a result I could include them in the Metal kernel files, but also include them in the tests in C++. This design would also allow me to define constants and types in Metal headers and guarantee they were always the same in the C++ code that would call it.</p><p><strong>Background on Threadgroups and Metal concepts</strong></p><p>As background for further ideas and explanation, Metal execution is organized into grids. A grid is a 1D, 2D or 3D group of ThreadGroups. A ThreadGroup is a synchronizable group within that grid. Threads within a ThreadGroup are broken and executed into further groups, called warps.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/837/1*G_AMsEANOt0a4QynPeY6JA.jpeg" /><figcaption>Relationship of Grid, ThreadGroup, Thread, and SIMD</figcaption></figure><p>A thread is the most basic block in GPU programming, and roughly translates to the model of a thread on a CPU core. It is a single, linear, in-order execution of instructions. The thread has registers that it can access directly as well as read and write to shared memory. It is a different memory model than on the CPU, but that is beyond the scope of this article.</p><p>A warp (called SIMD in Metal documentation) is often a group of 16 or 32 threads. The same instruction must be executed at the same time on all threads in a warp, although potentially on different data (SIMD, Single Instruction, Multiple Data). If some of the threads take a different path in the code, all of the threads within that warp must wait for all of the branches to execute serially. This leads to designing GPU code with as few branches as possible, such that you keep all of the threads within a warp busy as much as possible.</p><p>Other systems like CUDA and OpenCL have similar concepts, just with different names.</p><h3><strong>Implementation</strong></h3><p>Link to implementation: <a href="https://github.com/mattpaletta/metaldb">https://github.com/mattpaletta/metaldb</a></p><p>In my opinion, I think it makes the most sense to talk about the implementation in the order of the flow of data through the system. However, this is almost the perfect inverse of how I went about implementing it.</p><h4>Binary</h4><p>The final result that is produced is very simple. It is a binary called metaldb and it just has a main function in it. I made the application very light so that I, as well as others, could reuse the internal libraries easily as part of other libraries and applications in the future.</p><h4>Engine</h4><p>The Engine is where most of the logic of the system is coordinated. The Engine interacts with the QueryPlanner, which is implemented in the QueryPlanner library, as well as the Scheduler , which is responsible for running and coordinating the execution of the generated query plan.</p><h4>Query Parser</h4><p>The Query Parser is the component that is responsible for turning an SQL-like query into an AST that can be more easily parsed<strong> </strong>by the rest of the system.</p><p>This first version of the database does not implement a Query Parser. Instead, I have hardcoded the AST for various queries I want to test. Writing a parser and producing an AST, while it does sound very interesting, is something I’ve done in another project, and was not the focus of this project.</p><p>I also did not intend for this project to be a production-ready database. Therefore it does not need a query parser at this time, but all of the stubs are there for me to implement it at a later point if I so choose.</p><p>In addition to the system accepting query strings, I plan to eventually implement a Dataframe API, similar to Pandas, but in C++. From my point of view, this kind of API would be simpler for other libraries to work with. This also saves the step of the other library having to produce a query string only for it to then be immediately reparsed by the parser. This Dataframe API is also left as future work.</p><p>As a test dataset I first used the publicly available <a href="https://gist.github.com/netj/8836201">Iris dataset</a>. I chose this dataset because it is relatively small, in CSV format, and mostly numbers, with no null values.</p><p>After I got that dataset working, I wanted to try a much larger dataset with multiple files. For this I used the <a href="https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page">New York Taxi Dataset</a>. This larger dataset proved some interesting challenges I did not expect, more on this later.</p><h4>Query Planner</h4><p>After the Query Parser has generated the AST, the next component is the Query Planner. This is responsible for turning the AST into an optimized execution plan.</p><p>The first step of making an optimized execution plan is making a plan at all. Inspired by the <a href="https://cloud.google.com/bigquery/docs/query-plan-explanation">BigQuery reference</a>, I liked the idea of breaking an execution plan into a graph of “Stages”. In BigQuery, each stage is made up of one or more steps. Each step could be a read or a write, an aggregate or a join, etc. I didn’t quite want to go down to the granularity of steps, but I have a similar concept, I call a “partial”.</p><p>To go from an AST to a graph of stages, I first list the files on disk for the table(s). Next I go to the leaves of the AST and for each of them, I produce a new stage that will read that file.</p><p>As I walk back up the tree, I decide if I will create a new partial as part of the existing stage or create a new stage. The key point is when I have to go from the GPU to the CPU or vice-versa for a step, I create a new stage. This means as much data can be processed on the GPU while minimizing transfer times between the CPU and the GPU. This is especially relevant for devices that do not have unified memory.</p><p>Every stage has a singular list of partials to run. These will later get translated as instructions to the GPU within that stage, as we’ll explore more in the section about the scheduler.</p><p>Every time I create a new stage, I insert a “Shuffle Instruction”, which tells the GPU to copy the information back to the CPU.</p><p>In the future, I would also write an optimizer that could rewrite queries to minimize the amount of data read from each file and copied back to the CPU after being read.</p><h4>Scheduler</h4><p>The scheduler is responsible for the parallel execution of the query. I was tempted to write my own multithreaded library to do this. I ended up writing my implementation on top of <a href="https://github.com/taskflow/taskflow">TaskFlow</a>, an open-source C++ task graph library.</p><p>At a high level, the creation of the task graph follows the graph of stages. Each stage is a task in the graph, and depends on its children.</p><p>Within a stage, each partial, the list of steps to be done on either the CPU or the GPU, are expanded in order. As each partial is being registered, it has several tasks within the task graph it can hook into.</p><p>The main task that can be hooked into, is the encode task of the previous task. The partial should create a new task that is dependent on the parent partial encode task. It uses the Encoder passed in to encode itself into a serialized representation that can be sent to the GPU. For most tasks, this is all that is necessary and the implementation of the partial is on the GPU in Metal.</p><p>The other task that is available is the work task. This exists in case a partial wants to override something about how the work gets executed for that partial instead of the default behaviour.</p><p>Most tasks read the buffers from one or more child stages and write to their output buffer. The read instruction is unique because it has to read from disk, not from child buffers.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fE4WrtEdH2SpUshu-TFqjA.jpeg" /><figcaption>Example TaskFlow graph for MetalDB</figcaption></figure><p>The read instruction sets up a chain of tasks that read the CSV file (the only file type currently implemented) it has been assigned and reads it into a buffer. As it is reading into a buffer, it keeps track of the offset of the current row and stores them as part of the RawTable object, described below.</p><p>Once the file has been read, the GPU is free to start processing the rows. The design of the database calls for one thread per row. Metal happens to have a limit of how many threads can be assigned per ThreadGroup. Therefore we first split the rows into multiple buffers that will each be sent off to the GPU independently.</p><p>TaskFlow allows dynamic subtasks within a task. When I get the RawTable, I query the number of threads that Metal allows me schedule and break up the original rows into chunks of that size.</p><p>Each chunk is then sent to the GPU in parallel.</p><p>After all of the chunks have each been processed, I run a merge task that copies all of the OutputRow objects from the GPU and merges them into a single giant OutputRow so that the next stage can read them together.</p><p>In the future, I would like to optimize the splitting of multiple batches. As soon as the batch has been split it can be sent to the GPU., As soon as that chunk comes back, it can be copied into the final buffer while the other tasks are processing asynchronously.</p><p>In addition, I would like to free the original RawTable once all the rows have been split into chunks, which each store a copy. Additionally, I should be able to free the output buffer from the chunk as soon as it has been copied into the final buffer, reducing the total amount of memory required.</p><h4><strong>ParseRow Instruction</strong></h4><p>The ParseRowInstruction starts out with a simple premise. Given a list of indexes for the start of each row and information about the number of rows and the types of the columns, parse out the values for a particular row, cast to their correct types.</p><p>The simplest column type is a string. For row <em>N</em>, we can jump to the beginning of that row by looking up its index, which the CPU stored when we read the file from disk. We can then get a pointer to that index. This is the beginning of the row. The end of any column is the position before the next comma (marking the next column) when we move forwards one character at a time, or one before the beginning of the next row (if it’s the last column of the row), or one before the end of the buffer (if it’s the last column of the last row).</p><p>The instruction reads every column as a string first. It parses out a column exactly as described and reads it as a string, character by character. Now to read the next column, we start at the beginning of the row. When we get to the first comma, we mark that as the beginning, and go until the comma after that. The process repeats for subsequent columns.</p><p>If we have an integer, we pass the pointers to the beginning and end of the string to a custom stoi function. This is similar to the one from the C standard library, which converts the string to an integer representation. I wrote my own version of stof as well.</p><p>As you can imagine, reading every column from the beginning of the row each time is very slow and there is a lot of duplicate work. We can do better, much better.</p><p>The first realization in optimizing finding the beginning of the column is, that there is often a low number of columns. I’ve chosen 16 as an arbitrary number of columns to cache.</p><p>With this first level of cache, if I am reading a column within the first 16 columns, I try and read the previously cached pointer for that column. If it’s not null, I already have the value. Rows are immutable, so the pointer must be valid, and the process is finished!</p><p>If the pointer is null, I can iterate over my cache backwards from the 16th column index until I find a column previously cached or I get to the first entry.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/836/1*2MdxirNplYI-C2fsByx1mg.jpeg" /><figcaption>Example steps of fetching a column using the cache</figcaption></figure><p>From wherever I stop, I can iterate through the row the naive way, one character at a time. Every time I find a comma, I store the pointer to the beginning of that column in my cache so subsequent queries can jump straight there.</p><p>This means that random access to the first 16 columns should be basically free as it becomes a straight pointer lookup. This excludes the first access, which is <em>O(n)</em>.</p><p>What about rows with more than 16 columns? I already know where the 15th column is (starting from 0), so I can jump straight to the 15th column and then interate the naive way after that. If I don’t know where the 15th column is, I can quickly calculate and cache it.</p><p>This pretty good, except there is one more optimization that can be done. The other realization is that within the <em>ParseRowInstruction</em> as it is constructing the output row, it accesses the columns in order. In addition to the fixed size random cache for the first 16 columns, we can keep an additional pointer which stores the beginning of the last column accessed, and the index of that column. This allows a straight pointer lookup for sequential accesses for any number of columns, without having to store an infinite number of pointers, like in the first level of caching. Of course, these two caching layers work together. As we update the first 16 values, we also update the last_accessed pointer.</p><p>When running on the GPU, every thread is responsible for a single row. So every thread has its own multi-layer cache as described. The cache also keeps track of which row we are caching. If it is different from the one requested, we reset the cache, so we know the cache is always relevant. It’s possible to expand this to cover use cases of reading multiple rows or sharing the cache between threads, but this was beyond the scope of the initial implementation.</p><h4><strong>Projection Instruction</strong></h4><p>The ProjectionInstruction is very simple by comparison. It is given a list of column indexes to fetch. It creates a new TempRow object and copies those columns from the last TempRow, updating the metadata in the new TempRow object.</p><h4>Filter Instruction</h4><p>The basic implementation of the FilterInstruction is designed around evaluating some row against some expression which returns either true or false .</p><p>This was implemented as a stack-based virtual machine. The allocation of the stack is fixed at compile time and therefore always allocates its maximum size.</p><p>The stack was somewhat interesting to implement. I opted to design the bytecode for the VM to include the types as well as instructions for casting one type to another. The implementation of the stack allows heterogenous data, but the caller is responsible for providing the types.</p><p>In a normal stack, you may create boxes for an object, and the box will store what type the thing is as well as a pointer to the thing. In this case, the compiler (not yet implemented) is responsible for writing the bytecode to include all of the casting necessary. This allows the runtime to push an integer onto the stack, which is x bytes, and later when it goes to read an integer, it can pop x bytes off the stack and it get the same integer. No boxes or dynamic casting required. This does put the onus on the compiler to get all of the types correct, but that is left for future implementation.</p><h4>Output Instruction</h4><p>The OutputInstruction is used to combine all of the data from the individual threads within the ThreadGroup and remove all of the duplicate data that each individual thread needs, but that only really needs to be copied once to the CPU, and efficiently put it into one big buffer.</p><p>The first step is every row (every thread) calculates its own size. Then we run a prefix sum of the sizes. This gives us an index where we know we can start writing our data.</p><p>Prefix sum is an algorithm often used in GPU computation where given an array of integers, returns a new array where for every index <em>i, </em>contains the sum of all items less than <em>i</em>. If the sum includes item <em>i</em> for position <em>i</em>, it is called an inclusive sum, otherwise it is called an exclusive sum. I used an exclusive sum for my implementation.</p><p>Before we can start writing data, the threads must coordinate writing the header of the OutputRow. To do this, the first row, responsible for writing the header, also adds the header size to its own size. After we do the prefix sum, we also run a reduce on the row sizes so the first thread is able to write the total number of bytes to the header.</p><p>Once that completes, each row can jump to its offset from the prefix sum output and copy its bytes into the buffer starting at that point in parallel, and we are guaranteed there won’t be any collisions.</p><h4>TempRow</h4><p>The TempRow is the data structure that is passed around while the data is being processed in Metal. Ideally, we would allocate a resizableTempRow on the heap, to minimize memory footprint, but because Metal does not support dynamic memory allocations. Every TempRow is a buffer of a fixed size. I have chosen it to be 1024 bytes, or 1 kilobyte. The first section of the TempRow is a header, followed by the data.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RQSDKmM10PMIZECqA9wCkg.jpeg" /><figcaption>Layout of a TempRow</figcaption></figure><p>The first value in the header is its length. This is important because the data begins immediately after the header, and the header is a variable size depending on the number of columns and their types.</p><p>The next byte is the number of columns. Since this is only 1 byte, the maximum number of columns is therefore 256. I feel this is plenty for most use cases.</p><p>The next N bytes are the column types. Columns can be one of: Integer , Float , String or their nullable equivalents. A boolean value is simply expressed as an integer.</p><p>An integer and a float are always a constant size, so we do not have to store their size in the header, unless it is a nullable column. By contrast, a string can have any number of characters. Therefore we store the size of all of the variable length columns (strings and optional columns) in the subsequent bytes. Again, since the size of a column is only 1 byte, the maximum length of a string is 256 characters.</p><p>After the header, all of the data for the columns are appended one after the other.</p><p>In order to make the construction of TempRow simpler, there is a helper class TempRowBuilder where the caller can write all of the column types and sizes, etc. into separate arrays. The TempRow can then be trivially constructed from the builder by copying in the values.</p><p>The data from the columns can then be appended in order. There are helper methods to assist with copying in strings, integers, and floats, and writing them byte by byte.</p><p>When the next method then goes to read the TempRow , there are helper methods that read from the header to determine the start and end indexes in the buffer for that column, and cast the bytes back into the appropriate type. The caller is responsible for querying the ColumnType of the column they are interested in, before reading it as that type.</p><p>Because the TempRow reads all of data directly from a fixed sized buffer, it could be trivially adapted to a constexpr class for other applications.</p><h4>OutputRow</h4><p>The OutputRow is created by the OutputRowInstruction (described above) and serves the purpose of moving multiple rows around that share the same schema. It would be wasteful to copy all of the individualTempRow objects directly because every row has the same schema, so there is a lot of duplicate metadata. Instead, we copy all of the data into a singular structure such that we can copy it into separate TempRow objects if needed later, or split it into two or more OutputRow objects if needed.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*uS-bjRxO_9IySXK0l80O7A.jpeg" /><figcaption>Layout of an OutputRow</figcaption></figure><p>Similar to the TempRow , the OutputRow has a header definition, though it is slightly different from the TempRow . The first value as explained earlier is the size of the header, but this value is larger, with 2 bytes allocated instead of 1. The next value is the number of bytes in the OutputRow , and this is a 32-bit unsigned integer. After this is the number of columns, and this is only a single byte. Followed by the column types, similar to the TempRow .</p><p>After the header, all of the data is appended. Since the OutputRow is always constructed from one or more TempRow or from another OutputRow , we can compute the data size of every row in parallel using the prefix sum algorithm, and write into the data buffer in parallel.</p><p>When running in Metal, the OutputRow is statically allocated to be a fixed size of 1,000,000 bytes. On the CPU, we can be more efficient and use a std::vector to only allocate the amount of space we need.</p><p>In order to better faciliate every thread reading and writing the OutputRow in parallel, instead of the sizes of variable size columns being written in the header as they are in the TempRow , they are instead prepended to the data for that column per row. So for example, a row with 2 integers followed by a string of 3 characters “abc”, would have the format: &lt;integer&gt;&lt;integer&gt;3abc . The reader of the OutputRow (currently only implemented on the CPU) knows that the column is a string, and can therefore jump to the beginning of the string to read its contents. The sizes of each row are not written to the OutputRow . Instead, the reader iterates through the buffer and records the start of every row and the sizes of every variable size column for every row. This was done to save space, but could be optimized to be written into the header or per row, such that reading the OutputRow is more efficient and therefore faster. The details of reading, splitting and merging OutputRow objects on the CPU was briefly discussed earlier in the section about the Scheduler .</p><h3><strong>Future work</strong></h3><p>I worked on this project as an experiment to see if it was possible. There are many things that I would have liked to implement, if I was going to make it production-ready, or even just spend more time on the prototype than I have.</p><h4>That one bug</h4><p>The first issue I would love to solve is (what I believe to be a bug in Xcode 13), where multiple threads are getting assigned thread 0 within a ThreadGroup. Let me know if you have any ideas. This causes multiple threads to try and write the header. This results in the header getting partially squashed with data, depending on the ordering of the threads. I tried to google about it, but couldn’t find any sources that were particularly helpful. I think it had to do with the amount of the memory I was trying to allocate to each thread. Unfortunately Apple’s official documentation doesn’t say anything about that that I could find.</p><h4>Query Engine + Parser</h4><p>The next big task is implementing a parser and a query engine so the database can accept SQL-like queries and turn them into query plans and execute them. This task also involves implementing a DataFrame API, or writing in multiple formats to disk, to be consumed by other libraries and programs.</p><h4>Join + Group By</h4><p>Expanding on the SQL-spec, it would be fun to be able to compute a join and a Group By clause. I thought the naive way to implement a join is to compute each raw row on the GPU in parallel, and then do a hash-join on the CPU, once per chunk. However, it may be more efficient instead to figure out a way to instead submit one chunk from 2 different tables you want to join at the same time, and have the GPU return the joined rows.</p><p>For the Group By, you could either do it on the CPU, or perhaps doing a partial aggregation on the GPU. Or you could do some combination whereby you do the initial raw processing on the GPU, and then have a different kernel you execute where given a set of rows, computes the group for each row within the set. This would allow you to quickly bucket rows on the CPU where you could allocate more data to hold the rows, while taking advantage of the parallel nature of the GPU to compute groups in parallel.</p><h4>Distributed System</h4><p>If this system is going to be used in production, it likely needs to be able to take advantage of multiple machines. I could imagine a heterogeneous network of Apple (and non-Apple) connected devices working together. Imagine an iPhone as the host controller sending out commands to the other machines, and a group of iPads that each do processing on the data they have locally and sending processed rows back to the central controller. Alternatively, perhaps you have a cloud deploy running the same code on the CPU in an AWS lambda instance, or across multiple GPUs with a Mac Pro server on premise. All of these systems could work together to give you very quick responsive access to very large datasets with devices that (I feel) have a lot of untapped processing power still available.</p><h4>Reduce Memory Footprint</h4><p>As another optimization, especially since I want this to run on any device that runs Metal, it would be nice to keep the memory footprint as small as possible such that we can maximize the resources on the device for the end-user application that is running. Ideally, we should be able to read a chunk of a file from disk into memory, turn it into a buffer to send it to the GPU, and then free that chunk of memory. I tried to design the system that way by using shared_ptr , such that I would have a reference-counting memory allocation system for buffers. However I found in practice that since the task library I was using didn’t know if it needs to re-run the task graph with multiple inputs, the library did not free the lambda capturing the reference to the buffer as it went. This means that the shared_ptr that was captured by the lambda is still referenced, and therefore does not free its memory until after the task graph is destroyed, which only happens when the entire graph finishes executing.</p><h3>Conclusion</h3><p>Overall I had a lot of fun working and thinking about this project. It was very different from many of the other projects I’ve done. I hope you enjoyed reading this article. My full implementation is linked at the top of this article. If you have any comments or ideas of things you liked or would do differently, please feel free to contact me. Thanks!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b1b7cf280ba2" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Sticking With It — A Personal Organization System]]></title>
            <link>https://medium.com/@mattpaletta/sticking-with-it-a-personal-organization-system-2b1c5b262c6c?source=rss-ea25e3a9f50d------2</link>
            <guid isPermaLink="false">https://medium.com/p/2b1c5b262c6c</guid>
            <category><![CDATA[tasks]]></category>
            <category><![CDATA[system]]></category>
            <category><![CDATA[todo]]></category>
            <category><![CDATA[goals]]></category>
            <category><![CDATA[love-yourself]]></category>
            <dc:creator><![CDATA[Matthew Paletta]]></dc:creator>
            <pubDate>Fri, 31 Dec 2021 13:32:50 GMT</pubDate>
            <atom:updated>2021-12-31T13:32:50.087Z</atom:updated>
            <content:encoded><![CDATA[<h3>Sticking With It — A Personal Organization System</h3><p>If you ever walked into my bedroom or have been on a Zoom call with me in the past few years, you would see a wall that looks something like this:</p><figure><img alt="The wall of sticky notes in my bedroom." src="https://cdn-images-1.medium.com/max/1024/1*cSHrqpE0FMbS0zxQOICH3g.jpeg" /></figure><p>I’ve been asked out this wall many times, as you can likely imagine, and when I’ve explained my system to people, I generally hear positive comments about it, so I thought I would share it with you. Here is my system of sticky notes that I use to organize my life and other positive benefits. I hope you find this useful, or inspires you to find a system that works for you.</p><h3>Overview of the Sections</h3><p>I know even before writing this post that it will be quite long, so here is a table of contents (of sorts) so that you can search for the section(s) that are most interesting &amp; relevant to you.</p><h4>Ikigai</h4><p>Finding my overall life purpose. Overarching goals, very abstract.</p><h4>The TODO List</h4><p>The system of tracking the things that I have to do in the near to short term future.</p><h4>The Done Wall</h4><p>Using the things I’ve completed as motivation to do future things.</p><h4>Uncomfies</h4><p>Taking things in life that make me uncomfortable and turning them into opportunities for celebration and growth, at my own pace.</p><h4>Single Matt things</h4><p>Figuring out the things <em>I</em> like to do, what makes me tick, what do I like, what do I not like, etc. Despite the name, I apply this in relationships as well as while I’m single.</p><h4>Start, Stop, Continue</h4><p>Taking time to step back from the day-to-day tasks and look at what’s working and what’s not. This is a concept I borrowed from the software world.</p><h4>Quotes</h4><p>Finding and putting up inspirational quotes that resonate with me.</p><h4>Bonus section: Love Letter &amp; Year In Review</h4><p>I decided to include this section because I think it ties in nicely with the other sections, even if it’s something I do once a year vs. every week or every day.</p><p>This section has two main underlying principles:</p><p>A) Love yourself as you love others, put in practice.</p><p>B) You are a different person (good + bad) than you were a year ago. You cannot determine where you want to go if you do not acknowledge where you were.</p><h4>Recommended Reading</h4><p>If you want to read material I was inspired by, or others explaining similar concepts that I’ve tried to put in practice, I have included a list of other resources to check out.</p><h3>Ikigai</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*DLgvAlKwRCCoTDlk4qOtEw.jpeg" /></figure><p>An Ikigai (pronouced icky-guy) [my new favourite word], is a Japanese concept that is described as the overlap between your passions, your values, your profession, and your vocation. It is often associated with finding your purpose. The term roughly translates to “the reason you wake up in the morning.”</p><p>In the book, The Happiness Equation (linked at the bottom), the author goes into more depth of what an Ikigai is, and the benefits of having one.</p><p>In the spirit of transparency, my current Ikigai is two-fold:</p><p>A) Change the world</p><p>B) Be a person</p><p>Let me explain. Part A means changing the world, specifically for the better. Not just for myself, but for everyone around me + nature. I don’t know how I am going to do that yet, but that’s the moonshot goal. Part B is mostly a condition on part A.</p><p>I have read about numerous cases in history where individuals, or groups, did amazing things, and did change the world for the better in some form or another, but often at the cost of their own health or personal relationships. I included a part B in my Ikigai because I want to do part A, but I am unwilling to ignore the self. This includes taking care and spending time with loved ones around me, being kind to strangers, being kind and taking care of myself, etc.</p><p>I like having an Ikigai because it provides an overarching goal for all of the other systems (described below). I purposely made mine so abstract that the <em>way </em>I define success or even how I achieve it can change drastically, without having to change the goal. The other thing, in case it has to be mentioned, is that it’s <em>your</em> goal, so you’re free to change it at any time as you see fit.</p><p>You can see in the photo at the beginning of this post that my Ikigai is the one sticky note by itself on the wardrobe. It is at eye-level when laying in bed so it is the first thing I see when I get up in the morning.</p><h3>Active TODO List</h3><p>Most days after work, I plan my evening. Every Saturday morning, I plan what I am going to do that weekend. I find that by having a list at the beginning of the day, I’m better able to prioritize the things I have &amp; want to do, and not spending time on things to fill time when I am bored, that retrospectively, I don’t really want to spend my time doing. One of these things for me, is spending too much time on social media, as an example.</p><p>For every task I have or want to do, I write it on a sticky note, and I stick it to my dresser. Some tasks are really small, some are larger. Here are some examples of the things I write down:</p><ul><li>Go for walk</li><li>Read book</li><li>Grocery shopping</li><li>Make dinner</li><li>Hangout with &lt;friend&gt;, 2pm</li></ul><p>I take the time to write down the small tasks, because I sometimes feel overwhelmed with all the small things that I have to do. By writing them down, I can see what they all are, and I can prioritize them as I go. Writing down the small tasks doesn’t mean you shouldn’t write down the big tasks too, there will just be less of them.</p><p>Sometimes, one task depends on another task. For example, making dinner requires going grocery shopping first. For these tasks, I write them on separate sticky notes, and I put the “Grocery” sticky on top of the “Making dinner”. This means that I have now automatically filtered out all the tasks that I can’t do yet, and I don’t have to think about them, but I know they’re there.</p><p>My sticky note wall has different colours. Sorry to disappoint, but the colours don’t mean anything (in my system), I just use one stack of post-it’s until I finish it and then move on to the next colour. Feel free to experiment with different colours if that makes sense for you.</p><p>Side Note: It has been pointed out to me that sticky notes aren’t great for the environment. In some cities, you cannot recycle them. In consideration of the environment, I recommend buying eco-friendly sticky notes if possible. If you can’t recycle them, it turns out you can compost them. It’s worth checking with your local recycling system if they take mixed paper, as the best option is to recycle them.</p><h3>The Done Wall</h3><p>When I’ve finished a task on a sticky note, I put it up on the wall. I put them up instead of recycling them straight away because it’s something to look at.</p><p>I find for myself, there are some days where I’m having a lazy day and it feels like “I’ve not done anything”, but now I can’t say that, because I giant unmissable wall of things I’ve done! This also contributes to why I write down the small things I have todo. I think that doing the small things are not things we tell others when we asked “what did you do this weekend?”, but they are part of being a person.</p><h3>Uncomfies</h3><p>I have a column of sticky notes on my dresser with the title “Uncomfies”. This is a list of things that I find uncomfortable doing, or uncomfortable situations. I think that pushing yourself to be uncomfortable, but never unsafe, is generally a good thing.</p><p>Here are some example things that are on my uncomfies list:</p><ul><li>Plans changing at the last minute</li><li>Talking to strangers</li><li>Parties with many new people</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*icPcivkyEYgP62SVo5u78A.png" /></figure><p>I think that by writing them down I’m saying to myself that I don’t have to be comfortable in every situation. When I write them down, I can work towards them, at my own pace. When I find myself in an uncomfortable list, I can think of my list and tell myself “this is an uncomfy, but I’m OK”.</p><p>Since writing them down, there are some uncomfies that I’ve gotten a lot more comfortable with. I have opted to keep them up, because I want it to be a goal list as much as an accomplishments list. Another reason to keep them up is even if the situation affects you less, it is still more likely to affect you when you’re tired or already in a bad mood. I keep them up because that means I can always go “That’s an uncomfy”, rather than a TODO list that you cross off your list. There are no regressions, only good days and bad days.</p><p>I think that your uncomfies can be as public or as private as you like. You might decided to share them with a close friend or partner, or just keep them to yourself.</p><p>I have decided to share mine with close friends. One friend in particular I talk to at the same time every week, and we have been for years. They know that plans changing at the last minute is not something I like very much, but I asked them to sometimes cancel plans at the last minute, or delay by 30 minutes randomly so that I can get more of those situations. I don’t believe I have to wait for them to happen, I think that the more times I do it, the quicker I will become comfortable with it. I recognize that some things will be easier to manufacture situations than others.</p><h3>Single Matt Things</h3><p>One day, I came to the realization that I wanted to figure out who I was as a person, rather than assuming the same things I did yesterday. When I made the list “Single Matt things”, I had just gotten out of a relationship, and wanted to revamp my hobbies. I wanted to figure out what I liked doing as newly single person, hence the name.</p><p>Some examples of <em>Single Matt Things</em>:</p><ul><li>Sing in a choir</li><li>Participate in improv comedy</li><li>Drawing</li><li>Walk around museums by myself</li><li>Go to restaurants by myself</li><li>Rock climbing</li></ul><p>These are just a few of the things, but of these examples, I’m very proud to say I’ve done all of them, and more.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*GANTBoWVIOM2MruaBk2RJg.jpeg" /></figure><p>When I wrote the list, I imagined that some of the things I would do with a future partner and/or friends, if they were interested, but I would first enjoy going by myself and trying new things.</p><p>It turns out that now that I’ve done some of things, I made new friends. Some of them, I’ve continued doing, some of them I decided to reprioritize and put down for the moment. I can still say I did it, and you never know, I can always go back to it.</p><h3>Start / Stop / Continue</h3><p>You’ve already read (or skipped) the section about how I do my active TODO list. In addition, I have 3 separate piles that work a little different, these piles are: Start, Stop, Continue.</p><p>I was first introduced to this concept working as a Software Engineer. At work, we used it as part of our project planning, but I really liked the idea, so decided to adapt it work for my personal life.</p><p>Here’s how it works:</p><p>In the Start column, you write down <em>processes </em>that you would like to start doing.</p><p>In the Stop column, write down processes that you would like to stop doing. The Stop column is optional as every stop can be written as a start with its opposite.</p><p>The Continue column is hopefully the largest pile, and these are processes that you have been doing, that you would like to continue doing.</p><p>I emphasize processes because you have your tasks to do in the TODO list, but this is a the place for a broader view. For example, one of my ‘continue’ is going for a run 3 days a week before work. The accompanying TODO is “Go for run” (and “Shower”) once for each of the 3 days.</p><p>You can make the process as small or as big as you’d like. Generally, I try and make them things that don’t end. For example, planning a trip is a large task, that has many sub-tasks, but I’d rather leave them as just that, a goal with a bunch of subtasks, rather than a ‘process’. By focusing on processes and not tasks, it means that I have overall goals that I can improve in, and write up the tasks to do so as necessary.</p><p>Just because you have written it down, you did it on a sticky note, which means you can decide at any point that what was once important to start, or stop, or continue, is no longer important. That’s part of the reason I do my list on sticky notes, it’s easy to add/remove/update them anytime as I see fit.</p><p>You may have friends, partners &amp; family suggest things that should be on your Start/Stop/Continue. I think you should listen to what they’re saying, but also maintain your own list. I think you will be more likely to succeed in your goals if you have decided <em>yourself</em> that this is something you want to do (or not do).</p><p>Another thing that I’ve found helpful, if I have a bunch of processes I want to start at the same time, I will space them out. I write them down, and put the ‘pending start’ above the ‘start’ column. I know they’re there, but I haven’t committed myself to it yet. I move stickies down from the ‘pending’ to ‘start’ at my own pace, depending on how I feel the current ‘start’ items are going.</p><h3>Quotes</h3><p>I looked on Pinterest looking for quotes that resonated with me, and decided to put them up in sticky notes, of course. I put them behind my computer monitor so I can always see them while I’m working.</p><p>Since I got them from Pinterest, I don’t have the original authors for most of them. Here are some of the quotes that I’ve put up that resonated with me:</p><ul><li>“I am unapologetically myself”</li><li>“Always work on some <em>uncomfortably</em> exciting” — Larry Page</li><li>“Make today <em>ridiculously</em> amazing”</li><li>“Don’t wait for the perfect moment, take the moment and make it perfect”</li></ul><p>At various living situations, I’ve also had words of affirmations that I’ve put on my bathroom mirror to read to myself while I brush my teeth.</p><h3>Love Letter &amp; Year in Review</h3><p>I always heard the phrase “love others as you love yourself”, or “you can’t love others until you love yourself”. I always found it easier to think about how I could love others than loving myself. I think I got to a place where I wasn’t doing things that weren’t loving myself, but also nothing that was explicitly about “loving myself”, at least not in a conscious way.</p><p>Last year was the first time I decided to write myself a love letter. I don’t think there’s any ‘proper’ way to write a love letter. I wrote mine in the style of ‘you like x’, ‘you don’t like y’, ‘you feel strongly about z’, etc.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*jHTVE40ExF-GGpLy" /><figcaption>Photo by <a href="https://unsplash.com/@jannerboy62?utm_source=medium&amp;utm_medium=referral">Nick Fewings</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>It was very emotional for me writing the letter, but I felt amazing after completing it.</p><p>For the past few years I’ve stopped doing New Years resolutions, and opted instead for yearly themes. This year’s theme was working on myself. I’m very pleased to report, that went pretty well.</p><p>Slightly unrelated, over the Christmas break, I’ve started doing a “Year in Review”, akin to a Spotify Wrapped. It could be as detailed or not as you’d like, but I try and write down everything I did that year, and all the ways I think I’ve changed compared to how I was at the start of the year. I think it summarizes the various processes for tracking progress nicely. It also allows me to better adjust my goals for the next calendar year.</p><h4>Recommended Reading</h4><p>Here is a list of reading resources for someone who would like more detail about some of the concepts that I’ve incorporated into these various systems. I have listed them in a recommended reading order.</p><ul><li><a href="https://www.goodreads.com/book/show/22571656-the-happiness-equation">The Happiness Equation (book)</a></li><li><a href="https://autotranslucence.wordpress.com/2018/03/30/becoming-a-magician/">https://autotranslucence.wordpress.com/2018/03/30/becoming-a-magician/</a></li><li><a href="https://www.goodreads.com/book/show/40121378-atomic-habits">Atomic Habits (book)</a></li><li><a href="https://blog.stephsmith.io/how-to-be-great/">https://blog.stephsmith.io/how-to-be-great/</a></li><li><a href="https://www.goodreads.com/book/show/5771014-the-talent-code">The Talent Code (book)</a></li></ul><p>I hope you found this helpful, or at least interesting. Do you have a system that works for you? What do you like about my system? What would you change to make it work for you? Leave it in the comments!</p><p>Have a great year!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2b1c5b262c6c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Graph Multi-Colour(ed) Problem]]></title>
            <link>https://medium.com/@mattpaletta/graph-multi-colour-ed-problem-7aff54539f8f?source=rss-ea25e3a9f50d------2</link>
            <guid isPermaLink="false">https://medium.com/p/7aff54539f8f</guid>
            <category><![CDATA[dfs]]></category>
            <category><![CDATA[colors]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[graph]]></category>
            <category><![CDATA[colour]]></category>
            <dc:creator><![CDATA[Matthew Paletta]]></dc:creator>
            <pubDate>Fri, 05 Jun 2020 22:54:35 GMT</pubDate>
            <atom:updated>2020-06-12T22:00:44.910Z</atom:updated>
            <content:encoded><![CDATA[<p>I’m working on a personal project right now that I’m super excited about, but don’t want to reveal just yet. However, I did want to share one part of it that I found very interesting.</p><h3>Background</h3><p>Before I explain my specific problem, I want to review the classic graph colouring problem.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/440/1*y9hupdG4XQ_xR1WzkZPH3g.png" /><figcaption>Figure 1 <a href="https://en.wikipedia.org/wiki/Graph_coloring#/media/File:Petersen_graph_3-coloring.svg">https://en.wikipedia.org/wiki/Graph_coloring#/media/File:Petersen_graph_3-coloring.svg</a></figcaption></figure><p>In the classical graph colouring problem, you are given a graph with uncoloured nodes (often represented by black), and your task is to colour each vertex in the graph such that no two connected vertices have the same colour. In other words, the two vertices of every edge have different colours from each other. An example of such a graph, after being coloured is shown in Figure 1.</p><p>Graph colouring has applications in everything from creating schedules and time tables to register allocation, to solving sudoku. In each of these scenarios, each ‘state’ is a node in our graph, and the set of graph colouring problems allows us to place restrictions on the properties of each vertex.</p><h3>Background Practical Example</h3><p>For example, in Sudoku, the game rules (9x9) are as follows:</p><ol><li>Each vertical line must have exactly one of every number (1…9)</li><li>Each horizontal line must have exactly one of every number (1…9)</li><li>Each (3x3) box must have exactly one of very number (1…9)</li></ol><p>In order to turn this into a graph colouring problem, we can construct our ‘edges’ such that every square, represented as a vertex, is connected to every vertex in its respective vertical and horizontal line, and its box. Now, we assign every colour in 1 to 9 a unique colour. If we <em>can</em> colour this graph, we have a solution to our sudoku problem! By definition of graph colouring, no two connected vertices can have the same colour, meaning in Sudoku, they’d be the same number, violating our game rules.</p><h3>Problem Description</h3><p>I’m taking a different spin on the problem for my project. Instead of starting with a blank (uncoloured) graph and trying to colour it, I have a coloured graph already, and I want to traverse it in a very specific way. Before I do that, let me explain the properties of the graph:</p><ol><li>You are given a directed graph of coloured vertices (meaning you can only travel in the direction of the arrow)</li><li>There are zero or more <em>green</em> nodes, these are your starting node if they exist</li><li>There are zero or more of any other colour in the graph, including your end nodes (referred to “target nodes”)</li><li>The graph may contain cycles of any size</li><li>There can be disjoint nodes (nodes with no incoming or outgoing edges), these can include starting or target nodes</li></ol><p>You are given the graph (represented as an adjacency list), and a set of zero or more unique target colours. (meaning no duplicate colours in the list)</p><p>Task:<em> to find all of the sub-graphs (represented as adjacency lists) that include one of every target colour, and at least one green node</em></p><h3>Examples</h3><p>Before I delve into my solution, I want to walk through a few examples so we’re on the same page.</p><p>I tried to go through these solutions carefully, but if I made a mistake, feel free to leave a comment down below. You can also see the ‘code’ version of these examples here: <a href="https://github.com/mattpaletta/coloured-graph-traversal/blob/master/test/test_blog_examples.py">Blog Example Tests on Github</a></p><p>I challenge you to try and think about the solution to each example before you scroll down and I show you mine.</p><p><strong>Example 1</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/434/1*NBn2518-m6AMNKehE2iPUQ.png" /><figcaption>Example 1: Input</figcaption></figure><p>Our input, represented as code, would be as follows:</p><pre>graph = {<br>    green: [red, black]<br>    black: [],<br>    red: []<br>}<br>target_colours = [red]</pre><p>There is only one solution for this input, presented below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/278/1*M9iRc0TJXFcp3kKBLAjJ7Q.png" /><figcaption>Example 1: Solution</figcaption></figure><p>We discarded the black node, and simply left the path from the green to the red node.</p><p><strong>Example 2</strong></p><p>Consider when there is no path from our staring nodes to our staring target nodes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/434/1*6A-j2cFv3MEqgzFKSp7VUQ.png" /><figcaption>Example 2: Input</figcaption></figure><p>Just a very simple change (changing arrow directions), however, now there is no path from green -&gt; red, so there is no solution.</p><p><strong>Example 3</strong></p><p>Now let’s make things a bit more challenging, multiple targets.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/554/1*3U3vMCWDgkLXoDJQhiR9vA.png" /><figcaption>Example 3: Input</figcaption></figure><p>Here, we want all of the minimum subgraphs from the green node to both the red and the blue node. There are two solutions for this graph:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/528/1*iLVmC2Rr3u8z3qigOyizBA.png" /><figcaption>Example 3: Solution 1</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/528/1*_FzYmJm-tk_RxuJVhzl0Hw.png" /><figcaption>Example 3: Solution 2</figcaption></figure><p>This example could be extrapolated to graphs with any number of target nodes.</p><p>Finally, let’s do that a little harder. I want to introduce what’s intended when there are multiple starting nodes (green), and multiple end nodes, with multiple targets.</p><p><strong>Example 4</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/664/1*Uzrcp5vueufEOm9tXf_YBQ.png" /><figcaption>Example 4: Input</figcaption></figure><p>This one’s more tricky, it has multiple starting nodes and multiple targets. It also has multiple paths from a green node to a particular target. But I wanted <em>all</em> of the subgraphs. Here’s the solution, in multiple parts, again for clarity.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/664/1*QktkLH2rv7Zh6V1rWCrJBw.png" /><figcaption>Example 4: Solution 1</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/664/1*SPaw5y5DmXwY_0SEUnB7qQ.png" /><figcaption>Example 4: Solution 2</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/664/1*fR7FXaifkpq5oQLYKEHMsQ.png" /><figcaption>Example 4: Solution 3</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/622/1*RU0zsKl7VX54vmeUNAjdnQ.png" /><figcaption>Example 4: Solution 4</figcaption></figure><p>I tried to go through these solutions carefully, but if I made a mistake, feel free to leave a comment down below. You can also see the ‘code’ version of these examples here: <a href="https://github.com/mattpaletta/coloured-graph-traversal/blob/master/test/test_blog_examples.py">Blog Example Tests on Github</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*hj-F9Nk8EXf3MsE1" /><figcaption>Photo by <a href="https://unsplash.com/@benwhitephotography?utm_source=medium&amp;utm_medium=referral">Ben White</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>I had to think about this problem for a while, but I won’t make you think about it too hard, here’s how I did it.</p><h3>Solution</h3><p>Let’s start with the helpful data structures and utility functions we can test that will help us with our solution. The first thing is a way to easily represent colours. I opted to use a class and assign each colour an integer value so I can easily compare them. I’m copy/pasting from my solution, I will leave links to the relevant files on Github for easy reference, in case they change in the future, or if you want to read additional documentation I sometimes write.</p><h4><strong>Data Structures</strong></h4><pre>from enum import Enum </pre><pre>class Colour(Enum):<br>    BLACK = 1<br>    RED = 2<br>    GREEN = 3<br>    BLUE = 4<br>    YELLOW = 5</pre><p><a href="https://github.com/mattpaletta/coloured-graph-traversal/blob/master/colouring/colour.py">colouring/colour.py</a> on Github</p><p>Next up is a very simple matrix. I called it a matrix, but it’s really an adjacency matrix. It has no mathematical operators, only ones relevant to graphs. In this case: add_edge, get_connected, etc.</p><p>The data structure is a 2D square array of boolean values, all set to `False` initially. The dimension, or size, of the matrix is the number of vertices in the graph.</p><p>In a more optimized solution, I would use a sparse matrix, but I wanted to keep it as simple as possible, and without external dependencies.</p><p>If Matrix.get_connected(x, y) is True, there is a link from node x, to node y.</p><p>If g1.subset(g2) is True , then graph g1 is a subset of graph g2, meaning every edge of g1 is contained in g2.</p><pre>from typing import List, Iterator</pre><pre>class Matrix(object):<br>    def __init__(self, size: int):<br>        self._data: List[List[bool]] = []<br>        self._size = size</pre><pre>        # Initialize the matrix to all `False`<br>        for i in range(self._size):<br>            self._data.append([])<br>            for j in range(self._size):<br>                self._data[i].append(False)</pre><pre>    def add_edge(self, from_node: int, to_node: int) -&gt; None:<br>        self._data[from_node][to_node] = True</pre><pre>    def get_edge(self, from_node: int, to_node: int) -&gt; bool:<br>        return self._data[from_node][to_node]</pre><pre>    def get_connected(self, node: int) -&gt; Iterator[int]:<br>        for i in range(self._size):<br>            if self._data[node][i]:<br>                yield i</pre><pre>    def get_connected_lst(self, node: int) -&gt; List[int]:<br>        return list(self.get_connected(node))<br>    <br>    def inward_edges(self, node: int) -&gt; Iterator[int]:<br>        for i in range(self._size):<br>            if self._data[i][node]:<br>                yield i<br>    <br>    def inward_edges_lst(self, node: int) -&gt; List[int]:        <br>        return list(self.inward_edges(node))<br>    <br>    def equals(self, other) -&gt; bool:<br>        if self.size() != other.size():<br>            return False<br>        for i in range(self.size()):<br>            for j in range(self.size()):<br>                if self.get_edge(i, j) != other.get_edge(i, j):<br>                     return False<br>        return True</pre><pre>    def subset(self, other) -&gt; bool:<br>        if self.size() != other.size():<br>            return False<br>        for i in range(self.size()):<br>            for j in range(self.size()):<br>                if other.get_edge(i, j) and not self.get_edge(i, j):<br>                    return False</pre><pre>    def size(self) -&gt; int:<br>        return self._size</pre><p><a href="https://github.com/mattpaletta/coloured-graph-traversal/blob/master/colouring/matrix.py">colouring/matrix.py</a> on Github</p><p>Finally, as far as data structures are concerned, this is a representation of a Node in our adjacency list.</p><pre>from colouring.colour import Colour</pre><pre>class Node(object):<br>    def __init__(self, colour: Colour, id: int):<br>        self._colour = colour<br>        self.id = id</pre><pre>    def get_colour(self) -&gt; Colour:<br>        return self._colour</pre><p><a href="https://github.com/mattpaletta/coloured-graph-traversal/blob/master/colouring/node.py">colouring/node.py</a> on Github</p><p>I think this one should be relatively straightforward, it stores its colour and an ID. You could imagine the node storing more information when running in a proper application, but this serves the purpose of our algorithm.</p><h4><strong>Utility Functions</strong></h4><p>I have the following utility functions all in one file, which you can view here: <a href="https://github.com/mattpaletta/coloured-graph-traversal/blob/master/colouring/utils.py">colouring/utils.py</a></p><p>I’ll go through one at a time so it’s easier to follow along. I’ve modified the snippets a little bit so they are self-contained examples that could be put in their own file as much as possible, and tested independently.</p><pre>from colouring.matrix import Matrix</pre><pre>def has_prev_output_graph(lst_out: List[Matrix], graph: Matrix):<br>    for mat in lst_out:<br>        if mat.equals(graph):<br>            return True<br>    return False</pre><p>Given a list of matrices, we have previously output (in our main algorithm), this returns if the new matrix graph matches any of them. This ensures we don’t output the same solution multiple times. We compare each matrix in lst_out against graph, using the Matrix.equals method we defined above.</p><pre>from colouring.matrix import Matrix<br>from colouring.node import Node</pre><pre>def matrix_to_adj(nodes: List[Node], graph: Matrix):<br>    out: Dict[Node, List[Node]] = {}<br>    for i in range(graph.size()):<br>        for j in range(graph.size()):<br>            if graph.get_edge(i, j):<br>                out[nodes[i]] = out.get(nodes[i], []) + [nodes[j]]<br>            else:<br>                out[nodes[i]] = out.get(nodes[i], [])<br>    return out</pre><pre>def adj_to_matrix(graph: Dict[Node, List[Node]]) -&gt; Matrix:<br>    all_nodes = list(graph.keys())<br>    m = Matrix(size = len(all_nodes))<br>    for k, v in graph.items():<br>        for connected_node in v:<br>            k_index = all_nodes.index(k)<br>            connected_index = all_nodes.index(connected_node)<br>            m.add_edge(k_index, connected_index)<br>    return m</pre><p>The first takes a matrix and returns an adjacency list. The second is it’s inverse, it takes an adjacency list of Node , and returns an equivalent Matrix.</p><pre>def node_to_index(nodes: List[Node], lst: List[Node]) -&gt; List[int]:<br>    return [nodes.index(n) for n in lst]</pre><p>Finally, this one takes two lists of Node objects, and returns for every item of lst, it inserts the index of that node found in nodes .</p><p>If you are still unsure about what any of these methods do, you can find my test suite for them here, clone the repo, add a print statement, and try running it:</p><p><a href="https://github.com/mattpaletta/coloured-graph-traversal/blob/master/test/test_utils.py">test/test_utils.py</a></p><p><a href="https://github.com/mattpaletta/coloured-graph-traversal/blob/master/test/test_matrix.py">test/test_matrix.py</a></p><h4>Now, the moment you’ve been waiting for…</h4><p>I think it would be simplest if I started with a birds-eye view, and then we zoomed in to view the details in each part.</p><p>The testing code calls a single function:</p><pre>def traverse_graph(<br>    graph: Dict[Node, List[Node]], <br>    target_colours: List[Colour]) <br>       -&gt; Iterator[Dict[Node, List[Node]]]:<br>    pass</pre><p>It takes in an adjacency list of Node , and a list of target colours, and it returns an iterator of adjacency lists of nodes.</p><p>While implementing this method, I found that it made more sense to me to have the algorithm operate on adjacency matrices internally. The pair of utility functions we wrote above help us convert between an adjacency list -&gt; adjacency matrix on input, and reverse this process before outputting a solution.</p><p>The pseudocode is as follows:</p><pre>- Identify all possible target nodes (all nodes that are one of the colours in our `target_colours` list</pre><pre>- Identify all green nodes (all possible starting positions)</pre><pre>for each green node:<br>  for each (set of targets), each set contains one of every colour:<br>     - find all paths from the green node to each target node<br>     - merge every possible combination of paths in this set<br>     - check if the merged set has previously been output<br>     - if not, check if it is a valid soltion<br>     - if it is, `yield` the graph, after turning it back to an adj. list</pre><p>I’ll go through each part slowly if you want to follow along with the code:</p><p><a href="https://github.com/mattpaletta/coloured-graph-traversal/blob/master/colouring/traversal.py">colouring/traversal.py</a> on Github</p><p>In order to identify all possible target nodes, the first thing I do is I build a reverse-lookup of colours. I take all the nodes in the graph, and build a dictionary that maps a Colour with a list of all of the Node that are that colour. This is done in the function build_node_colour_lookup</p><p>I then pass this lookup to another function: get_all_target_nodes . This builds the sets of all target nodes combinations, such that every set has all of the colours. I think this is best shown through an example:</p><pre>target_colours: [Red, Blue, Brown]</pre><pre>Given: {<br>  Red: [Node(0)],<br>  Blue: [Node(1)],<br>  Brown: [Node(2), Node(3)],<br>}</pre><pre>Output:<br>[ <br>  [Node(0), Node(1), Node(2)]<br>  [Node(0), Node(1), Node(3)]<br>]</pre><p>As you can see, this outputs two lists, each of which contains a red, blue, and brown node.</p><p>In order to get all of the starting nodes, I can use the node_colour_lookup I created earlier to get me all of the green nodes. If there are no green nodes, I will iterate 0 times, meaning I do nothing.</p><p>As mentioned earlier, I iterate through each green node, and I will find all of the paths from that green node to all of the target node sets. (output from get_all_target_nodes ). I iterate through each set, and for each node in the set, I return all paths from that particular green node to that particular target node. This allows me to have a 1–1 mapping, meaning I can use a simple DFS (Depth-First Search) algorithm to find the path, updating a matrix of the route travelled along the way.</p><p>The DFS algorithm I’m using is nothing fancy, I have a graph Matrix , which represents all of the edges in the graph and a curr_matrix , which contains only the edges taken so far. Before I recurse to each child, I create a deep copy of curr_matrix , so subsequent recursion calls won’t affect the previous state. I did test this, and it doesn’t work without the deep-copy function, I realize this is not ideal. I return a generator from this recursive function so that I can easily output all of the curr_matrix anytime I find a solution, without having to append them all to a list and then returning the list. If you want my tips on using Python generators, you can find that here:</p><p><a href="https://medium.com/@mattpaletta/gotchas-python-generators-returns-5d990684dbf9">Gotcha’s: Python Generators — mattpaletta</a></p><p>The output from DFS might look like this (taken from Example 4):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/622/1*Ep_93C2yUGYH1EHXr1f6lQ.png" /><figcaption>DFS Partial Solution 1</figcaption></figure><p>and:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/384/1*sTBue_Mzek8sHxeZ0jStNQ.png" /><figcaption>DFS Partial Solution 2</figcaption></figure><p>There would be others, but these two would be combined as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/664/1*5-uxvEyN7EHbdfQjxbCOkg.png" /><figcaption>DFS Sample Merged Solution</figcaption></figure><p>Now that I have my list of paths, represented as a Matrix from the green-node we’re on to each node in the target_node_set , then we find all of the combinations of those solutions and merge them together. The number of combinations is dependent on the number of nodes in each target_node_set, in other words, the number of colours we are looking for.</p><p>For example, if we are looking for [Red, Blue] , then we will find all combinations of 2 solutions from our list of partial-solutions because we know the end-solution must have 2 target nodes in it.</p><p>In order to combine two partial solutions, we pass in the starting node, in other words, the current green node, along with the two adjacency matrices. We start by comparing if two matrices are equal, if we are, we can just return either one of them. If they are not equal, we check if one is the subset of the other. If we do find a subset, we return the larger graph. Finally, we start at the green node and do another DFS traversal of this graph. In order to determine the output edges from the current node, we take the output edges from graph1 and append the outward edges from graph2. This means we combine all of the paths from graph1 and graph2. Before we add the edge to our output graph, we traverse-ahead, using a helper function to determine if that edge reaches one of the target nodes. This means we discard any nodes that aren’t connected, allowing for a smaller solution. We can only combine graphs in this way because we know that they must contain the same set of vertices.</p><pre>def combine_adj_matrix(starting_node: int, graph1: Matrix, graph2: Matrix, target_nodes: List[int]) -&gt; Matrix:<br>    if graph1.equals(graph2):<br>        return graph1<br>    elif graph1.subset(graph2):<br>        return graph1<br>    elif graph2.subset(graph1):<br>        return graph2<br><br>    def does_lead_to_target(curr_node, visited: Set[int]):<br>        if curr_node not in target_nodes:<br>            if curr_node not in visited:<br>                g1_outward = graph1.get_connected_lst(curr_node)<br>                g2_outward = graph2.get_connected_lst(curr_node)<br>                all_outgoing = set(g1_outward + g2_outward)<br>                visited.add(curr_node)<br>                for outgoing in all_outgoing:<br>                    if outgoing not in visited:<br>                        if does_lead_to_target(outgoing, visited):<br>                            return True<br>            return False<br>        else:<br>            return True</pre><pre>    out = Matrix(graph1.size())<br>    def traverse(curr_node, visited: Set[int]):<br>        # Do nothing if we already visited the node<br>        if curr_node not in visited:<br>            # Get all outgoing edges<br>            g1_outward = graph1.get_connected_lst(curr_node)<br>            g2_outward = graph2.get_connected_lst(curr_node)<br>            all_outgoing = set(g1_outward + g2_outward)<br>            visited.add(curr_node)<br>            for outgoing in all_outgoing:<br>                # Make sure we don&#39;t go in circles, <br>                # make sure to prune any extraneous edges<br>                if outgoing not in visited and \<br>                  does_lead_to_target(outgoing, deepcopy(visited)):<br>                    out.add_edge(curr_node, outgoing)<br>                    traverse(outgoing, visited)<br>    traverse(starting_node, set())<br>    return out</pre><p>The keen-eyed among you may have noticed that we could end up with two red nodes in our solution when we combine our two partial-solutions together. For this reason, we must check if the merged solution contains one node of each colour before returning it.</p><p>Assuming all goes well and we make it this far, we can take our now single solution, turn it back into an adjacency list, add it to the list of solutions we’ve previously output, and return it to the caller.</p><p>I’d say the most difficult part for me was coming up with the idea of merging two partial paths together. While I was experimenting with graphs that had a single green node and a single colour, it wasn’t too bad. If there was a path from one target colour to the other, I could do that as well. But I needed to implement partial paths to handle cases where the two nodes are not connected to each other, so I can’t go through one to get to the other (see Example 4).</p><p>I hope you found this interesting, if you did, and once again, you can view all of my code on GitHub here:</p><p><a href="https://github.com/mattpaletta/coloured-graph-traversal">Github Repo</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7aff54539f8f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Branching Web Forms]]></title>
            <link>https://medium.com/@mattpaletta/branching-web-forms-cc2ee044d6ef?source=rss-ea25e3a9f50d------2</link>
            <guid isPermaLink="false">https://medium.com/p/cc2ee044d6ef</guid>
            <category><![CDATA[react]]></category>
            <category><![CDATA[web-forms]]></category>
            <category><![CDATA[mvc]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[branching]]></category>
            <dc:creator><![CDATA[Matthew Paletta]]></dc:creator>
            <pubDate>Sat, 28 Mar 2020 20:42:11 GMT</pubDate>
            <atom:updated>2020-03-28T20:42:11.074Z</atom:updated>
            <content:encoded><![CDATA[<p>You can view the code here: <a href="https://github.com/mattpaletta/branching-forms-example">https://github.com/mattpaletta/branching-forms-example</a></p><p>I’m currently working on a project that requires complex web forms. Specifically, it requires a multi-page form that accepts input from the user at each step, but unlike many multi-page forms online, the next screen is different depending on what the user chose in the last screen. Hence the term, <em>branching web forms</em>.</p><p>I’m using React for this project, and I structured my code in such a way that I follow the MVC architecture. This has already made such a huge difference for me in terms of managing and testing a large web application as a single developer. Here’s a great resource about MVC, targeted at iOS development, but the same principles apply to a React app: <a href="https://learnappmaking.com/model-view-controller-mvc-swift/">https://learnappmaking.com/model-view-controller-mvc-swift/</a></p><p>My initial attempt at this branching form was to put all of my state for the entire form in a parent controller, but that quickly became an unmanageable ball of state and if-statements. Gross.</p><p>I’d like to present the software architecture I arrived at, which so far, I’m very happy with. The example I’ll be using is a form to help the user decide what pet they should get based on a series of questions. Some choices include: do they have a yard, do they have any allergies, etc.</p><p>Below is a diagram of the decisions through the form. I realize this is a greatly simplified example, but I chose it because it’s easy enough to comprehend, and not too complex, so we can focus on the code structure that supports this.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/922/1*zAox2rPAmAhiIbniG328Sw.png" /></figure><p>Now, let’s jump into the code!</p><h3>Code Deep Dive</h3><p>The code is broken into two parts, the library (in pet_chooser/src/lib ) and the application (in pet_chooser/src/components ). Let’s go through the structure of the application first, since that will help frame the use case for the library architecture.</p><h4>Application</h4><p>The entry point is in pet_chooser/src/App.tsx . Nothing really special going on here, it sets up our top-level view and creates our FrienshipFormController .</p><p>The FrienshipFormController itself is pretty simple. It wraps a GenericForm (from the library), and determines the first screen of the form to be the HomeSelection , which asks if you live in a house or an apartment.</p><h4>Library</h4><p>The library is relatively simple implementation wise, but has some subtleties. There are only 2 important classes: BaseStep and GenericForm .</p><p>GenericForm , the component we set up in our FrienshipFormController is responsible for storing the current screen being rendered, initially, as well as rendering and managing the next and back buttons to move between screens.</p><p>The other, more interesting component is the BaseStep . Below is the interface, in mostly-typescript pseudocode. Some implementation details have been removed for simplicity:</p><pre>class BaseStep {<br>    private readonly update_callback: CallableFunction | undefined;<br>    private readonly prevStep: BaseStep | undefined;<br>    protected state: Map&lt;string, any&gt;;</pre><pre>constructor(prevStep, update_callback) : none</pre><pre>forceUpdate() : none</pre><pre>setStepState(key: string, value: any) : none<br>    getStepStateOr(key: string, or: any) : any<br>    getStepState(key: string) : any | undefined</pre><pre>recalculateErrors() : number</pre><pre>shouldShowNextButtons() : booelean<br>    showShowBackButton() : boolean</pre><pre>getScreen() : HTMLElement<br>    getNextScreen() : BaseStep | undefined<br>    getPreviousScreen() : BaseStep | undefined<br>}</pre><p>So now that we’ve outlined the building blocks, we can talk about putting them all together.</p><p>Essentially, what this BaseStep class lets us do, is define every screen as a class, that implements BaseStep . Every screen then has it’s own logic about storing it’s local state, rendering itself, as well as calculating if there are any errors on the screen, and what screen it should move to next.</p><p>Every BaseStep gets a pointer to the previous screen, prevStep . This creates a linked list of screens. This abstraction allows for every screen to determine the next screen, based on its current, and the previous screens state.</p><p>The BaseStep can store state that’s local to itself as private properties, set in its constructor. Any state that is shared with other screens can be set and read through: setStepState and getStepState methods. In getStepState , the current screen looks at its own state and if it has the value, it will return the value in the state map. If it doesn’t, it will follow the previous screen’s pointer, and call the same method recursively on the previous screen. The code for getStepState is shown below:</p><pre>getStepState(key: string): undefined | any {<br>     if (this.state.has(key)) {            <br>          return this.state.get(key);        <br>     } else if (this.prevStep !== undefined) {            <br>          return this.prevStep.getStepState(key);<br>     } else {            <br>          return undefined;        <br>     }    <br>}</pre><p>When a class updates its state, it calls forceUpdate() , which forces the GenericForm to redraw all sub children, in this case, the current screen. In doing so, the GenericForm will ask the screen to recalculate_errors() , which the screen implements. This method returns the number of errors the screen currently has before it is ready to advance to the next screen. Once that number reaches 0, the ‘next’ button is enabled in the GenericForm. When the user clicks ‘next’, the getNextScreen() is called on the current screen. Below is an example implementation, which decides which next screen to show based on the currents state of the screen.</p><pre>getNextScreen(): BaseStep | undefined {        <br>    if (this.getStepState(PetFormSources.HOUSING.OPTION) === &quot;House&quot;) {<br>         return new HasYardSelectionStep(this);<br>    } else {<br>         return new HasAllergiesStep(this);<br>    }<br>}</pre><p>The this pointer is the key to creating the linked list. Because every item implements BaseStep , the this pointer (referring to the current screen) is passed as the previous screen of the next screen.</p><h3>Running the example</h3><p>That concludes the code walkthrough, now let’s run the example so you can play with it and see it working in action.</p><p>Clone the code repository, change into the pet_chooser folder, and install npm dependencies.</p><pre>git clone <a href="https://github.com/mattpaletta/branching-forms-example">https://github.com/mattpaletta/branching-forms-example</a><br>cd branching-forms-example/pet_chooser<br>npm install</pre><p>Finally, run npm start .</p><p>Open localhost:3000 in your browser.</p><p>Thanks for reading. I hope you found this helpful for your projects. Enjoy!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=cc2ee044d6ef" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Gotchas: Python Generators & Returns]]></title>
            <link>https://medium.com/@mattpaletta/gotchas-python-generators-returns-5d990684dbf9?source=rss-ea25e3a9f50d------2</link>
            <guid isPermaLink="false">https://medium.com/p/5d990684dbf9</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[generator]]></category>
            <category><![CDATA[yield]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Matthew Paletta]]></dc:creator>
            <pubDate>Sat, 03 Nov 2018 18:52:34 GMT</pubDate>
            <atom:updated>2018-11-03T18:52:34.593Z</atom:updated>
            <content:encoded><![CDATA[<p>I’m currently working on a project in Python that heavily makes use of generators and gRPC. Both amazing technologies, that I’ll hopefully write about in the future.</p><p>I found a really weird bug (or feature?) in Python generators that took me a while to figure out, and I wanted to share it.</p><p>Consider these examples:</p><pre># Example A</pre><pre>def foo():</pre><pre>  for i in range(1, 10 + 1):</pre><pre>    yield i</pre><pre>print(list(foo(x)) #expected: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]</pre><pre># Example B</pre><pre>def bar(x):</pre><pre>  return x + 1</pre><pre>def foo():</pre><pre>  for i in range(10):</pre><pre>    yield bar(i)</pre><pre>print(list(foo()) # expected: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]</pre><p>Example A does what you expect. Example B however, only returns <em>[1]</em>. The reason is that return raises a <em>StopIteration </em>exception, which causes the <em>f</em>oo function to break out of the loop. The weird thing is that if you change example B to:</p><pre># Example C</pre><pre>def bar(x):</pre><pre>  return x + 1</pre><pre>def foo():</pre><pre>  for i in range(10):</pre><pre>    x = bar(i)</pre><pre>    yield x</pre><pre>print(list(foo()) # expected: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]</pre><p>You get the expected answer. This gave me pause because I would have thought that the return in <em>bar()</em> from example B would have evaluated the expression and returned it, and then <em>foo()</em> would just yield that value. So that theoretically, example B should be doing what example C is doing.</p><p>I know that the other option is to change to code to the following (with the new <em>yield from</em> syntax:</p><pre># Example D</pre><pre>def bar(x):</pre><pre>  yield x + 1</pre><pre>def foo():</pre><pre>  for i in range(10):</pre><pre>    yield from bar(i)</pre><pre>print(list(foo()) # expected: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]</pre><p>I think you get the idea, but I think example B (if it worked), is the cleanest. example D has an extra loop for the one element, which I think could be confusing in a large code base.</p><p>For those who aren’t familiar with the new <em>yield from</em> syntax:</p><pre>for i in foo():<br>    yield i</pre><pre># equivalent to</pre><pre>yield from foo()</pre><p>Is this a bug? Is it a feature? Is it an oversight on the development of the yield statement? This was tested in Python 3.6 and 3.7 on MacOS High Sierra.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5d990684dbf9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Is always always always?]]></title>
            <link>https://medium.com/@mattpaletta/is-always-always-always-213c79a15f01?source=rss-ea25e3a9f50d------2</link>
            <guid isPermaLink="false">https://medium.com/p/213c79a15f01</guid>
            <category><![CDATA[always]]></category>
            <category><![CDATA[psychology]]></category>
            <category><![CDATA[human-nature]]></category>
            <dc:creator><![CDATA[Matthew Paletta]]></dc:creator>
            <pubDate>Sat, 03 Nov 2018 17:11:04 GMT</pubDate>
            <atom:updated>2018-11-03T17:11:04.660Z</atom:updated>
            <content:encoded><![CDATA[<p>I’ve definitely made the mistake many times when I said “always” instead of “sometimes” or “in many cases”. Friends have called me out on it, and I’ve tried to improve. I think I can say, I’m now much better than I used to be. This morning I was thinking about “always”, more specifically, is there such a thing as always?</p><p>I consider myself a creative/innovator (not quite sure what the right word is), and I do believe in the scientific method/process. The idea that a hypothesis, any hypothesis can be considered true if there is enough evidence to show it is true for a general case, and not untrue for any of those cases. In other words, true if shown to be true, until proven false.</p><p>So, I want to make the jump that a thought, or belief, or an opinion that an individual has is simply an unproven hypothesis, at least to the general case. Therefore, if the belief is that “X is always true”, and they didn’t mean “in some cases”, but said “always” by accident; that the individual has not yet found evidence for their belief to be false, and therefore must be true.</p><p>Now, of course there is the whole field of psychology that goes into the filtering of information that goes against your beliefs, and heightening the prevalence of new information to support existing beliefs (regardless if the pattern actual exists), but I’ll just skim over that for now. Let’s assume that this filtering doesn’t happen for a moment, and that we are rational beings (both huge assumptions): if a belief is true, then either no false evidence exists, or we simply haven’t found it yet.</p><p>I believe that there are some instinctual thoughts and behaviours we have as humans, but that a big part of our human thought process is heavily influenced from the world we experience.</p><p>As as a thought experiment, and hopefully you’re still with me here, if we were born in a vacuum, or a black room by ourselves from birth (assuming this was theoretically possible, and we just skip over eating, drinkimg, etc. since there’s nothing around you), what would be think about? We still have a brain, but we’ve only ever experience ourself, though we’ve never seen ourself. We certainly wouldn’t know a spoken or written language, would we know how to make sounds? Would we have creative ideas?</p><p>Finally, I would love to hear your thoughts on: if always is always always?</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=213c79a15f01" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>