User:Katharine Berry/Scripts/Brainfsck

From The SchomEmunity Wiki
< User:Katharine Berry‎ | Scripts
Revision as of 20:51, 9 August 2007 by Katharine Berry (talk | contribs) (First version)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

About

This script interprets the incredibly useless (but Turing-Complete) Brainfsck language.

Usage

Place the script in a prim. Place a notecard containing the program in the same prim. Say "run Program Name" to start it.

If it states that it is awaiting input, provide input on channel 2 (e.g. by saying "/2 11"). It only listens to the owner.

Script

// LSL brainfsck interpreter v1.0.
// Copyright (c) 2007, Katharine Schomer
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above copyright
//       notice, this list of conditions and the following disclaimer in the
//       documentation and/or other materials provided with the distribution.
//     * Neither the name of Katharine Schomer nor the names of any contributors
//       may be used to endorse or promote products derived from this software
//       without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY KATHARINE SCHOMER ``AS IS'' AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL KATHARINE SCHOMER BE LIABLE FOR ANY
// DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// Settings
integer STRIP_COMMENTS = FALSE; // If TRUE, comments will be removed while loading. If FALSE, comments are ignored while running.

// Brainfsck VM
list gBytes = [];
integer gPointer = 0;
string gInputBuffer = "";
string gOutputBuffer = "";
string gProgramCommands = "";
list gLoopPoints = [];
integer gCurrentVal = 0;
integer gCurrentInstruction = 0;

// Interpreter stuff
string ASCII_CHARSET = "§§§§§§§§§§\n§§§§§§§§§§§§§§§§§§§§§ !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~";
string VALID_COMMANDS = "[].,+-<>"; // # is also valid, but isn't included here.
string gProgram = "";
integer gLine = 0;
key gDataserverKey = NULL_KEY;
integer gArraySize = 0;

// Functions
integer GetArrayLength()
{
    return llGetListLength(gBytes);
}

integer GetCurrentCellValue()
{
    return llList2Integer(gBytes,gPointer);
}

SetCurrentCellValue(integer value)
{
    gBytes = llListReplaceList(gBytes,[value],gPointer,gPointer);
}

string chr(integer c)
{
    return llGetSubString(ASCII_CHARSET,c,c);
}

integer ord(string c)
{
    return llSubStringIndex(ASCII_CHARSET,c);
}

RunProgram()
{
    integer i;
    integer length = llStringLength(gProgramCommands);
    llSay(0,"Entering program flow at instruction "+(string)gCurrentInstruction);
    for(i = gCurrentInstruction; i < length; ++i)
    {
        string command = llGetSubString(gProgramCommands,i,i);
        if(command == ">")
        {
            SetCurrentCellValue(gCurrentVal);
            ++gPointer;
            gCurrentVal = GetCurrentCellValue();
        }
        else if(command == "<")
        {
            SetCurrentCellValue(gCurrentVal);
            --gPointer;
            gCurrentVal = GetCurrentCellValue();
        }
        else if(command == "+")
        {
            ++gCurrentVal;
        }
        else if(command == "-")
        {
            --gCurrentVal;
        }
        else if(command ==  ".")
        {
            if(gCurrentVal == 10)
            {
                llSay(0,gOutputBuffer);
                gOutputBuffer = "";
            }
            else
            {
                gOutputBuffer += chr(gCurrentVal);
            }
        }
        else if(command == ",")
        {
            if(gInputBuffer == "")
            {
                gCurrentInstruction = i;
                llSay(0,"Awaiting input: ");
                return;
            }
            else
            {
                gCurrentVal = ord(llGetSubString(gInputBuffer,0,0));
                if(gCurrentVal == 0) gInputBuffer = "";
                else gInputBuffer = llDeleteSubString(gInputBuffer,0,0);
            }
        }
        else if(command == "[")
        {
            if(gCurrentVal != 0)
            {
                gLoopPoints = (gLoopPoints = []) + gLoopPoints + [i];
            }
            else
            {
                integer depth = 1;
                while(i != -1 && depth)
                {
                    command = llGetSubString(gProgramCommands,++i,i);
                    if(command == "[")
                    {
                        ++depth;
                    }
                    else if(command == "]")
                    {
                        --depth;
                    }
                }
                if(command != "]")
                {
                    llSay(0,"FATAL ERROR: Missing ]. Terminating program.");
                    llResetScript();
                }
            }
        }
        else if(command == "]")
        {
            integer len = llGetListLength(gLoopPoints);
            if(len == 0)
            {
                llSay(0,"FATAL ERROR: Encountered ] at "+(string)i+" without leading [. Terminating program.");
                llResetScript();
            }
            i = llList2Integer(gLoopPoints, -1) - 1;
            gLoopPoints = llDeleteSubList(gLoopPoints, -1,-1);
        }
        else if(command == "#")
        {
            llSay(0,"gPointer = "+(string)gPointer+" | gCurrentVal = "+(string)gCurrentVal+" | gInputBuffer = \""+(string)gInputBuffer+"\" | gOutputBuffer = \""+(string)gOutputBuffer+"\"");
            llSay(0,"gLoopPoints = ["+llList2CSV(gLoopPoints)+"]");
            llSay(0,"gBytes = ["+llList2CSV(gBytes)+"]");
        }
    }
    if(gOutputBuffer != "")
    {
        llSay(0,gOutputBuffer);
    }
    llSay(0,"Program execution complete.");
    llResetScript();
}

