Літо Sexps!

Вступ

Привіт усім! Сподіваюся, у всіх усе гаразд.

Останні кілька тижнів в Exercism були справді захопливими: ми запустили Exercism Premium та Exercism Insiders. У нас також були чудові зустрічі зі спільнотою, а ще багато покращень сайту вже розгорнуто, і ще більше зʼявиться незабаром. Зараз є багато приводів для радості, але найбільший із них - це те, що ми ввійшли в шостий місяць #12in23! Літо S-виразів, а якщо коротше й милозвучніше - Літо секспів.

Як завжди, до мене приєднується мудрець світу програмування, Ерік.

Отже, цього місяця у нас пʼять мов: Clojure, Common Lisp, Emacs Lisp, Racket і Scheme. Кожна з них є діалектом мови Lisp, тож замість того, щоб надто зосереджуватися на окремих мовах у цьому відео, ми трохи більше поговоримо про сам Lisp і про те, що робить його унікальним. А наприкінці коротко пройдемося мовами.

Але спершу трохи організаційних питань! Щоб отримати значок Літа секспів, треба виконати будь-які пʼять вправ однією з цих мов протягом червня.

Значки

Є також річний значок 12in23. Щоб отримати його, треба розвʼязати пʼять із наших обраних вправ цією мовою. Якщо ми дивимося це після червня, цю частину можна виконати будь-коли протягом року, тож ми нічого не пропустили. Оскільки багато людей ніколи не працювали з Lisp, ми намагалися обрати відносно прості вправи, які дають уявлення про те, що являє собою мова Lisp.

• Високосний рік: попрацювати з булевими умовами та правдивістю (а за бажанням - і з лексичною областю видимості)
• Двоє за одного: форматувати рядок тексту (англ. string) і працювати з необовʼязковим параметром
• Різниця квадратів: викликати функції, визначені користувачем, і робити обчислення в префіксній нотації
• Імʼя робота: працювати з випадковістю, атомами та структурованими даними
• Відповідність дужок: використати рекурсію, щоб перевірити рядок тексту

Усі ці вправи та вправи за попередні місяці можна знайти на сторінці #12in23.

Огляди

Отже, мови на основі Lisp. Мабуть, варто почати з того, щоб трохи зрозуміти сам Lisp. Почнімо з короткого вступу до Lisp загалом.

Lisp

• Передусім зауважмо, що Lisp - одна з найстаріших мов.

• Його створив Джон Маккарті в MIT 1958 року, коли компʼютери ще займали цілі кімнати від підлоги до стелі 🙂

• Назва Lisp розшифровується як LISt Processing (або LISt Processor), що підкреслює важливість структури даних «список».

• Його створювали з метою досліджень у галузі штучного інтелекту.

• Lisp ґрунтувався на лямбда-численні, яке винайшов Алонзо Черч: це формальна система для опису обчислень у математиці (спрощено).

• Це неймовірно впливова мова, і причин тому багато:

• Це друга найстаріша мова програмування високого рівня, яку досі широко використовують (після Fortran)

• Це була перша високорівнева функціональна мова програмування, яка започаткувала багато можливостей, що ми зараз повʼязуємо з функціональним програмуванням.

• Зауважмо, що Lisp усе одно підтримував імперативне програмування

• Це була найперша мова зі збирачем сміття, який позбавляв автора необхідності вручну керувати памʼяттю

• Порівняно небагатий синтаксис і відносно проста семантика роблять її чудовою для навчання.

• Тому Lisp (точніше, один з його діалектів) часто використовують для навчання програмування

• Він породив (і досі породжує!) безліч мовних діалектів (про ті, які підтримує Exercism, ми поговоримо).

• Іншими словами, у дереві мов програмування є окрема гілка для Lisp-подібних мов (так само, як є гілка C-подібних мов).

Коли я нещодавно розмовляв із Саймоном Пейтоном Джонсом, одним з авторів Haskell, він говорив про різницю між мовами, побудованими навколо машин Тюринга, і мовами, побудованими навколо лямбда-числення. Тож якщо нам хочеться дізнатися про це більше, варто подивитися те інтервʼю.

Дужки

У Lisp-мовах багато дужок, але це не обовʼязково погано (так само, як велика кількість фігурних дужок не обовʼязково погана в C-подібних мовах). Lisp-мови побудовані навколо того, що називається S-виразами. S-вираз (скорочено від symbolic expression, також sexpr або sexp, звідси й назва цьогомісячного завдання) - це вираз, яким подають дані. Їх вигадали для першої мови Lisp, і саме вона зробила їх популярними. S-вираз може мати одну з двох форм:

