Любимите управляващи пак се правят на ощипани булки и се опитват да ни хвърлят прах в очите -- ако президентът наложел вето върху закона за актуализация на бюджета, щяло да бъде прецедент, защото това било въпрос на правителствени политики, а не на противоконституционност. Било намеса в работата на правителството и като цяло много лошо.
Да ама не. Правомощията на президентската институция са регламентирани в Конституцията и там пише, цитирам:
Чл. 101. (1) В срока по чл. 88, ал. 3 президентът може мотивирано да върне закона в Народното събрание за ново обсъждане, което не може да му бъде отказано.
Забележете какво пише -- мотивирано. Не пише какви трябва да са мотивите му -- това е оставено на неговата съвест. Не е нужно да се мотивира с "противоконституционност". Може да се мотивира например с това, че в обществото има противоречиви настроения относно разпоредбата, поради факта, че предназначението й и нуждата от нея са недостатъчно добре обяснени, какъвто е и случая.
И най-малкото това не е намеса в работата на правителството, а в работата на законодателната власт. В края на краищата, парламента приема закона.
И поне според мен смисъла на тази разпоредба е президентът наблюдавайки обществените настроения да се опита да даде на законодателите нишан, че правят глупости и да ги повъзпре малко.
Само малко, защото така или иначе после ще си го приемат въпреки всичко, поне това показва статистиката досега...
вторник, 30 юли 2013 г.
петък, 21 юни 2013 г.
Размишления върху Конституцията
Слушайки напоследък как политиците като едни неуморни пчели, цял ден събирали прашец от нечия лимонова овощна градина, кисело обясняват как ще пренапишат изцяло Избирателния кодекс, защото така искало Гражданското общество, ми се доповръща като на пасажер, намиращ се в брулена от силен страничен вятър Лада в завой. Твърде рядко получавам позиви за прочистване на храносмилателния тракт едновременно в двете посоки, поради което прегърнах появилата се възможност и се възползвах от нея. След като почистих старателно местообитанието си и себе си, си сипах едно питие, което ми помогна да възстановя жизнените си показатели до що-годе поносими равнища. И тъй като историческите сведения показват, че Онези избраните няма да помислят вместо мен, започнах да мисля.
Какво му е лошото на Избирателния кодекс?
Като за начало, нека да разгледаме защо имаме Избирателен кодекс? Ами за да пише в него правилата за избор. Избор на какво? Ами да погледнем в Конституцията:
Чл. 8. казва, че "Държавната власт се разделя на законодателна, изпънителна и съдебна". Аз като един лаик инжинер, не-завършил Право в СУ, очаквам тези 3 поименно изброени власти да са независими една от друга -- иначе защо ще ги изброяват поотделно, можеше да се каже само, че има държавна власт и това е. А след като съгласно Чл. 1, ал. 1. "...цялата държавна власт произтича от народа", аз очаквам, народа да има възможност да си ги избира независимо една от друга.
Въоръжен с непрекършваем оптимизъм в светлото бъдеще чета нататък, за да се ориентирам какво точно идва да каже "законодателна", "изпълнителна" и "съдебна" власт. Установявам, че никъде не се споменава какво правят тези три власти и какви са органите им, освен в чл. 62, ал. 1. "Народното събрание осъществява законодателната власт и упражнява парламентарен контрол". Никъде не се споменава напр., че Министерския съвет упражнява изпълнителната власт, или какви са органите на съдебната власт. Всички нейни институции, като Висш съдебен съвет, прокуратура, следствие и т.н. се въвеждат в летящ старт, без да стане нясно кой какъв е и защо съществува.
Добре, казвам си, сигурно прекалено формално гледам на нещата. Сигурно тия работи, дето не са написани конкретно се подразбират и се учат във втори клас, пък аз съм ги пропуснал, щото съм бил келеш. Дай поне да видим дали са независими.
Първото нещо, което бие на очи е, че в Конституцията думата "независим" и нейните производни се срещат по-рядко, отколкото думата "мерцедес" в произволно чалга произведение. Никъде не се споменава изрично, че трите власти от чл. 8 са всъщност независими. От чл. 117, ал. 2 става ясно единствено, че "Съдебната власт е независима. При осъществяване на своите функции съдиите, съдебните заседатели, прокурорите и следователите се подчиняват само на закона". Това поражда въпроси: Независима от какво? А останалите 2 власти зависими ли са? От какво? Защо няма реципрочни текстове за останалите власти? Или при осъществяване на своите функции участниците в останалите 2 власти се подчиняват и на други неща, освен закона?
Добре де, не са го споменали изрично. Но сигурно поне се избират независимо? Да, ама не. И няма нужда да четем Конституцията -- всички сме били на избори. Защо се избират пряко от народа само представителите на законодателната власт? Защо изпълнителната власт е функция от законодателната (парламента избира правителство)? Защо органите на съдебната власт също са функция от законодателната и на Президентската институция? Това пък последното какво беше и защо не е в списъка на чл. 8?
И въобще: какво се занимаваме с Изборен кодекс, след като Конституцията все едно е писана от полуграмотни четвъртокласници, които никога не са чували за аксиоматичен базис и причинно-следствена връзка? Моето лично мнение е, че първото нещо, което трябва да се направи е да се промени Конституцията, поне в следните й части:
Какво му е лошото на Избирателния кодекс?
Като за начало, нека да разгледаме защо имаме Избирателен кодекс? Ами за да пише в него правилата за избор. Избор на какво? Ами да погледнем в Конституцията:
Чл. 8. казва, че "Държавната власт се разделя на законодателна, изпънителна и съдебна". Аз като един лаик инжинер, не-завършил Право в СУ, очаквам тези 3 поименно изброени власти да са независими една от друга -- иначе защо ще ги изброяват поотделно, можеше да се каже само, че има държавна власт и това е. А след като съгласно Чл. 1, ал. 1. "...цялата държавна власт произтича от народа", аз очаквам, народа да има възможност да си ги избира независимо една от друга.
Въоръжен с непрекършваем оптимизъм в светлото бъдеще чета нататък, за да се ориентирам какво точно идва да каже "законодателна", "изпълнителна" и "съдебна" власт. Установявам, че никъде не се споменава какво правят тези три власти и какви са органите им, освен в чл. 62, ал. 1. "Народното събрание осъществява законодателната власт и упражнява парламентарен контрол". Никъде не се споменава напр., че Министерския съвет упражнява изпълнителната власт, или какви са органите на съдебната власт. Всички нейни институции, като Висш съдебен съвет, прокуратура, следствие и т.н. се въвеждат в летящ старт, без да стане нясно кой какъв е и защо съществува.
Добре, казвам си, сигурно прекалено формално гледам на нещата. Сигурно тия работи, дето не са написани конкретно се подразбират и се учат във втори клас, пък аз съм ги пропуснал, щото съм бил келеш. Дай поне да видим дали са независими.
Първото нещо, което бие на очи е, че в Конституцията думата "независим" и нейните производни се срещат по-рядко, отколкото думата "мерцедес" в произволно чалга произведение. Никъде не се споменава изрично, че трите власти от чл. 8 са всъщност независими. От чл. 117, ал. 2 става ясно единствено, че "Съдебната власт е независима. При осъществяване на своите функции съдиите, съдебните заседатели, прокурорите и следователите се подчиняват само на закона". Това поражда въпроси: Независима от какво? А останалите 2 власти зависими ли са? От какво? Защо няма реципрочни текстове за останалите власти? Или при осъществяване на своите функции участниците в останалите 2 власти се подчиняват и на други неща, освен закона?
Добре де, не са го споменали изрично. Но сигурно поне се избират независимо? Да, ама не. И няма нужда да четем Конституцията -- всички сме били на избори. Защо се избират пряко от народа само представителите на законодателната власт? Защо изпълнителната власт е функция от законодателната (парламента избира правителство)? Защо органите на съдебната власт също са функция от законодателната и на Президентската институция? Това пък последното какво беше и защо не е в списъка на чл. 8?
И въобще: какво се занимаваме с Изборен кодекс, след като Конституцията все едно е писана от полуграмотни четвъртокласници, които никога не са чували за аксиоматичен базис и причинно-следствена връзка? Моето лично мнение е, че първото нещо, което трябва да се направи е да се промени Конституцията, поне в следните й части:
- ясна дефиниция на това с какво се занимават трите власти (законодателна, изпълнителна и съдебна) и какви са техните органи и как се формира техния бюджет;
- пряк избор от народа на всеки един от съответните органи (народно събрание, ръководства на органите на изпълнителната власт и ръководства на органите на съдебната власт);
- премахване на синекурни длъжности като Президент, който формално погледнато не е част от държавната власт, поне не и съгласно чл. 8. Вместо това приемливо би било например органът на изпълнителната власт да се нарече Президент (напр. както в САЩ, Франция и т.н.);
Въобще не съм засегнал темата за местната власт. Тя също ли се дели на тези трите, подобно на държавната? Ако да, за нея също важат горните точки. Защо напр. не си избираме районен съдя или районен прокурор? Ако не -- защо не?
След това идват въпроси по конкретиката как да стане избора. Например, нека разгледаме случая с гласуване за законодателна власт. Напоследък тезата как "управляващите нямат никаква връзка с избирателите" присъства в публичното пространство с упоритостта на третирана с хомеопатия венерическа болест. Прост преглед на изборните системи ще покаже, че многомандатните избирателни райони (какъвто е случая в РБ) водят точно до това -- тъй като гласуваме за партийни листи, нямаме никаква представа кои са ни представителите всъщност, т.е. нямаме никаква връзка с тях. И си мисля, че когато улицата говори за "мажоритарна система", сигурно хората имат предвид въвеждането на едномандатни райони. Много е просто -- разделяме страната на райони, напр. използваме като база съществуващите общини, и всеки район излъчва по 1 народен представител напр. на 30 000 души, но поне по 1 за община. Съгласно текущите цифри, това би увеличило броя на народните представители, обаче ако това е проблем -- нека намалим броя на общините? В рамките на района, всеки избирател гласува за конретно лице, което да го представлява. И в последствие знае конкретно към кой да се обърне, за да му решава проблемите. И няма такива филми "А. Б. е водач на листите в 23, 12 и 18-ти район". WTF? Шизофрения нещо? И освен това, ако някой престане да бъде депутат, просто се провеждат избори наново в съответния район, а не "на неговото място влиза следващия от листата". Няма парламентарни групи, няма номадство, несъвместимости и т.н. ушна кал в промишлени количества. Ако събереш 1000 подписа се кандидатираш за района и това е -- хората гласуват (или не гласуват) за тебе.
Редовният вой на политиците срещу едномандатните райони е, че бавно и полека те водят до двупартиен модел (виж Великобритания и САЩ, където тази система се прилага). А дали това е лошо? Не знам дали е лошо, но със сигурност според мен е по-добро от това, което имаме в момента.
Да обобщя: моето лично мнение, е че промени в Конституцията в духа на горното е това, което ни трябва. След това ще се занимаваме с Изборен кодекс. Всичко останало е не по-различно от пластична хирургия, извършена посредством клепане с баданарката или ремонт на печатна платка с SMB монтаж посредством заварки с поялника за улуци.
неделя, 9 юни 2013 г.
SBCL за ARM Част III
Пръдължение на това: Част II
От последния път добавих в src/compiler/arm/params.lisp още един enum, който дефинира константите, използвани за разграничаване на различните софтуерни прекъсвания. За какво става въпрос: понякога се налага в lisp кода да се генерира прекъсване, което да бъде обработено от C runtime-а. Такива са например ситуациите, в които се генерира грешка, breakpoint, halt на виртуалната машина и т.н. Като гледам останалите платформи това се реализира чрез инструкция, която да доведе до генериране на SIGILL или SIGTRAP от страна на ОС и този сигнал се прихваща и обработва от специална функция в C runtime-а. Е, за да може да разбере тази функция какъв точно е повода за прекъсването, е необходимо това да бъде записано около (а най-добре във) инструкцията. Ще му мислим за това като му дойде времето, засега копираме списъка с trap-ове от някоя друга платформа.
Оказва се, че следващият платформено-зависим файл, src/compiler/arm/backend-params.lisp е продължение на params, разделено от основния файл по някое време в далечното минало, понеже е съдържало зависимости от конкретна структура, наречена BACKEND, която се е компилирала след params. Тази структура отдавна вече не съществува, така че разделението вече е само по исторически причини. Биха могли нещата да се merge-нат обратно в params, но някой друг път (трябва да се направи за всички платформи и да се махне backend-params изобщо). Тук се дефинират неща като:
От последния път добавих в src/compiler/arm/params.lisp още един enum, който дефинира константите, използвани за разграничаване на различните софтуерни прекъсвания. За какво става въпрос: понякога се налага в lisp кода да се генерира прекъсване, което да бъде обработено от C runtime-а. Такива са например ситуациите, в които се генерира грешка, breakpoint, halt на виртуалната машина и т.н. Като гледам останалите платформи това се реализира чрез инструкция, която да доведе до генериране на SIGILL или SIGTRAP от страна на ОС и този сигнал се прихваща и обработва от специална функция в C runtime-а. Е, за да може да разбере тази функция какъв точно е повода за прекъсването, е необходимо това да бъде записано около (а най-добре във) инструкцията. Ще му мислим за това като му дойде времето, засега копираме списъка с trap-ове от някоя друга платформа.
Оказва се, че следващият платформено-зависим файл, src/compiler/arm/backend-params.lisp е продължение на params, разделено от основния файл по някое време в далечното минало, понеже е съдържало зависимости от конкретна структура, наречена BACKEND, която се е компилирала след params. Тази структура отдавна вече не съществува, така че разделението вече е само по исторически причини. Биха могли нещата да се merge-нат обратно в params, но някой друг път (трябва да се направи за всички платформи и да се махне backend-params изобщо). Тук се дефинират неща като:
- *backend-byte-order*, което показва дали архитектурата е little endian или big endian (в нашия случай -- :little-endian);
- *backend-page-size*, което е размера на страниците в паметта (засега слагаме 4096, колкото да има нещо, а като стигнем до използването й, ще установим правилната стойност по емпиричен път);
- и разни други константи, свързани с garbage collection–а, които за сега само копираме, те би трябвало само да доведат до евентуална оптимизация, но според мен би следвало като първо приближение да работи и със стойностите от другите платформи;
събота, 1 юни 2013 г.
SBCL за ARM Част II
Продължение на това: Част I
Гледайки build-order.lisp-expr, първия изцяло платформено зависим файл, който се зарежда е src/compiler/arm/params.lisp. Тук се дефинират основни [константни] параметри на платформата, като например:
Следва списък от символи (разбирай -- променливи и функции), които да се запишат в static space-а, при това списъка е подреден. Тъй като те са непреместваеми, SBCL знае как да ги реферира като събере началото на статичното пространство с число, формирано от поредния номер на символа, умножено по размера на символа в паметта (който за щастие е константен ;-)). За момента не знаем кои символи ще ни трябват и кои не -- оставяме ги така, както са в X86 порта.
С това src/compiler/arm/params.lisp приключва. Ще трябва да го навестим някъде в бъдещето, когато стигнем до make-target-2.sh. Но засега -- това е.
Гледайки build-order.lisp-expr, първия изцяло платформено зависим файл, който се зарежда е src/compiler/arm/params.lisp. Тук се дефинират основни [константни] параметри на платформата, като например:
- (def!constant n-word-bits 32) -- брой битове в една дума, където под дума се разбира 1 lisp descriptor. Какво точно е lisp descriptor? Това е основната "кукичка" към данните в SBCL. Ако данната се събира в 1 дескриптор, тя е самодостатъчна (такива са например т.н. fixnum числа). Ако данната не се събира в 1 дескриптор, то дескриптора съдържа пойнтер към паметта, където се съдържа останалата част от данните. И в двата случая една част от дескриптора указва типа на данните, но за това после. Забележете, че тук (и на много други места) се използва def!constant вместо стандартното defconstant, тък като тази версия се грижи да прави необходимите неща в зависимост от това кога точно се изпълнява (напр. по време на компилиране на крос-компилатора, дефинира не една, а две константи -- едната за да може host компилатора да знае за тази константа и да я разбира в последствие, другата за самия cross компилатор, който също трябва да си я запише някъде и да я използва когато той компилира);
- (def!constant n-machine-word-bits 32) -- брой битове в думата, където под дума се разбира естествения тип данни за съответната архитектура. Аз лично не знам кому е нужно n-word-bits да е различно от n-machine-word-bits, но това е факт за alpha порт-а.
- (def!constant n-byte-bits 8) -- малко безмислен параметър съгласно съвременните разбирания, но като се има предвид, че SBCL наследява code base от началото на 80-те години на миналия век, който пък не е ясно какво точно наследява, мога да си представя случаи, в които байтът не е бил 8 бита...
- следващите няколко дефинират floating point форматите, които се поддържат native от платформата; в случая с ARM те изцяло съвпадат с IEEE 754 single и double float (при x86 напр. има и long-double, който се поддържа от хардуера, но тук -- не):
- (def!constant float-sign-shift 31) -- колко наляво трябва да се шифтне бита за знак, за да застане на мястото си във floating point формата. Използва се и за single и за double, като за double се прилага за старшата дума;
- (def!constant single-float-bias 126)-- колко трябва да се прибави към експонентата, когато тя се кодира в съответния формат (виж IEEE 754);
- (defconstant-eqx single-float-exponent-byte (byte 8 23) #'equalp) -- коя част от кодираните данни заема експонентата. (byte size pos) е стандартна lisp конструкция, която избира size на брой бита, започвайки от позиция pos. Странният начин за дефиниране на константата тук (и на други места) е свързан с факта, че това всъщност не е точно immediate константа, а е по-сложен Lisp обект, чиято стойност по време на компилация и после по време на зареждане може да се различава, която пък противоречи на смисъла "константа". Затова се ползва къстъм версия на defconstant.
- (def!constant single-float-normal-exponent-min 1)
- (def!constant single-float-normal-exponent-max 254) -- минимална и максимална стойност на експонентата за нормализирани числа;
- (def!constant single-float-hidden-bit (ash 1 23)) -- съгласно IEEE 754 най-старшия бит на мантисата по подразбиране е 1 и не се записва;
- (def!constant single-float-trapping-nan-bit (ash 1 22)) -- пак съгласно IEEE 754, когато има NaN (not-a-number), който води до грешка (trapping nan), то съответния бит е вдигнат;
- Аналогични константи се дефинират и за double
Следва списък от символи (разбирай -- променливи и функции), които да се запишат в static space-а, при това списъка е подреден. Тъй като те са непреместваеми, SBCL знае как да ги реферира като събере началото на статичното пространство с число, формирано от поредния номер на символа, умножено по размера на символа в паметта (който за щастие е константен ;-)). За момента не знаем кои символи ще ни трябват и кои не -- оставяме ги така, както са в X86 порта.
С това src/compiler/arm/params.lisp приключва. Ще трябва да го навестим някъде в бъдещето, когато стигнем до make-target-2.sh. Но засега -- това е.
петък, 31 май 2013 г.
SBCL за ARM част I
Ами да започваме...
Напълно в стила на метакръговите оценители, SBCL се билдва от...SBCL (е, може и от друг Lisp и му трябва и малко GCC, но като цяло е написан на Lisp). Това не е нещо ново -- и GCC е написан на C и му трябва малко помощ да бутстрапне.
По принцип си има билд скрипт, който ако вече има някакъв Lisp и GCC на машината -- работи. В случая обаче искаме да правим крос-компилация, т.е. скрипта няма да ни свърши работа наготово.
Билд скрипта общо взето прави следното (плюс някакви дреболии):
make-configh.sh
make-host-1.sh
make-target-1.sh
make-host-2.sh
make-target-2.sh
Тези, които имат host в тях, се пускат на хоста за крос-компилация, т.е. на PC-то ми. Другите, които имат target в тях, се пускат на Малинката. config-а го пускам също на Малинката.
make-config.sh се опитва да разбере върху каква система работи и да установи правилните параметри (нещо като ./configure)
make-host-1.sh създава лисп частта на една орязана версия на SBCL, написана изцяло на portable ASNI Common Lisp, така че да може да се компилира от какъвто Lisp има на хоста. Въпреки, че пише орязана, тя съдържа целия SBCL крос-компилатор, способен да върви на host машината, но да генерира код за ARM. Друго важно нещо, което make-host-1.sh прави, е че създава C .h файлове, необходими за да се билдне C частта на бъдещия SBCL (т.н. genesis).
make-target-1.sh прави C частта (т.н. runtime) на бъдещия SBCL. Тя се пуска на Малинката и се компилира с нейния GCC, генерирайки нормален ARM изпълним файл. От така получения ELF binary се извличат символите и адресите (посредством nm) на всички функции и техните адреси, които записани в sbcl.nm се копират на host машината, заедно с разни неща от .h файловете. Те ще трябват в следващата стъпка, в който крос-компилатора компилира окончателната версия на лисп частта и трябва да знае адресите на функциите без те да са всъщност в паметта.
make-host-2.sh се пуска отново на PC-то. Тук крос-компилатора, компилиран в първата стъпка се използва, за да компилира (този път за ARM) друга орязана версия на SBCL, която съдържа почти всичко (без някои по-специфични неща, механизъма за които още не е компилиран :–)). Готовите неща се записват в т.н. cold core, който е лисп частта, предназначена за последната стъпка.
make-target-2.sh се пуска на Малинката. Това е компилирания в make-target-1.sh runtime, който прочита създадения в make-host-2.sh cold core и му предава управлението. Там вече има native ARM компилатор, с който се докомпилират всички останали неща и се създава окончателния sbcl.core със всичките му салтанати.
make-host-1.sh, заедно с make-target-1.sh са като че ли единствените неща, които трябва да се пипнат. Доколкото успявам да схвана, останалите работи са на машинно-независим Lisp, така че те би трябвало да минат лесо. make-host-1.sh обаче е яката работа.
И така: да почваме по ред. Първите промени са тук:
https://github.com/vpavlov/sbcl/commit/4e21ee17c471aa653541d777974646c8beb0d91a
Файл по файл, промените са следните:
make-config.sh се опитва да разбере върху каква система работи и да установи правилните параметри (нещо като ./configure). Той обаче работи само за платформи, за които вече може да се компилира, така че трябва малко да го пипнем, за да добавим и ARM:
src/cold/shared.lisp -- промените тук са предимно свързани с едни sanity check–ове, които проверяват дали написаните в ltf фийчъри са съвместими едни с други. Така например проверява за кои платформи се поддържат thread–ове, и ако не сме в тях -- се оплаква. Е, тъй като въвеждаме нова платформа, се налага да променим малко въпросните sanity check-ове.
Другата по-важна промяна е във функцията stem-remap-target (на ред 257). Ето и цялата функция:
(defun stem-remap-target (stem)
(let ((position (search "/target/" stem)))
(if position
(concatenate 'string
(subseq stem 0 (1+ position))
#!+x86 "x86"
#!+x86-64 "x86-64"
#!+sparc "sparc"
#!+ppc "ppc"
#!+mips "mips"
#!+alpha "alpha"
#!+hppa "hppa"
#!+arm "arm"
(subseq stem (+ position 7)))
stem)))
Малко пояснение: сорсовете, които трябва да се билднат (един вид -- проекта), се намират също в лисп файл (build-order.lisp-expr в основната директория). В него на места се срещат пътища от сорта на src/compiler/target/inst.lisp Горната функция се грижи за това стринга /target/ в съответните файлови имена да се замени със стринг, който да отговаря на платформата (в нашия случай напр. src/compiler/arm/inst.lisp) По този начин се компилират файловете само за съответната платформа. Е, тук се налага да добавим случая за arm, който, разбираемо липсваше.
Малко странно изглеждат редовете с #! отпред. Това е conditional read, нещо като #ifdef ... #endif, но по-хитро. Нещото, което е след #! е keyword от ltf. Някъде в началото, преди за пръв път да се използва #!, се дефинира т.н. reader macro. Това е лисп код, който се изпълява по време на парсването на лисп сорсовете. Задейства се от прочитане на определена последователност, в случая #!+ (или #!-). Функцията проверява дали следващата keyword е налична в списъка, прочетен от ltf и ако е наличен -- прочита следващата форма; ако не е наличен -- я пропуска. По този начин се получава условна компилация в зависимост от нещата, описани в ltf. Както можете да се сетите, кода по-нататък е изпъстрен от такива #!+ неща
Една скоба: съгласно стандарта има макроси #+ и #-, които правят същото, но те работят с точно определен списък с feature-и (наречен... :features), който го има в host компилатора, но понеже не искаме да се бъзикаме с него и да му омешваме нашите фийчъри с неговите, се налага въвеждането на още един набор reader макроси, този с #!+ и #!-
Толкова за днес. Следват изцяло платформено зависими неща (huuuuge) и за първото от тях -- дефиницията на регистрите и т.н. -- в отделен пост, че темата е голяма...
Напълно в стила на метакръговите оценители, SBCL се билдва от...SBCL (е, може и от друг Lisp и му трябва и малко GCC, но като цяло е написан на Lisp). Това не е нещо ново -- и GCC е написан на C и му трябва малко помощ да бутстрапне.
По принцип си има билд скрипт, който ако вече има някакъв Lisp и GCC на машината -- работи. В случая обаче искаме да правим крос-компилация, т.е. скрипта няма да ни свърши работа наготово.
Билд скрипта общо взето прави следното (плюс някакви дреболии):
make-configh.sh
make-host-1.sh
make-target-1.sh
make-host-2.sh
make-target-2.sh
Тези, които имат host в тях, се пускат на хоста за крос-компилация, т.е. на PC-то ми. Другите, които имат target в тях, се пускат на Малинката. config-а го пускам също на Малинката.
make-config.sh се опитва да разбере върху каква система работи и да установи правилните параметри (нещо като ./configure)
make-host-1.sh създава лисп частта на една орязана версия на SBCL, написана изцяло на portable ASNI Common Lisp, така че да може да се компилира от какъвто Lisp има на хоста. Въпреки, че пише орязана, тя съдържа целия SBCL крос-компилатор, способен да върви на host машината, но да генерира код за ARM. Друго важно нещо, което make-host-1.sh прави, е че създава C .h файлове, необходими за да се билдне C частта на бъдещия SBCL (т.н. genesis).
make-target-1.sh прави C частта (т.н. runtime) на бъдещия SBCL. Тя се пуска на Малинката и се компилира с нейния GCC, генерирайки нормален ARM изпълним файл. От така получения ELF binary се извличат символите и адресите (посредством nm) на всички функции и техните адреси, които записани в sbcl.nm се копират на host машината, заедно с разни неща от .h файловете. Те ще трябват в следващата стъпка, в който крос-компилатора компилира окончателната версия на лисп частта и трябва да знае адресите на функциите без те да са всъщност в паметта.
make-host-2.sh се пуска отново на PC-то. Тук крос-компилатора, компилиран в първата стъпка се използва, за да компилира (този път за ARM) друга орязана версия на SBCL, която съдържа почти всичко (без някои по-специфични неща, механизъма за които още не е компилиран :–)). Готовите неща се записват в т.н. cold core, който е лисп частта, предназначена за последната стъпка.
make-target-2.sh се пуска на Малинката. Това е компилирания в make-target-1.sh runtime, който прочита създадения в make-host-2.sh cold core и му предава управлението. Там вече има native ARM компилатор, с който се докомпилират всички останали неща и се създава окончателния sbcl.core със всичките му салтанати.
make-host-1.sh, заедно с make-target-1.sh са като че ли единствените неща, които трябва да се пипнат. Доколкото успявам да схвана, останалите работи са на машинно-независим Lisp, така че те би трябвало да минат лесо. make-host-1.sh обаче е яката работа.
И така: да почваме по ред. Първите промени са тук:
https://github.com/vpavlov/sbcl/commit/4e21ee17c471aa653541d777974646c8beb0d91a
Файл по файл, промените са следните:
make-config.sh се опитва да разбере върху каква система работи и да установи правилните параметри (нещо като ./configure). Той обаче работи само за платформи, за които вече може да се компилира, така че трябва малко да го пипнем, за да добавим и ARM:
- от uname -n взимаме архитектурата, която докладва Малинката и виждаме, че е arm6l, добавяме в необходимия case;
- понеже ОС-а си е Linux, си мисля, че ще мога да добавя и тредове и футекси (каквото и да значи това), затова добавям :sb-thread и :sb-futex към local-target-features.lisp-expr (ltf, малко повече за това -- след малко);
- съответно добавяме case за вече познатата по-горе архитектура, в който се установяват другите неща от ltf. Тук копирам всичко от x86 архитектурата, пък после ще му мислим, като му дойде времето.
src/cold/shared.lisp -- промените тук са предимно свързани с едни sanity check–ове, които проверяват дали написаните в ltf фийчъри са съвместими едни с други. Така например проверява за кои платформи се поддържат thread–ове, и ако не сме в тях -- се оплаква. Е, тъй като въвеждаме нова платформа, се налага да променим малко въпросните sanity check-ове.
Другата по-важна промяна е във функцията stem-remap-target (на ред 257). Ето и цялата функция:
(defun stem-remap-target (stem)
(let ((position (search "/target/" stem)))
(if position
(concatenate 'string
(subseq stem 0 (1+ position))
#!+x86 "x86"
#!+x86-64 "x86-64"
#!+sparc "sparc"
#!+ppc "ppc"
#!+mips "mips"
#!+alpha "alpha"
#!+hppa "hppa"
#!+arm "arm"
(subseq stem (+ position 7)))
stem)))
Малко пояснение: сорсовете, които трябва да се билднат (един вид -- проекта), се намират също в лисп файл (build-order.lisp-expr в основната директория). В него на места се срещат пътища от сорта на src/compiler/target/inst.lisp Горната функция се грижи за това стринга /target/ в съответните файлови имена да се замени със стринг, който да отговаря на платформата (в нашия случай напр. src/compiler/arm/inst.lisp) По този начин се компилират файловете само за съответната платформа. Е, тук се налага да добавим случая за arm, който, разбираемо липсваше.
Малко странно изглеждат редовете с #! отпред. Това е conditional read, нещо като #ifdef ... #endif, но по-хитро. Нещото, което е след #! е keyword от ltf. Някъде в началото, преди за пръв път да се използва #!, се дефинира т.н. reader macro. Това е лисп код, който се изпълява по време на парсването на лисп сорсовете. Задейства се от прочитане на определена последователност, в случая #!+ (или #!-). Функцията проверява дали следващата keyword е налична в списъка, прочетен от ltf и ако е наличен -- прочита следващата форма; ако не е наличен -- я пропуска. По този начин се получава условна компилация в зависимост от нещата, описани в ltf. Както можете да се сетите, кода по-нататък е изпъстрен от такива #!+ неща
Една скоба: съгласно стандарта има макроси #+ и #-, които правят същото, но те работят с точно определен списък с feature-и (наречен... :features), който го има в host компилатора, но понеже не искаме да се бъзикаме с него и да му омешваме нашите фийчъри с неговите, се налага въвеждането на още един набор reader макроси, този с #!+ и #!-
Толкова за днес. Следват изцяло платформено зависими неща (huuuuge) и за първото от тях -- дефиницията на регистрите и т.н. -- в отделен пост, че темата е голяма...
четвъртък, 16 май 2013 г.
Нова играчка -- нов Lisp
От известно време насам в България е налично това:
Мисля да портна SBCL (Steel Bank Common Lisp) за ARM за Raspberry Pi и да пиша тук за този проект. Надявам се да останат 3-4 души, които да ме четат (Кременлиев и Спасов-- вас ви броя поне за по двама!); за останалите -- надежда всяка оставете -- нищо смислено няма да прочетете тук.
С две думи: 700 MHz ARM процесор, 24 GFLOP/s GPU, 512 MB RAM, Linux операционна система, 100 MB/s Ethernet, 2 USB порта, FullHD декодиране, HDMI и т.н. екстри и всичко това на цената от кръгло 57 лв без ДДС. Пак ще повторя: нема 30 евро.
Мисля да портна SBCL (Steel Bank Common Lisp) за ARM за Raspberry Pi и да пиша тук за този проект. Надявам се да останат 3-4 души, които да ме четат (Кременлиев и Спасов-- вас ви броя поне за по двама!); за останалите -- надежда всяка оставете -- нищо смислено няма да прочетете тук.
SBCL е Лисп среда (за Java фенбойчетата -- виртуална машина, ама не баш, ама айде да не изпадаме още толкова рано в подробости), която компилира/интерпретира до native код. Т.е. портването на SBCL за ARM е свързано с написването на асемблер/компилатор от Lisp към машинен ARM код. Затова и няма SBCL за ARM, на никой не му се е занимавало достатъчно. Аз смятам да поправя тази неспарведливост. Трябва веднага да кажа, че освен асемблер и компилатор, трябва да направя и дизасемблер и дебъгер, тъй като те са неизменна част от SBCL -- там има всичко, което ти трябва за да develop-ваш. С две думи -- работата е чутовна. Хората казват, че отнема 2-3 човекоседмици. Аз лично, ако до Нова 2014 година имам нещо, дето да работи що-годе, ще се гордея със себе си.
Ще Ви keep-вам posted за any progress.
Наздраве и лека нощ!
неделя, 3 март 2013 г.
Колко виртуална е виртуалната машина на SBCL?
Както стана ясно в предишния пост, посредством defun се дефинира функция: на съответното име се присвоява списък от форми, които при извикването на функцията се оценяват (т.е. изпъляват) една след друга. ANSI Common Lisp стандарта не уточнява дали по време на дефиницията на функцията формите се превеждат до някакъв byte code или каквото и да било друго, стига при оценяването да се случва това, което е указано в сорс кода. С прости думи -- не става ясно дали еval действа като интерпретатор или като компилатор и ако действа като компилатор, до какъв код компилира. Всяка имплементация на стандарта е свободна да процедира както намери за добре.
Фен-бойчетата на C# и Java знаят, че техните компилатори превеждат до byte code -- някакво вътрешно представяне със специализирани инструкции, които виртуалната машина по някое време (най-често по време на изпълнението) превежда до машинен код за съответния процесор. В Microsoft средите на това му викат Common Language Runtime (CLR), а в Java средите не знам какво му викат, ама е точно толкова дебилно. Защо eval да не създава код, който директно да се изпълява на съответната физическа машина? Знам какво ще чуя: защото не е преносим. И какво от това -- нали сорс кода, бидейки прост текст, е преносим? И ако за съответната платформа има виртуална машина, която по зададен сорс код може да създаде вътрешно представяне, защо трябва да се интересувам от това, дали вътрешното представяне на една архитектура е същото като на друга? Просто разпространявам сорс кода и всичко е ОК. Естествено, това е в разрез с Enterprise мисленето, но пък моята теза е, че именно Enterprise мисленето е в основата на всичко зло. Така че това не е довод, поне не пред мен.
Аз използвам имплементацията SBCL -- Steel Bank Common Lisp. Последните две думи (Common Lisp) са ясни -- името на диалекта, за който си говорим. Първите две (Steel Bank) са бъзик с CMU-CL, чийто fork e SBCL. Университета Carnegie Mellon University (CMU) e именован на Andrew Carnegie -- крупен стоманен (Steel) магнат в Щатите в началото на XX век, и Andrew Mellon -- водещ банкер (Bank) по същото време.
В тази имплементация нещата седят по следния начин: всяко дефинране на функция води до създаването на списък от инструкции, които могат директно да се изпълнят на съответния процесор, на който се е случило това дефиниране. Това има следния недостатък -- ако компилирам нещо върху X86_64, няма да мога да го ftp-осам на PPC машина и да го изпълня там. Но на кой му пука за този use-case така или иначе? Затова пък кода, който е генериран не отстътва по бързодействие на аналогичен код, компилиран със C компилатор. И за да не съм голословен, ще приведа следния пример:
CL-USER> (defun bahor (i j) (+ i (* 2 j)))
BAHOR
Това вече трябва да е ясно на всички, чели предишния пост. Дефинираме функция bahor, която по зададени парметри i и j връща стойност i+2*j. Наблюдавайте сега:
CL-USER> (disassemble #'bahor)
; disassembly for BAHOR
; 05C102CD: 488B55F0 MOV RDX, [RBP-16]
; 2D1: BF04000000 MOV EDI, 4
; 2D6: 4C8D1C25B9020020 LEA R11, [#x200002B9]
; 2DE: 41FFD3 CALL R11
; 2E1: 480F42E3 CMOVB RSP, RBX
; 2E5: 488BFA MOV RDI, RDX
; 2E8: 488B55F8 MOV RDX, [RBP-8]
; 2EC: 4C8D1C25E0010020 LEA R11, [#x200001E0]
; 2F4: 41FFD3 CALL R11
; 2F7: 480F42E3 CMOVB RSP, RBX
; 2FB: 488BE5 MOV RSP, RBP
; 2FE: F8 CLC
; 2FF: 5D POP RBP
; 300: C3 RET
; 301: CC0A BREAK 10
; 303: 02 BYTE #X02
; 304: 18 BYTE #X18
; 305: 54 BYTE #X54
NIL
Опаааа -- какво имаме тук? Първо -- имаме стандартна функция disasseble, която изпечатва листинг на машинния код + асемблера за съответната функция (само помислете колко софтуер трябва да инсталирате, за да получите същата информация за дадена функция на C, не дай си боже на Java). И второ -- машинния код както можем да видим е съставен от инструкции за (в случая) 64-битов X86 процесор. И понеже имам достъп и до PowerPC машина, ето как изглежда аналогичния изход там:
CL-USER> (disassemble #'bahor)
; disassembly for BAHOR
; 5119667C: 92EF0004 STW $LRA,4($CFP)
; 680: 830F0010 LWZ $A0,16($CFP)
; 684: 3B200008 ADDI $A1,$ZERO,8
; 688: 3AF30070 ADDI $LRA,$CODE,112
; 68C: 3CE00400 ADDIS $NL4,$ZERO,1024
; 690: 38E70360 ADDI $NL4,$NL4,864
; 694: 7CE803A6 MTLR $NL4
; 698: 4E800020 BLR
; 69C: 00000000 BYTE #X00, #X00, #X00, #X00
; 6A0: 00001C36 BYTE #X00, #X00, #X1C, #X36
; 6A4: 7ED0B378 MR $CSP,$OCFP
; 6A8: 60000000 NOP
; 6AC: 3A77FF90 ADDI $CODE,$LRA,-112
; 6B0: 7F19C378 MR $A1,$A0
; 6B4: 830F000C LWZ $A0,12($CFP)
; 6B8: 3AF300A0 ADDI $LRA,$CODE,160
; 6BC: 3CA00400 ADDIS $NL2,$ZERO,1024
; 6C0: 38A50200 ADDI $NL2,$NL2,512
; 6C4: 7CA803A6 MTLR $NL2
; 6C8: 4E800020 BLR
; 6CC: 00000000 BYTE #X00, #X00, #X00, #X00
; 6D0: 00002836 BYTE #X00, #X00, #X28, #X36
; 6D4: 7ED0B378 MR $CSP,$OCFP
; 6D8: 60000000 NOP
; 6DC: 3A77FF60 ADDI $CODE,$LRA,-160
; 6E0: 806F0000 LWZ $NL0,0($CFP)
; 6E4: 82EF0004 LWZ $LRA,4($CFP)
; 6E8: 7DF07B78 MR $CSP,$CFP
; 6EC: 7C6F1B78 MR $CFP,$NL0
; 6F0: 3BF70005 ADDI $LIP,$LRA,5
; 6F4: 7FE803A6 MTLR $LIP
; 6F8: 4E800020 BLR
; 6FC: 00000000 BYTE #X00, #X00, #X00, #X00
NIL
Вижда се, че SBCL компилира/интерпретира до машинен код. Т.е. на въпроса колко виртуална е виртуалната му машина -- отговора е "много малко виртуална е".
В този момент C фанатиците доволно потриват ръце и си викат "толкова много код за едно умножение и едно събиране? -- това очевидно не е оптимално". В който момент аз почвам да обяснявам как този код е в състояние да обработи всякакви стойности за i, j и върнатия резултат, стига да се събират в паметта, независимо дали са цели числа, рационални дроби или floating point и давам следния пример:
CL-USER> (bahor 10000000000000000000000000000000000000000000000000000000000 7/19)
190000000000000000000000000000000000000000000000000000000014/19
(това между другото е числото 10 на 58-ма степен + два пъти по 7/19, което е равно на рационалното число, получено като резултат на последния ред)
Но те продължават -- "Е да де, ама аз не искам такива сложнотии, аз искам i и j да са простички цели числа, които се събират в регистри на съответния процесор; резултатa и той се събира в такъв регистър, сигурен съм! И тогава това е overkill, защото не ме интересува колко е всеобхватно, аз искам да е бързо!"
За такива случаи в Common Lisp е предвидено програмистът да може да укаже на компилатора какви всъщност са типовете на променливите. Но забележете -- само с цел оптимизация, а не промяна на семантиката! Функцията ще работи и без да й указвате какви са типовете на променливите; ако ги укажете може просто да заработи по-бързо, но крайния резултат ще е един и същ!
И така, нека да опитаме да укажем типовете, като променим кода да изглежда така:
(defun bahor (i j)
(declare (optimize (speed 3) (safety 0)) (fixnum i j))
(the fixnum (+ i (* 2 j))))
Имаме един допълнителен ред, който започва с declare, в който се казват следните неща преведени на Български: компилаторе, искам да оптимизираш тази функция за бързодействие (speed 3), без да се интересуваш дали типовете на аргументите, които ти подавам, съответстват на истината (safety 0) и променливите i и j са от тип fixnum (Без да изпадам в подробности ще кажа, че съгласно стандарта, променливи от тип fixnum се събират в регистър). Другата промяна е на последния ред, в който казваме "... върнатия резултат и той ще се събере в регистър". И тогава (на x86-64):
CL-USER> (disassemble #'bahor)
; disassembly for BAHOR
; 0351C4F5: 48D1E7 SHL RDI, 1
; 4F8: 4801FA ADD RDX, RDI
; 4FB: 48D1E2 SHL RDX, 1
; 4FE: 488BE5 MOV RSP, RBP
; 501: F8 CLC
; 502: 5D POP RBP
; 503: C3 RET
NIL
CL-USER>
CL-USER> (disassemble #'bahor)
; disassembly for BAHOR
; 0351C4F5: 48D1E7 SHL RDI, 1
; 4F8: 4801FA ADD RDX, RDI
; 4FB: 48D1E2 SHL RDX, 1
; 4FE: 488BE5 MOV RSP, RBP
; 501: F8 CLC
; 502: 5D POP RBP
; 503: C3 RET
NIL
CL-USER>
а на PowerPC:
CL-USER> (disassemble #'bahor)
; disassembly for BAHOR
; 5119D20C: 54A6083C RLWINM $NL3,$NL2,1,0,30
; 10: 7CC43214 ADD $NL3,$NL1,$NL3
; 14: 54D8103A RLWINM $A0,$NL3,2,0,29
; 18: 7DF07B78 MR $CSP,$CFP
; 1C: 7ECFB378 MR $CFP,$OCFP
; 20: 3BF70005 ADDI $LIP,$LRA,5
; 24: 7FE803A6 MTLR $LIP
; 28: 4E800020 BLR
; 2C: 00000000 BYTE #X00, #X00, #X00, #X00
NIL
CL-USER> (disassemble #'bahor)
; disassembly for BAHOR
; 5119D20C: 54A6083C RLWINM $NL3,$NL2,1,0,30
; 10: 7CC43214 ADD $NL3,$NL1,$NL3
; 14: 54D8103A RLWINM $A0,$NL3,2,0,29
; 18: 7DF07B78 MR $CSP,$CFP
; 1C: 7ECFB378 MR $CFP,$OCFP
; 20: 3BF70005 ADDI $LIP,$LRA,5
; 24: 7FE803A6 MTLR $LIP
; 28: 4E800020 BLR
; 2C: 00000000 BYTE #X00, #X00, #X00, #X00
NIL
Смея да твърдя, че това е съизмеримо с кода, който генерира произволен C компилатор за подобна функция. И какво излиза -- ако искаме всеобхватност, просто пишем кода; той работи за всякакви случаи; ако искаме бързодействие и знаем какво правим, можем да го декларираме и ще получим каквото искаме. Ето това за мен е мощна и смислена платформа -- по принцип може да работи за всички случаи, а ако съм много умен, може да го накарам да работи и бързо. А не като Java-та -- каквото и да правиш, все е бавно...
Лека нощ, драги зрители!
събота, 2 март 2013 г.
(здравей-свят)
Имам намерението да ви разкажа в рамките на известен брой публикации за благините на Lisp. Надявам се да ви стане интересно и да получите една различна гледна точка към програмирането. Наясно съм, че конюнктурата не позволява да седнем и да си изкарваме хляба на Lisp в момента -- за съжаление сме "женени" за някакви технологии и няма да получим лесно развод, но това че сме си поръчали, не означава, че не можем да разглеждаме менюто, нали така?
Бидейки на 55 г. Lisp е еволюирал дълго, като през това време е дал началото на концепции като виртуална машина, garbage collection, exception handling, та дори и на конструкцията if-then-else. В началото на XXI век има няколко живи диалекта на Lisp, като най-смисленият за мен се казва Common Lisp. Той е стандартизиран от ANSI и е достатъчно освободен (за разлика напр. от Scheme) за да е всъщност полезен.
Теоретична подготовка
Преди да се втурнем да реализираме "Hello, World!" не е лошо да вкараме малко теоретична подготовка. Lisp е изведен преди 55 г. и е вторият най-стар език за програмиране от високо ниво -- само FORTRAN е с 1 г. по-стар от него. Като казвам "изведен", имам предвид именно това -- той е изведен математически и това го отличава от всички останали упражнения по строене на пясъчни кули под формата на езици за програмиране. Хард-кор феновете могат да прочетат оригиналната статия на John McCarthy от 1958 г. тук. Аз няма да й обръщам много внимание, само ще отбележa, че подобно на машината на Тюринг и тук става въпрос за съвсем малък набор от примитиви (ако не ме лъже паметта 7 на брой), чрез които може да се изгради всеки възможен алгоритъм.Бидейки на 55 г. Lisp е еволюирал дълго, като през това време е дал началото на концепции като виртуална машина, garbage collection, exception handling, та дори и на конструкцията if-then-else. В началото на XXI век има няколко живи диалекта на Lisp, като най-смисленият за мен се казва Common Lisp. Той е стандартизиран от ANSI и е достатъчно освободен (за разлика напр. от Scheme) за да е всъщност полезен.
Lisp е дефиниран като homoiconic език и е първият такъв. На Български това означава, че програмата на Lisp се представя посредством същата структура, с която се представят и данните. Това позволява на дадена Lisp програма да създава, променя и както си иска да манипулира части от Lisp код, вкл. части от своя собствен, без при това да се налага допълнително писане на парсери, генератори на двоичен код, компилатори и т.н. Сега, радетелите за чиста и свята република ще почнат да обясняват колко е вредно да пишем само-модифициращ се код. И сигурно са прави донякъде. Само че ако лежим на тая кълка по-добре да ходим да пасем овцете, защото всяка девелопърска станция без изключение прави точно това: съвкупността от инсталиран софтуер ни позволява да създаваме, променяме и манипулираме други програми, които стават част от инсталирания софтуер. А, и освен това ни позволява да се създаваме, променяме и манипулираме данни по същия начин. С други думи: Lisp изпълнява ролята на цяла (development) машина, от там и термина "виртуална машина". При това всичко се случва по дефиниция, а не защото някой се е сетил (или не се е сетил съответно) да напише компилатор за C и сега се опитва да ни го продаде на промоция за $800 долара.
CL-USER>
(Това преди знака за по-голямо е името на текущия package, което е нещо като namespace-ите на C++, C# и package-ите в Java, но затова -- друг път.)
Има нещо изключително важно, което се съзира след внимателен прочит на горното и това е, че всяко нещо, което Lisp може да прочете си има стойност. Именно намирането на тази стойност е задача на оценяването (Eval).
Числата и стринговете са self-evaluating, т.е. резултата от оценяването им е присъщата им стойност:
CL-USER> 5
5
CL-USER> "БАХОР"
"БАХОР"
(Тук 2-ри и 4-ти ред показва резултата от Print частта на REPL).
Когато става въпрос за символ, като напр. PI, резултата е стойността, която в момента е свързана с това име:
CL-USER> PI
3.141592653589793d0
Свързването (binding) прилича малко на присвояването (assignment), но не е същото, но затова друг път. За целите на настоящия пост е достатъчно да си мислим, че в случая променливата PI има стойност 3.141592653589793d0, която Eval частта на REPL е намерила и съответно Print частта е изпечатала.
Интересното става, когато трябва да се оцени стойността на списък. Каква е стойността на списъка (1 2 3 4) ? Или пък на списъка (трябва да пия кафе сега) ? Тук се процедура по следния начин: първия елемент от списъка трябва да е символ и той се разглежда като име на функция. Ако такава функция има дефинирана, тя се извиква, като останалите елементи от списъка се разглеждат като аргументи на фукцията и се оценяват (по същите тези правила), един по един и отляво надясно. Стойността на списъка е стойността, която функцията връща. Например:
CL-USER> (cos (/ pi 2))
6.123233995736766d-17
Най-напред имаме списък от 2 елемента: първият е символа cos, а вторият е списъка (/ pi 2). Първият елемент се разглежда като име на функция. Има ли такава функция? Има, да, както се сетихте това е функция с един аргумент, имащ смисъла на ъгъл в радиани, и нейната стойност е косинуса от този ъгъл. След като има дефинирана такава функция, остава да я изпълним. За целта обаче трябва първо да се оценят аргументите й, т.е. останалите неща в списъка, а това е от своя страна списъка (/ pi 2). Първия елемент от този списък е символа /, а втория и третия са съответно името pi и числото 2. Има ли дефинирана функция / -- има, тя дели първият си аргумент на всички останали аргументи. Остава да оценим нейните аргументи. Те са атоми и следователно се оценяват както е описано по-горе. Делението се изпълнява и резултата от него PI/2 се използва като аргумент за функцията cos. Сега от своя страна се изпълява и тя и резултата е някакво много близко до нула число (както знаем от Студ. град -- cos от 90 градуса = нула в чашката).
REPL
Като всяка нормална машина, и виртуалната машина на Lisp, когато я стартираме показва промпт (въпрос към Java фен-бойчетата: защо тяхната виртуална машина не прави така?). Има и един друг съвременен език, по който хората напоследък са луднали, който прави същото: нарича се Python. На Lisp-а промпта се нарича REPL и е съкращение от Read-Eval-Print-Loop -- т.е. прочитаме какво иска да ни каже потребителя (Read), изпълняваме го (по-правилния термин е оценяваме го) (Eval) и изпечатваме резултата (Print); след това почваме от начало (Loop). Просто като боб. Ето как изглежда REPL промпта обикновено:CL-USER>
(Това преди знака за по-голямо е името на текущия package, което е нещо като namespace-ите на C++, C# и package-ите в Java, но затова -- друг път.)
Има нещо изключително важно, което се съзира след внимателен прочит на горното и това е, че всяко нещо, което Lisp може да прочете си има стойност. Именно намирането на тази стойност е задача на оценяването (Eval).
Форми и оценяването им
Програмите/данните на Lisp се състоят от неща, които се наричат форми. На най-ниско ниво Lisp разбира от два вида форми: атоми и списъци. Атомите са единични неща, като напр. числото 5, стринга "БАХОР" или името PI (терминът, който се използва в Lisp за означаване на име е символ (symbol). Да не се бърка със символ в смисъла на char). Списъците от своя страна се записват по възможно най-простия начин: като поредица от атоми заградени в кръгли скоби (например този наклонен текст тук в скобите е списък).Числата и стринговете са self-evaluating, т.е. резултата от оценяването им е присъщата им стойност:
CL-USER> 5
5
CL-USER> "БАХОР"
"БАХОР"
(Тук 2-ри и 4-ти ред показва резултата от Print частта на REPL).
Когато става въпрос за символ, като напр. PI, резултата е стойността, която в момента е свързана с това име:
CL-USER> PI
3.141592653589793d0
Свързването (binding) прилича малко на присвояването (assignment), но не е същото, но затова друг път. За целите на настоящия пост е достатъчно да си мислим, че в случая променливата PI има стойност 3.141592653589793d0, която Eval частта на REPL е намерила и съответно Print частта е изпечатала.
Интересното става, когато трябва да се оцени стойността на списък. Каква е стойността на списъка (1 2 3 4) ? Или пък на списъка (трябва да пия кафе сега) ? Тук се процедура по следния начин: първия елемент от списъка трябва да е символ и той се разглежда като име на функция. Ако такава функция има дефинирана, тя се извиква, като останалите елементи от списъка се разглеждат като аргументи на фукцията и се оценяват (по същите тези правила), един по един и отляво надясно. Стойността на списъка е стойността, която функцията връща. Например:
CL-USER> (cos (/ pi 2))
6.123233995736766d-17
Най-напред имаме списък от 2 елемента: първият е символа cos, а вторият е списъка (/ pi 2). Първият елемент се разглежда като име на функция. Има ли такава функция? Има, да, както се сетихте това е функция с един аргумент, имащ смисъла на ъгъл в радиани, и нейната стойност е косинуса от този ъгъл. След като има дефинирана такава функция, остава да я изпълним. За целта обаче трябва първо да се оценят аргументите й, т.е. останалите неща в списъка, а това е от своя страна списъка (/ pi 2). Първия елемент от този списък е символа /, а втория и третия са съответно името pi и числото 2. Има ли дефинирана функция / -- има, тя дели първият си аргумент на всички останали аргументи. Остава да оценим нейните аргументи. Те са атоми и следователно се оценяват както е описано по-горе. Делението се изпълнява и резултата от него PI/2 се използва като аргумент за функцията cos. Сега от своя страна се изпълява и тя и резултата е някакво много близко до нула число (както знаем от Студ. град -- cos от 90 градуса = нула в чашката).
Вариации на тема "Здравей, Свят!"
Първи вариант:
CL-USER> "Здравей, Свят!"
"Здравей, Свят!"
Нищо ново -- Lisp прочете стринга, който му написах, оцени го като самия себе си и ми го изпечата обратно.
Втори вариант:
CL-USER> (format t "Здравей, Свят!~%")
Здравей, Свят!
NIL
Това, което се случва тук, е функцията format. Тя има същата роля както fprintf в C. Първия й аргумент е stream, към който да изпрати изхода. В случая със символа T (който по дефиниция е свързан с булевата стойност True) се указва на функцията да прати резултата на стандартния изход. Следващия аргумент е форматиращия стринг, нищо по-сложно от fprintf. Това, което е по-различно е как се задават полета за печат. Тук, за разлика от C-то не се задават с процент (%), а с тилда (~). Това, което се вижда на края на стринга (~%) е еквивалента на \n в C. Изключително мощна е конструкцията ~A, която печата съответния аргумент в естетически формат, т.е. така, че да е удобно да бъде прочетен от човек.
Прави впечатление, че след изпълнението на функцията се появяват 2 реда. Това е така, защото първия ред е изхода, генериран от функцията и изпратен на стандартния изход, а втория ред е самата стойност на функцията, т.е. резултата от Eval-а (в случая този резултат е NIL -- символ, обратен на T, който по дефиниция е свързан с булевата стойност False). Тук се наблюдава т.н. страничен ефект -- функцията повлиява на обкръжението си освен със стойността си, и по друг начин (в случая изпечатването на стринг на екрана). В някои по-рестриктивни диалекти на Lisp, като например Scheme, страничните ефекти са забранени. Това обаче не е продуктивно и затова към Scheme има по-скоро само академичен интерес.
Трети вариант:
CL-USER> (format t "~A~%" "Здравей, Свят!")
Здравей, Свят!
NIL
Същото като преди, само че този път във форматиращия стринг е използвана конструкцията ~A, която печата стойността на съответния аргумент, в случая стойността на стринга "Здравей, Свят!". Това е едно към едно с fprintf(stdout, "%s\n", "Здравей, Свят!") на C.
Последен вариант:
CL-USER> (defun здравей-свят () (format t "Здравей, Свят!~%"))
ЗДРАВЕЙ-СВЯТ
CL-USER> (здравей-свят)
Здравей, Свят!
NIL
Ето до това трябваше да стигнем. На първия ред изпълняваме функцията defun, която дефинира нова функция (нали се сещате -- малко по-нагоре, в теоретичната подготовка -- "...позволява да се създава, променя и манипулира код..."). Първият й аргумент е името на новата функция, в случая здравей-свят. Усещам как любителите на camelCase-а почват да се въртят като обрани евреи. Безспорно от трите имена
locate_image_and_perform_stuff_on_it
locateImageAndPerformStuffOnIt
locate-image-and-perform-stuff-on-it
последното е най-четимо. В Lisp практически няма (е, почти няма) ограничение за буквите и символите, които могат да присъстват в имената на променливи и функции. Затова и мога да дефинирам функция с име на Български, че ако искам и на Японски:
CL-USER> (defun 世界ようこそう () (format t "世界、ようこそう！~%"))
世界ようこそう
CL-USER> (世界ようこそう)
世界、ようこそう！
NIL
Втория аргумент на defun е списък с аргументи за новата функция. В случая тя няма такива, затова списъка е празен. Останалите елементи от списъка на defun формират тялото на новата функция.
Резултата от изпълнението на defun (т.е. това, което се вижда на 2-рия ред) е името на дефинираната (или ре-дефинираната!) функция. Когато тя се извика (което става на 3-ти ред), формите в тялото й се изпълняват една по една. Резултатът от изпълнението на функцията е стойността на последната изпълнена форма от тялото й. В случая резултата е резултата от извикването на format, т.е. както и преди -- NIL.
Резултата от изпълнението на defun (т.е. това, което се вижда на 2-рия ред) е името на дефинираната (или ре-дефинираната!) функция. Когато тя се извика (което става на 3-ти ред), формите в тялото й се изпълняват една по една. Резултатът от изпълнението на функцията е стойността на последната изпълнена форма от тялото й. В случая резултата е резултата от извикването на format, т.е. както и преди -- NIL.
Толкова за днес. Лека нощ, драги зрители, дано съм успял да Ви заинтригувам!
петък, 1 март 2013 г.
Нещо като OpenMP...на 27 реда код
Често (особено на чашка) съм се опитвал да обяснявам на хората, с които надигаме съответната течност, колко смислен e Lisp-а и колко безмислена -- Java-та. Този пост е още един пример в подкрепа на първото.
Става въпрос за високо-производителни изчисления (HPC). Знаем, че мулти-трединга, особено в контекста на съвременните многоядрени процесори, е един от механизмите за постигане на по-добра производителност. Когато говорим конкретно за математически изчисления (а и не само), едно от нещата, които се ползват от съответното комюнити е OpenMP. За тези, които не са наясно, с две думи: вместо да занимаваме нАучните работници да мислят в термините тредове, синхронизация, race conditions и др., им даваме достатъчно проста абстракция, с която да си раз-паралелят кода, като например следното (това съм го взел от Wikipedia, признавам си):
Единственото странно нещо в този код е на 6-ти ред. Въпросната прагма указва на компилатора, че следващия стейтмънт (т.е. for-а с цялото си тяло) представлява всъщност паралелен for. Това е една от т.н. worksharing constructs, основна концепция в OpenMP, чиято семантика е следната: създават се няколко паралелни треда, които изпълняват тялото на цикъла; N-те итерации на цикъла се разпределят между тях; на края има имлицитна синхронизация, така че на ред 11 тредовете пристигат заедно (ако въобще пристигат до там няколко треда, защото би могло и да приключват на ред 9).
Разбира се в OpenMP има и куп други подобни благини, разни сложнотии и възможности за финно доизпипване на как точно искаме да ни се изпълни паралелния код, но в края на краищата, моя опит показва, че в 99% от програмите, които ползват OpenMP, 99% от конструкциите са parallel for.
Очевидно OpenMP е много смислено нещо. Използва се поголовно в световен мащаб. В него са наляти много време и пари, направен е консорциум, уеб-сайт, документация, пачнати са компилатори, направени са библиотеки и въобще бая труд е хвърлен за да се направи да работи. А то работи посредством специални издания на компилаторите, напр. за да проима идея за #pragma omp ..., даден компилатор трябва да е специално създаден за това. Още веднъж ще наблегна на това, защото е важно -- не е достатъчно само да свържете към кода си някоя библиотека, за да ползвате OpenMP -- трябва ви специален компилатор, който да разбира от съответните прагми. Има издания на повечето смислени компилатори за C/C++/FORTRAN, които кльопат директивите. gcc след версия 4.3.2 (ако не се лъжа) поддържа OpenMP по подразбиране.
Сигурно вече се питате "Aми за Java има ли го?". Само от уважение към колегите от EPCC към Университета в Единбург няма да нареча JOMP "абоминация", но сериозно си го мисля. Аз не смятам да обяснявам какво точно е JOMP, защото получавам позиви само като се сетя, но ако ви влече -- прочетете си го сами. Само ще кажа, че това е research проект, с няколко нАучни публикации, екип от нАучни работници и т.н. Искам да уточня -- не са виновни колегите, виновна е нефелната Java, на която дори да се издрайфаш не можеш като хората.
Та да си дойдем на думата. Викам си "след като това е толкова полезно и след като в 98% от случаите се използва конструкцията за parallel for, не мога ли да се опитам да си реализирам един такъв на Lisp?". И така -- седнах и за 1/2 час написах това:
Забележете, че става въпрос за 27 реда, от които един празен, събрани на 80 колони (както всеки сорс код следва да бъде). Имайки горното, мога да напиша това:
което отговаря на main функцията на C програмата, дадена малко по-горе. Единственото, което съм променил спрямо стандартен Lisp е, че вместо dotimes съм написал dotimes*. Получавам същия ефект като при parallel for конструкцията на OpenMP. Е, не е като да съм направил сайт, документация, нямам борд на директорите на консорциум, нито екип от 100-200 човека, които да направят пачове на всеки известен компилатор, но пък от друга страна...не ми и трябват. В интерес на истината моите 27 реда не могат да се сравняват със софистицизма на OpenMP, но реализират 98% от usage pattern-а му. Представете си какво би могло да се направи с 270 или 2700 реда на Lisp. А за JOMP не искам и да си спомням, защото ще сънувам кошмари (наистина, прочетете описанието, за да го сравните после с 27-те реда).
Лека нощ драги зрители, ако на някой му е станало интересно какво пише в 27-те реда по-горе, да напише коментар, за да знам и ще го обясня в нарочна публикация тук.
Става въпрос за високо-производителни изчисления (HPC). Знаем, че мулти-трединга, особено в контекста на съвременните многоядрени процесори, е един от механизмите за постигане на по-добра производителност. Когато говорим конкретно за математически изчисления (а и не само), едно от нещата, които се ползват от съответното комюнити е OpenMP. За тези, които не са наясно, с две думи: вместо да занимаваме нАучните работници да мислят в термините тредове, синхронизация, race conditions и др., им даваме достатъчно проста абстракция, с която да си раз-паралелят кода, като например следното (това съм го взел от Wikipedia, признавам си):
1 int main(int argc, char *argv[])
2 {
3 const int N = 100000;
4 int i, a[N];
5
6 #pragma omp parallel for
7 for (i = 0; i < N; i++) {
8 a[i] = 2 * i;
9 }
10
11 return 0;
12 }
Единственото странно нещо в този код е на 6-ти ред. Въпросната прагма указва на компилатора, че следващия стейтмънт (т.е. for-а с цялото си тяло) представлява всъщност паралелен for. Това е една от т.н. worksharing constructs, основна концепция в OpenMP, чиято семантика е следната: създават се няколко паралелни треда, които изпълняват тялото на цикъла; N-те итерации на цикъла се разпределят между тях; на края има имлицитна синхронизация, така че на ред 11 тредовете пристигат заедно (ако въобще пристигат до там няколко треда, защото би могло и да приключват на ред 9).
Разбира се в OpenMP има и куп други подобни благини, разни сложнотии и възможности за финно доизпипване на как точно искаме да ни се изпълни паралелния код, но в края на краищата, моя опит показва, че в 99% от програмите, които ползват OpenMP, 99% от конструкциите са parallel for.
Очевидно OpenMP е много смислено нещо. Използва се поголовно в световен мащаб. В него са наляти много време и пари, направен е консорциум, уеб-сайт, документация, пачнати са компилатори, направени са библиотеки и въобще бая труд е хвърлен за да се направи да работи. А то работи посредством специални издания на компилаторите, напр. за да проима идея за #pragma omp ..., даден компилатор трябва да е специално създаден за това. Още веднъж ще наблегна на това, защото е важно -- не е достатъчно само да свържете към кода си някоя библиотека, за да ползвате OpenMP -- трябва ви специален компилатор, който да разбира от съответните прагми. Има издания на повечето смислени компилатори за C/C++/FORTRAN, които кльопат директивите. gcc след версия 4.3.2 (ако не се лъжа) поддържа OpenMP по подразбиране.
Сигурно вече се питате "Aми за Java има ли го?". Само от уважение към колегите от EPCC към Университета в Единбург няма да нареча JOMP "абоминация", но сериозно си го мисля. Аз не смятам да обяснявам какво точно е JOMP, защото получавам позиви само като се сетя, но ако ви влече -- прочетете си го сами. Само ще кажа, че това е research проект, с няколко нАучни публикации, екип от нАучни работници и т.н. Искам да уточня -- не са виновни колегите, виновна е нефелната Java, на която дори да се издрайфаш не можеш като хората.
Та да си дойдем на думата. Викам си "след като това е толкова полезно и след като в 98% от случаите се използва конструкцията за parallel for, не мога ли да се опитам да си реализирам един такъв на Lisp?". И така -- седнах и за 1/2 час написах това:
1 (defparameter *default-num-threads* (or (sb-posix::getenv "NUM_THREADS") 2)) 2 3 (defmacro dotimes* ((var count &optional (num-threads *default-num-threads*) 4 (result nil)) &body body) 5 (let ((thread-list (gensym "THREAD-LIST-")) 6 (i (gensym "I-")) 7 (q (gensym "Q-")) 8 (r (gensym "R-")) 9 (s (gensym "S-")) 10 (e (gensym "E-"))) 11 `(let* ((,thread-list ()) 12 (%num-threads ,num-threads)) 13 (multiple-value-bind (,q ,r) 14 (ceiling ,count %num-threads) 15 (dotimes (,i %num-threads) 16 (let ((%thread-id ,i) ,s ,e) 17 (declare (ignorable %thread-id)) 18 (if (< ,i (+ %num-threads ,r)) 19 (setf ,s (* ,i ,q) ,e (+ ,s ,q)) 20 (setf ,s (+ %num-threads ,r (* ,i (1- ,q))) ,e (+ ,s (1- ,q)))) 21 (push (sb-thread:make-thread 22 #'(lambda () 23 (do ((,var ,s (1+ ,var))) 24 ((>= ,var ,e) ,result) 25 ,@body))) 26 ,thread-list)))) 27 (mapcar #'(lambda (th) (sb-thread:join-thread th)) ,thread-list))))
Забележете, че става въпрос за 27 реда, от които един празен, събрани на 80 колони (както всеки сорс код следва да бъде). Имайки горното, мога да напиша това:
(let* ((n 100000)
(a (make-array n)))
(dotimes* (i n)
(setf (aref a i) (* 2 i))))
което отговаря на main функцията на C програмата, дадена малко по-горе. Единственото, което съм променил спрямо стандартен Lisp е, че вместо dotimes съм написал dotimes*. Получавам същия ефект като при parallel for конструкцията на OpenMP. Е, не е като да съм направил сайт, документация, нямам борд на директорите на консорциум, нито екип от 100-200 човека, които да направят пачове на всеки известен компилатор, но пък от друга страна...не ми и трябват. В интерес на истината моите 27 реда не могат да се сравняват със софистицизма на OpenMP, но реализират 98% от usage pattern-а му. Представете си какво би могло да се направи с 270 или 2700 реда на Lisp. А за JOMP не искам и да си спомням, защото ще сънувам кошмари (наистина, прочетете описанието, за да го сравните после с 27-те реда).
Лека нощ драги зрители, ако на някой му е станало интересно какво пише в 27-те реда по-горе, да напише коментар, за да знам и ще го обясня в нарочна публикация тук.
Абонамент за:
Коментари (Atom)