Pytania otagowane jako lambda-calculus

Rachunek λ jest formalnym systemem do definiowania funkcji, stosowania funkcji i rekurencji, który stanowi matematyczną podstawę programowania funkcjonalnego.

3
Czy istnieje różnica między a ?
Obecnie uczę się rachunku lambda i zastanawiałem się nad następującymi dwoma różnymi rodzajami pisania terminu lambda. λxy.xyλxy.xy\lambda xy.xy λx.λy.xyλx.λy.xy\lambda x.\lambda y.xy Czy jest jakaś różnica w znaczeniu lub sposobie zastosowania redukcji wersji beta, czy to tylko dwa sposoby wyrażenia tego samego? Szczególnie ta definicja tworzenia par wzbudziła we mnie zastanowienie: …
2
Uniwersalna / egzystencjalna kwantyfikacja?
Usiłuję zrozumieć cel uniwersalnej i egzystencjalnej kwantyfikacji typów. Bawię się pisząc zabawkowy język na podstawie rachunku konstrukcji . Czytałem o Morte i Henku, aby pomóc mi lepiej zrozumieć. Nie rozumiem, dlaczego CoC ma zarówno lambda, jak i całkowitą abstrakcję. (λx:A.B)(λx:A.B)(\lambda x:A . B) (∀x:A.B)(∀x:A.B)(\forall x:A . B) Wydaje mi się, …
1
Zwięzły przykład wykładniczego kosztu wnioskowania typu ML
Zwrócono mi uwagę, że koszt wnioskowania o typ w funkcjonalnym języku, takim jak OCaml, może być bardzo wysoki. Twierdzenie jest takie, że istnieje ciąg wyrażeń taki, że dla każdego wyrażenia długość odpowiedniego typu jest wykładnicza względem długości wyrażenia. Wymyśliłem sekwencję poniżej. Moje pytanie brzmi: czy znasz sekwencję z bardziej zwięzłymi …
2
Czy rachunek SK2 jest kompletną podstawą, gdzie K2 jest odwróconym kombinatorem K?
W szczególności, jeśli zdefiniowałem nowy jako zamiast czy -calculus byłby podstawą do konkurowania?K2K2K_2K2=λx.(λy.y)K2=λx.(λy.y)K_2 = \lambda x. (\lambda y. y)K=λx.(λy.x)K=λx.(λy.x)K = \lambda x. (\lambda y. x){S,K2,I}{S,K2,I}\{S, K_2,I\} Domyślam się, że „nie”, tylko dlatego, że nie wydaje mi się, że jestem w stanie zbudować zwykłego kombinatora K z kombinacji SSS , III …
2
Zbieg ekspansji beta
Niech →β→β\to_\beta będzie redukcją ββ\beta w rachunku λλ\lambda . Zdefiniuj ββ\beta rozszerzenie ←β←β\leftarrow_\beta przez t′←βt⟺t→βt′t′←βt⟺t→βt′t'\leftarrow_\beta t \iff t\to_\beta t' . Czy ←β←β\leftarrow_\beta zbieżny? Innymi słowy, nie mamy, że dla każdego l,d,rl,d,rl,d,r , jeżeli l→∗βd←∗βrl→β∗d←β∗rl \to_\beta^* d\leftarrow_\beta^* r , to istnieje uuu taki sposób, że l←∗βu→∗βrl←β∗u→β∗rl\leftarrow_\beta^* u \to_\beta^* r ? Słowa …
5
Lambda Calculus Generator
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, …
1
Analiza złożoności algorytmu dla implementacji funkcjonalnego języka programowania
Dowiedziałem się dzisiaj, że analiza algorytmów różni się w zależności od modelu obliczeniowego. To jest coś, o czym nigdy nie myślałem ani nie słyszałem. Przykładem podanym mi przez użytkownika @chi , który dalej to ilustruje : Np. Rozważ zadanie: dany zwraca x i . W pamięci RAM można to rozwiązać …
1
Czy typy własne powodują, że rachunek konstrukcji indukcyjnych staje się przestarzały?
Typy własne są rozszerzeniem Rachunku konstrukcji [1], które pozwalają językowi wyrażać algebraiczne typy danych zakodowane za pomocą kodowania Scott. Kodowanie Scott daje możliwość dopasowania do wzorca O(1), który jest jednym z głównych czynników motywujących do włączenia definicji indukcyjnych do CC. Jednak typy własne tworzą znacznie prostszą i elegancką teorię podstawową …
2
Kombinacyjna interpretacja rachunku lambda
Według Petera Selinger , Lambda Rachunek jest algebraiczna (PDF). Na początku tego artykułu mówi: Kombinacyjna interpretacja rachunku lambda jest znana jako niedoskonała, ponieważ nie spełnia reguły ξξξ : zgodnie z interpretacją M=NM=NM = N nie oznacza λx.M=λx.Nλx.M=λx.N\lambda x.M = \lambda x.N (Barendregt, 1984). Pytania: Jaki rodzaj równoważności ma tu na …
2
Co sprawia, że ​​rachunek lambda jest istotny w badaniu?
Jesienią rozpoczynam licencjat z informatyki, ale tak naprawdę nie rozumiem rachunku λ w kontekście programowania funkcjonalnego. Być może całkowicie błędnie to interpretuję, ale w oparciu o tę definicję z Encyklopedii Filozoficznej Stanforda jest to kolejna notacja funkcji. Jeśli to jest właśnie to, dlaczego jest korzystne stosowanie λ nazębnego nad regularnych …
3
anonimowe funkcje lambda (programowanie funkcjonalne)
Co to są funkcje anonimowe (lambda)? Jaka jest formalna definicja anonimowej funkcji w funkcjonalnym języku programowania? Mówiąc najprościej, kiedy programuję w schemacie / lisp, powiedziałbym, że funkcja anonimowa (lambda) jest funkcją niezwiązaną z identyfikatorem. Czy to wszystko, co możesz formalnie powiedzieć o funkcji lambda? Myślę, że do tej prostej definicji …
1
λ-rachunek: Co jest najbardziej wydajne w reprezentacji pamięci w funkcjach?
Chciałbym porównać wydajność struktur danych zakodowanych funkcyjnie (Church / Scott) i klasycznie zakodowanych (asembler / C). Ale zanim to zrobię, muszę wiedzieć, jak wydajna jest / może być reprezentacja funkcji w pamięci. Funkcję tę można oczywiście częściowo zastosować (inaczej zamknięcie). Interesuję się zarówno obecnym algorytmem kodowania, popularnymi językami funkcjonalnymi (Haskell, …
1
Co to jest super wszechświat?
Czytam ten dobrze znany artykuł o wszechświatach w teorii typów . Na początku spodziewałem się czegoś podobnego do SetωAgdy, ale okazuje się, że jest to nawet coś bardziej ogólnego. Wydaje się uogólniać konstrukcję wszechświata od zwykłego typu indukcyjno-rekurencyjnego do spoiwa (podobnego doΠΠ\Pi i ΣΣ\Sigma). Główne pytanie, które chcę zadać, to …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.