Thursday, October 9, 2014 #

The Power of XSLT and XQuery


About 15 years ago,  software architect bright-sparks  proposed transforming data into HTML as the mutt's nuts for web apps. Of course, upon implementation, webdevs literally retched at the complexity, and moved on to other shiny new things (web forms ?!?).

HOWEVER, it must be stressed that XSLT is a [neglected] INCREDIBLY POWERFUL tool for semi-structured data transformation, and its cousin XQuery is an awesome weapon for querying hierarchal data.


So, here are my reference notes:

XPath

  • Overview - syntax for selecting a subset of nodes in a document (querying an XML document). used in XSLT & Xpointer, precursor for XQuery

syntax:

<axis>::<search element | node test> [<predicate expression>]

eg:

descendant::elementX get elementX from all descendants

  • context node element - starting point in the node tree from where to perform the Xpath query. specifies the document subset to query. can be the root

  • axes - specifies the search direction. can be: child , descendant , parent , ancestor , following-sibling , preceding-sibling , following , preceding , attributes (contains the attributes of the context node), namespace (contains the namespace nodes of the context node), self (only the context node itself), descendant-or-self, ancestor-or-self

  • all nodes (the entire document tree) can be partitioned into 5 axes: ancestor, descendant, following, preceding & self

  • node tests (node type functions) - can be: node() (return all nodes of the context node - not very selective!), element() , attribute() , text() , cdata() , comment() , processing-instruction() , * (true for any node of the principal type)

  • principal node type - every axis has its own principal node type. for most axes the principal node type is ‘element’, but for attributes axis it is ‘attribute’ and for the namespace axis it is ‘namespace’. eg

descendant-or-self::*

attribute::* - fetches all attributes in the context node

attribute::attributeX - fetches all attributeX values in context node

  • constructing paths - XPath expressions can be appended to each other to form a longer expression by separating them with a forward slash. The 1st expression in the path is evaluated in the original context, and the result set of the expression forms the context of the next etc. Each of the nodes in the resultset is used as the context of the following expression

descendant::elementX/parent::*

  • Absolute path - Set an absolute path by prefixing a slash . Eg /child::*/attribute::* - selects nothing because the document root (the child) has no attributes!!! Sets the expression context to the document root (the parent of the root element, not the root element)

  • Abbreviated form - Makes queries shorter.

    • The default node test is *

    • The default axis is child

Child::elementX = elementX

  • The attribute axis can be abbreviated to the prefix @

Attribute::elementX = @elementX

Attribute::* = @

  • The self axis can be abbreviated to the prefix .

Self::* = .

  • The parent axis can be abbreviated to the prefix ..

parent::* = ..

  • The descendant axis can be abbreviated to the prefix //

descendant::* = .//*

/descendant::* = //*

  • predicate expressions for selecting subsets - a way to optionally filter a subset from an XPath resultset. the predicate expression is appended in square brackets [ ]. predicate expressions can contain numeric values, XPath functions & XPath expressions! The filtered resultset from an XPath expression with a predicate expression can be further filtered by appending another predicate to it

    • Can use the following operators: = != <= >= > < and or + - * div mod | (union)

    • Boolean expressions - If the expression evaluates to true then the node remains in the resultset

Child::elementX[position() < 2] – returns only the 1st 2 elements found

Child::elementX[count() > 2] – only returns elements if > 3 are found!

  • integer expressions

Child::elementX[2] – returns only the 3rd element found

Child::elementX[last()] – returns only the 3rd element found

  • node set expressions - if the result of the expression is a node set, then the context node is included if there are nodes in the node set - allows for subquerying! If 2 node sets are compared, the result is true if any one node from the 1st can be matched with any one node from the 2nd ???

Child::elementX[Child::ElementY] – returns only the elements found that have subelements

Child::elementX[Attribute::AttributeX=’xxx’] – returns only the elements found that have a specific attribute value

    • String values - If the string value is numerical (eg [Attribute::AttributeX=’1’] ) then the node’s value is converted & numerically compared! If the string value is literal (eg [Attribute::AttributeX=’xxx’] ) then the expression is true if the string values are identical

  • Node set XPath functions

    • Count (node set) – returns number of nodes found

    • Last ()

    • End() – equivalent of last()

    • Position () – returns the position number of the context node in its set – nth element – eg return every 2nd element: [position() mod 2 = 1]

    • Id (‘xxx’) – returns nodes that have a specific ID attribute value(s)

    • Key (‘xxx’) – returns nodes that have a specific key

    • Namespace-uri (node set) – returns a string containing the namespace URI of the passed node set eg //*[namespace-uri() = ‘http://www.w3.org//1999/xsl/transform’

    • index() – returns index number of the context node within its parent

    • nodename() – returns the tag name including namespace prefix

    • nodetype() – returns a number indicating node type

    • value() – returns the value of an element or attribute

  • string XPath functions

    • string (object) – converts the passed object to a string

    • date (string) – converts the passed string to a date

    • starts-with (string1, string2) – check if the 1st string starts with the 2nd string – eg [starts-with (@lastname, “A”)]

    • translate (string1, string2, string3) – takes a string & char by char compares to 2nd string – if matched, converts to 3rd string

    • eg convert to upper case:

descentant::elementX

[

starts-with

(

translate

(

@lastname,

“abcdefghijklmnopqrstuvwxyz”,

“ABCDEFGHIJKLMNOPQRSTUVWXYZ”

),

“A”

)

]

  • number XPath functions

  • number (object) – converts any passed value to a number (Booleans go to 1 or 0)

  • sum (node set) – returns the sum of the numerical values of all passed nodes

  • round (n), floor(n), ceiling(n) – convert floating point number into integer

  • Boolean XPath functions

  • Not() – converts a Boolean value to its opposite

  • True() – always returns true

  • False() – always returns false

  • Lang() – used to check the language of the content?



XSLT

  • XSL - original goal was to convert XML to HTML. divided into 2 parts: 1) XSLT – transformation, 2) XSL-FO - Formatting objects – still in development

  • XSL-FO - formatting objects. define the display format of an XML document. uses CSS box model. use XSLT to make document display target specific. dynamically create PDFs

  • XSLT - Extensible Stylesheet Language Transformations. While it is fairly easy to generate WebForms with an editor, this approach is not maintainable – if there is a change in layout or style, then we have to rebuild dozens of pages  poor maintainability. A Stylesheet is a set of rules (themselves written in XML) For transforming an XML document. Also an alternative method to styling a document than CSS. Rules described in XML on how to convert a document from one schema to another. Involves 3 documents: 1) XML source, 2) XSLT transformation Stylesheet, 3) XML destination. Carried out by XSLT processor

  • Tool XSLTester from vbxml.com allows you to see source, Stylesheet & dest docs side by side

  • Templates - Each Stylesheet is composed of templates - defines how source document content elements are to appear in the destination document. like an event handler – produces nodes in the output document, but can also raise events itself. always has an XPath expression that describes what nodes in the source the template first applies to. At the start of transformation the event for processing the root is raised.

  • Transform steps: 1) starts with the XML Document data & searches for the context node to start transformation from. 2) the XSLT processor searches the XSL Stylesheet file for the correct template for transforming the node. 3) the template defines certain output nodes which are added to the result document. 4) the template specifies which node to process next (Goto step 2). 5) the process ends when there are no more nodes specified to process next. the most common form is for every template to tell the processor to continue by processing the children of the current node – ensures all nodes are processed & that no infinite loops occur

  • E.g.

var oXMLDocument As DOMDocument;

var oXSLTransform As DOMDocument;

oXMLDocument.Async = False;

oXSLTransform.Async = False;


oXMLDocument.Load “http://localhost/myVDir/myXML/x.xml”;

oXSLTransform.Load “http://localhost/myVDir/myXSL/x.xsl”;


strResult = oXMLDocument.TransformNode (oXSLTransform);

objXMLDocument = oXMLDocument.Transform (oXSLTransform);

  • XML to XHTML - One of XSL’s main uses is to transform XML to XHTML - An XML router. Unlike CSS, not limited to dynamically configuring only HTML. Generated HTML must be lower case to produce valid XHTML. If you want to produce HTML instead of XHTML, use <xsl:output method=”html” >

  • XML to XHTML with CSS support - insert a style attribute or a specific class attribute (that is referenced) into the specific XHTML element. this combination provides a very dynamic & powerful UI engine. don’t have to recompile a single line of code to change a display option, just modify the .xsl & .css files. instead of embedding cell formatting, fonts etc in the XSL, reference classes defined in CSS  just edit the CSS for changes – don’t have to sift through XSL <font> tags. e.g.

<? xml version=”1.0” ?>

<xsl:stylesheet version=”1.0” xmlns:xsl=“http://www.w3.org/1999/XSL/Transform” />


<xsl:template match=”DOCUMENT” >

<html>

<body>

<xsl:apply-templates select=”TITLE” />

<xsl:apply-templates select=”INTRO” />

<xsl:apply-templates select=”BODY” />

</body>

</html>

</xsl:template>


<xsl:template match=”TITLE” >

<xsl:apply-templates />

<p/>

</xsl:template>


<xsl:template match=”INTRO” >

<xsl:apply-templates />

<p/>

</xsl:template>


<xsl:template match=”BODY” >

<xsl:apply-templates select=”ITEM”/>

<p/>

</xsl:template>


‘—a comma delimited list

<xsl:template match=”ITEM” >

<xsl:apply-templates />

<xsl:if test=”position() != last()”>

,

</xsl:if>

</xsl:template>


</xsl:stylesheet>

  • client side XSLT - PI tells the browser which XSL file to download & use. Can take a large part of processing from server to client. E.g.

<? xml version=”1.0” encoding=”utf8” ?>

<? xml-stylesheet type=”text/xsl” href=”x.xsl” ?>

<ROOT>

</ROOT>


XSLT elements for composing the XSLT Stylesheet:

  • <xsl:Stylesheet> , <xsl:transform> , <xsl:import> , <xsl:apply-imports> , <xsl:include> , <xsl:output> , <xsl:template> , <xsl:apply-templates> , <xsl:call-template> , <xsl:attribute-set> , <xsl:strip-space> & <xsl:preserve-space> , <xsl:namespace-alias> , <xsl:key>

<xsl:Stylesheet>

  • Normally the root element of a Stylesheet. Holds templates & contains configuration attributes. Elements that can only appear as direct child subelements of Xsl:Stylesheet are called top level elements. Attributes:

  • Xmlns:xsl - To differentiate the XSLT specific elements in a Stylesheet from other XML content. the stylesheet uses the official XSLT namespace: xmlns:xsl=“http://www.w3.org/1999/XSL/Transform” (doesn’t actually point to a real URL)

  • Version - Ensure that later additions to the XSLT specification can be implemented without changing existing stylesheets. Defaults to “1.0” – the current version. If set to anything else, the XSLT processor switches on forward compatibility mode – ignores any unknown elements or elements in the wrong place

  • Extension-element-prefixes - Allows XSLT processor vendors to add their own private extensions. Use to assign namespace prefixes (besides the default xsl:) as XSLT prefixes. These prefixes must be defined namespaces. The XSLT processor will watch out for any namespace prefixes specified. To determine if the XSLT processor supports an extension element or function use the XSLT functions element-available() and function-available()

  • Exclude-result-prefixes - To exclude specific namespaces in the source document from appearing in the destination document. Default – all namespace declarations in the source document automatically appear in the destination document except xsl:

  • Eg a simple Stylesheet:

<?xml version=”1.0” ?>

<xsl:stylesheet

id=”stylesheet1”

version=”1.0”

xmlns:xsl=“http://www.w3.org/1999/XSL/Transform”

extension-element-prefixes=<tokens>

exclude-result-prefixes=<tokens>

>

<xsl:template match=”/”>

<root_node/>

</xsl:template>

</xsl:stylesheet>


this stylesheet will transform any source document into the following destination document:

<root_node/>

<xsl:transform>

  • Exactly the same as xsl:stylesheet

<xsl:import>

  • Allows you to construct a Stylesheet from several reusable external stylesheet document fragments. Beware of relative paths  VB6 DOM transform errors! The document retrieved from the URI should be a Stylesheet document itself – the children of its xsl:stylesheet element are imported directly into the main xsl:stylesheet element. Can only be used as a top level element. Must appear before any xsl:template elements. Local rules override imported rules!!! Circular references are illegal (even indirect ones). If the main XSLT document contains templates that match the same XPath expression of templates in the Stylesheet imported by <xsl:import>, then the main Stylesheet templates will override the imported ones. When several documents are imported, the XML processor builds a tree of imported documents.

<xsl:import href=”xxx.xsl” />

<xsl:apply-imports>

  • use to override & extend any imported templates. e.g. encase the transformed value between 2 strings:

<xsl:import href=”xxx.xsl” />

<xsl:template match=”ELEMENTX” >

xxx <xsl:apply-import /> xxx

</xsl:template>

<xsl:include>

  • Simpler than xsl:import. Just insert the rules from the referenced URI. Can only appear at the top level. Difference – can appear after an xsl:template element

<xsl:output>

  • set of attributes which specify the style of generated output. Attributes:

  • method - has 3 possible values: “xml | html | text” – upon which the other attribs are based. default = xml. if set to html: empty elements will not automatically receive a closing tag , script & style elements will not be escaped, non ASCII chars are HTML escaped. if set to text output will be restricted to only the string values of every node

  • version - for method=”xml”: specifies which XML version – default = “1.0”. for method=”html”: specifies HTML version – default = “4.0”

  • encoding - for method=”xml”: default to “UTF-8”. for method=”html”: if an encoding is specified, a <meta> tag is included in the <head>

  • indent - values = “yes | no” default is no. yes adds more whitespace to improve readability

  • cdata-section-elements - tells the processor when to use CDATA sections in the dest document and when to escape illegal chars by using entity references. e.g. < is replaced by &lt; value holds a space delimited list of element names – text nodes whose parent node appears here will be outputted as CDATA sections, else they are escaped

  • omit-xml-declaration - values = “yes | no” default is no

  • doctype-system - set validation rule that a <!DOCTYPE fragment will be included before the 1st element. the value of this attrib is the DTD URL (system identifier). doctype attrib value in the dest document will be name of root element

  • doctype-public - as above except doctype attrib value in the dest document will refer to a public DOCTYPE

  • media-type - used to specify a MIME type for dest document. default = “text/xml”. media-type defaults to “text/plain”. can set other media types

<xsl:template>

  • the main building block of an XSLT Stylesheet. start processing from the XML element(s) that match the match XPath statement. consists of 2 parts: 1) the match pattern – defines which nodes can act as input for the template; 2) the implementation – defines what the output will look like

  • if several templates match and are of the same mode: a locally scoped template (a child element of <xsl:apply-templates>) will take precedence ; a template within the main stylesheet takes precedence over an imported one; a template imported later takes precedence over a template imported earlier; a template with a higher priority attrib value takes precedence over a template with a lower priority attrib value; a more specific match attrib value takes precedence over a more general match attrib value; if several templates exist in the same document with the same priority attrib, the one nearest the bottom takes precedence.

  • the attributes name, priority & mode are used to differentiate between multiple templates that match on the same node

  • match - holds the matching pattern for the template. specifies what XML element in the source document to apply the template to. syntax – a subset of XPath that uses only the axes: child, attribute & // (descendant)

eg match the document root

<xsl:template match=”/” >


eg match all nodes, but not attributes & the root:

<xsl:template match=”node()” >


eg match any ElementY that has an ElementX as a parent:

<xsl:template match=”child::elementX/child::elementY” >


eg match any ElementY that has an ElementX as an ancestor:

<xsl:template match=”elementX//elementY” >


eg match any ElementX or ElementY:

<xsl:template match=”(elementX|elementY)” >

  • name

  • priority - can be any positive or negative numeric value. if not set, it is calculated from the match attrib as a value between 0.5 and -0.5 as follows:

a specific name along a child or attribute axis  priority=”0”

e.g. child::ELEMENTX or @attribx


unspecified name along a child or attribute axis  priority=” -0.25”

e.g. attribute::* or *


only a node test  priority=”0”

e.g. node() or text()

all other cases  priority=”0.5”

  • mode - use when templates are only applied in special cases. e.g. print templates

  • implementation - any subelements are the content that is placed in the destination document - eg <root_node> - a literal element, not an XSLT element

  • 2 default templates are provided - can be overruled by creating a template that matches the same nodes. default templates process all nodes in the source document. if you try to transform a source document using only the built in templates, the 1st built in template would match the source document root then process all child nodes --> processes the document but produces no output except for any text nodes (matched by 2nd built in template)

1) match all elements & the root

<xsl:template match=”*|/”>

<xsl:apply-templates />

</xsl:template>


2) match text nodes & all attributes

<xsl:template match=”text()|@*”>

<xsl:value-of select=”.” />

</xsl:template>

  • simplified syntax - for simple Stylesheets consisting of only 1 template that matches the root, the whole document is considered the content of the template

<html xmlns:xsl=”http://www.w3.org/1999/XSL/Transform” >

<body>

<xsl:value-of select=”/ELEMENTX/ELEMENTY” />

<p/>

</body>

</html>

<xsl:apply-templates>

  • start the processing of a node – invoke another template. way to tell XSLT processor to continue processing other nodes after finding a source document node that matches an xsl:template & implementing it in the destination document. the most common XSLT mistake is to leave this out! selects nodes to process next using an XPath expression. set the next context node for the XSLT processor to apply an xsl:template to. the transformed output of the specified node will appear within the output generated by the current template. attributes:

  • Select - specifies which nodes to transform next using an XPath expression. if not specified, defaults to child::node() – all child nodes of the current context excluding attributes

  • Mode - only use an <xsl:template> if it has the same mode attrib value

  • eg do all elements!

<xsl:template match=”/”>

<root_node>

<xsl:apply-templates /> ‘does the child elements of root

</root_node>

</xsl:template>


<xsl:template match=”*”>

‘—triggered by the 1st <xsl:apply-templates> AND recursively!

‘—match all nodes in current context

<result_node> ‘—just an arbitrary node we made up

‘—go to child elements

<xsl:apply-templates /> ‘—because of “*” recursive!

</result_node>

</xsl:template>

  • eg do all elements to HTML output using literals!

<xsl:template match=”/”>

<HTML><BODY>

<xsl:apply-templates />

</BODY></HTML>

</xsl:template>


<xsl:template match=”*”>

<xsl:apply-templates />

<!- some content here -->

</xsl:template>

<xsl:call-template>

  • used to organize templates in a document. the target template must have a name attribute. works like <xsl:apply-templates> but without changing the context node. if a template is called by name attrib the match attrib is ignored. see Wrox proff VB6 XML pg 196 for example

<xsl:attribute-set>

  • use to define attributes that multiple elements can use  smaller & easier to maintain XSL documents. can be used to define attributes that are used together e.g.

<xsl:attribute-set name=”myattribs” >

<xsl:attribute name=”size”>

5

</xsl:attribute>

<xsl:attribute name=”face”>

Arial

</xsl:attribute>

</xsl:attribute-set>


<xsl:template match=”ELEMENTX” >

<font xsl:use-attribute-set=”myattribs” >

<xsl:apply-templates />

</font>

</xsl:template>

<xsl:strip-space> & <xsl:preserve-space>

  • 2 points during transformation where whitespace can appear or not: 1) when parsing the source & Stylesheet documents and constructing a tree, 2) encoding a generated XML tree to the dest document. parser removes all text nodes that: consist entirely of whitespace chars, have no ancestor node with the space attrib set to preserve, are not children of whitespace preserving element, after stripping space from source & Stylesheet docs, parsing occurs, for the Stylesheet, the only whitespace preserving parent is <xsl:text>. NOTE: by default, all elements in the source document preserve whitespace

  • elements attribute - space delimited list of elements in the source doc. use to specify which elements to explicitly strip or preserve whitespace for. can accept XPath expressions. conflicts are resolved like the Template conflict resolution

<xsl:namespace-alias>

  • used only when transforming a source doc into a XSLT document. allows dest document to hold the XSLT namespace & literal elements without interfering with the transformation process. allows you to use another namespace in the Stylesheet and have its declaration show up in the dest document with another URI. in the transforming XSLT, literal XSLT output elements have fake namespaces, but in the dest XSLT document, the same prefixes will refer to the correct URI.uses 2 attribs to accomplish this: stylesheet-prefix and result-prefix. e.g.

<xsl:stylesheet version=”1.0”

xmlns:xsl=”http://www.w3.org/1999/XSL/Transform”

xmlns:myxsl=”http://www.w3.org/1999/XSL/MyTransform” >

<xsl:namespace-alias stylesheet-prefix=”myxsl” result-prefix=”xsl” />

<xsl:template match=”/” >

<myxsl:stylesheet>

<xsl:apply-templates>

</myxsl:stylesheet>

</xsl:template>

</xsl:stylesheet>

