Skip to content

Programming.md

Latest commit

 

History

History
448 lines (350 loc) · 35.9 KB

Programming.md

File metadata and controls

448 lines (350 loc) · 35.9 KB
Raw

Программирование

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

Что такое программирование

Программирование (англ. programming) — процесс создания программ: описание того, что и в каком порядке должен сделать компьютер.

Алгоритм (англ. algorithm) — конечная последовательность точных шагов, решающая задачу. Программа (англ. program) — запись алгоритма, которую может выполнить компьютер: набор инструкций на языке программирования.

Компьютер ничего не придумывает сам. Ада Лавлейс перевела статью Луиджи Менабреа (1842) об Аналитической машине Чарльза Бэббиджа и дописала к ней примечания. В примечании G она предостерегает от преувеличенных ожиданий: машина не претендует на то, чтобы что-то порождать сама, она делает то, что мы умеем ей приказать (текст). Программирование и есть умение приказывать — точно, полно и без двусмысленностей.

Приказы записывают на языке программирования (англ. programming language) — формальном языке со строгими правилами. Человек поймёт фразу с ошибкой, а компьютер — нет.

Семиотика, синтаксис и семантика

Говоря простыми словами, язык программирования - это средство коммуникации между программистом и компьютером. С помощью него программист может "рассказать" компьютеру, что нужно сделать (исполнить, выполнить) последнему.

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

Синтаксическая ошибка (англ. syntax error) — нарушение правил записи. Такую программу нельзя даже запустить:

const price = 100;
const total = price +; // SyntaxError: Unexpected token ';'

Смысловая (логическая) ошибка (англ. logic error) хитрее: программа записана правильно и работает, но делает не то, что задумано. Компьютер её не заметит.

const price = 100;
const discount = 20;
const total = price + discount; /* по смыслу нужна разность */
console.log(total); // 120 вместо 80

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

Краткая история

Идеи, на которых стоит современное программирование, появились задолго до привычных нам компьютеров. Ссылки в таблице ведут на первоисточники.

Год Событие Что изменилось
1842 Луиджи Менабреа публикует статью об Аналитической машине Бэббиджа. Позже Ада Лавлейс переводит её и дописывает примечания в последнем примечании по шагам расписано, как машина вычислила бы числа Бернулли (текст)
1936 Алан Тьюринг описывает абстрактную вычислительную машину незадолго до этого Алонзо Чёрч ввёл «эффективную вычислимость», и Тьюринг показывает, что она равносильна его «вычислимости»: появляется строгое понятие того, что вообще можно вычислить (статья Тьюринга)
1945 Джон фон Нейман, «Первый проект отчёта о EDVAC» в одной памяти хранятся и числа, и команды (англ. numbers and orders) (отчёт)
1957 Коммерческий выпуск Фортрана в IBM (создан в 1954-м, главный автор — Джон Бэкус) раньше программы писали на машинном языке — нулями и единицами, теперь — формулами: название — сокращение от formula translation. Фортран стал первым стандартом языка программирования (IBM)
1960 Джон Маккарти описывает Лисп (статья, апрель 1960) язык создан в MIT для IBM 704: программы строятся из рекурсивных функций над символьными выражениями (статья)
1960 ALGOL 60 (отчёт под редакцией Петера Наура) каждый блок вводит свой уровень имён — вложенные области видимости; синтаксис описан формально — метаязыковыми формулами (отчёт)
1966 Коррадо Бём и Джузеппе Якопини блок-схемы можно свести к трём базовым схемам: последовательности, ветвлению и циклу (статья)
1967 SIMULA 67 (Оле-Йохан Даль и Кристен Нюгор, Норвежский вычислительный центр) классы и подклассы; Алан Кэй относит Simula к ранним идеям, из которых выросло объектно-ориентированное программирование (история SIMULA, Алан Кэй)
1968 Эдсгер Дейкстра, письмо «О вреде оператора go to» (англ. Go-to statement considered harmful) go to стоит убрать из языков высокого уровня: он слишком примитивен и провоцирует запутанный код (EWD 215)
1970 Эдгар Кодд (IBM), реляционная модель данных данные — связанные таблицы, и пользователю не нужно знать, как они хранятся (статья, IBM). Позже в IBM Дональд Чемберлин и Рэймонд Бойс создали язык запросов SQL
1972 Язык C (Деннис Ритчи; 1969–1973, самый творческий период — 1972-й) язык для системного программирования: летом 1973-го на нём переписали ядро Unix (история C)
1972 Smalltalk-72 (Алан Кэй, Xerox PARC) всё — объекты; у каждого своя память, а общаются объекты, посылая друг другу сообщения (история Smalltalk)
1972 Пролог (Ален Кольмероэ и Филипп Руссель, Марсель) логическое программирование: имя — сокращение от PROgrammation en LOGique (история Пролога)
1978 Джон Бэкус, «Можно ли освободить программирование от стиля фон Неймана?» главный автор Фортрана предлагает функциональный стиль и алгебру программ (лекция)
начало 1990-х Гвидо ван Россум создаёт Python в CWI (Нидерланды) преемник языка ABC (история Python)
1995 Брендан Эйх в Netscape в мае делает прототип будущего JavaScript под названием Mocha прототип встраивают в браузер Netscape Navigator 2.0, который тогда только разрабатывался (Брендан Эйх)

