#set page(
  paper: "a4",
  margin: (x: 1.5cm, y: 1.5cm),
)

#set par(
  justify: true,
)

#set text(
  size: 12pt
)

#set heading(
  numbering: "1.",
  supplement: [Разделе]
)

#show raw: set block(
  above: 1em,
  below: 2em,
)

#let clr-caption = rgb("777777")
#let que = [*(?)*]

#let cred(url) = link(
  url,
  text(
    fill: blue
  )[
    \[cred\]
  ],
)

#let caption(body) = text(fill: clr-caption)[
  #par[
    #body
  ]
]

#align(center)[
  #text(18pt)[*Материалы по языкам программирования*]

  Январь 2024
]

= Динамическое окружение
#caption[
  Понятие динамического окружения. Порядок формирования и использования динамического окружения.
]

*Динамическое окружение* #sym.dash.em окружение, в котором присутствует структура данных, связывающая имена переменных с их значением во время выполнения очередной инструкции.

Рассмотрим пример формирования динамического окружения на языке _SML_. В примере упростим представление динамического окружения до массива, содержащего пару "имя переменной" #sym.arrow.l.r "значение". Функции будем связывать с их замыканиями:
```sml
val x = 2 (* [(x, 2)] *)
val y = x + 3 (* [(y, 5), (x, 2)] *)
val z = x + y (* [(z, 7), (y, 5), (x, 2)] *)
(* #[(x, 49), (z, 7), (y, 5), (x, 2)] произошло затенение *)
val x = z * z
(* [(x, 49), (z, 7), (y, 5), (x, 2)] в let создается временное динамическое окружение *)
val z =
  let
    val x = 7 (* [(x, 7), (x, 49), (z, 7), (y, 5), (x, 2)] *)
    val d = 1 (* [(d, 1), (x, 7), (x, 49), (z, 7), (y, 5), (x, 2)] *)
  in
    z + x + d (* [(z, 15), (d, 1), (x, 7), (x, 49), (z, 7), (y, 5), (x, 2)] *)
  end (* [(z, 15), (x, 49), (z, 7), (y, 5), (x, 2)] *)
(* [(e, -10), (z, 15), (x, 49), (z, 7), (y, 5), (x, 2)] *)
val e = z - 25
(* [(x, 3), (e, -10), (z, 15), (x, 49), (z, 7), (y, 5), (x, 2)] *)
val x = 3
(* [(f, [x], x + 25, [(x, 3), ...]), (x, 3), (e, -10), (z, 15), (x, 49), (z, 7), (y, 5), (x, 2)] *)
fun f x = x + 25
```

Функция в динамическое окружение записывается в виде замыкания:
#align(center)[
  ```text [форм. параметры], тело, [копия текущего окружения]```
]

Здесь отражён основной принцип формирования динамического окружения. Он не идеален, и существует множество других более эффективных реализаций.
#cred("https://course.sgu.ru/mod/forum/discuss.php?d=14597#p28625")

= Абстракции
#caption[
  Что понимается под терминами "Абстракция данных", "Абстракция процессов"? Что значит "построение абстракций"? Что такое "Барьеры абстракций"? За счет чего обеспечивается абстрагирование?
]

*Абстрагирование* #sym.dash.em процесс удаления характеристик чего-либо с целью сведения его к набору существенных элементов.

*Абстракция данных* #sym.dash.em сведение набора данных к упрощенному представлению целого.

*Абстракция процессов* фокусируется на сокрытии деталей реализации процесса или алгоритма и предоставлении упрощенного интерфейса для его запуска (*методы*). Это позволяет инкапсулировать набор операций в единую сущность. Причём пользователь объекта не обязан знать реализацию метода.

*Построение абстракций* #sym.dash.em процесс компоновки техник абстракции данных и абстракции процессов для постоения одной абстрактной сущности #sym.dash.em объекта или класса.

#que *Барьеры абстракций* #sym.dash.em те высокоуровневые операции, которые предоставлены пользователю создателями класса. Нарушение барьера абстракций #sym.dash.em использование низкоуровневых методов и полей, когда имеются более высокоуровневые, выполняющие ту же задачу.

В объектно ориентированных языках программирования абстракция реализована через понятия классов и объектов (абстрагирование данных).
Она используется для того, чтобы скрывать низкоуровневые детали компонентов программы, содержащих логику, что позволяет упростить процесс разработки.

В ООП приложения строятся вокруг объектов и *сообщений*, с помощью которых объектам можно подавать сигнал на изменение внутреннего состояния или запрашивать информацию о нём (абстрагирование процессов).

Пример на языке _Ruby_:
```rb
class Point
  attr_accessor :x, :y

  def initialize(x, y)
    @x = x
    @y = y
  end

  def move(dx, dy)
    @x += dx
    @y += dy
  end
end

# абстракция данных: передаем данные о точке одним объектом
def diag_move(p, v)
  p.move(v, v)
end

p1 = Point.new(x, y)

# абстракция процесса
p1.move(4, 7)

# нарушение барьера абстракций
p1.x += 10
p1.y += 11
```

= Рекурсивный и итерационный процесс
#caption[
  Рекурсивный и итерационный процесс. Хвостовая рекурсия. Преимущества хвостовой рекурсии над нехвостовой. Преимущества нехвостовой рекурсии над хвостовой.
]
*Рекурсия* #sym.dash.em это функция, которая вызывает саму себя, но с другими значениями параметров.

*Рекурсивный процесс* #sym.dash.em это процесс вызова рекурсивной функции, при котором состояние вызывающей функции сохраняется в памяти до момента, пока не будет известен результат вызываемой функции.

*Итерационный процесс* #sym.dash.em процесс вызова рекурсивной функции без сохранения в памяти состояния вызывающей функции.

