Mornington Crescent

Mornington Crescent, named after Mornington Crescent tube station in London and invented by Timwi in 2013 as somewhat of a tribute to the game of Mornington Crescent, is an esoteric programming language in which the data pointer moves through the London Underground by traveling by tube from station to station, starting and ending at Mornington Crescent.

Syntax

Mornington Crescent programs consist of a series of transitions from the current tube station to another, using one of the tube lines available at the current station. For example:

Take Northern Line to Leicester Square
Take Piccadilly Line to King's Cross St. Pancras
Take Circle Line to Westminster

etc.

Only lines matching ^Take (.*) Line to (.*)$ are valid, and the capturing groups must match a valid tube line name and tube station name, respectively.

An optional extra newline at the end of the program is acceptable.

Environment

• During execution, every tube station on the London Underground has a current value, which is either an arbitrary-size integer or a string. Unless otherwise noted below, every station’s value starts out as a string containing that station’s name, for example Waterloo starts out with the value "Waterloo".
• There is an accumulator which is also either an arbitrary-size integer or a string. This starts out with the contents of STDIN as a string.
• The data pointer points at a current station. Execution begins at Mornington Crescent.
• There is also a “jumpstack”, a stack of program locations, which is initially empty.

Valid Mornington Crescent programs must end at Mornington Crescent tube station. If execution moves beyond the last instruction in the program and that instruction does not validly take the data pointer to Mornington Crescent, a runtime error occurs.

Execution

Each instruction is executed as follows:

• If the specified line or tube station doesn’t exist, or the line doesn’t connect the current station with the destination, a runtime error occurs.
• Otherwise:
  • the data pointer is moved to the destination station;
  • the accumulator and the destination station’s value are swapped.

For example, if the first instruction in the program is

Take Northern Line to Leicester Square

then Leicester Square’s value becomes the string read from STDIN and the accumulator’s value becomes "Leicester Square".

However, some of the stations have special behaviour as described below.

Station	Short	Special meaning
Upminster	add	The accumulator’s value is set to the sum of its current value and the station’s current value, if both are integers (otherwise, standard swap).
Chalfont & Latimer	multiply	The accumulator’s value is set to the product of its current value and the station’s current value, if both are integers (otherwise, standard swap).
Cannon Street	integer division	The accumulator’s value is set to the quotient (rounded towards 0) of the station’s current value divided by the accumulator’s current value (or the empty string if the accumulator is 0) if both are integers (otherwise, standard swap).
Preston Road	remainder	The accumulator’s value is set to the remainder of the station’s current value divided by the accumulator’s current value (or the empty string if the accumulator is 0) if both are integers (otherwise, standard swap).
Bounds Green	max	The accumulator’s value is set to the station’s current value only if it is larger, if both are integers (otherwise, standard swap).
Manor House	bitwise NOR (OR+NOT)	Just like the above arithmetic operators, but with bitwise operations. The shift operations only trigger if the shift amount is positive.
Holland Park	bitwise AND
Turnham Green	bitwise shift-right
Stepney Green	bitwise shift-left
Russell Square	square	The accumulator’s value is set to the square of the station’s current value if it is an integer (otherwise, standard swap).
Notting Hill Gate	bitwise NOT	The accumulator’s value is set to the bitwise NOT of the station’s current value if it is an integer (otherwise, standard swap).
Parsons Green	parse string to integer	If the accumulator contains a string, attempts finding and parsing an integer in it. The accumulator is set to the first integer found (or 0 if none), and the station’s value is set to the rest of the string (or ""). (If the accumulator is an integer, standard swap occurs. Note that this condition is inconsistent with other instructions, which decide this based on their current value rather than the accumulator.) Example: If the accumulator value is "a-2b4", the accumulator becomes -2 and the station "b4".
Seven Sisters	7	This station’s value is always 7. The accumulator’s value is set to 7 and its previous value discarded.
Charing Cross	character ↔ codepoint	If the station’s value is a non-empty string, the accumulator is set to the Unicode codepoint of the first character; if it’s the empty string, to 0; if it is an integer, the accumulator is set to the Unicode character with this codepoint.
Paddington	string concatenation	The accumulator is set to the concatenation of the station’s value followed by the accumulator’s previous value, if both are strings (otherwise, standard swap).
Gunnersbury	left substring	If one of the two values is a string s and the other an integer i, the accumulator is set to the string containing the first i characters of s. If i is negative or out of range, a runtime error occurs. If they are both strings or both integers, standard swap occurs.
Mile End	right substring	Like Gunnersbury, but the accumulator is set to the last i characters.
Upney	upper-case	Sets the accumulator to the upper-case of the station’s value if it is a string (otherwise, standard swap).
Hounslow Central	lower-case	Sets the accumulator to the lower-case of the station’s value if it is a string (otherwise, standard swap).
Turnpike Lane	reverse string	Sets the accumulator to the reverse of the station’s value if it is a string (otherwise, standard swap).
Bank		When a value is stored in Bank, Hammersmith is also set to the same value.
Hammersmith		Always retains its current value. The value of the accumulator is discarded and replaced.
Temple	continuation	This station does not have a current value. The accumulator remains unaltered. Landing on this station pushes the current instruction pointer onto the jumpstack.
Angel	if	This station does not have a current value. The accumulator remains unaltered. If the accumulator is the integer 0, nothing happens. Otherwise, execution continues at the instruction stored at the top of the jumpstack (without popping it) and the data pointer is teleported to Temple.
Marble Arch	pop	This station does not have a current value. The accumulator remains unaltered. Landing on this station pops the topmost value off the jumpstack. Nothing else happens.
Mornington Crescent	output/exit	The value of the accumulator is printed and the program is terminated.

