Yesterday I've read of a new Garbage Collection implementation
G1.
To be honest I was not impressed.
I think Garbage Collection is an evil, or at least its present implementations.
I do not believe in algorithms that in their very core assume a centralized
execution.
On the other hand it's clear it's not in my power to change the status quo. My
lot is to give advices mostly incompetent and ignorable.
I'm waiting for the time when someone will reach the idea to bring some parts of
GC logic out of runtime scope. This will require more VM intelligence,
however will bear its fruits.
JIT or compiler during a static analysis may prove that some objects being
collected may make some of their referring objects unreachable, provided it can
prove that referring objects are not reachable through the other means (e.g.
private field which is not stored in other places). This is close to the ideas
expressed in
Muse on value types in java. It's possible to prepare a garbage graph in
advance before runtime.
In many cases it's also possible to prove that when method's variable goes out
of scope it's not reachable through the other means and may be collected. This
allows to implement a stage of automatic garbage collection when objects that
are proven to be a garbage be immedeately added to a free memory set.
As an example I'm thinking of java's ArrayList object which stores private
array. When ArrayList is reclaimed or resized a reference to the private array
is getting lost and memory can be added to the free set immediately.
This mechanics being integrated as the first stage of GC will make it less
centralized, as I believe many objects will be collected this way.
Suppose you have constructed a sequence of attributes.
How do you access a value of attribute "a"?
Simple, isn't it? It has taken a couple of minutes to find a solution!
<xsl:variable name="attributes" as="attribute()*">
<xsl:apply-templates mode="t:generate-attributes" select="."/>
</xsl:variable>
<xsl:variable name="value" as="xs:string?"
select="$attributes[self::attribute(a)]"/>
Saying
Our project, containing many different xslt files, generates many different
outputs (e.g: code that uses DB2 SQL, or Oracle SQL, or DAO, or some
other flavor of code). This results in usage of
indirect calls to handle different generation options, however to allow xslt
to work we had to create a big main xslt including stylesheets for each kind of
generation. This impacts on a compilation time.
Alternatives
- A big main xslt including everything.
- A big main xslt including everything and using "use-when" attribute.
- Compose main xslt on the fly.
We were eagerly inclined to the second alternative. Unfortunately a limited set of information is available when "use-when" is evaluated. In
particular there are neither parameters nor documents available. Using
Saxon's extensions one may reach only static variables, or access
System.getProperty(). This isn't flexible.
We've decided to try the third alternative.
Solution
We think we have found a nice solution: to create XsltSource ,
which receives a list of includes upon construction, and creates an xslt
when getReader() is called.
import java.io.Reader;
import java.io.StringReader;
import javax.xml.transform.stream.StreamSource;
/**
* A source to read generated stylesheet, which includes other stylesheets.
*/
public class XsltSource extends StreamSource
{
/**
* Creates an {@link XsltSource} instance.
*/
public XsltSource()
{
}
/**
* Creates an {@link XsltSource} instance.
* @param systemId a system identifier for root xslt.
*/
public XsltSource(String systemId)
{
super(systemId);
}
/**
* Creates an {@link XsltSource} instance.
* @param systemId a system identifier for root xslt.
* @param includes a list of includes.
*/
public XsltSource(String systemId, String[] includes)
{
super(systemId);
this.includes = includes;
}
/**
* Gets stylesheet version.
* @return a stylesheet version.
*/
public String getVersion()
{
return version;
}
/**
* Sets a stylesheet version.
* @param value a stylesheet version.
*/
public void setVersion(String value)
{
version = value;
}
/**
* Gets a list of includes.
* @return a list of includes.
*/
public String[] getIncludes()
{
return includes;
}
/**
* Sets a list of includes.
* @param value a list of includes.
*/
public void setIncludes(String[] value)
{
includes = value;
}
/**
* Generates an xslt on the fly.
*/
public Reader getReader()
{
String[] includes = getIncludes();
if (includes == null)
{
return super.getReader();
}
String version = getVersion();
if (version == null)
{
version = "2.0";
}
StringBuilder builder = new StringBuilder(1024);
builder.append("<stylesheet version=\"");
builder.append(version);
builder.append("\" xmlns=\"http://www.w3.org/1999/XSL/Transform\">");
for(String include: includes)
{
builder.append("<include href=\"");
builder.append(include);
builder.append("\"/>");
}
builder.append("</stylesheet>");
return new StringReader(builder.toString());
}
/**
* An xslt version. By default 2.0 is used.
*/
private String version;
/**
* A list of includes.
*/
private String[] includes;
}
To use it one just needs to write:
Source source = new XsltSource(base, stylesheets);
Templates templates = transformerFactory.newTemplates(source);
...
where:
base is a base uri for the generated stylesheet; it's used to
resolve relative includes;
stylesheets is an array of hrefs.
Such implementation resembles a dynamic linking when separate parts are bound at
runtime. We would like to see dynamic modules in the next version of xslt.
Why we've turned our attention to the Saxon implementation?
A considerable part (~75%) of project we're working on at present is creating
xslt(s). That's not stylesheets to create page presentations, but rather
project's business logic. To fulfill the project we were in need of xslt 2.0
processor. In the current state of affairs I doubt someone can point to a good
alternative to the Saxon implementation.
The open source nature of the SaxonB project and intrinsic curiosity act like a
hook for such species like ourselves.
We want to say that we're rather sceptical
observers of a code: the code should prove it have merits. Saxon looks
consistent. It takes not too much time to grasp implementation concepts taking
into account that the code routinely follows xpath/xslt/xquery specifications.
These code observation and practice with live xslt tasks helped us to form an
opinion on the Saxon itself. That's why we dare to critique it.
1. Compilation is fused with execution.
An xslt before being executed passes several stages including xpath data model, and a graph of expressions - objects implementing
parts of runtime logic.
Expression graph is optimized to achieve better runtime performace. The
optimization logic is distributed throughout the code, and in particular lives
in expression objects. This means that expression completes two roles: runtime
execution and optimization.
I would prefer to see a smaller and cleaner run time objects (expressions),
and optimization logic separately. On the other hand I can guess why Michael Kay
fused these roles: to ease lazy optimizations (at runtime).
2. Optimizations are xslt 1.0 by origin
This is like a heritage. There are two main techniques: cached
sequences, and global indices of rooted nodes.
This might be enough in xslt 1.0, but in 2.0 where there are diverse set of
types, where sequences extend node sets to other types, where sequences may
logically be grouped by pairs, tripples, and so on, this is not enough.
XPath data model operates with sequences only (in math sense). On the other hand it
defines many set based functions (operators) like: $a intersect $b , $a except $b ,
$a = $b , $a != $b . In these examples XPath sequences are better to consider as sets, or maps of items.
Other example: for $i in index-of($names, $name) return $values[$i] , where
$names as xs:string* , $values as element()* shows that
a closure of ($names , $values ) is in fact a map, and
$names might be implemented as a composition of a sequence and a map of
strings to indices.
There are other use case examples, which lead me to think that Saxon lacks set
based operators. Global indices are poor substitution, which work for rooted
trees only.
Again, I guess why Michael Kay is not implementing these operators: not everyone
loads xslt with stressful tasks requiring these features. I think xslt is mostly
used to render pages, and one rarely deviates from rooted trees.
In spite of the objections we think that Saxon is a good xslt 2.0 implementation,
which unfortunately lacks competitors.
We strongly object against persistence frameworks in their contemporary meaning.
This includes a long row of names like Hibernate, Java Persistence API, LINQ,
and others.
Consider how one of them describes itself:
...high performance object/relational persistence and query service... lets you
develop persistent classes following object-oriented idiom - including
association, inheritance, polymorphism, composition, and collections... allows you to express queries in its own portable SQL extension...
Sounds good, right?
We think not! Words "own" and "portable" regarding SQL are heard
almost like antonyms. When one creates a unified language (a noble rush, opposed to a
proprietary one (?)) she will inevitably adds a peer, increasing
plurality in the family of languages.
Attempts to create similar layers between data and business logic are not new.
This happens throughout the computer history. IDMS, NATURAL, COOL:GEN these are
20-30 years old examples.
Our reasoning (nothing new).
One need to approach to a design (development and maintainance) from different
perspectives, thus she will understand the question under the design better, and
will estimate skills to accomplish the problem. This will lead to a
modularization e.g: business layer, data layer, appearance; and to development
(maintainance) roles: program developer, database specialist, appearance
speciaist. On a small scale several roles are often fulfilled with one person;
this should not mean, however, that these roles are redundant, one just need to
try on different roles.
Why does one separate business layer and data layer?
Pragmatic perspective. There are databases, which may accomplish most of data
storage tasks in a more efficient way than one may achieve without database.
There are two worlds of database specialists and program developers. These two
layers and roles are facts of reality.
A desiner's goal is to keep these roles separate:
- do not force a database specialist to know the business logic details;
- do not force a program developer to know details on how to organize a storage
in more efficient way, or on how to optimize a particular query;
Modularity helps here. Databases are well equipped to solve these tasks: the data
layer should expose a database API through stored procedures, functions, and
views, while the business layer should use this API to access the database.
With persistence frameworks there are two alterantives:
- still use data layer API;
- rely on a persistence framework.
When the first case is selected then a framework provides almost no aditional
value comparing to traditional database access (jdbc, ado.net, an so on).
When one relies on a framework then a data layer interface virtually disappears
(in fact a framework substitutes this interface). Database specialist has very
little control over tuning the data structure, and optimizing queries, unless
she starts digging in the business code but even then she always cannot control
queries to the database. Moreover database specialist must learn a proprietary
query language.
Result is that a persistence framework erodes a division of responsibilities,
complicating development and maintainance.
We often hear a following explanation on why one should use Persistence
Frameworks: "It eases database vendor switch". This is the most stupid reason to use
Persistence Frameworks! It looks as if they plan to switch vendors once a
day.
A design needs to focus on a modularity. This will make code more robust, faster
and maintainable. This also eases potential migration process, as the data layer
should be migrated only, with minimal (mostly configurational) changes in the
business layer.
We are certain xslt/xquery are the best for web application frameworks from the
design perspective; or, in other words, pipeline frameworks allowing use of
xslt/xquery are preferable way to create web applications.
Advantages are obvious:
-
clear separation of business logic, data, and presentation;
-
richness of languages, allowing to implement simple presentation, complex
components, and sophisticated data binding;
-
built-in extensibility, allowing comunication with business logic, written in
other languages and/or located at different site.
It seems the agitation for a such technologies is like to force an open
door. There are such frameworks out there:
Orbeon Forms, Cocoon, and others.
We're not qualified to judge of their virtues, however...
Look at the current state of affairs. The main players in this area (well, I
have a rather limited vision) push other technologies: JSP/JSF/Faceletes and
alike in the Java world, and ASP.NET in the .NET world. The closest thing they
are providing is xslt servlet/component allowing to generate an output.
Their variants of syntaxis, their data binding techniques allude to similar
paradigms in xslt/xquery:
<select>
<c:forEach var="option" items="#{bean.options}">
<option value="#{option.key}">#{parameter.value}</option>
</c:forEach>
</select>
On the surface, however, we see much more limited (in design and in the
application) frameworks.
And here is a contradiction: how can it be that at present such a good design is
not as popular, as its competitors, at least?
Someone can say, there is no such a problem. You can use whatever you want. You
have a choice! Well, he's lucky. From our perspective it's not that simple.
We're creating rather complex web applications. Their nature isn't important in
this context, but what is important is that there are customers. They are not
thoroughly enlightened in the question, and exactly because of this they prefer
technologies proposed by leaders. It seems, everything convince them: main
stream, good support, many developers who know technology.
There is no single chance to promote anything else.
We believe that the future may change this state, but we're creating at present,
and cannot wait...
I've uploaded jxom.zip
Now, it contains a state machine generator. See "What you can do with jxom".
The code is in the java-state-machine-generator.xslt. The test is in the java-state-machine-test.xslt.
Java has no value types: objects allocated inplace, in contrast to objects
referred by a pointer in the heap. This, in my opinion, has a negative impact on
a program design and on a performance.
Incidentally, I've thought of a use case, which can be understood as a value
type by the jvm implementations. Consider an example:
class A
{
private final B b = new B();
}
Implementation may layout class A, in a way that field b will be a content of
an instance of class B itself rather than a pointer to an instance of a class B. This way we
save a pointer and a heap allocation of instance B. Another example:
class C
{
C(int size)
{
values = new D[size];
for(int i = 0; i < values.length; i++)
{
values[i] = new D();
}
}
private final D[] values;
}
Here field values is never a null and each item of array contains a non null
value. Assuming these conditions are kept for a whole life cycle, and values are
not passed by reference, we can consider values as an array of value types.
A use case conditions are following:
- a field contains a non null value;
- the field value is an instance of the field type and not
descendant type;
- if the field is an array, then all elements of the array are
initialized with instances of element type, and not descendant type.
- the field or an element of the array can be assigned through the
operator
new only (field = new T() , array[i] = new T() );
- the array field is not passed by reference
(
Arrays.sort(array) never happens).
JIT's allowed to interpret a field as a
value type provided it proves these conditions.
Later...
There is another use case to detect value types:
- a method variable contains no null value, and
- that variable is never stored in any field, and
- no synchronization is used on the instance of value in variable, and
- a value to the variable is assigned through the operator
new only.
A variable can be layed out directly onto the stack, provided a preceding conditions are satisfied.
P.S. In spite that .NET has built in value types, it may use the very same technique to optimize reference types.
We're facing a task of conversion of a java method into a state machine.
This is like to convert a SAX Parser, pushing data, into an Xml Reader, which
pulls data.
The task is formalized as:
- for a given method containing split markers create a class perimitting
iteration;
- each iteration performs part of a logic of a method.
We have defined rules converting all statements into a state machine except
of the statement synchronized . In fact the logic is rather linear, however the most untrivial conversion is for try statement.
Consider an example:
public class Test
{
void method()
throws Exception
{
try
{
A();
B();
}
catch(Exception e)
{
C(e);
}
finally
{
D();
}
E();
}
private void A()
throws Exception
{
// logic A
}
private void B()
throws Exception
{
// logic B
}
private void C(Exception e)
throws Exception
{
// logic C
}
private void D()
throws Exception
{
// logic D
}
private void E()
throws Exception
{
// logic E
}
}
Suppose we want to see method() as a state machine in a way that split markers are after calls to
methods A() , B() , C() , D() , E() . This is how it looks as a state machine:
Callable<Boolean> methodAsStateMachine()
throws Exception
{
return new Callable<Boolean>()
{
public Boolean call()
throws Exception
{
do
{
try
{
switch(state)
{
case 0:
{
A();
state = 1;
return true;
}
case 1:
{
B();
state = 3;
return true;
}
case 2:
{
C(ex);
state = 3;
return true;
}
case 3:
{
D();
if (currentException != null)
{
throw currentException;
}
state = 4;
return true;
}
case 4:
{
E();
state = -1;
return false;
}
}
if (currentException == null)
{
currentException = new IllegalStateException();
}
}
catch(Throwable e)
{
currentException = null;
switch(state)
{
case 0:
case 1:
{
if (e instanceof Exception)
{
ex = (Exception)e;
state = 2;
}
else
{
currentException = e;
state = 3;
}
continue;
}
case 2:
{
currentException = e;
state = 3;
continue;
}
}
currentException = e;
state = -1;
}
}
while(false);
return this.<Exception>error();
}
@SuppressWarnings("unchecked")
private <T extends Throwable> boolean error()
throws T
{
throw (T)currentException;
}
private int state = 0;
private Throwable currentException = null;
private Exception ex = null;
};
}
Believe it, or not but this transformation can be done purely in xslt 2.0 with the help of the
jxom (Java xml object model). We shall update
jxom.zip whenever
this module will be implemented and tested.
In the xslt one can express logically the same things in different words like:
exists($x)
and
every $y in $x satisfies exists($y)
newbie> Really the same?
expert> Ops... You're right, these are different things!
What's the difference?
I was already writing about tuples and maps in the xslt (see
Tuples and maps - Status: CLOSED, WONTFIX, and
Tuples and maps in Saxon).
Now, I want to argue on a use case, and on how xslt processor can detect such a
use case and implement it as map. This way, for a certain conditions, a sequences
could be treated as maps (or as sets).
Use case.
There are two stages:
- a logic collecting nodes/values satisfying some criteria.
- process data, and take a special action whenever a node/value is collected on
the previous stage.
Whenever we're talking of nodes than result of the first stage is
a sequence $set as node()* . The role of this sequence is a
set of nodes (order is not important).
The second stage is usually an xsl:for-each , an xsl:apply-templates ,
or something of this kind, which repeatedly verifies whether a some $node as
node()? belongs to the $set , like a following: $node intersect
$set , or $node except $set .
In spite of that we're still using regular xpath 2.0, we have managed to express
a set based operation. It's a matter of xslt processor's optimizer to detect
such a use case and consider a sequence as a set. In fact the detection rule is
rather simple.
For expressions $node except $set and $node intersect $set :
$set can be considered as a set, as order of elements is not important;
- chances are good that a
$set being implemented as a set outperforms implementation
using a list or an array.
Thus what to do? Well, I do not think I'm the smartest child, quite opposite...
however it worth to hint this idea to xslt implementers (see
Suggest optimization). I still do not know if it was fruitful...
P.S. A very similar use case exists for a function index-of($collection, $item).
I know we're not the first who create a parser in xslt.
However I still want to share our implementation, as I think it's beautiful.
In our project, which is conversion from a some legacy language to java, we're
dealing with dynamic expressions. For example in the legacy language one can
filter a collection using an expression defined by a string:
collection.filter("a > 0 and b = 7");
Whenever expression string is calculated there is nothing to do except to parse such
string at runtime and perform filtering dynamically. On the other hand we have
found that in the majority of cases literal strings are used. Thus we have decided to
optimize this route like this:
collection.filter(
new Filter<T>()
{
boolean filter(T value)
{
return (value.getA() > 0) and (value.getB() = 7);
}
});
This means that we're converting that expression string into java code on the
generation stage.
In the xslt - our generator engine - this means that we have to convert a string
into expression tree like this:
(a > 7 or a= 3) and c * d = 2.2
to
<and>
<or>
<gt>
<identifier>a</identifier>
<integer>7</integer>
</gt>
<eq>
<identifier>a</identifier>
<integer>3</integer>
</eq>
</or>
<eq>
<mul>
<identifier>c</identifier>
<identifier>d</identifier>
</mul>
<decimal>2.2</decimal>
</eq>
</and>
Our parser fits naturally to the world of parsers: it uses xsl:analyze-string instruction to tokenize input and
parses tokens according to an expression grammar. During implementation I've
found some new to me things. I think they worth mentioning:
-
As tokenizer is defined as a big regular expression, we have rather verbose
regex attribute over xsl:analyze-string . It was hard
to edit such a big line until I've found there is flag="x" option that solves
formatting problems:
The flags attribute may be used to control the interpretation of the regular expression... If it contains the letter x, then whitespace within the regular expression is ignored.
This means that I can use spaces to format regular expression and /s to specify space as part of expression.
-
Saxon 9.1.0.1 has inefficiency in implementation of
xsl:analyze-string
instruction, whenever regex contains literal value however with '{' character
(e.g. "\p{{L}}"), as it considers the value to be an AVT and delays pattern
compilation until runtime, which it does every time instruction is executed.
Use following link to see the xslt:
expression-parser.xslt.
To see how to generate java from an xml follow this link:
Xslt for the jxom (Java xml object model), jxom.zip.
Yesterday, incidentally, I've arrived to a problem of a dynamic error during evaluation of a template's match.
This reminded me
SFINAE in C++. There the principle is applied at compile time to find a
matching template.
I think people underestimate the meaning of this behaviour. The effect of
dynamic errors occurring during pattern evaluation is described in the
specification:
Any dynamic error or type error that occurs during the evaluation of a pattern against a particular node is treated as a recoverable error even if the error would not be recoverable under other circumstances. The optional recovery action is to treat the pattern as not matching that node.
This has far reaching consequences, like an error recovery. To illustrate what I'm talking about please look at this simple stylesheet that recovers from "Division by zero.":
<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:xs="http://www.w3.org/2001/XMLSchema">
<xsl:template match="/">
<xsl:variable name="operator" as="element()+">
<div divident="10" divisor="0"/>
<div divident="10" divisor="2"/>
</xsl:variable>
<xsl:apply-templates select="$operator"/>
</xsl:template>
<xsl:param name="NaN" as="xs:double" select="1.0 div 0"/>
<xsl:template
match="div[(xs:integer(@divident) div xs:integer(@divisor)) ne $NaN]">
<xsl:message select="xs:integer(@divident) div xs:integer(@divisor)"/>
</xsl:template>
<xsl:template match="div">
<xsl:message select="'Division by zero.'"/>
</xsl:template>
</xsl:stylesheet>
Here, if there is a division by zero a template is not matched and other
template is selected, thus second template serves as an error handler for the
first one. Definitely, one may define much more complex construction to be
handled this way.
I never was a purist (meaning doing everything in xslt), however this example
along with
indirect function call, shows that xslt is rather equiped language. One just
need to be smart enough to understand how to do a things.
See also: Try/catch block in xslt 2.0 for Saxon 9.
Among other job activities, we're from time to time asked to check technical skills of job applicants.
Several times we were interviewing people who're far below the
acceptable professional skills. It's a torment for both sides, I should say.
To ease things we have designed a small
questionnaire (specific to our projects) for job applicants. It's sent to an applicant before the
meeting. Even partially answered, this
questionnaire constitutes a good filter against profanes:
<questionnaire> <item>
<question> Please estimate your knowledge in XML Schema
(xsd) as lacking, bad, good, or perfect.
</question> <answer/> </item> <item>
<question> Please estimate your
knowledge in xslt 2.0/xquery 1.0 as lacking, bad, good, or perfect.
</question> <answer/> </item> <item>
<question> Please estimate your
knowledge in xslt 1.0 as lacking, bad, good, or perfect. </question> <answer/> </item> <item>
<question> Please estimate your
knowledge in java as lacking, bad, good, or perfect. </question> <answer/> </item> <item>
<question> Please estimate your
knowledge in c# as lacking, bad, good, or perfect. </question> <answer/> </item> <item>
<question> Please estimate your
knowledge in sql as lacking, bad, good, or perfect. </question> <answer/> </item> <item>
<question> For logical values A, B,
please rewrite logical expression "A and B" using operator "or".
</question> <answer/> </item> <item>
<question> For logical values A, B,
please rewrite logical expression "A = B" using operators "and" and "or".
</question> <answer/> </item> <item>
<question> There are eight balls, with
only one heavier than some other.
What is a minimum number of weighings reveals the
heavier ball?
Please be suspicious about the "trivial" solution.
</question> <answer/> </item> <item>
<question> If A results in B. What one
may say about the reason of B? </question> <answer/> </item> <item>
<question> If only A or B result in C.
What one may say about the reason of C? </question> <answer/> </item> <item>
<question> Please define an xml schema
for this questionnaire. </question> <answer/> </item> <item>
<question> Please create a simple
stylesheet creating an html table based on this questionnaire.
</question> <answer/> </item> <item>
<question> For a table A with columns
B, C, and D, please create an sql query selecting B groupped by C and ordered by
D. </question> <answer/> </item> <item>
<question> For a sequence of xml
elements A with attribute B, please write a stylesheet excerpt creating a
sequence of elements D, grouping elements A with the same string value of
attribute B, sorted in the order of ascending of B. </question> <answer/> </item> <item>
<question> Having a java class A with
properties B and C, please sort a collection of A for B in ascending, and C in
descending order.
</question> <answer/> </item> <item>
<question> What does a following line
mean in c#?
int? x; </question> <answer/> </item> <item>
<question> What is a parser? </question> <answer/> </item> <item>
<question> How to issue an error in the
xml stylesheet? </question> <answer/> </item> <item>
<question> What is a lazy evaluation? </question> <answer/> </item> <item>
<question> How do you understand a
following sentence?
For each line of code there should be a comment.
</question> <answer/> </item> <item>
<question> Have you used any
supplemental information to answer these questions? </question> <answer/> </item> <item>
<question> Have you independently
answered these questions? </question> <answer/> </item> </questionnaire>
I've found that proposition to introduce tuples and maps to xslt/xquery type system has not found a support:
At the joint meeting of the XSL and XQuery Working groups 2008-06-23
it was decided that a change of this nature would be too large for the
next "point" release of the Recommendations. The request for new
functionality will be considered for a future "main" release.
Boor> *****!
Pessimist> Ah, there won't be tuples and maps in xslt/xquery...
Optimist> Wow, chances are good to see this addition by the year 2018!
|