Paradygmaty programowania/Test 8: U podstaw programowania funkcyjnego — rachunek lambda

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Test 8

Jeśli jest termem rachunku lambda, zaś jest zmienną, to nazywamy:

abstrakcją

aplikacją

termem wolnym

to w ogóle nie jest term rachunku lambda

W termie wolna jest zmienna:

żadna

Który term jest wynikiem -konwersji termu ?

żaden z wymienionych

Wynikiem -redukcji termu jest term:

żaden z wymienionych

Aplikacja zwana jest redeksem, jeśli:

jest w postaci abstrakcji

jest w postaci bstrakcji

nie zawiera zmiennych wolnych

nie zawiera zmiennych wolnych

Mówimy, że term jest w postaci normalnej, jeśli:

żaden jego podterm nie jest redeksem

zawiera dokładnie jeden redeks

zawiera co najmniej jeden redeks

nie zawiera zmiennych wolnych

Postać normalna (o ile istnieje) jest unikalna z dokładnością do:

-konwersji

-redukcji

i -konwersji, i -redukcji

jest bezwzględnie unikalna

Przymując standardową reprezentację liczb naturalnych w rachunku lambda, term reprezentuje:

dodawanie

mnożenie

potęgowanie

żadne z wymienionych tu działań

Funkcje reprezentowalne w rachunku lambda (klasycznym, beztypowym) odpowiadają dokładnie modelowi:

funkcji obliczalnych totalnych (nieczęściowych)

funkcji obliczalnych częściowych

funkcji dających się obliczyć w stałej pamięci

żadnemu z wymienionych

Operator punktu stałego to term taki, że dla dowolnego termu aplikacja jest równa, modulo -redukcja: