-5
\$\begingroup\$

In this challenge, you get to create a language. Although you have to provide code in other languages, you will only be rated based on the language. Here are the requirements.

  1. You must invent a programming language that is Turing complete.
  2. You will choose a real (as in existed before this question did) language. It must be a different paradigm then the made up language.
  3. You will write a boot strapping compiler. This means you write a program in your new language, that will take code in your new language, and translate it to code in your real language.
  4. So people can run it initially, you will provide an interpreter (or compiler) in a real language (which may or may not be written the real language you choose above) to run programs in the new language. This does not need to be golfed.

Note: Your language can't have builtin functions for generating code in the real language. This basically means that if the real language were proprietary, your language wouldn't violate its copyright by making it to easy to generate its code.

Scoring:

Your score is the size of your compiler. Your will find your programs' sizes using roundup(s*log_2(a)) where s is the number of characters in your program and a is the number of available characters in your language (meaning huge penalties if you use Chinese characters or something.)

Tip: String characters count too, so if you are looking to really shrink how many characters are available, you will need to find a way to represent strings with few characters.

Smallest score wins!

So in summary, you invent a turing-complete language X. Then you implement an interpreter or compiler for it in Y. Finally, you implement a compiler for X in X itself. (Based on a comment from Victor.)

\$\endgroup\$

closed as too broad by Justin, plannapus, manatwork, Peter Taylor, VisioN Feb 25 '14 at 13:46

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    \$\begingroup\$ Well, this will take a considerably large amount of time... \$\endgroup\$ – Ismael Miguel Feb 24 '14 at 23:50
  • 2
    \$\begingroup\$ What if the language isn't character based, like Piet? \$\endgroup\$ – Victor Stafusa Feb 25 '14 at 0:01
  • 9
    \$\begingroup\$ So this is basically 1. Invent a turing-complete language X. 2. Implement an interpreter or compiler for it in Y. 3. Implement a compiler for X in X itself. Got it right? \$\endgroup\$ – Victor Stafusa Feb 25 '14 at 0:11
  • 4
    \$\begingroup\$ According to the rules, taking C and swapping { and } would be a valid entry? You may have a tough time coming up with a definitive line for how different the languages have to be. \$\endgroup\$ – Kendall Frey Feb 25 '14 at 0:45
  • 2
    \$\begingroup\$ Aw man, why is this closed? It's one of the only genuinely interesting challenges I've seen on this site. \$\endgroup\$ – Nathaniel Jul 1 '14 at 10:18
9
\$\begingroup\$

Brainfuckoff -> Javascript, 527 characters, 3463 points

My language, Brainfuckoff is a brainfuck-derived language with the following changes:

  • It has a new instruction * which sends everything in input to the output, until the end-of-input is reached.
  • It has a new instruction ^ which sends everything following this and before the following backtick to the output.
  • It takes a line of the input at a single shot in the start of the program, consuming each char with the , instruction.

So, here is a partially-golfed javascript compiler for my language:

function bfg(j){
  w=String.fromCharCode;
  r='(function(n){m=[];p=0;c=0;t=n.substring(0,0);';
  for(x=0;x<j.length;x++){
    q=j.charCodeAt(x);
    if(q==91)r+='while(~~m[p]){';
    if(q==93)r+='}';
    if(q==62)r+='p++;';
    if(q==60)r+='p--;';
    if(q==43)r+='m[p]=1+~~m[p];';
    if(q==45)r+='m[p]=-1+~~m[p];';
    if(q==46)r+='t+=String.fromCharCode(~~m[p]);';
    if(q==44)r+='if(c<n.length)m[p]=n.charAt(c++);';
    if(q==94){z=j.indexOf(w(96),x+1);r+='t+='+w(34)+j.substring(x+1,z)+w(34)+';';x=z}
    if(q==42)r+='t+=n.substring(c);c=n.length;'
  }
  return r+'return t})'
}

Here is a brainfuck Hello World program:

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

Compiling it:

program = '++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.';
jsprogram = bfg(program);
alert(jsprogram);

The output:

 (function(n){m=[];p=0;c=0;t=n.substring(0,0);m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];while(~~m[p]){p++;m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];while(~~m[p]){p++;m[p]=1+~~m[p];m[p]=1+~~m[p];p++;m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];p++;m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];p++;m[p]=1+~~m[p];p--;p--;p--;p--;m[p]=-1+~~m[p];}p++;m[p]=1+~~m[p];p++;m[p]=1+~~m[p];p++;m[p]=-1+~~m[p];p++;p++;m[p]=1+~~m[p];while(~~m[p]){p--;}p--;m[p]=-1+~~m[p];}p++;p++;t+=String.fromCharCode(~~m[p]);p++;m[p]=-1+~~m[p];m[p]=-1+~~m[p];m[p]=-1+~~m[p];t+=String.fromCharCode(~~m[p]);m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];t+=String.fromCharCode(~~m[p]);t+=String.fromCharCode(~~m[p]);m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];t+=String.fromCharCode(~~m[p]);p++;p++;t+=String.fromCharCode(~~m[p]);p--;m[p]=-1+~~m[p];t+=String.fromCharCode(~~m[p]);p--;t+=String.fromCharCode(~~m[p]);m[p]=1+~~m[p];m[p]=1+~~m[p];m[p]=1+~~m[p];t+=String.fromCharCode(~~m[p]);m[p]=-1+~~m[p];m[p]=-1+~~m[p];m[p]=-1+~~m[p];m[p]=-1+~~m[p];m[p]=-1+~~m[p];m[p]=-1+~~m[p];t+=String.fromCharCode(~~m[p]);m[p]=-1+~~m[p];m[p]=-1+~~m[p];m[p]=-1+~~m[p];m[p]=-1+~~m[p];m[p]=-1+~~m[p];m[p]=-1+~~m[p];m[p]=-1+~~m[p];m[p]=-1+~~m[p];t+=String.fromCharCode(~~m[p]);p++;p++;m[p]=1+~~m[p];t+=String.fromCharCode(~~m[p]);p++;m[p]=1+~~m[p];m[p]=1+~~m[p];t+=String.fromCharCode(~~m[p]);return t})

Running that:

program = '++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.';
input = '';
jsprogram = bfg(program);
alert(eval(jsprogram)(input));

The output:

Hello World!

This other brainfuckoff's Hello World is simpler:

program = '^Hello World!`'
input = '';
jsprogram = bfg(program);
alert(eval(jsprogram)(input));

The output:

Hello World!

Great, now a compiler of brainfuckoff to javascript written in brainfuckoff (527 characters):

^(function(j){w=String.fromCharCode;r='(function(n){m=[];p=0;c=0;t=n.substring(0,0);';for(x=0;x<j.length;x++){q=j.charCodeAt(x);if(q==91)r+='while(~~m[p]){';if(q==93)r+='}';if(q==62)r+='p++;';if(q==60)r+='p--;';if(q==43)r+='m[p]=1+~~m[p];';if(q==45)r+='m[p]=-1+~~m[p];';if(q==46)r+='t+=String.fromCharCode(~~m[p]);'; if(q==44)r+='if(c<n.length)m[p]=n.charAt(c++);';if(q==94){z=j.indexOf(w(96),x+1);r+='t+='+w(34)+j.substring(x+1,z)+w(34)+';';x=z}if(q==42)r+='t+=n.substring(c);c=n.length;'}return eval(r+'return t})')})('`*^')`

Compiling the compiler:

program = "^(function(j){w=String.fromCharCode;r='(function(n){m=[];p=0;c=0;t=n.substring(0,0);';for(x=0;x<j.length;x++){q=j.charCodeAt(x);if(q==91)r+='while(~~m[p]){';if(q==93)r+='}';if(q==62)r+='p++;';if(q==60)r+='p--;';if(q==43)r+='m[p]=1+~~m[p];';if(q==45)r+='m[p]=-1+~~m[p];';if(q==46)r+='t+=String.fromCharCode(~~m[p]);'; if(q==44)r+='if(c<n.length)m[p]=n.charAt(c++);';if(q==94){z=j.indexOf(w(96),x+1);r+='t+='+w(34)+j.substring(x+1,z)+w(34)+';';x=z}if(q==42)r+='t+=n.substring(c);c=n.length;'}return eval(r+'return t})')})('`*^')`";
jsprogram = bfg(program);
alert(jsprogram);

The compiled compiler:

(function(n){m=[];p=0;c=0;t=n.substring(0,0);t+="(function(j){w=String.fromCharCode;r='(function(n){m=[];p=0;c=0;t=n.substring(0,0);';for(x=0;x<j.length;x++){q=j.charCodeAt(x);if(q==91)r+='while(~~m[p]){';if(q==93)r+='}';if(q==62)r+='p++;';if(q==60)r+='p--;';if(q==43)r+='m[p]=1+~~m[p];';if(q==45)r+='m[p]=-1+~~m[p];';if(q==46)r+='t+=String.fromCharCode(~~m[p]);'; if(q==44)r+='if(c<n.length)m[p]=n.charAt(c++);';if(q==94){z=j.indexOf(w(96),x+1);r+='t+='+w(34)+j.substring(x+1,z)+w(34)+';';x=z}if(q==42)r+='t+=n.substring(c);c=n.length;'}return eval(r+'return t})')})('";t+=n.substring(c);c=n.length;t+="')";return t})

