Hacker News Reader

Comment by vocram | Hacker News Reader

Yet another proof that C is simple but not easy.

The simplest languages tend to be the most difficult. Brainfuck, Binary Lambda Calculus, Unlambda, and other "Turing tarpits" are all extremely difficult to use for anything even mildly complex.

Forth. It’s easy for a small cute script. But quickly becomes a PITA.

Stack machines look cool until you realize you could save all the stack mumbling by using registers. At this point, you could try to make a full VM instead.

I always felt like unlambda and other SKI calculus esque esolangs(iota comes to mind) could have some kinda strange use case in some kind of generalised genetic programming. It should be possible to create a binary notation for SKI calculus where arbitrary bitstrings will be valid, and so one could randomly mutate and recombine arbitrary programs. Though I've never delved deeper into genetic algorithms and evolutionary programming, my sense is that genetic algorithms tend to be restricted to parameterised algorithms where the "genes" determine the various parameters. Which can be great for optimisation problems.

It's one of those weird ideas I've had kicking about for years but never did anything about, and yet I keep coming back to it.

This must be an avenue for very exciting explorations. I'm quite ignorant about this stuff but have some questions :

  > It should be possible to create a binary notation for SKI calculus where arbitrary bitstrings will be valid

What if it's not ? How will your genetic petri dish spot and eliminate invalid programs ?

  > one could randomly mutate and recombine arbitrary programs

What if non-halting programs get generated ?

In this vein I've seen magnificent images of 1D cellular automatons that use the surrounding pattern to decide on the local rule for next gen.

I assume that an invalid program would not compile/parse, and so would die and fail to reproduce. The issue is more that if the space of invalid programs is too large compared to the space of valid ones, generating valid offspring by combining two programs would be too rare and the population would die off.

Though if the space is small enough I imagine you could get past that. It's a bit of a gnarly point, hard to tell how this would turn out without trying I suppose.

As for the halting problem there's of course no clever solution there other than limiting CPU time. So I guess pick a reasonable limit that makes sense for whatever you're trying to do.

Reply on news.ycombinator.com