3 ms·

Author here. Why would it? Let's have a look at Scheme letrec (or let* in Emacs Lisp) translated to pseudo-SectorLISP: (LETREC ((IS-ODD? (QUOTE (LAMBDA (X

by jart 5y ago

Author here. Why would it? Let's have a look at Scheme letrec (or let* in Emacs Lisp) translated to pseudo-SectorLISP: (LETREC ((IS-ODD? (QUOTE (LAMBDA (X) (CAR X)))) (IS-EVEN? (QUOTE (LAMBDA (X) (NOT (IS-ODD X)))))) (IS-EVEN? (QUOTE (NIL T NIL T)))) The oldskool LISP way of writing that is: ((LAMBDA (IS-ODD? IS-EVEN?) (IS-EVEN? (QUOTE (NIL T NIL T)))) (QUOTE (LAMBDA (X) (CAR X))) (QUOTE (LAMBDA (X) (NOT (IS-ODD X))))) As far as I can tell, letrec is just a nicer syntax for the same thing. So I don't know why it should require any mutability. It works probably because LISP is dynamically scoped. Most languages and modern LISP implementations prefer different scoping models to make the Assoc() equation faster. However that comes at a cost, since it can turn the difficulty of LISP up to 11. Next thing you know, you're discovering things like the Y combinator. So I have major respect for what languages like Haskell and Scheme are doing, because it's incredibly difficult. One of the reasons why I created SectorLISP is because I wanted to have a fun bastion of simplicity when I don't need the more mature tools. SectorLISP doesn't have any kind of internal mutability last time I checked. But I have experimented with it. For example, the Peel() optimization described in the blog post is how we solve the "make Assoc() faster problem". As it's written in the blog post, it's 100% pure. But if you introduce a tiny bit of mutability, it can go even faster on benchmarks even though it doesn't change the complexity class. See https://justine.lol/sectorlisp2/fast.js https://justine.lol/sectorlisp2/fast.js

dan-robertson 5y ago
I think you’ve a trivial error in your function definitions but I don’t think it’s relevant. I think you’re right about avoiding cycles. I think the parent was talking about a let rec construction for data, e.g. in Haskell: let funky_list = 1:2:3:4:funky_list (Note that : is the cons operator). If this is allowed then you may have issues. I think the problem is perhaps that the GC won’t work if you have pointers in the opposite of the normal direction. The fix though is relatively simple: add forwarding pointers (somehow), then after copying from the ‘B’ region to the ‘C’ region you leave behind a forwarding pointer and, if you see it again in your copying, you don’t make a duplicate copy of the data. Then I think you can proceed as before. But representing forwarding pointers efficiently is hard, I suspect. Actually I think I don’t understand the GC sufficiently. Do you end up with a lot of memory usage after this or a little? ((LAMBDA (D Z) (D Z)) (QUOTE (LAMBDA (X) (COND (X ((LAMBDA (Y) (CONS Y Y)) (D (CDR X)))) ((QUOTE T) (QUOTE T))))) (QUOTE (A A A A A A A A))) This should get you a binary tree about 8 levels deep with T on every leaf, and I think it should use linear memory (in the depth of the tree) but I don’t understand how the GC avoids ending up with an exponential amount of memory being used?
- jhgb 5y ago
  > a let rec construction for data Is there actually any Lisp dialect where letrec works for data? I'm not aware of such, at least where it comes to major ones (CL and common implementations of Scheme).
  - dan-robertson 5y ago
    Common Lisp let’s you write e.g. (list-length '#1=(1 2 3 4 . #1#)) But I think that isn’t what you mean.
  - dan-robertson 5y ago
    I don’t understand how to construct cyclic references using only letrec. Do you have a concrete example?
  - JonChesterfield 5y ago
    It would need a lazy data constructor and the lisp ones are (usually) strict. If you make cons et al lazy then letrec on data works as it does in other languages. Alternatively, make letrec wrap the values in thunks. The resulting cyclic structures are then moderately annoying to work with.
    - jhgb 5y ago
      Oh, I forgot lazy Lisps. But those would probably not be considered "major". > Alternatively, make letrec wrap the values in thunks. Aaaand of course I forgot that as well. My bad. So basically full lexical scoping and the presence of lambda should be enough to create cyclic structures, even in the absence of mutability.
- MaxBarraclough 5y ago
  > I think the parent was talking about a let rec construction for data You know more Haskell than I do ;-) What I had in mind were recursive and mutually recursive functions, defined with letrec, as examples of reference-cycles in functional programming.
