Standard ML as graphics file format design tool
Thant Tessman
I've been thinking about graphics file formats on and off for many years
now. Somewhere along the way I figured out that people were thinking
about the problem from the wrong point of view.
The problem is that graphics file formats invariably have to let the
semantics of the data they represent drive the syntax of the format. For
example, geometric vertex position data usually--but not
necessarily--takes the form of homogeneous arrays of 3-dimensional
coordinates. Applications are forced to work within the semantic
confines of the data structures the format can faithfully represent. If
the format hopes to allow for the efficient parsing of data directly
into memory, its design is forced to anticipate every kind of data its
designers think might need to be stored.
Invariably, designers are forced to create complex formats that never
quite transcend an overly-specific approach to the development of
computer graphics applications.
What we need is not a file format, but a programming language--or at
least something like a programming language. This programming language's
job is merely to read in a 'program' and build the data structures
described. It doesn't need to evaluate anything. It doesn't need control
structures. It doesn't need functions. But it does need a type system.
The end goal was always to provide the services of this 'language' as a
highly-optimized C++ library, but on my third or fourth attempt to
create just such a 'language' I decided to do a 'reference'
implementation in Standard ML. What this bought me was a huge amount of
confidence that there were no holes in the semantics or un-accounted-for
corner cases in the design.
The language is described here:
http://www.thant.com/projects/dl/dl090117.pdf
The SML 'reference' implementation is available here:
http://www.thant.com/projects/dl/dl_sml_090122.tar.gz
It builds for both SML/NJ and MLton.
Data Language can be thought of as playing the role that XML plays in
the Collada standard, only it's more efficient, easier to implement,
safer, and can be described in a dozen pages instead of a hundred. And I
can't help but think that even my SML implementation is far more
efficient than any XML library written in C. The Collada standard
explicitly states that it is not a "run-time delivery format" or
"streaming-friendly." But my C++ implementation of my "Data Language" is
already serving as exactly that.
Although I do have some experience with XML, I'm no expert. What am I
missing? What is the use of XML for these kinds of things buying people?
-thant
Dimiter "malkia" Stanev
If you have Windows machine available, you might want to check Microsoft
DirectX SDK - it has a similiar .X file format for describing 3D models,
where the definitions of the structures representing the data are int
the actual file. I can't tell how related it's to your work, but it
might be of interrest to you.
I myself am newbie functional programmer, so can't really give any opinion.
Here is a little excerpt from one of the Microsoft DirectX .X files:
D:\dx\Samples\C++\XACT\XACTGame\media\ammo.x
xof 0303txt 0032
template Frame {
<3d82ab46-62da-11cf-ab39-0020af71e433>
[...] // this is not snipped from the .X file - it was like that
}
template Matrix4x4 {
<f6f23f45-7686-11cf-8f52-0040333594a3>
array FLOAT matrix[16];
}
template FrameTransformMatrix {
<f6f23f41-7686-11cf-8f52-0040333594a3>
Matrix4x4 frameMatrix;
}
template Vector {
<3d82ab5e-62da-11cf-ab39-0020af71e433>
FLOAT x;
FLOAT y;
FLOAT z;
}
template MeshFace {
<3d82ab5f-62da-11cf-ab39-0020af71e433>
DWORD nFaceVertexIndices;
array DWORD faceVertexIndices[nFaceVertexIndices];
}
template Mesh {
<3d82ab44-62da-11cf-ab39-0020af71e433>
DWORD nVertices;
array Vector vertices[nVertices];
DWORD nFaces;
array MeshFace faces[nFaces];
[...]
}
template MeshNormals {
<f6f23f43-7686-11cf-8f52-0040333594a3>
DWORD nNormals;
array Vector normals[nNormals];
DWORD nFaceNormals;
array MeshFace faceNormals[nFaceNormals];
}
template Coords2d {
<f6f23f44-7686-11cf-8f52-0040333594a3>
FLOAT u;
FLOAT v;
}
template MeshTextureCoords {
<f6f23f40-7686-11cf-8f52-0040333594a3>
DWORD nTextureCoords;
array Coords2d textureCoords[nTextureCoords];
}
template ColorRGBA {
<35ff44e0-6c7c-11cf-8f52-0040333594a3>
FLOAT red;
FLOAT green;
FLOAT blue;
FLOAT alpha;
}
template ColorRGB {
<d3e16e81-7835-11cf-8f52-0040333594a3>
FLOAT red;
FLOAT green;
FLOAT blue;
}
template Material {
<3d82ab4d-62da-11cf-ab39-0020af71e433>
ColorRGBA faceColor;
FLOAT power;
ColorRGB specularColor;
ColorRGB emissiveColor;
[...]
}
[ snipped other structures ]
...
And later some actual data:
Frame Frame_World {
FrameTransformMatrix {
1.000000,0.000000,0.000000,0.000000,0.000000,1.000000,0.000000,0.000000,0.000000,0.000000,-1.000000,0.000000,0.000000,0.000000,0.000000,1.000000;;
}
Frame Frame_ammo4 {
FrameTransformMatrix {
1.000000,0.000000,0.000000,0.000000,0.000000,1.000000,0.000000,0.000000,0.000000,0.000000,1.000000,0.000000,0.000000,0.000000,0.000000,1.000000;;
}
Frame Frame_pSphere1____0 {
FrameTransformMatrix {
1.000000,0.000000,0.000000,0.000000,0.000000,1.000000,0.000000,0.000000,0.000000,0.000000,1.000000,0.000000,0.004506,-0.024622,-0.032291,1.000000;;
}
Mesh pSphere1____0 {
2271;
0.119716;-1.117010;0.029854;,
0.119716;-1.117010;0.029854;,
-0.966603;-0.624395;-0.124618;,
1.126690;-0.072870;-0.053448;,
1.126690;-0.072870;-0.053448;,
0.286907;1.113333;0.020714;,
0.286907;1.113333;0.020714;,
0.011680;-0.092646;-1.187050;,
-0.622948;0.965559;0.091267;,
0.424839;0.365545;1.080494;,
-0.674366;-0.404169;0.936062;,
0.776580;-0.443052;0.806629;,
0.813160;-0.771349;-0.050308;,
0.813160;-0.771349;-0.050308;,
0.720916;0.283476;-0.851158;,
0.848972;0.699999;-0.039787;,
0.848972;0.699999;-0.039787;,
-0.752758;-0.018713;-0.853310;,
-0.151104;1.072626;-0.433803;,
0.035850;0.927404;0.747101;,
0.976493;0.386835;0.525112;,
0.131359;-0.723265;-0.778648;,
-0.224499;-1.053362;0.033665;,
0.008384;-0.654142;0.967896;,
-0.614071;0.502821;-0.809711;,
-0.933640;0.663775;0.256989;,
Jon Harrop
> Although I do have some experience with XML, I'm no expert. What am I
> missing? What is the use of XML for these kinds of things buying people?
XML brings uniform syntax to people who only have lame parsing tools, no
experience writing parsers and no functionality to write parsers easily
(e.g. no combinators).
With XML, they just pull in the defacto-standard XML parser for their
framework of choice (usually Java's or .NET's) and they get a data
structure that they can manipulate. Also, the manipulations are often not
performance critical and, consequently, even the standard libraries for
manipulating XML are extremely inefficient in some respects. For example,
serialization on .NET is O(n^2) where "n" is the number of function
pointers being serialized. I have also heard that the complexity of getting
the text for a branch of XML can be proportional to the size of the entire
document.
Regarding your idea, PostScript is a nightmare because it embeds a PL in a
graphics file format. Fortunately, PDF remedied this design mistake. I
would not recommend repeating it.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Shyamal Prasad
Jon> Thant Tessman wrote:
>> Although I do have some experience with XML, I'm no
>> expert. What am I missing? What is the use of XML for these
>> kinds of things buying people?
Jon> XML brings uniform syntax to people who only have lame
Jon> parsing tools, no experience writing parsers and no
Jon> functionality to write parsers easily (e.g. no combinators).
True, but that statement could also be true for unsophisticated users
of any language. One thing XML *does* have which is very sophisitcated
is XSLT. Most people I know don't recognize XSLT for what it is: a
purely functional language built specifically to manipulate XML. It
has a horrible syntax (since XSLT programs are XML documents) but it
would not qualify as "lame parsing tools". It's actually pretty cool.
Jon> I have also heard that the complexity of getting the text for
Jon> a branch of XML can be proportional to the size of the entire
Jon> document.
As I understand it, the W3C DOM specification for XML has resulted in
some very poor implementations that do have this problem (if I'm wrong
about the specificaion being the cause I would love to be
corrected). But it's not inherent in XML; there are lots of efficient
implementations around.
I'm certainly not a XML fanboy but there's more than a few good ideas
there (XSLT being my favorite). They mostly get lost in the Java/XML
noise that one always hears in industry there days.....
Cheers!
Shyamal
Thant Tessman
[...]
> Regarding your idea, PostScript is a nightmare because it embeds a PL in a
> graphics file format. Fortunately, PDF remedied this design mistake. I
> would not recommend repeating it.
Thanks for the reply. Note that when I describe DL as a programming
language, I'm only talking about the ability to specify data structures
and type check them. Nothing ever gets executed or evaluated or
computed. This is indeed by design.
-thant
Thant Tessman
> Hi Thant,
>
> If you have Windows machine available, you might want to check Microsoft
> DirectX SDK - it has a similiar .X file format for describing 3D models,
> where the definitions of the structures representing the data are int
> the actual file. I can't tell how related it's to your work, but it
> might be of interrest to you.
I don't trust Microsoft to get *anything* right, but at first glance
this does indeed seem to be the same basic idea. Thanks for the pointer.
Note that the only relationship this has to functional programming is
that the specification of the type system of my graphics file format was
made more robust by its implementation in Standard ML. The description
of the types in the document closely parallels its implementation as a
datatype in the code. Writing the whole thing in SML helped in other
ways as well.
-thant
Jon Harrop
I see. My misunderstanding. In that case it may well be a good idea. :-)
Jon Harrop
> Dimiter "malkia" Stanev wrote:
>> Hi Thant,
>>
>> If you have Windows machine available, you might want to check Microsoft
>> DirectX SDK - it has a similiar .X file format for describing 3D models,
>> where the definitions of the structures representing the data are int
>> the actual file. I can't tell how related it's to your work, but it
>> might be of interrest to you.
>
> I don't trust Microsoft to get *anything* right, but at first glance
> this does indeed seem to be the same basic idea.
I used to think that but I have learned a great deal by studying Microsoft's
work in recent years.
Jon Harrop
>>>>>> "Jon" == Jon Harrop <j...@ffconsultancy.com> writes:
>
> Jon> Thant Tessman wrote:
> >> Although I do have some experience with XML, I'm no
> >> expert. What am I missing? What is the use of XML for these
> >> kinds of things buying people?
>
> Jon> XML brings uniform syntax to people who only have lame
> Jon> parsing tools, no experience writing parsers and no
> Jon> functionality to write parsers easily (e.g. no combinators).
>
> True, but that statement could also be true for unsophisticated users
> of any language.
I would like to think that even unsophisticated users would find it much
easier to write a parser using ocamllex or camlp4 than anything in C++.
> One thing XML *does* have which is very sophisitcated
> is XSLT. Most people I know don't recognize XSLT for what it is: a
> purely functional language built specifically to manipulate XML. It
> has a horrible syntax (since XSLT programs are XML documents) but it
> would not qualify as "lame parsing tools".
AFAIK, I would not even categorize XSLT as a parsing tool at all: I thought
it was a tree rewriter?
> Jon> I have also heard that the complexity of getting the text for
> Jon> a branch of XML can be proportional to the size of the entire
> Jon> document.
>
> As I understand it, the W3C DOM specification for XML has resulted in
> some very poor implementations that do have this problem (if I'm wrong
> about the specificaion being the cause I would love to be
> corrected). But it's not inherent in XML;
Hmm, I'm not quite sure what you mean here. Do you mean a different XML
could have been cleanly designed without the horrors of Schemas and so
forth?
> there are lots of efficient implementations around.
There are lots of broken implementations around. XML-Light is by far the
most common XML parser for OCaml and it is completely broken. PXP is
supposedly standards complaint but its interface is horrendous: you don't
even get a tree that you can dissect with pattern matching!
> I'm certainly not a XML fanboy but there's more than a few good ideas
> there (XSLT being my favorite). They mostly get lost in the Java/XML
> noise that one always hears in industry there days.....
Understandably. :-)
Xah Lee
I scanned your doc and read your message, but i don't quite understand
your idea clearly. It appears to me, you Data Language (DL) is just a
lean version of XML. (as one way to put it)
here's some thought about this topic ...
things that happen in the industry or academia has a strong, not
neglect-able social causes. It might be obvious, that some language X,
protocols Y, etc, is clearly technically superior, yet nobody seems to
thought of it, invented it, or use it, while the industry and everyone
is using or talking about Z and its variants. If one puts social
aspects into this equation, many such mystery dissolves.
if i understand your case correctly... note that the concept of XML
was due to the popularity of HTML, and was born as a effort to cleaned
up HTML, when HTML hit the world big time with once known as World
Wide Web in the 1990s. (HTML itself is borne out of SGML, which is
quite complex) Once XML with its regularity of syntax came into broad
awareness among tech people, large number of ideas and movement
happened... you have a bunch of XML related technologies (RSS, XSLT,
the whole Ajax related protocols, too many to list)
few years ago, it was popularly thought among lisp fanatics, that the
world finally got the sexp idea and copied lisp to have XML. But lisp
syntax is not regular. XML is. (and Mathematica is) Once you have a
pure uniform syntax that can trivially parsed, the ideas of the its
power spread and lots of tech based on it comes into being, as we see
with the case of XML. (note that the many tech development derived
from XML happened similarly to Mathematica since 1996 with Mathematica
3)
For details on this, the implication and consequences of a regular
syntax, see:
• Fundamental Problems of Lisp
http://xahlee.org/UnixResource_dir/writ/lisp_problems.html
Now, given XML, we notice that it is EXTREMELY verbose. Verbose to the
point that in puts significant burden to even machines. One wonders,
that XML could simply have a lisp like syntax. For example:
<entry>
<title>a</title>
<id>b</id>
<updated>2009-01-24T20:39:02-08:00</updated>
<summary>c...</summary>
<link rel="alternate" href="xyz"/>
</entry>
could simply be:
(entry
(title a)
(id b)
(updated 2009-01-24T20:39:02-08:00)
(summary c...)
(link rel:alternate href:xyz)
)
this would be clearly superior. (any tech problem, such as easy
conflict of data string with the demilitor, can be easily mended by
several ways. (e.g. JSON, due to javascript and xml influence, is a
format similar to the above))
However, consider the social and historical factor, things just
happened the way they happened. In retrospect, one can always spot
lots flaws that seems obvious.
In regard to your idea, i think similar reason apply. Sure, your DL
may be superior. The world doesn't know about it, and probably doesn't
need it. Unless, perhaps you started a movement, and if successful,
than perhaps all future graphics data will be in DL, and you write a
page of history.
On the subject of graphics format... here's some of my grievances. I
always hated OpenGL. The incomprehensible, low level, hardware based,
speed oriented, C unix style type of shit. I wanted a high level
graphics lang.
Around 1995, Apple tried to do something about it. The result is
http://en.wikipedia.org/wiki/QuickDraw3D
and subsequently, SGI, HP, Microsoft followed with
http://en.wikipedia.org/wiki/Fahrenheit_graphics_API
for complex social reasons (Apple was in the verge of bankruptcy;
fighting among the corporations) history be what it is, these fall off
the planet earth. We are stuck with the fucking “free & OpenSoure”
OpenGL garbage, and DirectX low level fuck.
• Graphics Programing Pains
http://xahlee.org/3d/graphics_programing_pain.html
You might also be interested in:
• Requirements For A Visualization Software System For 2020
http://xahlee.org/3d/viz.html
Xah
∑ http://xahlee.org/
☄
Thant Tessman
[...]
> things that happen in the industry or academia has a strong, not
> neglect-able social causes. It might be obvious, that some language X,
> protocols Y, etc, is clearly technically superior, yet nobody seems to
> thought of it, invented it, or use it, while the industry and everyone
> is using or talking about Z and its variants. If one puts social
> aspects into this equation, many such mystery dissolves.
This is indeed the conclusion I have come to. It's just that XML is SO
horrible I was trying to get folks to play devil's advocate in case I
was missing something.
> On the subject of graphics format... here's some of my grievances. I
> always hated OpenGL. The incomprehensible, low level, hardware based,
> speed oriented, C unix style type of shit. I wanted a high level
> graphics lang.
Welcome to my world.
Thanks for the references. I'll check them out.
-thant
Jon Harrop
> Xah Lee wrote:
>> On the subject of graphics format... here's some of my grievances. I
>> always hated OpenGL. The incomprehensible, low level, hardware based,
>> speed oriented, C unix style type of shit. I wanted a high level
>> graphics lang.
>
> Welcome to my world.
If you're after high-level easy-to-use graphics libraries then you will
appreciate my work, although it is commercial and mostly Windows only.
Smoke is a library for high-performance 2D vector graphics that is based
upon OpenGL:
http://www.ffconsultancy.com/products/smoke_vector_graphics/?clfl
F# for Visualization is a more evolved form of Smoke rewritten from scratch
to use Microsoft's Windows Presentation Foundation (WPF) instead of OpenGL
and with 3D support as well:
http://www.ffconsultancy.com/products/fsharp_for_visualization/?clfl
In both cases, the interfaces were designed to be declarative. Smoke is more
hardcore, featuring a lot more complexity and vastly better performance. F#
for Visualization focuses on a broad range of features ideal for
interactive technical computing (inspired by Mathematica) but can also be
used as WPF controls embedded in users' own GUI programs.
Modern functional programming languages excel at all aspects of these
applications, most notably interactive technical computing. For example, F#
makes our visualization software run 20x faster than the equivalent
Mathematica because F# is JIT compiled to native code. The ability to embed
our graphics in Windows applications at no extra cost obviously adds value
to our libraries.
F# is unquestionably better suited to such applications than any existing
FPL implementation in the open source world. Hopefully this will be
addressed in the future through the creation of an open source equivalent
to the CLR and robustly deployable graphics libraries like WPF but, until
then, Windows has no competition here.
Kenneth Tilton
> Thant Tessman wrote:
>> Xah Lee wrote:
>>> On the subject of graphics format... here's some of my grievances. I
>>> always hated OpenGL. The incomprehensible, low level, hardware based,
>>> speed oriented, C unix style type of shit. I wanted a high level
>>> graphics lang.
>> Welcome to my world.
>
> If you're after high-level easy-to-use graphics libraries then you will
> appreciate my work, although it is commercial and mostly Windows only.
What a genius. His Amphibitude takes two great things (3D and
portability) and transforms it into propietary and flat. Reminds me of
people who take the cool dynamic functional paradigm and turn them into
languages with static... oh, OK.
kth
Shyamal Prasad
Jon> Shyamal Prasad wrote:
Jon> I have also heard that the complexity of getting the text for
Jon> a branch of XML can be proportional to the size of the entire
Jon> document.
>>
>> As I understand it, the W3C DOM specification for XML has
>> resulted in some very poor implementations that do have this
>> problem (if I'm wrong about the specificaion being the cause I
>> would love to be corrected). But it's not inherent in XML;
Jon> Hmm, I'm not quite sure what you mean here. Do you mean a
Jon> different XML could have been cleanly designed without the
Jon> horrors of Schemas and so forth?
Nope - I was just addressing your concern above. Many XML libraries
were designed to use the W3C DOM API. This Api specifies that each
element in the tree can be interrogated to determine which XML
"Document" it belongs to, and also find any element's siblings.
This interface often results in implementations that make operations
on a branch of the XML document run in time "proportional to the size
of the entire [sub tree]". (Not necessarily proportional to the "entire
document" as you wrote, but I can see how an an implementation might
end up that way).
The DOM structure (AFAIK) was motivated by the desire to help
standardize browser environments. It can make sharing structure
between, or moving subtrees between, documents relatively inefficient.
Jon> AFAIK, I would not even categorize XSLT as a parsing tool at
Jon> all: I thought it was a tree rewriter?
Yes, it is a tree rewriter, but it is also a side effect free, domain
specific, programming language with pattern matching well suited to
dealing with XML constructs.
Cheers!
Shyamal
Xah Lee
yeah?
you know that one line of mathematica equals to about ten thousand
lines of F#, right?
are you aware, that you can solve differential equations, algebraic
equations, symbolic logic equations, transcendental equations, all in
one line in Mathematica, right?
you are aware that Mathematica can do typesetting of any 2D math
notation on the fly, right?
now, in scientific visualization, often you need to solve equations
with your data. So, Mathematica lets you do that with few lines and
few more lines gives you interactive dynamic visualization with
buttons and sliders. So what the fuck you?
I gave a few problems for the graphics world for the next 10 years:
• Requirements For A Visualization Software System For 2020
http://xahlee.org/3d/viz.html
why don't you try to write a functional 3D library to solve this
problem?
Xah
∑ http://xahlee.org/
☄
java...@gmail.com
> $$$
YOU SHALL NOT DO WORK ON SUNDAYS.
YOU HAVE 6 (SIX) DAYS TO EARN YOUR LIVING.
OTHERWISE THE LORD HIMSELF WILL VISIT YOU UNEXPECTEDLY AND DESTROY ALL
OF YOUR BANK ACCOUNTS.
YES, HE WILL DO SO, ONE DAY (BUT MOSTLY THE OTHER).
Oh, sorry, wrong list, wrong day, wrong recipient(s)...
Oh, sorry for the sorry: right list, right day, right recipient(s)!!!
Jon Harrop
> On Jan 25, 7:49 am, Jon Harrop <j...@ffconsultancy.com> wrote.
>
> yeah?
>
> you know that one line of mathematica equals to about ten thousand
> lines of F#, right?
Apparently you did not learn your lesson after you failed my ray tracer
challenge.
> are you aware, that you can solve differential equations, algebraic
> equations, symbolic logic equations, transcendental equations, all in
> one line in Mathematica, right?
F# has the TPL for parallel programming, PLINQ for database querying, XNA
for GPU programming and WPF for GUI programming. Mathematica 7 is nowhere
near providing that level of functionality.
> you are aware that Mathematica can do typesetting of any 2D math
> notation on the fly, right?
So does F# for Visualization.
> now, in scientific visualization, often you need to solve equations
> with your data.
I often need to do intensive numerical computations for which Mathematica is
far too slow. Also, I want correct answers and Mathematica is extremely
buggy.
> So, Mathematica lets you do that with few lines and
> few more lines gives you interactive dynamic visualization with
> buttons and sliders.
So does F# for Visualization.
> I gave a few problems for the graphics world for the next 10 years:
>
> • Requirements For A Visualization Software System For 2020
> http://xahlee.org/3d/viz.html
>
> why don't you try to write a functional 3D library to solve this
> problem?
I already did.
Kaz Kylheku
> On Jan 25, 7:49 am, Jon Harrop <j...@ffconsultancy.com> wrote.
>
> yeah?
>
> you know that one line of mathematica equals to about ten thousand
> lines of F#, right?
That's can only be true if the Mathematica programmer gets the advantage
of choosing the one line, not if the F# programmer gets the advantage of
choosing the ten thousand lines. :)
Xah Lee
http://wolfram.com/products/mathematica/newin7/
Xah
∑ http://xahlee.org/
☄
