Binary lambda calculus output is broken

[andersk]

The binary lambda calculus output is broken, and moreover, breaks differently depending on the input parenthesization.

$ mel '(a -> a).blc'
000
$ mel '((a -> a)).blc'
00010000
$ mel '(((a -> a))).blc'
0001000010000
$ mel '((((a -> a)))).blc'
000100001000010000

The correct output for all of these cases is 0010.

[VictorTaelin]

You are right, the BLC output was incorrect and is fixed now. But notice (a -> a) and ((a -> a)) are different. A lone parenthesis isn't redundant, it denotes an unary tuple. So, ((a -> a)) is actually the same as (t -> (t (a -> a))). As you add more parens, you further wrap the inner term within tuples.

[andersk]

What do you think about using (x,) rather than (x) for unary tuples, like Python, so that adding and removing plain parentheses is free?

That would also mean we could consistently allow (a -> a a) instead of requiring (a -> (a a)).

[VictorTaelin]

@andersk not sure I like it, what would be the point of adding redundant parens? Also, I think we can already allow (a -> a a) without ambiguity, no? Just that I didn't implement it.

[andersk]

It’s pretty common for redundant parens to show up while I’m refactoring something—especially since the current grammar forces you to write a lot of parens that you wouldn’t expect based on other languages and it’s hard to keep track of them all.

Yes, we could already allow (a -> a a), but it may be confusing to have (a -> a a) = (a -> (a a)) ≠ (a -> ((a a))). The trailing comma would make it clear which parens are tuples and which ones are just grouping.

[VictorTaelin]

I understand. That might be frustrating. I do think you have a good point. But I don't like the solution, as it might cause confusion in the case I will describe. The current tuple syntax is consistent in a sense it can be used as uncurried argument lists. For example, suppose we do remove the need for () for application after = and inside tuples/arrays (which is planned). This is how you could use tuples to emulate procedural function calls:

-- Adds 2 church nats
add x y = s z -> (x s (y s z))

-- "apply to args" operator
! f x = x f

-- 1 + 2, lisp-style
main = (add (add 1 2) (add 3 4))

-- but with tuples, we can easily emulate the procedural function call:
main = !add(!add(1,2), !add(3,4))

-- we can even separate the arg lists
main = !add args
    args = (!add(1,2), !add(3,4))

Now, suppose I just taught a novice that trick. He might, then, assume this is valid:

main = !double(1)

But if we don't allow unary tuples, it isn't. We need, thus, to teach a special case: "tuples can be used for function calls, except for unary functions". Which is bad, IMO. Moreover, I consider it a good feature that, in the current syntax, every () is significant - it naturally avoids redundant parens, which bloat the code, and force you to pay more attention.

I do agree with your feeling that unary tuples are confusing and frustrating, even more so due to the fact we are used to languages where redundant parens can be placed anywhere. But under those arguments I'm tempted to leave it this way. Let me know what you think.

[andersk]

By the same argument, your novice might write

main = !double(!add(1, 2))

And it won’t work—whether or not (1) is a unary tuple, (!add(1, 2)) can’t be one.

Some alternate suggestions for tuples, if you don’t like Python’s choice:

• <>, <x>, <x, y>, <x, y, z>?
• '(), '(x), '(x, y), '(x, y, z)?
• (), (x,), (x, y,), (x, y, z,), with the trailing comma always required, for consistency?

[VictorTaelin]

Sorry, why wouldn't main = !double(!add(1, 2)) work?

<> and '() look fine to me, I personally just don't like the last one. Why would you pick it?

[andersk]

Sorry, why wouldn't main = !double(!add(1, 2)) work?

Because (!add(1, 2)) is just 3, not (as the novice might naïvely extrapolate) the unary tuple containing 3, this evaluates to !double 3 = 3 double rather than to double 3.

I don’t think I have a preference for <> vs. '(). The latter idea was sort of inspired by LISP, but the analogy is far from perfect.

[VictorTaelin]

Ah, fair enough. That indeed looks confusing. I'm tempted to say <> might be the best solution, though. Why do you prefer the trailing comma version, again?

[andersk]

Using <> would make it hard to define comparison functions like <, >, <=, >=. Not a showstopper though. Most people probably aren’t expecting to be able to use punctuation in identifiers anyway.

[VictorTaelin]

But then, are <, >, etc., really useful if we don't have infix operators? I'm still undecided if we should have them.