Computational class

Mornington Crescent is Turing-complete (assuming the accumulator and station values have truly no maximum value) by translation from the Universal Register Machine model shown in the last section here (a variation of Brainfuck where cells are addressed by register rather than using a tape). The below translation is almost certainly not optimal.

First off, observe it is possible to go to the same station twice in a row, and doing so (for a non-special station) affects neither the station's value nor the accumulator. The map of the London Underground is sufficiently well-connected that this means that you can think of a program as a series of station names, ignoring the lines entirely. In the below translation, stations that have no special properties will be referred as <description>, representing the purpose of the station in the code:

First, get zero, one, and negative one into stations and set the accumulator to 1:

# Get 1 by dividing 7 by itself
Seven Sisters
Cannon Street
Seven Sisters
Cannon Street
Bank
Hammersmith
<1>
# Get zero by failing to find an integer in the name of the station used to represent <1>
Parsons Green
Bank
# Initialize a bunch of stations to zero
Hammersmith
<skipped loop depth>
Hammersmith
# Repeat for each station used to represent a register
<station>
Hammersmith
# End of repeat
# Get -1 by taking the bitwise inverse of zero and store it
Notting Hill Gate
Notting Hill Gate
<-1>
# Set the accumulator to <1>
<1>
Bank
Hammersmith
<1>
Hammersmith

Now we can define some basic operations:

Basic arithmetic operations

Add the accumulator to station <station> (assuming <temp> is a string, and leaving it unchanged). This represents a "+n" in the URM code, and also is used as a subroutine below:

Bank
Hammersmith
<temp>
Upminster
Hammersmith
Upminster
<temp>
<station>
Upminster
<station>
Hammersmith

Multiply the accumulator by -1 (used as a subroutine below) <temp> is any arbitrary station:

<temp>
<-1>
Bank
Hammersmith
Chalfont & Latimer
Hammersmith
<-1>
<temp>
Chalfont & Latimer

A "-n" in the URM is represented by:

• Multiply the accumulator by -1
• Add the accumulator to station <station>
• Multiply the accumulator by -1

Building on that, we can define the following more complicated operations:

- Toggle the accumulator between zero and one:

<Multiply the accumulator by -1>
Notting Hill Gate
Notting Hill Gate
<Multiply the accumulator by -1>

- Multiply the accumulator by the station <station> (set it to zero if either is zero and a nonzero number otherwise)

