Highways

Highways is an esoteric programming language created by User:DigitalDetective47 where the program is a highway network.
== Program structure ==
Each Highways program must be a square grid enclosed in a box of #s and the interior area must be at least 2×2. The source file cannot have a trailing newline. Any program that does not conform to the required shape, or contains unrecognized or disallowed characters and/or patterns will not run. Runtime errors should be of the following form:
 BREAKING NEWS
 -------------
 <Insert error message here>
=== Character set ===
This language uses a slightly modified version of wikipedia:Windows-1252 with the MS‐DOS extensions for I/O. Source files should use a standard encoding scheme. The full character table is as follows:
 Character set
 	_0 	_1 	_2 	_3 	_4 	_5 	_6 	_7 	_8 	_9 	_A 	_B 	_C 	_D 	_E 	_F
0_	○ 	■ 	↑ 	↓ 	→ 	← 	║ 	═ 	╔ 	╗ 	╚ 	╝ 	░ 	▒ 	► 	◄
1_	│ 	─ 	┌ 	┐ 	└ 	┘ 	├ 	┤ 	┴ 	┬ 	◆ 	┼ 	█ 	▄ 	▀ 	▬
2_	SP 	! 	" 	# 	$ 	% 	& 	' 	( 	) 	* 	+ 	, 	- 	. 	/
3_	0 	1 	2 	3 	4 	5 	6 	7 	8 	9 	: 	; 	< 	= 	> 	?
4_	@ 	A 	B 	C 	D 	E 	F 	G 	H 	I 	J 	K 	L 	M 	N 	O
5_	P 	Q 	R 	S 	T 	U 	V 	W 	X 	Y 	Z 	[ 	\ 	] 	^ 	_
6_	` 	a 	b 	c 	d 	e 	f 	g 	h 	i 	j 	k 	l 	m 	n 	o
7_	p 	q 	r 	s 	t 	u 	v 	w 	x 	y 	z 	{ 	| 	} 	~ 	HT
8_	Č	€ 	‚ 	ƒ 	„ 	…	†	‡	ˆ 	‰	Š	‹	Œ 	Ÿ 	Ž	ẞ
9_	č	‘ 	’ 	“ 	” 	• 	– 	— 	˜ 	™ 	š	›	œ 	ÿ 	ž	ß
A_	NBSP 	¡ 	¢ 	£ 	¤	¥ 	¦	§ 	¨ 	© 	ª 	« 	¬ 	SHY 	® 	¯
B_	° 	± 	² 	³ 	´ 	µ 	¶ 	· 	¸ 	¹ 	º 	» 	¼	½	¾	¿
C_	À	Á	Â 	Ã	Ä 	Å 	Æ 	Ç 	È	É	Ê 	Ë 	Ì	Í	Î 	Ï
D_	Ð 	Ñ	Ò	Ó	Ô 	Õ	Ö 	× 	Ø	Ù	Ú	Û 	Ü 	Ý	Þ 	NL
E_	à	á	â 	ã	ä 	å 	æ 	ç 	è	é	ê 	ë 	ì	í	î 	ï
F_	ð 	ñ	ò	ó	ô 	õ	ö 	÷ 	ø	ù	ú	û 	ü 	ý	þ 	EOFCLS
=== Cars ===
A car is an entity in a Highways program. Each car has a tape which is infinite in both directions and holds 8‐bit unsigned integers that wrap on both ends. On each step, a car will move one character in its current direction of travel. All cars move at the same time, and signs are executed in a random order. If after moving, multiple cars end up on the same tile facing the same direction, they will crash with the message Crash at (x, y) going direction!, where x is replaced with the x position of the tile where the cars ended up, y is replaced with the y position, with (0, 0) being the top‐left corner, and direction is replaced with the direction that the cars were facing when the crash happened. If multiple crashes occur on the same step, they will all be printed in a random order with only a single BREAKING NEWS header. If a car attempts to enter a non‐road tile, it will crash and crash the program with the message A car has driven off-road at (x, y)!.
=== Roads ===
A simple road tile is one of -/|\; it makes a car that moves onto it move parallel to it. (These are two‐lane roads, so cars don't crash. Also, cars drive on the right.) A road tile on the edge (not including the border of #s) of the program will automatically spawn a car moving away from the edge. A road parallel to the edge cannot be placed on the edge, and a slash cannot be placed in a corner where two cars would spawn (/ banned in top‐left and bottom‐right, and \ banned in top‐right and bottom‐left). If a car moves onto it when it is already travelling parallel to it, nothing happens. If it is moving 45° away from parallel, it is rotated to the closest direction to its current direction. If it is moving perpendicularly to the road, it will choose a direction at random to move in. A bridge is one of +X; it acts as two perpendicular roads on the same tile. It cannot be placed on the edge. A car attempting to drive onto a bridge from a disconnected road will crash with the A car has driven off-road at (x, y)! message. A roundabout is O; it allows cars to choose from multiple paths. It also cannot be placed on the edge. When a car enters a roundabout, it will circulate counterclockwise n+1 times before leaving, where n is the current cell value. It starts by moving onto its own entrance. It circulates by one exit every step. An exit is any road adjacent to the roundabout, regardless of direction. This includes bridges and other roundabouts, except for bridges that are misaligned.
==== Roundabouts: example for clarity ====
Imagine there is a roundabout like this:
 || 
 C| 
 || 
 -- 
 / \ 
 ---| |B--
 D--| |---
 \ / 
 -- 
 |A 
 || 
 || 
(Diagram enlarged for demonstration purposes)Cars A, B, and D have a current cell value of 0, and car C has a current cell value of 1. After one step, it looks like this:
 || 
 || 
 C| 
 -- 
 / \ 
 ---| B---
 -D-| |---
 \ / 
 -A 
 || 
 || 
 || 
After a second, like this:
 || 
 || 
 |B 
 C- 
 / \ 
 ---| |---
 --D| |A--
 \ / 
 -- 
 || 
 || 
 || 
After a third step, cars C and D crash at point #.
 || 
 |B 
 || 
 -- 
 / \ 
 ---| |---
 ---# |-A-
 \ / 
 -- 
 || 
 || 
 ||
=== Signs ===
A car driving down a road will perform certain actions upon reaching a sign. Cars only react to signs directly to their right. Signs on diagonal roads must be placed diagonally from the road tile. The < sign moves the cell pointer one cell to the left. The > sign moves the cell pointer one cell to the right. The ^ sign increments the current cell. The v sign decrements the current cell. The ? sign takes input from the user as a character and stores its value into the current cell. The ! sign prints the current cell as a character. The _ sign has two possible behaviors. If it is empty, the car will push the value of the current cell onto it. If it is full, the car will pop the value on the sign and write it into the current cell. If multiple cars attempt to push at the same time, a value will be selected randomly from the current cell values of each car to be pushed. If multiple cars attempt to pop at the same time, they will all get the value on the sign. The % sign is a yield sign. A car that reaches a yield sign will not move forward until the space in front of it is clear. If a car comes up to another car stopped at a yield sign, it will wait behind the first car. This line can extend arbitrarily long, with no empty spaces between the cars. If multiple cars are yielding to the same empty space, one is chosen at random to move forward, with all others waiting. The @ sign is a stop sign. A car that reaches it will only move forward when the stop sign has multiple cars at it. This means that if one car is stopped for a while, and a second car comes up to the sign from another road, they will both move once the second car reaches the stop sign. Stop signs have the same queueing behavior as yield signs, but any queueing cars beyond the one at the front of the line don't count.
==== Stop sign: example for clarity ====
Imagine there is a network like this:
 -B-A---
 @ 
 ------C
Cars A and B are moving right, and car C is moving left. After one step, the network looks like this:
 --BA---
 @ 
 -----C-
After a second:
 --BA---
 @ 
 ----C--
Note that car A does not move. This is because car B doesn't count for the stipulation of multiple cars present. After a third step, it looks like this:
 --BA---
 @ 
 ---C---
A fourth:
 ---BA--
 @ 
 --C----
Cars A and C move, as in the previous step, there were two cars at the stop sign. After a fifth step, the network looks like this:
 ---B-A-
 @ 
 -C-----
Car B doesn't move because it is the only car at the stop sign. This also means that a stop sign with only one road will stop cars forever.
== Examples ==
=== Hello, world! ===
 #################################################################################################################
 # \ #
 # -\/------------ -\/----- -\/--- -\ -\/- \ #
 # / || \ \ \ \/ || \\ \ / || \ \/ \ / || \ |\ #
 # | \\ | \ |\|| \\ || |\ | \\ |\|| \ | \\ |\-\ \------#
 #--\---O\---O\---O--\---O\---O---------------\----O\ \-O\---\----O\<---------------------------------------\ #
 # -/^ -/|/ -/|/! -/^ |-/|/|^^^^^^^!!^^^!^ -/^^||-/|/||!v -/vv|| >!^^^^^^!vvvvvvvv!^^^!vvvvvv!vvvvvvvv!> \ #
 # | / / | / / / >| // / // | // ^ \ #
 # \--------- \------ \-------- \-- ! \ #
 # \#
 #################################################################################################################
Did not test, may not work.
=== Infinite loop ===
 #######
 #\ #
 # \ O #
 # / #
 # O #
 # #
 #######
=== Truth-machine ===
 #########
 # #
 # O ! #
 #!v \ #
 #--O/ O #
 #?^ v #
 #########
== Computational class ==
Highways can be proven to be Turing-complete as a variant of Boolfuck without I/O can be translated into Highways. This can be accomplished using simple substitutions. + translates to
 #
 
 
 -
 ^
< translates to
 #
 
 
 -
 <
> translates to
 #
 
 
 -
 >
The translation of [] is slightly more complicated.
[ translates to
 ##########
 
 -\ 
 --/---O -
 / | / 
 || \ | 
 \ \-----+-
 \ | 
 -----/ 
] translates to
 ######
 
 
 -\ -
 | / 
 // 
 --/ 
These may need to be extended vertically to accommodate nested brackets, just make sure that each pair lines up correctly.
Category:LanguagesCategory:2021Category:NondeterministicCategory:ProbabilisticCategory:Cell-basedCategory:Concurrent programming
Category:Turing completeCategory:Two-dimensional languagesCategory:UnimplementedCategory:Low-level