This is a Livecoding Recap – an almost-weekly post about interesting things discovered while livecoding. Usually shorter than 500 words. Often with pictures. Livecoding happens almost every Sunday at 2pm PDT on multiple channels. You should follow My Youtube channel to catch me live.

Think about how a product manager writes code.

They define some features, come up with constraints, and unleash a team of engineers. A few days pass while stuff they don’t understand goes on, and voilà! New features with working code and business metrics twitching to and fro as users respond to new goodies.

Great, huh?

Now think about how a software engineer writes code.

They talk to the product manager and get a “This is what it should do” spec, then they agree on “This is how much it should cost in time/resources to build”. Then the engineer looks at existing code and gets a “This is the code the new stuff should fit into”. Then they come up with a set of tests, automated or otherwise, that answer the question, “Does it work yet?”

With tests in hand, the engineer sets to work. Painstakingly manipulating characters on screen, typing and typing and running and testing and eventually they have code that is syntactically correct and doesn’t break existing stuff and implements the new stuff. Hooray!

Great, huh?… kinda tedious 🤔

Your core value add as an engineer is to help the product manager come up with sensible constraints. To help them include the new stuff into the existing stuff. To suggest constraints they didn’t think of. And to add constraints they shouldn’t have to worry about.

All that code writing stuff… meh.

I know, it’s not just typing. It takes smarts and experience, and it’s really hard to do well. But if you had good tests and infinite memory and infinite time, you could keep generating random strings until one of them happened to make the tests pass. You’d call that string The Code.

Similar idea as the monkeys with typewriters thought experiment and the random sort algorithm. Do random stuff until requirements are met.

Expected running time: Infinity.

Because you’re smart and experienced and a grizzled veteran or an eager newbie, it takes you less than infinity to write that code. You use smart heuristics like “not typing random stuff” and “actually thinking about what to do”.

Although I often just keep trying random things when things get really tough. 😇

Wouldn’t it be cool if someone could do that for you? I mean, if computers can write news, why not the code that makes computers write news?

Here’s the idea: You write the tests, AI makes them pass.

Experiment 1 – failed

I’m calling this first experiment “faux AI” because it doesn’t know what it’s doing. The current approach is at the “Paste random characters and fingers crossed” stage.

We tried an evolutionary algorithm based on manipulating code as character strings. This did not work.

Our population kept getting stuck at a maximum far away from the result. Once every member of the population had the same fitness score, they stopped changing and a solution was never reached.

The situation improved once we tweaked our fitness function and added constraint weights. Instead of having a series of true/false conditions, we weighted them by importance.

// We aim to maximize this value
function fitness(code, conditions) {
    const max = conditions.reduce((sum, { condition, weight }) => sum + weight,
                                  0),
          fit = conditions.map(({ condition, weight }) => Number(condition(code))*weight)
                          .reduce((sum, fit) => sum + fit,
                                  0);
 
    return fit/max;
}
 
const Conditions = [
    {
        condition: code => !(run(code) instanceof Error),
        weight: 10
    },
    {
        condition: code => run(code) === 4,
        weight: 8
    },
    {
        condition: code => code !== "4",
        weight: 2
    },
    {
        condition: code => code !== 4,
        weight: 2
    },
    {
        condition: code => code.length > 4 ? 4/code.length : 1,
        weight: 6
    }
];

The fitness function takes a piece of code and walks through a set of conditions. We test each condition and multiply the result with its weight. A syntactically valid piece of code gets 10, an invalid one gets 0. One that produces the correct result gets8, an invalid result gets 0, etc.

We’re looking for code that is shorter than 4 characters, isn’t 4 or "4", and returns 4. A good solution would be, say, 2+2, or 1+3. Even a = 4 works. Or maybe "afwaelfjlkwefj"; 4.

The tricky part of evolutionary algorithms is that even when they work, their results are weird. Best things in the world at finding loopholes in your conditions.

Our evolutionary algorithm looks like this:

function* generation({ population, fitness, N }) {
    while (true) {
        population = rank(population, fitness);
 
        // pairwise breed top 50% of population
        population = population.concat(
            breedPairs(_.chunk(_.take(population,
                                 population.length/2),
                          2)
            ));
 
        population = rank(population, fitness);
 
        population = _.take(population, BIGGEST_POPULATION);
 
        yield {
            fitness: fitness(population[0], Conditions),
            code: population[0],
            fitnessLast: fitness(population[population.length-1], Conditions),
            codeLast: population[population.length-1],
            size: population.length
        };
    }
}

That’s a generator, by the way. Call .next() to get the next generation from the current population. Call it as many times as you want; it keeps working 🙂

Each generation starts with an existing population, which is ranked by the fitness function. We make pairs out of the best 50% of the specimens, breed them, and add their offspring to the population.

The new population is again ranked, and if there’s more specimen than we have room for, the bottom few are thrown away. They’re useless.

You can see how the breedPairs and rank functions work on Github.

This current approach did not produce a single working piece of code. This was the best solution with a score of 0.5535714285714286

" pci  s |ePke "

At least it’s syntactically valid 🤔

This field of research is known as genetic programming. I don’t think anyone has gotten it to the point of replacing software engineers yet, but I remember a cool project from my high school days by some Slovenian person called Critticall. It was able to invent novel sorting algorithms.

Next steps

The experiment failed, and the code is slow.

Maybe we should switch to Python? Or parallelize the generation generator. Evolution is, after all, highly parallelizable and there are 4 cores in my computer…

Fundamentally, we’re gonna have to change the level of abstraction. You cannot evolve code as if it was a random series of characters. Maybe if our algorithm could understand syntax, or at least JavaScript symbols, and evolve an AST, then it might work.

I think there’s also room for neural nets and deep learning in the evolution step. 🤔

Ideas very welcome. I will continue to dabble with this as time allows.

Learned something new? 💌

Join 8,400+ people becoming better Frontend Engineers!

Here's the deal: leave your email and I'll send you an Interactive ES6 Cheatsheet 📖 right away.  After that you'll get an email once a week with my writings about React, JavaScript,  and life as an engineer.


You should follow me on twitter, here.