LINUX.ORG.RU

Самый лучший pattern matching где взять?

 , , ,


1

5

Вопрос по дизайну языка. В CL есть destructuring-bind, но он что-то слабоват. Либо ты попал в один шаблон, либо ошибка - никакого destructuring-case нет. Кроме того, квазицитаты, которые тут просятся, использовать нельзя. По сути задействован синтаксис из определения функции, т.е. можно обязательные, необязательные, параметры ключи и сопоставление головы и хвоста списка из консов.

Когда пытаешься использовать pattern matching, сразу становится ясно, что этого мало. Нужно:

1. Нужна возможность сопоставления с несколькими шаблонами, как в case.

2. В шаблоне не всё является параметром, иногда нужно, чтобы была возможность задать фиксированные ключевые слова, которые там должны быть, но нам не нужно их видеть среди переменных.

3. Нужно иногда проверять тип значения, к-рое мы сопоставляем.

4. Иногда нужно использовать разные предикаты для сопоставления. Т.е. если мы ищем шаблон со строкой «abc», то иногда нам нужно искать без учёта регистра.

5. Если в языке есть квазицитаты, должна быть возможность строить шаблон из них, где подстановочные места будут переменными.

Я попробовал пару библиотек pattern-matching для CL, но в итоге как-то стал без него обходиться (почему-то это не сильно меня опечалило).

Тем не менее, ищутся люди, интенсивно применяющие pattern matching, и от таких людей я хотел бы узнать: язык на котором они это делают, степень вашего удовлетворения технологией и ссылка на описание технологии.

★★★★★

Как ни банально --- Ocaml. Большого опыта с этим делом не имел, но всё запрашиваемое в пунктах 1-4 присутствует.

ugoday ★★★★★ ()

Называть это «технологией» - много чести. Просто языковая конструкция. Если не пользуешься ADT - в основном не нужна.

tailgunner ★★★★★ ()

Кстати вот какая у меня идея появилась, навеяло. pattern matching всегда будет ограничен. Он либо слишком слабый, либо слишком запутанный. Как кто-то сказал, «если у вас была проблема и вы попытались решить её регекспами, то теперь у вас две проблемы». Поэтому, наверное имеет смысл конструкция break, как в switch. Тогда образец находит сопоставление только «вчерне», в меру своих ограниченных возможностей. А внутри составного оператора можно обложить переменные из образца отдельным условием и, если всё нормально, сделать возврат из оператора с помощью «вернуть», как делает break в switch. То есть, не нужно перегружать сопоставление с образцом лишними смыслами. Например, поиск отрицательного числа:

сопоставлять-с-образцами Ю 
  имя СЮ // имя конструкции нужно для возврата
  или-ошибка ("Ждали отрицательное число, а нашли ~S",Ю)
  образец квц квп(П -- двойное-плавающее) кнк
    если П < 0.0 то 
      СЮ.вернуть П
    кне
  // поскольку здесь нет возврата, будем сравнивать дальше
  образец квц квп(Ч -- число) кнк
    если Ч < 0 то
      СЮ.вернуть Ч
    кне
    // здесь выполнение пойдёт дальше, на генерацию ошибки
кнс 

P.S. добавил 5-е требование - квазицитаты.

den73 ★★★★★ ()
Последнее исправление: den73 (всего исправлений: 2)

а optima чем не устроила?

anonymous ()

Тем не менее, ищутся люди, интенсивно применяющие pattern matching

Использую racket/match и Haskell. Всем доволен.

В CL вместо destructuring-bind гораздо удобнее использовать metabang-bind

Именно для match в CL похоже правильный вариант: http://quickdocs.org/trivia/ . Но не использовал.

monk ★★★★★ ()
Ответ на: комментарий от den73

образец квц квп(Ч — число) кнк

ну... кто первый, кроме автора, расскажешь что это за фигня? :)

допустим ч — число --- проверка типа. а остальное? :)

Rastafarra ★★★ ()
Ответ на: комментарий от den73

