control flow: loops

[quinn-dougherty]

Allow the user to write conditionals and loops in squiggle

EDIT: this is the loops issue. See 174 for if.

[Hazelfire]

Should this be like... functional loops and conditionals? I feel like it would be useful for Squiggle code to have guaranteed termination

[umuro]

Not loops, instead:
map, reduce, reject

[OAGr]

I'm pretty unsure here. I think conditionals are probably needed. Loops with control flow are more controversial; I'm not very sure here. We could try pushing loops off for a while.

Control flow is tricky to reason about, because we need to decide how to treat distributions in different cases.

[Hazelfire]

Agreed, I think loops and conditionals come up surprisingly little in practical models. I don't believe this is a priority

[quinn-dougherty]

Please discuss if on #174 -- this issue is for the loop question.

[umuro]

Termination, Recursion and Functional Programming.

• All loops lead to non-terminating code
• All recursion lead to non-terminating code

The solution to this is map-reduce operations. And all functions can be written using map-reduce operations instead using recursion or loops.
Example:

factorial 0 = 1
factorial n  = n * factorial n-1

If I make a typing mistake

factorial 0  = 1
factorial n  = n * factorial n+1 

then this is a non-terminating code.
However, I can write the same code using map-reduce logic
factorial n = (n..0) -> reduce( 1, \i, acc => if (i==0) then acc else i * acc )
Here we might need some creativity so that map-reduce operations are more natural and readable... But... Termination is guaranteed! And there is a way to write everything. For some cases, some languages provide syntax sugar for map-reduce operations.

factorial n = for i in (n..0)
     first acc is 1
     then acc is  \i, acc =>  
         if i == 0
             then  acc  
             else  i * acc

Or even,

factorial n = for i in (n..0)
     first acc is 1
     then acc becomes
         if i == 0
             then  acc  
             else  i * acc

Ordinary loops are not worth discussing even. They are totally evil.

Make map-reduce available -> put some syntax sugar to make it user friendly

Remember that for any solution we need the custom parser. But when we have the custom parser then we can have all the syntax sugar. It does not have to be dull function calls...

[Hazelfire]

Hey Umur! Just a thought. Can't you get non-terminating code without (explicitly self referential) recursion?

apply_self x = x(x)
run_forever = apply_self(apply_self)

So in the end... We might need to add some sort of type checker for something like simply typed lambda calculus if we wanted to ensure non-termination?
I was thinking we could then apply a really rudimentary type inference algorithm, like Hindley-Milner, to ensure that all functions don't terminate?

Maybe we should have a meeting sometime about non-termination

[OAGr]

My guess is that it will be tricky to ensure non-termination. Also, there are other measures we could have to help, like timeouts.

My strategy has been something like, "don't make it easy for users to shoot themselves in the foot, but also, it's not too important to make sure they have absolutely no way to."

That said, if it's surprisingly easy to ensure, that could be great.

[Hazelfire]

Yes it is tricky xD. Although I've done it before for Pedant. I am being mildly nerd sniped by the fact that it's such an interesting problem to work on though.

[OAGr]

I think I'm happy to introduce map/reduce, before considering loops. (And for those, map is much more important than reduce)

[umuro]

Just map

doubleArray anArray =  for elem in anArray
    elem * 2

[umuro]

Note. There is a way to have non-terminating code without recursion.
But it requires anonymous functions and quite a determination
https://matt.might.net/articles/implementation-of-non-terminating-program-in-javascript-without-loops-iteration-recursion/