From 32e0e105f663ace08896f22ab4079521070b0cac Mon Sep 17 00:00:00 2001 From: Amir Saeid Date: Wed, 18 Feb 2026 21:25:00 +0000 Subject: Change the theme and add a new post --- public/post/2017-08-16-tapl/index.html | 288 +++++++++++------ .../index.html | 226 +++++++++++++ public/post/2017-08-22-thinkpad-e470/index.html | 300 +++++++++++------- .../2017-08-24-untyped-lambda-calculus/index.html | 233 ++++++++++++++ public/post/2018-09-11-shapeless/index.html | 229 ++++++++++++++ public/post/fairstream/index.html | 263 +++++++++++++++ public/post/index.html | 351 ++++++++++++++------- public/post/index.xml | 9 +- .../index.html | 258 +++++++++++++++ 9 files changed, 1822 insertions(+), 335 deletions(-) create mode 100644 public/post/2017-08-17-untyped-arithmetic-expressions/index.html create mode 100644 public/post/2017-08-24-untyped-lambda-calculus/index.html create mode 100644 public/post/2018-09-11-shapeless/index.html create mode 100644 public/post/fairstream/index.html create mode 100644 public/post/simple-fair-and-terminating-backtracking-monad-transformer/index.html (limited to 'public/post') diff --git a/public/post/2017-08-16-tapl/index.html b/public/post/2017-08-16-tapl/index.html index d0ce0d0..bf71d20 100644 --- a/public/post/2017-08-16-tapl/index.html +++ b/public/post/2017-08-16-tapl/index.html @@ -1,146 +1,224 @@ - - - - - Types and Programming Languages | - - - - - - - - - + + + Types and Programming Languages :: + + + + + - - + + - - - + + - + + - + + - - - + + - - - - - - - - - - - - - - - - - - - - - - + + - - - - - - - + -

- +

+ + + + + +

+ +

+ Types and Programming Languages +

2017-08-16

- - -

- -

Types and Programming Languages

+ + #tapl + #rust - August 16, 2017 - + + + - - -

February 2016, as a birthday present to myself I bought a copy of Types and Programming Languages. At the time the only thing I did with it was to take a photo of it, sharing it on Twitter and congratulating myself. To be fair, I did try reading it, but it was so intimidating that I gave up very early in the book. One and a half years later I’m going to give it another go because a few things have changed.

+ + + +

First of all, I should say that I’ve no academic background in computer science—I’ve studied Zoology. I easily get frightened by any text with more than a few lines of maths in it especially when it’s heavy on symbols which I don’t know, and Google doesn’t help. I’ve had many attempts at learning maths—watching YouTube videos, reading books—but I always gave up mostly due to lack of discipline in doing the exercises. A year ago I decided to do something about it and enrolled into DIT’s B.Sc. in Information Systems and Information Technology. I thought if I’m paying a substantial amount of money for a class in a relatively well-established institute it might help. To my unwelcome surprise, the course isn’t heavy on maths, but it was an immense help, discipline-wise, nonetheless.

The second thing was that due to some unforeseen circumstances, all of a sudden I found myself with plenty of free time and I didn’t want to waste this once in a lifetime opportunity.

After deciding that I want to read the book and be rigorous in doing the exercises, I had to choose a programming language to do the exercises in, and I found it a good excuse to give Rust a try.

I also decided to publish my progress both as in code as well as in a series of blog posts, as suggested by a wise man, Iain. Hence this blog.

+ +

+ + + +

+ +

+ + + < [ThinkPad E470] + + + + +

+ + -

- Tapl -

+ -

- Rust -

+ + - +

- -

- - -

+ + + - + + + + + + + + + + + + + + + diff --git a/public/post/2017-08-17-untyped-arithmetic-expressions/index.html b/public/post/2017-08-17-untyped-arithmetic-expressions/index.html new file mode 100644 index 0000000..5997c93 --- /dev/null +++ b/public/post/2017-08-17-untyped-arithmetic-expressions/index.html @@ -0,0 +1,226 @@ + + + + + Untyped Arithmetic Expressions :: + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

+ + + + +

+ +

+ Untyped Arithmetic Expressions +

2017-08-17

+ + + + + #tapl + + #rust + + + + + + + + +

Chapters 3 and 4 of the book develop the required tools for a small and trivial language of numbers and booleans. You can find the OCaml implementation of this language on book’s website. And you can find my Rust implementation at arith.rs.

+ +

+ + + +

+ +

+ + + < [ThinkPad E470] + + + + :: + + + + [Types and Programming Languages] > + + +

+ + + + + + + + +

+ +

+ + + + + + + + + + + + + + + + +

