Введення в scheme

Кен Дікі (переклад Олексія десятник)

Альтернативний погляд на світ

Кожна мова програмування являє собою певний світогляд в поняттях, які він дозволяє (або не дозволяє) використовувати. Ця серія статей описує погляд на світ мови програмування Схема ( «Схематичне світогляд»). Дане світогляд містить безліч сучасних елементів програмування: підтримка різних парадигм програмування, легко поєднувані, багаторазово використовувані абстракції, можливість створення мови, «заточеного» під певне застосування, чітке розходження між переносяться і нестерпними частинами програми, масштабованість, починаючи від окремих утиліт і закінчуючи серйозними програмними системами.

Схема починалася як експеримент в розробці мови програмування для тестування деяких фундаментальних положень в теорії розробки програм. Зараз же вона отримує розташування з боку багатьох відомих університетів (таких, як МТІ - Массачусетський Технічний Інститут) в якості першого досліджуваного мови програмування. Крім того, Схема використовується в промисловості такими компаніями, як DEC. Texas Instruments. Tektronix. Hewlett Packard і Sun.

Що таке Схема?

Схема - це маленький, виключно «чистий» мова, який (що дуже важливо!) Приємно використовувати. Схема розроблялася таким чином, щоб мале число універсальних конструкцій можна було легко використовувати в різних стилях програмування: функціональному, об'єктно-орієнтованому і імперативний. Стандарт мови займає всього близько 50 (!) Сторінок, включаючи формальне визначення семантики. Схема ґрунтується на формальній моделі лямбда-обчислень, так що тут повно особливостей, зручних для теоретиків; це дозволяє досить легко побудувати розумні кошти розробки програм.

Схема має механізм лексичних областей видимості, однорідні правила обчислень, і однорідне розуміння типів даних. Схема не має понять покажчика, неініціалізованих змінних, спеціальних циклічних конструкцій або детального управління зберіганням даних.

На що ж схожа Схема? Ну, вона сильно змахує на Лісп. Нехай це вас не лякає: зовнішній вигляд Схеми можна змінити (і цим ми займемося в майбутньому). Що дійсно важливо, так це ті концепції, які покладені в основу Схеми, і можливості їх використовувати. Отже, давайте порівняємо Схему і який-небудь «класичний» мову програмування - скажімо, Сі. Можливо, ви вже знаєте, що Схема використовує префіксних запис, на відміну від інфіксной записи Сі:

У Схемі всі типи даних еквівалентні. Все, що можна зробити з одним типом даних, можна зробити з усіма іншими. Це різко відрізняється від більшості мов програмування, в яких є спеціальні операції для деяких типів даних, а застосування деяких інших типів даних спеціально обмежена. У більшості мов, наприклад, числа мають особливі права: вони можуть бути використані без привласнення ним імен (уявіть, що, наприклад, що в Бейсике кожному число треба було б призначати ім'я перед його використанням!). Функції, навпаки, обмежені: вони зобов'язані мати ім'я.

У Схемі, функції без імені створюються за допомогою ключового слова lambda:

(Lambd a (x) (* x x)); результат - функція!

(Define sq (lambda (x) (* x x))

((Lambda (x) (* x x)) 9); 27

((If (foo? X) * +) 2 3 4); якщо (foo? x) істинно.

(Define (curried-add x) (lambda (y) (+ x y))

(Define add3 (curried-add 3)); add3 - функція

((Curried-add 3) 7); 10

- змінна може містити значення будь-якого типу;

- імена позначають значення; імена не обов'язкові;

- вираз - одна або кілька форм між дужками;

- для того, щоб обчислити вираз, треба спочатку обчислити значення всіх форм між дужками, а потім застосувати значення першої форми до всіх інших; вкладені вирази також вважаються формами;

- коли функція обчислюється, вона «згадує» стан «навколишнього середовища», в якій вона створювалася (так що add 3 згадує, що X дорівнювало трьом в момент її створення, тобто в момент обчислення виразу (lambda (y) (+ xy)) 7)).

(Define sq (lambda (x) (* x x))

Можливі сім видів виразів:

- константи: 'foo # \ Z 3 "рядок"

- застосування процедури: (cube37)

- умова. (If (

(Зрозуміло, в цьому списку перераховані далеко не всі варіанти виразів)

Схема має звичайний набір типів даних:

- літери (character): # \ a # \ A \ #space # \ newline

- рядки (string): "рядок тексту"

- масиви (вектори - vector): # (1 2 "рядок" # \ x5)

- списки (list): (a little (list of) (lists))

- числа (numbers): 47 1/3 2.3 4.3e14 1 + 3i

- логічні значення (boolean. соотв. істина і брехня): # t # f

- порти (наприклад, відкриті файли або мережеві з'єднання)

- символи (symbol. зазвичай використовуються для позначення змінних): this-is-a-symbolfooa32> adfasf23 @ # $%!<

- вектор може складатися з будь-яких об'єктів даних;

- символ може містити букви англійського алфавіту, цифри і літери + -. * / <=>. $% _

- символи не чутливі до регістру букв (тобто символи SYMBOL і SyMboL ідентичні)

- символи використовуються для позначення змінних (але не тільки для цього!)

- за угодою (просто для зручності) предикати (вираження перевірки значень) закінчуються на знак питання, а «небезпечні» (змінюють значення змінної) функції закінчуються на знак оклику

Числа особливо цікаві в Схемі: кожне ціле (integer) є дробом (rational), дріб - дійсним числом (real), а дійсне число - комплексним (complex). Числа класифікуються за ознакою точності (точне або приблизне - exact / inexact):

Філософія Схеми

Одна з приємних особливостей Схеми, яка спочатку багатьох бентежить - відсутність обмежень. Схема дуже виразна: програміст може «сказати» на цій мові одну думку (дія) абсолютно різними способами. У Схемі програміст має свободу - і відповідальність - «говорити» в точності так, як хоче. У багатьох інших мовах програмування часом доводиться шукати якісь «обхідні шляхи», щоб отримати від них необхідну, а в Схемі це просто не потрібно.

Для «розігріву» давайте побудуємо структуру даних «пара» (pair). Пара складається з двох елементів, одержуваних за допомогою функцій доступу FIRST і SECOND (відповідно ПЕРШИЙ і ДРУГИЙ). Функція створення пари буде називатися PAIR. Повинні бути виконані наступні співвідношення: (first (pair12)) дорівнює 1, (second (pair1 2)) дорівнює 2. Для знаючих Лисп в цьому немає нічого незвичайного. Однак скількома різними способами ми можемо реалізувати це тріо: PAIR. FIRST. SECOND?

; можна і просто (define PAIR vector). але так стилістично краще

(Define (PAIR a b) (vector a b))

(Define (FIRST aPair) (vector-ref aPair 0))

(Define (SECOND aPair) (vector-ref aPair 1))

; 2. Ф ункції вибору

; Не забувайте про лексичну область видимості:

; кожна функція, створювана функцією PAIR, буде пам'ятати

; значення a і b в момент створення

(Define (PAIR a b) (lambda (bool) (if bool a b)))

(Define (FIRST aPair) (aPair #t))

(Define (SECOND aPair) (aPair #f))

; 3. Передача повідомлень

(Define (PAIR (a b)

(Case msg; конструкція case для кожного значення msg

; виконує відповідну дію

((First) a); якщо повідомлення - символ first.

; апостроф ( ') перед символом забороняє обчислювати його значення

; (Без нього була б помилка «відсутній змінна»)

(Define (FIRST aPair) (aPair 'first))

(Define (SECOND aPair) (aPair 'second))

; 4. Псевдоніми: в Схемі вже є тип даних «пара»!

(Define PAIR cons)

(Define FIRST car)

(Define SECOND cdr)

; 5. Лямбда-функції (передача функцій як параметрів іншим

(Define (PAIR a b) (lambda (proc) (proc a b)))

(Define (FIRST aPair) (aPair (lambda (x y) x)))

(Define (SECOND aPair) (aPair (lambda (x y) y)))

Сенс всього вищенаведеного: навіть найпростіші речі можна зробити абсолютно по-різному.

Тепер, коли ми розігрілися, давайте поглянемо на старий добрий факторіал (нагадую: факторіал - твір всіх цілих чисел від 1 до даного числа).

Для початку - рекурсивне визначення:

Коли я (Кен Дікі) вперше вивчав рекурсивні визначення на кшталт цього, найскладнішим було зрозуміти, як приховане стан функції зберігається на стеку. Невелике перетворення коду робить стек видимим.

; функція identity просто повертає свій аргумент

(Define (identity value) value)

; збережемо форму функції fact

; (Тепер вона всього лише викликає функцію cfact)

(Define (fact n) (cfact n identity))

; А функція cfact - обчислює факторіал

(Define (cfact n k)

(Lambda (result) (k (* n result))))))

Функція cfact - версія функції fact. використовує «продовження». Замість повернення результату кожен раз функція отримує додатковий аргумент, «продовження», який і викликається з результатом обчислень функції.

Давайте подивимося, як буде змінюватися виклик (fact3):

(Fact 3) стає (cfact 3 identity)

(Cfact 3 identity) стає

(Identity (* 3 result)))); k '

Це в свою чергу перетворюється в

(Lambda (result ') ;; k' '

(Identity (* 3 result))); функція k '

(* 2 result ')); аргумент, який передається k '

((Lambda (result ') ;; k' '

(Identity (* 3 result))) (* 2 result '))

((Lambda (result) (identity (* 3 result))) (* 2 1))

(Identity (* 3 (* 2 1)))

Це - не приклад того, як з простих речей можна легко зробити жахливо складні. Навіщо ж ми так зробили? Сенс в тому, що ми можемо управляти тим, що зазвичай заховано на стеку. Це дозволяє робити деякі цікаві речі. Ми можемо ігнорувати одне «продовження» і використовувати замість нього іншого. Ми можемо контролювати, наприклад, тривалі обчислення. Якщо вони займають більше часу, ніж очікувалося, ми можемо зберегти наше продовження ( «де ми зараз») і спробувати інший підхід до вирішення завдання. Якщо новий варіант ще гірше, ми можемо повернутися до збереженого «продовження» і продовжити обчислення. Ми, звичайно, зможемо зберегти і наші спроби зробити краще на той випадок, якщо дійсно вийшло краще ...

Таким чином, використання «продовжень» дозволяє будувати дуже цікаві, гнучкі керуючі структури. Давайте тепер подивимося на факторіал з іншого боку. Кожен рекурсивний виклик просто кладе на стек ще один множник. Але ми можемо і не використовувати стек, якщо введемо додаткову переменную- «акумулятор». Зрозуміло, перед початком обчислень акумулятор повинен бути рівний 1 (так як x * 1 = x).

; визначаємо функцію обчислення факторіала з акумулятором

(Define (cfact _n acc)

(Cfact (- _n 1) (* _n acc))

; викликаємо цю функцію з акумулятором, рівним 1

Зовні ця функція здається рекурсивної. Однак це не так. У Схемі є поняття «хвостовій рекурсії», яка робить непотрібними звичайні цикли. Кожна функція, яка викликає саму себе в «хвостовій» позиції (тобто як останню дію) - це просто цикл.

Отже, ми перетворили рекурсивную функцію в ітеративну, циклічну. Є формальний (теоретично «правильний») спосіб такого перетворення; але одна приємна особливість Схеми в тому, що ці перетворення прості і наочні. Правильно працюючі програми можуть бути написані швидко, навіть якщо спочатку вони можуть повільно працювати і вимагати багато пам'яті. Після налагодження алгоритму їх нескладно перетворити в набагато більш ефективні - і теж правильно працюють! Перетворення програм для досвідченого програміста на Схемі стає другою натурою.

Схема має кілька важливих переваг над іншими мовами. Її елегантно проста, однорідна структура і тривіальний синтаксис дозволяє уникати різних «особливих випадків». Її виразність дозволяє не витрачати час на пошук обхідних шляхів: програміст може сконцентруватися на тому, що йому потрібно зробити, але не на тому, як це зробити. Схема підтримує кілька стилів програмування, включаючи модне сьогодні об'єктно-орієнтоване, - так що програміст не повинен пристосовуватися під Схему; він може використовувати той стиль або спосіб вирішення завдань, до якого звик. Формальність Схеми робить доказ правильності програм набагато простішим. Потужні засоби абстрагування дозволяють відокремити частини програми, які можна повторно використовувати, від частин, «заточених» під конкретну проблему / реалізацію мови / операційну систему. Легкість поєднання різних функцій і створення на їх основі нових конструкцій дозволяє створювати цілі бібліотеки добре налагоджених, універсальних компонентів.

Інакше кажучи, якщо ви хочете писати складні, коректні програми, але не хочете витрачати на це роки, Схема - те, що потрібно для успіху!

Короткий список найбільш відомих реалізацій Схеми.

Chez Scheme і MacScheme - одні з кращих комерційних реалізацій; проте існує безліч безкоштовних інтерпретаторів і компіляторів Схеми як для навчальних цілей, так і для серйозної роботи.

Одна з кращих систем для Windows і Linux - MzScheme. і побудовані на її основі MrEd (система створення переноситься графічного інтерфейсу користувача) і DrScheme (мабуть, найзручніша середовище розробки програм з існуючих).

Отже, ось неповний список реалізацій Схеми:

Схожі статті

Попередня ◈ Наступна