<xsl:key>

  • analogous to creating an RDBMS index. attribs: name - specify a name for the key, match - XPath statement of where the index should be created, use - specify which attrib to index. allows direct access to document nodes via the key() function - 2 params: name & value - returns a string holding all matching nodes. note: a node can be indexed by multiple keys. use when XML elements refer to each other using IDs, but without validation. increases readability & helps perf as the XSLT processor keeps all source document key references in an in memory hash table eg

to set a key:

<xsl:key name=”mykey” match=”ELEMENTX” use=”@attribx” />

to use:

key(‘mykey’, ‘xxx’)



XSLT Elements that generate output elements

  • Place as subelements of xsl:template elements

  • Literals - The most easily understandable elements in an XSLT Stylesheet. Any fragment of valid XML within an <xsl:template> element that is not in the xsl: namespace. Passed to destination document as is. Can include both text & XML elements. Must always be well formed. Cannot include other node types e.g. comments or CDATA

  • Attribute value templates - Much more readable than xsl:attribute. Can contain an expression in curly brackets that is evaluated. Evaluated before execution of the element the attribute is in??? Can be an Xpath expression

In source XML Doc:

<imageElement>

<url>myImages/x.jpg</url>

<size width=”50” />

</imageElement>


In XSL file:

<xsl:template match=”imageElement” >

<img src=”{url}” width=”{size/@width}” />

</xsl:template>


In dest XML Doc:

<img src=”myImages/x.jpg” width=”50” />

<xsl:value-of>

  • generates text output containing the string value of the context node. attributes:

  • Select - indicates which node’s value to output. an Xpath expression that is evaluated in the template’s context. eg select=”@attributeX”

  • disable-output-escaping - use if source XML doc text contains reserved chars that you don’t want the XSLT processor to replace with escape chars. only use if you don’t require the dest doc to be well formed. (can use <xsl:eval no-entities=’true’ instead)

<xsl:copy>

  • creates a node in the destination document with the same node name & node type as the context node. doesn’t copy attributes or children of context node

<xsl:copy-of>

  • copy a set of nodes to the destination document. has a select attribute to indicate which nodes to copy relative to the source context node. similar to xsl:value-of except it copies instead of converts & it will copy all selected nodes, not just the 1st

<xsl:element>

  • allows creation of elements in destination document. attributes (actually attribute value templates):

  • name – compulsory - specifies destination element name

  • namespace – optional - set the namespace of the created element. if set, the XSLT engine may change the prefix set in the name attribute

<xsl:attribute>

  • generates attributes in the destination document. set the value of a given attribute to the value obtained dynamically through an XPath select statement in an <xsl:value-of> element

  • limitations: cannot insert an attribute after child elements have been added to that element, can only be used in a the context of an element (cant add to the context of a comment node), within the attribute element, no node may be generated other than text nodes, attribute nodes can obviously not have child nodes

  • often used to create attributes in the output that have a calculated name. attribute value templates includes all XSLT literal attributes + some attributes on predefined XSLT elements

<xsl:template match=”@AttributeX”>

<xsl:attribute name=”AttributeY”>

<xsl:value-of />

</xsl:attribute>

</xsl:template>

  • can contain an expression to be evaluated within curly braces, which is evaluated before the attribute’s container element is executed e.g.

<ELEMENTX attribx=”xxx{4 + 5}” />



<ELEMENTX attribx=”xxx9” />

  • the expression can be XPath – e.g.

--source xml:

<PICS>

<PIC idattrib=”xxx” >

<URL>images/x.jpg</URL>

<SIZE width=”50” />

</PIC>

</PICS>


--xsl:

<xsl:template match=”/” >

<DOCUMENT>

<IMAGES>

<xsl:apply-templates select=” PICS/PIC” />

<IMAGES>

</DOCUMENT>

</xsl:template>

<xsl:template match=”PIC” >

<img src=”{URL}” width=”{SIZE/@width}” >

<xsl:attribute name=”id” >

<xsl:value-of select=”@idattrib” />

</xsl:attribute >

</img>

</xsl:template>


--dest xhtml:

<DOCUMENT>

<IMAGES>

<img src=”images/x.jpg” width=”50” id=”xxx”/>

</IMAGES>

</DOCUMENT>

<xsl:text>

  • this element creates a text node in the destination document, holding the content of the original text element. better than a literal because it can include whitespace. attributes:

  • disable-output-escaping - see <xsl:value-of> for explanation

  • e.g. the following 2 are identical in result:

<xsl:template match=”ELEMENTX” >

<xsl:text> xxx </xsl:text>

</xsl:template>


<xsl:template match=”ELEMENTX” >

xxx

</xsl:template>

<xsl:processing-instruction>

  • generate a PI in the destination document. typically for preprocessing – specifying the transformation rules for the next step. can only contain text, no subelements. the text cannot contain the string?> as it signals end of PI.

  • name attribute must contain a valid PI name, but not “xml” – this XSLT element cannot be used to generate the actual XML declaration

  • has 2 attributes that must be in the text: href and type – must be created as text nodes, not attributes, because the PI content is not necessarily well formed XML

<xsl:processing-instruction name=”xml-stylesheet” >

href=”x.xsl” type=”text/xsl”

</xsl:processing-instruction>



<? xml-stylesheet href=”x.xsl” type=”text/xsl” ?>

<xsl:comment>

  • the only way to create comments in the destination document, because comments in the source doc are ignored

<xsl:comment > xxx </xsl:comment >



<!—xxx -->

<xsl:number>

  • numerical conversion tool – creates a formatted numeric value in the output. simplest way to use is just specify value attrib. attribs:

  • value - e.g. “1000” - string is evaluated & converted to a number, rounded to an integer & converted back into a string

  • level - can be “single | multiple | any”. single is default, multiple can return many concatenated numbers

  • count - specify a pattern to match

  • from - specify a pattern. allows us to look at only matching part of the ancestor axis

  • format - values can be: “1” – default = integers, “01” – integers with 0 prefix, “I”, “i" – upper/lower case roman numerals, “A”, “a” – upper/lower case alphabetic

  • grouping-seperator - the separator char – default = “.”

  • grouping-size - a number to specify how many chars between each grouping char

  • e.g.

<xsl:number value=”1000000” grouping-size=”3” grouping-seperator=”,” />



1,000,000

<xsl:eval> and <xsl:script>

  • not standard – Microsoft extensions. the <xsl:eval> element generates a text node in the dest document using script. the <xsl:script> element contains script function definitions that can be called from the <xsl:eval> element or from attribs that are evaluated as an expression. because scripting languages contain non allowable XML chars, place in CDATA nodes. the this value refers to the context node. e.g.

‘—source XML:

<ELEMENTX attribx=”A” attriby=”100” />


‘—XSL:

<xsl:template match=”ELEMENTX[attribx=’A’]”>

<xsl:eval language=”JavaScript” >

getInt (this.getAttribute (‘attriby’))

</xsl:eval>

</xsl:template>

