Przejdź do treści
Biblioteka skilli
Programowanie · Konwersja i formaty

program-to-model-extractor

/program-to-model-extractor

Wyodrębnia abstrakcyjne modele matematyczne z kodu funkcyjnego (Haskell, OCaml, F#) do definicji w Isabelle/HOL na potrzeby rozumowania formalnego.

Repozytorium
Skills-4-SE ↗
Licencja
Apache-2.0
Ostatnia zmiana repozytorium
21.08.2026

Ocena i bezpieczeństwo

100/ 100Klasa: dobry
Format25 / 25
Frontmatter z nazwą i opisem, poprawna nazwa, opis do 1024 znaków, nazwa zgodna z folderem.
Odkrywalność25 / 25
Opis mówi, kiedy użyć skilla, ma sensowną długość i jest w 3. osobie.
Treść35 / 35
Co najmniej 150 słów i do 500 linii, nagłówki, listy kroków, przykłady albo kod.
Higiena15 / 15
Bez zaślepek typu TODO, bez ścieżek Windows, z licencją.
Ryzykobrak sygnałów w skanie
Pliki w paczce
3
Skrypty
0
Komentarze HTML
0
Adresy URL w SKILL.md
0
Przestarzałość

Brak sygnałów. Repozytorium zmienione 21.08.2026, bez odwołań do wycofanych modeli i API.

Licencja

Apache-2.0, otwarta: można używać i zmieniać, z zachowaniem licencji i informacji o zmianach.

Co robi i kiedy

Wyodrębnia abstrakcyjne modele matematyczne z kodu funkcyjnego (Haskell, OCaml, F#) do definicji w Isabelle/HOL na potrzeby rozumowania formalnego.

Oryginalny opis (EN)

Extract abstract mathematical models from functional code (Haskell, OCaml, F#) for formal reasoning in Isabelle/HOL. Use when users need to: (1) Convert functional programs to Isabelle definitions, (2) Extract high-level algorithm essence from implementation code, (3) Generate formal specifications and properties from code, (4) Create verification-ready models that capture mathematical properties while abstracting away implementation details. Focuses on structural recursion, algebraic data types, higher-order functions, and invariant extraction.

Jak działa

  1. Overview
  2. Extraction Workflow
  3. Common Extraction Patterns
  4. Abstraction Guidelines
  5. Example: Complete Extraction
  6. References
  7. Tips
Sekcje z nagłówków SKILL.md, w oryginale · 181 linii, 710 słów
Podgląd SKILL.md
---
name: program-to-model-extractor
description: "Extract abstract mathematical models from functional code (Haskell, OCaml, F#) for formal reasoning in Isabelle/HOL. Use when users need to: (1) Convert functional programs to Isabelle definitions, (2) Extract high-level algorithm essence from implementation code, (3) Generate formal specifications and properties from code, (4) Create verification-ready models that capture mathematical properties while abstracting away implementation details. Focuses on structural recursion, algebraic data types, higher-order functions, and invariant extraction."
---

# Program-to-Model Extractor

Extract high-level mathematical models from functional code for formal reasoning in Isabelle/HOL.

## Overview

This skill transforms functional programs (Haskell, OCaml, F#) into abstract mathematical models suitable for formal verification in Isabelle/HOL. The extraction focuses on the algorithm's mathematical essence—capturing core properties, invariants, and structural patterns while abstracting away language-specific implementation details.

## Extraction Workflow

### 1. Analyze the Source Code

Identify key elements:
- **Data structures**: Algebraic types, lists, trees, custom types
- **Core functions**: Main computational logic
- **Recursion patterns**: Structural, tail, mutual recursion
- **Properties**: What should be true about inputs/outputs?

### 2. Extract Data Types

Convert source language types to Isabelle datatypes:

```haskell
-- Haskell
data Tree a = Leaf | Node a (Tree a) (Tree a)
```

```isabelle
(* Isabelle *)
datatype 'a tree = Leaf | Node "'a" "'a tree" "'a tree"
```

### 3. Model Functions

Choose the appropriate Isabelle construct:

**For primitive recursion** (terminates obviously):
```isabelle
fun length :: "'a list ⇒ nat" where
  "length [] = 0" |
  "length (x # xs) = 1 + length xs"
```

**For general recursion** (needs termination proof):
```isabelle
function gcd :: "nat ⇒ nat ⇒ nat" where
  "gcd m n = (if n = 0 then m else gcd n (m mod n))"
by pat_completeness auto
termination by (relation "measure snd") auto
```

**For non-recursive definitions**:
```isabelle
definition compose :: "('b ⇒ 'c) ⇒ ('a ⇒ 'b) ⇒ ('a ⇒ 'c)" where
  "compose f g = (λx. f (g x))"
```

### 4. State Properties

Extract and formalize key properties as lemmas:

```isabelle
lemma length_append: "length (xs @ ys) = length xs + length ys"
lemma quicksort_permutes: "mset (quicksort xs) = mset xs"
lemma quicksort_sorted: "sorted (quicksort xs)"
```

### 5. Identify Invariants

For stateful or accumulator-based functions, state what holds during computation:

```isabelle
fun sum_acc :: "int ⇒ int list ⇒ int" where
  "sum_acc acc [] = acc" |
  "sum_acc acc (x # xs) = sum_acc (acc + x) xs"

lemma sum_acc_correct: "sum_acc acc xs = acc + sum_list xs"
```

## Common Extraction Patterns

### List Processing

**Source**: Recursive list operations
**Model**: Isabelle list functions with length/permutation properties
**See**: [extraction_patterns.md](references/extraction_patterns.md#pattern-1-list-operations)

### Sorting Algorithms

**Source**: Comparison-based sorting
**Model**: Functions with `sorted` and `mset` (permutation) properties
**See**: [extraction_patterns.md](references/extraction_patterns.md#pattern-2-sorting-and-permutations)

### Tree Operations

**Source**: Recursive tree traversals and folds
**Model**: Isabelle datatypes with structural recursion
**See**: [extraction_patterns.md](references/extraction_patterns.md#pattern-3-tree-structures)

### Higher-Order Functions

**Source**: map, filter, fold, composition
**Model**: Isabelle higher-order definitions with fusion lemmas
**See**: [extraction_patterns.md](references/extraction_patterns.md#pattern-4-higher-order-functions)

### Partial Functions

**Source**: Functions that may fail (division, lookup)
**Model**: Option types with case analysis
**See**: [extraction_patterns.md](references/extraction_patterns.md#pattern-5-monadic-operations)

### Tail Recursion

**Source**: Accumulator-based functions
**Model**: Functions with accumulator correctness lemmas
**See**: [extraction_patterns.md](references/extraction_patterns.md#pattern-6-accumulation-and-state)

## Abstraction Guidelines

Focus on **high-level mathematical essence**:

✓ **Do extract**:
- Core algorithm structure
- Mathematical properties (sorted, permutation, etc.)
- Invariants and pre/post-conditions
- Structural recursion patterns
- Type relationships

✗ **Don't extract**:
- Performance optimizations
- Language-specific syntax details
- Implementation tricks
- Memory layout concerns
- Specific evaluation strategies

## Example: Complete Extraction

**Source (Haskell)**:
```haskell
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = quicksort lesser ++ [p] ++ quicksort greater
  where lesser  = filter (< p) xs
        greater = filter (>= p) xs
```

**Extracted Model (Isabelle)**:
```isabelle
fun quicksort :: "'a::linorder list ⇒ 'a list" where
  "quicksort [] = []" |
  "quicksort (p # xs) =
     quicksort (filter (λx. x < p) xs) @ [p] @
     quicksort (filter (λx. x ≥ p) xs)"

(* Key properties *)
lemma quicksort_permutes: "mset (quicksort xs) = mset xs"
lemma quicksort_sorted: "sorted (quicksort xs)"
lemma quicksort_correct:
  "sorted (quicksort xs) ∧ mset (quicksort xs) = mset xs"
```

**Explanation**:
- Converted type constraint `Ord a` to `'a::linorder`
- Preserved structural recursion pattern
- Extracted two key properties: permutation and sortedness
- Combined into correctness specification

## References

- **[extraction_patterns.md](references/extraction_patterns.md)**: Detailed patterns for common functional programming constructs
- **[isabelle_syntax.md](references/isabelle_syntax.md)**: Quick reference for Isabelle/HOL syntax

## Tips

- Start with the simplest functions first to build up the model incrementally
- Use `mset` (multisets) to express permutation properties elegantly
- For complex recursion, explicitly state the termination measure
- Group related lemmas together (e.g., all properties of a single function)
- Use meaningful names that reflect mathematical concepts, not implementation details
Pliki w paczce (3)
  • SKILL.md 6 KB
  • references/extraction_patterns.md 6 KB
  • references/isabelle_syntax.md 5 KB

Wersje

W bazie nie ma innych skilli o nazwie program-to-model-extractor.

Migawka bazy z 13.11.2026 · wersja paczki 86292cd752c6 (skrót SHA-256 całej paczki)

Pobrania w ostatnich 30 dniach: 0 · ranking

Zgłoś problem z tym skillem: szkodliwa treść, błędny opis albo prośba autora o usunięcie.

Podobne skille

  • 100proof-carrying-code-generator
    Generuje wykonywalny kod razem z formalnymi dowodami bezpieczeństwa i poprawności w Isabelle/HOL lub Coq: bezpieczeństwo pamięci, granice, niezmienniki i terminacja, z ekstrakcją do OCaml, Haskell i SML.
  • 100imperative-to-coq-model-extractor
    Wyciąga abstrakcyjne modele matematyczne z kodu imperatywnego (C, C++, Python, Java) nadające się do formalnego rozumowania w Coq, w tym specyfikacje do weryfikacji i dowodów.
  • 100writing-isabelle-proofs
    Pomaga pisać dowody w Isabelle/HOL z automatyką Sledgehammer oraz sesje AFP.
  • 100haskell-pure-functional-programming
    Pisze poprawne oprogramowanie w Haskellu z użyciem monad, funktorów aplikatywnych, typów algebraicznych i wnioskowania typów.
  • 100ocaml
    Pomaga w programowaniu funkcyjnym w OCaml: algebraiczne typy danych, dopasowanie wzorców, moduły i Dune, przy narzędziach do analizy statycznej, kompilatorach i oprogramowaniu wysokiej niezawodności.
  • 100haskell-expert
    Wspiera programowanie funkcyjne w Haskellu na poziomie eksperckim: rozbudowany system typów, monady, leniwa ewaluacja, czyste funkcje i typy algebraiczne z klasami typów.

Uwagi i zgłoszenia

Wiadomość trafi do Bartosza Sokolińskiego. Adres e-mail jest potrzebny tylko do odpowiedzi. Szczegóły w polityce prywatności.