#esolangs

[aadenboy]

esolangs: oh wow!! this is so fun!! it's like a puzzle… trying to figure out how to do an otherwise easy algorithm by getting around the limitations of the language! yippie!!

regular programming languages: Genuinely wtf is this. This is the worst code that I have ever written. Horrible in every way imaginable. SOPPING WET code. Unbearable and unmaintainable. Jank as crap. Completely remaking from scratch IMMEDIATELY.

[myzanilred]

SIGCHLD, PTYs, Why Exet Still Can't Properly Deal With Fully Interactive Programs, and What it Will Take to Fix it

Programming can be hard. Sometimes everything just falls into place, and other times, it can seem like every party responsible for the tools you're presented with conspired to ensure that combining them in the way you need would be as difficult as possible.

For this rant, I will be looking at a case of the latter scenario. Get comfortable, because this is going to be a long ride.

A Vague Problem:

I have been working on something called exet. It is designed to be able to do everything the expect utility does, and then some, using its own programming language, purpose built to handle the task. In many ways, it already accomplishes this, and I'm nearing an alpha release, so that others can start playing around with it.

However, there is still one major thing that exet can't do. It can't properly deal with fully interactive programs. Programs that present a prompt, and wait for a user to enter something.

Currently, exet deals with external programs through commands, which are file channels (what exet has instead of conventional variables) with a path that begins with a bang (!). Exet executes commands in much the same way as the shell, connecting to them using pipes. Most interactive programs will actually set themselves into a non-interactive mode when they detect that they're connected to a pipe, which allows this method to work for the majority of programs. This is also easier, and more efficient than the alternative, which is why I set it up first, and have avoided the other "solution" until now. But what happens when a program doesn't have a non-interactive mode, or when you need the interactive version of the command, because of some quirk of what you're trying to do?

Enter Pseudoterminals:

A pseudoterminal, or PTY as I will refer to them from here on, is like a pipe, in that it allows one process to be connected to another. The difference is that, to the process on the slave end of the PTY, it appears to be connected to a terminal device, and therefor believes that it is interacting with a user. Whenever you open a graphical terminal window, or "terminal emulator", one of the first things that software does is start a PTY session. It then controls details of the PTY to reflect the size of the window, and the type of terminal being emulated, as well as capturing special "control codes" and responding to them, so that the software running in the session behaves as we would expect it to on a proper terminal.

So how does this help us, and what is the problem?

A Specific Problem:

The first real problem we encounter when dealing with programs attached to pipes is that of buffering. Many programs use the standard I/O library to read and write text to whatever they're connected to. If this is a terminal, then the output of the program is "line buffered", by default. This means that the program waits to output anything until either the buffer is full, or a newline is stored to the buffer. This makes sense if you're interacting with a user, and want every full line to be immediately visible to them. However if the standard I/O is connected to a pipe, it instead defaults to "fully buffered", and the output won't be sent until the buffer is full, or if the program explicitly flushes the buffer. Remember that last bit, it'll be important later.

So, if we're using a pipe to redirect output of a program into exet, we could end up waiting forever for input that will never come, because the the buffer never fills, because the process is waiting for exet to make the first move, but we don't know that. But we can solve this by making it think that it's talking to a user by connecting it to PTY. Cool. So we just use a PTY then?

If it were only that simple...

Setting Things Up:

Lets start by looking at the process for setting up pipes, and compare that to the process of setting up a PTY. I will try to condense this as much as possible. It's a lot of information, and we don't really need the details of it.

To start a process, and connect it via pipes, we need to first, create a set of pipes using the pipe() function, one for the new process' stdin, and one for stdout, create a duplicate of the current process using fork(), close the ends of the pipes we don't need in their respective processes (if we set the O_CLOEXEC option on the pipes, we can skip this for the child process), duplicate the correct ends of the correct pipes to STDIN_FILENO and STDOUT_FILENO using dup2() in the new child process, then replace the child process' image with the image of the program we want using an exec call of some flavour (exet uses execvp()). Once we've done all that, we can read from the pipe ends in the parent process to see and respond to what the child is doing.

If that sounded complicated, remember, that's the easy way. Now lets look at what it takes to set up a PTY.

There are actually a number of ways to open a PTY, some of which are much easier to work with than others. However, because portability is something I strive for, the one we want is the POSIX method, which also happens to be one of the ones that requires a bit more work.

