Lisp

Харесвате ли езика Lisp. Аз съм разглеждал диалекта Scheme и ми хареса много. По принцип теорията(идеята) на езика Lisp идва от ламбда-смятането.

Какво е необходимо за езици като Lisp и Prolog да бъдат използвани за комерсиални цели? Или можем да ги използваме само за моделиране на някоя задача, а окончателното изпълнение да е на C/C++

/b3

... не е популярен, тоест трудно е да се използва за комерсиални цели. Лично моето мнение е, че е така поради факта, че Lisp е функционален, а не алгоритмичен език, затова някои смятат че е по-труден за научаване от масовия програмист и за реализиране на практически задачи. Доколкото знам, развитието му практически е спряло. SQL също не е алгоритмичен език, но има директно практическо приложение, затова и е толкова известен.

Както казваш, много приятен език. Някои смятат, че е труден за научаване, но не са опитали по-упорито.

Проблема при Lisp и Prolog, е че интерпретаторите им са не-ефективни (не могат да се направят) и тези езици определено не стават за real-time задачи. Например Lisp постоянно оперира с динамичната памет за аллокиране(де-алокиране) на елементите на списъци; знаем, че списъка е основно средство в Lisp. По този начин паметта се фрагментира и управлението и е направо ужас. Prolog е по-икономичен в това отношение.

По принцип Lisp и Prolog се поддават лесно за паралелни смятания. Можем да направим много-процесорен компютър, който паралелно да смята програма на Lisp(Prolog). Ясни са недостатъците тук: един обикновен "printf" на екрана не може да е паралелен -- user-a чете изхода последователно. Но това не е проблем. В Lisp има конструкции, задължаващи последователно пресмятане на терми.

Казвам това, понеже в днешно време има евтини 66Mhz процесори, като ADSP-21065L на Analog Device, с които човек може да си сглоби много-процесорен компютър. Според мен с "няколко" такива процесори, с Lisp, като основен език и Assembler за графичните примитиви и драйверите за дискове, . . ., може да се построи хубав компютър, който да конкурира PC-то с Windows или Linux. Отново проблем е пазарната реализация.

