simple n-ary tree (long)

[mnicolet <mnicolet@...>]

I learned lots from the lua community. I am a beginner, and every day I can
uncover another powerful way of lua usage. Great work of the lua team !!!
It's like I must contribute this to the list.

The problem:
Frequently I face the problem of exceptions to 'ruled' behaviour.
An example may help:
In a given system, a given entity ( A ) associates an estimated attribute,
which is taken from a reference entity ( R ). Example migth be a delivery
expense, which migth be determined by the selected carrier, and the
distance.
But there could be some exceptions, which migth depend on some other
attributes of entity A ( or another joined entity ).
The exceptions are of such nature that they depends on different
subsets of the A attributes. Following the example, the exception may depend
sometimes on the customer, sometimes on the article being sold, sometimes on
another one and finally, on some specific, arbitrary, combination of those.
When this class of situations arise, there is no simple 'static data'
solution,
some conf language is required.
But the obvious approach ( write a function with lots of if/elseif/else
constructs ) is not very appealing, both because of verbosity ( which tends
to hide the condition paths ) and because there is a small window for
erroneous formulation ( think that the conf maintenance as a job done by a
non programmer clerk - or by a seasoned programmer ).
Viewing the whole thing, it's a subset of a programming language construct,
something I call an 'expression tree'.
In the past, I developed a generic library for such n-ary trees in C, but
it tends to be cumbersome, because lots of parsing chores are done again
and again ( with little variations ) and because the specific of a tree
usage is based on module globals ( callbacks and support data structures ).
I don't like it.

The idea:
So I turned to lua's data description capabilities.
First I tried a strict tree class based on a previous work from some lua
list
posting ( don't remember his name ). It's not a bad path.
But later I realized that what I was looking for could be achieved not going
further than a simple lua native table.
And also, that I could generalize enough a whole group of problems, to also
get a mini lua 'evaluation module', which can be feeded several different
'condition tables' and cope with all them.

The result:
A solution for a set of problems of mine, and a simple path or guideline
to solve other, similiar situations.

What it does:
Given a table, mainly estructured as duples, where every duple is formed
by a pair "attribute/value" and a 'terminal member' which at some level
furnishes a scalar value or equivalent function, and a 'dictionary' of
pairs 'attribute/value' representing some entity instance, checks every
entity attribute against a given 'level' of the first table, and when
the attribute value provided satisfies some condition ( if at all )
evaluates the 'terminal member', and if it is in turn a table, iterates
over it, etc, until all provided entity attributes are exhausted, or there
are no more paths to follow, or a true terminal has been found.
In fact, the 'condition table' behaves or can be seen like a n-ary tree,
because the 'terminal member' being a table represents another node, being
a scalar or function, it determines a leaf.

Only to fullfill some cases, every sub-tree may have a 'terminal only duple'
( one not providing an attribute/value pair ) which can be seen as an
'else' clause at that level.

One of the most interesting thing is that the 'dictionary' of entity
attributes must not follow any predefined order between them ( so freeing
someway the host program from draconian rules ) and that, if the condition
table allows it, not every entity dictionary must be 'complete', and
nevertheless some path will be found and honored.

Also, the example code module can see an attribute in the condition table
not only as a scalar ( string, in my example ) but also as a function
to which the value being evaluated is passed as an argument.

As a complementary idea, the example I'm posting uses a functor module
to setup the 'terminals' or leafs when they are functions,
so simplifying the conf maintenance by non programmers.

The main modules are
1) evalcond.lua
  table of routines for conditional evaluation, whose front end is
  eval.try( arg, value, table, tmem )
  where
    - arg is an argument 'dictionary' of the form { atribute, value }
    - value is the seed value, which may be changed after evaluation
    - table is the condition table to use
    - tmem is a string carrying the member name which denotes
      a 'terminal' or leaf entry in every 'duple'

  returns
  nil = no condition path found
  a number = some path was found, and the terminal member is itself a
             number or a function, and the seed value was manipulated
             by that function
  a string = some path was found, but the corresponding terminal member
             is a string, which is supposed to be further evaluated by the
             calling environment

2) evaltable.lua
   module which carries the condition table

Not required but useful:
3) evalfun.lua
  table of functors, to easy the construction of terminal functions

4) evaltest.lua
  test module ... which takes as arguments pairs att=value
  one of them, called 'value' is special, and is segregated from
  the table of arguments.

Note:
A) I cannot devise a pattern match thar correctly parses the decimal
   point from the arguments
   I tried "(%w+)%=(%w%.*%w) with no success
B) I am not sure regarding how good are two support functions
   from evalcode.lua
   eval.empty( )
   eval.terminal( )

Lua code follows

-------------------- evalcond.lua ----------------------


eval = {}

eval.terminal = function( t, m )
   if type( t ) == 'table' then
      if not m then
         m = "t"
      end
      local k, v
      local s = 0
      for k, v in pairs( t ) do
         s = s + 1
      end
      if s == 1 and t[ m ] then
         return t[ m ]
      end
   end
   return nil
