This is my own collection of hard-earned knowledge about how integers work in C/C++, and how to use them carefully and correctly. In this article, I try to strike a balance between brevity (easing the reader) and completeness (providing absolute correctness and extensive detail).

Whenever I read or write C/C++ code, I need to recall and apply these rules in many situations, such as: Choosing an appropriate type for a local variable / array element / structure field, converting between types, and doing any kind of arithmetic or comparison. Note that floating-point number types will not be discussed at all, because that mostly deals with how to analyze and handle approximation errors that stem from rounding. By contrast, integer math is a foundation of programming and computer science, and all calculations are always exact in theory (ignoring implementations issues like overflow).

Read More
@linuxgirl shared their post

This book is a product of my own endeavour of understanding category theory. It is just that as I am explaining something, I am understanding it better. It is aimed at programmers, as well as anyone else who is interested in this stuff.

The main reason I am interested in Category Theory is that it allows us to formalise some common concepts that we use in our daily (intellectual) lives. Much of our language is based on intuition and rightfully so: relying on intuition is a very easy way to get your point across so it is understood by other human beings. However, that is part of the problem: sometimes intuition makes it too easy to communicate with someone. So easy that he might, in fact, understand things that you haven’t actually said. For example, when I say that two things are equal, it would seem obvious to you what I mean, although it isn’t obvious at all (how are they equal, at what context etc). That is the place when we might want to provide a more rigorous definition of what am I saying (even if I did not have one, to begin with). But providing such definition in natural language, which is designed to use intuition as a means of communication, is no easy task. It is in these situations that people often resort to diagrams to explain their thoughts. Diagrams are ubiquitous in science and mathematics because they are an understandable way to communicate a formal concept clearly. Category theory formalises the concept of a diagram and their components - arrows and objects and creates a language for presenting all kinds of ideas.

In this book, we will visit those formalisms and along the way, we would see all other kinds of mathematical objects, viewed under the primsm of categories.

Read More

WebGL2 from the ground up. No magic.

These are a set of articles that teach WebGL2 from basic principles. They are NOT old rehashed out of date OpenGL articles like many others on the net. They are entirely new, discarding the old out of date ideas and bringing you to a full understanding of what WebGL really is and how it really works.

“Formal methods of software design” means using mathematics to write error-free programs. The mathematics needed is not complicated; it’s just basic logic. The word “formal” means the use of a formal language, so that the program logic can be machine checked. Our compilers already tell us if we make a syntax error, or a type error, and they tell us what and where the error is. Formal methods take the next step, telling us if we make a logic error, and they tell us what and where the error is. And they tell us this as we make the error, not after the program is finished. It is good to get any program correct while writing it, rather than waiting for bug reports from users. It is absolutely essential for programs that lives will depend on.

The course begins by introducing (or reviewing) the basic logic that will be used as an aid to programming. Then we look at formal specifications, and how they are refined to become programs. At each refinement step, there is a small theorem to be proven (that the step is correct), so that at the end, the program is correct. Most of the course uses just those programming constructs that are common to most programming languages (assignment statement, if statement, array). We also look at parallel and interacting processes, at probabilistic programming, and functional programming. Along the way, we formally define the language features we use (both execution control and data structures). The emphasis is on program development to meet specifications, and on program modifications that preserve correctness, rather than on verification after a program is finished.

Read More

An explanation of how to implement a simple hash table data structure using the C programming language. I briefly demonstrate linear and binary search, and then design and implement a hash table. My goal is to show that hash table internals are not scary, but – within certain constraints – are easy enough to build from scratch.

Cubic Béziers are by far the most common curve representation, used both for design and rendering. One of the fundamental problems when working with curves is curve fitting, or determining the Bézier that’s closest to some source curve. Applications include simplifying existing paths, efficiently representing the parallel curve, and rendering other spline representations such as Euler spiral or hyperbezier. A specific feature where curve fitting will be used in Runebender is deleting a smooth on-curve point. The intent is to merge two Béziers into one, which is another way of saying to find a Bézier which best approximates the curve formed from the two existing Bézier segments.

In spite of the importance of the curve-fitting problem and a literature going back more than thirty years, there has to date been no fully satisfactory solution. Existing approaches either fail to consistently produce the best result, are slow (unsuitable for interactive use), or both.

The main reason the problem is so hard is a basic but little-known fact about cubic Béziers: with C-shaped curves (no inflection point and a small amount of curvature variation) there tend to be three sets of parameters that produce extremely similar shapes. As a result, in general when fitting some arbitrary source curve, there are three local minima. Approaches based on iterative approximation (in addition to being slow) are likely to find just one, potentially missing a closer fit of one of the others.

Read More

This tutorial assumes no previous knowledge of scripting or programming, yet progresses rapidly toward an intermediate/advanced level of instruction … all the while sneaking in little nuggets of UNIX® wisdom and lore. It serves as a textbook, a manual for self-study, and as a reference and source of knowledge on shell scripting techniques. The exercises and heavily-commented examples invite active reader participation, under the premise that the only way to really learn scripting is to write scripts.

This book is suitable for classroom use as a general introduction to programming concepts.

Read More

Over the last 25 years, I’ve written a lot of event-driven code in C++. A typical example of event-driven code is registering a callback that gets invoked every time a socket has data to be read. Once you have read an entire message, possibly after many invocations, you parse the message and invoke another callback from a higher layer of abstraction, and so forth. This kind of code is painful to write because you have to break your code up into a bunch of different functions that, because they are different functions, don’t share local variables.

Read More

One of my favourite programming languages in the last few years has been Crystal. While the language has not yet reached its 1.0 version, it has been widely used in production and has a growing ecosystem. Crystal provides an easy setup and allows you to jump straight into developing your own Crystal programs. I’m going to walk you through getting it setup and how you can get started!

I have been exploring how disk-oriented databases efficiently move data in and out of disk. One way, that I explored in Discovering and exploring mmap using Go and But how, exactly, databases use mmap?, is through memory-mapped files. Although mmap is a really neat solution, it has some troubles. Most troubles come from the fact that the database has no control of how pages are flushed to disk since that job is carried through the OS. Because of that most databases avoid using mmap. However, they still need to read and write data from disk in an efficient manner. And the answer to that is: buffer pool.

In this post, we’ll explain how a buffer pool manager works and how to implement one in Go. But first, let’s do a simple recap of how data is structured in disk.

Read More

In shared memory multiprocessor architectures, threads can be used to implement parallelism. Historically, hardware vendors have implemented their own proprietary versions of threads, making portability a concern for software developers. For UNIX systems, a standardized C language threads programming interface has been specified by the IEEE POSIX 1003.1c standard. Implementations that adhere to this standard are referred to as POSIX threads, or Pthreads.

The tutorial begins with an introduction to concepts, motivations, and design considerations for using Pthreads. Each of the three major classes of routines in the Pthreads API are then covered: Thread Management, Mutex Variables, and Condition Variables. Example codes are used throughout to demonstrate how to use most of the Pthreads routines needed by a new Pthreads programmer. The tutorial concludes with a discussion of LLNL specifics and how to mix MPI with pthreads. A lab exercise, with numerous example codes (C Language) is also included.

Read More

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
Created on Nov 8, 2020
By @gurlic