Axiom Tutoring

Advanced Math, Stats, Logic, Physics, CompSci, and test-prep tutoring

Professional tutoring service offering individualized, private instruction for high school and college students.  Well qualified and experienced professional with an advanced degree from Columbia University.  Advanced/college mathematics, logic, philosophy, test prep, microeconomics, computer science and more.

Filtering by Tag: functional programming

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!


I've lately been learning to program in OCaml.  Having some familiarity with Haskell I'll say that, as of now, it's hardly distinguishable from Haskell to me.  Perhaps I'll change my tune in a few weeks of playing with it.  For now, though, they both seem like functional languages that incorporate object-oriented functionality, they strongly depend on recursion and pattern-matching, and both are largely seen as educational play-things rather than industrial-strength languages. 

Well, there's that stereotypical grumbling over nothing that all techy people do.  On the bright side, using OCaml is fun, and I hope to exercise and tighten my familiarity with Recursion Theory through its use. 

I'm also simultaneously getting through Hopcroft's Automata book, and that's more confusing.  The exact nature of the physical systems that he (they?) model with graphs is not transparent.  Perhaps I'm being a little too tedious in trying to match things up.