Путь от машинного языка к современным языкам — это путь абстракций. Сначала вместо нулей и единиц появились формулы (Фортран). Затем вместо произвольных переходов — ветвления и циклы (структурное программирование). Потом данные и код объединились в объекты (SIMULA, Smalltalk), а рядом выросли декларативные языки: в них описывают результат, а не шаги (Пролог, SQL).

Из чего состоит программа

Языки программирования сильно отличаются, но строительные блоки у них почти одни и те же. Примеры ниже — на JavaScript, местами для сравнения — на C.

Значения, переменные и типы

Значение (англ. value) — данные, с которыми работает программа: число 31, строка 'Max', логическое false. Переменная (англ. variable) — именованное место для значения, которое можно изменить; константа (англ. constant) — имя, которому нельзя присвоить новое значение. Тип (англ. type) определяет, какие значения допустимы и какие операции над ними разрешены.

const name = 'Max'; /* строка */
let age = 30; /* число */
const isAdmin = false; /* логическое значение */
age = age + 1; /* переменную можно изменить, константу — нет */
console.log(typeof name, typeof age, typeof isAdmin); // string number boolean

Подробно о типах — в заметке про типы данных, об объявлении переменных в JavaScript — в заметке про JavaScript.

Выражения и инструкции

Выражение (англ. expression) вычисляется в значение. Инструкция (англ. statement) выполняет действие: объявляет переменную, присваивает, ветвится, повторяет.

/* выражения: у каждого есть значение */
console.log(2 + 3 * 4, age >= 18, isAdmin ? 'да' : 'нет'); // 14 true нет

/* инструкции: выполняют действие */
let total = 0; /* объявление */
total = total + 10; /* присваивание */
if (total > 5) total = 5; /* ветвление */
console.log(total); // 5

Ветвления и циклы

Порядок выполнения задают три конструкции:

  • последовательность (англ. sequence) — инструкции выполняются одна за другой;
  • ветвление (англ. branching) — выбор одного из путей по условию: if, switch, тернарный оператор;
  • цикл (англ. loop) — повторение, пока выполняется условие: for, while.

В 1966 году Коррадо Бём и Джузеппе Якопини показали, что блок-схему можно свести к этим трём конструкциям — иногда ценой дополнительных переменных-флагов (Communications of the ACM, май 1966). В 1968-м Эдсгер Дейкстра сослался на эту работу: по ней выходит, что оператор перехода go to логически не нужен. Но механически переписывать любую схему без переходов он не советовал: понятнее она от этого не станет (EWD 215). Программирование такими конструкциями, без go to, называют структурным программированием (англ. structured programming).

const grade = (score) => {
  if (score >= 90) return 'отлично';
  if (score >= 60) return 'зачёт';
  return 'незачёт';
};

for (let i = 1; i <= 3; i++) {
  console.log(i * 40, grade(i * 40));
}
/* 40 незачёт
80 зачёт
120 отлично */

/* сколько цифр в числе */
let n = 2026;
let digits = 0;
while (n > 0) {
  n = Math.floor(n / 10);
  digits++;
}
console.log(digits); // 4

Процедуры и функции

Подпрограмма (англ. subroutine) — именованный фрагмент кода, который можно вызвать из разных мест. Подпрограммы бывают двух видов:

  • функция (англ. function) вычисляет и возвращает значение;
  • процедура (англ. procedure) выполняет действие и ничего не возвращает.

Параметры (англ. parameters) — имена в объявлении (width, height), аргументы (англ. arguments) — значения, переданные при вызове (3, 4).

В JavaScript оба вида записываются одинаково, а процедура просто возвращает undefined:

/* функция: вычисляет значение из аргументов */
const area = (width, height) => width * height;

/* процедура: выполняет действие и ничего не возвращает */
const printArea = (width, height) => {
  console.log(`Площадь: ${area(width, height)}`);
};

console.log(area(3, 4)); // 12
const result = printArea(3, 4); /* Площадь: 12 */
console.log(result); // undefined

В C процедуру отличает тип результата void:

#include <stdio.h>

int area(int width, int height) { /* функция: возвращает число */
    return width * height;
}

void print_area(int width, int height) { /* процедура: void — ничего не возвращает */
    printf("Площадь: %d\n", area(width, height));
}

