Tag Archive for 'Language Design'

Global side-effects

Published
by
Victor Nicollet
on July 20, 2009
in Functional
. 0 Comments

Functional programming languages do not allow global state—they don’t really allow any kind of state, but at least local state can be simulated by function arguments. The only way to handle “global” state would be to pass the global variable as an additional parameter (and additional return value) to every function. And it wouldn’t play nice with exceptions either, so every exception would have to carry the values of all global variables.

Besides, global state has the annoying habit of creating hidden dependencies between program parts, which lead to coupling that is hard to break and code that is not re-entrant.

On the other hand, global variables have the clear benefit of making code shorter by making many dependencies implicit. Why pass around data as an argument or a member variable if making it global works just as well?

Some kind of middle ground here would be self-propagating implicit function arguments and return values.

Such arguments would have to be declared at global scope, since they have to be globally accessible. On the other hand, since they are merely arguments, they have no value until a function is called with one, which means the declaration would probably end up looking like:

channel total : int

This would declare an implicitly progated integer argument named “total“. Then, functions could be made to read and write to that channel implicitly as if it were a normal variable.

let rec sum = function
  | [] ->
      ()
  | head :: tail ->
      total <- total + head ;
      sum tail

Since the presence of the channel can be determined statically (it happens at name resolution time)  it can also be made a part of the function’s type signature, which has the double benefit of allowing compile-time checking of channel usage and letting the programmer know which channels must be provided for a function to work:

sum : int list [total] -> unit

The presence of a list of channels before a function means the function must be called in an environment where the channel is available. This means either the environment’s type is inferred to contain that channel, or a conflict appears and the channel must be explicitly defined:

let a = 0 in
bind a as total in
  sum [ 1 ; 2 ; 3 ] ;
  print_int a ;
  sum [ 4 ; 5 ; 6 ] ;
  print_int a

The bind instruction creates an environment where the named variable or expression is automatically updated in the local scope (as if it were applied the principles of assignment I explored last week). That is, every time a function call writes to the channel, the modification is propagated back to the bound variable as soon as the function returns (and the channel always reflects the value of the variable). So the example above would print 6 and 21.

Channel implementation is fairly straightforward : every function that accesses a channel takes an implicit final argument representing the input value of that channel (if the channel is read) and returns an implicit value (if the channel is written to). That value is then locally bound, in the calling function, to either a similar constructor that propagates the use of the channel, or an explicit bind operation for the channel.

Local side-effects

Published
by
Victor Nicollet
on July 17, 2009
in Functional
. 0 Comments

In pure functional languages, variables cannot be modified. In order to perform operations that imperative programmers achieve with variable modification, functional programmers perform re-assignment:

// Imperative
x = sqrt(x);

(* Functional *)
let x = sqrt x in ...

And in the case of a loop, they represent the loop body as a function that is called with different arguments, and the modified value is propagated through the calls as an argument:

// Imperative
x = 0
for (i = 0; i < 10; ++i)
  x += i;

(* Functional *)
let x = 0 in
let rec loop i x =
  if i = 10 then x else loop (i+1) (x+i)
in
let x = loop i x in ...

So, can local modification of variables be allowed in a pure functional context through simple rewriting rules that turn the imperative constructs into their functional counterparts? Yes, although there are some limits.

Simple assignments

We know that there might be assignments within every expression (an assignment is an expression of the form x ← <V> ; <E>). The tactic used here is to turn every expression <E> into an expression of the form:

