# num2church.sed

### convert the input integer to church numeral form
### 0 = (\f.(\x.x))
### 1 = (\f.(\x.(f x)))
### 2 = (\f.(\x.(f (f x))))
### ...
### n = (\f.(\x.(f^n x)))

### sanity check input
# clear whitespace
s/[[:space:]]//g
# kill leading zeros
: zeros
s/^0\(.\+\)$/\1/
t zeros
### should be an integer
/^[[:digit:]]\+$/b start
s/.*/bad input/
b end

:start

### have three segments
### <target number>|<current number>|<church number>
### start <current number> and <church number> at zero
### and add one until <target number> = <current number>
### then return the <church number>

s/\([[:digit:]]\+\)/\1|0|(\\f.(\\x.x))/

# clear t status
t loop

:loop

# check for termination
s/^\([[:digit:]]\+\)|\1|\(.*\)/\2/
t end

# add one to <current number> and <church number>
# church is easy
# (slow) s/^\([^|]\+\)|\([^|]\+\)|\(.*(\\x\.\)\([^)]\+\)\(.*\)/\1|\2|\3(f \4)\5/
s/^\([^|]\+\)|\([^|]\+\)|(\\f.(\\x.\(.*\)))/\1|\2|(\\f.(\\x.(f \3)))/

# current is harder
# use rules like (1:0) = 10, and (4+1) = 5
# add one
s/^\([^|]\+\)|\([^|]\+\)|\(.*\)/\1|(1+\2)|\3/

:add
# reduce addition
# if (1+n) | n>9, deal with multiple digits
# (1+14) => (1:(1+4)) => 15
s/(1+\([[:digit:]]\+\)\([[:digit:]]\))/(\1:(1+\2))/
s/(1+0)/1/
s/(1+1)/2/
s/(1+2)/3/
s/(1+3)/4/
s/(1+4)/5/
s/(1+5)/6/
s/(1+6)/7/
s/(1+7)/8/
s/(1+8)/9/
s/(1+9)/10/

### shift carry
### ie. (2:10) => ((1+2):0)
s/(\([[:digit:]]\+\):10)/((1+\1):0)/

### reduce simple :
### (23:4) => 234
s/(\([[:digit:]]\+\):\([[:digit:]]\))/\1\2/

t add
b loop

:end