루시드 (프로그래밍 언어)

루시드(Lucid)는 폰 노이만 구조를 따르지 않는 프로그래밍 모델을 갖춘 실험적으로 설계된 데이터플로 프로그래밍 언어이다. 빌 웨지(Bill Wadge)와 에드 애시크로프트(Ed Ashcroft)에 의해 설계되었으며 1985년 책 "데이터플로 프로그래밍 언어, 루시드"(Lucid, the Dataflow Programming Language)에 기술되었다.^[1]

루시드
Lucid

패러다임	데이터플로
설계자	에드워드 A. 애시크로프트 윌리엄 W. 웨지
발표일	1976년
자료형 체계	타입 없음 (Typeless)
주요 구현체
pLucid
방언
GIPSY, Granular Lucid
영향을 받은 언어
ISWIM
영향을 준 언어
SISAL, 퓨어데이터, Lustre

pLucid는 루시드를 위한 최초의 인터프리터이다.

모델

루시드는 데이터 계산을 위해 수요 기반 모델을 사용한다. 각 문장은 프로세서 네트워크와 데이터가 흐르는 프로세서 간의 통신 라인을 정의하는 방정식으로 이해될 수 있다. 각 변수는 무한한 값의 스트림이며 모든 함수는 필터 또는 변환기이다. 반복문은 '현재' 값과 스트림 구성을 허용하는 'fby'(followed by의 약어) 연산자를 통해 시뮬레이션된다.

루시드는 이력의 대수학을 기반으로 하며, 이력은 무한한 데이터 항목 시퀀스이다. 운영적으로 이력은 변수의 변경되는 값에 대한 기록으로 생각할 수 있으며, first 및 next와 같은 이력 연산은 그 이름이 시사하는 방식으로 이해할 수 있다. 루시드는 원래 검증이 단순화될 수 있는 규율적이고 수학적으로 순수한 단일 할당 언어로 구상되었다. 그러나 데이터 흐름 해석은 루시드가 진화한 방향에 중요한 영향을 미쳤다.^[2]

세부 사항

루시드(및 다른 데이터 흐름 언어)에서 아직 바인딩되지 않은 변수를 포함하는 표현식은 해당 변수가 바인딩될 때까지 기다렸다가 진행한다. x + y와 같은 표현식은 x와 y가 모두 바인딩될 때까지 기다렸다가 표현식의 출력을 반환한다. 이의 중요한 결과는 관련 값을 업데이트하기 위한 명시적 로직이 피할 수 있어 주류 언어에 비해 상당한 코드 감소를 가져온다는 것이다.

루시드의 각 변수는 값의 스트림이다. n = 1 fby n + 1 표현식은 'fby' 연산자(기억술 for "followed by")를 사용하여 스트림을 정의한다. fby는 이전 표현식 다음에 오는 것을 정의한다. (이 경우 스트림은 1,2,3,...을 생성한다.) 스트림의 값은 다음 연산자들에 의해 주소 지정될 수 있다 (x가 사용되는 변수라고 가정):

'first x' - 스트림 x의 첫 번째 값을 가져온다.

'x' - 스트림의 현재 값.

'next x' - 스트림의 다음 값을 가져온다.

'asa' - 주어진 조건이 참이 되는 '즉시' 어떤 작업을 수행하는 연산자.

'x upon p' - upon은 스트림 x의 이전 값을 반복하고, 스트림 p가 true 값을 사용할 수 있게 할 때만 새 값으로 업데이트하는 연산자이다. (스트림 x의 속도를 늦추는 역할을 한다) 즉: x upon p는 p가 참일 때 새로운 값이 나타나는 스트림 x이다.

계산은 이러한 시간 변화하는 데이터 스트림에 작용하는 필터 또는 변환 함수를 정의함으로써 수행된다.

예시

계승

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

소수

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