FStarLang / FStarLang/FStar

Pulse expects type constructors to be injective

Open
#4,239 3 comments 0 reactions 0 assignees View on GitHub
Dominant language
F*
Stars
3.1k
Forks
266
Avg merge
21h 1m
Merged PRs (30d)
54

Description

The following is code that works in F*, but not in Pulse:

```fstar
module Natlt
open Pulse.Nolib
#lang-pulse

let natlt (n: nat) = i:nat { i < n }

let works #n (x: natlt n -> bool) (i: nat { i < n }) =
let a: (natlt i -> bool) = x in
()

fn doesnt_work #n (x: natlt n -> bool) (i: nat { i < n }) {
let a: (natlt i -> bool) = x;
()
}
```

Looking at the debugging output, the core type checker produces the guard `forall (_: Natlt.natlt i). i == n` which is obviously not provable.

Contributor guide

Open the contributing guide

Research direction

Start with the Natlt reproduction using Pulse.Nolib and compare the working let example with the failing fn example. Inspect the core type checker’s debugging output around the guard forall (_: Natlt.natlt i). i == n. Done means the fn example type-checks without producing an unprovable guard.

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
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.