ser2

ser2 was created between 2009 and 2012. Its name abbreviates "Search Entity and Replace", the "2" indicates the second attempt. ser2 is inspired by C++ template meta-programming. It is a minimalistic functional language with the initial and final state predefined and built-in i/o.

Overview

Relation to established languages

C++ template meta-programming is Turing-complete and in order to achieve this, only a tiny subset of the template engine is necessary. It boils down to partial specializations as in

template <typename T>
struct object<fixed,T>{
 typedef new_object<foo,T,bar>::result result;
};

So that the result of struct object<fixed,T> is the result of new_object<foo,T,bar>. ser2 basically strips this down to the essential content of such a specialization

!object--:fixed:#T: / new_object---:foo:#T:bar:

In fact, ser2 easily translates to a C++ template meta-program.

In a nutshell

In a nutshell, the language translates a (sub-)tree of objects to a new (sub-)tree of objects. In order to make the language easier readable, at the end of the object name the number of subobjects is indicated by a number of "-"-signs. Wildcards start with a "#". The initial object is the object "'@run-:" with a i/o object as subobject. At termination, it is this i/o subobject that must remain. The following shows "Hello world!":

!print--:#o:--:#c:#n: / wrote--:'@output--:#o:#c :#n:
!print--:#o:     eol: / wrote- :'@output--:#o:&0a:
!wrote--:'@iopair--:#o:#c:#n: / print--:#o:#n:
!wrote- :'@iopair--:#o:#c:    / #o:

!'@run-:#: / print--:#:
--:'H:--:'e:--:'l:--:'l:--:'o:--:' :--:'w:--:'o:--:'r:--:'l:--:'d:--:'!:eol:

The "'@output--:" object gets replaced by "'@iopair--:", repeating the subobjects of "'@output--:". Meanwhile the character that forms the second object gets printed.

Language definition

The language purely consists of a set of rules. A rule consists of two parts, the pattern and the replacement. The pattern starts with a "!" and the replacement by "/". The state of the program is a rooted tree of objects. If a pattern matches a subtree, then the subtree is replaced by the replacement. Smaller subtrees are treated first, following the eager evaluation scheme.

File format

The file is in 8-bit ASCII. Within a pattern or replacement, any character other than alphanumeric and "_!/&:-#'" is ignored, but the character following "'". Outside of a pattern or replacement, any character except "!/&:-#'" is ignored.

Objects

Object names are alphanumeric + "_" and are terminated by ":", for extended names involving "&'" see below. An object name may have in addition an arbitrary number "-"s at the end, indicating the number of child objects. These child objects have to be listed after the object name. Example:

pair--:first:second:

denotes the object "pair--:" with two child objects, "first:" and "second:". Arbitrary hierarchies are admissible, a typical example is

list--:s:list--:e:list--:r:list--:2:nil:

denoting the object tree

 list--:
 /  |
s:  list--:
    /  |
   e:  list--:
       /  |
      r:  list--:
          /  |
         2:  nil:

Wildcards

A wildcard name is alphanumeric + "_" and starts with a "#" and ends with a ":". No "&'" are allowed. A wildcard matches and replaces a subtree. Example:

#wildcard:

Patterns

A pattern is like a tree of objects. It can have wildcards. Then

/list--:#cur:#next:

would match the object above with "#cur:" set to "s:" and "#next:" set to "list--:e:list--:r:list--:2:nil:". In a pattern, each wildcard must be unique. Implementations may refuse to allow a wildcard at the root object, since this always leads to a non-terminating program.

Replacements

A replacement is an object, where the wildcards are replaced by the subtree that was assigned while matching the pattern. In a replacement, each wildcard must occur at most once. Child objects are subject to a replacement prior to the parent object. Different child objects of the same parent object may be replaced in any order or even concurrently.

Resolution order

There may be ambiguous cases in pattern matching. The following rule is used: A pattern X matches at least as good as a pattern Y if, no matter what objects would be assigned to the wildcards, the resulting object always matches Y. If there exists a rule for which no other rule matches at least as well, this rule is applied. Otherwise undefined behaviour will occur.

Names with special characters

In the names of objects an "'" may occur and than the following character is forced to be part of the object name, but the character has to be below 0xf0. Examples:

object's_name:
arbitrary' chars' are' possible' e'.g'.' ':' or' '':
name'1:
name1:

Note in particular, that the latter two objects are different.

Instead of using "'" it is also possible to use "&xx" where xx is the hexadecimal 8-bit code (upper or lower case) for the character. Hence the following two objects are the same:

space' :
space&20:

Specials

Special objects

Finally there are a few objects that have a special meaning. They define the initial condition, simple i/o routines and some optional convenience stuff. Each of those special objects is limited to appear either only in patterns or only in replacements. In detail we have:

object	restriction	description
'@run-:	pattern only	This object is created at start time. The child object is an i/o object which can only be matched by means of a wildcard. A valid program must eventually replace "'@run-:" by the i/o object.
'@eof:	pattern only	Indicates the end of input.
'@iopair--:	pattern only	Contains the i/o object as first child object and the i/o character as second child object.
'@aborted:	pattern only	Indicates that a SIGINT was caught.
'@input-:	replacement only	If the first subobject is the i/o object, then this object is replaced by "'@iopair--:", where the second subobject is either the input character object (e.g. "'x:") or "'@eof:" if the input ended. This replacement may block the course of the program.
'@output--:	replacement only	If the first subobject is the i/o object then the second subobject must be a single character object (e.g. "'x:"). This character is then printed to the standard output and the object is replaced by "'@iopair--:". This replacement may block the course of the program.
'@debug-:	replacement only	Replaced by the subobject. May be used to print debug information of the subobject (implementation dependent).
'@guard-:	replacement only	Gets replaced by the subobject. If the implementation allows to catch signals, the following behaviour is in place: If during the calculation of the subobject a SIGINT occurs, then the object will be replaced by "'@aborted:" (take care not to loose the i/o object on abort). If there are are several guards, the first one while going up the hierarchy will be replaced. Note, that in concurrent implementations, there might be several aborted calculations, yielding several such replacements.

Syntax characters

Character	Usage
alphanumeric + _	Object and wildcard names.
'	The next character is part of the object name.
&	Similar to ' but using the hex code of the ASCII character.
:	End of a object or wildcard name.
-	Each "-" character indicates a subobject.
#	Start of wildcard.
!	Start of a pattern.
/	Start of a replacement.

Caveats

• There is no support for any number, strings, or similar things and in addition there is no inherent way to compare or copy objects. This may make it a bit difficult to write something useful…

• ser2 approaches an entry from the List of ideas:

Take C++, but remove everything except the bare minimum required for turing-complete template meta-programming. The keywords template, typedef, typename and struct should be enough. Could get rid of either struct or typename with some trivial changes from C++, but if you want to keep it compatible your options are more limited.

• When translating to C++, the order of the rules may play a role. An example is

!const-:x:/foo-:bar:
!foo-:bar:/bar:

!'@run-:#:/done--:#:const-:x:
!done--:#:bar:/#:

Which would instantiate class foo<bar> before its specialization. This can be avoided by using a dummy template as in template <typename DUMMY> class foo<DUMMY,bar>.