Функции, где рекурсивный вызов является последней выполняемой операцией называются *функциями с хвостовой рекурсией*.

== Две реализации функции вычисления факториала на языке _SML_
С хвостовой рекурсией:
```sml
fun fact (n, acc) =
  if (n < 1) then acc
  else fact (n - 1, n * acc)
```

Без хвостовой рекурсии #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14588#p28648"):
```sml
fun fact n =
  if (n < 1) then 1
  else n * fact (n - 1)
```

Одним из основных преимуществ хвостовой рекурсии является меньший расход памяти, а нехвостовой #sym.dash.em наглядность выполнения операций и меньшая громоздкость кода.

== Хвостовая рекурсия в языках с ленивой моделью вычислений
Хвостовая рекурсия может быть неприемлема в языках, где присутствуют ленивые вычисления. Рассмотрим пример на языке _Haskell_:
```hs
-- без хвостовой рекурсии
fromTo n m = n : xs
  where
    xs = if n >= m then []
         else fromTo (n + 1) m

-- с хвостовой рекурсией
fromTo' n m = fromToTmp [] m
  where
    fromToTmp acc m' =
      if m' < n then acc
      else fromToTmp (m' : acc) (m' - 1)

nth l n =
  if n == 0 then head l
  else nth (tail l) (n - 1)
```

Вызов ```hs nth (fromTo 5 2000000) 5``` завершится за приемлемое время. Но ```hs nth (fromTo' 5 2000000) 5``` нет. Так происходит потому, что в ``` fromTo ``` результат может быть вычислен до СГНФ, и `nth` сможет выполнить операцию почти моментально. А в `fromTo'` сначала должен создаться полный список, и только потом `nth` сможет извлечь из него значение.

= Модели вычислений
#caption[
  Модели вычислений: аппликативные вычисления, нормальный порядок вычислений.
]

*Аппликативные вычисления* #sym.dash.em стратегия вычисления, при которой сначала вычисляются аргументы функции (значения фактических параметров), потом вызывается сама функция. Проблема таких вычислений #sym.dash.em выражения могут быть невычислимы.

*Нормальные вычисления* #sym.dash.em стратегия вычисления, при которой сначала вызываются все функции до тех пор, пока выражение не будет упрощено до элементарных операций, потом вычисляется полученное упрощенное выражение (подстановка аргументов в функции, пока не дойдем до элементарных операций).
Проблема таких вычислений #sym.dash.em возможны повторные вычисления. 

Пусть на некотором языке заданы функции:
```sml
fun sq x = x * x
fun f (x, y) = sq x + sq y
```

Если бы язык имел аппликативную модель вычислений, то вызов ``` f (1 + 2, 2)``` разрешился бы как:
```
f (1 + 2, 2)
f (3, 2)
sq 3 + sq 2
(op +) (sq 3) (sq 2)
(op +) (3 * 3) (sq 2)
(op +) 9 (sq 2)
(op +) 9 (2 * 2)
(op +) 9 4
13 
```

А если бы нормальную модель, то так #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14589#p28694"):
```
f (1 + 2, 2)
(op +) (sq (1 + 2)) (sq 2)
(op +) ((1 + 2) * (1 + 2)) (sq 2)
(op +) ((1 + 2) * (1 + 2)) (2 * 2)
(op +) (3 * (1 + 2)) (2 * 2)
(op +) (3 * 3) (2 * 2)
(op +) 9 (2 * 2)
(op +) 9 4
13
```

= Объекты первого класса <first-class-citizens>
#caption[
  Понятие "Объект первого класса". Примеры сущностей, являющихся и не являющихся объектами первого класса.
]

*Объект первого класса* #sym.dash.em сущность языка программирования, которую можно:
+ Передавать в качестве аргумента.
+ Возвращать в качестве результата.
+ Связывать с именем.
+ Сохранять как элемент сложной структуры данных.
+ Проверять на равенство.

Сущность может принадлежать, либо не принадлежать объектам первого класса #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14590#p28623").

Например, в _SML_ объектами 1-го класса будут:
- функции; ```sml
fun add (x, y) = x + y
val myFunction = add
```
- значения (включая сложные структуры данных); ```sml
val x = 42
val myList = [1, 2, 3]
```
- записи; ```sml
type person = { name: string, age: int }
val john = { name = "John", age = 30 }
```
- типы данных. ```sml
datatype 'a tree = Empty | Node of 'a * 'a tree * 'a tree
val myTree = Node(1, Node (2, Empty, Empty), Node (3, Empty, Empty))
(* использование Empty как аргумента конструктора Node *)
```

В _Ruby_, например, следующие сущности будут принадлежать 1-му классу:
- объекты; ```rb
x = 42
def add(x, y)
  x + y
end

my_function = method(:add)
```
- `Proc` и `Proc`-лямбды ```rb
x = -> (x) { x + 5 }
```
- идентификаторы; ```rb
my_symbol = :example
```
- массивы и хэши; ```rb
my_array = [1, 2, 3]
my_hash = { key: 'value' }
```
- классы и модули. ```rb
class MyClass
  # ...
end

my_class = MyClass.new
```
На самом деле в _Ruby_ всё, что является объектом #sym.dash.em объект 1-го класса. А к объектам относится всё вышеперечисленное.

К объектам в _Ruby_ не относятся блоки: им нельзя присвоить имя или сохранить в переменную без перевода в объект класса `Proc`. С ними нельзя делать ничего, кроме как передать в функцию.

= Функции как объекты первого класса
#caption[
  Функции как объекты первого класса на примере языка _Standard ML_.
]

