///

From Esolang
(Redirected from Slashes)
Jump to: navigation, search

/// is a minimalist Turing-complete esoteric programming language, invented by Tanner Swett (User:Ihope127) in 2006 based on the "s/foo/bar/" notation that everybody seemed to be using in IRC. The only operation is repeated string substitution, using the syntax /pattern/replacement/. Despite its extreme simplicity – there isn't even an obvious way to create a loop – it was proved Turing-complete by Ørjan Johansen in 2009, who created an interpreter for the Turing-complete language Bitwise Cyclic Tag.

Description

If the program is empty, execution halts. Otherwise, the first character is taken, and execution proceeds as follows:

  • If the character is \, the character after it (if any) is printed and both characters are removed from the program.
  • If the character is /, it is removed, the pattern and replacement are identified and a substitution is performed.
  • Otherwise, the character is printed and removed.

The execution process then starts over again with the modified program.

Pattern

A substitution starts by reading characters in a loop to make up the pattern, as follows:

  • If the character read is \, the character after it is added to the pattern, and both characters are removed.
  • If the character read is /, it is removed, and the pattern-reading process ends.
  • Otherwise, the character is added to the pattern and removed.

If this process reaches the end of the program without reaching a terminating /, then the program halts.

Replacement

Otherwise, the same process is repeated again, making up the replacement.

  • If the character read is \, the character after it is added to the replacement, and both characters are removed.
  • If the character read is /, it is removed, and the replacement-reading process ends.
  • Otherwise, the character is added to the replacement and removed.

Again, if no terminating / is reached, the program halts.

Substitution

Now that the pattern and replacement have both been read, the substitution process begins.

If the pattern is empty, then the program loops forever (which is the mathematically obvious result of replacing all occurrences of the empty string). If there are no occurrences of the pattern in the rest of the program, then the substitution ends. Otherwise, the first occurrence in the text is replaced by the replacement, and the substitution repeats.

Note that a replacement which contains the pattern will cause an infinite loop; for example, /foo/foobar/foo will evolve as follows (one step per line):

/foo/foobar/foo
foobar
foobarbar
foobarbarbar
...

As the substitution process never ends, the program never halts, and nothing is printed.

Such an infinite loop is possible even without a replacement containing the pattern, e.g. /ab/bbaa/abb:

/ab/bbaa/abb
abb
bbaab
bbabbaa
bbbbaabaa
bbbbabbaaaa
...

The pattern that this sequence follows is bnabbanbn+2aabanbn+2abban+2.

Examples

Hello, world!

A "Hello, world!" program and quine:

Hello, world!

A slightly more elaborate "Hello, world!"

/ world! world!/Hello,/ world! world! world!

Here, the first occurence of " world! world!" is replaced with "Hello,", yielding "Hello, world!". This is then printed.

An even more elaborate "Hello, world!" program, where the first replacement modifies the second:

/foo/Hello, world!//bar/foo/bar

First, foo is replaced with "Hello, world!", yielding /bar/Hello, world!/bar. This turns the bar into "Hello, world!" as well, which is then printed.

99 bottles of beer

