RC W4D5 - Types: tests that you get for free?

If you search for “there is more than one way to do it”, the link that comes up top on Google is this one from WikiWikiWeb (which I learned is different from Wikipedia). It’s an expansive take on the expressiveness vs interpretability discussion. In English you could write ‘fast’ vs ‘quick’ vs ’swift’ and the meaning would be more apt in different contexts, which was my take away from this excerpt on Perl.

Its inventor, LarryWall, is trained as a linguist. He has this crazy notion that sometimes phrasing a sentence differently might make its meaning clearer…

Next I learned from the Python vs Ruby page that Ruby inherits from Smalltalk and Perl, believing that 'everything is an object' and ’there is more than one way to do it’, whereas Python inherits from the Algol family. I didn’t have Smalltalk and Algol in my categorization, and ChatGPT added them to the respective groups as expected.

Re: experimenting with Idris, it was not easy. I signed up to present as a way to force myself to talk about a distinctive facet of the language. I managed to weave a thread around types as 'tests that you get for free' (detailed below), but I'll need a proper project or use case as motivation to overcome the pain points and get deeper into the (experimental) language. Naturally it doesn't help it's not the easiest language to look up on Google (try it!).

For the functional programming study group, I read up (and later wrote on) effect systems. In the remaining pockets of time, I watched more Graham Hutton on Haskell, Bartosz Milewski on category theory, and Andrej Karpathy on generative models. 

The Friday presentation was titled 'Types: tests that you get for free?’. I started by talking about my last role where the main codebase was in TypeScript, the data stack that I mainly worked on was in Python, and initially my changes to the main codebase was one-off or piecemeal. I learned a lot about TypeScript when I later ported a section of the codebase into Python, and picked up a number of things on Python types too!

Python is dynamically-typed, but you can optionally type-annotate your code. For example, you can represent a list of ints as `List[int]`, and running mypy tells you if the code type-checks OK. If you represent your list as a `Sequence[int]`, however, mypy will complain when you try to make changes to the list (say by mutating an existing value or appending to the list) since `Sequence` is read-only.

At RC I’ve had the chance to go from Python to Haskell to (a little bit of) Idris. Suppose you’re trying to append an int to a list of strings. While mypy will complain when you run the type-check, the code will run successfully as Python is weakly typed. In strongly-typed Haskell, compilation will fail when you try to do the same thing.

With Idris you can go even further. The canonical example introduces a `Vect` type, which is like a list but has the length of the list in its definition. This means you can create a function that concatenates two `Vect`, the first on length n and the second m, and returns a `Vect` of length n + m. Suppose there was a typo and the first `Vect` is concatenated to itself, the compilation will fail since the lengths don’t add up.

In fact you can go even further with Idris to write proofs. The powerful type checker is able to run proofs by induction say. I briefly mentioned proofs but didn't follow up to talk about type-driven development. It's like test-driven development but with types. In Idris you get to go further in exploring the shape of the program (analogous to denotation design) and have the type checker to 'write the code for you'.

What’s also interesting is instead of types describing values, types in Idris are first class and exist in the same namespace as values. In Idris `if True then Int else String` run successfully but fails in Haskell.

To circle back to the title, I quoted Edwin Brady (the creator of Idris) from the book Type-Driven Development.

The difference is that, unlike tests, which can usually only be used to show the presence of errors, types (used appropriately) can show the absence of errors. But although types reduce the need for tests, they rarely eliminate it entirely.

The idea here is that when you write tests, you need to have a sense what errors you’re trying to guard against. With types, you’re ‘constraining’ the space of what’s possible. In the example of List vs Sequence in Python, these guardrails can even be more ergonomic (hence more likely to be added). That being said, neither tests or types provide fail-safe guardrails in all cases.

RC W4D4 - Exploring effect systems

The topic that got most votes at functional programming study group was effect systems. I was a little unsure if a seemingly-advanced topic would get people talking. In the true spirit of RC, what ensued was a group exploration.

