На первый взгляд, отличия самые минимальные, or1 ну разве что чуть громоздче выглядит. Оки-доки, залез в R6RS draft чтобы узнать, что же такого жуткого написано про "or" в R6RS:
(or <test> ...) Syntax: The <test>s must be expressions. Semantics: If there are no <test>s, #f is returned. Otherwise, the <test> expressions are evaluated from left to right until a <test> returns a true value val (see section 5.7) or the last <test> is reached. In the former case, the or expression returns val without evaluating the remaining expressions. In the latter case, the last expression is evaluated and its values are returned.
The or keyword could be defined in terms of if using syntax-rules (see section 11.19) as follows:
(define-syntax or
(syntax-rules ()
((or) #f)
((or test) test)
((or test1 test2 ...)
(let ((x test1))
(if x x (or test2 ...))))))
The last <test> expression is in tail context if the or expression itself is; see section 11.20.
Последняя фраза и наводит на ответ MC>- Каким недостатком обладает "неправильный" по сравнению с правильным?
Определение or1 не подчиняется требованию хвостовой рекурсии, а or2 — подчиняется.
MC>- Приведите пример кода, который будет по разному вести себя для "неправильной" и "правильной" реализации "or".
Достаточно залудить какие-нибудь длинные рекурсивные вычисления, версия без хвостовой рекурсии быстро сожрёт всю память.
MC>PS: Все-же этюд касается не только scheme, так что, если надо, могу немного рассказать о семантике вышеозначенных макросов или попытаться накидать аналогичные макросы, скажем, на nemerle.
гм... весьма специфичный этюд, однако.
Этюд актуален для любого языка с аппликативным порядком вычисления и макросами, однако в силу происхождения этюда — я предлагаю его в контексте scheme.
В scheme "or" — short-circuit операция, которая принимает произвольное число аргументов. Реализовать "or" можно в виде макроса.
Вот вариант реализация "or":
(define-syntax or
(syntax-rules ()
((_) #f)
((_ e1 e2 ...)
(let ((t e1))
(if t t (or e2 ...))))))
Этот вариант "or" будем считать "неправильным", т.к. он обладает определенным недостатком (с приходом r6rs можно сказать, что двумя).
Вот такой вариант "or" (в нем появляется дополнительное условие) будем считать "правильным":
(define-syntax or
(syntax-rules ()
((_) #f)
((_ e) e)
((_ e1 e2 e3 ...)
(let ((t e1))
(if t t (or e2 e3 ...))))))
В связи с этим, предлагаю ответить на два вопроса.
— Каким недостатком обладает "неправильный" по сравнению с правильным?
— Приведите пример кода, который будет по разному вести себя для "неправильной" и "правильной" реализации "or".
PS: Все-же этюд касается не только scheme, так что, если надо, могу немного рассказать о семантике вышеозначенных макросов или попытаться накидать аналогичные макросы, скажем, на nemerle.
Кодт,
К>Хе, а если первым элементом, удовлетворяющим критерию, будет элемент "f#"? К>Нет уж, тут нужен Maybe или нечто подобное.
В реализации монад (гы-гы) на Схеме мне встретился даже такой изврат:
(define fail (vector 'fail))
Такое значение будет не eq? любому другому. Ну конечно до тех пор, пока кто-нибудь не переопределит eq? подходящим образом
К>Вспомнился анекдот. К>- Скажи, как переводится с английского "I don't know"? К>- "Я не знаю". К>- Ну вот... никто не знает...
English variation:
(We take you now to the Oval Office.)
George: Condi! Nice to see you. What's happening?
Condi: Sir, I have the report here about the new leader of China.
George: Great. Lay it on me.
Condi: Hu is the new leader of China.
George: That's what I want to know.
Condi: That's what I'm telling you.
George: That's what I'm asking you. Who is the new leader of China?
Condi: Yes.
George: I mean the fellow's name.
Condi: Hu.
George: The guy in China.
Condi: Hu.
George: The new leader of China.
Condi: Hu.
George: The Chinaman!
Condi: Hu is leading China.
George: Now whaddya' asking me for?
Condi: I'm telling you Hu is leading China.
George: Well, I'm asking you. Who is leading China?
Condi: That's the man's name.
George: That's who's name?
Condi: Yes.
George: Will you or will you not tell me the name of the new leader of China?
Condi: Yes, sir.
George: Yassir? Yassir Arafat is in China? I thought he was in the Middle East.
Condi: That's correct.
George: Then who is in China?
Condi: Yes, sir.
George: Yassir is in China?
Condi: No, sir.
George: Then who is?
Condi: Yes, sir.
George: Yassir?
Condi: No, sir.
George: Look, Condi. I need to know the name of the new leader of China. Get me the Secretary General of the U.N. on the phone.
Condi: Kofi?
George: No, thanks.
Condi: You want Kofi?
George: No.
Condi: You don't want Kofi.
George: No. But now that you mention it, I could use a glass of milk. And then get me the U.N.
Condi: Yes, sir.
George: Not Yassir! The guy at the U.N.
Condi: Kofi?
George: Milk! Will you please make the call?
Condi: And call who?
George: Who is the guy at the U.N?
Condi: Hu is the guy in China.
George: Will you stay out of China?!
Condi: Yes, sir.
George: And stay out of the Middle East! Just get me the guy at the U.N.
Condi: Kofi.
George: All right! With cream and two sugars. Now get on the phone.
(Condi picks up the phone.)
Condi: Rice, here.
George: Rice? Good idea. And a couple of egg rolls, too. Maybe we should send some to the guy in China. And the Middle East. Can you get Chinese food in the Middle East?
К>>>И тут же стали путать списки с #t. MC>>Почему же путать? Для того, чтобы различать объекты разных типов, есть соответствующие предикаты: boolean?, list? и т.п. А if и логические операции различают только #f и "не #f".
К>Вот потому и путать: переменная или функция содержит список, а его истолковали как булевское значение. (Только в лиспе и в схеме эта трактовка различается).
К>В этом плане, скажем, питон дружественнее: там приведение к булю основано на смысле. К>Ложью считаются К>- нули всех числовых типов К>- атом None (нулевой указатель) К>- пустые контейнеры (списки, кортежи, строки, словари)
К>В лиспе смысл был примерно тот же, но он оказался замаскирован дурным минимализмом. То есть непонятно стало — то ли мы приравниваем "пусто" к "ложно", то ли тупо сэкономили на одном атоме (для "истина", однако, ввели атом t).
Я категорически против того, чтобы считать пустой список за #f. Приведу пример: мы читаем из xml
и формируем список '(42292 42298 42300), если xml будет просто <UnreadMessages/>, то сформируется пустой список. В любом случае список на выходе — это сигнал о том, что чтение было успешно, а вот если чего-то обвалилось, то пожалуйста на этот счёт есть #f.
Здравствуйте, Mr.Cat, Вы писали:
MC>PS: Все-же этюд касается не только scheme, так что, если надо, могу немного рассказать о семантике вышеозначенных макросов или попытаться накидать аналогичные макросы, скажем, на nemerle.
А можно на Common Lisp? Я вообще не понимаю схемовских макросов. =)
Здравствуйте, jartur, Вы писали: J>А можно на Common Lisp? Я вообще не понимаю схемовских макросов. =)
Охх, попробую. Случаем, нет у тебя годной ссылки на "quickstart" по макросам и паттерн-матчингу (syntax-rules — суть паттерн-матчинг для s-выражений) в cl?
MC>Охх, попробую. Случаем, нет у тебя годной ссылки на "quickstart" по макросам и паттерн-матчингу (syntax-rules — суть паттерн-матчинг для s-выражений) в cl?
А в общих чертах, там все тупо:
(defmacro name (params*)
body*)
Впрочем по сути макрос — просто функция, которая возвращает форму. При этом ` (backquote) используется для экранирования вичисления, а , и ,@ для их форсирования. Ну например
(defmacro if1 (test true-branch &optional else-branch)
"My super if."
`(cond (,test ,true-branch)
(t ,else-branch)))
Тогда
(if1 (= a b)
(+ a b)
(- a b))
Развернется в (COND ((= A B) (+ A B)) (T (- A B))).
При этом возможен захват переменных и прочие неприятности, потому для имен переменных локальных для макроса нужно использовать gensym. А паттерны можно задавать в строке params. Например
(defmacro for ((a b) &body body)
(let ((a-var (gensym)))
`(do ((,a-var ,a (+ 1 ,a-var)))
((>= ,a-var ,b))
,@body)))
Тогда
(for (1 5)
(+ 1 1)
(+ 2 2))
превращается в (DO ((#:G826 1 (+ 1 #:G826))) ((>= #:G826 5)) (+ 1 1) (+ 2 2))
Если бы мы не использовали gensym, и вместо #:G826 стояло бы SOMEVAR, то в случае наличия SOMEVAR в lexical scope во время вызова макроса, мы бы поимели неприятный эффект. Ладно shadowing, а если бы мы деструктивно присваивали бы что-то SOMEBVAR внутри макроса? Ну понятно, в общем. Никакой гигиены =)
Ну да ладно, лучше в книжке прочитать, там подробнее и понятнее.
Здравствуйте, jartur, Вы писали: J>Вообще можно здесь прочитать: http://www.gigamonkeys.com/book/macros-defining-your-own.html
Ммм, точно. Как-то я позабыл про practical common lisp (как-то даже начинал читать, да бросил). Что ж, попробую переписать в cl-макросы...
Re: [Этюд]Макрос "or"
От:
Аноним
Дата:
29.04.09 10:48
Оценка:
Можно подсказку? А то ничего умнее
(define-syntax or
(syntax-rules ()
((_) #f)
((_ e1 e2 ...)
(let ((t e1))
(if t t (or e2 ...))))))
(define-syntax or1
(syntax-rules ()
((_) #f)
((_ e) e)
((_ e1 e2 e3 ...)
(let ((t e1))
(if t t (or1 e2 e3 ...))))))
(define (if x y z) (error ""))
(or false) ; ошибка
(or1 false) ; нет ошибки
Здравствуйте, Аноним, Вы писали: А>Я еще не отчаялся, так что лучше тонкую
Ок.
В принципе, недостаток у "неправильного" or довольно безобидный. Однако из-за этого он не удовлетворяет r6rs.
Re[5]: [Этюд]Макрос "or"
От:
Аноним
Дата:
30.04.09 10:22
Оценка:
Здравствуйте, Mr.Cat, Вы писали:
MC>Здравствуйте, Аноним, Вы писали: А>>Я еще не отчаялся, так что лучше тонкую MC>) Ок. MC>В принципе, недостаток у "неправильного" or довольно безобидный. Однако из-за этого он не удовлетворяет r6rs.
Ммм.. Scheme я знаю только в рамках SICP и непродолжительных ковыряний в доках по PLT Scheme. Так что для меня отличия r5rs и r6rs это rocket since
Здравствуйте, Lazy Cjow Rhrr, Вы писали: MC>>- Каким недостатком обладает "неправильный" по сравнению с правильным? LCR>Определение or1 не подчиняется требованию хвостовой рекурсии, а or2 — подчиняется.
Именно. Если "правильный" or находится в хвостовой позиции — последний операнд тоже стоит в хвостовой позиции. "Неправильный" or такого не обеспечивает
Хотя здесь отметили, что имплементации могли бы оптимизировать "неправильный" or до состояния "правильного" (но вот, например, chicken не оптимизирует).
К>вернёт не булевское значение, вместо того, чтобы заругаться на месте.
Ага.
А вообще, в scheme любое значение, кроме #f, считается истинным с точки зрения if, or, and и т.п.
он не гигиеничный?
потому что в syntax-rules все никак руки не дойдут разобраться
C>Этюд актуален для любого языка с аппликативным порядком вычисления и макросами, однако в силу происхождения этюда — я предлагаю его в контексте scheme.
MC>В scheme "or" — short-circuit операция, которая принимает произвольное число аргументов. Реализовать "or" можно в виде макроса. MC>Вот вариант реализация "or": MC>
MC>(define-syntax or
MC> (syntax-rules ()
MC> ((_) #f)
MC> ((_ e1 e2 ...)
MC> (let ((t e1))
MC> (if t t (or e2 ...))))))
MC>
MC>Этот вариант "or" будем считать "неправильным", т.к. он обладает определенным недостатком (с приходом r6rs можно сказать, что двумя).
MC>Вот такой вариант "or" (в нем появляется дополнительное условие) будем считать "правильным": MC>
MC>В связи с этим, предлагаю ответить на два вопроса.
MC>- Каким недостатком обладает "неправильный" по сравнению с правильным? MC>- Приведите пример кода, который будет по разному вести себя для "неправильной" и "правильной" реализации "or".
MC>PS: Все-же этюд касается не только scheme, так что, если надо, могу немного рассказать о семантике вышеозначенных макросов или попытаться накидать аналогичные макросы, скажем, на nemerle.
Здравствуйте, GSergey, Вы писали: GS>Вот вариант для SCM Scheme GS>он не гигиеничный?
Гигиена — свойство самой макро-системы (syntax-rules, syntactic-closures и т.п.) а не конкретного макроса.
Re[2]: [Этюд]Макрос "or"
От:
Аноним
Дата:
11.05.09 04:21
Оценка:
GS>Здравствуйте, Mr.Cat, Вы писали:
GS>Вот вариант для SCM Scheme
GS>(defmacro or2 ( . args ) GS> (if (null? args) #f GS> `(if ,(car args) #t GS> (or2 ,@(cdr args)))))
GS>он не гигиеничный?
Во первых, да, он негигиеничный. Во вторых, он не является аналогом схемовского or, потому как последний возвращает первое не-#f значение, а Ваш or2 возвращает только #t или #f.
GS>потому что в syntax-rules все никак руки не дойдут разобраться
А вот как раз syntax-rules — простой до примитивизма. Там и разбираться то нечего — просто выучить очередной pattern-matching синтаксис (довольно интуитивно-понятный, к слову). syntax-case — гораздо мощнее, гибче и соответственно сложнее в нюансах.
Re[3]: [Этюд]Макрос "or"
От:
Аноним
Дата:
11.05.09 04:26
Оценка:
GS>>Вот вариант для SCM Scheme GS>>он не гигиеничный? MC>Гигиена — свойство самой макро-системы (syntax-rules, syntactic-closures и т.п.) а не конкретного макроса.
Автоматическая гигиена — свойство макросистемы, а гигиена — свойство самих макросов (результата их раскрытия)
hygiene condition for macro expansion:
“Generated identifiers that become binding instances in the completely expanded program must only bind variables that are generated at the same transcription step.”
Простой пример: автоматически гигеническая макросистема syntax-case позволяет нарушать гигиену и писать негигенические макросы.
Здравствуйте, Аноним, Вы писали: А>Автоматическая гигиена — свойство макросистемы, а гигиена — свойство самих макросов (результата их раскрытия)
Да, пожалуй так будет правильнее.
Здравствуйте, Кодт, Вы писали: К>Зачем тогда отказались от лисповского nil? Чтобы не путать с пустым списком?
Я так понимаю, #f было введено как универсальное "пустое" значение, которое можно возвращать как признак ошибки/неудачи. Например, при поиске первого подходящего элемента в списке — как еще различить 2 случая "критерию не удовлетворяет ни один элемент" и "первым элементом, удовлетворяющим критерию, является пустой список"?
К>И тут же стали путать списки с #t.
Почему же путать? Для того, чтобы различать объекты разных типов, есть соответствующие предикаты: boolean?, list? и т.п. А if и логические операции различают только #f и "не #f".
Здравствуйте, Mr.Cat, Вы писали: MC>Я так понимаю, #f было введено как универсальное "пустое" значение, которое можно возвращать как признак ошибки/неудачи.
Т.е. я хотел сказать, что пустой список Сассмана/whoever в роли такого значения почему-то не устраивал — потому и ввели новое.
Здравствуйте, Mr.Cat, Вы писали:
К>>Зачем тогда отказались от лисповского nil? Чтобы не путать с пустым списком? MC>Я так понимаю, #f было введено как универсальное "пустое" значение, которое можно возвращать как признак ошибки/неудачи. Например, при поиске первого подходящего элемента в списке — как еще различить 2 случая "критерию не удовлетворяет ни один элемент" и "первым элементом, удовлетворяющим критерию, является пустой список"?
Хе, а если первым элементом, удовлетворяющим критерию, будет элемент "f#"?
Нет уж, тут нужен Maybe или нечто подобное.
Вспомнился анекдот.
— Скажи, как переводится с английского "I don't know"?
— "Я не знаю".
— Ну вот... никто не знает...
К>>И тут же стали путать списки с #t. MC>Почему же путать? Для того, чтобы различать объекты разных типов, есть соответствующие предикаты: boolean?, list? и т.п. А if и логические операции различают только #f и "не #f".
Вот потому и путать: переменная или функция содержит список, а его истолковали как булевское значение. (Только в лиспе и в схеме эта трактовка различается).
В этом плане, скажем, питон дружественнее: там приведение к булю основано на смысле.
Ложью считаются
— нули всех числовых типов
— атом None (нулевой указатель)
— пустые контейнеры (списки, кортежи, строки, словари)
В лиспе смысл был примерно тот же, но он оказался замаскирован дурным минимализмом. То есть непонятно стало — то ли мы приравниваем "пусто" к "ложно", то ли тупо сэкономили на одном атоме (для "истина", однако, ввели атом t).
Здравствуйте, Кодт, Вы писали: К>Хе, а если первым элементом, удовлетворяющим критерию, будет элемент "f#"?
Ну вот почему-то Сассман (или кто там) решил, что #f можно сделать козлом отпущения.
К>Нет уж, тут нужен Maybe или нечто подобное.
Ну так пожалуйста — можно возвращать этот самый Maybe — пару "#t, значение", либо "#f, диагностика-ошибки". Но вот надо ли?
К>Вот потому и путать: переменная или функция содержит список, а его истолковали как булевское значение. (Только в лиспе и в схеме эта трактовка различается). К>В этом плане, скажем, питон дружественнее: там приведение к булю основано на смысле.
Честно говоря, меня устраивают оба варианта.
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
К>>Нет уж, тут нужен Maybe или нечто подобное.
LCR>В реализации монад (гы-гы) на Схеме мне встретился даже такой изврат: LCR>
LCR>(define fail (vector 'fail))
LCR>
LCR>Такое значение будет не eq? любому другому. Ну конечно до тех пор, пока кто-нибудь не переопределит eq? подходящим образом
И как его диагностировать? Типа, уж послала так послала?
Впрочем, элементарно-ватсон! Где-то недавно проскакивала тема — как проверять на равенство NaN, при том, что на нём равенство тоже сломано.
(define fail? (x) (not (eq? x x)))
LCR>Я категорически против того, чтобы считать пустой список за #f. Приведу пример: мы читаем из xml LCR>
LCR>и формируем список '(42292 42298 42300), если xml будет просто <UnreadMessages/>, то сформируется пустой список. В любом случае список на выходе — это сигнал о том, что чтение было успешно, а вот если чего-то обвалилось, то пожалуйста на этот счёт есть #f.
И снова Maybe. Не надо валить в одну кучу значения и сигналы.
По той же самой причине, если неаккуратно кодировать, можно нарваться на проблемы с русской буквой 'я' в Си.
char c;
while(true)
{
c = getchar(); // прочитали символ либо признак конца/ошибки - int getchar(void)if(c == EOF) break; // EOF - это (int)-1
printf("<%02X>", (unsigned char)c); // вывели в hex-формате, например
}
Правда, в Си возвращаемый тип заведомо шире и позволяет выразить и то и другое.
Что касается твоего списка, то напрашивается очень простой ответ. Нужно возвращать список списков.
<Messages><int>1</int><int>2</int></Messages> ---> '((1 2))
<Messages></Messages> ---> '(())
<Messages><int>1</int></Messages><Messages><int>2</int></Messages> ---> '((1) (2)) - если это в принципе допустимо
пусто/облом ---> '() - он же nil
Здравствуйте, Кодт, Вы писали: К>И как его диагностировать? Типа, уж послала так послала? К>Впрочем, элементарно-ватсон! Где-то недавно проскакивала тема — как проверять на равенство NaN, при том, что на нём равенство тоже сломано. К>
К>(define fail? (x) (not (eq? x x)))
К>
Да eq? (eqv? и equal?) по-моему, сломаны by design.
Здравствуйте, Mr.Cat, Вы писали:
MC>Да eq? (eqv? и equal?) по-моему, сломаны by design.
Я не про nan, я про fail говорил. Если для fail не выполняется eq? сам себе, то... "если фортуна повернулась к вам задом, не расстраивайтесь, а воспользуйтесь".
Здравствуйте, Кодт, Вы писали:
К>И как его диагностировать? Типа, уж послала так послала? К>Впрочем, элементарно-ватсон! Где-то недавно проскакивала тема — как проверять на равенство NaN, при том, что на нём равенство тоже сломано. К>
Кодт,
К>Что касается твоего списка, то напрашивается очень простой ответ. Нужно возвращать список списков. К>
К><Messages><int>1</int><int>2</int></Messages> ---> '((1 2))
К><Messages></Messages> ---> '(())
К><Messages><int>1</int></Messages>
К><Messages><int>2</int></Messages> ---> '((1) (2)) - если это в принципе допустимо
К>пусто/облом ---> '() - он же nil
К>
К>Вполне себе maybe.
Ну конечно, ты решаешь проблему выше введением дополнительного слоя абстракции. Любую проблему можно так решить (за некоторым исключением). Просто получается чуть менее удобно — потом придётся выковыривать само значение:
(let ((l (parse xml))
(if l ; типа рассматривает пустой список как ложь
(do-stuff-with (car l)) ; фи!
(display "try again"))))
Хаскель спасает то, что такие слова как let, in, data и т.п. являются зарезервированными, и поэтому никто не может ничего изменить, и поэтому Maybe кажется таким незыблемым — Nothing — это Nothing, Just — это Just, и паттерн-матчинг работает как всегда работал. А вот в условиях "повышенной гибкости" ничего такого нет, поэтому любое предопределённое поведение можно изменить:
(define if (lambda (x y z) 'omg))
(display (if 1 2 3)) ; выведет omg
Следоветельно и любое определение Maybe не железобетонно. Конечно, никто специально не отстреливает себе выступающие части тела, переопределяя ради прикола стандартные формы, однако лисперам/схемерам нравится само существование возможности переопределить всё нахрен.
LCR>Хаскель спасает то, что такие слова как let, in, data и т.п. являются зарезервированными, и поэтому никто не может ничего изменить, и поэтому Maybe кажется таким незыблемым — Nothing — это Nothing, Just — это Just, и паттерн-матчинг работает как всегда работал. А вот в условиях "повышенной гибкости" ничего такого нет, поэтому любое предопределённое поведение можно изменить: LCR>
LCR> (define if (lambda (x y z) 'omg))
LCR> (display (if 1 2 3)) ; выведет omg
LCR>
LCR>Следоветельно и любое определение Maybe не железобетонно. Конечно, никто специально не отстреливает себе выступающие части тела, переопределяя ради прикола стандартные формы, однако лисперам/схемерам нравится само существование возможности переопределить всё нахрен.