Disable Recursion in Ruby to Force Use of Y Combinator

Question

How can Ruby's recursion be 'sabotaged' to disable the ability of ruby methods to engage in recursion?

Needed for the creation of a program to teach lambda calculus, but using Ruby.

Motivation from Crockford on JavaScript - https://www.youtube.com/watch?v=ya4UHuXNygM&feature=youtu.be&t=1h9m53s

Answer 1

You can use the TracePoint API to trace all method calls and returns and build a stack to see whether a method that is called is already on the stack. That way, you can at least detect recursion, and then you can just raise an exception or exit the program.

Something like:

stack = []

TracePoint.trace(:call, :return) do |trace|
  p trace, stack
  method = trace.method_id
  case trace.event
  when :call
    if stack.include?(method)
      $stderr.puts "RECURSION DETECTED: method `#{stack.last}` calls method `#{method}`."
      exit!
    end
    stack.push(method)
  when :return
    stack.pop
  end 
end

def foo; bar end
def bar; baz end
def baz; qux end
def qux; bar end

foo

Note that I stuck a debug print in there so that you can observe how it works:

#<TracePoint:call `foo'@./test.rb:20>
[]
#<TracePoint:call `bar'@./test.rb:21>
[:foo]
#<TracePoint:call `baz'@./test.rb:22>
[:foo, :bar]
#<TracePoint:call `qux'@./test.rb:23>
[:foo, :bar, :baz]
#<TracePoint:call `bar'@./test.rb:21>
[:foo, :bar, :baz, :qux]
RECURSION DETECTED: method `qux` calls method `bar`.