#WEEKLY 20 — Multiplication Tables (in LOLCODE!)

So this week, I decided to make things hard on myself and use an esoteric language. I chose LOLCODE since I've never used it before, and it seems pretty popular.

Little did I know, LOLCODE has no support for lists.

So, this weekly became quite a challenge — how can I solve a problem which requires some sort of list-like data structure to solve (to implement a uniqueness check) with a system that has no lists.

Well, my solution was to realize that what I just said was a lie. There are lists in LOLCODE — yarns (or, as boring normal programmers call them, strings).

So my task became a) encoding a list of numbers in a string,and b) figuring out how to compare a number to all the numbers in that "list", and check if there is a match.

These things probably don't sound too hard, but this is an esoteric language so of course it was difficult. The first goal I accomplished by giving each number an arbitrary precision — 10 digits (which seems big enough that you won't run out of space for something like this challenge while keeping the performance modest). I could then simply pad each number up to 10 digits with leading zeroes, and it becomes possible to get any number out of the list. The next goal was not as easy, but through a lot of loops and fun names like `LAZERPOINTER` and `DIJIT` I managed to make it work.

So here it is, a bunch of unreadable code that sounds like your cat wrote it, complete with LOLspeak prompts. It doesn't look like much, but don't assume the complexity of an esoteric program based on its size :D

Note 1: Don't give it big numbers, due to the obvious performance downsides of this approach it will get really laggy. Anything over 20x20 starts to get laggy, so I'd keep it around that range at most. (If you're wondering, under no circumstances put anything greater than 99999x99999 — it will max out the 10 digit limit and be frozen forever!)

Note 2: If nothing shows up at first, re-run the program. It appears that sometimes repl's lolcode interpreter doesn't run the first time.

You are viewing a single comment. View All
fuzzyastrocat (788)

@DynamicSquid hai sad 2 noe u not liek mah coedz, iz very insult to catz evrywear

plz trai to understand, skwid an cat can be fwiend u noe

DynamicSquid (3641)

@fuzzyastrocat Oh, quick question if you don't mind, I finally made a recursive decent parser:

``````class AST
{
private:
struct Node;

public:
static Token EvaluateExpression(const std::vector<Token>& expression)
{

return result;
}

public:
static Node* CreateTree(const std::vector<Token>& expression)
{
if (expression.size() == 1)
return new Node{ expression[0], nullptr, nullptr };

for (std::size_t a = 0; a < expression.size(); ++a)
{
if (expression[a].value == "+")
{
if (expression[a + 1].value == "(")
{
expression[a],
head == nullptr ? new Node{ expression[a - 1], nullptr, nullptr } : head,
CreateTree(GetBracketExpression(expression, a))
};

continue;
}

expression[a],
head == nullptr ? new Node{ expression[a - 1], nullptr, nullptr } : head,
new Node{ expression[a + 1], nullptr, nullptr }
};
}
else if (expression[a].value == "*")
{
{
if (expression[a + 1].value == "(")
{
expression[a],
new Node{ expression[a - 1], nullptr, nullptr },
CreateTree(GetBracketExpression(expression, a))
};

continue;
}

expression[a],
new Node{ expression[a - 1], nullptr, nullptr },
new Node{ expression[a + 1], nullptr, nullptr }
};

continue;
}

if (expression[a + 1].value == "(")
{
expression[a],
CreateTree(GetBracketExpression(expression, a))
};

continue;
}

expression[a],
new Node{ expression[a + 1], nullptr, nullptr }
};
}
}

}

static void TravelTree(Node* node)
{
if (node->left == nullptr || node->right == nullptr)
return;

TravelTree(node->left);
TravelTree(node->right);

if (node->left->token.type == "val" && node->right->token.type == "val")
{
if (node->token.value == "+")
node->token = Token{ "val", std::to_string(std::stoi(node->left->token.value) + std::stoi(node->right->token.value)) };
else if (node->token.value == "*")
node->token = Token{ "val", std::to_string(std::stoi(node->left->token.value) * std::stoi(node->right->token.value)) };

delete node->left;
delete node->right;
}
}