default
{
    state_entry()
    {
        llSay(0,"Initialising...");
        if(ord("\n") != 10 || chr(10) != "\n" || ord("P") != 80 || chr(80) != "P")
        {
            llSay(0,"Failed system test: ASCII table inaccurate.");
            return;
        }
        for(gPointer = 0; gPointer < 125; ++gPointer)
        {
            gBytes = (gBytes = [])+gBytes+[0,0];
            gArraySize += 8;
        }
        gPointer = 0;
        gDataserverKey = NULL_KEY;
        gLine = 0;
        gProgram = "";
        llSay(0,"Ready. BF VM: 250 bytes free. LSL VM: "+(string)llGetFreeMemory()+" bytes free.");
        llListen(0,"",llGetOwner(),"");
    }
    
    listen(integer channel, string name, key id, string message)
    {
        if(llGetSubString(message,0,3) == "run ")
        {
            string program = llGetSubString(message,4,-1);
            if(llGetInventoryType(program) == INVENTORY_NOTECARD)
            {
                gProgram = program;
                state loading;
            }
            else
            {
                llSay(0,"Could not load "+program+"!");
            }
        }
    }
}

state loading
{
    state_entry()
    {
        llSay(0,"Loading and preprocessing "+gProgram+"...");
        gProgramCommands = "";
        gDataserverKey = llGetNotecardLine(gProgram,gLine++);
    }
    
    dataserver(key id, string data)
    {
        if(id != gDataserverKey) return;
        if(data == EOF)
        {
            llSay(0,"Loaded program ("+(string)llStringLength(gProgramCommands)+" bytes); starting interpreter.");
            state running;
            return;
        }
        data = llStringTrim(data,STRING_TRIM);
        if(STRIP_COMMENTS)
        {
            integer i;
            integer length = llStringLength(data);
            for(i = 0; i < length; ++i)
            {
                string char = llGetSubString(data,i,i);
                if(~llSubStringIndex(VALID_COMMANDS,char))
                {
                    gProgramCommands += char;
                }
            }
        }
        else
        {
            gProgramCommands += data;
        }
        gDataserverKey = llGetNotecardLine(gProgram,gLine++);
    }
}

state running
{
    state_entry()
    {
        llSay(0,"Setting up input stream...");
        llListen(2,"",llGetOwner(),"");
        llSay(0,"I/O ready. Beginning execution now.");
        gCurrentInstruction = 0;
        RunProgram();
    }
    
    listen(integer channel, string name, key id, string message)
    {
        if(message == "EOF")
        {
            gInputBuffer += "§";
        }
        else
        {
            gInputBuffer += message+"\n";
        }
        RunProgram();
    }
}

Hello, World!

This is a nicely commented "Hello world!" in Brainfsck, courtesy Wikipedia. Please note that it takes about a minute to run.

++++++++++
[>+++++++>++++++++++>+++>+<<<<-] The initial loop to set up useful values in the array
>++.                             Print 'H'
>+.                              Print 'e'
+++++++.                         Print 'l'
.                                Print 'l'
+++.                             Print 'o'
>++.                             Print ' '
<<+++++++++++++++.               Print 'W'
>.                               Print 'o'
+++.                             Print 'r'
------.                          Print 'l'
--------.                        Print 'd'
>+.                              Print '!'
>.                               Print newline

Flaws

  • The original compiler had 30,000 bytes of memory. Due to technical restrictions, this version has 250. (Could be raised to ~1000 at the expense of some speed)
  • Due to Second Life limitations, input is line-at-a-time. All input will have a trailing "\n" (ASCII code 10) added to the end. For an EOF, either say "EOF" or "§".
  • Bounds checks, which were originally implemented, were removed for speed reasons.
  • It's inherently slow anyway, given it runs a highly inefficient language on a slow virtual machine.