_SML_ #sym.dash.em функциональный язык программирования, поэтому функция в нём является объектом первого класса. Приведём примеры такого поведения функции.
#list(tight: false)[
  Возврат функции в качестве результата в зависимости от значения аргумента #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14591#p28629"):
  ```sml
  fun realFun a = if a > 0 then Math.cos else Math.sin
  ```
][
  Передача `f` в качестве аргумента в функцию `apply` и возврат результата применения этой функции к значению:
  ```sml
  fun apply f = f 3.0
  ```
][
  Переменным можно присваивать функции:
  ```sml
  fun f x = 5 + x
  val g = f
  val z = g 4
  val k = f 4
  ```
][
  Сохранение в список:
  ```sml
  val l = [ Math.sin, Math.cos ]
  ```
][
  Проверка на равенство:
  ```sml
  val f = Math.sin
  val g = Math.cos
  f = g
  ```
]

= Затенение
#caption[
  Что такое затенение? В чем заключается его механизм?
]

*Затенение* #sym.dash.em объявление идентификатора, который уже существует в окружении. Таким образом, доступ к прежнему значению идентификатора невозможен, поскольку невозможно разрешить неоднозначность между "старым" (возможно, несколькими старыми) и "новым" значениями данного идентификатора #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14592#p28627").

Пример:
```sml
val x = 5
val y = 4
val x = 12 (* (x, 5) затенено в данном окружении *)
```

В функциях _SML_ будет использоваться то значение, которое было
первым в динамическом окружении при объявлении функции:
```sml
val x = 5
val x = "text"
fun f s = x ^ s
f "more"
```

= Лексика, синтаксис, семантика
#caption[
  Лексика, синтаксис, семантика. Что есть что. В частности, в отношении языка программирования.
]

*Лексика* #sym.dash.em словарный состав языка, совокупность слов ("лексем") конкретного языка. Включает в себя:
- *ключевые слова* #sym.dash.em предварительно определенные идентификаторы, имеющие особое синтаксическое значение (`for`, `while`, `if`, `else`, ...);
- *литералы* #sym.dash.em безымянные константы, являющиеся фиксированными значениями (`23`, `-8`, `"abc"`, `7e-8`, ...);
- *идентификаторы* #sym.dash.em имена, задаваемые в программе для переменных, типов и функций (`a2`, `abc`, `zlp`, ...);
- *разделители* #sym.dash.em используются для отделения друг от друга (разделения) лексем языка (#sym.dot.c (пробел), #sym.arrow.r.curve (переход на новую строку), ...);
- *ограничители* #sym.dash.em лексемы, использующиеся для группировки выражений. Например, ограничителями являются `{` `}` в _C++_ или `(` `)` в _Lisp_.

*Синтаксис* #sym.dash.em правила построения языковых конструкций. Он описывает форму, последовательность символов, которая составляет синтаксически правильную программу.

*Семантика* указывает, имеет ли смысл в контексте данного языка программирования синтаксически верная конструкция.
Семантика бывает, в частности:
- литерала: задаёт какое-то значение;
- идентификатора: обращается к динамическому окружению; если найдена связь идентификатора с некоторым значением из динамического окружения, значит под этим идентификатором скрывается значение, которое нашли; иначе #sym.dash.em семантическая ошибка;
- выражения: рассмотрим `v1 + v2`; проверяем, для каких типов определен оператор `+`. Если не нашлось оператора, принимающего объекты данных типов #sym.dash.em семантическая ошибка. Иначе подставляем результат операции вместо `v1 + v2` #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14593#p28634").

= Контейнеры
#caption[
  Что понимается под термином "Контейнер"? Какие стандартные контейнеры вы знаете? Какие средства для описания новых контейнеров существуют?
]

*Контейнер* — структура, заключающая в себе другие элементы, относящиеся к тому же или к другому типу.

== Частые контейнеры в _SML_
=== `option`
```sml
datatype 'a option = NONE | SOME of 'a
```

`NONE` является конструктором, олицетворяющим пустое значение (_ничего_), `SOME` #sym.dash.em конструктор, инкапсулирующий в точности
одно значение (_один элемент_).

```sml
val a = NONE
val b = SOME 5
(isSome a, isSome b)
(* val it = (false, true) : bool * bool *)
valOf b
(* val it = 5 : int *)
valOf a
(* uncaught exception Option *)
```

- `isSome` #sym.dash.em функция, возвращающая `true`, если аргумент является `SOME`;
- `valOf` извлекает значение из `option`. Если аргумент является `NONE`, то поднимается исключение `Option`.

=== Кортеж
Кортеж хранит в себе декартово произведение каких-то значений.
Это контейнер, хранящий ровно $n$ элементов любых типов.
```sml
val p = (5, 2.5)
#1 p
(* val it = 5 : int *)
#2 p
(* val it = 2.5 : real *)
```

=== Список
```sml
datatype 'a list = nil | :: of 'a * 'a list
```
Список #sym.dash.em контейнер, который может в любой момент времени хранить $>= 0$ элементов. В частности, в _SML_ все элементы списка должны быть одного типа.
```sml
val l1 = [1, 2, 3]
val l2 = l1 @ [3, 4]
hd l1
(* val it = 1 : int *)
tl l1
(* val it = [2,3] : int list *)
```

=== Запись
Запись #sym.dash.em набор в точности из $n$ полей, у каждого из которых есть имя и тип #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14594#p28695").
```sml
val z = {name = "Anna", age = 25};
(* val z = {age=25,name="Anna"} : {age:int, name:string} *)
#name z
(* "Anna" : string *)
```

= Классы в Haskell
#caption[
  Классы в _Haskell_. Что означает термин? Что может относиться к классу и что гарантирует факт такой принадлежности?
]

