Dynamic functions

Dynamic functions

[Poul-Erik Andreasen]

How is the best way to make a representation of a
function/algorithm wich can bee setup at runtime in Ada.

Let say i have for instans a function/algorithm looking like this

F(x,y,z) = (3x+25**y)/z

This will ofcource require a parser to do the setup, that I can handle.
But what will bee the best structure for such generalised function.

I am thinking about some base functions and a tree struture with some
access to function variables. Anyone with a better idea?

Due to peformance consideration i cannot let the parser calculate the 
result imidialty.

Any hints will bee very appreciated


Poul-Erik Andreasen

Re: Dynamic functions

[Georg Bauhaus]

On Thu, 2007-08-09 at 18:06 +0200, Poul-Erik Andreasen wrote:
> How is the best way to make a representation of a
> function/algorithm wich can bee setup at runtime in Ada.

Maybe not the best, but perhaps the easiest way is to embed
one of the available interpreters or compilers for run-time
evaluated source code.

Re: Dynamic functions

[Poul-Erik Andreasen]

Georg Bauhaus wrote:
> On Thu, 2007-08-09 at 18:06 +0200, Poul-Erik Andreasen wrote:
>> How is the best way to make a representation of a
>> function/algorithm wich can bee setup at runtime in Ada.
> 
> Maybe not the best, but perhaps the easiest way is to embed
> one of the available interpreters or compilers for run-time
> evaluated source code.
> 
> 
I have been considering Lua, but i am afraid that i sometime in the
future will regret it due to performance, then i will stand with a
lot of waisted work.


Poul-Erik

Re: Dynamic functions

[Dmitry A. Kazakov]

On Thu, 09 Aug 2007 18:06:23 +0200, Poul-Erik Andreasen wrote:

> How is the best way to make a representation of a
> function/algorithm wich can bee setup at runtime in Ada.
> 
> Let say i have for instans a function/algorithm looking like this
> 
> F(x,y,z) = (3x+25**y)/z
> 
> This will ofcource require a parser to do the setup, that I can handle.
> But what will bee the best structure for such generalised function.

You have to decide whether you want native or interpretable code. The
former could be a little bit complex. The latter is much simpler, it could
be some sort of reverse polish notation.

> I am thinking about some base functions and a tree struture with some
> access to function variables. Anyone with a better idea?

Tree is only needed if you wanted a full blown compiler with some complex
semantic analysis phase. In your case simple stack would suffice:

3, x, *, 25, y, **, +, z, /

Operands can be kept in a separate storage, organized, again as a stack,
maybe split into several stacks one per operand's type/size. If you know
the element size, stack could be implemented more efficiently. Access to
function for operators is OK, if you don't need to store or else marshal
the code. Otherwise you would need OP-codes instead.

> Due to peformance consideration i cannot let the parser calculate the 
> result imidialty.

Yes, you parse into interpretable code as most interpreters do. You can
take a look at examples:

http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc

Where they evaluate an expression or generate a parsing tree for it, you
just generate the code as above by pushing the operand or operation on the
stack(s). Interpretation is trivial: if an operand then push it onto the
working stack (or a reference to the operand), if an operation, call to it,
pop all its n operands from the working stack,  push the result back,
repeat ad infinitum.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Dynamic functions

[Poul-Erik Andreasen]

Dmitry A. Kazakov wrote:
> On Thu, 09 Aug 2007 18:06:23 +0200, Poul-Erik Andreasen wrote:
> 
>> How is the best way to make a representation of a
>> function/algorithm wich can bee setup at runtime in Ada.
>>
>> Let say i have for instans a function/algorithm looking like this
>>
>> F(x,y,z) = (3x+25**y)/z
>>
>> This will ofcource require a parser to do the setup, that I can handle.
>> But what will bee the best structure for such generalised function.
> 
> You have to decide whether you want native or interpretable code. The
> former could be a little bit complex. The latter is much simpler, it could
> be some sort of reverse polish notation.
> 
>> I am thinking about some base functions and a tree struture with some
>> access to function variables. Anyone with a better idea?
> 
> Tree is only needed if you wanted a full blown compiler with some complex
> semantic analysis phase. In your case simple stack would suffice:
> 
> 3, x, *, 25, y, **, +, z, /

This is just an simplified example, things will bee a lot more
complicated
> 
> Operands can be kept in a separate storage, organized, again as a stack,
> maybe split into several stacks one per operand's type/size. If you know
> the element size, stack could be implemented more efficiently. Access to
> function for operators is OK, if you don't need to store or else marshal
> the code. Otherwise you would need OP-codes instead.
> 
>> Due to peformance consideration i cannot let the parser calculate the 
>> result imidialty.
> 
> Yes, you parse into interpretable code as most interpreters do. You can
> take a look at examples:
> 
> http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc
> 
> Where they evaluate an expression or generate a parsing tree for it, you
> just generate the code as above by pushing the operand or operation on the
> stack(s). Interpretation is trivial: if an operand then push it onto the
> working stack (or a reference to the operand), if an operation, call to it,
> pop all its n operands from the working stack,  push the result back,
> repeat ad infinitum.
> 

Thanks, I will take a look at that.


Poul-Erik

Re: Dynamic functions

