For anyone who finds this interesting, I cannot recommend enough investing a half hour in watching the "Programming With Nothing" talk:
https://www.youtube.com/watch?v=VUhlNx_-wYk
In it, the speaker implements fizzbuzz using only lambda calculus (making significant use of church encoding).