Oskar Lidelson - Blog

Like an ancient wizard weaving his magics into an amulet , my emacs configuration has grown, and grown. Each year I've woven more of my power into it, to the point where emacs is now a part of me. It's not just an editor, it's literally a part of my mind.

A lisper accumulates every line of code they've ever written into a massive personal library, interconnected through org-mode with their music, media, books, links, diary, budget, documentation, website, repositories, … (and the list goes on for quite some time..)

It's not easy to describe this to the emacs uninitiated. Those unlucky people see editors as tools. Emacs is not a tool, it's a systematic way of life, a method of combining all things that I've ever done into a conglomerated tangle that can be reused integratively.

You either get it, or you don't.

A lot of my friends ask me why in the hell I use Lisp. They can't comprehend it. Most of them seem to be turned off by the parenthesis, actually, and at least one of them I'm certain is just complaining to be difficult, and has never actually given lisp any more than a moment's worth of thought (terrible excuse for a logical person he is!)

I use Lisp for my initial prototypes and ideas, and in general for things that don't need strong correctness guarantees or extreme speed.

I spent some time on The Science of Programming by Gries.

When I don't need the sheer power of Lisp, or the sheer speed of C++, I use Haskell for the sheer strictness and correctness.

It feels great to be able to reason (as well as I can) about the correctness of my code. It still has bugs, but when using haskell I try to be in a bourbaki-like ultra-rigorous mindset. If it compiles, it is probably correct.

This is a good mindset to have sometimes and I like that I get the opportunity now and again to exercise it. This is why I write in haskell sometimes.

Ipv6 is beautiful. The address space is huge, everyone gets a massive block to subdivide as they like (unless your ISP hands you only a single /64), and the stateless autoconfiguration (SLAAC) mechanisms are absolutely gorgeous: Nothing ever needs to be manually configured.

From the perspective of distributed systems, the router advertisements, RDNSS, and NDP messages are very cool. The ICMP messages for fragmentation size calculation are neat! Everything talks to everything else and autoconfigures itself dynamically constantly. Nothing is set once, everything is constantly being re-set and expiring so the system as a whole is self healing.

IPv6 is global, and encourages you to set up your firewall appropriately, since you can no longer rely on NAT to 'protect' you. That, and it means that anything can (in principle) talk to anything else. You'll never again be locked out of ssh'ing into your system because your stupid ISP was in the way. You'll never again be locked out of anything. As long as you know the address and have the firewall rules configured, you can connect.

The IPv6 address spaces are so enormous that even if you knew my prefix, you simply could not scan it for hosts, no matter how much bandwidth you had available. This means that there should be a massive reduction in all the random scans and attacks I receive every day on the internet. The network is finally quiet and clean, peaceful.

I use IPv6-only because IPv4 is broken. NAT broke it and the address blocks are exhausted. The protocol is, as far as I'm concerned, deprecated and obsolete, and should not be used at all. Don't write new code to interoperate with IPv4. Just write pure IPv6 code, and build tunnels to allow you to bypass incompetent ISPs if you must.

Applying a homomorphism to a true statement within an algebraic structure results in another true statement in the destination algebraic structure.

For instance, consider this:

Let \(P(x)\) denote some polynomial with coefficients taken from the reals. ie. \(P(x)\) is in \(R[x](+,*)\).

More importantly, \(P(x)\) is also in \(C[x](+,*)\) ie. the field of complex numbers.

Observe that the map \((f(x):C->C = x conjugate)\) is a homomorphism from \(C\) to \(C\). This is straightforward to verify, just check that \(f(x)+f(y) = f(x+y)\) and that \(f(x)f(y) = f(xy)\).

A homomorphism applied to a true statement in a field results in a true statement in the other field, therefore, if \(f(x) = 0\), then \(P(f(x))\) vanishes, too. This implies that roots of polynomials with real coefficients come in pairs; if they're complex: \((x, f(x))\), and if they're real, just \(x\) (because in that case \(x = f(x)\)).

So here you see that you can use homomorphisms to prove some really interesting things very concisely! They're also incredibly useful for computation, and making spiffy algorithms that map things into a smaller, easier to work in space, operate on them, and then use the results there as a heuristic to search for the true results in the larger space.

There are some algorithms where you'd like to iterate over all permutations of n objects. Here's some C++ code that will generate a list of them for you. It can be modified in a straightforward way to iterate instead, perhaps altered to accept a lambda function to apply to each one on generation.

#include <iostream>
#include <list>
#include <algorithm>

template<typename type_t>
std::list<std::list<type_t> > permutations ( std::list<type_t> set ) {
        typedef std::list<type_t> oset_t;
        typedef std::list<oset_t > oset_oset_t;
        oset_oset_t result_set;
        if(set.size() == 1) {
          result_set.push_back(set);
          return result_set;
        } else {
          for(auto i=set.begin();i!=set.end();i++) {
                std::list<type_t> rest_of_list;
                std::copy(set.begin(),set.end(),std::back_inserter(rest_of_list));
                rest_of_list.remove((*i));
                std::list<std::list<type_t> > partial_result = permutations<type_t>(rest_of_list);
                for(auto p = partial_result.begin();p!=partial_result.end();p++) {
                  p->push_front(*i); }
                std::copy(partial_result.begin(),partial_result.end(),std::back_inserter(result_set)); }
          return result_set; }}

