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

Test 8

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

abstrakcją Dobrze

aplikacją Źle

termem wolnym Źle

to w ogóle nie jest term rachunku lambda Źle

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

$x$ Źle

$y$ Źle

$z$ Dobrze

żadna Źle

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

$\lambda x.xz$ Źle

$\lambda y.yy$ Źle

$\lambda z.zy$ Dobrze

żaden z wymienionych Źle

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

$\lambda x.xz$ Źle

$\lambda y.zy$ Dobrze

$\lambda zy.zy$ Źle

żaden z wymienionych Źle

Aplikacja $PQ$ zwana jest redeksem, jeśli:

$P$ jest w postaci abstrakcji Dobrze

$Q$ jest w postaci bstrakcji Źle

$P$ nie zawiera zmiennych wolnych Źle

$Q$ nie zawiera zmiennych wolnych Źle

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

żaden jego podterm nie jest redeksem Dobrze

zawiera dokładnie jeden redeks Źle

zawiera co najmniej jeden redeks Źle

nie zawiera zmiennych wolnych Źle

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

$\alpha$-konwersji Dobrze

$\beta$-redukcji Źle

i $\alpha$-konwersji, i $\beta$-redukcji Źle

jest bezwzględnie unikalna Źle

Przymując standardową reprezentację liczb naturalnych w rachunku lambda, term $\lambda mnsx.(ms)(nsx)$ reprezentuje:

dodawanie Dobrze

mnożenie Źle

potęgowanie Źle

żadne z wymienionych tu działań Źle

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

funkcji obliczalnych totalnych (nieczęściowych) Dobrze

funkcji obliczalnych częściowych Źle

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

żadnemu z wymienionych Źle

Operator punktu stałego to term $Y$ taki, że dla dowolnego termu $M$ aplikacja $YM$ jest równa, modulo $\beta$-redukcja:

$M$ Źle

$M(YM)$ Dobrze

$Y$ Źle

$YM$ Źle