Но проектиране на такива системи едва ли ще бъде спонсорирано от частните фирми в близко време :(

Предполагам, че всички ние си имаме идеи за собствен компютър или голяма софтуерна система, която да унищожи Windows,UNIX-ите или Aple, . . .

Идеята на Lisp идва от ламбда-смятането. Има еднa близко до него, Комбинаторна Алгебра, създадена от Haskell B. Kurry, който е бил колега на Чърч, Клини, Тюринг, . . . през 30-те години на миналия век. От неговата комбинаторна алгебра също може да излезе нещо.

/b3

Наистина Lisp използва много интензивно инамичната памет, но не е единствен; погледни Java например - там са диманични *всеки* масив и *всеки* обект, а единствените други конструкции, с които можеш да
кодираш данни са примитивните цели стойности и ези с плаваща запетая. Без обекти в един обектен език не можеш да работиш, така че при Java проблема с динамичната памет в никакъв случай не е по-лек от Lisp.

От друга страна, проблема при паралелни изчисления далеч не е само в разпаралеляването на програмата - не забравяй и комуникациите между процесорите - ако имаш повече от 4-5 процесора ще имаш много сериозен проблем с това кой с кого да свържеш; ако свържеш всеки с всеки ти трябват (n-1) канала на процесор и n*(n-1) връзки общо; да не говорим за синхронизацията между програмите на отделните машини. Има и друг начин - с обща памет, обаче там ядовете са още по-големи при голям брой процесори.

Между другото, ако се интересуваш от симулатор на паралелни архитектури, мога да ти предложа дипломната си работа - ще я намериш на адрес [линк] Накратко, това е софтуерен симулатор, който ти позволява да
дефинираш по време на работа самата архитектура - с обща памет или с връзки между процесорите, както и броя на процесорите. Програмира се на C с леки изменения (необходими са конструкции за комуникация между процесорите).

Първо, Java и подобни могат да използват динамичната памет, но разликата е несравнима. В Lisp списъка е основна конструкция, самата програма е списък, а когато смяташ интерпретатора да работи на повече процесори стекове (който улесняват организацията на паметта) почти не вършат работа.

Второ, когато става дума за паралелен компютър със стотици процесори комуникацията и връзките се уточняват веднъж съгласно алгоритъма на интерпретатора и след това няма пороблем. Известни са много схеми освен обща шина – ring, 3D mesh, . . . не искам да ги обсъждам. Но истинския проблем ще го видят приложните програмисти едва след това, понеже има разлика между компютър със стотици процесори, и такъв с 4-5 които обслужват десетина таска или нишки в някоя обикновенна ОС.
На прилижните програмисти тепърва им остава да си блъскат главите по своите задачи е паралелен компютър. За целта има създадени специални езици, като Concurent C, но работата с такива езици е трудна.

Никой си няма пороблем кой с кой процесор да свърже; всичко е добре известно и в някои чипове е вече предвидено това; продават се (не скъпо) чипове с по 4-6 процесора въре и широки възможности за комуникация с други процесори.

/b3

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

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

Според мен, основното предимство на Lisp е различния (може би по-добър) подход към създаването на софтуера, а не че автоматично решава проблемите, за които ти говоря - в крайна сметка, самият интерпретатор обикновено се пише на C и ще-не ще трябва да реши тези задачи.

Да, няма проблем да ги свържем, в смисъл че не е толкова сложна работа и знаем как да го направим. И това съвсем не означава, че не е важно как точно ще ги свъежем. Точно това казах в предишния си постинг. Много добре разбирам, че схемата по която са свързани процесорите директно влияе на скоростта. Всеки го знае.

Нормално (най-често) онези чипове с по 4-6 процесора вътре се използват по следния начин. Първо имаме задача изискваща много изчисления, за която смятаме, че поради някакви причини универсален компютър (като PC) не ни върши работа. След това програмистите разбиват на елементарни части алгоритъма, като се стремят да достигнат максимална паралеризация. Като се направи това, решаваме по каква схема ще свържем многото процесори и как ще комуникират и колко на брой. После правим агломерация, като разбития паралелен алгоритъм го групираме разпределяме по процесорите с необходимия протокол и управление. Софтуера се пише на Assembler и C, естествено.

Но това са специализирани системи, които очевидно са скъпи.

Дали ти помага Lisp? Когато отворих темата за Lisp имах съвсем друго в предвид, но разговора тръгна за многопроцесорни компютри. А по отношение на това, не става въпрос дали Lisp ми помага.
Да речем, че аз обичам да пиша на Lisp и искам да имам бърз компютър, ако ще да е с 1000 процесора или само с един, но да ми изпълнява бързо програмата.
В такъв дух, когато говорих за Lisp, споменах многопроцесорните компютри.

/b3

Reshih i az da vi napisha nyakoi moi razmisli po temata "Efektiven li e Prolog i negovoto razpredelyane" :-)
Ima edin shirok klas zadachi, za koito po-dobyr algoritym ot pylnoto izcherpvane (eventualno s podkastryane na nyakoe klonche tuk-tame :-) ne e izvesten. Napr. zadachi za tyrsene na pytishta v grafi po zadadeno uslovie. Za takyv vid zadachi spored men Prolog e ne po-malko efektiven ot kompiliruemite imperativni ezici. A shto se otnasya do reshenieto na zadachata na Prolog i C, napr... E nyama kakvo da si govorim :-) Na Prolog se opisva vida na reshenieto, a ne samiya algoritym (tova sigurno go znaete, ama az da si kaja :-), dokato na C - pishesh, majesh, testvash, bugove, i za kakvo? Za nyakakvo symnitelno konstantno podobrenie...
Za razpredelyaneto. Reshil sym moyata diplomna rabota da e razpredelen kernel-Prolog (tova e Prolog bez stranichni efekti (bez assert i retract i rabota s faylove), no s cut) za slabo-svyrzani s-mi (t.e. otdelni kompyutri v mreja). Kak mislya da go pravya? Predelno yasno e (a i v ISO standarta si go pishe), che interpretatoryt, tyrseyki reshenie, stroi dyrvo na vyzmojnite izvodi. I vinagi obhojda naslednicite na daden vyzel otlyavo na dyasno. Emi az tova uslovie nyama da go spazvam, t.e. raznite poddyrveta shte se dostroyavat ot razlichni kompyutri. Ideyata mi e klientyt da znae vsichki kompyutri-server-i, koito sa obyavili, che mogat (i iaskat :-) da stroyat dyrvenca, i oshte na pyrvoto nivo da razdade kolkoto se moje poveche ot poddyrvetata. Na svoy red, t.nar. server-i syshto shte se dyrjat kato klienti, t.e. te shte pochvat istinskata smetka chak kogato sa razdali kolkoto se moje poveche poddyrveta na drugi svobodni server-i, za koito znayat. I taka, dokato vsichki serveri si imat rabota. V momenta, v koyto nyakoy si postroi poddyrvoto i raportuva na klienta si, toy se osvobojdava i nyakoy ot drugite myrzelivi server-i mu puska neshto da si rychka :-) Izoboshto - plytno natovarvane :-)
Problem: mi kvo stava, kogato daden klient poluchi resheniya za poddyrvetata si ot po-byrzite server-i, a pyk nyakoya tutkava 386-ica razviva poddyrvoto, v koeto e skrito pilenceto? :-) Mi samata 386-ica shte nameri rabota na toku-shto osvobodilite se Athlon-i! :-)
Drug problem: ami assert, retract i drugite stranichni efekti? Moje da se napravi taka: vseki predikat, koyto izpolzva predikat sys stranichni efekti (definiciyata e rekursivna s baza vgradenite predikati sys stranichni efekti), se schita za nerazpredelim i se izpylnyava na klientskata mashina samo. Za da mu e po-efektivno razpredelyaneto, programistyt shte se stremi da iznese tezi predikati kolkoto se moje "po-nagore". Be ne mi zvuchi mnogo pravdiva tazi ideya :-) Zasega shte mogat da se izpylnyavat samo chisti predikati, pyk raznite stranichni deynosti shte se pishat na programa na C/C++ (koyato shte polzva uslugite na Prolog server-chetata chrez razni strukturki, koito taka ili nache shte gi ima v interpretatora (toy shte e napisan na C++));
Pone takava mi e ideyata, az oshte parser-yt ne sym si napisal :-(((

:) Избрал си си интересна курсова работа. Завиждам ти. Прочетох внимателно това, което си написал и съм напълно съгласен.

Твоята система, която избягва предикати със странични ефекти и деструктивни предикати, като assert и retract може да е полезна. Както казваш, голямото предимство на стила в Prolog е, че програмиста само казва “какво иска”, а не “как да стане”. Такава система, със разпределени по мрежа задачи, ако ускори работата може да е полезна за разработка на информационни системи с разпределена база данни (база знания), AI, . . .

Има една идея, която съм видял в книгата “Genesereth M., Nilson N., Logical Foundations of Artificial Intelligence, 1987”. Книгата я има в ЦИНТИ. Говори се за Knowledge и Belief, като има AI модел, в който участват повече агенти (отделните компютри в мрежата) които заедно се опитват да отговорят на въпрос, съобразно своите “вярвания” (т.е. собствената си база данни или знания), но могат да си комуникират, a и някой друг агент (компютър) може да прави съждения за относителна вярност на факти от гледна точка на друг агент.

Не че нямаш литература (да си кажа, понеже и други четат), но искам да посоча книгата “Чень Ч., Ли Р., Математическая логика и автоматическое доказателство теорем, 1973”, която не е точно за Prolog (понеже когато е била писана не е имало Prolog), а за метода на резолюцията с ускоряващи варианти и приложения.

Интересно ми е да си поговорим още по тази тема.

/b3
b.angelov@infotel.bg

Mi az ne sym koy znae kakyv logik, oshte po-malko spec po II. Izbral sym si takava diplomna rabota, zashtoto specializaciyata mi e ezici i translatori, a v syshtoto vreme lyubimata mi kompyutyrna oblast sa mrejite :-)
Takiva Prolozi ima, obache sa vse za razni mashini, deto ne sym gi chuval, ta kamo li da moga da gi vidya. Moyat shte ima samo 2 predimstva pred tyah - pyrvoto e, che shte bachka na obiknoveni PC-ta s obiknoveni i obshtodostypi OS (UNIX-i, Win32). Silno se nadyavam da optimiziram mrejovata chast taka, che da moje da vyrvi i po modem, t.e. dori na bavni komunikacionni kanali tyasnoto myasto vse pak da si ostava procesornata mosht.

Moyat Prolog nyama da pozvolyava dobavyane/iztrivane na fakti ot BD => tova precakva pochti vsichki izvestni mi algoritmi ot II. No problemyt ne e nereshim. Pishesh programa na C++, koyato dyrji bazata s generirani fakti i puska razni "query"-ta vyrhu neyni podmnojestva, posle merge-va rezulatite i t. n. Eventualno sled vreme moga taka da prerabotya interpretator-a, che toy sam da precenyava tova, koeto zasega shte se pravi rychno na C++. Kakto kaza diplomnata mi rykovoditelka: "Ne se prestaravay zasega, drugoto - za doktorat" :-))) Ne, che sym se zasilil, zasega iskam prosto da zavyrsha, da otbiya kazarmata, pyk posle shte vidim :-)