Кстати вот какая у меня идея появилась, навеяло. pattern matching всегда будет ограничен. Он либо слишком слабый, либо слишком запутанный.

Пример по ссылке в нормальном matching'е решается

> (match '(1 2 3 4 5 6)
    [(list 1 a ... 4 _ ...) a])
'(2 3)

образец находит сопоставление только «вчерне», в меру своих ограниченных возможностей. А внутри составного оператора можно обложить переменные из образца отдельным условием

Делается обычно что-то наподобие

(match -2.0 
  [(? (and real? (</c 0)) a) a]
  [(? (and integer? (</c 0)) a) a])

// поскольку здесь нет возврата, будем сравнивать дальше

Вот это легко пропустить. Синтаксической ошибки не будет, а будет трудноуловимая ошибка «почему условие проверки не срабатывает?».

monk ★★★★★ ()
Ответ на: комментарий от Rastafarra

ну... кто первый, кроме автора, расскажешь что это за фигня?

квц — похоже, квазицитата

квп — квазицитата.переменная

кнк — конец квазицитаты.

Это всё ИМХО.

monk ★★★★★ ()
Ответ на: комментарий от monk

trivia - спасибо, посмотрю.

Посмотрел racket/match. Слишком много, на мой вкус. Какую долю из описания racket/match ты использовал на практике? Не было ли проблем с отладкой?

Про Хаскель - мне понравилась компактность описания, но есть ли там возможность сопоставления по вызову произвольного предиката над объектом? Я что-то не увидел здесь

metabang-bind пока не смотрел.

den73 ★★★★★ ()
Ответ на: комментарий от den73

Слишком много, на мой вкус.

Там в описании, если убрать конструкторы, то останется только (and ...), (or ...), (not ...), (? ...), (app ...).

Какую долю из описания racket/match ты использовал на практике?

(? ...), (list ...), (list-rest ...), (vector ...), (struct-id ...) — самое частое, иначе структуру долго разбирать, (reqexp ...).

но есть ли там возможность сопоставления по вызову произвольного предиката над объектом

Neg x@(Double y) | y < 0.0 = x
Neg x@(Int y) | y < 0 = x

или

Neg x = case x of
          Double y -> if y < 0.0 then x
          Int y -> if y < 0 then x

monk ★★★★★ ()

ты пробовал объяснить паттерн-матчинг людям, которые ниасиливают англоязычный синтаксис?

anonymous ()
Ответ на: комментарий от monk

Ну это не совсем то: Вот что я хочу:

Neg x@(MyPredicate y) = x
Где MyPredicate - это не тип, а предикат. Хотя в языке с упором на типы отсутствие сопоставления по предикату оправдано хотя бы идеологически, или может быть у них можно определять тип через предикат, так что ладно. Другая проблема, сопоставление с данными должно допускать выбора способа сравнения. Например, более-менее понятен шаблон «число 1», а если тип структурный, то можно уже сравнивать очень большим количеством способом. Скажем, структуру можно сравнивать по указателю (по идентичности) и почленно. Есть ли в Хаскеле возможность задать способ сопоставления с константой?

den73 ★★★★★ ()

Erlang:

case Var of
    Int when is_integer(Int) -> ....;
    #some_struct{Member1 = ..., Member2 = ...} -> ....;
    Lst when is_list(Lst) -> ....;
    <<?IP_VERSION:4, HLen:4, SrvcType:8, TotLen:16, 
      ID:16, Flgs:3, FragOff:13,
      TTL:8, Proto:8, HdrChkSum:16,
      SrcIP:32,
      DestIP:32, RestDgram/binary>> when HLen>=5, 4*HLen=<DgramSize -> ....;
    "String" -> ....;
    [1, 2, 3, {4, 5}, _, _, [_ | _], "Some string"] -> ....
end

cyanide_regime ()
Ответ на: комментарий от cyanide_regime

