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

From Studia Informatyczne

Test 8

Jeśli \displaystyle M jest termem rachunku lambda, zaś \displaystyle x jest zmienną, to \displaystyle \lambda M.x nazywamy:

abstrakcją

aplikacją

termem wolnym

to w ogóle nie jest term rachunku lambda

W termie \displaystyle \lambda xy.yz wolna jest zmienna:

\displaystyle x

\displaystyle y

\displaystyle z

żadna

Który term jest wynikiem \displaystyle \alpha-konwersji termu \displaystyle \lambda x.xy?

\displaystyle \lambda x.xz

\displaystyle \lambda y.yy

\displaystyle \lambda z.zy

żaden z wymienionych

Wynikiem \displaystyle \beta-redukcji termu \displaystyle (\lambda xy.xy)z jest term:

\displaystyle \lambda x.xz

\displaystyle \lambda y.zy

\displaystyle \lambda zy.zy

żaden z wymienionych

Aplikacja \displaystyle PQ zwana jest redeksem, jeśli:

\displaystyle P jest w postaci abstrakcji

\displaystyle Q jest w postaci bstrakcji

\displaystyle P nie zawiera zmiennych wolnych

\displaystyle Q 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:

\displaystyle \alpha-konwersji

\displaystyle \beta-redukcji

i \displaystyle \alpha-konwersji, i \displaystyle \beta-redukcji

jest bezwzględnie unikalna

Przymując standardową reprezentację liczb naturalnych w rachunku lambda, term \displaystyle \lambda mnsx.(ms)(nsx) 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 \displaystyle Y taki, że dla dowolnego termu \displaystyle M aplikacja \displaystyle YM jest równa, modulo \displaystyle \beta-redukcja:

\displaystyle M

\displaystyle M(YM)

\displaystyle Y

\displaystyle YM