<xsl:script language=”JavaScript” > <![CDATA[

Function getInt (intX)

{

getInt = intX * 10;

}

</xsl:script>

<xsl:message>

  • rarely used. for issuing warnings & errors. has 1 attrib: terminate – if set to “yes” the processor stops after the message.


XSLT programmatic Elements

<xsl:if>

  • for conditionals. has 1 attrib: test – takes an XPath expression as a param. If it returns false (no nodes) then the content of this element is not executed. can be nested. if you have multiple conditions, use <xsl:choose> instead

<xsl:template match=”ELEMENTX” >

<xsl:if test=”@attribx=’xxx’” >

<xsl:value-of select=”@attribx” />

</xsl:if >

</xsl:template >

<xsl:choose> , <xsl:when> , <xsl:otherwise>

  • a case statement

<xsl:template match=”ELEMENTX” >

<xsl:choose>

<xsl:when test=”@attribx=’xxx’” >

<xsl:value-of select=”@attribx” />

</xsl:when >

<xsl:otherwise >

<xsl:text> not found </xsl:text>

</xsl:otherwise >

</xsl:choose>

</xsl:template >

<xsl:for-each>

  • iterate through all XML elements that match the select XPath statement. for iterating through a set of nodes. select attrib holds an XPath expression. same functionality as <xsl:apply-templates> (as an inline template), but much easier to read

<xsl:template match=”ELEMENTX” >

<xsl:for-each select=”child::ELEMENTY”>

<xsl:value-of select=”attribute::attribx” />

<xsl:text> &#13 </xsl:text> ‘--CR

</xsl:for-each>

</xsl:template>

<xsl:sort>

  • can be used to sort an XSLT iteration. can only be a child element of <xsl:apply-templates> or <xsl:for-each>. optional attribs:

  • order - value can be “ascending | descending”

  • data-type - value can be “alphabetically | numerically”. default value is alphabetically  10 < 9

  • case-order - value can be “lower-first | upper-first”

<xsl:template match=”ELEMENTX” >

<xsl:apply-templates select=” ELEMENTY”>

<xsl:sort select=”attribute::attribx” />

<xsl:sort select=”attribute::attriby” order=”ascending” />

</xsl apply-templates >

</xsl:template>

<xsl:variable>

  • acts like a constant. has a name attrib & an optional select attrib. <xsl:copy-of> is a convenient way to insert variable value into dest document

declare using an XPath expression  numeric value in this case

<xsl:variable name=varx” select=”2” />


declare using an included XML fragment  string value

<xsl:variable name=varx”> 2 </xsl:variable>


to reference the variable, prefix its name with “$”

<xsl:value-of select=”item[$varx]” />

<xsl:copy-of select=”$varx” />

<xsl:param> and <xsl:with-param>

  • acts like a variable. defined as a sub element of an <xsl:template> - a value can be passed when the template is executed via <xsl:call-template> or <xsl:apply-templates>. its select value is used as an initial value and can be changed - used to set attribs of other xsl elements. Set value from another template using <xsl:with-param> - Can be a child of <xsl:call-template> or <xsl:apply-templates> & has 2 attribs: name and select. see Wrox Proff VB6 XML pg 203 to see how to do from DOM. e.g.

‘—set up a template containing a number that uses a param value to set one of its attribs

<xsl:template name=”mytemplate” >

<xsl:param name=”paramx” select=”1. ” />

<xsl:number format=”{$paramx}” />

<xsl:apply-templates />

</xsl:template>


‘—set the value of the param from another template

<xsl:template match=”ELEMENTX” >

<xsl:call-template name=”mytemplate” >

<xsl:if test=”@attribx=’xxx’” >

<xsl:with-param name=”paramx” select=”a. “ />

</xsl:if>

</xsl:call-template >

</xsl:template>

XSLT Functions

  • Can be used in expressions

Generate-id(node-set)

  • Generates a unique ID as a string of alphanumeric chars. Depends on 1st element in passed node-set. If no node is passed, the context node is used

Format-number (number, string, string)

  • 1st param - function Converts it to a string

  • 2nd param - use to specify format - can have 2 values separated by a semicolon to handle positive & negative values. can use the following chars: 0 – digit , # - digit without leading & trailing zeros, . - decimal separator, , - grouping separator, - - negative prefix, % - percent, X - any char can serve as a prefix or suffix

  • 3rd param - optional reference to an <xsl:decimal-format> element (must be a top level element and has attribs: name, decimal-seperator, grouping-seperator)

  • e.g.

<xsl:decimal-format name=”myformat”

decimal-seperator=”,”

grouping-seperator=”.” />

<xsl:template match=”/” >

<xsl:value-of select=”format-number (1111.1, ‘#.###,00’, ‘myformat’)” />

</xsl:template>

document(object, node-set)

  • use to combine info from several source docs into 1 dest doc. object param is a string referring to a specific document URI. node-set is an optional param – nodes are converted to URI strings. requires some XML that references all the documents. e.g. combine stuff in local doc with referenced docs

‘—source doc

<ELEMENTX>

</ELEMENTY>

<ELEMENTZ>

<ELEMENTABC/>

</ELEMENTZ>

<ELEMENTX>

<ITEM type=”url” loc=”http://www.x.com/xxx.xml” />

<ITEM type=”local” loc=”xml/xxx.xml” />

‘—xsl:

<xsl:template match=”ITEM” >

<xsl:if test=”@type=’url’” >

<a href=”{@loc}”>

<xsl:value-of select=”.” />

</a>

</xsl:if >

<xsl:if test=”@type=’local’” >

<a href=”{@loc}”>

<xsl:value-of select=”document(concat(‘xxx’, @loc, ‘.xml’))

/ELEMENTX/ELEMENTY”/>

</a>

(by: <xsl:apply-templates

select=”document(concat(‘xxx’, @loc, ‘.xml’))

/ELEMENTX/ELEMENTZ/ELEMENTABC”/>)


</xsl:if >

</xsl:template>

current()

  • returns the current context. useful in sub-queries & XPath expressions. allows construction of XPath expressions similar to SQL Joins- combine & compare values from different contexts. e.g. (confusing)

each ELEMENTX has 2 sub elements ELEMENTY (one) & ELEMENTZ (many)

1st predicate checks if the text of ELEMENTZ relative to the selected ELEMENTX is equal to the current context of the for-each  selects the ELEMENTX whose ELEMENTZ subelement has the same text value as the current ELEMENTZ

2nd predicate checks if the ELEMENTX’s ELEMENTY subelement’s text value is equal to the current ELEMENTZ’s ancestor ELEMENTX’s ELEMENTY subelement’s text value

<xsl:template match=”ELEMENTZ” >

<xsl:for-each select=”//ELEMENTX[ELEMENTZ/text() = current()/text()]

[ELEMENTY != current()/ancestor::ELEMENTX/ELEMENTY ”>

<a>

<xsl:attribute name=”href” >

mylink <xsl:number/> ‘—e.g. mylink1

</xsl:attribute>

<xsl:value-of select=”ELEMENTY” /> ‘—text value

</a>

<br/>

</xsl:for-each>

</xsl:template >



XQuery


XQuery Overview

  • This technology facilitates query searches of distributed datasources (XML documents or XML Streams exposed from Relational Databases or WebServices) over the entire semantic web.

  • XQuery is to XML data is what SQL is to relational data

  • Designed for working with node sets, not individual values

  • Returns structured hierarchical( user defined ), dataset, unlike SQL which returns a flattened dataset that must be rebuilt as XML

  • Standard - platform & DB independent - can operate over any form of XML

  • Limits - read only - unlike SQL, does not support updates

  • Superseded competition - XQL, SQLX, Oasis TransQuery

  • Version 2.0 - supports read/write, overloading & polymorphic functions, extensibility mechanisms, data definition facilities for persistent views, ability to access the SQLXML functionality of XSD mapping schemas (to improve performance and more efficiently control the structure of the returned XML outside of the SQLXML query), ability to specify a URI to retrieve XML directly from SQL Server, and XML Templates that contain multiple XML PIs (processing instructions )


W3C XML specifications interact with XQuery:

  • XPath

    • A component of XSLT & XQuery

    • Expresses paths through an XML hierarchy to one or a set of nodes

    • XPath 2.0 is sequence based - can understand the concept of ordering in a sequence of nodes

  • XML Schema

    • Templates for an XML document

    • XQuery is compatible & can define XML behaviors beyond just the minimum & maximum bounds

  • PSVI Infoset

    • Post schema validation

    • Generated by XML Schema processors to ensure that the XQuery data model captures (& stores in memory ) everything the parser determines about the document

    • Http://www.w3.org/tr/xml-infoset/

  • XSLT

    • XQuery is more than XSLT without the template rules & some XPath axes - has several advantages over XSLT:

    • XQuery can query over multiple documents

    • XQuery is a more compact syntax

    • XQuery supports the XML Schema type system

    • XQuery is designed for database optimization


XQuery syntax

  • Path expressions - based on XPath 1.0 syntax, can navigate to a set of nodes or values in the XML document - includes an inter-document dereference & range operators

  • element constructors - return hierarchical XML data using the literal <starttag> & </endtag> elements to build resultset XML structure & curly brackets {} to distinguish literal content from evaluated sub-expressions

  • FLoWeR expressions - (FOR, LET, WHERE, RETURN ) - more powerful version of SQL SELECT statement - return information that satisfies the condition

  • Rich set of expression functions & operators

  • Conditional expressions - if ... Then ... else

  • quantified expressions - flower expressions can check that some or all tuples created by the FOR & LET clauses satisfy a given condition by using the WHERE SOME & WHERE EVERY predicate clauses - test every value of a collection, composing output while narrowing a search - EVERY operates like a logical AND, and SOME operates like a logical OR

  • E.g.

FOR $NodeSetX IN document("xxx.xml")//elementX

WHERE SOME $NodeSetY IN $NodeSetX/elementY SATISFIES contains ( $NodeSetY , "xxx")

RETURN

$NodeSetX

  • Expressions that test or cast (modify) data types - can treat an expression as though it were a subtype of its actual type Variables are not assigned to, but bound so that values are immutable - prevents side affects of value reassignment, allows query optimization

  • Select members of a set & return them to the output stream

  • the FOR clause - handles iteration over sequences by specifying a variable (prefixed with "$") that acts as a variable reference that points to each element in the selection of nodes

  • The IN clause - reference an XPath expression to assign values to the variable specified in the FOR clause

  • The LET clause - handles assignment of sequences to a placeholder variable

  • The RETURN clause - return XML results as specified within the curly brackets - converts their contents into XML

  • RETURN does not work like a Return statement in a programmatic language - it doesn't return a single value, instead acting as a pattern construction template for each value assigned to each NodeSet variable specified in a FOR or LET clause - ensuring delivery of well formed XML fragments

  • Subqueries & expression chaining - compose complex queries by including a FLWR expression within a RETURN clause

  • The WHERE clause - evaluates a boolean predicate to filter the returned NodeSet

  • The IN clause - same functionality as WHERE, but uses XPATH

  • WHERE string ($NodeSetX/elementY) = "xxx" --is equivalent to: IN document ("xxx.xml") //elementX[elementY="xxx"]

  • The document () function references an XML document

  • The string() function retrieves the text node of an element and converts it into a string expression

  • E.g. select member elements of a set:

FOR $NodeSetX IN document ("xxx.xml") // elementX

WHERE string ($NodeSetX/elementY) = "xxx"

RETURN {$NodeSetX} -- return matching elements

  • The RETURN statement can return complex expressions - e.g. an XHTML unordered list:

RETURN

<li>

{string ($NodeSetX/elementY)}

</li>

  • can embed an XQuery expression within any XML element - e.g. in XHTML:

<body>

<ul>

FOR $NodeSetX IN document ("xxx.xml") // elementX

WHERE string ($NodeSetX/elementY) = "xxx"

RETURN

<li>

{string ($NodeSetX/elementY)}

</li>

</ul>

</body>

  • The LET clause - assign node sequences to a single variable to be used by the FOR statement to iterate through a sequence

  • The LET statement creates NodeSet variables of 0 or more nodes - the NodeSet is connected to the source XML as each node acts as a pointer to a source node

  • Use the XPath function value-distinct to remove duplicate nodes from a NodeSet

  • E.g.

LET $NodeSetX := document ("xxx.xml") // elementX

LET $NodeSetY := value-distinct (document ("xxx.xml") // elementY)


FOR $NodeSetA IN $NodeSetX

RETURN

<elementA >

<elementJ >

{string($NodeSetX)}

</elementJ>

<elementY>

{

FOR $NodeSetB IN $NodeSetY

WHERE $NodeSetB/elementA = $NodeSetA

RETURN

<elementB>

{string($NodeSetB/elementZ )


}

</elementB>


}

</elementY>


</elementA>

  • Constraining FLWR statements - improve query efficiency by terminating a set of comparisons once a hit has been met

  • use the SOME and SATISFIES keywords to setup a condition where queries are made until a single conditional expression evaluates as true, at which point the RETURN expression is called - e.g.

FOR $NodeSetX IN document ("xxx.xml") // elementX

WHERE SOME $propertyX IN $NodeSetX/*

SATISFIES contains ($propertyX, 'abc')

RETURN { $NodeSetX }

  • Note: $NodeSetX/* - all children

  • The BEFORE & AFTER keywords constrain the range of searchable elements in either direction, reducing the amount of processing required - e.g.

FOR $NodeSetX IN document ("xxx.xml") // elementX

BEFORE string ($NodeSetX/attributeX ) = "aaa"

AFTER string ($NodeSetX/attributeX ) = "eee"

RETURN { $NodeSetX }

  • can use conditional statements in a RETURN clause (more powerful than WHERE) - e.g.

RETURN <elementX>

{

IF ($NodeSetX/elementY )

THEN

{

string($elementA),

string($elementB/@href)

}

ELSE

{

string($elementC)

}

}

  • the SORTBY operator acts on the FOR operator to sort a sequence by the value of a sub-node of the NodeSet - each sorting expression is evaluated for each item in the source expression and its values converted to be an operand for the ">" operator -sort order can be ASCENDING / DESCENDING - e.g.

FOR $NodeSetX IN document ("xxx.xml") //elementX[elementY ="xxx"]

RETURN { $NodeSetX }

SORTBY {elementZ DESCENDING}

  • TO - return a sequence range of nodes - Can be used in LET or FOR statements:

LET $NodeSetX := document("xxx.xml")//record[3 TO 10, 15 TO 20]

FOR $NodeSetX IN document("xxx.xml")//record[3 TO 10, 15 TO 20]


Datatypes

  • based on XML Schema - 5 categories: numeric, string, date, node types, sequences

  • Each datatype has its own constructor function that casts a string into the appropriate datatype - e.g.

<elementX>

{

LET $a := float(10.5)

LET $b := float(16.8)

RETURN { $a + $b}

}

</elementX >

  • note: the returned content between the curly brackets is automatically converted into a string

  • Objects can then be input into other expressions or saved to local variables - e.g.

{

LET $startDate := dateTime ("2003-10-10")

LET $interval := 7

LET $newDate := add-days ($startDate , $interval )

RETURN <date>

{ get-day($newDate)} /

{ get-month($newDate)}

{get-year($newDate)}

</date>


}

  • The numeric types & cast functions in order of lowest to highest precedence: integer, byte, int, short, long, decimal, float, double - comparisons convert to the operand with the highest precedence

  • numeric operators: = < > <= >= != + - * div mod - includes unary + -

  • the "/" character is reserved for XPath expression child nodes, thus div is used instead

  • Numeric functions: floor() , ceiling() , round(), abs()

  • Boolean functions: true() , false(), (make code more legible) , boolean-from-string()

  • Boolean functions: boolean-and() , boolean-or(), boolean-not(), not(), not3()

  • 0 is false, all other numbers are true: 3 and 0 = false

  • Dates = true

  • Empty string, empty NodeSets & empty sequences = false

  • The string types (- consist of Unicode character sequences) & cast functions :

    • String

    • NormalizedString - no leading or trailing spaces, all other spaces are 1 char length

    • Token - sequence of alphanumeric characters

    • Language - a sequence that matches the IETF language codes - e.g. "EN"

    • Name - a generalized XML name

    • NMToken - a token used as an Enum value

    • ID - a token used as an ID value

    • IDREF - a token used as an IDREF value

    • ENTITY - a sequence of characters used as an entity

  • String literals can be created by wrapping a sequence of characters in either single or double quotes

  • String comparison - not supported in XPath 1.0 - cannot test the predicate 'xxx' > 'yyy' - can do directly in XSLT via <xsl:sort>

  • Collation -set of rules to describe the relative ordering of 2 strings

  • the codepoint-compare() function - converts 2 strings to Unicode, then compares them - returns 0 if equal & 1 if different

  • The compare() function takes a 3rd argument that specifies a URL to a collation file

  • String functions:

    • Concat(s,s,s...)

    • Starts-with(s,s), ends-with (s,s)

    • Codepoint-contains(), contains()

    • Codepoint-substring(s,s), Substring()

    • String-length ()

    • Codepoint-substring-before (s,s), Substring-before(s,s, collation)

    • Codepoint-substring-after(s,s), Substring-after(s,s,collation)

    • Normalize-space(s), normalize-Unicode (s, normalizationForm)

    • Upper-case(s), lower-case(s)

    • Translate(s, s, s) - replace

    • Match(s, regex) - regular expression

    • Replace(s, regex, s, collation)

    • String-pad-beginning(s,i,s), String-pad-end(s,i,s)

  • Most XQuery work is done on raw untyped XML - regex can be useful

  • Datetime functions - pg 48-51


NodeSets & node operators

  • primary purpose of both XPath & XQuery is the retrieval of NodeSets of 0 or more nodes from a query - XQuery is thus very similar to & supersedes multi-join SQL queries

  • Node operators:

  • ==, !== - tests if 2 nodes do or don’t have the same functional identity - test for duplication of structure , not content values

  • =>- retrieve a node by its ID - left operator is an element or attribute with a value of type IDREF or IDREFS, while the right operand is a node test - the operator de-references the value & returns the referenced nodes that satisfy the node test

  • Is - proposed tests for specific node reference matches - that both point to the same source node

  • Node functions:

    • Local-name(node) - return node name

    • Namespace-uri(node) - return node namespace URI

    • Number(node) - return node value cast as a number

    • Node-equal(node, node) - return true if 2 nodes have the same identity

    • Value-equal(node, node) - return true if 2 nodes have the same value

    • Node-before(node, node)

    • node-after(node, node)

    • Copy(node) - return a deep copy of a node (all its attributes & descendants)

    • Shallow(node) - return a shallow copy of a node (all its attributes but not its descendants)

    • Boolean(node) - cast a node as boolean

    • If-absent(node, simpleType) - if node is an empty sequence, return the content of simpleType

    • If-empty(node, simpleType) - if node is an empty sequence or an element with empty content, return the content of simpleType

  • Note: copies break the implicit link to the source document


Sequence operators

  • a NodeSet is considered a sequence (an array)

  • Sequences allow for more complex data structures - a sequence of XML nodes is a collection of pointers to XML trees, each of which can be a sequence in itself

  • Sequence functions:

  • Position (item, sequence ) - returns integer

  • Last (sequence ) - returns integer

  • Item-at (sequence , decimal ) - return node at a given position

  • Index-of (sequence , type, collation) - return an array of node positions

  • Empty (sequence ) - return boolean

  • Exists (sequence ) - return boolean

  • Identity-distinct(sequence ) - return a NodeSet with all redundant duplicate elements deleted based on node identity

  • Value-distinct(sequence, collation) - return a NodeSet with all redundant duplicate elements deleted based on node value

  • Sort(sequence, collation) -

  • Reverse-sort (sequence, collation) -

  • Insert (sequence, decimal, type) -

  • Sublist-before (sequence, sequence, collation) - return part of the 1st sequence that occurs before the 1st occurrence of the 2nd sequence

  • Sublist-after (sequence, sequence, collation) -

  • Sublist (sequence, decimal, decimal)

  • Sequence-pad-beginning (sequence, decimal, type) -

  • Sequence-pad-end(sequence, decimal, type) -

  • Truncate-beginning (sequence, decimal) -

  • Truncate-end (sequence, decimal)

  • Resize-beginning (sequence, decimal, type) -

  • Resize-end (sequence, decimal, type)

  • Unordered (sequence ) - hint to query optimizer that sequence order is unimportant


Sequence logical operators

  • Sequence-value-equal (sequence, sequence, collation)

  • Sequence-node-equal (sequence, sequence, collation)

  • Union (sequence , sequence )

  • Union-all (sequence , sequence )

  • Intersect (sequence , sequence )

  • Intersect-all (sequence , sequence )

  • Except (sequence , sequence ) - inverse of intersection

  • Except-all (sequence , sequence )


Aggregate functions

  • perform simple math operations on a sequence

  • Count (sequence)

  • Avg (sequence)

  • Max (sequence, collation )

  • Min (sequence, collation )

  • Sum (sequence )


Referencing & filtering functions

  • allow retrieval of XML nodes from a location external to the current node - note: arguments can be sequences - e.g. a sequence of IDREF values

  • These functions establish relational links that are explicit in the data structure for organizational purposes

  • Id (IDREF) - return the NodeSet with matching unique IDs

  • Idref (string) - return the NodeSet with matching unique IDREFs

  • Filter (node) - return a NodeSet consisting of a shallow copy of nodes selected by the expression argument , preserving any interrelationships

  • The Filter() function operates on a tree hierarchy to narrow a query on a NodeSet or extract a summery of tree data

  • E.g. - keep hierarchy, but only the elements selected: Filter (document ("xxx.xml" //(elementX | elementY | elementZ/text() ))

  • Document (URIstring) - return a NodeSet consisting of the root node of the referenced document

  • E.g. use the id function to retrieve a specific set of elements :

LET $Root := document("xxx.xml")

LET $NodeSetX := $Root//id("3", "56")

FOR $ElementX IN $NodeSetX

RETURN

<elementY>

{ $ElementX /attributeX }

</elementY>

  • E.g. use the id function with IDREF types that are IDREF attributes defined in the structure schema

FOR $ElementX IN document("xxx.xml")

//ElementX

LET $NodeSetZ := $ElementX //id(@ElementZ)

RETURN

<elementY>

{ $ElementX /attributeX }

{ $NodeSetZ/attributeX }

</elementY>

  • The idref() function works in reverse - if given a specific IDREF string, it will return a list of all elements that have this IDREF - e.g. find all elements that reference the current element

FOR $NodeSetX IN document("xxx.xml")

//ElementX

RETURN

<elementX>

{ $NodeSetX /attributeX }

<elementY>

{

FOR $NodeSetY IN $NodeSetX //idref(@id)

RETURN

{ $NodeSetY /attributeY}

}

</elementY>

</elementX>


Some Use Cases:

Use case 1: querying a standard XML datasource to retrieve a flat hierarchy

  • Include an outer element to wrap results for it to be well formed XML & encase the XQuery statement in curly brackets to differentiate XML content from XQuery - XQuery expressions within curly brackets are converted into strings when the output is an attribute :

<elementX>

{

FOR $NodeSetX IN value-distinct(document ("xxx.xml")/elementX[@attributeX != "5"]

WHERE number($NodeSetX/@attributeX) > 90

RETURN <elementY attributeX=" {$NodeSetX/@attributeX} " />

}

</elementX>


Use case 2: querying a standard XML datasource to retrieve a tree hierarchy

  • E.g. filter NodeSet for matches with 3 possible XPath expression patterns - note: filter returns a shallow copy

<elementX>

{

LET $NodeSetX := document("xxx.xml")

RETURN

filter( $NodeSetX//elementY |

$NodeSetX//elementY/element Z |

$NodeSetX//elementY/element Z/text())


}

</elementX>

  • E.g. use the comprehensive XPath search // to locate all of a specific element type within a document

<elementX>

{

FOR $NodeSetX IN document("xxx.xml") //ElementX

RETURN

<elementY>

{ $NodeSetX /@*}

{ $NodeSetX /elementY}

{ count($NodeSetX /elementY)}

{ ($NodeSetX //elementY)[3]/elementZ}

{(($NodeSetX //* AFTER ($NodeSetX //elementY)[1]) BEFORE ($NodeSetX //elementY)[2])

</elementY>


}

</elementX>

  • // - the comprehensive XPath descendants search can locate all instances of an element within an XML tree

  • /@* - retrieve all attributes of the current source element & add them to a target container element

  • Attribute values are converted to strings to ensure syntax safety


Use case 3: relational querying

  • The temporal-datetime-contains function takes 3 arguments(start date, end date, current date) & tests to see if current date is between the two

  • The LET clause is used to enforce a PK to FK relationship between 2 XML documents

FOR $NodeSetX IN document("xxx.xml") //elementX

LET $NodeSetW := document ("www.xml") //elementW[element_FKID = $NodeSetX/element_FKID]

WHERE temporal-datetime-contains (

date (concat( "15", string( $NodeSetX /element_start_date))),

date ( "15" + string( $NodeSetX /element_end_date)),

date(currentDatetime()))

AND contains ($NodeSetX/elementY, "xxx")

RETURN

<elementY>

{$NodeSetX/elementA}

{$NodeSetW/elementB}

</elementY>

SORTBY (element_PKID)

  • e.g. to determine which items are in 1 XML document and not the other:

FOR $NodeSetX IN document("xxx.xml") //elementX

WHERE not (SOME $NodeSetY IN document("yyy.xml") //elementY SATISFIES $NodeSetX/elementPKID = $NodeSetY/elementFKID)


Use case 4: full text search

WHERE SOME $NodeSetY IN $NodeSetX// elementY SATISFIES contains( $NodeSetY /text(), "xxx")

OR SOME $NodeSetY IN $NodeSetX// elementY SATISFIES contains( $NodeSetY /text(), $NodeSetW /text())

OR SOME $NodeSetY IN $NodeSetX// elementY SATISFIES contains( string($NodeSetX) $NodeSetW /text())


Use case 5: references between XML documents

  • XML documents can reference each other through the mechanism of IDs & IDREFs

  • The dereferencing operator "->" is used to follow a referential link from an IDREF pointer attribute to a specified element's ID attribute (has a unique value for that attribute)

  • E.g.

<xxx>

{

FOR $NodeSetX IN document ("xxx.xml")// elementX[attributeX = "xxx"], $NodeSetY IN $NodeSetX/@attrib_IDREFy->elementY

WHERE $NodeSetX/elementY/elementZ = "xxx"


RETURN shallow ($NodeSetX/@attrib_IDREFx->elementX ),


}

<xxx>


Comparison of SQL to XQuery

  • Designed with different data models (unordered relational vs. portable XML hierarchical fragments )

  • While SQL is more powerful it is bound to a host RDBMS (with the exception of point to point linked queries ), whereas XQuery can formulate queries which act on XML fragments (or RDBMS that can natively expose XML) distributed all over the internet

  • Key differences:

  • SQL operates on tuple-sets from unsorted tables while XQuery operates on simple datatypes , documents, document fragments & document sequences

  • SQL works on tuples of attributes (rows with well defined columns), while XQuery works on XML nodes

  • SQL has no inherent order, with sorting explicitly specified in the query, while XQuery returns data in the order defined in the source documents or specified in the query

  • While SQL relational data is expressed through DDL and used to validate each DML statement , the minimal structure requirement for XQuery data is a fragment of well formed XML, optionally validated with a XML Schema

  • While SQL supports commands to insert, delete & update tuples , XQuery can only read data

  • While SQL can define a view as a query, XSLT can transform a document over which XQuery can run

  • XQuery is suited to the portable and hierarchical XML data model which is more concise when describing complex data structures - unlike SQL, where a minor change in data structure may require a large redesign

  • Compared to XQuery FLWR statements, SQL is less flexible than XQuery because it only deals with tuple sets

  • Always return a NodeSet or simple datatypes

  • All FOR, LET, WHERE & RETURN clauses take expressions as arguments - can include other FLWR expressions - No limit to chaining FLWR expressions, & can handle complex data structures by iterating over a sequence & binding each of its items to a variable

  • A FLWR expression can have multiple FOR & LET clauses, allowing the definition of multiple variables to be manipulated in the WHERE & RETURN clauses or even other FOR or LET statements

  • A FLWR expression is not a program - it is a bindable template of instructions

  • Path’s role in XQuery is equivalent to that of SQL FROM & WHERE

  • The basic XPath construct is the location path- an expression resembling a readable URI which identifies a portion of an XML document

  • XPath sees the document structure as a tree of nodes, including comments & processing instructions

  • / - points to the root node -returns the whole document

  • //elementX - return a NodeSet of elements no matter where they are in the tree

  • //elementX[6] -

  • //elementX [@attributedX='xxx'] - equivalent to above with a SQL WHERE clause

  • //elementX [//elementY/@attributedY='xxx']/@attributeX - select an attribute instead of an element

  • An XPath location axis selects nodes to narrow the search - absolute axis (prefixed with "/") starts from the root node, while relative axis starts from the context node

  • XPath offers 13 axes: child, parent, self, descendant, ancestor, descendant-or-self, ancestor-or-self, following, preceding, following-sibling, preceding-sibling, attribute, namespace

  • XPath axis selection , node selection & predicate evaluation make up a node testing step

SELECT DISTINCT tableX.colX

FROM tableX

WHERE tableX.colY < 0

XPath equivalent:

//elementX[//elementY/number()>0]/@number


SELECT tableX.colX

FROM tableX

GROUP BY colX

HAVING SUM(colY) = 0

XPath equivalent:

//elementX[count(elementY)=0]/@number


SELECT SUM(tableX.colX)

FROM tableX

XPath equivalent:

Sum (number(//elementY))

  • composing new elements - the equivalent to SQL creating new output columns is using XQuery to compose new XML elements in the query output:

SELECT COUNT(*) AS colNew

FROM tableX

...

<elementNew>

{

count(document("xxx.xml")//elementX

}

</elementNew>

  • E.g. replacing a SELECT statement with a WHERE clause that has multiple AND clauses - use a variable that assumes every possible value in the NodeSet:

FOR $NodeSetX IN document("xxx.xml")//elementX[elementY/attribX='x']

RETURN

<elementX>

<elementA> { string($NodeSetX/elementY/@attributeX) } </elementA>

<elementB>

{

$NodeSetX/elementY/@attributeY

}

</elementB>

</elementX>



Comparison of XSLT to XQuery

  • Both can process multiple XML datasource document trees & generate a presentation ready document by applying transformations according to pattern matches identified by XPath in the source XML Document

  • XQuery has better mechanisms to work with structured & distributed XML data

  • XSLT provides more refined transformation mechanisms, while XQuery allows simple expressions to query structured & distributed XML data

  • XSLT template rules easily describe changes to a document - XQuery requires cumbersome recursion for complex transformations

  • XSLT can create global variables visible to the whole stylesheet, while XQuery variables are bound to an expression result

  • XSLT can generate XHTML while XQuery can only generate results on the XQuery/XPath model

  • XSLT can recursively apply multiple templates and automatically sort precedence of instructions

  • XQuery is more suited for handling data with strict & repeated formatting in contrast to XSLT's ability to easily describe minor updates in a document

  • XQuery can apply paths on multiple source documents & easily compare or apply set operations on the results - while XSLT can deal with multiple documents, it is difficult to do so simultaneously

  • XQuery can define functions that can be used in XPath expressions, while XSLT can only provide callable templates

  • XQuery can match text across element boundaries, while XSLT can only compare contents of single elements & attributes

  • XQuery can perform set operations on the result of path operations (XSLT applies templates on each element that matches a pattern , but can not filter a NodeSet by comparing it with other node sequences)

  • XQuery can express subsets of items of a path, while XSLT, which uses XPath 1.0, which can only refer to sibling items in a path

  • XQuery is best suited for extracting XML fragments from a document , not for transformation of whole documents, adding markup or global restructuring

  • While it is possible to do transformation using XQuery, it is complicated -use XQuery to extract relevant data from huge documents & generate a small XML resultset, then apply XSLT to transform

  • XQuery influence in XSLT 2.0

    • simple manipulation of XML Schema data type content (handled by XPath 2.0) , string content

    • Improved ease of use, interoperability, 1i8n support ,

    • Data grouping support

    • Direct use of IDREF attributes to select paths

    • Note: each language has a clear role - XSLT is for transformation to produce presentation , and not for generation of structured resultsets

Posted On Thursday, October 9, 2014 5:32 AM | Comments (0)

PMML – Predictive Model Markup Language



PMML Overview

  • An XML standard managed by the Data Mining Group (www.dmg.org ) whose members include IBM, Microsoft, Oracle, SAS, SPSS,, NCR, SAP, KXEN, Magnify, MINEit, & StatSoft

  • Predictive Model Markup Language (PMML) is an XML mark up language to describe statistical and data mining models.

  • PMML describes the inputs to data mining models, the transformations used prior to prepare data for data mining, and the parameters which define the models themselves.

  • It is the most widely deployed data mining standard.

  • PMML is complementary to many other data mining standards. It's XML interchange formats is supported by several other standards, such as XML for Analysis.

  • provides a way for applications to define statistical and data mining models and to share models between PMML compliant applications.

  • PMML provides applications a vendor-independent method of defining models so that proprietary issues and incompatibilities are no longer a barrier to the exchange of models between applications.

  • It allows users to develop models within one vendor's application, and use other vendors' applications to visualize, analyze, evaluate or otherwise use the models the exchange of models between compliant applications is now straightforward.

  • One or more mining models can be contained in a PMML XML document.

  • The PMML statistics subset provides a basic framework for representing univariate statistics, such as mean, min, max, counts, standard deviation & frequency

  • PMML is a standard for XML documents which express trained instances of analytic models.

  • PMML supports the following Model classes:

    • Association Rules

    • Decision Trees

    • Center-Based & Distribution-Based Clustering

    • Regression

    • General Regression

    • Neural Networks

    • Naive Bayes

    • Sequences

PMML document structure:

<?xml version="1.0"?>

<!DOCTYPE PMML PUBLIC "PMML 2.0"

"http://www.dmg.org/v2-0/pmml_v2_0.dtd">

<PMML version="2.0">

...

</PMML>

  • The root element of a PMML document must have type PMML.

  • A PMML document can contain zero or more models - The document can be used to carry the initial metadata before an actual model is computed. A PMML document containing no model is not meant to be useful for a PMML consumer.

  • The element <MiningBuildTask> can contain any XML value describing the configuration of the training run that produced the model instance - the natural container for task specifications as defined by other mining standards, e.g., in SQL or .NET.

  • The fields in the <DataDictionary> and in the <TransformationDictionary> elements are identified by unique names - Other elements in the models can refer to these fields by name so that Multiple models on one PMML document can share the same fields defined in these dictionary elements

  • Certain types of PMML models such as neural networks or logistic regression can be used for different purposes - some instances implement prediction of numeric values, while others can be used for classification according to the functionName attribute which specifies the mining function.

  • A Model element has the following attributes:

    • modelName - identifies the model with a unique name in the context of the PMML file.

    • functionName and algorithmName provide informational descriptions of the nature of the mining model, e.g., whether it is intended to be used for clustering or for classification.

  • Basic data types and entities: NUMBER, INT-NUMBER, REAL-NUMBER, PROB-NUMBER (a real number between 0.0 & 0.1) & PERCENTAGE-NUMBER

  • The types <Array> , <NUM-ARRAY>, <REAL-ARRAY> & <STRING-ARRAY> are defined as container structure which implements arrays of numbers and strings in a fairly compact way:

<Array n="3" type="int">

1 22 3

</Array>

<Array n="3" type="string">

ab "a b" "with \"quotes\" "

</Array>

PMML Header Information

  • Header: The top level tag that marks the beginning of the header information.

  • copyright: This attribute contains the copyright information for this model.

  • description: obvious.

  • Application: This element describes the software application that generated the model.

  • name: The name of the application that generated the model.

  • version: The version of the application that generated this model.

  • Annotation: Document modification history is embedded here.

  • Timestamp: This element allows a model creation timestamp

PMML Data Dictionary

  • The data dictionary contains definitions for fields as used in mining models. It specifies the types and value ranges. These definitions are assumed to be independent of specific data sets as used for training or scoring a specific model.

  • A data dictionary can be shared by multiple models, statistics and other information related to the training set is stored within a model

  • The value numberOfFields is the number of fields which are defined in the content of <DataDictionary>, this number can be added for consistency checks. The name of a data field must be unique in the data dictionary. The displayName is a string which may be used by applications to refer to that field.

  • The fields are separated into different types depending on which operations are defined on the values; this is defined by the attribute optype. Categorical fields have the operator "=", ordinal fields have an additional "<", and continuous fields also have arithmetic operators. Cyclic fields have a distance measure which takes into account that the maximal value and minimal value are close together.

  • The optional attribute 'taxonomy' refers to a hierarchy of values and is only applicable to categorical fields.

  • The content of a DataField defines the set of values which are considered to be valid – the mining model will categorize a value as valid, invalid or missing

  • If a categorical or ordinal field contains at least one Value element where the value of property is 'valid' or unspecified, then the set of Value elements completely defines the set of valid values. Otherwise any value is valid by default.

  • The element Interval defines a range of numeric values - The attributes leftMargin and rightMargin are optional but at least one value must be defined. If a margin is missing, then +/- infinity is assumed.

PMML Mining Schema

  • Each model contains one mining schema which lists fields as used in that model - This is a subset of the fields as defined in the data dictionary.

  • While the mining schema contains information that is specific to a certain model, the data dictionary contains data definitions which do not vary per model.

  • The main purpose of the mining schema is to list the fields which a user has to provide in order to apply the model.

  • The usageType attribute can have the following values:

    • active: field used as input (independent field).

    • predicted: field whose value is predicted by the model.

    • supplementary: field holding additional descriptive information.

  • The outliers attribute can have the following values:

    • asIs: field values treated at face value.

    • asMissingValues: outlier values are treated as if they were missing.

    • asExtremeValues: outlier values are changed to a specific high or low value defined in MiningField.

  • name: symbolic name of field, must refer to a field in the data dictionary.

  • highValue and lowValue: for outliers

  • missingValueReplacement: If this attribute is specified then a missing input value is automatically replaced by the given value. That is, the model itself works as if the given value was found in the original input..

  • missingValueTreatment: informational only.

PMML Data flow

  • PMML defines a variety of specific mining models such as for tree classification, neural networks, regression, etc.

  • there are definitions which are common to all models, in order to describe the input data itself and generic transformations which can be applied to the input data before the model itself is evaluated.

  • The <DataDictionary> element describes the data 'as is', that's the raw input data and refers to the original data and defines how the mining model interprets the data, e.g., as categorical, or numerical

  • The <MiningSchema> element defines an interface to the user of PMML models, listing all fields which are used as input to the computations in the mining model. The MiningSchema also defines which values are regarded as outliers, which weighting is applied to a field, e.g., for clustering. Input fields as specified in the MiningSchema refer to fields in the data dictionary but not to derived fields because a user of a model is not required to perform the normalizations.

  • Various transformations are defined such as normalization of numbers to a range [0..1] or discretization of continuous fields, which convert the original values to internal values as they are required by the mining model such as an input neuron of a network model. The mining model may internally require further derived values that depend on the input values defined in the transformations block The transformations cover expressions that were generated by a mining technique - A complete mining project usually needs many other preprocessing steps which may have to be defined manually, and PMML does not provide a complete language for this full preprocessing These data preparation steps must be performed before feeding the values into a PMML consumer.

  • If a PMML document contains multiple models then sharing definitions of normalizations could save space in the document. That's the same idea as for having a common data dictionary. Note, the normalizations may still differ between models, i.e., different models may refer to different sets of derived fields.

  • A derived value, defined by a normalization, can be input for another transformation. E.g. a neural network model could have a linear normalization defined on a log-transformed input field 'income'.

  • The specific definitions of models such as tree classification or neural network may refer to fields listed in the MiningSchema or to derived fields which can be computed from the MiningSchema-fields (incl. transitive closure).

  • The statistics and the specific model can refer to fields in the MiningSchema but also to transformed fields. If there is a replacement value defined for missing values, the statistics refer to the values before the missing values are replaced.

  • The output of a model always depends on the specific kind of model, and the final result, such as a predicted class and a probability, are computed from the output of the model.

  • If a neural network is used for predicting numeric values then the output value of the network usually needs to be denormalized into the original domain of values, which can use the same kind of transformation types - The PMML consumer system will automatically compute the inverse mapping.

PMML Transformation Dictionary & Derived Values

  • At various places the mining models use simple functions in order to map user data to values that are easier to use in the specific model – e.g. for neural networks - internally work with numbers, usually in the range from 0 to 1. Numeric input data are mapped to the range [0..1], and categorical fields are mapped to series of 0/1 indicators..

  • PMML defines 4 kinds of simple data transformations:

    • Normalization: map values to numbers, the input can be continuous or discrete.

    • Discretization: map continuous values to discrete values.

    • Value mapping: map discrete values to discrete values.

    • Aggregation: summarize or collect groups of values, e.g. compute average.

  • The transformations in PMML do not cover the full set of preprocessing functions which may be needed to collect and prepare the data for mining, as there are too many variations of preprocessing expressions - Instead, the PMML transformations represent expressions that are created automatically by a mining system

PMML Conformance

  • PMML intends to enable application portability, sharing, and reuse of analytic models produced by a variety of tools.

  • Conformance must therefore be specified from both producer and consumer perspectives.

  • Applications need ways to specify what kinds of analytic models they can use, and modeling tools need ways to specify what kinds of analytic models they produce.

  • A PMML document is what gets produced by a modeling tool to specify a trained analytic model and is what an application uses to deploy that model.

  • Satisfying conformance rules ensures a model definition document is syntactically correct , specification consistent and that such a model will be applied in ways which are valid.

PMML Regression

  • A RegressionModel defines three types of regression models: linear, polynomial, and logistic regression. The modelType attribute indicates the type of regression used.

  • Linear and stepwise-polynomial regression are designed for numeric dependent variables having a continuous spectrum of values. These models should contain exactly one regression table. The attributes normalizationMethod and targetCategory are not used in that case.

  • Logistic regression is designed for categorical dependent variables. These models should contain exactly one regression table for each targetCategory. The normalizationMethod describes whether/how the prediction is converted into a probability.

  • p is the predicted value and is normally interpreted as the confidence or the probability of an individual belonging to the category of interest, as defined by targetCategory. There can be multiple regression equations. A confidence value for a category j can be computed by the softmax or simplemax functions

  • the <RegressionModel> element is the root element of an XML regression model, and contains the following attributes:

    • modelName: This is a unique identifier specifying the name of the regression model.

    • functionName: Can be regression or classification.

    • algorithmName: Can be any string describing the algorithm that was used while creating the model.

    • modelType: Specifies the type of a regression model. This information is used to select the appropriate mathematical formulas during the scoring phase. The supported regression algorithms are linearRegression, polynomialRegression, & logisticRegression.

    • targetFieldName: The name of the target field (also called response variable).

  • The <RegressionTable> element represents a table that lists the values of all predictors or independent variables. If the model is used to predict a numerical field, then there is only one RegressionTable and the attribute targetCategory may be missing. If the model is used to predict a categorical field, then there are two or more RegressionTables and each one must have the attribute targetCategory defined with a unique value.

  • The <NumericPredictor> subelement defines a numeric independent variable. The list of valid attributes comprises the name of the variable, the exponent to be used, and the coefficient by which the values of this variable must be multiplied. If the independent variable contains missing values, the mean attribute is used to replace the missing values with the mean value.

  • The <CategoricalPredictor> subelement defines a categorical independent variable. The list of attributes comprises the name of the variable, the value attribute, and the coefficient by which the values of this variable must be multiplied.

  • To do a regression analysis with categorical values, some means must be applied to enable calculations. If the specified value of an independent value occurs, the term variable_name(value) is replaced with 1. Thus the coefficient is multiplied by 1.

  • If the value does not occur, the term variable_name(value) is replaced with 0 so that the product coefficient × variable_name(value) yields 0. Consequently, the product is ignored in the ongoing analysis. If the input value is missing then variable_name(v) yields 0 for any 'v'.

  • E.g. a linear regression analysis PMML model:

<RegressionModel

functionName="regression"

modelName="Sample for linear regression"

modelType="linearRegression"

targetFieldName="number of claims">


<RegressionTable intercept="132.37">

<NumericPredictor name="age"

exponent="1" coefficient="7.1"/>

<NumericPredictor name="salary"

exponent="1" coefficient="0.01"/>

<CategoricalPredictor name="car location"

value="carpark" coefficient="41.1"/>

<CategoricalPredictor name="car location"

value="street" coefficient="325.03"/>

</RegressionTable>


</RegressionModel>



PMML Neural Network Models for Backpropagation

  • PMML can model each neuron to receive one or more input values, each coming via a network connection, and sends only one output value. All incoming connections for a certain neuron are contained in the corresponding <Neuron element>. Each connection Con stores the ID of a node it comes from and the weight. A bias weight coefficient may be stored as an attribute of <Neuron> element.

  • All neurons in the network are assumed to have the same (default) activation function, although each individual neuron may have its own activation and threshold that override the default.

  • NeuralInput defines how input fields are normalized so that the values can be processed in the neural network. For example, string values must be encoded as numeric values.

  • NeuralOutput defines how the output of the neural network must be interpreted.

  • NN-NEURON-ID is a string which uniquely identifies a neuron within a model (not within a document).

  • An input neuron represents the normalized value for an input field using the normalization elements <NormContinuous> and <NormDiscrete>. A numeric input field is usually mapped to a single input neuron while a categorical input field is usually mapped to a set of input neurons using some fan-out function.

  • Restrictions: A numeric input field or a pair of categorical input field together with an input value must not appear more than once in the input layer.

  • Neuron contains an identifier which must be unique in all layers, its attribute threshold has default value 0. If no activationFunction is given then the default activationFunction of the NeuralNetwork element applies.

  • The attribute 'bias' implicitly defines a connection to a bias unit where the unit's value is 1.0 and the weight is the value of 'bias'

  • Weighted connection between neural net nodes are represented by Con elements which are always part of a Neuron and define the connections coming into that parent element.

  • The neuron identified by 'from' may be part of any layer.

  • NN-NEURON-IDs of all nodes must be unique across the combined set of NeuralInput and Neuron nodes. The 'from' attributes of connections and NeuralOutputs refer to these identifiers.

  • In parallel to input neurons, there are output neurons which are connected to input fields via some normalization.

  • While the activation of an input neuron is defined by the value of the corresponding input field, the activation of an output neuron is computed by the activation function, and thus an output neuron is defined by a 'Neuron'.

  • In networks with supervised learning the computed activation of the output neurons is compared with the normalized values of the corresponding target fields

  • The difference between the neuron's activation and the normalized target field determines the prediction error.

  • For scoring the normalization for the target field is used to denormalize the predicted value in the output neuron. Therefore, each instance of 'Neuron' which represent an output neuron, is additionally connected to a normalized field. Note that the scoring procedure must apply the inverse of the normalization in order to map the neuron activation to a value in the original domain.

  • For neural value prediction with back propagation, the output layer contains a single neuron, this is denormalized giving the predicted value.

  • For neural classification with backpropagation, the output layers contains one or more neurons. The neuron with maximal activation determines the predicted class label. If there is no unique neuron with maximal activation then the predicted value is undefined.

  • backward connections from level N to level M with M <= N or connections between non-adjacent layers and variable values for activationFunction per Neuron require extensions

  • e.g.

<?xml version="1.0" ?>

<PMML version="2.0">

<Header copyright="DMG.org"/>

<DataDictionary numberOfFields="5">

<DataField name="gender" optype="categorical">

<Value value=" female"/>

<Value value=" male"/>

</DataField>

<DataField name="no of claims" optype="categorical">

<Value value=" 0"/>

<Value value=" 1"/>

<Value value=" 3"/>

<Value value=" &gt; 3"/>

<Value value=" 2"/>

</DataField>

<DataField name="domicile" optype="categorical">

<Value value="suburban"/>

<Value value=" urban"/>

<Value value=" rural"/>

</DataField>

<DataField name="age of car" optype="continuous"/>

<DataField name="amount of claims" optype="continuous"/>

</DataDictionary>

<NeuralNetwork modelName="Neural Insurance"

functionName="regression"

activationFunction="logistic">

<MiningSchema>

<MiningField name="gender"/>

<MiningField name="no of claims"/>

<MiningField name="domicile"/>

<MiningField name="age of car"/>

<MiningField name="amount of claims" usageType="predicted"/>

</MiningSchema>

<NeuralInputs>

<NeuralInput id="0">

<DerivedField>

<NormContinuous field="age of car">

<LinearNorm orig="0.01" norm="0"/>

<LinearNorm orig="3.07897" norm="0.5"/>

<LinearNorm orig="11.44" norm="1"/>

</NormContinuous>

</DerivedField>

</NeuralInput>

<NeuralInput id="1">

<DerivedField>

<NormDiscrete field="gender" value="male"/>

</DerivedField>

</NeuralInput>

<NeuralInput id="2">

<DerivedField>

<NormDiscrete field="no of claims" value="0"/>

</DerivedField>

</NeuralInput>

<NeuralInput id="3">

<DerivedField>

<NormDiscrete field="no of claims" value="1"/>

</DerivedField>

</NeuralInput>

<NeuralInput id="4">

<DerivedField>

<NormDiscrete field="no of claims" value="3"/>

</DerivedField>

</NeuralInput>

<NeuralInput id="5">

<DerivedField>

<NormDiscrete field="no of claims" value="3"/>

</DerivedField>

</NeuralInput>

<NeuralInput id="6">

<DerivedField>

<NormDiscrete field="no of claims" value="2"/>

</DerivedField>

</NeuralInput>

<NeuralInput id="7">

<DerivedField>

<NormDiscrete field="domicile" value="suburban"/>

</DerivedField>

</NeuralInput>

<NeuralInput id="8">

<DerivedField>

<NormDiscrete field="domicile" value="urban"/>

</DerivedField>

</NeuralInput>

<NeuralInput id="9">

<DerivedField>

<NormDiscrete field="domicile" value="rural"/>

</DerivedField>

</NeuralInput>

</NeuralInputs>

<NeuralLayer>

<Neuron id="10">

<Con from="0" weight="-2.08148"/>

<Con from="1" weight="3.69657"/>

<Con from="2" weight="-1.89986"/>

<Con from="3" weight="5.61779"/>

<Con from="4" weight="0.427558"/>

<Con from="5" weight="-1.25971"/>

<Con from="6" weight="-6.55549"/>

<Con from="7" weight="-4.62773"/>

<Con from="8" weight="1.97525"/>

<Con from="9" weight="-1.0962"/>

</Neuron>

<Neuron id="11">

<Con from="0" weight="-0.698997"/>

<Con from="1" weight="-3.54943"/>

<Con from="2" weight="-3.29632"/>

<Con from="3" weight="-1.20931"/>

<Con from="4" weight="1.00497"/>

<Con from="5" weight="0.033502"/>

<Con from="6" weight="1.12016"/>

<Con from="7" weight="0.523197"/>

<Con from="8" weight="-2.96135"/>

<Con from="9" weight="-0.398626"/>

</Neuron>

<Neuron id="12">

<Con from="0" weight="0.904057"/>

<Con from="1" weight="1.75084"/>

<Con from="2" weight="2.51658"/>

<Con from="3" weight="-0.151895"/>

<Con from="4" weight="-2.88008"/>

<Con from="5" weight="0.920063"/>

<Con from="6" weight="-3.30742"/>

<Con from="7" weight="-1.72251"/>

<Con from="8" weight="-1.13156"/>

<Con from="9" weight="-0.758563"/>

</Neuron>

</NeuralLayer>

<NeuralLayer>

<Neuron id="13">

<Con from="10" weight="0.76617"/>

<Con from="11" weight="-1.5065"/>

<Con from="12" weight="0.999797"/>

</Neuron>

</NeuralLayer>

<NeuralOutputs>

<NeuralOutput outputNeuron="13">

<DerivedField>

<NormContinuous field="amount of claims">

<LinearNorm orig="0" norm="0.1"/>

<LinearNorm orig="1291.68" norm="0.5"/>

<LinearNorm orig="5327.26" norm="0.9"/>

</NormContinuous>

</DerivedField>

</NeuralOutput>

</NeuralOutputs>

</NeuralNetwork>

</PMML>


Posted On Thursday, October 9, 2014 4:44 AM | Comments (0)

Wednesday, October 8, 2014 #

Standard Modern C++ in a Nutshell

Modern C++ Coding Style

This post is based upon the standard - not supported with VC compiler ! Try these techniques using GCC / LLVM compilers and QtCreator / CLion IDEs


Avoid C programming style idioms 

  • = rather than strcpy() for copying , == rather than strcmp() for comparing

  • use const , constexpr functions rather than #DEFINE, macros

  • Avoid void*, unions, and raw casts (use static_cast instead)

  • use std:string instead of char*

  • avoid pointer arithmetic

  • To obey C linkage conventions, a C++ function must be declared to have C linkage 

Avoid C# / Java programming style idioms 

  • Minimize the use of reference and pointer variables: use local and member variables

  • Use abstract classes as interfaces to class hierarchies; avoid “brittle base classes,” that is, base classes with data members.

  • Use scoped resource management (“Resource Acquisition Is Initialization”; RAII) 

  • Use constructors to establish class invariants (and throw an exception if it can’t)

  • Avoid “naked” new and delete; instead, use containers (e.g., vector, string, and map) and handle classes (e.g., lock and unique_ptr).


  • minimal run-time reflection: dynamic_cast and typeid
  • Namespaces are non-modular - headers can introduce name clashes - avoid using directives in header files, because it increases the chances of name clashes.

 C++11 new features 

        Constructor Controls =delete and =default

        type deduction - auto

        constant expression compile time evaluation - constexpr

        In-class member initializers

        Inheriting constructors

struct derived : base {

   using base::base; // instead of deriving multiple constructor sigs

};

        Lambda expressions

        Move semantics

        specify function may not throw exceptions - noexcept

        A proper name for the null pointer - nullptr (instead of NULL)

        The range-for statement

        Override controls: final and override

        Template Type aliases- binding arguments of another template

template<class T> struct Alloc {};

template<class T> using Vec = vector<T, Alloc<T>>;

// type-id is vector<T, Alloc<T>>

Vec<int> v; // Vec<int> is the same as vector<int, Alloc<int>>


        Typed and scoped enumerations: enum class

        Universal and uniform initialization 

        Variadic templates

        Hashed containers, such as unordered_map

        basic concurrency library components: thread, mutex, and lock

        asynchronous computation: future, promise, and async()

        regexp

        unique_ptr, shared_ptr

        tuple

        bind(), function

decltype(expr)  // reuse a type

Basics 

The stream idiom

// overloading IO stream ops:

        ostream& operator<<(ostream& os, const Entry& e)

        istream& operator>>(istream& is, Entry& e)

      cout << ,   cin >> // stdio streams

 getline() // helper function for making it easier to read from stdin

  If a pointer to function is given as the second argument to <<, the function pointed to is called.  cout<<pf means pf(cout). Such a function is called a manipulator

  • <sstream> istringstream - A stream that reads from a string 

  • c_str() returns a C-style pointer to a zero-terminated array of characters 

determine the memory footprint of a variable, or the size of an array

        sizeof(T)

extent <decltype( T )> ::value

// size of an array must be a constant expression

 Utilize initializer lists, auto, constexpr 

        use initializer lists {} instead of =, ()       - prevents narrowing conversions

        with auto, need to use =

        prefer constexpr to const       - compile time evaluation

 iterating over a container:

v.begin() and v.end() or begin(v) and end(v)

for (const auto& x : v)            // for each x in v

for (int& x : v)        // to modify an element in a range-for loop, the element variable should be a reference


Mechanisms: pass by ref, const functions, operator overloading, subscripting

        void doSomething(MyClass& c) {} // pass by ref

        const function:         double real() const { return re; } 

        operator overload:      complex& operator+=(complex z) { re+=z.re, im+=z.im; return *this; } // add to re and im

        double& operator[](int i) { return elem[i]; } // element access: subscripting

    

A common pattern: templatized RAII Handles as custom container wrappers

          template<typename T>

        class Handle {          // Parameterized Type

        private:

                T* elem;

...

           Handle(int s) :elem{new double[s]}, sz{s}  { ... } // constructor: acquire resources, initializer_list<T>

            ~Handle() { delete[] elem; }                       // destructor: release resources

       virtual double& operator[](int) = 0;     // pure virtual function

        void doSomething(vector<Item*>& v, int x) { //  do something to all items

                for (auto p : v)

                        p–>doSomething(x);

        }

Optimal techniques to pass arguments and retvals

  • pass & return references & from functions.

  • never return a pointer *. can return a smart pointer.

  • Return containers by value (relying on move for efficiency)

  • Each time a function is called, a new copy of its arguments is created. 

  • a pointer or a reference to a local non-static variable should never be returned.

  • non-primative arguments should be passed as const &

  • For template arguments, an rvalue reference is  used for “perfect forwarding”


  • Default arguments may be provided for trailing arguments only
  •  the recommended way to pass containers in and out of functions: pass Containers by reference, return them as objects by value (implicitly uses move)            

range-for over a handle

        // To support the range-for loop for a container handle, must define suitable begin() and end() functions:

        template<typename T>

        T* begin(Handle<T>& x)

        {

 functors, lambdas, variadic templates

        // functor

        bool operator()(const T& x) const { return x<val; } // call operator


bind - // forward call wrapper


        // lambda  - eg capture all by ref

        [&](const string& a){ return a<s; }


        // variadic template

        template<typename T, typename... Tail>

        void f(T head, Tail... tail)


ISO C++ standard char types 

  • character types: char (8), [signed | unsigned ] char, wchar_t (unicode), char16_t (UTF), char32_t. L'AB'

  • <cctype>:: isspace(), isalpha(), isdigit(), isalnum()

ISO C++ standard int types 

  • integer types: [signed | unsigned] short | int | long | long long

  • ::size_t x = sizeof(xxx) ; // implementation defined type

  • <limits>::numeric_limits // query arithmetic type properties

initialization gotchas – narrowing, default values, initialization lists

  • bool b2 {7};      // error: narrowing 

  • {} indicates default value (nullptr for pointers)

  • if (p) {  // equivalent to p!=nullptr

  • auto - use =, because {} is deduced to std::initializer_list<T>

  • The only really good case for an uninitialized variable is a large input buffer. 

  • only stack variables are default initialized !

 function pointers 

  • using PF = int(*)(double);  // pointer to function taking a double and returning an int

        void (*pf)(string)  = &DoSomething;  

        pf("blah");

        using F = void(*)(string);

  • beware: cannot dereference or increment void*

problems with passing arrays as arguments 

  • arrays cannot be copied, assigned, or passed by val

  • extern "C" int strlen(const char*);       // from <string.h> - the size of the array is lost to the called function. 

  • an argument of type T[] will be converted to a T* by val - preferable to pass a reference to some container

    

 Prefer references 

  • must be initialized from an object / primitive,

  • read only,

  • object like syntax,

  • used for passing by ref params / retvals

        int var = 0;

        int& rr {var};

        ++rr;               // var is incremented by 1

        int* pp = &rr;      // pp points to var

       move uses “ref ref”

        move(x) means static_cast<X&&>(x) where X& is the type of x.

Simple constructs:       

  • struct, union, enum, enum class
  •  enum class vs enum        

        enum class Color { red, blue, green };  auto col = Color::red;   // must be 

  • struct vs class - struct can be initialized using the {} notation - order is important , no need for constructor. all members public.

 function signature keywords

[[noreturn]] virtual inline auto f(const unsigned long int *const) –> void const noexcept;

  • avoid argument conversions for params: explicit // no implicit conversions 
  • 2 ways to specify an inline function:A) A member function defined within the class declaration is taken to be an inline member function. B)  Use inline keyword
  •  specify a static function - keyword static in declaration - is not repeated in the definition

eg

        template<class T, class U>

        auto product(const vector<T>& x, const vector<U>& y) –> decltype(x*y);

What makes a function signature unique          

  • unique function signature check ignores const in params

  • Function argument names are not part of the function type

  • an argument is unused in a function definition by not naming it

    

Error handling

 gracefully / ungracefully halting execution 

        if (something_wrong) exit(1);

        terminate() // does not invoke destructors. calls abort()

        std::set_terminate()

quick_exit() , at_quick_exit() 

 basic guarantee vs strong guarantee 

  • basic guarantee for all ops: invariants of all objects are maintained, and no resources are leaked

  • strong guarantee for key ops: either the operation succeeds, or it has no effect

  • nothrow guarantee for some operations


handling errors 

  • errno vs <stdexcept>

  • throw ex

  • throw; //rethrow

  • catch (std::exception& err) {

  • catch (...)


Catch common exceptions in main

        catch (...) {

                cerr <<

the standard exception hierarchy 

  • exception: logic_error, runtime_error,  bad_exception, bad_alloc, bad_cast, bad_typeid, 

  • logic_error: length_error, domain_error, invalid_argument, out_of_range, future_error

  • runtime_error: overflow_error, range_error, underflow_error, system_error, regex_error, ios_base::failure

 useful members of the exception class 

        exception::what(), current_exception(), rethrow_exception(), make_exception_ptr(), exception_ptr, nested_exception, terminate()


 catch exception& best practices for handling exceptions 

  • destructors do not throw 

  • can throw runtime_error in ctor

  • an exception is potentially copied several times up the stack before it is caught - don’t put huge amounts of data in exception body

  • innocent-looking operations (such as <, =, and sort()) might throw exceptions

  • error in a thread can crash a whole program -  add a catch-all handler to main()

  • The body of a function can be a try-block.

  • handle RAII is neater than try catch finally

   

assertions 

  compiletime static_assert vs runtime macro <cassert> assert

       

 handling exceptions in multithreaded code    

   

packaged_task does the following:  

catch(...) { myPromise.set_exception(current_exception());

     

Source Files and Programs

 the C++ compilation and linkage process 

  • A program is a collection of separately compiled units combined by a linker

  • file is unit of compilation

  • precompiler --> translation unit       

  • A program must contain exactly one function called main()

  • An entity must be defined exactly once in a program. It may be declared many times, but the types must agree exactly.

  • Outside a class body, an entity must be declared before it is used 

     static vs shared libraries 

 include semantics 

        #include <iostream>     // from standard include directory

        #include "myheader.h"   // from current directory

external linkage 

external linkage - when definition is not in same TU as declaration. 

extern // used for external linkage

        #ifdef __cplusplus

        extern "C" {}   // a linkage block

using, constexpr, static & const not accessible from other TUs - hence extern const


Defining macros

        #define PRINT(a,b) cout<<(a)<<(b)

        ## concatenate

        Writing #x " = " rather than #x << " = " is obscure “clever code”

        predefined macros: __FUNC__ , __FILE__ , __LINE__ 


best practices for reducing compile time 

  • Precompiled headers - modern C++ implementations provide precompiling of header files to minimize repeated compilation of the same header.

  • avoid global variables

  • a header should never contain: ordinary function definitions, fields, global variables, unnamed namepsaces, using directives

  • To ensure consistency (identical definition), place using aliases, consts, constexprs, and inlines in header files

  • dont abuse #include

  • minimize dependencies

  • compiler include guards

  • An unnamed namespace {} can be used to make names local to a compilation unit - internal linkage


Classes and OOP

       

A class provides 6 default methods 

by default a class provides 6 things

        class X {

             X();                     // default constructor

             X(const X&);             // copy constructor

             X(X&&);                  // move constructor

             X& operator=(const X&);  // copy assignment: clean up target and copy

             X& operator=(X&&);       // move assignment: clean up target and move

             ~X();                    // destructor: clean up


When to customise the default functions of a class:

  • If a class has a virtual function, it needs a virtual destructor
  •  If a class has a reference member, it probably needs copy operations

  •  If a class is a resource handle, it probably needs copy and move operations, constructor, a destructor, and non-default copy operations

  •  If a class has a pointer member, it probably needs a destructor and non-default copy operations

  •  Don't need a copy constructor just to copy an object - objects can by default be copied by assignment. default semantics is memberwise copy.

 =default and =delete 

  • if you implement custom class, for default functions that are default, specify = default;

  • prevent destruction of an object by declaring its destructor =delete (or private)


  • prevent slicing - Prohibit copying of the base class: delete the copy operations.


constructor call order:

  • be aware that constructor is called on every copy and move

  • delegating constructor - when one constructor calls another

  • Constructors execute member and base constructors in declaration order (not the order of initializers)

  • A constructor can initialize members and bases of its class, but not members or bases of its members or bases

  • Prevent conversion of a pointer to a derived to a pointer to a base: make the base class a protected base


Defining a class

constructor initialization lists

const functions and mutable fields

friend class / functions

defining an abstract base class 

        virtual ~Base() = 0;   // abstract base class definition (.cpp)


Nested Classes

  • A nested class has access to non-static members of its enclosing class, even to private members (just as a member function has), but has no notion of a current object of the enclosing class. 

  • A class does not have any special access rights to the members of its nested class

 different types of initialization: default, copy, memberwise

         MyClass o1 {};                     // default initialization


        MyClass o2 {   "aaa", 77 };          // memberwise initialization


        MyClass o3 { o2 };   // copy initialization

Operator Overloading

// stream out operator:      

ostream& operator<<(ostream&, const string&); 

 calling  std::cout << s; is the same as operator<<(std::cout,s);

// overload the + and += operators for a Complex number type ?   

        complex operator+(complex a, complex b) {

                return a += b; // access representation through +=.  arguments passed by value, so a+b does not modify its operands.


        inline complex& complex::operator+=(complex a) {

                re += a.re;

                im += a.im;

                return *this;

// define a conversion operator:

        MyClass::operator int() const { return i; }      // a conversion operator resembles a constructor


// declaring an indexer

        const MyClass& operator[] (const int&) const;


// declaring a functor:

        int operator()(int);

        pair<int,int> operator()(int,int);


// the -> operator

smart pointers overload operator –>, new 

increment / decrement   operators:

        Ptr& operator++();             // prefix

        Ptr operator++(int);           // postfix

        Ptr& operator––();             // prefix

        Ptr operator––(int);           // postfix


allocator / deallocator operators - implicitly static

        void* operator new(size_t);               // use for individual object

        void* operator new[](size_t);             // use for array

        void operator delete(void*, size_t);      // use for individual object

        void operator delete[](void*, size_t);    // use for array


// user defined literal operator:

        constexpr complex<double> operator"" i(long double d) ;

the order of construction / destruction in a class hierarchy

  • Objects are constructed from the base up and destroyed top-down from derived

  • destructors in a hierarchy need to be virtual

  • the constructor of every virtual base is invoked (implicitly or explicitly) from the constructor for the complete object 

  • destructors are simply invoked in reverse order of construction - a destructor for a virtual base is invoked exactly once.


keywords virtual, override, final:

  • override and final are compiler hints

  • keywords virtual, override, final should only appear in .h files

  • override - The override specifier comes last in a declaration.

  • Virtual functions - vtbl efficiency within 75%

  • final - can make every virtual member function of a class final - add final after the class name

        class Derived final : public Base {

         

Scope rules for deriving from a base class 

  • deriving from a base class can be declared private, protected, or public

  • If B is a private base, its public and protected members can be used only by member functions and friends of D. Only friends and members of D can convert a D* to a B*

  • If B is a protected base, its public and protected members can be used only by member functions and friends of D and by member functions and friends of classes derived from D. Only friends and members of D and friends and members of classes derived from D can convert a D* to a B*.

  • If B is a public base, its public members can be used by any function. In addition, its protected members can be used by members and friends of D and members and friends of classes derived from D. Any function can convert a D* to a B*.

       

 Best practices for abstract classes and virtual functions 

  • An abstract class should have a virtual destructor 

  • A class with a virtual function should have a virtual destructor;

  • An abstract class typically doesn’t need a constructor


Best practices for declaring  interfaces and data members

  • Prefer public members for interfaces;

  • Use protected members only carefully when really needed;  a protected interface should contain only functions, types, and constants.

  • Don’t declare data members protected;  Data members are better kept private & in the derived classes to match specific requirements.


Best practices deriving from a base class

  • Don’t call virtual functions during construction or destruction

  • Copy constructors of classes in a hierarchy should be used with care (if at all) to avoid slicing

  • A derived class can override new_expr() and/or clone() to return an object of its own type

  • covariant return rule - Return Type Relaxation applies only to return types that are pointers or references

  • a change in the size of a base class requires a recompilation of all derived classes

       

Almost Reflection

RTTI

  • <typeinfo> type_info typeid(x)

  • typ_info.name(),

  • size_t typ_info.hash_code() 

type traits to inspect code elements 

        <type_traits>

eg is_class<X> , is_integral<X>

 eg static_assert(std::is_floating_point<T>::value ,"FP type expected");

            Add_pointer<T>

            enable_if and conditional,

            declval<X>         


Casting

different types of casts:

  •         const_cast for getting write access to something declared const
  •         static_cast for reversing a well-defined implicit conversion
  •         reinterpret_cast for changing the meaning of bit patterns
  •         at least dynamic_cast is run-time checked - it supports polymorphic class hierarchies


limits of dynamic casting 

  • if (auto px = dynamic_cast<MyClass*>(py)) // dynamic_cast used an upcast - returns nullptrotherwise. 

  • dont use a ref: dynamic_cast<MyClass&> - could throw a bad_cast 

  • dynamic_cast cannot cast from a void*. For that, a static_cast is needed

  • crosscasting, dynamic dispatch. better to use visitor pattern

upcasting vs downcasting 

        class Manager : public Employee {}

        void g(Manager mm, Employee ee) {

                Employee* pe = &mm;               // OK: every Manager is an Employee

                Manager* pm = &ee;                // error: not every Employee is a Manager

                pm–>level = 2;                    // error: ee doesn't have a level

                pm = static_cast<Manager*>(pe);   // brute force: works


        void Manager::doSomething() const {

                Employee:: doSomething();      //       base method

                doSomething();                // error

Custom Allocators

explicitly calling new      

  // placement new - edge case where we specify memory address

        void C::push_back(const X& a){

            new(p) X{a};   //  copy construct an X with the value a in address p

        void C::pop_back() {

                p–>~X();      // destroy the X in address p

explicitly overloading allocators / deallocators 

        // explicit:

        new(&s) string{"xxx"};      // placement new: explicitly construct string

         s.~string();             // explicitly destroy string

         for enum class, define operator|() , operator&()

        allocator<T>

Templates

 Advantages of Templates 

  • faster & easier to inline - no casting , or double dispatch

  • code for a member function of a class template is only generated if that member is used

  • Use templates to express containers

  • excellent opportunities for inlining, pass constant values as arguments --> compile-time computation.

  • resembles dynamic programming with zero runtime cost


 Limitations of templates 

  • no way to specify generic constraints ... until concepts. so errors that relate to the use of template parameters cannot be detected until the template is used

  • A member template cannot be virtual

  • copy constructors, copy assignments, move constructors, and move assignments must be defined as non-template operators or the default versions will be generated.

  • A virtual function member cannot be a template member function

  • Source Code Organization: #include the .cpp definition of the templates in every relevant translation unit long compile times

  • caution is recommended when mixing object-oriented and generic techniques - can lead to massive code bloat for virtual functions


creating and using a template

        template<typename C>

        class MyClass { };


        MyClass<string> o;      // called a specialization          

Members of a template class are themselves templates parameterized by the parameters of their template class.

        template<typename C>

        MyClass<C>::MyClass() {}        // ctor

    

template compile-time polymorphism 

        template<typename T> 

        void sort(vector<T>&);          // declaration

        void f(vector<int>& vi, vector<string>& vs) {

                sort(vi);  // sort(vector<int>&);

                sort(vs);  // sort(vector<string>&);


  • Function Template Arguments - Use function templates to deduce class template argument types

        template<typename T, int max>

        struct MyClass {};

        template<typename T, int max>

        void f1(MyClass<T,int>& o);

        void f2(MyClass<string,128>& o){

            f1(o);      // compiler deduces type and non-type arguments from a call, 

        }


 function template overloads 

        sqrt(2);     // sqrt<int>(int)

        sqrt(2.0);   // sqrt(double)

        sqrt(z);     // sqrt<double>(complex<double>)


 SFINAE 

A template substitution failure is not an error. It simply causes the template to be ignored;    

use enable_if to conditionally remove functions from overload resolution

           

 Template Aliases 

        using IntVector = vector<int>;   

 Best practices for implementing Templates    

  • If a class template should be copyable, give it a non-template copy constructor and a non-template copy assignment - likewise for move

  • Avoid nested types in templates unless they genuinely rely on every template parameter

  • Define a type as a member of a template only if it depends on all the class template’s arguments

  • lifting - design for multiple type arguments

 Concepts Generic Constraints 

  • Estd namespace – template constraints

  • Ordered<X>, Equality_comparable<T>, Destructible<T>, Copy_assignable<T>, etc

  • implement a concept as a constexpr templated function with static_assert

  • parameterized --> constraint checks

Passing parameters to templates 

  • template Parameters can be template types, built in types, values, or other class templates!

  • literal types cannot be used as template value parameters;  function templates cannot be used as template params

  • can specify default types !

        template<typename Target =string, typename Source =string>

        Target to(Source arg)       // convert Source to Target

        { ... }

        auto x1 = to<string,double>(1.2);  // very explicit (and verbose)

        auto x2 = to<string>(1.2);         // Source is deduced to double

        auto x3 = to<>(1.2);               // Target is defaulted to string; Source is deduced to double

        auto x4 = to(1.2);                 // the <> is redundant

        

 partial specialization vs complete specialization

  • partial specialization   curbing code bloat - replicated code can cost megabytes of code space, so cut compile and link times dramatically

  • complete specialization - Specialize templates to optimize for important cases

template<> argument deduction         

        // template argument can be deduced from the function argument list, we need not specify it explicitly:

        template<>

        bool less(const char* a, const char* b)

    

techniques to reduce compilation time when implementing templates :

  • Partial specialization       

  • to declare a pointer to some templated class, the actual definition of a class is not needed:

        X* p;    // OK: no definition of X needed

  • one explicit instantiation for a specialization then use extern templates for its use in other TUs.

 The curiously recurring template pattern (CRTP)  

a class X derives from a class template instantiation using X itself as template argument

template<class T>

class Base {

// methods within Base can use template to access members of Derived

};

class Derived : public Base<Derived> {

use for static polymorphism (generic meta-programming )

Template Metaprogramming 

  • templates constitute a complete compile-time functional programming language

        constexpr

  • it is achieved via type functions, iterator traits


        is_polymorphic<T>

        Conditional<(sizeof(int)>4),X,Y>{}(7);   // make an X or a Y and call it

        Scoped<T>,On_heap<T>

    

        template<typename T>

        using Holder = typename Obj_holder<T>::type;

        is_pod<T>::value

        iterator_traits

        <type_traits>

        Enable_if<Is_class<T>(),T>* operator–>();   // select a member (for classes only)

        std::is_integral and std::is_floating_point,

variadic templates 

template<typename T, typename... Args>      // variadic template argument list: one or more arguments

void printf(const char* s, T value, Args... args)    // function argument list: two or more arguments

  • One of the major uses of variadic templates is forwarding from one function to another

  • pass-by-rvalue-reference of a deduced template argument type “forward the zero or more arguments from t.”

        template<typename F, typename... T>

        void call(F&& f, T&&... t){

                f(forward<T>(t)...);

        }

        

        auto t = make_tuple("Hello tuple", 43, 3.15);

        double d = get<2>(t);  

    

Know the Standard-Library

        <utility> operators & pairs

        <tuple>

        <type_traits>

        <typeindex> use a type_info as a key or hashcode

        <functional> function objects

        <memory> resource management pointers

        <scoped_allocator>

        <ratio> compile time rational arithmetic

        <chrono> time utilities

        <iterator>              begin, end

        <algorithm>

        <cstdlib> bsearch(), qsort()

        <exception> exception class

        <stdexcept> standard exceptions

        <cassert> assert macro

        <cerrno> C style error handling

        <system_error> system error support            error_code, error_category, system_error

        <string>                strlen(), strcpy(),

        <cctype> character classification        atof() , atoi()

        <cwctype> wide character classification

        <cstring> C-style string functions

        <cwchar> C-style wide char functions 

        <cstdlib> C-style alloc functions

        <cuchar> C-style multibyte chars

        <regex>

        <iosfwd> forward declerations of IO fascilities

        <iostream>

        <ios> iostream bases

        <streambuf> stream buffers

        <istream> input stream template

        <ostream> output stream template

        <iomanip> Manipulator

        <sstream> streams to/from strings

        <cctype> char classification functions

        <fstream> streams to/from files

        <cstdio> printf family of IO

        <cwchar> printf family of IO for wide chars

        <locale> cultures

        <clocale> cultures C-style

        <codecvt> code conversion facets

        <limits> numerical limits

        <climits> C-style integral limits 

        <cfloat> C-style float limits 

        <cstdint> standard integer type names

        <new> dynamic memory management

        <typeinfo> RTTI

        <exception>

        <initializer_list>

        <cstddef> C-style language support        sizeof(), size_t, ptrdiff_t, NULL

        <cstdarg> variable length function args 

        <csetjmp> C-style stack unwinding         setjmp , longjmp

        <cstdlib> program termination , C-style math functions             abs() , div() 

        <ctime> system clock

        <csignal> C-style signal handling

        <complex>

        <valarray>

        <numeric>

        <cmath>        

        <random>

        <atomic>

        <condition_variable>

        <future>

        <mutex>

        <thread>

        <cinttypes> type aliases for integrals

        <cstdbool> C bool, true, false

        <ccomplex>

        <cfenv> C floating point stuff

        <ctgmath>


STL Containers

STL features:

  • concepts: sequence vs associative containers; adapters, iterators, aglorithms, allocators 
  • container adapters - eg stack, queue, deque - double ended queue
  • Iterators are a type of pointer used to separate algorithms and containers

  • push_back does a copy via back_inserter

  • forward_list - SLL

  • multiset / multimap - values can occur multiple times

  • unordered_X

  • Xstream_iterator

  • How to implement a range check vector – not sure if this is good idea …

//override operator [] with at()

  • prefer standard algorithms over handwritten loops

  • accumulate - aggregator algo     

  • valarray // matrix slicing

  • unordered_map / set; multimap / set

  • bitset - array of bool

  • pair<T,U>  tuple<W,X,Y,Z>


functions common to several containers:

        less<T>

        copy(), find(),  sort(), merge(), cmp(), equiv(), swap() , binary_search(),splice() 

        size(), capacity()

        at() - range checks

        emplace // nice and terse

        hash<T> - functor

const iterators, reverse iterators 

        reverse iterators: rbegin, rend

        const iterators: cbegin, cend

Container and Algorithm requirements

  • To be an element type for a STL container, a type must provide copy or move operations;

  • arguments to STL algorithms are iterators, not containers
  • _if suffix is often used to indicate that an algorithm takes a predicate as an additional argument.

STL common algorithms:

        lower_bound(), upper_bound(), iter_swap()

        for_each(b,e,f)

        sequence predicates: all_of(b,e,f) , any_of(b,e,f) none_of(b,e,f)

        count(b,e,v) , count_if(b,e,v,f)

        isspace()

        find_if(b,e,f)

        equal(b,e,b2)

        pair(p1,p2) = mismatch(b,e,b2)

        search(b,e,b2,e2)        // find a subsequence

        transform(b,e,out,f)

        copy(b,e,out), move(b,e,out)

        copy_if(b,e,out,f)

        unique, unique_copy

        remove() and replace()

        reverse()

        rotate(), random_shuffle(), and partition() - seperates into 2 parts

        next_permutation(), prev_permutation() , is_permutation() - generate permutations of a sequence

        fill(), generate_n(), uninitialized_copy, uninitialized_fill assigning to and initializing elements of a sequence. (unitialized_ is for low level objects that are not initialized)

        swap(), swap_ranges(), iter_swap()

        sort(), stable_sort() - maintain order of equal elements, partial_sort()

        binary_search() - search sequence that is pre-sorted

        merge() - combine 2 pre-sorted sequences

        set_union, set_intersection, set_difference

        lexicographical_compare() - order words in dictionaries

        min & max

        Use for_each() and transform() only when there is no more-specific algorithm for a task

Iterating over a container       

  [b:e) end points to the one-beyond-the-last element of the sequence. 

        Never read from or write to *end. 

        the empty sequence has begin==end;

        while (b!=e) {       // use != rather than <

                // do something

                ++b;   // go to next element

        }

Iterator operations 

            input (++ , read istream), output (++, write ostream), forward (++ rw), bidirectional(++, --), random access

        iterator_traits - select among algorithms based on the type of an iterator

        ++p is likely to be more efficient than p++.


 3 insert iterators:

            insert_iterator - inserts before the element pointed to using insert().

            front_insert_iterator - inserts before the first element of a sequence using push_front().

            back_insert_iterator - inserts after the last element of the sequence using push_back().

 efficiently moving items from one container to another 

        copy(c1,make_move_iterator(back_inserter(c2)));    // move strings from c1 into c2

 getting an iterator from a reverse_iterator 

    Use base() to extract an iterator from a reverse_iterator

       

raw array vs array type 

  • T[N], array<T,N>

  • Use array where you need a sequence with a constexpr size

  • Prefer array over built-in arrays

 bitset<N> vs vector<bool>

  • bitset<N>, vector<bool>

  • Use bitset if you need N bits and N is not necessarily the number of bits in a built-in integer type

  • Avoid vector<bool>

 pair vs tuple

  • pair<T,U>, tuple<T...>

  • When using pair, consider make_pair() for type deduction

  • When using tuple, consider make_tuple() for type deduction

  • tie() can be used to extract elements from a tuple as out params


basic_string<C>, valarray<T>

New Techniques: Lambdas, smart pointers and move

Mitigating common memory management problems  

        mem management problems: leaks, premature deletion, double deletion

        int* p2 = p1;                 // potential trouble

        handles, RAII, move semantics eliminate problems


 function adapters: bind() , ref(), mem_fn(), function<T> 

  • <functional> - function adaptors - take a function as argument and return a functor that can be used to invoke it

  • bind(f,args) , mem_fn(f) , not(f) - currying, partial evaluation -.more easily expressed using lambdas. Uses   _1 std::placeholders

  • ref() - like bind(), but doesnt dereference early - use to pass references as arguments to threads because thread constructors are variadic templates.useful for callbacks, for passing operations as arguments, etc.

  • mem_fn() or a lambda can be used to convert the p–>f(a) calling convention into f(p,a)

  • function is specified with a specific return type and a specific argument type. Use function when you need a variable that can hold a variety of callable objects

        int f(double);

        function<int(double)> fct {f};  // initialize to f

        fct = [](double d) { return round(d); };     // assign lambda to fct

Passing values in / out of Lambdas

         lambda default is all by reference: [&]

        [=] by value (copy). recommended for passing a lambda to another thread

        mutable - capture values can change

        for_each - just use ranged for

        [&v...]   variadic params can be captured

        can capture the current object BY REFERENCE [this]

        the minimal lambda expression is []{}

        auto z4 = [=,y]()–>int { if (y) return 1; else return 2; }    // OK: explicit return type


Passing lambdas around         

std::function<R(AL)> where R is the lambda’s return type and AL is its argument list of types - function<void(char* b, char* e)>

can store a lambda in a variable of type auto - no two lambdas have the same type


3 types of smart pointers in C++11 

  • unique_ptr

unique_ptr<int> f(unique_ptr<int> p) {

             ++*p;

             return p;

        }


        void f2(const unique_ptr<int>& p) {

             ++*p;

        }


        unique_ptr<int> p {new int{7}};

        p=f(p);            // error: no copy constructor

        p=f(move(p));      // transfer ownership there and back

        f2(p);             // pass a reference


  • shared_ptr – create with make_shared() // a structure with two pointers: one to the object and one to the use count

        auto p = make_shared<MyStruct>(1,"Ankh Morpork",4.65);


  • weak_ptr - break loops in circular shared data structures

  • unique_ptr<X> sp {new X};  //  there is no make_unique ... yet

  • shared_ptr are copied ,unique_ptr are moved

  • you obviously still need to know your pointer prefix operator overloads *, & :prefix unary * means “dereferenced contents of” and prefix unary & means “address of.”

 Mixing containers and smart pointers 

vector<unique_ptr<Item>> v;

// rather than vector<Item*> ,vector<Item>

// because all Items implicitly destroyed


 move

  • STL containers & smart pointers leverage move operations, as should custom RAII handles:

template<class T> class Handle {

  • primitive types & their pointers are always copied, even when moved

  • move must leave the source object in a valid but unspecified state so its destructor can be called

  • a move cannot throw, whereas a copy might (because it may need to acquire a resource). 

  • a move is often more efficient than a copy. 

  • Because initializer_list elements are immutable, cannot apply a move constructor - use uninitialized_copy


copying vs moving

  •  the diff between lvalues and rvalues:  lvalue - named & unmovable VS rvalue - temporary value that is movable
  •  copy constructors by default do memberwise copy - not good for containers !
  • A copy constructor and a copy assignment for a class X are typically declared to take an argument of type const X&

  • Item a2 {a1};                // copy initialization

  • Item a3 = a2;                // copy assignment

  • Handle(const Handle& a);             // copy constructor

  • Handle& operator=(const Handle  a);  // copy assignment

  • Handle(Handle&& a);               // move constructor

  • Handle& operator=(Handle&& a);          // move assignment

  • std::move(x)                    // explicit

  • =delete;        supress default copy / move definitions

 move vs forward 

        A move() is simply a cast to an rvalue: static_cast<Remove_reference<T>&&>(t);

        forward() is for “perfect forwarding” of an argument from one function to another 

        <utility> swap() 

        <typeindex> comparing and hashing type_index (created from a type_info)


 allocate / deallocate functions 

        p=a.allocate(n);    // acquire space for n objects of type T

        a.deallocate(p,n);  // release space for n objects of type T pointed to by p

 best practices for working with smart pointers         

  • unique_ptr cannot be copied, but can be moved. When destroyed, its deleter is called to destroy the owned object.

  • Shared pointers in a multi-threaded environment can be expensive (because of the need to prevent data races on the use count).

  • A destructor for a shared object does not execute at a predictable time

  • Prefer resource handles with specific semantics to smart pointers

  • Prefer unique_ptr to shared_ptr.

  • Prefer ordinary scoped objects to objects on the heap owned by a unique_ptr

  • Minimize the use of weak_ptrs

  • a weak_ptr can be converted to a shared_ptr using the member function lock(). 

        if (auto q = p.lock()) {        

        }

        else {        

                p.reset();

        }


Basic Mathematics Support

 query numeric limits

        specializations of the numeric_limits template presented in <limits>

        numeric_limits<unsigned char>::max()

        <climits>        DBL_MAX and FLT_MAX C MACROS

valarray efficient matrix operations 

        valarray - slices and strides for matrices

        slice_array, gslice_array, mask_array, indirect_array

        valarray<int> v {

             {00,01,02,03},    // row 0

             {10,11,12,13},    // row 1

             {20,21,22,23}     // row 2

        };

        slice{0,4,1} describes the first row of v (row 0)

        slice{0,3,4} describes the first column (column 0)

        gslice is a “generalized slice” that contains (almost) the information from n slices

        accumulate() adds elements of a sequence using their + operator:

        inner_product(), partial_sum() and adjacent_difference()

         iota(b,e,n) assigns n+i to the ith element of [b:e).

 generate random numbers 

        <random> random_device, Rand_int , Rand_double

        auto gen = bind(normal_distribution<double>{15,4.0},default_random_engine{});

        for (int i=0; i<500; ++i) cout << gen();

Concurrency

different levels of concurrency and locking 

        atomic,  thread, condition_variable,  mutex , future + promise, packaged_task, and async()

 Creating a worker thread 

        thread t {F{x}};     //pass a functor constructor to a thread --> thread executes functor

        function arguments - const refs for RO, pointers for out params

Advanced Threading Constructs in C++11

  • advanced locking: defer_lock & explicit lock()

  • condition_variable      - ::wait(), ::notify_one()

  • promise<T>::set_value(), future<T>::get

  • packaged_task<Task_Type> ::get_future()

  • async::get

  • thread_local

creating a critical section 

        mutex m; // used to protect access to shared data

        void f() {

             unique_lock<mutex> lck {m}; // acquire the mutex m, automatically scoped

             // ... manipulate shared data ...

        }

 atomics 

        simplest memory order is sequentially consistent

        Atomics - Lock-free programming:  load and store

        enum memory_order {

             memory_order_relaxed,

             memory_order_consume,

             memory_order_acquire,

             memory_order_release,

             memory_order_acq_rel,

             memory_order_seq_cst

        };

        r1 = y.load(memory_order_relaxed);

        x.store(r1,memory_order_relaxed);

        [[carries_dependency]] //for transmitting memory order dependencies across function calls

        kill_dependency() //for stopping the propagation of such dependencies.

        atomic<T> - compare_exchange_weak(), compare_exchange_strong(), is_lock_free()

        2 possible values of an atomic_flag are called set and clear.

        atomic_thread_fence, atomic_signal_fence       // barriers

        volatile

 simple multi-threaded programming    


        thread::join, joinable, swap, detach      


        thread my_thread2 {my_task,ref(v)};       // OK: pass v by reference

        

        this_thread::sleep_until(tp)

        this_thread::sleep_for(d) 

        this_thread::sleep_for(milliseconds{10});

        this_thread::yield() 

    

        thread_local  // thread local storage

::hardware_concurrency() // reports the number of tasks that can simultaneously proceed with hardware support

        ::get_id() // get thread id


 Threading gotchas

  • A thread is a type-safe interface to a system thread. After construction, a thread starts executing its task as soon as the run-time system can acquire resources for it to run. Think of that as “immediately.”

  • Do not destroy a running thread; Use join() to wait for a thread to complete

  • don’t pass pointers to your local data to other threads

  • beware of by-reference context bindings in lambdas

  • a thread can be moved but not copied

  • thread constructors are variadic templates - to pass a reference to a thread constructor, must use a reference wrapper


Locking    

        mutex - lock(), unlock(), try_lock()

        recursive_mutex - can be repetedly aquired without blocking

        timed_mutex - try_lock_until(tp) , try_lock_for(d)

        recursive_timed_mutex

        lock_guard<T>   - guard for a mutex - simplest

        unique_lock<T>  - lock for a mutex - supports timed ops

        A mutex cannot be copied or moved

        lock_guard<mutex> g {mtx};      // destructor does the necessary unlock() on its argument.

        owns_lock() - check whether an acquisition succeeded

Ensure that a function is executed only once across multiple threads 

        once_flag

        call_once()

 Signalling between threads       

        condition_variable - ::wait(), ::wait_until() ::wait_for() , ::notify_one(), notify_all() - like a WaitHandle on a unique_lock<mutex>

        condition_variable_any - like a condition_variable but can use any lockable object 

        

The the promise-future paradigm for 'async callbacks'

        A future is a handle to a shared state. It is where a task can retrieve a result deposited by a promise

        The status of a future can be observed by calling wait_for() and wait_until(). the result can be retrieved via ::get()

        future<double> fd = async(square,2);

        double d = fd.get();


        shared_future<T> - can read result multiple times

        auto handle = async(task,args); 

        res = handle.get()                 // get the result

        

        future_error exception with the error condition broken_promise

        promise ::set_value, ::set_exception

    

        A packaged_task can be moved but not copied. ::get_future()

        packaged_task<int(int)> pt1 {DoSomething};  

        pt1(1); 

    

Don’t set_value() or set_exception() to a promise twice. Don’t get() twice from a future;

           Use async() to launch simple tasks

C++ is not C 

mechanisms of dealing with IO and strings 

The C way:

        <stdio> fopen(), fclose(), mode flag

        printf(), fprintf(), sprintf()

        stdin, stdout, stderr

        scanf()

        getc(), putc(), getchar(), putchar()

        <string.h>: strlen(), strcpy(), strcat(), strcmp(), strstr()

        atoi

The C++ way: streams

        <istream>, <ostream>

        iostream

        Forward declarations for stream types and stream objects are provided in <iosfwd>

        cin, cout, cerr, clog

        <fstream> ifstream, ofstream, fstream

        <sstream> istringstream, ostringstream, stringstream

            ios::ate // write at end

             use str() to read a result 

         state functions: good(), eof(), fail(), bad()

        getline(), get(c)

        put(), write() flush()

        noskipws

        cin >> c1 >> x >> c2 >> y >> c3;

        peek, seekg

        ostream& operator<<(ostream& os, const Named_val& nv) {

                return os << '{' << nv.name << ':' << nv.value << '}';

        basic_ios class manages the state of a stream: buffers, formatting, locales, Error handling

        streambuf

        istreambuf_iterator and ostreambuf_iterator

        An ostreambuf_iterator writes a stream of characters to an ostream_buffer

sto* (String to) functions 


 Time 

The C way:

        <ctime> clock_t, time_t, tm

The C++ way: duration

        std::chrono namespace FROM <chrono>

high_resolution_clock, duration_cast<T>

            duration, time_point

            call now() for one of 3 clocks: system_clock, steady_clock, high_resolution_clock

            duration_cast<milliseconds>(d).count()

            ratio<1>

            duration<si45, micro>       // SI units from <ratio> constructed from ratio<int,int>

Some low level C features may still be handy in a C++ program 

  • memory.h: memcpy(), memove(), memcmp(), memset(), calloc(), malloc(), realloc(), free()

  • cmp() , qsort() ,  bsort() 
  • safe fast low level C style copy: 

        if (is_pod<T>::value) memcpy( ...

  •  initialize a char array:

        char* p = L“…”;

        "" == const char* p = '\0';

        prefxes: L for wide chars, R for raw strings


Some best practice Takeaways:

  • using namespace std; // place in cpp files after includes to make your code more succinct
  • prefer {}-style initializers and using for type aliases
  • Use constructor/destructor pairs to simplify resource management (RAII).

  • Use containers and algorithms rather than built-in arrays and ad hoc code 

  • Prefer standard-library facilities to locally developed code 

  • Use exceptions, rather than error codes, to report errors that cannot be handled locally 

  • Use move semantics to avoid copying large objects 

  • Avoid “naked” new and delete. Use unique_ptr / shared_ptr

  • Use templates to maintain static type safety (eliminate casts) and avoid unnecessary use of class hierarchies 

  • Header files - semi-independent code fragments minimize compilation times

  • Pointers - a fixed-size handle referring to a variable amount of data “elsewhere”

  •  use namespaces for scope:  namespace {}

  • establish class invariants in constructors (throw exceptions  fail fast)

  • static_assert - only works on constant expressions (useful in generics)


Posted On Wednesday, October 8, 2014 7:53 AM | Comments (0)

Thursday, May 30, 2013 #

Putting NET Framework behind me

For the past decade, Ive focused on the MS stack – but the cheese is moving, and its time to look for more cheese!

Henceforth I will focus on C++, JavaScript & Algorithms.

 

So what happened? NET was well marketed & easy to learn – a massive amount of blogs & reading material ensured the development of communities and pools of skilled employees to draw upon. The language of choice for NET, C#, is a highly efficient programming language, as long as you don't go outside the box.

 

 


The situation for NET devs is dire:

It is foolish to bet your mortgage on the long term viability of any development platform. What goes up must come down, and the software industry is prone to rapid changes. Do you seriously expect todays skills to be relevant in 10 years?

 

  1. NET may be highly productive, but it is relatively idiot proof (compared to C++, JavaScript) - so attracted a fair few mediocre devs ! Stop patting yourself on the back because you know MVVM.
  2. the pit of success is in fact a pit - a career race to the bottom - NET was the apex predator, but the pool it swims in is drying up. C# devs are pumped out of courses at an alarming rate, while the non-viability of post-Win7 is making IT departments evaluate non-NET friendly platforms. This is supply & demand - there will be glut of cheap NET devs in the near future, all scrambling for the same cookie-cutter jobs. When the avalanche starts, it will accelerate rapidly.
  3. There has been nothing major new in the platform over the last 3 years (async is too small to count) - what have NET devs learnt in this time ? Compare this to the revolution of NET 3.0 (WPF / WCF / WF v1), NET 3.51 (LINQ, EF), & NET 4.0 (TPL).

The fact is, NET just didn't have a tangible ROI for MS (it wasn't a product), but it helped with portability lockin for application servers & dev stations – & that can only work if a critical mass of win OS deployments remains the status quo.

A Productive Framework … for Windows

 

Only 8% of .NET 4.5 classes can be used in Win8 non-desktop apps - http://blogs.msdn.com/b/dotnet/archive/2012/04/17/net-for-metro-style-apps.aspx 

 

Once people figure out they don't need Windows, NET has no where to run on - lets look at the options:

  1. Non-MS platforms via MonoTouch / MonoDroid
            •    costs: https://store.xamarin.com/  $1000. In comparison: Eclipse is free. XCode is free.
            •    will always be a gen or 2 behind & not be able to use the many 3rd party libs designed for IOS / Android platforms
  2. WP8  tablet mode – low market penetration, & only 8% of NET can run here.
  3. Win8 (non legacy tablet mode) – supports C#, but not NET – need to port to WinRT, recompile for ARM, sideloading for LOB apps is horrendous – why bother for low market penetration ?
  4. Azure
                    Azure PAAS – low market penetration
            Azure IAAS – not restricted to Win7 VMs, so makes no diff
  5. Win2012 Server – low market penetration

Conclusion: As MS is not selling Win7 anymore, and corporations wont upgrade to Win8 even for desktop mode ? NET is heading to legacy land.

 

 

Having said that, I've pretty much decided to put NET behind me.

 

A Graveyard of APIs

I consider the past decade a wasted effort of personal esoteric research in MS APIs, for the following reasons:

  1. DOA APIs: Oslo, Software Factories, MBF (project green), Whitehorse (ACD), WPF, Silverlight, Sketchflow, XNA, Spec#, Accelerator (.NET GPGPU),IronRuby, RIA Services, English Query, Solver Foundation, DryadLINQ, XSG (Farenheit), MLNet
  2. Quietly forgotten APIs: SQL Server Data mining + DMX, Robot Toolkit
  3. Coma of limited serious adoption: HPC, WF, F#, Azure, LightSwitch, EF, MDX, WinRT , DirectX (in Israel anyway), StreamInsight, HDInsight, Gadgeteer, NETArduino
  4. Terminal: ASP.NET, IIS, XAML - not needed anymore in a HTML5/JS world – we have NodeJS, AngularJS etc      
  5. Solid but bloated: XAML, WCF (SOAP has been superseded by REST, then by ProtoBuff), SQL (superseded by NO-SQL), Visual Studio (API bloat), TFS (ALM bloat)

Whats left that's innovative in NET: LINQ, TPL, RX

Developers, Developers, Developers …

We are a long way from developers, developers, developers - MS is refocusing on becoming a devices [that the market has rejected] and services [which boils down to VM re-hosting]

Services

Azure is not the solution for a NET dev - problems:

  1. do people really need the cloud - we got on fine without it. Was it just to counter the Linux server threat ?
  2. there have been some serious downtimes
  3. PAAS is nicely productive, but failed because people don't want lockin
  4. demand is just for IAAS - so is MS just another VM rehosting provider ?
  5. would Orleans replace NET ?

Devices

Win8 fail points:

  1. Metro is ugly & will quickly become dated
  2. businesses will not move to it - it wont support their legacy info systems & side loading is non-viable
  3. stiff competition - Win8 faces a market lag behind cool, cheap & multiple players - insurmountable

Win8 == death of .NET - there are 2 grim scenarios:
       

  1. success scenario (unlikely) - WinRT replaces alot of NET, XAML is just a verbose token effort when you have JS, C# is just a WinRT component ‘scripting’ language.
           
  2. fail scenario - because no-one is buying its target platform, NET is not developed beyond v5.x

Win8 does have a dirty trick up its sleeve though - the UEFI monopoly on laptops
        Ubuntu is idiot proof, but has zero marketing –>and thus zero market awareness.
        computer stores & OEMs just do not stock desktops / laptops with Linux pre-loaded OS's
        UEFI stops Wubi - the UEFI secureboot story is currently a bit of a trainwreck: http://www.linuxbsdos.com/2012/11/05/dual-boot-windows-8-and-ubuntu-12-10-on-uefi-hardware/

How MS could lose enterprise computing


        At this point I don't see Google / Linux attacking MS on their home turf - enterprise computing.
        The current IT department lock-in stems from skills & infrastructure built around MS Office & the NET framework. 
       

 

EEE (Embrace, Extend, Extinguish) will be much harder this time

Now that JavaScript has won, there is no great need for IDE bells & whistles.

MS has recognized this, & is scrambling to find some kind of lockin inducing strategy for applications requiring visual studio support (and thus windows):

  1. Azure PAAS & AD security
  2. TypeScript (get C# into your JS implementation)
  3. EdgeJS (get C# into your NodeJS implementation
  4. HDInsight (get C# into your Hadoop implementation).

Viva LibreOffice

Office cannot be relied upon to always be a cash cow with demand that requires Windows.


        Canonical has done an amazing job with Ubuntu & LibreOffice - It is a viable competing platform & is just a saner economic choice than Win8 + Office 13 licensing in the workplace.
        However, Ubuntu has zero market mindshare - people are just unaware of its viability.

        Likewise, Google is not exactly ratcheting up the marketing engine for ChromeBook & Google Docs in the enterprise.


        If Canonical solves its UEFI issues, and both Canonical & Google start marketing their competitive platforms, then MS could be in serious trouble: Instead of guarding their enterprise hen-house (which they have deemed 'legacy'), MS is focusing on an uphill battle in the consumer market.

What could make me change my mind (but is improbable)

  1. MS kills Metro UX –and shoots the Patridge family for suggesting it!
           
  2. WebGL support in IE 11 + JS support for DX
           
  3. A NET migration story for LOB apps to run in Win9
           
  4. Finish open sourcing it - NET platform independence - the fact is Android has usurped windows everywhere but the office
           
  5. A whole new set of functionality & abstraction in NET vnext – surprise us, take us to another level.

Side note: 2 years as an MVP

2 years ago , I was a lot less jaded – I enjoyed the MS dev ecosystem, and scoffed at the term “year of Linux of the Desktop” – (funny how that turned out with Android running on a Linux kernel).

In 2011, I applied for an MVP award in the area of Technical Computing (which is my area of expertise). During this process, the Technical Computing group was dissolved and scattered to other groups - I found myself awarded an MVP … in System Center, which I knew nothing about !

In 2012 I applied again – this time I received an award in Technical Computing, but found myself in the Azure group !

 

I enjoyed the perks of being an MVP, but as I am heading in different directions, needless to say I wont be re-applying this year !

The fact is I have 3 degrees (BSc Comp Sci, Grad Dip Biotech, MSc Bioinformatics), and I don’t feel the need to promote a specific vendor under the auspices of an additional certificate of technical adeptness. So thanks MS, & good journeys on your road.

 

Well that’s my 2 cents

As the human torch says, flame on !

Posted On Thursday, May 30, 2013 8:52 AM | Comments (14)

Monday, January 28, 2013 #

C++ Unit Testing with GoogleTest

Unit testing is critical for quality code – they help you:

  • find problems early
  • facilitate change by avoiding breakage of other functionality
  • simplify integration via a bottom up approach
  • document the code
  • maintain good design – testable code is good code: single intent, clear retval etc

Google has created a unit testing framework for C++ :

http://code.google.com/p/googletest/

 

I downloaded Google Test from http://code.google.com/p/googletest/downloads/list and built the solution under the msvc folder (Im using Visual C++ today). I see that there is a lib file created here called gtest-1.6.0\msvc\gtest\Debug\gtestd.lib

I then created a new VC++ Win32 Console App and set the following project properties:

VC++ Directories > Include Directories – added path to ..\ gtest-1.6.0\include

VC++ Directories > Library Directories – added path to ..\ gtest-1.6.0\msvc\gtest\Debug

Linker > Input > Additional Dependencies  - added gtestd.lib

All swell ?

I thought so, until I compiled & got the dreaded LNK2005: http://msdn.microsoft.com/en-us/library/72zdcz6f(v=vs.80).aspx

WTF – linker errors ?

To quote Cousin Eddie from National Lampoon’s Vacation:

'Everytime Catherine would turn in the microwave I'd piss my pants and forget my name' - C++ often makes me feel like an idiot !

 

Thank God for Pavel http://blogs.microsoft.co.il/blogs/pavely/ , who pointed out to me that I need to change the C runtime library from DLL multithreaded debug to multithreaded debug:

clip_image002[5]

 

I could now build.

 

I added an include to access the Google Test macros:

#include "gtest/gtest.h"

 

I then created a canonical testable function:

int Factorial(int x, int result = 1) {

if (x == 1) return result;

else return Factorial(x - 1, x * result);

}

 

I used the TEST macro to construct a named test – it leveraged the EXPECT_EQ & EXPECT_GT macros to test for equality and greater than respectably.

TEST(FactorialTest, Negative) {

        EXPECT_EQ(1, Factorial(-1));

        EXPECT_GT(Factorial(-10), 0);

}

 

in my main function, I initialized google test & used RUN_ALL_TESTS macro to … run all tests.

int _tmain(int argc, _TCHAR* argv[])

{

        testing::InitGoogleTest(&argc,argv);

        RUN_ALL_TESTS();

        int x;  

        std::cin >> x;

        return 0;

}

 

I debugged my code - It breaks into the test:

clip_image002

And I get the following test results displayed:

clip_image004

So I am up & running with C++ Google Test !

 

Further things to try:

All fun & games !

Posted On Monday, January 28, 2013 12:24 PM | Comments (0)

Saturday, January 12, 2013 #

3D Programming Concepts

2 years ago I built & presented a course on XNA 4: http://www.e4d.co.il/Events/ExpertDays2011/Courses/Details/29

 

XNA may be dead & buried, but the 3D programming concepts are tech-stack-agnostic – They apply equally well to DirectX. I’ve extracted this subsection into a set of slides:

 

enjoy !

Posted On Saturday, January 12, 2013 4:44 AM | Comments (1)

Thursday, January 10, 2013 #

I didnt know how to do that in C++ !

I've been reading through the C++ Cookbook (an oldie but a goodie – I assume that 99% of C++ out there is not modern C++, and modern C++ does not mean you don’t need to be able to grok templates, pointers etc – you may need to port something, or use a 3rd party lib)

Anyway, reading through stream manipulators, from my understanding this is how you pass a generic 'delegate' into a constructor & invoke it:

template<typename T, typename C>

class ManipInfra {

public:   

ManipInfra (basic_ostream<C>&

(*pFun) (basic_ostream<C>&, T), T val) // pass in

: manipFun_(pFun) // init list – init func pointer var

, val_(val) {}

void operator( )(basic_ostream<C>& os) const

{

    manipFun_(os, val_); // Invoke the generic function pointer with the stream and value

}

private:

T val_;

basic_ostream<C>& (*manipFun_) (basic_ostream<C>&, T); // a function pointer – a delegate !

};

Note: C++ 11 has function<T> which provides the same functionality – courtesy of my esteemed colleague Tomer Shamam http://blogs.microsoft.co.il/blogs/tomershamam/ :

 

class YourClass

{

public:

YourClass(std:function<return_type (param_type param)> func)
{             

    ...

    func(param);
}

};

YourClass y([](param_type param){ ...});

Posted On Thursday, January 10, 2013 6:31 AM | Comments (3)

Sunday, December 30, 2012 #

2012: Study Plan Year in Review

 

Over the past year I went into study overdrive: I learned A LOT about C++, Maths, Algorithms, Finance & JavaScript. It was a great year in terms of knowledge acquisition.

pro amore scientiam !

C++

C / C++ is the language for performant algo dev. It also has a higher barrier of entry than C#. While C# is elegant, it is targeted towards LOB apps and it is very easy to pick up à a proliferation of decent NET code monkeys is a career race to the bottom. It is a wise time to move back to C++. Note: I am about to revise this all again !

· C# to C++ guide – a good refresher

· Revise Kinnect API

· WMF from Pavels course - I worked with this API for 2 months this year – non-trivial !

· ConcRT & PPL – I went through everything on msdn + Alon's course materials. Unlike TPL you can control priority. The agent paradigm is quite similar to Axum, TPL DataFlow.

· AMP – see my post here: http://geekswithblogs.net/JoshReuben/archive/2011/12/04/c-amp.aspx

· Book: C++ AMP http://amzn.to/WWxC2J – a great book with much practical advice.

clip_image001

· Win32, strings, pragmas, intrinsics, lbs vs dlls, project settings, etc etc etc

· COM, ATL – be prepared for a lot of dead code out there !

· STL / TR1 – I wrote a set of exercises for a course on this

· Book: Windows via C/C++ http://amzn.to/WWxO1S - essentially thread management – I never realized how insecure Windows was until I read this !

clip_image002

· WRL & C++/CX - just in case pigs fly !

· C++ 11 – some amazing changes to the standard.

3D

3D is an interesting & non-trivial problem domain. I hope to do further work in this area.

· SIGGRAPH – http://www.siggraph.org/asia2011/hong-kong I attended this conference 1 year ago – an eye opening trip into the future! I participated in intense courses on OpenGL & OpenCL.

· clip_image003

· Book: Mathematics for Computer Graphics http://amzn.to/WWxwZ2 - I used this to build an XNA course (before it died)

clip_image004

· Book: DirectX http://amzn.to/WWxj81 - see my summary here: http://geekswithblogs.net/JoshReuben/archive/2012/03/14/d3d-11-programming-in-a-nutshell.aspx

clip_image005

· Direct3D tooling – I'll blog on this sooner or later

· RasterTek DirectX tutorials – http://www.rastertek.com/tutindex.html - the only way to learn DX !

· Book: Unity3D http://amzn.to/WWxbph - I built the island, shot coconuts at the hut door, and started a particle fire !

clip_image006

Trading Systems Infrastructure

· I did a fair few consults for trading firms – they have unique high performant scalable infrastructure requirements – leave your NET hat at the door ! see my blog post here: http://geekswithblogs.net/JoshReuben/archive/2012/03/26/low-latency-high-performant-financial-app-infrastructures.aspx

· Onyx FIX - http://www.onixs.biz/ – a low latency API for messaging with the FIX (financial information exchange) protocol. Critical for trading systems.

· LMAX – I blogged about this trading API here: http://geekswithblogs.net/JoshReuben/archive/2011/07/08/lmax-.net-api-walkthrough.aspx

· Book: Big Data Glossary http://amzn.to/UpRaJs

clip_image007

· NOSQL – did an investigative comparison

· LMAX Disruptor – amazing ring buffer architectural paradigm: http://lmax-exchange.github.com/disruptor/

· Redis - http://redis.io/ - an incredibly fast distributed in memory cache

Maths, Computation & Cognition

Going through life, I feel it is a core personal goal to understand as much as possible about the nature of reality.

· Book: Physics http://amzn.to/WWA610 - a great coffee table book detailing the greatest 500 discoveries in physics

clip_image008

· Schuams Computer Architecture http://amzn.to/UpNXte - an in depth drill down into registers, microcode & memory hierarchies. Very worthwhile read. Hadn't looked at this since my first degree 20 years ago !

clip_image009

· Book: Schaums Vector Analysis http://amzn.to/UpO9IV - nice refresher on linear algebra + some interesting stuff on Stokes Theorem & intro to Tensors

clip_image010

· Book: Schaums Mathematica http://amzn.to/UpPAHm - while this has very little penetration in the Israeli market, it is an amazingly powerful symbolic mathematical programming language environment. I will delve deeper. See my blogpost here: http://geekswithblogs.net/JoshReuben/archive/2012/07/04/mathematica-programming-languagendashan-introduction.aspx

clip_image011

· Book: Excel Scientific Computing http://amzn.to/UpPGyG - everything you need to know about programming excel

clip_image012

· Book: Language instinct - http://amzn.to/UpPPCm - amazing coverage on how language works – will serve me well if I ever head into NLP

clip_image013

· Numerical analysis videos - http://numericalmethods.eng.usf.edu/videos/ - an awesome resource.

· Book: Short Intro to Reality - http://amzn.to/UpQ5Bf - philosophical questions regarding the simulated universe hypothesis – stop thinking like an ant, & read this.

clip_image014

· Book: Short Intro to Sociology - http://amzn.to/UpQbsO - a bit wishy washy, but a good analysis of how & why aspects of cultures are socially constructed

clip_image015

· Book: short intro to Game Theory http://amzn.to/UpQQub - will serve me well if I ever head into constructing a probabilistic reasoning system for decision support.

clip_image016

· Book: Short intro to Nothing http://amzn.to/UpQP9s - Is the Higgs Field the new ether ?

clip_image017

· Book: History of Modern Computing http://amzn.to/UpQV0V - gives you perspective into how fast paradigms can shift

clip_image018

· Book: The Quest for AI http://amzn.to/UpRIPi - a good refresher after reading Norvig & Russell

clip_image019

· Book: C# numerical computing http://amzn.to/UpT9xm - a nice overview via a toy language

clip_image020

· Book: millennium problems http://amzn.to/UpTccv - it is quite amazing to grasp the current limits of our understanding

clip_image021

· Extreme Optimization Library – the strongest C# maths library - http://www.extremeoptimization.com/

· Book: C# ANNs + Encog http://amzn.to/UpTikt - see my blogpost here: http://geekswithblogs.net/JoshReuben/archive/2011/02/04/c-neural-networks-with-encog.aspx

clip_image022

Finance & Economics

The world is rapidly changing – we don’t live in a bubble – its worthwhile to understand the patterns in the undercurrents.

· Book: How the west was lost http://amzn.to/UpTro1

clip_image023

· Book: Cartoon Guide to Macroeconomics http://amzn.to/UpTDUj

clip_image024

· Book: After America http://amzn.to/UpTxMd

clip_image025

· Book: Crash Course http://amzn.to/UpTQql

clip_image026

· Peak Oil http://amzn.to/UpU3K6

clip_image027

JavaScript

I've got a fair few years experience as a web dev – its important to keep abreast of the current Cambrian explosion of JavaScript platforms. JavasScript is pervasive.

· WebGL- a GPU accelerated javascript library for 3D that loads shaders via the canvas 3D context – see my blogpost here: http://geekswithblogs.net/JoshReuben/archive/2012/07/26/an-introduction-to-webgl.aspx

· Book: Javascript pocket guide http://amzn.to/UpUp3v - a good refresher

clip_image028

· JS WebWorkers – true parallelization on the client

· Book: HTML 5 & CSS 3 http://amzn.to/UpUO67 - good overview of whats new

clip_image029

· KnockoutJS – a descent MVVM framework with binding support

· EmberJS – the strongest client side platform – feature rich

· Book: Javascript Design Patterns – good to revise 2 things in one ! http://addyosmani.com/resources/essentialjsdesignpatterns/book/

· Javascript for C# devs http://blog.boyet.com/blog/javascriptlessons/ - a great blog series

· Book: JQuery Pocket Guide http://amzn.to/UpUVP8 - another good refresher

clip_image030

· QUnit – client side unit testing

· JQueryUI

· HTML5 Boilerplate

· Book: ImpactJS HTML5 game programming http://amzn.to/UpV9Wc

clip_image031

· SocketIO , Pusher – WebSockets APIs

· REST API design – consulted on this for a trading client.

· FireBug – amazing debugging capabilities – a must know.

· WebStorm – a great IDE for webdev without the VS bloat

· JSLint / JSHint - code quality tools

· NodeJS – beginners guide http://amzn.to/UpViZR

clip_image032

· NodeJS baby steps & toddler steps - http://elegantcode.com/category/node-js/ - a great blog series

· JS RiverTrail – JavaScript GPGPU – see my blogpost here: http://geekswithblogs.net/JoshReuben/archive/2012/11/29/rivertrail---javascript-gppgu-data-parallelism.aspx

Conclusion: Groundwork laid for 2013

It was definitely a great year in terms of knowledge acquisition.

It is true that I need to consolidate – that’s exactly what I am doing now !

Now, this may all seem freaky to your standard LOB dev tradesman drone, who micro-specializes in XAML & WCF.

I have indeed absorbed a lot of disparate information, and I definitely need to revise & get practical hands-on; however once something is conceptualized, it is yours to rapidly refresh on demand forever. Besides, I have made detailed summaries on various topics.

The whole is greater than the sum of the parts – a worthwhile goal in life is to be a renaissance man: http://en.wikipedia.org/wiki/Polymath

I am not just a jack-of-all-trades – I can quickly drill down & become an expert in many topics.

Maths & C++ have opened up many new worlds for me – which I can now dive into in 2013.

Anyone who thinks I have spread myself too thin is just under-estimating me – don’t tell me what I cannot do !

Posted On Sunday, December 30, 2012 12:24 AM | Comments (1)

Tuesday, December 25, 2012 #

Big Data–Where to Start

I recently read the Big Data Glossary - http://www.amazon.com/Big-Data-Glossary-Pete-Warden/dp/1449314597

 

big_data_glossary

Big Data is essentially a MapReduce stack for scatter-gather-aggregate scaleout of compute jobs.

The core tools are:

  • Apache Hadoop – a MapReduce scale-out infrastructure
  • Hive – SQL language for Hadoop
  • Pig – procedural language for Hadoop
  • Cascading – orchestration of jobs on Hadoop
  • Datameer – BI on Hadoop
  • Mahout – distributed machine learning library on Hadoop
  • ZooKeeper – work coordinator / monitor

On top of these are various tools & extensions, as well as ports (e.g. HDInsight )

You also need to be aware of elastic cloud platforms to run on, and the various NoSQL DBs tend to be leveraged in this space as well.

Additionally, MapReduce is just an infrastructure pattern for distributed processing of algorithms – you will not get much usage out of it without knowledge of the appropriate algorithms to leverage on the nodes in your compute grid – the whole point of Big Data.

Posted On Tuesday, December 25, 2012 11:39 AM | Comments (0)

Sunday, December 9, 2012 #

A Taxonomy of Numerical Methods v1

Numerical Analysis – When, What, (but not how)

Once you understand the Math & know C++, Numerical Methods are basically blocks of iterative & conditional math code. I found the real trick was seeing the forest for the trees – knowing which method to use for which situation. Its pretty easy to get lost in the details – so I’ve tried to organize these methods in a way that I can quickly look this up.

I’ve included links to detailed explanations and to C++ code examples.

I’ve tried to classify Numerical methods in the following broad categories:

  • Solving Systems of Linear Equations
  • Solving Non-Linear Equations Iteratively
  • Interpolation
  • Curve Fitting
  • Optimization
  • Numerical Differentiation & Integration
  • Solving ODEs
  • Boundary Problems
  • Solving EigenValue problems

Enjoy – I did !

Solving Systems of Linear Equations

Overview

Solve sets of algebraic equations with x unknowns

The set is commonly in matrix form

Gauss-Jordan Elimination

http://en.wikipedia.org/wiki/Gauss%E2%80%93Jordan_elimination

C++: http://www.codekeep.net/snippets/623f1923-e03c-4636-8c92-c9dc7aa0d3c0.aspx

Produces solution of the equations & the coefficient matrix

Efficient, stable

2 steps:

· Forward Elimination – matrix decomposition: reduce set to triangular form (0s below the diagonal) or row echelon form. If degenerate, then there is no solution

· Backward Elimination –write the original matrix as the product of ints inverse matrix & its reduced row-echelon matrix à reduce set to row canonical form & use back-substitution to find the solution to the set

Elementary ops for matrix decomposition:

· Row multiplication

· Row switching

· Add multiples of rows to other rows

Use pivoting to ensure rows are ordered for achieving triangular form

LU Decomposition

http://en.wikipedia.org/wiki/LU_decomposition

C++: http://ganeshtiwaridotcomdotnp.blogspot.co.il/2009/12/c-c-code-lu-decomposition-for-solving.html

image

Represent the matrix as a product of lower & upper triangular matrices

A modified version of GJ Elimination

Advantage – can easily apply forward & backward elimination to solve triangular matrices

Techniques:

· Doolittle Method – sets the L matrix diagonal to unity

· Crout Method - sets the U matrix diagonal to unity

Note: both the L & U matrices share the same unity diagonal & can be stored compactly in the same matrix

Gauss-Seidel Iteration

http://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method

C++: http://www.nr.com/forum/showthread.php?t=722

Transform the linear set of equations into a single equation & then use numerical integration (as integration formulas have Sums, it is implemented iteratively).

an optimization of Gauss-Jacobi: 1.5 times faster, requires 0.25 iterations to achieve the same tolerance

Solving Non-Linear Equations Iteratively

find roots of polynomials – there may be 0, 1 or n solutions for an n order polynomial

use iterative techniques

Iterative methods

· used when there are no known analytical techniques

· Requires set functions to be continuous & differentiable

· Requires an initial seed value – choice is critical to convergence à conduct multiple runs with different starting points & then select best result

· Systematic - iterate until diminishing returns, tolerance or max iteration conditions are met

· bracketing techniques will always yield convergent solutions, non-bracketing methods may fail to converge

Incremental method

if a nonlinear function has opposite signs at 2 ends of a small interval x1 & x2, then there is likely to be a solution in their interval – solutions are detected by evaluating a function over interval steps, for a change in sign, adjusting the step size dynamically.

Limitations – can miss closely spaced solutions in large intervals, cannot detect degenerate (coinciding) solutions, limited to functions that cross the x-axis, gives false positives for singularities

Fixed point method

http://en.wikipedia.org/wiki/Fixed-point_iteration

C++: http://books.google.co.il/books?id=weYj75E_t6MC&pg=PA79&lpg=PA79&dq=fixed+point+method++c%2B%2B&source=bl&ots=LQ-5P_taoC&sig=lENUUIYBK53tZtTwNfHLy5PEWDk&hl=en&sa=X&ei=wezDUPW1J5DptQaMsIHQCw&redir_esc=y#v=onepage&q=fixed%20point%20method%20%20c%2B%2B&f=false

image

Algebraically rearrange a solution to isolate a variable then apply incremental method

Bisection method

http://en.wikipedia.org/wiki/Bisection_method

C++: http://numericalcomputing.wordpress.com/category/algorithms/

image

Bracketed - Select an initial interval, keep bisecting it ad midpoint into sub-intervals and then apply incremental method on smaller & smaller intervals – zoom in

Adv: unaffected by function gradient à reliable

Disadv: slow convergence

False Position Method

http://en.wikipedia.org/wiki/False_position_method

C++: http://www.dreamincode.net/forums/topic/126100-bisection-and-false-position-methods/

Bracketed - Select an initial interval , & use the relative value of function at interval end points to select next sub-intervals (estimate how far between the end points the solution might be & subdivide based on this)

Newton-Raphson method

http://en.wikipedia.org/wiki/Newton's_method

C++: http://www-users.cselabs.umn.edu/classes/Summer-2012/csci1113/index.php?page=./newt3

image

Also known as Newton's method

Convenient, efficient

Not bracketed – only a single initial guess is required to start iteration – requires an analytical expression for the first derivative of the function as input.

Evaluates the function & its derivative at each step.

Can be extended to the Newton MutiRoot method for solving multiple roots

Can be easily applied to an of n-coupled set of non-linear equations – conduct a Taylor Series expansion of a function, dropping terms of order n, rewrite as a Jacobian matrix of PDs & convert to simultaneous linear equations !!!

Secant Method

http://en.wikipedia.org/wiki/Secant_method

C++: http://forum.vcoderz.com/showthread.php?p=205230

image

Unlike N-R, can estimate first derivative from an initial interval (does not require root to be bracketed) instead of inputting it

Since derivative is approximated, may converge slower. Is fast in practice as it does not have to evaluate the derivative at each step.

Similar implementation to False Positive method

Birge-Vieta Method

http://mat.iitm.ac.in/home/sryedida/public_html/caimna/transcendental/polynomial%20methods/bv%20method.html

C++: http://books.google.co.il/books?id=cL1boM2uyQwC&pg=SA3-PA51&lpg=SA3-PA51&dq=Birge-Vieta+Method+c%2B%2B&source=bl&ots=QZmnDTK3rC&sig=BPNcHHbpR_DKVoZXrLi4nVXD-gg&hl=en&sa=X&ei=R-_DUK2iNIjzsgbE5ID4Dg&redir_esc=y#v=onepage&q=Birge-Vieta%20Method%20c%2B%2B&f=false

combines Horner's method of polynomial evaluation (transforming into lesser degree polynomials that are more computationally efficient to process) with Newton-Raphson to provide a computational speed-up

Interpolation

Overview

Construct new data points for as close as possible fit within range of a discrete set of known points (that were obtained via sampling, experimentation)

Use Taylor Series Expansion of a function f(x) around a specific value for x

Linear Interpolation

http://en.wikipedia.org/wiki/Linear_interpolation

C++: http://www.hamaluik.com/?p=289

image

Straight line between 2 points à concatenate interpolants between each pair of data points

Bilinear Interpolation

http://en.wikipedia.org/wiki/Bilinear_interpolation

C++: http://supercomputingblog.com/graphics/coding-bilinear-interpolation/2/

image

Extension of the linear function for interpolating functions of 2 variables – perform linear interpolation first in 1 direction, then in another.

Used in image processing – e.g. texture mapping filter. Uses 4 vertices to interpolate a value within a unit cell.

Lagrange Interpolation

http://en.wikipedia.org/wiki/Lagrange_polynomial

C++: http://www.codecogs.com/code/maths/approximation/interpolation/lagrange.php

image

For polynomials

Requires recomputation for all terms for each distinct x value – can only be applied for small number of nodes

Numerically unstable

Barycentric Interpolation

http://epubs.siam.org/doi/pdf/10.1137/S0036144502417715

C++: http://www.gamedev.net/topic/621445-barycentric-coordinates-c-code-check/

image

Rearrange the terms in the equation of the Legrange interpolation by defining weight functions that are independent of the interpolated value of x

Newton Divided Difference Interpolation

http://en.wikipedia.org/wiki/Newton_polynomial

C++: http://jee-appy.blogspot.co.il/2011/12/newton-divided-difference-interpolation.html

Hermite Divided Differences:

image

Interpolation polynomial approximation for a given set of data points in the NR form - divided differences are used to approximately calculate the various differences.

For a given set of 3 data points , fit a quadratic interpolant through the data

Bracketed functions allow Newton divided differences to be calculated recursively

Difference table

Cubic Spline Interpolation

http://en.wikipedia.org/wiki/Spline_interpolation

C++: https://www.marcusbannerman.co.uk/index.php/home/latestarticles/42-articles/96-cubic-spline-class.html

image

Spline is a piecewise polynomial

Provides smoothness – for interpolations with significantly varying data

Use weighted coefficients to bend the function to be smooth & its 1st & 2nd derivatives are continuous through the edge points in the interval

Curve Fitting

A generalization of interpolating whereby given data points may contain noise à the curve does not necessarily pass through all the points

Least Squares Fit

http://en.wikipedia.org/wiki/Least_squares

C++: http://www.ccas.ru/mmes/educat/lab04k/02/least-squares.c

image

Residual – difference between observed value & expected value

Model function is often chosen as a linear combination of the specified functions

Determines:

A) The model instance in which the sum of squared residuals has the least value

B) param values for which model best fits data

Straight Line Fit

Linear correlation between independent variable and dependent variable

Linear Regression

http://en.wikipedia.org/wiki/Linear_regression

C++: http://www.oocities.org/david_swaim/cpp/linregc.htm

image

Special case of statistically exact extrapolation

Leverage least squares

Given a basis function, the sum of the residuals is determined and the corresponding gradient equation is expressed as a set of normal linear equations in matrix form that can be solved (e.g. using LU Decomposition)

Can be weighted - Drop the assumption that all errors have the same significance –-> confidence of accuracy is different for each data point. Fit the function closer to points with higher weights

Polynomial Fit - use a polynomial basis function

Moving Average

http://en.wikipedia.org/wiki/Moving_average

C++: http://www.codeproject.com/Articles/17860/A-Simple-Moving-Average-Algorithm

image

Used for smoothing (cancel fluctuations to highlight longer-term trends & cycles), time series data analysis, signal processing filters

Replace each data point with average of neighbors.

Can be simple (SMA), weighted (WMA), exponential (EMA). Lags behind latest data points – extra weight can be given to more recent data points. Weights can decrease arithmetically or exponentially according to distance from point.

Parameters: smoothing factor, period, weight basis

Optimization

Overview

Given function with multiple variables, find Min (or max by minimizing –f(x))

Iterative approach

Efficient, but not necessarily reliable

Conditions: noisy data, constraints, non-linear models

Detection via sign of first derivative - Derivative of saddle points will be 0

Local minima

Bisection method

Similar method for finding a root for a non-linear equation

Start with an interval that contains a minimum

Golden Search method

http://en.wikipedia.org/wiki/Golden_section_search

C++: http://www.codecogs.com/code/maths/optimization/golden.php

image

Bisect intervals according to golden ratio 0.618..

Achieves reduction by evaluating a single function instead of 2

Newton-Raphson Method

Brent method

http://en.wikipedia.org/wiki/Brent's_method

C++: http://people.sc.fsu.edu/~jburkardt/cpp_src/brent/brent.cpp

Based on quadratic or parabolic interpolation – if the function is smooth & parabolic near to the minimum, then a parabola fitted through any 3 points should approximate the minima – fails when the 3 points are collinear , in which case the denominator is 0

Simplex Method

http://en.wikipedia.org/wiki/Simplex_algorithm

C++: http://www.codeguru.com/cpp/article.php/c17505/Simplex-Optimization-Algorithm-and-Implemetation-in-C-Programming.htm

image

Find the global minima of any multi-variable function

Direct search – no derivatives required

At each step it maintains a non-degenerative simplex – a convex hull of n+1 vertices.

Obtains the minimum for a function with n variables by evaluating the function at n-1 points, iteratively replacing the point of worst result with the point of best result, shrinking the multidimensional simplex around the best point.

Point replacement involves expanding & contracting the simplex near the worst value point to determine a better replacement point

Oscillation can be avoided by choosing the 2nd worst result

Restart if it gets stuck

Parameters: contraction & expansion factors

Simulated Annealing

http://en.wikipedia.org/wiki/Simulated_annealing

C++: http://code.google.com/p/cppsimulatedannealing/

image

Analogy to heating & cooling metal to strengthen its structure

Stochastic method – apply random permutation search for global minima - Avoid entrapment in local minima via hill climbing

Heating schedule - Annealing schedule params: temperature, iterations at each temp, temperature delta

Cooling schedule – can be linear, step-wise or exponential

Differential Evolution

http://en.wikipedia.org/wiki/Differential_evolution

C++: http://www.amichel.com/de/doc/html/

More advanced stochastic methods analogous to biological processes: Genetic algorithms, evolution strategies

Parallel direct search method against multiple discrete or continuous variables

Initial population of variable vectors chosen randomly – if weighted difference vector of 2 vectors yields a lower objective function value then it replaces the comparison vector

Many params: #parents, #variables, step size, crossover constant etc

Convergence is slow – many more function evaluations than simulated annealing

Numerical Differentiation

Overview

2 approaches to finite difference methods:

· A) approximate function via polynomial interpolation then differentiate

· B) Taylor series approximation – additionally provides error estimate

Finite Difference methods

http://en.wikipedia.org/wiki/Finite_difference_method

C++: http://www.wpi.edu/Pubs/ETD/Available/etd-051807-164436/unrestricted/EAMPADU.pdf

image

Find differences between high order derivative values - Approximate differential equations by finite differences at evenly spaced data points

Based on forward & backward Taylor series expansion of f(x) about x plus or minus multiples of delta h.

Forward / backward difference - the sums of the series contains even derivatives and the difference of the series contains odd derivatives – coupled equations that can be solved.

Provide an approximation of the derivative within a O(h^2) accuracy

There is also central difference & extended central difference which has a O(h^4) accuracy

Richardson Extrapolation

http://en.wikipedia.org/wiki/Richardson_extrapolation

C++: http://mathscoding.blogspot.co.il/2012/02/introduction-richardson-extrapolation.html

A sequence acceleration method applied to finite differences

Fast convergence, high accuracy O(h^4)

Derivatives via Interpolation

Cannot apply Finite Difference method to discrete data points at uneven intervals – so need to approximate the derivative of f(x) using the derivative of the interpolant via 3 point Lagrange Interpolation

Note: the higher the order of the derivative, the lower the approximation precision

Numerical Integration

Estimate finite & infinite integrals of functions

More accurate procedure than numerical differentiation

Use when it is not possible to obtain an integral of a function analytically or when the function is not given, only the data points are

Newton Cotes Methods

http://en.wikipedia.org/wiki/Newton%E2%80%93Cotes_formulas

C++: http://www.siafoo.net/snippet/324

image

For equally spaced data points

Computationally easy – based on local interpolation of n rectangular strip areas that is piecewise fitted to a polynomial to get the sum total area

Evaluate the integrand at n+1 evenly spaced points – approximate definite integral by Sum

Weights are derived from Lagrange Basis polynomials

Leverage Trapezoidal Rule for default 2nd formulas, Simpson 1/3 Rule for substituting 3 point formulas, Simpson 3/8 Rule for 4 point formulas. For 4 point formulas use Bodes Rule. Higher orders obtain more accurate results

Trapezoidal Rule uses simple area, Simpsons Rule replaces the integrand f(x) with a quadratic polynomial p(x) that uses the same values as f(x) for its end points, but adds a midpoint

Romberg Integration

http://en.wikipedia.org/wiki/Romberg's_method

C++: http://code.google.com/p/romberg-integration/downloads/detail?name=romberg.cpp&can=2&q=

Combines trapezoidal rule with Richardson Extrapolation

Evaluates the integrand at equally spaced points

The integrand must have continuous derivatives

Each R(n,m) extrapolation uses a higher order integrand polynomial replacement rule (zeroth starts with trapezoidal) à a lower triangular matrix set of equation coefficients where the bottom right term has the most accurate approximation. The process continues until the difference between 2 successive diagonal terms becomes sufficiently small.

Gaussian Quadrature

http://en.wikipedia.org/wiki/Gaussian_quadrature

C++: http://www.alglib.net/integration/gaussianquadratures.php

Data points are chosen to yield best possible accuracy – requires fewer evaluations

Ability to handle singularities, functions that are difficult to evaluate

The integrand can include a weighting function determined by a set of orthogonal polynomials.

Points & weights are selected so that the integrand yields the exact integral if f(x) is a polynomial of degree <= 2n+1

Techniques (basically different weighting functions):

· Gauss-Legendre Integration w(x)=1

· Gauss-Laguerre Integration w(x)=e^-x

· Gauss-Hermite Integration w(x)=e^-x^2

· Gauss-Chebyshev Integration w(x)= 1 / Sqrt(1-x^2)

Solving ODEs

Use when high order differential equations cannot be solved analytically

Evaluated under boundary conditions

RK for systems – a high order differential equation can always be transformed into a coupled first order system of equations

Euler method

http://en.wikipedia.org/wiki/Euler_method

C++: http://rosettacode.org/wiki/Euler_method

image

First order Runge–Kutta method.

Simple recursive method – given an initial value, calculate derivative deltas.

Unstable & not very accurate (O(h) error) – not used in practice

A first-order method - the local error (truncation error per step) is proportional to the square of the step size, and the global error (error at a given time) is proportional to the step size

In evolving solution between data points xn & xn+1, only evaluates derivatives at beginning of interval xn à asymmetric at boundaries

Higher order Runge Kutta

http://en.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods

C++: http://www.dreamincode.net/code/snippet1441.htm

image

2nd & 4th order RK - Introduces parameterized midpoints for more symmetric solutions à accuracy at higher computational cost

Adaptive RK – RK-Fehlberg – estimate the truncation at each integration step & automatically adjust the step size to keep error within prescribed limits. At each step 2 approximations are compared – if in disagreement to a specific accuracy, the step size is reduced

Boundary Value Problems

Where solution of differential equations are located at 2 different values of the independent variable x à more difficult, because cannot just start at point of initial value – there may not be enough starting conditions available at the end points to produce a unique solution

An n-order equation will require n boundary conditions – need to determine the missing n-1 conditions which cause the given conditions at the other boundary to be satisfied

Shooting Method

http://en.wikipedia.org/wiki/Shooting_method

C++: http://ganeshtiwaridotcomdotnp.blogspot.co.il/2009/12/c-c-code-shooting-method-for-solving.html

image

Iteratively guess the missing values for one end & integrate, then inspect the discrepancy with the boundary values of the other end to adjust the estimate

Given the starting boundary values u1 & u2 which contain the root u, solve u given the false position method (solving the differential equation as an initial value problem via 4th order RK), then use u to solve the differential equations.

Finite Difference Method

For linear & non-linear systems

Higher order derivatives require more computational steps – some combinations for boundary conditions may not work though

Improve the accuracy by increasing the number of mesh points

Solving EigenValue Problems

An eigenvalue can substitute a matrix when doing matrix multiplication à convert matrix multiplication into a polynomial EigenValue

For a given set of equations in matrix form, determine what are the solution eigenvalue & eigenvectors

Similar Matrices - have same eigenvalues. Use orthogonal similarity transforms to reduce a matrix to diagonal form from which eigenvalue(s) & eigenvectors can be computed iteratively

image

Jacobi method

http://en.wikipedia.org/wiki/Jacobi_method

C++: http://people.sc.fsu.edu/~jburkardt/classes/acs2_2008/openmp/jacobi/jacobi.html

Robust but Computationally intense – use for small matrices < 10x10

Power Iteration

http://en.wikipedia.org/wiki/Power_iteration

For any given real symmetric matrix, generate the largest single eigenvalue & its eigenvectors

Simplest method – does not compute matrix decomposition à suitable for large, sparse matrices

Inverse Iteration

Variation of power iteration method – generates the smallest eigenvalue from the inverse matrix

Rayleigh Method

http://en.wikipedia.org/wiki/Rayleigh's_method_of_dimensional_analysis

Variation of power iteration method

Rayleigh Quotient Method

Variation of inverse iteration method

Matrix Tri-diagonalization Method

Use householder algorithm to reduce an NxN symmetric matrix to a tridiagonal real symmetric matrix vua N-2 orthogonal transforms

 

 

Whats Next

Outside of Numerical Methods there are lots of different types of algorithms that I’ve learned over the decades:

Sooner or later, I’ll cover the above topics as well.

Posted On Sunday, December 9, 2012 5:28 AM | Comments (0)

Copyright © JoshReuben

Design by Bartosz Brzezinski

Design by Phil Haack Based On A Design By Bartosz Brzezinski