The SMALL Programming Language

Note

An ASCII text version of this document can be found at [ small.txt ] using the XBNF notation developed by Dr. R J Botting.

Goals

The SMALL language is a simple scripting language used to learn about programming language concepts. It is easy to implement. It can be used for doing simple algorithms and calculations. Many things are missing from it. There are many ways to extend SMALL (TBD) This specification is also (by design) incomplete and ambiguous. Removing errers(TBD), resolving ambiguitites(TBD), filling holes(TBD), and extending the language(TBD) makes an interesting project.

Running SMALL Programs

Like all scripting languages (awk, PERL, JavaScript, TCL, etc) SMALL is interpreted. The interpreter can run interactively reading statements from the user. The SMALL interpretter can also read and interpret a file with extension or suffix ".sma". A SMALL program called p is always stored in a file p.sma.

SMALL interpreters recognise the names of programs inside programs. When the name of a program is met they start to interpret the program's file. This is named a "call". The program name "calls" the program file. The call is in the "calling" program's file. When a called file is finished the interpreter returns to the calling program at the next statement after the call. One program can have any number of calls of any number of files.

The name of the interpreter should be "small". A command "small p" should interpret file "p.sma". The command "small" with no argument executes the interpreter in interactive mode. In a graphic environment it should be possible to drag and drop a "p.sma" file into the icon for small interpreter to get the same effect as "small p.sma". A double-click on a "p.sma" file would also run the interpreter.

Programs

A SMALL program is a sequence of statements, commands, comments, and separators.
1. program::=#(statement | comment | command | separator). See Examples below.

   Each statement and command in a program is interpreted in the order that they occur. Comments and separators are ignored.

   A program or part of a program can either terminate or not terminate. If it terminates it either succeeds or fails:

2. outcome::= termination | nontermination.
3. termination::=success | failure.

   Statements and commands can either succeed, fail, or not terminate. A program succeeds if all the statements and commands executed in the program succeed. A program fails if any statement or command fails. A program terminates when all executed statements and commands in the program have terminated. A program will not terminate if any executed statement or command in it does not terminate.

4. comment::= "//" #(char~end_of_line).

    	// This is a comment

   Comments separate statements and commmands. They are ignored by the interpreter.

5. separator::= end_of_line whitespace. A separator comes between statements and commands in a program and has no effect on the interpretter.

6. whitespace::= #(end_of_line | ws)
7. ws::= #( horizontal_tab | space). Whitespace should be used to expose the structure of a script. It has no effect on the meaning of a program - except inside a string.

   Commands

8. command::="edit" program_name | "exit".

    		edit example

    		exit

   Commands communicate with the operating system in which the SMALL interpreter is embedded. An "exit" terminates the interpreter. An "edit p" command saves the current version of the program in the program file and invokes the users favorite editor -- stored in the environment variable EDIT -- to edit the file. SMALL takes over control when the editor exits. In essence SMALL calls the editor as a subprogram.

   Statements

   Statements do things they are either structured or an expression followed by other things:
9. statement::= structured_statement | expression_statement.

   Structured statement

    		[ a < 0? -a -> b || a -> b ]

   Expresion statement

    		-a -> b

   Structured statements allow a program to select alternatives and to repeat pieces of code. Expression statements allow the computation and disposition of values.

   An expression statement combines testing, assignment and output into one simple construct.

10. expression_statement::= expression O(assignment) O(disposition ).
11. assignment::= arrow variable.
12. disposition::= ignored | output | returned | tested.

    Examples
    

    1. Increment i

        		i+1 -> i;

    2. Evaluate a relation and test

        		i > 0?

    3. Decrement and test

        		i - 1 -> i ?

    4. Concatenate string and value and output

        		"i =" i !

    5. Divide h by 2 and print

        		h/2.0 -> h !

    6. Add reciprocal of i to s

        		1/i+s ->s

    7. Return the square of x as value of subprogram

        		x*x^

    
    The expression is evaluated to give a value. The value can be saved in a variable. It is then disposed of in one of four ways:

    ---

    1. It is ignored(default).
    2. ignored::=O(";").

    3. It is output to the user.
    4. output::="!".

    5. It is returned to the invoking program.
    6. returned::="^". Control is returned along with the value.

    7. It is tested.
    8. tested::="?". If the value tested is 0 or it is a call that fails then the alternative or program in which the test occurs fails. Otherwise the alternative continues.

    ---

13. arrow::="->".

14. expression::= O(prefix) ws simple_expression ws #(operator ws O(prefix) ws simple_expression ws).

     		2*3

     		1*3+3

     		3+3*1

     		1+2*2

     		1+2+3

    The interpretter evaluates expressions to give a value. Whitespace (ws) has no effect on the computation. Values can be strings, integers, or floating point numbers. Expressions are evaluated strictly from left to right. All the above examples give the value 6.

    Here is a more precise definition of the semantics of an expression using two functions E and V.

15. E::expression->constant, E(e) is the value of expression e.
16. V::simple_expression->constant, V(s) is the value of a simple_expression s and is defined later (see Values below).

    For example

17. E( 1+2*3 ) = E(1+2)*V(3)=E(1+2)+3=(V(1)+V(2))*3=9.
18. E(-1+2) = E(-1) + V(2) = -V(1) + V(2) = -1.
    Net
    1. For c:constant, p:prefix, i:infix, e:expression, v:variable, s:simple_expression.
    2. E(e i s)= E(e) i V(s).
    3. E(e i p s)= E(e) i V(p s).
    4. E(s) = V(s).

    
    (End of Net)
    
    

19. prefix::= "+" | "-" | "~". Plus converts a string to a number. Minus negates a number (and also converts a string to a number). The tilde is a boolean negation changing 0 to 1 and all other values to 0 (like the ! in C/C++/Java).

20. operator::= arithmetic | relational | boolean | string_op.
21. arithmetic::="+" | "-" | "*" | "/" | "%". The operators +, -, *, /, and % have the same meaning as in C or C++ as arithmetic operators. They also convert strings into numbers.

22. relational::= "<" | "<=" | "<>" | "=" | ">=" | ">". "<", "<=", ">" and ">=" are relation operators as in C/C++/Ada/Java. Equals is represented by "=" and is true when the two values are equal. Inequality is shown as "<>" (as in Pascal and BASIC). String comparisons are done character by character by character and numerical comparisons numerically. When a number is compared to a string, the string is converted into a number.

23. boolean::="&" | "|". "&" and "|" are boolean conjunction and disjunction(inclusive) respectively.

24. string_op::= ":" | default. The colon(":") is used for comparing strings following the rules for regular expressions as defined in the ANSI standard C library. For example

     		"abbbc" : "ab*c"

    is true(non-zero) but

     		"axbc" : "ab*c"

    is false (0).

    The default operator indicates string concatenation:

25. default::="", -- string concatentation:

     		"Time = " h ":" m "."!

    Numbers are converted to decimal strings before taking part in string operations. Strings are converted to numbers before taking part in numerical operations.

26. simple_expression::= constant | variable | input | program_call.

     		123

     		a

     		$

    		abc

27. input::="$".

     		$->a;

    Read next line into variable a as a string.

     		$+$!

    Read two lines, convert to number, add them and print the result.

     		"Answer Y or N"! $="Y"?

    Prompt for a Yes or No response and test it.

     		"Answer y or n:"! $:"[yY].*"?

    A less stringent test for words like "yes", "Yes", "Yo", "Ya", "y", ...

     		"n=?"! $->n

    Prompt for a value for n.

28. program_call::= name_of_program.

     		abs

     		sqrt

     		quadratic

    A program call p fails if the file p.sma can not be found, or if the program inside the file fails. As an aid to debugging a program call outputs a warning: "p.sma not found" if the the file does not exist.

    A call can fail, succeed, or not terminate according to what its program does. A program call that succeeds returns a value. The file should contain an expression whose value is disposed of by returning it ("^"). This command also returns control. For example a program sqx might consist of a single statement.
    (sqx):

     		x*x^

    Values

    The value, V(s), of simple expression s is defined as folows:
    Net
    1. For c:constant, p:program_name, v:variable.
    2. V(c) = c.
       V(v) = the value saved in the variable (if any) else "".
       V($) = the next line of input.
       V(p) = the value returned by executing a '^' in program p.

       
       V(+ s)= if V(s) is a number n then n else convert string to number.

    3. V(- s)= - V(s).
    4. V(~ s)= if V(s) = 0 then 1 else 0.

    
    (End of Net)
    
    

    The set of variables are part of the interpreter not a particular program. They are can be used and changed by any program that is executed. A called program gets its variables from the calling program. Any variables that are changed by the called program are also changed in the calling program.

    For example suppose we wish to read a number and output its square. We can use sqx above:

     		$->x; sqx!

    Or, perhaps, if we have a program sqxy (in file sqxy.sma)
