ScopeScript

View language IDE: https://github.com/danpaxton/scopescript-ide

Parser

Given code as raw text, the parser converts it into zero or more statement syntax trees defined by an operator precedence and a set of grammar rules. Text is parsed left to right in top down manner. The parser is built from larger parse functions built out of smaller parse functions. Specifically, the parser starts by parsing text using simple regular expression parsers. Then, parses expressions using these regex parsers. Then, parses statements using expression parsers. Lastly, parses programs using statement parsers. Operator precedence is handled by building lower precedence operator parsers that use the next highest precedence operator parser as their main parse function. This allows the parser to bind to higher precedence operators before lower precedence operators. The variable checker traverses the syntax trees and maintains a set of bound variables at each level of the program. The variable checker is used to find cases of undeclared variables, duplicate parameters, valid statment use and invalid built-in function use. The parser is built using the Parsimmon library.

Interpreter

The interpreter is built using a network of JavaScript objects that map a 'kind' to a function. The main two objects that drive decision making are the statements and expressions objects. The statements object returns a specific function given a statement kind, and the expressions object returns a specific function given an expression kind. Certain statement functions use the statements object again (self-referencing) or the expressions object. Once the program is operating using the expressions object the only way to use to the statements object again would be through a function call, otherwise there is only access to the expressions object until the next statement in the program is executed. There also exists helper objects for operator (binary/unary) and built-in function use, all are used by the expressions object. Code blocks are represented as a list of statements (syntax trees) that the interpreter sequentially evaluates.

Scope

Program scope is represented as a linked list of states. Each state is represented as an object with value, parent, and out attributes. The 'value' attribute points to a map containing the state's local variables and their values. The 'parent' attribute points to the outer-state relative to itself. Lastly, the 'out' attribute points to the program output list. New states are added to the scope when the program enters a different code block (i.e. if, while, for, and function blocks). Variable look up starts in the current state and follows parents pointers to find variables that are global to the current state.

Closures

Closures are represented as an object with params, body, parent and env attributes. The 'params' attribute stores a list of strings that represent each parameter. The 'body' attribute stores a block of code to be executed on call. The 'parent' attribute maintains a link to it's creating state at closure creation time. Lastly, the 'env' attribute is a stack that tracks the most recently made call environment. Variable look up during a function call follows the closure's lexical environment, not the current program scope at call time. At any point in the program, the only variables that can be referenced must be on the path from the current state to the outermost state. (i.e variables must be in scope)

Installation

Clone repository,

$ git clone https://github.com/danpaxton/scopescript.git
$ cd scopescript

Install and run tests,

$ npm install
$ npm run test

Or install package,

$ npm i scopescript

Operator Precedence

The table below summarizes operator precedence from highest precedence to lowest precedence. Operators in the same box have the same precedence. Operators without syntax are binary. All operators group left to right. Operator| Description ---:| --- (expression),{key: value...} | Binding or parenthesized expression, collection display x(...), x.attribute, x[...] | call, reference, subscriptor !x, ~x, ++x, --x, +x, -x| logical not, bitwise not, pre-increment, pre-decrement, unary plus, unary negative *, /, //, % | multiplication, division, floor division, remainder +, -| addition, subtraction <<, >>| shifts & | bit and | | bit or ^ | bit xor <, >, <=, >=, !=, == | comparisons && | logical and || | logical or ... ? ... : ... | ternary

Grammar

Below is a set of instructions that define valid statements and expressions for the scope script programming language. Scope script is an imperative, dynamically-typed language. Each program consists of a series of statements that change the state of the program.

Lexical

type boolean ::= true | false

type number ::= /([0-9]+\.?[0-9]*|\.[0-9]+)([eE][+-]?[0-9]+)?/ | Infinity

