interpreter.shen fails

[deech]

Using Shen 15 and Ruby 2.0.0 the test in interpreter.shen fails with the following message: Qi interpreter - chapter 13: (tc +) = true run time: 4.0531158447265625e-06 secs passed Qi interpreter - chapter 13: (load "interpreter.shen") = loaded type#num : symbol type#primitive_object : symbol type#pattern : symbol type#l_formula : symbol l_interpreter : (A --> B) read_eval_print_loop : (string --> A) normal_form : (l_formula --> l_formula)

failed with error maximum stack depth exceeded

Qi interpreter - chapter 13: (tc -) = false run time: 1.0013580322265625e-05 secs passed passed ... 111 failed ...1 pass rate ...99.10714285714286%

[gregspurrier]

Thank you for reporting this. This is currently mentioned in the Known Issues section of the README, but did not yet have an GitHub issue associated with it. As far as I can tell, the code is executing correctly, but exhausts the Ruby stack.

I had a private email conversation with Mark Tarver and he said that this failure would not be considered to compromise ShenRuby w.r.t. the Shen license. I would still like to find a way to fix it or work around it, though.

[deech]

Thanks for getting back to me. We are considering possibly using ShenRuby in production. Can you give me anymore insight into what's causing the failure? Are there Shen constructs that aren't safe to use? The exception seems to occur only when type checking is on.

[gregspurrier]

Unfortunately, I can't give much more insight into it. I investigated it a bit at the time and it did not appear to be going into infinite recursion or anything like that, but rather just needing a call stack larger than Ruby could provide.

IIRC, I've also seen problems when reading large strings from a file because the string reader function makes non-tail recursive calls.

[deech]

Another possible avenue might be that currently the branches of an "if" statement are not forced to be in tail-position. According to http://www.cesura17.net/~will/professional/research/papers/tail.pdf (Section 2, Definition 1), in Scheme at least, it's required. I tried modifying the code so that true_clause and false_clause in compile_if always set in_tail_pos to true. But that led to an error with hd being called on an Array. I don't have time to take it further but I thought I'd mention it.

[gregspurrier]

Thanks for the pointer to the paper. I believe that this is currently handled correctly in ShenRuby. In rule 2 of definition 2, it says "If (if E0 E1 E2) is a tail expression, then both E1 and E2 are tail expressions". You'll see in the definition of compile_if that the in_tail_position status of the if statement is propagated when compiling the E1 and E2 clauses.

Thank you very much for describing the change you tried and the failure mode. I'm currently working on a new implementation of Kl in Ruby that should be much more performant than the current one (see https://github.com/gregspurrier/klam) and it is running into a very similar failure mode. Sure enough, in my conversion of self-tail calls to loop/recur I'm not considering that the if may not be in tail position. Now that I know the problem, it should be simple to fix.

[gregspurrier]

Actually, I spoke too soon. I am indeed handling tail-position if differently than non-tail-position if in the Klam code I mentioned. Back to the drawing board....

[tizoc]

@gregspurrier is there an easy way to see the Ruby code generated from .kl sources?

[gregspurrier]

@tizoc yes: (set-dump-code true) will show the Kl code passed to eval-kl and the resulting Ruby code that will be evaluated within the context of the Kl environment instance.

[tizoc]

FYI the Clisp port fails for me in the same way on OSX unless I raise the stack limits with ulimit -s to a very high value (about 32k), but the SBCL port works fine.

[gregspurrier]

Unfortunately raising the stack limit doesn't appear to have any affect on Ruby. E.g., this snippet:

def dive(x)
  puts x
  dive(x + 1)
end

dive(0)

Gets a stack level too deep exception after printing 8712 on both a normal OS X shell and one that I've raised the limit up to 60000 while running as root.

[gregspurrier]

Good news. It turns out that Ruby 2.0.0 introduced support for specifying the Ruby VM stack size via an environment variable called RUBY_THREAD_VM_STACK_SIZE. When I set this to 2 * 1024 * 1024 the test suite passes on OS X:

$ RUBY_THREAD_VM_STACK_SIZE=2097152 ./bin/shen_test_suite.rb
...
passed ... 128
failed ...0
pass rate ...100%

ok
0

run time: 68.60321521759033 secs

I'll add a note to the README later and then close out this issue.

[tizoc]

Cool, thats great news :)

[deech]

yay!

On Tue, Dec 16, 2014 at 11:23 AM, tizoc notifications@github.com wrote:

Cool, thats great news :)

— Reply to this email directly or view it on GitHub https://github.com/gregspurrier/shen-ruby/issues/11#issuecomment-67196663 .

[gregspurrier]

I've updated the README with instructions on how to set the stack size for MRI 2.0.0+ and JRuby. See https://github.com/gregspurrier/shen-ruby#setting-stack-size.