Setup github.io page with Jekyll

Now that I am blogging about programming, I’ve figured that I should start a separate blog just for that, which I can showcase to others without the risk of political incorrectness (which of course requires I keep it strictly technical). I had thought of blogspot, but the pros use github.io. So I naturally looked into that. And I’ve decided that I’m going to document the process as I go.

First, I found that the version of ruby on my mac was not to date, so I used rbenv to install a sufficiently up to date version. However,

ruby -v

did not change though almost certainly, the later version was installed. Annoying, it meant that I had to point the ruby bash command to the newly installed executable either directly or indirectly. I had done this shit quite a while ago, and now it recycles, just like every time you start a new tech job, you have to go through a not terribly fun setup process. Fortunately, switching to rvm did the trick.

See, I had created on my github a repository for my github.io page, selected a theme (kind of like a WordPress theme), and git cloned that to my local machine. But when I, per instructions here, run

bundle exec jekyll serve

it complains

jekyll 3.8.3 | Error:  The jekyll-theme-cayman theme could not be found.

So I decide to start all over with

jekyll new . --force

Now when I ls the directory, I get

404.html	Gemfile		Gemfile.lock	_config.yml	_posts		about.md	index.md

Running again

bundle exec jekyll serve

gives me

Configuration file: cwdir/_config.yml
            Source: cwdir/me.github.io
       Destination: cwdir/_site
 Incremental build: disabled. Enable with --incremental
      Generating... 
                    done in 1.555 seconds.
 Auto-regeneration: enabled for me.github.io'
    Server address: http://127.0.0.1:4000/
  Server running... press ctrl-c to stop.

Going there gives me

Screen Shot 2018-06-11 at 6.03.38 PM
And now I git commit and push to GitHub and see it at the actual hosted page!

Bubble sort using IORef

I started learning Haskell around summer of 2015, and to be honest, I found it very difficult. It, as a representative of functional programming, requires a very different mode of reasoning, one that I had not really exposed myself to before. I used very light features of Haskell at a real job for testing purposes. With “very light,” IORef is obviously disqualified. I haven’t touched it for over a year, and I am quite rusty on it. Though I expect, since I had diligently worked through example code of various Haskell constructs and patterns, to the point where I could follow what was going on without much difficulty, I can retrain up to the level I had previously been at without too much difficulty.

I believe I first learned of functional programming a few years before when I started with Haskell, with, memorable, the introduction of the two line quicksort. See, at that time, I basically didn’t have a clue how programming really worked, and so I actually might have believed that it was the real quicksort. Maybe I wasn’t even fully aware of quicksort’s important in place distinction, which is what renders it superior to mergesort, which is also O(n \log n). It’s pretty non-trivial to implement the actual quicksort in Haskell, because Haskell, as a functional (non-mutable state) programming language, is such that mutable arrays are somewhat difficult to work with. Of course, this no mutable state associated with functional programming is an ideal that is too good to be true. What happens, roughly, is that mutation of memory, which is necessary for any program to run, is done under the hood; it is the higher level language that protects against dangerous mutation of memory. Though I have read the code for it, long ago, I still cannot say that I actually ever understood how real quicksort is implemented in Haskell. Even now, given how rusty I am, I feel like it might be a bit too much to put on my place. So instead, I’ll go over bubble-sort, with the hope that quicksort will be elaborated on this blog not long after. The resource I am basing off of is from another blog.

We start by introducing IORef, which gives us a mutable reference to a type. It is not a pure operation, with every operation on it involving the IO monad.

The functions involved for manipulating IORef are:

data IORef a

newIORef    :: a -> IO (IORef a)
readIORef   :: IORef a -> IO a
writeIORef  :: IORef a -> a -> IO ()
modifyIORef :: IORef a -> (a -> a) -> IO ()

I will assume the reader if aware how bubble sort works. Now let’s brainstorm how we would, using IORef, implement it. First of all, what is its type. It should be

bubbleSort :: [Int] -> IO [Int]

From this, we can easily guess that we ought to transform the input [Int] into a IORef [Int]. A difficulty here is that the constructor for IORef, newIORef wraps the IORef inside IO. Applying map would thus give us a list of IO, the results of which we wish to collect. For this, we use mapM.

