th.oughts

Living the fake American dream, 3 years at a time

As a newbie programmer, recursion took some time getting used to and once something worked, it usually appeared like magic. So, when working on an evening Lisp project, nostalgia kicked in and encouraged a little bit of exploration!

Let's consider a program that computes that the nth-power of a number. I usually tend to think in C (just like my thought process is mostly in my mother tongue which is not English) and looks as simple as:

int nth-power(int number, int n)
{
    if (n == 1)
        return number;
    else
        return number * nth-power(number, n - 1);
}

The Lisp (elisp) version is easy enough and almost identical:

(defun nth-power (number n)
   (let* ((result number))
   (if (eq n 1)
        number
        (setq result (* result (nth-power number (-n 1)))))
        result))

This works for small numbers but let's try a large number:

(nth-power 200 10000)
Debugger entered--Lisp error: (error "Lisp nesting exceeds `max-lisp-eval-depth`")
...

Ok, elisp gives up but what about SBCL:

(nth-power 200 10000)
(SB-KERNEL::CONTROL-STACK-EXHAUSTED-ERROR)

However, if we slightly modify the program to look like this:

(defun nth-power (number n acc)
   (let ((result (* number acc)))
     (if (eq n 1)
          result
     (nth-power number (- n 1) result))))

The result is:

Some huge number

The point is there's no more stack overflow. How so ?

Notice how the recursive call is the last statement in the above definition. That enables the compiler to do a Tail call-optimization. In simple terms, it means that the stack from the previous call can be reused and won't grow over time.

A disassembly makes it clearer. With the first example program, we have:

0] (disassemble 'nth-power)
; disassembly for NTH-POWER
					; Size: 130 bytes. Origin: <a href="https://th.oughts.org/tag:x1001F8EBC9" class="hashtag"><span>#</span><span class="p-category">x1001F8EBC9</span></a>
...
; C18:       488B0559FFFFFF   MOV RAX, [RIP-167]              ; #<SB-KERNEL:FDEFN NTH-POWER>
; C1F:       B904000000       MOV ECX, 4
; C24:       48892B           MOV [RBX], RBP
; C27:       488BEB           MOV RBP, RBX
; C2A:       FF5009           CALL QWORD PTR [RAX+9]
; C2D:       480F42E3         CMOVB RSP, RBX
; C31:       488B75E0         MOV RSI, [RBP-32]
; C35:       488BFA           MOV RDI, RDX
; C38:       488BD6           MOV RDX, RSI
; C3B:       41BB80030020     MOV R11D, 536871808             ; GENERIC-*
; C41:       41FFD3           CALL R11
; C44:       488BF2           MOV RSI, RDX
; C47:       EB98             JMP L0
; C49:       CC10             BREAK 16                        ; Invalid argument count trap

Notice how recursion is implemented with the call instruction on line C2A. This signifies switching to a new stack frame. In contrast, with our modified nth-power program, we have:

0] (disassemble 'nth-power)

; disassembly for NTH-POWER
; Size: 105 bytes. Origin: <a href="https://th.oughts.org/tag:x1001E67663" class="hashtag"><span>#</span><span class="p-category">x1001E67663</span></a>
...
; 98: L0:   488B55E8         MOV RDX, [RBP-24]
; 9C:       BF02000000       MOV EDI, 2
; A1:       41BB10030020     MOV R11D, 536871696              ; GENERIC--
; A7:       41FFD3           CALL R11
; AA:       488BFA           MOV RDI, RDX
; AD:       488B5DD8         MOV RBX, [RBP-40]
; B1:       488B55F0         MOV RDX, [RBP-16]
; B5:       488BF3           MOV RSI, RBX
; B8:       488B0549FFFFFF   MOV RAX, [RIP-183]               ; #<SB-KERNEL:FDEFN NTH-POWER>
; BF:       B906000000       MOV ECX, 6
; C4:       FF7508           PUSH QWORD PTR [RBP+8]
; C7:       FF6009           JMP QWORD PTR [RAX+9]
; CA:       CC10             BREAK 16                         ; Invalid argument count trap

The call instruction has been replaced with a jmp on line C7. This signifies that the stack size won't grow as was the case with the call instruction.

Note that, when using optimization with gcc, it will always try to optimize tail calls. It's easy to experiment with the optimization switches(-O0 -O1 -O2) and check the generated assembly code.

#lisp #programming

P2P and ready to be stolen!

Sometime in 2012, I made up my mind that I was done with my Bitcoin stash. I had a small collection, which at that time I thought wasn't much. Those were the good old days; I remember websites giving you free coins just for visiting them. Back to the point, I said to myself: “If I needed them later, I will get them again but for now, there's no sense in holding onto them”. So, off I went, transferring my coins to a [presumably] very reputable exchange and sell them for cash. Alas, before I could blink, I saw my account getting drained in small increments. It was almost like a scene from a popular CSI episode that nerds would make fun of for being too good to be true! Well, money was lost and I tried to wipe the experience from my memory somehow believing that it's just a matter of time before cryptocurrencies would be dead anyway. Boy, was I wrong!

Not only have many alt-coins of varied popularity sprung up with large communities thriving around them, they are getting unusual attention, both good and bad from researchers to financial organizations to oppressive governments. And while their fate is still a bit uncertain, news of breaches and stolen bitcoins are still not uncommon. One begs the question: Are cryptocurrencies really solving a problem and introducing another ?

Researchers are often so engrossed in solving a specific problem that they seldom look at the potential advantages of the bad by design (no pun intended) problem. And the cryptocurrencies solution seem to fall into this category. Ofcourse, Anonymity and Decentralization all sound like a step forward and they might be inherently desired but do they always work for the better ? Probably not. One of the many reasons why you don't hear about major breaches at your local bank is because by design, paper currency and the economy that encompasses it make transactions trackable. So, while they do expose your identity which might be undesirable in the greater scheme of things, maybe, a medium of exchange system could mostly benefit from being easily trackable and controlled by a central authority for it to work fairly. It would be difficult to ignore the evidence that paper money's long and successfully history provides in support of this theory.

On the other hand, while the anonymity advantage that digital currencies offer does sound appealing, it's worth pondering if it contributes to making it more difficult to protect it as well. Allow me to explain with an example: A regular bank transaction, by definition, requires an identifiable account holder. Even assuming that someone does hack into your account, there's a certain degree of responsibility that the exchange (read: the bank) has when it comes to protecting your investment. Ofcourse, once alt-coins get widespread recognition and there are standards put in place to protect users, this would be applicable to them too but that's exactly my point! With conventional currency, it's impossible for just anyone to setup an exchange without proper security protocols in place to protect users. That's because the creator of the currency (the government in most cases) has the authority over its usage and disbursement. On the other hand, with the decentralized nature of digital currencies, light regulations have led to rampant fraudulent activities. If there's any consolation, all attacks are on the associated services and not the core software and protocol. But to reiterate on my point, it's worth considering whether the large number of unpleasant hesists associated with bitcoins are directly proportional to the design intended to make it decentralized.

Understandably, it's easy to blame this thought on conservative bias. I do wonder however whether research and innovation and their applications are entirely two separate beasts and worth analyzing very carefully with differently colored eyeglasses. With our constant desire to improve our lives, I believe this ideology should be universally applicable. As a different example, let's consider Autonomous Driving too! Advances in Machine Learning is all good but can a machine's logic really replace the empathetic decision making of a human at the time of a crisis ? That's a topic for some other time!

#thoughts #tech #crypto