Не понял, <<>> - это набор битов, HLen:4 - это что? Размер в битах? А можно ли вместо 1 в предпоследней строчке подставить некий предикат и ещё переменную, в к-рую это можно записать?

den73 ★★★★★ ()
Ответ на: комментарий от monk

Дочитав до определения локальных функций, я понял, что metabang-bind - это разновидность моей perga, но моя perga лучше.

den73 ★★★★★ ()

Самый лучший pattern matching где взять?

В Prolog.

quantum-troll ★★★★★ ()
Ответ на: комментарий от anonymous

Плюсую за Erlang

Минусую за Erlang. В нём нельзя произвольные функции в гардах использовать, что очень и очень бесит.

hateyoufeel ★★★★★ ()
Ответ на: комментарий от den73

Value:Size/TypeSpecifierList - общая форма для <<>> - Bit Syntax. [A, 2, 3, 4, 5] when (A) > 0 -> ...

anonymous ()
Ответ на: комментарий от hateyoufeel

А зачем засорять? В этом и суть, что доступен минимальный список доступных предикатов

anonymous ()
Ответ на: комментарий от den73

Вот что я хочу

это записывается как

Neg x | MyPredicate x = x

В твоём варианте неясно, что такое y. Конструкция @ подразумевает раскрытие структуры, например,

Growing4 x@([a b c d]) | a < b && b < c && c < d = x
Growing4 _ = []

Если x является списком и элементы удовлетворяют условию, вернуть x.

Скажем, структуру можно сравнивать по указателю (по идентичности) и почленно.

Если это литерал, то какой смысл её сравнивать по идентичности. В шаблоне могут быть либо литералы, либо условия (а там сам выбираешь метод). Конкретно для Хаскеля разницы в методе сравнения нет, так как изменяемых объектов в этом языке не существует.

monk ★★★★★ ()
Ответ на: комментарий от anonymous

В этом и суть, что доступен минимальный список доступных предикатов

В этом и суть, что этот минимальный список недостаточен.

hateyoufeel ★★★★★ ()
Ответ на: комментарий от cyanide_regime

У обычных функций могут быть побочные эффекты.

Кто мешает, например, добавить функциям атрибут pure для таких целей? Я не говорю уже о полноценной системе типов, которая бы это могла разрузить, как в Haskell.

hateyoufeel ★★★★★ ()
Ответ на: комментарий от monk

Если это литерал, то какой смысл её сравнивать по идентичности.

Прямой. Всякого рода уникальные идентификаторы не обязаны же быть числами. Они могут быть и указателями на структуру, содержащую полезные данные. Идентификатор и данные в одном лице.

Конкретно для Хаскеля разницы в методе сравнения нет, так как изменяемых объектов в этом языке не существует.

Ну ладно, а если я хочу «поматчить» строку с учётом/без учёта регистра?> так как изменяемых объектов в этом языке не существует. А хеш-таблицы как же? Всегда мысленно копируются?

den73 ★★★★★ ()
Ответ на: комментарий от anonymous

[A, 2, 3, 4, 5] when (A) > 0

Имеет право на существование, хотя имеет смысл проверять when (это гард называется что ли?) не после разбора всего образца, а в момент, когда разбираем именно A. Например, если шаблон содержит в себе «или», то можно обусловить дальнейшее поведение разбора.

den73 ★★★★★ ()
Ответ на: комментарий от quantum-troll

Пролог. Хм. Ну я бы не сказал, что он удовлетворяет моим требованиям. В сумме с унификацией получается кудряво, но я говорю именно про сопоставление с образцом. Можно ссылку на доку?

den73 ★★★★★ ()
Ответ на: комментарий от cyanide_regime

У обычных функций могут быть побочные эффекты.

И это прекрасно. Например, они могут вывести что-то в поток трассировки :) Но и атрибут pure тоже ввести можно.

den73 ★★★★★ ()
Ответ на: комментарий от hateyoufeel

Кто мешает, например, добавить функциям атрибут pure для таких целей?