И аз не разбирам много от логика и ИИ. Също съм обикновен програмист, но си говоря просто така – да става лаф и да не е скучно.

Между другото, парсера на Prolog не е никак прост. По-труден e от Lisp (в Lisp имаме лява скоба, дясна скоба, стрингове, числа, символи и нищо друго).

Например, в някои Prolog-и програмиста може runtime да дефинира оператори (унарни, бинарни), като +, -, да им задава приоритет и съвместимост (относно асоциативния закон). Но може би това спада към интерпретатора, а не към парсера.

/b3

Mda, tova e osn. mi problem :-( V tozi smisyl Prolog e po-truden za parsvane dori ot Java!
Napisah edin LR parser. Toy raboti s edna specialna tablica, determiniran e, izobshto - pushka. Da, ama tablicata na Duron 750 MHz se smyata za nad sekunda, a vseki custom operator promenya gramatikata => tryabva da se preizchislyava tablicata => za vseki custom operator po edna sekunda, i to na takyv procesor (na Pentium 166 MHz beshe 12 sekundi!!)... Mnogo mi se vidya za edin parser, pochvam go sega otnachalo s direkten podhod (t.e. bez yavno definirane na gramatika).
Oh, kato ti se oplakah, po-leko mi stana :-)))

> Харесвате ли езика Lisp. Аз съм разглеждал
> диалекта Scheme и ми хареса много. По принцип
> теорията(идеята) на езика Lisp идва от ламбда-
> смятането.
Радвам се, че някой най-после повдигна темата за Lisp-а. Мисля, че това общо-взето е един от най-гъвкавите езици съществуващи досега. Дори само наличието на garrbage collector го прави по-добър от досегашните C/C++.

