lambdaclass / lambdaclass/lambda_compiler_kit
perf/safety: convert parseStr from recursive to iterative to prevent stack overflow
Nessuno ha ancora preso questa issue.
- Lingua principale
- Lean
- Stelle
- 2
- Fork
- 1
- Metriche di merge delle PR
- Nessuna PR unita negli ultimi 30g
Descrizione
Problem
parseStr in Lck/Json/Tokenizer.lean is written as a recursive CPS function. While the continuation wrapping is proven zero-cost at runtime (proofs are erased), the recursion itself is structural on the input — meaning for a string literal of length n, the Lean runtime creates n stack frames.
For pathologically large string values this can overflow the stack.
Expected fix
Rewrite parseStr as an iterative (tail-recursive or explicit loop) accumulator, maintaining the same CPS interface for callers. The proof structure can be adapted to use an inductive invariant on the loop state.
References
- Flagged by AI code review on PR #8
Guida per i contributori
Nessuna guida per i contributori indicizzata per questo repository
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.
Direzione di ricerca
Inizia in Lck/Json/Tokenizer.lean, all’implementazione CPS ricorsiva di parseStr, quindi esamina in che modo i chiamanti dipendono dalla sua interfaccia CPS. Riscrivi l’analisi delle stringhe come un accumulatore iterativo preservando tale interfaccia, adatta la dimostrazione intorno a un invariante induttivo del ciclo e verifica che i letterali stringa di grandi dimensioni non rischino più di causare uno stack overflow.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Valutazione
- Ambito
- compilers, performance
- Tipo di issue
- Refactoring
- Difficoltà
- 4/5
- Tempo stimato
- 3-5 giorni
- Stato di attività
- Ferma
- Chiarezza
- Specificata chiaramente
- Idoneità per principianti
- 45/100