Учебник языка Перфо для школьников — различия между версиями

Версия 10:30, 3 сентября 2020

Это заготовка для переделки под язык Перфо - учебника "Введение в 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)

Перем и Уст с переменными работают похоже, пока дело не касается установки значений полей или свойств объектов, тут уже только Уст подойдет...

Перевод терминов функционального программирования

Термины должны выбираться такими чтобы не требовать объяснения. Необходимо обращать внимание на то как называют такие понятия опытные программисты когда объясняют "на пальцах".

• монада - list - контейнер
• map() - преобразовать
• функтор - обработчик

Рабочие варианты терминов

• list - Список, контейнер
• map - Прим (применить функцию), преобразовать
• car - ПЭЛ (первый элемент), первый
• cdr - ОЭЛ (остальные элементы), остаток

Введение в синтаксис

Сперва познакомимся с несколько необычным порядком слов этого языка: «действие — предмет». Но необычен он только в сравнении с популярными языками программирования. В русском языке такая последовательность нередка:

• Сумма трёх и пяти.
• Произведение пяти, шести и семи.
• Купи в булочной батон.

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

(+ 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_для_школьников - оригинал который был переделан в учебник по Перфо

• Викиучебник «Лисп».
• Лисп, статья в Википедии.
• Scheme, статья в Википедии.
• Plt Scheme, официальная страница Plt Scheme.
• Bigloo, страничка о Bigloo.
• LispMe, официальная страница LispMe.
• Gambit-C, здесь можно скачать Gambit-C.