This book is an introduction to programming language theory using the proof assistant Agda.

While it seems unreasonable to expect the XOR solutions in interviews, it is quite fun to figure out how they work. As it turns out, they are all based on the same fundamental trick, which we will derive in a bottom-up way in this post. Afterwards we will look at a bunch of applications of that XOR trick ™, such as solving this popular interview question:

You are given an array of n - 1 integers which are in the range between 1 and n. All numbers appear exactly once, except one number, which is missing. Find this missing number.

Of course, there are a number of straightforward ways to solve this problem, but there is also a perhaps surprising one using XOR.

Read More

This course covers all the main aspects of the language that you need to use in your daily practice. The course consists of five parts that explain the theory and offer many practical assignments. It is assumed that you try solving the tasks yourself before looking to the solution.

If you only start learning Raku, you are advised to go through all the parts in the order they are listed in the table of contents. If you have some practice and you want to have some specific training, you are welcome to start with the desired section.

Read More

hello! Yesterday I learned about a cool new way of streaming events from a server I hadn’t heard of before: server-sent events! They seem like a simpler alternative to websockets if you only need to have the server send events.

I’m going to talk about what they’re for, how they work, and a couple of bugs I ran into while using them yesterday.

We all know how to teach recursion. We’ve done it for decades. We pick some honored, time-tested examples—Fibonacci numbers and factorial being leading candidates—and use them to teach the general idea. They’re so canonical they come directly from the gods: you can find these in books by people like Niklaus Wirth.

But I’m here to tell you they got it wrong, and everyone’s been getting it wrong ever since. Students come away underwhelmed and baffled, and go on to become the next generation of teachers who repeat this process. However, we need not repeat this cycle; we have much better methods.

Read More
Dec 30, 2020

Well, I’m finally bringing this series back from a months-long hiatus! In the last post, we started implementing an emulator for a simple instruction set of our own. We sketched out the overall architecture, and implemented a few instructions for moving data between virtual registers and memory, learning about the corresponding x86-64 instructions along the way. In this one, I want to focus on arithmetic and logic operations, which will allow our emulator to do stuff that is a bit more interesting than just moving bytes around. But before we jump into that, I want to briefly talk about how numbers are represented in a computer.

Read More

Recursion is a powerful and subtle concept. A great way to gain an intuition of its structure is to visualise different patterns of recursion with graphics. In this chapter, we will use a simplified interface to the vector graphics library Rasterific to generate recursive images.

Dec 28, 2020

Bloom filters are a data structure which allows you to test whether an element exists in a set, with lower memory usage and better access times than other hash table implementations. It is probabilistic, and while it can guarantee negative matches, there is a slight chance it returns a false positive match. Through clever mathematical assumptions, we can produce constraints to minimise the chance of a false positive.

Dec 27, 2020

Haskell is notoriously famous for having a steep learning curve. A situation that frustrates newcomers to the language, especially newcomers who are experienced developers using other programming languages.

It is not uncommon to see seasoned developers express their frustration by making the point that all of the other languages they have picked up, they have been able to get productive within a reasonable amount of time, but Haskell only manages to remain an impenetrable wall of Egyptian glyphs after the same period of time.

A reason often cited for Haskell’s steep learning curve is the fact that “Haskell is different”. The argument goes: Haskell is not all that difficult, it is just different, and because of this, it is unfamilair. But most of the time, when this argument is made, it is not mentioned how exactly Haskell is different.

Sure, there could be other reasons why learning Haskell may be considered difficult, but we think the difference argument is an interesting one worth exploring. This is exactly what this post is about. The idea is to do more than just mention that Haskell is different but to show how. The hope is that doing this, will prepare newcomers to the language, hence preventing Haskell’s difference from being a stumbling block to learning the language.

So in what ways is Haskell different?

Read More
Dec 26, 2020

You do not need math to become a first-rate programmer because we do not use much of Math directly. If you want to become programmer then learn programming. Computer programming is very different from mathematics, and as a computer programmer you have to focus more on how to write better programs, how to think in a particular paradigm…

@UndergroundMan shared their post

This flânerie is about the formalization of the idea of proof, and its application in computer science. It’s a rich and complex subject, and there is far more material than I can possibly cover without attempting to be encyclopedic. This is one possible approach to the subject; not the most widely-used approach, but one that I believe will be of particular interest to computer scientists.

In a nutshell, over the course of this stroll, if you do the recommended exercises, you will construct a very small proof assistant (which I call Proust) to help you construct and verify proofs of statements about programs. Furthermore, and this is the main novelty of this treatment (at least for my intended audience), the proofs themselves will be programs. You will think of them as programs, and you will use what you know of programming to construct them. In the process, you will learn the language and substance of formal logic. We’ll wrap up with a look at some larger systems that use the same principles and that are in use in research and industrial settings. By the end of this introductory chapter, I hope to convince you that this is a sensible approach, and that you should continue reading.

Read More

In this post, I’d like to re-introduce lock-free programming, first by defining it, then by distilling most of the information down to a few key concepts. I’ll show how those concepts relate to one another using flowcharts, then we’ll dip our toes into the details a little bit. At a minimum, any programmer who dives into lock-free programming should already understand how to write correct multithreaded code using mutexes, and other high-level synchronization objects such as semaphores and events.

Read More
Dec 14, 2020

Scala is one of the main application programming languages used at Twitter. Much of our infrastructure is written in Scala and we have several large libraries supporting our use. While highly effective, Scala is also a large language, and our experiences have taught us to practice great care in its application. What are its pitfalls? Which features do we embrace, which do we eschew? When do we employ “purely functional style”, and when do we avoid it? In other words: what have we found to be an effective use of the language? This guide attempts to distill our experience into short essays, providing a set of best practices. Our use of Scala is mainly for creating high volume services that form distributed systems — and our advice is thus biased — but most of the advice herein should translate naturally to other domains. This is not the law, but deviation should be well justified.

Read More
Dec 12, 2020

This tutorial will guide you through writing the “Hello World” program in the C programming language. You’ll use Unix-style terminal emulators and command-line tools to execute commands, Linux-style package managers to install programs and libraries, the GNU nano text editor to write C code, the meson build system to build executable programs and the Gtk+ library to write portable, cross-platform graphical programs.

Nov 29, 2020

In Ray Tracing in One Weekend, you will build a simple brute-force path tracer. Continuing with Ray Tracing: The Next Week, you will add textures, volumes (like fog), rectangles, instances, lights, and support for lots of objects using a bounding volume hierarchy (BVH). Finally, with Ray Tracing: The Rest Of Your Life, we’ll dive into the math of creating a very serious ray tracer.

This document is intended to be informative, not evangelical. It is aimed at people who, like me:

  • dislike the official Perl documentation at http://perl.org/ for being intensely technical and giving far too much space to very unusual edge cases

  • learn new programming languages most quickly by “axiom and example”

  • wish Larry Wall would get to the point

  • already know how to program in general terms

  • don’t care about Perl beyond what’s necessary to get the job done.

This document is intended to be as short as possible, but no shorter.

Read More
Created on Nov 8, 2020
By @gurlic