List Processor

A real List Processor would process only with lists. Let's build N using lists and make an instruction set for operating on them.
(define n-zero? (lambda (x) (equal? x '())))
(define n-zero '())

(define n-succ
(lambda (n)
(((lambda (x) (x x))
(lambda (V)
(lambda (A B)
(if (n-zero? A) B (cons (car A) ((V V) (cdr A) B))))))
(cons n n-zero) n)))

(define n-prev
(lambda (n)
(if (n-zero? n) #f
(car n))))

(define n-lt?
(lambda (a b)
(((lambda (x) (x x))
(lambda (V)
(lambda (n m)
(if (n-zero? m) #f
(if (equal? n (car m)) #t
((V V) n (cdr m))))))) a b)))

(define n-gt?
(lambda (a b)
(and (not (equal? a b)) (not (n-lt? a b)))))

(define n-add
(lambda (a b)
(if (n-zero? b) a (n-add (n-succ a) (n-prev b)))))

(define n-sub
(lambda (a b)
(if (n-zero? b) a (n-sub (n-prev a) (n-prev b)))))

(define n-mul
(lambda (a b)
(((lambda (x) (x x))
(lambda (V)
(lambda (t m)
(if (n-zero? t) m ((V V) (n-prev t) (n-add m a))))))
(n-prev b) a)))

(define n-div
(lambda (a b)
(if (n-zero? a) n-zero
(if (n-zero? b) #f
(((lambda (x) (x x))
(lambda (V)
(lambda (t d)
(if (n-lt? d b) t ((V V) (n-succ t) (n-sub d b))))))
n-zero a)))))

(define n-mod
(lambda (a b)
(if (n-zero? b) n-zero
(if (n-zero? b) #f
(n-sub b (n-mul (n-div b a) a))))))

(define n-pow
(lambda (a b)
(((lambda (x) (x x))
(lambda (V)
(lambda (t m)
(if (n-zero? t) m ((V V) (n-prev t) (n-mul m a))))))
(n-prev b) a)))

(define make-stack
(lambda()
(let* ((stk n-zero)
(pop (lambda ()
((lambda (a b)
(begin
(if (n-zero? a) #f (set! stk (cdr a)))
b)) stk (car stk))))
(push (lambda (n) (begin
(set! stk (cons n stk))
n)))
(action (lambda (m)
(if (eq? m 'push) (lambda (n) (push n))
(if (eq? m 'pop) (pop) #f)))))
action)))

(define stack (make-stack))
(define push (lambda (n) ((stack 'push) n)))
(define pop (lambda () (stack 'pop)))

(define dup (lambda () ((lambda (x) (begin (push x) (push x))) (pop))))
(define dup-second (lambda () ((lambda (x y) (begin (push y) (push x) (push y))) (pop) (pop))))
(define swap (lambda () ((lambda (x y) (begin (push y) (push x))) (pop) (pop))))
(define drop (lambda () (pop)))
(define add (lambda () (push ((lambda (a b) (n-add a b)) (pop) (pop)))))
(define sub (lambda () (push ((lambda (a b) (n-sub a b)) (pop) (pop)))))
(define mul (lambda () (push ((lambda (a b) (n-mul a b)) (pop) (pop)))))
(define div (lambda () (push ((lambda (a b) (n-div a b)) (pop) (pop)))))
(define mod (lambda () (push ((lambda (a b) (n-mod a b)) (pop) (pop)))))
(define cmp (lambda () (push ((lambda (a b) (if (equal? a b) (n-succ n-zero) n-zero)) (pop) (pop)))))
(define cmp-lt (lambda () (push ((lambda (a b) (if (n-lt? a b) (n-succ n-zero) n-zero)) (pop) (pop)))))
(define exec-if (lambda (fn) ((lambda (a) (if (equal? a n-zero) #f (fn))) (pop))))
(define write (lambda () ((lambda (a) (begin (display a) (newline))) (pop))))
(define write-peek (lambda () (begin (dup) (write))))

Calculate the first seven fibs:
(define zero n-zero) (define one (n-succ zero)) (define five (n-succ (n-succ (n-succ (n-succ (n-succ zero))))))
(push zero) (write-peek)
(push one) (write-peek)
(dup)
(exec-if
(lambda ()
(((lambda (x) (x x))
(lambda (V)
(lambda (t)
(begin
(push five)
(push t)
(cmp-lt)
(and (exec-if (lambda () (begin
(dup-second)
(dup-second)
(add)
(dup)
(write)
(push one)
(push t)
(add)
((V V) (pop))))) #t))))) zero)))
Result: ()
(())
(())
((()) ())
(((()) ()) (()) ())
(((((()) ()) (()) ()) ((()) ()) (()) ()) (((()) ()) (()) ()) ((()) ()) (()) ())
((((((((()) ()) (()) ()) ((()) ()) (()) ()) (((()) ()) (()) ()) ((()) ()) (()) ()) ((((()) ()) (()) ()) ((()) ()) (()) ()) (((()) ()) (()) ()) ((()) ()) (()) ()) (((((()) ()) (()) ()) ((()) ()) (()) ()) (((()) ()) (()) ()) ((()) ()) (()) ()) ((((()) ()) (()) ()) ((()) ()) (()) ()) (((()) ()) (()) ()) ((()) ()) (()) ()) ((((((()) ()) (()) ()) ((()) ()) (()) ()) (((()) ()) (()) ()) ((()) ()) (()) ()) ((((()) ()) (()) ()) ((()) ()) (()) ()) (((()) ()) (()) ()) ((()) ()) (()) ()) (((((()) ()) (()) ()) ((()) ()) (()) ()) (((()) ()) (()) ()) ((()) ()) (()) ()) ((((()) ()) (()) ()) ((()) ()) (()) ()) (((()) ()) (()) ()) ((()) ()) (()) ())

>>1
Is 'define' a list?

>>3
define is a list of opcodes instructing the environment to register the symbol as a function.
An opcode is a list of bytes that the interpreter evaluates in order to modify the environment.
An enviroment is a list of pairs of symbols and functions.
A pair is a list of two items.
A symbol is a list of characters.
A character is a list of bytes.
A function is a list of opcodes.
An interpreter is a list of bytes that the processor executes.
A byte is a list of eight bits.
A processor is a list of wires and silicon.
A wire is a list of copper atoms.
Silicon is a list of silica atoms.
An atom is a list of subatomic particles.
A subatomic particle is a list of infinitesimal copies of the current universe, for all relevant purposes.
A universe is a list of everything within the universe, including define.

Did I miss anything?

>>2
Did you just use a Y combinator to make an imperative loop? That's some sort of abuse.

>>4

A byte is a list of eight bits.

no

Also, why are you using ZFC's definition of a number? That's O(2ⁿ) space complexity. You could do all operations processing with 0=(); n=(n-1), and it would be O(n).

Why would you use recursion to add two numbers? Is this the hidden power of LISP?

>>6
Teach me why not, using multiple words.

>>9
its a vector of 8 bits

dubs processor

>>1
Yeah, that's really nice. How many years does this take?:

(define two (n-succ (n-succ n-zero)))
(define thirty-two (n-mul two (n-mul two (n-mul two (n-mul two two)))))

(n-pow two thirty-two)

>>7
that's really cool

or you could do it in logn space like it's usually implemented ...

>>9
It's a list of 9 bits.

>>5
I want to look cool on /prog/.

>>7
I'm not, I'm using it backwards. It has several advantages over S(n)=n∪{n} and S(n)={n-1}, but finding those are left as an exercise to the interpreter.

>>8
Why wouldn't you? Do you think Kiketel wastes precious transistors parallelizing addition? Of course not. Addition at the hardware level is all done by a single half-adder looped on itself. That's recursion at it's sloppiest. I've only refined the process. But as a matter of fact, I haven't even done that! How's that for a mind fuck? The addition is done with the successor function, the recursion in the adder is only for looping. But that just means that's it's a recursive definition somewhere else, right?

>>12
I worked it out, and surprisingly, it should take only a few minutes, assuming that the memory access time is constant for all locations.

>>13
How?

>>15
Well all right then. But this still isn't really a processor. You've defined some functions, but you are still relying on the language to do loops and such. It can hardly be called a processor until you have some flow contol instructions.

>>16
Ah, well, I've spent a few days on it, and it proved to be, um, cumbersome. Still completely possible of course! But for now, just treat the Lisp it's embedded in as a macro.