int main (){
        std::list<int> S;
        for(int i=0;i<6;i++) {
          S.push_back(i); }
        std::list<std::list<int> > P = permutations<int>(S);

        for(auto i = P.begin();i!=P.end();i++) {
          for(auto j = i->begin();j!=i->end();j++) {
                std::cout<<(*j); }
          std::cout<<std::endl;
        }
}

Readable, simple code should better be called infantile. It's a good first step, but it's incomplete.

You need to write complex, difficult to understand code in order to get anything done properly. Consider the most performant algorithms available for known problems: FFT integer multiplication, group-theoretic alarmingly complex factorization algorihtms, the mind-twisting spatial data structures with various different locality or operation time guarantees, and I don't even want to get into the complexity of caching or distributed algorithms.

If your code is readable, it is likely also unoptimized. Programmers are not meant to write slow code any more than engineers are meant to build flimsy bridges. If it takes longer to write, so be it. The facts are, we either do it properly or we don't do it at all. I don't accept half-built bridges in the name of development speed.

Nobody builds a skyscraper and says "Hang on, the engineers might not be that smart. Let's use the dumbed-down building techniques and hope it stays up, so that they can have an easier time of it.".

What really happens is that they use the most advanced techniques they have available, and if the other engineers aren't up to snuff, they are in the wrong line of work! It's not my job to dumb down my code for lesser engineers. It's their job to train harder and get themselves to the level where they can work on faster code.

Simple code has its place for educational purposes, for the initial proof-of-concept version, and so forth, but when it comes down to production code it's going to be one unholy abomination because of all the layers of caching, abstraction, extendability, indirection and so forth you have to built into it for it to be well engineered.

Consider the following implementations of strstr to get an idea of what I'm saying:

It's probably happened to you before. You're running some simulation program on your GNU/linux system, and suddenly, you realize there was an error in your code; it would allocate far too much memory.

You foresaw issues like this and thus disabled swap. Modern systems don't really need swap space, anyway, unless you've got an SSD in which case it's still fast enough to be useful. However, even with swap disabled, you see kswapd in your process list consuming CPU cycles, and the whole system grinds to a halt. How? Why?

As it turns out, kswapd doesn't just work on swap space. It also swaps out mmap'd pages. Now, mmap is one of the best tools available to a linux programmer because it allows you to operate on large files with essentially transparent caching, and in the case where your accesses have great locality, you'll get massive speedups plus the security of fitting huge datasets into memory even if you don't have enough, knowing that it will only ever swap in the pieces you're currently viewing.

The fact that mmap is so awesome means that it's in use everywhere. That, of course, is a double edged sword. If your system is under memory pressure, (ie. some program is using up almost all of the available memory) then kswapd will come into play and begin paging out those mmapd regions. The problem, though, is that those mmap'd pages are, by design, for processes making active use of those files!

Thus, every mmap'd page that gets swapped out will be needed again, and soon. Your system grinds to a halt, attempting to swap the pages in and out endlessly. Even with swap space entirely disabled, your system will thrash purely because of the popularity of mmap.

Checkmate. Linux under memory pressure has been beaten by its own efficient system features. The only real solution is to use ulimit to set hard memory limits, and prevent your rogue simulator from exerting memory pressure in the first place.

At the time I've written this, there hasn't been any real progress toward a solution, ie. the ability to mark individual processes as 'unswappable no matter what', which would allow you to mark the GUI-related processes and, even under intense load, retain some control over your system; just enough to summon a terminal and issue the kill commands for your rogue processes.

As it stands now, once the thrashing begins you can't even summon the OOM-killer with the sysrq key. You can, but it will take minutes, perhaps hours, before the kernel is able to rise from its stupor to honor the OOM request.

You can use information theory to prove this, but compression is actually related to permutations. The set of all strings in your language, you permute. Some of them become representable in shorter strings, but others necessarily become longer strings. In total, the sum of information remains unchanged (information is conserved).

Good compression functions are those which map interesting inputs to shorter strings, while uninteresting inputs become longer ones.

So for instance, you'd want an algorithm which encodes written text and all human-created interesting media to compress well, but randomized strings of gibberish to become much longer under 'compression', because we don't care about those.

This site is actually written and managed in emacs org-mode, compiled to html in emacs, and then pushed to a static-serving bucket.

Some of the assets were manually created (the CSS, etc.)

If \(F(i)\) is the discrete convolution of \(f(x)\) and \(g(x)\), with \(f\) and \(g\) as two polynomials in \(R[x]\), then \(F(i)\) is the i^th coefficient of \(x\) in \(f*g\).

ToDo: Use this for something.

This is managed in git here: https://gitlab.com/sea/public/diary/media

This is just to fold/hide the section at the bottom with my emacs local variables for this file:

If you're curious, this is what's included:

(add-hook 'after-save-hook
          (lambda ()
                  (if (y-or-n-p "Tangle?")
                          (org-babel-tangle)))
                nil t)