Running the compiled compiler to compile the first Hello World:

program1 = "^(function(j){w=String.fromCharCode;r='(function(n){m=[];p=0;c=0;t=n.substring(0,0);';for(x=0;x<j.length;x++){q=j.charCodeAt(x);if(q==91)r+='while(~~m[p]){';if(q==93)r+='}';if(q==62)r+='p++;';if(q==60)r+='p--;';if(q==43)r+='m[p]=1+~~m[p];';if(q==45)r+='m[p]=-1+~~m[p];';if(q==46)r+='t+=String.fromCharCode(~~m[p]);'; if(q==44)r+='if(c<n.length)m[p]=n.charAt(c++);';if(q==94){z=j.indexOf(w(96),x+1);r+='t+='+w(34)+j.substring(x+1,z)+w(34)+';';x=z}if(q==42)r+='t+=n.substring(c);c=n.length;'}return eval(r+'return t})')})('`*^')`";
jsprogram1 = bfg(program1);
input1 = '++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.'
jsprogram2 = eval(jsprogram1)(input1);
input2 = '';
alert(eval(jsprogram2)(input2));

The output:

Hello World!

Calculating the score:

roundup(527 * log_2(asciiCharOf('~') - asciiCharOf(' ') + 1))
roundup(527 * log_2(126 - 32 + 1))
roundup(527 * log_2(95))
roundup(527 * 6.5698556083309478416638388523962)
roundup(3462.3139055904095125568430752128)
3463

Note: There are indeed some ways to reduce the size of the interpreter in maybe ~20%. But this was already hard enough to do for me.

\$\endgroup\$
  • 2
    \$\begingroup\$ Very nice, exactly what I intended. You rounded up incorrectly though. \$\endgroup\$ – PyRulez Feb 25 '14 at 15:11
  • 1
    \$\begingroup\$ @PyRulez Fixed. Sorry for the mistake, I was a bit nervous at the time. \$\endgroup\$ – Victor Stafusa Feb 25 '14 at 15:17
  • 1
    \$\begingroup\$ @PyRulez Since it is unlikely that this question will get any more attention, and since my answer is the only answer that is complete, detailed, not abusing the scoring, and meeting your expectations, could you please accept it? \$\endgroup\$ – Victor Stafusa Feb 27 '14 at 23:51
  • \$\begingroup\$ Nice name (just get rid of brain from it) \$\endgroup\$ – User that is not a user Apr 15 '18 at 0:23
5
\$\begingroup\$

Score = (Number too long for an SE post * log_2(1)) = 0

Given how the score is weighted by the number of characters available in the language, the less the better:

1.) My language (X) is called Compressed Unary. It is similar to Unary in that it only has one available character in the language. Unlike Unary, it uses the number "1" instead of "0". It improves on Unary by assigning the operators in a different bit order, with lower values assigned to operations that occur more often. It is proven to be Turing complete in that it can be trivially converted to Brainfuck.

The code is a string of 1s, and the length of the code determines the logic (see the description of Unary from the link above for more details. The encoding is as follows:

Brainfuck   Binary
+           (1000)
-           (1001)
>           (1010)
<           (1011)
.           (1100)
,           (1101)
[           (1110)
]           (1111) 

All the binary is combined from left to right and the resulting number is how many "1"s should be in the source code. This should yield much smaller code that Unary, but will absolutely suck as a golfing language. Much better for code bowling (see the compiler below and you'll see why).

2.) I chose C#. It was easy, I could port an existing BF implementation (props to the original author), and given that log_2(1) is zero, the length of the code doesn't have any effect my score.

3.) The source code is too long to include here (stupid 30k character limit), in fact the number is too long to post here (it is 123411 characters in hex notation). The following link will give you the number in hex. You can create the bootstrap compiler simply by typing that many ones in a text file. Like I said, this completely sucks as a golfing language. It's much worse than C# for golfing.

