Binary Lambda caclulus, 39 bits (< 5 bytes).

In lambda calculus with church numerals, that function is simply 𝜆a. a add = 𝜆a. a(𝜆m𝜆n𝜆f𝜆x. m f (n f x)), with blc encoding 000110000000000101111101100101111011010), since eta expansion handles all the additional arguments.

Lambda calculus, 51 characters (or 73 bits)

The function takes two arguments (in curried form as usual): the first argument is a as a Church numeral, and the second argument is a list of Church numerals.

\a\l l(\h\t\f t(f h))(\f f)(a(\m\n\f\x m f(n f x)))

Or in the binary lambda calculus encoding:

0000010101100000000111001101110001001110000000000101111101100101111011010

In lambda calculus, the standard representation of a list is: e.g. the list [a, b, c] is represented by \$\lambda x . \lambda y . x~a~(x~b~(x~c~y))\$. (As a mnemonic, I like to think of the case where \$x = \mathrm{cons}\$ and \$y = \mathrm{nil}\$.) In other words, in lambda calculus, a list is its "fold-right" operation.

Now, if we have a list \$l\$, the expression \$l ~ (\lambda h . \lambda t . \lambda f . t ~ (f ~ h)) ~ (\lambda f . f)\$ builds up an "apply" operation. For example, in the case \$l = [a, b, c]\$, it evaluates to \$\lambda f . f ~ a ~ b ~ c\$. (To see this, for example: $$ [a, b, c] (\lambda h . \lambda t . \lambda f . t ~ (f ~ h)) ~ (\lambda f . f) = \\ (\lambda h . \lambda t . \lambda f . t ~ (f ~ h)) ~ a ~ ([b, c] (\lambda h . \lambda t. t ~ (f ~ h)) ~ (\lambda f . f)) = \\ (\lambda h . \lambda t . \lambda f . t ~ (f ~ h)) ~ a ~ (\lambda f . f ~ b ~ c) = \\ \lambda f . ((\lambda f . f ~ b ~ c) (f ~ a)) = \\ \lambda f . f ~ a ~ b ~ c$$ where from the second line to the third we applied an inductive hypothesis on the case \$l = [b, c]\$. For the base case, the empty list is \$l = [] = \lambda x . \lambda y . y\$, so \$l ~ (\lambda h . \lambda t . \lambda f . t ~ (f ~ h)) ~ (\lambda f . f) = \lambda f . f\$. Alternatively, you can see this as a special case of how in general you would write a fold-left operation on lists in terms of the fold-right operation.)

From here, what we want is simply: \$\lambda a . \lambda l . \mathrm{apply} ~ (a ~ \mathrm{add}) ~ l\$. Substituting \$\mathrm{apply} = \lambda f . \lambda l . l (\lambda h . \lambda t . \lambda f . t ~ (f ~ h)) ~ (\lambda f . f) ~ f\$, and \$\mathrm{add} = \lambda m . \lambda n . \lambda f . \lambda x . m ~ f ~ (n ~ f ~ x)\$ gives the final expression above.

JavaScript (Node.js),  65  56 bytes

Saved 7 bytes thanks to @tsh

This is really just a port of alephalpha's algorithm.

Expects (n)(x), where x is an array of BigInts.

x=>x[x.map((v,i)=>[a,b]=i?[v**=b,v**a]:[0n,1n]),0]*b+a*b

Try it online!

Or 54 bytes without BigInts:

x=>x[x.map((v,i)=>[a,b]=i?[v**=b,v**a]:[0,1]),0]*b+a*b

Try it online!

Flurry, 28 bytes

({}){{}{}}[{}{<><<>(){}>}]{}

A language based on untyped lambda calculus is certainly the right tool here :)

Takes input in the order of xa xa-1 ... x1 x0 a, and evaluates to the Church value of the required expression.

({})      pop a; evaluate to a; push back a
{{}{}}    \x. x (pop), which takes a function and applies one item from stack
          a (\x. x (pop)) [...] evaluates to [...] x0 x1 ... xa-1
[{}       the expression (a add)
   {<><<>(){}>}  add = \x. S (S . K . x)
]
          so far, the result is (a add x0 x1 ... xa-1)
{}        finally, pop xa and apply to the above

Test script:

Compare-Object (.\Flurry.exe -nin src.txt 9 0) 9
Compare-Object (.\Flurry.exe -nin src.txt 2 2 1) 4
Compare-Object (.\Flurry.exe -nin src.txt 2 2 2 2) 16
Compare-Object (.\Flurry.exe -nin src.txt 5 4 3 2) 5000
Compare-Object (.\Flurry.exe -nin src.txt 8 1 7 2) 120
Compare-Object (.\Flurry.exe -nin src.txt 5 1 4 1 3) 30
Compare-Object (.\Flurry.exe -nin src.txt 2 2 2 1 3) 4352
Compare-Object (.\Flurry.exe -nin src.txt 2 2 2 0 3) 4096
Compare-Object (.\Flurry.exe -nin src.txt 2 2 2 2 3) 4608

PARI/GP, 47 bytes

x->[[a,b]=[t=c^b,t^a]|c<-x[^b=!a=0]];(x[1]+a)*b

Attempt This Online!

A port of my Haskell answer. Takes input as \$[x_0,x_1,\dots,x_n]\$.

Haskell, 54 bytes

x#y|(a,b)<-foldl(\(a,b)c->(c^b,(c^b)^a))(0,1)y=(x+a)*b

Attempt This Online!

Takes input as \$x_0 \# [x_1,\dots,x_a]\$.

Abusing the notation, we have:

\$0 \operatorname{add} x_0 = x_0 = (x_0 + 0) \times 1\$.

If we have

\$(n-1) \operatorname{add} x_0 \cdots x_{n-1} = (x_0 + a_{n-1}) \times b_{n-1}\$,

then:

\$\begin{align} n \operatorname{add} x_0 \cdots x_n &= (n-1) \operatorname{add} (\operatorname{add} x_0) x_1 \cdots x_{n-1} x_n \\ &= (((\operatorname{add} x_0) + a_{n-1}) \times b_{n-1}) x_n \\ &= ((\operatorname{add} (\operatorname{add} x_0) a_{n-1}) \circ b_{n-1}) x_n \\ &= \operatorname{add} (\operatorname{add} x_0) a_{n-1} (b_{n-1} x_n) \\ &= (\operatorname{add} x_0 (b_{n-1} x_n)) \circ (a_{n-1} (b_{n-1} x_n)) \\ &= (x_0 + {x_n}^{b_{n-1}}) \times ({x_n}^{b_{n-1}})^{a_{n-1}} \\ &= (x_0 + a_n) \times b_n \end{align} \$

where:

\$a_n = {x_n}^{b_{n-1}}, b_n = ({x_n}^{b_{n-1}})^{a_{n-1}}\$.