Онлайн словарь
& . 1 2 3 4 5
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Μ
А Б В Г Д Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Э Ю Я
ВА ВВ ВЕ ВЗ ВИ ВО ВТ ВЫ

Введение в язык Scheme для школьников

[loadfile: templates/common/google_ads.txt is empty]
 
* Часть викиучебника «Лисп»
* Исходный вариант статьи (С. И. Иевлев, «Ваш новый язык — Scheme») опубликован в двух частях в Журнал «Потенциал»
журнале «Потенциал».
Вы хорошо знаете русский, возможно, неплохо уже говорите по-английски, в школе вас научили несколько необычному языку математики. Предлагаю выучить ещё один — Лисп. Точнее, один из его самых интересных диалектов — Scheme ('Ским').
= Введение в синтаксис=
Сперва познакомимся с несколько необычным порядком слов этого языка: «действие — предмет». Но необычен он только в сравнении с популярными языками программирования. В русском языке такая последовательность нередка:
* Сумма трёх и пяти.
* Произведение пяти, шести и семи.
* Купи в булочной батон.
Каждая законченная фраза на этом языке должна быть окружена парой круглых скобок. Запишем сказанное выше на Sheme:
(+ 3 5)
(* 5 6 7)
(kupitj bulochnaja baton)
Можно записать выражения и посложнее:
(kupitj bulochnaja baton (+ 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: вывод перевода строки.
Мы бы хотели иметь такие «глаголы»:
; privet: для приветствия с одним параметром — именем пользователя;
; polzovatel: для получения имени пользователя, без параметров.
Наша задача выглядела бы так:
(privet (polzovatel))
Дело за малым — определить privet и polzovatel. Нет проблем. Вот полный текст программы.
(define (privet imja)
(display 'Privet ')
(display imja)
(display '!')
(newline))
(define (polzovatel)
(write 'Predstavtes:')
(read))
(privet (polzovatel))
Лисп — полноценный функциональный язык, а поэтому функции — полноправные члены этого языка, независимо от того, определили вы их сами, или они уже были в языке готовые. В частности, их можно передавать в качестве параметров в другие функции, а там уже делать с ними всё, что потребуется.
Например, функцию «модуль числа» можно определить так:
(define (abs x)
(if (positive? x )
x
(- x)))
«Определим, что функция abs возвращает свой аргумент, если он положителен, иначе — -x». А можно и так:
(define (abs x)
((if (positive? x) + -) x))
«. . .если аргумент положителен, то плюс, иначе минус x». Здесь в результате исполнения выражения if возвращается функция + или -, которая затем применяется к аргументу x. Полагаю, что смысл конструкции if вам сразу ясен. Сначала проверяется первый аргумент, если он истинен, то исполняется второй аргумент, иначе третий. Общий формат таков:
(if условие )
= Где посмотреть и попробовать =
В теории всё хорошо, а где немного попрактиковаться? В мире можно найти много прекрасно разработанных сред для работы со Scheme. К сожалению, большинство документации по Scheme на английском языке, но можно найти и отличные введения на русском — язык-то простой.
Вот названия нескольких самых распространённых реализаций:
; : одна из самых полных реализаций, включает в себя удобную обучающую среду Dr.Scheme. Есть версии для платформ Windows, Linux, Mac OS.
; : тоже достаточно полная реализация. Доступна для платформ Windows, Linux.
; : версия для карманных компьютеров с операционной системой Palm OS.
Также ещё посмотрите — один из самых быстрых компиляторов Scheme.
Все перечисленные реализации Scheme — это интерпретаторы. Запускаете интерпретатор — и можно вести с ним диалог на Scheme: в ответ на его приглашение вводите конструкции на Scheme, а он будет возвращать результаты вычислений.
console
Wecome to Mz Scheme version 208, Copyright (c) 2004 PLT Scheme, Inc.
>1
1
>(+ 1 2)
3
>(define a 3)
>(+ a a)
6
>
Попробуйте «проиграть» все вышеперечисленные примеры. Думаю, вам понравится!
= Кот в мешке =
Простота Scheme обманчива. На самом деле — это один из самых мощных на сегодняшний день языков программирования. На основе этого языка можно изучить все известные стили и методы программирования. С частью этих приёмов мы познакомимся с вами в следующих статьях этой серии.
= Упражнение =
Посмотрите следующие две реализации функции вычисления Факториал f(n) = 1 \cdot 2 \cdots n. Одна из них основана на Рекурсия, а другая – на Итерация. Напишите на Scheme рекурсивную и основанную на итерациях реализации функции возведения в степень f(a, n) = a^n.
= Вариант 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))
= Повторение – мать учения =
Приведём небольшую шпаргалку по базовым конструкциям Scheme для тех, кто еще не ознакомился с первой частью статьи.
Базовый синтаксис:
( . . .) ; комментарий
Например:
(+ 1 2 3 4) ; сумма первых четырёх натуральных чисел
(+ (+ 1 2) 5 6) ; возможно вкладывать одни вызовы функций в другие
(string-append 'hello' 'world') ; результат — склеенная строка 'helloworld'
Задание переменных и функций:
(define )
(define ( . . .) )
; функция возвращает значение последнего вычислительного выражения в теле функции
Например:
(define a 3)
(define 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, и у неё будет один параметр — количество повторов. Алгоритм следующий:
Рамка
Если количество повторов больше нуля, то:
# выполняем действие
# Вызываем функцию repeat с количеством повторов меньшим на 1
Акмар
(define (repeat number)
(if (> number 0) ; если количество повторов не нулевое
(begin (display 'hello') ; выполняем действие
(repeat (- number 1))))) ; повторим действие на единицу меньшее количество раз.
Попробуем. Запустим один из доступных вам интерпретаторов Scheme, например mzscheme, который можно найти в Интернете по адресу http://www.plt-scheme.org/software/drscheme/ и установить на вашем компьютере.
console
> (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) ; три раза выведет на экран '1'
(repeat 5 print-hello) ; пять раз выведет на экран '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 . . .)
Пример:
(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. Единственный параметр — исходный список. Алгоритм работы нашей функции следующий:
Рамка
Если список не пуст, то:
# выводим голову списка.
# вызываем print-list для хвоста списка
Акмар
(define (print-list lst)
(if (not (null? lst))
(begin (display (car lst))
(newline)
(print-list (cdr lst)))))
Поэкспериментируем в интерпретаторе:
console
> (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
упражнение 7 с помощью функции map — правильный ответ вас сильно удивит.
= См. также =
* Викиучебник «Лисп».
* Лисп, статья в Википедии.
* Scheme, статья в Википедии.
* , официальная страница Plt Scheme.
* , страничка о Bigloo.
* , официальная страница LispMe.
* , здесь можно скачать Gambit-C.
Учебники на английском
* , Dorai Sitaram.
* , R. Kent Dybvig.
* .
* .
* .
* , Harold Abelson и Gerald Jay Sussman.
на заглавную О сайте10 самыхСловариОбратная связь к началу страницы
© 2008-2014

online
magazines pdf download
download magazine pdf
download ebooks pdf
XHTML | CSS
1.8.11