Lucid (プログラミング言語)

Lucid
パラダイム	データフロー
登場時期	1976年
設計者	Edward A. Ashcroft,William W. Wadge
開発者	Ashcroft,Wadge
型付け	Typeless
主な処理系	pLucid
方言	GYPSY GLU
影響を受けた言語	ISWIM
影響を与えた言語	SISAL, Pure Data, Lustre
	テンプレートを表示

Lucid はデータフロープログラミング言語である。非ノイマン型プログラミング言語の実験の為に設計された。Bill Wadge と Ed Ashcroft によって設計され、書籍 Lucid, the Dataflow Programming Language が出版された。

言語モデル

Lucid はデータ処理の際に要求駆動モデルを採用している。Lucid の文は、プロセッサのネットワークを定義する方程式と、その間をデータが流れる通信線として考える事が出来る。変数は無限に続く値のストリームであり、関数はフィルタか変換器である。反復は 'current' 変数と、'fby' 変数によってシミュレートされストリーム合成を行う事が出来る。

Lucid は無限に続くデータの列であるヒストリーの代数を基にしている。利用時には、ヒストリーは変化し続ける変数の値の記録と考える事が出来、first や next 等のヒストリー操作は名前から連想するとおり動作する。Lucid は当初、動作検証が非常にシンプルであるような、非常に厳格で数学的に純粋な単一代入言語として考えられていた。しかしながら、データフローの解釈は非常に重要であり、Lucid の発展に大きく影響を及ぼした。 [1]

言語の詳細

Lucid (とその他のデータフロー言語)では、まだ束縛されていない変数を含む式は、変数が束縛されるまで待機してから実行される。x + y のような式は、x と y の双方が束縛されるまで待ってから式の値を返す。その結果重要なのは、関連する値を更新するためのロジックを明記しないという点であり、一般的な言語と比較してコード量を非常に少なくする事が出来る。

Lucid でのそれぞれの変数は値のストリームである。式 n = 1 fby n + 1 は、演算子 'fby' を使ってストリームを定義している。fby ('followed by' と読む) は直前の式の後に続く物を定義する。(この例では、ストリームは 1,2,3... を生成する。) ストリームの値は以下の演算子によって導かれる(使われる変数を x とする)。

'first x' - ストリーム x の最初の値を取得する。

'x' - ストリームの現在の値。

'next x' - ストリームの次の値を取得する。

'asa' - 条件が真になると何かを「出来るだけ早く (as soon as)」実行する演算子。

'x upon p' - upon はストリーム x の古い値を繰り返す演算子で、ストリーム p が真の時だけ新しい値に更新する。(これによりストリーム x の変化が遅くなる)。すなわち、x upon p は p が真の時に新しい値が現れるストリーム x である。

計算はフィルタ又は時間によって変化するデータの変換関数を定義する事によって実行される。

pLucid は Lucid の最初の実装だった。

例

数列の合計

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;

素数

[2]

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

データフローダイアグラム

 ---+1<--- -->isprime----
 |         |              |
 |         |              V
  ->fby--------------->whenever--->
     ^
     |
     2

クイックソート

[3]

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

Hamming Problem

[4]

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;

データフローダイアグラム

  --------------------*2---------
 |       -------------*3---------|
 |      |           --*5---------|
 |      |          |             |
 |      V          V             |
  --->merge----->merge----->fby-------->
                             ^
                             |
                             1

外部リンク