next »

[a-k-]

Oh wow, the idea of having to unlock keywords in programming contexts never occurred to me before. That's one way to tackle the expression problem!

Well, there have already been achievements for programming that get unlocked, so why not keywords?

[a-k-]

I've finally created a teaser video for the game. It's a screen recording of a ~1 minute programmed animation, so it'll be easy to change in the future. OBS didn't succeed to match the 60 fps of the game, so in some parts of the video it looks like time goes backward in the left side of the screen while the right side advances forward - hopefully that won't be too confusing for viewers.

Link to video (11 MB)

As part of preparing the video, I've changed all Common Lisp translations to emit "(while X)" instead of "(unless X (finish))" for tests in the middle of loops.

There have been excellent cost-cycles contributions from many players in the last months, and today I've finally lost first place on the leaderboard. That has actually happened multiple times before, but only briefly - this time it's going to be pretty hard to win back, if at all. Which is good news!

[a-k-]

One more translation, the 11th in the demo:


(example program and the corresponding LLVM IR)

[a-k-]

Game loading speed

A few attempts to accelerate the loading of the 4.5 MB HTML5 version (after noticing occasional 20-30 sec spikes):

• Added preloading hints, so that the 3 files that Emscripten generates are loaded in parallel in browsers that honor them (e.g. Chrome).
• Enabled HTTP/2, so that one TLS connection can be used for many parallel transfers.
• Made the 3 files cacheable by including a hash of the content as part of the filename.
• Started serving those files using a hierarchical CDN service (content is replicated to a few servers, and the many CDN servers fetch from them on cache misses - all supported out of the box). CDN server location is displayed in the loading screen.

Playtime desensitization

The time component of all timestamps in the DB is automatically wiped after two weeks. For example, if in a given day there are 100 unique timestamps (in 1 sec resolution), they will all get overwritten by values in the range 0:00:00 to 0:01:39. Order is preserved so that future analyses are still possible. Timestamps are shown in the Data Report screen only after undergoing this process.

Refined Level Select histograms

"Attrition" histograms distinguish between players that started any of the next levels, to those that didn't (including if those levels weren't available at the time of playing):


(previously, the last two shared the same bar)

[a-k-]

Localization

It seems that the last translation I presented here was incorrect! Here's the fixed version alongside the old one:


(in LLVM, basic blocks don't "fall through", and temporary names for them can't be specified explicitly)


