Computing as Mere Rewritting

I've been studying functional programming lately, and it's really changed my whole conception of what computing is. The standard concept of computing is: Info is stored in memory.

(To elaborate on that: You pull that memory out when you want it, do some function on it, put the result somewhere in memory again. So for instance x = 1+(2*3) is thought of as 1, 2, and 3 as being info somewhere in memory. You do * to 2 and 3, get 6. Then do + to 1 and 6, get 7. Then store that 7 in an address in memory which we reference as x.)

But functional computing doesn't have memory! All of functional programming can be thought of as *rewriting*. The function 1+(2*3) is just regarded as an expression that we can rewrite as 1+6 and then rewrite that as 7.

But computers need to be able to interact, right? If you click here, the computer does this. If you click there the computer does something else. How do you get this behavior with just rewriting? It turns out it's possible! You just need a conditional function. We could write it as

`cond click1 doBrowser doGame`

where the computer is told that if you find the pattern `cond click1 ...` then do the first thing. That way `cond click1 doBrowser doGame` gets rewritten as `doBrowser` and the browser function runs. To get the other behavior you write

`cond click2 doBrowser doGame`

and the computer has another rule which says, if you find the pattern `cond click2 ...` it'll rewrite to the second thing, in this case, it rewrites to `doGame` and now you're playing a computer game.

And in general, everything computable can be done with rewriting rules! I think that's wild. You can even re-create the behavior of having memory, by using this memory-less structure!