Arc Forum | Recursive functions defined using "let"

Arc Forum

Recursive functions defined using "let"

1 point by Pauan 5158 days ago | 14 comments

Why can't I do the following?

  (let rec (fn (x) (rec x)))

Is there a technical reason? Is there a better alternative? I am aware that I can use "def" to create named functions, and "rfn" and "afn" to create recursive functions, but what if I want to do this:

  (let rec (fn (x) (rec x))
    (def foo (x) (rec x)))

This is supposed to create a private function "rec" that can call itself, and can also be called by the global function "foo", but is hidden from everything else. Is there a better way to do this? Am I completely wrong in trying to make the recursive function accessible only to "foo"? The following works, but feels clunky to me:

  (let rec (afn (x) (self x))
    (def foo (x) (rec x)))

P.S. This is not the code I'm using; it's used only as an example. If run, it would create an infinite loop.

P.P.S. Sorry if this has been brought up before. A quick search on Google didn't bring up anything, but a more thorough search found a similar situation: http://arclanguage.org/item?id=7815

2 points by waterhouse 5158 days ago | link

The reason it doesn't work is that in the code

  (let rec (fn (x) (rec x)))

the "rec" inside (fn (x) ...) refers to the global value of "rec". One might conceivably change the semantics of "let" so that this didn't happen, but then I'd be annoyed because, as rocketnia says, you wouldn't be able to say (let x (+ 1 x) ...). Also, "let" expands to a call to "fn", and one of the things about functions is that you should be able to take a function, rename one of its arguments (and all its uses in the body of the function), and get the same results:

  ; to use akkartik's example
  (let rec (fn (x) (rec x))
    (rec 3))
  ; expands to
  ((fn (rec)
     (rec 3))
   (fn (x)
     (rec x)))
  ; which should be the same as
  ((fn (meh)
     (meh 3))
   (fn (x)
     (rec x)))

There is an alternative semantic for functions, known as "dynamic scope", in which it does matter what names you give to your arguments, and your original "rec" example would work. The thing we have instead of "dynamic scope" is called "lexical scope". I think most people agree that lexical scope is better, though sometimes they encounter particular cases where they want dynamic scope; Common Lisp allows you to declare variables "special" with forms called "defvar" and "defparameter", while Racket/Scheme provides "parameters". Some people (aw and maybe others) have worked out ways to import Racket/Scheme's parameters into Arc; search this forum for "defvar", "implicit", "dynamic", or "parameter".

Now, it is possible to create local recursive functions without using assignment. If you want to do something like "letrec" without assignment, basically you pass the let-environment as extra arguments to your local functions:

  ;The following function is the same as factorial:
  (fn (n)
   ((fn (fact)
      (fact fact n))
    (fn (fact k) ;the "fact" function
      (if (is k 1)
          1
          (* k (fact fact (- k 1)))))))

  ;The following function is the same as "even":
  (fn (n)
    ((fn (even odd)
       (even even odd n))
     (fn (even odd n) ;the "even" function
       (if (is n 0)
           t
           (odd even odd (- n 1))))
     (fn (even odd n) ;the "odd" function
       (if (is n 0)
           nil
           (even even odd (- n 1))))))

The above examples are paraphrased from SICP: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-26.html...

-----

1 point by akkartik 5158 days ago | link

Ooh, thanks for the connection with dynamic scope.

-----

1 point by akkartik 5158 days ago | link

  arc> (macex '(let rec (fn(x) (rec x))
                 (rec 3)))
  ((fn(rec)
     (rec 3)) ; A
   (fn(x)
     (rec x))) ; B

It seems rec has been replaced inside A by (fn(x) (rec x)), and there's no binding for rec in there.

I suppose that's the technical reason: to let a fn be recursive you'd need to give it a name right there. And that's what rfn does. Perhaps you could make the name optional, do 'the right thing' when you get a name, and get rid of the rfn name.