The first thing we need is to open the PTY master using posix_openpt(), which will give us the file descriptor for the PTY master. Next we need to make sure that the slave PTY has the correct owner and permissions by using grantpt() on the master, and if that sounds stupid and pointless, it is, but it's also necessary and a problem, but we'll come back to that. Next we need to unlock the slave PTY, so that we can actually connect something to it, which we do with unlockpt(). Once that's done, we can finally get the path to the slave PTY by using ptsname(), open the slave like any other file, fork() a new child process, attach its standard I/O to the slave PTY using dup2(), just pile we did with the pipes, set the mode of the new PTY, if needed, and exec into the command we want to run.

Okay, so that's all we need to do right? We can just do that.

Right?

Another Bloody Problem:

There is one thing that I haven't talked about, until now, and that's what happens after a child process is running. Or, more specifically, what happens when a process ends.

On UNIX-like systems, when a process dies, it doesn't immediately die completely. Instead, the return code, and the conditions that caused the process to terminate are recorded, and the kernel saves this information in the form of a zombie. These mostly dead processes linger in the systems process table until their parent process waits on them using something like waitpid(). The parent process is notified of its undead children using the SIGCHLD signal, so by catching that signal, and performing a wait, it is able to free the zombie processes, allowing the kernel to put its soul to rest while returning the details of how they died, and what they had to say about it.

Without getting too much into the details of this system, and how absolutely awful it is to actually deal with, know that exet needs to be able to do this for it's child processes. Capturing SIGCHLD, and dealing with the task of waiting on any dead children is something that took a lot of effort to do correctly. It would be really inconvenient if something conflicted with that system.

So...

Remember that grantpt() step?

The grantpt(), unlockpt() combination was designed to deal with a potential security flaw. Particularly, a case when an application goes to reuse a PTY. Most contemporary systems don't have to worry about it, and some, like most BSDs, don't do anything with grantpt(), other than checking that it was passed a valid PTY master. However, on Linux, specifically under glibc, the grantpt() function does do something. In most implementations, it fork-execs an external command to set the owner and permissions of the slave PTY.

Wait. So it forks a new process?

Lets take a look at what the manual has to say:

The behavior of grantpt() is unspecified if a signal handler is installed to catch SIGCHLD signals.

Ah.

Of course!

Why not?!

Why wouldn't it conflict with SIGCHLD?!

Okay, so we can open a PTY, but not in the main exet process, without a lot of extra work to solve a conflict with a system that was already a massive pain to set up. Are we cooked?

Well, there is a way to get around it. We can fork a process using the pipe method first, then use that as a barrier between the main process, and the process connected via PTY. It's more overhead, but we knew what we were getting into. In for a penny, in for a pound.

So then that's it. We spawn a process connected to the main exet process via a pipe, reset all the signal handlers in the new process, create a PTY session, and spawn another process connected via PTY. That will fix all of our problems, right?

Well, remember way back near the start, when I mentioned that a program can explicitly flush its output buffer? It's time to talk about the real problem. It's time to talk about-

The Problem With Prompts:

When an interactive program wants to read something from the user, typically, it expresses this by presenting the user with a prompt. If you've ever used any kind of command line utility, you've almost certainly seen this. It prints something right before the cursor to let you know that it's waiting on your input, and usually telling you something about your environment.

Note that I said before the cursor. A prompt doesn't typically end in a newline.

Do you see the problem yet?

Exet currently will only accept full lines. Partial lines are ignored until a newline is seen. So how do we detect a prompt?

A "Solution":

The answer is, there is no real answer. Any solution we use will have some kind of flaws that we'll need to work around. So, with that in mind, what is the best option?

Well, in a post a few days ago, I mentioned rlwrap. It uses a PTY to help provide a GNU readline wrapper to utilities that don't natively support things like command history and editing. If we take a look at its prompt detection, it uses a timeout (and some other magic that we don't need to worry about). This isn't perfect, but it seems to work well enough.

A naive way to apply this in exet would be to handle the timeout in the process controlling the terminal. That way it could simply append a newline to the current buffer once the timer expires, and send it on as though it were a complete line. However, realistically, we want our exet programs to be aware whether a line is complete, incomplete, or a continuation of an incomplete line. So, with this in mind, we can implement the timeout in the main exet process, then make the details of how "complete" the line was available to our exet programs using special channels. Alright then. We finally have our answer. We have to fork a piped process, which will create a PTY, which will be connected to another process, which will execute our command, which we can then communicate with through the piped process, through the PTY, and if the main process times out waiting for a response from the command, then we submit whatever's currently in the buffer to our exet program, even if there's no newline, while also letting it know how complete the information was. It's done. We know how to fix it.

