Kent Recursive Calculator
パラダイム | 関数型、宣言型 |
---|---|
登場時期 | 1981年 |
設計者 | デビッド・ターナー |
型付け | 動的型付け |
影響を受けた言語 | SASL |
影響を与えた言語 | Miranda、Orwell (OL)、Haskell |
ウェブサイト | krc-lang |
テンプレートを表示 |
KRC (Kent Recursive Calculator) とは、イギリス・ケント大学(University of Kent)のデビッド・ターナーによって設計・実装された単純な遅延評価方式の純粋関数型プログラミング言語である[1]。1979年11月から1981年10月にかけて、EMAS オペレーティングシステム上に BCPL で実装された[2]。
概要
1972年から1976年にかけてデビット・ターナーはスコットランドのセントアンドリュース大学においてSASL(St.Anrews Static Language)という言語を設計・実装し、主に教育に用いていた。ターナーがケント大学に移ってからはこの経験を生かして新たに言語を設計・実装したが、その言語がKRC(Kent Recursive Calculator)である[3]。KRC は1980年代にケント大学やオックスフォード大学で関数型プログラミングの講義に使用された。
KRCはSASLの文法にさらに改良を加えた言語で、パターンマッチ、ガード、等式で表現された再帰可能な関数定義、ZF 表記(リストの内包表記)を備えている。一方で、where 句は省略された。なお、変数の型が実行時に決まる動的型付け言語である。
KRC の後継言語としては Miranda である。Miranda では多相型が導入された他、KRC では省略された where 句が実装されている。
ZF 集合演算機能(ZF set abstraction)
KRCにおいてリストは遅延評価を実現するストリームとして実装されている。そのストリーム処理の延長として容易に実現できる機能としてKRCに実装されているのがツェルメロ=フレンケル集合演算機能(以下、ZF 集合演算機能と言う)である。ツェルメロ=フレンケルの公理系において、集合を内包表記で記述する場合、
- (ただし、S は集合)
と記述するが、この表記法をプログラミング言語に導入したのが、KRC の ZF 集合演算機能である。ただし、KRC では、本来の集合ではなくリスト(ストリーム)によって実現している。
サンプルコード
Hello, World
krc> "Hello, World\n"! Hello, World
関数定義
krc> I x = x krc> I 42? 42
遅延評価
krc> answer = const 42 (1 / 0) krc> answer? 42
パターンマッチ
krc> total [] = 0 krc> total (x:xs) = x + total xs krc> total [1..10]? 55
リスト
krc> take 20 [10, 14..]? [10,14,18,22,26,30,34,38,42,46,50,54,58,62,66,70,74,78,82,86]
再帰関数
krc> fac 0 = 1 krc> fac n = n * fac (n-1) krc> fac 10? 3628800
相互再帰関数
krc> ev 0 = "TRUE" krc> ev n = od (n-1) krc> od 0 = "FALSE" krc> od n = ev (n-1) krc> map ev [1..10]? ["FALSE","TRUE","FALSE","TRUE","FALSE","TRUE","FALSE","TRUE","FALSE","TRUE"]
ガード
krc> fac n = 1, n == 0 krc> = n * fac (n-1), n > 0 krc> fac 10? 3628800
文字列の連結
krc> implode ["Hello, ", "World", "\n"]? "Hello, World\n"
脚注
参考文献
- KRC Manual Page
- D. A. Turner (1982), Rrecursion Equations as a Programming Language, https://www.cs.kent.ac.uk/people/staff/dat/krc/recursion_equations.pdf
- D. A. Turner (2012), Some History of Functional Programming Languages, https://www.cs.kent.ac.uk/people/staff/dat/tfp12/tfp12.pdf
- D. A. Turner (2017), Some History of Functional Programming Languages, http://www.lambdadays.org/static/upload/media/1487239321204160davidturner.pdf
- Paul Hudak, John Hughes, Simon Peyton Jones, Philip Wadler (2007), A History of Haskell: Being Lazy With Class, https://www.microsoft.com/en-us/research/publication/a-history-of-haskell-being-lazy-with-class/
- 淵 一博,黒川 利明(編著) 編『新世代プログラミング』共立出版株式会社、1986年。
関連項目
外部リンク
公式ウェブサイト