<?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 Dhruv Rajvanshi on Medium]]></title>
        <description><![CDATA[Stories by Dhruv Rajvanshi on Medium]]></description>
        <link>https://medium.com/@dhruvrajvanshi?source=rss-256be141b225------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/proxy/1*TGH72Nnw24QL3iV9IOm4VA.png</url>
            <title>Stories by Dhruv Rajvanshi on Medium</title>
            <link>https://medium.com/@dhruvrajvanshi?source=rss-256be141b225------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 19:09:15 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@dhruvrajvanshi/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[Advanced Typescript patterns]]></title>
            <link>https://medium.com/@dhruvrajvanshi/advanced-typescript-patterns-6cf8826c7944?source=rss-256be141b225------2</link>
            <guid isPermaLink="false">https://medium.com/p/6cf8826c7944</guid>
            <category><![CDATA[type-safety]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[typescript]]></category>
            <dc:creator><![CDATA[Dhruv Rajvanshi]]></dc:creator>
            <pubDate>Wed, 09 May 2018 20:45:59 GMT</pubDate>
            <atom:updated>2025-05-24T20:09:56.373Z</atom:updated>
            <content:encoded><![CDATA[<p>Here are some cool things that I discovered in Typescript that allow me to statically check pretty neat invariants and reduce type/interface declaration boilerplate using type inference.</p><h4>Ensuring that a value has passed through a function</h4><p>Consider this scenario. A client sends you dates, times, years as strings and you need to store all of them in the DB as Unix time-stamps. But you have to make sure that when client is putting things in, you parse the time according to the correct format and when you’re sending back entities to the client, you’re returning back strings that formatted correctly. To the client, all of them are strings but some are “YYYY”, others are “YYYY-MM-DD” and others are “YYYY-MM-DDTHH:mm”. Your database must store them as numbers for them to be sortable fields.</p><p>There’s a trick for differentiating between different formats of strings (or rather any values of the same type) using the never type.</p><p>Lets say our client needs an entity called BunchOfDates and when they call PUT /bunchofdates they send you this object.</p><pre>interface PutBunchOfDatesObj {<br>  date: string; // formatted as YYYY-MM-DD<br>  time: string; // formatted as YYYY-MM-DDTHH:mm<br>  year: string; // formatted as YYYY</pre><pre>}</pre><p>And you want your DB object to contain a Unix timestamp. So, your DB row type will look something like this.</p><pre>interface DBBunchOfDatesObj {<br>  date: number;<br>  time: number;<br>  year: number;</pre><pre>}</pre><p>Your putBunchOfDates function might look like this.</p><pre>function putBunchOfDates(dates: DBBunchOfDatesObj): Promise&lt;void&gt;</pre><p>You might accidentally try to parse time using YYYY format or what not. If you’re lucky, it will fail at run-time. If you’re not, it will fail silently and your DB will contain the wrong date.</p><p>Here’s the trick. First, update your DBBunchOfDatesObj interface to the following.</p><pre>interface DBBunchOfDatesObj {<br>  // all these My* types are actually just<br>  // strings at runtime. Just their existence<br>  // is a proof that they are correctly formatted.</pre><pre>  date: MyDate;<br>  time: MyTime;<br>  year: MyYear;</pre><pre>}</pre><p>Then, define interfaces for each type of time formatted string.</p><pre>interface MyYear extends String {<br>  // the name of this field doesn&#39;t really matter<br>  // as long as it&#39;s unique to this interface.<br>  // you can&#39;t really do anything with this field and this<br>  // won&#39;t even be present in the object so, it&#39;s okay<br>  // to pretend that this field isn&#39;t there. It only exists on<br>  // the type level and has no runtime significance.<br>  // This is why this technique is sometimes called a &quot;Phantom type&quot;</pre><pre>  __my_year__: never;</pre><pre>}</pre><p>No value can ever be assigned to never type without type casting and no method can be called on never. This means that MyYear can be used instead where you’re expecting a string (you can call .split or whatever on a MyYear) but you can’t use a string where a MyYear is expected.</p><p>How do you create a MyYear?</p><p>Have a function parseMyYear.</p><pre>function parseMyYear(str: string): MyYear | null {<br>  if (/^\d{4}$/.test(str)) {<br>    return str as MyYear;</pre><pre>  } else {<br>    // or throw an exception. Doesn&#39;t matter how you<br>    // handle errors.</pre><pre>    return null;</pre><pre>  }</pre><pre>}</pre><p>This function will check if the format is correct by whatever means necessary (here, by calling isYYYY) and if it is, it will cast it to a MyYear. If you turn on linter rules for disabling type casting, you can ensure that the only way to create a MyYear is by using the aforementioned function. You can add a tslint disable comment inside this function because you’ve proved that str is a MyYear by calling isYYYY.</p><p>Now, you can make a function for converting the MyYear into a UNIX time-stamp using the signature,</p><pre>function myYearToUnix(y: MyYear): number</pre><p>Inside this, you can treat y as a YYYY string because it’s guaranteed that y has been checked.</p><h4>Type safe object validation</h4><p>Your API might expect your clients to respect a certain schema for JSON payloads. It would be nice if you could write a declarative schema for the request and have that automatically converted to a type so that intellisense can work properly.</p><p>There’s a pretty good library for validating arbitrary objects according to a schema called <a href="https://github.com/hapijs/joi">Joi</a>. It lets you write schemas like this. The syntax of the library isn’t important. You can write a similar declarative validator yourself. What matters is how we’re gonna convert this validator into an honest to god type that you can use intellisense on.</p><pre>const myValidator = Joi.object().keys({<br>  key1: Joi.string(),<br>  key2: Joi.string().valid(&quot;x&quot;).valid(&quot;y&quot;).required(),</pre><pre>  key2: Joi.number().required()</pre><pre>}).required()</pre><p>You can call .validate method on myValidator and pass in any value to it. It will check the type to make sure that it’s valid. It will only give you the value if the schema matches.</p><p>It should be pretty obvious what the type of the object that passes successfully thourgh this validator will be.</p><p>Now, lets write a type declaration for Joi object. This will get a bit dense so I’ll explain with comments. This is not for the faint hearted but these 100 lines of pure type level code covers a lot of ground on advanced typescript features.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0fd204509f29c9bfe0ee8d1354ebe98f/href">https://medium.com/media/0fd204509f29c9bfe0ee8d1354ebe98f/href</a></iframe><p>You might wonder if this is worth it. I would argue yes because if you’re writing an HTTP api, you would have to write a bunch of routes. These 100 lines, would ensure that all of your dozen routes are using the payload correctly.</p><p>Here’s a sample route I wrote in using hapi.js. You can easily convert the route function to express/koa or whatever without any problems. Though for Hapi, the route function simply returns its argument. It’s present only for type inference. I won’t go into the details of the type of route function but you can ask if you wanna know how I did it.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bf31c908545e559161be48e2923b1ebf/href">https://medium.com/media/bf31c908545e559161be48e2923b1ebf/href</a></iframe><p>Basically, the “framework” ensures that validator will be run on the request payload and the validated value will be set on the request object. If validation fails, a 400 response will be returned.</p><p>If you hover over item on line 19, you’ll see that it has its type inferred properly right down to the fact that .description is optional. I don’t know about you but I’m pretty darn pleased with this. Heck even intellisense works. Excuse my use of 90s patois but…RAD! The validator allows us to both check untrusted values at runtime, validated values at compile time and serve as a human readable documentation for your route/ You can probably auto generate a pretty HTML version of your api documentation using typescript compiler api if you were so inclined. BTW, Hapi already has plugins for generating type api docs using Joi validators so that’s pretty nice all things considered.</p><h3>And there’s more</h3><p>I’ve written previously about neat stuff you can do in Typescript.</p><p><a href="https://medium.com/@dhruvrajvanshi/simulating-haskells-do-notation-in-typescript-e48a9501751c">Here’s how you emulate Haskell’s do notation.</a></p><p><a href="https://medium.com/@dhruvrajvanshi/making-exceptions-type-safe-in-typescript-c4d200ee78e9">And this is about emulating Rust’s error handling (sort of including the </a><a href="https://medium.com/@dhruvrajvanshi/making-exceptions-type-safe-in-typescript-c4d200ee78e9">? operator).</a></p><p>Also, my library <a href="https://github.com/dhruvrajvanshi/ts-failable">ts-failable</a> allows you to emulate Kotlin and Swift’s Elvis operator ?..</p><p>All of this is type safe. So that’s pretty cool. Once you get used to it, you’ll realize that type systems can do a lot more for you than simply ensuring you’re not assigning strings to ints.</p><p>Obviously, you also need to show a bit of restraint while using advanced types in production. You might not want your coworkers’ brain to explote when they try to read your 3 levels nested type mapped conditional types with string literal types and what not. You can always use the excuse that I use which is, just pretend the types aren’t there and you’ll be fine ;).</p><p>Till next time, farewell.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6cf8826c7944" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Making exceptions type safe in Typescript]]></title>
            <link>https://medium.com/@dhruvrajvanshi/making-exceptions-type-safe-in-typescript-c4d200ee78e9?source=rss-256be141b225------2</link>
            <guid isPermaLink="false">https://medium.com/p/c4d200ee78e9</guid>
            <category><![CDATA[typescript]]></category>
            <category><![CDATA[error-handling]]></category>
            <dc:creator><![CDATA[Dhruv Rajvanshi]]></dc:creator>
            <pubDate>Sun, 11 Feb 2018 19:04:42 GMT</pubDate>
            <atom:updated>2025-05-24T20:14:12.181Z</atom:updated>
            <content:encoded><![CDATA[<p>Many times I’ve wished that I could reason about exceptions in a type safe manner. Like getting a specific field from the exception to handle the error. But in Typescript, exceptions have any type by default. You can throw whatever but when you catch it, it will have any type.</p><p><em>EDIT: Some people have pointed out that this just the Either type. Its true that its equivalent to Either type but its more than that. It gives a way to flatten out nested flatMaps so if you have multiple computations that can fail and each depends on the result of the previous, you’ll have as many levels of nesting as there are failable calls depending on the last one. BTW, </em><a href="https://medium.com/@dhruvrajvanshi/simulating-haskells-do-notation-in-typescript-e48a9501751c"><em>here’s another article</em></a><em> I wrote that solves the nesting problem for Monads in Typescript by simulating Haskell’s do notation. You can use that too for the same effect but I think the syntax for this method is closer to exceptions and less alien.</em></p><p>The alternative to using exceptions is use discriminated unions to indicate the possibility of an error. Something like this.</p><pre>// So you like boilerplate like if (result.isError) {...}<br>// Just use Go :/</pre><pre>type MyResult&lt;T&gt; = {<br>  isError: true,<br>  error: ErrorType</pre><pre>} | {<br>  isError: false,<br>  value: T</pre><pre>}</pre><p>This will force the user of a MyResult&lt;T&gt; value to check the isError field on the result to access the value field. There’s no way around it which is good. However, this approach has a small problem which is not present when using exceptions. Error propagation.</p><p>Consider this. If you have two functions that return MyResult values and you want to call them after each other, with the return value of the first call being used as an argument to the second call, you’ll have to check each of them for errors seperately. This can become tedious in case of multiple failable steps in your computation.</p><p>If you had used exceptions, you could have called them like normal functions and the errors thrown by each inner function would have propagated up, essentially “short circuiting” the evaluation if any step failed.</p><p>What if I told you that you could have type safety as well as error propagation at the same time?</p><h3>Checked Exceptions (ignore your gag reflex for now)</h3><p>Java has this feature that lets you annotate a method’s return type with the types of exceptions it can throw. The caller can either handle the error (using try/catch), or add a throws clause to the return type to indicate that this method too can throw the exception.</p><p>What? You ask. After what we’ve been through in Java? Really? To which I say, Typescript is not Java. The only reasonable arguments against Java’s checked exceptions are:</p><ul><li>Adding a new exception type to a function that’s being called deep in the stack requires changing the signature of all the functions that call it.</li><li>throws clauses aren’t first class types.</li></ul><p>The solution to the first problem is there in Typescript. You can alias a function’s errors by doing</p><pre>type MyFuncErrors = Error1 | Error2 | Error3</pre><p>If your function needs to throw a new type of error, you can simply do add it to MyFuncErrors and every function that propagates the function will remain unchanged provided the function’s type contains MyFuncErrors and not its cases (which is agains DRY principle anyway).</p><p>The functions that catch MyFuncErrors will have to change and the compiler will tell you that. Adding a new case shoud force you to do that.</p><h3>The idea</h3><p>Here’s how it will work.</p><p>We make a new type called Failable that is generic over the type of the result it can contain and type type of errors it can throw. Failable&lt;T, E&gt; is returned by a function that can return a value of type T on success, or an error of type E in case of failure.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8d60cb63d8ada3aa0282c244a17b096b/href">https://medium.com/media/8d60cb63d8ada3aa0282c244a17b096b/href</a></iframe><p>The type is straightforward enough. If there’s an error, isError is true and there will be an error field, containing the error. As per Typescript rules, you’ll have to check isError field to read the value or error.</p><p>Next, we need a way to create these Failable values. Writing out object literals is verbose and doesn’t help with error propagation. Take a look at this signature as this is the most important thing.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d86fa62cdb230bea682a53a73212bd8a/href">https://medium.com/media/d86fa62cdb230bea682a53a73212bd8a/href</a></iframe><p>This might be a bit hard to read but it captures the entire idea.</p><p>So, you create a value of Failable&lt;T, E&gt; by calling the failable function.</p><p>To it you pass in a lambda function that does whatever computation it needs and returns an error or value. This lambda function will be passed some arguments by failable that would help in indicating success or failure. For now, ignore the run argument.</p><p>Here’s an example that simulates a database call. DB calls can fail so that is encoded in its signature. It either returns a Row or “throws” a DB_ERROR or a USER_DOESNT_EXIST_ERROR.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3ebcd81826b2148738ee150d5cdf6637/href">https://medium.com/media/3ebcd81826b2148738ee150d5cdf6637/href</a></iframe><p>The signature of getUserRow tells you that it takes a string (query), and can either successfully return a Row or undefined, or, in case of failure, it returns a DB_ERROR object. For creating a Failable, it calls failable with the computation. It gets success and failure functions as arguments. Note the destructuring syntax here. Its not strictly required but makes the API a little nicer.</p><p>The good thing here is that the types of success and failure are such that returning something other than the given exception type to failure, or something other than the success type to success is not possible.</p><p>You can think of success as return and failure as throw. Calling failure actually throws an exceptions under the wraps to do error propagation. success simply wraps its argument into a Failable object.</p><p>To explain sequencing, I made another function for converting a Row object to a User object. This can also fail and give a PARSE_ERROR.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c9490bcce7419ad1e49a47ab466a404e/href">https://medium.com/media/c9490bcce7419ad1e49a47ab466a404e/href</a></iframe><p>Now comes the fun part. How to we call both of these in sequence without explicit error handling, while making sure that an error on any step will be propagated up the call stack?</p><p>Here’s a simple function that uses these two functions to get a user from the database.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bd471e77d835217255d0fe00e534c8fd/href">https://medium.com/media/bd471e77d835217255d0fe00e534c8fd/href</a></iframe><p>As you can see, ther’s no explicit error handling done on each step. If getUserRow fails, the the computation stops at the call site and the error is propagated. run function makes sure that if its argument function returns a Failable value having an error, it is thrown. The failable function makes sure that the exceptions thrown by run are converted into Failable values.</p><p>Also, run can only be called with a function returning a Failable whose error type is a subtype of the error type of itself. You can test this by removing | DB_ERROR from the type signature. This will result in a type error on the call to getUserRow. We need to either change the type of getUser to include the thrown DB_ERROR, or we need to “catch” and handle it.</p><p>The way we can catch a failable computation is by calling it directly instead of passing it to run. If we call it directly, we get a simple object of Failable type that we can check for error using simple if statements. Again, if isError is true, an error will be present and if its false, a value is returned.</p><h3>The implementation</h3><p>If you understand the type and semantics of failable function, its straightforward to implement. I won’t bother explaining much and will just give it to you in code. The most interesting thing about it is the fact that failable needs to differentiate between exceptions thrown by run blocks and other exceptions. It should catch the ones thrown by run and convert them to Failable objects with isError: true and throw the other exceptions as it is. This is done by creating a helper class Failure. run wraps the error value of its computation into this type and throws it. Now, failable can simply check if the error was thrown by run using an instanceof Failure check. AFAIK, making a new class/prototype is the only foolproof way to check if an object was created by a particular function. You obviously won’t expose this Failure class to the outside world so that its instances can only be created by run.</p><p>Here’s the implementation.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7e575a05dd1e05e37f688d78541a47a2/href">https://medium.com/media/7e575a05dd1e05e37f688d78541a47a2/href</a></iframe><p>You can see that success and failure are not strictly required. They just wrap up the result/error into a Failable value. Also, I saw that always creating Failables using these functions localized the type errors better.</p><h3>Better API</h3><p>Edit: Someone pointed out on Reddit that you don’t need `run` to take a function that returns a `Failable`. Simply passing the `Failable` will do and would clean up the calls.</p><p>One obvious way the API of Failable can be made better is by adding a .map method (and maybe even a .flatMap) on it. So, if you have a value of type Failable&lt;number, SomeError&gt;, you could call .map(x =&gt; x.toString()) to get a Failable&lt;string, SomeError&gt;. flatMap isn’t that important because run is kind of does that already. So, yes Failable is a monad…and monads are burritos.</p><p>Also, it would also make it way nicer if you implement .mapError method on it so that if you’re calling a function that returns a Failable with a different error type than your context, you can convert it to an error of your given type inside run so you can call it normally.</p><h3>Final thoughts</h3><p>I think this is a decent ways to have type safe exception handling in Typescript. Unlike Java, where adding a throws clause makes methods tedious to use, in this way, the throws clause is simply a generic argument to the return type. It is a simple type and it can be aliasesd to avoid cascading of type signature changes when adding a new error. Other than that, checked exceptions weren’t that bad anyway. Java’s checked exceptions occasionally made it tedious to do the right thing (adding throws clause along long chains of calls) which made them such a pain. Otherwise, it was a good idea. Heck no I think of it, Java’s checked exception problem can be easily solved by type aliases and union types.</p><p>This way is also similar to Rust’s Result type and ? operator, with worse type errors. This is expected because Rust’s handles ? operator in the compiler. Also, Rust can semi automatically converts error types if there’s an implementation of a Convert trait between those types. Rust is one of the languages that has really good error handling thanks to the ? operator and I hope other languages steal this idea.</p><p>I might package this into a library if I get the time. You have the implementation here anyway if you need it.</p><blockquote>Standard Disclaimer: Don’t pay too much attention to the actual implementation just understand the type signatures and the meaning of the functions. The implementation might have bugs.</blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c4d200ee78e9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Some tips on type safety with Redux]]></title>
            <link>https://medium.com/@dhruvrajvanshi/some-tips-on-type-safety-with-redux-98588a85604c?source=rss-256be141b225------2</link>
            <guid isPermaLink="false">https://medium.com/p/98588a85604c</guid>
            <category><![CDATA[typescript]]></category>
            <category><![CDATA[redux]]></category>
            <dc:creator><![CDATA[Dhruv Rajvanshi]]></dc:creator>
            <pubDate>Sun, 12 Nov 2017 20:33:21 GMT</pubDate>
            <atom:updated>2017-11-12T20:48:54.117Z</atom:updated>
            <content:encoded><![CDATA[<p>I’ve been using Redux/Typescript in a medium sized project and I’m one of those people who don’t trust themselves at all at writing code. My first attempts at writing type safe redux code were usable but had a lot of boilerplate type annotations. After some research and with <a href="https://github.com/Microsoft/TypeScript/issues/19207">some help from Anders Hejlsberg</a> himself, I’ve come up with a few patterns that may help you in creating type safe action creators and reducers.</p><p>Obviously if you clicked on this article, you care about type safety. If you’re one of those 10xers who scoffs at type safety by saying “Type safety is for careless programmers” (an actual thing someone said to me), I would reply by saying “Seat belts are for careless drivers”.</p><p>This is a very opinionated way and there might be other ways of dealing with it but I’ll just describe mine.</p><h3>The type of an action</h3><p>An action is just an object with a type (usually a string) and a payload (which may have a different type for each type of action in your application).</p><p>We start by defining a simple type which maps from action types to the type of the payload for that action.</p><pre>type IActionMap = {<br>  &quot;<a href="http://twitter.com/announcement/PUBLISH_SUCCESS">A</a>CTION_1&quot;: IPayload1;<br>  &quot;ACTION_2&quot;: IPayload2;<br>  &quot;ACTION_3&quot;: IPayload3;<br>  ...</pre><pre>}</pre><p>IPayloadN can be any Typescript type you want.</p><p>Now, we want a type which basically is a union of all the actions described by this map.</p><p>Let’s start with a type that is a union of all our action types (the string tags not the object).</p><pre>type IActionType = keyof IActionMap;</pre><p>This is just a concise way of writing</p><pre>type IActionType = &quot;ACTION_1&quot; | &quot;ACTION_2&quot; | ... | &quot;ACTION_N&quot;</pre><p>Next, we need a generic type that takes an IActionType and gives us the corresponding payload type.</p><pre>type IActionPayload&lt;K extends IActionType&gt; = IActionMap[K];</pre><p>So, IActionPayload&lt;&quot;ACTION_1&quot;&gt; will be equivalent to IPayload1 and so on. I won’t go into details on how IActionMap[K] thing works but you can essentially pass the type of a key of an object type using [] to get the type of the key’s corresponding value type in that object type. Ignore this if you don’t understand because this type level trickery is only needed once in your application. Also note that the generic argument to IActionPayload (K) has a bound on it extends IActionType which means you can’t just pass in any type to IActionPayload. Only the types of your actions.</p><p>Next, we move on to getting the type of an action object from a given key.</p><pre>import { Action } from &quot;redux&quot;;<br>// We&#39;re inheriting from Action defined in the type definition<br>// of redux so we can pass our actions to dispatch</pre><pre>interface IActionObject&lt;K extends IActionType&gt; extends Action {<br>  type: K;<br>  payload: IActionPayload&lt;K&gt;;<br>}</pre><p>This is just saying that given an IActionType K, IActionObject&lt;K&gt; will be the type of the object with that key and the corresponding payload type from our action map. So, IActionObject&lt;&quot;ACTION_1&quot;&gt; will be equivalent to</p><p>{ type: &quot;ACTION_1&quot;, payload: IPayload1 }</p><p>Next, we can get finally the union type of all our actions by using the same type level trickery we did earlier.</p><pre>type IAction = {<br>  [P in IActionType]: IActionObject&lt;P&gt;<br>}[IActionType];</pre><p>Again, the last part may be a bit confusing because we’re passing a key type to an object type. I won’t even attempt to explain this one.</p><p>So, all of it put together,</p><pre>import { Action } from &quot;redux&quot;;</pre><pre>type IActionType = keyof IActionMap;<br>type IActionPayload&lt;K extends IActionType&gt; = IActionMap[K];<br>interface IActionObject&lt;K extends IActionType&gt; extends Action {<br>  type: K;<br>  payload: IActionPayload&lt;K&gt;;<br>}</pre><pre>type IAction = {<br>  [P in IActionType]: IActionObject&lt;P&gt;<br>}[IActionType];</pre><p>I know it looks a bit awful but the payoff is worth it.</p><p>Now, for convenience, we can make a function that makes action creators from action types.</p><pre>function actionCreator&lt;Type extends IActionType&gt;(type: Type) {<br>  return (payload: IActionPayload&lt;Type&gt;): IActionObject&lt;Type&gt; =&gt;<br>    ({type: type, payload: payload});<br>}</pre><p>This is a higher order function that returns an action creator from a given action type.</p><p>So, if you do,</p><pre>const action1 = actionCreator(&quot;ACTION_1&quot;);</pre><p>action1 is now a function that takes 1 argument of type IPayload1 and returns the action. If you try to pass a value of a type other than IPayload1 to it, the compiler will complain. Nice!</p><p>Now, your reducers can have type</p><p>(state: YourState, action: IAction) =&gt; YourState</p><p>Thanks to Typescript’s discriminated unions, if you do</p><pre>if (action.type === &quot;ACTION_1&quot;) { ... }</pre><p>action.payload will be inferred to have the type IPayload1 in the if block. There’s really no way for you to mess up the types in your reducers now.</p><p>You can be happy with that but wait there’s more.</p><h3>Getting rid of those horrible switch/cases</h3><p>Take a look at this</p><pre>export type ReducerCases&lt;State&gt; = {<br>  [T in IActionType]: (<br>    state: State,<br>    payload: IActionPayload&lt;T&gt;<br>  ) =&gt; State;<br>};</pre><pre>function createReducer&lt;State&gt;(<br>  cases: Partial&lt;ReducerCases&lt;State&gt;&gt;<br>) {<br>  return function (state: State, action: IRootAction): State {<br>    const fn = cases[action.type];<br>    if (fn) { // the &quot;as any&quot; part is a bit of a shame but ignore it<br>      return (fn as any)(state, action.payload, action);<br>    } else {<br>      return state;<br>    }<br>  };<br>}</pre><p>I won’t go into the details of the types here, but it essentially allows you do do this:</p><pre>createReducer&lt;YourState&gt;({<br>  &quot;ACTION_1&quot;: (state, payload) =&gt; { ...; return newState },<br>  &quot;ACTION_2&quot;: (state, payload) =&gt; ...,</pre><pre>});</pre><p>You obviously don’t have to handle all cases in a single reducer. If the action type is not handled, the argument state is returned. Also, payload in each “branch” of the cases is inferred correctly.</p><p>You probably should factor out the case handlers to different functions instead of writing them as lambdas for hygiene.</p><p>You might have noticed that the createReducer function is also mentioned in the redux docs. The only difference here is that this is type safe.</p><p>Also, note that you have to write out the names of the actions in the case object as a string literal. You can’t use computed properties like this</p><pre>const ACTION_1 = &quot;ACTION_1&quot;;<br>createReducer({<br>   [ACTION_1]: ...</pre><pre>})</pre><p>This is because of a limitation in Typescript that computed properties are always treated as string types. Even if you wrote a type annotation in your const declaration like const ACTION_1: “ACTION_1&quot; = “ACTION_1&quot;, you wouldn’t get type safety.</p><h3>Bonus</h3><p>You can also split your action maps across files, as I did.</p><pre>type IActionMap1 = { ... }<br>type IActionMap2 = { ... }</pre><pre>type IActionMap = IActionMap1 &amp; IActionMap2</pre><p>This is useful if your want to split your actions by domain/module.</p><h3>Conclusion</h3><p>With some simple (well…maybe not that simple but definitely write once) type definitions, you’ve prevented a lot of ways of shooting yourself in the foot. If you change the action types, you get a compiler error, changing payload type, same, matching on a wrong action type, ditto. Creating actions with wrong types, you bet. The only way you can mess up is by assigning a wrong type to an action in the action map. This will probably be caught when you try to write a reducer case for it though.</p><p>Anyway, these things have helped me a lot in my codebase.</p><p>Feedback and suggestions welcome. Cheers.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=98588a85604c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Thoughts on Redux and it’s similarities with OOP]]></title>
            <link>https://medium.com/@dhruvrajvanshi/thoughts-on-redux-and-its-similarities-with-oop-6d200f34656?source=rss-256be141b225------2</link>
            <guid isPermaLink="false">https://medium.com/p/6d200f34656</guid>
            <category><![CDATA[react]]></category>
            <dc:creator><![CDATA[Dhruv Rajvanshi]]></dc:creator>
            <pubDate>Sat, 11 Nov 2017 22:35:35 GMT</pubDate>
            <atom:updated>2017-11-11T22:39:57.485Z</atom:updated>
            <content:encoded><![CDATA[<p>You might have heard about Redux, a great library for state management for UI applications. I’ve personally used Redux to rewrite a 100k(ish) line Javascript application for better maintainability. Basically, the reason I gravitated towards Redux was that if you use Redux, a lot of your application logic becomes easy to test as you can just create a store (essentially a function/reducer), dispatch some actions to it and assert the resulting state to have the expected values.</p><p>Moreover, you can split your store into pieces that keep track of a particular slice of your application state and respond to certain actions.</p><p>It is well known that this pattern is heavily inspired by functional programming where your application logic essentially resides in a single function (a reducer in Redux terminology) which takes a function that takes the current state, an action and returns a new state. While this may look like a fundamentally different way to architect your applications, especially if you come from an OOP background, I argue that this is essentially the same as OOP.</p><p>Confused (or maybe not…I’m not assuming)? Let me explain.</p><h3>Redux in a nutshell</h3><p>Basically, in Redux, your application state resides in a single <strong>state container </strong>called a store to which you can <strong>dispatch</strong> <strong>actions</strong>. In response to the <strong>action type</strong> and the <strong>payload</strong> of the message, your store calls your <strong>reducer</strong> function that takes the current state and returns a new state. Your UI can update on every dispatch using whatever rendering techniques you’re using (in case of React, using Virtual DOM diffing, or in case of Angular, using MVVM bindings).</p><h3>Similarities with OOP</h3><p>If you’ve looked at some fundamental definitions of OOP and paid careful attention to the keywords I’ve mentioned in the last section (terms in bold font), you might have already made the connection. If not, let me translate some of these keywords into OOP jargon.</p><p>State container -&gt; Object</p><p>Dispatching actions -&gt; Method calls</p><p>Action type -&gt; Method name</p><p>Payload -&gt; Method arguments</p><p>Reducer -&gt; Method bodies</p><p>Alan Kay, the creator of Smalltalk and one of the pioneers of object oriented programming has talked a lot about message passing as being the key idea of OOP (rather than classes or inheritance).</p><p>Here’s a snippet straight out of Wikipedia page for Object oriented programming:</p><blockquote>A method call is also known as <em>message passing</em>. It is conceptualized as a message (the name of the method and its input parameters) being passed to the object for dispatch.</blockquote><p>Note that the article uses the exact term (dispatch) as Redux terminology.</p><p>Moreover, in Redux, you have separate store slices which can respond to actions. You can simulate this using separate objects for different pieces of your state. This is the whole point of OOP. To have “state containers” (objects) that can respond to different types of “messages” (method calls). This is almost exactly what a Redux store is. The key difference being that methods are separated out from the store in the form of reducers. In fact, I think the creation of stores using the “createStore” function from Redux is almost analogous to defining a class. You attach some reducers (roughly composite methods in this analogy; a single reducer stands in for multiple methods and can allow the store to react to multiple types of messages whereas a method only reacts to a single type of message, hence the use of the term “composite”) to the main store (roughly the class).</p><p>To drive the point home, here’s a code snippet from the application I’m working on right now:</p><pre>// createReducer is just returns a function that<br>// takes state and action and passes the action<br>// to the given function based on the mapping from<br>// the given object</pre><pre>export const reducer = createReducer({<br>    &quot;<a href="http://twitter.com/assignment/FETCH_DATA_SUCCESS">@assignment/FETCH_SUCCESS</a>&quot;:<br>        fetchSuccess,<br>    &quot;<a href="http://twitter.com/assignment/CREATE_SUCCESS">@assignment/CREATE_SUCCESS</a>&quot;:<br>        createSuccess,<br>    &quot;<a href="http://twitter.com/assignment/DELETE_SUCCESS">@assignment/DELETE_SUCCESS</a>&quot;:<br>        deleteSuccess,<br>    &quot;<a href="http://twitter.com/assignment/EDIT_SUCCESS">@assignment/EDIT_SUCCESS</a>&quot;:<br>        editSuccess,<br>    &quot;<a href="http://twitter.com/assignment/PUBLISH_SUCCESS">@assignment/PUBLISH_SUCCESS</a>&quot;:<br>        publishSuccess,<br>    &quot;<a href="http://twitter.com/assignment/SUBMIT_SUCCESS">@assignment/SUBMIT_SUCCESS</a>&quot;:<br>        submitSuccess,</pre><pre>    ...<br>});</pre><p>I could easily write the same thing as</p><pre>class AssignmentReducer {<br>   fetchSuccess(payload) { ... }<br>   createSuccess(payload) { ... }<br>   deleteSuccess(payload) { ... }<br>   ...</pre><pre>}</pre><p>The only difference is that the state argument to the reducer is implicit and it is stored in the instance of the class.</p><h3>Differences</h3><p>Let’s talk about the elephant in the room. Immutability. In Redux, your application level logic is purely functional, meaning that none of the application code you write changes any existing objects in memory (at least if you do it in ways the tooling around Redux expects you to use it). It just makes you write functions that take simple values/objects as arguments and return simple values/objects as results. This has the advantage of being testable (you can just call them with initial state and an action and assert the resulting state). Note your stores themselves contain mutable state. Just that your application code doesn’t need to write mutable code.</p><p>However, there’s nothing stopping you from doing the same thing with OOP. If you have objects that contain some state and they don’t depend on anything else (much like a Redux reducer), you can initialise your objects with an initial state and call a method on them, and then assert on their resulting state.</p><p>The other difference is that in redux, there’s only one store which means all your reducers can receive the same messages. This can definitely be orchestrated in an OOP setting by having an action dispatcher class that calls appropriate methods on other classes. The more you try to replicate redux in OOP, the more it will start to look like OOP flavoured Redux.</p><p>The next few sections are my own personal thoughts on the advantages/disadvantages of Redux vs OOP, good/bad decisions I made in my own Redux application that would’ve been different in an OOP setting.</p><h3>Key benefits of Redux</h3><p>In my opinion, the main advantage of Redux is that it enforces a good practice (keeping mutable state localised) on the programmer. This gives you lesser ammunition to blow your foot off (which you can still do, BTW). One way you can mess up Redux is if you have poor state design. “Poor state design” can mean a lot of things but the most significant mistake I made in practice was having deeply nested state (upto 5–6 levels of nesting) which can become a pain to manage. Other than that, the discipline enforced by the pattern was pretty useful.</p><p>Another advertised selling point of Redux is the debugging tools. <a href="https://github.com/gaearon/redux-devtools">Redux devtools</a> are seriously good and they allow you to filter your dispatched actions and inspect the differences in your state at each action. This is very useful if you don’t write tests first and mildly useful if you do.</p><p>Also, Redux devtools have time travelling debugging which means you can undo your actions from the devtools menu and replay them, and if you have hot reloading set up, you can update your reducers and have the store re run all your actions in order to reflect the state of your application as if your latest reducer was there from the start (without reloading). Hot reloading is pretty useful (again more useful if you don’t write tests first).</p><p>In about 6 months of production use, I’ve not ever needed to use the time travelling feature of Redux but maybe that’s just me.</p><p>Again all these things are possible using OOP if you enforce certain simple rules. You just need to have some way of marking your “message handler” methods in your objects. Easily possible in a language like Javascript (decorators come to mind). One could easily build devtools like Redux if one was so inclined (it’s not that hard either).</p><h3>Disadvantages of Redux</h3><ul><li>* Flame shields up: I actually like functional programming and I think it’s almost necessary for writing things like compilers. It’s just not a silver bullet.</li></ul><p>The main disadvantages that I faced with Redux were immutable updates for deeply nested objects. This was mainly because of deeply nested state schema and also I had a self enforced requirement of having almost all (99%ish) of my reducer code statically typed (using Typescript). If you give up that requirement and take it upon yourself to be extra careful, you can easily (oxymoron lol) update deeply nested objects using lodash/ramda/your own functions that take a list of strings and update the deeply nested key. Unfortunately, if you want static typing, you need to write deeply updates using the spread syntax which can get tedious and in some cases, error prone. There are some other approaches (like Lenses, as in Haskell like lenses) which can be used but I didn’t want my code to be unreadable to the average programmer who’s gonna maintain the code (general rule of thumb, don’t be clever).</p><p>The only good solution I found was to avoid having deep nesting in your state schema in the first place. The reason I even had deeply nested structures is because my backend is in MongoDB (not my choice, don’t judge me) and I wanted to make my app state as similar to the DB (if you can even call Mongo a DB lel) schema as possible to reduce impedance mismatch. This was a pretty bad decision in hind sight. I plan to refactor it into a schema with lesser degree of nesting (whenever the deadlines get relaxed).</p><h3>Conclusion</h3><p>So, I’ve tried to compare OOP and Redux (primarily FP) ways of state management here. Hopefully, you see the parallels between the two approaches as well as the differences.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6d200f34656" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Simulating Haskell’s do notation in Typescript]]></title>
            <link>https://medium.com/@dhruvrajvanshi/simulating-haskells-do-notation-in-typescript-e48a9501751c?source=rss-256be141b225------2</link>
            <guid isPermaLink="false">https://medium.com/p/e48a9501751c</guid>
            <category><![CDATA[typescript]]></category>
            <category><![CDATA[monads]]></category>
            <category><![CDATA[functional-programming]]></category>
            <dc:creator><![CDATA[Dhruv Rajvanshi]]></dc:creator>
            <pubDate>Thu, 26 Oct 2017 20:10:59 GMT</pubDate>
            <atom:updated>2017-10-26T20:10:59.138Z</atom:updated>
            <content:encoded><![CDATA[<p>Haskell has convenient syntax for monads called “do notation” that is useful for flattening out nested Monadic binds (sort of equivalent to .then method in Javascript/Typescript). If you don’t know what monadic means, it will become clear in the following sections. If you’re familiar with async/await, it is a somewhat more powerful version of the do notation with one limitation. It is restricted to the built in Promise type. Promise happens to be a monad because it has the .then method. Unfortunately, async/await is a missed opportunity IMO because monads come in all shapes and sizes. It would be helpful to have some way to flatten out nested calls to the .then method for any monadic type. Well, there is (sort of). Keep reading.</p><h3>Motivation</h3><p>You may skip this section if you’re already familiar with Haskell do notation/Scala’s for/yield/F# computation builders.</p><p>A simple type built into Haskell is the Maybe type (which is also a Monad). It represents an optional value which can either be a value or nothing. The only way to get the value out of it is to pattern match (which you can think of as a more powerful if/else) over it so, you are forced to handle cases when the result is nothing. For example,</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/11a6d47e79a73d8d81d6971a70288e89/href">https://medium.com/media/11a6d47e79a73d8d81d6971a70288e89/href</a></iframe><p>Here, someFailableComputation can maybe return an Int value, or return Nothing.</p><p>When we call the function in main function, we are pattern matching over the result of the computation (which is the case… of thingy). When it succeeds, (Just x), we bind the result to the variable x and print (x + 1). Otherwise we print “Failed”. Simple. Type information flows through so the type of x is known to be Int at compile time.</p><p>Now, what if we have multiple computations that we need to run in sequence that use the results of the previous computations (for example, a series of network calls)? We can do it the usual way by pattern matching.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2b2f3dfcc0d79b0a3ed6edb33e381893/href">https://medium.com/media/2b2f3dfcc0d79b0a3ed6edb33e381893/href</a></iframe><p>As you can see, we have nested pattern matches here. It sort of looks okay here, but if we have more computations that can fail, it can get ugly soon. Fortunately, using do notation, we can set up a function that “short circuits” the whole thing in case of a Nothing being returned in the middle.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0ca989c44ddbcc5e9ca5a5d914ecb1eb/href">https://medium.com/media/0ca989c44ddbcc5e9ca5a5d914ecb1eb/href</a></iframe><p>See, much better. The control flow is more obvious and the boilerplate of pattern matching has been taken care of by the syntax. What would have been a series of nested pattern matches is now flattened out vertically.</p><p>If this looks familiar to async/await, it is. For example, look at this piece of code in Javascript.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/97481e14b275ab57fc860af84358441b/href">https://medium.com/media/97481e14b275ab57fc860af84358441b/href</a></iframe><p>Now that looks callback hellish. I probably missed out some parenthesis so don’t look too hard at it. You get the idea.</p><p>Rewriting it using async/await gives us this.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f38fbf7a3654bd2392f77a93ae64c1bb/href">https://medium.com/media/f38fbf7a3654bd2392f77a93ae64c1bb/href</a></iframe><p>Much better.</p><p>Despite the async/await version being superior in one way (closer to the regular syntax of the language; can be used in if statements, loops, etc) to the Haskell version, which restricts the &lt;- binds (similar to await in the JS version) to do blocks, it is more restricted in another sense that only Promises currently support async/await. Still, both help in flattening out nested calls to then or &gt;&gt;= in Haskell. Can we have something in Typescript that flattens out .then calls for arbitrary monads without losing type safety?</p><p>The answer is yes.</p><h3>My solution</h3><p>I have used Typescript’s mapped properties to simulate a “scope” of variable assignments which can be chained using method syntax.</p><h4>Defining the Maybe class</h4><p>Lets start by defining a Maybe class in Typescript. (Install typescript beforehand by doing sudo npm install -g typescript first). Create a file Maybe.ts.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ad5179e99536376b68f804fddcb8ace1/href">https://medium.com/media/ad5179e99536376b68f804fddcb8ace1/href</a></iframe><p>Things to note in the Maybe class.</p><ul><li>The constructor takes a value of type A | null and creates a new value of Maybe&lt;A&gt;. Basically, if _value is null, it’s treated as Nothing, otherwise, it’s treated as Just. Also, constructor is private and you can create Just or Nothing values using the static functions Just and Nothing.</li><li>The match method takes an object of cases and calls the appropriate case by checking this._value.</li><li>The then method is the standard monadic bind function. It matches over the current Maybe and if it’s Just, it calls the argument function with this.value otherwise, returns a Nothing.</li></ul><p>If you run this script by running tsc &amp;&amp; node Maybe.js in the directory where you created the file, you should get the following output</p><pre>Got Just(23)<br>Got Nothing</pre><h4>The actual trick</h4><p>Now, here’s a method that you can add to the class that will make flattening possible.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5248e9090e53e0de5ed8d8de073d9078/href">https://medium.com/media/5248e9090e53e0de5ed8d8de073d9078/href</a></iframe><p>The most interesting thing about this method is the type signature. It uses some relatively advanced Typescript features (intersection types, union types, mapped types). Mapped types is the one feature that’s not present in most other languages that allows the function to be well typed.</p><p>Before looking more closely into the guts of the type signature, let’s look at how it will make our code look.</p><pre>console.log(<br>    Maybe.Just({})<br>    .assign(&quot;x&quot;, positive(23))<br>    .assign(&quot;y&quot;, positive(23))<br>    .assign(&quot;z&quot;, (scope) =&gt; positive(scope.x - scope.y))<br>    .then(scope =&gt; Maybe.Just(scope.z))<br>    .match({<br>        Just:result =&gt; `Just(${result})`,<br>        Nothing:() =&gt; &quot;Nothing&quot;<br>    })<br>) // Just(0)</pre><pre>console.log(<br>    Maybe.Just({})<br>    .assign(&quot;x&quot;, positive(23))<br>    .assign(&quot;y&quot;, positive(25))<br>    .assign(&quot;z&quot;, (scope) =&gt; positive(scope.x - scope.y))<br>    .then(scope =&gt; Maybe.Just(scope.z))<br>    .match({<br>        Just:result =&gt; `Just(${result})`,<br>        Nothing:() =&gt; &quot;Nothing&quot;<br>    })<br>) // Nothing</pre><p>As you see, we start our chain with a Maybe.Just({}) value, which will keep our “scope” inside it. Each call to .assign will attach a new value to our scope object with the given key. Thanks to Typescript’s mapped types, our scope object at each step will contain the keys assigned by the previous steps so the compiler knows that result in the final step is a number.</p><p>Pretty cool if you ask me but then I’m biased ;)</p><p>Now, lets break down the type signature of the .assign method.</p><pre>assign&lt;K extends string, B&gt;(<br>        k: K, other: (Maybe&lt;B&gt; | ((a: A) =&gt; Maybe&lt;B&gt;))<br>    ): Maybe&lt;A &amp; {[k in K]: B}&gt;</pre><p>This method takes two generic parameters, K and B. K should be a subtype of string because we will be attaching it to an object. K is the type of the key you supply and B is the type of the return value of the Maybe you’re using to do the assignment. For ease of use, the other parameter can either be a Maybe&lt;B&gt; or a function from the current type A to Maybe&lt;B&gt;.</p><p>The return type is Maybe&lt;A &amp; {[k in K]: B}&gt;. It simply means that the result will be a Maybe of the current Maybe&#39;s contained value with an additional field K which will contain a value of type B. So, if you have a Maybe&lt;{x: number}&gt;, and you call .assign(&quot;y&quot;, Maybe.Just(&quot;asdf&quot;)) on it, the resulting type will be Maybe&lt;{x: number; y: string}&gt;. We need the type of the key to be generic K for type safety to be maintained. If we had used string as the type of the k parameter, it wouldn’t work. Basically, typescript can narrow down string types to string literal types so when you use a generic parameter K extends string, the .assign(&quot;y&quot;, ...) will infer the type K to be &quot;y&quot; as opposed to string.</p><p>There’s hardly anything interesting going on in the body of the assign method. It calls .then on the Maybe values. It also checks if the second argument is an instance of Maybe or if it’s a function. If it’s a function, then it calls it with the current Maybe&#39;s value to get a new Maybe. Then it simply calls .then on it. If you stare at it for long enough, you should be able to figure it out. Note that when calling Object.assign to attach the new result to the scope, I’ve put a cast to any type. This is because Object.assign requires it’s arguments to be objects. This means calling assign on a Maybe that contains a non object type, it will fail at runtime. We can actually put a bound on the class parameter A by A extends object but then we wouldn’t be able to create Maybe&lt;number&gt;, Maybe&lt;string&gt;, etc. Just make sure that you only call .assign on object type Maybes.</p><h4>For other monads</h4><p>.assign method only uses .then method so you can attach it to any type that has a then method with the correct type. Unfortunately, Typescript lacks Higher-Kinded types so it’s not possible to write a generic assign method for any type in a type safe manner. But because it will only be defined once per monad, you can ignore type safety in this case and just copy and paste the definition for your type, replacing YourType with whatever your actual type is as long as YourType has .then and .of methods of the correct types.</p><pre>public assign&lt;K extends string, B&gt;(<br>        k: K, other: (YourType&lt;B&gt; | ((a: A) =&gt; YourType&lt;B&gt;))<br>    ): YourType&lt;A &amp; {[k in K]: B}&gt; {<br>        return this.then(<br>            a =&gt; {<br>                const m = other instanceof YourType<br>                    ? other : other(a);<br>                return m.then(<br>                   // define a static method `of`<br>                   // for YourType which takes an A<br>                   // and returns a YourType&lt;A&gt;</pre><pre>                   b =&gt; YourType.of(<br>                        Object.assign(<br>                            {}, a, {[k.toString()]: b}<br>                        ) as any<br>                    )<br>                )<br>            }<br>        );<br>    }</pre><p>You can even make a function that takes YourType as a parameter and returns the body of this method so you don’t have to copy and paste. It won’t be type safe of course but you can trust the implementation is correct because it’s pretty short.</p><h3>Caveats</h3><ul><li>I haven’t tried this out in anything serious so I don’t know if it will be as elegant in more complex scenarios even though I don’t see why not.</li><li>Be careful with scoping. If you have multiple assigns to the same key in a single chain, the most recent one will be used (which is what you’ll probably expect). Also, don’t assign values of different types to same keys in a single chain because the type of that key would be inferred as a union of all the assignments.</li><li>The Maybe type we implemented here will treat Maybe.Just(null) as Nothing because we’re comparing the value with null in the then method. If you’re implementing it for anything serious, you’d probably want another private member which decides whether the value is Nothing or Just.</li><li>Monads don’t compose so obviously you can’t use another monadic type (something like Result&lt;T, E&gt;) value for assigning to a chain of monadic values of another type. This is apparent in the type signature of .assign method.</li><li>As I pointed out earlier, there’s a cast to any in the assign method. Calling this on a Maybe&lt;T&gt; where T is not an object fill fail at runtime. Always start with Maybe.Just({}) to start with an empty scope. Also, don’t assign to types you care about, that may lead to unexpected results. Start with empty scopes.</li></ul><h3>Conclusion</h3><p>While this post only showed one of the simplest monads (Maybe) but you can go crazy with your custom monads. Want to have an implicit environment (Reader monad), accumulate values (Writer monad), keep implicit state (State monad), do error handling (Error monad) or a combination of all, roll your own monad type! This is actually pretty useful if you’re writing a compiler or something where you need to keep some state (State), have a scoped type environment (Reader), collect type errors (Writer) and do error handling (Error).</p><p>While this may not be as elegant as async/await, Haskell do, Scala for, etc, it still does the job of flattening out nested thens pretty well.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e48a9501751c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Type inference for beginners — Part 2]]></title>
            <link>https://medium.com/@dhruvrajvanshi/type-inference-for-beginners-part-2-f39c33ca9513?source=rss-256be141b225------2</link>
            <guid isPermaLink="false">https://medium.com/p/f39c33ca9513</guid>
            <category><![CDATA[compilers]]></category>
            <category><![CDATA[generics]]></category>
            <category><![CDATA[polymorphism]]></category>
            <dc:creator><![CDATA[Dhruv Rajvanshi]]></dc:creator>
            <pubDate>Sat, 21 Oct 2017 11:08:11 GMT</pubDate>
            <atom:updated>2017-10-21T11:08:11.714Z</atom:updated>
            <content:encoded><![CDATA[<h3>Type inference for beginners — Part 2 (Polymorphism)</h3><p>In the <a href="https://medium.com/@dhruvrajvanshi/type-inference-for-beginners-part-1-3e0a5be98a4b">last part</a>, we implemented type inference for simply typed lambda calculus. In this part, we’ll extend our type system with <a href="https://en.wikipedia.org/wiki/Parametric_polymorphism">parametric polymorphism</a> or generics.</p><p>Note: There were some mistakes in the last part so check out the edit notes at the bottom.</p><h3>Motivation</h3><p>There are some functions that need their argument to be of a specific type. For example, a function “add” can add two Int values. It wouldn’t make sense to add two Bool values. However, there can be some functions which don’t care about the actual type of their argument. Their body may not enforce any constraints on the type of their arguments. They are known as polymorphic functions. The simplest example of a polymorphic function is the identity function which simply returns its argument as it is.</p><ul><li>(x) =&gt; x</li></ul><p>The so, this function should work for Int, Bool, or any other type. Its return type is the same as the type of its argument. In our current system, such a function is not expressible as we need to assign a concrete type to the function.</p><h3>Universal quantification</h3><p>Polymorphic types are expressible through the means of universal quantification. The type of our identity function from the previous section can be written as</p><ul><li>forall A. A -&gt; A</li></ul><p>This says that for all types “A”, the type of this function is A -&gt; A. Such types, with forall quantifiers (also called universal quantifiers, universal because they quantify over all types) may be “instantiated” when they are used with a concrete type. Type instantiation is similar to calling a function. Just like when you call a function (x) =&gt; x with 1, we replace the instances of x in the body with 1 and remove the parameter, instantiating a quantified type is equivalent to replacing the instances of the “type parameter” in its body with the “type argument” and removing the forall clause. For example, if you call identity with an Int argument, all instances of “A” should be replaced with “Int”, giving the type</p><ul><li>Int -&gt; Int</li></ul><p>Same for other types.</p><p>Quantified types are sometimes called type schemes.</p><p>There are other kinds of quantification as well like bounded quantification and existential quantification. Bounded quantification is useful when we need to apply other constraints on the generic type variables. This is commonly seen in interface types. We’ll look at bounded quantification later when we implement interfaces.</p><h3>Where to allow quantification?</h3><p>If you have problems understanding this section, don’t worry. Just skim through it and move on.</p><p>The language designer can choose where to allow quantifiers in the type system. This can range from highly restricted, only allowing quantifiers at the top level, to completely unrestricted, allowing quantifiers to appear anywhere a type can. The depth at which a quantifier can appear is commonly known as “Rank” of the type. For example, under Rank 0 types are simply non polymorphic types we implemented in the last part. Rank 1 types mean a quantifier can only appear at the top level. So, under Rank 1 restriction, the following type is valid</p><ul><li>forall A. A -&gt; A</li></ul><p>Whereas this is invalid</p><ul><li>forall A. A -&gt; (forall B. B -&gt; B)</li></ul><p>In this specific case, we can simply move the inner quantifier to the top level without changing the type so, in Haskell, this actually counts as a Rank-1 class as its equivalent to</p><ul><li>forall A, B. A -&gt; B</li></ul><p>Moving the quantifier outside is not possible in all the cases, for example,</p><ul><li>forall B. (forall A. A) -&gt; B</li></ul><p>Can’t be converted to Rank-1 so to represent this type in Haskell, you would need to turn on Rank-2 or Rank-N compiler extension.</p><p>Classical Hindley-Milner type system allows Rank 1 types. This is because of the fact that in an arbitrary rank system, type inference is undecidable, i.e. it is impossible to infer types of some well typed expressions without some type annotations. Also, arbitrary rank type inference is harder to implement.</p><p>For now, we’ll implement Rank-1 types where the forall quantifier can appear only on certain places.</p><h3>Let expressions</h3><p>To ease implementation, we won’t allow function arguments to have polymorphic types. We’ll add another type of binding which allows polymorphic types to be assigned to variables. These are let bindings. This type of polymorphism restricted to let bindings is also known as “let-polymorphism”.</p><p>A simple let expression can be</p><ul><li>let x = 3 in plus(x)(1)</li></ul><p>Here, variable x is being bound to the value 3 in the body (plus(x)(1)) of the let. Don’t confuse this with let/var statements in other languages. This is an expression which evaluates its body. This expression will return 4 when evaluated. In statement oriented languages, let statements don’t have a body. They just bind a variable to an expression’s value from the next statement to the rest of the block.</p><p>So, let expressions will be used to assign polymorphic types to variables. For example, our identity function can be defined and used as</p><ul><li>let id = ((x) =&gt; x) in id(1)</li></ul><p>The id binding will be visible in the body of the let.</p><h3>Type checking let bindings</h3><p>Let’s go through the process of type checking this snippet to informally to get an intuition for the process.</p><ul><li>let id = ((x) =&gt; x) in id(1)</li></ul><p>We start with the let declaration. We start by taking the RHS of the assignment ((x) =&gt; x) and calling infer on it. As we know from the previous part, the inferred type of the RHS would be (T0 -&gt; T0) where T0 is a newly generated type variable.</p><p>This will take us back to the call to infer for the let expression. We have the type of the RHS of the let binding (T0 -&gt; T0) and our environment is empty.</p><p>Now, we can see intuitively that (T0 -&gt; T0) should be polymorphic. So we can generalise it to a polymorphic type (forall T0. T0 -&gt; T0).</p><p>Notice that we can’t just quantify over all the type variables. If a variable occurs in free the environment, that means it could be bound outside the scope of the current let binding. Occurring free means not bound by a quantifier. For example, A is free in the type (A -&gt; A), but it’s not free in (forall A. A -&gt; A).</p><p>So we have to check the environment for free occurrences of the type variables in the type we’re generalising. If they don’t have free occurrences in the environment, we can quantify over them. In this case, the environment was empty so, we can generalise over T0.</p><p>So, back to the inference. Now, we have found the most general type for the RHS of the let, we can add a binding to the environment (id: forall T0. T0 -&gt; T0).</p><p>Now, we can infer the type of the let expression’s body (id(1)). We start by trying to infer the type of variable “id”. We look it up in the environment. We find (forall T0. T0 -&gt; T0). Now, infer function needs to return a regular type. We have a polymorphic type. So we need to “instantiate” the polymorphic type by removing the quantifier. We can do this by taking the quantifier’s name, generating a new type variable for it and replacing its instances in the quantified type with the new generated type variable. So, this would give us (T1 -&gt; T1). We still don’t know what T1 actually is. We created a new type variable because once we infer the actual type of T0 (Int in this case), we don’t want T0 to be Int right? Otherwise, other calls to id will require their argument to be of type Int. So we generate a new variable. Anyway, call to infer on the variable id returns (T1 -&gt; T1). Now, we infer the type of the argument which will give us Int along with the substitution (T1: Int) as usual. So, the type of (id(1)) will be Int, and the type of the entire let expression will be the same.</p><p>That was a lot of hand waving, so lets look at the actual code.</p><h3>The code</h3><p>First, we add a new type for let expressions.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/aed10da87e883fe0d734f7828003e61d/href">https://medium.com/media/aed10da87e883fe0d734f7828003e61d/href</a></iframe><p>A let node has a name, RHS expression, which is bound to the name, and a body.</p><p>Next, we define the type for Forall quantified types.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8c38dee9f1f040124c47e5737cf8fd6b/href">https://medium.com/media/8c38dee9f1f040124c47e5737cf8fd6b/href</a></iframe><p>It can quantify over multiple type variables (quantifiers).</p><p>Note that we don’t extend our Type union to include the Forall type. This is because we want to restrict the places where a forall can occur. It shouldn’t be allowed at all places where a Type can occur.</p><p>The environment can now contain types as well as Forall. So we update the Env type to reflect that.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1128d0d32f076f0e944f0c953a618cca/href">https://medium.com/media/1128d0d32f076f0e944f0c953a618cca/href</a></iframe><p>We need to add a function to apply a substitution to a Forall type.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/39c2ad7f7e04d59cb60acda2d3063be4/href">https://medium.com/media/39c2ad7f7e04d59cb60acda2d3063be4/href</a></iframe><p>As you can see, we don’t replace the types that are quantified over by the forall, because the forall bindings “shadow” the previous bindings with the same name. This is similar to how function bindings work. A the function parameter variable hides variables with the same name from outer scopes. So we clone the given substitution and delete the quantified names from it, then apply the substitution to the type of the forall. Note the use of object spread syntax here. { …subst } is equivalent to writing Object.assign({}, subst).</p><p>We need to change the signature of our addToContext function to accept Forall along with Type.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/52960feb5bd5f70f5cd75fb0e4206ebc/href">https://medium.com/media/52960feb5bd5f70f5cd75fb0e4206ebc/href</a></iframe><p>Next, we need to add some functions for getting free type variables from different types. Remember free vars are the type variables that aren’t bound by a quantifier. So, for Forall types, free variables are the free variables of its body minus the quantifiers. Here are those functions.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f70bd4b83104457365deb8af370d372b/href">https://medium.com/media/f70bd4b83104457365deb8af370d372b/href</a></iframe><h4>Instantiation</h4><p>We need a function to instantiate Forall types. As I said earlier, it involves generating new type variables for each quantified variable and substituting them in the body of forall and returning it.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/350d0eea3e4bfff35d5ca771ad3fda53/href">https://medium.com/media/350d0eea3e4bfff35d5ca771ad3fda53/href</a></iframe><h4>Inference for vars</h4><p>Now, since our environment can contain forall as well as regular types, we need to update our inference for variable expressions. If the variable name is bound to a type, then it is the same as before, however, if its a Forall, we need to instantiate it and then return it.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bc36aeaaafefe5a3316fa5eed3584da1/href">https://medium.com/media/bc36aeaaafefe5a3316fa5eed3584da1/href</a></iframe><p>Note that I’ve separated out a new function inferVar that handles inference for vars from the main infer function. The same for other node types. The switch case in infer just matches over the node type and calls the appropriate specific infer function (inferVar, inferCall, etc). Just to make the code a little bit cleaner.</p><h4>Generalisation</h4><p>Let bindings can bind polymorphic values so we can generalise the RHS type of the let binding to a forall type.</p><p>Here’s the generalize function</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/eba0d1cbfda82adc3b1fd58ee016a228/href">https://medium.com/media/eba0d1cbfda82adc3b1fd58ee016a228/href</a></iframe><p>It takes the free vars in the given type and puts them to the left hand side of a forall. Note that we first check if the type variable is not free in the environment. We can’t generalize free vars in the environment because they may be bound to specific types later.</p><h4>Infering Let expressions</h4><p>Now we move on to inference for let expressions.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8668f4adfcfc56ed860b1ca99cc6a3a3/href">https://medium.com/media/8668f4adfcfc56ed860b1ca99cc6a3a3/href</a></iframe><p>So we infer the RHS of let, generalize the type and add the generalized type to the context environment. Then infer the type of the let body under the new environment. Then we return the body’s inferred type and the composed substitutions from previous steps.</p><p>Now, we can check our inference for polymorphic types.</p><p>Here are a few helper functions.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/40e00d96dcd306220922da83c8e15f98/href">https://medium.com/media/40e00d96dcd306220922da83c8e15f98/href</a></iframe><p>And here are some tests.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ef9b5b35f524be51675980f28a361040/href">https://medium.com/media/ef9b5b35f524be51675980f28a361040/href</a></iframe><h3>Conclusion</h3><p>In this part, we added a form polymorphism (let-polymorphism) to our language. This makes our type system a lot more expressive. Again, play around with it. Here’s a very simple exercise. Add a `throw` function to the initial environment. It can take one parameter of any type and returns a value that can be used in any expression regardless of what type of expression is expected there. Think of the type of throw. Hint: It’s polymorphic obviously.</p><p>In the next part, we’ll continue our journey further and add records to our language. They will allow us to represent key value pairs in a concise manner. They will be statically typed of course. We will also have a discussion about nominal and structural typing.</p><p>That’s all for now folks. Have a nice day.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f39c33ca9513" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Type inference for beginners — Part 1]]></title>
            <link>https://medium.com/@dhruvrajvanshi/type-inference-for-beginners-part-1-3e0a5be98a4b?source=rss-256be141b225------2</link>
            <guid isPermaLink="false">https://medium.com/p/3e0a5be98a4b</guid>
            <category><![CDATA[compilers]]></category>
            <category><![CDATA[functional-programming]]></category>
            <dc:creator><![CDATA[Dhruv Rajvanshi]]></dc:creator>
            <pubDate>Fri, 20 Oct 2017 11:35:11 GMT</pubDate>
            <atom:updated>2017-11-08T18:17:40.185Z</atom:updated>
            <content:encoded><![CDATA[<p>Greetings. This is a tutorial series for gradually implementing type checking/inference.</p><p>*Also see the EDIT note at the end</p><p>We’ll start with a very simple language (simply typed lambda calculus) and gradually add features to it and by the end, we’ll have a compiler with the following features:</p><ul><li>Proper error reporting</li><li>Parametric polymorphism (also called generics)</li><li>Records/Structs</li><li>Methods</li><li>Tuples (also called product types)</li><li>Algebraic data types (also called tagged union/sum types)</li><li>Pattern matching</li><li>Assignments</li><li>Blocks</li><li>Modules</li><li>Interfaces/typeclasses</li><li>Sub-typing</li><li>Higher kinded types</li><li>Rank-N types</li></ul><p>If you don’t know what some or any of these things are, don’t worry, I’ll assume 0 knowledge of type theory and will explain things as we go along.</p><p>Also, to make it accessible to most people, I’ll be using Typescript as an implementation language.</p><p>If you don’t know Typescript, don’t worry, it’s basically Javascript with type annotations. You can ignore the type annotations in the code and pretend it’s Javascript.</p><p>With that out of the way, let’s get started shall we?</p><h3>In this part</h3><p>Well implement type inference and checking for a very simple language called lambda calculus. The entire type checker is less than 200 lines so it’s easy to digest.</p><h3>Syntax</h3><p>The only syntactic category in lambda calculus is expressions. An expression is the thing that can appear on the right hand side of an assignment statement in most languages. I’ve changed the actual syntax of the original lambda calculus slightly so that it would be familiar to beginners. You may skip this section after a brief glance at the snippet below if you already know lambda calculus.</p><p>So, here’s a description of the syntax</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/59fbc37511c51a5c07d4ce9e34a846d9/href">https://medium.com/media/59fbc37511c51a5c07d4ce9e34a846d9/href</a></iframe><p>Basically, what this says is an expression can be one of the following things</p><ul><li>An integer literal (e.g. 0, 1, …)</li><li>A variable (e.g. x, y, abc, etc)</li><li>A function (e.g. (x) =&gt; increment(x)); Same as javascript but with only one argument.</li><li>Call (e.g. f(1)) also with only one argument</li><li>If expression (e.g. if (isEven(x)) 1 else 2 )</li></ul><p>There are a few things to note here.</p><p>Firstly, all functions take 1 argument and return 1 value. For functions with multiple arguments, we use a technique called “currying”. Basically, you write functions with multiple parameters like this:</p><ul><li>(x) =&gt; ((y) =&gt; (add(x))(y))</li></ul><p>Function arrow associates to the right and calls associate to the left so you can write it more concisely as</p><ul><li>(x) =&gt; (y) =&gt; add(x)(y)</li></ul><p>If you call this function with 1 argument (x), it will return another function which takes 1 argument (y) which calls add with x and the calls the result of that again with y.</p><p>Secondly, “if” is an expression instead of statement in most languages. This means it “returns” a value when evaluated, so you can write something like</p><ul><li>(condition) =&gt; if (condition) 1 else 2</li></ul><p>When called, with true, this function will return 1, otherwise, 2.</p><h3>Syntax Tree</h3><h4>What?</h4><p>You may skip this sub section if you know what syntax trees are.</p><p>Basically, any valid program that the user types into a file is represented as a “Tree” of “Nodes”. A tree is a structure which has nodes that contain information and can optionally have child nodes. A parser takes the source text and converts this into a tree structure that can be easily manipulated by the compiler. We won’t be implementing a parser right but we will describe the tree nodes for each type of expression.</p><p>It will become more clear when we se the code.</p><h4>Expressions</h4><p>Here’s the type representing an expression tree.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a75cd9a0d7161be46e204c1d896e2635/href">https://medium.com/media/a75cd9a0d7161be46e204c1d896e2635/href</a></iframe><p>As you can see, each expression node has a “nodeType” property, which indicates what type of expression this node is, and some values associated with the corresponding type. If you don’t know typescript, the ‘|’ operator means the type Expression can have one of these structures. An expression with type “Int” has a value property containing the number it represents. A “Var” type node contains the variable name. Most of this should be self explanatory.</p><p>So, for example, here’s an expression and it’s tree object</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/277b8ab356a0196d4564fc0984e5988e/href">https://medium.com/media/277b8ab356a0196d4564fc0984e5988e/href</a></iframe><p>Thankfully, we don’t have to write these trees by hand in practice as parsers convert our source text into these trees. Real compilers store a bit more information with each node like positions in original source so that when an error occurs, the user can be notified exactly where the error occurred and maybe show the snippet of offending code as well. We’ll add that later.</p><h4>Types</h4><p>Apart from expressions, we also need to represent types as trees. Each expression has a known type at compile time. Since there are no type annotations (yet) in our source language, the type checker that we’re writing has to figure out the type of each expression (and it’s sub expressions, recursively). The types can be simple types (like Int, Bool, etc) or function types (for example, Int -&gt; Int is a function that takes an Int and returns an Int). Because function types contain other types, the tree type is recursive.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/357eb022c46c2ebeb3f6e6ed04b4a713/href">https://medium.com/media/357eb022c46c2ebeb3f6e6ed04b4a713/href</a></iframe><p>“Named” types are the types that have been declared. They include builtin types like Int and Bool, and in the future, they’ll also be used to represent user declared types like record types.</p><p>“Var” types are type variables. They can stand in for any type. They can be “instantiated” on use. Right now, we’ll use them to represent types that haven’t been inferred yet.</p><p>“Function” type is self explanatory. It’s the type of a function that takes a value of type “from” and returns a value of type “to”.</p><h3>Typechecker</h3><p>Now, to the exciting part!</p><p>So, we’ll be implementing type inference and checking using a method called <a href="https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system">Hindley-Milner</a>. Most modern statically typed functional languages (Haskell, ML, F#) use some variation of it. Note that the main goal of HM was to implement type inference for polymorphism. Right now, we’ll ignore the polymorphism part and focus on the rest of the algorithm.</p><p>Here’s how it works. Our type checker maintains an “environment”, which is simply a mapping of variable names and their inferred type. We start with an empty environment and start traversing the expression tree recursively from top to bottom. As we infer types of variables, we add them to the environment.</p><p>At the core of our type checking is a function called “unify”. It takes two types and tries to match them. If the types don’t match, it returns a type error.</p><p>So, our inference function, using unification, matches the types of the expression tree, and it ensures that they fit.</p><h4>Integers</h4><p>Let’s start with the most basic type inference function and gradually add stuff to it. Here’s the starting point.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2ffdc541d2d3e8386457cc122c14c643/href">https://medium.com/media/2ffdc541d2d3e8386457cc122c14c643/href</a></iframe><p>As you can see, when you call it with an expression of nodeType “Int”, you get a named type “Int”.</p><h4>Variables</h4><p>Now, think about variables. For variables, we need a type environment that keeps track of the types of the variables in scope. When a variable is encountered, we need to look up the variable name in the scope. If it’s found in the environment, we return the type from the environment, otherwise, we throw an error saying that variable is not in scope.</p><p>So, we need to modify our infer function to take an additional argument, which is the environment of variables in scope.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/94795e3245c6c53b6a291bf1867158bb/href">https://medium.com/media/94795e3245c6c53b6a291bf1867158bb/href</a></iframe><p>We just added a case for “Var” nodeType. This should be pretty straightforward.</p><h4>Functions</h4><p>Now, we’ll look at something a little bit more involved. Let’s think about the case of functions. When we see a function, we need to infer the type of it’s body. So, we need to make a recursive call to infer with the function’s body. Also, the body may refer to the parameter of the function, so it needs to be added to the environment. We don’t have to add it permanently, only for the next call, so we make a copy of the environment with one extra member which is the parameter. But here we run into a problem. The environment needs a name and a type. We have a name from the param property of the expression node, but we don’t know it’s type. Here’s where type variables come in. We simply generate a new unique type variable to stand in for the parameter’s type. Then we can add &lt;param_name, new_type_variable&gt; to the environment and pass the new environment and the function’s body to the infer function.</p><p>Now, during the call to infer for the function’s body, we may find the actual type for the param’s generated type variable. In general, infer function may find the actual types that these type variables in the environment stand for. Here’s an example</p><ul><li>(x) =&gt; not(x)</li></ul><p>If we know that “not” has the type Bool -&gt; Bool, then x must have the type Bool.</p><p>So, the infer function must return an additional result along with the type of the expression. It must also return a mapping of type variables to types. This mapping is called a substitution. Be careful not to confuse substitutions with environments. A substitution maps type variables to types whereas an environment maps variables (which are expressions) to types.</p><p>So now back to the case of functions. Once we’ve called infer for the body, we’ll get back a type (which is the type of the body) and a substitution which may or may not contain the actual type of our parameter’s type variable that we added to the environment before the call. So now we have the type of the body. So the type of the function must be</p><ul><li>&lt;type_of_param&gt; -&gt; &lt;type_of_body&gt;</li></ul><p>We need to “apply” the returned substitution to the type variable we generated. Applying a substitution to a type means replacing all (unbound, more on that in later chapters) instances of the variables present in the substitution with their values from the substitution. So, after applying the substitution to the type variable (in this case, simply replacing it with the value type from the substitution if present), we can simply return the function type from param type to body type along with the substitution we generated. Note that we should ideally remove the type variable we generated for the parameter from the substitution that we return because the scope of that type variable is limited to the function’s body. We’re not doing it here because the type variables we generate are guaranteed to be unique so there’s no chance of collisions.</p><p>That was a lot of talk so let’s look at the code.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2406462bbe0ad3586001e58ba8228ee1/href">https://medium.com/media/2406462bbe0ad3586001e58ba8228ee1/href</a></iframe><p>Notice that we replaced the env parameter with a context parameter. The context contains the environment along with some other information we might need. We need to keep a count of type variables we’ve generated till now so that we can generate the next one.</p><p>We added a new function applySubstToType which recursively traverses a type node and for type variables, it looks them up in the given substitution and returns it. If not, it simply returns the type variable itself. For other types, it recursively applies the substitution to the child nodes.</p><p>Function addToContext takes a context, a variable name and a type, and adds the mapping of name and type to the context’s environment. Notice that it doesn’t mutate the original context or it’s environment. It makes a copy and returns a new context. This is because when we bind a new variable, it should only be visible in the scope it was declared in. We don’t want to add it to the global scope.</p><p>The function newTVar takes a context, increments it’s next property and returns a new type variable with name T&lt;context.next&gt; (T1, T2, …). Each call will generate a new type variable. This does mutate the given context because the generated names should be unique across scopes. Though, this isn’t strictly required, this makes the implementation slightly easier.</p><p>Finally, we change the signature of the infer function to take a context instead of environment and it now returns a type and a substitution. The case for functions is added which does exactly what I explained earlier.</p><ol><li>Generate a new type variable for parameter.</li><li>Add the generated type to a copy of the context.</li><li>Call infer with the function’s body and the new context.</li><li>Apply the returned substitution to the type variable we generated in step 1.</li><li>Create a new function type with the parameter’s type and body type.</li><li>Return the function’s type and substitution.</li></ol><p>Note that the cases for variables and Ints just return an empty substitution.</p><p>Now, to the final part of the puzzle.</p><h4>Function calls</h4><p>As you see in the type of the “Call” nodes, it has two expressions, the function to be called, and the argument.</p><p>First, we need to call infer with the function node. The we check if the returned type is a function. If not, we throw a type error saying a function was expected.</p><p>Now we need to apply the resulting substitution to the environment’s context so that the type of any type variables inferred by the last call is available to the call to infer the argument’s type. Then infer is called with this new context and the argument node.</p><p>Now, we need to match the type of the argument with the type expected by the function. This is not as simple as simply comparing the types. The types may contain type variables which may stand for other types. This is where unification comes in.</p><p>Basically, unification is a way to check if 2 types “fit” and if they do, return a substitution that makes them equal. For example, if we try to unify (Int -&gt; A) and (Int -&gt; Bool), we’ll get a substitution {“A”: Bool}, because “A” is a type variable, which can stand in for any type and the second type requires it to be Bool. That’s the intuitive idea behind it.</p><p>Here’s the code</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b7fb0433c075975bd27230addbb73765/href">https://medium.com/media/b7fb0433c075975bd27230addbb73765/href</a></iframe><p>First, let’s look at the unify function, that takes 2 types and returns a substitution that makes them match. There are a few cases in this function</p><ul><li>When both the types are named types, and they’re the same, we return an empty substitution because they already match.</li><li>If one of them is a type variable, and they’re the same, we return a null substitution.</li><li>If one of them is a type variable, and the other type contains the same type variable, we throw an error. This is because unifying them would lead to an infinitely recursive type. For example, if A and A -&gt; B unify, this would mean that A is A -&gt; B, which would mean A -&gt; B is (A -&gt; B) -&gt; B. You can see that this will go on forever.</li><li>If one of them is a type variable and the other type doesn’t contain it, we can “bind” the type variable to the other type. Because a type variable can stand in for any type, and a call to unify means both types must be same, the type variable must stand for the other type.</li><li>When both types are functions, we recursively unify their param types and return types and compose the resulting substitutions (using composeSubst).</li><li>Any other case is a type error.</li></ul><p>Also notice that here too, at each step, when we get a new substitution, we apply it to the older types as a way to update them with the new constraints generated by calling unify.</p><p>Now, back to the infer function for call expressions. As you see here, we generate a new type variable for the return type of the function, then infer the types for the function arguments, then we unify the inferred type of the function with the type &lt;argType&gt; -&gt; &lt;newVar&gt;. Finally, we unify the function’s param type with the actual argument’s type because you shouldn’t be able to pass, say for example an Int to a function that takes a Bool argument right? At each step, we have to apply newly generated substitutions to the earlier types. Also, we use composeSubst (* This is a correction. Earlier, I was using simple Object.assign. See EDIT note at the end) to “compose” multiple substitutions. composeSubst function applies the first substitution to the types of the second one and then combines the result with the first substitution. At the end, we just apply the combined substitutions to the function type’s return type and return it, along with the combined substitution. You should be able to see intuitively a function (A -&gt; B), applied to an argument of type A should have the type B.</p><p>That’s pretty much all you need to know for now. Just for completeness, here’s the case for If expressions.</p><h4>If expressions</h4><p>It should be straightforward. We just check the condition expression’s type should unify with Bool, and the types of both branches should unify. Then we simply return the type of the first branch (could have been the second branch as well because both unify). Before looking at the following snippet, I suggest you try writing it yourself. You don’t need any more functions than those we have already defined. Just make sure you don’t throw away any substitutions.</p><p>Here’s the code.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8bb05c486c34e4dd8d04fb4285ebf560/href">https://medium.com/media/8bb05c486c34e4dd8d04fb4285ebf560/href</a></iframe><h4>Testing out our typechecker</h4><p>You can call the infer function on expression trees to see if they match the types. Writing out bigger expressions may become slightly tedious, I wrote a few helper functions to create expression trees.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4560539c47ca3bc08089b76295e87670/href">https://medium.com/media/4560539c47ca3bc08089b76295e87670/href</a></iframe><p>Now, we can test some stuff by calling infer by passing in an initial context. You can add some builtins like “true”, “false”, “==”, “+”, etc.</p><p>Here are some very simple tests</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/26da853ac4f71b3f32e3fd3740277102/href">https://medium.com/media/26da853ac4f71b3f32e3fd3740277102/href</a></iframe><p>You can test it out with more complicated expressions to see if everything works fine.</p><h3>Conclusion</h3><p>I hope this gave you some idea about how type inference works. This might have been a lot to take in all at once but if you actually write the code out, you’ll start understanding it better. Play around it a bit. Maybe add a few things. Start with showing the actual expression where the type error occurred.</p><p>In the <a href="https://medium.com/@dhruvrajvanshi/type-inference-for-beginners-part-2-f39c33ca9513">next part</a>, we’ll add polymorphism/generic types to our system. That would allow us to express functions that work on any type.</p><p>In the mean time, I would appreciate some corrections and suggestions. I’m sure there are plenty of subtle bugs in the code ;)</p><p>EDIT: There was a bug in this part’s code. Instead of merging substitutions using Object.assign, the first one has to be applied to the types of the second one and then take the union with the first. Thanks to <a href="http://twitter.com/mbulfone">@mbulfone</a> for pointing this out.</p><p>EDIT2: There was another bug in infer for the case of “Call” expression. I had forgotten to apply the substitution after unifying with the expected function type to the funcType variable. I’ve fixed the snippet.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3e0a5be98a4b" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>