4.) Once you type out the source code (I'd include a download link, but it would take way too long even on a fast fiber connection), you can run it through the following interpreter:

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;

namespace CompressedUnary
{
    class Program
    {
        static void Main(string[] args)
        {
            BigInteger code = new BigInteger(0);
            int next = 0;

            try
            {
                using (FileStream source = new FileStream(args[0], FileMode.Open, FileAccess.Read))
                {
                    next = source.ReadByte();
                    while (next != -1)
                    {
                        if (next != 49)
                        {
                            System.Console.WriteLine("Syntax error.");
                            break;
                        }
                        code += 1;
                        next = source.ReadByte();
                    }
                }
            }
            catch (FileNotFoundException oops)
            {
                Console.WriteLine(oops.Message);
            }

            if (next == -1)
            {
                string processed = PreProcess(code);
                Interpreter runner = new Interpreter(Console.OpenStandardInput(), Console.OpenStandardOutput());
                runner.Run(processed);
            }
            Console.WriteLine("Done");
        }

        static string PreProcess(BigInteger input)
        {
            StringBuilder output = new StringBuilder("");
            BigInteger current;

            while (input > 0)
            {
                BigInteger.DivRem(input, 16, out current);
                switch ((int)current)
                {
                    case 0:    
                        output.Append("+");
                        break;
                    case 1:    
                        output.Append("-");
                        break;
                    case 2:    
                        output.Append(">");
                        break;
                    case 3:    
                        output.Append("<");
                        break;
                    case 4:
                        output.Append(".");
                        break;
                    case 5:
                        output.Append(",");
                        break;
                    case 6:
                        output.Append("[");
                        break;
                    case 7:
                        output.Append("]");
                        break;
                }
            }
            return output.ToString();
        }

        enum ILCode : byte
        {
            NextCell = (byte)'>',
            LastCell = (byte)'<',
            Increment = (byte)'+',
            Decrement = (byte)'-',
            Output = (byte)'.',
            Input = (byte)',',
            BeginLoop = (byte)'[',
            EndLoop = (byte)']'
        }

        class Machine
        {
            public int pointer = 0;
            private int cell = 0;
            private readonly byte[] cells;
            private readonly Stack<int> stack = new Stack<int>();

            public Machine(int memory)
            {
                cells = new byte[memory];
            }

            public byte CurrentCell
            {
                get { return cells[cell]; }
                set { cells[cell] = value; }
            }

            public void Increment()
            {
                if (CurrentCell == 255)
                    CurrentCell = 0;
                else
                    CurrentCell++;
                pointer++;
            }

            public void Decrement()
            {
                if (CurrentCell == 0)
                    CurrentCell = 255;
                else
                    CurrentCell--;
                pointer++;
            }

            public void NextCell()
            {
                cell++;
                pointer++;
            }

            public void LastCell()
            {
                cell--;
                pointer++;
            }

            public void BeginLoop()
            {
                stack.Push(pointer);
                pointer++;
            }

            public void EndLoop()
            {
                if (CurrentCell == 0)
                    pointer++;
                else
                    pointer = stack.Pop();
            }
        }

        class Interpreter
        {
            private readonly Stream output;
            private readonly StreamReader reader;
            private readonly Dictionary<byte, Action> actions;
            private readonly Machine machine;

            public Interpreter(Stream ioin, Stream ioout, int memorySize = 30000)
            {
                output = ioout;
                reader = new StreamReader(ioin);
                machine = new Machine(memorySize);
                actions = new Dictionary<byte, Action>
                    {
                        {(byte) ILCode.BeginLoop, machine.BeginLoop},
                        {(byte) ILCode.EndLoop, machine.EndLoop},
                        {(byte) ILCode.Increment, machine.Increment},
                        {(byte) ILCode.Decrement, machine.Decrement},
                        {(byte) ILCode.NextCell, machine.NextCell},
                        {(byte) ILCode.LastCell, machine.LastCell},
                        {(byte) ILCode.Input, InputCurrentByte},
                        {(byte) ILCode.Output, OutputCurrentByte},
                    };
            }

            public void Run(string program)
            {
                byte[] instructions = program.Select(c => (byte)c).Where(b => actions.ContainsKey(b)).ToArray();
                while (machine.pointer < instructions.Length)
                {
                    Action action = actions[instructions[machine.pointer]];
                    action.Invoke();
                }
                byte[] newLine = Environment.NewLine.Select(c => (byte)c).ToArray();
                output.Write(newLine, 0, newLine.Length);
            }

            private void InputCurrentByte()
            {
                byte next = (byte)reader.Read();
                machine.CurrentCell = next;
                machine.pointer++;
            }

            private void OutputCurrentByte()
            {
                output.WriteByte(machine.CurrentCell);
                machine.pointer++;
            }
        }
    }
}

FORE!

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice exploit. I should have added log_2 of the length, but too late now. \$\endgroup\$ – PyRulez Feb 25 '14 at 13:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.