• Атом (наприклад, 'x'). Уявімо їх як невкладені «значення» або листки дерева
• Вираз x . y, де x та y - S-вирази. Уявімо їх як пари, де y може бути наступним елементом списку (якщо він є) або вузлом дерева. Зауважмо, що це рекурсивне означення, яке завершується на рівні листків. Зазвичай для S-виразів цього типу використовують дужки.

S-вирази

S-вирази використовують для подання і даних, і списків у Lisp. Тож щоразу, коли ми визначаємо список, ми використовуємо дужки. Якщо додати до цього той факт, що: список - основна структура даних у Lisp (звідси й назва), у деяких Lisp-мовах це єдина структура даних, то дужок виходить дуже багато. Щоб показати, наскільки списки є центральними, зауважмо: щоб викликати функцію в Lisp, ми створюємо список.

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

• Можна застосувати оператор до багатьох аргументів, не повторюючи його (наприклад, (+ 1 2 3))
• Пріоритет операторів стає явним, бо для виклику іншого оператора все одно доводиться створювати новий S-вираз

Цікаво, що списки використовують навіть для подання вихідного коду, але про це ми поговоримо пізніше.

Загалом більшість Lisp-мов мають досить мінімальний синтаксис і відносно просту семантику, тому їх відносно легко вивчати, і розуміти код теж стає простіше. Мінімальний синтаксис не робить їх менш потужними! Поєднання цих двох речей (мінімальний синтаксис + проста семантика) робить Lisp-мови ідеальними для написання компіляторів та інтерпретаторів. Якщо нам колись захочеться створити власний компілятор, Lisp - гарний варіант для початку!

Круті можливості Lisp

Як уже згадувалося, Lisp-мови всередині використовують ті самі типи даних і структури даних для подання коду. Цю властивість називають гомоіконністю (або кажуть, що мова гомоіконна). Іншими словами, мова є гомоіконною, якщо програму, написану нею, можна обробляти як дані засобами самої мови, а отже, внутрішнє подання програми можна вивести просто з її читання. Часто цю властивість описують так: мова поводиться з кодом як з даними.

Мови

Scheme

• Створена в 1970-х Гаєм Стілом і Джеральдом Сассманом у Лабораторії штучного інтелекту MIT.
• Починалася як спроба зрозуміти модель акторів Карла Гʼюїтта через крихітний інтерпретатор Lisp.
• Саму мову представили в серії дослідницьких AI Memos, які згодом дістали спільну назву Lambda Papers.
• Перший діалект Lisp із лексичною областю видимості (значення перебуває в області видимості лише там, де його визначено) і одна з перших мов із підтримкою продовжень першого класу.
• Офіційний стандарт IEEE і де-факто стандарт під назвою Revised Report on the Algorithmic Language Scheme (RnRS).
• Багато реалізацій: ChezScheme, Guile (обидві підтримує Exercism), MIT/GNU Scheme і Racket
• Дуже мінімальна мова з небагатьма синтаксичними конструкціями, але це вийшло ненавмисно.
• Автори намагалися створити щось складне, але зрештою спроєктували щось набагато простіше, ніж задумували
• Коректна хвостова рекурсія. Ідіоматичний спосіб виконувати ітерацію - через рекурсію.
• Scheme оптимізує хвостові рекурсивні виклики, щоб не витрачати місце у стеку чи інші ресурси. Це означає, що рекурсію можна застосовувати до як завгодно великих даних чи як завгодно довгих обчислень
• Потужні числові типи даних, зокрема раціональні та комплексні числа
• Відкладене обчислення, схоже на проміси.
• Потужна система макросів.
• Гігієнічні макроси зменшують імовірність несподіваних результатів під час визначення макросів.

Common Lisp

• Робота над Common Lisp почалася 1981 року після ініціативи керівника ARPA Боба Енгелмора створити єдиний спільний стандартний діалект Lisp, бо різні вживані діалекти часто були несумісні, а отже, код і знання не можна було передавати
• Перший стандарт опублікували 1984 року, а остаточний - 1994-го (дуже стабільна специфікація)
• Оскільки це стандарт, існують різні його реалізації, як-от Steel Bank Common Lisp (типова для Exercism) і CLisp.
• Є також комерційні реалізації, як-от Allegro CL і LispWorks, а також ECL (Embeddable Common Lisp), яку можна вбудувати в C-програми, і ABCL, яка працює на Java Virtual Machine.
• Визначений стандартом (ANSI INCITS 226-1994), тож код, написаний 30 років тому, досі чудово працює
• Багата й розширювана система типів
• Створений для розробки з образом і REPL, тому дуже добре піддається інтроспекції.

