Изчисление в Lisp

Програмата се състои от форми и функции

Формата е символичен израз, чиято стойност може да бъде намерена от интерпретатора. Преди това вече са използвани най-простите форми на езика: константи, променливи, ламбда извиквания, извиквания на функции и техните комбинации. В допълнение към тях бяха разгледани някои специални форми, като'иsetq, които третират своите аргументи по различен начин от нормалните функции. Ламбда израз без действителни параметри не е форма. Изчислените изрази могат да бъдат разделени на три групи:

  1. самоопределени форми. Тези форми, подобно на константите, са обекти, които представляват само себе си. Това са форми като числа и специалните константиtrue,falseиnil, както и символи и низове.
  2. Символи, които се използват като променливи.
  3. Формуляри под формата на списъчна структура, които са:
  1. Функционални извиквания и ламбда извиквания.
  2. Специални форми, включителноsetq,'и много от формите, описани в тази глава, са предназначени да контролират оценката и контекста.
  3. Макро повиквания (ще бъдат обсъдени по-късно).
Всяка форма обаче има свой собствен синтаксис и семантика, основани на един единствен начин на нотация и интерпретация.

Контролните структури на Lisp са форми

В общите процедурни езици, наред с основните действия, има специални контролни механизми за разклоняване на изчисления и организиране на цикли. В Pascal например се използват структуритеif then else,while do,caseи други. Контролните структури на Lisp (ще използваме термина изречение за тях) изглеждат като извиквания на функции. Изреченията ще бъдат написани като изрази в скоби, чийто втори елемент действа като име на контролата.структури, а останалите елементи като "аргументи". Резултатът от изчислението, също като функция, е стойност, т.е. контролните структури са форми. Клаузите обаче не са извиквания на функции и различните клаузи използват аргументи по различен начин. Най-важните синтактични форми от гледна точка на програмирането могат да бъдат разделени на следните групи въз основа на тяхната употреба:Работа с контекст:-'или блокиране на оценка; - извикване на функция и ламбда извикване; - изречениенека.Форма за изпълнение:- стъпка по стъпкаprogn; - паралеленуспореден; - независимавилка.Изчисления с разклоняване:- условни изреченияcond,if.Итерации:- циклични изреченияfor,for*,while,do-while. Вече разгледахме формата', както и ламбда извикването и извикването на функцията. Тези форми са тясно свързани с механизма за дефиниране на функции и тяхното извикване. Останалите форми се използват предимно в тялото на ламбда изрази, които дефинират функции.

LET създава локална връзка

Оценката на функцията създава нови връзки за формалните параметри на функцията за времетраенето на оценката. Нови връзки във формуляр могат също да бъдат създадени с помощта на клаузатаlet. Тази структура изглежда така:

Клаузатаletсе оценява по такъв начин, че първо динамичните променливиm1,m2, … от първия „аргумент“ на формуляра се свързват (едновременно) със съответните стойностиvalue1,value2, … След това стойностите на формуляритеform1,form2, … са изчислен стъпка по стъпка, като стойността на целия формуляр се връща стойността на последния формуляр. Както при функциите, след изчисляването на връзката на динамичните променливиm1,m2, ... се елиминират и всички промени в техните стойности (setq) не се премахватще се вижда отвън. Например:

Форматаletвсъщност е синтактичен вариант на ламбда извикването, при което формалните и действителните параметри се поставят заедно в началото на формуляра:

Тялото на ламбда израз може да се състои от множество форми, които се оценяват стъпка по стъпка и стойността на последната форма се връща като стойност на ламбда извикването. Стойностите се присвояват едновременно на променливи във форматаlet. Това означава, че стойностите на всички променливиmi се изчисляват преди обвързване с формални параметри. Новите връзки на тези променливи все още не са в сила към момента на изчисляване на първоначалните стойности на променливите, които са изброени във формуляра по-късно. Например:

Форма на изпълнение: поетапно, паралелно и независимо

Клаузитеprogn,parallelиforkви позволяват да работите с няколко изчислени форми:

Тези специални форми имат променлив брой аргументи. Клаузатаprognпреминава през тези аргументи и връща стойността на последния аргумент като своя стойност. Клаузатаparallelоценява всички тези аргументи паралелно и не връща нищо, т.е.nil. Клаузатаforkизпълнява формата(nil prognform1 form2 ... formn)за оценка, не очаква резултата си и не връща нищо, т.е.nil. Тези формуляри не съдържат механизъм за дефиниране на вътрешни променливи:

С помощта на форматаletтрябва да зададете обхвата на променливите. Този формуляр ви позволява да използвате формуляри, които се изчисляват стъпка по стъпка и връща стойността на последния формуляр като резултат. Това свойство се нарича имплицитноprogn.

Изчисляване с разклоняване: Условно изречение COND

Клаузатаcondе основното средстворазклонени изчисления. Това е синтактична форма, която ви позволява да контролирате изчисления въз основа на условия, дефинирани от предикати. Структурата на условното изречение е следната:

Предикатитеpiи произтичащите изразиaiмогат да бъдат произволни форми. Стойността на изречениетоcondсе определя, както следва:

  1. Изразитеpi, които действат като предикати, се оценяват стъпка по стъпка отляво надясно (отгоре надолу), докато се срещне израз, чиято стойност не е нитоnil, нитоfalse, т.е. чиято булева стойност е истина.
  2. Изразът, съответстващ на този предикат, се оценява и получената стойност се връща като стойността на цялото изречениеcond.
  3. Ако няма истински предикат, тогава стойността наcondще бъдеnil.
