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

Перевод под Перфо "Введение в Scheme для школьников"

* https://ru.wikibooks.org/wiki/Введение_в_язык_Scheme_для_школьников - Оригинал Введение в Scheme для школьников 

Замечания: Из-за поломки расширения подсветки синтаксиса в настройке этой вики, при попытке вставить тег подсветки синтаксиса syntaxhighlight lang="scheme"  - эта вики зависает, поэтому подсветка синтаксиса не работает и теги подсветки синтаксиса syntaxhighlight  надо удалять :( при копировании.

• Часть викиучебника «Лисп»
• Исходный вариант статьи (С. И. Иевлев, «Ваш новый язык — Scheme») опубликован в двух частях в журнале «Потенциал».

Вы хорошо знаете русский, возможно, неплохо уже говорите по-английски, в школе вас научили несколько необычному языку математики. Предлагаю выучить ещё один — Лисп. Точнее, один из его самых интересных диалектов — Scheme (Ским).

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

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

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

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

(+ 3 5)
(* 5 6 7)
(купить булочная батон)

Можно записать выражения и посложнее:

(купить булочная батон (+ 2 1))

«Купи в булочной батоны: два плюс ещё один». Просто, не правда ли? Давайте двигаться дальше. Фраза (* 3 5) хороша, а (* width height) — лучше. Выражение (* 2 3.1415926 5) — интригующе, а (* 2 pi radius) гораздо более осмысленно. Здесь width, height — переменные, а 3 и 5 — их текущие значения.

Переменная задаётся следующей конструкцией языка:

(define имя <первоначальное значение>)

Пример:

Пример:

(define width 3)

(define height 7) (* 2 (+ width height))

Прочитаем записанное по-русски: «Положим ширина — это 3, высота — это 7, подсчитаем произведение двух и суммы ширины и высоты (например, периметр прямоугольника)». Результат такого вычисления в нашем случае будет 20.

Продолжим совершенствовать конструкции. Положим, нам требуется подсчитать сумму квадратов двух чисел. Это можно сделать, например, так:

(define a 3)

(define b 4) (+ (* a a) (* b b))

Что-то не так; мы обычно вместо «помножь переменную на саму себя» говорим «возведи в квадрат эту переменную», на Скиме — square:

(+ (square a) (square b)) 

«Сумма квадрата a и квадрата b». Есть задача — есть её решение. Мы можем объявить новое слово-функцию, назвать её square. Функция будет принимать в качестве параметра число и возвращать его квадрат. Делается это следующим образом:

(define (square x) (* x x)) 

Общий формат:

(define (название параметр параметр …) тело_функции) 

Функция возвращает последнее вычисленное значение. Это означает, что следующая функция square2:

(define (square2 x) (* 2 2) (* x x)) 

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

(define a 3)

(define b 4) (define (square x) (* x x)) (+ (square a) (square b))

Нам не хватало слов в языке — мы их добавили. Вообще, когда пишете программу на Лиспе, вы описываете не алгоритм, а сначала создаёте язык, а потом на нём формулируете исходную задачу. Несколько точнее — вы «подгоняете» данный вам язык Scheme до тех пор, пока он не станет совпадать с языком, на котором задача формулируется легко.

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

Scheme предоставляет нам несколько готовых «глаголов»:

read

для чтения имени,

display

вывод чего-то на дисплее,

newline

вывод перевода строки.

Мы бы хотели иметь такие «глаголы»:

привет

для приветствия с одним параметром — именем пользователя;

пользователь

для получения имени пользователя, без параметров.

Наша задача выглядела бы так:

(привет (пользователь)) 

Дело за малым — определить привет и пользователь. Нет проблем. Вот полный текст программы.

(define (привет имя)
 (display "Привет, ")
 (display имя)
 (display "!")
 (newline))

(define (пользователь)

 (write "Представьтесь:")
 (read))

(привет (пользователь))

Лисп — полноценный функциональный язык, а поэтому функции — полноправные члены этого языка, независимо от того, определили вы их сами, или они уже были в языке готовые. В частности, их можно передавать в качестве параметров в другие функции, а там уже делать с ними всё, что потребуется. Например, функцию «модуль числа» можно определить так:

(define (abs x)
 (if (positive? x )
      x
     (- x))) 

«Определим, что функция abs возвращает свой аргумент, если он положителен, иначе — -x». А можно и так:

(define (abs x)
 ((if (positive? x) + -) x)) 

«…если аргумент положителен, то плюс, иначе минус x». Здесь в результате исполнения выражения if возвращается функция + или -, которая затем применяется к аргументу x. Полагаю, что смысл конструкции if вам сразу ясен. Сначала проверяется первый аргумент, если он истинен, то исполняется второй аргумент, иначе третий. Общий формат таков:

(if условие <действие, если условие выполняется> <действие в противном случае>) 

Где посмотреть и попробовать

В теории всё хорошо, а где немного попрактиковаться? В мире можно найти много прекрасно разработанных сред для работы со Scheme. К сожалению, большинство документации по Scheme на английском языке, но можно найти и отличные введения на русском — язык-то простой.

Кот в мешке

Простота Scheme обманчива. На самом деле — это один из самых мощных на сегодняшний день языков программирования. На основе этого языка можно изучить все известные стили и методы программирования. С частью этих приёмов мы познакомимся с вами в следующих статьях этой серии.

Упражнение

Посмотрите следующие две реализации функции вычисления факториала <math>f(n) = 1 \cdot 2 \cdots n</math>. Одна из них основана на рекурсии, а другая – на итерациях. Напишите на Scheme рекурсивную и основанную на итерациях реализации функции возведения в степень <math>f(a, n) = a^n</math>.

Вариант 1

(define (factorial n)
 (if (= n 0)
     1
     (* n (factorial (- n 1)))))

Вариант 2

(define (fact-iter result counter)

(if (= counter 0)
   result
   (fact-iter (* counter result)
              (- counter 1))))
(define (factorial n) (fact-iter 1 n))