A Functional Programming ISA

← Jun 24, 2023

I designed a new computer architecture which uses functional programming all the way down to the lowest level. Its assembly language has features like function composition and closures. Then, I made an emulator for it.

Unlike previous attempts to bring functional programming to hardware, this is not a hack on top of x86 (unlike the Lisp Machines and Reduceron), this needs no hardware garbage collection (unlike SECD), and most instructions run in O(1) time.

Here’s a video of it computing Fibonacci numbers,

and here’s a diagram of what the hardware might look like.

About the language

The syntax is similar to lisp but the parentheses are implicit. The sequence + + 1 2 3 really means (+ (+ 1 2) 3) because the + function is known to take two arguments. If statements are also implicit. The sequence true 123 b really means if (true) then goto 123, else b.

In lisp, a plain + is a reference to the addition function, and (+ ... ) applies that function to arguments. in BigFP, this is reversed. + ... applies the function and + e is a reference it.

Before passing anything as an argument to a function, all statements are reduced to a number, boolean, or closure. When a function who wants n arguments takes its first argument, it becomes a closure (with the arguments as environment data) who wants n – 1 arguments.

Example: recursive Factorial(1 + 2)

Lisp-like pseudocode:

(fact (+ 1 2)) halt
(def (fact r0) 
  (if (= r0 n1)
      1
      (* r0 (fact (- r0 1)))))

BigFP Assembly:

f1 8 + n1 e n2 e halt
= r0 e n1 e 25 * r0 e f1 8 - r0 e n1 e e
n1 e e

Result: n6 e halt

Example: basic fibonacci

A list can be represented as a function which returns the first item when given true as its parameter, and returns a “list” (another function) of the other items when given false.

Lisp-like pseudocode:

((((fib 1 2 #f) #f) #f) #t) halt
(def (fib r0 r1 r2)
  (if r2
      (lambda (x) (fib r1 (+ r0 r1) x))
      r0))

BigFP Assembly:

f3 15 n1 e n2 e f e f e f e t e halt
r2 27 f3 15 r1 e + r0 e r1 e e
r0 e e

Result: n5 e halt

Example advanced fibonacci

We can define a function which gets any “list” (another function) and returns the n-th element by repeatedly applying true or false. I’ll remind you this is all easily interpretable by hardware.

Lisp-like pseudocode:

(listGet (lambda (x) (fib 1 1 x)) 5) halt

(define (listGet r0 r1)
  (if (= r1 0)
      (r0 #t)
      (listGet (r0 #f) (- r1 1))))
(def (fib r0 r1 r2)
  (if r2
      (lambda (x) (fib r1 (+ r0 r1) x))
      r0))

BigFP Assembly:

f2 12 f3 34 n1 e n1 e e n5 e halt
= r1 e n0 e 30 f2 12 r0 f e e - r1 e n1 e e 
r0 t e e
r2 46 f3 34 r1 e + r0 e r1 e e
r0 e e

For code like n1 e e, A function could be running and evaluated to return n1 e. The second e signifies the function is over and whatever’s left should be returned. The second e serves a different purpose but never has to be distinguishd from e. It may be given a different name in the future.

Why could this be useful?

Nobody’s gonna remake the entire computing stack because of this silly design, but if you like to imagine, functional programming all the way down would make verifying correctness way easier. You can say things like “factorial(5) always returns 120, no matter what.” It also might lead to stronger parallelization and caching abilities. You may have noticed I snuck in a memoizer in the hardware diagram. Other cores could potentially compute factorial(5) on the side to speed up computation.