local z,e,K,D=type,setmetatable,getmetatable,rawset local O,n=table.concat,table.insert local t=tostring local b=require("\112\108\046\117\116\105\108\115")local P,A,c,f=pairs,rawget,b.unpack,b.pack local a=require("\112\108\046\116\097\098\108\101\120")local U=a.map local T=A(_G,"\095\068\069\066\085\071")local p=b.assert_arg local i={}local B={}local function X(z)e(z,B)return z end i.PE=X local function F(z)return K(z)==B end i.isPE=F local function Y(z)return X({op="\088",repr="\095"..z;index=z})end local function V(z)return X({op="\088";repr="\095\067"..z;index=z})end i._1,i._2,i._3,i._4,i._5=Y(1),Y(2),Y(3),Y(4),Y(5)i._0=X({op="\088";repr="\046\046\046",index=0})function i.Var(z)local e=b.split(z,"\091\037\115\044\093\043")local K={}for z=1,#e,1 do n(K,X({op="\088",repr=e[z];index=0}))end return c(K)end function i._(z)return X({op="\088",repr=z,index="\119\114\097\112"})end local k i.Nil=i.Var("\110\105\108")function B.__index(z,e)return X({op="\091\093";z,e})end function B.__call(z,...)return X({op="\040\041";z;...})end function B.__tostring(z)return k(z)end function B.__unm(z)return X({op="\117\110\109",z})end function i.Not(z)return X({op="\110\111\116";z})end function i.Len(z)return X({op="\035";z})end local function l(z,e)for e,K in P(e)do D(z,e,function(z,e)return X({op=K,z,e})end)end end local function y(z,e,K)D(K,z,function(...)return X({op="\040\041";e,...})end)end local N={}local function R(e)return z(_G[e])=="\116\097\098\108\101"end function i.import(z,e)p(1,z,"\115\116\114\105\110\103",R,"\097\114\103\035 \049\058 \110\111\116 \097 \110\097\109\101 \111\102 \097 \103\108\111\098\097\108 \116\097\098\108\101")local K=_G[z]e=e or _G for z,K in P(K)do y(z,K,e)N[K]=z end end function i.register(z,e)p(1,z,"\102\117\110\099\116\105\111\110")if e then p(2,e,"\115\116\114\105\110\103")N[z]=e end return function(...)return X({op="\040\041",z,...})end end function i.lookup_imported_name(z)return N[z]end local function Q(...)return...end function i.Args(...)return X({op="\040\041",Q,...})end local h={["\111\114"]=0;["\097\110\100"]=2,["\061\061"]=4;["~\061"]=4;["\060"]=4,["\062"]=4,["\060\061"]=4,["\062\061"]=4,["\046\046"]=6,["\043"]=8;["-"]=8,["\042"]=10,["\047"]=10,["\037"]=10;["\094"]=14}local q={["\110\111\116"]=12,["\035"]=12,unm=12}l(i,{And="\097\110\100",Or="\111\114";Eq="\061\061";Lt="\060",Gt="\062",Le="\060\061";Ge="\062\061"})l(B,{__add="\043";__sub="-",__mul="\042";__div="\047";__mod="\037",__pow="\094";__concat="\046\046"})l(B,{__eq="\061\061"})function i.tail(z)p(1,z,"\116\097\098\108\101")local e={}for K=2,#z,1 do n(e,z[K])end return e end function k(e,K)local D=i.tail if F(e)then local z=h[e.op]or q[e.op]if z then local D if h[e.op]then local K=z local O=z if e.op=="\046\046"or e.op=="\094"then K=K+1 else O=O+1 end local n=k(e[1],K)local t=k(e[2],O)D=n..(" "..(e.op..(" "..t)))else local K=e.op=="\117\110\109"and"-"or e.op D=K..(" "..k(e[1],z))end if K and K>z then D="\040"..(D.."\041")end return D else local z=U(k,e)if e.op=="\091\093"then return z[1]..("\091"..(z[2].."\093"))elseif e.op=="\040\041"then local e if z[1]~=nil then e=z[1]else e=""end return e..("\040"..(O(D(z),"\044").."\041"))else return e.repr end end elseif z(e)=="\115\116\114\105\110\103"then return"\""..(e.."\"")elseif z(e)=="\102\117\110\099\116\105\111\110"then local z=i.lookup_imported_name(e)if z then return z else return t(e)end else return t(e)end end i.repr=k local w function w(z,e)if F(z)then if z.op~="\088"then local K=0 for D=1,#z,1 do local O=z[D]local t=F(O)if t then if O.op=="\088"and O.index=="\119\114\097\112"then O=O.repr t=false else K=math.max(K,w(O,e))end end if not t then n(e,O)z[D]=V(#e)end end return K else return z.index end else return 0 end end i.collect_values=w function i.instantiate(z)local e,K,D={},{},{}local t,P,A local f=i.collect_values(z,K)for z=1,#K,1 do n(e,"\095\067"..z)if T then print(z,K[z])end end for z=1,f,1 do n(D,"\095"..z)end e=O(e,"\044")D=O(D,"\044")t=k(z)local a=("\114\101\116\117\114\110 \102\117\110\099\116\105\111\110\040\037\115\041 \114\101\116\117\114\110 \102\117\110\099\116\105\111\110\040\037\115\041 \114\101\116\117\114\110 \037\115 \101\110\100 \101\110\100"):format(e,D,t)if T then print(a)end A,P=b.load(a,"\102\117\110")if not A then return nil,P end A=A()A=A(c(K))z.__PE_function=A return A end function i.I(z)if A(z,"\095\095\080\069\095\102\117\110\099\116\105\111\110")then return z.__PE_function else return i.instantiate(z)end end b.add_function_factory(B,i.I)i.bind1=b.bind1 i.curry=i.bind1 function i.compose(z,e)return function(...)return z(e(...))end end function i.bind(z,...)local e=f(...)local K,D,t,P={},{},{"\102\110"},{}local A,a,U=1,0,false for z=1,e.n,1 do local D=e[z]if F(D)and D.op=="\088"then n(K,D.repr)a=math.max(a,D.index)if D.index==0 then U=true end else local z="\095\118"..A n(t,z)n(K,z)n(P,D)A=A+1 end end for z=1,a,1 do n(D,"\095"..z)end if U then n(D,"\046\046\046")end t=O(t,"\044")D=O(D,"\044")K=O(K,"\044")local p=("\114\101\116\117\114\110 \102\117\110\099\116\105\111\110 \040\037\115\041\n    \114\101\116\117\114\110 \102\117\110\099\116\105\111\110\040\037\115\041 \114\101\116\117\114\110 \102\110\040\037\115\041 \101\110\100\n\101\110\100\n"):format(t,D,K)if T then print(p)end local i=b.load(p)i=i()return i(z,c(P))end return i
--- 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