Emacs Lisp

• Розроблена 1985 року, щоб мати ефективну мову для розширення текстового редактора
• Динамічна типізація
• Приблизно 80% Emacs написано мовою Emacs Lisp (20% - мовою C заради швидкодії)
• Дещо відрізняється від інших Lisp-мов:
• Не стандартизована, досі повільно розвивається
• Немає автоматичного усунення хвостових викликів, є підтримка через макрос named-let (який перетворюється на цикл while)
• Типово динамічна область видимості, для нового коду рекомендують лексичну
• Гарна документація просто в редакторі
• Багатоплатформна (працює всюди, де працює Emacs)
• Мову можна вивчати, читаючи код тієї функціональності, якою ми користуємося щодня (ядро Emacs + пакети)
• Підмножина Common Lisp доступна через пакет cl-lib. Emacs Lisp досить мінімалістичний, а Common Lisp має набагато більше можливостей. Пакет cl-lib відкриває доступ до підмножини CL

Racket

• Маттіас Феллайзен заснував PLT Inc., яка в січні 1995 року вирішила створити педагогічне середовище програмування на основі Scheme. Спочатку його назвали PLT Scheme, а згодом перейменували на Racket.
• Крім педагогічного середовища програмування, його задумували як платформу для проєктування та реалізації мов програмування.
• Сучасний LISP, нащадок Scheme
• Підтримує логічне програмування!
• Простий і виразний синтаксис, який ідеальний для початківців і потужний у руках експертів
• Підтримує багато парадигм програмування: функціональне програмування, обʼєктно-орієнтоване програмування, проєктування за контрактом, логічне програмування, метапрограмування
• Вичерпна стандартна бібліотека
• Постачається з DrRacket, повноцінним IDE, створеним для навчання й дослідження без зайвих клопотів
• Чудова документація з безліччю довідкової інформації та прикладів

Clojure

• Розробив Річ Гікі з метою отримати сучасний LISP, який працює на JVM і має чудову конкурентність
• Діалект LISP, але він дещо відрізняється від інших LISP-мов: не підтримує неявну хвостову рекурсію (не хвилюймося, якщо не знаємо, що це) і має більше структур даних, ніж просто списки: словники, множини, вектори. Кожна з цих структур має власний літеральний синтаксис.
• Усі вони також незмінні, але попри це мають чудову швидкодію: пошук за O(log32 n), що «фактично» є сталим часом
• Поліморфізм під час виконання через мультиметоди й протоколи
• Чудова взаємодія з JVM
• Система специфікації даних Clojure Spec (під час виконання, а не під час компіляції) дає змогу описувати структуру даних, генерувати дані, проводити тестування на основі властивостей тощо

Варіанти використання

Scheme

• Використовують в освіті для навчання компʼютерних наук (впливова Structure and Interpretation of Computer Programs використовує Scheme).
• Використовують у ШІ. Використовують як мову сценаріїв, наприклад у GIMP (редакторі графіки), інструментах CAD (Computer Aided Design) і навіть у кіно, де нею написані скрипти керування системою рендерингу фільму Final Fantasy: The Spirit Within

Common Lisp

• Common Lisp використовують у багатьох місцях, наприклад у штучному інтелекті й дослідженнях, а також у комерційних застосунках: NASA написала мовою Common Lisp програмне забезпечення автопілота космічного апарата Deep Space One, Viaweb був написаний мовою Common Lisp, а згодом його придбав Yahoo і перейменував на Yahoo Store!, і перша версія Reddit

Emacs Lisp

• Emacs Lisp використовують у... власне, в Emacs!
• По суті, Emacs - це інтерпретатор Emacs Lisp, діалекту мови програмування Lisp, але з додатковими розширеннями для роботи з текстом

Racket

• Використовують в освіті, оскільки Racket створювали з акцентом на підтримку створення, спрощення й аналізу мов.
• Використовують у дослідженнях: його розширюваний синтаксис і семантика роблять його придатним для проєктування й прототипування нових мов та їхніх можливостей.
• Використовують в іграх: наприклад, Джон Кармак (той самий, з Doom) застосовував його в інтерактивному середовищі сценаріїв для VR, а студія Naughty Dog писала ним скрипти (наприклад, в Uncharted). Hacker News написано мовою Arc, теж Lisp, а сам Arc написано мовою Racket.

Clojure

• Clojure використовують для багатьох різних речей, зокрема 2022 року Docker придбав Atomist, платформу безпеки й автоматизації контейнерів, реалізовану мовою Clojure.
• Найбільший у світі користувач Clojure - Nubank, новий банк, який кілька років тому придбав його і тепер наймає основну команду Clojure.
• Його активно використовують для швидкого прототипування, адже він динамічний і дуже інтерактивний.

