Minimal language with arrays in Ruby

For a (presumably) fully functional language, all we need is the following:

Boolean logic

We can define the two boolean constants YES and NO like this:

NO = []
YES = [ [] ]

An IF function can be defined with lambda, and uses #each (which will only yield for YES) to call the right branch:

IF =
  lambda do |val, if_yes, if_no|
    val.each { return if_yes.call }
    if_no.call
  end

With IF, we can implement dyadic (“binary”) operations, such as OR and AND:

OR =
  lambda do |val_a, val_b|
    IF[val_a, -> { YES }, -> { IF[val_b, -> { YES }, -> { NO }] }]
  end

This now works as expected:

p OR[YES, YES]
p OR[YES, NO]
p OR[NO, YES]
p OR[NO, NO]

We can define ZERO and ONE in the same way NO and YES:

ZERO = NO
ONE = YES

We can define successor function, which returns 1 more than the input:

SUCC =
  lambda do |val|
    [val]
  end

We can define TWO this way:

TWO = SUCC[ONE]

We can also define PRED, which returns the previous integer in sequence:

PRED =
  lambda do |val|
    val.each { |e| return e }
    return ZERO
  end

With PRED and SUCC, we can define SUM:

SUM =
  lambda do |val_a, val_b|
    IF[val_a, -> { SUM[PRED[val_a], SUCC[val_b]]}, -> { val_b }]
  end

Now this works:

p SUM[ZERO, ZERO]
p SUM[ZERO, ONE]
p SUM[ZERO, TWO]
p SUM[TWO, TWO]

Note last edited November 2023.