+ Penlight

1 files changed, 393 insertions, 0 deletions

diff --git a/Data/Libraries/Penlight/lua/pl/func.lua b/Data/Libraries/Penlight/lua/pl/func.lua
new file mode 100644
index 0000000..daac0fc
--- /dev/null
+++ b/Data/Libraries/Penlight/lua/pl/func.lua
@@ -0,0 +1,393 @@
+--- Functional helpers like composition, binding and placeholder expressions.
+-- Placeholder expressions are useful for short anonymous functions, and were
+-- inspired by the Boost Lambda library.
+--
+--    > utils.import 'pl.func'
+--    > ls = List{10,20,30}
+--    > = ls:map(_1+1)
+--    {11,21,31}
+--
+-- They can also be used to _bind_ particular arguments of a function.
+--
+--    > p = bind(print,'start>',_0)
+--    > p(10,20,30)
+--    > start>   10   20  30
+--
+-- See @{07-functional.md.Creating_Functions_from_Functions|the Guide}
+--
+-- Dependencies: `pl.utils`, `pl.tablex`
+-- @module pl.func
+local type,setmetatable,getmetatable,rawset = type,setmetatable,getmetatable,rawset
+local concat,append = table.concat,table.insert
+local tostring = tostring
+local utils = require 'pl.utils'
+local pairs,rawget,unpack,pack = pairs,rawget,utils.unpack,utils.pack
+local tablex = require 'pl.tablex'
+local map = tablex.map
+local _DEBUG = rawget(_G,'_DEBUG')
+local assert_arg = utils.assert_arg
+
+local func = {}
+
+-- metatable for Placeholder Expressions (PE)
+local _PEMT = {}
+
+local function P (t)
+    setmetatable(t,_PEMT)
+    return t
+end
+
+func.PE = P
+
+local function isPE (obj)
+    return getmetatable(obj) == _PEMT
+end
+
+func.isPE = isPE
+
+-- construct a placeholder variable (e.g _1 and _2)
+local function PH (idx)
+    return P {op='X',repr='_'..idx, index=idx}
+end
+
+-- construct a constant placeholder variable (e.g _C1 and _C2)
+local function CPH (idx)
+    return P {op='X',repr='_C'..idx, index=idx}
+end
+
+func._1,func._2,func._3,func._4,func._5 = PH(1),PH(2),PH(3),PH(4),PH(5)
+func._0 = P{op='X',repr='...',index=0}
+
+function func.Var (name)
+    local ls = utils.split(name,'[%s,]+')
+    local res = {}
+    for i = 1, #ls do
+        append(res,P{op='X',repr=ls[i],index=0})
+    end
+    return unpack(res)
+end
+
+function func._ (value)
+    return P{op='X',repr=value,index='wrap'}
+end
+
+local repr
+
+func.Nil = func.Var 'nil'
+
+function _PEMT.__index(obj,key)
+    return P{op='[]',obj,key}
+end
+
+function _PEMT.__call(fun,...)
+    return P{op='()',fun,...}
+end
+
+function _PEMT.__tostring (e)
+    return repr(e)
+end
+
+function _PEMT.__unm(arg)
+    return P{op='unm',arg}
+end
+
+function func.Not (arg)
+    return P{op='not',arg}
+end
+
+function func.Len (arg)
+    return P{op='#',arg}
+end
+
+
+local function binreg(context,t)
+    for name,op in pairs(t) do
+        rawset(context,name,function(x,y)
+            return P{op=op,x,y}
+        end)
+    end
+end
+
+local function import_name (name,fun,context)
+    rawset(context,name,function(...)
+        return P{op='()',fun,...}
+    end)
+end
+
+local imported_functions = {}
+
+local function is_global_table (n)
+    return type(_G[n]) == 'table'
+end
+
+--- wrap a table of functions. This makes them available for use in
+-- placeholder expressions.
+-- @string tname a table name
+-- @tab context context to put results, defaults to environment of caller
+function func.import(tname,context)
+    assert_arg(1,tname,'string',is_global_table,'arg# 1: not a name of a global table')
+    local t = _G[tname]
+    context = context or _G
+    for name,fun in pairs(t) do
+        import_name(name,fun,context)
+        imported_functions[fun] = name
+    end
+end
+
+--- register a function for use in placeholder expressions.
+-- @func fun a function
+-- @string[opt] name an optional name
+-- @return a placeholder functiond
+function func.register (fun,name)
+    assert_arg(1,fun,'function')
+    if name then
+        assert_arg(2,name,'string')
+        imported_functions[fun] = name
+    end
+    return function(...)
+        return P{op='()',fun,...}
+    end
+end
+
+function func.lookup_imported_name (fun)
+    return imported_functions[fun]
+end
+
+local function _arg(...) return ... end
+
+function func.Args (...)
+    return P{op='()',_arg,...}
+end
+
+-- binary operators with their precedences (see Lua manual)
+-- precedences might be incremented by one before use depending on
+-- left- or right-associativity, space them out
+local binary_operators = {
+    ['or'] = 0,
+    ['and'] = 2,
+    ['=='] = 4, ['~='] = 4, ['<'] = 4, ['>'] = 4,  ['<='] = 4,   ['>='] = 4,
+    ['..'] = 6,
+    ['+'] = 8, ['-'] = 8,
+    ['*'] = 10, ['/'] = 10, ['%'] = 10,
+    ['^'] = 14
+}
+
+-- unary operators with their precedences
+local unary_operators = {
+    ['not'] = 12, ['#'] = 12, ['unm'] = 12
+}
+
+-- comparisons (as prefix functions)
+binreg (func,{And='and',Or='or',Eq='==',Lt='<',Gt='>',Le='<=',Ge='>='})
+
+-- standard binary operators (as metamethods)
+binreg (_PEMT,{__add='+',__sub='-',__mul='*',__div='/',__mod='%',__pow='^',__concat='..'})
+
+binreg (_PEMT,{__eq='=='})
+
+--- all elements of a table except the first.
+-- @tab ls a list-like table.
+function func.tail (ls)
+    assert_arg(1,ls,'table')
+    local res = {}
+    for i = 2,#ls do
+        append(res,ls[i])
+    end
+    return res
+end
+
+--- create a string representation of a placeholder expression.
+-- @param e a placeholder expression
+-- @param lastpred not used
+function repr (e,lastpred)
+    local tail = func.tail
+    if isPE(e) then
+        local pred = binary_operators[e.op] or unary_operators[e.op]
+        if pred then
+            -- binary or unary operator
+            local s
+            if binary_operators[e.op] then
+                local left_pred = pred
+                local right_pred = pred
+                if e.op == '..' or e.op == '^' then
+                    left_pred = left_pred + 1
+                else
+                    right_pred = right_pred + 1
+                end
+                local left_arg = repr(e[1], left_pred)
+                local right_arg = repr(e[2], right_pred)
+                s = left_arg..' '..e.op..' '..right_arg
+            else
+                local op = e.op == 'unm' and '-' or e.op
+                s = op..' '..repr(e[1], pred)
+            end
+            if lastpred and lastpred > pred then
+                s = '('..s..')'
+            end
+            return s
+        else -- either postfix, or a placeholder
+            local ls = map(repr,e)
+            if e.op == '[]' then
+                return ls[1]..'['..ls[2]..']'
+            elseif e.op == '()' then
+                local fn
+                if ls[1] ~= nil then -- was _args, undeclared!
+                    fn = ls[1]
+                else
+                    fn = ''
+                end
+                return fn..'('..concat(tail(ls),',')..')'
+            else
+                return e.repr
+            end
+        end
+    elseif type(e) == 'string' then
+        return '"'..e..'"'
+    elseif type(e) == 'function' then
+        local name = func.lookup_imported_name(e)
+        if name then return name else return tostring(e) end
+    else
+        return tostring(e) --should not really get here!
+    end
+end
+func.repr = repr
+
+-- collect all the non-PE values in this PE into vlist, and replace each occurence
+-- with a constant PH (_C1, etc). Return the maximum placeholder index found.
+local collect_values
+function collect_values (e,vlist)
+    if isPE(e) then
+        if e.op ~= 'X' then
+            local m = 0
+            for i = 1,#e do
+                local subx = e[i]
+                local pe = isPE(subx)
+                if pe then
+                    if subx.op == 'X' and subx.index == 'wrap' then
+                        subx = subx.repr
+                        pe = false
+                    else
+                        m = math.max(m,collect_values(subx,vlist))
+                    end
+                end
+                if not pe then
+                    append(vlist,subx)
+                    e[i] = CPH(#vlist)
+                end
+            end
+            return m
+        else -- was a placeholder, it has an index...
+            return e.index
+        end
+    else -- plain value has no placeholder dependence
+        return 0
+    end
+end
+func.collect_values = collect_values
+
+--- instantiate a PE into an actual function. First we find the largest placeholder used,
+-- e.g. _2; from this a list of the formal parameters can be build. Then we collect and replace
+-- any non-PE values from the PE, and build up a constant binding list.
+-- Finally, the expression can be compiled, and e.__PE_function is set.
+-- @param e a placeholder expression
+-- @return a function
+function func.instantiate (e)
+    local consts,values,parms = {},{},{}
+    local rep, err, fun
+    local n = func.collect_values(e,values)
+    for i = 1,#values do
+        append(consts,'_C'..i)
+        if _DEBUG then print(i,values[i]) end
+    end
+    for i =1,n do
+        append(parms,'_'..i)
+    end
+    consts = concat(consts,',')
+    parms = concat(parms,',')
+    rep = repr(e)
+    local fstr = ('return function(%s) return function(%s) return %s end end'):format(consts,parms,rep)
+    if _DEBUG then print(fstr) end
+    fun,err = utils.load(fstr,'fun')
+    if not fun then return nil,err end
+    fun = fun()  -- get wrapper
+    fun = fun(unpack(values)) -- call wrapper (values could be empty)
+    e.__PE_function = fun
+    return fun
+end
+
+--- instantiate a PE unless it has already been done.
+-- @param e a placeholder expression
+-- @return the function
+function func.I(e)
+    if rawget(e,'__PE_function')  then
+        return e.__PE_function
+    else return func.instantiate(e)
+    end
+end
+
+utils.add_function_factory(_PEMT,func.I)
+
+--- bind the first parameter of the function to a value.
+-- @function func.bind1
+-- @func fn a function of one or more arguments
+-- @param p a value
+-- @return a function of one less argument
+-- @usage (bind1(math.max,10))(20) == math.max(10,20)
+func.bind1 = utils.bind1
+func.curry = func.bind1
+
+--- create a function which chains two functions.
+-- @func f a function of at least one argument
+-- @func g a function of at least one argument
+-- @return a function
+-- @usage printf = compose(io.write,string.format)
+function func.compose (f,g)
+    return function(...) return f(g(...)) end
+end
+
+--- bind the arguments of a function to given values.
+-- `bind(fn,v,_2)` is equivalent to `bind1(fn,v)`.
+-- @func fn a function of at least one argument
+-- @param ... values or placeholder variables
+-- @return a function
+-- @usage (bind(f,_1,a))(b) == f(a,b)
+-- @usage (bind(f,_2,_1))(a,b) == f(b,a)
+function func.bind(fn,...)
+    local args = pack(...)
+    local holders,parms,bvalues,values = {},{},{'fn'},{}
+    local nv,maxplace,varargs = 1,0,false
+    for i = 1,args.n do
+        local a = args[i]
+        if isPE(a) and a.op == 'X' then
+            append(holders,a.repr)
+            maxplace = math.max(maxplace,a.index)
+            if a.index == 0 then varargs = true end
+        else
+            local v = '_v'..nv
+            append(bvalues,v)
+            append(holders,v)
+            append(values,a)
+            nv = nv + 1
+        end
+    end
+    for np = 1,maxplace do
+        append(parms,'_'..np)
+    end
+    if varargs then append(parms,'...') end
+    bvalues = concat(bvalues,',')
+    parms = concat(parms,',')
+    holders = concat(holders,',')
+    local fstr = ([[
+return function (%s)
+    return function(%s) return fn(%s) end
+end
+]]):format(bvalues,parms,holders)
+    if _DEBUG then print(fstr) end
+    local res = utils.load(fstr)
+    res = res()
+    return res(fn,unpack(values))
+end
+
+return func
+
+