Prior to SICP, I thought about programming languages as being static vs dynamic, compiled vs interpreted, with vs without garbage collection. Reading SICP I was (more formally) introduced to functional vs imperative, eager vs lazy evaluation.

With functional vs imperative, I thought about the latter as allowing functions to have side effects. Since pure functions in the former don’t allow for side effects, enabling side effects (like reading a file or printing to the screen) in a language like Haskell requires a little bit of ‘ceremony’ through monads.

I’m still wrapping my head around monads. My understanding is monads allows side effects in a controlled way, performed when explicitly triggered rather than being triggered automatically by the evaluation of a function.

The problem with monads is composability, as the composition of two monads may not be a monad. In other words, care is needed when monads are composed together as the desired effect may be different vs what was intended when considering each monad individually.

Having an effect system offers an alternative to using monads. Koka is an experimental language that introduces effect types and handlers. Reading about the different effect types, there’s a ‘continuum’ and thus not simply a pure vs effectful function distinction.

Why bother? This beginner-friendly post has examples of algebraic effects allowing a more flexible or generalized form of try-except. Instead of simply catching the error, we could perform arbitrary operations and then ‘go back’ to the function that raised the error. It’s also worth nothing that having handlers allows for this in an ergonomic way, which also avoids having to ‘color’ functions.

Haskell has the `freer-simple` library that enables an extensible effect system. Where effects can have a major impact is enabling ergonomic concurrency in OCaml (c.f. Haskell which has better multicore primitives). This has been in the works for close to a decade and is currently an experimental feature in OCaml 5.

The discussion is timely. Earlier in the week we watched Simon Peyton-Jones present on the Verse language. Verse has an effect system instead of using monads, slide 6 here. The study group got curious about logic programming (Verse is a functional logic language) so we’ll be discussing this next week!

Special thanks to Sam Eisenhandler for seeding the discussion on effect systems.

RC W4D3 - Categorizing programming languages with ChatGPT

In a prior post, I shared a quote from Chelsea Troy comparing expressiveness vs interpretability in programming languages. I thought it would be interesting to get ChatGPT to categorize other languages based on this measure.

