Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

letrec* incorrectly reorders statements #659

Closed
fare opened this issue Jan 19, 2021 · 12 comments
Closed

letrec* incorrectly reorders statements #659

fare opened this issue Jan 19, 2021 · 12 comments

Comments

@fare
Copy link
Contributor

fare commented Jan 19, 2021

R7RS says that letrec* should not reorder the side-effects, that will happen from left-to-right, but this function, when compiled (as opposed to interpreted, which works correctly), reorders line 300 below line 500, which is incorrect. Presumably, it detects that 400 and 500 do not "depend" on x (or anything else defined in the letrec*), whereas 300 does.

":" ; ( echo -e 'INTERPRETED' ; gsi letrec-star-reordered.scm; echo -e '\nCOMPILED' ; gsc letrec-star-reordered.scm && gsi -e '(load "letrec-star-reordered")' ) 2>&1 | less

(define (displayln . a) (for-each display a) (newline))

(define (reordered)
  (letrec* ((x (begin (displayln 100) 42))
            (_200 (displayln 200))
            (_300 (displayln 300 (list x)))
            (_400 (displayln 400))
            (y (begin (displayln 500) 23)))
    (displayln 600 (list y))))

(reordered)
@fare
Copy link
Contributor Author

fare commented Feb 10, 2021

Marc said on gitter: Concerning the implementation of letrec*, there are two implementations… a correct one in the interpreter (procedure ##comp-let-like-form in lib/_eval.scm) and a buggy one in the compiler (procedure pt-recursive-let in gsc/_ptree1.scm).

@SamuelYvon SamuelYvon mentioned this issue Mar 5, 2021
Closed
gambiteer added a commit that referenced this issue Jul 30, 2021
@gambiteer
Fix reordering of clauses in letrec*
47f2eb7 
Fix by SamuelYvon; fixes issue #659.
@gambiteer
Copy link
Collaborator

Fixed by 47f2eb7

@gambiteer
Copy link
Collaborator

Sometimes we make mistakes. Reopening.

@gambiteer gambiteer reopened this Jul 30, 2021
@fare
Copy link
Contributor Author

fare commented Jul 21, 2023

NB: the fix was immediately reverted in the next commit d1a6c6b because it broke some regression tests... that I believe might need be updated.

@SamuelYvon
Copy link

SamuelYvon commented Jul 22, 2023 •
edited

@fare

$ ./gsc/gsc
Gambit v4.9.4-211-g97e4bff5

> (define (displayln . a) (for-each display a) (newline))
> (define (reordered)
   (letrec* ((x (begin (displayln 100) 42))
            (_200 (displayln 200))
            (_300 (displayln 300 (list x)))
            (_400 (displayln 400))
            (y (begin (displayln 500) 23)))
    (displayln 600 (list y))))
> (reordered)

100
200
300(42)
400
500
600(23)

Isn't this the desired behaviour?

@fare
Copy link
Contributor Author

fare commented Jul 22, 2023

Yes, this is the desired behaviour. As of 4.9.4-210-g420f1e5e, it works in the interpreted case, and fails in the compiled case with

100
200
400
500
300(42)
600(23)

@SamuelYvon
Copy link

Do you have a link to the spec where conditions about reordering can be found?

@fare
Copy link
Contributor Author

fare commented Jul 23, 2023

I suppose that would be r7rs section 4.2.2 "Binding constructs": https://standards.scheme.org/corrected-r7rs/r7rs-Z-H-6.html#TAG:__tex2page_sec_4.2.2

@SamuelYvon
Copy link

I see. I'm still trying to wrap my head around the exact semantics. Can you confirm that this following example would be illegal:

(letrec* ((x (lambda (...))
          (y x))
          <body>)

@fare
Copy link
Contributor Author

fare commented Aug 12, 2023

Why would that be illegal? You bind x then you bind y to x. What would be illegal is trying to bind y to x before x was bound.

@SamuelYvon
Copy link

SamuelYvon commented Aug 12, 2023 •
edited

It was too early in the morning, my example is miswritten, I was trying to construct something that refers to:

If it is not possible to evaluate each without assigning or referring to the value of the corresponding or the of any of the bindings that follow it in
, it is an error

from the R7RS spec. Flipping the <init> would be a valid example of that.

Something like this "breaks" in chicken scheme:

(letrec* ((x y)
          (y (lambda (z) (+ z 5))))
         (print x))

since x cannot be bound left-to-right. Looking at the code, it seems the problem stems from the topological sort of the dependency graph. I think the implementation is a bit more complex than it needs to be, but I'm not sure I fully understand the semantic of letrec* (thus why I'm trying to see if those are valid edge cases)

@gambiteer gambiteer mentioned this issue Aug 12, 2023
Closed
@fare
Copy link
Contributor Author

fare commented Aug 15, 2023

Agreed. (Except I make no comment on the implementation, that I didn't look at properly). letrec* might not need any topological sort at all.

vyzo added a commit to mighty-gerbils/gerbil that referenced this issue Sep 18, 2023
@vyzo
update gambit to 24201248effa23d5017be4992b5b9879e4cd3a4c
28ec6e7 
Important fix affecting Gerbil, wrt compilation of letrec*.

See gambit/gambit#659
@vyzo vyzo mentioned this issue Sep 18, 2023
Merged
fare pushed a commit to mighty-gerbils/gerbil that referenced this issue Sep 18, 2023
@vyzo
Update gambit pin (#870)
4eecb14 
Pin gambit to 24201248effa23d5017be4992b5b9879e4cd3a4c

Important fix affecting Gerbil, wrt compilation of letrec*.

See gambit/gambit#659
@fare fare mentioned this issue Nov 28, 2023
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@fare @gambiteer @SamuelYvon