Erlush evolves its first non-trivial program!

November 4, 2009
by John Schanck (jms07)

It computes factorial. Here it is:

[{exec,pop}, [[[{exec,do_star_times},{integer,yank}],[[-9,{integer,yankdup}]]], [{boolean,stackdepth}, [[{integer,flush},{exec,b},{exec,k}], {exec,y}, [[[[{boolean,rot},{exec,do_star_times}]]], {integer,divide}, {integer,yank}]], [[[[{exec,do_star_count},{integer,lessthan}]]]]]], {integer,equal}, [{exec,do_star_times}, [[{exec,s},{exec,do_star_times}],[{integer,max},{boolean,yankdup}],{exec,c}], {exec,k}, {integer,multiply}]]

And the same program after simplification (by hand):

[{exec,do_star_times}, [[{exec,do_star_times}],{exec,c},[[],{exec,c}]], {exec,k}, {integer,multiply}]

And again in nicer, lispy, Push3 syntax

(EXEC.DO*TIMES ((EXEC.DO*TIMES) EXEC.C (() EXEC.C)) EXEC.K INTEGER.*)

I was pretty excited to see C combinators in there, perhaps they’re a worthwhile addition to the language.. No worries if you can’t figure out what’s going on here, I’ve single stepped through it with Erlush in debugger mode and still can’t say for sure that I know how it works. I did, however, discover that it’s exploiting a bug in my implementation of EXEC.DO*TIMES — which is discouraging and exciting at the same time.

More to come.

John

UPDATE: I fixed the EXEC.DO*TIMES bug and reran the factorial evolver, and got (after simplification and Push3ifying)

(EXEC.STACKDEPTH INTEGER.DUP INTEGER./ EXEC.DO*RANGE INTEGER.*)

Which is much clearer. The first three instructions just put a 1 on the stack on top of input and then EXEC.DO*RANGE INTEGER.* iterates from the input value down to 1 multiplying the loop counter and the value beneath it each time.



Leave a Reply

You must be logged in to post a comment.