1.1-scheme_basics.tex

\documentclass[alsotrans,beameroptions={aspectratio=169}]{beamerswitch}
\usepackage{fprog}

\title{Основни понятия в Scheme}

\date{2--9 октомври 2024 г.}

\lstset{language=Scheme}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\section{Въведение в Scheme}

\begin{frame}
  \frametitle{Що за език е Scheme?}

  \begin{itemize}
  \item Създаден през 1975 г. от Guy L.~Steele и Gerald Jay Sussman
  \item Диалект на LISP, създаден с учебна цел
  \item „Structure and Interpretation of Computer Programs“, Abelson \& Sussman, MIT Press, 1985.
  \item Минималистичен синтаксис
  \item Най-разпространен стандарт: R$^5$RS (1998)
  \item Най-нов стандарт: R$^7$RS (2013)
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Програмиране на Scheme}

  \begin{itemize}
  \item Среда за програмиране: DrRacket
  \item Има компилатори и интерпретатори
    \begin{itemize}
    \item Ние ще ползваме интерпретатор
    \end{itemize}
  \item REPL = Read-Eval-Print-Loop
  \item Програма = списък от дефиниции
  \item Изпълнение = оценка на израз
  \end{itemize}
\end{frame}

\section{Синтаксис и семантика}

\begin{frame}[fragile]
  \frametitle{Синтаксис в Scheme}

  \begin{itemize}[<+->]
  \item Литерали
    \begin{itemize}
    \item Булеви константи (\lst{#f}, \lst{#t})
    \item Числови константи (\lst{15}, \lst{2/3}, \lst{-1.532})
    \item Знакови константи (\lst{#\a}, \lst{#\newline})
    \item Низови константи (\lst{"Scheme"}, \lst{"hi "})
    \end{itemize}
  \item Символи (\lst{f}, \lst{square}, \lst{+}, \lst{find-min})
  \item Комбинации\\[2ex]
    \alert({}<израз$_1$> <израз$_2$> \ldots <израз$_n$>\alert)
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Оценки на литерали и символи}

  На всеки израз се дава оценка.
  \begin{itemize}[<+->]
  \item Оценката на булевите константи, знаците, числата и низовете са самите те
    \begin{itemize}
    \item \evalsto 5 5
    \item \evalsto{\#t}{\#t}
    \item \evalsto{\#\\a}{\#\\a}
    \item \evalsto{\"scheme\"}{\"scheme\"}
    \end{itemize}
  \item Оценката на символ е стойността, свързана с него
    \begin{itemize}
    \item \evalsto +{\#<procedure:+>}
    \item \evalstoerr a
    \item \lst{(define a 5)}
    \item \evalsto a5
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Основно правило за оценяване}

  Оценка на комбинация \textbf{(основно правило за оценяване)}\\[2ex]
  \begin{equation*}
    \newcommand{\evals}{\text{\small се оценява до}}
    \underbrace{%
      \begin{array}{cccccc}
        (&\text{<израз}_0\text{>}&\text{<израз}_1\text{>}&\ldots&\text{<израз}_n\text{>}&)\\
         &\vert&\vert&&\vert&\\
         &\evals&\evals&&\evals&\\
         &\bda&\bda&&\bda&\\
        (&f&v_1&\ldots&v_n&)
      \end{array}
    }_{%
      \begin{array}{c}
        \vert\\
        \evals\\
        \bda\\
        f(v_1,\ldots,v_n)
      \end{array}}
  \end{equation*}\\[2ex]
  \pause
  Ако $f$ не е функция --- \alert{грешка!}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Пример за оценяване на комбинации}
  \begin{fixedarea}[.7]
    \begin{equation*}
      \underbrace{%
        \begin{tabular}{cccc}
          \tt{(+}&$\underbrace{\tt{(* 2 3)}}_{}$&$\underbrace{\tt{(- 14 6 5)}}_{}$&\tt)\\
                 &\bda&\bda&\\
          \tt{(+}&\tt6&\tt3&\tt)
        \end{tabular}
      }_{%
        \begin{tabular}{c}
          \bda\\
          \tt 9
        \end{tabular}}
    \end{equation*}\\[4ex]
    \pause
    \onslide<+->
    \begin{center}
      \evalstoerrp {(1 2 3)}
    \end{center}
  \end{fixedarea}
\end{frame}

\section{Дефиниции в Scheme}

\begin{frame}
  \frametitle{Дефиниция на символи}

  \begin{itemize}[<+->]
  \item \tta{(define} <символ> <израз>\tta)
  \item Оценява <израз> и свързва <символ> с оценката му.
  \item Примери:
    \begin{itemize}
    \item \lst{(define s "Scheme is cool")}
    \item \evalsto s{\"Scheme is cool\"}
    \item \lst{(define x 2.5)}
    \item \evalsto x{2.5}
    \item \evalsto{(+ x 3.2)}{5.7}
    \item \lst{(define y (+ x 3.2))}
    \item \evalsto{(> y 3)}{\#t}
    \item \evalstoerr{(define z (+ y z))}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Специални форми}

  \begin{itemize}[<+->]
  \item По основното правило ли се оценява \lst{(define x 2.5)}?
  \item \alert{Не!}
  \item В синтаксиса на Scheme има конструкции, които са изключение от стандартното правило
  \item Такива конструкции се наричат \textbf{специални форми}
  \item \tt{define} е пример за специална форма
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Цитиране}

  \begin{itemize}[<+->]
  \item \tta{(quote} <израз>\tta)
  \item Алтернативен запис: \tta'<израз>
  \item Оценката на \tt{(quote} <израз>\tt) или \tt'{}<израз> е самият <израз>
  \item \textbf{Примери:}
    \begin{itemize}
    \item \evalsto{'2}2
    \item \evalsto{'+}+
    \item \evalsto{'(+ 2 3)}{(+ 2 3)}
    \item \evalsto{(quote quote)}{quote}
    \item \evalstoerr{('+ 2 3)}
    \item \evalstoerr{(/ 2 0)}
    \item \evalsto{'(/ 2 0)}{(/ 2 0)}
    \item \evalsto{'(+ 1 '(* 3 4))}{(+ 1 (quote (* 3 4)))}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Дефиниция на функции}

  \begin{itemize}[<+->]
  \item \tta{(define (}{}<функция> \{{}<параметър>\}\tta) <тяло>\tta)
  \item {}<функция> и <параметър> са символи
  \item {}<тяло> е <израз>
  \item Символът <функция> се свързва с поредица от инструкции, които пресмятат <тяло> при подадени стойности на <параметър>
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Примери за дефиниция на функции}

  \begin{itemize}[<+->]
  \item \lst{(define (square x) (* x x))}
  \item \evalsto{(square 5)}{25}
  \item \lst{(define (1+ k) (+ k 1))}
  \item \evalsto{(square (1+ (square 3)))}{100}
  \item \lst{(define (f x y) (+ (square (1+ x)) (square y) 5))}
  \item \evalstop{(f 2 4)}{30}
  \item \lst{(define (g x) (- (g (+ x 1)) 1))}
  \item \evalstop{(g 0)}{...}
  \item \lst{(define (h) (+ 2 3))}
  \item \evalsto{h}{\#<procedure:h>}
  \item \evalsto{(h)}5
  \end{itemize}

\end{frame}

\begin{frame}
  \frametitle{Оценяване на комбинации с дефинирани функции}
  \begin{center}
    \evalchain{
      "(f 2 4)" ->
      "(+ (square (1+ 2)) (square 4) 5)" ->
      "(+ (square (+ 2 1)) (square 4) 5)" ->
      "(+ (square 3) (square 4) 5)" ->
      "(+ (* 3 3) (* 4 4) 5)" ->
      "(+ 9 16 5)" ->
      "30"
    }
  \end{center}
\end{frame}

\section{Стандартни функции}

\begin{frame}
  \frametitle{Стандартни числови функции}

  Аритметични операции\\
  \tt{+}, \tt{-}, \tt{*}, \tt{/}\\[1em]
  Други числови функции\\
  \tt{remainder}, \tt{quotient}, \tt{max}, \tt{min}, \tt{gcd}, \tt{lcm}\\[1em]
  Функции за закръгляне\\
  \tt{floor}, \tt{ceiling}, \tt{round}\\[1em]
  Функции над дробни числа\\
  \tt{exp}, \tt{log}, \tt{sin}, \tt{cos}, \tt{tan}, \tt{asin}, \tt{acos}, \tt{atan}, \tt{expt}, \tt{sqrt}
\end{frame}

\begin{frame}
  \frametitle{Стандартни предикати}

  Предикати за сравнение на числа\\
  \tt{<}, \tt{>}, \tt{=}, \tt{<=}, \tt{>=}\\[1em]
  Числови предикати\\
  \tt{zero?}, \tt{negative?}, \tt{positive?}, \tt{odd?}, \tt{even?}\\[1em]
  Предикати за проверка на тип\\
  \tt{boolean?}, \tt{number?}, \tt{char?}, \tt{string?}, \tt{symbol?}, \tt{procedure?}
\end{frame}

\section{Условни изрази}

\begin{frame}
  \frametitle{Условна форма \tt{if}}

  \begin{itemize}[<+->]
  \item \tta{(if} <условие> <израз$_1$> <израз$_2$>\tta)
  \item Оценява се <условие>
    \begin{itemize}
    \item Ако оценката е \tt{\#t} --- връща се оценката на <израз$_1$>
    \item Ако оценката е \tt{\#f} --- връща се оценката на <израз$_2$>
    \end{itemize}
  \item \alert{\tt{if} е специална форма!}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Примери с условната форма \tt{if}}

  \begin{itemize}[<+->]
  \item \evalsto{(if (< 3 5) (+ 7 3) (- 4 2))}{10}
  \item \lst{(define (abs x) (if (< x 0) (- x) x))}
  \item \evalsto{(abs -5)}5, \evalsto{(abs (+ 1 2))}3
  \item \lst{(define (f x) (if (< x 5) (+ x 2) "Error"))}
  \item \evalsto{(f 3)}5, \evalsto{(f 5)}{\"Error\"}
  \item \lst{(define (g x y) (if (< x y) (+ x y) (* x y)))}
  \item \lst{(define (g x y) ((if (< x y) + *) x y))}
  \item \evalsto{(g 2 3)}5, \evalsto{(g 3 2)}6
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Форма за многозначен избор \tt{cond}}

  \begin{itemize}[<+->]
  \item \tta{(cond} \{\tta({}<условие> <израз>\tta)\} [\tta{(else} <израз>\tta)]\tta)
  \item \tta{(cond (}{}<условие$_1$> <израз$_1$>\tta)\\
    \tta{\hskip 7ex(}{}<условие$_2$> <израз$_2$>\tta)\\
    \hskip 7ex\ldots\\
    \tta{\hskip 7ex(}{}<условие$_n$> <израз$_n$>\tta)\\
    \tta{\hskip 7ex(else} <израз$_{n+1}$>\tta{))}
  \item Оценява се <условие$_1$>, при \tt{\#t} се връща <израз$_1$>, а при \tt{\#f}:
  \item Оценява се <условие$_2$>, при \tt{\#t} се връща <израз$_2$>, а при \tt{\#f}:
  \item \ldots
  \item Оценява се <условие$_n$>, при \tt{\#t} се връща <израз$_n$>, а при \tt{\#f}:
  \item Връща се <израз$_{n+1}$>
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Пример с формата \tt{cond}}

\begin{lstlisting}
(define (grade x)
  (cond ((>= x 5.5) "Отличен")
        ((>= x 4.5) "Много добър")
        ((>= x 3.5) "Добър")
        ((>= x 3)   "Среден")
        (else       "Слаб")))
\end{lstlisting}
\end{frame}

\begin{frame}
  \frametitle{Форма за разглеждане на случаи \tt{case}}

  \begin{itemize}[<+->]
  \item \tta{(case} <тест> \{\tta({}\tta(\{<случай>\}\tta) <израз>\tta)\} [\tta{(else} <израз>\tta)]\tta)
  \item \tta{(case} <тест> \tta{((}{}<случай$_{1,1}$> \ldots <случай$_{1,k_1}$>\tta) <израз$_1$>\tta)\\
    \tta{\hskip 16ex((}{}<случай$_{2,1}$> \ldots <случай$_{2,k_2}$>\tta) <израз$_2$>\tta)\\
    \hskip 16ex\ldots\\
    \tta{\hskip 16ex((}{}<случай$_{n,1}$> \ldots <случай$_{n,k_n}$>\tta) <израз$_n$>\tta)\\
    \tta{\hskip 16ex(else} <израз$_{n+1}$>\tta{))}
  \item Оценява се <тест>
  \item при някое от <случай$_{1,1}$>\ldots<случай$_{1,k_1}$> $\rightarrow$ <израз$_1$>, иначе:
  \item при някое от <случай$_{2,1}$>\ldots<случай$_{2,k_2}$> $\rightarrow$ <израз$_2$>, иначе:
  \item \ldots
  \item при някое от <случай$_{n,1}$>\ldots<случай$_{n,k_n}$> $\rightarrow$ <израз$_n$>, иначе:
  \item Връща се <израз$_{n+1}$>
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Пример с формата \tt{case}}

\begin{lstlisting}
(define (days-in-month m y)
  (case m
    ((1 3 5 7 8 10 12) 31)
    ((4 6 9 11) 30)
    (else (if (leap? y) 29 28))))
\end{lstlisting}
\end{frame}

\begin{frame}
  \frametitle{Логически операции}

  \begin{itemize}[<+->]
  \item \tta{(not} <булев-израз>\tta)
    \begin{itemize}
    \item Връща отрицанието на <булев-израз>
    \end{itemize}
  \item \tta{(and} \{<булев-израз>\}\tta)
  \item \tta{(and} <булев-израз$_1$> <булев-израз$_2$> \ldots <булев-израз$_n$>\tta)
    \begin{itemize}
    \item Оценява последователно всички <булев-израз$_i$>
    \item Ако всички се оценяват до \tt{\#t}, връща \tt{\#t}
    \item Ако <булев-израз$_i$> се оценява до \tt{\#f}, връща
      \tt{\#f} без да оценява следващите <булев-израз$_{i+1}$> \ldots <булев-израз$_n$>
    \end{itemize}
  \item \tta{(or} \{<булев-израз>\}\tta)
  \item \tta{(or} <булев-израз$_1$> <булев-израз$_2$> \ldots <булев-израз$_n$>\tta)
    \begin{itemize}
    \item Оценява последователно всички <булев-израз$_i$>
    \item Ако всички се оценяват до \tt{\#f}, връща \tt{\#f}
    \item Ако <булев-израз$_i$> се оценява до \tt{\#t}, връща
      \tt{\#t} без да оценява следващите <булев-израз$_{i+1}$> \ldots <булев-израз$_n$>
    \end{itemize}
  \item \alert{\tt{and} и \tt{or} са специални форми!}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Примери с логически операции}

  \begin{tabular}{lcl}
    \lstinline!(not x)! &\eqv& \lstinline!(if x #f #t)!\\
    \lstinline!(and x y)! &\eqv& \lstinline!(if x y #f)!\\
    \lstinline!(or x y)! &\eqv& \lstinline!(if x #t y)!
  \end{tabular}
  \pause
\begin{lstlisting}
(define (divisible? a b)
  (= (remainder a b) 0))

(define (leap? y)
  (and (divisible? y 4)
       (or (not (divisible? y 100))
           (divisible? y 400))))
\end{lstlisting}
\end{frame}
\end{document}