So in our code will have something like

xs <- mapM newIORef input

Now, we want to n-1 times, where n is the length of the input, the number of passthroughs needed to complete bubble-sort with guarantee, perform the passthrough swap adjacent elements (if not in order) operation. The passthrough swap operation is an action to be completed n-1 times. How do we characterize this action, in code? It consists of pass through and maybe swap on each index. Each index maps to an operation, and these operations can be collected in a sequential fashion. In code, this would along the lines of

\j -> do
    let ix = xs !! j
    let iy = xs !! (j + 1)

    x <- readIORef ix
    y <- readIORef iy     when (x > y) $ do
        writeIORef ix y
        writeIORef iy x

For this we can use mapM again, but better can be done stylistically. There is the output of the operation, which is IO () , or when combined IO [()] contains no information, so it can be discarded. There is a variant of mapM for that, mapM_. Since an anonymous function (that in this case maps an index to a do statement) is somewhat bulky, we’d like to have it as the latter argument, and forM_ is mapM_ with the arguments swapped.

Finally, we pull out the values from the IORef with

mapM readIORef xs

Putting all this together gives us

bubbleSort :: [Int] -> IO [Int]
bubbleSort input = do
    let ln = length input

    xs <- mapM newIORef input
    forM_ [0..ln - 1] $ \_ -> do
        forM_ [0..ln - 2] $ \j -> do
            let ix = xs !! j
            let iy = xs !! (j + 1)

            x <- readIORef ix
            y <- readIORef iy

            when (x > y) $ do
                writeIORef ix y
                writeIORef iy x

    mapM readIORef xs

Finally, we note that there is an issue ignored for the sake of simplicity since it is not the focus of this article. One might have noticed the !!. What is that?

Prelude> :t (!!)
(!!) :: [a] -> Int -> a

It’s the list accessor function, which is linear time, unlike constant time array access. I will, hopefully, dive into how arrays with constant time reads and writes are implemented in Haskell in some detail. For a high level explanation, see this answer on StackOverflow. Basically, there is a Haskell runtime system with primitive operations for memory reads and writes (that is linked with a Haskell program as part of the compilation process for production of the executable). See here for a manual of the runtime system, with all the runtime system options one can set for the executable.

Tech industry, an interview question, and tail recursion

I have written on here before that I sort of disliked the tech industry. Why? Because I felt many of the people there are kind of boring and not that smart, and much of the work is quite mundane, though of course there are some extremely good ones who do the bulk of the technical heavy lifting (I’m not, though maybe I could become one), who are grossly under compensated relative to their actual contribution. Of course, my standards must be way too high, or I must be way too weird or non-conformist, or too spoiled. At the very least, the tech industry pays quite well, especially the big companies which offer bonus and equity. Of course, plenty of 150+ IQ people will go into grad school in math or physics or computer science, doing some much more academically involved work, often with contempt for the intellectual lightweights in the tech industry. I plead guilty to having had that sort of attitude as well, and maybe I still do. Related to that is how I found the whole artificial marketing and inflation of achievement in tech kind of disingenuous. However, I’ve figured out by now that one only has much to lose from not playing along in that game. I’ve been paying more attention to LinkedIn recently. It’s literally a credentialist cesspool of professional posturing, full of mediocrities who put on there literally every detail of their professional and extracurricular life. My having become more accepting of that indicates somewhat that I’ve improved attitude-wise. I feel like I talk to some non-techs too now, in a normal way, without expressing any sign of contempt, because what’s the point? My next step would probably be to shut down this socially unacceptably nerdy and elitist and non-PC blog, but unfortunately, I don’t feel comfortable dulling myself out like that. Of course, it might just be that the whole career game more or less compels me to do so sooner or later. When I say this, I have in mind the following from Michael O Church’s essay Does Genius Exist:

Most gifted children seem like they might achieve creative excellence in adulthood; very few actually do. I’ve observed the careers of extremely intelligent (i.e., IQ 160+) people and the results are, at best, disappointing. About half go to graduate school; the other half go to Wall Street or Silicon Valley straight out of college. Either way, they expect to defeat the morons in business handily, retire within ten years, and dedicate the remainders of their lives to intellectual pursuits. It almost never works out that way. It’s not uncommon for highly intelligent people to be mobbed and bullied in their corporate jobs by resentful mediocrities, although even more common is for them to disappear into the bland, beige fog, and to lose every element of originality they once had. Most often, they disappear somewhere in the folds of middle management, and do what they can to hide what they once were.