/]
[///#/ bottles of beer on the wall,
//$/ bottles of beer
Take one down, pass it around
//%/ bottles of beer on the wall.

/99#99$98%98#98$97%97#97$96%96#96$95%95#95$94%94#94$93%93]
[#93$92%92#92$91%91#91$90%90#90$89%89#89$88%88#88$87%87#87]
[$86%86#86$85%85#85$84%84#84$83%83#83$82%82#82$81%81#81$80]
[%80#80$79%79#79$78%78#78$77%77#77$76%76#76$75%75#75$74%74]
[#74$73%73#73$72%72#72$71%71#71$70%70#70$69%69#69$68%68#68]
[$67%67#67$66%66#66$65%65#65$64%64#64$63%63#63$62%62#62$61]
[%61#61$60%60#60$59%59#59$58%58#58$57%57#57$56%56#56$55%55]
[#55$54%54#54$53%53#53$52%52#52$51%51#51$50%50#50$49%49#49]
[$48%48#48$47%47#47$46%46#46$45%45#45$44%44#44$43%43#43$42]
[%42#42$41%41#41$40%40#40$39%39#39$38%38#38$37%37#37$36%36]
[#36$35%35#35$34%34#34$33%33#33$32%32#32$31%31#31$30%30#30]
[$29%29#29$28%28#28$27%27#27$26%26#26$25%25#25$24%24#24$23]
[%23#23$22%22#22$21%21#21$20%20#20$19%19#19$18%18#18$17%17]
[#17$16%16#16$15%15#15$14%14#14$13%13#13$12%12#12$11%11#11]
[$10%10#10$9%9#9$8%8#8$7%7#7$6%6#6$5%5#5$4%4#4$3%3#3$2%2#2]
[$1 bottle of beer on the wall.
 
1 bottle of beer on the wall,
1 bottle of beer
Take one down, pass it around
No more bottles of beer on the wall.

Note the brackets: these are used to mark unnecessary ("comment") line breaks, and are removed at the beginning of the program. The brackets are not part of the language itself; they are removed by the very first replacement given in the program. The symbols #, $ and % make up a simple data compression scheme which shrinks most of the bulk from the program.

Since characters other than / and \ are used only for printing, they aren't necessary for writing programs. However, they might make good comments as well as data representations, as long as you don't try to execute them. You may want to write code to strip the comments out.

Improved version

/]
[///#/ bottles of beer on the wall,
//!/ bottles of beer
Take one down, pass it around//$/!
//%/ bottles of beer on the wall.

//NL/
/]
[/I/99#99$98%98#98$97%97#97$96%96#96$95%95#95$94%94#94$93%93#93$92%92#92$91%91#91$90%90#90!/]
[/V/NL99%I/]
[I]
[/NL9/NL8/V]
[/NL8/NL7/V]
[/NL7/NL6/V]
[/NL6/NL5/V]
[/NL5/NL4/V]
[/NL4/NL3/V]
[/NL3/NL2/V]
[/NL2/NL1/V]
[/NL1/NL/]
[/NLNL0#0!//]
[/0/No more/]
[/1 bottles/1 bottle/V

This program works similarly to the above one, but with some improvements. First, a substitution is made from NL to a newline. V is replaced with a section of the song, 10 verses long but spanning 11, in which all the numbers have the same tens digit (at first 9, which does not actually exist in the song), and I is replaced with the first such section, which is cut off at the beginning. The first section is printed. Then, a replacement changes the tens digits (identified by being preceded by a newline) to those of the next section, which is then printed. This repeats until the last section, where some extra substitutions handle the changes there.

Binary to unary conversion

/1/0*//*0/0**//0//100010

The above also shows that a single substitution can blow up the size of the program exponentially, even if it halts.

Thue-Morse sequence

/*/\/.\\0\/,\\,0,\\,1\/\/.\\1\/,\\,1,\\,0\/\/,\\,\/.\//********/.//.0

This shows the first 256 digits of the Thue-Morse sequence. Modify number of asterisks to get any power of 2.

Fibonacci sequence

/
///!/\/.\\0\/,\\,0,\\,1\/\/.\\1\/,\\,0\/\/,\\,\/.\/\/+\\+\/=\\=.\\1-\/
\/=\\=\/+\\+\//!!!!!!!!!/.///+\+///-/\\\///0/1//1/*/++.1

This prints the first Fibonacci numbers as sequences of asterisks separated by slashes.

Looping counter

/]
[///+/
/]
[/-\-/|\/|*|-|\/|\\|\\|*|\/|*|-|+|\/|||\\|\\|||\\|\\|||*|||\\|\/|||*|||-|||\]
[/|*|\\|-|\/|\/|*|\\|-|\/|||\\|\\|||\\|\\|||*|||\\|\\|||\\|\\|||*|||\\|\/|||]
[*|||-|||\/|\/|*|+|-|\/|\\|\/|*|\\|\\|+|*|\\|\/|*|\\|\\|-|\\|\/|\\|\/|*|\\|\]
[\|-|\\|\/|*|\\|\\|+|*|*|\\|\\|+|*|\\|\/|\/|*|+|-|*|+|-|*|+|-|*|+|-|*|+|-|*|]
[+|-|*|+|-|\/|*|\\|+|*|\/|\\|\\|*|\/|\/|\\|\\|*|\/|\\|\/|+|\\|\\|+|||*|\\|\/]
[|*|+|+|\\|\/|\\|\/|+|\\|\\|+|||+|\\|\/|+|+|+|\\|\/|\\|\/|+|\\|\\|+|||-|\\|\]
[/|-|+|+|\\|\/|\\|\/|+|\\|\\|+|||||\\|\/|\\|\\|||+|+|\\|\/|\\|\/|+|\\|\\|+||]
[|\\|\\|\\|\/|\\|\/|\\|\\|\\|\/|+|+|\\|\/|\\|\/|+|\\|\\|+|||\\|\\|\\|\\|\\|\]
[/|\\|\\|\\|\\|+|+|\\|\/|\/|*|+|*|*|+|*|*|+|*|*|-|*|-|\/|+|\\|+|||\/|\/|\/||]
[|\\|\\|||\/|\\|||\\|\\|\\|\\|||\/|\/|||\\|\/|||\/|\\|||\\|\\|\\|\/|||\/|\/|]
[-|\\|-|\/|-|-|\/|+|+|-|-|/]
[/*-/\\*/]
[*-+]
[/|\\|\\|*|\/|*|-|/*\-//*\-/|\\|\\|*|\\|\\|*|\/|*|-|/]
[/*+-/\/*\\+*\/*\\-\/\/*\\-\/*\\+**\\+*\//]
[*+-*+-*+-*+-*+-*+-*+-]
[/*\+*/\\*/]
[/\\*/\/+\\+|*\/*++\/\/+\\+|+\/+++\/\/+\\+|-\/-++\/\/+\\+||\/\\|++\/\/+\\+|\]
[\\/\/\\\/++\/\/+\\+|\\\\\/\\\\++\//]
[*+**+**+*]
[*-*-]
[/+\+|//]
[/|\\|/\|\\\\|//|\/|/\|\\\/|/]
[/-\-/--/++--

This program by Ørjan Johansen loops indefinitely, (slowly) printing longer and longer lines of asterisks. It was generated semi-automatically from a Haskell program (but don't panic, to cut short on my usually lethal over-engineering I ended up using no monads outside the main function).

We use the same trick as in the bottles of beer program of inserting line breaks between ][, which are removed at the beginning. We also change all +'s into newlines, although this only affects printing (and was done to save having more different characters in the main loop)

The "obvious" (and perhaps only) way of looping indefinitely in /// is by program self replication, which here happens into the -- spots in the final line. One of the copies needs to be recopied, which means first re-escaping slashes and backslashes, but without clobbering the rest of the program this is hard to do without marking that copy in some way, which here is done by surrounding all the characters by |'s. We make sure not to have literal |/| or |\| anywhere else in the main program.

But then we first need to remove those |'s from the copy of the program that actually "runs" at the next iteration. We cannot do that with a simple substitution, because such a substitution is local and cannot see context enough to avoid clobbering the other copy which needs to preserve the |'s. (This conclusion turns out to be wrong. See the simplified program below.)

The information about which copy is which cannot be inside it, since they are initially identical. Instead we put ++ before the copy that is to be run next. Now to remove the |'s from that copy we have to gradually substitute, using the ++ to scan through the copy.

This requires iteration, but fortunately we don't need an unbounded loop, or else we would have an infinite recursion. Instead we calculate an upper bound for the length of the copy (making sure to include the increasing length of the counter), and make that many copies of the subprogram that scans ++ (at least) one step.

That subprogram itself needs to contain one substitution for each different character used in the main loop, which is why I have kept that number down to six, making the subprogram 71 characters long. We overestimate copied program length a bit for ease of calculation, (3*27+2) on the first iteration, giving a total scanner length of 27406 characters.

Other than this, we make sure to print the counter as asterisks, and increment it in the next iteration program copies.

Simpler counter

/]
/]//] /]//][//]
[/|/<-\\\\>\\\\\\/]
[/QT/]
    [|/R|N|/Q|T|/|/<-|\|\>|/<-|\|\|\|\>|\|\|\|\|/|/<|\->|/|/]
    [C|T|/C|\T|/C|T|/|/*|\
]   [|/I|\N|/|/I|\N|/**|\
]   [|/]
    [|/Q|\T|/Q|T|/R|N]
[/]
[/RN/QT//<-\\>/<-\\\\>\\\\//<\->//]
[/CT/*
/]
[/Q\T/QT/RN

The original counter loop was based on the mistaken belief that it was impossible to distinguish two copies of program code without scanning through them. But after my morning coffee I realized that there was a simple way to distinguish them: Copy one of them again to another place. This will remove some backslashes from just that copy, and if we choose a suitable quoting scheme, we can then do just a few substitutions to turn one copy into the original quoted form, and the other into the final program.

This is much more efficient than scanning, and we also don't need to minimize the number of characters used for efficiency, so the program can use more mnemonic "tokens".

The quoting scheme used here is as follows for a character c:

   |c          original quoted program source
   <-\\>\\\c   runtime quoted form
   <-\>\c      after copying once
   <->c        after copying twice
   c           "runnable" code

Using three characters <-> gives a slightly shorter set of substitutions and saves a total of 5 characters in the source program compared to just <>, at the cost of a longer runtime program. A version using only <> can be found here.

While it should be harmless to quote all characters, this is not necessary. / and \ need quoting, and there should be a quoting break inside any "tokens" or other strings that are substituted in the main program, so that their quoted form is not affected unless that is what you actually want. As usual some care must be taken to avoid confusing any strings, in particular | and <-> cannot occur in the unquoted program with this scheme.

Bitwise Cyclic Tag interpreter

This interpreter for the language Bitwise Cyclic Tag was generated using this Haskell program. The BCT program and data can be changed by modifying the strings after (P| and (D| near the beginning. (The empty program and the program containing just 1 are not supported.) As the BCT page suggests is enough for Turing-completeness, it (slowly!) prints out the sequence of deleted data bits as 0 = /, 1 = \.

All characters except / and \ are replaced before the main loop is entered, showing that /// is Turing-complete even when restricted to those two characters.

Quine

Since any /// program not containing / or \ is trivially a quine, here is one containing only / and \.

/\/\/\/\\\\/\\\\\\\/\\\\\\\/\\\\\\\/\\\\\\\\\\\\\\\\\\\\\\//\/\/\/\\\/\/\\////\\////\\\///\\////\\\///\\////\\\///\\////\\\///\\\///\\\///\\\///\\////\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\////\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\////\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\////\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\////\\////\\\///\\////\\\///\\////\\\///\\////\\\///\\\///\\\///\\////\\\///\\////\\\///\\\///\\////\\////\\////\\////\\\///\\////\\\///\\////\\////\\\///\\////\\////\\\///\\////\\\///\\////\\\///\\////\\\///\\\///\\\///\\////\\\///\\\///\\\///\\////\\\///\\\///\\////\\////\\////\\////\\\///\\////\\////\\\///\\////\\////\\\///\\////\\\///\\////\\\///\\////\\\///\\\///\\\///\\\///\\////\\\///\\\///\\////\\////\\\///\\\///\\\///\\////\\\///\\\///\\\///\\////\\\///\\\///\\\///\\////\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\////\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\////\\\///\\\///\\\///\\////\\\///\\\///\\\///\\\///\\////\\////\\////\\////\\\///\\////\\////\\\///\\////\\////\\\///\\////\\\///\\////\\\///\\////\\\///\\\///\\\///\\\///\\////\\\///\\\///\\\///\\////\\\///\\\///\\\///\\////\\\///\\\///\\\///\\////\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\\///\\////\\////\\////\\////\\\///\\////\\\///\\////\\\//\/\/\/\\\/\\\/\\////\//\//\/\/\/\\\\/\\//\\\/\\\/\\\/\\\\\\\/\\\\\\\/\\\/\\\\////\//\//\/\/\/\\\\/\\\/\\\/\\\/\\\\\\\\\\////\/\/\

Implementation

The below implementation is appropriately written in the Perl language, well-known for also supporting a /// construction.

#!/usr/bin/perl -w

my $debug =
    ($#ARGV >= 0 and $ARGV[0] =~ m/^-d([1-2]?)$/ and shift and ($1 || 1));
$| = 1;

$_ = join '', <>;
while (1) {
        print "\n[", $_, "]" if $debug == 1;
        if (s!^([^/\\]+)!! or s!^\\(.)!!s) {
                print($1);
                print "\n[", $_, "]" if $debug == 2;
        }
        elsif (s!^/((?:[^/\\]|\\.)*)/((?:[^/\\]|\\.)*)/!!s) {
                my ($s,$d) = ($1,$2);
                $s =~ s/\\(.)/$1/gs;
                $d =~ s/\\(.)/$1/gs;
                while (s/(?:\Q$s\E)/$d/) { }
        }
        else { last; }
}

More interpreters can be found on Programming puzzles & code golf Stack Exchange.

See also