+ + + diff --git a/public/post/2017-08-22-thinkpad-e470/index.html b/public/post/2017-08-22-thinkpad-e470/index.html index 3f0cc7d..666c98f 100644 --- a/public/post/2017-08-22-thinkpad-e470/index.html +++ b/public/post/2017-08-22-thinkpad-e470/index.html @@ -1,121 +1,165 @@ - - - - - ThinkPad E470 | - - - - - - - - - + + + ThinkPad E470 :: + + + + + - - + + - - - + + - + + - + + - - - + + - - - - - - - - - - - - - - - - - - - - - - + + - - - - - - - + -

- +

+ + + + + +

+ +

+ ThinkPad E470 +

2017-08-22

- - -

- -

ThinkPad E470

+ + #thinkpad + #e470 - August 22, 2017 - + + + - - -

Recently I’ve been looking for a Linux-friendly, budget laptop. I like ThinkPads, and all of my laptops have been either T-series or X-series but this time I didn’t want to spend that amount of money and was looking for cheaper alternatives.

+ + + +

Browsing Lenovo website, I realised that a reasonably configured E470 would cost about €1000 which was about how much I was willing to pay. I configured it, so it has:

Intel® Core™ i7-7500U

It’s weighty, ugly, bulky, and the design is unimaginative.

+ +

+ -

- Thinkpad -

+ +

+ + + < [Fairstream] + + + + :: + + + + [Types and Programming Languages] > + + +

+ + -

- E470 -

+ - + + + +

- -

- - -

+ + + - + + + + + + + + + + + + + + + diff --git a/public/post/2017-08-24-untyped-lambda-calculus/index.html b/public/post/2017-08-24-untyped-lambda-calculus/index.html new file mode 100644 index 0000000..b3556e7 --- /dev/null +++ b/public/post/2017-08-24-untyped-lambda-calculus/index.html @@ -0,0 +1,233 @@ + + + + + Untyped Lambda Calculus :: + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

+ + + + +

+ +

+ Untyped Lambda Calculus +

2017-08-24

+ + + + + #tapl + + #rust + + + + + + + + +

As I mentioned in an [earlier post]({% post_url 2017-08-16-tapl %}), I’ve been working through Types and Programming Languages in Rust. Chapters 5 to 7 of TAPL discuss untyped lambda calculus through an implementation of a simple expression-based language. Chapter 5 lays the foundations; chapter 6 focuses more on one of the concepts introduced in chapter 5; de Bruijn index and chapter 7 explores an ML implementation of the said language, but only how to evaluate the terms, and not how to parse them. The accompanying OCaml implementation’s parser is generated automatically from a Yacc grammar.

I’ve had good experiences writting parsers in Haskell using parsec and attoparsec before, so I started looking for parser-combinators in Rust. There seem to be three capable options:

combine
chomp
nom

Combine even has the combine-language extension which is very similar to Parsec’s Text.Parsec.Token which would’ve simplified the task of parsing lexical elements but I couldn’t add it as a dependency to my project—due to compile errors which I’m sure has been because of my ignorance and lack of familiarity with Rust and Cargo. At the end I ended up choosing using layman’s metrics, number of GitHub stars and nom won by a huge margin.

+ +

+ + + +

+ +

+ + + < [Shapeless] + + + + :: + + + + [ThinkPad E470] > + + +

+ + + + + + + + +

+ +

+ + + + + + + + + + + + + + + + +

+ + + diff --git a/public/post/2018-09-11-shapeless/index.html b/public/post/2018-09-11-shapeless/index.html new file mode 100644 index 0000000..e54c9a9 --- /dev/null +++ b/public/post/2018-09-11-shapeless/index.html @@ -0,0 +1,229 @@ + + + + + Shapeless :: + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

+ + + + +

+ +

+ Shapeless +

2018-09-11

+ + + + + #shapeless + + #scala + + + + + + + + +

Shapeless

import shapeless._
+import shapeless.ops.hlist.{LiftAll, Mapper, Mapped}
+import shapeless.UnaryTCConstraint._
+

+ + + +

+ +

+ + + < [Fairstream] + + + + :: + + + + [Untyped Lambda Calculus] > + + +

+ + + + + + + + +

+ +

+ + + + + + + + + + + + + + + + +

+ + + diff --git a/public/post/fairstream/index.html b/public/post/fairstream/index.html new file mode 100644 index 0000000..26887df --- /dev/null +++ b/public/post/fairstream/index.html @@ -0,0 +1,263 @@ + + + + + Fairstream :: + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

+ + + + +

+ +

+ Fairstream +

2026-02-17

+ + + + + + + +

Backtracking is a versatile approach for solving search problems by building solutions incrementally. If a partial solution cannot be extended, it is discarded and the process returns to a previous step to explore an alternative path. This method is generally more efficient than brute-force searching due to pruning: stopping exploration of a branch as soon as it violates a constraint, which eliminates entire sections of the search space.