int main(void) {
    print_area(3, 4); /* Площадь: 12 */
    return 0;
}

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

Рекурсия

Рекурсия (англ. recursion) — вызов подпрограммой самой себя. У рекурсии должен быть базовый случай (англ. base case), на котором она останавливается, иначе вызовы никогда не закончатся.

const factorial = (k) => (k <= 1 ? 1 : k * factorial(k - 1)); /* k <= 1 — базовый случай */
console.log(factorial(5)); // 120

Каждый вызов занимает место в стеке вызовов. Слишком глубокая рекурсия его переполняет: factorial(1e6) в Node.js падает с ошибкой RangeError: Maximum call stack size exceeded.

Составные данные

Отдельные значения объединяют в структуры:

  • Массив (англ. array) — упорядоченный набор значений, доступных по номеру (индексу).
  • Запись (англ. record), или структура (англ. struct), — набор именованных полей: в C это struct, в JavaScript — объект.
  • Словарь (англ. dictionary, map) — соответствие «ключ → значение».
const temperatures = [12, 15, 9, 20];
console.log(temperatures[0], temperatures.length); // 12 4

const point = { x: 3, y: 4 };
console.log(point.x); // 3

const prices = new Map([['margherita', 10], ['pepperoni', 12]]);
console.log(prices.get('pepperoni')); // 12

Подробнее о массивах — в заметке про JavaScript.

Одна задача в разных стилях

Стиль, в котором пишут программу, называют парадигмой программирования (англ. programming paradigm). Главное деление: императивный стиль описывает, как получить результат (шаги и изменение состояния), декларативный — что нужно получить. Подробно о парадигмах и о том, какие из них поддерживают языки, — в заметке про характеристики языков.

Разницу проще всего увидеть на одной задаче: посчитать выручку — сумму оплаченных заказов.

Процедурный стиль (C): цикл, условие и изменяемый счётчик.

#include <stdio.h>

struct Order {
    int amount;
    int paid;
};

int revenue(const struct Order orders[], int count) {
    int total = 0;
    for (int i = 0; i < count; i++) {
        if (orders[i].paid) {
            total += orders[i].amount;
        }
    }
    return total;
}

int main(void) {
    struct Order orders[] = { {100, 1}, {250, 0}, {70, 1} };
    printf("%d\n", revenue(orders, 3)); /* 170 */
    return 0;
}

Объектно-ориентированный стиль (JavaScript): данные и поведение объединены в объекты, а список заказов спрятан внутри OrderBook.

class Order {
  constructor(amount, paid) {
    this.amount = amount;
    this.paid = paid;
  }

  isPaid() {
    return this.paid;
  }
}

class OrderBook {
  #orders = []; /* приватное поле: снаружи недоступно */

  add(order) {
    this.#orders.push(order);
    return this;
  }

  revenue() {
    let total = 0;
    for (const order of this.#orders) {
      if (order.isPaid()) total += order.amount;
    }
    return total;
  }
}

const book = new OrderBook()
  .add(new Order(100, true))
  .add(new Order(250, false))
  .add(new Order(70, true));

console.log(book.revenue()); // 170

Функциональный стиль (JavaScript): цепочка преобразований без изменяемых переменных; исходный массив не меняется.

const orders = [
  { amount: 100, paid: true },
  { amount: 250, paid: false },
  { amount: 70, paid: true },
];

const revenue = (list) => list
  .filter((order) => order.paid)
  .map((order) => order.amount)
  .reduce((sum, amount) => sum + amount, 0);

console.log(revenue(orders)); // 170

Python позволяет записать то же одной строкой: генераторное выражение (англ. generator expression) читается почти как описание результата.

orders = [
    {"amount": 100, "paid": True},
    {"amount": 250, "paid": False},
    {"amount": 70, "paid": True},
]

print(sum(order["amount"] for order in orders if order["paid"]))  # 170

Декларативный стиль (SQL): запрос описывает, что нужно получить. Как именно перебрать строки — решает база данных.

CREATE TABLE orders (amount INTEGER, paid INTEGER);
INSERT INTO orders VALUES (100, 1), (250, 0), (70, 1);

SELECT SUM(amount) FROM orders WHERE paid = 1; -- 170
Стиль Как описываем решение Что с состоянием
Процедурный последовательность шагов в подпрограммах изменяется по шагам: total += ...
Объектно-ориентированный объекты с данными и поведением общаются через методы спрятано внутри объектов
Функциональный композиция функций, преобразующих данные не изменяется: каждый шаг создаёт новое значение
Декларативный описание результата скрыто: шаги выбирает система

Лучшего стиля нет. Многие современные языки — мультипарадигменные, и в одном проекте могут встретиться все четыре стиля.

Работа со строками

Конкатенация

Конкатенация (англ. concatenation) — склеивание строк в одну. В JavaScript строки склеивают оператором +, шаблонной строкой (англ. template literal) или методом массива join:

const firstName = 'Max';
const lastName = 'Starling';

console.log(firstName + ' ' + lastName); // Max Starling
console.log(`${firstName} ${lastName}`); // Max Starling
console.log([firstName, lastName].join(' ')); // Max Starling

Если хотя бы один операнд + — строка, второй тоже приводится к строке (MDN):

console.log('1' + 2); // 12
console.log(1 + 2 + '3'); // 33
/* сначала 1 + 2 = 3, затем 3 + '3' = '33' */

Подробнее о неявном преобразовании типов — в заметке про JavaScript.

Регулярные выражения

О регулярных выражениях

Регулярное выражение (англ. regular expression, regex, regexp) - это поисковый шаблон (англ. search pattern), который позволяет по заданным в нём правилам найти подстроку (некоторую последовательность символов) в некоторой строке.

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

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

Регулярное выражение позволяет задавать в шаблоне

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

Всё это мы рассмотрим далее на примерах.

Когда регулярные выражения могут быть полезны

  • при поиске: для включения удовлетворяющих шаблону строк в некоторую выборку
  • при валидации строки: проверка сложности пароля, проверка правильности введённого номера телефона или электронной почты
  • при необходимости обрабатывать строку по-разному в зависимости от того, что она содержит.

Простейшее регулярное выражение

Подобно тому, как строки обычно заключаются в одинарные, двойные или косые кавычки:

'hello'
"hi"
`welcome`

регулярные выражения размещают между двумя косыми чертами / (англ. slash):

/hey/

Это позволяет интерпретатору (компилятору) отличить регулярное выражение от других выражений.

Самым простым поисковым шаблоном является конкретная последовательность символов.

Например, выясним, какие из указанных строк содержат подстроку "ay". Регулярное выражение примет вид /ay/.

'Ray Palmer'.match(/ay/); // ['ay', index: 1] (начинается с 1-ого символа)
'Dorian Gray'.match(/ay/); // ['ay', index: 9] (начинается с 9-ого символа)
'Max Starling'.match(/ay/); // null (соответствий не найдено)

Перечисление допустимых символов

Перечисление символов

Регулярное выражение позволяет перечислить допустимые символы. Для этого используются квадратные скобки [] (англ. square brackets). Читается как "любой символ из символов ...".

Например,

  • регулярному выражению [abc] удовлетворяет каждый из символов a, b, c и никакой другой символ,
  • регулярному выражению [13579] удовлетворяют только символы 1, 3, 5, 7, 9
'May'.match(/[abc]/) // ['a', index: 1]
'#ff00ff'.match(/[0123456789]/) // ['0', index: 3]

Исключение перечисленных символов

Для исключения из регулярного выражения символов используется символ карет ^ (англ. caret) внутри квадратных скобок. Читается как "любой символ, кроме символов из интервала".

Включение символа из интервала символов

Для включения в регулярное выражение символов из некоторого интервала символов используется символ - (англ. hyphen) внутри квадратных скобок. Читается как "любой символ из интервала ...".

Например,

  • регулярное выражение /[0-9]/ соответствует любому из символов 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (то есть любой цифре),
  • регулярное выражение [A-Z] - любой большой букве латинского алфавита,
  • регулярное выражение [a-z] - любой маленькой букве латинского алфавита,
  • а выражение [А-я] - любой букве (большой или маленькой) русского алфавита, кроме Ё и ё: в Юникоде они стоят вне этого интервала, поэтому их добавляют отдельно — [А-яЁё]
'Hello'.match(/[A-Z]/) // ['H', index: 0]
'Hi'.match(/[a-z]/) // ['i', index: 1]
'Hey'.match(/[0-9]/) // null
'Greetings user2000'.match(/[0-9]/) // ['2', index: 14]

Исключение символа из интервала символов

Для исключения из регулярного выражения символов из некоторого интервала также используется символ карет ^ (англ. caret).

Например,

'Greetings user2000'.match(/[^0-9]/) // ['G', index: 0]

'15,000 dollars'.match(/[0-9]/) // ['1', index: 0]
'15,000 dollars'.match(/[^0-9]/) // [',', index: 2]

'GitHub'.match(/[^A-z]/) // null

Комбинация перечислений символов

Например, регулярное выражение [A-Za-z0-9] соответствует любой букве латинского алфавита или цифре, а регулярное выражение [^A-Za-z0-9] соответствует любому символу, который не является ни буквой латинского алфавита, ни цифрой.

"Hey! How is it going?".match(/[A-Za-z0-9.]/) // ['H', index: 0]
"Hey! How is it going?".match(/[^A-Za-z0-9]/) // ['!', index: 3]

Классы символов

Классы символов (англ. character classes) чем-то напоминают типы данных: они ограничивают область допустимых значений (в данном случае, область допустимых символов).