A Lambda Calculus Model in POSIX sh

lambda.sh

# run with bash -x for a wild ride

# escaping with '\s' messes up dash, use '-s' instead
escape(){
	if test -n "$1"; then
		if test "${1%"${1#?}"}" = ' '; then
			echo '-s'"$(escape "${1#?}")"
		elif test "${1%"${1#?}"}" = '-'; then
			echo '--'"$(escape "${1#?}")"
		else
			echo "${1%"${1#?}"}""$(escape "${1#?}")"
		fi
	fi
}

unescape_match(){
	if test "${1%"${1#?}"}" = '-'; then
		echo '-'"$(unescape "${1#?}")"
	elif test "${1%"${1#?}"}" = 's'; then
		echo ' '"$(unescape "${1#?}")"
	fi
}

unescape(){
	if test -n "$1"; then
		if test "${1%"${1#?}"}" = '-'; then
			unescape_match "${1#?}"
		else 
			echo "${1%"${1#?}"}""$(unescape "${1#?}")"
		fi
	fi
}

pair(){
	echo "$(escape "$1")" "$(escape "$2")"
}

fst_(){
	unescape "$1"
}

fst(){
	fst_ $1
}

snd_(){
	unescape "$2"
}

snd(){
	snd_ $1
}

call(){
	"$(fst "$1")" "$(snd "$1")" "$2"
}

native(){
	"$1" "$2"
}

lift(){
	pair native "$1"
}

identity_(){
	echo "$1"
}

# \x -> x
identity="$(lift identity_)"


# \nil cons -> nil identity
nil_1(){
	call "$1" "$identity"
}

nil_0(){
	pair nil_1 "$1"
}

nil="$(lift nil_0)"


# \x xs nil cons -> cons x xs

cons_3(){
	call "$(call "$2" "$(fst "$1")")" "$(fst "$(snd "$1")")"
}

cons_2(){
	pair cons_3 "$(pair "$(fst "$1")" "$(pair "$(snd "$1")" "$2")")"
}

cons_1(){
	pair cons_2 "$(pair "$1" "$2")"
}

cons_0(){
	pair cons_1 "$1" 
}

cons="$(lift cons_0)"


echo "identity(1)=""$(call "$identity" 1)"

list="$(call "$(call "$cons" 1)" "$(call "$(call "$cons" 2)" "$(call "$(call "$cons" 3)" "$nil")")")"
echo "cons(1)(cons(2)(cons(3)(nil)))=""$list"

range(){
	if test "$1" -eq "$2"; then
		echo "$nil"
	else
		echo "$(call "$(call "$cons" "$1")" "$(range "$(($1 + 1))" "$2")" )"
	fi
}

echo "[0..4]=""$(range 0 4)"