Conclusions:

So that's it. It's "solved", and the only thing left is to make it happen. It'll be a while, but I will be adding this functionally. The language will never really be complete without it.

I still need to decide on some of the exact details of the implementation, but that's a problem for when I actually go to build it. Until then, I can think about it, and toy with how I can improve this, incredibly flawed, system. The alpha release comes first anyway.

Sorry for the somewhat anticlimactic ending. The post is long enough as it is, and I didn't want to keep dragging it out. If you actually managed to get through this, thank you for taking the time. I hope it was entertaining, and informative, seeing what happens when nothing goes the way you want, and what it takes to overcome these kinds of issues. Feel free to stick around, ask questions, what have you. I'm always happy to share knowledge, and help with whatever I can. I would have done some illustrations, but I didn't have the mental or physical energy. Maybe next time, if anyone actually reads this.

[cincodenada]

So, here's a little peek at the bullshit I've been up to the last couple days:

It's Advent of Code time, which is a series of programming puzzles that Some Guy puts out every December. I've been back on a TIS-100 kick lately, so I decided to see if I could solve the first day in there.

For those unfamiliar, TIS-100 is a programming game. It is not intended as a general-purpose language or environment, it is itself a series of programming puzzles that you have to solve with an incredibly esoteric and limited environment. It's a bespoke assembly language (which is the least human-friendly class of languages*) where you can only use numbers from -999 to 999, the only math operations you have are add and subtract, you have very limited memory, and doing anything complex requires coordinating message-passing between 12 independent "nodes" that are running their own tiny programs, and are only connected to up to four neighbors.

It's an absurd thing to use when trying to solve a problem designed with general-purpose languages in mind, but, when has that ever stopped me?

Anyway, after much shenanigans, I solved both parts of Day 1, entirely in unmodified TIS-100. It did require some preprocessing of the input and summing of partial outputs, since the game only lets you can only run 39 numbers through the system at a time, and the input for the puzzle was over 4000 lines long, but all the actual logic happened in the game. The Part 2 took 20 minutes to run its 2.6 million in-game cycles. Or 200,000, depending on how you look at it. More on that in a minute.

I put all the code up on my Advent of Code repo on GitLab, and I'll go through some of the more interest details of how I managed to get there under the cut.

Getting the Input In

TIS-100 is of course a game, and not intended as a general programming environment. There are emulators that are more general-purpose, but for the challenge, I wanted to stay as close to stock as I could.

The key is that it does let you write your own specifications (puzzles) with arbitrary input and expected output, so there was a way in. It doesn't make the output from the runs programmatically available in any way, but...well, we'll get there.

First, to get all 4000-plus inputs into the 39-slot input buffer, I first had to break them into bite-sized chunks. The specs are Lua scripts, but seemed pretty sandboxed, so I couldn't just read the file in there. Instead, I wrote a python wrapper script that did the chunking, then edited the specification on disk to inject each chunk as a Lua variable. After a run, TIS-100 updates the save file with some stats, so the python script watches the save file for modifications, and when a run finished and updated the save file, it injects the next chunk.

TIS-100 does notice when a specification is edited on disk and reloads it, so with the above that made it possible to run the program, go back to the specification list which triggers reloading the spec with the new input chunk that had been injected in the background, and then go back to the program and run it with the new input.

Getting the Output Out

The remaining problem was that the chunks were not independent - there was a bit of state (a single integer from 0-99) that needed to be preserved from one run to the next. The game is about outputting values, but as mentioned above, there's no way to access those values from outside the game short of screen-scraping, which felt a little against the spirit of things. Was there another way??

I soon realized that there is a sidechannel: that save file that I was watching to trigger the next input injection has, among the stats, the number of cycles taken by the most recent run of a spec. Inspired by things like timing attacks, I wondered: could I manipulate the number of cycles the run took in order to smuggle data out?

It was a very small bit of data: just the one number from 0-99, plus a partial count to be summed at the end, somewhere around 50-100 per chunk. That could easily be encoded into a 4-5 digit number, and my runs were already taking a few thousand cycles...

...the answer, reader, is of course you can! Allow me to introduce you to...

The Cycle Smuggler

this is the funnest part imo

Using just two of my precious twelve nodes, I implemented a system that idles for a set number of cycles, long enough for the rest of the program to process the most complex input chunk.

After the base idle, it takes in the output, (a 3-digit integer `m`) and idles for `100*m` loops, then takes in the state (a 2-digit integer `n`), idles for `n` loops, and immediately terminates.

