fram-lang / fram-lang/dbl

Subtyping failure for pure/impure functions under type constructors

Open
#324 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
OCaml
Stars
45
Forks
28
PR merge metrics
No merged PRs in 30d

Description

The interpreter currently treats type constructors like `List` and `Option` as invariant with respect to function purity. While a total function (`->`) is correctly treated as a subtype of an impure function (`->>`) in isolation, it does not recognize it correctly when nested inside a constructor as shown in the following REPL session.

```ml
> let id (x : Int) = x ;;
> id ;;
: Int -> Int
=
> let rec factorial (x : Int) = if x == 0 then 1 else x * (factorial (x-1)) ;;
> factorial ;;
: Int ->[] Int
=
> let xs = [id, factorial] ;;
error: This expression has type List (Int ->> Int), but an expression was expected of type List (Int -> Int)
| let xs = [id, factorial] ;;
| ^^^^^^^^^^
|
> let ys = [factorial, id] ;;
error: This expression has type List (Int -> Int), but an expression was expected of type List (Int ->> Int)
| let ys = [factorial, id] ;;
| ^^^
|
> let (x : Option (Int ->> Int)) = Some id ;;
error: Annotating pattern with type Option (Int ->> Int), but it was expected to match values of type Option (Int -> Int)
| let (x : Option (Int ->> Int)) = Some id ;;
| ^^^^^^^^^^^^^^^^^^^^
|
> let (x : Option (Int ->> Int)) = Some (id : Int ->> Int) ;;
>
```

It is possible to circumvent that problem by explicitly annotating the value under the constructor with the supertype, but it would be nice if the interpreter did it automatically.
```ml
> let zs = [factorial, (id : Int ->> Int)] ;;
> let (y : Option (Int ->> Int)) = Some (id : Int ->> Int) ;;
>
```

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by reproducing the List and Option examples in the issue's REPL session, then trace the interpreter's subtype checking for function purity under type constructors. Done means the examples accept pure functions where impure functions are expected without explicit annotations, while preserving the existing standalone function-subtyping behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
ocaml
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.