TOPIC:

The TTCN3 interleave construction is described in both the core
language and operational semantics specifications as something that
should be expanded by a compiler into a tree of nested alt statements.
While this is aesthetically pleasing and academically sound,
experience of this expansion process in the real world is
disappointing. I would like to open a debate on this issue by stating
my opinion that this expansion process should be considered harmful to
the language in general and the construction of TTCN3 tools in
particular.

It is, of course, possible that this debate has taken place already
and I have simply not been party to it: I have only just subscribed to
this list, but I have been following TTCN3 standards and issues via
the CR process for many years as part of my work. So, if this is an
old and well-trodden path please tell me and I will crawl back under
my rock.

Background: I am contracted to NSN in Germany and am part of the team
developing our TTCN3 toolchain (K3). I am posting this in a private
capacity - I do not speak for NSN and they don't speak for me. K3 is
basically a compiler/runtime combination where the intermediate code
takes the form of virtual-machine instructions.

As illustration please consider the following (rather contrived) code:

module maxileave {
type record R1 {}
type record R2 {}
type record R3 {}
type record R4 {}
type record R5 {}
type record R6 {}
type record R7 {}
type record R8 {}
type record R9 {}

type port P message {
in
R1, R2, R3, R4, R5, R6, R7, R8, R9
}

type component M {
port P p
}

testcase tc() runs on M {
interleave {
[] p.receive(R1:?) {}
[] p.receive(R2:?) {}
[] p.receive(R3:?) {}
[] p.receive(R4:?) {}
[] p.receive(R5:?) {}
[] p.receive(R6:?) {}
[] p.receive(R7:?) {}
[] p.receive(R8:?) {}
[] p.receive(R9:?) {}
}
}

control {
execute(tc())
}
}

Compiling this code using the expansion algorithm takes about a minute
on this old G5 Mac and produces a 72 MEGABYTE file. Pretty silly for
39 lines of input.

Compiling the same code to target a runtime that supports 'native
interleave' on the same machine takes 24 milliseconds (yes,
milliseconds) and produces a file of exactly 1136 bytes.

Now add a tenth branch to the example above and try again. The native
interleave version takes the same 24 ms with the output file growing
to 1232 bytes. The expansion version crashes with an out-of-memory
error: so 5Gb isn't enough!

Then, just for fun, take the number of branches up to 32 (actually a
real situation) and see what happens. 26 milliseconds and 3344 bytes
of output. K3 files are very compact.

These results make it clear that the interleave expansion, while
technically valid, should perhaps be removed from the main body of the
core language specification and placed in an appendix. The main
discussion of the expansion in the operational semantics specification
should be reworked entirely. It just doesn't scale and even if the
normal case is, say, three branches, where the output file size
difference is trivial, it gives tool users a false sense of the
abilities of the whole toolchain and then breaks completely with only
a modest increase in the number of branches.

With best regards

Richard Spence

Hi Richard,

Welcome to the list.

Note that each vendor is free to choose how a given construct is
implemented. No one is forced to follow the implementation suggestions in a
standard.

Remember that standards are meant to describe what should happen, not how it
should happen. Each vendor is free to implement TTCN-3 as it sees fit.
Complient implementations should behave as described in the standard. Most
people won't be interested in how something is implemented (speaking of
users mostly here) until problems arise. :-) ( execution time too slow,
compilation time tends towards infinite, generated code exceeds size
available on disk, incorrect implementation...)

Expanding an interleave using the algorithm described in the standard of
course leads to 'huge' files. Not exactly a performance winner either most
likely, and as you attest, a real 'memory hog'!

Choosing to implement a construct based on the description in a standard is
possible but not a requirement. The interleave statement is one of those
cases where there are definitely better ways of implementing them.

The interleave was introduced into TTCN-3 to provide testers with a way to
succinctly describe a series of receive statements where all messages need
to be received, but the actual order of reception wasn't known up front.
Less code, less work, less maintenance, less chance of getting it wrong!

I remember this problem showing up with GSM protocols in the late 80s/early
90s (it's still mostly a blur to me :-) :-) . The problem was solved using
boolean expressions and GOTO statements! :-) Not pretty, but it worked
without too much muss and fuss! This approach can also be used in C, C++,
Java, C#, ADA or any other reasonable programming language.

I can't imagine manually writing out/expanding the code for an interleave
with 32 messages in it, insane! It's not practical nor desirable.


Out of curiosity, is K3 a commercially available tool? Or is this toolchain
strictly for internal use at NSN?


Cheers,

Claude Desroches

Blukaktus Communications phone: +49 (0)30 9606 7986
Edinburger Strasse 39 fax: +49 (0)30 9606 7987
13349 Berlin mobile: +49 (0)174 701 6792

email: This email address is being protected from spambots. You need JavaScript enabled to view it.

