НОУ ІНТУІТ,Лекція, Інтерпретатор

Інтерпретація або універсальна функція - це функція, яка вміє обчислювати значення будь-якої форми, включаючи форми, що зводяться до обчислення довільної заданої функції, що застосовується до представлених у цій формі аргументів, за доступним описом даної функції. (Звичайно, якщо функція , яка має інтерпретуватися, має нескінченну рекурсію, то інтерпретація повторюватиметься нескінченно.)

Визначимо універсальну функцію eval від аргументу - виразу, що є довільною формою мови Лісп.

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

Атомарний вираз зазвичай розуміється як змінна. Для нього слід знайти пов'язане з ним значення. Наприклад, можуть бути змінні види "x", "elem", зміст яких залежить від контексту, в якому вони обчислюються.
Константи, представлені як аргументи функції QUOTE , можна витягти зі списку її аргументів. Наприклад, значенням константи (QUOTE T) є атом T, який зазвичай символізує значення "істина".
Умовний вираз вимагає спеціального алгоритму для пошуку справжніх предикатів та вибору потрібної гілки. Наприклад, інтерпретація умовного вираження

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

Інші форми виразів розглядаються за загальною схемою як список із функції та її аргументів. Зазвичай аргументи обчислюються, а потім обчислені значення передаютьсяфункції інтерпретації її визначення. Так забезпечується можливість написання композицій функцій. Наприклад, у виразі (first (CAR x)) внутрішня функція CAR спочатку отримає як свій аргумент значення змінної x , а потім свій результат передасть як аргумент зовнішньої функції first .
Якщо функція представлена своєю назвою, то серед назв різняться імена вбудованих функцій, такі як CAR, CDR, CONS і т.п., і імена функцій, введених у програмі, наприклад, first. Для вбудованих функцій інтерпретатор сам знає як знайти їх значення за заданими аргументами, а для введених у програмі функцій - використовує їх визначення, яке знаходить на ім'я або контекст.
Якщо функція використовує лямбда-конструктор, то, перш ніж її застосовувати, знадобиться пов'язувати змінні з лямбда-списку зі значеннями аргументів. Функція, що використовує лямбда-конструктор,

залежить від одного аргументу, значення якого має бути пов'язане зі змінною x. У визначенні використовується вільна функціональна змінна first , яка має бути визначена більш зовнішньому контексті.

Якщо подання функції починається з DEFUN , то знадобиться зберегти ім'я функції з відповідним визначенням так, щоб коректно виконувались рекурсивні виклики функції. Наприклад, попереднє LAMBDA-визначення безіменної функції стає рекурсивним за допомогою спеціальної функції DEFUN, перший аргумент якої – fisrt – ім'я нової функції.

Можна сміливо сказати, що DEFUN замикає вираз , що містить функціональну змінну.

Таким чином, інтерпретація функцій здійснюється як взаємодія чотирьох підсистем:

обробка структур даних (cons, car, cdr, atom, eq),
конструюванняфункціональних об'єктів (lambda, defun),
ідентифікація об'єктів (імена змінних та назви функцій),
управління порядком обчислень (композиції, quote, cond, eval).

Визначення універсальної функції

Універсальна функція eval , яку належить визначити, повинна задовольняти наступній умові: якщо представлена аргументом форма зводиться до функції, що має значення списку аргументів цієї форми, це значення і є результатом функції eval .

Результат застосування "fn" до аргументів "arg1, .argK".

Обчислення

Явне визначення такої функції дозволяє досягти чіткості механізмів обробки Лісп-програм.

Вводимо дві основні функції eval та apply для обробки форм та звернення до функцій відповідно. p align="justify"> Кожна з цих функцій використовує асоціативний список для зберігання пов'язаних імен - значень змінних та визначень функцій. Спочатку цей список порожній.

Повернемося до синтаксичної зведення обчислюваних форм.

Кожній галузі цього зведення відповідає галузь універсальної функції:

Допоміжна функція ev знадобилася, щоб ввести накопичувальний параметр – асоціативний список , в якому зберігатимуться зв'язки між змінними та їх значеннями та назвами функцій та їх визначеннями.

Пояснимо низку пунктів цього визначення.

Перший аргумент ev – форма. Якщо вона - атом , цей атом може лише ім'ям змінної, а значення змінної має вже перебувати у асоціативному списку.

Якщо CAR від форми - QUOTE , вона є константу, значення якої обчислюється як CADR від неї самої.

Якщо CAR від форми-COND, то форма-умовний вираз. Вводимо допоміжну функцію EVCON (визначення її буде дано нижче),яка забезпечує обчислення предикатів (пропозиційних термів) по порядку та вибір форми, що відповідає першому предикату, що набуває значення "істина". Ця форма передається EV для подальших обчислень.

Всі інші випадки розглядаються як список із функції з наступними аргументами.

Допоміжна функція EVLIS забезпечує обчислення аргументів, потім представлення функції та перелік обчислених значень аргументів передаються функції APPLY .

Перший аргумент apply - функція. Якщо вона - атом, існує дві можливості: атом представляє одну з елементарних функцій (car cdr cons atom eq). У разі відповідна галузь обчислює значення цієї функції на заданих аргументах. В іншому випадку цей атом - ім'я раніше заданого визначення, яке можна знайти в асоціативному списку.

Якщо функція починається з LAMBDA , її аргументи попарно з'єднуються зі зв'язаними змінними, а тіло визначення (форма з лямбда-выражения) передається як аргумент функції EV для подальшої обробки.

Якщо функція починається з DEFUN , то її назва та визначення з'єднуються в пару та отримана пара розміщується в асоціативному списку, щоб ім'я функції стало визначеним при подальших обчисленнях. Вони відбудуться як рекурсивний виклик apply , яка замість імені функції тепер працює з її визначенням при повнішому асоціативному списку - в ньому тепер розміщено визначення назви функції. Оскільки визначення розміщується на "горі" стека, воно стає доступним для всіх наступних перевизначень, тобто працює як локальний об'єкт. Глобальні об'єкти, такі як забезпечує псевдо-функція DEFUN у системі Clisp, влаштовані трохи інакше, що буде розглянуто у наступній лекції.