Погляд на програмування

Усі ці мови підтримують функціональну, імперативну та символьну парадигми. Деякі з них підтримують ще й ООП, і найяскравіший приклад - Common Lisp.

Lisp-мови переважно динамічні, хоча Racket підтримує статичну типізацію.

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

Scheme

• Мінімалістична, з ясною й простою семантикою і небагатьма способами утворювати вирази.
• Завдяки цьому мову легко вивчати й розуміти код.
• Тому Scheme також часто використовують у багатьох вступних курсах із компʼютерних наук
• Продовження першого класу.
• Продовження - це подання стану програми.
• Продовження можна використовувати для моделювання потоку керування (наприклад, конструкції return) або корутин (які дають змогу виконувати кілька задач одночасно)

Common Lisp

• Розширювана обʼєктно-орієнтована система з програмованими комбінаціями методів (як щодо поєднання методів підкласів і надкласів, так і щодо методів before, after і around, які дають змогу розширювати системи без їх зміни)
• Програмована система умов (надмножина «винятків»), яка дає змогу відокремити виявлення умови від вибору способу її обробки. Система умов гнучкіша за системи винятків: замість того, щоб ділити все на дві частини (код, який сигналізує про помилку1, і код, який її обробляє2), система умов розділяє відповідальність на три частини: сигналізування про умову, її обробку та перезапуск.
• Макроси дають змогу розширювати синтаксис мови, а не лише генерувати шаблонний код. Це допомагає створити мову під предметну область, а не навпаки.

Emacs Lisp

• Чудова підтримка редактора та інтеграція з ним
• Нею можна налаштовувати Emacs прямо під час роботи («наче робиш собі операцію на мозку» :))
• Її можна використовувати в пакетному режимі, де доступні всі можливості редактора щодо обробки тексту (як-от буфери й команди переміщення)

Racket

• Потужна система макросів. На ній побудований синтаксичний цукор на кшталт threading-макросів. Макроси також гігієнічні, а це відповідь на просте запитання: макрос генерує код, який потрапляє в інше місце. Коли цей код виконується, як нам визначити привʼязки ідентифікаторів усередині? Гігієнічні макроси зменшують імовірність несподіваних результатів під час визначення макросів.
• Орієнтована на мови.
• Racket постачається з інструментами, щоб написати власну мову програмування чи DSL на основі макросів Racket.
• Кілька вбудованих мов, як-от typed Racket (з підтримкою статично перевірених анотацій типів), datalog (мова, схожа на Prolog), яку підтримує IDE DrRacket, і scribble, інструмент для створення текстових документів у форматі HTML або PDF
• REPL - центральна частина процесу розробки, а не лише місце, щоб щось спробувати чи зазирнути в документацію

Clojure

• Потужна система макросів.
• На ній побудований синтаксичний цукор на кшталт threading-макросів
• REPL - центральна частина процесу розробки, а не лише місце, щоб щось спробувати чи зазирнути в документацію

Що спробувати

• Якщо ми ніколи не пробували Lisp, Scheme і Racket будуть чудовими варіантами, адже в обох дуже мінімальний синтаксис.
• Водночас і Common Lisp, і Clojure мають режим навчання, тож саме вони, ймовірно, найкращі для навчання на Exercism.
• Якщо ми вже користуємося Emacs, Emacs Lisp - природний вибір.
• Так само, якщо ми користуємося мовою на JVM, Clojure - природний варіант.
• Emacs Lisp (через Emacs), Clojure (через IntelliJ) і Racket (через DrRacket) мають чудову підтримку в IDE.
• Для Common Lisp і Scheme, звісно, теж є хороші IDE.
• Якщо нам потрібен справді багатофункціональний Lisp, Common Lisp, Clojure і Racket дуже обʼємні
• Якщо нам потрібен дещо інший Lisp, у Clojure досить унікальний для Lisp синтаксис.
• Якщо нас цікавлять макроси й метапрограмування, то всі вони, по суті, хороші варіанти! Але якщо ми хочемо створювати нові мови, то Racket тут особливо гарний

Звісно, якщо маємо час, я б радив спробувати кілька! І ще: не лякаймося дужок! Я знаю, що сам їх боявся, і саме тому довго відкладав вивчення Lisp. Але ми швидко до них звикнемо і, можливо, навіть почнемо їх цінувати, як я. Насправді я тепер люблю Lisp-мови: мінімальний синтаксис, проста семантика, і водночас вони дуже виразні.