*Класс в _Haskell_* обозначает, что при отношении типа `A` к классу `Cl`, для типа `A` разрешены операции, описанные в классе `Cl`. К классу могут относиться любые типы, в том числе и созданные пользователем. Более точно классы в _Haskell_ называются *классами типов данных* (они же ваши `trait` в _Rust_, только с неявным преобразованием типов).

Классы типов с иерархией наследования напоминают интерфейсы в классических императивных языках программирования. Синтаксис объявления класса:
```
class <Имя класса> <типовая переменная> where
  <op1> :: <сигнатура1>
  <op2> :: <сигнатура2>
  ...
```

Эта концепция позволяет создавать математические абстракции: класс эквивалентности, порядка, предпорядка. У переменных класса существуют, так называемые, *требования* или *ограничения*:
```
instance (SomeType a, ...) => Class (Type (a, b, c, ...)) where
  op1() = ... -- определение операций, объявленных в классе, для данного типа
  op2() = ...
  op3() = ...
  ...
```
Здесь для того, чтобы `Type (a, b, c, ...)` можно было отнести к классу `Class` нужно, чтобы `a` относился к классу `SomeType`.
Это составляет необходимый функционал для обращения с полиморфными сущностями. 

*Фактом принадлежности типа к классу* является удовлетворение всем операциям класса, т.е. для того, чтобы тип `A` стал относится к классу `Cl`, для типа `A` необходимо определить все операции, описанные в классе `Cl` #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14595#p28715").

= Полиморфные типы
#caption[
  Что такое "полиморфный тип"? Каким образом можно определить полиморфный тип? Что такое "Переменная типа"?
]

*Переменная типа* #sym.dash.em переменная, вместо которой можно записать любой тип. Рассмотрим пример:
```sml
map :: (a -> b) -> [a] -> [b]
```
Здесь вместо переменной `a` можно подставить любой тип: `Int`, `Double`, `Bool`, `String`. При этом одинаковые типовые переменные означают, что при передаче аргументов в функцию на этих местах должны быть одинаковые типы. `(a -> b)` #sym.dash.em тип, обозначающий сигнатуру функции.

При объявлении типа в _Haskell_ используется следующий синтаксис:
```hs
data MyType <переменные типа> = ... -- Конструктор типа #1
                              | ... -- Конструктор типа #2
                              | ... -- ...
```
Блок переменных типа необязателен. Но если таковые будут указаны, то новый тип станет *полиморфным*. Полиморфизм типа заключается в том, что его экземпляры могут создаться по-разному в зависимости от того, какие типы были у аргументов конструктора. Пример:
```hs
data MyList a = Cons (a, MyList a)
              | Null
```
В данном случае объявляется тип (список), аргументом которого является типовая переменная `a`. Это значит, что вместо неё может быть абсолютно любой тип #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14596#p28716"). При этом вторым элементом в конструкторе `Cons` обязан быть экземпляр `MyList a`:
- либо `Null`;
- либо `Cons a`, где `a` #sym.dash.em тип данных элементов списка.

= Статическое окружение
#caption[
  Статическое окружение. Что это такое? Каков порядок его формирования? Время жизни?
]

*Статическое окружение* (*лексическое окружение*) #sym.dash.em окружение, в котором метса, где может использоваться переменная, определяются лексической структурой программы.

Статическое окружение *формируется на стадии компиляции* программы. В результате в программе пропадает необходимость в именах переменных, так как на каждом этапе выполнения программы точно известно, к какой переменной будет производиться обращение.

*Порядок формирования:* статическое окружение формируется в порядке физического расположения кода (наверное, можно сказать, построчно), в отличие от динамического окружения, которое формируется по ходу выполения программы.

Отсюда следует, что такое окружение "*живёт*" до тех пор, пока программа не будет скомпилирована.

= Формы результата вычислений на Haskell
#caption[
  В каких формах может быть представлено значение выражения на _Haskell_? Какой смысл каждой из таких форм?
]

