Lost

Lost is a 2-Dimensional language where the instruction pointer starts at a random location, moving in a random direction. Despite this, Lost is still capable of creating completely deterministic programs. Lost was designed by Programming Puzzles and Code-Golf user WheatWizard

Description

Lost, like many 2D languages, operates on a grid where each instruction is a character of the source. Lost's instruction pointer (ip) moves through the grid in one of the four cardinal directions. When it goes off one side of the grid it wraps around to the other as if the program were written on a torus.

Lost's memory is stored in a main stack and a scope. Both are stacks padded with zeros at the bottom. At the end of execution the contents of the main stack are printed and the scope discarded. Lost also stores a single value called the "safety", which begins on.

Programs can only terminate when the safety is off. The safety feature allows Lost to make deterministic programs, without it it would be impossible to make any deterministic program other than a cat program and a program that never halts.

Lost mostly borrows its instruction set from Klein.

Mirrors

• \ Swaps the x and y directions

• / Swaps the x and y directions and multiplies them by -1

• | Multiplies the horizontal direction by -1

Directions

• > Tells the ip to move east

• < Tells the ip to move west

• v Tells the ip to move south

• ^ Tells the ip to move north

Doors

• [ Reflects the ip if it is moving east; becomes ] if the ip is moving horizontally

• ] Reflects the ip if it is moving west; becomes [ if the ip is moving horizontally

Jumps

• ! Skips the next operation

• ? Pops off the top of the stack and jumps if not zero

Stack manipulation

• : Duplicates the top of the stack

• $ Swaps the top two items of the stack

• ( Pops from the stack and pushes to the scope

• ) Pops from the scope and pushes to the stack

Literals

• 0-9 pushes n to the top of the stack

• " Starts and ends a string literal. During a string literal commands are not run and instead their character values are pushed to the stack.

Operations

• + Adds the top two numbers

• * Multiplies the top two numbers

• - Multiplies the top by -1

Control

• % Turns the safety off

• # Turns the safety on

• @ Ends execution if the safety is off (starts on)

Deterministic programming in Lost

Since the ip can start anywhere going anywhere, it can be quite hard to make a program that does anything. This section will be a walk through on making your first Lost program. For the purposes of demonstration we are going to make a program that prints

Hello, World!

The first thing we are going to want to do is create a program that prints Hello, World! if it starts at a particular position.

%"Hello, World!"@

This works if we start in on the left side going right. Now we make a line of arrows to point the ip so it will end up in that place.

v<<<<<<<<<<<<<<<<<
>%"Hello, World!"@

Anything that lands in that "stream" will flow to the start of the program and begin execution. The only problem is not everything gets caught in the stream. If we start inside the string moving left, our ip will never touch the stream unless it is in string mode. In order to fix this we need a v or ^ somewhere in the string. But since neither of those is actually in in the string we want to print we need to get rid of it afterwards.

v<<<<<<<<<<<<<<<<<<<
>%"Hello, World!v"(@

However we still have some problems, the first is that if we start on ! going up or down we will loop forever. So we get rid of the !, instead we make it by computing v-U.

v<<<<<<<<<<<<<<<<<<<<
>%"Hello, WorldvU"-+@

Our last problem is that we sometimes accumulate garbage we don't want in our final product before we arrive at the start of execution. To fix this we just eat everything on the stack that is not zero (this only works because the garbage never contains a zero).

v<<<<<<<<<<<<<<<<<<<<<<<
>%?!<"Hello, WorldvU"-+@

The code >&?!< acts our loop, discarding values until it discards a zero.

This doesn't work because the ! can jump to itself over the top or bottom of the program when the ip starts on it moving either up or down. This will cause an infinite loop. We can fix two ways. The first way, which works in most scenarios, is to another stream below to catch this specific pointer.

v<<<<<<<<<<<<<<<<<<<<<<<
>%?!<"Hello, WorldvU"-+@
^<<<

With this new stream our program has now covered all the possibilities and is deterministic.

However if we want to be a bit more clever and save a few bytes we can do away with ! entirely. We replace our loop with <%?.

v<<<<<<<<<<<<<<<<<<<<<
>%?"Hello, WorldvU"-+@

Since there is a v later on the line which sends us back to the begining of the loop our ? will reset the loop if the top of the stack is non-zero, while if it is zero it will hit " and complete the program as intended.

As a general strategy to write a program in Lost one

• Writes a program that works from a particular starting point,
• Adds a stream to collect most of the pointers,
• Makes changes to the original program to fix problems with specific start locations.

Example programs

Add two numbers

v<<<
>%+@

Hello World

The shortest known program to deterministically print Hello, World! was discovered by code golf stack-exchange user Wheat wizard. It is 36 bytes long.

roW"\\ dl
<@+1(\
lo, /"Hel
%<<<\?<<<

Wheat wizard also discovered a 37 byte hello world:

<\<@+-\
WorldP/" 
(/"Hello,
?/%>>>(>>

A much more straightforward 38 byte program was discovered by code golf stack exchange user JoKing.

>/-+@>>>>>>>>>>
P/"Hello, World
?/>>>%

Quine

>:2+52*:6*:(84*+75*):>:::::[[[[[[[:[(52*)>::::[[[[[[:[84*+@>%?!<((((((((((([[[[[[[[[[[[[[ "
\#<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\

Interpreter

• The original interpreter in Python

See also

• My Unreliable Past