Collaborative articulation of how abstraction and language is employed in the computational manifestation of numbers -- including analysis of the role of syntax, semantics, and meaning in the specification and use of software interfaces.

- Archives - 2004-05-30 2004-06-06 2004-06-13 2004-06-27 2004-08-22 2004-08-29 2004-10-03 2004-12-05 2005-01-23 2005-06-19 2005-08-14 2005-10-09 2006-01-01 2006-02-05 2006-02-12 2006-07-09 2006-07-16 2006-07-30 2006-08-06 2006-08-20 2006-10-08 2006-10-22 2006-10-29 2006-11-26 2007-04-29 2007-11-04 2007-11-11 2007-11-18 2008-01-06 2008-01-13 2008-01-27 2008-02-10 2008-02-24 2008-05-04 2008-05-25 2008-06-08 2008-06-15 2009-06-21 2009-11-08 2010-04-25


Blog Feed

Recent Items
 
Alan Turing Birthday: July 23, Centenary: 2012
 
Miser: Interpretations of Identity
 
Turing Arrives: Petzold on Arithmetic
 
Reality Is the Model
 
Catching Up with Turing
 
Miser: The Logic of Ot
 
Miser: Frugalese for Applicative Operations
 
SeaFunc: 2008-02-20 Functional Programming Meetup
 
Miser: The Immutability of Obs
 
Computer Science Classics: Your Picks?

  

visits to Miser Project pages

The nfoCentrale Blog Conclave
 
Millennia Antica: The Kiln Sitter's Diary
 
nfoWorks: Pursuing Harmony
 
Numbering Peano
 
Orcmid's Lair
 
Orcmid's Live Hideout
 
Prof. von Clueless in the Blunder Dome
 
Spanner Wingnut's Muddleware Lab (experimental)

nfoCentrale Associated Sites
 
DMA: The Document Management Alliance
 
DMware: Document Management Interoperability Exchange
 
Millennia Antica Pottery
 
The Miser Project
 
nfoCentrale: the Anchor Site
 
nfoWare: Information Processing Technology
 
nfoWorks: Tools for Document Interoperability
 
NuovoDoc: Design for Document System Interoperability
 
ODMA Interoperability Exchange
 
Orcmid's Lair
 
TROST: Open-System Trustworthiness

 

Friday Miser Note: Interchanging Code

While I think and post mainly about the theoretical abstractions that are important in getting Miser and the Frugal language done properly, I am also thinking ahead to the way the Miser engine can be delivered as a platform component (Windows DLL, .NET assembly, etc.) that hosts Miser on behalf of a software application.  I have in mind that any kind of Frugalese user interface for a console application, including any interactive development environment (IDE), would be built atop a hosted oMiser engine as an important first case.

Because the Miser model is platform independent, it would be nice to have a platform-independent way to save, load, and interchange Miser “codes” in a neutral, highly-interchangeable format.

XML comes to mind.   Although XML is not a compact binary format, it is a well-known, standard format for which a great number of problems are already solved, including versioning, the ability to deal with extensions gracefully, the complete hiding of the storage structure, and harmony with my intention that the Miser abstraction be universally comprehended.  (That is to say, it shall seem as if there is only one oMiser in the world, and the fact that implementations are distributed and replicated is as invisible as can be practically achieved.)  In the oMiser case, the XML stream would also be highly compressible using widely-available compression techniques.

The interchangeable “object code” among all oMiser implementations will be standardized in an XML stream. 

I propose to abuse the purity of XML for this purpose.   The XML will be well-formed but it won’t be the way XML would be naturally used to communicate a persistent format for oMiser Obs.

My basic plan is that the loadable Ob will be coded in a reverse-Polish notation conveyed in XML.   The notation will have a syntactic structure that conforms to a BNF grammar such as

〈ob〉::= 〈term〉 | 〈ob〉 〈un-op〉 | 〈ob〉 〈ob〉 〈bin-op〉

allowing the bottom-up build-up of an internal Ob representation as the XML stream is being read.  Not every Ob operation needs to be implemented, only those needed for constructing constant Obs: 

• Here 〈term〉 entries will specify individuals or links to Obs defined earlier in the stream. 
    
• There will be unary〈un-op〉operations, including one for ob.e(ob) and one for labeling an Ob so that it can be referenced later in the stream.  Linking to already-expressed Obs is indispensible for simplifying repetitive introduction of the same Ob in the interior of a larger Ob.  I intend to make use of xml:id for this purpose.
     
• There will be binary 〈bin-op〉operations, including one for ob.c(ob, ob). 
    
• There will be additional mark-up, but this is the essential structure.

XML streams for the loadable format will be supported at the core level of an oMiser implementation.  Given a handle on an Ob, there is an interface that will emit the XML stream for persistent representation of that Ob for any interchange purpose.  Likewise, there is a low-level interface on every oMiser engine by which an XML stream is accepted and a handle for the corresponding Ob returned for use in the hosting application.

The XML representation will be flat.  That is, the <oMiser:ob> XML element contains a flat sequence of <term />, <un-op />, and <bin-op /> elements.  It is easy to process such a flat structure, and it is easy to ensure that such a structure is well-formed according to the grammar for〈ob〉given above.

There are three interesting challenges for this structure.  These need to be explored to ensure that the choice of a reverse-polish Ob-loading is as practical as I intend for it to be:

1. It is more difficult to produce the loadable format than it is to consume it.  This desirable trade-off has to be a containable problem.  In particular, we need storage-efficient techniques for emitting the bottom-up reverse-polish construction of any Ob that we are given a handle to.
    
2. Because Obs are inherently immutable, sharing of common parts is an important storage economizer in oMiser implementations.   Taking advantage of opportunities for sharing of substructure in a running implementation is an interesting challenge.  Preserving or even enhancing sharing in an exported loader format is an additional opportunity.  (It may well be the case that improved sharing and the consequent logical compression of the persistent form is better done by a separate post-processing optimization utility.)
     
3. While the run-time validation of a well-formed reverse-Polish sequence of elements is trivial, its expression as a constraint on an XML schema is not so easy.  We don’t need an XML schema to implement a consumer of the format (and we can use namespace and DTD rules to signify that the format constraints apply).  Just the same, it is valuable to have some sort of schema that expresses the reverse-Polish constraint on the sequence of content elements within an XML <oMiser:ob> element.

I was reminded of all of this when I recently read the 2009-09-29 Rick Jelliffe post on context-free XML.   The shoe-horning of the context-free reverse-Polish flat stream for〈ob〉as content for an XML <oMiser:ob> element creates a context-sensitive problem for expression in some sort of XML schema.  This post is intended to elaborate on the comment that Rick’s post inspired from me.  I trust this is useful context for that.  (As usual, your mileage may vary.)

Discussing oMiser implementation considerations is long overdue in any case.

Labels: implementation note, oMiser

¶ posted by orcmid at 11/13/2009 09:34:00 AM

  <$BlogBacklinkTitle$>  

<$BlogBacklinkSnippet$>
posted by <$BlogBacklinkAuthor$> at <$BlogBacklinkDateTime$>