DEV Community: sayedhajaj

Thoughts On Types

sayedhajaj — Mon, 30 Aug 2021 11:10:50 +0000

This article was initially published on my website.

Introduction

I've used multiple programming languages, each with their own ideas of how types should be handled.

Each of these approaches created some issues and solved other issues, and my goal in this article is to describe these pros and cons. Rather than describe them in a list format, I will try to examine what we do as programmers and how various approaches to handling types can help or hinder this.

I'm writing my own programming language. I'll announce it here later. One of my goals with it is to analyse what I do in practise, and add in what I feel is missing. The thoughts I've expressed in this article have gone into my own programming language.

Every program has types, whether you write them or not

If you pause the execution of a program whilst it's executing an expression, each expression will have a type. There will be valid things you can do to it and things you can't. If an expression evaluates to an integer, you can use it for arithmetic operations you could not perform on strings.

You might think then that using static types is redundant in this case, but actually this makes it all the more valuable. It means that whether or not you're specifying types, you need to think about them to ensure that your program does not crash.

If your compiler does not enforce this, then you will need to be extra vigilant to avoid run-time errors.

Whenever you deal with a variable, you have to read the implementation and usage to make sure you are treating it in a valid way.

By having static types, your IDE or editor can notify you if you are writing invalid code. Static types are also a good form of documentation, because the compiler makes sure it is consistent with your program.

Data structures make algorithms obvious

If you have an array you will probably have a loop.
If you have a tree you will probably have a recursive function.
For any data structure, there are more and less natural ways for processing that data structure.

The first implication of this is that it's important for a programming language to make it easy to define different kinds of data structure.

The second implication is that clearly communicating the data structure makes it easier to write the code to process it.

If you can clearly see that a variable is an array, then you have a good idea of what kind of code you will write next.

If you don't, and instead have to read implementation code from multiple files, then you will have a harder time figuring out what you should do with the variable.

Some static types have a lot of boilerplate

Java is, or was, a good example of this. A lot of Java code looks like this:

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

The compiler and IDE can easily tell that the variable refers to a BufferedReader instance from the fact that it instantiates a BufferedReader. There's no need to repeat that information.

Some statically typed languages have type inference. This allows you to write something like this:

val reader = BufferedReader(InputStreamReader(Sytem::in))

(This is Kotlin).

If you want to, you can still provide type annotations. The compiler still makes sure every variable and expression has a type and that only valid operations are called on the associated types.

Many typed programming languages disallow programs that won't crash

Will this program crash:

var item = "foo"
print(item)
item = 4
print(item * 2) // assume print converts automatically to string

No, it won't crash. By the time you multiply the variable by 2, the value contained in it is an integer so it is a valid operation. But many statically typed languages won't let this compile.

Programmers who are used to dynamic types feel that valid useful options for writing a program are closed off for no good reason in statically typed languages.

The way some statically typed languages have gotten around this is by having more flexible type systems, capable of representing more valid programs.

For example, this can be dealt with by using union types:

var item: String | Int = "foo"
// now the compiler will tell you to check it is an integer before multiplying it.

Powerful typed programs have issues

Javascript is a very dynamic language. It's common for javascript users to iterate through all of the fields in an object to create a new one. In order to represent that in a typed programming langauge such as TypeScript, you often need to have a powerful type system.
As a result, the type system in TypeScript is Turing complete. This is also the case for a few other languages.

In TypeScript, for example, you can use the type system to make sure that a number is prime.

This is cool, although it has problems. That means that you cannot tell ahead of time if type checking will complete (the halting problem).

In my opinion, this just pushes the problem developers deal with back a step.

Instead of being able to glance at the type declaration and understand how you should write your program, you now need to act like a computer and follow along.

A smellier alternative

What if you could tell your compiler that in this particular instance, you know better?

You could stick to using simple type system features, and force the language to do what you think will work in certain circumstances. For example, in Kotlin and typescript you can assert that a type is not null, or force a cast.

This is generally considered a bad practise, and should be used sparingly, but it can be useful.

Maybe optional typing?

What if invalid types generated warnings rather than errors, so you can still deal with them but you don't have to make your programs awkward in areas that aren't amenable to static types?

I think this is helpful for transitioning from dynamic types, and still provides some of the benefits of static typing.

Related rant on null

The Java type system is lying to you. Every variable could be referring to null. Tony Hoare referred to this as his billion dollar mistake.
As a result of this mistake, variables in Java often need null checks before they're used. One of the most common causes of runtime exceptions in Java is null pointer exceptions.

As a result of this, people have all the extra work associated with static types, but they don't really get all of the benefits since they have to check if every variable really is the type it says it is manually.

One of the ways to get round this is non-nullable types. This way null cannot be assigned to most variables by default, unless is null is specified as a valid option. If it is then the compiler requires null checks.
This can also be achieved with union types.

Engineers and tradeoffs

So it looks like each avenue presents some issues. Some avenues try to get the best of both worlds, but nothing seems to be capable of avoiding all issues.

So then the question is, what to pick and when.
I think it depends on the kind of project.

In a large project where you are working with multiple people, I think a slightly flexible statically typed language is the best option. This makes sure that everyone is on the same page regarding what every function expects, reduces runtime errors and cognitive load for developers.

Whilst it might be tempting to go for something less stringent, I think it's ultimately not a good idea for a large project that's expected to last and work.

Announcing Drawlang

sayedhajaj — Sun, 29 Dec 2019 20:17:39 +0000

This article was originally posted on my website

I'm officially releasing, and open-sourcing, Draw: a programming language and environment for graphics.

Motivation
How it started
Overview
Design Decisions
Examples
- Modern Art
- Chessboard
- Asteroids
- Magic Real Estate
- Spritesheets
A peek under the hood
Current issues
Missing features
Potential applications
What about alternatives?

Motivation

I like developing games. That means I have to work with graphics. Not just for creating the players, backgrounds, and buttons, etc, but also for putting graphics in a consistent format that is convenient to load programmatically.

For example, converting from this:

to something like this:

That way I don't have to hardcode the position of each frame within the game and can easily switch between them or replace the animation.

Whilst cheap assets are available online, they aren't always available or easy to find. Or cheap. And whilst there are people who can make good graphics, that can take time and you need something whilst you develop the game - programmer art.

There are two main ways I have approached creating and modifying graphics.

The first is by opening up Microsoft Paint and a lot of trial and error. This often involves a lot of repetition. To make something that can be loaded programmatically requires a lot of precision.

The second way is with code.

Java Swing, JavaFX, and HTML5 JavaScript all have a similar canvas API.

With Javascript I enter this code into the console on any browser tab.

document.body.innerHTML=''; // clear page
let canvas = document.createElement('canvas');
canvas.width = 640;
canvas.height = 480;
document.body.appendChild(canvas);
let ctx = canvas.getContext("2d");
// use context here to render to canvas