Выражение на _Haskell_ может быть представлено в четырех формах:
+ *Нормальная форма* (НФ) #sym.dash.em полностью вычисленное выражение. Например, выражение `8` (обычная константа) полностью вычислено.
+ *Дно* (#sym.bot) #sym.dash.em выражение невычислимо. Например, бессмысленная бесконечная рекурсия вида `rec x = rec x` является примером дна.
+ *Невычисленное выражение* (thunk) #sym.dash.em обещание вычислить выражение. Это форма выражения, которое не использовалось в вычислениях и ещё не было вычислено. Изначально (до участия в вычислениях) к этому типу относится любое выражение, не являющееся константой.
+ *Слабая головная нормальная форма* (СГНФ) #sym.dash.em выражение частично вычислено до вызова каких-то конструкторов, параметрами которых могут быть выражения в НФ, thunk или СГНФ. Это выражения, которые были вычислены до определённого момента, а остальная часть выражения не требовалась, поэтому она может оставаться в форме thunk. Пример #sym.dash.em вычисление первых $n$ членов бесконечной последовательности #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14599#p28639"): ```hs
nat = 1 : map (+1) nat
take n l =
if n = 0 then []
else head l : take (n - 1) (tail l)
take 5 nat -- nat окажется в СГНФ, поскольку будут вычислены
           -- только первые 5 элементов массива nat
```

= Каррированные функции
#caption[
  Каррированные функции. Что это? О чем это? В чем отличия коррированной функции от некаррированной.
]

*Каррированная функция* #sym.dash.em это функция $n >= 1$ аргументов, результатом которой является функция от $n - 1$ оставшихся аргументов.

Рассмотрим пример на _SML_. Рассмотрим функцию `f1` с сигнатурой ```_sml_ ('a * 'b * 'c) -> 'd```:
```sml
fun f1 (x, y, z) = x + y + z
```
С точки зрения языка это функция одной переменной #sym.dash.em кортежа из трёх элементов.

Ту же функцию можно объявить в каррированной форме:
```sml
fun f2 x y z = x + y + z
```
Сигнатура тогда будет ```_sml_ 'a -> ('b -> ('c -> 'd))```.

*Отличие* каррированной функции будет проявляться при ее вызове. Можно передавать не все аргументы. Тогда значения переданных параметров "сохранятся" до вычисления итогового результата (они запишутся в замыкание, возвращаемое каррированной функцией). Если попытаться передать не все параметры некаррированной функции, получится ошибка несоответствия типов кортежей #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14600#p28624").

= Полиморфные функции
#caption[
  Что такое полиморфная функция. Способы определения полиморфных функций. В чем отличие полиморфной функции от перегруженной?
]

*Полиморфная функция* #sym.dash.em функция, способная между различными своими вызовами принимать и возвращать значения многих типов.

В _SML_ есть два способа *определения полиморфной функции*:
+ Пользуясь переменными типа (`'a`, `'b`, ...). Статическая система типизации, при отсутствии ограничений, по умолчанию всем аргументам и возвращаемым значениям присваивает наиболее широкий полиморфный тип: ```sml
fun f1 x = x
(* val f1 = fn : 'a -> 'a *)
```
+ Используя по отношению к аргументам другие полиморфные функции. В этом случае система неявной типизации может додумать как наиболее широкий тип (`'a`, `'b`, ...), так и наложить возможные ограничения на полиморфный тип (всё равно оставив его полиморфным): ```sml
fun f2 xs = length xs + 1
(* val f2 = fn : 'a list -> int *)
```

#grid(
  columns: (1fr, 1fr),
  column-gutter: 2em,
  [
    *В полиморфизме* функция обобщена для работы с разными типами данных. Типы определяются динамически в процессе выполнения программы. Типы аргументов и возвращаемого значения могут быть переменными (типовыми переменными), а не конкретными.
  ],
  [
    *В перегрузке* функции могут иметь одинаковые имена, но различные сигнатуры (типы аргументов и возвращаемого значения). Решение, какую функцию вызывать, принимается на этапе компиляции или во время разрешения ссылок.
  ],
)

= Механизм вывода типов
#caption[
  Алгоритм Хиндли#(sym.dash.en)Милнера. Как работает механизм вывода  типов? В чем его достоинства и недостатки?
]

*Алгоритм Хиндли#(sym.dash.en)Милнера* #sym.dash.em это алгоритм для вывода типов значений на основании того, как они используются. Буквально, он формализует интуитивное представление о том, что тип может быть выведен из поддерживаемых им операций.

*Вывод типов* #sym.dash.em возможность компилятора самостоятельно вывести тип значения у выражения. Впервые механизм вывода типов был представлен в языке _ML_, где компилятор всегда выводит наиболее общий полиморфный тип для всякого выражения.

Компилятор _ML_ сам определяет тип данных из контекста, удовлетворяя поставленным ограничениям. Он восстанавливает пропущенную информацию о типах наименее строгим путем.

== Пример 1

```sml
fun f x =
  let
    val (y, z) = x
  in
    (sqrt y) + z
  end

f : T1 -> T2 (* f должна быть функцией; все функции принимают один аргумент *)
x : T1
y : T3
z : T4

T1 : (T3 * T4) (* аргумент х должен соответствовать шаблону (y, z) *)
T3 : real (* sqrt имеет тип real -> real *)
T4 : real (* потому что мы складываем z с real *)

T1 : (real * real)
T2 : real
```

В итоге, функция `f` имеет сигнатуру ```_sml_ (real * real) -> real```.

По умолчанию операции `>`, `<`, `+`, `-`, `*` приводят к тому, что аргументы определяются как целочисленные, но если эти же аргументы встречаются в выражении с операцией `/`, то тип определяется как вещественный.

== Пример 2

При определении функции по шаблонам тип данных, возвращаемый функцией, как и в примерах выше, определяется по наиболее общему полиморфному типу выражения, находящегося в каком-либо шаблоне функции:
```sml
fun g (x, y, 0) = x + y
  | g (x, y, z) = x / y

g : T1 * T2 * T3 -> T4
x : T1
y : T2
z : T3
```

Так как при определении первого шаблона функции на месте третьего аргумента стоит `0`,
```sml
T3 : int
```

Выражение `x + y` в этом же шаблоне по умолчанию относятся к типу `int`. Но так как в следующем определении шаблона вычисляется выражение `x / y`, аргументы которого относятся к типу `real` (и результат имеет тип `real`), который является менее общим, то этот тип и будет являться возвращаемым.

В итоге:
```sml
T1 : real
T2 : real
T4 : real
```
И функция `g` будет иметь сигнатуру ```_sml_ (real * real * int) -> real```.

== Пример 3
```sml
fun h (x, y) = if x = y then 1 else 0

h : T1 * T2 -> T3
x : T1
y : T2

T3 : int (* функция возвращает либо 1, либо 0, что является значением типа int *)
```
В теле функции используется выражение, сравнивающее `x` и `y` на равенство, поэтому `x` и `y` могут быть любого типа данных, допускающего операцию *полиморфного равенства* (обозначается `''a`).

Таким образом:
```sml
T1 : ''a
T2 : ''a
```
И `h` будет иметь сигнатуру ```_sml_ ''a * ''a -> int``` #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14602#p28696").

= Двумерный синтаксис
#caption[
  Что это такое? В чем отличия двумерного синтаксиса от одномерного?
]

*Двумерный синтаксис* #sym.dash.em синтаксис, управляющими конструкциями которого являются отступы. Это значит, что на семантическое значение влияет не только то, в каком порядке слева направо написан код, но также и то, как это расположено относительно друг друга в вертикальной плоскости (на одном отступе или разных) #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14603#p28640").

Отступ в двумерном синтаксисе означает, что конструкция, начатая на предыдущей строке, продолжена на данной.

На практике одномерный синтаксис означает, что любую программу можно написать в одну строку.

= Модули
#caption[
  Что такое модуль. В чем преимущество модульного программирования? Как определяются модули на _Standard ML_.
]

Когда размер программы достигает нескольких тысяч строк, возникают следующие проблемы:
+ Рассмотрение программы как единого набора подпрограмм не обеспечивает хорошего уровня организации программы и управления ею.
+ Для больших программ продолжительность повторной компиляции становится значительной.

Решить эти проблемы можно, разделив программу на модули #sym.dash.em синтаксические контейнеры, содержащие группы логически связанных подпрограмм и данных.

Свойство *функциональной законченности* каждого модуля позволяет абстрагироваться от деталей реализации и проще понимать программу, а отсутствие необходимости повторной компиляции уже скомпилированного модуля решает оставшуюся проблему.

*Модуль* #sym.dash.em это последовательность логически связанных функционально законченных фрагментов, оформленных как отдельная часть программы.

*Назначение модульного программирования* #sym.dash.em скрытие реализации и определение области видимости переменных для пользователя.
Различают интерфейсную (подпространство пространства имён, доступное пользователю) и инкапсулированную части модуля.

*Преимущества модульного программирования*:
- упрощение групповой разработки программы;
- возможность корректировки модуля без затрагивания остальной системы;
- уменьшение времени перекомпиляции при внесении изменений;
- уменьшение объема занимаемой памяти программы за счет сокращения количества повторений кода;

Определение модулей на _SML_: #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14604#p28698")
```sml
signature TM = sig
  val h : int -> int
  val f1 : int -> int -> int
  val f2 : int -> real -> real
end

(* : не скрывает от пользователя объявления, не входящие в определение сигнатуры *)
(* :> скрывает *)
structure M : TM = struct
  fun h x = x * x + 25
  fun f1 x y = h x * h (3 * y)
  fun f2 x y = real (h x) + y
end
```

= Ленивые и энергичные вычисления
#caption[
  В чем заключается механизм ленивых вычислений? Отличия аппарата ленивых и энергичных вычислений.
]

*При ленивых вычислениях* (например, в _Haskell_) выражение не вычисляется, пока оно не понадобится.

*При энергичных вычислениях* (например, в _Lisp_) происходит вычисление всех выражений до тех пор пока они не будут вычислены полностью.

Ленивые вычисления позволяют создавать бесконечные последовательности и работать с ними, например:
```hs
nat = 1 : map (1+) nat
main = print (take 5 nat)
```
В языках с энергичными вычислениями придётся самостоятельно откладывать вычисления элементов бесконечной последовательности с помощью лямбда-функций.

= Мемоизация
#caption[
  Что такое мемоизация. Для чего она применяется?
]

*Мемоизация* #sym.dash.em это техника оптимизации, которая заключается в сохранении результатов выполнения метода для заданных входных данных и возврате сохраненного результата при повторном вызове метода с теми же входными данными. Это позволяет избежать повторных вычислений и улучшить производительность.

*Мемоизация применяется* для общего ускорения исполнения программы, оптимизации рекурсивных функций.

Пример на _Ruby_ #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14607#p28638"):
```rb
class Fibonacci
  def initialize
    @memo = {}
  end

  def fib(n)
    return n unless n > 1
    return @memo[n] if @memo.key?(n) # проверяем, есть ли результат в кэше
    result = fib(n - 1) + fib(n - 2) # если результат не найден, вычисляем его рекурсивно
    @memo[n] = result # сохраняем результат в кэше для последующих вызовов
    result
  end
end
```

= Способы передачи параметров
#caption[
  Передача параметров по ссылке и по значению.
]

В случае передачи параметров *по значению* значение переменной копируется в параметр функции. Изменения внутри функции не влияют на первоначальное значение.

При передаче параметра *по ссылке* функция получает доступ к оригинальному значению переменной, и изменения внутри функции отражаются на этом значении.

#que *Пример*

= Перегрузка функций. Динамическая диспетчеризация <dynamic-disp>
#caption[
  Перегрузка функций в привязке к объектно-ориентированному программированию на примере _Ruby_. Динамическая диспетчеризация.
]

В _Ruby_ нет *перегрузки функций*. Но есть другой механизм, не уступающий по возможностям перегрузке, и позволяющий писать более "правильный" с точки зрения ООП код.

*Динамическая диспетчеризация* означает выбор конкретной реализации метода во время выполнения программы в зависимости от типа объекта, к которому применяется этот метод.

Пример динамической диспетчеризации на _Ruby_:
```rb
# родительский класс
class Animal
  def speak
    puts "Animal speaks"
  end
end

# дочерний класс
class Dog < Animal
  def speak
    puts "Woof"
  end
end

# дочерний класс
class Cat < Animal
  def speak
    puts "Meow"
  end
end

# динамическая диспетчеризация
animals = [Animal.new, Dog.new, Cat.new]

animals.each do |animal|
  animal.speak
end
```

Для нас не имеет значения, к какому классу относится каждый из элементов списка, до тех пор, пока у них есть метод `speak`, принимающий $0$ обязательных параметров. _Ruby_ во время исполнения сам определит тип каджого объекта и вызовет соответствующую реализацию метода.

= Макросы
#caption[
  Что это? Как описать макрос? Протечки макросов.
]

*Макросы* это инструмент генерации и преобразования исходного текста программы. В _Lisp_, в частности, макросы позволяют генерировать и преобразовывать код во время препроцессинга.

Макрос в _Lisp_ определяется с помощью ключевого слова `defmacro`. Оно принимает список аргументов и тело макроса #sym.dash.em неявный список.

Пример создания макроса в _Lisp_:
```lisp
(defmacro double (x) `(* 2 ,x))
```

При написании макроса нужно следить за следующими *протечками*:
#enum(tight: false)[
  Поскольку макрос #sym.dash.em просто текстовые замены, нужно предусмотреть копирование одного и того же выражения в разные места программы.
  ```lisp
  (defmacro cube (x) `(* ,x ,x ,x)) # плохо

  (defmacro cube (x) # плохо, но лучше
    `(let (a ,x)
      (* a a a)))
  ```
][
  Другая проблема макроса: оперирование локальными именами. Что, если они совпадут с именами окружения?
  ```lisp
  (defmacro cube (x) # хорошо
    (let ((a (gensym)))
      `(let (,a ,x)
         (* ,a ,a ,a))))
  ```
][
  Порядок вычисления выражений, переданных в качестве аргументов макросу. (Только при наличии побочных эффектов.) Чтобы избежать проблем, принято считать (и разработчикам, и пользователям макросов), что все аргументы макроса вычисляются слева направо в порядке появления в списке аругментов.
]

= Статическая и динамическая типизация
#caption[
  Статическая и динамическая типизация. Определение. Примеры языков. Отличия.
]

*Статическая типизация* #sym.dash.em вид типизации, при котором переменная, параметр подпрограммы или возвращаемое значение функции связывается с типом в момент объявления, и тип не может быть изменён позже (переменная или параметр будут принимать только значения заданного типа, функция #sym.dash.em возвращать значения только заданного типа).

*Язык программирования со статической типизацией* #sym.dash.em это язык, в котором происходит предварительный анализ типов данных сущностей перед выполнением программы.

Если при компиляции все проверки на соответствие типов пройдены, и программа выполняется корректно, то статическое окружение больше не нужно, и далее используется динамическое окружение.

При *динамической типизации* переменная может изменять тип хранимого значения во время выполнения. Обычно это достигается путём хранения не просто значения, а пары: `[дескриптор типа, значение]`, благодаря чему интерпретатор может отслеживать изменения всех типов во время выполнения.

Языки со статической типизацией: _C/C++_, _Java_, _SML_, _Haskell_, #text(fill: rgb("#ee7777"))[_Rust_].

Языки с динамической типизацией: _Lisp_, _Python_, _Ruby_, _JavaScript_ #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14618#p28633").

= Лексическое и динамическое связывание
#caption[
  Лексическое и динамическое связывание. Что это? В чем отличия?
]

При *лексическом связывании* локальная область видимости функции ограничена текстом определения этой функции (имя переменной имеет значение внутри тела функции и считается неопределённым за его пределами).

При *динамическом связывании* локальная область видимости ограничена временем исполнения функции (имя доступно, пока функция выполняется, и исчезает, когда функция возвращает управление вызвавшему её коду).

Рассмотрим пример на _SML_:
```sml
val x = 5
fun f x =
  let
    x = 3
  in
    g x
  end
fun g x = print (Int.toString x)
```
Если бы в _SML_ было динамическое связывание, то при вызове функции `f` и передаче управления `g` в ней значение `x` было бы равно `3`, поскольку локальные значения функции `f` распространялись бы на функцию `g`. Однако, так как связывание лексическое, значение `x` для функции `g` берётся из глобальной переменной `x = 5` (поскольку `g` не входит в лексическую область выполнения функции `f`). В этом заключается различие типов связывания #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14619#p28628").

= Наследование
#caption[
  Наследование на примере _Ruby_.
]

*Наследование* #sym.dash.em это инструмент, позволяющий описать новый класс на основе уже существующего с частично или полностью заимствованной функциональностью.

Чтобы не повторяться, пример наследования на _Ruby_ есть в @dynamic-disp.

= Шаблоны (образцы)
#caption[
  Что такое шаблон с точки зрения программиста на Standard ML и Haskell? В чем заключается механизм сопоставления с образцом? Какие средства для работы с шаблонами вы знаете? 
]

В любом месте, где происходит связывание значения с именем, вместо имени можно использовать шаблон #sym.dash.em разложение данных по конструктору и присвоение новым именам. Тогда, если правая часть связывания сконструирована при помощи тех же конструкторов данных, именам будут присвоены значения соответствующих компонент правой части связывания. В качестве шаблона может быть использован символ `_` (джокер) или идентификатор, начинающийся на символ `_`. Тогда соответствующее место в шаблоне будет проигнорировано #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14608#p28697").

== _SML_
```sml
fun myFoldl (l, start, f) =
  case l
    of [] => start
     | x :: xs => myFoldl (xs, f (x, start), f)

(* или *)

fun myFoldl ([], start, _) = start
  | myFoldl (x :: xs, start, f) = myFoldl (xs, f (x, start), f)
```

== _Haskell_
```hs
myFoldl ([], start, _) = start
myFoldl (x : xs, start, f) = myFoldl (xs, f (x, start), f)
```

= Идентификаторы #sym.dash.em объекты первого класса
#caption[
  Идентификаторы #sym.dash.em объекты первого класса: что это значит? Продемонстрировать на примерах.
]

В некоторых языках (_Lisp_, _Ruby_) идентификаторы являются объектами 1-го класса. Это означает, что для них справедливы утверждения, упомянутые в @first-class-citizens.

Идентификаторы в _Ruby_ начинаются с символа `:`. Например, `:apple`.

В _Lisp_ идентификаторы получаются в результате вызова функции `quote` или более короткой записи: `'`. Например, `'apple`.

= Исключения
#caption[
  Стандартные исключения. Описание собственных исключений. Поднятие исключения. "Перехват" исключения. 
]

*Исключение* #sym.dash.em специальный объект, который поднимается (выбрасывается), когда фрагмент программного кода сталкивается с проблемой, которая на данном уровне не может быть разрешена самостоятельно. Исключение сигнализирует вызывающей функции о том, что принимать решение о дальшейшем ходе программы предстоит ей.

*Стандартные исключения* во многих языках программирования: целочисленное деление на $0$, выход за границы массива, или просто ошибка времени исполнения.

Часто пользователь может определить собственные исключения, инкапсулирующую дополнительную информацию или измененный текст сообщения.

Вызываемая подпрограмма имеет возможность "*поднять*" исключение, в то время как подпрограммы ниже по стеку вызовов могут его "*перехватить*" и обработать соответствующе.

= Отражения
#caption[
  Отражения (reflections) на примере _Ruby_.
]

*Отражения* #sym.dash.em инструменты языка, позволяющие получать динамическую информацию о среде исполнения и об объектах самого языка.

Пример:
```rb
a = "abc"
a.class # String
a.class.superclass # Object
a.class.superclass.superclass # BasicObject
```

= Парадигмы программирования
#caption[
  Императивное и декларативное программирование. Функциональное, логическое, параллельное и объектно-ориентированное программирование. Факультативно: модульное программирование; событийно-ориентированное программирование.
]
Там все расписано: #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14615#p28664").

= Инкапсуляция. Модификаторы доступа к элементам объекта
#caption[
  Инкапсуляция. Модификаторы доступа к элементам объекта.
]

*Инкапсуляция* #sym.dash.em это принцип, согласно которому внутреннее представление объекта скрыто от внешнего мира, а взаимодействие с объектом осуществляется только через строго определенный интерфейс.

Методы с модификатором `public` доступны из любого места.
Все методы в классе по умолчанию являются `public`.
```rb
class MyClass
  # по умолчанию public
  def public_method
    puts "This is a public method"
  end
end
```

Методы с модификатором `private` могут быть вызваны только внутри класса
```rb
class MyClass 
  private # модификатор доступа private
  def private_method 
    puts "This is a private method" 
  end 
end.
```

Методы с модификатором `protected` могут быть вызваны только внутри класса и его подклассов.
```rb
class Parent  # родительский класс
  protected # модификатор доступа protected 
  def protected_method 
   puts "This is a protected method" 
  end 
end 

class Child < Parent # дочерний класс
  def call_protected_method 
    protected_method # наследует метод родительского класса
  end 
end
```

Для переменных объекта всё аналогично #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14616#p28636").

= Параметры функции/макроса
#caption[
  Формальные и фактические параметры. Описание параметров функции/макроса на _Lisp_.
]

*Формальный параметр* #sym.dash.em идентификатор, указываемый при объявлении или определении функции, который будет содержать передаваемое снаружи при вызове значение.

*Фактический параметр* #sym.dash.em значение, передаваемое в функцию при её вызове.

== Описание параметров функции/макроса на _Lisp_
В списке формальных параметров можно указывать ключевые слова, которые позволяют в дальнейшем трактовать параметры функции по-разному. Ключевые слова: `&optional`, `&key`, `&rest` (при определении макросов вместо него используется ключевое слово `&body`), `&aux`.

Если ключевое слово упоминается в списке формальных параметров, то оно относится ко всем параметрам, расположенным в списке после него до следующего ключевого слова или до конца списка, если такой отсутствует.

Параметры, расположенные в списке до первого ключевого слова, являются *обязательными* параметрами функции.

`&optional` указывает, что относящиеся к нему параметры являются *необязательными*, и при вызове для них можно не указывать фактические параметры. Тогда параметр связывается со значением по умолчанию, или, если оно отсутствует, со значением `nil`.

`&rest` указывает, что количество фактических параметров описываемой функции может превосходить количество формальных параметров. С формальным параметром, расположенным в списке после слова `&rest`, связывается список всех значений фактических параметров, для которых не предусмотрено формального параметра. Поэтому после `&rest` может быть только один идентификатор, и не может быть других ключевых слов.

`&key` служит для определения *ключевых параметров*. Ключевой параметр функции в _Lisp_ #sym.dash.em необязательный параметр для передачи значения, которому требуется указание соответствующего символьного ключа (ключевого слова). Символьный ключ для каждого ключевого параметра представляет имя формального параметра, перед которым поставлено двоеточие. Если при вызове функции ключевой параметр не указан, то он связывается со значением по умолчанию или, если оно отсутствует, с `nil`.

Нельзя использовать в одном списке ключевые слова `&rest` и `&key`.

`&aux` говорит, что перечисленные далее символьные имена не являются на самом деле параметрами функции, а являются её вспомогательными локальными переменными. Этим именам не могут быть сопоставлены фактические параметры. Но для них можно так же, как и для необязательных параметров, указать значения по умолчанию (начальные значения) #cred("https://course.sgu.ru/mod/forum/discuss.php?d=14621#p28632").

= Замыкание
#caption[
  Что такое замыкание? Из чего оно состоит? Когда и как формируется? Как используется?
]

*Замыкание* #sym.dash.em это результат определения функции.

*Замыкание состоит из следующих частей:*
- её определения;
- параметров функции;
- копии динамического окружения в момент её определения.

В динамическое окружение функция записывается в виде пары `[имя_функции, замыкание]`.

Например, результат объявления функции `f` в динамическом окружении:
```
(f, (f x = a * x, [(a, 3)]))
```

*Замыкание формируется* в момент определения функции в программе (про каррированные функции тоже не забываем).

*Замыкание используется для* вычисления значения вызова функции. Копия динамического окружения, сохраненного в замыкании, станет основой для временного динамического окружения, которое создастся при вызове функции. Кроме копии динамического окружения во временное окружение дописываются фактические параметры функции.