> Какво е необходимо за езици като Lisp и Prolog
> да бъдат използвани за комерсиални цели?
За момента сме в омагьосан кръг. Университетите преподават C/C++, защото това е главното което се търси от комерсиалните фирми, а комерсиалните фирми на свой ред набират главно хора знаещи C/C++, защото не могат да намерят други, а дори и да намерят има опасност, ако тези хора напуснат да няма кой да поддържа проекта. В това отношение Open Source проектите са в малко по-добро положение от комерсиалните проекти, защото често за едно и също нещо има поне 2-3 Open Source проекта, написани на каквото им хрумне на авторите. Ако екипа който поддържа един open source проект се разпадне или хората загубят интерес към него, остават другите 1-2 конкурентни проекта. Оцеляване на приспособените. <grin>.

> Или можем да ги използваме само за моделиране на
> някоя задача, а окончателното изпълнение да е
> на C/C++
Според мен в момента C/C++ имат _прекалено_ много проблеми за да са идеалното решение. От една страна е необходимостта от изрично освобождаване на заделените ресурси. Доскоро го имаше главно под M$ Windows, но напоследък се среща и под Linux... В крайна сметка всички по-големи проекти поне под Linux, се принуждават да си разработят собствени garbage collector-и за кода писан под C. В това отношение Lisp + някакъв обобщен garbage collector (не само за памет ще е идеален). Отделно C++ според мен има много други проблеми, както си личи от опита на M$ Windows. Човек може да пише обектно ориентирани програми без изобщо да е необходимо използването на обектно ориентиран език като C++. При писането на програми на C++ поне според мен твърде много усилия се хвърлят за създаването на йерархията от класове с надеждата в бъдеще този код да се използва повторно, което разбира се не се случва, защото технологията се развива прекалено бързо. Впрочем поне от 2-3 години не съм писал нещо сериозно под Windows, така че е добре някой програмист под Windows да подтвърди/опровергае това което съм написал. Отделно стои Java-та, която според мен е пълна скръб (все пак отбелязвам че не съм работил по никакви сериозни проекти на Java :-). Досега не съм видял нещо което да работи прилично бързо на Java, т.е. явно проблема е във виртуалната машина, а щом за толкова време не са успели да я направят както трябва, значи не само технологията куца, но и цялата идея не е читава. Изобщо цялата идея с преносимостта на Java, ми прилича на злополучната преносимост между различните версии на Apple процесорите, където "съвместимостта" се осигуряваше чрез емулация на предишните процесори. Изобщо ми е чудно как Apple, все още съществуват като търговска марка. Цялата i386 архитектура просперира не защото е добра, а защото Apple от десетина години насам упорито се мъчат да си направят харакири, а когато не успеят, тръбят из целия свят колко са добри. И евтини разбира се...