And then, after programmatically rendering whatever it is I want on the canvas, I right-click on it and save the result.

This worked fine if I wanted to create something like a chessboard, but it became messy when I tried to work with images and some features required running the code on a server.

Because many of the games I made used Java (most of my earlier games used Java Swing), I would sometimes use that to get around some of these problems. I would write some code on startup to load an image, do some processing, and save it in another file. Then I would compile and execute it, and look at the final image to see if it was the result that I wanted.

Not only did this require a lot of boilerplate, but it had a longer feedback loop, and requiring me writing, saving, and executing code that I only used once.

If only there was a way for me to use code to create graphics, with minimal boilerplate, without even having to save the code, and to see the output immediately.

Enter Draw.

How it started

For a school computing project, I wanted to make an evolutionary tower defence game, when I realised that I would really like to have the aforementioned graphics language and environment to design the graphics in the game. So I decided to go with that instead.

Fortunately Robert Nystrom (also known as munificent) had posted some chapters for his online book Crafting Interpreters. (Check his stuff out, it's really interesting. He also wrote the book Game Programming patters).

In this online book, he teaches how to make a programming language. He designed one called Lox, and made two implementations of it. The first implementation, fortunately for me, was in Java. And the second one is in C. At the time of writing, he is about 75% of the way through the second book. When I started this project, he was around 40% of the way into the first book.

The first implementation is what is known as a Tree Walk Interpreter. This is one of the easiest ways to implement a programming language, but it is less efficient. The implementation is of a virtual machine bytecode interpreter.

The first implementation was good enough for my purposes since I only intented to write small scripts, performance was not a very high priority. Also, since it was written in Java, it is easier to integrate with JavaFX, a popular Java GUI library that includes canvas.

So I followed his tutorial, did his exercises, added some more features, made some other changes. And then I implemented the GUI.

Whilst it is not very advanced yet, I have already found it very useful.

Overview

The Lox language is syntactically similar to Javascript since it is dynamically typed and uses curly brackets, but it is more semantically similar.

For simplicity, Draw mostly follows Lox.

// variable declaration
var message = "hello"; // only double quotes currently supported
var example; // can also be declared without value

// if statements
var age = 17;
if (age >= 18) {
    // perform action
} else if (age == 16) {
    // perform alternate action
} else {
    // perform some other action
}

// while statements
var index = 0;
while (index < 10) {
    index++;
    // perform action
}

// for statements
for (var i = 0; i < 10; i++) {
    // perform action
}

// functions
function factorial(num) {
    return num <= 1 ? 1 : num * factorial(num-1);
}

// anonymous functions
var printHello = function(name) {
    println("hello " + name);
    // no string templates yet
    // println prints to a new line, like Java's System.out.println
}
printHello("world");

// closures

// object oriented programming
class Square {
    // constructor
    init(length) {
        // fields
        this.length = length;
    }

    // methods
    area() {
        return this.length ** 2;
    }

    perimeter() {
        return 4 * this.length;
    }

    static numSides() {
        return 4;
    }
}

var smallSquare = Square(3);
println(smallSquare.area());
println(Square.numSides);

// inheritance
class Parent {
    speak() {
        println("Hello World!");
    }
}

class Child extends Parent {

}

Child().speak() // Hello World!

In the program, I have a help/welcome page that goes through the standard library and syntax, it also provides some tutorials.

Design decisions

Context methods moved into canvas

In JavaFX, Java Swing, and HTML5 canvas, you don't render directly to the canvas. You have to obtain a graphics context from a canvas and render to that.

I've always thought that using a graphics context ruined a good metaphor. In real life, we draw on canvases, not contexts. Whilst graphics context is useful for 3D rendering, that is not something I expect to support in Draw.

So I "got rid of the middle man". Under the hood, I still use context, but the user will just render to the canvas.

Syntax similar to Lox with some additional features

Some things have been changed to be more like javascript, e.g function instead of fun. This is intended to reduce the learning curve, make it easy to port to and from javascript, and seem more familiar.

Print is a function rather than a statement

I have also added a ternary operator:

println(2*3 < 5 ? "foo" : "bar"); // expect bar

array literals:

var lst = [3, 4, 5, 2, 1];
println(lst[0]); // expect 3
println(
    lst.map(
        function(item) {
            return item * 2;
        }
    )
); // expect [6, 8, 10, 4, 2]

break and continue statements, multi-line comments (also supported nested comments), and do while statements, prefix and postfix unary increment and decrement:

var a = 3;
a++; // a = 4
--a; // a = 3

multiple short hand assignment operators:

var number = 10;
number += 3; //add 3 to number
number %= 2; //same as number = number % 2
number **=3; //cube number
// also -=, /=, *=

and a few data structures such as Array lists, Hashmaps, Strings, and Characters.

In addition to this, I have implemented a canvas object, a colour object, an image object, and a Math API.

Examples

Modern Art

var canvas = getCanvas();

for (var i = 0; i < 1000; i++) {
    var r = Math.random() * 255;
    var g = Math.random() * 255;
    var b = Math.random() * 255;
    canvas.setColor(Color(r, g, b, 255));

    var x = Math.random() * 500;
    var y= Math.random() * 400;
    var w= Math.random() * 100;
    var h = Math.random() * 100;
    canvas.fillRect(x, y, w, h);
}

Chessboard

var canvas = getCanvas();
var black = Color(0, 0, 0, 255);
var white = Color(255, 255, 255, 255);
var size = 45;

for (var row = 0; row < 8; row++) {
    for (var col = 0; col < 8; col++) {
        var tile = (row+col) % 2 == 0 ? black : white;
        canvas.setColor(tile);
        canvas.fillRect(col*size, row*size, size, size);
    }
}

Asteroids

For my game Deluge, I wanted to add asteroids as obstacles. I also wanted to release my game soon, so I didn't want to wait for someone else to make it for me before releasing.

So I whipped up Draw and decided to try myself.

My initial thought is that an asteroid is sort of like a bumpier circle. A circle could be thought of as a bunch of points equally far from one point.

var canvas = getCanvas(); // get the main canvas in current tab
var centreX = 200;
var centreY = 200;
var distance = 50;

for (var angle = 0; angle < 360; angle++) {
    var x = centreX + Math.sin(Math.toRadians(angle)) * distance;
    var y = centreY + Math.cos(Math.toRadians(angle)) * distance;
    canvas.fillRect(x, y, 1, 1);
}

This resulted in a blurry circle, and wasn't quite what I had in mind when I said that an asteroid was like a bumpy circle. Instead of filling one pixel 360 times, I draw lines between each point. This makes it easier to modify into an asteroid - by changing the distance of the points.

To do this, instead of using filling 1-pixel rectangles, I will draw a path, using the canvas API.

I position the first point, and add lines between the points.

var canvas = getCanvas();
var centreX = 200;
var centreY = 200;
var distance = 50;

canvas.beginPath();
canvas.moveTo(centreX, centreY + distance);
for (var angle = 0; angle < 360; angle++) {
    var x = centreX + Math.sin(Math.toRadians(angle)) * distance;
    var y = centreY + Math.cos(Math.toRadians(angle)) * distance;
    canvas.lineTo(x, y);
}
canvas.drawPath();

To make it less round, and more asteroid like, I will vary the distance of the points from the centre, but also keep them within a certain range.

var canvas = getCanvas();

function randomInRange(min, max) {
    return min + Math.random() * (max-min);
}


var centreX = 200;
var centreY = 200;
var minDistance = 40;
var maxDistance = 60;
var distance = randomInRange(40, 60);

canvas.beginPath();
canvas.moveTo(centreX, centreY + 50);
for (var angle = 0; angle < 360; angle++) {
    distance = randomInRange(40, 60);
    var x = centreX + Math.sin(Math.toRadians(angle)) * distance;
    var y = centreY + Math.cos(Math.toRadians(angle)) * distance;
    canvas.lineTo(x, y);
}
canvas.drawPath();

This produces a very jagged asteroid. To make it smoother, I will vary the angles from the centre, so that the lines are further apart. Because the distances from the centre have changed, I will need to close the path at the end so that the canvas automatically joins the last point to the first one.

var canvas = getCanvas();

function randomInRange(min, max) {
    return min + Math.random() * (max-min);
}

var centreX = 200;
var centreY = 200;
var minDistance = 40;
var maxDistance = 60;
var distance = 50;

canvas.beginPath();
canvas.moveTo(centreX, centreY + 50);

for(var angle = 0; angle < 360; angle += randomInRange(15, 25)) {
    var x = centreX + Math.sin(Math.toRadians(angle)) * distance;
    var y = centreY + Math.cos(Math.toRadians(angle)) * distance;
    canvas.lineTo(x, y);
    distance = randomInRange(40, 60);
}

canvas.closePath();
canvas.drawPath();

To add a finishing touch, I will make the outline thicker, and fill the asteroid with a dark brown colour.

var canvas = getCanvas();

function randomInRange(min, max) {
    return min + Math.random() * (max-min);
}

var centreX = 200;
var centreY = 200;
var minDistance = 40;
var maxDistance = 60;
var distance = 50;

canvas.setColor(Color(90, 10, 40, 255));
canvas.setLineWidth(5);
canvas.beginPath();
canvas.moveTo(centreX, centreY + 50);

for(var angle = 0; angle < 360; angle += randomInRange(15, 25)) {
    var x = centreX + Math.sin(Math.toRadians(angle)) * distance;
    var y = centreY + Math.cos(Math.toRadians(angle)) * distance;
    canvas.lineTo(x, y);
    distance = randomInRange(40, 60);
}

canvas.closePath();
canvas.fillPath();
canvas.setColor(Color(0, 0, 0, 255));
canvas.drawPath();

For some time, I have used this in my game:

until the graphic designer made this:

Magic Real Estate

For Ludum Dare, I made Magic Real Estate.
I initially started with rectangles. Then I spent some time making graphics for the players using Draw. The code is not great to look at, but it beat trying to draw by hand.

By changing a few lines, I was able to draw both wizards.

This was the final result:

The difference was two lines of code.

var canvas = getCanvas();

/*
I started with the hat, this is just a triangle, uncommenting the next line
makes it red rather than blue, for the other wizard
*/
canvas.setColor(Color(70, 50, 180, 255));
//canvas.setColor(Color(255, 0, 0, 255));
canvas.beginPath();
canvas.moveTo(100, 100);
canvas.lineTo(150, 0);
canvas.lineTo(200, 100);
canvas.fillPath();

/*
Then I moved on to the clothes, also a triangle
*/
canvas.beginPath();
canvas.moveTo(120, 150);
canvas.lineTo(180, 150);
canvas.lineTo(230, 270);
canvas.lineTo(70, 270);
canvas.fillPath();
canvas.setLineWidth(30); // arms are thick lines
canvas.drawLine(120, 150, 60, 200);
canvas.drawLine(180, 150, 250, 200);

/*
next was the face
This was a quadratic curve between two points
*/
canvas.setColor(Color(240, 220, 160, 255));

canvas.beginPath();
canvas.moveTo(100, 100);
canvas.quadraticCurveTo(150, 250, 200, 100);
canvas.fillPath();


/*
The outline of the beard is also a quadratic curve but not a filled one

*/
canvas.setLineWidth(5);
canvas.setColor(Color(200, 210, 200, 255));
canvas.beginPath();
canvas.moveTo(105, 105);
canvas.quadraticCurveTo(150, 250, 195, 105);
canvas.drawPath();

/*
The goatee included two curves, one filled and the other outlined,
with different thicknesses
*/
canvas.beginPath();
canvas.moveTo(122, 152);
canvas.quadraticCurveTo(150, 250, 180, 152);
canvas.fillPath();
canvas.setLineWidth(10);
canvas.beginPath();
canvas.moveTo(130, 152);
canvas.quadraticCurveTo(150, 120, 170, 152);
canvas.drawPath();


/*
Next was the hair and eye lashes, just lines
*/
canvas.drawLine(105, 105, 100, 200);
canvas.drawLine(195, 105, 200, 200);
canvas.setLineWidth(7);
canvas.drawLine(120, 110, 130, 106);
canvas.drawLine(170, 106, 180, 110);


// eyes - just black circles
canvas.setColor(Color(0, 0, 0, 255));
canvas.fillCircle(130, 120, 13);
canvas.fillCircle(170, 120, 13);


/*
and finally the staff, uncommenting the next line makes it black
*/
canvas.setColor(Color(255, 215, 0, 255));
canvas.setLineWidth(20);
canvas.drawLine(50, 20, 50, 250);

I recommend writing this code block by block. Whilst this is not the best way to make such graphics (too many magic numbers and constants), using Draw made me finish this much faster than trying to do it without code, because I was able to trial and error many changes and get feedback quickly, and able to achieve a level of precision that I rarely get elsewhere.

Spritesheets

Starting with this:

I was able to produce this:

with this code:

var canvas = getCanvas();
var dir = "insert_directory_here";
var spritesheet = loadImage(dir);

for (var row = 0; row < 4; row++) {
    for (var col = 0; col < 4; col++) {
        var frame = spritesheet.getSubimage(col*50, 20+row*100,  40, 80);
        // set pink colour to transparent
        frame = frame.setTransparentColor(Color(255, 0, 255, 255));
        canvas.drawImage(frame, col*40, row*80);
    }
}

// saveImage(canvas.toImage(), "outputdirectory") would have saved it, I right clicked
// on the canvas to save

A peek under the hood

There are two make packages in this project, for the interpreter and for the GUI.

The GUI contains basic editor code: keyboard shortcuts, file and line search, file opening and saving.

Because JavaFx can use CSS, it also has themes - but they don't look very good right now, so I stick with the default theme most of the time.

The GUI also contains support for two kinds of tabs: "draw tabs" and "help tabs". Each draw tab is bound to the interpreter. A draw tab contains a text section for the code, a console, a canvas, and a run button. When the run button is pressed, the code in the text area is interpreted, and when getCanvas() is called, the canvas in the current tab is returned. println and print also logs to the current console.

The interpeter package is responsible for executing the code. First lexical analysis takes place in "Scanner.java". The output is a list of tokens. Then an abstract syntax tree is created, this happens in "Parser.java". Then semantic analysis takes place in "Resolver.java". And finally the abstract syntax tree is traversed and executed in "Interpreter.java".

It is in "Interpreter.java" where all the global functions are defined.

They all implement DrawCallable.

This is the code for the println function:

globals.define("println", new DrawCallable() {
    @Override
    public int arity() {
        return 1;
    }

    @Override
    public Object call(Interpreter interpreter, List<Object> arguments) {
        Main.getConsole().println(stringify(arguments.get(0)));
        return null;
    }
});

This is the code for the clock function:

globals.define("clock", new DrawCallable() {
    @Override
    public int arity() {
        return 0;
    }

    @Override
    public Object call(Interpreter interpreter, List<Object> arguments) {
        return (double)System.currentTimeMillis();
    }
});

Library classes extend LoxInstance. And the DrawMath class extends DrawClass because it is static.

Here is one of the simplest library classes, Color:

package com.drawlang.drawinterpreter;

import javafx.scene.paint.*;

public class DrawColor extends DrawInstance {

    public Color color;

    DrawColor(Color color) {
        super(null);
        this.color = color; 
    }

    @Override
    Object get(Token name) {
        switch (name.lexeme) {
            case "r": return color.getRed()*255;
            case "g": return color.getGreen()*255;
            case "b": return color.getBlue()*255;
            case "a": return color.getOpacity()*255;

            default:
                throw new RuntimeError(name, "Undefined property '" + name.lexeme + "'.");
        }
    }

}

To obtain an instance of a color within the Drawlang code, I defined a global function that looks like a constructor in "Interpreter.java"

globals.define("Color", new DrawCallable() {
    @Override
    public int arity() {
        return 4;
    }

    @Override
    public Object call(Interpreter interpreter, List<Object> arguments) {
        return new DrawColor( new Color(
            (double)arguments.get(0)/255f, (double) arguments.get(1)/255f, 
            (double) arguments.get(2)/255f, (double) arguments.get(3)/255f
            ));
    }
});

In addition to getting fields, children of DrawInstance can also support setting fields.

Current issues

Continue statement in for loop causes infinte loop. For statements are "desugared into while statements" in the parsing stage.

This

for (var i = 0; i < 5; i++) {
    // do stuff
}

becomes:

{
    var i = 0;
    while (i < 5) {
        // do stuff
        i++
    }

This is the parser code for handling for statements:

private Stmt forStatement() {
    consume(LEFT_PAREN, "Expect '(' after 'for'.");

    // checks the initializer, e.g for('var i = 0') or for('i = 0')
    // this also allows for no initializer - e.g for(;)
    Stmt initializer;
    if (match(SEMICOLON)) {
        initializer = null;
    } else if (match(VAR)) {
        initializer = varDeclaration();
    } else {
        initializer = expressionStatement();
    }

    // checks for a condition - for(var i = 0; 'i < 5')
    Expr condition = null;
    if (!check(SEMICOLON)) {
        condition = expression();
    }
    consume(SEMICOLON, "Expect ';' after loop condition.");

    // check for incrementer expression - for(var i = 0; i < 5; 'i = i + 1')
    Expr increment = null;
    if (!check(RIGHT_PAREN)) {
        increment = expression();
    }
    consume(RIGHT_PAREN, "Expect ')' after for clauses.");
    loops++;
    Stmt body = statement();

    // if there is an incrementer add it to the end of the body
    if (increment != null) 
        body = new Stmt.Block(Arrays.asList(body, new Stmt.Expression(increment)));

    // if there is no condition it will loop infinitely
    if (condition == null) condition = new Expr.Literal(true);
    body = new Stmt.While(condition, body);

    // if there is an initializer then add it to the start of the body
    if (initializer != null)
        body = new Stmt.Block(Arrays.asList(initializer, body));
    loops--;
    return body;

}

Then the interpreter executes it as though it was a while loop.

@Override
public Void visitWhileStmt(Stmt.While stmt) {
    // keep executing statement body while statement
    // condition evaluates to a non falsey value
    while (isTruthy(evaluate(stmt.condition))) {
        try {
            execute(stmt.body);
        } catch (BreakException breakException) {
            break;
        } catch (ContinueException continueException) {

        }
    }

    return null;
}

For most cases, this works. But it means that continue statements never call the increment statement so it loops indefinitely.

Two ways I have thought of handling it are:

Don't desugar for loops, handle them differently in the interpreter.
In the AST, have an incrementer expression field that is set to null for while loops and the increment expression when it comes to for loops. Then, in the interpreter, call the incrementer if it exists when handling continue statements.

I am leaning towards the second solution.

State persisting across execution.

Setting the current colour or line width of the canvas sets the default the next time the script is run in a tab. I would like it to start from a clean slate.

Colour fields are non-modifiable because set has not been implemented.
No animation The interpreter is executed in one thread. There is no support for keyboard input or for doing something for X amount of time. I am not sure if I would like to support this, but it could allow people to quickly prototype games.

Missing features

Iterators. Right now I just have basic, C-style loops.
Modules and imports
Switch statements
Headless mode. Right now the concept of a current tab is built in. This makes implementing imports harder.
Foreign function interface. Allowing people to define library modules in other languages.
Multiple assignment E.g

var a, b, c = 3, 4, 5;

Line numbers
Syntax highlighting
Swizzling This is a handy feature in glsl.

gl_FragColor.rgb = glFragColor.bgr;

It is possible to create cool looking effects with this. Here is an example in a game engine tutorial I followed:

It might be possible to implement this in the get and set method of the DrawColor wrapper. By checking if the letters in the method are r, g, b, or a. And checking the length. Then returning an array or colour with the respective fields. And also setting the respective fields.

// rough java pseudocode
@Override
Object get(Token name) {
    boolean validFields = true;
    ArrayList<Char> fields = new ArrayList<Char>();
    for (Char field : name) {
        if (!(field.equals('r') || field.equals('g') || field.equals('b') || field.equals('a'))) {
            validFields = false;
            // throw error
        } else {
            fields.add(field);
        }
    }

    if (fields.size() === 4) return new DrawColor(new Color(fields))
}

@Override 
void set(Token name) {
    // similar to get
}

Potential applications

Compression. The file size of the code is often many times smaller than the file size of the output image. Not only that, but it is often possible to create images that look very different with code that is very similar by changing one parameter. One example of this is in an earlier post about biomorphs.

This image takes 2.29kb:

And this code takes 570 bytes:

var canvas = Canvas(160, 130);

function drawBranch(x, y, size, angle, angleDiff, iterations) {
    if (iterations == 0) return;
    var endX = x + Math.sin(Math.toRadians(angle)) * size;
    var endY = y - Math.cos(Math.toRadians(angle)) * size;

    canvas.drawLine(x, y, endX, endY);

    drawBranch(endX, endY, size, angle+angleDiff, angleDiff, iterations-1);
    drawBranch(endX, endY, size, angle-angleDiff, angleDiff, iterations-1);
}

drawBranch(80, 80, 10, 0, 35, 8);
saveImage(canvas.toImage(), "output_dir");

Changing the parameters to this:

drawBranch(80, 80, 10, 0.8, 0, 65, 10);

Produces this:

What about alternatives?

The first alternative that comes to mind is Processing and Processing JS.

For me, Draw has a few advantages over Processing.

I don't like it. This is the main reason I prefer Draw. I personally do not like their API. Maybe I am biased because I am used to using some form of Canvas API and Processing just looks wrong to me, but, for whatever reason, their API does not correspond to how I think about images so I made my own.
It is statically typed. I like static types, but I don't think it is a good idea for the kind of things I had in my when creating draw. I mostly intended to write small scripts and the advantages of static types are not visible in small scripts, only the disadvantages.
It was designed for non-programmers. From the Wikipedia page:

Processing is an open-source graphical library and integrated development environment (IDE) built for the electronic arts, new media art, and visual design communities with the purpose of teaching non-programmers the fundamentals of computer programming in a visual context

And from the ProcessingJS website:

Processing started as an open source programming language based on Java to help the electronic arts and visual design communities learn the basics of computer programming in a visual context

I made Draw for the opposite reason: I want to help people who know how to program, and think in terms of algorithms, create graphics.

Having said this, at the time of writing this, the maturity of Processing means that it is probably better for what I wrote Draw to achieve.

How to get started

The code is available here. You can download the JAR file from the classes folder.

Brooklyn 99 Brain Teaser: 12 islanders

sayedhajaj — Mon, 09 Dec 2019 00:02:58 +0000

This article was originally posted on my website.

In the show Brooklyn 99, Captain Holt poses a brain teaser to his detectives:

There are twelve men on an island. Eleven weigh exactly the same amount, but
one of them is either lighter or heavier. You must figure out which. The island has no scales but there is a seesaw. The exciting catch? You can only use it three times.

I have misremembered this teaser twice. The first time I assumed that the odd person out was heavier and that the goal was to find the person that weighed the most.

That is fairly simple to determine; it is similar to binary search.

Put 6 people on one side of the seesaw and the other six on the other side. Discard the lighter half.
Split the heavier 6 into groups of three and weigh them against each other. Then put one person from the heavier side on each side of the seesaw. If they are equal then the third person must be the odd one out.
Otherwise, the heavier side of the seesaw is the odd one out.

I was pleased with myself for discovering it so quickly, then I remembered that Holt said the person was either lighter or heavier.

Trying to solve that occupied my thoughts for a long time. I could only get solutions that work most of the time. After looking it up, I found that it was actually mathematically impossible.

I think the approach I took to try to solve it is still interesting.

I reasoned that whatever approach I used had to filter out as many people as possible in the fewest amount of checks. To narrow down the suspect list as much as possible, from twelve to one.

It also had to be "symmetric". That is, no matter how the seesaw balanced, it had to reduce the suspect list the same. If one result reduced the suspect list from twelve to four, and another result reduced the suspect list from twelve to eight, then it wouldn't be a very effective method.

The approach I came up with worked like this:

First split the islanders into four groups of 3. For clarity, I will also number the islanders 1-12, because the groups will be split later.

Put group 1, islanders 1-3, on one side of the seesaw, and group 2 on the other. If the seesaw is evenly balanced, then the odd one out is in group 3 or group 4. If the seesaw is uneven, the the odd one out is in group 1 or group 2.

I'll refer to the groups that contain the odd one out as the "suspect groups" and the groups which have been shown not to contain the odd one out as the "control groups".

Put one of the control groups on one side of the seesaw and one of the suspect groups on the other side of the seesaw.
If the seesaw is evenly balanced, the the other suspect group becomes the only suspect group and everyone on the seesaw is now part of the control group.
If the seesaw is not evenly balanced, then the suspect group on the seesaw becomes the only suspect group.

By now the suspect group should have 3 people, and we can use the seesaw one more time.

There is also a 7% chance that we know if the odd person out is heavier or lighter. This is because we know which group contains the odd person out know, and if that group has previously been compared with a control group, then we know if they were heavier or lighter. However, there is also a chance that we don't know if the person is heavier or lighter, if we have determined that they must be a suspect group by elimination, if the seesaw was evenly balanced for every comparison.

If we know if the odd islander is heavier or lighter, than this is solvable. If not, then we can narrow it down to two people.

We do this by putting one person from the suspect group on each side of the seesaw.
If they are evenly balanced then the third person must be the odd one out. It is possible that we don't know if this person is heavier or lighter.
If the seesaw is not evenly balanced, then it is one of the two people on the seesaw who is the odd one out. If we know if the person is heavier or lighter, then we know who the odd one out is. Otherwise, we can only say that it is between those two.

On relistening to the clip so that I can write this post, I saw that the puzzle could be interpreted to mean: "find out if the odd person out is heavier or lighter"

In that case, it is solvable.

Instead of splitting into groups of 3, split into groups of 4. Weigh group 1 against group 2, then group one against group 3. If the seesaw is even in the first usage, then look at where group 3 is relative to group 1. If the seesaw was uneven in the second usage, then the second comparison will reveal whether group 1 or group 2 contained the odd one out, and since they were both compared in the previous usage, remembering which one was heavier or lighter reveals gives the answer.

All whilst only using the seesaw twice.

Biomorphs

sayedhajaj — Sun, 01 Dec 2019 17:29:45 +0000

This article was originally posted on my website.

In a previous post I recreate Dawkin's Weasel Program.
In this post we will recreate a more visual demonstration of evolution - biomorphs.

A biomorph is a computer generated shape, with an appearance that can be influenced by a few variables. Richard Dawkins treats these variables as genes, and produces multiple biomorphs. They look like this:

He uses them to demonstrate evolution by asking members of an audience to try to evolve their own biomorphs, by selecting the one they like the most, and cloning their "genes" multiple times, with some variation to produce biomorphs that look slightly different.

He was able to produce a large variety of different biomorphs. Here are some of his favourite:

To draw his Biomorphs, Dawkins imitates embryology using recursion:

Embryonic development is far too elaborate a process to simulate
realistically on a small computer. We must represent it by some
simplified analogue. We must find a simple picture-drawing rule that
the computer can easily obey, and which can then be made to vary
under the influence of 'genes'. What drawing rule shall we choose?
Textbooks of computer science often illustrate the power of what they
call 'recursive' programming with a simple tree-growing procedure.
The computer starts by drawing a single vertical line. Then the line
branches into two. Then each of the branches splits into two sub-
branches. Then each of the sub-branches splits into sub-sub-branches,
and so on. It is 'recursive' because the same rule (in this case a
branching rule) is applied locally all over the growing tree. No matter
how big the tree may grow, the same branching rule goes on being
applied at the tips of all its twigs.

Drawing the biomorphs

I'll be using Javascript and HTML canvas to recreate Dawkin's biomorphs.

Let's start with enough HTML to get a canvas on the screen and get a rendering context.
First create a file called biomorphs.html.

<!DOCTYPE html>
<html>
    <head>
        <title>Biomorphs</title>
    </head>
    <body>
    <canvas width="720" height="480" id="canvas">

    </canvas>
    <script type="text/javascript">
        var canvas = document.getElementById("canvas");
        var ctx = canvas.getContext("2d");


    </script>

    <style type="text/css">
        canvas {
            border: thin solid black;
        }
    </style>

    </body>
</html>

Now I will make a javascript function to create biomorphs.
First we write the code to draw a line at 45 degrees. If we have a line with length s, and a angle of a, and a starting position of x and y, then the final position, according to trigonometry, is $x+sin(a)$ and $y+cos(a)$.

In our case, however, since the origin of the canvas coordinate system is on the top left, we will be using $y-cos(a)$ so the angles appear as expected.

var canvas = document.getElementById("canvas");
var ctx = canvas.getContext("2d");

function toRadians(angle) {
    return angle * Math.PI / 180;
}

function drawLine(x, y, endX, endY) {
    ctx.beginPath();
    ctx.moveTo(x, y);

    ctx.lineTo(endX, endY);
    ctx.stroke();
}

function drawBranch(x, y) {
    var endX = x + Math.sin(toRadians(45)) * 40;
    var endY = y - Math.cos(toRadians(45)) * 40;

    drawLine(x, y, endX, endY);
}

drawBranch(100, 100);

Since the sin and cos functions in Javascript use radians, I've created a helper function that converts degrees to radians. This is because people tend to prefer degrees, and 360 is divisible by many whole numbers, allowing for the easy creation of variety of biomorphs.

I've also created a function to draw a line between two points, since that does not exist in Javascript canvas.

Running them in the browser should show this:

Now let's remove the hard-coded values for the angle:

function drawBranch(x, y, size, angle) {
    var endX = x + Math.sin(toRadians(angle)) * size;
    var endY = y - Math.cos(toRadians(angle)) * size;

    drawLine(x, y, endX, endY);
}

drawBranch(100, 100, 40, 45);

After drawing the first line, two more lines should to branch from the end.
Like this:

Before we go about making this function recursive, let's try to implement it by hand.

function drawBranch(x, y, size, angle) {
    var endX = x + Math.sin(toRadians(angle)) * size;
    var endY = y - Math.cos(toRadians(angle)) * size;

    drawLine(x, y, endX, endY);

    x = endX;
    y = endY;


    endX = x + Math.sin(toRadians(angle+angle)) * size;
    endY = y - Math.cos(toRadians(angle+angle)) * size; 

    drawLine(x, y, endX, endY);     

    endX = x + Math.sin(toRadians(angle-angle)) * size;
    endY = y - Math.cos(toRadians(angle-angle)) * size; 

    drawLine(x, y, endX, endY);


    }

Most of the code is repeated. The difference is the angle has changed. The first branch is 45 degrees to the left, and the other branch it is 45 degrees to the right.

This means we only have to modify the angle when calling recursively, and add a base condition to return when the number of iterations has been met to prevent an infinite loop.

function drawBranch(x, y, size, angle, angleDiff, iterations) {
    if (iterations == 0) return;
    var endX = x + Math.sin(toRadians(angle)) * size;
    var endY = y - Math.cos(toRadians(angle)) * size;

    drawLine(x, y, endX, endY);

    drawBranch(endX, endY, size, angle+angleDiff, angleDiff, iterations-1);
    drawBranch(endX, endY, size, angle-angleDiff, angleDiff, iterations-1);
}

drawBranch(100, 100, 40, 45, 45, 2);

Now, by changing the number of iterations, we have a whole new image.

function drawBranch(x, y, size, angle, angleDiff, iterations) {
    if (iterations == 0) return;
    var endX = x + Math.sin(toRadians(angle)) * size;
    var endY = y - Math.cos(toRadians(angle)) * size;

    drawLine(x, y, endX, endY);

    drawBranch(endX, endY, size, angle+angleDiff, angleDiff, iterations-1);
    drawBranch(endX, endY, size, angle-angleDiff, angleDiff, iterations-1);
}

drawBranch(100, 200, 40, 0, 45, 3);
drawBranch(300, 200, 40, 0, 45, 4);
drawBranch(500, 400, 40, 0, 45, 5);

function drawBranch(x, y, size, angle, angleDiff, iterations) {
    if (iterations == 0) return;
    var endX = x + Math.sin(toRadians(angle)) * size;
    var endY = y - Math.cos(toRadians(angle)) * size;

    drawLine(x, y, endX, endY);

    drawBranch(endX, endY, size*0.8, angle+angleDiff, angleDiff, iterations-1);
    drawBranch(endX, endY, size*0.8, angle-angleDiff, angleDiff, iterations-1);
}



drawBranch(50, 200, 20, 0, 45, 3);
drawBranch(150, 200, 20, 0, 45, 4);
drawBranch(250, 200, 20, 0, 45, 5);
drawBranch(350, 200, 20, 0, 45, 6);
drawBranch(470, 200, 20, 0, 45, 8);

Now replace the drawBranch calls with:

var i = 0;
for (var row = 1; row < 5; row++) {
    for (var col = 1; col < 6; col++) {
        i++;
        drawBranch(col * 110, row * 110, 20, 0, i*6, 8);
    }
}

One last gene - the size factor:

function drawBranch(x, y, size, sizeFactor, angle, angleDiff, iterations) {
    if (iterations == 0) return;
    var endX = x + Math.sin(toRadians(angle)) * size;
    var endY = y - Math.cos(toRadians(angle)) * size;

    drawLine(x, y, endX, endY);

    drawBranch(endX, endY, size*sizeFactor, sizeFactor, angle+angleDiff, angleDiff, iterations-1);
    drawBranch(endX, endY, size*sizeFactor, sizeFactor, angle-angleDiff, angleDiff, iterations-1);
}


var i = 0;
for (var row = 1; row < 5; row++) {
    for (var col = 1; col < 6; col++) {
        i++;
        drawBranch(col * 110, row * 110, 20, 0.8, 0, i*6, 8);
    }
}

Remember, every change to the parameters that drawBranch accepts means we have to pass it in when calling it.

The evolution bit

Now we have a function that, given some parameters, can draw many different shapes. But we have no way of evolving it yet. To do that, we will need a concept of genes. I'll use arrays to replicate this. First I will create a Biomorph class that takes in an array of genes.

const GENE_INDICIES = {
    SIZE: 0, 
    SIZE_FACTOR: 1,
    ANGLE_DIFF: 2,
    ITERATIONS: 3 
};

class Biomorph {
    constructor(genes) {
        this.genes = genes;
    }

    draw(x, y) {
        drawBranch(
            x, y, 
            this.genes[GENE_INDICIES.SIZE], 
            this.genes[GENE_INDICIES.SIZE_FACTOR], 
            0,
            this.genes[GENE_INDICIES.ANGLE_DIFF],
            this.genes[GENE_INDICIES.ITERATIONS]
        );
    }
}

Now replace the loop for drawing the branches with this:

var biomorph = new Biomorph([20, 0.8, 25, 8]);
biomorph.draw(100, 100);

And running it should show this:

Now let's add the ability to "reproduce" a biomorph:

reproduce() {
    var newGenes = [];

    for (var i = 0; i < this.genes.length; i++) {
        var geneValue = this.genes[i];
        var difference = Math.random() * 0.3 - 0.15;
        if (Math.random() * 100 > 20) geneValue *= 1 + difference;
        newGenes.push(geneValue);
    }

    return new Biomorph(newGenes);
}

We change a value by no more than 25%.

To make this work we also have to make sure the genes stay within valid ranges - otherwise they get too big:

draw(x, y) {
    drawBranch(
        x, y, 
        Math.min(this.genes[GENE_INDICIES.SIZE], 30),
        Math.min(this.genes[GENE_INDICIES.SIZE_FACTOR], 0.9), 
        0,
        this.genes[GENE_INDICIES.ANGLE_DIFF],
        Math.min(Math.round(this.genes[GENE_INDICIES.ITERATIONS]), 12)
    );
}

Now we can test this by creating a biomorph and reproducing it then drawing both to the screen.

var biomorph = new Biomorph([20, 0.8, 25, 8]);
biomorph.draw(100, 100);

var child = biomorph.reproduce();
child.draw(300, 100);

Next we need to fill a grid with child biomorphs.

First let's create a method to populate the grid. In this method we set add the parent biomorph to the middle cell, and add children of the parent in all other cells.

function populateGrid(parent) {
    var grid = Array.from(Array(3), () => new Array(5));
    for (var y = 0; y < grid.length; y++) {
        for (var x = 0; x < grid[y].length; x++) {
            if (y == (grid.length+1)/2 - 1 && x == (grid[y].length+1)/2 - 1) {
                grid[y][x] = parent;
            } else {
                grid[y][x] = parent.reproduce();
            }
        }
    }
    return grid;
}

This takes in a parent so that when we select a biomorph, we create a new grid with the selected biomorph as the parent.

function drawGrid() {
    for (var y = 0; y < grid.length; y++) {
        for (var x = 0; x < grid[y].length; x++) {
            grid[y][x].draw((x+1) * 110, (y+1) * 110 + 25);
        }
    }
}

var biomorph = new Biomorph([20, 0.8, 25, 8]);
grid = populateGrid(biomorph);
drawGrid();

Next we need a way to select a biomorph. We'll do this by adding an event handler to the canvas.

canvas.addEventListener('click', function (evt) {


});

To get the mouse coordinates relative to the canvas, we get the clientX and clientY from the event.

canvas.addEventListener('click', function (evt) {
    var x = evt.clientX;
    var y = evt.clientY;
});

And to convert from the x and y coordinates to indices in the grid, we offset the coordinates and divide by the size of the cell.

canvas.addEventListener('click', function (evt) {
    var x = evt.clientX;
    var y = evt.clientY;
    var col = Math.floor((x - 55)/110);
    var row = Math.floor((y - 55)/110);


});

Now that we have the indices in the grid, all we have to do is extract the selected biomorph, repopulate the grid using that biomorph as the parent, and redraw the grid. We also have to check that the row and column are valid indices within the grid:

canvas.addEventListener('click', function (evt) {
    var x = evt.clientX;
    var y = evt.clientY;
    var col = Math.floor((x - 55)/110);
    var row = Math.floor((y - 55)/110);
    if (row >= 0 && row < grid.length && col >= 0 && col < grid[row].length) {
        var parent = grid[row][col];
        grid = populateGrid(parent);
        drawGrid();
    }

});

To prevent the previous biomorphs from being drawn over, we clear the canvas:

function drawGrid() {
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    for (var y = 0; y < grid.length; y++) {
        for (var x = 0; x < grid[y].length; x++) {
            grid[y][x].draw((x+1) * 110, (y+1) * 110 + 25);
        }
    }
}

Next Steps

This is enough to demonstrate the general principle but there is a lot more that could be done. For example, by adding "segmentation", and playing with symmettry and adding a gradient scale, Dawkins was able to create much more complex shapes:

Another way we could extend it is by saving a selected biomorph - that's something Richard Dawkins decided to do after trying to recreate a biomorph.

Weasel Program

sayedhajaj — Sat, 30 Nov 2019 22:22:41 +0000

This article was originally posted on my website.

One big misconception of evolution by natural selection is the idea that it operates by random chance. People often look at the number of ways a protein, for example, could be arranged, and claim that the probability of it evolving must be miniscule.

In his book The Blind Watchmaker, Richard Dawkins addresses this using a computer program to demonstrate an analogy.

He does this by first referencing infinite monkey theorem.

This is the idea that monkeys bashing on keys randomly, given enough time, will produce all the works of Shakespeare.

He contrasts this with an evolutionary approach: starting from random gibberish, copy it with a probability of a random mutation. Select the mutation that most resembles the works of Shakespeare. Repeat until the works of Shakespeare have been reproduced.

To simplify the demonstration, instead of attempting to produce all the works of Shakespeare, he instead tries to produce just one phrase: "METHINKS IT IS LIKE A WEASEL" (from Hamlet).

28 characters. Each character can be any one of 27 characters (the alphabet and a space character). That's $27^{28}$ combinations, or roughly $10^{40}$ (underestimate).

If we were producing these sequences at a rate of one per second, it would take $2.29628729 * 10^{22}$ times longer than the length of the universe to go through all combinations.

This program has come to be known as "The Weasel Program".

Let's reproduce this program here. I'll be using python to write this.

How it works

Generate a random sequence of 28 characters.
Copy every character that in that sequence 100 times.
Give every character a 5% chance of mutating to a random character.
Choose the sequence that most closely resembles "METHINKS IT IS LIKE A WEASEL".
Repeat the process for this sequence until the target phrase has been produced.

First we define our target phrase and the possible characters than can be used.

import random
def main():
    goal = "METHINKS IT IS LIKE A WEASEL"
    characters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "

Next we create a method to generate a random sequence of characters. I will pass in the goal so I don't have an extra variable for the length.

def generate_random_sequence(goal, characters):
    sequence = ""
    for i in range(len(goal)):
        sequence += characters[random.randint(0, len(characters)-1)]
    return sequence

Let's go back to the main method to use the random sequence generator.

def main():
    goal = "METHINKS IT IS LIKE A WEASEL"
    characters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "
    generations = 0
    current_sequence = generate_random_sequence(goal, characters)
    print("Generation:", generations)
    print(current_sequence)
    while current_sequence != goal:
        generations += 1
        print("Generation:", generations)
        print(current_sequence)

If we run this now, we'll have an infinite loop.
The next step is to modify the current sequence by mutating it.
We will do this by creating a method that takes in the current sequence, creates one hundred mutated copies, and returns the copy that most closely resembles the target sequence.

def get_mutated_sequence(sequence, goal, characters):
    sequence_list = get_sequence_mutations(sequence, characters)
    best_seq = sequence_list[0]
    best_similarity_factor = get_score(best_seq, goal)
    for seq in sequence_list:
        similarity_factor = get_score(seq, goal)        
        if similarity_factor > best_similarity_factor:
            best_similarity_factor = similarity_factor
            best_seq = seq
    return best_seq

This depends on:

def get_sequence_mutations(sequence, characters):
    sequence_list = []
    for i in range(100):
        sequence_list.append(mutate_sequence(sequence, characters))
    return sequence_list

And

def mutate_sequence(sequence, characters):
    result = ""
    for i in range(len(sequence)):
        if random.randint(0, 100) <= 5:
            result += characters[random.randint(0, len(characters)-1)]
        else:
            result += sequence[i]
    return result

To calculate the score we count the number of letters in the correct place

def get_score(sequence, goal):
    score = 0
    for i in range(len(goal)):
        if goal[i] == sequence[i]:
            score += 1
    return score

To tie it all together, we modify the current sequence in the main loop by the mutated sequence.

def main():
    goal = "METHINKS IT IS LIKE A WEASEL"
    characters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "
    generations = 0
    current_sequence = generate_random_sequence(goal, characters)
    print("Generation:", generations)
    print(current_sequence)
    while current_sequence != goal:
        current_sequence = get_mutated_sequence(current_sequence, goal, characters)
        generations += 1
        print("Generation:", generations)
        print(current_sequence)

And to run it, we call main.

main()

Running this program yields this:

Generation: 0
YBNBWOMPQYBVOC UELOZYJMU QKG
Generation: 1
YBNBWOKPQIBVOC UEJOZYKMU QKG
Generation: 2
MBNBWOKPQIBVRC UEJOUYKMU QKG
Generation: 3
MBNBWOKPQIBVRC UEJOUAKMR QKG
Generation: 4
MBNPWOKPQIBVRC UIJOUAKMR QKG
Generation: 5
MBNPWOKI IBVRC UIJOUAKMR CKM
Generation: 6
MBNPWNKI IBVRC UIJOUAKMR CKM
Generation: 7
MBNPWNKI IBVRC UIJOUA MR CKM
Generation: 8
MBNPWNKI IBVRZ UIJOUA WR CKM
Generation: 9
MBNPWNKI IBVRZ UIJOUA WR CKL
Generation: 10
MBOPXNKI ITVRZ UITOUA WR CKL
Generation: 11
MBTPXNKI ITVRZ UITOUA WR CKL
Generation: 12
MBTPXNKI ITVRZ UIKOUA WR CKL
Generation: 13
METPXNKS ITVRZ UIKOUA ZR CKL
Generation: 14
METPXNKS ITBRZ UIKOUA ZR CKL
Generation: 15
METPINKS ITBRZ UIKOUA ZR CKL
Generation: 16
METPINKS ITBRZ OIKOUA ZR CKL
Generation: 17
METBINKS ITBRZ OIKOUA ZRACKL
Generation: 18
METBINKS ITBRZ OIKOUA ZRASKL
Generation: 19
METBINKS IT RZ WIKOUA ZRASKL
Generation: 20
METBINKS IH RZ WIKO A ZGASKL
Generation: 21
METBINKS IH RZ WIKO A ZGASKL
Generation: 22
METHINKS IH RZ WIKO A ZGASKL
Generation: 23
METHINKS IH IZ WIKO A ZGASKL
Generation: 24
METHINKS IH IZ WIKF A WGASKL
Generation: 25
METHINKS IH IZ LIKF A WGASKL
Generation: 26
METHINKS IH IZ LIKF A WGASKL
Generation: 27
METHINKS IB IZ LIKE A WGASKL
Generation: 28
METHINKS IT IZ LIKE A WGASKL
Generation: 29
METHINKS IT IZ LIKE A WGASKL
Generation: 30
METHINKS IT IZ LIKE A WEASKL
Generation: 31
METHINKS IT IZ LIKE A WEASKL
Generation: 32
METHINKS IT IZ LIKE A WEASKL
Generation: 33
METHINKS IT IZ LIKE A WEASKL
Generation: 34
METHINKS IT IZ LIKE A WEASKL
Generation: 35
METHINKS IT IZ LIKE A WEASKL
Generation: 36
METHINKS IT IZ LIKE A WEASKL
Generation: 37
METHINKS IT IZ LIKE A WEASKL
Generation: 38
METHINKS IT IZ LIKE A WEASEL
Generation: 39
METHINKS IT IZ LIKE A WEASEL
Generation: 40
METHINKS IT IS LIKE A WEASEL

In just 40 generations of, as Dawkins describes it, cumulative selection, we were able to arrive at a target phrase that has a 1 in $10^{40}$ chance of being arrived at by pure chance in single step selection.

Note that there are differences between this program and natural selection - here we explicity set a target phrase, in nature there is no target phrase. However, the principle is almost the same. In fact, it could be comparable to a predator not being able to see certain colours (e.g camouflage).

This is the basis for genetic algorithms.
It has a starting population - the randomly generated phrase, it has a fitness funtion - the score method, and there is mutation and reproduction.

DEV Community: sayedhajaj

Thoughts On Types

Introduction

Every program has types, whether you write them or not

Data structures make algorithms obvious

Some static types have a lot of boilerplate

Many typed programming languages disallow programs that won't crash

Powerful typed programs have issues

A smellier alternative

Maybe optional typing?

Related rant on null

Engineers and tradeoffs

Announcing Drawlang

Table of contents

Motivation

How it started

Overview

Design decisions

Examples

Modern Art

Chessboard

Asteroids

Magic Real Estate

Spritesheets

A peek under the hood

Current issues

Missing features

Potential applications

What about alternatives?

How to get started

Brooklyn 99 Brain Teaser: 12 islanders

Biomorphs

Drawing the biomorphs

The evolution bit

Next Steps

Weasel Program

How it works