-3 language

-3.md

-3

Here's the gist.

Memory

Memory is a map of tapes, where the keys are strings and values are arbitrary-sized integers.

Additionally, there is a set of labels, where the program can jump to.

There is a stack, which contains the operands, which are strings.

There is an offest, which controls where in the memory's tapes it can access.

The One Instruction

-. First, it pops a string LABEL off the stack. If that LABEL is undefined as a label, it defines the label, and clears the source of that label (i.e. where it was pushed from) and the current instruction. Otherwise, it performs the following calculation, using the top two values, A and B:

if mem[A] < mem[B]:
    jump to LABEL
if mem[A] != mem[B]:
    mem[A]--
else:
    mem[B]++

The offset can be modified by accessing the value of ..

Example code

X-

i i X-
i i X-
i i X-
i i X-
i i X-
i i X-
i i X-

This sets variable i to 7, by incrementing 7 times.

X-

i i X-
i i X-
i i X-
LOOP-
    a a X-
    a a X-
    j i LOOP-

This multiplies i+1 by the constant 2.

Proof of Turing Completeness

Disregarding C++'s int sizes (that is, assuming they are infinite), -3 is Turing Complete by reduction to 3-cell brainfuck. I can disregard this size because there can be written an interpreter for -3 on a computer with infinite memory that has arbitrarily-large cells.

I also believe that any BCT can be written as a -3 program.

n3.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <cctype>
#include <exception>

static const char ONE_OP = '-';
static const std::string OFFSET = ".";

enum class TokenType { DATA, OPERATOR, NO_OP };
static std::string type_reprs[] = { "DATA", "OPERATOR", "NO_OP" };

struct Token {
    std::string     raw;
    TokenType       type;
    size_t          start;
};

void show_token(Token t) {
    std::cout << "Token("   << t.raw
              << ", "       << type_reprs[(int)t.type]
              << ", "       << t.start
              << ")"        << std::endl;
}

template <class T>
void show_map(std::map<int, T> m, size_t pad) {
    for(auto it = m.begin(); it != m.end(); it++) {
        std::cout << std::string(pad, ' ');
        std::cout << it->first << ": " << it->second << std::endl;
    }
}
template <class T>
void show_map(std::map<int, T> m) {
    show_map(m, 4);
}

std::vector<Token> tokenize(std::string str) {
    std::vector<Token> res;
    
    size_t i = 0;
    while(i < str.size()) {
        Token build;
        char c = str[i];
        build.start = i;
        
        if(isalpha(c)) {
            while(isalpha(c)) {
                build.raw += c;
                c = str[++i];
            }
            build.type = TokenType::DATA;
        }
        else if(c == ONE_OP) {
            build.raw += c;
            build.type = TokenType::OPERATOR;
            i++;
        }
        else if(isspace(c)) {
            build.raw += c;
            build.type = TokenType::NO_OP;
            i++;
        }
        else {
            build.raw += c;
            build.type = TokenType::DATA;
            i++;
        }
        
        // show_token(build);
        res.push_back(build);
    }
    
    return res;
}

class StackEmptyException : public std::exception {
    virtual const char* what() const throw() {
        return "Error: popping from an emtpy stack";
    }
} stack_empty_exception;

class StackArgumentException : public std::exception {
    virtual const char* what() const throw() {
        return "Error: excess arguments left on stack";
    }
} stack_argument_exception;

class Negative3State {
private:
    std::vector<Token> stack;
    std::vector<Token> tokens;
    std::map<std::string, size_t> labels;
    std::map<std::string, std::map<int, int>> memory;
    size_t ptr = 0;
    bool move = true;
    // methods
    bool running();
    size_t get_label(std::string);
    void next();
    void jump(std::string);
    void one_instruction();
    int& get_mem(std::string);
    int offset = 0;
    void assert_stack_size(size_t);
public:
    static const size_t npos = -1;
    Negative3State(std::string);
    void push(Token);
    Token pop();
    void run();
    void step();
    void debug();
};

Negative3State::Negative3State(std::string str) {
    tokens = tokenize(str);
    memory[OFFSET][0] = 0;
}

bool Negative3State::running() {
    return ptr < tokens.size();
}

