racket / racket/typed-racket

Passing Listof to a (List 'x ... A) can cause unsound results

Open
#494 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

unsound
Dominant language
Racket
Stars
575
Forks
106
Avg merge
2h 1m
Merged PRs (30d)
2

Description

What version of Racket are you using?

6.8.0.1

What program did you run?
#lang typed/racket

(: f (∀ (A ...)
        (-> (List 'x ... A)
            (-> (List 'a ... A)))))
(define ((f xs))
  (map (λ (x) 'a) xs))

((f (map (const 'x) (range 3))))
;; =>
;; - : (Listof Nothing)
;; '(a a a)
What should have happened?

The ((f (map (const 'x) (range 3)))) expression should produce a (Listof 'a), not a (Listof Nothing). The current result type is unsound, and allows 'a to be "cast" as Number:

(car (ann ((f (map (const 'x) (range 3))))
          (Listof Number)))
;; =>
;; - : Number
;; 'a

Note that this does not happen if f directly returns the (List 'a ... A), there has to be a nested function type, otherwise the argument is simply rejected (which at least is not unsound).

If you got an error message, please include it here.

Contributor guide

No contributing guide indexed for this repository

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.

Research direction

Start by running the supplied #lang typed/racket reproducer and compare its inferred type with the expected (Listof 'a). Investigate the nested polymorphic function case involving (List 'x ... A) and verify that the ann expression can no longer treat 'a as Number; the issue names no source file or test path.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.