Arc Forum | Y combinator in arc

Arc Forum

Y combinator in arc

3 points by mpr 3027 days ago | 7 comments

Y combinator in mit-scheme

    (define Y
      (lambda (f)
        (let ((g (lambda (h)
                   (f (lambda (x)
                        ((f (h h)) x))))))
          (g g))))

Y combinator in Arc

    (def Y
      (fn (f)
        (let g (fn (h)
                 (f [(f (h h)) _]))
          (g g))))

The shortest working definition of Y I can think of. It makes use of Arc's bracketed anonymous functions of a single argument. These types of bracketed anonymous functions of one argument cannot be nested as they all bind their argument to the underscore.

What if they could be nested? Maybe the outermost function would bind its argument to @0, and subsequently nested functions would bind their arguments to unique variables by incrementing the integer (@0, @1, @2, ...). Then we could write Y quite compactly like this.

    (def Y [let g [@0 [(@0 (@1 @1)) @2]] (g g)])

2 points by akkartik 3019 days ago | link

Interesting idea; can you think of any other uses for it?

FYI, Anarki uses _1, _2, etc. to support anonymous functions with more than one argument. It might get confusing to have both. So which would you choose?

-----

3 points by mpr 3019 days ago | link

Considering it for about a minute, I say bracket functions of multiple args is better to have than nested bracket functions. The multiple args case applies more often I would guess. And the nested case is hard to parse, so taking away the power of the multi arg case to have the nested case doesn't seem worth it.

Edit: that is, hard for humans to parse

-----

2 points by zck 3018 days ago | link

I agree; the nested case is a bit difficult for humans to parse.

I wonder if there's a way to make (fn (x) ...) even more lightweight.

What if, to do the same thing, we had a new anonymous function syntax?

    {x ...}

It would work somewhat like this:

    arc> (let my-fn {arg (string "I got " arg)}
              (my-fn "this thing"))
    "I got this thing"

This is somewhat analogous to "let"

    (let x ...)

It could also allow for multiple arguments, like this:

    {(x y} ...)

Allowing for multiple arguments prevents destructuring-bind style function calls, though, which is a downside. I guess you could use other kinds of brackets for that?

    {{x y} ...};; this would be non-destructuring-bind
    {(x y) ...};; this is destructuring-bind
    {{(x y} ...);;; this is the same as #2; it would destructuring-bind the first argument, a list.

Heck, we could even build it into the existing anonymous function syntax:

    [{x y} ...]

Would be the same as

    (fn (x y) ...)

But I'm not sure that's a big enough win.

-----

3 points by mpr 3018 days ago | link

As per akkartik's comment, we already have multi-argument anonymous functions in anarki:

    ([prn _1 _2] "hello " "there")

But yeah maybe having full lambda list capabilities in the anonymous function would be cool.

    ([((a b) c) (prn c b a)] (list "is" "name ") "my ")

So if the first argument to the bracket function is a list, it acts as a lambda list.

But this interferes with the arc special syntax of having lists act as functions on their indices. Because the following is already valid arc code:

    (let x (list 1 2 3)
      (x 2))
    ;; > 3

In that case having different delimiters might be the way to go. So your brace notation would be used for anonymous functions with full lambda list capability.

    (let x (list 1 2)
      ({((a b) c) (prn c b a)} x 3))

Edit: trying some other formatting...

    (with (f {((a b) c)
               (prn c b a)}
           x (list 1 2))
      (f x 3))

-----

3 points by zck 3018 days ago | link

I was thinking that if you have an even simpler way to bind specific variables in the function call, you can nest these anonymous functions, and not have the arguments shadow each other.

> In that case having different delimiters might be the way to go. So your brace notation would be used for anonymous functions with full lambda list capability.

Yeah, I think you're right. The square-brace anonymous function could have optionally a curly-braced first argument. If that argument isn't there, it works as the square-braced anonymous function currently does. If that argument is there, it's the arguments to that function. Since curly braces aren't used anywhere else in Arc, it can only be parsed in that one way.

But perhaps this is all a lot of work to avoid writing `fn (arg1 arg2)`. Other than golfing, I don't know if you really want to nest functions this way. And this seems like a waste of the only paired characters Arc doesn't use.

-----

3 points by rocketnia 3018 days ago | link

"And this seems like a waste of the only paired characters Arc doesn't use."

I don't think even the [] syntax really pulls its weight. Between (foo [bar baz _]) and (foo:fn_:bar baz _), the latter is already more convenient in some ways, and one advantage is that we can define variations of (fn_ ...) under different names without feeling like these variations are second-class.

(Arc calls it "make-br-fn" rather than "fn_", but I wanted the example to look good. :-p )

-----

2 points by zck 3018 days ago | link

Interesting.

Personally, I've never gotten comfortable with the colon intrasymbol syntax. Even in your example, I'm having trouble parsing it right now. I really don't like how it makes "bar" look like part of the first part, not the second.

-----