\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.}
\end{center}
\begin{enumerate}
\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$ redukcija zamenjuje sva 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)$
ispravnom $\beta$ konverzijom svodi na izraz
$(\lambda y'.\ y + y')$, a ne na $(\lambda y.\ y + y)$, kao \v sto bi se moglo pomisliti.

\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$redukcija 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
%    ;
\end{enumerate}

\begin{center}
\textbf{Prevodioci i interpretatori - jun 2007.}
\end{center}
\begin{enumerate}
\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$ redukcija zamenjuje sva 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)$
ispravnom $\beta$ konverzijom svodi na izraz
$(\lambda y'.\ y + y')$, a ne na $(\lambda y.\ y + y)$, kao \v sto bi se moglo pomisliti.

\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$redukcija 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
%    ;
\end{enumerate}

\newpage
\begin{enumerate}
\item[2.]
\begin{enumerate}
\item Napisati perl skript koji omogu\' cava korisniku rad sa kona\v cnim skupovima brojeva.
Skript, simulacijom rada potisnog automata nani\v ze, izra\v cunava vrednost izraza
u kojima u\v cestvuju operacije unije (\verb"\/"), preseka (\verb"/\") i razlike (\verb"\").
Npr. \verb"{1, 2, 3, 1} \/ ({4, 5} /\ ({5, 6} \ {6}))". Za izraz koji se unosi sa standardnog
ulaza, skript na standardni izlaz ispisuje rezultat.
\item Osnovno\v skolci su radili test poznavanja skupovnih operacija. Direktorijum
\v cije je ime argument komandne linije perl skripta sadr\v zi datoteke sa radovima
u\v cenika. Svaka datoteka nosi ime u\v cenika, a sadr\v zi niz linija, pri \v cemu
svaka linija sadr\v zi prvo skupovni izraz koji predstavlja pitanje postavljeno u\v ceniku,
a zatim skup koji je u\v cenik naveo kao odgovor. Napisati perl skript koji, koriste\' ci
skript iz prethodnog dela zadatka, generi\v se HTML tabelu u kojoj se rezimira uspeh svakog
u\v cenika. Tabela bi trebalo da sadr\v zi ime u\v cenika, ukupan broj njemu postavljenih pitanja
i broj pitanja na koje je ta\v cno odgovorio. Tabela bi trebalo da je sortirana opadaju\' ce
na osnovu procenta ta\v cnih odgovora.
\end{enumerate}
\end{enumerate}

\vspace{10cm}
\begin{enumerate}
\item[2.]
\begin{enumerate}
\item Napisati perl skript koji omogu\' cava korisniku rad sa kona\v cnim skupovima brojeva.
Skript, simulacijom rada potisnog automata nani\v ze, izra\v cunava vrednost izraza
u kojima u\v cestvuju operacije unije (\verb"\/"), preseka (\verb"/\") i razlike (\verb"\").
Npr. \verb"{1, 2, 3, 1} \/ ({4, 5} /\ ({5, 6} \ {6}))". Za izraz koji se unosi sa standardnog
ulaza, skript na standardni izlaz ispisuje rezultat.
\item Osnovno\v skolci su radili test poznavanja skupovnih operacija. Direktorijum
\v cije je ime argument komandne linije perl skripta sadr\v zi datoteke sa radovima
u\v cenika. Svaka datoteka nosi ime u\v cenika, a sadr\v zi niz linija, pri \v cemu
svaka linija sadr\v zi prvo skupovni izraz koji predstavlja pitanje postavljeno u\v ceniku,
a zatim skup koji je u\v cenik naveo kao odgovor. Napisati perl skript koji, koriste\' ci
skript iz prethodnog dela zadatka, generi\v se HTML tabelu u kojoj se rezimira uspeh svakog
u\v cenika. Tabela bi trebalo da sadr\v zi ime u\v cenika, ukupan broj njemu postavljenih pitanja
i broj pitanja na koje je ta\v cno odgovorio. Tabela bi trebalo da je sortirana opadaju\' ce
na osnovu procenta ta\v cnih odgovora.
\end{enumerate}
\end{enumerate}
}
\end{small}


\end{document}
