Oz (язык программирования)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Oz
Семантика:

функциональный, процедурный, декларативный, объектно-ориентированный, вычисления с ограничениями, Н-модели, параллельные вычисления

Тип исполнения:

компилируемый

Появился в:

1991

Автор(ы):

Gert Smolka & his students

Релиз:

1.4.0 (July 3 2008)

Основные реализации:

Mozart

Испытал влияние:

Пролог

Повлиял на:

Alice

Сайт:

mozart-oz.org

Oz — учебный язык программирования высокого уровня, в котором совмещены функциональная, процедурная, декларативная семантики.

История разработки[править | править вики-текст]

Разработку языка программирования Oz начал в 1991 году профессор Gert Smolka со своими студентами из лаборатории систем программирования Лувенского католического университета в Бельгии. В 1996 году к процессу разработки подключились Seif Haridi и Peter Van Roy из Шведского института информатики (Swedish Institute of Computer Science), которые использовали этот язык в своём классическом учебнике Concepts, Techniques, and Models of Computer Programming[1]. С 1999 до 2005 года язык развивался под руководством международной научно-исследовательской группы (Mozart Consortium), состоящей из трёх университетов: Саарский университет, Шведский институт информатики (Swedish Institute of Computer Science) и Лувенский католический университет.

Высококачественная открытая реализация языка Oz — Mozart включает IDE на основе расширения редактора Emacs, компилятор, отладчик, профайлер и другие утилиты.

Управление разработкой системы программирования Mozart в 2005 года было передано группе разработчиков (Mozart Board) с целью привлечения более широкого круга исследователей. Эта система выпущена группой Mozart Consortium под свободной лицензией и впоследствии перенесена (портирована) на большинство популярных операционных систем, в том числе Unix, FreeBSD, Linux, Microsoft Windows и Mac OS X.

Особенности языка[править | править вики-текст]

Язык программирования Oz включает в себя большинство концепций популярных парадигм программирования, в том числе логического, функционального (причём как ленивые, так и «энергичные» вычисления), императивного, объектно-ориентированного, программирования с ограничениями, распределённого и параллельного программирования. С одной стороны, Oz обладает простой формальной семантикой, а с другой — для него создана эффективная программная реализация.

К основным преимуществам этого языка относится поддержка мультипарадигменного программирования, программирования в ограничениях, а также распределённое программирование. Так, на уровне языковых конструкций поддерживается простое и естественное распараллеливание и распределение вычислений по сети, что позволяет легко создавать отказоустойчивые приложения. Для реализации программирования в ограничениях в языке Oz вводится концепция вычислительных пространств (computation spaces), в которой происходит поиск решения. Это позволяет решать задачи математического программирования, и в частности задачи дискретной оптимизации.

Обзор языка[править | править вики-текст]

Структуры данных[править | править вики-текст]

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

Основные структуры данных:

  • Числа (целые или с плавающей запятой)
  • Записи (для группировки элементов данных): circle(x:0 y:1 radius:3 color:blue style:dots)
  • Списки (простые линейные структуры):
'|'(2 '|'(4 '|'(6 '|'(8 nil))))
2|(4|(6|(8|nil))) % синтаксический сахар
2|4|6|8|nil % ещё более краткая запись
[2 4 6 8] % эффективное применение синтаксического сахара для реализации лаконичного синтаксиса

Эти значения являются константными сущностями первого рода (first class), типизация при этом динамическая.

Функции[править | править вики-текст]

Функции являются сущностями первого рода, что позволяет применять парадигму функционального программирования:

fun {Fact N} % факториал
   if N =< 0 then 1 else N*{Fact N-1} end
end

fun {Comb N K} % количество сочетаний
   {Fact N} div ({Fact K} * {Fact N-K}) % целые числа могут иметь сколь угодно большое значение
end

fun {SumList List} % сумма элементов списка
   case List of nil then 0
   [] H|T then H+{SumList T} % сопоставление с образцом для списка
   end
end

Потоковые переменные и декларативный параллелизм[править | править вики-текст]

