Lean backend: a closure over a variable that changes is translated as a copy, so a false ensures proves

Aperta
#267 1 commento 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
4/5
Tempo stimato
3-5 giorni
Idoneità per principianti
45/100
Tipo di issue
Bug
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
typescript

Direzione di ricerca

Start at the Lean backend code that translates closures and captured bindings; the issue does not name its file, so trace the --backend=lean path from the compiler entry point. Reproduce the reassigned-variable and mutated-array cases, then compare generated Lean and proof results with JavaScript. Done means generation either rejects unsafe captures with a useful error or preserves their JavaScript behavior, and zero-parameter arrows are handled or rejected clearly.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

Summary

With --backend=lean, a closure that captures a variable which changes after the closure is made is translated as a copy of the variable's value at that point. The generated Lean builds, and velvet_vcgen proves a postcondition that JavaScript falsifies, while the true postcondition fails to prove. lsc gen, lsc check and lake build all report success.

Versions

lemmascript (npm), lsc version 0.6.6
LemmaScript tag v0.6.6 (736fb7ce5ef89555b566bdbcca0c8fe057fbb205)
Velvet branch lemma2 (22ed7829f4a90e786eed9b193d29fe46e61fe949)
Mathlib 5ed2965256430c3649e86755f9576b54eca72435 (LemmaScript's manifest)
Lean / Lake 4.34.0 / 5.0.0-src+293d5d0, Linux x86-64

Reproduction 1: a let reassigned after a closure reads it

//@ ensures \result === 2
export function late(): number {
  let n = 1;
  const f = (x: number): number => x + n;
  n = 5;
  return f(1);
}

In JavaScript, late() returns 6: f reads n when it's called, and n is 5 by then.

lsc gen --backend=lean late.ts exits 0 and writes:

method late  returns (res : Int)
  ensures ensures_1: (res = 2 : Prop)
  do
    let mut n : Int := 1
    let f := (fun x => x + n)
    n := 5
    return f 1

f closes over the value n had at let f, which is 1. With

prove_correct late by
  velvet_vcgen [late] with finish

lake build succeeds, so the false ensures \result === 2 is proved. With the true //@ ensures \result === 6, the same proof fails with finish failed.

Reproduction 2: an array mutated after a closure reads it

//@ ensures \result === 1
export function stale(): number {
  const a: number[] = [1];
  const len = (k: number): number => a.length + k;
  a.push(2);
  return len(0);
}

JavaScript returns 2. The generated Lean is:

method stale  returns (res : Int)
  ensures ensures_1: (res = 1 : Prop)
  do
    let mut a : Array Int := #[1]
    let len := (fun k => a.size + k)
    a := Array.push a 2
    return len 0

With prove_correct stale by velvet_vcgen [stale] with finish, lake build succeeds and \result === 1 is proved.

Reproduction 3: the change happens through a call or an alias

function push1(a: number[]): void { a.push(1); }

//@ ensures \result === 0
export function viaCall(): number {
  const arr: number[] = [];
  const f = (k: number): number => arr.length + k;
  push1(arr);
  return f(0);
}

JavaScript returns 1. The generated Lean passes arr to push1 by value, and f has copied it anyway:

method viaCall  returns (res : Int)
  ensures ensures_1: (res = 0 : Prop)
  do
    let mut arr : Array Int := #[]
    let f := (fun k => arr.size + k)
    let _t0 ← push1 arr
    _ := _t0
    return f 0

With prove_correct push1 by velvet_vcgen [push1] with finish and prove_correct viaCall by velvet_vcgen [viaCall, push1] with finish, the build succeeds and === 0 is proved. === 1 fails with finish failed.

Through an alias the result is the same: const b = arr; b.push(1); in place of the call generates let mut b : Array Int := arr and b := Array.push b 1, and === 0 is proved while JavaScript returns 1.

Related: shapes that generate but don't build

lsc gen --backend=lean also exits 0 on these. The generated Lean is rejected later, with no TypeScript-level message:

TypeScript Lean error
let c = 0; const bump = (x: number): number => { c = c + x; return c; }; return xs.map(bump).length; Variable c cannot be mutated. Only variables declared using let mut can be mutated
export function counter(): () => number { let n = 0; return () => { n = n + 1; return n; }; } `unexpected token '=>'; expected '[', '{', '
any zero-parameter arrow, for example const len = (): number => a.length; the same: it's emitted as fun => ... with no binder

A pure closure over a const primitive (const k = 3; xs.map(x => x + k)) generates Lean that builds and means the same as the TypeScript.

Expected

Either:

  1. lsc gen --backend=lean refuses a closure that captures a binding which is reassigned, or an array or object that is mutated (directly, through an alias, or by a call), with an error naming the closure and the variable; or
  2. it translates the capture so that the Lean has JavaScript's meaning: in reproduction 1, ensures \result === 6 proves and ensures \result === 2 doesn't.

The first seems the smaller change, and the safer one while the translation is unproved.

Separately, a zero-parameter arrow should be emitted as fun () => ... (or refused), rather than producing Lean that doesn't parse.

How it was run

lsc gen --backend=lean late.ts   # exit 0
lake build                       # package requiring LemmaScript by path, roots «late.def» and «late.proof»
node -e 'function late(){ let n = 1; const f = (x) => x + n; n = 5; return f(1); } console.log(late())'   # 6
Lingua principale
TypeScript
Stelle
113
Fork
13
Merge medio
16h 22m
PR unite (30g)
40

Preparare l'ambiente

Questo progetto non fornisce container di sviluppo, Dockerfile né guida per i contributori, quindi l'ambiente è a tuo carico: parti dal suo README e consulta la nostra guida al primo contributo per i passaggi generali.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di midspiral/LemmaScript

Tutte le issue di midspiral/LemmaScript

Issue simili

Altre issue su TypeScript

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.