[Dmitry A. Kazakov]

On Thu, 09 Aug 2007 20:17:21 +0200, Poul-Erik Andreasen wrote:

>> 3, x, *, 25, y, **, +, z, /
> 
> This is just an simplified example, things will bee a lot more
> complicated

Add "program counter" for jumps and you will be able to represent flow
control as well.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Dynamic functions

[Jacob Sparre Andersen]

Poul-Erik Andreasen wrote:

> How is the best way to make a representation of a function/algorithm
> wich can bee setup at runtime in Ada.

Is there any reason that you cannot convert the function to Ada, write
it to a file, compile it to a plug-in/DLL/shared library, and then
load the plug-in/DLL/shared library?

The complication is that it requires an Ada compiler on the running
system, but the benefit is pretty fast execution.

Greetings,

Jacob
-- 
The secret is to bang the rocks together.

Re: Dynamic functions

[Dmitry A. Kazakov]

On Fri, 10 Aug 2007 08:54:57 +0200, in comp.lang.ada you wrote:

> Poul-Erik Andreasen wrote:
> 
>> How is the best way to make a representation of a function/algorithm
>> wich can bee setup at runtime in Ada.
> 
> Is there any reason that you cannot convert the function to Ada, write
> it to a file, compile it to a plug-in/DLL/shared library, and then
> load the plug-in/DLL/shared library?

Yup, this is how MatLab and many other similar languages do, if you really
need to *program* (as opposed to draw (:-))  something...
 
> The complication is that it requires an Ada compiler on the running
> system, but the benefit is pretty fast execution.

?

Execution includes elaboration of the code. In your case elaboration would
mean to call the compiler, to link the DLL, to load the DLL. How frequent
the given function F will be called per run? If you are not going to design
some image rendering/processing system with millions of calls per function,
it probably will not pay off.

Other potential issues:

1. You will need a lot of free system resources to be able to run the
compiler/linker in parallel to your program, free memory and disk space.

2. The response time (from request to execute F to its start) will be
awful.

3. You will need to manage files (lots of) and other environmental stuff.
Deployment, integration etc might turn difficult.

4. DLL interface does not know Ada. Exporting complex data types and
objects of from a dynamically loaded DLL could be difficult.

5. DLL handling stuff is non-portable.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Dynamic functions

[Poul-Erik Andreasen]

Dmitry A. Kazakov wrote:
> On Fri, 10 Aug 2007 08:54:57 +0200, in comp.lang.ada you wrote:
> 
>> Poul-Erik Andreasen wrote:
>>
>>> How is the best way to make a representation of a function/algorithm
>>> wich can bee setup at runtime in Ada.
>> Is there any reason that you cannot convert the function to Ada, write
>> it to a file, compile it to a plug-in/DLL/shared library, and then
>> load the plug-in/DLL/shared library?
> 
> Yup, this is how MatLab and many other similar languages do, if you really
> need to *program* (as opposed to draw (:-))  something...
>  
>> The complication is that it requires an Ada compiler on the running
>> system, but the benefit is pretty fast execution.
> 
> ?
> 
> Execution includes elaboration of the code. In your case elaboration would
> mean to call the compiler, to link the DLL, to load the DLL. How frequent
> the given function F will be called per run? If you are not going to design
> some image rendering/processing system with millions of calls per function,
> it probably will not pay off.

In my case wee are in fact talking about  several million calls per 
function. Jacob have bee proposing this model to me before, but i find i 
a bit to cumbersome. By the way it is not images it is timeseries

> Other potential issues:
> 
> 1. You will need a lot of free system resources to be able to run the
> compiler/linker in parallel to your program, free memory and disk space.
> 
> 2. The response time (from request to execute F to its start) will be
> awful.
> 
> 3. You will need to manage files (lots of) and other environmental stuff.
> Deployment, integration etc might turn difficult.

This is my main issue
> 
> 4. DLL interface does not know Ada. Exporting complex data types and
> objects of from a dynamically loaded DLL could be difficult.
> 
> 5. DLL handling stuff is non-portable.
> 
This could also become an issue.

Re: Dynamic functions

[Dmitry A. Kazakov]

On Fri, 10 Aug 2007 16:59:45 +0200, Poul-Erik Andreasen wrote:

>> Execution includes elaboration of the code. In your case elaboration would
>> mean to call the compiler, to link the DLL, to load the DLL. How frequent
>> the given function F will be called per run? If you are not going to design
>> some image rendering/processing system with millions of calls per function,
>> it probably will not pay off.
> 
> In my case wee are in fact talking about  several million calls per 
> function. Jacob have bee proposing this model to me before, but i find i 
> a bit to cumbersome. By the way it is not images it is timeseries

I see, it is basically same pattern.

But if you have many small functions to call over a large grid of data, the
function call overhead becomes a problem on all those pipelined processors
with cache etc. I guess that you could give a try to dense interpretable
code. In end effect it might turn faster than calls to compiled subprograms
from a DLL.

As a guess, there is a third variant. You can try to pass the data
container to a DLL subprogram rather than individual elements of. Instead
of passing a function to some iterator, you can pass the iterator to the
function. I.e. you could try to vectorize your elementary operations. This
might be hard or impossible, though.

It looks quite interesting.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de