fizzbuzz.ls

# FizzBuzz in Lambda Calculus LiveScript
#
# Based on the problem from Chapter 6 of
#     Understanding Computation: From Simple Machines to Impossible Programs
#     by Tom Stuart
#     http://computationbook.com/
#
# Only these things are allowed:
#   - Creating functions
#   - Invoking functions
#   - Constants (they must be substitutable, so no recursive)

# church numeral scheme for 0 and 1
ZERO  = (f) -> (x) -> x
ONE   = (f) -> (x) -> f(x)

# pair data structure
PAIR  = (a) -> (b) -> (f) -> f(a)(b)
LEFT  = (x) -> x((a) -> (b) -> a)
RIGHT = (x) -> x((a) -> (b) -> b)

# successor and predecessor function
SUCCESSOR = (n) -> (f) -> (x) -> f(n(f)(x))
SLIDE = (pair) -> PAIR(RIGHT(pair))(SUCCESSOR(RIGHT(pair)))
PREDECESSOR = (n) -> LEFT(n(SLIDE)(PAIR(ZERO)(ZERO)))

# basic math
ADD      = (a) -> (b) -> (f) -> (x) -> a(f)(b(f)(x))
SUBTRACT = (a) -> (b) -> b(PREDECESSOR)(a)
MULTIPLY = (a) -> (b) -> (f) -> a(b(f))
POWER    = (a) -> (b) -> b(a)

# more numbers
TWO     = SUCCESSOR(ONE)
THREE   = SUCCESSOR(TWO)
FIVE    = ADD(TWO)(THREE)
TEN     = MULTIPLY(FIVE)(TWO)
FIFTEEN = MULTIPLY(FIVE)(THREE)
HUNDRED = POWER(TEN)(TWO)

# church booleans
TRUE  = (a) -> (b) -> a
FALSE = (a) -> (b) -> b

# if statement (for code decoration)
IF = (c) -> c

# check if zero
IS_ZERO = (n) -> n((x) -> FALSE)(TRUE)

# check if less than or equal
LEQ = (a) -> (b) -> IS_ZERO(SUBTRACT(a)(b))

# the y-combinator
Y = (f) -> (
  (g) -> f((x) -> g(g)(x)))(
  (g) -> f((x) -> g(g)(x)))

# recursive div and modulo function
DIVMOD = Y((f) -> (a) -> (b) ->
  IF(LEQ(b)(a))(
    (_) ->
      ( (v) -> PAIR(SUCCESSOR(LEFT(v)))(RIGHT(v)) )(f(SUBTRACT(a)(b))(b))
  )(
    (_) -> PAIR(ZERO)(a)
  )(TRUE)
)

# modulo function
MOD = (a) -> (b) -> RIGHT(DIVMOD(a)(b))

# list data structure
#   - (TRUE,FALSE) = NIL
#   - (FALSE,(value,next))
NIL = PAIR(TRUE)(FALSE)
UNSHIFT = (list) -> (value) -> PAIR(FALSE)(PAIR(value)(list))
EMPTY = LEFT
FIRST = (list) -> LEFT(RIGHT(list))
REST = (list) -> RIGHT(RIGHT(list))

# range generation function
RANGE = Y((range) -> (a) -> (b) ->
  IF(LEQ(a)(b))(
    (_) -> UNSHIFT(range(SUCCESSOR(a))(b))(a)
  )(
    (_) -> NIL
  )(TRUE)
)

# foldr
FOLDR = Y((foldr) -> (f) -> (init) -> (list) ->
  IF(EMPTY(list))(
    (_) -> init
  )(
    (_) -> f(FIRST(list))(foldr(f)(init)(REST(list)))
  )(TRUE)
)

# map
MAP = (f) -> FOLDR((a) -> (b) -> UNSHIFT(b)(f(a)))(NIL)

# list concat
CONCAT = (a) -> (b) -> FOLDR((char) -> (list) -> UNSHIFT(list)(char))(b)(a)

# generate ascii code
CHAR = ADD(POWER(TWO)(MULTIPLY(TWO)(THREE)))
CHAR_L = ADD(MULTIPLY(THREE)(POWER(TWO)(FIVE)))
CHAR_N = ADD(MULTIPLY(THREE)(POWER(TWO)(POWER(TWO)(TWO))))

# generate characters
CH_F = CHAR(MULTIPLY(TWO)(THREE))
CH_B = CHAR(TWO)
CH_I = CHAR_L(PREDECESSOR(TEN))
CH_Z = CHAR_L(MULTIPLY(TWO)(ADD(TEN)(THREE)))
CH_U = CHAR_L(MULTIPLY(THREE)(ADD(FIVE)(TWO)))

# now make our text
S_ZZ = UNSHIFT(UNSHIFT(NIL)(CH_Z))(CH_Z)
S_FIZZ = UNSHIFT(UNSHIFT(S_ZZ)(CH_I))(CH_F)
S_BUZZ = UNSHIFT(UNSHIFT(S_ZZ)(CH_U))(CH_B)
S_FIZZBUZZ = CONCAT(S_FIZZ)(S_BUZZ)

# convert number to string
TO_S = Y((to_s) -> (out) -> (n) ->
  (
    (result) ->
      (
        (div) -> (mod) ->
          (
            (build) ->
              IF(IS_ZERO(div))(
                (_) -> build
              )(
                (_) -> to_s(build)(div)
              )(TRUE)
          )(UNSHIFT(out)(CHAR_N(mod)))
      )(LEFT(result))(RIGHT(result))
  )(DIVMOD(n)(TEN))
)(NIL)

# our range of one to hundred
ONE_TO_HUNDRED = RANGE(ONE)(HUNDRED)

# finally, our fizzbuzz array
FIZZBUZZ = MAP((n) ->
  IF(IS_ZERO(MOD(n)(FIFTEEN)))(
    S_FIZZBUZZ
  )(
    IF(IS_ZERO(MOD(n)(THREE)))(
      S_FIZZ
    )(
      IF(IS_ZERO(MOD(n)(FIVE)))(
        S_BUZZ
      )(
        TO_S(n)
      )
    )
  )
)(ONE_TO_HUNDRED)


# <END>
# ------------------- testing code

# convert church numeral to js number
Function.prototype.i = -> this((x) -> x + 1)(0)

# convert church boolean to js boolean
Function.prototype.b = -> this(true)(false)

# convert pair to js array
Function.prototype.p = -> [LEFT(this), RIGHT(this)]

# convert church numeral with value as ascii to string
Function.prototype.c = -> String.fromCharCode(this.i())

# convert list to js array
Function.prototype.l = ->
  list = this
  out = []
  while !EMPTY(list).b()
    out.push(FIRST(list))
    list = REST(list)
  return out

# convert list to string
Function.prototype.s = -> this.l().map((.c())).join('')

p = console.log

for s in FIZZBUZZ.l().map((.s()))
  p s