Lambda Calculus countdown, for old times sake

lambda_calculus_countdown.rb

# NOTE: Printed output can be seen at the end of the file

# helper fn to make the lambdas have useful inspect methods so that I can tell
# what they are when I look at them.
def as(name, fn)
  fn.define_singleton_method(:inspect) { "λ#{name}" }
  fn
end


# === Available Functions ===
# No assignment in the lambda calculus, so you have to receive anything you want
# to name as an argument. Thus we begin by receiving all our helper functions
# as argumetns.
#
# Also, functions may only take 1 argument in the lambda calculus (I'm not sure)
# if they MUST take 1, I didn't enforce that, I only enforced 0 or 1. So, we
# have to nest function calls within each other to allow binding of multiple names.
# Really syntactically ugly, but it is a fun constraint. 🤷

# Utility
-> poison {      # a function that explodes if called (useful when you have to pass a value that should never be used)
-> y {           # y-combinator, enables recursion
-> statements {  # call it with arbitrarily many functions, it will execute them sequentially
-> println {     # wrapper for Ruby's `puts`
-> wrap {        # basically a noop, useful for giving a different inspect method for a different context

# Logic
# have to prepend "λ" to the name b/c these are keywords
-> λfalse { -> λtrue { -> λif {

# List
-> cons { -> empty_list { -> tail { -> head { -> is_empty { -> reduce { -> append {

# Math
-> is_zero {
-> succ {
-> λ0 { -> λ1 { -> λ2 { -> λ3 { -> λ4 { -> λ5 { -> λ6 { -> λ7 { -> λ8 { -> λ9 {
-> λ10 { -> λ11 { -> λ12 { -> λ13 { -> λ14 { -> λ15 {
-> pred {
-> num2ruby {

# String
-> str { -> str2ruby {
-> λeos {
-> λa { -> λb { -> λc { -> λd { -> λe { -> λf { -> λg { -> λh { -> λi { -> λj {
-> λk { -> λl { -> λm { -> λn { -> λo {

# === Main Function ===
  # Here, we have a countdown timer, it is equivalent to this ruby code:
  # `5.downto(1) { |n| puts n }; puts "done"`
  y[-> countdown { -> n {
    λif[is_zero[n]][-> {
      println[str2ruby[str[λd][λo][λn][λe][λeos]]] # => "done"
    }][-> {
      statements.(-> {
        println[num2ruby[n]] # => 5, 4, 3, 2, 1
      }).(-> {
        countdown[pred[n]]
      })
    }]
  }}][λ5]


# === DEFINITIONS ===

# --- String --
# Strings are lists of chars
# Chars are represented as numerical ordinals: a=1, b=2, ..., z=26
# They are wrapped so that if I inspect them in Ruby, I can tell what I'm looking at
  }.(as :o, wrap[λ15])
  }.(as :n, wrap[λ14])
  }.(as :m, wrap[λ13])
  }.(as :l, wrap[λ12])
  }.(as :k, wrap[λ11])
  }.(as :j, wrap[λ10])
  }.(as :i, wrap[λ9])
  }.(as :h, wrap[λ8])
  }.(as :g, wrap[λ7])
  }.(as :f, wrap[λ6])
  }.(as :e, wrap[λ5])
  }.(as :d, wrap[λ4])
  }.(as :c, wrap[λ3])
  }.(as :b, wrap[λ2])
  }.(as :a, wrap[λ1])
  }.(as :eos, wrap[λ0])

  }.(as :str2ruby, -> str {
    reduce
      .(str)
      .(-> char { -> memo { memo << ("a".ord.pred + num2ruby[char]).chr }})
      .("")
  })

  # String constructor, as close to a literal as I can get. Call with arbitrarily
  # many chars, and then terminate it by calling it with EOS (end of string)
  # Sadly this is very inefficient b/c it appends each char to the end, which
  # requires rebuilding the list for each one, but it's the only way to allow
  # such a convenient invocation interface. The efficient way would be either
  # enter the chars backwards, or reverse the list after it is built.
  }.(as :str, y[-> recur { -> str {
    -> char {
      λif[is_zero[char]]
        .(-> { str })
        .(-> { recur[append[char][str]] })
    }
  }}][empty_list])

# --- Math ---
# note that numbers take a function and value
# and inject the value through the function that many times

  }.(as :num2ruby, -> n {
    n[-> n { n+1 }][0]
  })

  # builds a new number by counting up from zero, but skips the first increment
  }.(as :pred, -> n {
    n.(-> state {                                 # state just lets us pass 2 args through: is_first, and sum
      λif[state[head]]                            # on the first iteration
        .(-> { cons[λfalse][state[tail]] })       # do nothing
        .(-> { cons[λfalse][succ[state[tail]]] }) # otherwise increment
    })
    .(cons[λtrue][λ0])
    .(tail)
  })

  }.(as :"15", succ[λ14])
  }.(as :"14", succ[λ13])
  }.(as :"13", succ[λ12])
  }.(as :"12", succ[λ11])
  }.(as :"11", succ[λ10])
  }.(as :"10", succ[λ9])
  }.(as :"9",  succ[λ8])
  }.(as :"8",  succ[λ7])
  }.(as :"7",  succ[λ6])
  }.(as :"6",  succ[λ5])
  }.(as :"5",  succ[λ4])
  }.(as :"4",  succ[λ3])
  }.(as :"3",  succ[λ2])
  }.(as :"2",  succ[λ1])
  }.(as :"1",  succ[λ0])
  }.(as :"0", -> fn { -> val { val }})

  }.(as :succ, -> n {
    -> fn { -> val { n[fn][fn[val]] } }
  })

  }.(as :is_zero, -> n {
    n[-> _ { λfalse }][λtrue]
  })

# --- Lists ---
  }.(as :append, y[-> recur {
    -> element { -> list {
      λif[list[is_empty]]
        .(-> { cons[element][list] })
        .(-> { cons.(list[head])
                   .(recur[element][list[tail]])
        })
    }}
  }])

  }.(as :reduce, y[-> recur {
    -> list { -> fn { -> memo {
      λif[list[is_empty]]
        .(-> { memo })
        .(-> {
          recur.(list[tail])
                .(fn)
                .(fn[list[head]][memo])
        })
    }}}
  }])

  # not sure how it's supposed to be done, but I am needing to pass 3 values to
  # the selector, to differentiate between a constructed pair and an empty list
  }.(as :is_empty, -> head { -> tail { -> is_empty { is_empty }}})
  }.(as :head,     -> head { -> tail { -> is_empty { head }}})
  }.(as :tail,     -> head { -> tail { -> is_empty { tail }}})
  }.(as :"[]", -> selector {
    selector[poison][poison][λtrue]
  })
  }.(as :cons, -> val1 { -> val2 {
    as "[#{val1.inspect}, #{val2.inspect}]",
      -> selector { selector[val1][val2][λfalse] }
  }})

# --- Logic ---
  }.(as :if, -> bool { -> true_case { -> false_case {
    bool[true_case][false_case].()
  }}})

  }.(as :true, -> true_case { -> false_case {
    true_case
  }})

  }.(as :false, -> true_case { -> false_case {
    false_case
  }})

# --- Utility ---
  }.(as :wrap, -> fn {
    -> arg { fn[arg] }
  })

  }.(as :println, -> ruby_val {
    -> _ { ruby_val }[puts(ruby_val)]
  })

  # not sure what the real name for this is, since my print statement operates by
  # side effects instead of evaluating to a value, I need to print and then recur
  # so this just allows for execution of arbitrarily many sequential lambdas.
  }.(as :statements, y.(-> recur {
    -> fn {
      -> _ { recur }[fn[]]
    }
  }))

  }.(as :y,
    ->   unbound_y { -> f { -> arg { f.(unbound_y[unbound_y][f]).(arg) }}}
    .(-> unbound_y { -> f { -> arg { f.(unbound_y[unbound_y][f]).(arg) }}})
  )  

  }.(as :poison, -> *args {
    raise "POISON WAS CALLED WITH #{args.inspect}"
  })

# >> 5
# >> 4
# >> 3
# >> 2
# >> 1
# >> done