ЛІСП: урок другий

[Python]

Уроки ЛІСП
Урок 1
Урок 2
Обговорення

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

Оскільки функції та інші алгоритмічні конструкції, як правило, складаються більш ніж з одного рядка, їх зручніше описувати не безпосередньо в REPL (хоча це теж можливо, а інколи навіть зручніше), а в окремому файлі. Розширення може бути довільним, але як правило це .scm для Scheme, .clj для Clojure, .lsp для Common Lisp. Якщо ми хочемо поекспериментувати з функціями з цього файла, його можна завантажити в інтерактивне середовище:
   (load "ІМ'Я_ФАЙЛА")       ;у Scheme
   (load-file "ІМ'Я_ФАЙЛА")    ;у Clojure
Або ж ми можемо запустити роботу своєї програми без участі REPL — для цього в командному рядку можна ввести:
   clojure ІМ'Я_ФАЙЛА
чи, у випадку SISC Scheme,
   sisc ІМ'Я_ФАЙЛА
В інших реалізаціях деталі запуску можуть відрізнятись, але принцип той же. Інтерпритатор запуститься, виконає програму, після чого завершить свою роботу.

Функції. Оскільки лісп належить до мов функціонального програмування, було б дивно, якби в ньому не було користувацьких функцій. Синтаксис опису функцій у різних ліспах дещо відрізняється.
Scheme:
   (define (ІМ'Я_ФУНКЦІЇ ПАРАМЕТРИ) ТІЛО)
Параметри — прості ідентифікатори (один чи більше, або жодного), розділені між собою пробілами. Тіло функції — один або декілька виразів, значення останнього з яких повертається як результат. Використання кількох виразів у тілі функції буває потрібне, якщо вони викликають якусь побічну дію: вивід на екран чи у файл, перевизначення змінної тощо.

В першому уроці я згадував про функції зі змінною кількістю параметрів. Щоб описати таку функцію, останній аргумент у списку формальних параметрів слід відокремити крапкою від попередніх (крапка має оточуватися пробілами з обох боків). Якщо ми викличемо таку функцію, значенням цього параметра буде список фактичних параметрів, що залишились укінці (чи просто список фактичних параметрів, якщо це єдиний формальний параметр). Приклад:
   (define (f . args) (cons 0 args))
Робить те ж саме, що й функція list, але дописує 0 перед початком списку.

У Clojure синтаксис опису функції дещо відрізняється:
   (defn ІМ'Я_ФУНКЦІЇ [ПАРАМЕТРИ] ТІЛО)
Синтаксис списку параметрів також має деякі відмінності. Зкрема, для змінної кількості фактичних параметрів слід використовувати не крапку, а амперсанд. Зверніть також увагу на квадратні дужки замість круглих. У Clojure цей тип дужок використовується для опису векторів (подібно до того, як круглі дужки утворюють список), але в даному випадку ми їх можемо розглядати як елемент синтаксису функцій та деяких інших конструкцій.

Якщо треба передати функції фактичні параметри, кількість яких невідома наперед, можна скороистатись функцією apply:
   (apply ФУНКЦІЯ СПИСОК)
Список — змінна чи вираз спискового типу, кожний елемент якого передається функції як окремий параметр.

Це далеко не всі можливості ліспівських функцій, але йдемо далі.

Глобальні змінні. Оголошуються вони наступним чином:
Clojure:
   (def ЗМІННА ЗНАЧЕННЯ)
Scheme:
   (define ЗМІННА ЗНАЧЕННЯ)
LISP використовує динамічну типізацію, тому тип не вказується (втім, у багатьох реалізаціях є можливість вказувати тип явно з метою оптимізації). Змінна може мати будь-який тип, у т.ч. функціональний. Власне, синтаксис оголошення функцій розгортається в def чи define з анонімною функцією як значенням:
   (def    ІМ'Я_ФУНКЦІЇ (fn     [ПАРАМЕТРИ] ТІЛО)) ;Clojure
   (define ІМ'Я_ФУНКЦІЇ (lambda (ПАРАМЕТРИ) ТІЛО)) ;Scheme
Глобальні змінні в функціональному програмуванні — далеко не найпотрібніша річ (власне кажучи, присвоєння нового значення змінній вважається поганим стилем, на рівні goto в алгоритмічних мовах. Хоча інколи це необхідно, і засоби для цього також існують — наприклад, set! у Scheme).
   
Локальне зв'язування (let). Приблизно те ж саме, що й локальні змінні в інших мовах. Однак, є деякі відмінності. Насемперед, те, що таким змінним значення присвоюється при входженні в блок let, і в межах цього блоку, як правило, не переприсвоюється. Якщо в тілі let буде ще один let зі змінною з таким же ім'ям, як і в зовнішньому блоці, ці змінні вважатимуться двома різними.
Синтаксис Scheme:
   (let ((ЗМІННА ЗНАЧЕННЯ)
         (ЗМІННА ЗНАЧЕННЯ)
        .....
         (ЗМІННА ЗНАЧЕННЯ))
       ТІЛО)
Синтаксис Clojure:
   (let  [ЗМІННА ЗНАЧЕННЯ
          ЗМІННА ЗНАЧЕННЯ
         .....
          ЗМІННА ЗНАЧЕННЯ]
       ТІЛО)
Результатом, який повертає let, є значення останнього виразу в його тілі. У Scheme є декілька різновидів let, що відрізняються можливістю використання одних змінних у значеннях, присвоюваних іншим. Так, звичайний let узагалі не дозволяє змінним бачити одна одну, тоді як у let* кожна наступна змінна бачить усі попередні. Кложурний let є аналогом схемівського let*. Ще одна конструкція — letrec — дозволяє описати серію локальних функцій, що посилаються одна на одну. У Clojure аналогом letrec є letfn, яка має дещо інший синтаксис.

Поданий вище синтаксис let дещо спрощений. Детальніше ми його розглянемо в наступних уроках.

[Python]

   
Вибір, або галуження. Найпростіший спосіб зробити галуження в програмі — використати форму if:
   #;> (if 4 4) 'equal 'different)
   equal
   #;> (if (= 4 5) 'equal 'different)
   different
Як бачимо, ця синтаксична конструкція реалізована в вигляді S-виразу з трьома параметрами, перший з яких є умовою, другий — гілкою, яка обчислюється, якщо умова виконується, третій — якщо не виконується. Третій парметр можна пропустити — тоді, в разі хибної умови, ми отримаємо дещо різний результат у різних ліспах. У Scheme можуть існувати вирази, що не повертають някого значення, і if з однією гілкою спрацьовує як саме такий вираз:
   #;> (if (= 2 5) 'equal)
   #;> (if (= 2 2) 'equal)
   equal
   #;>
У Clojure (і так само в Common Lisp) кожен вираз повертає значення, і якщо результат не вказати, ним буде nil — пусте значення:
   user=> (if (= 2 5) 'equal)
   nil
   user=> (if (= 2 2) 'equal)
   equal
   user=>
Конструкція if є таким же виразом, як і будь-який інший, а тому може використовуватись усередині інших виразів:
   #;> (* 3 (if (= 0 0) 1 2))
   3
   #;> (* 3 (if (= 0 77) 1 2))
   6
Якщо нам треба перевірити декілька умов, також можна використати конструкцію cond, синтаксис якої у Scheme та Clojure дещо різний. Scheme:
   (cond (УМОВА1 => РЕЗУЛЬТАТ1)
      (УМОВА2 => РЕЗУЛЬТАТ2)
      ....
      (УМОВАn => РЕЗУЛЬТАТn))
Clojure:
   (cond УМОВА1 РЕЗУЛЬТАТ1
      УМОВА2  РЕЗУЛЬТАТ2
      ....
      УМОВАn  РЕЗУЛЬТАТn)
      
Порівняння та логічні операції. Істина та хибність. Операції порівняння (=, >, <, >=, <= та деякі інші) можуть мати два аргументи або більше, що інколи досить зручно. Наприклад, якщо за умовою змінна лежить у проміжку від 2 до 5, це можна записати як (<= 2 x 5). Всі ці операції можуть працювати з числами. Що ж до інших типів (імена, списки, рядки, літери тощо), ситуація з ними дещо складніша. Clojure дозволяє порівнювати їх за допомогою =, але решта операцій порівняння працюють лише з числами, тому змінні нечислових типів перевіряють за допомгою функції compare, числовий результат якої далі порівнюється з нулем. Scheme не використовує для нечисел навіть =, але має чималий арсенал функцій порівняння для кожного типу. З універсальних функцій порівняння слід згадати equal?, яка добре підходить для перевірки тотожності будь-яких даних (eq? та eqv? роблять приблизно те ж саме, але мають деякі обмеження й відмінності — зокрема, вони можуть перевіряти не значення, а ідентичність об'єктів у пам'яті).

Результатом порівняння може бути істина чи хибність (#t, #f — для Scheme; true, false — для Clojure; T, NIL — для Common Lisp). Крім того, замість істини може використовуватись будь-яке значення інших типів. У Clojure також існує спеціальне значення nil, яке мало чим відрізняється від false й так само може використовуватись у ролі хибності.

Логічні операції: and, or, not.  Логічні «і», «або», «не» — тут мало що можна додати. Для and та or кількість аргументів може бути довільною; крім того, ці дві операції реалізовані не як функції, а як макроси, і завдяки цьому при обчисленні їх значення кінцеві аргументи можуть узагалі не обчислюватись, якщо попередніх аргументів достатньо для отримання результату. На це слід звертати увагу, якщо в процесі перевірки викликаються функції, що мають побічну дію. Результатом and та or є останній обчислений аргумент (який може бути не лише логічного типу), результатом not — істина чи хибність.

Хвостова рекурсія. Маючи в своєму розпорядженні такі засоби, як функція та вибір, неважко побудувати з них аналог циклу. Щоправда, тут виникає невеличка складність: при кожному виклику функція забирає частину стеку для своїх потреб і звільняє її лише після свого завершення — таким чином, при достатньо високому рівні вкладеності рекурсії, функція може переповнити стек, що призведе до збою програми. На щастя, цю проблему можна обійти (хоч і не у всіх випадках).
Якщо виклик функції є останньою дією в тілі функції, Scheme його оптимізує, звільняючи пам'ять, яку використовує поточна функція, не після виклику, а перед ним. Таким чином, навіть якщо це буде нескінченна рекурсія, стек ніколи не переповниться. Це не стосується, однак, випадків, коли функція мусить виконати ще якісь дії після виклику — в цьому разі, оптимізації не буде. На практиці це означає, що рекурсивний виклик бажано розміщувати у «хвостовій позиції»: або безпосередньо останнім виразом у тілі функції, або в конструкції вибору (if, cond — в одній з гілок, не в умові), яка йде останньою в тілі функції, або останньою дією в тілі останнього let, і т.д.

Описувати кожен цикл як окрему функцію не завжди зручно. Альтернативним варіантом є т. зв. іменований let:
   (let ІМ'Я
         ((ПАРАМЕТР ЗНАЧЕННЯ)
         (ПАРАМЕТР ЗНАЧЕННЯ)
         ....
         (ПАРАМЕТР ЗНАЧЕННЯ))
      ТІЛО)
Вказане ім'я можна використати в тілі аналогічно імені функції, щоб рекурсивно викликати цей блок, задавши нові значення параметрів. Ім'я в іменованому let доступне лише зсередини його тіла.

Clojure відрізняється від Scheme тим, що неявна хвостова оптимізація в цій мові відсутня. Однак, хвостову рекурсію можна задати явно, використавши замість імені функції слово recur. Такий рекурсивний виклик обов'язково має бути у хвостовій позиції, інакше це помилка.
Існує й аналог іменованого let — форма loop:
   (loop
         [ПАРАМЕТР ЗНАЧЕННЯ
         ПАРАМЕТР ЗНАЧЕННЯ
         ....
         ПАРАМЕТР ЗНАЧЕННЯ]
      ТІЛО)
Як і в випадку з хвостовим рекурсивним викликом функції, у тілі loop використовується recur.

Спробуймо, для прикладу, обчислити факторіал, використовуючи рекурсію й галуження:
   (defn fac [ x ]
      (if (> x 1)
         (* x (fac (- x 1)))
         1))
Однак, така функція використовуватиме не хвостову рекурсію, а звичайну: рекурсивний виклик у ній знаходиться не в хвостовій позиції, а в математичному виразі, і якщо ми спробуємо зробити хвостову оптимізацію, просто замінивши fac на recur, транслятор видасть нам помилку. Без recur функція буде цілком роботоздатною, але відсутність хвостової оптимізації означатиме, що при кожній ітерації функція забиратиме трохи пам'яті зі стека, і при достатньо великому значенні аргумента стек може переповнитись.

Кращий варіант (функція, що обчислює факторіал, з хвостовою оптимізацією):
   (defn fac [ x ]
      (loop [res 1, i x]
         (if (> i 1)
            (recur (* res i) (- i 1))
            res)))

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

Як нам підказує слово loop (англ. цикл), конструкція з хвостовою рекурсією — не що інше, як цикл. Це не єдиний засіб для організації циклів, але один з найважливіших, особливо якщо йдеться про Scheme. У Clojure, як ми побачимо в наступних уроках, здебільшого зручніше використовувати не loop+recur, а функції для роботи з лінивими послідовностями.

Завдання.
1) Перепишіть приклад функції факторіала з Clojure на Scheme.
2) Спробуйте написати функцію, що обчислює число Фібоначчі з заданим номером. Зробіть це з хвостовою оптимізацією.
3) Напишіть функцію, що отримує змінну кількість параметрів і повертає їх кількість як результат.

[arseniiv]

(define (fac x)
  (let loop ((res 1) (i x))
    (if (> i 1)
      (loop (* res i) (- i 1))
      res)))

(define (fib x)
  (let loop ((f1 0) (f2 1) (i x))
    (if (> i 1)
      (loop f2 (+ f1 f2) (- i 1))
      f2)))

(define (param-count . args)
  (let loop ((res 0) (li args))
    (if (null? li)
      res
      (loop (+ res 1) (cdr li)))))

[Demetrius]

Мої відповіді.

(define (fac x)
  (let loop ((res 1) (i x))
    (if   (> i 1)
      (loop (* res i) (- i 1))
      res)))

(define (fib n)
  (let loop ((i 0) (f0 0) (f1 1))
    (if (= i n)
      f0
      (loop (+ i 1) f1 (+ f0 f1)))))

(define (count . args)
  (let loop ((res 0) (current args))
    (if (equal? current '())
      res
      (loop (+ res 1) (cdr current)))))

(defn fib [n]
  (loop [i 0, f0 0, f1 1]
    (if (= i n)
      f0
      (recur (+ i 1) f1 (+ f0 f1)))))

(defn count-args [& args]
  (loop [res 0, current args]
    (if (= current '())
      res
      (recur (+ res 1) (rest current)))))

[Demetrius]

Недочекавшися продовження (), узявся за читання SICP.

[arseniiv]

Кстати, надеюсь, мои уроки пока мало кто читает, потому что я пока не могу продолжать.

[Python]

Жаль. Що ж, будемо чекати, коли Ви зможете продовжити...