XL (programming language)

XL stands for eXtensible Language. It is a computer programming language designed to support concept programming.

XL features programmer-reconfigurable syntax and semantics. Compiler "plug-ins" can be used to add new features to the language. A base set of plug-ins implements a relatively standard imperative language. Programmers can write their own plug-ins to implement application-specific notations, such as symbolic differentiation, which can then be used similarly to built-in language features.

Language

XL is defined at three different levels:
* XL0 defines how an input text is transformed into a parse tree.
* XL1 defines a base language with features comparable to C++
* XL2 defines the standard library, which includes common data types and operators.

XL has no primitive types nor keywords. All useful operators and data types, like integers or addition, are defined in the standard library (XL2). XL1 is portable between different execution environments. There is no such guarantee for XL2: if a particular CPU does not implement floating-point multiplication, the corresponding operator definition may be missing from the standard library, and using a floating-point multiply may result in a compile-time error.

The Hello World program in XL looks like the following:

use XL.TEXT_IO WriteLn "Hello World"

An alternative form in a style more suitable for large-scale programs would be:

import IO = XL.TEXT_IO IO.WriteLn "Hello World"

Syntax

Syntax is defined at the XL0 level. The XL0 phase of the compiler can be configured using a syntax description file, where properties like the text representation and precedence of operators are defined. A basic syntax file defines common mathematical notations, like + for addition, with the usually accepted order of operations.

The parse tree consists of 7 node types, 4 leaf node types (integer, real, text and symbol) and 3 internal node types (infix, prefix and block).

* "integer" nodes represent an integer literal, such as 2. The # sign can be used to specify a base other than 10, as in (2#1001). A separating underscore can be used to improve readability, as in 1_000_000.
* "real" nodes represent non-integral numbers, such as 2.5. Based-notations and separators can be used, as for integer nodes, for example 16#F.FFF#E-10 is a valid real literal.
* "text" nodes represent textual contents. They are normally surrounded by simple or double quotes, like "Hello" or 'a', but the syntax file can be used to add other separators, including for multi-line textual contents.
* "symbol" nodes represent names or operators. Names are sequence of alphanumeric characters beginning with a letter, like Hello. XL0 preserves case, but XL1 ignores case and underscores, so that JohnDoe and john_doe are the same name. Symbols are sequence of non-alphanumeric characters, like * or =/=.
* "infix" nodes represent two nodes related by an infix symbol, like A+1 or 2 and 3. Infix nodes are in particular used to separate lines, with an infix "new-line" symbol.
* "prefix" nodes represent two consecutive nodes, like Write "Hello". It is also used for postfix notations, like 3! or Open?.
* "block" nodes represent a node surrounded by grouping symbols, like (A), [Index] . Indentation is internally represented by a block node.

With the default syntax file, the following is valid XL0, irrespective of any semantics.

A = B + "Hello"

It parses as:

infix("=", symbol("A"), infix("+", symbol("B"), text("Hello")))

Semantics

The XL1 phase is defined as a sequence of operations on the XL0 parse tree. These operations are provided by various compiler plug-ins, that are triggered based on the shape of the parse tree.

Special constructs, translate and translation, are provided by a plug-in designed to facilitate the writing of other plug-ins. The quote construct generates a parse tree. Here is how these notation can be used to implement a plug-in called ZeroRemoval that eliminates superfluous additions and multiplications by zero.

translation ZeroRemoval when 'X' + 0 then return X when 'X' * 0 then return parse_tree(0)

A plug-in can be invoked on a whole file from the command line, or more locally in the source code using the "pragma" notation, as follows:

X := {Differentiate} d(sin(omega * T) * exp(-T/T0)) / dT

The XL1 phase contains a large set of plug-ins, notably XLSemantics, that provide common abstractions like subroutine, data type and variable declaration and definition, as well as basic structured programming statements, like conditionals or loops.

Type System

XL1 type checking is static, with generic programming capabilities that are beyond those of languages like C++ or Ada. Types like arrays or pointers, which are primitive in languages like C++, are declared in the library in XL. For instance, a one-dimensional array type could be defined as follows:

generic [Item : type; Size : integer] type array

A "validated generic type" is a generic type where a condition indicates how the type can be used. Such types need not have generic parameters. For instance, one can declare that a type is ordered if it has a less-than operator as follows:

// A type is ordered if it has a less-than relationship generic type ordered if A, B : ordered Test : boolean := A < B

It is then possible to declare a function that is implicitly generic because the type ordered itself is generic.

// Generic function for the minimum of one item function Min(X : ordered) return ordered is return X

