Return to Answer

2852 243 characters using LiveScript (No Regex! Not fully golfed - could be improved)

Edit: check my answer below for 250 under pure JavaScript.

2852 243 characters using LiveScript (No Regex! Not fully golfed - could be improved)

2852 243 characters using LiveScript (not fully golfed - could be improved)

2852 243 characters using LiveScript (No Regex! Not fully golfed - could be improved)

LiveScript, using Bruijin Indices: 144 135 133

s=(I=id;(c=(a,b=I,f=I,l=1)->map ((x)->x.toFixed&&(g=x==l&&b||x>l&&f||I;g x,l)||c x,b,f,l+1),a);(a,b)->c a,((x,l)->c b,I,(->it+l)),I)

Edit: below is a more complete version which fills the requirements of the thread, I guess. It has lots of rooms for improvement, though, as I have 2 very similar functions. I am using arrays in the form [f x] to denote application, objects in the form {λ:body} to denote abstractions and integers to denote bruijin indices.

285 characters

I=id;λ=(.λ?);P=(.forEach?);N=(.toFixed?)
S=(t,b=I,f=I,l=0)->|N t=>f t;|λ t=>λ:S t.λ,b,f,l+1;|P t=>R map ((x)->(N x)&&(g=x==l&&b||x>l&&f||I;g x,l)||S x,b,f,l),t
A=(a,b)->|N a=>[a,b];|λ a=>(S a,((x,l)->S b,I,(->it+l-1)),(--)).λ|P a=>[(A a.0, a.1),b]
R=(a)->(P a)&&(A (R a.0),(R a.1))||a

Test:

console.log R [(λ:(λ:[2 [2 [2 1]]])), (λ:(λ:[2 [2 1]]))]
# Ouputs: {"λ":{"λ":[2,[2,[2,[2,[2,[2,[2,[2,1]]]]]]]]}}

Which is 2^3=8, as stated on OP.

2852 243 characters using LiveScript (not fully golfed - could be improved)

L=(.0==\\)
A=->it.forEach?&&it.0!=\\
V=(.toFixed?)
S=(a,b,t=-1,l=0)->|L a=>[\\,S(a.1,b,t,l+1)];|A a=>(map (->S(a[it],b,t,l)),[0 1]);|a==l+-1=>S(b,0,l+-1,0)||a|l-1<a=>a+t;|_=>a
R=(a)->|L a=>[\\,R a.1]|(A a)&&(L a.0)=>R(S(R(a.0),R(a.1)).1)|_=>a

Test:

a = [\\,[\\,[1 [1 0]]]]
b = [\\,[\\,[1 [1 [1 0]]]]]
console.log R [a, b]
# outputs ["\\",["\\",[1,[1,[1,[1,[1,[1,[1,[1,[1,0]]]]]]]]]]]

Which is 3^2=9, as stated on OP.

If anyone is curious, here is an extended version with some comments:

# Just type checking
λ = 100
isλ = (.0==λ)
isA = -> it.forEach? && it.0!=λ
isV = (.toFixed?)

# Performs substitutions in trees
# a: trees to perform substitution in
# b: substitute bound variables by this, if != void
# f: add this value to all unbound variables
# l: internal (depth)
S = (a,b,t=-1,l=0) -> 
    switch
    | isλ a             => [λ, (S a.1, b, t, l+1)]
    | isA a             => [(S a.0, b, t, l), (S a.1, b, t, l)]
    | a == l - 1        => (S b, 0, (l - 1), 0) || a
    | l - 1 < a < 100   => a + t
    | _                 => a

# Performs the beta-reduction
R = (a) ->
    switch
    | (isλ a)               => [λ,R a.1]
    | (isA a) && (isλ a.0)  => R(S(R(a.0),R(a.1)).1)
    | _                     => a

# Test
a = [λ,[λ,[1 [1 0]]]]
b = [λ,[λ,[1 [1 [1 0]]]]]
console.log show R [a, b]