private:
static std::vector<Token> GetBracketExpression(const std::vector<Token>& expression, std::size_t& index)
{
index += 2;

std::vector<Token> bracket_expression;
for (int count = 0; index < expression.size(); ++index)
{
if (expression[index].value == "(")
count++;
else if (expression[index].value == ")")
count--;

if (expression[index].value == ")" && count == -1)
return bracket_expression;

bracket_expression.push_back(expression[index]);
}
}

private:
struct Node
{
Token token;
Node* left;
Node* right;
};

};``````

So what do I do now? I kinda have 2 questions

1. How will I do the error checking? Should I have a separate function that does it? Or should it be in the AST, like if something doesn't work then I know there has to be a syntax error

2. My AST only works for expressions. It will take in an array of tokens that represent an expression and return the output. Is that good enough? Or should it include more features?

fuzzyastrocat (788)

@DynamicSquid 1. If you do it the way you're doing it not, you'd put that in `TravelTree`. However, I'd strongly suggest making each AST `node` have an `eval` method which does what your `TravelTree` function does (so remove `TravelTree`). Then, instead of calling `TravelTree`, you say `rootNode.eval()`, and it calls `eval` on its subnodes (which may call more `eval`s on their subnodes, etc) and then it adds/multiplies/does whatever with the return values.
2. If you're doing an AST, make the entire program be represented as an AST! The AST should be your only representation of the entire program once you've parsed the tokens.

A final note: Your recursive descent parser works, but it's kinda ugly and will get really ugly the more you add to it. I'd suggest each task to different functions — rather than try to explain that here, I will (once again :D) direct you to my Sea parser.

I'm kinda busy right now, so I don't have the time to create a full example in C++. When I get the time (which should be soon), I'll make an example to help illustrate my point better.

DynamicSquid (3641)

@fuzzyastrocat oh thanks for the explanation! about making the entire program into an AST, I've been looking at your lang and a couple others from the game jam, and I noticed they have something like this:

``````Variable Initialization AST

[ token: int ]
|
|
V
[ token: var ]
|
|
V
[ AST: expression ]

If Statement AST

[ token: if ]
|    |
|    |
|    ------> [ AST: code inside curly braces ]
V
[ AST: condition ]``````

So in code it would look like this:

``````class Expression
{
Token* start;
}

class VariableInit
{
Token* type;
Token* name;
Expression* value;
}

class IfStatement
{
Expression* condition;
vector<Token*> code;
}``````

Am I getting this right?

fuzzyastrocat (788)

@DynamicSquid Yeah, that's the gist of it. However, two things I notice: An `Expression` might not be just a single token, so I'd rename that to something like `Atomic`. Also, in the IfStatement, your `vector<Token*> code;` needs to be something like `vector<Statement*> code;` where `Statement*` is the base class for an AST "statement" node.

Also, you might want to consider blocks (`{ statement; statement; statement... }`) to be a type of AST node, and then the IfStatement and WhileStatement and any other statement that needs a code block just has `Block* code;` instead of `vector<Statement*> code;`.

DynamicSquid (3641)

@fuzzyastrocat ah.. I see. last question though, the parser just generates an AST for the code, and the interpreter actually traverses the AST and does stuff right? or can it be a mix between both?

fuzzyastrocat (788)

@DynamicSquid You've got it 100% right (don't mix!). The interpreter "pipeline" kinda looks like this:

``````                ---------                ----------             -------------
Source code --> | LEXER | --> Tokens --> | PARSER | --> AST --> | Execution | --> Program output
---------                ----------             -------------``````

Notice how each section is like a "black box" which gets exactly 1 input and produces 1 output.

(Once again, I can't stress enough how useful it is to have the AST execute itself by calling some `exec` method on the root node and having the root node then call more `exec`s, which calls more `exec`s, etc)

DynamicSquid (3641)

@fuzzyastrocat gotcha! hmm don't have school tmr, so time to code until 12pm!

fuzzyastrocat (788)

@DynamicSquid Ha! Hope you get a good sleep after :D

fuzzyastrocat (788)

@DynamicSquid It's this thing your body does to uselessly waste a bit under half the day. Yeah, I don't know why I keep doing it either.