Compile 'do' as a sequence of expressions in Ruby.

[tizoc]

This allows the compiler to compile (do Exp1 Exp2) properly when Exp2 is in tail position so that it can be tail-call optimized as expected.

[tizoc]

Mmm... while the example I created works without overflowing the stack now, I still get 1 failure when running the Shen tests, I will let you know if I figure out why

Qi interpreter - chapter 13: (load "interpreter.shen") = loaded
num : symbol
primitive_object : symbol
pattern : symbol
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

[tizoc]

Ok, after experimenting a bit (and looking at interpreter.shen and powersets.shen) it is obvious that the reason those fail here is unrelated to 'do' and more about actual stack space usage. For me ruby-shen fails at powerset if the list contains 13 elements, the scheme port fails for lists containing 19 elements, and the clisp port for lists of 16 elements.

I suppose the difference between each port is how much stack space the underlying implementation uses for each nested call.

You may want to apply this modification to the compiler anyway because it solves the cases involving 'do'.

[gregspurrier]

Hi. Thanks for the pull request.

I'm reluctant to address do in the K Lambda compiler since it is not part of the K Lambda specification, but rather a Shen function defined in sys.kl.

Do you know whether there has been any previous discussion regarding changing the semantics of do in the news group? Do you take this approach in chibi-shen?

[tizoc]

Overriding functions is ok when you want a more performant version as long as everything keeps working as expected. This is true for replacing function references and also for program transformations (the CLisp implementation for example transforms calls to 'cons', 'hd', 'tl', etc to their direct equivalents in common lisp instead of just aliasing them).

The situation with 'do' is a bit special, because it is more about enforcing semantics (instead of just replacing a function). I do this in the Scheme port to make TCO work when 'do' is involved, otherwise the underlying implementation can't do it.

I discussed this previously here: https://groups.google.com/forum/#!msg/qilang/2ixosqX4Too/rzSdxGbwDncJ

My opinion is that 'do' should be a primitive, otherwise it will not work reliably (when TCO is expected) on all ports. Some compilers may notice that 'do' does nothing and optimize the call away, but thats not usually the case.

[tizoc]

For the record, the CLisp port doesn't optimize 'do' in this way, this means that it doesn't support TCO when 'do' is involved.

I may start this discussion on the list again in the following days, you can wait until then if you are unsure.

[gregspurrier]

You make good points. I'll be away from the computer for much of the day, but will be pondering it.

[gregspurrier]

OK, I'm back at the computer for a few minutes before stepping out again. I've been thinking about it quite a bit and I think it's fine to make this change under the following reasoning (which you probably already went through when you were considering it for your Scheme port):

1. It does not change the observable behavior of do. The arguments are still evaluated left to right and the return value is still that of the second expression. Ruby will not optimize away the evaluation of the first expression.
2. do is already listed in System Functions and their Types in Shen as being a special form, so it is reasonable to expect that its evaluation may be different than a normal function.
3. This is essentially a change in performance--by enabling TCO where it would not otherwise be--and it's a net improvement in performance.

I'd like you to make two changes before I merge in the pull request:

1. Add a comment before compile_do explaining that do is not one of the K Lambda primitives, but is added here in order to enable TCO.
2. Add tests for the do special form. Specifically that: (1) that its expressions are evaluated left-to-right, (2) the value of the do form is the value of evaluating the second expression, and (3) that the first expression is evaluated even though its return value is discarded.

After that, I'll be glad to bring in this change.

[gregspurrier]

By the way, if you do not have time to make the changes I requested, please let me know and I'll take care of them when I have some time tomorrow.

[tizoc]

Hi Greg, happy new year!

I can do this today.

[tizoc]

Pushed.

[gregspurrier]

Happy New Year!

Thank you for the changes.