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

Материал из ТХАБ.РФ
Перейти к: навигация, поиск
м (Вариант 2. Итерация)
м (Повторение – мать учения)
Строка 191: Строка 191:
 
== Повторение – мать учения ==
 
== Повторение – мать учения ==
  
Приведём небольшую шпаргалку по базовым конструкциям Scheme для тех, кто еще не ознакомился с первой частью статьи.
+
Приведём небольшую шпаргалку по базовым конструкциям [[Перфо]].
  
 
Базовый синтаксис:
 
Базовый синтаксис:
Строка 201: Строка 201:
 
  (+ 1 2 3 4)                    // сумма первых 4-х натуральных чисел
 
  (+ 1 2 3 4)                    // сумма первых 4-х натуральных чисел
 
  (+ (+ 1 2) 5 6)                // возможно вкладывать одни вызовы функций в другие
 
  (+ (+ 1 2) 5 6)                // возможно вкладывать одни вызовы функций в другие
  (string-append "hello" "world") // результат — склеенная строка "helloworld"  
+
  (string-append "Привет" "Мир") // результат — склеенная строка "ПриветМир"  
  
 
Задание переменных и функций:
 
Задание переменных и функций:
Строка 211: Строка 211:
 
Например:
 
Например:
  
  (define a 3)
+
  (перем a 3)
  (define b 4)
+
  (перем b 4)
 
  (define (square x) (* x x)) ; вычисляет квадрат числа
 
  (define (square x) (* x x)) ; вычисляет квадрат числа
 
  (define (+a x) (+ x a)) ; да-да, можно давать и такие имена функциям  
 
  (define (+a x) (+ x a)) ; да-да, можно давать и такие имена функциям  
Строка 226: Строка 226:
 
  (begin (display 1)
 
  (begin (display 1)
 
       (display 2)
 
       (display 2)
       (display 3)) ; последовательно выполнятся действия, и на экран будет выведено: 123  
+
       (display 3)) ; последовательно выполнятся действия, и на экран будет выведено: 123
  
 
== И опять про повторение: функция <code>repeat</code> ==
 
== И опять про повторение: функция <code>repeat</code> ==

Версия 17:14, 2 сентября 2020

Это заготовка для переделки под язык Перфо - учебника "Введение в Scheme для школьников".

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

Соответствие ключевых слов Ским (Scheme) и Перфо

  •  ; - // - комментарий, многострочный комментарий /* */ - не поддерживается
  • define - перем, функция -
    • перем - создаёт и изменяет переменную
    • функция - создаёт функцию
  • read - ввод - ввод строки пользователя
  • display - вывод
  • write - вывод
  • newline - ПС - перевод строки
  • if - если - оператор ветвления ЕСЛИ
  • positive? - (> переменная 0)

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

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

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

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

(+ 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))
(+ (квадрат А) (квадрат Б)) 

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

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

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

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

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

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

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

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

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

(функция (привет имя) // 
  (вывод "Привет, ")
  (вывод имя)
  (вывод "!")
  (ПС))
(функция (пользователь)
  (вывод "Представьтесь:")
  (ввод))
(привет (пользователь)) 

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

Ветвление программы - оператор если

Например, функцию «модуль числа» можно определить так:

(функция (модуль ф)
         (если (> ф 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)                 // возможно вкладывать одни вызовы функций в другие
(string-append "Привет" "Мир") // результат — склеенная строка "ПриветМир" 

Задание переменных и функций:

(define <имя> <значение>)
(define (<имя> <аргумент> …) <тело функции>)
// функция возвращает значение последнего вычислительного выражения в теле функции 

Например:

(перем a 3)
(перем b 4)
(define (square x) (* x x)) ; вычисляет квадрат числа
(define (+a x) (+ x a)) ; да-да, можно давать и такие имена функциям 

Дополнительные конструкции:

(if <условие> <действие при успехе условия> <действие при неудаче>)
(begin <первое действие> <второе действие> …) 

Пример:

(if (> a 0)
    (display "a > 0")) ; действие при неудаче можно не указывать
(begin (display 1)
      (display 2)
      (display 3)) ; последовательно выполнятся действия, и на экран будет выведено: 123

И опять про повторение: функция repeat

Ну вот, теперь можно продолжать двигаться дальше. Если вам надо выполнить какое-то действие один раз, то вы просто его делаете один раз:

(display "hello") 

Если вам надо выполнить какое-то действие два раза, то вы просто повторяете его:

(display "hello") (display "hello") 

А что, если вам нужно повторять работу снова и снова? Тогда мы сделаем функцию, которая будет повторяться требуемое количество раз. Называться эта функция будет repeat, и у неё будет один параметр — количество повторов. Алгоритм следующий:

Если количество повторов больше нуля, то: 1. выполняем действие 2. Вызываем функцию repeat с количеством повторов меньшим на 1

(define (repeat number)
      (if (> number 0) // если количество повторов не нулевое
          (begin (display "hello") // выполняем действие
                 (repeat (- number 1))))) // повторим действие на единицу меньшее количество раз. 

Попробуем. Запустим один из доступных вам интерпретаторов Scheme, например mzscheme, который можно найти в Интернете по адресу http://www.plt-scheme.org/software/drscheme/ и установить на вашем компьютере.

>> (define (repeat number)

               (if (> number 0)
                   (begin (display "hello")
                          (repeat (- number 1)))))

> (repeat 0) > (repeat 1) hello > (repeat 2) hellohello > (repeat 3) hellohellohello

Упражнение 1

Попробуйте написать функцию, которая будет выводить на экран цифру 1 заданное количество раз.

Упражнение 2

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

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

(define (repeat number function)
 (if (> number 0)
   (begin (function)
          (repeat (- number 1) function)))) 

Теперь повторять можно разные действия:

(define (print-one) (display "1"))
(define (print-hello) (display "hello"))
(repeat 3 print-one) // 3 раза выведет на экран "1"
(repeat 5 print-hello) // 5 раз выведет на экран "hello" 

Принцип наименьших усилий

Не надо делать лишних действий, если их можно избежать. Последний вариант функции repeat хорош, но… зачем каждый раз давать функции имя, если нужно просто её выполнить? А можно ли вообще создать функцию, но не давать ей имя? Оказывается можно. В языке есть специальная инструкция, которая говорит «создать функцию».

(lambda (<аргументы>) <тело функции> <последнее вычисленное значение возвращается>)

Пример:

(lambda (x) (* x x))    ; создать функцию, которая вычисляет квадрат числа
(lambda (x y) (+ x y)) ; создать функцию, которая вычисляет сумму двух чисел
(define square (lambda(x) (* x x)))  ; создать функцию, которая вычисляет квадрат числа и назвать её square.

Оказывается, последняя конструкция то же самое, что и:

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

Вот мы с вами открыли ещё один способ определять функции с именами: сначала создаём, затем даём имя. Давайте-ка теперь «повторим» действия, не давая имена функциям:

(repeat 3 (lambda() (display "hello")) ) ; три раза выведем на экран "hello"
(repeat 5 (lambda() (display "1"))) ; пять раз выведем на экран "1"

Для repeat используются функции без параметров, поэтому в конструкции lambda пустая пара скобок.

Списки

Проведём следующую работу:

(define a 1)
(define b 2)
(define c 3)
(+ a 1)
(+ b 1)
(+ c 1) 

А как бы нам сразу взять три числа и увеличить их на единицу одним махом? Для этого надо «связать» эти числа вместе. Один из способов склеивания — список. Создаётся список следующей конструкцией:

(list <элемент1> <элемент2> <элемент3> …) 

Пример:

(define abc (list 1 1 1))                 ; список из трёх единиц
(define lst1 (list 1 2 3))                ; список из трёх разных чисел
(define lst2 (list "hello" "my" "world")) ; список из строк
(define lst3 (list "hello" 1 "world" 3))  ; список из строк и чисел
(define lst4 (list (+ 1 0) 2 3))          ; элементы списка можно вычислять перед его созданием 

Scheme также предоставляет функцию:

(map <функция> <список>) 

Эта функция возвращает список, в котором каждый элемент есть результат применения <функция> к элементу исходного списка. Пример:

(define (inc x) (+ x 1))  ; увеличивает число на единицу
(map inc (list 1 1 1))    ; возвращает список из двоек
(map square (list 1 2 3)) ; возвращает список из квадратов элементов, то есть 1, 4 и 9 

Вспомним про lambda и решим задачу, которую поставили себе в начале этого раздела:

(define abc (list 1 1 1))
(map (lambda(x) (+ x 1)) abc) 

А можно даже и список не вводить как дополнительную переменную:

(map (lambda(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 — правильный ответ вас сильно удивит.

См. также

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