lisp-beamer.tex

\PassOptionsToPackage{table,dvipsnames}{xcolor}
\documentclass[fleqn]{beamer}
\usepackage{00}
\setdefaultlanguage{english}
\setmainlanguage{english}
\setotherlanguage{arabic}
\setotherlanguage{hebrew}

\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=white,
    urlcolor=blue,
}

% More space between lines in align
\setlength{\mathindent}{0pt}

% Beamer theme
%\usetheme{ZMBZFMK}
%\usefonttheme[onlysmall]{structurebold}
\mode<presentation>
\setbeamercovered{transparent=10}

% align spacing
\setlength{\jot}{0pt}

%\setbeamertemplate{navigation symbols}{}%remove navigation symbols

\title{Mini Lisp}
\author{Maxim Barsky}
\institute[236319/2020/2021]{%
Programming Languages 236319⏎
Autumn 2020/Winter 2021 ⏎
Department of Computer Science ⏎
The Technion
}
\date{\today}

\begin{document}
\setLTR
\begin{frame}
\titlepage
\end{frame}

\begin{frame}{Preliminaries}
\begin{block}{Common lisp online IDE}
  \url{https://rextester.com/l/common_lisp_online_compiler}
\end{block}
Note: Common Lisp language is (mostly) a superset of Mini Lisp.
\begin{block}{Allowed functions in this course}
  \begin{itemize}
    \item 8 atomic (primitive) functions of mini-lisp
    \item 8 library functions of mini-lisp
    \item any functions you define with these
  \end{itemize}
\end{block}
\begin{block}{In this course…}
  We implement function \lisp{eval} using atomic and library functions only.
\end{block}
\end{frame}

\begin{frame}{Eight Atomic Functions of Mini Lisp}{atomic functions are builtin}
\begin{block}{3 Structural Functions:}
  car/1, cdr/1, cons/2
\end{block}
\begin{block}{3 Logical Functions: }
  atom/1, eq/2, cond/2
\end{block}
\begin{block}{2 Other Functions: }
  set/2, error/n 
\end{block}
\end{frame}

\begin{frame}{The Three Structural Functions}
    \begin{description}
      \item[car/1] Quiz:
        \begin{itemize}
          \item \lisp{(car '(b.a))}?
          \item \lisp{(car '(b a))}?
          \item \lisp{(car '(a))}?
          \item \lisp{(car 'a)}?
          \item \lisp{(car ())}?
        \end{itemize}
      \item[cdr/1] Quiz:
        \begin{itemize}
          \item \lisp{(cdr '(a.b))}?
          \item \lisp{(cdr '(a b))}?
          \item \lisp{(cdr '(b))}?
          \item \lisp{(cdr t)}?
          \item \lisp{(cdr ())}?
          \item \lisp{(cdr nil)}?
        \end{itemize}
      \item[cons/2] Quiz:
        \begin{itemize}
          \item \lisp{(cons 'a '(b c))}?
          \item \lisp{(cons 'b nil)}?
          \item \lisp{(cons 'a 'b)}?
        \end{itemize}
\end{description}
\end{frame}

\begin{frame}{The Three Logical Functions}
    \begin{description}
      \item[atom/1] Quiz:
        \begin{itemize}
          \item \lisp{(atom nil)}?
          \item \lisp{(atom t)}?
          \item \lisp{(atom '(a a))}?
          \item \lisp{(atom 'a)}?
        \end{itemize}
      \item[eq/1] Quiz:
        \begin{itemize}
          \item \lisp{(eq t t)}?
          \item \lisp{(eq t nil)}?
          \item \lisp{(eq nil nil)}?
          \item \lisp{(eq 'a 'a)}?
          \item \lisp{(eq '(a a) '(a a))}?
        \end{itemize}
      \item[cond/n] Quiz:
        \begin{itemize}
          \item \lisp{(cond (t 'A))}?
          \item \lisp{(cond (nil 'A) (t 'B))}?
          \item \lisp{(cond (nil 'A) (t 'B) (t 'C))}?
          \item \lisp{(cond (nil 'A) (nil 'B) (nil 'C))}?
          \item \lisp{(cond)}?
        \end{itemize}
\end{description}
\end{frame}

\begin{frame}{The Remaining ``Other'' Functions}
\begin{description}
      \item[set/2] Quiz:
        \begin{itemize}
          \item \lisp{(set 'a '(b c))}?
          \item \lisp{(set 'b nil)}?
        \end{itemize}
      \item[error/2] Quiz:
        \begin{itemize}
          \item \lisp{(error)}?
          \item \lisp{(error A)}?
          \item \lisp{(error 'my-error 'message)}?
        \end{itemize}
\end{description}
\end{frame}

\begin{frame}{Predefined Functions in Mini Lisp}{defined using atomic functions only}
\begin{block}{Predefined Functions}
  defun ⏎
  lambda ⏎
  null ⏎
  ndefun ⏎
  nlambda ⏎
  quote
\end{block}
Two concepts:
\begin{itemize}
  \item Function name: strings \texttt{defun}, \texttt{nlamda},…
  \item Function body: defined in library
\end{itemize}
\pause
\begin{block}{Predefined Names of Atoms}
  t ⏎
  nil
\end{block}

% FIXME: the following part is not visible in the slide, it overflows the page
Predefined atoms, are just like functions that take no argument,
\begin{itemize}
  \item Function name: strings \texttt{t} and \texttt{nil}
  \item Function body: defined in library to the string \texttt{t} and \texttt{nil}
\end{itemize}
\end{frame}

\begin{frame}{Definition of predefined functions}
\begin{LTR}
  \lstinputlisting[language=kernel,style=display,
    numbers=left,
    stepnumber=1,
    numbersep=2pt,
    xleftmargin=3ex,
    numberblanklines=false,
    numberstyle=\tiny\bf,
    backgroundcolor=\color{orange!20}
  ]{00.library.lisp}
\end{LTR}
\end{frame}

\begin{frame}
\frametitle{Exercise}
\begin{block}{Binary representation of numbers}
  First let us define how we represent an unsigned integer in binary, ⏎
  A number will be represented in its' binary form as a List consisting of the atom O and Z with the LSB (Least Significant Bit) first. ie. the leftmost bit the the LSB. ⏎
  The atom Z will represent zero and the atom O will represent one.
\end{block}

\begin{block}{Example}
  The number~$6={110}_b$ will be represented as (Z O O) ⏎
  The number~$9={1001}_b$ will be represented as (O Z Z O)
\end{block}
\end{frame}

\begin{frame}{Exercise}
\begin{block}{Implement the following functions}
  \begin{description}
    \item [bnormalize] receives a number represented as a list and returns its'
      shortest representation, without trailing zeros.
    \item [badd] receives two numbers represented as lists (not necessarily the
      shortest-
      normalized representation) and returns the shortest list representing the
      sum of the two numbers.
  \end{description}
\end{block}
\end{frame}

\begin{frame}[fragile]
\frametitle{Solution- bnormalize}
\begin{block}{Auxiliary functions}
  \begin{LISP}
(defun list-contains-only-zeros (l) (
  cond
    ((null l) t)
    ((eq (car l) (quote Z))
      (list-contains-only-zeros (cdr l)))
    ((eq (car l) (quote O)) (nil))
))
    \end{LISP}
\end{block}
\end{frame}

\begin{frame}[fragile]
\frametitle{Solution- bnormalize}
\begin{block}{bnormalize}
  \begin{LISP}
(defun bnormalize (l) (
  cond
    ((list-contains-only-zeros l) nil)
    (t (cons (car l) (bnormalize (cdr l))))
))
    \end{LISP}
\end{block}
\end{frame}

\begin{frame}[fragile]
\frametitle{Solution- badd}
\begin{block}{Auxiliary functions}
  \begin{LISP}
(defun andalso (b1 b2) (
  cond
    ((null b1) nil)
    ((null b2) nil)
    (t t)
))
    \end{LISP}
\end{block}
\end{frame}

\begin{frame}[fragile]
\frametitle{Solution- badd}
\begin{block}{badd}
  \begin{LISP}
(defun badd (l1 l2) (
  cond
    ((null (bnormalize l1)) (bnormalize l2))
    ((null (bnormalize l2)) (bnormalize l1))
    ((andalso (eq (car l1) 'O) (eq (car l2) 'O))
      (cons 'Z (badd (badd 'O (cdr l1)) (cdr l2))))
    ((andalso (eq (car l1) 'Z) (eq (car l2) 'Z))
      (cons 'Z (badd (cdr l1) (cdr l2))))
    (t (cons 'O (badd (cdr l1) (cdr l2))))
))
    \end{LISP}
\end{block}

\begin{block}{Note}
  \lisp{(quote X)} is equivalent to \lisp{'X}.
\end{block}
\end{frame}

% should this be in the slides? or maybe use this or bsub as homework
% this is homework.

\begin{frame}[fragile]{Solution- bmul}
\begin{block}{bmul}
  \begin{LISP}
(defun bmul (l1 l2) (
  cond
    ((null (bnormalize l1)) nil)
    ((eq (car l1) 'O)
      (bnormalize
        (badd l1 (cons 'Z (bmul l1 (cdr l2))))))
    ((eq (car l1) 'Z) (cons 'Z (bmul l1 (cdr l2))))
))
    \end{LISP}
\end{block}
\end{frame}

\end{document}
\begin{frame}
\frametitle{Exercise}
\uncover<1>{erster Satz}⏎
\uncover<3>{zweiter Satz}⏎
\uncover<2>{dritter Satz}
\end{frame}