Strictly speaking, fair backtracking is not required for all search problems. A fair strategy guarantees all branches make progress, preventing any single branch from starving the others. The List monad handles non-deterministic computation well, and within a finite search space it produces the same results as a fair stream. When the search space is infinite, or when one branch may produce unbounded results, fairness becomes essential to ensure completeness.

fairstream is a Scala implementation of fair backtracking based on the work of Oleg Kiselyov.

The problem with depth-first search#

Consider Pythagorean triples: tuples $(i, j, k)$ such that $i^2+j^2=k^2$, with $(3, 4, 5)$ as the canonical first example. If we try to generate all such triples using nested infinite generators, a conventional stream composition based on sequential flatMap gets stuck exploring an infinite branch that contains no solution and never comes back up to try a larger value, so it may fail to produce any triples at all despite solutions existing.

The following example demonstrates how fs2.Stream’s depth-first approach can fail to find Pythagorean triples, even though the result set is non-empty:

val number: fs2.Stream[IO, Int] = fs2.Stream.iterate(1)(_ + 1)
+
+val triples = for {
+  i <- number
+  j <- number
+  k <- number
+  if i * i + j * j == k * k
+} yield (i, j, k)
+
+triples.take(7).compile.toList
+

The for comprehension desugars into nested flatMap calls. Since number is infinite, the innermost generator tries $k = 1, 2, 3, \ldots$ forever for $i = 1, j = 1$ before it ever consider $j = 2$. No Pythagorean triple exists for $i = 1, j = 1$, so the stream never produces a result.

This is not a quirk of ofs2. Any depth-first flatMap over infinite collections has this problem, including Scala’s standard library LazyList.

Fair interleaving with `fairstream`#

fairstream solves this by replacing sequential concatenation with fair disjuction (mplus), which interleaves branches so that every candidate is eventually reached.

At the time of writing, the library is published as snapshots:

resolvers += Resolver.sonatypeCentralSnapshots
+
+libraryDependencies += "com.codiff" %% "fairstream" % "0.0-9f9db42-SNAPSHOT"
+

import com.codiff.fairstream.Fair
+import com.codiff.fairstream.Fair._
+
+lazy val number: Fair[Int] = mplus(unit(0), number.map(_ + 1))
+
+val triples = for {
+  i <- number
+  _ <- guard(i > 0)
+  j <- number
+  _ <- guard(j > 0)
+  k <- number
+  _ <- guard(k > 0)
+  _ <- guard(i * i + j * j == k * k)
+} yield (i, j, k)
+
+Fair.runM(None, Some(7), triples)
+

`FairT`: effectful fair backtracking#

Fair[A] is a pure computation. But what if your search branches need to perform effects, like reading from a database, calling an API, or logging? That’s where FairT[F[_], A] comes in.

FairT is a monad transformer that layers fair backtracking on top of any effect F. This means you can interleave non-deterministic search with IO, Task, or any other cats-effect compatible monad.

fs2 integration#

If you want to stay in the fs2 ecosystem, fairstream-fs2 provides a conversion from Fair and FairT to fs2.Stream:

libraryDependencies += "com.codiff" %% "fairstream-fs2" % "0.0-9f9db42-SNAPSHOT"
+

import com.codiff.fairstream.fs2.syntax._
+
+triples.toFs2.take(7).compile.toList
+

This should let you compose fair backtracking with all the stream processing, concurrency, and resource management that fs2 provides. You define your search logic using Fair or FairT, then convert to fs2.Stream at the boundary where you need to integrate with the rest of your application.

+ +

+ + + +

+ +

+ + + + + [ThinkPad E470] > + + +

+ + + + + + + + +

+ +

+ + + + + + + + + + + + + + + + +

+ + + diff --git a/public/post/index.html b/public/post/index.html index 54bac6a..0377429 100644 --- a/public/post/index.html +++ b/public/post/index.html @@ -1,159 +1,270 @@ - - - - - - - - - - - - - - + + + Posts :: + + + + + - - + + - - - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + - - - - - - - - - - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

+ + + + +

- - + +

+ Fairstream +

2026-02-17

- -

- Posts -

+ +

+ -

+ [] +

+ +

+ ThinkPad E470 +

2017-08-22

+ + + + #thinkpad + + #e470 + + + -

- + -

- -

- August 22, 2017 -

- -

- - ThinkPad E470 - -

+ +

Browsing Lenovo website, I realised that a reasonably configured E470 would cost about €1000 which was about how much I was willing to pay. I configured it, so it has:

- read more -

+ +

+ + +

+ [] +

+ +

+ Types and Programming Languages +

2017-08-16

+ + + + + #tapl + + #rust + + + + + + +

+ +

- -

+ + +

+ [] +

+ +

+ + +

+ -

- August 16, 2017 -