I'm not sure how you'd compile fn to do this as a macro, though. You may need some knowledge of the surrounding form. Scheme has something called letrec (http://download.plt-scheme.org/doc/html/reference/let.html) which seems to do this, and common lisp has labels (http://www.lispworks.com/documentation/HyperSpec/Body/s_flet...) but perhaps there's a way to define let in a way that removes the need for them.

-----

2 points by Pauan 5158 days ago | link

I think so. The Arc source for "rfn" just uses "let" to initialize the variable to nil, then assigns a function to the variable. I'll try and see if I can come up with a simple definition of "let" that works like letrec. I think it would be great if Arc could have a simple unified "let", rather than multiple similar-but-slightly-different forms.

-----

3 points by rocketnia 5158 days ago | link

I like it just the way it is in this regard. If (let x (+ 1 x) ...) can get the 'x from the outer scope, then (let x (fn () x) ...) should be able to get that 'x too. Besides, I like minimizing the number of times I type a local variable name; the name 'self is often much shorter than the name of my function, and I have less editing to do if I decide to rename it. (I can find-and-replace, but that leaves me with indentation to fix.)

At one point I wanted to unify all lets to be Haskell-style, so that you could do crazy things like building arbitrary cyclic data structures:

  (let x (cons 1 y)
       y (cons 0 x)
    (iso (firstn 4 x) '(1 0 1 0)))

After all, recursive functions are cyclic data structures in a sense.

But now I think that's a job for a more pure language; as far as I can tell, it requires partial evaluation and lazy (or at least non-strict) semantics. I'm sure I'm wrong, 'cause strict Haskells exist, but I'm not sure what they do here.

Here's my comment from a similar thread that came up a while ago, which might help if you're looking for a 'letrec implementation: http://arclanguage.org/item?id=12418

-----

1 point by aw 5158 days ago | link

The key point is that in

  (some-let foo (... foo ...)

sometimes you might want the reference to "foo" to refer to the foo you are currently defining, or to the foo in the enclosing scope.

There are a couple ways to do this.

One way is that you can use different names for some-let to indicate which one you want.

For example, you could have "let" mean to use foo from the enclosing scope (which is what Arc does now), and have "letrec" mean to use the foo that you're defining.

Or, if you prefer, you could have "let" mean to use the foo that you're defining (and so would work like what we've been calling letrec), and make up another name ("let-parent" or something) for the other kind of let which works like Arc's let does now. You might prefer this if you use the former more often than the latter.

Choosing different names for let isn't the only way to distinguish between the two possibilities. You could modify the Arc compiler so that let worked the way it does now, except that you add a syntax to get at the foo being defined:

  (let rec (fn (x) (this.rec x)))

or, if you wanted let to work like letrec by default instead, except that you needed some way of sometimes referring to the enclosing foo, you could create a syntax for that:

  (let x (+ 1 parent.x) ...)

-----

1 point by Pauan 5158 days ago | link

Yes, that's what I'm saying. I understand now that sometimes it is useful to pull in a variable from an outer scope, but sometimes you want the behavior of letrec. I'm pretty sure letrec would be trivial to write as a macro, so this discussion is more about which should be the default. Do people usually want the outer scope, or the inner?

P.S. I whipped up a quick version of letr; it seems to work okay:

  (mac letr (var val . body)
    `(let ,var nil
       (assign ,var ,val)
       ,@body))

P.P.S. Adding more syntax would also solve it, but I actually would prefer to give them two different names. It just seems cleaner and less cluttered to me.

-----

2 points by akkartik 5158 days ago | link

That makes sense. But why is:

  (letr rec (fn (x) (rec x))
    (rec 3))

superior to

  (let rec (afn (x) (self x))
    (rec 3))

?

-----

1 point by Pauan 5158 days ago | link

For me, two reasons:

1) afn is somewhat of an anomaly. When I see "fn" I know "this is a function" but when I see "afn" I have to pause for a split second to realize what it does.

2) Pattern recognition due to redundancy. When I glance at the first version, my eyes quickly notice that there are 3 references to "rec", and thus I immediately form a pattern in my mind. But in the second version, there are two references to the same function: self and rec. This adds an additional cognitive overhead for me.

In other words, the first one appears less cluttered to me because it has fewer unique elements, and because "fn" is more familiar to me than "afn".

It's not a huge deal, but I would like to reduce the cognitive overhead of reading and writing code as much as I can, which is one of the things I really like about Arc: it's clean, simple, and short, but allow tons of flexibility to change the language to suit the way you think.

-----

1 point by akkartik 5158 days ago | link

"You could modify the Arc compiler so that let worked the way it does now, except that you add a syntax to get at the foo being defined"

I was thinking along these lines as well. How about:

  (let (def rec(x) (rec x))
    (rec x))

-----

2 points by aw 5158 days ago | link

Why do you want to create a private function that can be called from "foo" but is hidden from everything else?

-----

1 point by Pauan 5158 days ago | link

The function might have some internal state, like variables or helper functions. I don't want those to clutter up the namespace, nor do I want them to be mucked up by other code.

-----

1 point by rocketnia 5157 days ago | link

I used to have top-level (let ...) forms here and there for exactly the reasons you described, but sooner or later I regretted not being able to view those values at the REPL during debugging. For instance, Lathe's 'multival-cache* [1] is an implementation detail for the multival framework (which I won't go into here), but it turns out to be really useful to inspect when the framework goes awry.

In any case, I welcome the ability for people to muck with my code, 'cause it's a good way to experiment with making it better. ^_^ Just because something's exposed doesn't mean it's part of a stable API, especially in Arc where things are assumed unstable by default.

Cluttering up the namespace is still an issue, but the obvious advice is to choose unique names. ;) If you're still very worried about it, like I am, I humbly suggest you look at Lathe's namespace system.

[1] I made 'multival-cache* global at https://github.com/rocketnia/lathe/commit/f411a3848275de8510....

-----

1 point by Pauan 5157 days ago | link

Alright, thanks. I'll keep that in mind.

-----