Такаааа... Кого не съм споменал още с добра дума? :-) Май остава само Prolog. :-)

<flamebait>
Не ми е ясно защо една библиотека за backtracking + възможност за унифициране на изразите се ползва с гръмкото име език за ИИ. Още повече че в днешните програми съотношението на кода за търсене на решения в стил Prolog (имам предвид backtracking-а) към останалия код е може би 1:10).
Т.е. на практика ако напиша една програма на Prolog, за да стане тя действително полезна трябва да добавя още 10 пъти по толкова код за управление на потребителския интерфейс, комуникация с други програми, използване на системни функции. Не е ли по-просто вместо това да си напиша програмата на някакъв императивен език, а за вземането на решения да използвам една библиотека за backtracking? Както впрочем изглежда и правят екипите, които работят по комерсиални продукти.
</flamebait>

> За момента сме в омагьосан кръг. Университетите
> преподават C/C++, защото това е главното което
> се търси от комерсиалните фирми, а
> комерсиалните фирми на свой ред набират главно
> хора знаещи C/C++, защото не могат да намерят
> други, а дори и да намерят има опасност, ако
> тези хора напуснат да няма кой да поддържа
> проекта
Впрочем това вече се променя с навлизането на Java. За добро или за лошо.

И аз не виждам Prolog като конвенционален език за програмиране. Неговия back-tracking може да се емулира лесно, естествено.
Знаем, че езика на Prolog е ограничен до Хорнови клаузи, което не му дава мощ за да служи за автоматично доказателство на теореми. Между другото има една система на Boyer & Moore, която може да се намери на ftp сайта

[линк]

(не съм я разглеждал, но е много известна при системите за автоматично доказателства).

Практиката показва, че real-time задачи (за embeded системи) се правят на Assembler и C. Това е изключено да се замени с езици като Lisp.

/b3

За твое огромно съжаление C++ процъфтява и на хоризонта не се задава нищо, което би могло да го измести. Говоря за сериозни проекти - големи и сложни програми, за които най-важните фактори са бързодействие и стабилност.

