Optimizing a quadratic equation solver in OCaml]

On Friday 09 June 2006 02:20, you wrote:
> For some reason, this message couldn't go to your your
cam.ac.uk address...

My fault. I graduated and left two years ago... 

> Okay, so I must be misunderstanding variants
fundamentally.  I'll  compare
> an OO design with a variant design.  Please let me know
where I  go wrong:
>
> So for this particular raytracer, let's say we have
shapes, aggregates,
> and primitives.  Shapes are geometric objects (sphere,
cylinder,
> triangle mesh, etc.),

type shape =
  | Sphere of ...
  | Cylinder of ...
  | TriangleMesh of ...

> aggregates are accelerators (grid, k-d tree,  etc.),

type aggregate =
  | Grid of ...
  | KDTree of ...

> and primitives are objects which either: 1) can be
intersected  with a ray
> and returns information about the intersection (point
of  intersection,
> color, surface normal, etc.), 2) can be decomposed into
 other primitives 
> (e.g., a triangle mesh shape can be decomposed into 
triangle shapes, and
> the corresponding triangle mesh primitive can be 
decomposed into triangle
> primitives). A shape + a material type is a  primitive.
 An aggregate is 
> a primitive.

type primitive =
  | Shape of shape * material
  | Aggregate of aggregate
  | Compound of primitive * primitive list

> The OO way to design this would be to have an abstract
Shape class that
> has a method canIntersect() which returns true if the
shape can be
> intersected and false otherwise.   Intersect(ray) would
return a point  of
> intersection, if it exists.  Refine() would return a
list of other
> shapes.  Calling Intersect() if canIntersect() is false
or Refine() if
> canIntersect() is true would result in a run-time
error.

You can probably eliminate those run-time errors (and
checks!) in OCaml by 
leveraging the type system.

let intersect ray = function
  | Shape(shape, _) -> intersect_shape ray shape
  | Aggregate agg -> intersects ray agg
  | Compound(h, t) -> fold (intersect ray) t (intersect
ray h)

> A Primitive would be just like Shape, except
Intersect() would return
> more information than just the point of intersection.

Sounds like you might need a variant type to represent
different kinds of 
intersection result too.

> Refine() would 
> also return a list of primitives instead of a list of
shapes.

The "Refine" function would become part of the
pattern match for entities that 
cannot be intersected.

> A 
> GeometricPrimitive class would inherit from Primitive
and take a Shape  in
> its constructor (and other stuff, like materials,
etc.).

You could either nest the variant types or you could flatten
them out (as I 
did above - Shape and Aggregate appear at the same level as
Compound.

> An Aggregate would simply inherit from Primitive.  An
accelerator (k-d
> tree or whatever) would take in a list of Primitives
and use bounding  box
> information (another Primitive abstract method) to
build the
> necessary data structure.  Calling Intersect() on an
Aggregate would
> cause it to traverse its data structure, intersecting
Primitives along
> the way, and return the closest intersection.

In OCaml, calling the "intersect" function with
a primitive that happened to 
be an aggregate would invoke the corresponding pattern match
and recurse into 
the components of the aggregate.

> The main loop of the raytracer would look something
like this in
> OCaml-like pseudocode, assuming world is an primitive
containing all
> other primitives inside it (probably an accelerator):
>
> for ray in ... do
>   let intersection = world#intersect ray in
>     match Some (point, color ...) with -> ...
>     _ -> ()
> done

No objects. So "world#intersect" becomes
"intersect world":

for ... do
  match intersect ray world with
    | None -> ()
    | Some (point, color, ...) ->
        ...
done;

> The code to load a shape from a config file, assuming
"type" is a parsed
> string representing the desired shape type
("sphere", "triangle_mesh",
> etc.) and "params" is a parsed data
structure to be passed in to a
> create() method in the module (which would call the
constructor with
> items in "params"):
>
> let shape_module = load_module (type ^
".cmx") in
>   let shape = shape_module.create params  in
>     DynArray.append shapes shape
>
> However, OCaml doesn't yet support dynamically
loadable modules in  native
> code, so currently it looks more like this:
>
> let shape =
> match type with
>
> | "sphere" -> Sphere.create params
> | "cylinder" -> Cylinder.create params

You should probably use ocamlyacc for parsing such files.

> ...
> in
>   DynArray.append shapes shape

I'd use shape::shapes.

> But this is a limitation of the implementation and not
of OCaml's design.
>
> A design using variants would have "type Shape =
Sphere of ... |
> Cylinder of ...", and each module Sphere,
Cylinder, would have the same
> methods (intersect, refine, etc.).  It would also have
"type Accel = 
> GridAccel of ... | KDTree of ..." and "type
Primitive = GeomPrimitive of
> ... | Aggregate of ...".
>
> The outer loop would look like:
>
> for ray in ... do
>   let intersection =
>     match world with
>
>       | GridAccel ga -> GridAccel.intersect ray
>       | KDTree ga -> KDTree.intersect ray
>
>   ...
>   _ -> ()
> done

I don't understand this. Surely "world" is
invariant in that loop, in which 
case why are you pattern matching over it inside the loop?
Secondly, I 
thought the point was that these "aggregates"
can be nested in a tree?

> The code to load from a file would look similar, except
even if OCaml  had
> dynamically loadable modules, it would still need a
match statement.

Just use rules in a grammar. You'll have different
parameters for different 
shapes anyway, so you need to write the code at some point.


> One of the major touted benefits of the OO design is
that you have to
> write the raytracing loop and the load-from-file method
*once* and yet
> still be able to add shape, primitive, and accelerator
types.  With the
> variant design, every time you add a new shape, you'd
have to hunt down
> every match statement on a shape and add a handler. 
The match statement
> in the raytracing loop would essentially be boilerplate
code.

Swings and roundabouts. OOP groups by type (class) and ML
groups by function. 
ML provides exhaustiveness and redundancy checking over
pattern matches. OOP 
only provides some redundancy checking (i.e. cannot
instantiate abstract 
class). Haskell provides "views" which give the
benefits of both worlds, 
apparently.

> Also, if objects are so rarely used in OCaml, why is it
named Objective
> Caml? I thought the major feature that OCaml had over
other ML dialects 
> was the object system.

That is one of the major features. I value other features
(e.g. polymorphic 
variants) higher than OOP. I get the impression that the
OCaml developers 
were surprised at how little their object system gets used.

> Is it a case of variants and other features  being 
> more useful than the OO features?

Exactly. The alternatives are just better most of the time,
so OCaml 
programmers use them instead of objects.

> Thanks for your time and patience!  Once I figure out
how to make my
> raytracer more idiomatic OCaml, I'll probably post a
link to the code
> repository in the beginner's list so that other people
can hack on it.

Great, we'll look forward to it! I think you've got the
idea about using 
variants.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scient
ists


------------------------ Yahoo! Groups Sponsor
--------------------~--> 
Protect your PC from spy ware with award winning anti spy
technology. It's free.
http://us.click.yahoo.com/97bhrC/LGxNAA/yQLSAA/saFolB/TM

------------------------------------------------------------
--------~-> 

Archives up to August 22, 2005 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners/
The archives of the very official ocaml list (the seniors'
one) can be found at http://caml.inria.fr
Attachments are banned and you're asked to be polite, avoid
flames etc. 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http:/
/groups.yahoo.com/group/ocaml_beginners/

<*> To unsubscribe from this group, send an email to:
    ocaml_beginners-unsubscribe@yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.c
om/info/terms/
 

I understand most of your comments and it seems we're on
the same page.  
I have a few more questions/comments below:

Jon Harrop wrote:
> You should probably use ocamlyacc for parsing such
files.
>
>   
I'm already using ocamlyacc for parsing the files.  It's a
design 
decision of the config file format that pbrt uses that such
a switch 
statement is necessary (since it looks in a directory for
<Shape>.so and 
loads it in at runtime).  Although I may radically change
everything 
else, I'd like to have my program be able to read the files
that pbrt 
uses so that I can more easily compare the two versions (for

benchmarking, etc.).
>> for ray in ... do
>>   let intersection =
>>     match world with
>>
>>       | GridAccel ga -> GridAccel.intersect ray
>>       | KDTree ga -> KDTree.intersect ray
>>
>>   ...
>>   _ -> ()
>> done
>>     
>
> I don't understand this. Surely "world" is
invariant in that loop, in which 
> case why are you pattern matching over it inside the
loop? Secondly, I 
> thought the point was that these
"aggregates" can be nested in a tree?
>
>   
World *is* invariant in that loop, but the alternative would
be to have 
the for loop inside every pattern match statement.  In this
pseudocode, 
it's not such a big deal, but the "for ray in ...
do" stuff is a little 
more complex in real code.  I'm not sure if ocamlopt is
able lift the 
pattern match outside of the loop; I'd have to experiment
with it.  The 
aggregates can be nested in a tree, but the
"real" primitives are hidden 
inside "world", so the ray-tracing code can
pretend it's only 
intersecting a single primitive.
>> One of the major touted benefits of the OO design
is that you have to
>> write the raytracing loop and the load-from-file
method *once* and yet
>> still be able to add shape, primitive, and
accelerator types.  With the
>> variant design, every time you add a new shape,
you'd have to hunt down
>> every match statement on a shape and add a handler.
 The match statement
>> in the raytracing loop would essentially be
boilerplate code.
>>     
>
> Swings and roundabouts. OOP groups by type (class) and
ML groups by function. 
> ML provides exhaustiveness and redundancy checking over
pattern matches. OOP 
> only provides some redundancy checking (i.e. cannot
instantiate abstract 
> class). Haskell provides "views" which give
the benefits of both worlds, 
> apparently.
>   
Okay, so here's my fundamental concern.  ML groups by
function (each 
function (e.g., intersect) has to pattern-match on type) and
OOP groups 
by type (each class has to provide implementations for all
the 
functions).  Since from what I've read, OCaml is unlikely
to support 
dynamically loadable modules in native code anytime soon,
I'll probably 
write this raytracer in the ML style anyway.  But if OCaml
*did* support 
dynamically loadable modules, then ideally, someone would
write 
NewFangledShape.ml, compile it, drop in the .cmx file in a
directory, 
and have it "just work".  The OOP style fits
naturally with this, as 
it's already grouping by type.  However, the ML style
doesn't really 
fit, because the program would have to append "|
NewFangledShape nfs -> 
NewFangledShape.intersect ray" to the pattern-match
statement in the 
intersect method, and equivalent code for all the other
methods.  How 
would you implement this design constraint in ML? (again,
assuming 
modules were dynamically loadable)

Fred


------------------------ Yahoo! Groups Sponsor
--------------------~--> 
Everything you need is one click away.  Make Yahoo! your
home page now.
http://us.click.yahoo.com/AHchtC/4FxNAA/yQLSAA/saFolB/TM

------------------------------------------------------------
--------~-> 

Archives up to August 22, 2005 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners/
The archives of the very official ocaml list (the seniors'
one) can be found at http://caml.inria.fr
Attachments are banned and you're asked to be polite, avoid
flames etc. 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http:/
/groups.yahoo.com/group/ocaml_beginners/

<*> To unsubscribe from this group, send an email to:
    ocaml_beginners-unsubscribe@yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.c
om/info/terms/
 

> > The OO way to design this would be to have an
abstract Shape class that
> > has a method canIntersect() which returns true if
the shape can be
> > intersected and false otherwise.

I don't think so.  The existence of a hasProperty() type
function is a red-flag to tell you that your inheritance
heirarchy needs re-design.

http://www.parashift.com/c++-faq-lite/proper-inheri
tance.html



------------------------ Yahoo! Groups Sponsor
--------------------~--> 
You can search right from your browser? It's easy and it's
free.  See how.
http://us.click.yahoo.com/_7bhrC/NGxNAA/yQLSAA/saFolB/TM

------------------------------------------------------------
--------~-> 

Archives up to August 22, 2005 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners/
The archives of the very official ocaml list (the seniors'
one) can be found at http://caml.inria.fr
Attachments are banned and you're asked to be polite, avoid
flames etc. 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http:/
/groups.yahoo.com/group/ocaml_beginners/

<*> To unsubscribe from this group, send an email to:
    ocaml_beginners-unsubscribe@yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.c
om/info/terms/
 

On Friday 09 June 2006 04:24, Frederick Akalin wrote:
> I'm already using ocamlyacc for parsing the files. 
It's a design
> decision of the config file format that pbrt uses that
such a switch
> statement is necessary (since it looks in a directory
for <Shape>.so and
> loads it in at runtime).  Although I may radically
change everything
> else, I'd like to have my program be able to read the
files that pbrt
> uses so that I can more easily compare the two versions
(for
> benchmarking, etc.).

Sure. I may have misunderstood but can't the
"switch" occur inside the 
grammar?

> > I don't understand this. Surely
"world" is invariant in that loop, in
> > which case why are you pattern matching over it
inside the loop?
> > Secondly, I thought the point was that these
"aggregates" can be nested
> > in a tree?
>
> World *is* invariant in that loop, but the alternative
would be to have
> the for loop inside every pattern match statement.

No, that would be factored out into a higher-order function.
The pattern match 
would then return the function that was to be applied inside
that loop.

> In this pseudocode, 
> it's not such a big deal, but the "for ray in
... do" stuff is a little
> more complex in real code. I'm not sure if ocamlopt is
able lift the 
> pattern match outside of the loop; I'd have to
experiment with it.

Almost certainly not. It won't rearrange your code, e.g.
CSE.

> The 
> aggregates can be nested in a tree, but the
"real" primitives are hidden
> inside "world", so the ray-tracing code can
pretend it's only
> intersecting a single primitive.

Well, the ray tracing code is intersecting a ray with a
single node in a scene 
tree, exactly the same as in my ray tracer.

> Okay, so here's my fundamental concern.  ML groups by
function (each
> function (e.g., intersect) has to pattern-match on
type) and OOP groups
> by type (each class has to provide implementations for
all the
> functions).

Exactly, yes.

> Since from what I've read, OCaml is unlikely to
support 
> dynamically loadable modules in native code anytime
soon, I'll probably
> write this raytracer in the ML style anyway.  But if
OCaml *did* support
> dynamically loadable modules, then ideally, someone
would write
> NewFangledShape.ml, compile it, drop in the .cmx file
in a directory,
> and have it "just work".  The OOP style
fits naturally with this, as
> it's already grouping by type.  However, the ML style
doesn't really
> fit, because the program would have to append "|
NewFangledShape nfs ->
> NewFangledShape.intersect ray" to the
pattern-match statement in the
> intersect method, and equivalent code for all the other
methods.  How
> would you implement this design constraint in ML?
(again, assuming
> modules were dynamically loadable)

Firstly, this is a very odd requirement because compiling
the ray tracer will 
only take a couple of seconds and whole-program optimisation
will get you 
much better run-time performance.

Regardless, you could put your main pattern match in a
higher-order function 
that accepts a function to apply to any unknown shapes. Then
you use a 
polymorphic variant instead of an ordinary variant because
they are 
extensible (but slower to pattern match over) and voila. You
could make your 
code ray tracer a cmxa and compile in any new cmx files to
build a custom ray 
tracer. As I say, I don't think this would be useful in
practice because 
you'd just extend the ray tracer and recompile the whole
thing.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scient
ists


------------------------ Yahoo! Groups Sponsor
--------------------~--> 
Protect your PC from spy ware with award winning anti spy
technology. It's free.
http://us.click.yahoo.com/97bhrC/LGxNAA/yQLSAA/saFolB/TM

------------------------------------------------------------
--------~-> 

Archives up to August 22, 2005 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners/
The archives of the very official ocaml list (the seniors'
one) can be found at http://caml.inria.fr
Attachments are banned and you're asked to be polite, avoid
flames etc. 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http:/
/groups.yahoo.com/group/ocaml_beginners/

<*> To unsubscribe from this group, send an email to:
    ocaml_beginners-unsubscribe@yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.c
om/info/terms/
 

On Friday 09 June 2006 04:52, Jon Harrop wrote:
>
> That is one of the major features. I value other
features (e.g. polymorphic
> variants) higher than OOP. I get the impression that
the OCaml developers
> were surprised at how little their object system gets
used.

> ...

> Exactly. The alternatives are just better most of the
time, so OCaml
> programmers use them instead of objects.


that seems true, but I think that's because it's not that
easy to use (if you 
are used to c++ / java object system) and the syntax for
some constructs is 
*hmm* not easy too  


cheers,
 Michael



------------------------ Yahoo! Groups Sponsor
--------------------~--> 
Everything you need is one click away.  Make Yahoo! your
home page now.
http://us.click.yahoo.com/AHchtC/4FxNAA/yQLSAA/saFolB/TM

------------------------------------------------------------
--------~-> 

Archives up to August 22, 2005 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners/
The archives of the very official ocaml list (the seniors'
one) can be found at http://caml.inria.fr
Attachments are banned and you're asked to be polite, avoid
flames etc. 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http:/
/groups.yahoo.com/group/ocaml_beginners/

<*> To unsubscribe from this group, send an email to:
    ocaml_beginners-unsubscribe@yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.c
om/info/terms/
 

On Thu, Jun 08, 2006 at 08:24:05PM -0700, Frederick Akalin
wrote:
> Okay, so here's my fundamental concern.  ML groups by
function (each 
> function (e.g., intersect) has to pattern-match on
type) and OOP groups 
> by type (each class has to provide implementations for
all the 
> functions).  Since from what I've read, OCaml is
unlikely to support 
> dynamically loadable modules in native code anytime
soon, I'll probably 
> write this raytracer in the ML style anyway.  But if
OCaml *did* support 
> dynamically loadable modules, then ideally, someone
would write 
> NewFangledShape.ml, compile it, drop in the .cmx file
in a directory, 
> and have it "just work".  The OOP style
fits naturally with this, as 
> it's already grouping by type.  However, the ML style
doesn't really 
> fit, because the program would have to append "|
NewFangledShape nfs -> 
> NewFangledShape.intersect ray" to the
pattern-match statement in the 
[...]

OK, so this is a very good point about a big difference
between
ML-style languages and OOP languages.

In ML-style languages everything is type checked at compile
time,
which really assumes that all your source is around at
compile time
too.  In addition, ML programmers are used to
"breaking" code by, for
example, changing a structure or adding a case to a variant
type, and
then recompiling.  You allow the compiler to pick out all
the places
where the program needs to be updated; one of those will be
where you
need a new case ("| NewFangledShape nfs ->
...") in a match.  Once it
compiles without any errors or warnings, you know you've
fixed all the
places.

So, lack of dynamic loading aside (but see asmdynlink), the
ML-style
wants you to have all your code around, and wants you to
compile
everything into a big executable application.  Dropping
".so" (or
".cmx") files into directories at runtime isn't
part of that model.

I'm not sure how often your raytracer users actually drop
NewFangledShape.so into directories, but let's say this is
a
requirement.  There are a few possible ways to go in OCaml:

(1) Have a shell script which generates the match statements
and
recompiles the program based on the "extensions"
which it finds in a
directory.

(2) Write the extensions in a domain-specific language which
can be
loaded and interpreted at run time (probably a lot of work).

(3) Use something like asmdynlink.

(4) Use C modules with a bit of extension code to allow them
to be
loaded (using dlopen), and a tightly defined interface back
into the
OCaml code.

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com


------------------------ Yahoo! Groups Sponsor
--------------------~--> 
Protect your PC from spy ware with award winning anti spy
technology. It's free.
http://us.click.yahoo.com/97bhrC/LGxNAA/yQLSAA/saFolB/TM

------------------------------------------------------------
--------~-> 

Archives up to August 22, 2005 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners/
The archives of the very official ocaml list (the seniors'
one) can be found at http://caml.inria.fr
Attachments are banned and you're asked to be polite, avoid
flames etc. 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http:/
/groups.yahoo.com/group/ocaml_beginners/

<*> To unsubscribe from this group, send an email to:
    ocaml_beginners-unsubscribe@yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.c
om/info/terms/
 

In <20060609080045.GB22445furbychan.cocan.org>,
Richard Jones <richannexia.org> typed:
> (2) Write the extensions in a domain-specific language
which can be
> loaded and interpreted at run time (probably a lot of
work).

This is a fairly common thing in my circles, and isn't
considered a
lot of work. Except that writing a domain-specific language
is doing
it the hard way. Depending on the requirements, there are
number of
alternative solutions. In order of increasing work and
performance

1) Invoke an external progam, passing values as strings via
the
   command line, standard in, or the environment.

2) Use an RPC mechanism of some kind.

