\documentclass[a4paper]{article}
\setlength{\oddsidemargin}{-1cm} \setlength{\topmargin}{-3cm}
\setlength{\textwidth}{18cm} \setlength{\textheight}{26cm}
\pagestyle{empty}

\def\DJ{\leavevmode\setbox0=\hbox{D}\kern0pt
 \rlap{\kern.04em\raise.188\ht0\hbox{-}}D}
\def\dj{\leavevmode\setbox0=\hbox{d}\kern0pt
 \rlap{\kern.215em\raise.46\ht0\hbox{-}}d}

\usepackage{amssymb}
\usepackage{comment}
\usepackage{color}

\begin{document}

\begin{small}
{\color{blue}

\begin{center}
\textbf{Prevodioci i interpretatori - jun 2007. - 3. kolokvijum}
\end{center}
\begin{enumerate}
\begin{comment}
\item
$\lambda$ ra\v cun je formalni sistem koji omogu\' cava definisanje i primenu
matemati\v ckih funkcija. Funkcije se predstavljaju tzv. $\lambda$izrazima.
\begin{itemize}
\item Aritmeti\v cki izrazi predstavljaju elementarne $\lambda$izraze (npr. $2+3$,
$3*2 + 5$).
\item $\lambda$izrazi oblika $(\lambda x.\ \lambda izraz)$ predstavljaju
definiciju funkcije.
Npr. funkcija $f(x) = x + 2$ se predstavlja $\lambda$-izrazom $(\lambda x.\ x + 2)$.
\item Izrazi oblika $(\lambda izraz\ \lambda izraz)$ ozna\v cavaju poziv funkcije. Npr.
$((\lambda x.\ x + 2)\ 1)$ predstavlja primenu funkcije $f(x) = x+2$ na broj $1$.
Prethodni izraz se tzv. postupkom $\beta$redukcije svodi na $1 + 2$, odnosno $3$.
$\beta$ konverzija se svodi na zamenu svih pojavljivanja promenljive vezane
kvantifikatorom $\lambda$ u prvom izrazu, drugim izrazom. Me\dj utim, prilikom ove
zamene treba biti obazriv, jer se npr. izraz $((\lambda x.\ (\lambda y.\ x + y))\ y)$ $\beta$ konverzijom svodi na izraz
$(\lambda y'.\ y + y')$, a ne na $(\lambda y.\ y + y)$

\end{itemize}
Lambda ra\v cun predstavlja teorijsku osnovu funkcionalnih jezika. Napisati
interpretator za minijaturni funkcionalni jezik direktno zasnovan na lambda ra\v cunu.

Nakon uno\v senja elementarnih $\lambda$izraza, interpretator vr\v si njihovo
upro\v s\' cavanje i na standardni izlaz ispisuje rezultat.
\begin{verbatim}
2 + 3 * 5                                   17
\end{verbatim}

Sli\v cno, ukoliko je uneti $\lambda$izraz poziv funkcije, ispisuje se rezultat koji se
dobija primenom $\beta$redukcije.
\begin{verbatim}
((% x. x + 2) 1)                            3
((% x. x + 2) y)                            y + 2
((% f. (f 3)) (% x. x + 2))                 5
\end{verbatim}

Jezik se odlikuje mogu\' cno\v s\' cu imenovanja $\lambda$izraza kori\v s\' cenjem
konstrukcije \verb"(define id "$\lambda$\verb"izraz)".

Npr.
\begin{verbatim}
(define k 3)
(define square (% x. x * x))
(square k)                                  9
\end{verbatim}

\begin{verbatim}
(define f ((% x. (% y. x + y)) 1))
(f 5)                                       6
\end{verbatim}

Obezbediti da $\beta$konverzija ispravno radi i u slu\v cajevima
poput slede\' ceg:
\begin{verbatim}
(((% x. (% y. x + y)) y) 3)                 y + 3   (a ne 6)
\end{verbatim}


%lambda_expr : '(' lambda_expr lambda_expr ')'
%    | '(' '%' ID '.' lambda_expr ')'
%    | expr
%    ;

%expr : ID
%    | expr '+' expr
%    | expr '*' expr
%    ;


\item Napisati program koji omogu\' cava korisniku rad sa polinomima vi\v se promenljivih.
Program treba da omogu\' ci definisanje polinoma, izra\v cunavanje njegove vrednosti za
zadate vrednosti nezavisnih promenljivih i njegovo svo\dj enje na kanonski oblik. Polinom
je sveden na kanonski oblik ukoliko je predstavljen kao zbir monoma.
Npr.
\begin{verbatim}
f := x*(y + 2*x)+x*y
print(f[x=3, y=1])                      24
g := canonicalize(f)
print(g)                                2*x*y+2*x*x
\end{verbatim}
\end{comment}


\item Napisati program koji omogu\' cava korisniku rad sa kona\v cnim skupovima brojeva.
\begin{enumerate}
\item Skupovi se zadaju bilo navo\dj enjem elemenata izme\dj u \verb"{" i \verb"}", bilo
navo\dj enjem intervala oblika \verb"a..b". Komandom \verb"print" se ispisuju elementi
skupa.

\begin{verbatim}
A = {3, 2, 2, 1};
B = 7..10;
print A;                                {1, 2, 3}
print B;                                {7, 8, 9, 10}
\end{verbatim}

\item Nad skupovima je mogu\' ce vr\v siti operacije unije (\verb"\/"), preseka (\verb"/\")
i razlike (\verb"\").


\begin{verbatim}
A = {1, 2, 3, 4};
B = {3, 5, 7};
print A \/ B;              {1, 2, 3, 4, 5, 7}
print A /\ B;              {3}
print A \ B;               {1, 2, 4}
\end{verbatim}

\item Program treba da omogu\' ci i proveru da li je
dati broj element skupa (\verb":") i da li je jedan skup podskup drugog (\verb"<").
\begin{verbatim}
check 5 : A;                False
check 7 : A \/ B;           True
check A < B;                False
check {5, 7} < B;           True
\end{verbatim}
\end{enumerate}

\vspace{3cm}
\begin{center}
\textbf{Prevodioci i interpretatori - jun 2007. - 3. kolokvijum}
\end{center}


\item Napisati program koji omogu\' cava korisniku rad sa kona\v cnim skupovima brojeva.
\begin{enumerate}
\item Skupovi se zadaju bilo navo\dj enjem elemenata izme\dj u \verb"{" i \verb"}", bilo
navo\dj enjem intervala oblika \verb"a..b". Komandom \verb"print" se ispisuju elementi
skupa.

\begin{verbatim}
A = {3, 2, 2, 1};
B = 7..10;
print A;                                {1, 2, 3}
print B;                                {7, 8, 9, 10}
\end{verbatim}

\item Nad skupovima je mogu\' ce vr\v siti operacije unije (\verb"\/"), preseka (\verb"/\")
i razlike (\verb"\").


\begin{verbatim}
A = {1, 2, 3, 4};
B = {3, 5, 7};
print A \/ B;              {1, 2, 3, 4, 5, 7}
print A /\ B;              {3}
print A \ B;               {1, 2, 4}
\end{verbatim}

\item Program treba da omogu\' ci i proveru da li je
dati broj element skupa (\verb":") i da li je jedan skup podskup drugog (\verb"<").
\begin{verbatim}
check 5 : A;                False
check 7 : A \/ B;           True
check A < B;                False
check {5, 7} < B;           True
\end{verbatim}
\end{enumerate}


\newpage
\begin{enumerate}
\item[(d)] Kardinalnost skupova se izra\v cunava kori\v s\' cenjem komande \verb"card".
\begin{verbatim}
card  {1, 3, 2, 7, 3, 4};          5
\end{verbatim}

\item[(e)] Definisati operaciju komplementiranja \verb"~". Komplementiranje se vr\v si
u odnosu na univerzalni skup koji se zadaje kao \verb"UniversalSet".
\begin{verbatim}
UniversalSet = 1..10;
A = {1, 3, 5, 7, 9};
print ~A;                   {2, 4, 6, 8}
\end{verbatim}

Ukoliko univerzalni skup nije prethodno definisan, program treba da prijavi gre\v sku.

\item[(f)] Prilikom svakog ispisivanja skupa, potrebno je da njegovi elementi
budu iznova odre\dj eni na osnovu teku\' cih vrednosti promenljivih.
\begin{verbatim}
A = {1, 2};
B = {2, 3};
S = (A \ B) \/ (B \ A);
print S;                   {1, 3}
B = {1, 4};
print S;                   {2, 4}
\end{verbatim}
\item[(g)] Komandom \verb"partitive_set" se ispisuje partitivni skup datog skupa:
\begin{verbatim}
A = {1, 2};
partitive_set A;                {{}, {1}, {2}, {1, 2}}
\end{verbatim}

\end{enumerate}

\vspace{3cm}
\begin{enumerate}
\item[(d)] Kardinalnost skupova se izra\v cunava kori\v s\' cenjem komande \verb"card".
\begin{verbatim}
card  {1, 3, 2, 7, 3, 4};          5
\end{verbatim}

\item[(e)] Definisati operaciju komplementiranja \verb"~". Komplementiranje se vr\v si
u odnosu na univerzalni skup koji se zadaje kao \verb"UniversalSet".
\begin{verbatim}
UniversalSet = 1..10;
A = {1, 3, 5, 7, 9};
print ~A;                   {2, 4, 6, 8}
\end{verbatim}

Ukoliko univerzalni skup nije prethodno definisan, program treba da prijavi gre\v sku.

\item[(f)] Prilikom svakog ispisivanja skupa, potrebno je da njegovi elementi
budu iznova odre\dj eni na osnovu teku\' cih vrednosti promenljivih.
\begin{verbatim}
A = {1, 2};
B = {2, 3};
S = (A \ B) \/ (B \ A);
print S;                   {1, 3}
B = {1, 4};
print S;                   {2, 4}
\end{verbatim}

\item[(g)] Komandom \verb"partitive_set" se ispisuje partitivni skup datog skupa:
\begin{verbatim}
A = {1, 2};
partitive_set A;                {{}, {1}, {2}, {1, 2}}
\end{verbatim}

\end{enumerate}

\end{enumerate}
}
\end{small}
\end{document}