- 5y ago
nils-m-holm 5y ago
LETREC requires mutability in the presence of lexical scope. Otherwise it works fine in the way you describe it. Using lexical scope, IS-ODD and IS-EVEN would be bound in parallel and (LAMBDA (X) (NOT (IS-ODD X))) would close over IS-ODD before it is bound, so it would be undefined when applied inside of the outer LAMBDA. Of course dynamic scoping will bite you earlier or later because of the upward and downward FUNARG problems. See my book (http://t3x.org/lfn/ http://t3x.org/lfn/) for lots of entertaining details.

by jart 5y ago

dan-robertson 5y ago

I think you’ve a trivial error in your function definitions but I don’t think it’s relevant. I think you’re right about avoiding cycles. I think the parent was talking about a let rec construction for data, e.g. in Haskell: let funky_list = 1:2:3:4:funky_list (Note that : is the cons operator). If this is allowed then you may have issues. I think the problem is perhaps that the GC won’t work if you have pointers in the opposite of the normal direction. The fix though is relatively simple: add forwarding pointers (somehow), then after copying from the ‘B’ region to the ‘C’ region you leave behind a forwarding pointer and, if you see it again in your copying, you don’t make a duplicate copy of the data. Then I think you can proceed as before. But representing forwarding pointers efficiently is hard, I suspect. Actually I think I don’t understand the GC sufficiently. Do you end up with a lot of memory usage after this or a little? ((LAMBDA (D Z) (D Z)) (QUOTE (LAMBDA (X) (COND (X ((LAMBDA (Y) (CONS Y Y)) (D (CDR X)))) ((QUOTE T) (QUOTE T))))) (QUOTE (A A A A A A A A))) This should get you a binary tree about 8 levels deep with T on every leaf, and I think it should use linear memory (in the depth of the tree) but I don’t understand how the GC avoids ending up with an exponential amount of memory being used?

jhgb 5y ago
> a let rec construction for data Is there actually any Lisp dialect where letrec works for data? I'm not aware of such, at least where it comes to major ones (CL and common implementations of Scheme).
- dan-robertson 5y ago
  Common Lisp let’s you write e.g. (list-length '#1=(1 2 3 4 . #1#)) But I think that isn’t what you mean.
- dan-robertson 5y ago
  I don’t understand how to construct cyclic references using only letrec. Do you have a concrete example?
- JonChesterfield 5y ago
  It would need a lazy data constructor and the lisp ones are (usually) strict. If you make cons et al lazy then letrec on data works as it does in other languages. Alternatively, make letrec wrap the values in thunks. The resulting cyclic structures are then moderately annoying to work with.
  - jhgb 5y ago
    Oh, I forgot lazy Lisps. But those would probably not be considered "major". > Alternatively, make letrec wrap the values in thunks. Aaaand of course I forgot that as well. My bad. So basically full lexical scoping and the presence of lambda should be enough to create cyclic structures, even in the absence of mutability.
MaxBarraclough 5y ago
> I think the parent was talking about a let rec construction for data You know more Haskell than I do ;-) What I had in mind were recursive and mutually recursive functions, defined with letrec, as examples of reference-cycles in functional programming.
5y ago

nils-m-holm 5y ago

LETREC requires mutability in the presence of lexical scope. Otherwise it works fine in the way you describe it. Using lexical scope, IS-ODD and IS-EVEN would be bound in parallel and (LAMBDA (X) (NOT (IS-ODD X))) would close over IS-ODD before it is bound, so it would be undefined when applied inside of the outer LAMBDA. Of course dynamic scoping will bite you earlier or later because of the upward and downward FUNARG problems. See my book (http://t3x.org/lfn/ http://t3x.org/lfn/) for lots of entertaining details.