let [E'] in x1 ← v1 ; x2 ← v2 ... ; e

such that no sub-expression within the “let …” contains an assignment (and is therefore a plain old pure functional language expression) and only variable names appear after the “in …” . This rewriting tactic is applied recursively : atomic expressions (those without sub-expressions) are trivially written as such, which leaves only the question of expressions with sub-expressions that have already been recursively turned into the above format.

The key is to turn op(<A>, <B>, <C>, <D>) into:

let [A'] in
let xa* = va* in
let [B'] in
let xb* = vb* in
let [C'] in
let xc* = vc* in
let [D'] in
let e = op(a,b,c,d) in
xa1 ← va1 ; xa2 ← va2 ; ... xb1 ← vb1 ; ... ; e

The order of the sub-expression is fixed (which means an order of evaluation has to be specified for every operation). Every expression computes all its values (including the asisgned ones) and the assignment is simulated using redefinition of the variable so that subsequent sub-expressions can “see” the modified variable. The actual assignments are then pushed to the end of the complete expression so that the recursive rewriting rule will see them from the superexpression above.

Note that expressions which do not always evaluate all sub-expressions cannot be expressed as above. Fortunately, all such expressions can be rewritten as a conditional and expressions that evaluate all sub-expressions, and conditionals are evaluated above.

Note that a lambda expression is considered to be an atomic expression here, so no propagation of assignment occurs from within the anonymous function to the surrounding context! This means (as expected) that the assignments are a purely local construct that cannot cross function barriers, so I simply remove them when they reach the top level to obtain a normal pure functional expression.

This performs the transform:

(* Imperativeish *)
let x = 3.14 in
x ← sqrt x ; print_float x

(* Functional *)
let x = 3.14 in
let v = sqrt x in
let x = v in
print_float x

Loops and conditionals

Loops, conditionals are special cases of block-based expressions. A block is a language construct that looks like a lambda expression (it gathers all values from the surrounding scope) and may be executed zero, one or several times. The main difference is that a block cannot be saved for later execution, it is always executed at a specified time. In short, a block is a beta-redex. Since we have the guarantee that the block is executed before the current context resumes, we can let it alter the state of the current context.

For every block, I select a set of variables that the block may alter (although it does not necessarily do so). The block itself is syntactically an expression, so I can rewrite its internal assignments as above by moving them all to the top level of the expression. Then, I turn the block into a closure which takes as arguments the aforementioned set of variables, and returns a pair that contains the result of the expression and the final values (after assignment) of the set of variables. In short:

(* Imperativeish *)
{
  a ← 1 ;
  b ← b + 2 ;
  a + b
}

(* Functional *)
fun (a,b,c) ->
  let a = 1 in
  let b = b + 2 in
  a + b, (a,b,c)

I can add completely unused variables (like “c” above) to the set of variables simply because another branch of the construct (usually a conditional) may use that variable as well, and I need both blocks to be functions of the same type.

Then, by transforming any blocks into functions, a conditional follows the rewriting rule :

(* Imperativeish *)
let r = if cond then A else B in ...

(* Functional *)
let r, (a,b,c) = if c then A(a,b,c) else B(a,b,c) in ...

Loops work in the same way :

(* Imperativeish *)
while c do
  A
done ; ...

(* Functional *)
let rec loop (a,b,c) =
  if c then
    let _, (a,b,c) = A (a,b,c) in
      loop (a,b,c)
  else (a,b,c)
in let (a,b,c) = loop (a,b,c) in ...

Records

All of the above only handles assignment to variables. What about assigning to records?

It is of course impossible to alter a record held by someone else. However, if the record is stored in a local variable, then it is possible to change the local variable to take this into account.

The rewriting rule is quite simple, and turns a complex assignment (assign to a record) into a less assignment recursively:

x.label ← y   becomes   x ← { x with label = y }
var           remains the same
anything else causes an error

So, this rule would perform the following transform:

(* Imperativeish *)
x.owner.details.name ← boris ; ...

(* Functional *)
let x =
  { x with owner =
    { x.owner with details =
      { x.owner.details with name = "boris"} } }
in ...

The same approach can be applied to most other assignment operations (array, string, hash table).

Semantic & Symbolic

Published
by
Victor Nicollet
on June 30, 2009
in Functional
. 0 Comments

Our brain interprets variables in two different fashions : semantic and symbolic. Semantic understanding means understanding the meaning of the variable’s name, where long and detailed names like “newCustomers” convey information in plain english and shorter names like “i” and “x” convey information through conventions. Symbolic understanding relies on recognizing the shape of the variable in several locations in code, and deducing from there its actual meaning—in itself, the name is not relevant, your brain just goes “hey, that’s the same variable“. Of course, there is some amount of semantic recognition to symbolic variables, usually because we understand the variable as being a symbol.

Mathematics make much use of symbolic recognition. After all, mathematicians do not write f(number) = 10 × number, they write f(x) = 10x and while one-letter variables do have some amount of semantics associated to them (i,j,k,m,n are integers, x,y,z are reals, p is a prime number, q and r are rationals, f,g,h are functions, t is often seen as time, d is a divisor, P is a predicate or a polynomial) this minimal amount of information is ridiculous when compared to the huge amounts of purely symbolic information one gathers from the use of the letter.

Symbolic recognition works better when the expression is small. In descending order of readability when you’re familiar with the language,

Mathematical notation:

ƒ : A → ∃n∈A. 2|n

Objective Caml:

let f(a) = List.exists (fun n -> n mod 2 = 0) a

C++:

bool f(const std::vector<int> &a) {
  for(std::vector<int>::const_iterator it = a.begin(); it != a.end(); ++it)
    if (*it % 2 == 0) return true;
  return false;
}

I guess there are two things one can learn from this.

First, in a terse language, symbolic recognition works better, which in turns means the programs can be even more terse while retaining their understandability.

Second, don’t bother with long variable names in a two-line function if all the information present in the name can be readily and easily deduced from the two lines in the function.

Value Consistency

Published
by
Victor Nicollet
on March 27, 2009
in Functional
. 0 Comments

Jeff Atwood hates PHP. So do I—despite working with it on a daily basis and leading several interesting PHP-based projects to successful completion, I do find PHP to be a disaster in terms of language design, and despite its gradual improvements over the course of its evolution.

And yet, my biggest issue with PHP is the same I have with C and C++ and, arguably, every single language in the C family with the exception of JavaScript.

Some Examples

Consider a simple get-day-name function:

function french_day_name($timestamp)
{
  return array(
    "Dimanche", "Lundi",    "Mardi",   "Mercredi",
    "Jeudi",    "Vendredi", "Samedi"
  ) [(int)date('w',$timestamp)];
}

You feed in a timestamp, and you get the day’s name in French. It relies on the fact that array() is an array literal, which is an expression (you can assign it to a variable or pass it as an argument to a function) and [] subscripting can be used to extract a certain index from an array. Except that this doesn’t work because the syntax does not allow subscripting into an array literal. Contrast this with JavaScript :

function french_day_name(timestamp)
{
  return [
    "Dimanche", "Lundi", "Mardi", "Mercredi",
    "Jeudi", "Vendredi", "Samedi"
  ] [(new Date(timestamp)).getDay()];
}

This is what I call value consistency: if your semantics allow writing array[subscript], then I expect to be able to use an array literal (or any other expression that evaluates to an array) in that expression. As a matter of fact, I don’t know what kinds of expressions support subscripting in PHP, and that makes me feel insecure so I always assign my array to a variable beforehand.

The same happens in other situations as well. For instance, don’t expect to write (new Date(timestamp)) -> getDay() in PHP: there are restrictions on what kind of expressions are allowed on the left-hand side of the object member operator, too.

Also, don’t expect to write:

$obj -> random = $good_random ? 'mt_rand' : 'rand' ;

// Later

$obj -> random(); // Sorry, not a member function

($obj -> random)(); // Sorry, bad syntax

$rand = $obj -> random();
$rand(); // Good programmer, you get a twinkie

That’s right, there are restrictions on what kind of expressions can be used to call functions as well! At least JavaScript is sane about this.

Value Consistency

For consistency, every operation that can operate on an arbitrary value should have a syntax that lets the programmer specify that value as an expression, whether that expression is a literal, an identifier, or any complex expression that ultimately evaluates to an appropriate value.

There are no circumstances under which syntax alone should prevent an expression to be used in a context where another semantically identical expression can be used.

You’re Not My Type

Published
by
Victor Nicollet
on January 28, 2009
in Functional
. 0 Comments

Consider an extremely simple language. For instance, a language that only has boolean and integer values. You could write, say, MacCarthy’s 91 function with it:

def maccarthy(n):
  if n <= 100
    maccarthy(maccarthy(n+11))
  else
    n - 10

Type-checking this language would be trivially easy, even if you don’t have any type annotations. You’d just have to check whether a given expression is used as an integer, a boolean, neither, or both (and throw an exception in the “both” case). Here, for instance, the operation “n <= 100″ would constrain “n” as an integer and the operation “n-10″ would constrain the return type as an integer, then the various type constraints would be verified for all other expressions.

Requirements and Properties

Static verification involves determining, for every static piece of code (usually, at the expression level):

  • The requirements that allow the code to run correctly. For instance, the fact that a certain value needs to be comparable, that a certain value must be of the same type as another, or that a certain value must be an object with a certain member.
  • The properties that are provided by that code. For instance, the fact that a certain expression always evaluates to an integer, that it always evaluates to an object with a certain member, or that it’s always equal to 91.

In its simplest form, the algorithm would determine the entire set of requirements and properties, and then determine whether the properties satisfy the requirements. For instance, if a variable does not have the “is an integer” property but is subject to a “must be an integer” requirement, the verification fails and indicates the error.

This is the approach used in languages with explicit type annotations, such as C. There, whenever a value is created, its properties are known (whether by the type annotation in its definition or because of the return type of the function that returned it), and whenever it is used its requirements are known (whether by the type annotations of the called function parameters, of the current function’s returned value, or because of a syntactic requirement such as the condition in an ‘if’ statement). And so, starting with the parameters and ending with the return value, the properties for every sub-expression in every function’s body are deduced and then verified.

Of course, the version used in C++ is more complex than that. For instance, the “property satisfies requirement” rule is not a simple yes-no question, but instead has several levels of priority involving implicit conversions, built-in conversions and user-defined conversions (for instance, the property “is an integer” satisfies the “must be a floating-point number“, but with a lower priority than “must be an integer“) in order to resolve overloading and template functions. But the general idea remains the same.

Type Inference

The issue with this simple approach is that it requires annotations—the code deduces properties from type annotations, so the types of all function parameters must be specified. The return type specification can be deduced in some cases (for instance, if there is only one return statement, or if all return statements return the exact same type), and the type of local variables can be deduces from the function or expression used to initialize them. So, you would be left with a “type-inferred” language where the only type annotations ever required (outside of type definitions themselves) would be for function parameters.

It’s also possible to get rid of these type annotations, but it requires an entirely different algorithm : since you don’t know what are the properties of your function parameters, how can you determine whether they satisfy the requirements within your function?

This could be done by allowing the static checker to generate properties based on the requirements that must be satisfied. Of course, that doesn’t tell us how this could be done and, in the general case, it cannot be done. Consider C++ overloading: if a function is overloaded for both integer and vector arguments, then should its argument be an integer or a vector? Introducing an “is an integer or a vector” property is impractical in most cases, and it doesn’t tell the code generator whether that variable is a one-register integer or an SSE-friendly vector—a fatal flaw.

So, full type-inference algorithms only apply in languages with type systems that allow deducing properties from requirements. One example would be the ML type system, which merges properties and requirements together in a single concept of “type”. Since in that system a requirement is a property, there’s no difficulty determining what property a requirement corresponds to.

This means that every operation is not a top-down “I deduce the result from the arguments” process, but rather a two-way “I connect the types of the result and the arguments”. The connection can be, for instance, a type equality (being equal to a certain type, or to the type of another expression), as is the case for the equality operator: if you compare two expressions, then their types are constrained to be equal to each other, which means that in the example below the type of x would be properly inferred as being an integer:

let is_zero x =
  x = 0
;;

This system works pretty well as long as you don’t have types that are too complex. However, any serious language has to handle containers (quite often, functions and objects as well), and these can cause some issues with what has been done so far.

Parametric Types

PHP’s approach to types is pretty straightforward. You have a short list of possible types:

Integer, Floating-Point, Boolean, String, Object, Array, Resource and NULL.

Every single value manipulated inside a PHP program has exactly one type among the above. This makes the language quite simple to grasp, but makes compile-time type-safety impossible to achieve: even if you know the compile-time types of a handful of objects (such as function parameters and return values), you still have no guarantees about what type of objects an array holds, or whether an object has a certain member (and if it does, what its type is), because that information is not part of the extremely simple type system in PHP.

The array problem is usually solved by adding parametric types to the language: instead of an object being an “Array“, the object instead becomes an “Array of X“. This allows the compiler to determine the type of the objects inside the array (if it’s an “Array of X“, then the type of the element is X). Most languages with a static type system (C, C++, Java, C#, OCaml, Haskell to name a few) implement arrays as parametric types.

Some languages stop there: they add only a handful of built-in parametric types (C pointers and arrays) and rely on user-defined types for handling everything else. Other languages push it a step forward and introduce generics or generic-like constructs (C++ templates, Java and C# generics). And yet other languages use parametric types to their full extent to deduce one type from another both ways (OCaml, Haskell).

The ML type system supports parametric types. In fact, because of the way it’s defined, it works because of parametric types. Every final ML type (that is, those types of values that actually end up appearing in the running program) is a formal construct, a tree where every node is a type name and the children of that node represent the value of the type parameters (types with no type parameters are leaves). For instance, an array of integer pairs is described as:

(int * int) array

Or, as a tree-like structure:

[ int ]--
         |--[ * ]---[ array ]
[ int ]--/

The type-checking system allows “unknown” types: these are types which have no constraints and are therefore universal. They are usually represented as quoted type names. For instance, an array of pairs of unknown types:

[ 'a ]--
        |--[ * ]---[ array ]
[ 'b ]--/

Or, in linear form:

('a * 'b) array

This type represents an array of pairs, but the types of the first and second elements are not constrained, so they show up as “anything”.

Type Unification

ML types work through unification. As explained above, every expression applies constraints to types. These are almost always equality constraints (explaining that two types are equal). For instance, I could decide that types (’a * int) array and (int * ‘b) array are equal, and the algorithm would determine that both types are in fact (int * int) array by noticing the ‘a = int and int = ‘b equality constraints. This is known as unification.

The unification process is a simple tree traversal process.

  1. Unification of two trees with different roots (that is, roots that have different names) is always an error. This is why you can’t unify an ‘a list with an ‘a array: the “list” root is incompatible with the “array” root.
  2. Unification of any tree with an unknown tree replaces the unknown tree with the other. This replacement happens everywhere within the program. This also happens if both trees are unknown, of course.
  3. Unification of two known trees with the same root resolves to recursive unification of children (so child N of the first tree is unified with child N of the second tree).

In practice, this means that the unification algorithm determines if there’s a tree that’s compatible with both unified trees (otherwise, there’s an error because you have two incompatible uses of a given value) and if there is one it selects the smallest (so that there are no additional assumptions made on the type beyond those of the two original ones).

Certain expressions perform unification between two existing types. Most expressions actually construct a new intermediary type and perform unification between that new type and other types. For instance:

  • “if A then B else C” unifies A and bool, then unifies B and C, then unifies the expression’s type with B.
  • “F A” unifies F with ‘a -> ‘b, unifies ‘a with A, and unifies the expression’s type with ‘b.
  • “A.(I)” unifies A with ‘a array, unifies I with int, and unifies the expression’s type with ‘a.

Touchscreen Development

Published
by
Victor Nicollet
on January 13, 2009
in Functional
. 2 Comments

A touchscreen is a variation on the traditional screen-and-mouse combination for input-output. One of its main benefits is that aiming is easier when you can just point at things with your finger, which means interaction can be faster. One of its disadvantages is that there is no scale adjustment (you can move a mouse by one inch to move the cursor by a half inch, but one inch of your finger is always one inch of your touchscreen), which leads to increasing the size of buttons, and a larger user interface means a smaller area for displaying back information.

I’ve been looking around for touchscreen-centered development environments. Kodu comes close, since it’s able to work on a television screen with an Xbox 360 controller and could conceivably be controlled through finger pointing. Aside from that, however, I haven’t really found things worth mentioning (but I can certainly have missed some).

One direction I would like to see explored in greater depth is the area of visual (or nearly visual programming languages). For instance, something like:

These screenshots contain code blocks, where each block has a darker tab that serves as its header. Some blocks are short one-liners that only contain elementary code, so they’re on the same line as their header, whereas larger block are drawn below their header. Header colors mean:

  • Dark blue: top-level definitions, these appear as part of the current module.
  • Orange: conditional blocks. All such blocks are examined in order, the first one that matches is evaluated.
  • Light blue: for-loops, these define a new integer variable that traverses a range of integers.
  • Violet: nested definitions, these define a new variable bound to a specified value, and run some code with that binding.

All other code, in the white blocks, is actual code that is evaluated. A block’s value depends on the block type, with most blocks evaluating to their last line, and loops evaluating to an imperative ‘unit’ type.

The point of using blocks is to make the various elements stand out more for interaction, so that they are easier to identify and easier to touch.  The system supports four interaction modes: short presses, drag-and-drop, area select, and long presses. It also handles three distinct modes: view, edit and refactor. A short press on a block does the default action for that block, which depends on the current mode, for instance:

  • In edit mode, touching a dark blue, light blue or violet header inserts the variable defined by that header into the currently edited code.
  • In refactor mode, touching a dark blue, light blue or violet header selects that header for refactoring (it highlights and counts all occurences, and proposes a contextual menu for moving and renaming).
  • In view mode, touching a dark blue, light blue or violet header expands the definition itself. Touching any white block collapses that block. Touching the header of a white block expands that block back, and touching an expanded header collapses that header.

Drag-and-drop can be use to move things around. In view mode, it scrolls the screen. In edit and refactor mode, it moves blocks and lines. Area selection merely selects several touched areas. the difference between area selection and drag-and-drop is that area selection begins outside any blocks. Long presses bring up contextual menus for the activated block.

Done right, I believe this could improve the productivity of programmers by moving them away from the keyboard: not only is the physical speed itself faster, but selecting from a list has proven faster and less error-prone than typing out a name. Besides, automatic naming schemes could be found, for instance adding special documentation comments that suggests names for the return values of a function or the instances of a class.

So, What’s Your Name?

Published
by
Victor Nicollet
on January 6, 2009
in Functional
. 0 Comments

I’ve been having a lot of name-related problems, lately. Not my own name, but the names of various things I have to work with. Nothing unexpected: in the computer world, we tend to use names everywhere.

Every time there are objects to be manipulated by programmers, there’s a way to give names to these objects. It could be the “id” attribute in XML, it could be the name of a file in a filesystem, it could be the name of a variable or member in a program, or it could be the hostname of a web site… A name is, in theory, a set of characters from a predetermined alphabet (that varies based on the application) which is bound to an entity of some sort. Once you hold the name, you can get the associated entity directly.

This theoretical definition leads to two distinct issues:

  • There’s only a small number of acceptable names around. Of course, generic names like “clxbpf8990″ can be used (and if you look at the ids generated by generate-id() in XSLT, this is exactly what happens) but the entire point of a name is to allow people to retrieve content based on the name. As far as the internet goes, there’s only a finite number of names any user can remember—and web users have become increasingly reliant on google and the recently added Firefox 3.0 address bar to find sites with non-obvious names. How do we handle the inevitable collisions?
  • A programmer in Australia has a global variable named Foo in a C program. A programmer in Sweden, working on a different C program, also has a variable named Foo. Should the two collide? What about machine names on local networks? User names on the same machine? Not all names are global, which means that the scope of names has to be determined, and ways of handling collisions between local scopes must be invented.

Yet, it’s not all about collision. The most important element of naming is the ability to find the data bound to a name. This is what directories are for.

The simplest form of directory is the phone directory: you have a name on the left, and a phone number on the right. The directory also happens to be sorted by ascending key order so that dichotomic search can be used to find a given name in logarithmic time (how clever—in the age of search engines, we tend to forget logarithmic search times existed since the days of dictionaries and encyclopedias). Such directories exist in the computer world. The simplest would be the classic user directory, accessed through LDAP (Lightweight Directory Access Protocol) or perhaps ActiveDirectory, but these are not the most frequently encountered by the common user. Another simple example is /etc/passwd:

username:!:100:100:office:/home/username:/usr/bin/sh

User name is on the left, various user-related information is to the right.

Domain Name System

Let’s crank the complexity lever up a little bit. What classic directory format do we use several times a day? The Domain Name System (which most of you know as DNS). Everyone sends out queries to a DNS server, asking for the IP associated with a name. That is, when you type “www.nicollet.net” in your browser, the browser needs to know what server to connect to. The problem is that looking for a server is done by routers, which are usually not very smart: they have routing tables based on masking the IP address (whether that address is IPv4 or IPv6) so they need that address to begin with. So, the browser instead resolves the domain name to an address. This involves looking at the local “hosts” file to see if a definition exists (for instance, “localhost” tends to be bound to the loopback address “127.0.0.1″), then queries any local name services the operating system may provide (this allows you to connect to an HTTP server running on another machine on your network by using that machine’s name, without having to set up a local DNS server or registering with a public one), and finally sends out a query to a DNS server somewhere on the internet (the address of the DNS server is either provided by the ISP itself, or manually entered by the user in a configuration wizard or file). The DNS then returns the address for the domain.

This is where two of my recent name problems came from. As you might remember, one week ago I had to move my blog from one server to another, and in the process, I had to change the DNS entry so that reads who typed in “www.nicollet.net” connected to the new server instead of the old one.

The first issue was that DNS propagation is not instantaneous. Back in the days when the intertubes were often clogged, caching played a big role in avoiding too many DNS queries moving up to the reference DNS server for a given top-level domain. The downside is that when you type in “www.nicollet.net”, you’re not really asking the reference DNS server for domains ending in “.net”, you’re asking the DNS server provided by your ISP, which may decide that its copy of the “www.nicollet.net” address binding is correct, without even asking the reference server (this is what caching is for). So, it took about five hours for all visitors to be correctly redirected to the new website. If any of you posted any comments, they went to the old website and were lost along with it—sorry. Of course, as you can expect, this can get a lot more problematic once you have a highly interactive website. So, you tend to choose an IP address and stick with it (or, if you have to change it, then you have it forward everything to the new one until nobody uses it anymore).

This also meant that any e-mails sent to foobar@nicollet.net were routed to the old MX binding, “mx1.ovh.net” (for those who wonder, a DNS entry contains several bindings: a web browser would look at the main binding for that domain, while a mail delivery program would look for the Mail eXchange binding) even though I was expecting them on the new MX binding, “nicollet.net”.  This took a short while to be sorted out.

The second issue was with the name of the server. See, being listed in a directory doesn’t change your name: it merely gives you a name by which you can be found. So, the name of the famous emperor of Wei is still Cao Cao, despite being posthumously named Wu. And the name of my new server still was r17474.ovh.net despite being now referred to as nicollet.net by the DNS. Then, of course, when some mail arrived for the user foobar@nicollet.net, my qmail-powered server quite naturally answered “there’s no user named foobar@nicollet.net here, please go away” in perhaps not so polite terms. So, I still had to convince my server that it was now known as “nicollet.net” so that the mail delivery could work. Nothing that the “hostname” UNIX command couldn’t solve.

What about local area networks? How come that you can access another machine on your network by using its name? There usually isn’t a central naming service which can be queried by computers on a LAN, and it wouldn’t be practical because it would have to be manually configured on every new computer. Instead, computers on a LAN use NetBIOS to set up local directories: whenever a new computer is hooked up to the network, it broadcasts its hostname and address to everyone else, and everyone else writes down the association in a local directory. Conflicts are resolved quite simply: if two computers have the same name, the last to broadcast is the one that everyone else remembers (this is quite useful if you have to move from an office to another and get a new IP as a consequence).

Names in Languages

Programming languages all provide the user with ways of naming entities that are significant, both for documentation purposes (it’s easier to understand what a value is when it has a reasonable name) and for cross-referencing data defined in one place and used in another.

On the one hand, you have the static compile-time approach. This is the easiest to work with by far, because all the nitty-gritty details are written down in the documentation of the compiler and the build scripts of your application. For instance, most compilers allow the definition of “include paths”, a list of locations on the filesystem where the definitions of objects can be found. When the compiler needs something (an included file in C or C++, a class in Java or Actionscript, a module in Objective Caml), it will look for an appropriately named file in all these locations.

Let’s consider the Objective Caml compiler, “ocamlc”. Whenever a source file contains a reference to another module (by using a symbol in a module context, such as “ModuleName.member” or “Functor(ModuleName)” or “open ModuleName” or something like that), the compiler looks for the compiled interface of that module. This is done by looking for the file “moduleName.cmi” (which is generated manually by running “ocamlc moduleName.mli”) in all the locations configured with the compiler: first, the current directory, then paths specified through the environment variables, then include paths specified with the -I command-line argument. If you’re only compiling the module (flag -c), the result is a cmo file (or cmx file with “ocamlopt”). At link-time, you must then specify all the cmo files required by the program, and the compiler resolves all links based on the name of the cmo file (for simplicity, it’s possible to group together several cmo files as a single cma file : they are simply concatenated together, so using the cma library is equivalent to adding all the cmo files it contains manually).

Java goes a short step beyond this by eliminating the need for a link step. When you import a java class, using the “import abc.def.Foobar;” statement, java understands that by looking at the relative path “abc/def/” it will find either a “Foobar.class” or a newer “Foobar.java” that it can compile to “Foobar.class”. Here, the path is specified relative to one of the include paths (which Java calls classpaths) and can be a normal filesystem path or a path within a JAR archive.

C and C++ are both the simplest and the most complex. In these languages, every reference is explicit. The first step is compilation, where files are included in other files by specifying the relative path. The second step is linking, where libraries and objects are included by specifying the relative path. At each step, additional locations can be specified to look for headers.

PHP has an interesting dual approach to things. On the one hand, its normal cross-file interpretation system consists in include() and require() statements which look for the named file in any of the specified include paths for PHP, which makes it look like SH, C and C++. On the other hand, PHP has also introduced functionality for resolving class names: when a class is used (”ClassName::Member”, “Foobar extends ClassName” or “new ClassName”) but the class is not defined, a special function is called. This lets the user specify an alternative loading scheme, such as looking for a file named ClassName.php and including it. The Zend Framework makes heavy use of this, meaning that the inclusion approach is specified once in index.php (or a common configuration file) and then no other inclusion is used for class filed (arguably, Zend_View still includes phtml files explicitly).

On the other hand, there’s runtime access. This is harder to work with, because there’s less documentation available. Sure, some concepts, such as dynamic linking, are fairly well-documented mechanisms that look for the named file in the current directory first, then in other directories specified as environment variables or system-wide configuration elements (in the case of java, in the classpath, for example). However, even then, some programs insist on working on their own.

I recently had an issue with Alfresco, namely alfresco-mmt.jar which terminated with a ClassDefNotFound exception. Looking for solutions on the internet, I found out that the class it was looking for was defined in a JAR nearby, so I adapted the classpath when running the jar so that the class could be found. Except it couldn’t. The problem with this was that the exception did not specify where the class loader had been looking for the class (or perhaps it did internally, but as an end user with no access to the source code or, probably, a debugger, I couldn’t see it), so I had no way of understanding where the JAR with the class should have been placed. It turns out, the application loaded the JAR from inside its own JAR, so I had to place it there.

Looking for Minima

Published
by
Victor Nicollet
on December 16, 2008
in Functional
. 0 Comments

Annealing is a process to harden metals: by repeatedly heating and freezing metal, atoms within the metallic structure are dislodged and then moved back into place, which moves those atoms that were not part of a regular structure to more correct positions, resulting in a stronger metal piece.

The underlying process is that of energy reduction: an atom in a non-regular position within a crystalline lattice has a high potential energy, but is kept into place because it has reached a local energy minimum (so moving away requires more energy than it has). By imcreasing the available energy, the atom is allowed to move out of the local minimum, and so it ends up in a location with lower energy (with a reasonable probability, though this is by no means certain). By applying this process a high enough number of times, the global minimum can be reached.

Simulated Annealing

In computer science, that process can be applied to minimization techniques: instead of exploring the problem space completely, annealing is simulating by moving around randomly in that space. In order to move towards minima, every move which increases the value can be canceled with a certain probability that increases as time passes.

For example:

let annealing steps energy initial =
  let rec aux n best best_energy current =
    if n = 0 then best else
      let current = random_move current in
      let new_energy = energy current in
      if new_energy < best_energy then
        aux (n-1) current new_energy current
      else if Random.int steps < n then
        aux (n-1) best best_energy best
      else
        aux (n-1) best best_energy current
  in aux steps initial (energy initial) initial

This is by no means the only possible approach: other variations can involve checking whether the move is upwards since the last position (instead of the best position so far) or using a different probability approach for preventing up-moves.

Genetic Computing

A common problem found in simulated annealing and genetic algorithms is the implementation of solutions as programs: since these approaches require the ability to randomly mutate a solution, and a program is usually a fickle and weak construct that can easily die if one of its parts is forcibly removed, representing programs as randomly altered entities is difficult.

One possible solution is to consider stack based-languages: these languages have very light syntax requirements and can be represented mostly as a sequence of words. Besides, the only way for a program in these languages to die is to underflow the stack (which can be easily solved by stating that reading from an empty stack yields a reasonable value, such as zero or one. My concept was to use a language which reads a single integer variable ‘x’ and manipulates a stack ’s’, and outputs a stack of numbers. These numbers are then multiplied together to yield the final result. The available instructions are:

let operations =
  [|
    "nop", (fun (s,_) -> s);
    "pop", (fun (s,_) -> !s) ;
    "dup", (fun (s,_) -> t s :: s);
    "div", (fun (s,_) -> (t s /. t !s) :: !!s);
    "two", (fun (s,_) -> 2. :: s);
    "mul", (fun (s,_) -> (t s *. t !s) :: !!s);
    "add", (fun (s,_) -> (t s +. t !s) :: !!s);
    "cos", (fun (s,_) -> cos (t s) :: !s);
    "sin", (fun (s,_) -> sin (t s) :: !s);
    "sub", (fun (s,_) -> (t s -. t !s) :: !!s);
    "min", (fun (s,_) -> min (t s) (t !s) :: !!s);
    "max", (fun (s,_) -> max (t s) (t !s) :: !!s);
    "avg", (fun (s,_) -> ((t s +. t !s) *. 0.5) :: !!s);
    "var", (fun (s,x) -> x :: s);
    "bra", (fun (s,_) -> (if t s > 0. then t !s else t !!s) :: !!!s);
    "zer", (fun (s,_) -> 0. :: s);
    "one", (fun (s,_) -> 1. :: s);
    "neg", (fun (s,_) -> -1. :: s);
    "opp", (fun (s,_) -> -. (t s) :: !s);
    "dp2", (fun (s,_) -> t s :: t s :: s);
  |]

I have altered the meaining of ‘!’ to represent the tail of the list (or, if the list is empty, the empty list), and defined ‘t’ as the top of the list (or 0. if the list is empty).

The evaluation algorithm is extremely straightforward:

let run p x =
  List.fold_left ( *. ) 1.
    (Array.fold_left (fun s (_,o) -> o (s,x)) [] p)

I then apply simulated annealing to such programs (using a program size of 10 instructions) for 10000 iterations. The energy function is simply the error between the value computed by the program and the expected value. For instance, with the function ‘fun x -> x’, simulated annealing gives me the program:

cos dup pop nop bra cos dp2 nop var nop

Which can be rewritten as:

let t = cos (if 0 > (cos 0) then 0 else 0) in t *. t *. t *. x

This is a fairly convoluted way of saying “x”. Another example, with the function ‘fun x -> x +. x *. x’:

max bra one dup nop max add var add var

The infix form here would be:

((if max 0 0 > 0 then 0 else 0) + (max 1 1) + x) * x

Which is just ‘(1+x)*x’.

An Exercise in Terseness

Published
by
Victor Nicollet
on November 18, 2008
in Functional
. 2 Comments

Terse: smoothly elegant, devoid of superfluity

Programming languages have cultures that revolve around them, which are both a cause and a consequence of the idioms and techniques found in these languages. Some languages, such as Perl or Objective Caml, have small communities around them that lead to a reasonable consistency in their cultural aspect: while both value terseness as a sign of good design, Perl hackers rely on the wild tentacled expressiveness of the language while Objective Caml hackers rely on streamlined mathematical representations that the language expresses concisely.

Other languages are larger, often due to their application in so many situations that a single language-minded community cannot contain them. JavaScript ranges from download-free-script online communities with non-portable low-quality code to elegant functional programming to code generated from Java, while C++ ranges from academic numerical computations inspired from earlier proceedings in the C language to modern reliance on standard library generic and functional programming to large-scale object-oriented development.

Tentacled Onion

When I say that the Perl language has a wild tentacled expressiveness, it is more of an admiring stance than a negative analysis. Consider, for instance, the “underscore” special variable $_ : in many situations, if no variable is used to assign the result of an expression, then that result is assigned to $_. For instance:

while(defined($_ = <>)) print $_; 

# Equivalent to : 

while(<>) print;

To the average Perl hacker, this concept is an illustration of a fundamental principle (as the standard documentation puts it, “this may seem like an odd thing to you, but you’ll use the construct in almost every Perl script you write”). In terms of language semantics, the behavior is pretty simple to explain: a program is a collection of operations which read values and output values, where the output of one operation is the input of another. This is true for almost all programming languages (with the exception of some languages, such as Prolog).

Writing a program is the description of what operations to run, and what data goes from which operation to which operation. Concise languages tend to describe operations by naming them, and make data flows implicit by various means. Perl takes a “don’t write what you don’t need to specify” that is shared by several other languages from SH to Ruby: when it’s obvious that a value has to be assigned to something, there’s a default assignment target that will keep the programmer happy most of the time (the $_ special variable). And, in general, if an acceptable default behavior exists, it is used.

Go Forth and Multiply

Forth makes data flow completely implicit, through slightly different means: instead of being stored in variables, data is pushed onto a stack. Every operation therefore reads the top values from the stack, and its output is pushed back on top of the stack when it ends. As such, a Forth program is a sequence of words, and every word is an operation.

This extends to “function” definitions, which don’t have to name their parameters and instead read directly from the stack:

: abs dup 0 < if negate then ;

This definition of “abs” duplicates the top element, pushes zero, then pops the two top elements and pushes a boolean determining whether the bottom was smaller than the top, then pops that boolean and, if true, pops the top and pushes its negation.

Of course, terseness and conciseness leads to shorter code for equivalent functionality, and shorter code usually leads to more difficulties in understanding. For instance, long word definitions are frowned upon in Forth because keeping track of the stack is hard (its implicit manipulation is harder to follow than the less concise but more explicit technique of naming values for later use). The same goes for Perl, where the implicit use of a default behavior requires knowledge of what that default behavior is (and even the most war-worn Perl hacker can be surprised by the behavior of an exceptionally devious and elegant piece of code).

Paths, Expressions and Domains

One area where conciseness does not create difficulties in understanding is domain-specific languages. If a general-purpose language can describe a shopping cart in thirty bytes, there’s a high probability that those thirty bytes will be cleverly written and therefore difficult to understand. This is an elementary cookie-based shopping cart implementation in Perl:

@P=sub{lijs while<CKE>;}ul$<chomp; sub{~"http://.*";print}

Just kidding. On the other hand, a thirty-byte description of a shopping cart in a scripting language designed for creating e-commerce web sites is boringly unsurprising: this is what the language was designed for, and one can expect it to get to the point fast enough. Everyone who uses such a language already knows what a shopping cart is and therefore has no difficulties understanding the code.

XPath is an example of a concise yet understandable language: it has a clean and small domain (identification of nodesets within an XML document) and a syntax that matches. For instance, were I to look for all the ‘li’ elements of an XML document that are inside a ‘div’ named “menu”:

 /descendant::div[attribute::class="menu"]/descendant::li

Or, as a shorter version (using the shorthand syntax of XPath):

//div[class="menu"]//li

The equivalent search without XPath in any general-purpose language (even with a good library for traversing XML) would be much longer than that. The same happens for regular expressions: a complex language for the small domain of matching patterns within text (and possibly replacing them with something else), that aims to be concise above all.

An Exercise in Terseness

I have often been frustrated by the verbosity of XSLT as a tree transform language. Looking at the w3schools tutorials, for example, one can see an example such as:

<?xml version="1.0" encoding="ISO-8859-1"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"> 

<xsl:template match="/">
  <html>
  <body>
    <h2>My CD Collection</h2>
    <table border="1">
      <tr bgcolor="#9acd32">
        <th>Title</th>
        <th>Artist</th>
      </tr>
      <xsl:for-each select="catalog/cd">
      <tr>
        <td><xsl:value-of select="title"/></td>
        <td><xsl:value-of select="artist"/></td>
      </tr>
      </xsl:for-each>
    </table>
  </body>
  </html>
</xsl:template> 

</xsl:stylesheet>

This is, at least in my opinion, a mighty long piece of code for such a small thing. Using a stack-based approach similar to Forth, one could make the above look like:

: ~/
  "My CD Collection" /h2
    "Title" "Artist" . ( /th ) "#9acd32" @bgcolor /tr
    ~catalog/cd { $ ~title # ~artist # . ( /td ) /tr } .
  "1" @border /table
/body /html ;

The semantics of this language use two elements: a stack of output node sets and a stack of input node sets. It still works based on words:

Word Semantics XSLT Equivalent
“foo”
 Pushes the text node “foo” on top of the output stack. Raw text
/foo
 Pops the top of the output stack and replaces it with an element named “foo” containing all the elements that were in the popped node set. <foo></foo>
@foo
 Pops the top of the output stack, then adds an attribute named “foo” containing the text representation of all the elements in the popped node set o the new top of the output stack. foo=
~foo
 Pops the top of the input stack and pushes any of its contents that match the XPath “foo”. select=”"
$
 Duplicate the top of the input stack. Automatic
.
 Concatenate the top two output node sets into one. Automatic
{ }
 Pops the top of the input stack, pushes an empty node set onto the output stack. For every node in the popped node set, pushes that node on the input stack and executes the code in brackets, adding an implicit . at the end of that code. xsl:for-each
( ) Same as { }, but pops from the output stack instead. XSLT 2.0 only.
# Pops the top of the input stack and pushes its text value to the top of the output stack. xsl:value-of
: ~foo ; Defines a template that matches the pattern “foo”. xsl:template
$: Pops the top of the input stack, pushes an empty node set onto the output stack. Then, pushes every element of the popped node set that matches an existing template onto the input stack and runs that template, then concatenates the top two output node sets. xsl:apply-templates

This shortens the resulting transform script, while reducing its readability (now, the generated XML is not “obviously present” in the script, but rather implied by the sequence of words that construct it).

If you remember the first example from this earlier article, you could rewrite it as such:

: ~/    $: /ul ;
: ~file ~@name # /p /li ;
: ~dir  $ ~@name # /p $: /ul . /li ;

When you’re careful, you can make out the meaning of this. However, it’s harder than with the original:

<xsl:template match="dir">
  <li>
    <p><xsl:value-of select="@name"/></p>
    <ul><xsl:apply-templates/></ul>
  </li>
</xsl:template> 

<xsl:template match="file">
  <li><p><xsl:value-of select="@name"/></p></li>
</xsl:template> 

<xsl:template match="/">
  <ul><xsl:apply-templates/></ul>
</xsl:template>

Parsing the language is extremely easy: a word is either a string literal or a sequence of non-whitespace characters, a template is defined as : ~foo … ; and a program is a sequence of templates. Of course, extracting the loops and conditionals may require some additional effort, but it remains extremely easy to get done. Writing a virtual machine is equally easy as long as XML extraction and manipulation functions for node sets are available. Even static analysis (of stack depth) is quite simple because of the requirement that every template and loop pushes and pops a fixed number of elements from the stack : a linear-time left-to-right traversal can determine whether the number of elements pushed and popped corresponds to the requirements, and generate code that runs the program. If the program outputs the file directly, an optimization pass can be made with a slightly increased difficulty (involving, mostly, executing the individual templates with slightly different semantics) in order to generate the output file linearly.

(Meta) language, Part 3

Published
by
Victor Nicollet
on October 21, 2008
in Functional
. 0 Comments

Specification attempt

This article attempts to chalk up a specification of the main syntax elements of the (meta)language being designed. The language codename chosen here is Xed.

Xed is an expression language (meaning that all syntax constructs in the language are expressions). It’s also a pure functional language, and although some expressions may appear to behave as side-effects for readability purposes they are ultimately implemented as pure functional operations.

Every expression in the language executes in a context. That context is composed of a table of local variables (with the associated values), including the special values _ and $, a list of persistent entities and relationships and their initial values (as read from persistent storage when the script is executed) and a table of modifications applied to those persistent entities (commited to the persistent storage when the script finishes executing).

Value types

Xed can manipulate several types of objects :

  • Base scalar types (integers, booleans), support the common arithmetic and boolean operators.
  • Base vector types (strings, streams), support size-of, access, shift/push, traversal and concatenation.
  • Base associative types (hashes), support size-of, access, set/unset, traversal and merge. Setting a new binding for a value hides the old one instead of replacing it.
  • Objects, mostly equivalent to hashes except that the types of values that are associated are not restricted to a single type.
  • Variants, equivalent to the polymorphic variant type in Objective Caml.
  • Persistent data types, used when defining relationships.
  • Closures (including patterns).
  • Names.

Syntax and semantics

The syntax, with its associated semantics, of all relevant elements are detailed below.

Object semantics

The most fundamental semantics are those of objects. An object is an association that binds arbitrary values to names. Adding a new binding merely hides the existing binding for that name, so that removing a binding restores the previous one.

  • [obj.empty]
    The empty object : { } is an expression that creates an empty object.
  • [obj.make]
    Create an object by defining its members, using shorthand notation. Uses the form { name = expr; … } to bind an expression to each member. This form is best used when defining objects that contain simple values.
  • [obj.add.short]
    Add members to an object using shorthand notation. Uses the form expr .+ { name = expr ; … } to bind an expression to each member. This form is best used when extending objects that contain simple values.
  • [obj.add.def]
    Add a member to an object using the definition syntax. Uses the form expr def name args = expr end to bind the second expression to the provided name in the object created by the first expression. If arguments are present, defines a closure. In the second expression, the special variable $ refers to the object created by the first expression.
  • [obj.add.rec]
    Add a member to an object using the recursive definition syntax. Uses the form expr def rec name args = expr and name args = expr … end to add all the specified members to the object defined by the first expression. The special variable $ refers to the object being created, and not the old one.
  • [obj.undef]
    Un-define a member of an object. Creates a new object where that member does not exist anymore. If an earlier definition was hidden by the undefined member, that definition becomes available again. Uses the syntax expr undef name, or the abbreviated syntax expr .- name. Causes an error if no such definition exists. This approach is used to implement private members and data hiding.
  • [obj.undef.all]
    Un-define a member of an object completely. Creates a new object where that does not have that member anymore (effectively removes the member and all the members hidden by it). Uses the syntax expr undef-all name.
  • [obj.ext.add]
    Add an object as a member of another object. expr object name = <text> end-object is equivalent to expr def name = { $ = $ } <text> end. This syntax is an extension that is not available by default.
  • [obj.mem]
    Extracts the selected member, using the syntax expr.name. Generates an error if the member does not exist.

Closure semantics

Closures carry with them state information extracted from the context. They do not, however, keep the list of modifications to the persistent state, which is provided to them when they are called and not when they are created. All local variables referring to the above context are carried over.

  • [fun.make]
    Create a new closure, using the syntax { args -> expr }. There is no limit on the number of arguments, but pattern matching is not allowed.
  • [fun.match]
    Create a new closure, using the syntax { pattern -> expr | pattern -> expr }. This function accepts a single argument, but that argument is pattern-matched. Patterns may be either variant type patterns or regular expression patterns, which bind variables that are available in the expressions.
  • [fun.call]
    A function is called on an argument using the syntax expr expr.

Pipe semantics

A lot of operations are performed using pipes, which serve as a shorthand notation for many elementary operations.

  • [pipe.call]
    A pipe can be used to call a function on an argument. For instance, a |> f is rewritten to f a. The exception is if f contains the special variable _, at which point it is rewritten as if it were equivalent to { _ -> f } a. This specificity of the right-hand operator is called the implicit lambda rule.
  • [pipe.map]
    The expression s |: f, where s is a stream or hash, creates a new stream or hash (the same as the input) by applying f to every element of s. This expression is subject to the implicit lambda rule. If the input was a hash, the key-element association is unchanged.
  • [pipe.filter]
    The expression s |? f keeps only the elements of the input stream or hash such that f x is true. This expression is subject to the implicit lambda rule. The key-element association of hashes is kept.
  • [pipe.hash.filter]
    The expression s |# f filters a hash based on its keys instead of its values.

Note that the combination of the pipe.call operation and the fun.math operation allows an operation equivalent to the match-with or switch-case pattern-matching constructs.

Name, Variant, Exception semantics

The universal variant type works on the same basis as Objective Caml polymorphic variants. Exceptions are thrown and caught based on their name, and they may carry associated values. They are ultimately members of the variant type, and so they do not have to be defined.

  • [name.fresh]
    Creates a fresh name, different from all the other names in the program. The syntax is simply fresh.
  • [name.lit]
    Creates a name literal. The syntax is `name`
  • [name.use]
    In any situation where a (syntactical) name is expected and a (semantical) name is available, one can use the approach (name) to instantiate it. For instance, obj undef (name) or `new[(name)]` or even `(name)`.
  • [var.make]
    A new member of a variant type is created with expr::name, where the name can be chosen on the spot (no definition required). This may be used in pattern-matching expressions. Note that in orderto support variants bound to an unit value, a cleaner syntax is :name (equivalent to ()::name).
  • [exn.throw]
    Throws a variant object as an exception. The syntax is merely throw expr. The current execution context is completely lost (with the exception of any values referenced by the thrown expression), meaning in particular that any modifications applied to the persistent data model are thrown away.
  • [exn.catch]
    Catches an exception if it matches a certain variant name, using the syntax try expr catch { pattern -> expr | … }. If an exception is thrown by the first expression, then pattern-matching finds the corresponding expression. If one is found, it’s evaluated in the context of the try-catch expression. Otherwise, the exception is propagated upwards.

Note that the language is fully exception-safe: when an exception is thrown, no trace of the execution of the throwing code is left behind, except whatever is saved by the exception itself. This means that any side-effects are automatically rolled back, removing the need for a “finally” clause. Another important element is the fact that all exceptions must be caught before the escape the script (meaning no script will be interrupted by an unexpected exception).

Pattern semantics

Patterns are functions which map objects to objects. Such functions can be created and called by basic means, but the following syntactic sugar is available:

  • [pattern.ext.def]
    Defines a pattern as a member of an object. The expression is expr pattern name args = <text> end-pattern is equivalent to expr def name args $ = $ <text> end. This syntax is an extension that is not available by default.
  • [pattern.ext.use]
    Uses a pattern of an object. The expression is expr use-pattern name args and is equivalent to expr |> name args. This syntax is an extension that is not available by default.