Введение в язык Scheme для школьников: различия между версиями
Содержимое удалено Содержимое добавлено
Форматирование |
|||
Строка 1:
* Часть викиучебника «[[Лисп]]»
* Исходный вариант статьи (С.
Вы хорошо знаете русский, возможно, неплохо уже говорите по-английски, в школе вас научили несколько необычному языку математики. Предлагаю выучить ещё один — [[w:Лисп|Лисп]]. Точнее, один из его самых интересных диалектов — [[w:Scheme|Scheme]] (''Ским'').
== Введение в синтаксис==
Сперва познакомимся с несколько необычным порядком слов этого языка: «действие — предмет». Но необычен он только в сравнении с популярными языками программирования. В русском языке такая последовательность нередка:
*
* Произведение пяти, шести и семи. *
Каждая законченная фраза на этом языке должна быть окружена парой круглых скобок. Запишем сказанное выше на
<source lang="scheme">(+ 3 5)
(* 5 6 7)
(kupitj bulochnaja baton)</source>
Можно записать выражения и посложнее:
<source lang="scheme">(kupitj bulochnaja baton (+ 2 1))</source>
«Купи в булочной батоны: два плюс ещё один». Просто, не правда ли? Давайте двигаться дальше. Фраза <code>(* 3 5)</code> хороша, а <code>(* width height)</code> — лучше. Выражение <code>(* 2 3.1415926 5)</code> — интригующе, а <code>(* 2 pi radius)</code> гораздо более осмысленно. Здесь <code>width</code>, <code>height</code> — переменные, а <code>3</code> и <code>5</code> — их текущие значения.
Переменная задаётся следующей конструкцией языка:
<source lang="scheme">(define имя <первоначальное значение>)</source>
Пример:
<source lang="scheme">(define width 3)
(define height 7)
(* 2 (+ width height))</source>
Прочитаем записанное по-русски: «Положим ширина — это 3, высота — это 7, подсчитаем произведение двух и суммы ширины и высоты (например, периметр прямоугольника)». Результат такого вычисления в нашем случае будет 20.
Продолжим совершенствовать конструкции. Положим, нам требуется подсчитать сумму квадратов двух чисел. Это можно сделать, например, так:
<source lang="scheme">(define a 3)
(define b 4)
(+ (* a a) (* b b))</source>
Что-то не так; мы обычно вместо «помножь переменную на саму себя» говорим «возведи в квадрат эту переменную», на Скиме — <code>square</code>:
<source lang="scheme">(+ (square a) (square b))</source>
«Сумма квадрата <code>a</code> и квадрата <code>b</code>». Есть задача — есть её решение. Мы можем объявить новое слово-функцию, назвать её <code>square</code>. Функция будет принимать в качестве параметра число и возвращать его квадрат. Делается это следующим образом:
<source lang="scheme">(define (square x) (* x x))</source>
Общий формат:
<source lang="scheme">(define (название параметр параметр …) тело_функции)</source>
Функция возвращает последнее вычисленное значение. Это означает, что следующая функция <code>square2</code>:
<source lang="scheme">(define
вернёт тот же результат, что и <code>square</code>, перед этим умножив два на два безо всякого эффекта. Перепишем пример с суммой квадратов чисел заново:
<source lang="scheme">(define a 3)
(define b 4)
(define (square x) (* x x))
(+ (square a) (square b))</source>
Нам не хватало слов в языке — мы их добавили. Вообще, когда пишете программу на Лиспе, вы описываете не алгоритм, а сначала создаёте язык, а потом на нём формулируете исходную задачу. Несколько точнее — вы «подгоняете» данный вам язык Scheme до тех пор, пока он не станет совпадать с языком, на котором задача формулируется легко.
Сразу пример. Пусть перед нами стоит задача сделать программу, которая спрашивает имя пользователя, а потом выводит ему приветствие.
Scheme предоставляет нам несколько готовых «глаголов»:
; <code>
; <code>
; <code>newline</code>: вывод перевода строки.
Мы бы хотели иметь такие «глаголы»:
; <code>privet</code>: для приветствия с одним параметром — именем пользователя;
; <code>polzovatel</code>: для получения имени пользователя, без параметров.
Наша задача выглядела бы так:
<source lang="scheme">(privet (polzovatel))</source>
Дело за малым <source lang="scheme">(define (privet imja)
(display "Privet ")
(display imja)
Строка 67 ⟶ 96 :
(privet (polzovatel))</source>
[[w:Лисп|Лисп]]
Например, функцию «модуль числа» можно определить так:
<source lang=lisp>(define (abs x)
(if (positive? x )
Строка 74 ⟶ 104 :
(- x)))</source>
«Определим, что функция <code>abs</code> возвращает свой аргумент, если он положителен, иначе —
<source lang="scheme">(define (abs x)
((if (positive? x) + -) x))</source>
«…если аргумент положителен, то плюс, иначе минус <code>x</code>». Здесь в результате исполнения выражения <code>if</code> возвращается функция <code>+</code> или <code>-</code>, которая затем применяется к аргументу <code>x</code>. Полагаю, что смысл конструкции <code>if</code> вам сразу ясен. Сначала проверяется первый аргумент, если он истинен, то исполняется второй аргумент, иначе третий. Общий формат таков:
<source lang="scheme">(if условие <действие, если условие выполняется> <действие в противном случае>)</source>
== Где посмотреть и попробовать ==
В теории всё хорошо, а где немного попрактиковаться? В мире можно найти много прекрасно разработанных сред для работы со Scheme. К сожалению, большинство документации по Scheme на английском языке, но можно найти и отличные введения на русском — язык-то простой.
Вот названия нескольких самых распространённых реализаций:
; [http://www.plt-Scheme.org/ Plt Scheme]
; [http://www-sop.inria.fr/mimosa/fp/Bigloo/ Bigloo]: тоже достаточно полная реализация. Доступна для платформ [[w:Windows|Windows]], [[w:Linux|Linux]].
; [http://www.lispme.de/index.html LispMe]: версия для карманных компьютеров с операционной системой [[w:Palm OS|Palm OS]].
Также ещё посмотрите
Все перечисленные реализации Scheme — это интерпретаторы. Запускаете интерпретатор — и можно вести с ним диалог на
{{console|<pre style="border:none;margin:0;padding:0">Wecome to Mz Scheme version 208, Copyright (c) 2004 PLT Scheme, Inc.
>(+ 1 2) Попробуйте «проиграть» все вышеперечисленные примеры. Думаю, вам понравится!
== Кот в мешке ==
Простота Scheme обманчива. На самом деле — это один из самых мощных на сегодняшний день языков программирования. На основе этого языка можно изучить все известные стили и методы программирования. С частью этих приёмов мы познакомимся с вами в следующих статьях этой серии.
=== Упражнение ===
Посмотрите следующие две реализации функции вычисления [[w:Факториал|факториала]] <math>f(n) = 1 \cdot 2 \cdots n</math>. Одна из них основана на [[w:Рекурсия|рекурсии]], а другая – на [[w:Итерация|итерациях]]. Напишите на Scheme рекурсивную и основанную на итерациях реализации функции возведения в степень <math>f(a, n) = a^n</math>.
==== Вариант 1 ====
<source lang="scheme">(define (factorial n)
(if (= n 0)
1
Строка 116 ⟶ 155 :
==== Вариант 2 ====
<source lang="scheme">(define (fact-iter result counter)
(if (= counter 0)
result
(fact-iter (* counter result) (define (factorial n) (fact-iter 1 n))</source>
== Повторение – мать учения ==
Приведём небольшую шпаргалку по базовым конструкциям Scheme для тех, кто еще не ознакомился с первой частью статьи.
Базовый синтаксис:
<source lang="scheme">(<функция> <аргумент> <аргумент> …) ; комментарий</source>
Например:
<source lang="scheme">(+ 1 2 3 4) ; сумма первых четырёх натуральных чисел
(+ (+ 1 2) 5 6) ; возможно вкладывать одни вызовы функций в другие
(string-append "hello" "world") ; результат — склеенная строка "helloworld"</source>
Задание переменных и функций:
<source lang="scheme">(define <имя> <значение>)
(define (<имя> <аргумент> …) <тело функции>)
; функция возвращает значение последнего вычислительного выражения в теле функции</source>
Например:
<source lang="scheme">(define a 3)
(define b 4)
(define (square x) (* x x)) ; вычисляет квадрат числа
(define (+a x) (+ x a)) ; да-да, можно давать и такие имена функциям</source>
Дополнительные конструкции:
<source lang="scheme">(if <условие> <действие при успехе условия> <действие при неудаче>)
(begin <первое действие> <второе действие> …)</source>
Пример:
<source lang="scheme">(if (> a 0)
(display "a > 0")) ; действие при неудаче можно не указывать
(begin (display 1)
Строка 160 ⟶ 202 :
(display 3)) ; последовательно выполнятся действия, и на экран будет выведено: 123</source>
== И опять про повторение: функция <code>repeat</code> ==
<source lang="scheme">(display "hello")</source>
Если вам надо выполнить какое-то действие два раза, то вы просто повторяете его:
<source lang="scheme">(display "hello") (display "hello")</source>
А что, если вам нужно повторять работу снова и снова? Тогда мы сделаем функцию, которая будет повторяться требуемое количество раз. Называться эта функция будет <code>repeat</code>, и у неё будет один параметр — количество повторов. Алгоритм следующий:
{{Рамка}}
Если количество повторов больше нуля, то:
# выполняем действие
# Вызываем функцию repeat с количеством повторов меньшим на 1
{{Акмар}}
<source lang="scheme">(define (repeat number)
(if (> number 0) ; если количество повторов не нулевое
(begin (display "hello") ; выполняем действие
(repeat (- number 1))))) ; повторим действие на единицу меньшее количество раз.</source>
Попробуем. Запустим один из доступных вам интерпретаторов
{{console|<pre style="border:none;margin:0;padding:0">> (define (repeat number)
(if (> number 0)
(begin (display "hello")
(repeat (- number 1)))))
> (repeat 0)
> (repeat 1)
hello
> (repeat 2)
hellohello
> (repeat 3)
hellohellohello</pre>}}
=== Упражнение 1 ===
Попробуйте написать функцию, которая будет выводить на экран цифру 1 заданное количество раз.
=== Упражнение 2 ===
Попробуйте написать функцию, которая будет выводить на экран натуральные числа от 1 до заданного числа. Порядок вывода чисел не важен.
Самое время вспомнить, что в ''Scheme'' можно передавать функцию в качестве параметра. Усовершенствуем функцию <code>repeat</code> так, чтобы мы смогли повторять произвольные действия заданное количество раз. Пусть новая версия принимает два параметра: первый — количество повторов, второй — функция, которую надо запустить.
<source lang="scheme">(define (repeat number function)
(if (> number 0)
(begin (function)
(repeat (- number 1) function))))</source>
Теперь повторять можно разные действия:
<source lang="scheme">(define (print-one) (display "1"))
(define (print-hello) (display "hello"))
(repeat 3 print-one) ; три раза выведет на экран "1"
(repeat 5 print-hello) ; пять раз выведет на экран "hello"</source>
== Принцип наименьших усилий ==
Не надо делать лишних действий, если их можно избежать. Последний вариант функции repeat хорош, но… зачем каждый раз давать функции имя, если нужно просто её выполнить? А можно ли вообще создать функцию, но не давать ей имя? Оказывается можно. В языке есть специальная инструкция, которая говорит «создать функцию».
<source lang="scheme">(lambda (<аргументы>) <тело функции> <последнее вычисленное значение возвращается>)</source>
Пример:
<source lang="scheme">(lambda (x) (* x x)) ; создать функцию, которая вычисляет квадрат числа
(lambda (x y) (+ x y)) ; создать функцию, которая вычисляет сумму двух чисел
(define square (lambda(x) (* x x))) ; создать функцию, которая вычисляет квадрат числа и назвать её square.</source>
Оказывается, последняя конструкция то же самое, что и:
<source lang="scheme">(define (square x) (* x x))</source>
Вот мы с вами открыли ещё один способ определять функции с именами: сначала создаём, затем даём имя. Давайте-ка теперь «повторим» действия, не давая имена функциям:
<source lang="scheme">(repeat 3 (lambda() (display "hello")) ) ; три раза выведем на экран "hello"
(repeat 5 (lambda() (display "1"))) ; пять раз выведем на экран "1"</source>
Для <code>repeat</code> используются функции без параметров, поэтому в конструкции <code>lambda</code> пустая пара скобок.
== Списки ==
Проведём следующую работу:
<source lang="scheme">(define a 1)
(define b 2)
(define c 3)
Строка 239 ⟶ 294 :
(+ c 1)</source>
А как бы нам сразу взять три числа и увеличить их на единицу одним махом? Для этого надо «связать» эти числа вместе. Один из способов склеивания
<source lang="scheme">(list <элемент1> <элемент2> <элемент3> …)</source>
Пример:
<source lang="scheme">(define
(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)) ; элементы списка можно вычислять перед его созданием</source>
Scheme также предоставляет функцию:
<source lang="scheme">(map <функция> <список>)</source>
Эта функция возвращает список, в котором каждый элемент есть результат применения <функция> к элементу исходного списка. Пример: <source lang="scheme">(define (inc x) (+ x 1)) ; увеличивает число на единицу
(map inc (list 1 1 1)) ; возвращает список из двоек
(map square (list 1 2 3)) ; возвращает список из квадратов элементов, то есть 1, 4 и 9 Вспомним про lambda и решим задачу, которую поставили себе в начале этого раздела:
<source lang="scheme">(define abc (list 1 1 1))
(map (lambda(x) (+ x 1)) abc)</source>
А можно даже и список не вводить как дополнительную переменную:
<source lang="scheme">(map (lambda(x) (+ x 1))
(list 1 1 1))</source>
=== Упражнение 3 ===
Пользуясь функциями <code>write</code> (для печати списка на экране) и <code>map</code>, напишите функцию, которая будет выводить на экран список, увеличенный на заданное число, например
<source lang="scheme">(print-it 5 (list 1 2 3)) ; выведет "(6 7 8)"</source>
== Работа со списками ==
А как написать функцию, которая последовательно будет перемещаться по заданному списку и выводить каждый элемент этого
списка? Для этого нам надо только знать следующие инструкции:
* <code>(null? <список>)</code> — проверяет, а есть ли ещё какие элементы в списке,
* <code>(car <список>)</code> — возвращает первый элемент списка,
* <code>(cdr <список>)</code> — возвращает список из всех элементов, кроме первого, а если больше ничего не осталось, то
Пример:
<source lang="scheme">(car (list 1 2 3)) ; вернёт 1
(cdr (list 1 2 3)) ; вернёт список из 2 и 3, то есть (list 2 3).</source>
Проще говоря, функция <code>car</code> возвращает голову списка, а <code>cdr</code> — оставшийся хвост списка.
Имя функции <code>print-list</code>. Единственный параметр — исходный список. Алгоритм работы нашей функции следующий:
{{Рамка}}
Если список не пуст, то:
# выводим голову списка.
# вызываем <code>print-list</code> для хвоста списка {{Акмар}}
<source lang="scheme">(define (print-list lst)
(if (not (null? lst))
(begin (display (car lst))
Строка 295 ⟶ 363 :
(print-list (cdr lst)))))</source>
Поэкспериментируем в интерпретаторе:
=== Упражнение 4 ===
Поэкспериментируйте в интерпретаторе с функциями <code>car</code>, <code>cdr</code> и <code>null?</code>.
=== Упражнение 5 ===
Напишите функцию, которая будет вычислять длину списка. Длина пустого списка — ноль.
=== Упражнение 6 ===
Пользуясь изученными функциями <code>car</code>, <code>cdr</code> и <code>null?</code> напишите функцию <code>for-each-element</code>, которая будет применять заданную функцию к каждому элементу данного списка. Например, <code>(for-each-element display (list 1 2 3))</code> должна напечатать «123». Напишите новую версию <code>print-list</code>, пользуясь только что созданной функцией.
=== Упражнение 7 ===
Напишите функцию, которая будет принимать на вход два списка и возвращать список из попарных сумм элементов, например, команда <code>(plus (list 1 2) (list 5 6))</code> должна вернуть список <code>(6 8)</code>.
=== Упражнение
Попробуйте решить [[#Упражнение 7|упражнение 7]] с помощью функции <code>map</code> — правильный ответ вас сильно удивит.
== См. также ==
* Викиучебник «[[Лисп]]».
* [[w:Лисп|Лисп]], статья в Википедии.
* [[w:Scheme|Scheme]], статья в Википедии.
* [http://www.plt-scheme.org/ Plt Scheme], официальная страница Plt Scheme.
* [http://www-sop.inria.fr/mimosa/fp/Bigloo/ Bigloo], страничка о Bigloo.
* [http://www.lispme.de/index.html LispMe], официальная страница LispMe.
* [http://www.iro.umontreal.ca/~gambit/ Gambit-C], здесь можно скачать Gambit-C.
Учебники на английском
* [http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme.html Teach Yourself Scheme in Fixnum Days ], Dorai Sitaram.
* [http://www.scheme.com/tspl/ The Scheme Programming Language], R. Kent Dybvig.
* [http://schemecookbook.org/ Schematics Scheme Cookbook].
* [http://cl-cookbook.sourceforge.net/ The Common Lisp Cookbook].
* [http://www.gigamonkeys.com/book/ Practical Common Lisp].
* [http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/ Видео лекции "Structure and Interpretation of Computer Programs"], Harold Abelson и Gerald Jay Sussman.
[[Категория:Журнал «Потенциал»]]
| |||