Hugo Simoes
simple living, careful thinking, collective fun


Talks@DCC - Slides

I recently gave a talk on Prequel.
For those of you who wanted, but were unable to attend, I leave here the slides and the main points.

Event slides: poster

First, some context on why I decided to create a programming language.

Event slides: my childhood

I started to type-in program examples as a child (in 1983), because my (family household's) ZX Spectrum did not come with a tape recorder.
For a few months, if I wanted the Speccy to do something, I had to type-in code from the manual and from Spectrum magazines.
Some examples had typos and that forced me to make changes, trying to fix parser errors, to get the code running.
This was how I started to program.

Event slides: my oldest son's childhood

In 2017 my oldest son was about the same age I was when I started to program.
This happened to be a time when I had recently left my job and was doing some soul searching, trying to find something meaningful, something I really wanted to do, and I decided to help my kids with programming (looking at what was then available to help them).
There were many things available, but none I really liked (except the ELLO computer, which would have worked for my purposes, unfortunately I am still waiting for my backer unit).
I set up to build what I would like to have had when starting to program.
I wanted my kids, or anyone else for that matter, to be able to program anywhere, on a browser, even on a smartphone.
And I wanted a programming language that was simple.

Event slides: loop programs and primitive recursive functions

Well, simpler than loop programs is complicated ;)
Loop programs are the imperative programming counterpart to primitive recursive functions.

Event slides: loop programs with additional instructions

Over the years people experimented with variants — introducing instructions to directly handle subtraction, conditionals, and early termination of loops — and found out that, although the theoretical expressive power would remain unchanged, these added instructions would make the programming language more efficient from a practical point of view.
This was what I was looking for: a programming language that could be used with ease in practice.

Event slides: Primitive RECursive driven programming Language

As it turns out, loop programs are the theoretical underpinnings of my Primitive RECursive driven programming Language, which, instead of PRECL, I call Prequel because I like the idea of something that brings us back to basics, back to the foundation of programming.

The core of the language, the part that is common to all projects, to all the examples that use Prequel, simply has assignments, two datatypes (signed 32-bit integers and possibly nested lists of such integers), and two control structures.
There is a part of Prequel that is specific to each example: input (in the form of read-only variables) and procedures.
When an example is created it is also decided which input to pass on to Prequel and which procedures are needed to act on the example.
Creating an example is a process similar to a game designer deciding which ingredients to include, deciding how is the game best served.

Event slides: Prequel examples

Currently, everybody has the possibility of loading, running, and debugging Prequel programs in 9 projects/examples.

Note that, in the Ackermann example you are asked to implement the Ackermann function.
How are you going to implement a non-primitive recursive function in a primitive recursive programming language?
Well, Prequel is primitive recursion driven, general recursion powered.
Prequel makes it easy to keep a programming discipline of primitive recursion, but you are free to break that discipline and go beyond the expressive power of loop programs.
The idea is that, whenever the execution slips past the last instruction, the runtime system re-enters the module preserving the state (keeping its variables and their content).
This was a simple idea I had (too simple to have not been found) and I was told (as feedback from the talk) of an already existing paper proving that primitive recursion within an outer while loop is Turing-complete.
I will try to find the paper and have a look at the similarities to my approach, although, regardless of any theoretical result, my goal with Prequel was always about creating an environment that was fun to program in.

Event slides: demo

Finding the optimal score of the ConnXxis puzzle is still an open problem.
The optimal score cannot be higher than 90 and the current high score is 72.
If you improve upon any known highest score (perhaps by programming an heuristic in Prequel) you enter the ConnXxis Hall of Fame.

During the talk, I demoed Factorial, AlgoDeduce, and AmoebaArena.

Note that AlgoDeduce can be used by companies to help recruiters filter candidate programmers based on demonstrable algorithmic skills.
The fact that Prequel is currently not widespread can be used as an advantage: solutions in Prequel are hard to find (and copy/paste), so any programming exercise can be given beforehand.

Regarding AmoebaArena, I pointed out the 30 ticks per second, where, for each snapshot of the game state, a bot only has to call either AMOEBA.ACTIVATE() or AMOEBA.DEACTIVATE().
The bot view of the game state is not updated until either call.
So, although there is a limit on the number of instructions per tick, a bot can use more instructions by trading off the accuracy of a progressively out-of-sync picture in this soft real-time system.
I will try to organise 2-vs-2 tournaments locally by the end of the year, before moving those tournaments online.

Event slides: thank you

Hope you get the chance to attend a Prequel event in the future :)

EDIT 2023/10/17: Many thanks to Pedro Vasconcelos for showing me Kleene's normal form theorem, published in 1943, basically proving that you only need one while loop to obtain Turing-completeness. (Prequel gives us one while loop per module.)

EDIT 2024/04/08: Renamed Warpchase to AmoebaArena.

June 17, 2022