The result of all of this is that given the base idle cycles, you can extract a 5-digit number `mmmnn` by taking the number of cycles that the program ran and calculating `(cycles - base_count)/3`, where 3 is how many cycles each loop takes - it could be 2, but I left it at 3 for debugging reasons. That number will be something like 12355, which is a count of 123 and a state value of 55.

So that's exactly what my script did: when the save file updated, it extracted the number of cycles taken, extracted the output and state, injected the state back into the input for the next run, and then at the end summed together all the output values to get the final answer.

Actually Running the Thing

After all that nonsense, as well as, you know, writing the actual TIS-100 program (which used 8 more nodes and a total of 119 instructions), I also added mouse emulation to my python script to automate starting each program.

In the end, I started the python wrapper, switched over to TIS-100, loaded the spec, and hit "run" - after that, the python script took over, sending clicks to initiate the next 183 runs, extracting all the partial counts from the cycle counts in the save file after each.

After 20 minutes or so, the script had chunked up all the input, logged its progress, and added up all the counts to get the answer, that I could - finally - put into AoC and cross my fingers.

As happens with AoC, I originally misread the instructions for Part One and actually started implementing what ended up being the solution to Part Two. So I left that node there but unused, and once I retooled it for the simpler version, I ran it with the sample input, then three sample inputs concatenated to test the multi-chunk setup. That all went well so I ran the full input and much to my delight and surprise, got the right answer on the first go!

Part Two was, of course, more hairy - I did have the head start but still had much message-passing to figure. I ended up with one logic bug, and one bug in how I handled the state being passed forward, and a third bug in my chunking up of the input where I tried to give it too many values (and thus dropped some). I first guessed too high, then too low, so I had narrowed the range to about 500, but of course that doesn't help much.

The last bug was the most annoying - I eventually threw some basic checksum-ish checks in the wrapper script, which revealed the dropped inputs, which was then easy enough to fix.

Another fun detail: while TIS-100's integer range of -999 to 999 was a perfect match for the puzzle data, TIS-100's _inputs_ are limited to -99. I ended up encoding e.g. -999 as the pair of (-1, 999), and then reconstruct the original number in situ.

A Footnote on Cycles

Also, the cycle smuggler was originally designed to idle for `n` repeats of a known base count, so that it wouldn't impose a minimum runtime penalty on the main program. But to be able to extract the values, the base count has to be higher than the maximum output value. In my case that was theoretically over 100,000, although in my input it was an actual maximum of 7700.

And thus, since the actual program took comfortably less than 7700 cycles, it was easier to just make it a constant base. I have been scheming ways to make a variable base work, but there's not really a reason to at this point.

So while it took 2.6 million cycles to get the result, that's a bit of a misnomer - most of that time is just idling for very specific amounts of time to smuggle values out. I don't know what the actual runtime was, but base cycle count (and thus maximum runtime) was 3810 cycles, so 184 runs of that would be about 700,000 cycles.

It does look like I got my base time close: running some inputs without the cycle smuggler, it looks like it takes on average about 1100 cycles, with ~3000 cycles max, so it was probably more like 200,000 cycles of actual processing time.

* Programming languages vary a lot, but generally they fall on a spectrum from "easy for a computer to read" to "easy for a human to read" - the human-friendly ("high-level") languages abstract away more of the complexity of what's going on under the hood, and thus the computer has to do more to translate them into commands it can actually execute. The computer-friendly ("low-level") ones represent more directly what's going on under the hood, so the computer has to do less work to translate, with the tradeoff of being much harder to read and write for humans. Assembly is essentially the lowest-level language that humans can interact with, and requires knowing a lot about exactly what the processor is doing underneath all those layers.

[otesunki]

what if i told you

this:

is a Turing Complete Programming Language

[piratesexmachine420]

I don't respect trivial brainfuck substitutions. At least add a new operator. It's not that hard. Come on.

[stkptr]

qoob

qoob (pronounced /kub/ like coob) is a qoobular language, there are 3 qoobic qoobstructures:

0: put a 0 on the qoob

1: put a 1 on the qoob

[ ... ]: remove a bit from the qoob, then loop the contents if it was 1, repeating the check each loop around

qoob can do anything. This is because it is the most qoobish language in the universe.

https://esolangs.org/wiki/qoob

[esoteric-codes]

I have yet to find a residency brave enough to let me perform this language, by continually rearranging all of their stuff

[autistic-sack-of-friends]

no way it's the reference