- - Types and Programming Languages - -

- read more

- - +

+ +

+ + + - + + + + + + + + + + + + + + + diff --git a/public/post/index.xml b/public/post/index.xml index bd08f3a..85cb7be 100644 --- a/public/post/index.xml +++ b/public/post/index.xml @@ -6,8 +6,15 @@ Recent content in Posts on Hugo en - Tue, 22 Aug 2017 00:00:00 +0000 + Tue, 17 Feb 2026 20:59:41 +0000 + + Fairstream + https://blog.gluegadget.com/post/fairstream/ + Tue, 17 Feb 2026 20:59:41 +0000 + https://blog.gluegadget.com/post/fairstream/ + <p><a href="https://en.wikipedia.org/wiki/Backtracking">Backtracking</a> is a versatile approach for solving search problems by building solutions incrementally. If a partial solution cannot be extended, it is discarded and the process returns to a previous step to explore an alternative path. This method is generally more efficient than brute-force searching due to pruning: stopping exploration of a branch as soon as it violates a constraint, which eliminates entire sections of the search space.</p> <p>Strictly speaking, fair backtracking is not required for all search problems. A fair strategy guarantees all branches make progress, preventing any single branch from starving the others. The List monad handles non-deterministic computation well, and within a finite search space it produces the same results as a fair stream. When the search space is infinite, or when one branch may produce unbounded results, fairness becomes essential to ensure completeness.</p> + ThinkPad E470 https://blog.gluegadget.com/post/2017-08-22-thinkpad-e470/ diff --git a/public/post/simple-fair-and-terminating-backtracking-monad-transformer/index.html b/public/post/simple-fair-and-terminating-backtracking-monad-transformer/index.html new file mode 100644 index 0000000..40a74a1 --- /dev/null +++ b/public/post/simple-fair-and-terminating-backtracking-monad-transformer/index.html @@ -0,0 +1,258 @@ + + + + + Simple Fair and Terminating Backtracking Monad Transformer :: + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

+ + + + +

+ +

+ Simple Fair and Terminating Backtracking Monad Transformer +

2026-02-16

+ + + + + + + +

About eight years ago as part of an interview process I was given a take home code challenge. Considering how much it’s changed in the tech world and the fact that company is no longer hirigin I feel comfortable sharing the details of the challenge.

+
You run a paint shop, and there are a few different colors of paint you can prepare. Each color can be either “gloss” or “matte”. +You have a number of customers, and each have some colors they like, either gloss or matte. No customer will like more than one color in matte +You want to mix the colors, so that:
+
+
There is just one batch for each color, and it’s either gloss or matte.
+
For each customer, there is at least one color they like.
+
You make as few mattes as possible (because they are more expensive). +Your program should accept an input file as a command line argument, and print a result to standard out. An example input file is:
+
+
5
+1 M 3 G 5 G
+2 G 3 M 4 G
+5 M
+
The first line specifies how many colors there are.
+
Each subsequent line describes a customer. For example, the first customer likes color 1 in matte, color 3 in gloss and color 5 in gloss.
+
Your program should read an input file like this, and print out either that it is impossible to satisfy all the customer, or describe, for each of the colors, whether it should be made gloss or matte.
+
The output for the above file should be:
+
G G G G M
+

resolvers += Resolver.sonatypeCentralSnapshots
+libraryDependencies += "com.codiff" %% "fairstream" % "0.0-9f9db42-SNAPSHOT"
+

import com.codiff.fairstream.Fair._
+
+sealed trait Finish
+final case object Gloss extends Finish
+final case object Matte extends Finish
+
+final case class Color(id: Int)
+
+final case class Paint(color: Color, finish: Finish)
+
+def solve(
+    numColors: Int,
+    customers: List[List[Paint]]
+): Option[Vector[Finish]] = {
+
+  def go(color: Int, assignment: Vector[Finish]): Fair[Vector[Finish]] = {
+    // Prune early: if any customer's preferences are all decided and none match
+    val dominated = customers.exists { prefs =>
+      prefs.nonEmpty && prefs.forall { p =>
+        p.color <= assignment.length && assignment(p.color - 1) != p.finish
+      }
+    }
+    if (dominated) empty
+    else if (color > numColors) unit(assignment)
+    else
+      mplus(
+        go(color + 1, assignment :+ Gloss),
+        go(color + 1, assignment :+ Matte)
+      )
+  }
+
+  // Enumerate all valid assignments, pick the one with fewest mattes
+  val solutions = Fair.runM(None, None, go(1, Vector.empty))
+  solutions.minByOption(_.count(_ == Matte))
+}
+

+ + + +

+ +

+ + + + + [Shapeless] > + + +

+ + + + + + + + +

+ +

+ + + + + + + + + + + + + + + + +

+ + + -- cgit v1.2.3