3) Use an extensible/embeddable interpreter, extended with
   domain-specific functionality and embedded into the
application.

The first two have the advantage that customers can write in
pretty
much any language they want to, at least if they can find an
appropriate RPC library. The downside is the hit you take
crossing the
boundary. The latter two have a fair amount of work if you
have to do
the ocaml interface yourself.

The last one is closest to what Richard suggested.
Basically, you
trade off the possibility of a domain-specific syntax
(unless you
embed a LISP system and write lots of reader macros, anyway)
for
getting the interpreter and the flow control mechanisms done
for you.

Combining the first two is the most flexible model. In this
model, you
"load a module" by launching an external
program, passing it the
information it needs to make RPC calls back to your
application. Advanced applications will also act as a
server,
exporting their services to other applications.

	<mike
-- 
Mike Meyer <mwmmired.org>		http://www.mired
.org/consulting.html
Independent Network/Unix/Perforce consultant, email for more
information.


------------------------ Yahoo! Groups Sponsor
--------------------~--> 
Home is just a click away.  Make Yahoo! your home page now.
http://us.click.yahoo.com/DHchtC/3FxNAA/yQLSAA/saFolB/TM

------------------------------------------------------------
--------~-> 

Archives up to August 22, 2005 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners/
The archives of the very official ocaml list (the seniors'
one) can be found at http://caml.inria.fr
Attachments are banned and you're asked to be polite, avoid
flames etc. 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http:/
/groups.yahoo.com/group/ocaml_beginners/

<*> To unsubscribe from this group, send an email to:
    ocaml_beginners-unsubscribe@yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.c
om/info/terms/