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

Чтобы узнать о компании-разработчике программного обеспечения Lisp, см. Lucid Inc.

Ясный

Парадигма	Поток данных
Разработано	Эдвард А. Эшкрофт Уильям В. Уэдж
Впервые появился	1976
Дисциплина набора текста	Бестиповый
Основные реализации
Люцид, ЦЫГАНКА
Диалекты
Гранулярный Lucid, Индексный Lucid, Тензорный Lucid, Forensic Lucid, Lucx, JOOIPL
Под влиянием
ИСВИМ
Под влиянием
СИЗАЛЬ , PureData , Блеск

Lucid — это язык программирования потоков данных , предназначенный для экспериментов с моделями программирования, отличными от фон Неймана . Он был разработан Биллом Уоджем и Эдом Эшкрофтом и описан в книге 1985 года Lucid, the Dataflow Programming Language .

pLucid был первым переводчиком Lucid.

Модель

Lucid использует модель вычисления данных, основанную на спросе. Каждое утверждение можно понимать как уравнение, определяющее сеть процессоров и линий связи между ними, по которым проходят данные. Каждая переменная представляет собой бесконечный поток значений, а каждая функция — это фильтр или преобразователь. Итерация моделируется с помощью «текущих» значений и оператора «fby» (читается как «за которым следует»), позволяющего компоновать потоки.

Lucid основан на алгебре историй, история представляет собой бесконечную последовательность элементов данных. С функциональной точки зрения историю можно рассматривать как запись изменяющихся значений переменной, а исторические операции, такие как first и next, можно понимать так, как это следует из их названий. Первоначально Lucid задумывался как дисциплинированный, математически чистый, однозадачный язык, в котором проверка будет упрощена. Однако интерпретация потока данных оказала важное влияние на направление развития Lucid. [1]

Подробности

В Lucid (и других языках потоков данных переменную, ) выражение, содержащее еще не связанную ожидает, пока переменная не будет привязана, прежде чем продолжить. Выражение вроде x + y будет ждать, пока x и y не будут связаны, прежде чем вернуться с выводом выражения. Важным следствием этого является то, что избегается явная логика обновления связанных значений, что приводит к существенному сокращению кода по сравнению с основными языками.

Каждая переменная в Lucid представляет собой поток значений. Выражение n = 1 fby n + 1 определяет поток с помощью оператора «fby» ( мнемоника «за которым следует»). fby определяет, что будет после предыдущего выражение. (В этом случае поток выдает 1,2,3,...). Значения в потоке могут быть адресованы этими операторами (при условии, что x — это используемая переменная):

'first x' - извлекает первое значение в потоке x,

'x' - текущее значение потока,

'next x' — извлекает следующее значение в потоке.

'asa' - оператор, который выполняет какое-либо действие «как только» заданное условие становится истинным.

'x upon p' - on — это оператор, который повторяет старое значение потока x и обновляет новые значения только тогда, когда поток p выполняет true доступная стоимость. (Служит для замедления потока x) то есть: x upon p — это поток x с новыми значениями, появляющимися при истинности p.

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

Примеры

Факториал

fac
  where
    n = 0 fby (n + 1);
    fac = 1 fby ( fac * (n + 1) );
  end

Последовательность Фибоначчи

fib
  where
    fib = 0 fby ( 1 fby fib + next fib );
  end

Итого последовательности

total
  where
     total = 0 fby total + x
  end;

Текущее среднее

running_avg
  where 
     sum = first(input) fby sum + next(input);
     n = 1 fby n + 1;
     running_avg = sum / n;
  end;

Простые числа

prime
  where
     prime = 2 fby (n whenever isprime(n));
     n = 3 fby n+1;
     isprime(n) = not(divs) asa divs or prime*prime > N
                     where
                       N is current n;
                       divs = N mod prime eq 0;
                     end;
  end

Диаграмма потока данных

Быстрая сортировка

qsort(a) = if eof(first a) then a else follow(qsort(b0),qsort(b1)) fi
  where
     p = first a < a;
     b0 = a whenever p;
     b1 = a whenever not p;
     follow(x,y) = if xdone then y upon xdone else x fi
                     where
                        xdone = iseod x fby xdone or iseod x; 
                     end
  end

Схема потока данных

    --------> whenever -----> qsort ---------
   |             ^                           |
   |             |                           |
   |            not                          |
   |             ^                           |
   |---> first   |                           |
   |       |     |                           |
   |       V     |                           |
   |---> less ---                            |
   |             |                           |
   |             V                           V
---+--------> whenever -----> qsort -----> conc -------> ifthenelse ----->
   |                                                       ^   ^
   |                                                       |   |
    --------> next ----> first ------> iseod --------------    |
   |                                                           |
    -----------------------------------------------------------

Среднеквадратичное значение

sqroot(avg(square(a)))
  where
     square(x) = x*x;
     avg(y)    = mean
        where
          n = 1 fby n+1;
          mean = first y fby mean + d;
          d = (next y - mean)/(n+1);
        end;
     sqroot(z) = approx asa  err < 0.0001
        where
          Z is current z;
          approx = Z/2 fby (approx + Z/approx)/2;
          err    = abs(square(approx)-Z);
        end;
   end

Проблема Хэмминга

h
   where
     h = 1 fby merge(merge(2 * h, 3 * h), 5 * h);
     merge(x,y) = if xx <= yy then xx else yy fi
        where 
          xx = x upon xx <= yy;
          yy = y upon yy <= xx;
        end;
   end;

Диаграмма потока данных

Hamming problem dataflow diagram

Внешние ссылки

• pLucid