Препоръчително е да използвате символаtrueкато последен предикат и съответният израз винаги ще се оценява в случаите, когато не е изпълнено друго условие. Следният пример дефинира функция, която определя типа на израз с помощта на клаузатаcond:

В условното изречение изразътaiможе да отсъства или често може да има няколко форми на негово място:

Ако изразът не съответства на условието, тогава стойността на самия предикат се връща като резултат от клаузатаcond, ако предикатът е верен. Ако няколко форми отговарят на условието, тогава ако е вярно, формите се изчисляват стъпка по стъпка отляво надясно и резултатът от изречениетоcondще бъде стойността на последната форма (имплицитноprogn). Като пример за използване на условно изречение, нека дефинираме логическите действия на пропозиционалната логикаи,или,не,=>(импликация) и (идентичност):

Изводът може да се дефинира и чрез други операции:

Предикатитеииилиса част от вградените функции на Lisp. Броят на техните аргументи може да бъде произволен.

Клаузитеcondмогат да се комбинират по същия начин като извикванията на функции. Например, предикатътxor, който е верен, ако му бъде даден един твърд аргумент, може да се дефинира по следния начин:

В тази функция, вместо израза на първото условие, отново има изречениетоcond. На мястото, определено от условието, можете да използвате и друго условно изречение, в който случай получаваме условно условие. Такива конструкции много бързо водят до трудни определения.

Друга условна клауза: АКО

Клаузатаcondе най-общата условна структура. Той е критикуван за изобилието от скоби и за факта, че структурата на това изречение е напълно отделена от естествения език. Следователно в системите на Lisp се използват други, в различни отношения по-естествени условни изречения. Но можете да минете само с клаузаcond. В прост случай можете да използвате съвсем естествената форма с няколко скобиif.

(нил акоусловие тогава-форма else-форма) ≡ (нил условие (условие след това-форма) (вярноиначе-форма))

Циклични изчисления: клаузи FOR, FOR*, WHILE и DO-WHILE

В случай на повтарящи се изчисления Lisp използва цикли, известни главно от процедурните езици.

Стъпка по стъпка числа от0дочисло-1се присвояват на локална променлива. За всяка такава стойност се изчислява тялото на цикъла. Например, използвайки изречениетоза*, ние дефинираме функция, която изчисляваnта степен на число (n-цяло число, положително):

Цикълътforсе различава от цикълаfor*по това, че цялото тяло се оценява паралелно и всеки процес има своя собствена променлива. Този цикъл се използва при обслужване на елементите на вектора (ако изчисленията са независими от техния ред). Тези цикли също са дефинирани за обслужване на елементи от списък и низове.

Следният цикълwhileе за преминаване през действия, докато се получат задоволителни резултати.

Цикълътdo-whileсе различава отwhileсамо по реда на проверките и действията:

Итерация чрез итерация или рекурсия

В "чистия" функционален Lisp няма циклични клаузи (for,prognи други), още по-малко оператори за прехвърляне на управление. Той използва само условни условия и дефиниции на рекурсивни или самоизвикващи се функции за програмиране на повтарящи се изчисления. Например рекурсивна версия на функциятаexptможе да се дефинира по следния начин:

Функциятаexptсе самоизвиква, докато аргументътn, използван като брояч, не намалее до единица, т.е. самоn-1пъти. След това стойносттаthisсе връща като резултат от извикването на функциятаexpt. Всеки път, когато дадена стойност се предава на предишното ниво, резултатът се умножава поthis. Така четоваще бъде умножено по себе сиnпъти. Дефиницията на рекурсивната функцияexptе по-кратка и по-добре отразява същността на функцията, отколкото версиите, базирани наfor*. Нека разгледаме друга функция, която е просто дефинирана чрез рекурсия - факториел (факториелът е произведението на дадено число от всички положителни цели числа, по-малки от дадено. Например факториелът на 5, означен като 5!, е 1*2*3*4*5=120. Факториелът на нула се счита1):

Итеративните и рекурсивните програми са теоретично еднакви по отношение на техните изчислителни възможности, с други думи наборите от функции, изчислими с тяхна помощ, са еднакви (т.нар. частично рекурсивни функции). Така че всяко изчисление по принцип може да бъде програмирано по който и да е от тези начини. Свойствата на итеративните и рекурсивните версии на програмите обаче могат да се различават значително. В тази връзка често се налага да се реши кой от методите за програмиране е по-подходящ за дадена задача. Изборът, който правите, определя простотата и естествеността на програмирането, както и неговата ефективност по отношение на времето за изпълнение и използването на паметта. С итеративно програмиране, обикновено по-дълго и по-трудно за изпълнение, резултатът може да се изчисли много по-лесно и по-бързо. Това се случва по две причини, първо, защото компютрите обикновено работят стъпка по стъпка, и второ, защото преводачите не винаги могат да преобразуват рекурсивна дефиниция в итеративна и да използват стека в изчисленията, въпреки факта, че не винаги е необходим. Рекурсивното програмиране обикновено е по-кратко и по-смислено. Особено полезно е да се използва рекурсия в случаите, когато проблемът, който се решава, или данните, които се обработват, са по своята същност рекурсивни. Например, математическата дефиниция на факториел е рекурсивна и нейното прилагане чрез рекурсивна функция е напълно естествено:

n! = 1ако n=0
n! = n*(n-1)!ако n>0

Рекурсивното решение работи добре със списъци, тъй като списъците могат да съдържат подсписъци рекурсивно. Рекурсивните функции могат успешно да се използват вработа с други динамични структури, които не са напълно известни предварително. Рекурсивните процедури заемат важно място в почти всички програми, свързани с изкуствения интелект.