> LeekScript Tutorial
This page only applies to LS1.0. In LS1.1, classes can be used directly: Objects and Classes
In this article, we are going to build pseudo-OOP (Object-Oriented Programming), since LeekScript is not an object-oriented language. First, I'll introduce the concept of OOP, then I'll explain how variable scope works. So as not to be too theoretical, we are going to program a structure called a "Binary Search Tree", a structure optimized for ordered insertion and searching.
This concept is very important if you start taking an interest in other languages such as C (++/#), PHP, Java, etc. It's a new way of building your programs, and it introduces objects. You surely know what an object is in everyday life: something you can transform or handle. But in programming, an "object" is a structure made up of variables and functions called attributes and methods. Take the example of a car: it is characterized by a speed and an acceleration (let's not go into too much detail), as well as actions such as turning, accelerating, braking... Here is how we could represent our car:
This makes for structured, clean code. It also simplifies the use of actions made of complex instructions, which stay hidden from the user. Another very important thing in OOP is the principle of encapsulation... Not every attribute and method is meant to be handled by the user, who could "break" the object by failing to check this or that. Imagine the user changes the speed of our car mid-game without taking inertia or anything else into account: the car would start behaving strangely, and that's only a minor change. Encapsulation is therefore the principle of making parts of the object invisible to the user: these are called private attributes/methods. Conversely, attributes/methods that the user is allowed to use are public.
The definitions of these objects are called "classes". You use them by creating a new instance of the class, just like with a regular type (numbers, arrays, strings...). It's just that in most compilers (if not all of them), this instantiation is implicit: var a = 5; creates a variable of the number object with the value '5'. I'm using "number object" loosely here. One difference that OOP makes is how functions are applied to a variable:
var a = 1;
//Without OOP
add(a, 1); // defined by function (@obj, nbr) { obj += nbr; }
// OOP
a.add(1); // defined by method add (nbr) { this += nbr; }
The 'add' function takes a number to add as a parameter. The difference between the two versions is the context: in the first case, 'add' doesn't know which object to apply its instructions to, so it needs a reference to that number (the 'obj' parameter). In the second case, however, it's a method, so it knows which object to modify, since 'add' belongs to 'a'. Note: The syntax is completely arbitrary; what matters is understanding the principle.
By the way, if you've been following, 'add' is public, since the user can call the function.
You've probably already used global variables: they let you keep information from one turn to the next and access it anywhere in your code. What sets them apart from "local" variables is their "scope". Take the following code:
global _global;
function scopeTest () { var localFunction; }
var localMain;
Each of the variables above has a different scope: _global can be accessed everywhere, on every turn; localMain can only be accessed in the main block (not in functions); localFunction can only be accessed in the "scopeTest" function. Scope also applies to functions: scopeTest can be accessed from anywhere, on every turn, whereas an anonymous function can only be accessed in the space where it was created (like a variable).
Variable scope applies to all blocks (block symbols: '{' and '}'). So a variable created in an if, a while, a do/while or a for can't be accessed outside of it:
if (true) { var localIf = 0;// localIf is created } // End of localIf's life
debug(localIf); // Error: (localIf) unknown variable or function
for (var i = 0; i
Node: The tree is made of nodes, each holding a value as well as a reference to a right node and a left node, either of which can be null Root: Simply the node that has no parent Parent: Each node has only one parent: the node that points to it Children: The nodes pointed to by the current node Leaves: Nodes without children Internal nodes: An internal node is a node that isn't a leaf Successor: The minimum of the node's right subtree Predecessor: The maximum of the node's left subtree In the image above:
8 is the root of the tree 3, 6, 10 and 14 are internal nodes 1, 4, 7 and 13 are leaves 3 is the parent of 1 and 6 14 is a child of 10 The successor of 8 is 10 The predecessor of 8 is 7
Syntax used in the pseudo-code:
Input parameter
Attributes of the current object
Static methods (usable outside any class)
Attributes and methods of a node
Now let's look at the main BST algorithms. Inserting a node is one of them.
If the tree is empty: just set this value as the root. If there are one or more nodes: Walk down the tree starting from the root, if the value is smaller, move left otherwise, move right Repeat until you can't go any further: the targeted child is empty. There are two ways to do it: recursively (Recursion in depth) or iteratively. In the second case, the main tree (the one holding the reference to the root) has a method that walks down the tree until it finds the right spot. We are going to use recursion, i.e. each node has a method that delegates the insertion to one of its children, unless that child is empty, in which case it inserts the node there. Here is the recursive (Recursion in depth) pseudo-code for insertion:
// Main tree method: called by the user METHOD Insert (value : number) IF IsEmpty (root) root Being able to instantiate a class Having public and private attributes Having public and private methods
In what situation can you create new variables without using arrays? (Because arrays are too costly.) Functions: you have to use functions to create new variables:
function new_Object () { var attribute; }
With such a function, a new variable is created on each call, but it can't be accessed directly from outside the function. To solve this problem, you need to return either a reference to the variable (but if our object holds more than one, we're stuck), or a function or an array.
function new_Object () { var privateAttribute; var publicAttribute; var privateMethod; var publicMethod;
return @( function (/* What goes here?/) {/ What goes here?/} ); // OR return @ [/ What goes here? */]; }
var obj = new_Object();
Because I don't like arrays, given their cost, I'll use anonymous functions unless stated otherwise. 'obj' is now an instance of 'Object', but for now it can't be modified, because the function doesn't do anything... Now, what if we return an anonymous function that modifies our attributes:
function new_Object () { // ... (I won't repeat everything every time)
return @( function () { publicAttribute = 1; } ); }
var obj = new_Object(); // so obj is an anonymous function
// obj := // privateAttribute = null // publicAttribute = null; // privateMethod = null; // publicMethod = null;
obj(); // Calls the function created in new_Object
// obj := // privateAttribute = null // publicAttribute = 1; // privateMethod = null; // publicMethod = null;
Note: ':=' means 'equal by definition'; I'll use it to show you the values of its attributes
If you've been following, the attributes can be modified because the function "remembers" its context, i.e. when the function is called through 'obj()', it runs as if it were still inside the function where the attributes are accessible.
The catch is that, for now, we can't choose what to modify or how. It's very simple: just pass a command as a parameter to our anonymous function:
function new_Object () { // ... return @( function (@cmd) { if (cmd === "Modify!") publicAttribute = 1; }); }
var obj = new_Object();
obj("Modify!");
// obj := // publicAttribute = 1; // ...
And there you go! If the command is indeed "Modify!", then 'publicAttribute' will be set to 1. The second problem is how to choose the value to assign to 'publicAttribute'. We can't simply give the returned function several parameters, because that isn't very flexible: imagine we use an object in our program; adding a parameter to that function would break all our code... We can, however, return another function that takes as a parameter the value to assign to 'publicAttribute':
function new_Object () { // ... return @( function (@cmd) { if (cmd === "Modify!") return function (@value) { publicAttribute = value; }; }); }
Which we can then call like this:
var obj = new_Object();
var mod_obj = obj("Modify!"); // returns a function that takes one parameter mod_obj(5); // Modifies obj's attribute
//Which simplifies to: obj("Modify!")(5);
This way, encapsulation is possible: everything is private by default, and commands let you make methods public. Note that attributes can't be made public: you have to go through getters/setters, i.e.:
function new_Object () { var attribute; return @( function (@cmd) { if (cmd === "SetAttribute") return function (@value) { attribute= value; }; if (cmd === "getAttribute") return @attribute; }); }
Note: You can get a reference to an attribute through a return if and only if the attribute holds an array or a string (see Behavior of @).
---
When you send a command to your object: obj("command"); , it is sent as raw data. The '@' used in the function signature return function (@cmd) { /* ... */ } saves 1 operation, but the transfer still costs 1 operation. To reduce this cost, you need to pass a variable (Behavior of @). In our case, we'll use constants; in LS, we use globals for that.
global setAttribute = 0; // Each constant needs its own value
var obj = new_Object();
obj(setAttribute); // Costs 1 operation for the function call instead of 2
Plus, this gives you autocompletion.
Note: When using several classes, be careful not to create two globals with the same name: either prefix your constants with initials related to your object, or gather all your constants in one place and reuse them.
--- This second point is more complex. It reduces the average cost of calling a method. For now, we use a series of 'if's to pick the right method based on the command. To improve on this, we'll introduce the concept of binary search (dichotomy). If you've never come across this principle, imagine you're playing the "higher or lower" guessing game: you have to find a number picked at random within an interval, in as few guesses as possible. The best technique is to split the interval in two, guess the number in the middle, then start again with the new interval.
To use this technique, you must already be using constants for your commands. The constants must be consecutive natural numbers, unless you enjoy making things hard for yourself.
You can then apply binary search with ternary operators:
function new_Object () { return @( function (@cmd) { return @( cmd < 4 ? cmd < 2 ? // 4/2 cmd < 1 ? // 2/2 CMD_0 : CMD_1 : cmd < 3 ? // 2 + 1 CMD_2 : CMD_3 : cmd < 6 ? // 4 + 4/2 cmd < 5 ? // 4 + 2/2 CMD_4 : CMD_5 : cmd < 7 ? // 4 + 2 + 1 CMD_6 : CMD_7 ); }); }
Here is an example. It's a bit tricky to explain: just follow the conditions. Each CMD_X can be replaced by a function to return or an attribute. Finding the command will therefore always take 3 operations, whereas with 'if's it takes between 1 and 8 operations, i.e. 4.5 operations on average. To find out how many levels your binary search needs, compute ceil(log2(n)). For example, for n = 11: log2(11) = 3.46 (rounded), so ceil(3.46) = 4 levels, and your first condition will be: cmd < 2^(4-1).
Limits of the technique: in case you didn't know, accessing an array costs 5 operations and each condition costs 1 operation, so we can work out a maximum number of methods: 2^4 = 16 (beyond that, you need at least 5 levels, which cost at least as much as the array access). i.e. If you have 16 methods or fewer, use binary search; otherwise, use arrays like this:
function new_Object () { var this =@ [ 0 : CMD_0, 1 : CMD_1, 2 : CMD_2, 3 : CMD_3, 4 : CMD_4, 5 : CMD_5, 6 : CMD_6, 7 : CMD_7, //etc... ]; return @( this ); }
Much simpler, I'll grant you, but optimization comes first.
Fire up your editors!
First, let's draw up a list of requirements so we know how to organize our structures. We need: For the user:
Hidden from the user:
Structure of the BST (tree) class:
Structure of the Node class:
I'm not adding the Successor function, because it's only useful for deletion and it doesn't meet our needs (we need the parent).
For this, we'll reuse the structure from the Pseudo-OOP section above.
// Add the constants; we'll add binary search later // I prefix them to avoid conflicts global BST_Search = 0; global BST_Insert = 1; global BST_Remove = 2;
function new_BST () { // The root of the tree (' = null' is useless) // Another approach would be to pass a value for the root as an argument to new_BST, and create the node with that value var _root = null;
return @( function (@cmd) { // Each of the functions needs a value, so we have to return an anonymous function that takes a parameter if (cmd === BST_Search) return @(function (@v) {
}); if (cmd === BST_Insert) return @(function (@v) {
}); if (cmd === BST_Remove) return @(function (@v) {
}); }); }
We need this class to be out of the user's reach. To do that, the class has to be a function belonging to the BST class:
function new_BST () { var new_Node = function (@_value) { // We require a parameter, because our node must have a value // No need to do var v = value; since the variable already exists as a parameter, which changes nothing // add the children var _leftChild; var _rightChild;
return @( function (@cmd) { // Same thing: we have to return an anonymous function that takes a parameter if (cmd === BST_Search) return @(function (@v) {
}); if (cmd === BST_Insert) return @(function (@v) {
}); if (cmd === BST_Remove) return @(function (@v) {
}); }); };
// The rest of the BST function below }
All the structures are built; all that's left is the algorithms.
For this method, I'll use the algorithm we studied earlier.
// BST class: // ... if (cmd === BST_Search) return @(function (@v) { // A ternary would work too, but it doesn't change performance here if (_root === null) return @false; else return @_root(BST_Search)(v); }); // ...
// Node class: // ... if (cmd === BST_Search) return @(function (@v) { if (v < _value) { if (_leftChild === null) return @false; else return @_leftChild(BST_Search)(v); } else if (_value === v) return @true; else { if (_rightChild === null) return @false; else return @_rightChild(BST_Search)(v); } }); // ...
For this method, I'll use the algorithm we studied earlier.
// BST class: // ... if (cmd === BST_Insert) return @(function (@v) { if (_root === null) _root = new_Node(v); else _root(BST_Insert)(v); }); // ...
// Node class: // ... if (cmd === BST_Insert) return @(function (@v) { if (v < _value) { if (_leftChild === null) _leftChild = new_Node(v); else _leftChild(BST_Insert)(v); } else { if (_rightChild === null) _rightChild = new_Node(v); else _rightChild(BST_Insert)(v); } }); // ...
Translating this into LS is really simple. But things get complicated with deletion... [ Being written by Le Gentleman ... ]
Impossible de charger les données du jeu.
Vérifiez votre connexion et réessayez.