Lean backend: a closure over a variable that changes is translated as a copy, so a false ensures proves
Los mantenedores suelen responder en 1 día
Nadie ha tomado este issue todavía.
Evaluación
- Dificultad
- 4/5
- Tiempo estimado
- 3-5 días
- Aptitud para principiantes
- 45/100
- Tipo de issue
- Error
- Claridad
- Bien especificado
- Estado de actividad
- Activo
- Stack tecnológico
- typescript
- Área
- backend-api-design, compilers
Línea de trabajo
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.
Escrito por el modelo de indexación a partir del texto del issue.
Descripción
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
- Lenguaje dominante
- TypeScript
- Estrellas
- 113
- Forks
- 13
- Merge medio
- 16 h 22 min
- PR fusionados (30 d)
- 40
Preparar el entorno
Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.
Primeros pasos
- Lee el issue completo y luego la guía de contribución del proyecto.
- Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
- Haz un fork del repositorio y trabaja en una rama.
- Abre un pull request que haga referencia al número del issue.
Más de midspiral/LemmaScript
-
Dificultad 2/5 1-3 horas Aptitud para principiantes 82/100
midspiral/LemmaScript#308 ·
Los mantenedores suelen responder en 1 día
-
Dafny: `toUpperCase`/`toLowerCase` are modeled as ASCII-only, so false contracts about non-ASCII text verifyPosiblemente ocupada @quangng2000 la tomó hace 1 día. Abierto
midspiral/LemmaScript#312 · 1 comentario · 1 asignado ·
Los mantenedores suelen responder en 1 día
-
Dificultad 4/5 1-2 días Aptitud para principiantes 56/100
midspiral/LemmaScript#311 ·
Los mantenedores suelen responder en 1 día
-
Dificultad 5/5 Más de una semana Aptitud para principiantes 48/100
midspiral/LemmaScript#310 ·
Los mantenedores suelen responder en 1 día
-
Dificultad 3/5 1-2 días Aptitud para principiantes 67/100
midspiral/LemmaScript#309 ·
Los mantenedores suelen responder en 1 día
Todos los issues de midspiral/LemmaScript
Issues similares
-
Dificultad 1/5 1-3 horas Aptitud para principiantes 83/100
gofish-graphics/gofish-graphics#1384 ·
Los mantenedores suelen responder en 1 día
-
adapter bug
Dificultad 2/5 1-3 horas Aptitud para principiantes 83/100
Olanetsoft/agent-lookout#353 ·
Los mantenedores suelen responder en 1 día
-
Dificultad 2/5 1-3 horas Aptitud para principiantes 68/100
vicharanashala/vibe#1542 ·
Los mantenedores suelen responder en 1 día
-
bug chore P2 size:XS
Dificultad 2/5 1-3 horas Aptitud para principiantes 77/100
josephfung/curia#2666 ·
Los mantenedores suelen responder en 1 día
-
bug good first issue
Dificultad 2/5 1-3 horas Aptitud para principiantes 84/100
devarshishimpi/codra#178 ·
Los mantenedores suelen responder en 1 día