Prolog

В описании блога фигурирует слово Prolog но пока ни одного поста, посвященного этому интересному языку я не удосужился создать. Хочу исправить это досадное упущение.

Если честно, мне лень описывать синтаксис и особенности пролога, кому интересно, без труда найдут достаточное количество материала в интернете, благо язык довольно академичный. Скажу лишь, чем меня он заинтересовал. Дело в том, что пролог, по сути единственный язык, предлагающий качественно другой подход к программированию, чем хорошо известные императивный, ООП (который, по сути, тоже императивный, но нацелен на структурирование и модульность), функциональный. Можно назвать этот подход декларативно-логическим.
Не претендуя на точность терминологии, этот подход можно определить как такой, при котором программа представляет собой описанние теми или иными конструкциями языка программирования самого условия задачи. Роль ЯП при этом понять это описание, и сделать из него некоторый вывод, который окажется ни чем иным как правильным решением задачи.
Проиллюстрируем, что под этим подразумевается. Возьмем следующую задачу.

Условие задачи: Сократ - человек. Все люди смертны.
Найти: Смертен ли Сократ?

Запишем условие в терминах языка пролога (со знака % начинаются комментарии):

% Сократ - человек
human(sokrat).
% Платон - тоже человек
human(platon).

% Чтобы некто был смертным, он должен быть человеком
mortal(Someone) :- human(Someone).

теперь спросим пролог систему, смертен ли Сократ:

?- mortal(sokrat).

Yes % да

?- mortal(stranger).

No % нет, поскольку пролог система не знает ничего о stranger и потому, не может ответить на вопрос

% Мы можем спросить какие смертные существа известны системе:
?- mortal(Who).

Who = platon ;

Who = sokrat

Именно исходя из этой идеи программирования неудивительно, что именно пролог стал незаменимым средством в исследованях задач искусственного интеллекта, а именно, задачах поиска с возвратом, символьных вычислений, экспертных систем, анализа естественного языка, и множества других.

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

Собственно, хочу привести для примера решение на прологе задачи о расстановке на шахматной доске 8 ферзей, так чтоб они не били друг друга, основанное на приведенном в книге Братко И. Программирование на языке ПРОЛОГ для искусственного интеллекта (кстати, очень хорошая книга, рекомендую).

% будем искать решение как набор 8 координат вида X/Y каждого из ферзей
% при этом понятно, что поскольку все вертикали так или иначе будут заняты
% задача сводится к отысканию соответствующих Y - координат
getSolution(S):-
        S=[1/_,2/_,3/_,4/_,5/_,6/_,7/_,8/_],
        solution(S).

% доска 0x0 без ферзей очевидно является решением
solution([]).

% доска NxN является решением, если является решением её под-доска (N-1)*(N-1), 
% а первый ферзь не бьет ферзей на этой под-доске.
solution([X/Y | Others]) :-
        solution(Others),
        member(Y, [1, 2, 3, 4, 5, 6, 7, 8]),
        nokill(X/Y, Others).
                  
% очевидно что ферзь с любыми координатами не бьет ферзей из пустого массива, 
% поскольку просто некого бить
nokill(_, []).                

% ферзь не бьет набор ферзей если он не бьет первого ферзя из набора 
% и не бьет остальных ферзей набора                 
nokill(X/Y, [X1/Y1 | Others]) :-
        Y =\= Y1,      % на разных горизонталях     
        Y1-Y =\= X1-X, % на разных диагоналях
        Y1-Y =\= X-X1,
        nokill(X/Y, Others).

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

1 ?- getSolution(P).

P = [1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1] ;

P = [1/5, 2/2, 3/4, 4/7, 5/3, 6/8, 7/6, 8/1] ;

P = [1/3, 2/5, 3/2, 4/8, 5/6, 6/4, 7/7, 8/1] ;

P = [1/3, 2/6, 3/4, 4/2, 5/8, 6/5, 7/7, 8/1] ;

P = [1/5, 2/7, 3/1, 4/3, 5/8, 6/6, 7/4, 8/2] ;
...

Кстати, а как это будет выглядеть на вашем любимом языке программирования? =)

Кстати, тут можно посозерцать решение той же задачи на рефале, еще одном интересном языке функционального программирования, идейно перекликающимся с прологом, кстати, создатель которого - наш соотечественник Валентин Федорович Турчин (вики).

(Читать полностью...)

Функциональный питон

На досуге пришла идея используя list comprehensions изобразить на питоне некое подобие функционального программирования.

И вот что получилось:

[ [[[[[
  (
    (
      p('Multiplications:'),
      doMult(4, 10),
      l()
    ),
    (
      p(),
      p('Fib:'),
      [
        (
          p('%d->%d' % (i, fib(i)))
        )
        for i in range(1, 10)
      ]
    ),
    (
      p(),
      p('Qsort:'),
      p(qsort([2,1,4,-11,9]))
    )
  )
  
  for doMult in [lambda I, J:
    [
      (
        l() if j==1 else [],
        p('%sx%s=%s' % (i, j, i * j))
      )
      for i in range(1, I)
      for j in range(1, J)]
  ]]  
  
  for qsort in [lambda L:
      [] if L==[]
        else [
          qsort([e for e in T if e<=H]) + [H] + qsort([e for e in T if e>H])
            for H in [L[0]]
            for T in [L[1:]]
          ][-1]
  ]]
  
  for fib in [lambda n:
    n if n<2 else fib(n-1) + fib(n-2)
  ]]
  
  for l in [lambda:
    p('-' * 10)    
  ]]  
  
  for p in [lambda s='':
    w(str(s)+'\n')
  ]]
  
  for w in [
    __import__('sys').stdout.write
  ]
]

Вывод:

Multiplications:
----------
1x1=1
1x2=2
1x3=3
1x4=4
1x5=5
1x6=6
1x7=7
1x8=8
1x9=9
----------
2x1=2
2x2=4
2x3=6
2x4=8
2x5=10
2x6=12
2x7=14
2x8=16
2x9=18
----------
3x1=3
3x2=6
3x3=9
3x4=12
3x5=15
3x6=18
3x7=21
3x8=24
3x9=27
----------

Fib:
1->1
2->1
3->2
4->3
5->5
6->8
7->13
8->21
9->34

Qsort:
[-11, 1, 2, 4, 9]

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

(Читать полностью...)