Game loading speed (cont')

Since the CDN service I use has many more servers than the game has active players (...), chances are that when a player starts the game, the cache of the CDN server near their geographical location will be cold. To work around that, I've started doing the following:

• During loading, the server uses a public DNS service to resolve the root domain of the CDN, passing a prefix of the IP address as client subnet (ECS). The result is logged to a file, which over time, accumulates the addresses of CDN servers that players happen to use for loading the game (it's actually an approximation).
• After I deploy a new version of the game, I run a script that goes over the CDN servers in the file and loads the game's files directly from them (using "curl --resolve"). This brings the files into the cache of CDN servers that players tend to use, thereby accelerating game loading speed.

It's a pretty naive system and I have some ideas for improvement, but for now I think it'll do.

[a-k-]

One more translation...


(in the middle: a numeric label and an alphanumeric one, on the same line...)

[JobLeonard]

Wait, so are you compiling LLVM to a web app, or is all of that happening server-side?

[a-k-]

Wait, so are you compiling LLVM to a web app, or is all of that happening server-side?

Fortunately I didn't need to integrate LLVM at all (that would've been daunting client-side) - I just transpile directly to its text format, skipping the bitcode representation.

[JobLeonard]

I only have more questions now

Like: is that purely aesthetic then, or does it serve an in-game purpose?

[a-k-]

I only have more questions now

Like: is that purely aesthetic then, or does it serve an in-game purpose?

You're welcome! The translations are 100% aesthetic, and players can ignore them. They help keep developer motivation - this is my "art", some kind of statement.

I frequently use the C++ translation in order to refresh my memory with an old solution - it's concise and I parse it faster than commands on a board. And I can hover variables and follow the data flow, which helps in optimization. But I'm not sure how applicable this is to other players (I guess they don't change the language in the settings, and in that case, good luck reading INTERCAL...)

[JobLeonard]

Cool. Also makes kinda sense to me (also being a programmer)

I guess they don't change the language in the settings, and in that case, good luck reading INTERCAL...

You could give players a nudge via a prompt whenever a language is unlocked

[a-k-]

You could give players a nudge via a prompt whenever a language is unlocked

This is a good idea! There are no prompts in the game so I've added the message to the screen that's displayed when a new language is unlocked.


Player community

The game now has a Discord channel for player community, referenced from itch.io and moderated by two of the best players. I still prefer discussions over itch.io whose content isn't gated, but Discord has its special features and additionally supports spoilers, so can also be used for tips to players that get stuck.

Unlimited hint levels

Previously, players could unlock hint levels only if they had completed enough normal levels, in a 2:1 ratio. Coincidentally, 50% of the levels have hints so the ratio made some sense, but I suspect that the confirmation screen that showed up before unlocking a hint level may have discouraged players from doing so. Now it's gone, and clicking 'Hint' goes directly to the hint level.

Brute-force detection

Previously, whenever I noticed in the histograms that someone may have brute-forced a level - created a solution that assumed some limit on the size of the inputs (evident by solutions that are too fast and have many commands and conditions), I would add larger inputs until their solution is invalidated. That had some issues:

• Brute-force solutions can still be creative, and players felt that rejecting them didn't recognize that.
• Larger inputs/outputs render more slowly (affecting fps) and are harder to visualize.

(an output that's a complete binary tree with ~2⁷ nodes; bonus points for finding the root node...)

In order to give players recognition while not "polluting" the normal histograms with metrics that are infeasible to achieve for general solutions, I've introduced the concept of optional inputs:

• A solution doesn't need to succeed (or even terminate) on optional inputs in order to be regarded as a solution.
• Solutions that fail on optional inputs have their own histograms (the "root" histograms).
• Optional inputs (and outputs) are hidden and can't be selected by players.

This proved to be quite an intricate change, as it broke fundamental assumptions that the game had made since day 1, but now I can add extremely large inputs/outputs and simply mark them as optional, without concern for fps or for alienating players.

[JobLeonard]

Sounds like a good compromise to both stick to the original vision and give players their own wiggle room to play the game like they want to

[a-k-]

One more translation, this time to a predecessor of C:



I had to deviate from the idiomatic indentation style at places to save horizontal space, and there may be superfluous braces in rare cases.

The image also shows the format that's used when exporting (or importing) the game's internal clipboard to the system clipboard (or a file, in the HTML5 version) - a recent feature that was added to enable search-replace.

Sounds like a good compromise to both stick to the original vision and give players their own wiggle room to play the game like they want to

Yeah, I should probably make more changes in that spirit, but it's not easy to see where without a specific feedback (which I was fortunate enough to get in this case).

[a-k-]

Some initial thoughts:

	A if B then C else D E
Unstructured Code: main :- a, pred1. pred1 :- b, !, c, pred2. pred1 :- d, pred2. pred2 :- e.	Structured Code: main :- a, pred1, e. pred1 :- b, !, c. pred1 :- d.

The unstructured translation is easy to achieve - just go over the control flow graph and emit tail calls for all jumps. Similarly to the LLVM IR translation but using a different syntax.

The structured translation is more challenging. Need to determine which parts of the graph correspond to perfectly-structured conditions or loops (e.g. if B then C else D) and handle them as subroutines. The rest will use tail calls.

[JobLeonard]

Aren't there a ton of DSLs that doe exactly what you're trying to do here?

[a-k-]

Aren't there a ton of DSLs that doe exactly what you're trying to do here?

I haven't followed this space for a long time, off-hand I'd say that the CFG-->unstructured code is probably covered - anything that's based on rewriting may do. But I don't know about getting to the structure code - that would most likely require structural analysis as a prerequisite. After that there are source-to-source translation frameworks, but what would they do with the remaining gotos? And smaller in scope, graph transformation systems - I could certainly make use of them, but practically only for part of the process, otherwise it would be much more complex than just writing an ad-hoc algorithm (at least for me). But these are really only educated guesses.

[a-k-]

14 programming languages... when will it end?!


(a solution (right) and its translation (left))


First, the unstructured code (or some representation thereof) is generated, where each predicate (or clause) ends with a tail call to the next predicate (which is effectively a "goto"). Here, conditional jumps could be modeled either by Prolog's if-then-else operators ("-> ;") or with a red cut ("!"). After reviewing some code examples I decided to use the former for if's over actual code and the latter for loops and "if (...) break/continue/goto" stuff. This is merely a stylistic choice as both would work.

Then comes the "structurization" process, in which the output of the structural analysis, specifically the (possibly-nested) scopes of loops and conditions, is examined.


(a simple case of if-then-else and its conversion to a "subroutine")

We regard the predicates within a scope as a group (green in the diagram) and review its relation to predicates outside the group (orange). If the group is entered only via the start predicate, and all exits from the group are to the same "target" predicate, then we convert the group to a "subroutine" - we remove its calls to the target and add an "entry" predicate that calls the start predicate ("1") and then the target ("2") *.

Lastly, we repeatedly inline predicates under the constraint of not duplication code. So for example, a one-clause predicate that's called from only one (other) predicate can be inlined and its definition removed.


* Entry predicate is not created if the subroutine is nested inside another subroutine that already jumps to the same external target.

[a-k-]

Editing enhancements

• UI for inserting/deleting blank rows and columns anywhere (spreadsheet-like)
• UI for replacing workers (= variables) in multiple commands simultaneously

(top - deleting an empty column; bottom - replacing workers)


New mechanic

Previously, the goal in all levels was to create specific structures (outputs). Inspired by techniques used in busy beavers, now I've added levels where you need to keep the input but execute some no-op command a certain amount of times.

We've already had a level where you "compute" n+n and a hint level for n*n - now there's also nⁿ. Tetration will have to wait, though...


Prolog (cont')

In the previous post, I mentioned that I could choose, for each conditional jump, whether to model it with if-then-else or using Prolog's special cut operator. Giving the algorithm a second look, if I always selected if-then-else, the resulting control flow would fit virtually any language that supported tail call optimization. This opens up new candidates for implementation...


(this may have crashed a few servers at Google...)

[a-k-]

Top:
- A solution (partially redacted)
- Its control flow graph (as shown in the in-game profiler)
- Its canonical representation as a string (abstracting away actual location of commands on grid; DFS with numbers for back edges)

Bottom:
- Transformed string
- What it uniquely represents


Continued:
The above enables me to take all solutions of the player and quickly compute the set of distinct control flow patterns that they employ. But the algorithm isn't perfect - it distinguishes between the Yes and No branches of conditions, generating different canonical representations if you switch them (in the diagram above, that would mean swapping green and red). It would be better if "while (a == b) { ... }" and "while (a != b) { ... }" would be considered the same pattern.

As an example, negating the condition alternates between these two representations, so they should be considered the same pattern:

• A T A -1 A 1
• A T A 1 A -1

While these two are indeed different control flow patterns, and you can't arrive from one to the other by negating the condition:

• T -1 A 0
• T 0 A -1

So after calculating the canonical representations, I divide them to buckets based on invariants that are easy to compute, such as the number of T's and A's and the distribution of in-degrees. Then, in buckets that have more than one item, I convert the representations to labeled graphs and check for equivalence by the same algorithm that I use in the game, keeping only one items from each equivalence class.

This gives me the patterns I need - all based on the solutions of the player. But what do I need them for? To be continued...