Nie wiem, gdzie jeszcze zadać to pytanie, mam nadzieję, że to dobre miejsce.
Jestem tylko ciekawy, czy można zrobić generator lambda; zasadniczo pętla, która w nieskończonym czasie wytworzy każdą możliwą funkcję rachunku lambda. (jak w postaci ciągu).
Ponieważ rachunek lambda jest tak prosty, mając tylko kilka elementów do jego zapisu, pomyślałem, że może być możliwe (choć niezbyt przydatne) utworzenie wszystkich możliwych kombinacji tych elementów zapisu, zaczynając od najprostszych kombinacji, a tym samym wytworzenie każdej możliwej lambda funkcja rachunku różniczkowego.
Oczywiście nie wiem prawie nic o rachunku lambda, więc nie mam pojęcia, czy to naprawdę możliwe.
Czy to jest Jeśli tak, to czy jest to tak proste, jak to sobie wyobrażałem, czy jest to technicznie możliwe, ale tak trudne, że jest faktycznie niemożliwe?
PS. Nie mówię o funkcjach obniżonych beta, mówię tylko o każdej poprawnej notacji każdej funkcji rachunku lambda.
źródło
if n%2==0 ...
Tak. Weź coś, co wylicza wszystkie możliwe ciągi ASCII. Dla każdego wyjścia sprawdź, czy jest to poprawna składnia rachunku lambda, która definiuje funkcję; jeśli nie, pomiń to. (Można to sprawdzić.) Wymienia wszystkie funkcje rachunku lambda.
źródło
Jak już wspomniano, jest to tylko wyliczenie terminów z języka bezkontekstowego, więc zdecydowanie wykonalne. Ale kryje się za tym bardziej interesująca matematyka, wchodząca w zakres kombinatoryki anlytycznej.
Artykuł Liczenie i generowanie terminów w binarnym rachunku lambda zawiera sposób rozwiązania problemu zliczania i wiele więcej. Aby uprościć sprawę , używają czegoś, co nazywa się binarnym kalendarzem lambda , który jest po prostu kodowaniem terminów lambda za pomocą wskaźników De Bruijn , więc nie musisz nazywać zmiennych.
Ten artykuł zawiera także konkretny kod Haskella implementujący algorytm ich generowania. To zdecydowanie możliwe.
Zdarzyło mi się napisać implementację ich podejścia w Julii.
źródło
Pewnie. Możemy je bezpośrednio wygenerować zgodnie z definicją terminów lambda.
W Haskell najpierw definiujemy typ danych,
a następnie za pomocą uczciwego (er)
join
,po prostu je wyliczamy, jak np
fjoin
jest równoznaczne z Omega monada „sdiagonal
.źródło
Natknąłem się na jedno narzędzie online, które może generować ciągi przykładowe z wyrażenia regularnego: https://www.browserling.com/tools/text-from-regex . Możesz wygenerować wiele przykładowych wyrażeń lambda, wprowadzając coś takiego:
Oczywiście, aby uzyskać warunki z dowolnym poziomem zagnieżdżenia, będziesz musiał użyć gramatyki bezkontekstowej, która jest bardziej opisowym narzędziem do definiowania języka niż wyrażenie regularne. Nie natknąłem się na istniejące narzędzie do generowania przykładowych zdań w oparciu o bezkontekstową definicję gramatyki, ale nie ma powodu, dla którego nie można byłoby zbudować.
źródło