Lisp. Сравнение с образцами.
Беру свои слова обратно, и выкладываю это пост.
swizard был прав, что после введения ADT, паттерн-матчинг просто необходим, иначе исходники напоминают ужас, летащий на крыльях cond'а ©. Тем не менее паттерн-матчинг выглядит в лиспе достаточно плохо. Настолько плохо, что некоторые отказываются от программирования на лиспе.
Паттерн-матчинг не будет противоречить, принятой форме def, и в добавок будет иметь специальную форму case:
(case expr
(pattern-expr COND)
(pattern-expr COND)
... )
Как компилятор мог бы преобразовывать несколько def с паттерн матчингом, в несколько def без него?
Пример 1 Обычный факториал с матчингом в case
(def (fact n) (case n
(0 1)
(n (* n (fact (- n 1)))) ))Пример 2 Тот же факториал с матчингом в def:
(def (fact 0) 1)
(def (fact n) (* n (fact (- n 1))))пример 2 в пример 1 преобразуется исходя из спиcка значений символа
У каждого определения в примере 1 мы избавляемся от матчинга в def, перенося его в case и добавляя next, чтобы перейти к следующему определению в случае, если сравнение с образцом будет неуспешным. Пример 2 будет эквивалентен:
(def (fact n) (case n (0 1) (n (next fact n)) ))
(def (fact n) (case n (n (* n (fact (- n 1)))) ))Так должен будет поступать компилятор, если ему потребуется переводить def с паттерн-матчингом в def без него...
Далее, мы подставляем второе определение в первое на место next.
(def (fact n) (case n
(0 1)
(n (case n
(n (* n (fact (- n 1)))) ) ))Учитывая, что вложенный case не имеет смысла, получим
(def (fact n) (case n
(0 1)
(n (* n (fact (- n 1)))) ))что эквивалентно определению в примере 1.
Теперь о выражении pattern-expr:
Тем не менее здесь ничего не сказано о том, как матчить списки. Идея проста: CONS-ячейка - это объект ADT, и такие встроенные вызовы, как consp (предикат CONS-ячейки), конструкторы cons/nil и селекторы car/cdr определяются в одну ADT-декларацию:(consp nil (cons car cdr))
т. е. выражение (a . b) является всего лишь синтаксическим сахаром (cons a b), а выражение () - синтаксическим сахаром nil. Это значит nil/cons/consp можно использовать в выражениях образцов.
Несколько примеров с эквивалентными примерами на Хаскелле.
(def (length nil) 0)
(def (length (cons _ xs)) (+ 1 (length xs)))length [] = 0
length (_: xs) = 1 + length xs(def (map _ nil) nil)
(def (map f (cons x xs)) (cons (f x) (map f xs)))map _ [] = []
map f (x: xs) = f x: map f xs(def (tails nil) '(()))
(def (tails ((cons _ xs). xxs)) (cons xxs (tails xs)))tails [] = [[]]
tails xxs@(_: xs) = xxs: tails xs(def (sign 0) 0)
(def (sign (for n (> 0))) 1)
(def (sign (for n (< 0))) -1)sign 0 = 0
sign n | n > 0 = 1
sign n | n < 0 = -1(def (fact 0) 1)
(def (fact (for n (> 0))) (* n (fact (- n 1))))
(def (fact n) 'undefined)хм... допустим так
fact 0 = 1
fact n | n > 0 = n * fact (n - 1)
fact n = error "undefined"
Эти примеры примитивны. Есть более сложные определения для примеров?
На мой взгляд, получаемое достаточно неплохо для чтения и написания кода.
swizard был прав, что после введения ADT, паттерн-матчинг просто необходим, иначе исходники напоминают ужас, летащий на крыльях cond'а ©. Тем не менее паттерн-матчинг выглядит в лиспе достаточно плохо. Настолько плохо, что некоторые отказываются от программирования на лиспе.
Паттерн-матчинг не будет противоречить, принятой форме def, и в добавок будет иметь специальную форму case:
(case expr
(pattern-expr COND)
(pattern-expr COND)
... )
- expr - выражение, которое будет сравниваться с образцами pattern-expr
- COND - неявный cond, который изпользуется в def
Как компилятор мог бы преобразовывать несколько def с паттерн матчингом, в несколько def без него?
Пример 1 Обычный факториал с матчингом в case
(def (fact n) (case n
(0 1)
(n (* n (fact (- n 1)))) ))Пример 2 Тот же факториал с матчингом в def:
(def (fact 0) 1)
(def (fact n) (* n (fact (- n 1))))пример 2 в пример 1 преобразуется исходя из спиcка значений символа
У каждого определения в примере 1 мы избавляемся от матчинга в def, перенося его в case и добавляя next, чтобы перейти к следующему определению в случае, если сравнение с образцом будет неуспешным. Пример 2 будет эквивалентен:
(def (fact n) (case n (0 1) (n (next fact n)) ))
(def (fact n) (case n (n (* n (fact (- n 1)))) ))Так должен будет поступать компилятор, если ему потребуется переводить def с паттерн-матчингом в def без него...
Далее, мы подставляем второе определение в первое на место next.
(def (fact n) (case n
(0 1)
(n (case n
(n (* n (fact (- n 1)))) ) ))Учитывая, что вложенный case не имеет смысла, получим
(def (fact n) (case n
(0 1)
(n (* n (fact (- n 1)))) ))что эквивалентно определению в примере 1.
Теперь о выражении pattern-expr:
- x - любое значение
- _ - значение будет проигонорировано
- (CONSTR y) - любое значение y из конструктора CONSTR
- (TYPENAME obj) - любое значение obj типа TYPENAME
- (quote x) или 'x - значение должно быть равно x (автоквотируемые строки и числа, также)
- (for pattern p) - образец pattern должен удовлетворять предикату p
- (pattern . v) - успешно проматченное выражение pattern является значением символа v
Тем не менее здесь ничего не сказано о том, как матчить списки. Идея проста: CONS-ячейка - это объект ADT, и такие встроенные вызовы, как consp (предикат CONS-ячейки), конструкторы cons/nil и селекторы car/cdr определяются в одну ADT-декларацию:(consp nil (cons car cdr))
т. е. выражение (a . b) является всего лишь синтаксическим сахаром (cons a b), а выражение () - синтаксическим сахаром nil. Это значит nil/cons/consp можно использовать в выражениях образцов.
Несколько примеров с эквивалентными примерами на Хаскелле.
(def (length nil) 0)
(def (length (cons _ xs)) (+ 1 (length xs)))length [] = 0
length (_: xs) = 1 + length xs(def (map _ nil) nil)
(def (map f (cons x xs)) (cons (f x) (map f xs)))map _ [] = []
map f (x: xs) = f x: map f xs(def (tails nil) '(()))
(def (tails ((cons _ xs). xxs)) (cons xxs (tails xs)))tails [] = [[]]
tails xxs@(_: xs) = xxs: tails xs(def (sign 0) 0)
(def (sign (for n (> 0))) 1)
(def (sign (for n (< 0))) -1)sign 0 = 0
sign n | n > 0 = 1
sign n | n < 0 = -1(def (fact 0) 1)
(def (fact (for n (> 0))) (* n (fact (- n 1))))
(def (fact n) 'undefined)хм... допустим так
fact 0 = 1
fact n | n > 0 = n * fact (n - 1)
fact n = error "undefined"
Эти примеры примитивны. Есть более сложные определения для примеров?
На мой взгляд, получаемое достаточно неплохо для чтения и написания кода.