Chalfont & Latimer
<station>
Bank
Hammersmith
<station>
Hammersmith
Chalfont & Latimer

- Set the accumulator to one if it is a nonzero number (assuming <temp> and <temp2> are strings):

# Divide the accumulator by itself. If it is zero, then this produces the empty string (the defined result of dividing zero by anything). Otherwise it produces an integer (1)
# Cannon Street complains if given a zero so give it a string first
<temp>
Bank
Hammersmith
Cannon Street
Hammersmith
<temp>
Bank
Hammersmith
Cannon Street
Hammersmith
Cannon Street
# Make sure the value of Parsons Green is 1
<temp2>
<1>
Bank
Hammersmith
<1>
Hammersmith
Parsons Green
# Now go to Parsons Green. If the accumulator is a string, it fails to find an integer and sets it to zero. If it's an integer then it swaps and produces 1
<temp2>
Parsons Green

Loops

Since Mornington Crescent provides no reasonable way of skipping instructions, and it's unclear whether do-while loops only suffice for Turing completeness, loops are done by conditionally skipping instructions. Each instruction, including nested loop begins and ends, do nothing if the accumulator is zero, and behave normally if it is one.

The idea is to use one station to represent the "skipped loop depth", and define beginning a loop to be:

• If the skipped loop depth is non-zero, increment it.
• Otherwise, if the station being evaluated is zero, increment the skipped loop depth and set the accumulator to zero.

Ending a loop is:

• If the skipped loop depth is non-zero, decrement it. If this makes the depth zero, set the accumulator to one.
• Otherwise, if the station being evaluated is non-zero jump to the beginning of the loop.

Expressions in <angle brackets> should be substituted with one of the operations defined above.

