From: pTymN
Subject: DSL for converting functional to imperative
Date: 
Message-ID: <1160503870.513923.103410@h48g2000cwc.googlegroups.com>
Hello,

I'm using Corman Common Lisp 3.0 to write a 2D physics engine. Part of
the new release is a set of floating point operations that allow me to
do some math intensive computations for double precision floats without
consing. They are of the form:

(sys:dv/ divisor 0 dividend 0 quotient 0) ; divides divisor by dividend
and stores value in quotient

My program has become less readable, because now I have to give names
to intermediate results to my calculations. I'd like to find a way to
write the calculations in a functional style, and let macros do the
work of converting from functional to imperitive. Another approach that
I have thought about is just writing more helper functions that allow
me to at least reduce the imperitive approach's messiness by hiding
some of the common trig operations I use often. The problem is that
whether I use DSL or functions that do a higher level trig operation, I
lose the ability to reuse intermediate values. I have already gotton
the engine working, and I am in the optimization stages now.

So, given a sample function like this:


(defun test-triangle-point (p1 p2 p3 p)
    "fast triangle containment test for a point"
    (let ((edge (make-array 2 :element-type 'double-float))
          (normal (make-array 2 :element-type 'double-float))
          (dotProduct 0.0d0))

        ; Simple, creates fake normals for all three edges of
        ; triangle, then tests to see if dot product of point
        ; from edges and normals is the same all 3 times.
        (vector2d- p2 p1 edge)
        (vector2d-right edge normal)
        (vector2d- p p1 edge)
        (vector2d-dot edge normal dotProduct)
        (let ((last-result (sys:dv> dotProduct 0 0.0d0 0)))
            (vector2d- p3 p2 edge)
            (vector2d-right edge normal)
            (vector2d- p p2 edge)
            (vector2d-dot edge normal dotProduct)
            (when (eql last-result (sys:dv> dotProduct 0 0.0d0 0))
                (vector2d- p1 p3 edge)
                (vector2d-right edge normal)
                (vector2d- p p3 edge)
                (vector2d-dot edge normal dotProduct)
                (when (eql last-result (sys:dv> dotProduct 0 0.0d0 0))
                    T)))))


I'd like to be able to go back to something that resembles:

(defun test-triangle-point (p1 p2 p3 p)
    "fast triangle containment test for a point"
    (let* ((normal (vector2d-right (vector2d- p2 p1)))
           (dotProduct (vector2d-dot (vector2d- p p1) normal))
        (let ((last-result (sys:dv> dotProduct 0 0.0d0 0)))
...


I think that it'd also be fun to write a DSL for this, if that's a
reasonable way to go about things. I guess that a DSL would need a
macro that translates certain forms from a functional structure to
imperitive, find similar calculations and try to reuse intermediate
calculations, and somehow figure out what values are true return values
that need to be consed. Uh, can someone get me started here? Do I need
to wrap all the math expressions in a form that explicitly specifies
that everything in that block forms a set of calculations and
explicitly defines a return value from that block that can be used by
other logic? It'd be nice to be able to seamlessly insert my mathy DSL
right in with all the surrounding code. Thanks for any help anyone can
give me. I'm willing to do homework on this, so tell me what you want
from me if that will help you give me a clear set of steps to proceed
through this mess. Thanks ahead of time to anyone who is helpful!

From: Richard J. Fateman
Subject: Re: DSL for converting functional to imperative
Date: 
Message-ID: <452BE876.4090409@eecs.berkeley.edu>
You can look in http://www.cs.berkeley.edu/~fateman/generic

and look especially at the code in qd.lisp.
This includes macros dsetv and with-temps that take functional
programming style expressions like  (+ a (* b c))
and allocate temporaries and call imperative  (not imperitive) routines.

qd is "quad double" arithmetic.

For example,
(macroexpand '(dsetv a (+ b c)))

produces code
qd(24): (pprint (macroexpand '(dsetv a (+ b c))))

(let ((a1 (aqd-q b)) (a2 (aqd-q c)) (tt (aqd-q a)))
   (declare (optimize speed)
    (type (simple-array double-float (4)) a1 a2 tt))
   (qd_add a1 a2 tt)
   a)

;; this code is way simpler that the usual use I expect.

Note (aqd-q xxx) is the address of the quad-double array for xxx.
qd_add  takes 3 addresses and stores the result in tt, which is to say, 
the location for the value of a.

To make sense of this code you may need to read in packages and other 
stuff in that directory.  No guarantees.
Rjf



pTymN wrote:
> Hello,
> 
> I'm using Corman Common Lisp 3.0 to write a 2D physics engine. Part of
> the new release is a set of floating point operations that allow me to
> do some math intensive computations for double precision floats without
> consing. They are of the form:
> 
> (sys:dv/ divisor 0 dividend 0 quotient 0) ; divides divisor by dividend
> and stores value in quotient
> 
> My program has become less readable, because now I have to give names
> to intermediate results to my calculations. I'd like to find a way to
> write the calculations in a functional style, and let macros do the
> work of converting from functional to imperitive. Another approach that
> I have thought about is just writing more helper functions that allow
> me to at least reduce the imperitive approach's messiness by hiding
> some of the common trig operations I use often. The problem is that
> whether I use DSL or functions that do a higher level trig operation, I
> lose the ability to reuse intermediate values. I have already gotton
> the engine working, and I am in the optimization stages now.
> 
> So, given a sample function like this:
> 
> 
> (defun test-triangle-point (p1 p2 p3 p)
>     "fast triangle containment test for a point"
>     (let ((edge (make-array 2 :element-type 'double-float))
>           (normal (make-array 2 :element-type 'double-float))
>           (dotProduct 0.0d0))
> 
>         ; Simple, creates fake normals for all three edges of
>         ; triangle, then tests to see if dot product of point
>         ; from edges and normals is the same all 3 times.
>         (vector2d- p2 p1 edge)
>         (vector2d-right edge normal)
>         (vector2d- p p1 edge)
>         (vector2d-dot edge normal dotProduct)
>         (let ((last-result (sys:dv> dotProduct 0 0.0d0 0)))
>             (vector2d- p3 p2 edge)
>             (vector2d-right edge normal)
>             (vector2d- p p2 edge)
>             (vector2d-dot edge normal dotProduct)
>             (when (eql last-result (sys:dv> dotProduct 0 0.0d0 0))
>                 (vector2d- p1 p3 edge)
>                 (vector2d-right edge normal)
>                 (vector2d- p p3 edge)
>                 (vector2d-dot edge normal dotProduct)
>                 (when (eql last-result (sys:dv> dotProduct 0 0.0d0 0))
>                     T)))))
> 
> 
> I'd like to be able to go back to something that resembles:
> 
> (defun test-triangle-point (p1 p2 p3 p)
>     "fast triangle containment test for a point"
>     (let* ((normal (vector2d-right (vector2d- p2 p1)))
>            (dotProduct (vector2d-dot (vector2d- p p1) normal))
>         (let ((last-result (sys:dv> dotProduct 0 0.0d0 0)))
> ...
> 
> 
> I think that it'd also be fun to write a DSL for this, if that's a
> reasonable way to go about things. I guess that a DSL would need a
> macro that translates certain forms from a functional structure to
> imperitive, find similar calculations and try to reuse intermediate
> calculations, and somehow figure out what values are true return values
> that need to be consed. Uh, can someone get me started here? Do I need
> to wrap all the math expressions in a form that explicitly specifies
> that everything in that block forms a set of calculations and
> explicitly defines a return value from that block that can be used by
> other logic? It'd be nice to be able to seamlessly insert my mathy DSL
> right in with all the surrounding code. Thanks for any help anyone can
> give me. I'm willing to do homework on this, so tell me what you want
> from me if that will help you give me a clear set of steps to proceed
> through this mess. Thanks ahead of time to anyone who is helpful!
> 
From: pTymN
Subject: Re: DSL for converting functional to imperative
Date: 
Message-ID: <1160506935.438557.160230@i42g2000cwa.googlegroups.com>
wow! It looks like the work is pretty much done for me. This is a great
head start! Thanks Richard!

Richard J. Fateman wrote:
> You can look in http://www.cs.berkeley.edu/~fateman/generic
>
> and look especially at the code in qd.lisp.
> This includes macros dsetv and with-temps that take functional
> programming style expressions like  (+ a (* b c))
> and allocate temporaries and call imperative  (not imperitive) routines.
>
> qd is "quad double" arithmetic.
>
> For example,
> (macroexpand '(dsetv a (+ b c)))
>
> produces code
> qd(24): (pprint (macroexpand '(dsetv a (+ b c))))
>
> (let ((a1 (aqd-q b)) (a2 (aqd-q c)) (tt (aqd-q a)))
>    (declare (optimize speed)
>     (type (simple-array double-float (4)) a1 a2 tt))
>    (qd_add a1 a2 tt)
>    a)
>
> ;; this code is way simpler that the usual use I expect.
>
> Note (aqd-q xxx) is the address of the quad-double array for xxx.
> qd_add  takes 3 addresses and stores the result in tt, which is to say,
> the location for the value of a.
>
> To make sense of this code you may need to read in packages and other
> stuff in that directory.  No guarantees.
> Rjf
>
>
>
> pTymN wrote:
> > Hello,
> >
> > I'm using Corman Common Lisp 3.0 to write a 2D physics engine. Part of
> > the new release is a set of floating point operations that allow me to
> > do some math intensive computations for double precision floats without
> > consing. They are of the form:
> >
> > (sys:dv/ divisor 0 dividend 0 quotient 0) ; divides divisor by dividend
> > and stores value in quotient
> >
> > My program has become less readable, because now I have to give names
> > to intermediate results to my calculations. I'd like to find a way to
> > write the calculations in a functional style, and let macros do the
> > work of converting from functional to imperitive. Another approach that
> > I have thought about is just writing more helper functions that allow
> > me to at least reduce the imperitive approach's messiness by hiding
> > some of the common trig operations I use often. The problem is that
> > whether I use DSL or functions that do a higher level trig operation, I
> > lose the ability to reuse intermediate values. I have already gotton
> > the engine working, and I am in the optimization stages now.
> >
> > So, given a sample function like this:
> >
> >
> > (defun test-triangle-point (p1 p2 p3 p)
> >     "fast triangle containment test for a point"
> >     (let ((edge (make-array 2 :element-type 'double-float))
> >           (normal (make-array 2 :element-type 'double-float))
> >           (dotProduct 0.0d0))
> >
> >         ; Simple, creates fake normals for all three edges of
> >         ; triangle, then tests to see if dot product of point
> >         ; from edges and normals is the same all 3 times.
> >         (vector2d- p2 p1 edge)
> >         (vector2d-right edge normal)
> >         (vector2d- p p1 edge)
> >         (vector2d-dot edge normal dotProduct)
> >         (let ((last-result (sys:dv> dotProduct 0 0.0d0 0)))
> >             (vector2d- p3 p2 edge)
> >             (vector2d-right edge normal)
> >             (vector2d- p p2 edge)
> >             (vector2d-dot edge normal dotProduct)
> >             (when (eql last-result (sys:dv> dotProduct 0 0.0d0 0))
> >                 (vector2d- p1 p3 edge)
> >                 (vector2d-right edge normal)
> >                 (vector2d- p p3 edge)
> >                 (vector2d-dot edge normal dotProduct)
> >                 (when (eql last-result (sys:dv> dotProduct 0 0.0d0 0))
> >                     T)))))
> >
> >
> > I'd like to be able to go back to something that resembles:
> >
> > (defun test-triangle-point (p1 p2 p3 p)
> >     "fast triangle containment test for a point"
> >     (let* ((normal (vector2d-right (vector2d- p2 p1)))
> >            (dotProduct (vector2d-dot (vector2d- p p1) normal))
> >         (let ((last-result (sys:dv> dotProduct 0 0.0d0 0)))
> > ...
> >
> >
> > I think that it'd also be fun to write a DSL for this, if that's a
> > reasonable way to go about things. I guess that a DSL would need a
> > macro that translates certain forms from a functional structure to
> > imperitive, find similar calculations and try to reuse intermediate
> > calculations, and somehow figure out what values are true return values
> > that need to be consed. Uh, can someone get me started here? Do I need
> > to wrap all the math expressions in a form that explicitly specifies
> > that everything in that block forms a set of calculations and
> > explicitly defines a return value from that block that can be used by
> > other logic? It'd be nice to be able to seamlessly insert my mathy DSL
> > right in with all the surrounding code. Thanks for any help anyone can
> > give me. I'm willing to do homework on this, so tell me what you want
> > from me if that will help you give me a clear set of steps to proceed
> > through this mess. Thanks ahead of time to anyone who is helpful!
> >
From: ············@gmail.com
Subject: Re: DSL for converting functional to imperative
Date: 
Message-ID: <1160575839.268760.291640@m7g2000cwm.googlegroups.com>
pTymN wrote:
> wow! It looks like the work is pretty much done for me. This is a great
> head start! Thanks Richard!
>
> Richard J. Fateman wrote:
> > You can look in http://www.cs.berkeley.edu/~fateman/generic

It's good stuff.  I was all set to do the coding for it as a project in
his class, and then he whipped almost all of it out himself.  I think I
fixed a couple things in the code, but that's about it.

mfh