Возможность динамической перезагрузки кода, благодаря которой, в гардах зависимых модулей могут оказаться не-pure функции.

cyanide_regime ()
Ответ на: комментарий от den73

И это прекрасно. Например, они могут вывести что-то в поток трассировки :) Но и атрибут pure тоже ввести можно.

В Erlang'e это и без гардов можно сделать.

cyanide_regime ()
Ответ на: комментарий от cyanide_regime

Возможность динамической перезагрузки кода, благодаря которой, в гардах зависимых модулей могут оказаться не-pure функции.

А может вообще функции не оказаться, если она была удалена, и вызов в старом коде выдаст исключение. Таких возможностей выстрелить себе в ногу до жопы и больше, но ограничение языка - это тоже довольно убого.

hateyoufeel ★★★★★ ()
Ответ на: комментарий от den73

Про Хаскель - мне понравилась компактность описания, но есть ли там возможность сопоставления по вызову произвольного предиката над объектом? Я что-то не увидел здесь

Есть. Делается через расширение, которое называется ViewPatterns

dave ★★★★★ ()

Короче, всем спасибо, обойдёмся пока вовсе без pattern matching :)

den73 ★★★★★ ()

haskell, scala, прекрасные паттернматчинги. может где лучше есть , я не знаю

AndreyKl ★★★★★ ()
Ответ на: комментарий от den73

унификация это и есть «сопоставление с образцом», только не кастрированное как в этих ваших «функциональных» недоязычках.

anonymous ()
Ответ на: комментарий от den73

Сам то понял что написал? Вобщем оптима - один из самых крутых паттерн матчингов на сегодня, плюс он еще и расширяем (чего не скажешь о эрланге и друзьях):

OPTIMA> (match '(1 . "test")
          ((guard (cons _ x) (numberp x)) (1+ x))
          ((guard (cons _ x) (stringp x)) (format nil "1+~a" x)))
"1+test"
OPTIMA> (match '(1 . 5)
          ((guard (cons _ x) (numberp x)) (1+ x))
          ((guard (cons _ x) (stringp x)) (format nil "1+~a" x)))
6
loz ★★★★★ ()
Ответ на: комментарий от cyanide_regime

Окей, и что дальше? А в датацентр может молния ударить, а главного архитектора проекта может автобус сбить, прикинь.

Отсутствие юзерских гардов это существенный минус, один из многих которые делают эрланг таким ущербным языком.

loz ★★★★★ ()
Ответ на: комментарий от loz

я-то понял, что написал, хотя ошибки не исключены. Общая идея такова: да, хорошо встроить сторожа прямо в шаблон, например, в таком случае:

(match '(1 . "test")
  ((cons _ (guard x (stringp x))) (print x)))
Но если сторож относится ко всему результату сопоставления, то в общем-то сторож и само сопоставление с образцом становятся между собой ортогональны, и их желательно отделить друг от друга. Я бы хотел что-то типа того:
(match '(1 . "test") ; этот код не работает
  ((cons x "test")
   (cond 
     ((numberp x) (делай-раз))
     ((stringp x) (делай-два))
     (t (перейти-к-следующему-образцу-для-сопоставления))))
  ((cons x y)
     ...))
Так понятнее? И к тебе такой вопрос: насколько интенсивно пользуешься pattern matching и в каких языках?

den73 ★★★★★ ()
Последнее исправление: den73 (всего исправлений: 1)
Ответ на: комментарий от den73

Но если сторож относится ко всему результату сопоставления

Сторож это просто форма которая может использовать символы из сопостовления первой формы.

То что ты хочешь сделать можно легко написать макросом который будет трансформироваться в вызов оптимы, из

(match '(1 . 5)
          ((my-guard (cons _ x) 
               ((numberp x) (1+ x))
               ((stringp x) (format nil "1+~a" x)))))
в
(match '(1 . 5)
          ((guard (cons _ x) (numberp x)) (1+ x))
          ((guard (cons _ x) (stringp x)) (format nil "1+~a" x)))