29. (sqxy):

     		x*x -> y.

    then

      		$->x; sqxy; y!

30. variable::=letter. .As-is a

     		A

    Capital and lower case letters are different variables. There are therefore 52 variables.

31. constant::=string | integer | float.

32. string::= double_quotes #(char ~ double_quotes) double_quotes.
33. double_quotes::= "\"".

     		"This is a string"

     		"A"

     		"123"

34. integer::= decimal_digit #(decimal_digit).
35. decimal_digit::= "0".."9".

     		123

36. float::= integer "." integer.

     		123.0

    Note that 12. is not a valid float.

    Control Structures

37. structured_statement::=iteration | selection.

38. iteration::= "{" alternatives "}".
39. selection::= "[" alternatives "]".

40. alternatives::= alternative #( or_else alternative) .
41. or_else::= "||".

42. alternative::= program, -- as defined above.

    Examples of iterations and alternatives:
    (Log):

     		0->l; {a>1.0? 1+l->l; a/2.0->a;}

    
    (max):

     		[ a>b? a! || a<=b? b! ]

    
    (not):

     		[ p? 0^ || 1^]

    
    (iff):

     		[ p? q? 1^ || ~p? ~q? 1^ || 0^]

    
    (and):

     		[ p? [ q? 1^ || ~q? 0^] || 0^]

    
    (enigma):

     		{i>1? [ i%2=0? i/2->i; || 3*i+1->i; ] }

    
    (newt):

     		{h+l->x; x/2->x; sqx->y; y-0.5<t? x->l; || y+0.5>t? x->h; }

    These structures have a syntax like guarded commands. The semantics are simpler.

    Each alternative is tried, in turn, until one succeds or all have failed. The first alternative is tried first. If it completes without failing then the set of alternatives also complete successfully and the later one ones are ignored. If an alternative fails then control is passed to the start of next alternative. If all fail then the set of alternatives as a whole has failed. If any succeeds (even after several failures) the whole succeeds and the later ones are ignored.

    At the failure or success of a set of alternatives, control passes to the end of the structure. If the structure is an iteration and if the alternativess succeeded then the whole structure is repeated. When all alternatives in an iteration fail then the iteration terminates successfully. Notice that an iteration can not fail. However an iteration can avoid terminating for ever. In a selection, the structure fails if all the alternatives fail and succeeds if any alternative succeeds.

    Semantics

    The object-oriented operational semantics expressed using the UML is TBD.

    Examples

    abs

     // This would be put in a file abs.sma

     // It is given a number in variable e

     // It returns the absolute value of e

     	[  e < 0 ? -e^

     	|| e^

     	]

    sqrt

     // This would be put in file sqrt.sma

     // Given a positive number in d

     // sqrt leaves an approximation to its sqrt in the same variable

     // Uses variables x,y, e, and f

     // calls abs above

     	d/2 -> x

     	{ x*x-d -> e; abs>0.00001?

     	  2*d ->f; x/2.0 ->y; d/f+y ->x;

     vv	}

     	x ->d

    quadratic

     //This would be in a file quadratic.sma

     //'small quadratic' then reads three lines containing a number each

     //and solves a quadratic equation ax*x+bx+c=0

     // Uses variables a,b,c,d,e,f,s,t,x,y

     // Calls sqrt and indirectly abs

     //read a,b, and c

     $->a; $->b; $->c;

     // calculate the denominator t

     2*a->t

     [  t=0? "This is a linear equation"!

     || t<>0?// a<>0.

     	// find the discriminant d

     	2*t*c->s; b*b-s->d;

     	// select the correct case depending on the discriminant d

     	[ d>0? sqrt; "Real roots: " -b+d/t " and " -b-d/t !

     	||d=0? "Equal roots: " -b/t!

     	||d<0? -d ->d; sqrt; "Complex roots: " -b/t "+/- i*" d/t!

     	]

     ]

    . . . . . . . . . ( end of section Examples) <<Contents | End>>

    Notations

43. O::=optional.
44. char::=any ASCII character.
45. end_of_line::= ASCII.CR | ASCII.LF.
46. horizontal_tab::=ASCII.HT.
47. space::=ASCII.SP.
48. ASCII::= See http://csci.csusb.edu/dick/samples/comp.text.ASCII.html.
49. TBD::="To Be Done".
50. XBNF::="Extreme" BNF.
51. BNF::="Backus Naur Form", a popular formal syntactic meta-language.

. . . . . . . . . ( end of section Small) <<Contents | End>>