## Blog

### Sorting and groups

I can't find much reference to this in the literature (see Maus for some hints and an interesting paper) , but surely people have looked at sorting as a problem in group theory? Given a sequence $latex s=[x_1\dots x_n]$ say a permutation $latex \pi$ sorts $latex s$ if and…

### C compiler developers are hostile to C programming

From the LLVM developer mailing list this remarkable exchange in which Chris Lattner of LLVM says that the compiler use of undefined behavior (UB) is so "crappy" that the only solution is to abandon C programming (my bold). On Jul 7, 2017, at 1:40 PM, Peter Lawrence <peterl95124 at sbcglobal.net>…

### Current reading: July 8 2017

Principal type-schemes for functional programs∗ Luis Damas† and Robin Milner First published in POPL ’82: Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, ACM, pp. 207–212 THE PRINCIPAL TYPE-SCHEME OF AN OBJECT IN COMBINATORY LOGIC BY R. HINDLEY Quicksort.  Tiny C - sheer genius! Plan B …

### The C standard versus C and the mother of all hacks.

The Kafkaesque interaction of the C standard and the main open source C compilers was concisely outlined by one of the main LLVM authors back in 2011: "knowing that INT_MAX+1 is undefined allows optimizing X+1 > X to "true". Knowing the multiplication "cannot" overflow (because doing so would be undefined)…

### The C standard committee effort to kill C continues

Consider the following code: void f(void) { unsigned char x[1]; /* intentionally uninitialized */ x[0] ^= x[0]; printf("%d\n", x[0]); printf("%d\n", x[0]); return; } In this example, the unsigned char array x is intentionally uninitialized but cannot contain a trap representation because it has a character type. Consequently, the value is both indeterminate and an…

### Types considered harmful

Russell introduced what is often viewed as his most original contribution to mathematical logic: his theory of types—which in essence tries to distinguish between sets, sets of sets, etc. by considering them to be of different “types”, and then restricts how they can be combined. I must say that I…

### Basic math for basic algorithms

It's odd that all the descriptions of basic programming operations, such as sorting, rely on pseudo code or complex formal logic. All we are doing is modifying finite sequences so it seems like we should be able to use ordinary algebra. I'm going to start by defi ning basic operations on…

### undefined behavior and the purpose of C

C undefined behavior. From one of the LLVM developers: This behavior enables an analysis known as "Type-Based Alias Analysis" (TBAA) which is used by a broad range of memory access optimizations in the compiler, and can significantly improve performance of the generated code. For example, this rule allows clang to…

### Computer Science as a scholarly discipline.

Google Scholar tells me that "Why Functional Programming Matters" was published in 1989 and has been cited over 1000 times. Here's a quote.  Recall that a complete functional program is just a function from its input to its output. If f and g are such programs, then (g. f )…