Czy ktoś rzeczywiście stworzył system, który zapisuje programy komputerowe ze specyfikacji?

17

Czy ktoś kiedykolwiek napisał system (oprogramowanie lub szczegółowe wyjaśnienie na papierze z prostymi przykładami), który generuje programy komputerowe? Wprowadzam i tworzy program, który wyświetla liczby pierwsze mniejsze niż 10. P r i m e ( x ) jest po prostu zdefiniowany jako 1 < x ∧ ∄ AP.rjammi(x)∧x<10P.rjammi(x) Profesorowie mówią, że mogą, ale nikt nie podaje rzeczywistych pełnych przykładów.

1<x∧∄As.t.1<A∧A<x∧x=A×B, with A,B∈N.
logic type-theory coq proof-assistants cody
źródło
13
Masz na myśli kompilator dla języka programowania ogólnego przeznaczenia?
Sasho Nikolov
1
Cześć - witamy w cstheory! Niestety twoje pytanie nie jest pytaniem na poziomie badań teoretycznych w informatyce i jest nie na temat na tej stronie.
W rzeczywistości jest to dobre pytanie na szczycie obecnych badań i bardzo obiecujące. Jednak często bardzo trudno jest dokładnie określić, czego chcesz. Jeśli uda ci się to określić, potrzebujesz systemu, który udowodni, że ma sens, że jest wykonalny i będzie wymagał matematycznego dowodu. Z tego dowodu program, który to robi, można wyodrębnić. Ale badania nad zautomatyzowaniem dowodu i wyodrębnieniem programu są wciąż w powijakach, choć osiągają niezłe postępy. Możesz szukać na przykład w Coq na wikipedii. - - - cc @LevReyzin
babou
2
Oto książka odpowiadająca Twojemu pytaniu. Są inni. Nie jest to łatwe do zrozumienia. Tłum Coq i Isabelle (inny taki system) obejmuje użytkowników SE, którzy mogliby podać więcej informacji i przykładów, gdyby pytanie nie zostało zamknięte. Znalazłem to, szukając w Internecie: synteza przykładowego programu coq.
babou
2
Dziedzina informatyki, która wychwytuje to, o co pytasz, nazywa się syntezą programów i jest aktywnym obszarem badań.
Huck Bennett

Odpowiedzi:

11

Jest to bardzo aktywny temat badawczy, bardzo obiecujący, chociaż pełna automatyzacja generowania programów prawdopodobnie ma wewnętrzne ograniczenia (ale czy ludzie są w ogóle lepsi?). Ale pomysł jest nadal bardzo przydatny w znacznym wspomaganiu tworzenia programów poprzez mechanizację wielu kroków i automatyczne sprawdzanie poprawności generowania programu.

Jest to silnie powiązane z wynikiem w logice, zwanej korespondencją Curry'ego-Howarda (lub izomorfizmem), która pokazuje, że programy komputerowe i dowody matematyczne są bardzo podobne.

Chodzi o to, że system weźmie specyfikację programu jako twierdzenie, które ma zostać udowodnione. W twoim przykładzie byłoby to coś w stylu (nieformalnie): „istnieje zbiór wszystkich liczb pierwszych mniejszych niż 10”.

Następnie spróbujesz udowodnić to twierdzenie, a istniejące systemy pomogą ci w przeprowadzeniu dowodu, automatyzacji niektórych części, być może całego dowodu i upewnieniu się, że nigdy nie popełnisz błędów.

Z tego dowodu można następnie wyodrębnić program, który faktycznie oblicza żądaną listę liczb pierwszych, która została pierwotnie określona.

W przeszłości opracowano kilka systemów w celu wyjaśnienia tych pomysłów. Jednym z bardziej znanych był LCF przez Robin Milner , który stworzył język ML do tego celu. Jednym z najbardziej zaawansowanych systemów jest Coq .

Istnieją przykłady w pełni opracowane, niektóre z nich dość złożone. Niektóre z nich można znaleźć w poniższym artykule , chociaż nie jest to w żaden sposób proste czytanie i wymaga zaawansowanej znajomości logiki.

Babou
źródło
9

Prosta odpowiedź: tak, ale w chwili pisania tego tekstu, w przypadku większości programów niebanalnych specyfikacje wydają się tak samo trudne do napisania i debugowania, jak programy.

Mówiąc poważniej, odpowiedź Babou jest dobra, ale ja również zasugeruję sprawdzenie obszaru typów zależnych. Jest dość dobra książka z użyciem Coq (pełne zastrzeżenie: napisane przez mojego przyjaciela), ale są też Epigram, Agda i Idris. Warto również sprawdzić Isabelle / HOL.

Wszystkie są oparte na rachunku konstrukcji. Jeśli chcesz poznać podstawy teoretyczne, spójrz na teorię typu Martina-Löfa. Wokół jest kilka świetnych prezentacji.

Pseudonim
źródło
W pełni zgadzam się co do specyfikacji (a także reszty twojej odpowiedzi, ale znasz ją lepiej niż ja). Każdy prawdziwy programista wie, jak trudno jest w pełni określić, co program powinien zrobić. Jest to poważny problem w inżynierii oprogramowania. I to przekłada się również tutaj, nawet jeśli omawiane problemy są bardziej matematyczne. Nie chciałem jednak brzmieć zbyt zniechęcająco (zwłaszcza biorąc pod uwagę historię tego pytania, zilustrowaną przez pierwszy komentarz).
babou
4

W tym miejscu generatory programów (tj. Systemy, które opisywały coś wysokiego poziomu w jakimś specjalnym języku) istniały na zawsze. Każdy kompilator jest jednym z nich, podobnie jak każdy z wielu generatorów parsera. W dawnych czasach popularne były systemy nazywane „językami trzeciej generacji”, które generowały (większość) kod typowej aplikacji biznesowej, biorąc pod uwagę ogólny opis i katalog dostępnych danych.

vonbrand
źródło
1

Programowanie logiczne i, bardziej ogólnie, programowanie deklaratywne przyjmuje za podstawę dokładnie to, co proponujesz: mianowicie, ze specyfikacji logicznej, zwróć wynik spełniający tę specyfikację.

Jednym z obszarów, który wydaje się szczególnie dotyczyć podanego przykładu „liczb pierwszych mniejszych niż 10”, jest Programowanie Ograniczeń, które próbuje znaleźć rozwiązania problemów związanych z pewnymi ograniczeniami, w tym ograniczeniami całkowitymi, takimi jak te, które podałeś.

Możesz wypróbować ECLiPSe dla konkretnej implementacji takiego systemu (open source).

cody
źródło
Czy słuszne byłoby stwierdzenie, że paradygmat logiki / ograniczenia służy raczej określeniu odpowiedzi niż określeniu programów. Oczywiście można powiedzieć, że niepełna specyfikacja to program. Ale jakoś nie jestem pewien, czy to ta sama gra, co synteza programów. Prawdą jest jednak, że odpowiada na przykład, ponieważ przykład był bardzo prosty. Nie chcę powiedzieć, że programowanie ograniczeń dotyczy tylko prostych problemów.
babou