Введение в язык Scheme для школьников: различия между версиями
Содержимое удалено Содержимое добавлено
Greck (обсуждение | вклад) |
Greck (обсуждение | вклад) Нет описания правки |
||
Строка 1:
* Исходный вариант статьи (С. И. Иевлев, «Ваш новый язык — Scheme») опубликован в двух частях в [[Журнал «Потенциал»|журнале «Потенциал»]].
Вы хорошо знаете русский, возможно, неплохо уже говорите по-английски, в школе вас научили несколько необычному языку математики. Предлагаю выучить ещё один — [[w:Лисп|Лисп]]. Точнее, один из его самых интересных диалектов — [[w:Scheme|Scheme]] (''Ским'').
== Введение в синтаксис==
Начнём с того, что познакомимся с несколько необычным порядком слов этого языка: «действие объект объект ...». Но необычен он только в сравнении с популярными языками программирования. В русском языке предложения вполне часто строятся подобным образом:
*«Сумма трёх и пяти.»
*«Произведение пяти, шести и семи.»
*«Купи в булочной батон.»
Каждая законченная фраза на этом языке должна быть окружена парой круглых скобок.
Запишем сказанное выше на [[w:Scheme|Scheme]]:
<code>(+ 3 5)
(* 5 6 7)
(kupitj bulochnaja baton)</code>
Можно записать выражения и посложнее:
<code>(+ 2 3 (+ 5 6) )</code>
«Сумма двух, трёх и суммы пяти и шести.» Просто, не правда ли? Давайте двигаться дальше. Фраза <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> — переменные, а 3 и 5 — их текущие значения.
Переменная задаётся следующей конструкцией языка:
<code>(define имя «первоначальное значение»)</code>
Пример:
<code>(define width 3)
(define height 7)
(* 2 (+ width height))</code>
Прочитаем записанное по-русски: «Положим ширина — это 3, высота — это 7, подсчитаем произведение двух и суммы ширины и высоты (например, периметр прямоугольника)». Результат такого вычисления в нашем случае будет 20.
Продолжим совершенствовать конструкции. Допустим, нам требуется подсчитать сумму квадратов двух чисел. Это можно сделать, например, так:
<code>(define a 3)
(define b 4)
(+ (* a a) (* b b))</code>
Не правда ли, что-то режет глаз? Cлишком громоздко — так мы никогда не говорим. Если в русском был бы глагол «квадрат числа», то последнее выражение звучало бы:
<code>(+ (square a) (square b))</code>
Согласитесь, что так лучше.
Есть задача — есть её решение. Мы можем объявить новое слово-функцию, назвать её square. Функция будет принимать в качестве параметра число и возвращать его квадрат. Делается это следующим образом:
<code>(define (square x) (* x x))</code>
Общий формат:
<code>(define (название параметр параметр...) тело функции)</code>
Функция возвращает последнее вычисленное значение. Это означает, что следующая функция square2:
<code>(define (square2 x) (+ x x) (* x x))</code>
вернёт тот же результат, что и square, только попутно сделает ещё одно ненужное дело — удвоение числа.
Перепишем пример с суммой квадратов чисел заново:
<code>(define a 3)
(define b 4)
(define (square x) (* x x))
(+ (square a) (square b))</code>
Нам не хватало слов в языке — мы их добавили. Вообще, когда вы пишете программу на [[w:Лисп|Лисп]], вы описываете не алгоритм, а сначала создаёте язык, а потом на нём формулируете исходную задачу. Несколько точнее — вы «подгоняете» данный вам [[w:Scheme|Scheme]] язык до тех пор, пока он не станет совпадать с языком, на котором задача формулируется легко.
Сразу пример. Пусть перед нами стоит задача сделать программу, которая спрашивает имя пользователя, а потом выводит ему приветствие.
[[w:Scheme|Scheme]] предоставляет нам несколько готовых «глаголов»:
;<code>read</code>:для чтения имени
;<code>display</code>:вывод чего-то на дисплее
;<code>newline</code>:вывод перевода строки
Мы бы хотели иметь такие «глаголы»:
;<code>privet</code>:для приветствия с одним параметром — именем пользователя
;<code>polzovatel</code>:для получения имени пользователя, без параметров.
Наша задача выглядела бы так:
<code>(privet (polzovatel))</code>
Дело за малым — определить <code>privet</code> и <code>polzovatel</code>. Нет проблем. Вот полный текст программы.
<code>(define (privet imja)
(display "Privet ")
(display imja)
(display "!")
(newline))
(define (polzovatel)
(write "Predstavtes:")
(read))
(privet (polzovatel))</code>
[[w:Лисп|Лисп]] — полноценный функциональный язык, а поэтому функции — полноправные члены этого языка, независимо от того, определили вы их сами, или они уже были в языке «готовые». В частности, их можно передавать в качестве параметров в другие функции, а там уже делать с ними всё, что потребуется.
Например, функцию «модуль числа» можно определить так:
<code>(define (abs x)
(if (positive? x )
x
(- x)))</code>
«Если аргумент положителен — возвращается <code>x</code>, иначе минус <code>x</code>». А можно и так:
<code>(define (abs x)
((if (positive? x) + -) x))</code>
«Если аргумент положителен, то плюс, иначе минус x». Здесь в результате исполнения выражения <code>if</code> возвращается функция <code>+</code> или <code>-</code>, которая затем применяется к аргументу <code>x</code>. Полагаю, что смысл конструкции <code>if</code> вам сразу ясен. Сначала проверяется первый аргумент, если он истинен, то исполняется второй аргумент, иначе третий. Общий формат таков:
<code>(if условие «действие, если условие выполняется» «действие в противном случае»)</code>
== Где посмотреть и попробовать ==
В теории всё хорошо, а где немного попрактиковаться? В мире можно найти много прекрасно разработанных сред для работы со [[w:Scheme|Scheme]]. К сожалению, большинство документации по [[w:Scheme|Scheme]] на английском языке, но можно найти и отличные введения на русском — язык-то простой.
Вот названия нескольких самых распространённых реализаций:
;[http://www.plt-Scheme.org/ Plt Scheme] : одна из самых полных реализаций, включает в себя удобную обучающую среду Dr.Scheme. Есть версии для платформ [[w:Windows|Windows]], [[w:Linux|Linux]], [[w:Mac OS|Mac OS]].
;[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]].
Также ещё посмотрите '''[http://www.iro.umontreal.ca/~gambit/ Gambit-C]''' — один из самых быстрых компиляторов Scheme.
Все перечисленные реализации Scheme — это интерпретаторы. Запускаете интерпретатор — и можно вести с ним диалог на [[w:Scheme|Scheme]]: в ответ на его приглашение вводите конструкции на Scheme, а он будет возвращать результаты вычислений.
<code>Wecome to Mz Scheme version 208, Copyright (c) 2004 PLT Scheme, Inc.
>1
1
>(+ 1 2)
3
>(define a 3)
>(+ a a)
6
></code>
Попробуйте «проиграть» все вышеперечисленные примеры. Думаю, вам понравится!
== Кто в мешке ==
Простота [[w:Scheme|Scheme]] обманчива. На самом деле — это один из самых мощных на сегодняшний день языков программирования. На основе этого языка можно изучить все известные стили и методы программирования. С частью этих приёмов мы познакомимся с вами в следующих статьях этой серии.
=== Упражнение ===
Посмотрите следующие две реализации функции вычисления факториала <math>f(n)=1 \cdot 2 \cdot \cdots \cdot n</math>. Одна из них основана на рекурсии, а другая – на итерациях. Напишите на языке [[w:Scheme|Scheme]] рекурсивную и основанную на итерациях реализации функции возведения в степень <math>f(a,n) = a^n</math>.
==== Вариант 1 ====
<code>(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))</code>
==== Вариант 2 ====
<code>(define (fact-iter result counter)
(if (= counter 0)
result
(fact-iter (* counter result)
(- counter 1))))
(define (factorial n) (fact-iter 1 n))</code>
==Повторение – мать учения==
Приведём небольшую шпаргалку по базовым конструкциям языка программирования Scheme для тех, кто еще не ознакомился с первой частью [[Введение в язык Scheme для школьников|статьи]].
Базовый синтаксис:
<code>(<функция> <аргумент> <аргумент> ...) </code>
<code>;комментарий</code>
Например:
<code>(+ 1 2 3 4) ; сумма первых четырёх натуральных чисел</code>
<code>(+ (+ 1 2) 5 6) ; возможно вкладывать одни вызовы функций в другие</code>
<code>(string-append "hello" "world") ; результат — склеенная строка "helloworld"</code>
Задание переменных и функций:
<code>(define <имя> <значение>)</code>
<code>(define (<имя> <аргумент>...) <тело функции>)</code>
<code>; функция возвращает значение последнего вычислительного </code>
<code>; выражения в теле функции.</code>
Например:
<code>(define a 3)</code>
<code>(define b 4)</code>
<code>(define (square x) (* x x)) ; вычисляет квадрат числа</code>
<code>(define (+a x) (+ x a)) </code>
<code>; да-да, можно давать и такие имена функциям</code>
Дополнительные конструкции:
<code>(if <условие> <действие при успехе условия> <действие при неудаче>)</code>
<code>(begin <первое действие> <второе действие> ....)</code>
Пример:
<code>(if (> a 0) </code>
<code>(display "a > 0")) ; действие при неудаче можно не указывать</code>
<code>(begin (display 1)</code>
<code>(display 2)</code>
<code>(display 3)) ; последовательно выполнятся действия, и на экран будет выведено: 123</code>
==И опять про повторение: функция repeat==
Ну вот, теперь можно продолжать двигаться дальше. Если вам надо выполнить какое-то действие один раз, то вы просто его
делаете один раз: <code>(display "hello")</code>. Если вам надо выполнить какое-то действие два раза, то вы просто повторяете его:
<code>(display "hello") (display "hello")</code>. А что, если вам нужно повторять работу снова и снова? Тогда мы сделаем функцию, которая будет повторяться требуемое количество раз. Называться эта функция будет <code>repeat</code>, и у неё будет один параметр — количество повторов. Алгоритм следующий:
{{Рамка}}
Если количество повторов больше нуля, то:
#выполняем действие
#Вызываем функцию repeat с количеством повторов меньшим на 1
{{Акмар}}
<code>(define (repeat number)
(if (> number 0) ; если количество повторов не нулевое
(begin (display "hello") ; выполняем действие
(repeat (- number 1))))) ; повторим действие на единицу меньшее количество раз.</code>
Попробуем. Запустим один из доступных вам интерпретаторов ''Scheme'', например ''mzscheme'', который можно найти в интернете по
адресу http://www.plt-scheme.org/software/drscheme/ и установить на вашем компьютере.
<code> > (define (repeat number)
(if (> number 0)
(begin (display "hello")
(repeat (- number 1)))))
> (repeat 0)
> (repeat 1)
hello
> (repeat 2)
hellohello
> (repeat 3)
hellohellohello</code>
===Упражнение 1===
Попробуйте написать функцию, которая будет выводить на экран цифру "1" заданное количество раз.
===Упражнение 2===
Попробуйте написать функцию, которая будет выводить на экран натуральные числа от "1" до заданного числа. Порядок вывода чисел не важен.
Самое время вспомнить, что в ''Scheme'' можно передавать функцию в качестве параметра. Усовершенствуем функцию repeat так, чтобы мы смогли повторять произвольные действия заданное количество раз. Пусть новая версия принимает два параметра: первый — количество повторов, второй — функция, которую надо запустить.
<code>(define (repeat number function)
(if (> number 0)
(begin (function)
(repeate (- number 1)))))</code>
Теперь повторять можно разные действия:
<code>(define (print-one) (display "1"))
(define (print-hello) (display "hello"))
(repeat 3 print-one) ; три раза выведет на экран "1"
(repeat 5 print-hello) ; пять раз выведет на экран "hello"</code>
==Принцип наименьших усилий==
Не надо делать лишних действий, если их можно избежать. Последний вариант функции repeat хорош, но ... зачем каждый раз
давать функции имя, если нужно просто её выполнить? А можно ли вообще создать функцию, но не давать ей имя? Оказывается
можно. В языке есть специальная инструкция, которая говорит «создать функцию».
<code>(lambda (<аргументы>) <тело функции> <последнее вычисленное значение возвращается>)</code>
Пример:
<code>(lambda (x) (* x x)) ; создать функцию, которая вычисляет квадрат числа
(lambda (x y) (+ x y)) ;создать функцию, которая вычисляет сумму двух чисел
(define square (lambda(x) (* x x))) ; создать функцию, которая вычисляет квадрат числа и назвать её square.</code>
Оказывается, последняя конструкция то же самое, что и:
<code>(define (square x) (* x x))</code>
Вот мы с вами открыли ещё один способ определять функции с именами: сначала создаём, затем даём имя. Давайте-ка теперь
«повторим» действия, не давая имена функциям:
<code>(repeat 3 (lambda() (display "hello")) ) ; три раза выведем на экран "hello"
(repeat 5 (lambda() (display "1"))) ; пять раз выведем на экран "1"</code>
Для repeat используются функции без параметров, поэтому в конструкции lambda пустая пара скобок.
==Списки==
Проведём следующую работу:
<code>(define a 1)
(define b 2)
(define c 3)
(+ a 1)
(+ b 1)
(+ c 1)</code>
А как бы нам сразу взять три числа и увеличить их на единицу одним махом? Для этого надо «связать» эти числа вместе. Один из
способов склеивания — список. Создаётся список следующей конструкцией:
<code>(list <элемент1> <элемент2> <элемент3> ...)</code>
Пример:
(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 также предоставляет функцию:
<code>(map <функция> <список>)</code>
Эта функция возвращает список, в котором каждый элемент есть результат применения функции "<функция>" к элементу исходного
списка. Пример:
<code>(define (inc x) (+ x 1)); увеличивает число на единицу
(map inc (list 1 1 1)); возвращает список из двоек
(map square (list 1 2 3)); возвращает список из квадратов элементов, то есть 1, 4 и 9.</code>
Вспомним про lambda и решим задачу, которую поставили себе в начале этого раздела:
<code>(define abc (list 1 1 1))
(map (lambda(x) (+ x 1)) abc)</code>
А можно даже и список не вводить как дополнительную переменную:
<code>(map (lambda(x) (+ x 1))
(list 1 1 1))</code>
===Упражнение 3===
Пользуясь функциями write (для печати списка на экране) и map, напишите функцию, которая будет выводить на
экран список, увеличенный на заданное число, например
<code>(print-it 5 (list 1 2 3)) выведет "(6 7 8)"</code>
==Работа со списками==
А как написать функцию, которая последовательно будет перемещаться по заданному списку и выводить каждый элемент этого
Строка 47 ⟶ 330 :
===Упражнение 8===
Попробуйте решить упражнение 8 с помощью функции <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"], Hal Abelson и Gerald Jay Sussma]
[[Категория:Журнал «Потенциал»]]
[[Категория:Программирование]]
[[Категория:Функциональное программирование]]
[[Категория:Языки программирования]]
| |||