насколько интенсивно пользуешься pattern matching и в каких языках?

Только в эрланге пользовался, он там повсюду, потому что в нем паттерн матчинг реально полезен, в других языках на которых я пишу это максимум `a, b = pair`. Аналог лиспового паттерн матчинга (почти) никуда не завезли, потому что цитирования и макросистемы нигде нет, сам понимаешь.

loz ★★★★★ ()
Последнее исправление: loz (всего исправлений: 1)
Ответ на: комментарий от loz

Спасибо!

потому что цитирования и макросистемы нигде нет,

Последнее время стало слишком много языков. В Scala и Haskell что-то на тему макросов декларируется.

То что ты хочешь сделать можно легко написать макросом

Я не говорю, что нельзя или нелегко, я говорю, что ортогональные вещи иногда стоит делать отдельными для соблюдения простоты.

den73 ★★★★★ ()
Ответ на: комментарий от den73

Я бы хотел что-то типа того:

На racket/match

(match '(1 . "test") ; этот работает
  ((cons x "test") (=> перейти-к-следующему-образцу-для-сопоставления)
   (cond 
     ((number? x) (делай-раз))
     ((string? x) (делай-два))
     (else (перейти-к-следующему-образцу-для-сопоставления))))
  ((cons x y)
     ...))
monk ★★★★★ ()
Последнее исправление: monk (всего исправлений: 1)
Ответ на: комментарий от monk

Да, там это есть, я видел и может быть даже об этом написал.

den73 ★★★★★ ()
Ответ на: комментарий от loz

он там повсюду, потому что в нем паттерн матчинг реально полезен

А почему он там реально полезен, можно поинтересоваться? Потому что сделан хорошо или есть какая-то специфика языка?

den73 ★★★★★ ()
Ответ на: комментарий от loz

«But i agree, custom guards that can not only cause side effects but can crash, throw exceptions, do send and receives, pause code etc.. etc.. would be a horrible thing that i would never want to see in erlang You would need a try catch for just function names etc... tho maybe there is a compromise that could somehow be worked out.»

anonymous ()
Ответ на: комментарий от den73

Потому что сделан хорошо или есть какая-то специфика языка?

Специфика языка. Много мелких процессов и падение процесса-обработчика при ошибке во входящем сообщении. Ну и системная библиотека под матчинг заточена.

server() ->
    {ok, LSock} = gen_tcp:listen(5678, [binary, {packet, 0}, 
                                        {active, false}]),
    {ok, Sock} = gen_tcp:accept(LSock),
    {ok, Bin} = do_recv(Sock, []),
    ok = gen_tcp:close(Sock),
    Bin.

do_recv(Sock, Bs) ->
    case gen_tcp:recv(Sock, 0) of
        {ok, B} ->
            do_recv(Sock, [Bs, B]);
        {error, closed} ->
            {ok, list_to_binary(Bs)}
    end.

Здесь с маленькой буквы символы, с большой — переменные. Фактически, мы на каждом шаге проверяем, что результат имеет форму {ok, ...}. Если это не так, будет падение процесса. В платформе OTP куча подсистем, делающих программирование в таком стиле удобным (супервайзеры, логгеры, ...)

Также и в Haskell. С учётом того, что язык чистый и ленивый, паттерн-матчинг позволяет сразу разбирать входящее выражение. Раньше вообще можно было писать в стиле

f 0 = 1
f (n+1) = f n * (n+1)

monk ★★★★★ ()

Господа, не забывайте также, что важная деталь нормального паттерн матчинга — проверка в compile-time все ли инварианты типа обрабатываются. В лисповых матчерах этого нет (или куда-то уже завезли?).

grouzen ★★ ()
Ответ на: комментарий от anonymous

tho maybe there is a compromise that could somehow be worked out

Не делать их «особенной» частью языка? В общелиспе вон - это просто библиотека, и никакие специальные ограничения нигде не нужны.

loz ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.