Що за приказки относно ресурсите? Явно си скаран с ефективното им управление, след като са бреме за теб. Аз, да речем, ползвам Microsoft-ските библиотеки за да си заделя памет. В тях има т.нар. Heap State Reporting Functions, част от който преравят heap-а за загубени блокове.
Функцията "new" има 2 разклонения - в зависимост дали е дефиниран _DEBUG. В "debug" разклонението, при завършване на програмата, автоматично се извършва проверка на heap-a, загубените блокове се репортуват и съответно премахват. Понеже си ползвам и visual studio, един double click ме позиционира на реда, на който е бил алокиран загубния блок. Всъщност, всяка уважаваща себе си ОС трябва да премахва heap-а на програмата след нейното завършване.

Технологията не се развива чак толкова бързо. От win95 и NT 3.5 насам (вече около 6 год.) няма кой знае какви съществени напредъци.



Si Vis Pacem, Para Bellum

Redaktirano ot MиГ-31 na 24.12.00 11:54.

МиГ, ти сигoрно ме бъркаш с някого. Не съм казал, че ми е проблемен C++. Явно на теб ти е проблемен, след като само за C++ си говориш.

Някои хора явно свързват OOP със C++, понеже само това са видяли. Използвал съм Objectiv C, което се беше появило за малко още преди C++ а също познавам добре SmallTalk-80, езика, от който на практика следват (и са се учили) C++ и всички OOP езици.

Обаче в днешно време много самонарекли се програмисти умеят само да натискат копчетата на wizzard-а и си въобразяват, че знаят какво е OOP и как се програмира. Такива хора така са се учили да програмират - като натискат копчетата, и като им вземеш wizzard-а нищо не могат да направят. Има и други работи, освен MSVC++ и Windows.

/b3

P.S.
:-) На практика MSVC++ е единствения език на който програмирам (90%), но това не ми пречи да говоря и за други езици, като Lisp :-)

Да те бъркам?!
Не виждам къде съм ти отговарял...
Кой не може да се оправи с дървото? хехех:)

Израждаш диалога с псевдологични съждения, а това не е добре. Говоря само позитивно за c++, пропагандирам, един вид. Сещаш ли се за какво става въпрос?

Разбира се, че има и други работи освен c++, но за да се почувстваш различен, по-добре напиши нещо гениално на c++, отколкото да тръбиш колко гениален бил SmallTalk.

Si Vis Pacem, Para Bellum

OK. Извинявай!

/b3

> За твое огромно съжаление C++ процъфтява и на
> хоризонта не се задава нищо, което би могло да
> го измести. Говоря за сериозни проекти - големи
> и сложни програми, за които най-важните фактори
> са бързодействие и стабилност.
В момента Java измества C++. Не е въпрос на по-добра технология, а на това че в този език са вложени много пари, които трябва да се оправдаят по един или друг начин. Освен това лошата съвместимост на Java е по-добра от нулевата съвместимост на M$ Visual C++.

> Що за приказки относно ресурсите? Явно си
> скаран с ефективното им управление, след като
> са бреме за теб. Аз, да речем, ползвам
> Microsoft-ските библиотеки за да си заделя
> памет. В тях има т.нар. Heap State Reporting
> Functions, част от който преравят heap-а за
> загубени блокове.
> Функцията "new" има 2 разклонения - в
> зависимост дали е дефиниран _DEBUG. В "debug"
> разклонението, при завършване на програмата,
> автоматично се извършва проверка на heap-a,
> загубените блокове се репортуват и съответно
> премахват. Понеже си ползвам и visual studio,
> един double click ме позиционира на реда, на
> който е бил алокиран загубния блок. Всъщност,
> всяка уважаваща себе си ОС трябва да премахва
> heap-а на програмата след нейното завършване.
При езиците с garbage collector въобще няма загубени блокове памет. Още повече че под C++ нямаш никаква гаранция че утечката на памет ще се прояви на компютъра на който тестваш програмата си. Освен това паметта е само един от ресурсите, които могат да се губят.

> Технологията не се развива чак толкова бързо.
> От win95 и NT 3.5 насам (вече около 6 год.)
> няма кой знае какви съществени напредъци.
Това е причината избягвам M$ продуктите.