type string ::= /(['"])(\1|(.(?!\1))*.\1)/

type name ::= /[a-zA-Z_$][a-zA-Z_$0-9]*/

type none ::= none

Operators

type unop ::= !, ~, ++, --, +, -

type binop ::= *, /, //, %, +, -, <<, >>, |, &, |, ^, >=, <=, ==, !=, >, <, &&, ||

Atoms

type atom ::= { kind: 'none' } | { kind: 'boolean', value: boolean } | { kind: 'number', value: number } | { kind: 'string', value: string } | { kind: 'collection', value: { [ key: string ]: [ value: atom ] } } | { kind: 'variable', name: name } | { kind: 'closure', params: name[], body: statement[] }

Expressions

type expression ::= atom | { kind: 'unop', op: unop, expr: expression } | { kind: 'binop', op: binop, e1: expression, e2: expression } | { kind: 'call', fun: expression, args: expression[] } | { kind: 'subscriptor', collection: expression, expression: expression } | { kind: 'attribute', collection: expression, attribute: name } | { kind: 'ternary', test: expression, trueExpr: expression, falseExpr: expression }

Statements

type statement ::= { kind: 'static', expr: expression } | { kind: 'assignment', assignArr: expression[], expr: expression } | { kind: 'if', truePartArr : { test: expression, part: statement[] }[], falsePart: statement[] } | { kind: 'for', inits: statement[], test: expression, updates: statement[], body: statement[] } | { kind: 'while', test: expression, body: statement[]] } | { kind: 'delete', expr: expression } | { kind: 'return', expr: expression } | { kind: 'break' } | { kind: 'continue' }

Program

type program ::= { kind: 'ok', value: statement[] } | { kind: 'error', message: string }

Comments

Comments are specified using the # character.

Example, # integer value. x = 10;

None type

The absence of a value is specified using the none keyword.

Example, a = none;

Uknown attribute reference returns none. Given a = {}, a[1] == none is equivalent to true.

Boolean

Boolean values are represented using true or false.

Example, a = true;, true assignment. if (false) { ... }, conditional test.

boolean values are a subset of number values. 0 + true is equivalent to 1. 0 + false is equivalent to 0.

Numbers

Numbers are represented as integers, or floats.

Examples, 1, integer number.

.66, float number.

2.67e-100, scientific notation.

Infinity, infinity.

Strings

Strings are represented as a sequence of ascii characters between a matching pair of single or double quotes.

Example, '', empty string.

' str1 ', single quotes.

" str2 ", double quotes.

Strings can be subscripted at character positions. 'abc'[1] is equivalent to 'b'.

Operators

Define an expression using a binary or unary operator.

Unary Operators

Syntax, unop expression

Example, !x, ++x

Binary Operators

Syntax, expression binop expression

Example, 2 * 8, true && false, a == b

Bitwise Operators

Bitwise Operators only operate on integers.

Example, ~5, 1 >> 2

Error, 1.5 >> 2.5

Comparison chaining

Chaining comparsions will test each comparsion seperated by a logical AND (&&).

Example, 1 < 2 < 3, is equivalent to 1 < 2 && 2 < 3.

1 == 2 < 3 != 4, is equivalent to 1 == 2 && 2 < 3 && 3 != 4.

Built-in functions

Built in functions with default return values unless overwritten.

type(..), returns the argument type.

ord(..), returns the ASCII value of the character argument.

abs(..), returns the absolute value of the number argument.

pow(..), returns the first argument to the power of the second argument.

len(..), returns the length of the collection or string argument.

bool(..), returns the boolean representation of the argument.

num(..), returns the number representation of the argument.

str(..), returns the string represenation of the argument.

keys(..), returns a zero-based indexed collection of the argument collection's keys.

print(.. , ...), displays arguments seperated by a space, and then a newline to output.

Closures

Store parameters, function code, and a link to lexical environment.

Syntax, ( name, ..., name ) => expression | { body }

No parameters, foo = () => { message = 'Hello'; return message; }; foo();

Single parameter, foo = p => { return p + 1; }; foo(10);

Multiple parameter, foo = (a, b, c) => { return a + b + c; }; foo(1, 2, 3);

Return line, foo = (a, b) => { return a + b; };, using return line foo = (a, b) => a + b;

Both methods above will be parsed into the same result. Using no brackets allows only the one return statement.

Currying, foo = a => b => c => a + b + c; foo(1)(2)(3);

Collections

Store a collection of attributes mapped to a value.

Syntax, { atom : expression, ..., atom : expression }

Empty, data = {};

New attributes, data = {}; data['key'] = 1; data.number = 10;

data is now equivalent to { 'key': 1, 'number': 10 }.

Names, data = { a: 1, 2: true };, is the same as data = { 'a': 1, '2': true };.

Numbers, data = { 1: 1, 2: true };

Strings, data = { ' ': 1, 'key': true };

Only named attributes can be accesed using the reference ( x.attribute ) operator. Any attribute can be accesed using the subscriptor ( x[...] ) operator. All attributes are stored as strings, x[1] is the same as x['1'].

Example, data = { 1: 1, key: true, ' ': false };, access attribute 1 using data[1], attribute ' ' using data[' '] and attribute key using data.key or data['key'].

Ternary

Conditionally make decisions on the expression level. Defined by a test with a true expression and a false expression.

Syntax, test ? true expression : false expression

Ternary expressions can only contain expressions, use if statements for statement level conditionals.

Nested ternary must be within parentheses.

Example, a = test1 ? ( test2 ? 1 : 3 ) : 2;

Parse error, a = test1 ? test2 ? 1 : 3 : 2;

Assignment statement

Assign a variable, or a collection attribute to an expression.

Syntax, x = expression; x.attribute = expression; x[...] = expression;

Basic assignment

Example, a = 1;

Assign multiple variables, or attributes the same value using an assignment chain. a = b['key'] = c.val = 1;

Compound assignment

'+=' | '-=' | '*=' | '/=' | '//=' | '%=' | '<<=' | '>>=' | '&=' | '^=' | '|='

A variable must be defined before compound assignment.

Example, a = 1; a += 1;

A compound assigment and the equivalent simple assignment will be parsed into the same result. a += 1; is the same as a = a + 1;

Assignment types cannot be mixed. a = b += 1; will result in a parse error.

if statement

Conditionally make decisions on the statement level. Defined by a series of tests with associated parts, and finally a false part.

Syntax, if( test ) { part } elif ( test ) { part } ... else { false part }

if statements require brackets for more than one statement.

if only, if(true) 1 + 2;

if else, if(true) { 1 + 2; } else { 1 + 2; }

if else-if, if(true) { 1 + 2; } elif(true) { 1 + 2; }

if else-if else, if(true) { 1 + 2; } elif(true) { 1 + 2; } else { 1 + 2; }

while statement

Loop until termination defined by a test expression.

Syntax, while( test ) { body }

while loops require brackets for more than one statement.

Example, while(a < 10) ++a;

for statement

Loop with initializers. Performs updates at each iteration until termination defined by a test expression.

Syntax, for( inits , test , updates ) { body }

for statements require all parts. Require brackets for more than one statement.

Initializers must be assignments and update variables must be defined.

Example, for(i = 0; i < 10; ++i) 2 + i;

for(i = 0, j = z = 1; i < 10; ++i, ++z, --j) { z += j; j += i; }

Errors,

Need all parts, for(i = 0; true; ) { 2 + i; }

for(; true; ++i) { 2 + i; }

z not defined, for(i = 0; i < 10; z = 0) i;

true not an assignment statement, for(i = 0, true; i < 10; ++i) i;

return statement

Returns an expression from a function call.

Syntax, return expression;

Example, return 1 + 2;

No return statement or return;, are both equivalent to return none;.

delete statement

Removes an attribute from a collection.

Syntax, delete expression;

Example, a = { 1 : true, a : true }; delete a[1]; delete a.a; a is now equivalent to {}.

continue statement

Explicitly jump to next loop iteration.

Syntax, continue;

Example, for(a = 0; a < 10; ++a) { continue; --a; } The loop will run ten times because a is never decremented.

break statement

Explicitly step out of loop iteration.

Syntax, break;

Example, while(true) { break; print(1);} The loop will only run once and nothing will be printed because it breaks immediately.

Example programs

Creates ranges of numbers using a linked list.

# Returns a function that creates a range.
RangeMaker = () => {
  empty = () => {  
    toString: () => ')',
    map: f => empty()
  };
  node = (v, n) => { 
    val: () => v, 
    next: () => n, 
    toString: () => '(' + str(v) + n.toString(),
    map: f => node(f(v), n.map(f))
  };
  return (start, N) => {
    maker = n => n < N ? node(n, maker(n + 1)) : empty();
    return maker(start);
  };
};

# Returns a squared range.
squared = range => range.map(e => pow(e, 2));

Range = RangeMaker();

positive = Range(0, 20);
negative = Range(-20, 0);

print('Original:');
print(positive.toString());
print(negative.toString());
print();
print('Squared:');
print(squared(positive).toString());
print(squared(negative).toString());

Original: 
(0(1(2(3(4(5(6(7(8(9(10(11(12(13(14(15(16(17(18(19) 
(-20(-19(-18(-17(-16(-15(-14(-13(-12(-11(-10(-9(-8(-7(-6(-5(-4(-3(-2(-1) 

Squared: 
(0(1(4(9(16(25(36(49(64(81(100(121(144(169(196(225(256(289(324(361) 
(400(361(324(289(256(225(196(169(144(121(100(81(64(49(36(25(16(9(4(1) 

A program that uses binary search to find a value.

# Find target using binary search.
binarySearch = (arr, t) => {
  left = 0; right = len(arr) - 1;
  steps = 0;
  while(left <= right) {
   mid = left + (right - left) // 2;
   if (arr[mid] == t) {
     return steps;
   } elif (arr[mid] > t) {
     right = mid - 1;
   } else {
     left = mid + 1;
   }
   ++steps;
  }
  return -1;
};

# Iterate over collection to find target.
findNum = (arr, t) => {
  for(i = 0; i < len(arr); ++i) {
    if (arr[i] == t) {
      return i;
    }
  }
  return -1;
};

nums = {};
for(i = 0; i < 20000; ++i) {
  nums[i] = pow(i, 2);
}

targetNum = 126023076;

numSteps = findNum(nums, targetNum);
print("(Iteration) Found target:", targetNum, "in", numSteps, "steps.");
print();
numSteps = binarySearch(nums, targetNum);
print("(Binary Search) Found target:", targetNum, "in", numSteps, "steps.");

(Iteration) Found target: 126023076 in 11226 steps. 

(Binary Search) Found target: 126023076 in 12 steps.