Friday, January 21, 2011

Evolving a computer with TECS and Genprog

I've started reading The Elements of Computer Systems since it was recommended on Reddit and it's a great read. After the section on boolean gates I decided to have a quick go at build the gates in Haskell. Just implement Nand with pattern matching, and implement all the other gates just in term of functions calls to previously defined gates. The book mentioned "think positive" about implementing Not, so I just T as the second parameter, did't think more about it, even though I wasn't sure having a constant value was OK.



Then I moved on to the other gates. It was interesting to think about boolean logic without Or, for example, after years of only reasoning in terms of And Or and Not. But at some stage I thought "why am I doing this by hand?". I remembered a thread about a new genetic programming library on an Haskell group. Surely generating the gates would be simple enough?
So I got genprog from hackage, and adapted the example for my needs. I started with a very simple system to determine the implementation of Not:



And of course, the result came quickly enough: not a=nand(a,a). No need for a Const at all! Evolution has beaten me! (OK, I'm only a not-so-intelligent designer, I suppose...)
Now, I'm going to see if this approach can take me all the way to the arithmetic unit...

3 comments:

Bryan said...

It seems both work:

not a = nand (a,a)
nand (F,F) = T -- not F
nand (T,T) = F -- not T

not a = nand (a,T)
nand (F,T) = T -- not F
nand (T,T) = F -- not T

It works because in the truth table for nand:
a b NAND
F F T *
F T T *
T F T
T T F
Both starred methods work to get not F.

JP Moresmau said...

Oh I know that both works, I had tested my version before I started genprog, I was just amused that genprog found a version arguably simpler than mine (no need for constant expressions).

Dan Turner said...

I think that trying to evolve a whole ALU straight off the bat is a little excessive.

How about a half adder, and then a full adder?

If my memory serves me correctly, a half adder does need Not, And, and Or, so it'd have to evolve those before it could get any further in the same way that a human would, or it might evolve it straight away. I'd be interested in the results.

Haskell is a decent choice. Once you've got your understanding of hardware down, Haskell's pattern matching and abstract data types make producing assemblers, interpreters and compilers rather easy as compared to some other languages.

Best of luck!