>
> The TTCN3 interleave construction is described in both the core
> language and operational semantics specifications as something that
> should be expanded by a compiler into a tree of nested alt statements.
> While this is aesthetically pleasing and academically sound,
> experience of this expansion process in the real world is
> disappointing. I would like to open a debate on this issue by stating
> my opinion that this expansion process should be considered harmful to
> the language in general and the construction of TTCN3 tools in
> particular.
>
> It is, of course, possible that this debate has taken place already
> and I have simply not been party to it: I have only just subscribed to
> this list, but I have been following TTCN3 standards and issues via
> the CR process for many years as part of my work. So, if this is an
> old and well-trodden path please tell me and I will crawl back under
> my rock.
>
> Background: I am contracted to NSN in Germany and am part of the team
> developing our TTCN3 toolchain (K3). I am posting this in a private
> capacity - I do not speak for NSN and they don't speak for me. K3 is
> basically a compiler/runtime combination where the intermediate code
> takes the form of virtual-machine instructions.
>
> As illustration please consider the following (rather contrived) code:
>
> module maxileave {
> type record R1 {}
> type record R2 {}
> type record R3 {}
> type record R4 {}
> type record R5 {}
> type record R6 {}
> type record R7 {}
> type record R8 {}
> type record R9 {}
>
> type port P message {
> in
> R1, R2, R3, R4, R5, R6, R7, R8, R9
> }
>
> type component M {
> port P p
> }
>
> testcase tc() runs on M {
> interleave {
> [] p.receive(R1:?) {}
> [] p.receive(R2:?) {}
> [] p.receive(R3:?) {}
> [] p.receive(R4:?) {}
> [] p.receive(R5:?) {}
> [] p.receive(R6:?) {}
> [] p.receive(R7:?) {}
> [] p.receive(R8:?) {}
> [] p.receive(R9:?) {}
> }
> }
>
> control {
> execute(tc())
> }
> }
>
> Compiling this code using the expansion algorithm takes about a minute
> on this old G5 Mac and produces a 72 MEGABYTE file. Pretty silly for
> 39 lines of input.
>
> Compiling the same code to target a runtime that supports 'native
> interleave' on the same machine takes 24 milliseconds (yes,
> milliseconds) and produces a file of exactly 1136 bytes.
>
> Now add a tenth branch to the example above and try again. The native
> interleave version takes the same 24 ms with the output file growing
> to 1232 bytes. The expansion version crashes with an out-of-memory
> error: so 5Gb isn't enough!
>
> Then, just for fun, take the number of branches up to 32 (actually a
> real situation) and see what happens. 26 milliseconds and 3344 bytes
> of output. K3 files are very compact.
>
> These results make it clear that the interleave expansion, while
> technically valid, should perhaps be removed from the main body of the
> core language specification and placed in an appendix. The main
> discussion of the expansion in the operational semantics specification
> should be reworked entirely. It just doesn't scale and even if the
> normal case is, say, three branches, where the output file size
> difference is trivial, it gives tool users a false sense of the
> abilities of the whole toolchain and then breaks completely with only
> a modest increase in the number of branches.
>
> With best regards
>
> Richard Spence

Claude, List readers,

I fully understand that toolmakers have implementation freedom. Indeed, without this freedom, a sensible implementation of interleave would not be possible. Please understand that I have no issue with the interleave construction itself, just its description as an expansion. Here is another way to state my contention:

1. Core language is normative,
1a. Refers to operational semantics,
1b. Declares that interleave "can always be replaced by an equivalent set of nested alt statements" but this is presumably merely informative,
1c. Declares a prohibition on the use of 'repeat' within interleave,
2. Operational semantics is informative,
2a. Gives nearly full description of interleave expansion (omits interaction with defaults),
2b. Restates the prohibition of 'repeat',
2c. Shows a clear example of the expansion of interleave with many alts-within-alts,
3. I assume 'repeat' is prohibited within interleave because its operation is compromised by the expansion
4. If point 3 is true, then, de facto, the expansion of interleave is normative and, therefore, mandatory.

Point 3 is crucial. A separate thread, started by my colleague Uwe Truetsch, is attempting to address the issue of repeat within a default invoked from an interleave. In effect, these two threads are part of a larger discussion about the nature of the description of interleave

I can see no reason to prohibit 'repeat' within interleave. It is my belief that systems should always be designed with the "Principle of Least Astonishment" in mind, and the prohibition of 'repeat' is unnecessarily astonishing :-)

Some input from standards people would be useful at this point...

On 06 Nov, 2010,at 01:06 AM, Claude Desroches <This email address is being protected from spambots. You need JavaScript enabled to view it.> wrote:

> Hi Richard,
>
> Welcome to the list.
>
> Note that each vendor is free to choose how a given construct is
> implemented. No one is forced to follow the implementation suggestions in a
> standard.
>
> Remember that standards are meant to describe what should happen, not how it
> should happen. Each vendor is free to implement TTCN-3 as it sees fit.
> Complient implementations should behave as described in the standard. Most
> people won't be interested in how something is implemented (speaking of
> users mostly here) until problems arise. :-) ( execution time too slow,
> compilation time tends towards infinite, generated code exceeds size
> available on disk, incorrect implementation...)
>
> Expanding an interleave using the algorithm described in the standard of
> course leads to 'huge' files. Not exactly a performance winner either most
> likely, and as you attest, a real 'memory hog'!
>
> Choosing to implement a construct based on the description in a standard is
> possible but not a requirement. The interleave statement is one of those
> cases where there are definitely better ways of implementing them.
>
> The interleave was introduced into TTCN-3 to provide testers with a way to
> succinctly describe a series of receive statements where all messages need
> to be received, but the actual order of reception wasn't known up front.
> Less code, less work, less maintenance, less chance of getting it wrong!
>
> I remember this problem showing up with GSM protocols in the late 80s/early
> 90s (it's still mostly a blur to me :-) :-) . The problem was solved using
> boolean expressions and GOTO statements! :-) Not pretty, but it worked
> without too much muss and fuss! This approach can also be used in C, C++,
> Java, C#, ADA or any other reasonable programming language.
>
> I can't imagine manually writing out/expanding the code for an interleave
> with 32 messages in it, insane! It's not practical nor desirable.
>
>
> Out of curiosity, is K3 a commercially available tool? Or is this toolchain
> strictly for internal use at NSN?
>
>
> Cheers,
>
> Claude Desroches
>
> Blukaktus Communications phone: +49 (0)30 9606 7986
> Edinburger Strasse 39 fax: +49 (0)30 9606 7987
> 13349 Berlin mobile: +49 (0)174 701 6792
>
> email: This email address is being protected from spambots. You need JavaScript enabled to view it.
>
> >
> > The TTCN3 interleave construction is described in both the core
> > language and operational semantics specifications as something that
> > should be expanded by a compiler into a tree of nested alt statements.
> > While this is aesthetically pleasing and academically sound,
> > experience of this expansion process in the real world is
> > disappointing. I would like to open a debate on this issue by stating
> > my opinion that this expansion process should be considered harmful to
> > the language in general and the construction of TTCN3 tools in
> > particular.
> >
> > It is, of course, possible that this debate has taken place already
> > and I have simply not been party to it: I have only just subscribed to
> > this list, but I have been following TTCN3 standards and issues via
> > the CR process for many years as part of my work. So, if this is an
> > old and well-trodden path please tell me and I will crawl back under
> > my rock.
> >
> > Background: I am contracted to NSN in Germany and am part of the team
> > developing our TTCN3 toolchain (K3). I am posting this in a private
> > capacity - I do not speak for NSN and they don't speak for me. K3 is
> > basically a compiler/runtime combination where the intermediate code
> > takes the form of virtual-machine instructions.
> >
> > As illustration please consider the following (rather contrived) code:
> >
> > module maxileave {
> > type record R1 {}
> > type record R2 {}
> > type record R3 {}
> > type record R4 {}
> > type record R5 {}
> > type record R6 {}
> > type record R7 {}
> > type record R8 {}
> > type record R9 {}
> >
> > type port P message {
> > in
> > R1, R2, R3, R4, R5, R6, R7, R8, R9
> > }
> >
> > type component M {
> > port P p
> > }
> >
> > testcase tc() runs on M {
> > interleave {
> > [] p.receive(R1:?) {}
> > [] p.receive(R2:?) {}
> > [] p.receive(R3:?) {}
> > [] p.receive(R4:?) {}
> > [] p.receive(R5:?) {}
> > [] p.receive(R6:?) {}
> > [] p.receive(R7:?) {}
> > [] p.receive(R8:?) {}
> > [] p.receive(R9:?) {}
> > }
> > }
> >
> > control {
> > execute(tc())
> > }
> > }
> >
> > Compiling this code using the expansion algorithm takes about a minute
> > on this old G5 Mac and produces a 72 MEGABYTE file. Pretty silly for
> > 39 lines of input.
> >
> > Compiling the same code to target a runtime that supports 'native
> > interleave' on the same machine takes 24 milliseconds (yes,
> > milliseconds) and produces a file of exactly 1136 bytes.
> >
> > Now add a tenth branch to the example above and try again. The native
> > interleave version takes the same 24 ms with the output file growing
> > to 1232 bytes. The expansion version crashes with an out-of-memory
> > error: so 5Gb isn't enough!
> >
> > Then, just for fun, take the number of branches up to 32 (actually a
> > real situation) and see what happens. 26 milliseconds and 3344 bytes
> > of output. K3 files are very compact.
> >
> > These results make it clear that the interleave expansion, while
> > technically valid, should perhaps be removed from the main body of the
> > core language specification and placed in an appendix. The main
> > discussion of the expansion in the operational semantics specification
> > should be reworked entirely. It just doesn't scale and even if the
> > normal case is, say, three branches, where the output file size
> > difference is trivial, it gives tool users a false sense of the
> > abilities of the whole toolchain and then breaks completely with only
> > a modest increase in the number of branches.
> >
> > With best regards
> >
> > Richard Spence

