Dafny: a cross-file contract that names a helper from its own file is lifted without the helper (unresolved, or opaque when imported)

オープン
#307 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
43/100
issue の種類
バグ
明瞭さ
明確に書かれている
活発さ
活発
技術スタック
typescript

調査の方向性

The report names i6lib.ts and i6.ts as reproductions, but does not identify implementation files or tests. Start by tracing how lsc check --backend=dafny i6.ts lifts imported function contracts and how Dafny output is generated. Reproduce the unresolved helper and opaque axiom cases; done means helper-dependent contracts either include transparent helper bodies or report the unsupported dependency at lift time.

索引モデルが issue の本文から書いたものです。

説明

Version: lsc 0.6.10 (npm), Dafny 4.11.

When file B calls a verified function from file A, lsc lifts A's //@ ensures into B's .dfy as an {:axiom} signature. If that ensures calls a helper predicate defined in A, the helper doesn't come with it.

i6lib.ts verifies on its own (2 verified, 0 errors):

//@ backend dafny
export function isPos(n: number): boolean {
  //@ verify
  return n > 0
}

export function bump(n: number): number {
  //@ verify
  //@ requires n >= 0
  //@ ensures isPos(\result)
  return n + 1
}

i6.ts:

//@ backend dafny
import { bump } from './i6lib.ts'

export function twice(n: number): number {
  //@ verify
  //@ requires n >= 0
  //@ ensures \result > 0
  return bump(bump(n))
}

lsc check --backend=dafny i6.ts emits:

function {:axiom} bump(n: int): int
  requires (n >= 0)
  ensures isPos(bump(n))
i6.dfy(5,10): Error: unresolved identifier: isPos

If B also imports isPos and calls it, the helper is emitted as a bodiless axiom, function {:axiom} isPos(n: int): bool. The lifted ensures then tells B nothing. Here bump(bump(n)) can't establish the inner call's requires n >= 0:

import { bump, isPos } from './i6lib.ts'
export function twice(n: number): boolean {
  //@ verify
  //@ requires n >= 0
  return isPos(bump(bump(n)))
}
i6x.dfy(12,12): Error: function precondition could not be proved
i6x.dfy(6,14): Related location: this proposition could not be proved
  |
6 |   requires (n >= 0)

Naming isPos only in B's own //@ ensures leaves it unresolved, as in the first case.

Expected: a lifted contract carries the pure helpers it mentions, with their bodies, the same way they are emitted in A's own .dfy. Or lsc reports, at lift time, that the contract depends on a helper it can't bring in.

Suggested direction: when lifting an imported function's spec, collect the pure functions it references, transitively, and emit them as transparent functions with bodies. Emitting them as axioms gives B nothing to reason with.

Workaround: write cross-file contracts without helpers, e.g. //@ ensures \result > 0 instead of isPos(\result). With that, i6.ts verifies.

主要言語
TypeScript
スター
113
フォーク
13
平均マージ
16時間 22分
マージ済み PR(30日)
40

環境構築

このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

midspiral/LemmaScript のほかの issue

midspiral/LemmaScript の issue をすべて見る

似ている issue

TypeScript の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。