To begin a loop (representing a ( in the URM code:

<Multiply the accumulator by the station <station the loop is being branched off of>>
# Begin the loop here. The accumulator can be zero at this point, but by definition it cannot be zero if we just jumped there
Temple
<Set the accumulator to one if it is a nonzero number>
# At this point, if the accumulator is one, then we're ready to begin (and execute) the loop. Otherwise we should increment <skipped loop depth> for bookkeeping
<Toggle the accumulator between zero and one>
<Add the accumulator to station <skipped loop depth>>
<Toggle the accumulator between zero and one>

To end a loop (representing a ) in the URM code):

# If the accumulator is zero, make it -1. If it's 1, make is 0
<Multiply the accumulator by -1>
Notting Hill Gate
Notting Hill Gate
<Add the accumulator to station <skipped loop depth>>
# Undo that
Notting Hill Gate
Notting Hill Gate
<Multiply the accumulator by -1>
# If the accumulator is zero (we're in skip mode) then we just decremented the skip depth above and can end the loop. Otherwise branch based off of the station value (the accumulator is one)
<Multiply the accumulator by the station>
# Now actually end the loop
Angel
Marble Arch
# The value of the accumulator is nonsense at this point so rebuild it based on the loop depth - 1 if its 0, 0 otherwise
# This just gets <skipped loop depth> without changing its value
<skipped loop depth>
Bank
Hammersmith
<skipped loop depth>
<Set the accumulator to one if it is a nonzero number>
<Toggle the accumulator between zero and one>
# End of loop

This doesn't define an explicit halt operation and instead is assumed to halt only when code falls off the end of the program. A halt instruction could probably be defined by increasing the skipped loop depth by more than the number of nested brackets so all further instructions are ignored, but the UTM based on URM only has a halt at the end anyway so that should suffice.

There are other esoteric Turing-complete languages that would probably make simpler translation targets using the same basic primitives (i.e the numerical version of Brainpocalypse II).

Forward compatibility

As the validity and the semantics of a program depend on the structure of the London underground system, which is administered by London Underground Ltd, a subsidiary of Transport for London, who are likely unaware of the existence of this programming language, its future compatibility is uncertain. Programs may become invalid or subtly wrong as the transport company expands or retires some of the network, reroutes lines or renames stations. Features may be removed with no prior consultation with the programming community. For all we know, Mornington Crescent itself may at some point be closed, at which point this programming language will cease to exist.

Example

Hello, World!

This program was written by Martin Ender and is only half the length of the language creator’s original version.

Take Northern Line to Hendon Central
Take Northern Line to Bank
Take Northern Line to Bank
Take District Line to Gunnersbury
Take District Line to Victoria
Take Victoria Line to Seven Sisters
Take Victoria Line to Victoria
Take Victoria Line to Victoria
Take District Line to Bank
Take District Line to Hammersmith
Take District Line to Cannon Street
Take District Line to Hammersmith
Take District Line to Cannon Street
Take District Line to Bank
Take District Line to Hammersmith
Take District Line to Upminster
Take District Line to Hammersmith
Take District Line to Upminster
Take District Line to Gunnersbury
Take District Line to Paddington
Take District Line to Acton Town
Take Piccadilly Line to Holloway Road
Take Piccadilly Line to Acton Town
Take Piccadilly Line to Acton Town
Take District Line to Gunnersbury
Take District Line to Hammersmith
Take District Line to Notting Hill Gate
Take District Line to Upminster
Take District Line to Notting Hill Gate
Take District Line to Upminster
Take District Line to Victoria
Take Victoria Line to Seven Sisters
Take Victoria Line to Victoria
Take Victoria Line to Victoria
Take District Line to Upminster
Take District Line to Gunnersbury
Take District Line to Mile End
Take District Line to Hammersmith
Take District Line to Notting Hill Gate
Take District Line to Upminster
Take District Line to Upminster
Take District Line to Mile End
Take District Line to Paddington
Take District Line to Paddington
Take District Line to Acton Town
Take Piccadilly Line to Heathrow Terminals 1, 2, 3
Take Piccadilly Line to Holborn
Take Central Line to Holborn
Take Central Line to Mile End
Take District Line to Upminster
Take District Line to Hammersmith
Take District Line to Upminster
Take District Line to Barking
Take District Line to Hammersmith
Take District Line to Upminster
Take District Line to Gunnersbury
Take District Line to Barking
Take District Line to Gunnersbury
Take District Line to Paddington
Take District Line to Paddington
Take Circle Line to Wood Lane
Take Circle Line to Victoria
Take Circle Line to Victoria
Take District Line to Gunnersbury
Take District Line to Hammersmith
Take District Line to Upminster
Take District Line to Gunnersbury
Take District Line to Paddington
Take District Line to Paddington
Take District Line to Mile End
Take Central Line to Fairlop
Take Central Line to Mile End
Take District Line to Barking
Take District Line to Upminster
Take District Line to Upminster
Take District Line to Hammersmith
Take District Line to Notting Hill Gate
Take District Line to Upminster
Take District Line to Mile End
Take District Line to Gunnersbury
Take District Line to Paddington
Take District Line to Paddington
Take District Line to Hammersmith
Take District Line to Mile End
Take District Line to Richmond
Take District Line to Mile End
Take District Line to Paddington
Take District Line to Paddington
Take District Line to Richmond
Take District Line to Bank
Take District Line to Hammersmith
Take District Line to Upminster
Take District Line to Stepney Green
Take District Line to Hammersmith
Take District Line to Stepney Green
Take District Line to Upney
Take District Line to Notting Hill Gate
Take District Line to Notting Hill Gate
Take District Line to Notting Hill Gate
Take District Line to Upminster
Take District Line to Upney
Take District Line to Upminster
Take District Line to Bank
Take Circle Line to Bank
Take Northern Line to Charing Cross
Take Bakerloo Line to Charing Cross
Take Bakerloo Line to Paddington
Take Circle Line to Bank
Take Circle Line to Bank
Take Northern Line to Mornington Crescent

Interpreters

Esoteric IDE

Interpreter and debugger for many esoteric languages (including Mornington Crescent), written by the author of Mornington Crescent. The sources can be found at GitHub.

Esoterpret

Multi-language interpreter written in Python, as of 2015-10-06 only supporting Mornington Crescent. Open Source and available at GitHub.