[ИУ9] Основы информатики

Лекция 6б. Типы данных и типизация

Типы данных ———–

Тип данных — множество значений, множество операций над ними и способ хранения в памяти компьютера (машинное представление).

Абстрактный тип данных — множество значений и множество операций над ними, т.е. способ хранения не задан.

Первая классификация типов данных:

  1. Простые — неделимые порции данных: число, символ, литера.
  2. Составные — содержащие значения других типов: cons-ячейка, список, вектор, строка.

Вторая классификация типов данных:

  1. Встроенные типы данных — уже заранее есть в языке.
  2. Пользовательские — их определяет пользователь.

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

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

Т.е. проектируем представление типа данных и набор операций. При этом не рекомендуется работать с типом данных в обход предоставленных операций.

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

Для типов данных языка Scheme обычно определены четыре вида операций:

Пользовательские типы данных часто представляют как списки, первым элементом которых является символ с именем типа, а остальные — хранимые значения.

Пример. Тип данных — круг.

(define (make-circle x y r)
  (list 'cicrle x y r))

(define (circle? c)
  (and (list? c) (equal? (car c) 'circle)))

(define (circle-center c)
  (list (cadr c) (caddr c)))       ; (cadr xs) = (car (cdr xs))

(define (circle-radius c)
  (cadddr c))

(define (circle-set-center! c p)
  (let ((x (car p))
        (y (cadr p)))
    (set-car! (cdr c) x)
    (set-car! (cddr c) y)
    c))

(define (circle-set-radius! c r)
  (set-car! (cdddr c) r)
  c)

Типизация и системы типов

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

Определение по Пирсу, система типов — разрешимый синтаксический метод доказательства отсутствия определённых поведений программы путём классификации конструкции в соответствии с видами вычисляемых значений.

Классификации систем типов:

  1. Наличие системы типов: есть/нет.
  2. Типизация статическая/динамическая.
  3. Типизация явная/неявная.
  4. Типизация сильная/слабая.

Наличие системы типов:

Статическая и динамическая типизация:

Явная и неявная типизация:

/* Язык Си, тип указывается явно */
int x = 100;

/* тип выводится компилятором */
auto x = 100;      /* int */
auto y = "abc";    /* const char * */

var x int = 100
var y = 200        /* тип выведет компилятор */

Типизация сильная/слабая: