Учебник языка Перфо для школьников
Это заготовка для переделки под язык Перфо - учебника "Введение в Scheme для школьников".
- https://ru.wikibooks.org/wiki/Введение_в_язык_Scheme_для_школьников - Оригинал "Введение в Scheme для школьников"
- https://habr.com/ru/post/505928/ Почему функциональное программирование такое сложное - Хабр
- Исходный вариант статьи (С. И. Иевлев, «Ваш новый язык — Scheme») опубликован в двух частях в журнале «Потенциал».
Вы хорошо знаете русский, возможно, неплохо уже говорите по-английски, в школе вас научили несколько необычному языку математики. Предлагаю выучить ещё один — Лисп. Точнее, один из его самых интересных диалектов — Перфо, который является русским вариантом Scheme (Ским). Перфо не является копией Ским. Это адаптированная для практического программирования и
Содержание
Соответствие ключевых слов Ским (Scheme) и Перфо
- ; - // - комментарий, многострочный комментарий /* */ - не поддерживается
- define - перем, функция -
- перем - создаёт и изменяет переменную
- функция - создаёт функцию
- lambda - функ - создаёт анонимную (лямбда)-функцию
- read - ввод - ввод строки пользователя
- display - вывод
- write - вывод
- newline - ПС - перевод строки
- if - если - оператор ветвления ЕСЛИ
- positive? - (> переменная 0)
- string-append - - склеивание строк
- set! -
- begin - не к спискам относится, а к последовательности действий... в Перфо можно просто писать последовательность без ключевого слова begin. Например, на Scheme надо было бы написать:
(+ 3 (begin (set! y 4) y) 5)
а на Перфо будет так:
(+ 3 ((перем ф 4) ф) 5)
Перем и Уст с переменными работают похоже, пока дело не касается установки значений полей или свойств объектов, тут уже только Уст подойдет...
Перевод терминов функционального программирования
Введение в синтаксис
Сперва познакомимся с несколько необычным порядком слов этого языка: «действие — предмет». Но необычен он только в сравнении с популярными языками программирования. В русском языке такая последовательность нередка:
- Сумма трёх и пяти.
- Произведение пяти, шести и семи.
- Купи в булочной батон.
Каждая законченная фраза на этом языке должна быть окружена парой круглых скобок. Запишем сказанное выше на Перфо:
(+ 3 5) (* 5 6 7) (купить булочная батон)
Можно записать выражения и посложнее:
(купить булочная батон (+ 2 1))
«Купи в булочной батоны: два плюс ещё один». Просто, не правда ли? Давайте двигаться дальше.
Фраза (* 3 5) хороша, а (* ширина высота) — лучше.
Выражение (* 2 3.1415926 5) — интригующе, а (* 2 ЧислоПи Радиус) гораздо более осмысленно.
Здесь ширина, высота — переменные, а 3 и 5 — их текущие значения.
Переменная задаётся следующей конструкцией языка:
(Перем имя <первоначальное значение>)
Пример:
(перем ширина 3) (перем высота 7) (* 2 (+ ширина высота))
Прочитаем записанное по-человечески: «Положим ширина — это 3, высота — это 7, подсчитаем произведение двух и суммы ширины и высоты (например, периметр прямоугольника)». Результат такого вычисления в нашем случае будет 20.
Продолжим совершенствовать конструкции. Положим, нам требуется подсчитать сумму квадратов двух чисел. Это можно сделать, например, так:
(перем А 3) (перем Б 4) (+ (* А А) (* Б Б))
Что-то не так; мы обычно вместо «помножь переменную на саму себя» говорим «возведи в квадрат эту переменную», на Перфо — квадрат:
(+ (квадрат А) (квадрат Б))
«Сумма квадрата А и квадрата Б». Есть задача — есть её решение. Мы можем объявить новое слово-функцию, назвать её квадрат. Функция будет принимать в качестве параметра число и возвращать его квадрат. Делается это следующим образом:
(функция (квадрат x) (* x x))
Общий формат:
(функция (название параметр параметр …) тело_функции)
Функция возвращает последнее вычисленное значение. Это означает, что следующая функция квадрат2:
(функция (квадрат2 x) (* 2 2) (* x x))
вернёт тот же результат, что и квадрат, перед этим умножив 2 на 2 безо всякого эффекта. Перепишем пример с суммой квадратов чисел заново:
(перем А 3) (перем Б 4) (функция (квадрат x) (* x x)) (+ (квадрат А) (квадрат Б))
Нам не хватало слов в языке — мы их добавили. Вообще, когда пишете программу на Перфо, вы описываете не алгоритм, а сначала создаёте язык, а потом на нём формулируете исходную задачу. Несколько точнее — вы «подгоняете» данный вам язык Перфо до тех пор, пока он не станет совпадать с языком, на котором задача формулируется легко.
Сразу пример. Пусть перед нами стоит задача сделать программу, которая спрашивает имя пользователя, а потом выводит ему приветствие.
Перфо предоставляет нам несколько готовых «глаголов»:
-
ввод - для чтения имени,
-
вывод - вывод чего-то на дисплее,
-
ПС - вывод перевода строки.
Мы бы хотели иметь такие «глаголы»:
-
привет - для приветствия с одним параметром — именем пользователя;
-
пользователь - для получения имени пользователя, без параметров.
Наша задача выглядела бы так:
(привет (пользователь))
Дело за малым — определить привет и пользователь. Нет проблем. Вот полный текст программы.
(функция (привет имя) // (вывод "Привет, ") (вывод имя) (вывод "!") (ПС)) (функция (пользователь) (вывод "Представьтесь:") (ввод)) (привет (пользователь))
Перфо — полноценный функциональный язык, а поэтому функции — полноправные члены этого языка, независимо от того, определили вы их сами, или они уже были в языке готовые. В частности, их можно передавать в качестве параметров в другие функции, а там уже делать с ними всё, что потребуется.
Операция унарный минус
(-) "минус" - Перфо тоже функция/глагол. Если её применить к значению (- 3) или (- ЛюбоеЧисло) то знак поменяется на противоположный. Математическим аналогом является умножение на -1. Операция унарный плюс возможна но не имеет смысла как умножение на +1.
(Вывод "Отрицательное число -3 = " -3 ПС) (Вывод "Операция унарный минус (- 3) = " (- 3) ПС) (Вывод "Операция унарный минус (- -3) = " (- -3) ПС)
Ветвление программы - оператор если
Например, функцию «модуль числа» можно определить так:
(функция (модуль ф)
(если (> ф 0)
ф
(- ф)
)
)
«Определим, что функция модуль возвращает свой аргумент, если он положителен, иначе — -ф». А можно и так:
(функция (модуль ф) // писание функции Модуль с параметром Ф
// результат выполнения функции - знак (+) или (-) который применяется к переменной Ф
((если (> ф 0) + -) ф) // Если ф>0 то возвращает знак (+) иначе возвращает знак (-)
// знаки + и - на самом деле функции которые применяются к переменным или числам
// поэтому результат выполнения функции Модуль - одна из 2-х функций + или -
// в зависимости от значения Ф
)
«…если аргумент положителен, то плюс, иначе минус ф». Здесь в результате исполнения выражения если возвращается функция + или -, которая затем применяется к аргументу ф. Полагаю, что смысл конструкции если вам сразу ясен. Сначала проверяется первый аргумент, если он истинен, то исполняется второй аргумент, иначе третий. Общий формат таков:
(если условие <действие, если условие выполняется> <действие в противном случае>)
Где посмотреть и попробовать
В теории всё хорошо, а где немного попрактиковаться? Пеобходимо скачать среду языка Пефолента.NET 0.46+, в ней выбрать Файл - "Создать программа на языке Перфо..."
Кот в мешке
Простота Перфо (Лисп, Scheme ) обманчива. На самом деле — это один из самых мощных на сегодняшний день языков программирования. На основе этого языка можно изучить все известные стили и методы программирования. С частью этих приёмов мы познакомимся с вами в следующих статьях этой серии.
Упражнение
Посмотрите следующие две реализации функции вычисления факториала (т.е. умножаются все числа от 1 до N)
f(N) = 1 * 2 * N
Одна из них основана на рекурсии - это когда функция (или кусок кода) вызывает сама себя, а другая – на итерациях - это когда кусок кода повторяется несколько раз в цикле.
Напишите на Перфо рекурсивную (вызывающую саму себя) и основанную на итерациях (повторении) реализации функции возведения в степень N числа А
f(А, N) = A^N.
Вариант 1. Рекурсия - функция вызывает сама себя
(функция (факториал ф) // функция Факториал с параметром Ф
(если (= ф 0) // если a = 0
1 // то функция возвращает в то место в коде откуда её вызвали 1
(* ф (факториал (- ф 1) ) ) // умножается значение Ф на значение возвращаемое
// (факториал (- ф 1) ) - с параметром Ф-1 (на единицу меньше)
// т.е. внутри функции факториал вызывается функция факториал
// с другим (на единицу меньше) параметром!!
)
)
Вариант 2. Повторение (Итерация)
Вычисление факториала методом повторения (итерации):
(функция (факториал-повторением результат счётчик) // определение функции Факториал-повторением
(если (= счётчик 0)
результат
(факториал-повторением (* счётчик результат)
(- счётчик 1))))
(функция (факториал Число) (факториал-повторением 1 Число)) // описание функции Факториал которая использует функцию факториал-повторением
// использование функции Факториал
(Вывод "Факториал 6: " (факториал 6)) // вывод " Факториал 6:" + результат работы функции "Факториал" с параметром 6
//(которая сама вызывает другую функцию факториал-повторением )
Повторение – мать учения
Приведём небольшую шпаргалку по базовым конструкциям Перфо.
Базовый синтаксис:
(<функция> <аргумент> <аргумент> …) // комментарий
Например:
(+ 1 2 3 4) // сумма первых 4-х натуральных чисел (+ (+ 1 2) 5 6) // возможно вкладывать одни вызовы функций в другие (+ "Привет" "Мир") // результат — склеенная строка "ПриветМир"
Присвоить значение переменной:
(перем <имя> <значение>)
Объявление Функции:
(функция (<имя> <параметр1> … <параметрН>) <тело функции>)
Функция возвращает значение последнего вычисленного выражения в теле функции
Например:
(перем А 3) // создаётся переменная А = 3 (перем Б 4) // создаётся переменная Б = 4 (функция (квадрат П) (* П П)) // описывается функция которая вычисляет квадрат числа переданного в параметр П // результат = 16 (функция (+А Б) (+ Б А)) // да-да, можно давать и такие имена функциям (любое символьное выражение) // результат = 7
Дополнительные конструкции:
(если <условие> <действие при успехе условия> <действие при неудаче>) (begin <первое действие> <второе действие> …)
Пример:
(если (> a 0)
(вывод "a > 0")) // действие при неудаче можно не указывать
(begin (вывод 1)
(вывод 2)
(вывод 3)) // последовательно выполнятся действия, и на экран будет выведено: 123
И опять про повторение: функция повторить
Ну вот, теперь можно продолжать двигаться дальше. Если вам надо выполнить какое-то действие 1 раз, то вы просто его делаете 1 раз:
(Вывод "Привет")
Если вам надо выполнить какое-то действие 2 раза, то вы просто повторяете его:
(Вывод "Привет") (Вывод "Привет")
А что, если вам нужно повторять работу снова и снова? Тогда мы сделаем функцию, которая будет повторяться требуемое количество раз. Называться эта функция будет повторить, и у неё будет один параметр — количество повторов. Алгоритм следующий:
Если количество повторов больше нуля, то:
1. выполняем действие
2. Вызываем функцию repeat с количеством повторов меньшим на 1
(функция (повторить ЧислоПовторов)
(если (> ЧислоПовторов 0) // если количество повторов не нулевое
(begin (вывод "Привет") // выполняем действие
(повторить(- ЧислоПовторов 1))))) // повторим действие на единицу меньшее количество раз.
// проверим функцию Повторить
(повторить 5)
Упражнение 1
Попробуйте написать функцию, которая будет выводить на экран цифру 1 заданное количество раз.
Упражнение 2
Попробуйте написать функцию, которая будет выводить на экран натуральные числа от 1 до заданного числа. Порядок вывода чисел не важен.
Самое время вспомнить, что в Перфо можно передавать функцию в качестве параметра. Усовершенствуем функцию повторить так, чтобы мы смогли повторять произвольные действия заданное количество раз. Пусть новая версия принимает 2 параметра:
- первый параметр — количество повторов,
- второй параметр — функция, которую надо запустить.
(функция(повторить ЧислоПовторов ВызываемаяФункция) // описание функции Повторить
(если (> ЧислоПовторов 0)
( (ВызываемаяФункция)
(повторить (- ЧислоПовторов 1) ВызываемаяФункция))))
(функция (Вывести-Один) (вывод "1")) // описание функции Вывести-Один (функция (Вывести-Привет) (вывод "Привет")) // описание функции Вывести-Привет // Начало исполнения (повторить 5 Вывести-Один) // 3 раза выведет на экран "1", используемая функция Вывести-Один (вывод ПС) // Перевод строки (повторить 5 Вывести-Привет) // 5 раз выведет на экран "Привет", используемая функция Вывести-Привет
Принцип наименьших усилий. Анонимные (лямбда)-функции
Не надо делать лишних действий, если их можно избежать. Последний вариант функции repeat хорош, но… зачем каждый раз давать функции имя, если нужно просто её выполнить? А можно ли вообще создать функцию, но не давать ей имя? Оказывается можно. В языке есть специальная инструкция, которая говорит «создать функцию».
(функ (<аргументы>) <тело функции> <последнее вычисленное значение возвращается>)
Пример:
(функ (ф) (* ф ф)) // создать функцию, которая вычисляет квадрат числа (функ (ф ч) (+ ф ч)) // создать функцию, которая вычисляет сумму двух чисел (перем квадрат (функ (ф) (* ф ф))) // создать лямбда-функцию с переменой Ф. // ссылка на функцию присваивается ПЕРЕМЕННОЙ "квадрат". // При использовании переменной "квадрат" числа 100, это число обрабатывается // функцией которая была присвоена переменной "квадрат" // этой переменной можно присвоить другую функцию, и следующее число будет обработано другой функцией (Вывод "Квадрат = " (квадрат 100) ПС)
Оказывается, последняя конструкция то же самое, что и:
(функция (квадрат ф) (* ф ф))
Вот мы с вами открыли ещё один способ определять функции с именами: сначала создаём, затем даём имя. Давайте-ка теперь «повторим» действия, не давая имена функциям:
(повторить 3 (функ() (вывод "Привет")) ) // три раза выведем на экран "Привет" (повторить 5 (функ() (вывод "1"))) // пять раз выведем на экран "1"
Для повторить используются функции без параметров, поэтому в конструкции функ пустая пара скобок.
Анонимные (Лямбда)-функции позволяют передавать и принимать в качестве параметров функции не только числа, переменные строки, но и ссылки на другие функции (а фактически куски кода) которые будут обрабатывать данные внутри вашей функции. При этом при каждом вызове функции в качестве параметра ей можно передавать другую функцию. т.е. менять не только данные которые обрабатывает функция но и часть алгоритма по которому эти данные обрабатываются.
Представьте, что у вас есть функция, которая может строить графики и принимает в качестве параметров начало и конец интервала, а так же функцию график которой необходимо построить. Если вы передадите туда функцию Квадрат, то получите график параболы, а если передадите функцию Куб, то получите график гиперболы.
Пример:
//создадим две анонимных функции
//и сохраним их в переменные квадрат и куб
(перем квадрат (функ (ф) (* ф ф)))
(перем куб (функ (ф) (* ф ф ф)))
//создадим функцию для построения графика
(функция (график НачИнтервала КонИнтервала ФункцияГрафика)
(Для (Инд НачИнтервала КонИнтервала)
(Вывод "х=" Инд " у=" (ФункцияГрафика Инд) "; ")
)
(Вывод пс)
)
//строим график функции квадрат
(график 1 4 квадрат)
//строим график функции куб
(график -3 3 куб)
Списки
Проведём следующую работу:
(перем А 1) (перем Б 2) (перем В 3) (+ А 1) (+ Б 1) (+ В 1)
А как бы нам сразу взять 3 числа и увеличить их на единицу одним махом? Для этого надо «связать» эти числа вместе. Один из способов склеивания — список. Создаётся список следующей конструкцией:
(list <элемент1> <элемент2> <элемент3> …)
Пример:
(define abc (list 1 1 1)) // список из трёх единиц (define lst1 (list 1 2 3)) // список из трёх разных чисел (define lst2 (list "Привет" "Мой" "Мир")) // список из строк (define lst3 (list "Привет" 1 "Мир" 3)) // список из строк и чисел (define lst4 (list (+ 1 0) 2 3)) // элементы списка можно вычислять перед его созданием
Перфо также предоставляет функцию:
(map <функция> <список>)
Эта функция возвращает список, в котором каждый элемент есть результат применения <функция> к элементу исходного списка. Пример:
(функция (ПлюсОдин ф) (+ ф 1)) // увеличивает число на единицу (map ПлюсОдин (list 1 1 1)) // возвращает список из двоек (map square (list 1 2 3)) // возвращает список из квадратов элементов, то есть 1, 4 и 9
Вспомним про анонимные (лямбда)-функции и решим задачу, которую поставили себе в начале этого раздела:
(define abc (list 1 1 1)) (map (функ(x) (+ x 1)) abc)
А можно даже и список не вводить как дополнительную переменную:
(map (функ(x) (+ x 1))
(list 1 1 1))
Упражнение 3
Пользуясь функциями write (для печати списка на экране) и map, напишите функцию, которая будет выводить на экран список, увеличенный на заданное число, например
(print-it 5 (list 1 2 3)) // выведет "(6 7 8)"
Работа со списками
А как написать функцию, которая последовательно будет перемещаться по заданному списку и выводить каждый элемент этого списка? Для этого нам надо только знать следующие инструкции:
-
(null? <список>)— проверяет, а есть ли ещё какие элементы в списке, -
(car <список>)— возвращает первый элемент списка, -
(cdr <список>)— возвращает список из всех элементов, кроме первого, а если больше ничего не осталось, то пустой список.
Пример:
(car (list 1 2 3)) ; вернёт 1 (cdr (list 1 2 3)) ; вернёт список из 2 и 3, то есть (list 2 3).
Проще говоря, функция car возвращает голову списка, а cdr — оставшийся хвост списка.
Имя функции print-list. Единственный параметр — исходный список. Алгоритм работы нашей функции следующий:
Если список не пуст, то:
1. выводим голову списка.
2. вызываем print-list для хвоста списка
(define (print-list lst)
(if (not (null? lst))
(begin (display (car lst))
(newline)
(print-list (cdr lst)))))
Поэкспериментируем в интерпретаторе: >> (print-list (list 1 2 3)) 1 2 3 > (print-list (list "a")) a
Упражнение 4
Поэкспериментируйте в интерпретаторе с функциями car, cdr и null?.
Упражнение 5
Напишите функцию, которая будет вычислять длину списка. Длина пустого списка — ноль.
Упражнение 6
Пользуясь изученными функциями car, cdr и null? напишите функцию for-each-element, которая будет применять заданную функцию к каждому элементу данного списка. Например, (for-each-element display (list 1 2 3)) должна напечатать «123». Напишите новую версию print-list, пользуясь только что созданной функцией.
Упражнение 7
Напишите функцию, которая будет принимать на вход два списка и возвращать список из попарных сумм элементов, например, команда (plus (list 1 2) (list 5 6)) должна вернуть список (6 8).
Упражнение 8
Попробуйте решить упражнение 7 с помощью функции map — правильный ответ вас сильно удивит.
См. также
- https://ru.wikibooks.org/wiki/Введение_в_язык_Scheme_для_школьников - оригинал который был переделан в учебник по Перфо
