by Sean P. Miller
This document is a quick overview intended for intermediate or experienced programmers. I assume familiarity with the C or ML language families and the concept of context-free grammars.
In my opinion, the history of programming language design has been driven by the tension between imperative and declarative programming styles. Modern imperative languages tend to support object-oriented programming, meaning their programs are organized into large bundles of implicitly mutable state. On the other hand, declarative languages tend to encourage descriptive code, often based on the lambda calculus, with a strong aversion to implicitly mutable state. Some languages have tried to encourage multiparadigm programming styles with varying degrees of success; however, I feel most such efforts have fallen short.
I created Slang as a teaching language to bridge the gap between relatively low-level imperative languages (such as Java and C++) and high-level declarative languages (such as Standard ML, Haskell, and Lisp). Inexperienced students, who intuitively understand algorithms as series of steps, often have trouble grasping the declarative nature of functional languages. Even experienced students can be intimidated by the abrupt shift in style. Therefore, I designed Slang to be a high-level imperative language with features stolen shamelessly from popular functional-declarative programming languages. In this way, Slang provides a gentle introduction to sophisticated programming concepts.
Characteristic features of Slang include the following:
By default, the Slang compiler expects source to be encoded with UTF-8, which means it will also accept legacy ASCII-encoded source. If your editor inserts byte order marks, don't worry: Slang ignores them.
My implementation of Slang, which includes a compiler, runtime, and standard library, is not efficient. Many mainstream high-level languages are faster (e.g., Python). However, since efficiency was not a design goal, this is not a flaw.
That said, Slang piggybacks on the JVM, so it's rarely much slower than most interpreted languages.
I've confirmed that the Slang compiler will compile on the following platforms:
The precompiled binary supplied with the distribution should run on any Windows system with appropriate C++ runtime support. When I gain access to other platforms, I'll port the Slang distribution accordingly.
Currently, Slang uses the following third-party libraries:
Alert readers may be alarmed by potential license issues, but Apfloat is distributed under the GNU Lesser GPL v2.1+, and UTF8-CPP is "freely available for any purpose". See their respective licenses for more information.
Many sections contain relevant excerpts from the language grammar using a variant of BNF as described below:
For the grammar actually implemented in the compiler, see the Slang Programming Language Grammar.
Code listings appear in sections formatted like this.
However, excerpts from the grammar look like this.
Code written within the document text is monospaced.
Mathematical expressions need specialized font support. Hopefully, you have at least one font capable of displaying the appropriate ranges of characters.
This section provides instructions for getting up and running with Slang. Regardless of your operating system or hardware, the first thing you'll need is some version of the Java Virtual Machine. The HotSpot VM, previously of Sun and now of Oracle, is the most commonly-known example. You'll also need a Java compiler and supporting libraries. To get both in the same package, I recommend installing the JDK, which you can download at http://www.oracle.com/technetwork/java/javase/downloads/index.html. The linked page offers directions if needed. Once you've completed this step, download the Slang distribution and proceed to one of the subsections below according to your platform.
This section covers all versions of Windows from at least XP to 7, likely including 2000 and NT4 as well.
If you wish to rebuild the runtime and the standard library, run %SPL_ROOT%\make.cmd. This may fail if you don't have a program such as nmake to handle Makefiles. If necessary, there may still be an ancient version of nmake available at http://download.microsoft.com/download/vc15/patch/1.52/w95/en-us/nmake15.exe. Note that this is a 32-bit executable designed to run on Windows 95, so activate any applicable compatibility settings. You'll need to do this whenever you use the Foreign Function Interface.
If you'd like to recompile the compiler itself, open %SPL_ROOT%\compiler\slang.sln with Visual C++ and proceed as with any ordinary C++ project. The solution is from VS2008, but newer versions should be able to update it.
This section should cover all Unix-like operating systems, including but not limited to *BSD, Linux, and Apple OS X.
If you wish to rebuild the runtime and the standard library, go to $(SPL_ROOT) and type make -f Makefile.posix lib. You'll need to do this whenever you use the Foreign Function Interface.
I've tested modified versions of Slang's POSIX scripts under Interix, but I can't be certain they're correct for all platforms. Please report any problems you encounter.
The compiler source has comments designed to be parsed by DoxyS. If you'd like to see this automatically-generated documentation, first install DoxyS (available at http://www.doxys.dk/doxys_homepage/index.html) and then run slang\doc\autodocs.bat.
Portions of the runtime source also have comments designed to be parsed by JavaDoc.
In Slang, any datum is called a value. These values are organized into groups, the members of which are similar according to certain properties. These groups, represented intuitively as sets, are called types, and it's often helpful to refer to types rather than individual values. In Slang, types do not overlap, meaning the intersection of any two types is empty. Therefore, any given value has exactly one type because it only has membership in a single group of values.
I've further organized the types into three distinct categories: primitive, composite, and mutable. The shared properties of each category are described in their respective headers.
This section addresses Slang's primitive types, the values of which comprise the basic data of the language. Primitive values may be represented directly in the source code with literals. All primitive values are immutable, meaning that operations over them never happen in-place and instead generate new values. Slang provides no widening or narrowing conversions. This means, for example, that there are no typecasts. However, the standard library provides limited mappings between certain types subject to certain restrictions.
The integer type, written int, is probably the most important set of values in the language. For performance reasons, most programming languages restrict the range of integers to what will fit comfortably in one or two machine words. In Slang, however, int values have potentially infinite precision and can therefore represent any integer up to the limit of your computer's resources.
zero = 0 nonzero = 1 | 2 | ... | 9 digit = zero | nonzero integer-literal = zero | nonzero digit*
Valid literals must be written in base ten and cannot have any zero-padding. A leading zero does not indicate an octal literal as in other languages. Integer divison is a special operation and returns a 2-tuple containing the quotient and remainder, in that order.
| Valid | Invalid |
| 63 | 063 |
| 0 | 00 |
Arithmetic operators:
| Operator | Arity | Notation | Type | Annotation |
| + | binary | infix | int * int -> int | addition |
| - | binary | infix | int * int -> int | subtraction |
| * | binary | infix | int * int -> int | multiplication |
| / | binary | infix | int * int -> int | quotient |
| % | binary | infix | int * int -> int | modulo |
| div | binary | infix | int * int -> int * int | division (returns both Q and R) |
| ^ | binary | infix | int * int -> int | expontentiation (exponent must be in [0,2^32-1]) |
| - | unary | prefix | int -> int | negation |
Bitwise operators:
| Operator | Arity | Notation | Type | Annotation |
| & | binary | infix | int * int -> int | bitwise and |
| | | binary | infix | int * int -> int | bitwise inclusive or |
| :: | binary | infix | int * int -> int | bitwise exclusive or |
| << | binary | infix | int * int -> int | left shift |
| >> | binary | infix | int * int -> int | right shift (preserves sign) |
| ~ | unary | prefix | int -> int | bitwise not |
The left- and right-shift operators could be formally specified as multiplying their LHS by 2RHS and 2-RHS, respectively. For example, x << y is equivalent to x * 2^y, and x >> y is equivalent to x * 2^-y. However, shifting is much more efficient in this case due to the internal representation of integer values.
Slang takes a hybrid approach to arbitrary-precision integers. When values are relatively small, integers are stored in big-endian machine-sized fields, but as soon as an operation overflows, the operands are promoted to a library-backed little-endian sign-magnitude representation. Evaluation then continues unhindered, albeit much more slowly. To do this, the runtime checks every over- or underflowable operation. For large multiplies and squares, the runtime switches from a "schoolboy" algorithm first to Karatsuba and then, for even larger computations, to Toom-Cook-3.
These values could be said to have potentially infinite precision, but it's more correct to say they have arbitrary precision. In mathematics, the real numbers comprise a dense set, meaning that there are infinitely many numbers between any two real numbers. However, due to finite hardware resources, it's impossible to represent all real numbers in computer hardware. Instead, we use floating-point representations that can closely approximate most real numbers. Unfortunately, not all real numbers have an exact representation in binary floating-point form, and sometimes the implementation has to approximate. The most popular floating-point format in traditional programming languages is IEEE 754, first defined in 1985 and updated in 2008, but the standard only works with fixed-size values. Instead, Slang uses a third-party library to implement its real type.
real-literal = integer-literal . digit*
To construct a real literal, you must write, at the very least, a valid int literal followed by a period. You may optionally follow the period with any number of numerals without restriction.
| Valid | Invalid |
| 63. | 063. |
| 0.314 | .314 |
| 2.500 | 02.500 |
| Operator | Arity | Notation | Type | Annotation |
| + | binary | infix | real * real -> real | addition |
| - | binary | infix | real * real -> real | subtraction |
| * | binary | infix | real * real -> real | multiplication |
| / | binary | infix | real * real -> real | division |
| ^ | binary | infix | real * real -> real | exponentiation |
| - | unary | prefix | real -> real | negation |
The implementation of real values and operations (via the Apfloat library) is sophisticated, using number-theoretic transforms for many operations. It is, however, tuned for very large or very precise operations. This overhead limits performance for operations with small operands. Therefore, you should prefer float values and operations for most ordinary purposes.
In other languages, this word is usually reserved for the type of single-precision IEEE 754 numbers, but in Slang, float values are guaranteed to have double precision (64 bits). You should prefer this type over real unless you need more than 16 or 17 digits of precision.
float-literal = real-literal f
A valid float literal is merely a real literal followed immediately by a lowercase letter f. This type supports all the same operations as its arbitrary-precision sibling.
A single char can hold any modern Unicode code point. The size is guaranteed to be at least 32 bits to allow for future expansion of the format. Contrast this with Java characters, which are 16-bit fields and therefore cannot represent many valid code points.
hex-digit = digit | a | b | ... | f | A | B | ... | F escape-sequence = \n | \r | \t | \\ | \u hex-digit6 valid-char-symbol = escape-sequence | \' | <any UTF-8 character except CR, LF, and single-quote> character-literal = ' valid-char-symbol '
To create a char literal, you need two single quotation marks surrounding either a UTF-8 character in the closed range [0x20, 0x7e] or an escape sequence. When writing escape sequences, be aware that all Unicode codepoints fall within the closed range [0,0x10ffff].
| Valid | Invalid |
| ' ' | '' |
| '\n' | '\q' |
| 'X' | 'abc' |
| '\u000041' | '\u41' |
Many programming languages implement strings as lists or arrays of characters. Slang doesn't. In memory, a Slang string is a contiguous, immutable, encoded sequence of Unicode codepoints. Slang provides functions in its standard library for converting strings to and from character sequences. This is because the internal representation of Slang strings uses UTF-16 encoding, and any codepoint between U+10000 and U+10FFFF uses four octets in the string rather than two. Consequently, many string operations that are constant-time in other languages are linear-time in Slang. This happens because, as mentioned above, characters are not aligned on uniform octet boundaries, and therefore it is impossible to jump to an arbitrary index in the string in constant time. It is generally recommended that you use library function explode to convert a string into a sequence for processing, then implode that sequence back into a string when you're done. This coding practice forces the programmer to remember at every step of coding that string operations are linear-time. A sequence of char, on the other hand, offers logarithmic-time random access.
valid-string-symbol = escape-sequence | \" | <any UTF-8 character except CR, LF, and double-quote> string-literal = " valid-string-symbol* "
String literals may be written as two double quotation marks surrounding zero or more UTF-8 characters in the range [0x20, 0x7e] or escape sequences, in any order. Any characters outside of that range are illegal. Multiline literals, for example, are illegal, as they require you to put a newline in the literal.
| Valid | Invalid |
| "" | "\q" |
| "Slang" | " " |
| Operator | Arity | Notation | Type | Annotation |
| + | binary | infix | string * string -> string | string concatenation |
Slang doesn't believe in 3VL. Boolean values, all of which are of type bool, represent either truth or falsity.
boolean-literal = true | false
The only possible values are the literals true and false. There is no conversion to or from the integers, implicit or explicit.
| Operator | Arity | Notation | Type | Annotation |
| or | binary | infix | bool * bool -> bool | logical inclusive-or |
| and | binary | infix | bool * bool -> bool | logical and |
| not | unary | prefix | bool -> bool | logical negation |
In case you've forgotten, here are the truth tables for the binary logical operators:
| and | T | F |
| T | T | F |
| F | F | F |
| or | T | F |
| T | T | T |
| F | T | F |
The current implementation of the Boolean operations provides short-circuit semantics. If the LHS of a logical-or evaluates to true, the RHS isn't evaluated, and the expression "short circuits" to true. Similarly, if the LHS of a logical-and evaluates to false, the RHS isn't evaluated, and the expression short circuits to false. This limited form of lazy evaluation enables the programmer to "guard" dangerous expressions, thereby avoiding exceptions. For example:
(* this isn't safe -- what if y is zero? *) if (x / y == 6) { } (* guard expression introduced to prevent divison by zero *) if (y <> 0 and x / y == 6) { }
The unit type, which Slang refers to as void, is a singleton set, meaning it has only one value.
void-literal = ()
This can be stored in variables and passed to functions and is often used when the programmer "doesn't care" about a function parameter or return type.
| Symbol | Operands | Notation | Type | Annotation |
| == | binary | infix | $a * $a -> bool | value equality |
| <> | binary | infix | $a * $a -> bool | value inequality |
| < | binary | infix | int * int -> bool real * real -> bool |
less-than ordering |
| > | binary | infix | int * int -> bool real * real -> bool |
greater-than ordering |
| <= | binary | infix | int * int -> bool real * real -> bool |
less-than-or-equal ordering |
| >= | binary | infix | int * int -> bool real * real -> bool |
greater-than-or-equal ordering |
The composite types enable the programmer to create structured data. Slang provides direct syntactic support for literals of these types. All composite values containing either primitive values or other composite values are immutable. However, a composite value containing a mutable value (§2.3 Mutable Data) anywhere in its substructure must be treated as mutable.
The type of a sequence is the type of its elements surrounded by a pair of square brackets. For example, a sequence of integers would be written [int]. Sequences are immutable, meaning that all operations create new sequences, and no operations occur in-place. This provides worry-free thread-safety within a process without needing to copy shared data. Sequences are also fully persistent, meaning previous versions of any given sequence remain valid as long as they're reachable by any path from live program variables.
seq-literal = [ expression-list ] | [] expression-list = expression , expression-list | expression
The empty sequence is written with an empty pair of matching brackets. All other sequences contain a comma-delimited list of expressions.
| Symbol | Operands | Notation | Type | Annotation | Time Complexity* |
| +> | binary | infix | `a * [`a] -> [`a] | cons (push-left) | O(1) |
| <+ | binary | infix | [`a] * `a -> [`a] | snoc (push-right) | O(1) |
| @ | binary | infix | [`a] * [`a] -> [`a] | append | O(log2 min(|L|,|R|)) |
(* Amortized.)
Access to sequence contents is provided through the standard library, which offers constant-time deque operations including head/car, tail/cdr, reverse-head/rac, and reverse-tail/rdc. Querying a sequence's length is constant time, and sequences are indexed for log-time random access.
Slang allows you to write sequence comprehensions.
seq-comprehension = [ expression || pattern in expression ; expression ] | [ expression || pattern in expression ]
More specifically, the comprehension has the semantic structure [ <element-expression> || <pattern> in <source> ; <guard-condition> ], where the guard is optional for sequence sources, and imposes the following restrictions:
The comprehension has two distinct behaviors, depending on the source:
For example, given some function zplus: void -> (void -> int) that returns a closure generating all positive integers {1, 2, 3, ...}, you might generate the first 20 squares {1, 4, 9, ..., 400} as follows:
[x^2 || x in zplus (); x <= 20]
If, on the other hand, you have some function range: int * int -> [int] that returns a sequence of all integers in the closed range defined by its arguments, you might generate those first 20 squares this way:
[x^2 || x in range (1,20)]
If you wanted only the odd squares, you would write either
[x^2 || x in zplus (); x <= 20 and x mod 2 == 1]
or
[x^2 || x in range (1,20); x mod 2 == 1]
If you wanted to transform a sequence of integer pairs into a sequence of sums of each pair, you'd write:
[x + y || (x,y) in [(1,2),(3,4),(5,6)]]
Sequence comprehensions make the implementation of certain algorithms both clearer and easier to write. For example, consider the following simple, if inefficient, implementation of quicksort:
fun qsort (seq: [int]): [int] {
if (seq == []) {
return [];
} else {
def pivot: int = head seq;
def rest: [int] = tail seq;
return qsort [x || x in rest; x <= pivot] @
[pivot] @
qsort [x || x in rest; x > pivot];
}
}
A better implementation would take advantage of the partition() function provided in the standard library.
The type of a tuple is an ordered, asterisk-delimited series of the types contained within the tuple. For example, the type of a 2-tuple (pair) containing an integer and a string would be written int * string. In type theory, we call this a Cartesian product of sets. All tuples are immutable, but they may contain mutable types.
final = ( expression-list )
The empty tuple is interpreted as the void literal (§2.1.7 Unit). Two n-tuples are equal only if their contents are equivalent.
| Symbol | Operands | Notation | Type | Annotation |
| # | binary | infix | $tuple * int -> `a | access to tuple element |
| == | binary | infix | $tuple * $tuple -> bool | tuple equality |
| <> | binary | infix | $tuple * $tuple -> bool | tuple inequality |
Where $tuple is some tupled type of two or more elements.
record-literal = { member-list } member-list = member , member-list | member member = identifier = expression
To construct a record literal, write a comma-delimited list of member entries between open and close curly-braces, where each member entry is a key/value pair separated by an equals sign. For example, {name="Sean", age=25} is a valid record literal.
There is no such thing as an empty record: all records must have at least one member. Records are first-class values, and the equality/inequality operations are defined over all records that do not contain values of incomparable types. Two records are equal only if all their members are equal, and two members are equal only if both their names and their values are equal.
access-expression = final . identifier
As defined in the above production, the binary operator . may be used to access record members by name. This member-access operator is left-associative and requires a record value on the left and a name on the right. Therefore, you can write series of accesses into nested record values.
Unfortunately for those programmers used to mutable records, Slang's records are immutable, meaning that once created, they may not be changed.
(* name the record type *) type Person = {name: string, age: int}; (* simulate a constructor *) fun Person (n: name, a: int): Person { if (n == "") { throw "name cannot be empty"; } if (a < 0) { throw "age cannot be negative"; } return {name=n, age=a}; } (* instantiate "object" *) def me: Person = Person ("Sean", 25); (* display some info from record *) print ("My name is " + me.name + ".\n");
Notice that the symbol Person was used as both a type literal and an identifier. Slang does not prevent you from doing this.
data-statement = data type-parameter-list? identifier = data-constructor-list ; type-parameter-list = ( type-variable type-parameter-list' ) | type-variable type-parameter-list' = , type-variable type-parameter-list' | ε data-constructor-list = data-constructor data-constructor-list' data-constructor-list' = | data-constructor data-constructor-list' | ε data-constructor = identifier : type-expression | identifier
In traditional programming languages, this mechanism is generally referred to as a discriminated union, meaning a union of types with a regular interface that exposes a tag enabling the programmer to distinguish between them. Nearly all functional languages provide some mechanism for the construction of algebraic data types. Unlike the type-unsafe unions in C-like languages, Slang unions are typesafe, meaning that the programmer cannot access the wrong union member, whether intentionally or by accident. For example, in C, the programmer may fail to specify an appropriate tag field, and even when given well-formed unions, the programmer may still neglect to branch on the tag. Slang, however, enforces safety by only allowing the programmer to branch on the deep structure of a value, requiring the explicit specification of relevant and appropriate tags.
Data statements follow a simple format in a specified order:
The list of type parameters must be parenthesized if it contains more than one type variable. Each data constructor consists of an identifier optionally followed by a colon and a type expression specifying which values they accept as arguments. Those data constructors without type expressions are called nullary, meaning they have arity zero and therefore neither want nor accept any arguments. Algebraic data types can be used to implement enumerations with nullary data constructors, as in the following example:
data Color = Red
| Green
| Blue;
The ur-example of algebraic data types is the list, which may be defined over integers as follows:
data IntList = Nil
| Cons: int * IntList;
However, that definition is needlessly specific. If you wanted a list that could contain characters, for example, you'd have to create an entirely new algebraic data type (perhaps CharList) and corresponding functions. Considering that Slang has a potentially infinte number of types, this would quickly become tedious. A version parameterized over any type would look like
data `a List = Nil
| Cons: `a * `a List;
Consider the construction of a list using the above definition that contains the first three positive integers:
Cons (1, Cons (2, Cons (3, Nil)));
Walking such an inductive construction requires the match-statement (§5.3) and recursion.
I keep this category of types as small as possible.
The type of a function is its domain type followed by an arrow and then its range type. For example, a function mapping integers to reals would be written int -> real. Functions are mutable because calling them can and often does change their state.
In Slang, all functions are closures, meaning that they capture values for all free variables from the enclosing environment as they existed at the moment of the function's creation. This leads to different behavior than coders of most C-style languages would expect in that changes to variables in shallower scopes are not visible to other functions that "share" those same variables. Slang functions are also first-class values, meaning they can be treated like any other values: passed as arguments to other functions, created as literals, returned from functions, and so forth. They may appear at any depth of scope, meaning Slang supports nested and local functions.
No comparison operations are defined over functions.
This construction is almost equivalent to a def-statement with a function-literal except that it's the only way to recur.
fun-statement = fun identifier parameter-list : type-expression block | fun identifier parameter-list block parameter-list = ( param-list ) | void-literal param-list = parameter , param-list | parameter
Note that an "empty" parameter list actually specifies that the function takes only the void-literal argument, written ().
The simplest possible function, aside from a trivial empty void-valued function, is the identity function, which returns its argument unchanged:
fun id (e) {
return e;
}
Recursion is allowed with this construction. Consider a version of the factorial function:
fun fact (n) {
if (n == 0) {
return 1;
} else {
return n * fact (n - 1);
}
}
However, the Slang grammar does not lend itself well to tail-recursive optimizations, so deep recursion on the order of thousands of calls will likely blow the stack.
Anonymous functions are values and may appear in expressions like any other value, provided you obey the applicable semantic rules.
function-literal = lambda parameter-list : type-expression block
Recursion is not possible with anonymous functions because they have no name and therefore no way of referring to themselves. They are equivalent to shortcut-form functions in every other way.
If you wanted a function to compute the square of its integer argument, you might write something like the following:
lambda (n) { return n * n; }
Since functions are first-class values, you can (among many other things) store functions in variables.
def sqr = lambda (n) { return n * n; };
Of course, in the above example, you would likely prefer to use a fun-statement to reduce keystrokes.
The channel is designed to facilitate interthread communication.
channel-literal = channel type-expression construction-type = atom-type channel
Above are the relevant productions for the two purposes of the channel reserved word. The first rule enables the programmer to create a channel literal by specifying the type of values it will accept. The latter rule provides a type-constructor-like syntax for describing the type of a channel thereby created. For example, a definition for a variable c containing a channel of integers would look like:
def c: int channel = channel int;
Note again that the same reserved word is used in both expression and type contexts.
All channel values are mutable, but access to them is guaranteed to be threadsafe. Therefore, multiple threads can share a single channel without fearing about overlapping reads and writes. In general, operations on channels are asynchronous and only block on reads if there are no values available and on writes if there's no space available. This is the idiomatic way for threads to communicate. Due to their mutable nature, however, you're exposed to some potential pitfalls.
Consider the task of creating a sequence of n distinct channels of type int. The most obvious imperative solution would involve a loop pushing channel literals onto a sequence accumulator:
(* this is fine, albeit verbose *)
def channels = [];
def i = 0;
while (i < n) {
channels = channels <+ channel int;
i = i + 1;
}
And this is sufficient. However, you might want to avoid cluttering your code with the loop and the spurious counter and instead take advantage of the generate() function provided in the standard library. To do this, you need to create a fresh channel for each element in the sequence, which means a simple function that returns a new channel instance from each call.
(* this is shorter and less error-prone *)
def channels = generate (lambda () { return channel int; }, n);
A naïve programmer might attempt to return an existing channel value from the first argument, but this would lead to a sequence filled with instances of the same channel.
(* you probably DON'T mean to do this *) def c = channel int; def channels = generate (lambda () { return c; }, n); (* now channels is filled with n references to c *)
The standard library provides send and recv functions for writing to and reading from a channel, respectively. We can observe these functions' behavior in a singlethreaded program.
def c = channel int; (* create new channel *) send (c, 65535); (* asynchronous send; no rendezvous necessary *) def i = recv c; (* take the value *) print (int2str i); (* should print: 65535 *)
As addressed in the previous section, every value has a type. This enables the compiler to typecheck (§3.4 Type Checking) your code and determine whether you have made certain classes of errata. Also, types act as documentation, giving a hint to other programmers about how you intend a given variable (§4 Variables) to be used.
In programming language design, typing is a contentious issue. Most languages can be categorized according to the following (grossly simplified) criteria:
The C programming language's type system can be described as having the properties static, unsafe, and weak. In contrast, Python's type system is dynamic, safe, and strong. Slang's type system, on the other hand, is best described as static, safe, and strong.
Slang recognizes an expressive language-of-types that is not subject to the ugly warts of, for example, function-pointers in C and delegates in C#.
type-expression = production-type production-type = tuple-type -> production-type | tuple-type tuple-type = construction-type tuple-type' tuple-type' = * construction-type tuple-type' | ε construction-type = atom-type channel | atom-type identifier | atom-type atom-type = ( production-type ) | ( type-list ) | [ production-type ] | { member-type-list } | type-literal | ` identifier | identifier type-literal = int | real | float | bool | char | string | void member-type-list = member-type , member-type-list | member-type member-type = identifier : production-type type-list = type-expression , type-expression type-list' type-list' = , type-expression type-list' | ε
Operator -> represents a function which maps the left operand (domain) to the right operand (range).
Operator * in this context creates a Cartesian product of its operands. Slang refers to this construction as a tupled type.
The record type consists of a pair of curly braces surrounding a comma-delimited list of member types, each of which is written as a colon-delimited pair of name and type. For example, the type of a record containing one member named f that maps integers to integers would be written {f: int -> int}.
Parenthesization works as expected. The square brackets define the type of a homogeneous sequence of the contained type and the curly braces define the type of a record of the contained member types.
[string * int] -> [{name:string, age:int}]
The above type expression describes a function which takes as its argument a sequence of pairs (of string and int) and returns a sequence of records (of members name:string and age:int).
type-statement = type identifier = type-expression ;
Creates a type alias. Unlike nominatively-typed languages such as C++, Slang's type-statement is structurally typed such that two aliases (or, indeed, any two types) are considered the same type by the semantic analyzer if the types they refer to are identical.
type point3d = real * real * real;
These can be placed in any scope, and they obey scoping rules.
{
type QQ = int;
def x: QQ = 0; (* fine *)
}
def y: QQ = 0; (* error: QQ is not defined *)
Slang uses the implicit form of parametric polymorphism, meaning that the universal quantification of type parameters is omitted. Explicit type information is still required for all definitions and parameters, however, and type variables may appear in type expressions in most contexts. A monomorphic type is any type without unbound type variables, while a polymorphic type is any type containing unbound type variables, that is, anything fitting the following excerpt from the language-of-types:
atom-type = ` identifier
This is the form of an unbound type variable. The backtick is mandatory. In theory, the grammar could allow the programmer to write unbound type variables without adornment, but they wouldn't be easily distinguished from bound types at a glance. This is admittedly a cosmetic issue, but I feel it's justified.
In Slang, all type variables are implicitly universally quantified over the type expression in which they appear. Consider a type expression `a * `a -> `a. Mathematically, the programmer has written ∀a ∈ T. a × a → a, where T is the set of all possible Slang types. Unlike Haskell, Slang provides no means for making these quantifications explicit. Also, Slang offers no means by which the programmer may constrain quantification, but such a feature is planned. Haskell's implementation of type classes is a reasonably elegant solution.
Since the programmer has omitted the universal quantification of type parameters, as addressed in the preceding section, the typechecker must first assume said quantification and then attempt to infer types as best it can. This requires the creation and maintenance of an environment of substitutions from type variables to type expressions. Typechecking hinges on a variation of Robinson's unification algorithm.
Several examples of formal rules follow. In these rules of inference, Γ is an environment mapping assumed substitutions from variable identifiers or type variables to type expressions, and any premise or conclusion of the form Γ ⊢ expr is a judgement, meaning that expr can be inferred from some subset of assumptions in Γ. The function ftv(Γ) represents the set of all type variables free in the context of Γ, and this set of course has unbounded cardinality.
We begin with what some have called a tautology or identity, which establishes the type of a given variable identifier (or type variable) in the environment:
| Γ(x) = τ |
| Γ ⊢ x : τ |
Then we proceed with various inductive rules. Some examples follow:
| def x: α = e; α ∈ ftv(Γ) Γ ⊢ e : β | Var-Def |
| Γ(x) = β | |
| Γ ⊢ e1 : τ1 Γ ⊢ e2 : τ2 … Γ ⊢ en : τn | Tup-Con |
| Γ ⊢ ( e1, e2, …, en ) : τ1 × τ2 × … × τn | |
| Γ ⊢ ( e1, e2, …, en ) : τ1 × τ2 × … × τn (1 ≤ i ≤ n) | Tup-Acc |
| Γ ⊢ ( e1, e2, …, en ) # i : τi |
| Γ ⊢ e1 : α Γ ⊢ e2 : α … Γ ⊢ en : α | Seq-Lit |
| Γ ⊢ [ e1, e2, …, en ] : [α] |
| Γ ⊢ f : τ1 → τ2 Γ ⊢ x : τ1 | Fun-App |
| Γ ⊢ f x : τ2 |
| Γ ⊢ ⊕ : α × β → τ Γ ⊢ e1 : α Γ ⊢ e2 : β | Bin-Het-Op |
| Γ ⊢ e1 ⊕ e2 : τ |
| Γ ⊢ +> : τ × [τ] → [τ] Γ ⊢ e1 : τ Γ ⊢ e2 : [τ] | PushL |
| Γ ⊢ e1 +> e2 : [τ] |
Note that due to typographical constraints Slang realizes × as * and → as ->.
The typechecker doesn't require that all unbound type variables eventually become bound to some monomorphic type, though the utility of such code is unclear.
This is an advanced technique that novice programmers should probably avoid. You can omit type annotations in any position in the grammar that expects a parameter. You can also omit function ranges. When you do either of these things, the typechecker will do its best to infer the most general type to fit what you omitted. This is not always possible, and the error message may not make much sense.
The places where you can omit type annotations are limited to the following:
You cannot omit annotations from native statements, for example, because the compiler can't understand the Java source that implements them. You also can't omit type information for catch handlers, because the compiler has no other way to know which handler to pick. When in doubt, provide annotations.
For reference, consider this annotation-free program:
include std.basic;
include std.io;
fun map (f, seq) {
if (seq == []) {
return [];
} else {
return f (head seq) +> map (f, tail seq);
}
}
fun foreach (f, seq) {
if (seq == []) {
return;
} else {
f (head seq);
foreach (f, tail seq);
}
}
fun main (args) {
(* I've formatted this line for better readability *)
foreach (print,
map (int2str,
map (lambda (n) { return n * 2; },
[1,2,3,4])));
}
This should display 2468.
Variables enable you to associate names with values. In particular, the lexical environment maps variable names to pointers-to-values. When you assign a new value to a variable, its corresponding pointer in the lexical environment is updated to refer to the new value.
To declare a variable, you must know how to write a valid identifier.
identifier = identifier-initial identifier-body* identifier-initial = letter identifier-body = letter | join | digit letter = <any Unicode character in any letter category> join = _ digit = 0 | 1 | ... | 9
Unlike similar languages, Slang rejects all underscore-initial identifiers, preferring instead to reserve them for internal use. However, legal Slang identifiers can have Unicode characters from any of the following general categories:
For more information, see http://www.unicode.org/reports/tr44/#General_Category_Values.
Before you can use a variable, you must first declare it.
def-statement = def parameter = expression ; parameter = pattern : type-expression pattern = ( pattern-list ) | identifier pattern-list = pattern , pattern-list | pattern
In Slang, declaration is initialization because the def statement requires an initial value. The language requires this for a number of reasons covered elsewhere in this document.
def x: int = 0;
Since Slang allows you to use patterns of identifiers, you can create interesting declarations.
def (x,y): int * int = (7, 11);
def (id, (x,y)): string * (real * real) = ("some_particle", (3.14159265, 2.71828183));
You can and likely should omit type annotations from most declarations. In most cases, the compiler will infer the type successfully (§3.5 Type Inference). For example, the above declarations become much easier on the eyes:
def (x,y) = (7, 11);
def (id, (x,y)) = ("some_particle", (3.14159265, 2.71828183));
There's nothing stopping you from taking advantage of the relatively flexible identifier syntax to appropriately name your constants.
def π = 3.14159265f;
Slang is an imperative language, meaning the execution of its programs maintains an implicit body of state. This would be of little use if there were no mechanism to mutate program variables.
basic-statement = assignment-lhs? expression ; assignment-lhs = pattern =
Assignment statements are special cases of the basic-statement, and the compiler has to make a choice between an assignment statement and a normal expression with unbounded lookahead, thereby ensuring that the Slang grammar isn't LL(1). That's the price of C-style assignments. Assignment statements do not evaluate to anything, not even the void literal (), and may never appear where expressions may appear. This ensures that the slight difference between = and == won't trip people up.
Of course, variables are little more than named storage locations for pointers to values. Mutating a variable has no effect on the value to which it refers.
All variables have a fixed lifespan defined by the block in which they are declared. When control reaches the end of the defining block, the variable becomes undefined and cannot be referenced thereafter. Such variables are said to have gone out of scope. The values to which those variables were bound, however, can and often do live on.
Because control-flow constructs rely on conditions, which use Boolean logic, all conditions must evaluate to the bool type. Old C tricks such as using integer values one for true and zero for false will not work. There is no mapping between integers and Boolean values, implicit or explicit, and such mappings are not provided by the standard library.
No control flow construct may appear at global scope.
if-statement = if ( expression ) block else if-statement | if ( expression ) block else block | if ( expression ) block
Note that the parentheses around the condition are always required. The dangling-else problem does not apply, because any else must be immediately followed by either another if statement or a block. This lack of ambiguity in the grammar should help programmers avoid shooting themselves in the foot.
if (condition_1) {
(* ... *)
} else if (condition_2) {
(* ... *)
} else if (condition_N) {
(* ... *)
} else {
(* ... *)
}
while-statement = while ( expression ) block
To maintain consistency, parentheses around the condition are mandatory, though I may relax this requirement later as I have for other control structures. For those of you who may have forgotten how this construct works, consider first the following example:
while (5 > 0) {
(* body *)
}
(* false-resume *)
Execution proceeds first by evaluating the conditional expression, which in this case yields true because five is greater than zero. If the condition had instead evaluated to false, control would have jumped to the point immediately following the closing brace, here marked "false-resume". Instead, control continues into the loop "body", an arbitrary block of code. When control reaches the end of this block, execution returns to the initial step, which involves reevaluation of the condition. Since this particular condition always evaluates to true, control will never leave this loop. We describe this as an "infinite" loop.
There are techniques for avoiding infinite loops. In imperative programming languages, coders often use an integer variable as a loop counter as shown below:
def counter: int = 0;
while (counter < 25) {
(* do stuff here *)
counter = counter + 1; (* if you forget this, infinite loop! *)
}
The above loop will run exactly twenty-five times. Note that omission of the increment would lead to another infinite loop. Nobody's perfect, and programmers sometimes forget to update their loop counters. Off-by-one errors are also disturbingly common, even among professionals. Therefore, I recommend you take advantage of the standard library's higher-level algorithms whenever possible.
match-statement = match ( expression ) { case-list } case-list = case-statement case-list' case-list' = case-statement case-list' | ε case-statement = case pattern-expression block pattern-expression = pattern-operator pattern-operator = pattern-constructor pattern-operator' pattern-operator' = +> pattern-constructor pattern-operator' | <+ pattern-constructor pattern-operator' | ε pattern-constructor = identifier pattern-basic | pattern-basic pattern-basic = ( pattern-expression-list ) | [ pattern-expression-list ] | identifier | primitive-literal | ? | ε pattern-expression-list = pattern-operator+
[...]
return-statement = return expression? ;
If you omit the expression, the output code implicitly returns a void literal. Return statements are meaningless outside functions, and the compiler enforces that they appear inside functions. They may not, for example, appear at global scope.
return n + 4;
continue-statement = continue ; break-statement = break ;
These conditional jumps have the expected C-like semantics and may only appear in while-statements; they are meaningless outside loops, and the compiler will complain if you use them in such a way. You can think of them as structured gotos.
(* let's print some integers *) def seq = [1,2,3,4]; (* looks like an infinite loop but isn't *) while (true) { (* continue sends control to the guard expression above *) if (seq == []) { (* abort loop *) break; } else { (* show and advance *) print (int2str (head seq) + " "); seq = tail seq; (* you could leave this out *) continue; } } (* break sends control here, just after the loop body *) (* the following statements are invalid *) break; continue;
Unlike many similar imperative languages, Slang allows you to call functions with juxtaposition, meaning you should place the function immediately to the left of its argument. Each function may only take one argument and will return only one value, but either or both may be tuples, and in practice the parameter list is often written as if multiple parameters were legal, when in reality the parameter names are pattern-matched out of the tuple. Parenthesization will occasionally be required to clarify order-of-operations, but otherwise they may be omitted. When in doubt, add parentheses.
(* apply some int-valued function f to 7 *) f 7; (* you may opt to add parentheses for aesthetic reasons *) f (7); (* however, parentheses are sometimes necessary, as in this example of two int-valued functions *) f (g 7);
In general, this is the best way to signal that an unexpected or abnormal error has occurred. The standard library provides a few alternative methods, but those aren't covered here. Exceptions propagate up the call stack in a structured way that is outside normal control flow. The programmer should therefore wrap all dangerous, exception-throwing code with appropriate exception-handling logic. This section describes how to do that.
In C, errors were signaled by returning special codes from error-prone functions. This required the pervasive use of out-mode parameters. After detecting an error condition, the programmer could acquire more detailed information by checking a global variable named errno. Any mistakes or omissions along the line could lead to undetected errors with unpredictable consequences.
Java forced the programmer to handle checked exceptions with compile-time errors. This was an improvement, but frustrated programmers would sometimes silence the complaints by producing empty handlers that failed to address error conditions.
In Slang, however, exception-handling is left to the programmer's discretion. This cleaves more to C++'s approach. As a safety measure, any uncaught exception will propagate up to and out of global scope, thereby terminating the program and providing the programmer with the exception's error text and a dump of the call stack.
throw-statement = throw expression? ;
When an exceptional error occurs, standard practice dictates that the programmer should "throw" a value describing what went wrong. The standard library defines many data constructors designed for this purpose, but you may also throw any other value of your choice. In either case, you should document your choice for later users of your code.
throw "you done fucked up";
If you omit the expression, which is only legal in the context of a catch-statement, the code will attempt to propagate an exception that has already been thrown.
try {
(* dangerous code here that might throw some I/O exception *)
} catch (e: IOException) {
(* report exception and maybe do some cleanup *)
print "got an exception!\n";
(* propagate e up the call stack *)
throw;
}
throw; (* illegal -- not in catch handler *)
try-statement = try block catch-list finally block | try block catch-list | try block finally block catch-list = catch-statement+ catch-statement = catch ( identifier : type-expression ) block
Exception handlers, denoted with catch blocks, are associated with certain segments of code via the try block. If an exception is thrown within the guarded code, any handler with a parameter type matching the exception type will be run. Unlike some languages, Slang lacks a mechanism to catch unknown or otherwise unspecified exceptions. Also, you may not catch patterns of identifiers. Consider the following example:
try {
some_dangerous_function_call ();
} catch (n: int) {
(* valid -- handle exception here *)
} catch (e: BasicException) {
(* also valid ... and you might want to pattern-match: *)
match (e) {
case (Empty msg) { (* handle *) }
case Existential { (* handle *) }
(* and so forth *)
}
} catch ((a,b): int * int) {
(* not valid -- should trigger semantic error *)
} catch (p: int * int) {
(* valid -- not a pattern *)
}
Notice also the presence of the finally block in the grammar's productions. These blocks enable you to specify code that will always be run, no matter what happens during the execution of the try-statement. Even a thrown exception cannot prevent control from entering the finally block. Therefore, finally is ideal for ensuring deterministic cleanup of unmanaged resources in the presence of potential errata. However, this power doesn't come without a warning.
In languages such as Java and C#, where null references are allowed, programmers dealing with unmanaged resources such as file handles and database connections are often tempted to write code with the following general structure:
// This snipped is written in pseudo-Java/C#. First, // initialize var to null. This signals that the variable // does not yet refer to a resource. SomeClass var = null; try { // Attempt to set var to a reference to some unmanaged // resource. Unfortunately, the acquisition process can // throw an exception, so we have to wrap it with try. var = SomeClass.acquireResource(); // Do something important with it. var.useResource(); } catch (SomeException e) { // Handle error -- but which step sent us here? } finally { // Check for initialization success, then clean. if (var != null) var.releaseResource(); }
This is hideous for a host of reasons, chief among them being that the program can't necessarily distinguish between initialization failures and usage failures unless the library designer was kind enough to provide distinct exceptions. The programmer might also forget to write the null check, which will inevitably lead to a null-pointer exception. C# introduced its using block to address exactly this problem. Java programmers, on the other hand, are screwed.
In Slang, the programmer can't even write the first line because null references aren't available, and all variables must be initialized to some value. This forces the programmer to wrap the declaration itself in a try. A finally block at that scope is guaranteed to receive an acquired resource, so the branch-on-not-null is also gone. I've demonstrated a flawed version of this technique in the following excerpt:
try {
(* acquire handle *)
def is = open ("some_file.txt", MODE_IN);
try {
(* usage section -- read from the file *)
} catch (e: IOException) {
(* handle read errors *)
} finally {
(* release handle *)
close is;
}
} catch (e: IOException) {
(* handle open failure *)
}
One drawback to this approach is the physical distance between the resource acquisition and the logic that handles acquisition failures. That said, it's the best idiom I've seen thus far.
However, I've intentionally overlooked a complication. You must never allow an exception to propagate out of a finally block. Note that in the above code, close() can fail. If the usage section throws an exception, any exception thrown by close() will essentially overwrite it. The correct solution is ugly as hell, but necessary.
try {
def is = open ("some_file.txt", MODE_IN);
try {
(* ... *)
} catch (e: IOException) {
(* ... *)
} finally {
try {
close is;
} catch (e: IOException) {
(* ignore -- what else can we do? *)
}
}
} catch (e: IOException) {
(* ... *)
}
The astute reader may now suppose that language design must have gone horribly wrong somewhere in the past to require such ghastly bits of code. And to that I say: yeah, you're probably right.
include-list = include-statement* include-statement = include path ; path = identifier . path | identifier
A list of included files may optionally appear at the top of each Slang source file. Nothing may precede these statements, not even comments. A more sophisticated parser may at some point enable you to interleave these with comments or even source code. The path is resolved into a filename such that, for example, usr.util.crypt becomes %SPL_ROOT%\include\usr\util\crypt.slang. A source file hereby referenced is substituted directly in place of its corresponding include-statement. The parser ensures that multiple- and recursive-inclusion cannot occur.
Slang is a relatively simple language and does not have access to low-level details. To compensate, this facility provides direct access to the implementation language, which in this case is Java.
native-statement = native path { import-statement+ } import-statement = import identifier : type-expression ;
The path immediately following the native keyword must be a relative path from %SPL_ROOT%\src\slang\ to a directory containing Java source files that define each function imported. For example, the path lib.concurrent.algorithms would become %SPL_ROOT%\src\slang\include\lib\concurrent\algorithms\.
native userdefined.path.goes.here {
import func1: int -> int;
import func2: int -> int;
(* ... *)
import funcN: int -> int;
}
A native block may appear only at global scope. According to current limitations, all importations must be functions. You must always pass some value back to the caller. When the range of a function is the unit type void, you should return null. If the function has multiple formal parameters, the arguments will be tupled together and passed in via call()'s parameter. If you wish to return multiple values, return them as a tuple. You should have access to all parts of the language runtime. The Slang distribution cannot detect errata in Java source, so program carefully.
An example of this facility follows:
include std.io;
include std.basic;
native usr {
import add: int * int -> int;
}
fun main (args) {
print (int2str (add (2,4)) + "\n");
}
package slang.include.usr;
import slang.runtime.*;
public final class add extends Function
{
public Value call(Value args)
{
return slang.runtime.Runtime.add(args.sub(1), args.sub(2));
}
}
The included Slang file must match its usage in the include statement, and the files referenced by the native statement must match their function names.
The penultimate step is to modify the Makefile for your platform to add any relevant path(s) to the file(s) you wish to be included in the library/runtime archive. In this case, the changes are red-bolded in the following excerpt:
include_files= \
$(SRC_DIR)/include/std/alg/*.java \
$(SRC_DIR)/include/std/basic/*.java \
$(SRC_DIR)/include/std/io/*.java \
$(SRC_DIR)/include/std/math/*.java \
$(SRC_DIR)/include/std/rand/*.java \
$(SRC_DIR)/include/std/sys/*.java \
$(SRC_DIR)/include/std/text/*.java \
$(SRC_DIR)/include/std/thread/*.java \
$(SRC_DIR)/include/usr/add.java
Finally, run your platform's make script. Provided that you made no mistakes, the updated library/runtime jar should appear in slang\lib.
J. A. Robinson, "A Machine-Oriented Logic Based on the Resolution Principle," Journal of the ACM, Vol. 12, No. 1, pp. 23-41, 1965.
J. R. Hindley, "The principal type scheme of an object in combinatory logic," Transactions of the American Mathematical Society, Vol. 146, pp. 29-60, 1969.
L. Damas and R. Milner, "Principal type-schemes for functional programs," in POPL '82: Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1982, pp. 207-212.
L. Cardelli, "Basic polymorphic typechecking," Science of Computer Programming, Vol. 8, pp. 147-172, 1988.
L. Cardelli, "Typeful Programming," SRC Report No. 45, Digital Equipment Corporation, 1989.
F. Pottier, "A modern eye on ML type inference," Internet: http://cristal.inria.fr/~fpottier/publis/fpottier-appsem-2005.pdf, September 2005.
R. Hinze and R. Paterson, "Finger Trees: A Simple General-purpose Data Structure," Journal of Functional Programming, Vol. 16, No. 2, pp. 197-217, 2006.
D. E. Knuth, The Art of Computer Programming, 3ed, Vol. 2. New York: Addison-Wesley, 1998.
T. St Denis, M. Rasmussen, and G. Rose. Multi-Precision Math. Internet: public domain, 10 March 2007. No longer available.
[ sean.p.miller at gmail dot com ]
[ last updated Moon's Day, 14 Feb 2011 ]