size_t Negative3State::get_label(std::string str) {
    auto it = labels.find(str);
    if(it == labels.end()) {
        return Negative3State::npos;
    }
    else {
        return it->second;
    }
}

void Negative3State::jump(std::string label) {
    size_t pos = get_label(label);
    ptr = pos;
    move = false;
}

int& Negative3State::get_mem(std::string name) {
    if(name == OFFSET) {
        return offset;
    }
    else {
        return memory[name][offset];
    }
}

void Negative3State::assert_stack_size(size_t s) {
    if(stack.size() != s) {
        throw stack_argument_exception;
    }
}

void Negative3State::one_instruction() {
    Token label = pop();
    size_t pos = get_label(label.raw);
    if(pos == Negative3State::npos) {
        assert_stack_size(0);
        labels[label.raw] = ptr;
        tokens[ptr].type = TokenType::NO_OP;
        tokens[label.start].type = TokenType::NO_OP;
    }
    else {
        assert_stack_size(2);
        Token b = pop(), a = pop();
        int &a_mem = get_mem(a.raw);
        int &b_mem = get_mem(b.raw);
        if(a_mem < b_mem) {
            jump(label.raw);
        }
        if(a_mem != b_mem) {
            b_mem--;
        }
        else {
            a_mem++;
        }
    }
}

void Negative3State::next() {
    if(move) {
        ptr++;
    }
    else {
        move = true;
    }
}

void Negative3State::push(Token str) {
    stack.push_back(str);
}

Token Negative3State::pop() {
    if(stack.size() == 0) {
        throw stack_empty_exception;
    }

    Token res = stack.back();
    stack.pop_back();
    return res;
}

void Negative3State::step() {
    Token cur = tokens[ptr];

    if(cur.type == TokenType::DATA) {
        push(cur);
        if(memory.find(cur.raw) == memory.end()) {
            memory[cur.raw][0] = 0;
        }
    }
    else if(cur.type == TokenType::OPERATOR) {
        one_instruction();
    }
    else if(cur.type == TokenType::NO_OP) {
        // do nothing
    }
    else {
        std::cerr << "Unknown instruction at " << ptr << ": ";
        show_token(cur);
    }
    next();
}

void Negative3State::run() {
    while(running()) {
        step();
    }
}

void Negative3State::debug() {
    std::cout << ">> STACK <<" << std::endl;
    for(size_t i = 0; i < stack.size(); i++) {
        Token cur = stack[i];
        std::cout << "stack[" << i << "] = ";
        show_token(cur);
    }
    
    std::cout << ">> MEMORY <<" << std::endl;
    for(auto it = memory.begin(); it != memory.end(); it++) {
        std::cout << it->first << " -> [" << std::endl;
        show_map(it->second);
        std::cout << "]" << std::endl;
    }
    
    std::cout << ">> LABELS <<" << std::endl;
    for(auto it = labels.begin(); it != labels.end(); it++) {
        std::cout << it->first << " -> " << it->second << std::endl;
    }
    
    std::cout << ">> OFFSET <<" << std::endl;
    std::cout << offset << std::endl;
    
    // std::cout << ">> PROGRAM <<" << std::endl;
    // for(Token t : tokens) {
        // show_token(t);
    // }
}

// modified from http://insanecoding.blogspot.com/2011/11/how-to-read-in-file-in-c.html
std::string read_file(const char *filename) {
    std::ifstream in(filename, std::ios::in | std::ios::binary);
    if(in) {
        std::string contents;
        in.seekg(0, std::ios::end);
        contents.resize(in.tellg());
        in.seekg(0, std::ios::beg);
        in.read(&contents[0], contents.size());
        in.close();
        return contents;
    }
    throw errno;
}

int main(int argc, char** argv) {
    if(argc < 2) {
        std::cerr << "Usage: " << argv[0] << " program" << std::endl;
        return 1;
    }
    std::string program = read_file(argv[1]);
    Negative3State state (program);
    
    try {
        state.run();
    } catch(std::exception& ex) {
        std::cerr << ex.what() << std::endl;
        state.debug();
        return -1;
    }
    
    return 0;
}