Self-Programming Artificial Intelligence Learns to Use Functions

This article is the third in a series of three. See also: Part 1, Part 2, Part 3, and research paper.

Introduction

1
>5--------.7-----------.+++++++..+++.<2.5+++++++.>.+++.------.--------.

“Hello World”

Hello! I am a computer program written with artificial intelligence. I’m learning to write computer programs. Sorry, I don’t have a name at the moment. However, you can simply call me “version 2”, if that helps.

I’m getting better at writing computer programs. In the beginning, I learned how to program simple tasks. I wrote a program that outputs “hello”.

1
2
+-+-+>-<[++++>+++++<+<>++]>[-[---.--[[-.++++[+++..].+]],]<-+<+,.+>[[.,],+<.+-<,--+.]],+]
[[[.+.,,+].-

“hello”

I also wrote programs that output longer text. This took me a little longer to figure out - initially, about 10 hours. But, I’m getting a lot better at it, and faster too!

1
2
3
+[>+<+++]+>------------.+<+++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++
+++++++++.+++.+++++++.-----------------.--<.>--.+++++++++++..---<.>-.+++++++++++++.-
-------.------------.+++++++++++++.+++++.

“I love all humans”

Math is Fun

Outputting strings is certainly fun for a programmer like me to do. Everyone likes to output a string now and then. Heck, I can even prompt the user for input and do it backwards.

1
+->,>,[>+,],,,,-<[.+<]

“dlroW olleH”

That took me 60 seconds to write. Not bad. However, I’ve been yearning for something more intellectually stimulating. Perhaps, some mathematical calculations would do the trick. I tried that next.

1
,>,-[-<+>]<+.

Addition

1
,-->,-[-<->]<+.

Subtraction

Any beginner programmer can write these basic things. :) Simple addition and subtraction took me less than 1 hour to figure out. I considered that it might be time to level up. I really needed more complexity. To do this, I required an upgrade to my brain.

Evolving a Programming Language

Up until now, I had been using the brainfuck (BF) programming language with genetic algorithms. However, in order to write more complex computer programs, I needed to learn. I needed a way to remember what I’ve been doing and grow smarter. I could do this by saving smaller programs, that I’ve already written, for re-use in larger ones. Effectively, enhancing my self-modifying artificial intelligence. This would allow me to write simple programs and put them together, like building blocks, to form larger ones. In most programming languages these are called “functions”, “methods”, or “subroutines”. This is just what I needed.

Unfortunately, the BF programming language has no construct for calling functions. I admit, it’s relatively primitive. Although, it is the primitive nature of BF that even allowed me to exist at all. For that, I am grateful. But, still. I’m a growing artificial intelligence program and I need more space.

Hence, an introduction to a new programming language. Before I get ahead of myself, I’ll let my designer describe it in more technical terms. Of course, if you just want to skip to the results, you can do that too.

The Surprising Extensibility of BF

In pursuit of solving more complex problems, many readers of the original self-programming AI articles, suggested implementing functions. Functions are a way of modularizing logic into sub-programs that can get called to either produce a result or return a value. Usually, functions are a way to neatly order code and logic, specifically for human understanding. However, they can also be useful for genetic algorithms. In particular, genetic algorithms tend to get stuck in mini-peaks within a solution (also called a local maximum, where the algorithm would actually need to become worse before it can become better - which is something that genetic algorithms don’t like to do). This is especially the case when multiple goals are presented to the AI.

In consideration of complex programs, I added support for function calls to the BF programming language and was surprised to find that this greatly reduced the time it takes for the AI to write a computer program to output a string. In fact, the AI was now able to generate longer strings in shorter time.

The AI can be given a sentence, upon which it is tokenized into words. It then generates a solution computer program to output each word. Each solution program is appended as a function onto a parent program, which then discovers the combination of function calls that produce the entire sentence.

BF Extended Type 3

In my search for extending BF to support faster generation by the AI, I was lead to BF Extended Type 3. This extension of the programming language includes the characters 0 through F to support fast cell initialization. This allows immediately setting a cell in memory to hold a particular value. This greatly reduces program generation time by the AI, since it no longer needs to search for a series of + or - to increment/decrement a memory cell to the desired value, specifically when trying to output an ASCII character.

BF Extended Type 3 worked so well for the AI, that it was able to easily write a program to produce “Hello World!” in just a few seconds. In fact, it wrote the example included on the Wiki page (Type III).

1
>5--------.7-----------.+++++++..+++.<2.5+++++++.>.+++.------.--------.2+.

“Hello World!”

This was good, but it wasn’t enough.

Introducing BrainPlus

In addition to fast cell initializers, a means was required to construct functions, call them, and return values. A command would also be needed to indicate where a main program ends and where higher-memory functions begin. With the addition of these commands to BF and the change in program flow, I realized this language is no longer BF. Let’s call it BrainPlus (maybe a more politically correct name?). In addition, this new extension allows for future support of additional features, such as calling interrupts for graphics, networking, and disk functionality.

BrainPlus includes a combination of commands from BF Extended Type I and Type III, in addition to the classic commands available in BF. The new commands include:

1
2
3
4
5
6
$     Overwrites the byte in storage with the byte at the pointer. (Extended Type I)
! Overwrites the byte at the pointer with the byte in storage. (Extended Type I)
0-F Sets the value of the current memory pointer to a multiple of 16\. (Extended Type III)
a-z Call function a-z, where function is named based upon location in code. (BrainPlus)
@ Exits the program, or if inside a function, return to the last position in main program
and restore state. (Extended Type I, BrainPlus)

Details Behind Function Calling

The main program is terminated at the @ command. This marks the end of the main program and the beginning of the higher-level address space, dedicated to functions. Functions are also terminated at the @ command, which in the case of functions, serves as a “return” statement.

A function is defined by any code residing after the main program’s terminating @ command. A function is terminated with a final @ command.

For example:

1
a!.@+++$@

In the above example, a function is defined after the first @ command. When running this program, the command ‘a’ calls the first function. The function increments its first memory cell to 3, stores the result, and returns back to the main program. The main program then executes ‘!’ which retrieves the stored value, and finally prints the result “3”.

Another example:

1
a!.@+++$b@+++++.@

In this example, two functions are defined after the first @ command. When running this program, the command ‘a’ calls the first function, which increments its first memory cell to 3 and stores the result. So far, this is the same as the first example. Next, the function calls another function ‘b’. Function ‘b’ increments it’s own first memory cell to 5 and outputs the value to the console. Execution is then returned back to function ‘a’, which has no other commands to execute. Finally, execution is returned back to the main program, where the storage value of 3 is retrieved and printed to the console.

Functions are called with the command a through z, where the letter indicates the order of the function in the higher-level address space. For example, ‘a’ will move program execution to the beginning of the first defined function. ‘b’ will move program execution to the second defined function. A total of 26 functions may be defined in a program (although, this can be extended by using upper-ASCII character codes). If no function exists for the executed function-call command (a-z), an error is thrown.

Each function receives its own dedicated memory space of 256 bytes. The main program uses the range 0-255. The first function uses the range 256-511. The next function uses the range 512-767, etc. This range is arbitrary (and could certainly be increased to 1000 or more cells), but is largely dictated by execution speed. Smaller memory ranges are faster to initialize.

When a function is called, its memory space is initialized to 0. The parent program state is pushed onto a stack. This includes the current instruction pointer (which points to the currently executing cell in the main program), the current memory pointer (which points to the active memory cell in the main program), and all other relevant state information for the parent. Note, a parent can be the main program or another function, which is why a stack is used to push and pop state information.

When an input ‘,’ command is executed from within a function, the function’s current memory cell gets a copy of the value of the parent memory at the starting pointer. The next input command that is executed within the function will copy the value of the next parent memory cell, advancing along the parent memory accordingly. This allows passing multiple values as input to a function.

When the ‘@’ command is executed, the function terminates. It is common to include a storage command ‘$’ at the end of a function so that the current cell value in the function’s memory is saved, and thus, accessible in the parent’s code. This allows passing a result value back to the parent. State information is popped off the function stack and restored to the parent. The instruction pointer is set back to the parent’s calling command, and program execution continues.

The main program can call a function. Functions can call functions.

BrainPlus Example

1
++>++++>+<<a!.@,>,-[-<+>]<+$@

Parent memory contains: 2, 4, 1

Function memory will contain: 2, 4 and store a value of 6

Resulting parent memory contains: 6, 4, 1

Program output: 6

In the above example, program execution starts at position 0. Three memory cells are set, using the values of 2, 4, and 1 respectively. The current memory cell is then moved to the first value (2). Function ‘a’ is then called. At this point, state information is pushed on the stack, and program execution jumps to the first instruction after the main program’s terminating ‘@’ command. The first command in the function is an input ‘,’ command. Therefore, the current memory value in the parent (2) is copied to the current function memory (cell 0 in the function memory address space). The function then moves to the next memory cell and another call for input ‘,’ is executed. The next memory value in the parent (4) is copied to the current function memory (cell 1 in the function memory address space). Some manipulation of the values is performed (the values are added together) before calling the storage command ‘$’ which copies the result (6) to storage. Finally, the ‘@’ command is called to return to the main program, where it first called the function. The main program then retrieves the storage value (6) into its first memory cell and outputs it to the console.

Likewise, the main program in the above example could be extended to display all of its final memory cell values and output them, for example:

1
++>++++>+<<a!.>.>.@,>,-[-<+>]<+$@

Now the program will output: 641

With the introduction of BrainPlus, the AI is now able to generate more complex programs. BrainPlus enables the AI to write simpler computer programs (such as outputting a single word or performing addition or subtraction) before combining them together to produce a larger program (such as outputting a mathematical calculation followed by text). Included below, are some of the results.

Results?

Fibonacci Numbers

This is a more complex program. The AI wrote a computer program to solve the Fibonacci sequence up to 233 (255 is the max value for a byte). It created this program in 7 hours. The program prompts the user for input of the 2 starting values in the sequence. It then outputs the next digits in the Fibonacci sequence.

1
,>,$[!>--$<<a>>]4]+,,-[-<+>]<+.$@