Если программа обнаруживает несвязанную переменную, она ожидает до тех пор, пока переменной будет присвоено значение:

thread 
   Z = X+Y     % ожидает до тех пор, пока переменные X и Y не получат значения
   {Browse Z}  % отображает значение Z
end
thread X = 40 end
thread Y = 2 end

Изменить значение потоковой переменной, с которой связано значение, невозможно:

X = 1
X = 2 % error

Потоковые переменные позволяет легко создавать агентов, которые выполняются в параллельных потоках:

fun {Ints N Max}
   if N == Max then nil
   else 
      {Delay 1000}
      N|{Ints N+1 Max}
   end
end

fun {Sum S Stream}
   case Stream of nil then S
   [] H|T then S|{Sum H+S T} end
end

local X Y in
   thread X = {Ints 0 1000} end
   thread Y = {Sum 0 X} end
   {Browse Y}
end

Благодаря тому, как работают потоковые переменные, в любом месте программы можно использовать потоки вычисления, которые гарантированно вернут один и тот же результат, что делает параллельное программирование простым. Вместе с тем потоки расходуют очень мало системных ресурсов: как и в Эрланге, одновременно можно запустить 100 000 потоков[2].

Примеры программ на языке Oz[править | править вики-текст]

Решето Эратосфена[править | править вики-текст]

В данном примере вычисляется поток простых чисел с использованием алгоритма решето Эратосфена. Для этого рекурсивно создаются параллельные потоки, которые отсеивают составные числа:

fun {Sieve Xs}
   case Xs of nil then nil
   [] X|Xr then Ys in
      thread Ys = {Filter Xr fun {$ Y} Y mod X \= 0 end} end
      X|{Sieve Ys}
   end
end

Ленивые вычисления[править | править вики-текст]

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

fun lazy {Fact N}
   if N =< 0 then 1 else N*{Fact N-1} end
end
local X Y in
  X = {Fact 100} 
  Y = X + 1 % поскольку требуется значение X, оно вычисляется именно в этот момент
end

Передача сообщений[править | править вики-текст]

Модель декларативного параллелизма может быть расширена с использованием механизма передачи сообщений:

declare
local Stream Port in
   Port = {NewPort Stream}
   {Send Port 1} % Stream is now 1|_ ('_' indicates an unbound and unnamed variable)
   {Send Port 2} % Stream is now 1|2|_ 
   ...
   {Send Port n} % Stream is now 1|2| .. |n|_
end 

Создание асинхронных агентов реализуется с помощью потоков и портов:

fun {NewAgent Init Fun}
   Msg Out in
   thread {FoldL Msg Fun Init Out} end
   {NewPort Msg}
end

Состояния и объекты[править | править вики-текст]

Модель декларативного параллелизма может быть расширена с целью поддержки концепции состояния и объектно-ориентированного программирования; для этого необходимо создать структуру данных Cells, значение которой может быть изменено:

local A X in
   A = {NewCell 0}
   A := 1  % changes the value of A to 1
   X = @A  % @ is used to access the value of A
end

Благодаря такому незначительному расширению семантики можно использовать всю мощь объектно-ориентированного программирования:

class Counter
   attr val
   meth init(Value)
      val:=Value
   end
   meth browse
      {Browse @val}
   end
   meth inc(Value)
      val :=@val+Value
   end
end

local C in
   C = {New Counter init(0)}
   {C inc(6)}
   {C browse}
end

Пример программы на языке Oz, решающей ребус[править | править вики-текст]

Условие:

 ФУТ
+БОЛ
 ---
ИГРА
Где И=0 и все различные буквы означают различные цифры.

Решение:

local Fut Res in
proc {Fut C} 
 F#U#T#B#O#L#G#R#A = C 
in 
 C ::: 0#9 
 {FD.distinct C} 
 F \=: 0 
 B \=: 0 
 100 * F + 10* U + T + 100*B + 10*O + L =: 100*G + 10*R + A 
 {FD.distribute ff C} 
end 
{SearchAll Fut Res} 
{Browse Res} 
end 

покажет все решения данного ребуса в виде таблицы.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]