Lean backend: a closure over a variable that changes is translated as a copy, so a false ensures proves
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
- Ambito
- backend-api-design, compilers
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:
lsc gen --backend=leanrefuses 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- it translates the capture so that the Lean has JavaScript's meaning: in reproduction 1,
ensures \result === 6proves andensures \result === 2doesn'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
- Leggi tutta la issue e poi la guida ai contributi del progetto.
- Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
- Fai un fork del repository e lavora su un branch.
- Apri una pull request che faccia riferimento al numero della issue.
Altre issue di midspiral/LemmaScript
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 82/100
midspiral/LemmaScript#308 ·
I maintainer di solito rispondono entro 1 giorno
-
Dafny: `toUpperCase`/`toLowerCase` are modeled as ASCII-only, so false contracts about non-ASCII text verifyForse già presa @quangng2000 l’ha presa 1 giorno fa. Aperta
midspiral/LemmaScript#312 · 1 commento · 1 assegnatario ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 4/5 1-2 giorni Idoneità per principianti 56/100
midspiral/LemmaScript#311 ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 5/5 Più di una settimana Idoneità per principianti 48/100
midspiral/LemmaScript#310 ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 3/5 1-2 giorni Idoneità per principianti 67/100
midspiral/LemmaScript#309 ·
I maintainer di solito rispondono entro 1 giorno
Tutte le issue di midspiral/LemmaScript
Issue simili
-
bug
Difficoltà 2/5 1-3 ore Idoneità per principianti 78/100
hemilabs/ui-monorepo#2711 ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 76/100
code-yeongyu/senpi#6929 ·
I maintainer di solito rispondono entro 1 giorno
-
community first-timers-only good first issue hacktoberfest help wanted low hanging fruit up-for-grabs
Difficoltà 1/5 Meno di un'ora Idoneità per principianti 72/100
lingdojo/kana-dojo#34261 · 1 commento · 5 reazioni ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 65/100
embedpdf/embed-pdf-viewer#1116 ·
I maintainer di solito rispondono entro 1 giorno
-
Revise communication normsApertacurrent task
Difficoltà 1/5 1-3 ore Idoneità per principianti 88/100
Sunday-School-Software/Sunday-School-Scheduler#87 ·
I maintainer di solito rispondono entro 1 giorno