Bug with letrec call/cc interaction

Open
#946 8 comments 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 1 day

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
35/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Stale
Domain
compilers

Research direction

Start by reducing the reported Scheme examples and comparing the letrec and letrec* results, especially when the lambda call appears in both branches of an if expression. The issue reports the incorrect result as 9 instead of 4 and says the behavior was tested on Chez Scheme 10.2.0; use that case to locate the compiler or runtime path responsible. Done means letrec returns 4 in the failing case while the stated letrec* behavior remains intact.

Written by the indexing model from the issue text.

Description

If a lambda re-enters a letrec initialisation expression using a continuation from call/cc, and specifically that lambda is referred to in both branches of an if-expression, it will have the wrong behaviour.

For background, letrec differs from letrec*, in that letrec assigns all of its variables after all of their corresponding initialisation expressions have been evaluated, whereas letrec* assigns its variables one at a time after each corresponding initialisation expression has been evaluated. This difference leads to different behaviours with the following program, which mutates one of the letrec variables before re-entering another variable by its contiuation:

(let ((f (lambda ()
                 (letrec[*] ((a 4) (j (call/cc (lambda (cc) cc))))
                     (if (eqv? j 0)
                         a
                         (begin
                          (set! a 9)
                          (j 0)))))))
      (f))

With letrec* the mutation persists and results in the value 9, because a has already been initialised by the point of the call/cc. With letrec, the mutation is overwritten back to a 4, because a has not yet been initialised by the point of the call/cc, and is assigned 4 again after re-entering the initialisation expression for j.

Chez Scheme has the correct behaviour in this example. However, if f is instead reached through an if-expression, and particularly if f is referenced in both branches, letrec has the incorrect behaviour which seems to correspond with letrec*, and gives 9 rather than 4.

(let ((f (lambda ()
                 (letrec ((a 4) (j (call/cc (lambda (cc) cc))))
                     (if (eqv? j 0)
                         a
                         (begin
                          (set! a 9)
                          (j 0)))))))
      (if #t (f) (f)))

This example incorrectly produces 9. The correct behaviour should be to produce 4. This happens regardless if the true or false branch is taken. It does not happen if f is only referred to in one of the branches, i.e. (if #t (f) 0) gives 4.

Tested on 10.2.0, NixOS. Correct behaviour witnessed on Chicken.

Dominant language
Scheme
Stars
7.4k
Forks
1k
Avg merge
1d 20h
Merged PRs (30d)
19

Getting set up

This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from cisco/ChezScheme

All issues in cisco/ChezScheme

Similar issues

More Compilers issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.