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

Abierto
#267 1 comentario 0 reacciones 0 asignados Ver en GitHub

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

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:

  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
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

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de midspiral/LemmaScript

Todos los issues de midspiral/LemmaScript

Issues similares

Más issues de TypeScript

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.