end

eval.empty = function( t )
   if type( t ) == 'table' then
      local k, v
      local s = 0
      for k, v in pairs( t ) do
         s = s + 1
      end
      if s == 0 then
         return s
      end
   end
   return nil
end

eval.hasterminal = function( t, m )
   if type( t ) == 'table' then
      local k, v
      for k, v in pairs( t ) do
         q = eval.terminal( v, m )
         if q then
            return q
         end
      end
   end
   return nil
end



eval.get = function( table, field, value )
   local k, v
   local f
--   printid( "Get:", table )
   for k, v in pairs( table ) do
      if type( v ) == 'table' then
         f = v[ field ]
         if f then
            if type( f ) == 'function' then
               if f( value ) then
                  return v end
            elseif type( f ) == 'string' then
               if string.find( value, f ) then
                  return v end
            end
         end
      end
   end
end

eval.evalret = function( arg, value, c, tmem )
   local ct = type( c )
   if ct == 'table' then
      return eval.try( arg, value, c, tmem )
   elseif ct == 'function' then
      return c( value )
   else
      return c
   end
end


eval.try = function( arg, value, table, tmem )
   local k, v
   local s
   local c
   local ct
   if eval.empty( arg ) then
      local t = eval.hasterminal( table, tmem )
      if t then
--       print( "Has terminal" )
         return eval.evalret( arg, value, t, tmem )
--      else
--         print( "Don't has term" )
      end
   end
   for k, v in pairs( arg ) do
       s = eval.get( table, k, v )
       if s then
          arg[ k ] = nil
          if type( s ) == 'table' then
             c = s[ tmem ]
             ct = eval.evalret( arg, value, c, tmem )
             if ct then
                return ct
             end
          end
       end
   end
   v = eval.terminal( table, tmem )
   if v then
--      print( "Try: terminal" )
      return v
   end
end

-------------------- evaltable.lua ----------------------

evaltable = {
     {
       at1 = function( v )
             if v == "PKD" or v == "PKT" then
                return v else return nil end
             end,

        c = {
               { at2 = "PLP",
                 c = {
                       { at3 = "P91", c = 7.75,  },
                       { c = 6.75,  },
                     },
               },
               { at2 = "PLF", c = 7.55,  },
               { at2 = "...",
                 c = {
                       { at3 = "S/P", c = evf.gpls( 10 ), },
                       { at3 = "C/P", c = evf.gmin( 20 ), },
                       { at3 = "...", c = evf.gmul( 0.5 ), },
                       { c = 0.25 },
                     },
               },
            },
     },
     {
       at1 = "P%w%w",
       c = {
              { at2 = "STC", c = 1,  },
              { at2 = "SAF", c = 0.75,  },
              { at2 = "PLP", c = 0.60,  },
              { at2 = "PLU", c = "do as you like" },
           },
     },
     {
       at1 = "M%w%w", c = 5,
     },
     { c = 15.5678 },
}

-------------------- evalfun.lua ----------------------

-- functors with upvalues

evf = {}

evf.gmul = function( mul )
      local f
      f = function( raw )
            return mul * raw
         end
      return f
end

evf.gpls = function( mul )
      local f
      f = function( raw )
          return raw * ( 1 + mul / 100 )
      end
      return f
end

evf.gmin = function( mul )
      local f
      f = function( raw )
          return raw * ( 1 - mul / 100 )
      end
      return f
end

evf.gvalued = function( getv )
      local f
      f = function( raw )
          if getv then
             return raw * getv( )
          else
             return raw
          end
      end
      return f
end

--[[ test code
function bytwo( )
    return 2
end

gnda = eval.gvalued( bytwo )
gndb = eval.gvalued( )

a = 5
print( "gnda", a, gnda( a ) )
print( "gndb", a, gndb( a ) )
]]

--[[ test code
gnd1 = gmul( 1.2 )
gnd2 = gpls( 21.00 )
gnd3 = gmin( 21.00 )

a = 2
print( "gnd1", a, gnd1( a ) )
print( "gnd2", a, gnd2( a ) )
print( "gnd3", a, gnd3( a ) )
]]


-------------------- evaltest.lua ----------------------

dofile( "evalfun.lua" )
dofile( "evalcond.lua" )
dofile( "evaltable.lua" )


function fromarg( args )
    local k, v
    local K, V
    local kp, vp
    local a = {}
    local q = {}
    local val
    local res
    for k, v in pairs( args ) do
       kp = string.find( v, "=" )
       if not kp then
          break
       end
       K = string.sub( v, 1, kp - 1 )
       V = string.sub( v, kp + 1, string.len( v ) )
       print( K, V )
       a[ K ] = V
       table.insert( q, V )
    end
    if a[ "value" ] then
       val = a[ "value" ]
       a[ "value" ] = nil
    end
    r = eval.try( a, val, evaltable, "c" )
    if ( r ) then
       print( table.concat( q, "," ), "=", r )
    else
       print( table.concat( q, ":" ), "no res" )
    end
end

fromarg( arg )