This also applies to generic types that have parameters, such as array. A function computing the sum of the elements in any array can be written as follows:

function Sum(A : array) return array.Item is for I in 0..array.Size-1 loop result += A [I]

Type-safe variable argument lists

Functions can be overloaded. A function can be declared to use a variable number of arguments by using other in the parameter list. In such a function, other can be used to pass the variable number of arguments to another subroutine:

// Generic function for the minimum of N item function Min(X : ordered; ...) return ordered is result := Min(...) if X < result then result := X

When such a function is called, the compiler recursively instantiates functions to match the parameter list:

// Examples of use of the Min just declared X : real := Min(1.3, 2.56, 7.21) Y : integer := Min(1, 3, 6, 7, 1, 2)

Expression reduction (Operator overloading)

Operators can be defined using the written form of function declarations. Below is the code that would declare the addition of integers:

function Add(X, Y: integer) return integer written X+Y

Such "written forms" can have more than two parameters. For instance, a matrix linear transform can be written as:

function Linear(A, B, C : matrix) return matrix written A+B*C

A written form can use constants, and such a form is more specialized than a form without constants. For example:

function Equal(A, B : matrix) return boolean written A=B function IsNull(A : matrix) return boolean written A=0 function IsUnity(A : matrix) return boolean written A=1

The mechanism is used to implement all basic operators. An expression is progressively reduced to function calls using written forms. For that reason, the mechanism is referred to as "expression reduction" rather than operator overloading.

Iterators

XL iterators allow programmers to implement both generators and iterators.

import IO = XL.UI.CONSOLE

iterator IntegerIterator (var out Counter : integer; Low, High : integer) written Counter in Low..High is Counter := Low while Counter <= High loop yield Counter += 1

// Note that I needs not be declared, because declared 'var out' in the iterator// An implicit declaration of I as an integer is therefore made herefor I in 1..5 loop IO.WriteLn "I=", I

Development status and history

XL is the result of a long language design work that began around 1992. The language was designed and implemented primarily by Christophe de Dinechin.

Historically, the XL compiler was written in C++. It had achieved a point where most of the features described above worked correctly, but writing plug-ins was a nightmare, because C++ itself is not extensible, so implementing translate-like statements was impossible. The parse tree was more complicated, with dozens of node types, because it was designed for cross-language support. Moka was a Java-to-Java extensible compiler using the same infrastructure.

Abandoning the cross-language objectives and complex parse-tree structure, a complete rewrite of the compiler was started in 2003. The parse tree was vastly simplified down to the 7 XL0 nodes types now in use. This new compiler bootstrapped in 2004, and all new development is now written in XL. However, this new compiler still has somewhat incomplete XL1 support, although its capabilities already exceed C++ in a few areas.

Ancestry

XL was inspired by a large number of other languages. In alphabetical order:

* Ada inspired some of large-scale program support, exception handling, tasking, and supportability aspects.
* Basic, notably in the more modern variants that dispense of line numbers and support structured programming, showed how simple the syntax of a programming language could be. Basic is one of the first modern languages to not mandate parentheses around subroutine calls.
* C was used as the standard to expect in terms of runtime and machine-level support. XL will not require a virtual machine to run.
* C++ and the Standard template library demonstrated the need for good support of generic types, including implicit instantiation of generics (which Ada lacks).
* Fortran's continued performance lead over C and C++ for numerical-intensive applications helped identify which language constructs would prevent useful optimizations.
* Java demonstrated the importance of a large, portable support library. Java containers also showed the limitations of an approach not based on generic programming. Interfacing with Java code remains an interesting challenge for XL.
* Lisp extensibility was considered as a key factor in its survival and relevance to this day. Lisp was the first language to normalize object-oriented features, despite having been designed years before object-oriented ideas were invented.
* Prolog demonstrated that alternative programming models are sometimes useful and highly productive. Every effort was made to ensure that a Prolog-style plug-in could be written for XL.
* Visual Basic showed how the parse tree representation can be dissociated from its visual presentation. Few people edit VB Forms textually. It is expected that XL edit-time plug-ins will one day provide similar capabilities, by directly manipulating the parse tree.

External links

* [http://xlr.sf.net The SourceForge development page]
* [http://mozart-dev.sf.net The historical development site]
* [http://www.byte.com/documents/s=7784/byt1070853295820/1208_heller.html Article in Byte]
* [http://www.ddj.com/java/184404696 Article in Dr Dobbs Journal]
* [http://xlr.sourceforge.net/Concept%20Programming%20Presentation.pdf Slides presenting XL and Concept Programming]