Recently I've been playing with LISP and its decendants, Clojure in particular. One of the thing I love about LISP-like programming langugage is its simplicity. Have you ever learn a langugage and when you dont' know what a native functions do, and you just go to the source code to see how they implemented it? I haven't until I tried Clojure.

One of the the thing you'll see a lot if you learn LISP is many of its core feature are implemented in LISP itself. For example you can implement a when case using nested if.

Which mean the compiler itself only implements a set of core methods like :def, defmacro. And most of the functions are implemented using these core functions and macros.

And that make me thinking whether if is one of the core methods? Are there anyway we could implement if using LISP itself?

if is one of the specials instructions where it introduces the ability to branch between block of code. In C we achieve this by using the JUMP instruction from the CPU instruction sets. The instruction sets is the thing that come hard-coded inside your CPU. There is nothing you can do to change the behavior of these instructions.

Let's look at a function that have an if-else clause and its assembly code.

void the_ultimate_question(int n) {
  if (n == 42) {
    printf("The ultimlate answer\n");
  } else {
    printf("Eh?\n");
  }
}

Assembly

the_ultimate_question(int):
        PUSH    rbp
        MOV     rbp, rsp
        SUB     rsp, 16
        MOV     DWORD PTR [rbp-4], edi
        CMP     DWORD PTR [rbp-4], 42  ; (1)
        JNE     .L2                    ; (2)
        MOV     edi, OFFSET FLAT:.LC0  ; (3)
        CALL    puts
        JMP     .L4
.L2:
        MOV     edi, OFFSET FLAT:.LC1
        CALL    puts
.L4:
        NOP
        LEAVE
        RET

The assembly code aboves basically says:

1. Call the CMP (compare) instruction with 2 arguments: DWORD PTR [rbp-4], 42. The result of this comparision will be saved in a register.
2. Call the JNE (jump if not equal) instruction with one argument .L2. This instruction will check if the value from the register that step 1 stored equal to 0. If it's not it'll jump to .L2 and continue execute the instructions after that.
3. Otherwise it'll continue to execute the next instruction, which is MOV edi, OFFSET FLAT:.LC0

So this is how C introduces the ability to branch to our program. And if is one of the basic building blocks that the compiler has to recognize.

Now back to our quest, How can we create an ability to branch using the langugage itself, instead of adding it into the compiler?

One way I found is using Lambda calculus. The trick here is not think of a way to implement if, instead think of how we represent the nature of a TRUE and FALSE.

We've known for a long time that TRUE and FALSE can be presented using just one bit. But it lamda calculus, TRUE and FALSE is actually a function.

(defn true-λ
  [a b]
  a)

(defn false-λ
  [a b]
  b)

Both true-λ and false-λ is a function that takes in 2 arguments. The only different is in which argument it returns. For true-λ it returns the first argument and false-λ will return the second one.

So if we represent true and false as a funciton like this then we can implement if as a dead-simple macro

(defmacro if-λ
  [pred a b]
  `(~pred ~a ~b))

Let's try it

(if-λ true-λ :truthy :falsy)
;; => :truthy

(if-λ false-λ :truthy :falsy)
;; => :falsy

This implementation is not practical by any mean, instead this is just a fun way to explore and understand about lambda calculus - the foundation of recursive programming.

Resources

• https://wolchok.org/posts/how-to-read-assembly-language/