Consider implementing loops

[vks]

As far as I know, it is currently not possible to implement loops without resorting to recursion, which is limited by the stack size. It would be useful to have efficient loops in the language.

[murarth]

Loops are based on mutable state. While mutable state technically exists in the interpreter, it's not available to Ketos code. I don't see how loops could work.

However, the interpreter does implement tail recursion optimization, allowing infinite recursion without filling up the stack. This definitely should have been mentioned in the docs and I'll write something up about it straight away.

[hauleth]

:+1: for TCO instead of loops. After that it would be nice to have macros like loop that would simplify that, but with TCO.

[vks]

Under which conditions is TCO guaranteed? The factorial example blows up the stack rather quickly...

[murarth]

The code in examples/calling.rs was intended to be simple; not necessarily optimal. I didn't want to complicate it with a taill-call-optimizable implementation. Perhaps it would be better replaced with a naive implementation of something else that doesn't involve recursion at all.

In low-level terms, tail call optimization is guaranteed any place where a recursive call occurs immediately before a Return instruction. That's the way the bytecode compiler generates a TailCall instruction.

In high-level terms, any recursive function call in a tail position should become a tail call. If it doesn't, it's a bug. Note that this only applies to recursive calls.

[qthree]

I don't see how loops could work

Easy!

extern crate ketos;
use ketos::Interpreter;

fn main() {
    let interp = Interpreter::new();

    let _out = interp.run_code(r#"

(define (for from to body)
  (if
    (< from to) (do (body from) (for (+ from 1) to body))
  )
)
(define (hello x) (println (format "Hello ~d" x)))
(for 0 5 hello)
(for 0 5 (lambda (x) (println (format "World ~d" x)) ))

        "#, None);
}

[murarth]

@qthree: It looks like a loop (kind of), but there's no mutable state being modified in the body. That's what I was saying wouldn't work. Local bindings can't be modified. Maybe you could do something crazy with define, but... please don't.

[hauleth]

But that is how loops In Lisps works, almost. In Scheme there are loop macros which translates almost to that (they use let to not pollute global namespace).

Łukasz Jan Niemier

Dnia 16 mar 2016 o godz. 05:27 Murarth notifications@github.com napisał(a):

@qthree: It looks like a loop (kind of), but there's no mutable state being modified in the body. That's what I was saying wouldn't work. Local bindings can't be modified. Maybe you could do something crazy with define, but... please don't.

— You are receiving this because you commented. Reply to this email directly or view it on GitHub

[ghost]

I really don't think loops are necessary. However, I think a lot of imperative programmers find comfort in having some kind of list comprehension syntax, sort of like Elixir's for.

[murarth]

List comprehension and perhaps other styles of loop could be implemented via macro.

[hauleth]

@murarth alternatively you could provide only general loop with break and implement rest using macros.

[murarth]

@hauleth: It's conceivable, yes, but I don't believe it would be of much use without the ability to mutate values and/or bindings.

In Common Lisp implementations, values can be mutated. Ketos, however, uses a model of shared ownership and copy-on-write. (Some Value variants contain an Rc.) It would be possible to implement an operator that assigns a new value to a local let binding, but I think that a half-hearted mutation operator of this kind would only cause confusion because of the general absence of mutation facilities.

Without general mutation, imperative programming styles are less effective and a loop construct with break is, in my opinion, not significantly more useful than a tail-recursive function. If I'm wrong, please provide some hypothetical code examples for things that can't easily be done without looping and break.

[vklquevs]

For what it's worth, I think a construct that implicitly repeats a block of code (unless you tell it not to) is less intuitive than a construct that executes a block of code once (unless you tell it to execute again). Really, loop-with-break is functionally identical to run-with-rerun, just with the logic inverted.

Fixed-point combinators let you write loops without explicitly using recursion, which should keep everyone happy (?):

ketos=> (define (fix f v) (f (lambda (w) (fix f w)) v))
fix
ketos=> (fix (lambda (fact n) (if (< (first n) 1) (second n) (fact (list (- (first n) 1) (* (second n) (first n)))))) (list 50 1))
30414093201713378043612608166064768844377641568960512000000000000

(This example blows up the call stack at around 350 or so for me, but you get the idea.)