Implement natural numbers
Implement ADD, MULTIPLY and POWER for natural numbers
Implement DECREMENT and SUBTRACT for natural numbers
Implement booleans
Simplify IF with eta-contraction
Implement NOT, AND and OR for booleans

def not(b)
  if b
    false
  else
    true
  end
end

def and(a, b)
  if a
    if b
      true
    else
      false
    end
  else
    false
  end
end

def or(a, b)
  if a
    true
  else
    if b
      true
    else
      false
    end
  end
end
Implement IS_ZERO for natural numbers
Implement IS_LESS_OR_EQUAL and IS_EQUAL for natural numbers

def less_or_equal?(m, n)
  (m - n).zero? # 0 is the smallest number
end

def equal?(m, n)
  m <= n && n <= m
end
Implement broken, cheating FACTORIAL for natural numbers

def factorial(n)
  if n.zero?
    1
  else
    n * factorial(n - 1)
  end
end
Fix broken FACTORIAL with eta-expansion
Replace cheating FACTORIAL with non-cheating implementation
Define Y and Z combinators
Redefine FACTORIAL with the Z combinator
Implement DIV for natural numbers

def div(m, n)
  if n <= m
    div(m - n, n) + 1
  else
    0
  end
end
Implement MOD for natural numbers

def mod(m, n)
  if n <= m
    mod(m - n, n)
  else
    m
  end
end
Implement pairs
Implement EMPTY and UNSHIFT for lists
Implement IS_EMPTY for lists
Implement FIRST for lists
Implement REST for lists