I could not agree more with this statement. I stumbled on the same
problem while developing the first TTCN-3 compiler 10 years ago and we
decided to not go the expansion route because it makes no sense from a
compiler construction point of view (because of the reasons you pointed
out).

I think that the expansion paradigm was mainly chosen to EXPLAIN the (in
essence INTERLEAVE-PARALLEL - hence the name, I guess) semantics of the
interleave statement in a purely SEQUENTIAL way. I also think that all
the restrictions appended to the interleave statement are a direct
result of this expansion paradigm as it would be much harder to include
constructs like loops, conditionals or function calls into the expansion
algorithm, even though they don't pose any problem when not using it.

As the expansion thing does not make sense in the real world, as you so
aptly pointed out, most of the restrictions could also be removed from
the interleave statement once it gets a proper interleave-parallel
semantics (probably by use of some sort of mutually-exclusive-thread
paradigm) without the crutch of the alt-statement expansion.

I would therefore strongly support a CR on this issue.

BR, Jacob Wieland0

On 11/05/2010 05:14 PM, Richard Spence wrote:
> The TTCN3 interleave construction is described in both the core
> language and operational semantics specifications as something that
> should be expanded by a compiler into a tree of nested alt statements.
> While this is aesthetically pleasing and academically sound,
> experience of this expansion process in the real world is
> disappointing. I would like to open a debate on this issue by stating
> my opinion that this expansion process should be considered harmful to
> the language in general and the construction of TTCN3 tools in
> particular.
>
> It is, of course, possible that this debate has taken place already
> and I have simply not been party to it: I have only just subscribed to
> this list, but I have been following TTCN3 standards and issues via
> the CR process for many years as part of my work. So, if this is an
> old and well-trodden path please tell me and I will crawl back under
> my rock.
>
> Background: I am contracted to NSN in Germany and am part of the team
> developing our TTCN3 toolchain (K3). I am posting this in a private
> capacity - I do not speak for NSN and they don't speak for me. K3 is
> basically a compiler/runtime combination where the intermediate code
> takes the form of virtual-machine instructions.
>
> As illustration please consider the following (rather contrived) code:
>
> module maxileave {
> type record R1 {}
> type record R2 {}
> type record R3 {}
> type record R4 {}
> type record R5 {}
> type record R6 {}
> type record R7 {}
> type record R8 {}
> type record R9 {}
>
> type port P message {
> in
> R1, R2, R3, R4, R5, R6, R7, R8, R9
> }
>
> type component M {
> port P p
> }
>
> testcase tc() runs on M {
> interleave {
> [] p.receive(R1:?) {}
> [] p.receive(R2:?) {}
> [] p.receive(R3:?) {}
> [] p.receive(R4:?) {}
> [] p.receive(R5:?) {}
> [] p.receive(R6:?) {}
> [] p.receive(R7:?) {}
> [] p.receive(R8:?) {}
> [] p.receive(R9:?) {}
> }
> }
>
> control {
> execute(tc())
> }
> }
>
> Compiling this code using the expansion algorithm takes about a minute
> on this old G5 Mac and produces a 72 MEGABYTE file. Pretty silly for
> 39 lines of input.
>
> Compiling the same code to target a runtime that supports 'native
> interleave' on the same machine takes 24 milliseconds (yes,
> milliseconds) and produces a file of exactly 1136 bytes.
>
> Now add a tenth branch to the example above and try again. The native
> interleave version takes the same 24 ms with the output file growing
> to 1232 bytes. The expansion version crashes with an out-of-memory
> error: so 5Gb isn't enough!
>
> Then, just for fun, take the number of branches up to 32 (actually a
> real situation) and see what happens. 26 milliseconds and 3344 bytes
> of output. K3 files are very compact.
>
> These results make it clear that the interleave expansion, while
> technically valid, should perhaps be removed from the main body of the
> core language specification and placed in an appendix. The main
> discussion of the expansion in the operational semantics specification
> should be reworked entirely. It just doesn't scale and even if the
> normal case is, say, three branches, where the output file size
> difference is trivial, it gives tool users a false sense of the
> abilities of the whole toolchain and then breaks completely with only
> a modest increase in the number of branches.
>
> With best regards
>
> Richard Spence