Let’s have fun with some of C#’s recent features. Imagine you’re working on a recipe app. Users can type in what ingredients they have to hand and the app will suggest some recipe ideas from its library. As usual, each service in the app gets an interface : interface ILogger { void Log ( string message ); } interface IRecipeRepository { IEnumerable < Recipe > FindRecipesWithIngredient ( string…
Phil Wadler’s pearl A Prettier Printer is a classic example of functional design. Starting with a simple model and some algebraic laws, Wadler derives an implementation of a well behaved layout algorithm. It’s a great read — go and read it if you haven’t! (I’m going to assume you have read it and try not to recapitulate too much below.) I learned a lot about Wadler’s algorithm by translating it to…
Since starting at Microsoft earlier this year I’ve done a lot of maintenance work on my team’s build system. One of the things I’ve been working on has been incremental building : if you run a build in Visual Studio, and then run another build straight away, it should detect that nothing has changed and skip rebuilding. Incremental building is very important for day-to-day productivity, especially…
My parsing library Pidgin has some infrastructure to track positions in a textual input file, for the purposes of error reporting. The library’s written in C#, but for today let’s work in Haskell. data SourcePos = SourcePos { line :: Natural , col :: Natural } deriving ( Eq , Ord ) startOfFile :: SourcePos startOfFile = SourcePos 1 1 The parser keeps track of the current SourcePos by looping over…
I’ve been thinking a bit about how to build a library of tools to handle variables, capture-avoiding substitution, etc, on top of Sawmill . Pretty much every compiler needs to deal with variables, and they’re notoriously tricky to handle correctly. I’m a way off having a final design, but I thought I’d publish my unfinished notes, hastily written in an afternoon. You’ll see a few Thinking Emojis…
This is part of a series of posts about implementing a miniature Prolog interpreter in C#. Introduction & Syntax Parsing Unification The rules engine Today’s the day! We’re going to turn last week’s unification algorithm into an actual programming language by filling in the bottom-right part of the above diagram. Prolog’s rules engine is the system which processes the predicates and facts in your…
This is part of a series of posts about implementing a miniature Prolog interpreter in C#. Introduction & Syntax Parsing Unification The rules engine We’re getting on to the fun part of writing an interpreter: actually interpreting the input code. In this post we’re going to implement a unification algorithm using my generic programming library Sawmill . Unification slots somewhere in the middle…
Happy birthday to my sister! This is part of a series of posts about implementing a miniature Prolog interpreter in C#. Introduction & Syntax Parsing Unification The rules engine In this post I’m going to focus on the left-hand part of that diagram. We’ll use my parsing library Pidgin to convert Prolog source code into the abstract syntax classes I outlined in the previous post. About Pidgin…
I figured it’d be useful to have some examples of my language tooling libraries Sawmill and Pidgin in action. I thought it could be fun to use them to write a miniature Prolog interpreter! Introduction & Syntax Parsing Unification The rules engine You’ll find all the code for this series on GitHub . Whistle-Stop Introduction to Prolog Prolog is a logic programming language. Prolog code consists of…
I got married yesterday! This post is about my C# generic programming library Sawmill . Have a read of my earlier post for an introduction. How things were I recently made a substantial change to Sawmill’s core IRewritable interface. Here’s what it used to look like: interface IRewritable < T > where T : IRewritable < T > { Children < T > GetChildren (); T SetChildren ( Children < T > newChildren…
Happy birthday to me! I’m pleased to announce that version 2.0 of my functional parsing library, Pidgin , is now available on Nuget . In this release I’ve focused on error messages, performance, and Span support. Parser Combinators I haven’t written about Pidgin before, so allow me to briefly introduce it. Pidgin is a parser combinator library, meaning that it consists of three main concepts: A…
Given a polymorphic type, like List , what can we say about the relationship between different usages of that type? If A and B are related, is List[A] related to List[B] ? Variance is the word for this type of relationship, and it turns out there are a few different answers to that question, depending on the type you’re asking about. Covariance Probably the most familiar situation is when the…
It’s common in functional languages — and increasingly in hybrid languages like C# — to work with complex systems of immutable datatypes. For a contrived example, suppose you’re working on a billing application: class Order { public Customer Customer { get ; } public ImmutableList < Product > Products { get ; } } class Customer { public string Name { get ; } public Address Address { get ; } }…
My esteemed colleague Gervasio and I have arranged to live-stream some programming this Friday, the 20th of July Update : we’ve decided to move it to next Tuesday, the 24th , at 2PM BST. We’re going to be working on adding some basic Span support to my parsing library , and it’s going to involve unsafe and custom IL, which should be a bit of fun. The stream will be on YouTube and we’re planning to…
HTML templating systems are great but they sure are complex. ASP.NET’s Razor, for example, is a whole new programming language! While Razor does happen to have a large chunk of C# embedded within it, and it works by generating and then compiling C# code, it’s still a separate language with a separate syntax, separate abstraction techniques, separate compiler tooling, a separate file type, and…
One of my favourite little gems of functional programming is the following implementation of the dot product: dot :: [ Double ] -> [ Double ] -> Double xs `dot` ys = sum ( zipWith ( * ) xs ys) dot zips two lists of numbers, multiplying each pair of elements using (*) , and then aggregates the results with sum . It’s like a map-reduce program, but it processes two collections, not one. It…
You can teach a new dog old tricks. One of the fun things about category theory is that once you’ve learned an idea in one context it’s easy to apply it to another one. Of the numerous categories available to Haskell programmers, Hask , the category of Haskell types and functions, gets the lion’s share of the attention. Working with standard abstractions in more overlooked categories is a great…
If you visit Stack Overflow Jobs you’ll see that our job search form supports a simple advanced search syntax, including Boolean operators and a number of custom filters such as technology tags and minimum salary. For example, I hate writing JavaScript, but my loyalties can be bought, so I might type [c#] and (not [javascript] or salary:50000gbp) into the search box. This advanced search syntax is…