We start with Ruby being expressive (there's more than one way to do it) vs Python being interpretable (there should be one obvious way to do it). We continue on this rather simplistic thread. We get PHP and Perl in the expressive camp, Go in the interpretable camp.

Now ChatGPT seems to cop out with Rust, saying it’s emphasizes both expressiveness and interpretability. Functional languages like Haskell, Scala and Elixir are in this camp too. Then we have another camp of system languages that emphasize performance like C and Zig.

What’s also interesting is having this categorization in order of release date, here adding more languages. 
  1. Emphasis on expressiveness: Prolog (1972), Perl (1987), Lua (1993), JavaScript (1995), PHP (1995), Ruby (1995)
  2. Emphasis on interpretability: COBOL (1959), Python (1991), Go (2009)
  3. Both expressiveness and interpretability: Haskell (1990), OCaml (1996), Erlang (1998), Scala (2004), F# (2005), Elixir (2011), Rust (2010), Swift (2014)
  4. Less expressive and less interpretable: Fortran(1957), C (1972), C++ (1985), Java (1995), Kotlin (2011), Zig (2015)
For funsies I got ChatGPT to divvy up languages into more groups here. Note that 'interpretability' changes meaning from 'easy for humans to parse' with 4 camps to 'easy for machines to parse' with 8 camps, more context here.

In yesterday’s post I shared David Beazley's advice on improving Python skills. Today I’m reminded of Peter Norvig’s advice along the same thread.

Learn at least a half dozen programming languages. Include one language that emphasizes class abstractions (like Java or C++), one that emphasizes functional abstraction (like Lisp or ML or Haskell), one that supports syntactic abstraction (like Lisp), one that supports declarative specifications (like Prolog or C++ templates), and one that emphasizes parallelism (like Clojure or Go).

In the post prior to yesterday, I wrote about wanting to learn how generative models work under the hood alongside functional languages. This feels more fun. This caption by Bret Victor encapsulates this desire to explore (also inspired by Chelsea Troy's post).

How do we explore? If you move to a new city, you might learn the territory by walking around. Or you might peruse a map. But far more effective than either is both together — a street-level experience with higher-level guidance.

Likewise, the most powerful way to gain insight into a system is by moving between levels of abstraction. Many designers do this instinctively. But it’s easy to get stuck on the ground, experiencing concrete systems with no higher-level view. It’s also easy to get stuck in the clouds, working entirely with abstract equations or aggregate statistics.

RC W4D2 - What can I do to improve my Python skills?

In a previous post, I mentioned how David Beazley implemented a compiler in Python and Haskell. He did a write up on a 'Haskell-style' parser in Python here.

I'm struck by the raw minimalism and expressiveness of the code. There is no advanced metaprogramming, operator overloading, or even any classes. If you want to see how everything works, the code is right there to look at. Most of the functions are tiny. The way that they compose together is pretty awesome.

In particular, to the question "What can I do to improve my Python skills?".

Much to their surprise, I often suggest doing a project in a completely different language or outside of their area of expertise. I think the main benefit of doing this is that you'll often see a completely different way of thinking about a problem that you can bring home to your own projects.

I'm very excited to try out the parser myself.


RC W4D1 - Expressiveness vs interpretability in programming languages

My time at RC this batch has largely been exploring functional languages. With Haskell, it’s fascinating to see how lazy evaluation introduces a different paradigm. With Idris, it’s intriguing to see types as first class citizens.

We had a group viewing of the talk on Verse by Simon Peyton-Jones yesterday. I didn't quite follow where the gaps in existing languages for what Epic Games is trying to do resulted in the the choices they made - functional logic language, declarative, lenient evaluation, static types, effect system. The main thing I came away with was confirmation that I should look into Prolog.

More generally, what I haven’t been able to put into words is how a language 'looks'. I remember trying out Ruby (likely for Rails) but the syntax didn't quite feel as 'natural' to me. Python felt more concise, and the ‘one way to do things’ philosophy translated naturally when I was picking up Go. Haskell looks even less familiar, perhaps here the different paradigm element keeps it separate vs comparing against imperative languages.

Learning compilers helped me think of languages as more similar to each other than different (especially now with Haskell at one end of the spectrum). Chelsea Troy summed up the Ruby vs Python difference in this post.

Ruby values expressiveness over interpretability: the artful Rubyist can construct code that reads more or less like an English sentence. Indeed, that was the intent of that language’s design. When this happens, it’s gorgeous to see. However, the inexperienced (or malevolent) Rubyist can construct code that works fine, but is utterly unintelligible.

Python values interpretability over expressiveness: the authors strive for there to be only one way to write something.

To clarify, I'm not saying it's a good or bad, just different. I’ll be sure to bring this up at coffee chats to get a better perspective.

RC W3D5 - Focusing on the process

I enjoy writing Friday posts since it lets me recap the week, plus having the weekend to mull things over.

In Week 1 of RC, I felt a little down thinking how next year it’ll be 10 years since my first pull request. Over the weekend I spent a bit of time looking through Eli Bendersky’s blog. I believe I first came across his blog when going through SICP, and later discovered he also had posts on implementing Raft.

What I hadn’t realized was that he started in blogging in 2003! This got me looking up Patrick McKenzie’s blog (aka patio11), who started his blog in 2006. OK so if people I admire for their technical writing started way back, then maybe I’m on the right track.

In any case, it’s a reminder to focus on the process, not the outcome.

Reading through blog posts also made me think about how blogs are the more fun read because you feel you’re learning a lot. What’s probably happening is you’re trading off depth for breadth. Perhaps this is why I have a tendency to go deep when there’s an external source of discipline, like a boss or course instructor.

Maybe it’s time to build that volitional muscle to go deep.

Going back to Eli, he didn’t just do SICP for a week. He spent close to a year working through the whole book, completing 94% of the 356 exercises. He also wrote ~66k words across 52 blog posts. That’s real volitional muscle.

It's a great blog - I looked it up over the weekend to read up on functors in Haskell. I then found a post on Hindley-Milner. I also discovered a post discussing left vs right folds, which goes into it in quite a bit more detail than mine…

Process. Not outcome.

It’s half way through my RC half batch. My plans for the remaining 3 weeks: chat more, pair more, write more. I would actually like to spend a bit of time going through Andrej Karpathy videos, and play around with AI-assisted coding. Let’s be a bit more ambitious, here we go.

Week 4 - Idris, CIS 194 Week 10 (functors)
Week 5 - Prolog, CIS 194 Week 11 (applicative functors)
Week 6 - parser combinators, CIS 194 Week 12 (monads)

Building that volitional muscle to go deep will have to wait.

RC W3D4 - Applying ML to flag risky payments

I initially intended to write this 1 week after the post on payments and chargebacks, but advice to my younger self was hard to push back.

I'll add that it was Impossible Project Day at RC. Change of plans here too - I wanted to build a static site generator with Idris but ended up creating a basic WebAssembly compiler. It was clearly impossible since I planned to do it at my last RC batch and hadn't looked at it in the 2.5 years since.

In any case, risky payments. Imagine you start a payments processing startup. Everything goes well at first, but at some point you start to notice fraudsters processing stolen credit cards. You hire someone to lead up the operations team, going through every payment to make sure they're legitimate. Over time your payment volume goes up. Next you hire a software engineer to build a payment review queue, say to review the payment if it's above $1,000 and has an IP address outside of the US.

This decision tree is simple to understand and set up, but also easy to get around. Fraudsters may realize the $1,000 threshold and start processing $999 payments instead. In addition, what is thought of as fraud signal may not be it. For example, instead of the IP address being the red flag, it's actually the language setting on the browser.

This is where machine learning (ML) models can help. First, instead of a 'review' or 'no review' determination, the model would return a score between 0 (not fraud) and 1 (fraud). We can set up the queue such that payments above a certain threshold are reviewed; this is set based on review capacity and risk tolerance. Second, the model would use all possible features as input, and give higher weights to more predictive features based on historical data. This is often called a classification model.

Different models have different trade-offs. Logistic regression is the more 'explainable' model, in which there's a direct relationship between the weights and the likelihood of fraud. We also have 'black box' models like random forests, that employ a 'wisdom of crowds' approach by training a 'forest' of trees. These are harder to understand but have much better predictive performance.

How do we think about performance metrics? The 'precision' of each model is the percentage of cases reviewed by the ops team that end up being blocked, over the total number of cases created. The 'recall' is the total blocked dollar amount over total dollar amount across all cases. Tracking precision alone may end up solving for risky but low-dollar payments, so we'll want to optimize for both.

Another consideration is 'lagging' vs 'leading' indicators. Chargebacks are our 'ground truth' but can arrive up to 3 months from the payment time; this is our lagging indicator. Having the ops team review payments helps provide a leading indicator, especially against fraud rings, but what the ops team blocks may not necessarily end up being chargebacks.

Once we have an effective baseline workflow, we can potentially layer on a process to automatically block payments that are extremely likely to be fraudulent. This helps free up ops team capacity. In addition, if we think of high-scoring payments as 'bad', then low-scoring payments can highlight 'good' customers we want to do more business with. In other words, we get a 'credit-like' model for free.

RC W3D3 - Advice for my younger self

I had an in-person coffee chat with Ravi Dayabhai, and I believe it's the first time I've met a fellow Recurser in person! We had a fun chat across a wide range of topics. The part that stuck with me was talking about CS courses. I did a lot of them at Bradfield, more recently with David Beazley, and I would be the first to say it's better to run rather than sit still. To quote David Albert, "When in doubt, code".

That being said, if I was able to talk to my younger self, I would tell him to spend a bit of time thinking what he finds fun and how to find work that extends that. That way what you learned through 'joy of learning' gets reinforced and compounds.

Maybe it doesn't exist, and that's OK. It's a helpful exercise to think about it, even if it's 10 minutes every year.

RC W3D2 - The end of the speed-run

Different people have different learning styles. The style that I find works well is to go through the material end-to-end in multiple iterations. The first pass usually as fast as I can for the high-level overview, then hone in on specific sections. Perhaps this is why learning SICP with David Beazley was pure joy.

I’m at functors in Haskell and I can’t pattern-match as easily.

Time to slow down. Time to reflect. Time to do the other things I mentioned I’ll do at RC: chat more, pair more, write more.

RC W3D1 - The labors of the functional programming enthusiast

To those who maintain a blog and wonder if you’re putting in too much effort relative to the value you get out of it: (1) Let’s chat (2) The person who finds this blog most helpful is myself.

It’s the start of Week 3, thankfully feeling a bit more centered. I had been wondering if I was learning Haskell for the wrong reasons, did a presentation last Friday, and felt reassured in my decision when I was able to draw line linking learning SICP in December to learning Haskell now.

In yesterday’s post, I reflected on doing things for the wrong reason. I suppose it’s common to do things in extremes, hence the stereotype of the investment banker ditching the high life to get into spirituality. My version of this is getting into functional programming after spending time working on infra (though to be fair, I didn’t do it for that long).

I imagine I’m also not alone in wanting to learn one thing and then discover whole new worlds. The starting point was SICP into Haskell. Then there was lambda calculus, type theory, category theory. Maybe proofs. Maybe other functional languages. Maybe implementation / compilers.

In a nutshell, way too much. Too much for a half batch, too much for a full batch. I’m not sure my significant other would love the idea of a year-long sabbatical.

What is it all for anyway? How does it make me a better programmer?

I’m one third into the half batch. I feel compelled to share ’the story so far’.

The question ‘what is functional programming?’ came up in FP study group last week. I like to think of the broader answer around 'functions as first-citizens', namely that you can pass functions as arguments and functions can return other functions (often referred to as closures). This way lots of other imperative languages like Python say can be written in a functional way.

Then there’s functional in the sense of ‘functional vs imperative’. In this context, functions are pure (no side effects) and variables are immutable. Thus calling the same function with the same arguments results in the same output every time.

Now I imagine lots of people wanting to get into functional programming pick up Haskell, but Haskell is additionally a lazy language. This means that evaluation is delayed until results are actually needed, whereas most functional languages are eager. As per Brent Yorgey, It’s impractical and unexpected for a lazy language to not be pure.

We next get to the question of types. Why the tight coupling between functional languages and types? I don’t have a good answer.

Some suggest it’s a practical consideration, but I’m less convinced given the examples of most lisps (functional but dynamically typed) and Rust (imperative but has algebraic data types). I lean more towards the explanation of the language designers being ‘people who like abstract ideas and want to implement abstract ideas’; there’s a tradition of the languages being academic or experimental before becoming ‘industrial strength’. Examples include ML becoming OCaml, and Haskell itself.

I got to the chapter on functors in UPenn's CIS 194, and thought they looked familiar. I had a little digression into Bartosz Milewski’s category theory videos (highly recommend the intro, his enthusiasm is infectious). Functors appeared to me as ’this abstract idea is cool, let’s see what it looks like implemented in the language’.

OK so now we’re in real deep. The intro video talked about the Curry-Howard correspondence, which basically says there is a direct relationship between computer programs (namely the typed lambda calculus) and mathematical proofs. This was extended to the Curry-Howard-Lambek correspondence, that extended the equivalence (or isomorphism) to categories as well.

"Stop, stop, I’m lost!”, you say. I hear you, so am I.

Where do I go from here? I plan to finish up Haskell via CIS 194 (surely you can’t skip monads). I just got a copy of The Little Typer, maybe get Types and Programming Languages in post-batch (Stanford's CS 242 looks pretty cool, even has a paper on the teaching philosophy). RC has Impossible Projects Day on Thursday, here’s my excuse to jump head-long first and see where the tides take me.