I already feel more comfortable doing what, according to this, is most often done by the gifted later in life, not that I am +4 sigma above the mean, which is evident from my credentials, though +3 sigma sounds about right. Surely, success in the corporate world relies much on being liked by those in power which requires being conformist, loyal (or at least appearing so), dependable, and not threatening to the interests above. You get promoted by becoming the manager’s favorite, which is done by being the one who supports the career of the manager the most in an indispensable way.

I don’t like much the whole interview process in tech. It’s like the problems are so trivial (they are artificial and not all that related to real engineering) and some of the interviewers are nowhere near as smart as me, IQ-wise. Well, it doesn’t matter, because one has to adapt to one’s world instead of the other way round. And like it or not, for those on the tail end, the distribution of IQ/ability in the world is what it is today.

Speaking of tech interviews, I was asked this question in a recent interview.

Flatten a list. The list, of course, can have list elements. So something like
flatten([1,2,3,[10,30]]) => [1,2,3,10,30]

I had done this problem before. There is the brute force recursion solution. In Python, which is a dynamically typed language (which is more or less necessary for this problem (because otherwise, one would have to impose some type constraints and on top of that find a way to make nested lists work within a static type system, which as far as I can tell, would require defining some generic sum type of primitive types and the list type of that generic sum type itself), this would be, in functional style

def flatten(l):
  return [l] if type(l) != list else sum(map(flatten, l), [])

Of course, in the actual interview, I wrote it imperative style, to increase my chance of passing it. 😉

This is of course actually inefficient, in that there will be a copy made at each level of the recursion. To avoid that, we employ a helper function.

def traverse(acc, l):
  if type(l) != list:
    acc.append(l)
  else:
    for e in l:
      traverse(acc, e)

The flatten function itself would be

def flatten(l):
  acc = []
  traverse(acc, l)
  return acc

By essentially preallocating the space for the output flattened list and appending to it via traversal, we use constant memory aside from the linear for the returned flattened list itself.

What did this problem remind me of? Tail recursion. Functional languages support it to avoid adding a new stack frame on each recursive call, which would be very handy for this problem. In fact, the traverse function, in its pattern of implementation can be translated to a tail recursive one in a functional language. We’ll leave that for later.

To start, we’ll present a canonical example of tail recursion, the factorial function. In Haskell, the immediate implementation it would be

factorial :: Int -> Int
factorial n = if n <= 0 then 1 else n * factorial (n-1)

In assembly, we would have something like

_Z9factoriali:
        # create new stack frame
        pushq   %rbp
        movq    %rsp, %rbp
        subq    $16, %rsp
        # copy parameter to stack
        movl    %edi, -4(%rbp)
        # compare parameter with 0
        cmpl    $0, -4(%rbp)
        # the recursive case
        jg      .L2
        # the base case, set 1 as return value and return
        movl    $1, %eax
        jmp     .L3
.L2:
        # set argument in recursive call to current argument minus one
        movl    -4(%rbp), %eax
        subl    $1, %eax
        movl    %eax, %edi
        call    _Z9factoriali
        # set return value to n * factorial(n-1)
        imull   -4(%rbp), %eax
.L3:
        leave
        ret

One can see explicitly in the assembly the adding of a new stack frame for the recursive call. To avoid that, we employ tail recursion as follows.

factorialTail :: Int -> Int -> Int
factorialTail acc n = if n <= 0 then acc
                      else factorialTail (acc*n) (n-1)
factorial = factorialTail 1

In assembly, this would be

_Z13factorialTailii:
        # move acc to %edi
        movl    %edi, %eax
        # bitwise AND of %esi with %esi itself is %esi, set SF, ZF, PF flags accordingly
        testl   %esi, %esi
        # return if sign flag (SF) or zero flag (ZF) are on
        jle     .L5
.L2:
        # acc *= n
        imull   %esi, %eax
        # n -= 1, subl also sets zero flag 
        subl    $1, %esi
        # loop back if zero flag is not set, return once n == 0
        jne     .L2
.L5:
        ret

Notice how this is essentially a for loop, with no recursive calls. With the -O2 flag set on x86-64 gcc 8.1, which I used to generate the above assembly code, with my own comments later added, the tail recursion compiler optimization was implemented, as evidenced by the assembly produced. I ran this not on my own machine, but on the cloud via the handy godbolt.org compiler explorer I found, the code of which happens to be on GitHub. And I can only say that the guy who created this tool looks like another one of those uber prolific programmers blessed with tremendous instinct and power for building software systems. You might think that my writing a blog post with Haskell and x86 leans me towards this category as well. Oppositely, I actually think that I’m quite pathetically weak at computer stuff (and started off very unnatural at it), though I also believe that with some dedicated practice I can become good. I would say that I was natural with mathematics and algorithms but not with engineering or systems, though surely, with quite a lot of exposure, I developed, slowly, a sense for the latter as well, gradually steering what had been a horrendously off intuition towards the right direction, and concurrently, reducing, stage by stage, the sense of awe and intimidation I had felt with respect to the actual natural hackers. I can at least console myself by thinking that much of my awe’s having transformed into some sense of normalized (mentally) understanding is an indicator of rapid progress. Yes, there are still plenty of people way better than I am, but I no longer feel like what they are doing, their thought progress, cannot even be understood by my weakling brain, that once perceived it as some form of otherworldly wizardry beyond my comprehension, and of course, its actor some form of higher being.

On quite another domain, I felt somewhat similarly with regard to those at the top of the socioeconomic and political hierarchy. The default for corporate executives and those officially at the top is one of reverence. People assume that because they are on the top, they must be inherently superior in some way or another in their ability. Programmers, as status-insensitive, socially clueless aspies, are supposed to be largely oblivious to the political machinations orchestrated by those on top, to what is the reality of their (subordinate) position within the whole hierarchy. In any case, those people felt to me to be in a whole other world, similar to the impression I had of these elite programmers; I was much oblivious to that world and also could care less about it. Until I more or less developed, as far as I tell, a more accurate intuition for how that world works as well, much aided, of course, by experience, mostly indirect, but enough for me to, with my intelligence and independent judgment, construct what I believe is a reasonable picture or model for what actually goes on, one which I expect to be enhanced over time with more data collected. I’ve increasingly grown to realize, over time, that people are very much naturally psychologically chained to the reality of their official position, their formal credentials, which are correlated very imperfectly with actual ability, or in some cases loaded on (largely born) social position and artificial perception, even nil or negatively correlated; it takes an independent mind, a revolutionary mind to break free from that by disentangling the real and the artificial. And becoming mentally free is the first step towards becoming actually free.

Math vs engineering

I am currently a full time software engineer. I don’t really like the work and I mostly find it draining though I guess I’m not bad at it, though I’m definitely not great. Much of it is process and understanding of requirements and the specific codebase (that includes the tools it uses), which is more often than not not fun at all though I find it more tolerable now. It pays well but is low status, as Michael O Church loves to say. The work is rather lowbrow by STEM standards. I was thinking that it loads not very highly on g (at least line of business engineering) but rather highly on conscientiousness and ability to grind. The people who excel are at it are those who can do that type of work for long hours and not feel tired, and often ones who have the genes to sleep 5 hours a day and still be fine. It’s not a very attractive or sexy ability, but it is a very useful and respectable one. One of my colleagues spent 4 years working on FPGAs just to design one chip and he said after that experience, he’s not gonna do anything related to chip design again. I know that chip design is much more technically involved, much higher barrier to entry, and is actually the hardest to replicate part of computing. Anybody can build a website but only a few places have the expertise and infrastructure to make a good CPU. The latter requires a sophisticated industrial process, the fabrication part, which involves much advanced applied physics, none of which I know. I’ve heard that because fabs are a physical constraint which run in cycle, it is imperative to meet deadlines, which means you need the types who can pull all-nighters, who can toil day in day out in the lab on very detail oriented work (that’s often grindy, not artsy or beautiful like math is) with little room for error. It also pays less than software engineering, for obvious economic reasons. On this note, I recall adults knowledgeable were telling me not to major in EE because there are few jobs in it now. Electronics is design once mass produce. So many of them have been outsourced.

Engineering is hard hard work. Not intellectually hard (though there is that aspect of it too in some of it), but grindily hard. Plumbing is inevitable, and you have to deal with some dirty complexity. You need a very high level of stamina and of some form of pain tolerance that I don’t regard myself as very high in, though I’ve improved substantially. It’s not a coincidence that engineering is what makes the big bucks, for individuals (somewhat) and for economies (or execs in them). Rich countries are the ones who can sell high end engineering products like cars and CPUs.

Mathematics, theoretical science, on the other hand, is much more about abstraction of the form that requires a higher level of consciousness. Math and theoretical physics are far more g-loaded than engineering is and attracts smarter people, a different breed of personality, those with a more intellectual upper class vibe that I see largely absent in software engineering. These are used in engineering, but in it, they are merely tools with the focus being on design and on practical application, with cost as a major consideration. It is like how in physics, there is much mathematics used, but because math is just a tool for it, physicists can be sloppy with their math. Pure theoretical science is much more deep and far less collective and organizationally complex, with a pronounced culture of reverence for individual genius and brilliance. There is also an emphasis on beauty and on some pure elevation of the human spirit in this type of pure thought.

I myself am by nature much more in the theoretical category though I am for now in the practical one, pressured into it by economic circumstances, which I am looking to leave. I will say though that I have derived some satisfaction and confidence from having some practical skills and from having done some things which others find directly useful, as well as having endured some pain so I know what that feels like. In the unlikely case that I actually make it as a mathematician, I can say that unlike most of my colleagues I didn’t spend my entire life in the ivory tower and actually suffered a bit in the real world. I can thereby be more down-to-earth, as opposed to the intellectual snob that I am. I will say though that I do genuinely respect those who are stimulated by engineering enough to do it 24-7 even in their spare time. I don’t think I will ever be able to experience that by my very makeup. However, I do at least suspect that I am capable of experiencing to some extent a higher world that most of those guys fail to, which should bring me some consolation.

Programming types

Programming, the intense hacker side of it, attracts a certain breed of person. In short, I would put it as that it attracts those who are higher in autism than in g, though of course one needs to be reasonably high in both, especially the verbal side of g, as its activity is largely one of reading (of logs and documentation) and writing (of code (and its supporting documentation), the quality of which has good variable names as a major component). I do feel at times that programmers, even elite ones, are lacking in scientific taste. Many of them are mathematically null. They thrive on and even love the detailed minutiae involved in the work, such as encodings (like UTF, ASCII, that type of thing), the ins and outs of Unix, and arcane facts of various languages. I had to encounter in my work today parsing of CSV files, and it turned out that the CSV reader was not reading under the correct encoding. I ended up diffing my output with the output generated via a means more or less guaranteed to work to aid such’s diagnosis. I’m not bad at this type of thing any longer, having trained myself or more like grown to be able to patiently resolve such problems in a systematic, foolproof fashion.

Does that mean I enjoy this type of thing? No, not at all, though I find it tolerable, more or less. Too autistic for me. It does not have the depth that mathematics has. It has not the beauty of poetry or of music. It has not the wittiness of words or the expressiveness of (human) language. Nor does it have the significance on the world that politics has. There are more meaningful to be doing than programming, though needless to say there is much demand for it as the world now runs on computer programs, which are written mostly by politically incompetent and often socially awkward who answer to morons with MBAs.

I’ve come to notice that programmers tend to be very narrow. They only know programming. There are of course exceptions. Mathematicians and to a greater extent physicists are more broad, and more deep. It makes them very boring to talk with. The people who are more well rounded who are in programming are often, from my observation, in it for the easy money, which is of course paltry relative to what the parasites of our society suck in, but nonetheless a very good sum by the standards of ordinary folk.

There is of course another world of programming, that of the incompetents, who often know only Java and barely know any computer science even. They’re far from the functional programmers who I work with. This industry is so in need of grunt labor that those people manage to find their way into six figure salaries. Yes, this includes places like Google and Facebook. There are Google engineers who don’t know what the difference between stack memory and heap memory is and who think C++ pointers are scary, who make 200k a year or almost. I won’t talk more about them. Waste of breath.