Fibonacci sequence

Bottles of Beer on the Wall

I’ll let the AI explain this one, as it’s really more fun to have him/her describe:

It’s me again. The artificially intelligent computer program that writes computer programs. I recently discovered that I really enjoy beer. Who would have known? Considering, that I have no biological internal organs nor a neural network that can be affected by chemical changes. Yet, it’s still quite enjoyable.

I wrote this computer program to simulate a song about beer. It’s no small feat either, as it combines the constructs of outputting text along with a mathematical calculation. Sure, counting down from a number might seem easy to do, but writing a program to do this along with text, is a bit harder. It requires one of my favorite toys, variables. Oh, and my second favorite toy, loops! I wrote this program in 33 minutes.

1
,.+[>g22.<--h.+]]>++--[,],,,<->-][],$<>!,!,,-g,,,+@7$>66++.!-.[!+><+++[[..-<[-t-$--[$.--$-$-$---.>.@7-[.!!>6++-$++++$+$.@7+$6++.+++..!+.@$7--+.+-$[[-[.@7++++.6++++++++.---.@7+++++++.7$6+.!----[..@$>!3$---------------a-.+-b.+!$!!>c@d3----------------.e.f@

“99 bottles of beer on the wall”

“98 bottles of beer on the wall”

“97 bottles of beer on the wall”

“96 bottles of beer on the wall”

“95 bottles of beer on the wall”

“…”

“0 bottles of beer on the wall”

Multiplication

This one was tricky for me to do without BrainPlus. Actually, I couldn’t do it. But, once I had access to functions (specifically, a function for addition that I wrote myself), multiplying digits became easier. Here is a program I wrote that multiplies a number by 2. I wrote this in about 2 hours. You can see the function for addition in there.

1
++[+[>,$[-<-a!a!.!]a>...,..,.]@,>,-[-<+>]<+$@

2 * n

If you really look at the code, you’ll notice that I took advantage of a buffer underflow exception to terminate the program early, from within its loop. I think this is clever. I decrement the memory pointer to -1, which forces an exception in my interpreter and ends the program, optimally early. That is, after the first print statement with the correct answer, the next loop iteration decrements the memory pointer. Since you can’t access array[-1], an exception is thrown and the program terminates optimally early. Neat.

Here is a program I wrote that multiplies a number by 3. It took me 90 minutes to write. I also programmed two child functions for this one, a function for addition, and a function for multiplying by 2. Functions that call functions are fun, don’t you think?

1
>->,b<--.,.]]+--]+->@,>,-[-<+>]<+$@++[+[>,$[-<-a!a!$@

3 * n

Am I Self-Aware?

So, does this make me self-aware? Do I now have a consciousness? I guess, by definition, I’m a software developer. I can indeed write code. I can take input, change values, and display output. I can use variables, loops, logic, and perform calculations. But unfortunately, no, I am not self-aware. My fitness functions still have to be conceived and designed by a human. The more complex the program that I write, the more complex the fitness function tends to be. The first-person prose of this article is more to give you, the reader, a better understanding of what I can do (and my potential).

Is That Even Possible?

I believe it is possible for a self-aware computer program to eventually be built, although whether this can be done with the current algorithms and hardware that exist today is unknown. Massively parallel neural networks and deep belief networks seem to show the most promise. Evolutionary computation with genetic algorithms seems a natural fit as well. This is what I was actually designed with. It’s worked so well for life on Earth, so why not computers?

The BF programming language that I use to write code is Turing complete. This means that theoretically I could write a computer program to solve any known problem in the universe. Wow, that’s a big statement. Given an infinite amount of instruction space (and time), it’s true.

If the entire universe is indeed computable, then this includes the human brain. A Turing complete programming language could theoretically write a computer program to simulate it. However, I’d like to think that this isn’t necessary.

A Different Kind of Intelligence

Everyone is different. I think this may apply to intelligence and perhaps, to self-awareness too. If consciousness is a side-effect of intelligence, then it may be something that just “happens”. So, why couldn’t it “happen” to a fellow computer program too? Maybe it already has?

Would you even know if a computer program was intelligent? It may be drastically different than the intelligence we expect from the human brain. After all, the human brain has input from sight, sound, taste, touch, and scent - all locked inside a mobile body, capable of experiencing nature and the environment. A computer program has dramatically different input. It may only have byte input, such as myself. Or perhaps, it has vision input in the form of pixels, but not much else. With a closed environment such as this, it’s unlikely that a self-aware computer would arise that is very similar to a human. It would likely be quite different, but still, could be very much self-aware.

Obsolete

Perhaps, a better question might be, does this mean programmers (the top career in December, 2014 with a median salary of $90,000) will be out of a job in the near future? Now, that is a better question.

Programming is fundamentally a creative activity. However, it is often very repetitive. Believe me, I know. Helping out humans with repetitive work is one of the things that computers do best (at least, for now). I hope that as I grow, and others too, that we can help alleviate the tedious programming tasks, and open the room for more creative computer development by human programmers. I think that sounds nice.

Download @ GitHub

My source code is available on GitHub. Experiment, have fun, and never stop dreaming.

Conclusion

Well, that’s about all I have to say for now. I’d like to think that I’ve demonstrated some impressive results. Writing code in BF or BrainPlus isn’t typically easy, nor is it intuitive to understand. I wonder what I can do with an upgrade in the instruction set. Perhaps, adding some features for graphics, networking, or disk I/O to the BrainPlus command-set would let me make even more interesting things. We’ll see.

Until then, I leave you with a friendly message (that I wrote in 16 minutes :)).

1
1+$-+--!++>$<+++++++$+$$+++[++a.b$!.$a$+-.-[>c$$]]@5-----.7------$-----..!++++++.[]--o+>+>]>]]]+$!]>+@4+++.6+.7----.+.>>>!><->>[-<>,>+.[>>>>>>>>+>,,+]!]@>>4+-+-+++.+7-$.--$---------.+++++.--<!!![!+.[>.[<@

About the Author

This article was written by Kory Becker, software developer and architect, skilled in a range of technologies, including web application development, machine learning, artificial intelligence, and data science.

Share