Sigma is an extension language. Its purpose is to make it possible to
augment applications written in C++ with an interactive programming
language. The intention is that Sigma's strength lies in the ease with
which it is extended to support application-specific data structures
and functions. Consequently, this tutorial assumes the reader is
already an experienced computer programmer.
Sigma is a functional programming language. It allows the programmer
to write functions that build other functions, so ideally the reader
is also familiar with some other functional programming langauge, but
the hope is that this tutorial makes the functional aspects of Sigma
clear on its own.
Currently, the implementation supports a few basic number types: the
natural numbers (non-negative integers), integers, rational numbers,
and real numbers. The first three support arbitrary-precision
arithmetic. Real numbers correspond to the double-precision
floating-point numbers of the underlying interpreter implementation.
The implementation also supports parsing and printing C-style strings,
but there are no functions to manipulate them exposed within the
language yet.
The interpreter's prompt is a question mark. The input you would type
is shown after the question mark on the same line. The interpreter's
response is shown below on the next line. The interaction with the
interpreter is indented to offset it from the commentary.
For a more thorough description of the language grammar, see the
comments in the file:
sigma_0.6/src/lib/sigma/parse.hpp
The interpreter (in its current beta form) is invoked by typing
testsigma
which starts an interactive session:
Sigma 0.6
?
_____ARITHMETIC_____
At the '?' prompt, you type an expression, say a seven and a
semicolon, and then the enter key:
? 7;
7 : natural
A semicolon tells the interpreter that it has reached the end of an
expression. An expression can be something as simple as a number. The
interpreter evaluates the expression, and prints the resulting value
and its type. In the above case, the result of evaluating the number
seven is simply the number seven itself, which is of type 'natural'
(i.e. a member belonging to the set of natural numbers).
Here's a more complicated expression:
? 3+4*5;
23 : natural
The mathematical operators addition, subtraction, multiplication and
division are supported, and with their expected precidences. The
result of the expression is twenty-three, not thirty-five. The
multiplication happened before the addition.
? -3/(4+5);
(-1/3) : rational
Parentheses are supported, as well as rational numbers. Rational
numbers are automatically reduced to their simplest form.
? 111111111*111111111;
12345678987654321 : natural
The natural, integer, and rational numbers are of arbitrary-precision.
Numbers specified using floating-point and/or exponential notation is
stored and manipulated as reals:
? 2.34e56;
2.34e56 : real
Since reals are implemented using the underlying hardware
floating-point support, precision is limited. One way to demonstrate
this is with the 'floor' function. Unlike the C version of the
function, the Sigma version provides its result as an
arbitrary-precision integer even if the argument is a real.
? floor(2.34e56);
234000000000000005389490511679859447491219227766159310848 : integer
The floor function exposes the fact that a floating-point number is
only a limited-precision binary approximation. (Above is the exact
value used by the machine's floating-point format to approximate
2.34e56--not that this kind of precision is necessarily useful in this
situation.)
__COMPARISON OPERATORS__
? 7/23 < 1/3;
true : boolean
Comparison operators '<', '>', and '=' are supported.
__BOOLEAN OPERATORS__
? 3<4 & 9<8;
false : boolean
Boolean operators '&' (and) and '|' (or) are supported. The boolean
operators have lower binding precidence than the comparison operators,
which in turn have lower precidence than the arithmatic operators.
__VARIABLES__
? let q be 23/45;
(23/45) : rational
? q + 2/45;
(5/9) : rational
You can name values for later use. The result of an expression naming
a value is the value itself.
__BLOCKS__
? {let i be 43-27, i/34};
(8/17) : rational
An expression can be a block, which is a sequence of expressions
within a matching pair of curly brackets. The expressions within the
block must be separated by commas. The result of evaluating a block is
the result of the last expression.
? i;
Undefined identifier: i
A named value within a block is only valid for subsequent expressions
within that block.
__FUNCTIONS__
? let square(i) be i*i;
: lambda
This declares a function named 'square' that multiplies its argument
by itself. Like the result of an expression declaring a value, the
result of an expression declaring a function is the function
itself. Functions don't have a printable value, so its value is
displayed as its type within angle brackets. (A 'lambda' is a function
abstraction. Also note that any value without a defined printable form
is displayed similarly.)
? square(7);
49 : natural
A function is invoked by providing it with a list of arguments
supplied within parentheses. In the case above there is only one
argument.
? let leq(i,j) be not(j* : lambda
This defines a function named 'leq' (less or equal) of two
arguments. It uses the pre-defined function 'not'.
? leq(2,2);
true : boolean
? leq(1,2);
true : boolean
? leq(3,2);
false : boolean
It behaves as expected.
? leq(q, 24/46);
true : boolean
Arguments can themselves be expressions to be evaluated.
__LAMBDA__
An alternative way to define functions is with 'fn' which creates an
unnamed function (i.e. a lambda). You could also have defined the
'square' function like this:
? let square be fn(i){i*i};
The 'fn' keyword must be followed by a list of variables to be bound
and a block. The interesting thing is that the function doesn't have
to be bound to a name in order to be used. You can use a lambda
created with 'fn' directly. An example:
? fn(j){j*j*j}(3);
27 : natural
You can also build functions that build other functions:
? let addN be fn(n){fn(i){i+n}};
: lambda
? let add3 be addN(3);
: lambda
? add3(2);
5 : natural
? let add100 be addN(100);
: lambda
? add100(23);
123 : natural
Note that the first 'add3' function still works:
? add3(4);
7 : natural
(Higher-order functions are supported by way of closures.)
__RECURSION__
The main difference between the 'let f(i) be' form and the 'fn' form
is that you need the named form if you are going to write a recursive
function. Here's the factorial function:
? let f(i) be if i<2 then 1 else i * f(i-1);
: lambda
? f(20);
2432902008176640000
If we hadn't used the named form to define the function, the body of
the function would have referred to a previous definition of 'f' or
reported that 'f' was an undefined identifier if there was no previous
definition.
This example also introduces the if-then-else form. This form is an
expression like any other. Note that the expression following the 'if'
keyword must evaluate to a boolean, and that both the 'then' and the
'else' expressions need to be provided. Only one or the other of the
'then' and 'else' expressions gets evaluated.
When values are redefined, they do not replace any previous uses
captured in function definitions:
? let g() be q;
: lambda
? let q be -1;
-1 : integer
The 'g' function still returns the value of 'q' in effect at the time
it was defined:
? g();
(23/45)
__OPERATORS__
In Sigma, the mathematical and comparison operators are functions like
any you could define yourself, but with two differences. The first
difference is that they are generic functions.
A generic function is really a collection of functions where each
function is designed to handle different arguments. For example, the
addition operator works for different kinds of numbers. The code to
add integers is different from the code to add rational numbers which
is different from the code to add floating-point numbers.
When each of the different versions of the function is given the same
name (as with the '+' operator), the function name (i.e. e.g. '+') is
said to be overloaded. C overloads the '+' operator. It works for the
various number types supported by the hardware. But in the case of C,
the compiler needs to be able to determine at compile time what kinds
of numbers are being added together.
When the process of finding the function that matches the provided
arguments happens while the program is running, it is called
multi-method dispatching. Sigma supports multimethod dispatching, and
the mathematical functions in particular are generic functions.
The second difference of the mathematical operators from regular
functions is of course their syntax. The mathematical operators are
infix and take exactly two arguments. However, operators can be
manipulated using the syntax of normal function identifiers by
'escaping' their name with a backslash:
? \+;
: generic
? \+(2,3);
5 : natural
? let apply be fn(f,i,j){f(i,j)};
: lambda
? apply(\*,3,4);
12 : natural
? apply(\<,3,4);
true : boolean
_____LISTS_____
Values can be grouped into pairs:
? let p be pr(23, 5);
pr(23, 5) : pair
? hd(p);
23 : natural
? tl(p);
5 : natural
An SML-like notation can be used to assemble lists using pairs:
? [1,2,3,5];
[1, 2, 3, 5] : pair
There's a special symbol for the empty list:
? [];
[] : nil
You could build lists without the special notation:
? pr(1, pr(2, pr(3, pr(5, []))));
[1, 2, 3, 5] : pair
If it's a proper list (i.e. nested pairs ending in []) it will display
the list using list notation. Otherwise, it will use 'pr' notation:
? pr(1, pr(2, pr(3, 5)));
pr(1, pr(2, pr(3, 5))) : pair
Here's a function that builds a list containing a sequence of numbers:
? let seq(i) be if i<1 then [] else pr(i, seq(i-1));
: lambda
? seq(4);
[4, 3, 2, 1] : pair
Here's a function that takes a list, and sums up the elements:
? let sum(l) be if nil(l) then 0 else hd(l) + sum(tl(l));
: lambda
? sum([1,2,3,5,7]);
18 : natural
? sum(seq(10));
55 : integer
Here's a more general version of the sum function that takes a
function, an initial value, and a list:
? let fold(f,i,l) be if nil(l) then i else f(hd(l),fold(f,i,tl(l)));
: lambda
The sum of the first ten integers:
? fold(\+,0,seq(10));
55 : integer
The product of the first ten integers:
? fold(\*,1,seq(10));
3628800 : integer
_____FIRST-CLASS EXPRESSIONS AND ENVIRONMENTS_____
The evaluation of an expression can be suspended by enclosing it in
quotes:
? let e be '3 + 4 * 5';
: exp
The resulting value is a function which when passed an environment
will be evaluated returning the result. An environment is the set of
variables and their associated values in effect at any given
moment. The current environment is captured by using the 'this'
keyword.
? e(this);
23 : natural
Note that evaluating the expression above requires values for the
addition and multiply operators, which just happen to be defined in
the current environment.
An environment can be captured even from within functions and blocks:
? let env be {let i be 3, let j be 4, let k be 5, this};
: env
? 'i+j*k'(env);
23 : natural
The values defined within the block are captured within the
environment bound to the 'env' variable, but they are not exposed in
the top-level environment:
? i;
Undefined identifier: i
Objects in the traditional object-oriented sense can be simulated
using captured environments. Getters are trivial:
? let get_i(obj) be 'i'(obj);
: lambda
? get_i(env);
3 : natural
Setters are only slightly more complicated:
? let set_i(obj,new_val) be 'fn(i){this}'(obj)(new_val);
: lambda
? let env be set_i(env,7);
: env
? get_i(env);
7 : natural
Note that the rest of the values are still there:
? 'j'(env);
4 : natural
All for now...
*