(57)【要約】  ある技術は、ある数のデータ入力のストリームを取るデータフローグラフを実現し、これらの入力データをある数の出力のストリームに変換する。データフローグラフはパターンマッチングを実行できる。この技術は、入力データの結合されたストリーム全体にわたるパターンマッチングの合成を介して反応を実現する。入力シーケンスを特定の入力パターンにマッチングすることの完全性は、コールド（未だマッチしていない）、ウォーム（たとえば、最小マッチ）、ホット（たとえば、最大マッチ）などの少なくとも３つの異なる度合いを有するものとして特徴付けることができる。マッチングされるべき入力パターンは、ゼロ長さまたは無制限もしくは任意に大きい長さを含む可変長を有することができる。データフローは、プッシュベースもしくはプルベースまたは組み合わせとすることができ、状態に応じて変更することができる。
2019518264.tif 000002
【特許請求の範囲】
【請求項１】
システムであって、
各々がセンサに結合され、前記センサからデータを受信する複数のエージェントと、
前記複数のエージェントに接続されるデータバスを含み、一連の相互接続されたトランスダクションを形成することによって入力のストリームを出力のストリームに変換するデータ処理コンポーネントとを備え、前記トランスダクションは、
参照として外部データソースまたはトランスデューサのうちの少なくとも１つに各々が与えられる１つ以上の入力と、
参照として外部データシンクまたはトランスデューサのうちのいずれか少なくとも１つに各々が与えられる１つ以上の出力と、
各入力について、当該入力に適用されて、生の入力をフィルタリング、収集、および整理して、より有用な、部分的に処理された形式にし、誤った入力を除去するパターンとを含む、システム。
【請求項２】
少なくとも１つのエージェントは、
コンピュータメモリにおいて第１のメモリ位置を含む入力キューを含み、前記入力キューは、処理されるべきトークンの先入れ先出しシーケンスを前記第１のメモリ位置に格納し、前記キューにおける各トークンに関連付けられるタイムスタンプは、前記関連付けられるトークンが前記入力キューに入った時間を示し、前記トークンはネットワークを介して前記入力キューによって受信され、前記少なくとも１つのエージェントはさらに、
前記入力キューに結合されるドライバコンポーネントを含み、前記ドライバコンポーネントは、バックトラッキングなしで前記入力キューにおける前記トークンを処理し、１つ以上の所定の入力パターンにマッチする、前記トークンのシーケンスにおけるパターンを識別し、マッチした所定の入力パターンを識別すると、出力イベント出力を生成し、前記少なくとも１つのエージェントはさらに、
前記ドライバコンポーネントに結合され、前記コンピュータメモリにおいて第２のメモリ位置を含む出力キューを含み、前記出力キューは、前記第２のメモリ位置に、前記ドライバコンポーネントによって生成された前記出力イベントの先入れ先出しシーケンスを格納し、前記少なくとも１つのエージェントはさらに、
前記ドライバコンポーネントに結合される状態表コンポーネントを含み、前記状態表コンポーネントは前記所定の入力パターンを状態表フォーマットで格納し、前記少なくとも１つのエージェントはさらに、
前記ドライバコンポーネントに結合され、前記コンピュータメモリにおいて第３のメモリ位置を含む状態スタックコンポーネントを含み、前記状態スタックコンポーネントは前記第３のメモリ位置にフレームの後入れ先出しのシーケンシャルストレージを格納し、フレームは、変換状態番号、記号、およびデッドラインを含む、請求項１に記載のシステム。
【請求項３】
各トランスダクションは、フィルタ式をいつ評価するかを判断するために使用されるトリガ式を含む、請求項１に記載のシステム。
【請求項４】
前記トリガ式は、ノードのツリーとして定義され、各ノードは、
前記入力のうちの１つに対する参照と、
時間の単位で時間の間隔として与えられるタイムアウトと、
少なくとも２つの子を含み、各子は別のトリガ式ノードによって表わされる、二項連言演算子と、
少なくとも２つの子を含み、各子は別のトリガ式ノードによって表わされる、二項選言演算子とのうちの少なくとも１つである、請求項１に記載のシステム。
【請求項５】
各トランスダクションはフィルタ式を含み、前記フィルタ式はマッチした入力のドメインで指定され、前記フィルタ式はトランスダクションがいつ出力を生成するかを決定するブール結果をもたらす、請求項３に記載のシステム。
【請求項６】
入力パターンは、ゼロ長さまたは無制限長さを含む可変長の入力シーケンスとマッチすることができる、請求項１に記載のシステム。
【請求項７】
入力パターンを入力シーケンスとマッチングしようと試みた結果は、少なくとも３つの異なる状態を有することができる、請求項１に記載のシステム。
【請求項８】
入力パターンを入力シーケンスとマッチングしようと試みた結果は、少なくとも３つの異なる状態を有することができ、前記少なくとも３つの異なる状態は、
前記入力パターンの最小入力にマッチするまで、前記マッチングの試みは第１の状態にあることと、
前記最小入力にマッチした後、最大入力にマッチするまで、前記マッチングの試みは第２の状態にあることと、
前記最大入力にマッチした後、前記マッチングの試みは第３の状態にあることとを含む、請求項１に記載のシステム。
【請求項９】
前記第１の状態は「コールド」状態と呼ばれ、前記第２の状態は「ウォーム」状態と呼ばれ、前記第３の状態は「ホット」状態と呼ばれる、請求項８に記載のシステム。
【請求項１０】
データはプッシュベースでセンサからエージェントに流れる、請求項１に記載のシステム。
【請求項１１】
データは、プッシュベースでセンサからエージェントに流れ、
エージェントの入力のすべてが少なくとも前記第２の状態にあるとき、および前記センサの入力のうちの１つ以上が前記第３の状態にあるとき、そしてトリガ式の結果が前記第２の状態にあるとき、前記データは、エージェントによってセンサからプルベースで流れる、請求項８に記載のシステム。
【請求項１２】
エージェントは、前記第２の状態にあるそれのセンサを加速して、各そのようなセンサに、それのパターンが完全にマッチしたと考えさせ、したがって各そのようなセンサを前記第３の状態になるようにし、それの出力を生成させ、それによって、前記エージェントが、それのセンサからデータを効果的にプルすることを可能にする、請求項１１に記載のシステム。
【請求項１３】
限定的に長いパターンまたはオープンエンドのパターンが、トランスダクションにおいて有用に使用されることを可能にする、請求項１２に記載のシステム。
【請求項１４】
前記センサのうちの少なくとも１つは、物性をデジタル量に変換するハードウェア装置であり、前記デジタル量はストリーム化される、請求項１に記載のシステム。
【請求項１５】
方法であって、
複数のエージェントおよびセンサを相互接続することを備え、前記エージェントは前記センサに結合され、前記センサからデータのストリームを受信し、前記方法はさらに、
前記センサからの入力の前記ストリームを、一連の相互接続されたトランスダクションを介して、出力のストリームに変換することを備え、各トランスダクションは、
参照として外部データソースまたはトランスデューサのいずれかに各々が与えられる１つ以上の入力と、
参照として外部データシンクまたはトランスデューサのいずれかに各々が与えられる１つ以上の出力と、
各入力について、前記各入力に適用されて、生の入力をフィルタリング、収集、および整理して、より有用な、部分的に処理された、または一致した形式にし、誤った入力を除去するパターンと、
フィルタ式をいつ評価するかを判断するために使用され、ノードのツリーとして定義されるトリガ式とを含み、各ノードは、
前記入力のうちの１つに対する参照と、
何らかの便利な時間の単位で特徴づけられる時間の間隔として与えられるタイムアウトと、
少なくとも２つの子を含み、各子は別のトリガ式ノードである、二項連言演算子と、
少なくとも２つの子を含み、各子は別のトリガ式ノードである、二項選言演算子と、
マッチした入力のドメインで定義され、前記トランスダクションがいつ出力を生成するかを決定するブール結果をもたらすフィルタ式と、
マッチした入力のドメインで定義され、前記トランスダクションの出力を生成する型の任意の組み合わせの結果をもたらす１つ以上の式とのうちの１つである、方法。
【請求項１６】
入力パターンは、ゼロ長さまたは無制限長さを含む可変長の入力シーケンスとマッチすることができ、
それの最小入力にマッチするまで、コールド状態と考えられ、
それの最小入力にマッチした後、それの最大入力にマッチするまで、ウォーム状態と考えられ、
それの最大入力にマッチした後、ホット状態と考えられる、請求項１５に記載の方法。
【請求項１７】
トランスデューサのマッチングの準備の完全性モデルは、２つ以下の異なる度合いではなく、少なくとも３つの異なる度合いによって特徴付けられる、請求項１５に記載の方法。
【請求項１８】
前記３つの度合いの完全性モデルは、可変長パターンの処理を可能にするパターン駆動型反応を直接容易にする、請求項１７に記載の方法。
【請求項１９】
プロデューサからコンシューマへのデータフローはプッシュベースであり、ただし、それは
エージェントの入力のすべての入力が少なくとも前記ウォーム状態にあるとき、および前記センサの入力の１つ以上が前記ホット状態にあり、そしてトリガ式の結果が前記ウォーム状態にあるときを除くものであり、
そのとき、前記エージェントはそれのウォーム状態のセンサを加速して、各そのようなセンサに、それのパターンが完全にマッチしたと考えさせ、したがって各そのようなセンサを前記ホット状態になるようにし、それの出力を生成させ、
したがって、前記センサに、それが接続されている他のプロデューサデータを効果的にプルさせることができ、
したがって、限定的に長いかまたはオープンエンドのパターンがトランスダクションで有用に使用されることを可能にしてもよい、請求項１６に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
記載
関連出願への相互参照
この特許出願は、２０１６年３月２３日に出願された米国特許出願第６２／３１２，１０６号、第６２／３１２，１８７号、第６２／３１２，２２３号、および第６２／３１２，２５５号の利益を主張し、それらは、本願で引用されたすべての他の引例とともに、引用により援用される。
【背景技術】
【０００２】
発明の背景
この発明はコンピューティングの分野に関し、より具体的には、産業用機械によって生成される大量のデータを取扱うためのエッジコンピューティングにおいて用いられてもよいリアルタイムデータフロープログラミングにおけるパターン駆動型反応の合成に関する。
【０００３】
従来の企業ソフトウェアアプリケーションホスティングは、規模の経済性およびシステム効率を活用するために、データセンターまたは「クラウド」インフラストラクチャに依拠してきた。しかしながら、これらのデータセンターは、企業がそのビジネス活動のほとんどを行なう物理的活動地点（たとえば工場、倉庫、小売店など）から任意に離れている場合がある。産業用インターネット・オブ・シングス（industrial Internet of things ：ＩＩｏＴ）とは、非常に高頻度でイベントを追跡するセンサを用いた物理的活動の計測に依拠するデバイスまたは使用事例の集合を指す。
【０００４】
多くのセクターにおける産業用機械が、製造、石油およびガス、採鉱、運輸、電力および水、再生可能エネルギー、ヘルスケア、小売、スマートビルディング、スマートシティ、および接続された車両を含むこのインターネット・オブ・シングス（ＩｏＴ）の下に入る。クラウドコンピューティングの成功にもかかわらず、多くの欠点が存在する。そのデータのすべてをクラウドストレージへ送信することは実用的ではない。なぜなら、接続性が常にそこにあるとは限らず、帯域幅が十分ではなく、レイテンシにおける変動が高すぎ、または、帯域幅が存在していたとしても、それは法外なコストがかかるためである。接続性、帯域幅、およびコストが問題ではなかったとしても、リアルタイムの意思決定および予測保守はなく、それは機械への著しい損傷をもたらし得る。
【０００５】
したがって、改良されたエッジ解析およびデータフロープログラミングを含む改良されたコンピューティングシステム、アーキテクチャ、ならびに手法が、産業用機械によって生成される大量のデータを取扱うために必要とされる。
【発明の概要】
【課題を解決するための手段】
【０００６】
この発明の簡単な概要
ある技術は、ある数のデータ入力のストリームを取るデータフローグラフを実現し、これらの入力をある数の出力のストリームに変換する。データフローグラフはパターンマッチングを実行できる。この技術は、入力データの結合されたストリーム全体にわたるパターンマッチングの合成を介して反応を実行する。入力シーケンスを特定の入力パターンにマッチングすることの完全性は、コールド（未だマッチしていない）、ウォーム（たとえば、最小マッチ）、ホット（たとえば、最大マッチ）などの少なくとも３つの異なる度合いを有するものとして特徴付けることができる。マッチングされるべき入力パターンは、ゼロ長さまたは無制限もしくは任意に大きい長さを含む可変長を有することができる。データフローは、プッシュベースもしくはプルベースまたは組み合せとすることができ、状態に応じて変化し得る。
【０００７】
特定の実現例では、データフロープログラミング技術は、エッジコンピューティングシステムで使用される。ある方法はインテリジェンスをエッジで可能化にする。特徴は以下を含む。特徴は、以下を含む。ゲートウェイデバイスまたは組込まれたシステム上でホストされるソフトウェア層においてセンサデータによってトリガすること。ソフトウェア層はローカルエリアネットワークに接続される。サービス、アプリケーション、およびデータ処理エンジンのリポジトリが、ソフトウェア層によってアクセス可能にされる。ソフトウェア層によって利用可能にされた式言語を通して、センサデータを特定条件の発生の意味論的記述と整合させること。式を連続的に実行することによってパターンイベントを自動的に発見すること。アプリケーションおよび解析式をつなぐために、ソフトウェア層によって管理されるネットワーク全体のゲートウェイデバイスおよび組込まれたシステムを越えて、サービスおよびアプリケーションをインテリジェントに構成すること。リソース利用可能性に基づいてアプリケーションおよび解析のレイアウトを最適化すること。ソフトウェア層の健全性を監視すること。未加工のセンサデータまたは式の結果を、ローカル時系列データベースまたはクラウドストレージに格納すること。サービスおよびコンポーネントは、どのゲートウェイ環境でも円滑な動作を保証するために、コンテナ化され得る。
【０００８】
エッジインテリジェンスは、インターネット・オブ・シングス（ＩｏＴ）データのソースでイネーブルにされる。システムは、リアルタイムのエッジ解析およびアプリケーションのために、ＩｏＴデバイスセンサデータへの強化（enrich）されたアクセス（ストリームモードまたはバッチモード、または双方）を提供する。システムは、低メモリフットプリント機械で動作する高性能解析エンジンを通して解析関数および解析式を実行するための高効率で表現的なコンピュータ言語を含む。システムは、さらなる機械学習のために収集データをクラウドへ発行することを可能にする。システムは、エッジアプリを開発するためのソフトウェア開発キットを含む。クラウドベースの管理コンソールが、エッジデプロイメント、構成、アプリケーション、および解析式の管理を可能にする。
【０００９】
エッジインフラストラクチャおよびプラットフォームの特定の一実現化例は、フォグホーン・システムズ・インコーポレイテッド（FogHorn Systems, Inc）（フォグホーン）による。フォグホーンのウェブサイト、www.foghorn-systems.com、出版物（白書、ユーザガイド、指導書、ビデオなどを含む）、ならびに、フォグホーンの技術および製品についての他の出版物が、引用により援用される。
【００１０】
フォグホーンは、産業用および商業用インターネット・オブ・シングス（ＩｏＴ）データのためのエッジインテリジェンスを可能にするためのプラットフォームを提供する。何百億もの産業用および商業用ＩｏＴデバイスによって生成されるデータの量は、インターネット全体を圧倒するのに十分莫大になるであろう。フォグホーンのプラットフォームはＩｏＴデータを、それがまさしく生じるところ、すなわちネットワークのエッジで処理し、解析し、それに応答する。フォグホーンの「インテリジェントエッジ」ソフトウェアプラットホームは、前例がないレベルの自動化、業務効率、コスト削減などを可能にする。
【００１１】
産業用インターネット・オブ・シングス（ＩＩｏＴ）は、センサ、機械類、およびコンピュータといった、相互接続された産業用および商業用デバイスからなる。ＩＩｏＴの目標は、分散された企業全体にわたって、より優れたデバイス制御、データ管理、機械自動化、および業務効率を可能にすることである。会社は、システム全体の管理および最適化のためにクラウドコンピューティングを活用しながら、リアルタイムの解析および自動化応答を使用してグリーンフィールドＩＩｏＴ機会を捕らえるためにエッジでフォグコンピューティングを適用することができる。フォグホーンのエッジコンピューティングプラットフォームはまた、追加のコンピューティングリソースを追加することが実行できない場合に、既存のプログラマブルロジックコントローラ（programmable logic controller：ＰＬＣ）（たとえば、ブラウンフィールド機会）において動作するように設計される。ブラウンフィールドとは、確立されたシステムを勘案しながら情報技術（information technology：ＩＴ）問題領域を解決するための新しいシステムの実現を指す。新しいソフトウェアアーキテクチャは、既存のおよび動作中のソフトウェアを考慮する。
【００１２】
エッジインテリジェンスプラットフォームとは、ＩＩｏＴデバイスが存在するエッジのより近くまでデータ処理および解析を拡張する、フォグコンピューティング概念に基づいたソフトウェアベースのソリューションである。遠くの集中型クラウドへすべてのデータを送信する代わりに、エッジデバイスとの近接性を維持することは、待ち時間を最小化し、最大性能、より速い応答時間、ならびにより効果的な保守および業務戦略を可能にする。それはまた、全体的な帯域幅要件と、広範に分散されたネットワークを管理するコストとを著しく減少させる。
【００１３】
エッジでのＩＩｏＴ操作に焦点を合わせることは、全体的な帯域幅要件を減少させ、時間依存の条件への即時の自動化応答を可能にする。産業界は何十億もの新しいＩＩｏＴデバイスを追加しており、これらのデバイスは集団で、毎日多くのペタバイトのデータを生成する。このデータのすべてをクラウドに送信することは、法外なコストがかかるだけでなく、より大きいセキュリティリスクも生み出す。エッジで動作することは、はるかにより速い応答時間、リスクの減少、および全体的コストの低下を保証する。
【００１４】
２０１５年８月２７日に出願された米国特許出願第６２／２１０，９８１号、および２０１６年８月２９日に出願された米国特許出願第１５／２５０，７２０号は、ここに引用により援用され、エッジコンピューティング環境およびプラットフォームを記載する。２０１７年３月２３日に出願された米国特許出願第１５／４６７，３０６号は、ここに引用により援用され、リアルタイムデータフロープログラミングのための効率的な状態機械を記載する。２０１７年３月２３日に出願された米国特許出願第１５／４６７，３１８号は、ここに引用により援用され、リアルタイムデータフロープログラミング言語のためのツールおよび方法を記載する。
【００１５】
ある実現例では、システムは以下を備える。ある数のエージェントは各々がセンサに接続され、各エージェントはセンサからデータ（例：ストリームデータ）を受信し、データ処理コンポーネントは、エージェントが接続されるデータバスを含む。データ処理コンポーネントは、一連の相互接続されたトランスダクションを形成することによって入力のストリームを出力のストリームに変換する。 変換は、パターンマッチング、計算および他の動作を含み得る。各トランスダクションは、参照として外部データソースまたはトランスデューサのうちの少なくとも１つを各々が与えられる１つ以上の入力と、参照として外部データシンクまたはトランスデューサのうちのいずれか少なくとも１つに各々が与えられる１つ以上の出力とを含み得る。入力パターンを入力シーケンスとマッチングしようと試みた結果は、完全性の少なくとも３つの異なる状態または度合いを有することができる。
【００１６】
他の実現例では、方法は以下を備える。ある数のエージェントおよびセンサを相互接続することを備え、エージェントはセンサに接続され、センサからデータのストリームを受信し、方法はさらに、センサからの入力のストリームを、一連の相互接続されたトランスダクションを介して、出力のストリームに変換（transform）または変換（convert）することを備える。各トランスダクションは、参照として外部データソースまたはトランスデューサのいずれかに各々が与えられる１つ以上の入力と、参照として外部データシンクまたはトランスデューサのいずれかに各々が与えられる１つ以上の出力とを含む。各入力について、各入力に適用されて、生の入力をフィルタリング、収集、および整理して、より有用な、部分的に処理された、もしくは一致した形式にし、または誤った入力を除去するパターンがある。トランスデューサにおいては、トリガ式を用いて、フィルタ式をいつ評価するかを判断することができる。
【００１７】
本発明の他の目的、特徴、および利点は、以下の詳細な説明および添付図面を考慮すれば明らかになるであろう。図面では、図全体を通し、同じ参照記号は同じ特徴を表わす。
【図面の簡単な説明】
【００１８】
【図１】クライアント−サーバシステムおよびネットワークのブロック図である。
【図２】クライアントまたはサーバのより詳細な図である。
【図３】コンピュータシステムのシステムブロック図である。
【図４】センサストリームとクラウドとの間にあるエッジコンピューティングプラットフォームのブロック図である。
【図５】エッジ解析を含むエッジコンピューティングプラットフォームのより詳細なブロック図である。
【図６】エッジインフラストラクチャとクラウドインフラストラクチャとの間の動作フローを示す図である。
【図７】決定性有限オートマトン（ＤＦＡ）に変換された拡張非決定性有限オートマトン（ＮＦＡ）および状態縮小機械（state-reduced machine）を示す。
【図８】トークンアルファの受信で状態ＡからＢへの遷移を示す。
【図９】別途の状態遷移、状態Ｘを経た、状態Ａから状態Ｂへの遷移を示す。
【図１０】構文解析によって形成された抽象構文木の例を示す。
【図１１】離接のための部分グラフを示す。
【図１２】合接のための部分グラフを示す。
【図１３】構造を有する閉包（closure）を示す。
【図１４】物理センサを使用して、センサ式言語エンジンを介していくつかの仮想センサを作成する例を示す。
【図１５】フローグラフの例を示す。
【図１６】ノードの種類の階層を示す。
【図１７】エッジの種類の階層およびエッジのノードに対する濃度を示す。
【発明を実施するための形態】
【００１９】
発明の詳細な説明
図１は、本発明の一実施形態を取入れる分散型コンピュータネットワーク１００の簡略ブロック図である。コンピュータネットワーク１００は、複数の通信リンク１２８を介して通信ネットワーク１２４に結合された、複数のクライアントシステム１１３、１１６、および１１９と、サーバシステム１２２とを含む。通信ネットワーク１２４は、分散型ネットワーク１００のさまざまなコンポーネントが互いに通信して情報を交換することを可能にするためのメカニズムを提供する。
【００２０】
通信ネットワーク１２４はそれ自体、多くの相互接続されたコンピュータシステムおよび通信リンクで構成されてもよい。通信リンク１２８は、配線リンク、光リンク、衛星または他の無線通信リンク、波動伝搬リンク、もしくは、情報の通信のための他のメカニズムであってもよい。通信リンク１２８は、ＤＳＬ、ケーブル、イーサネット（登録商標）または他の配線リンク、受動または能動光リンク、３Ｇ、３．５Ｇ、４Ｇおよび他のモビリティ、衛星または他の無線通信リンク、波動伝搬リンク、もしくは、情報の通信のための任意の他のメカニズムであってもよい。
【００２１】
図１に示すさまざまなシステム間の通信を容易にするために、さまざまな通信プロトコルが使用されてもよい。これらの通信プロトコルは、ＶＬＡＮ、ＭＰＬＳ、ＴＣＰ／ＩＰ、トンネリング、ＨＴＴＰプロトコル、無線アプリケーションプロトコル（wireless application protocol：ＷＡＰ）、ベンダー固有プロトコル、カスタマイズされたプロトコルなどを含んでいてもよい。一実施形態では、通信ネットワーク１２４はインターネットであり、他の実施形態では、通信ネットワーク１２４は、ローカルエリアネットワーク（local area network：ＬＡＮ）、ワイドエリアネットワーク（wide area network：ＷＡＮ）、無線ネットワーク、イントラネット、私的ネットワーク、公的ネットワーク、スイッチドネットワーク、およびこれらの組合せなどを含む、任意の好適な通信ネットワークであってもよい。
【００２２】
図１の分散型コンピュータネットワーク１００は、本発明を取入れる実施形態の単なる例示であり、請求項に記載されるようなこの発明の範囲を限定しない。当業者であれば、他の変形、変更、および代替物を認識するであろう。たとえば、２つ以上のサーバシステム１２２が通信ネットワーク１２４に接続されてもよい。別の例として、複数のクライアントシステム１１３、１１６、および１１９は、アクセスプロバイダ（図示せず）を介して、または何らかの他のサーバシステムを介して、通信ネットワーク１２４に結合されてもよい。
【００２３】
クライアントシステム１１３、１１６、および１１９は典型的には、情報を提供するサーバシステムから情報を要求する。この理由により、サーバシステムは典型的には、クライアントシステムよりも多いコンピューティングおよびストレージ容量を有する。しかしながら、特定のコンピュータシステムは、そのコンピュータシステムが情報を要求しているか、または提供しているかに依存して、クライアントまたはサーバとして、双方として機能してもよい。加えて、この発明の局面はクライアント−サーバ環境を使用して説明されてきたが、この発明はスタンドアロンコンピュータシステムにおいても具現化され得ることが明らかであるはずである。
【００２４】
サーバ１２２は、クライアントシステム１１３、１１６、および１１９から情報要求を受信し、要求を満たすために必要とされる処理を行ない、要求に対応する結果を要求元クライアントシステムへ送り返す役割を担う。要求を満たすために必要とされる処理は、サーバシステム１２２によって行なわれてもよく、またはそれに代えて、通信ネットワーク１２４に接続された他のサーバに委任されてもよい。
【００２５】
クライアントシステム１１３、１１６、および１１９は、ユーザが、サーバシステム１２２によって格納された情報にアクセスし、情報をクエリすることを可能にする。特定の一実施形態では、クライアントシステムは、デスクトップアプリケーション、もしくはモバイルスマートフォンまたはタブレットアプリケーションなどのスタンドアロンアプリケーションとして動作可能である。別の実施形態では、クライアントシステム上で実行される「ウェブブラウザ」アプリケーションが、ユーザが、サーバシステム１２２によって格納された情報を選択し、情報にアクセスし、情報を検索し、またはクエリすることを可能にする。ウェブブラウザの例は、マイクロソフト社（Microsoft Corporation）によって提供されるインターネットエクスプローラ（Internet Explorer）ブラウザプログラム、モジラ（Mozilla）によって提供されるファイアーフォックス（Firefox）（登録商標）ブラウザ、グーグル（Google（登録商標））によって提供されるクローム（Chrome）ブラウザ、アップル（Apple）によって提供されるサファリ（Safari）ブラウザなどを含む。
【００２６】
クライアント−サーバ環境では、いくつかのリソース（たとえばファイル、音楽、ビデオ、またはデータ）はクライアントで格納され、一方、他のリソースは、サーバなどネットワークにおけるどこか他のところに格納されるかまたはそこから配信され、ネットワーク（たとえばインターネット）を介してアクセス可能である。したがって、ユーザのデータは、ネットワークまたは「クラウド」に格納され得る。たとえば、ユーザは、クラウド（たとえばサーバ）上にリモートに格納されている、クライアントデバイス上の文書に対して作業することができる。クライアントデバイス上のデータは、クラウドと同期され得る。
【００２７】
図２は、本発明の例示的なクライアントまたはサーバシステムを示す。一実施形態では、ユーザは、図２に示すようなコンピュータワークステーションシステムを通して、システムとインターフェイス接続する。図２は、モニタ２０３と、スクリーン２０５と、筐体２０７（システムユニット、キャビネット、またはケースとも呼ばれてもよい）と、キーボードまたは他の人間入力デバイス２０９と、マウスまたは他のポインティングデバイス２１１とを含む、コンピュータシステム２０１を示す。マウス２１１は、マウスボタン２１３などの１つ以上のボタンを有していてもよい。
【００２８】
本発明は、特定のフォームファクタ（たとえば、デスクトップコンピュータのフォームファクタ）のどのコンピューティングデバイスにも限定されず、さまざまなフォームファクタのあらゆるタイプのコンピューティングデバイスを含み得る、ということが理解されるべきである。ユーザは、スマートフォン、パーソナルコンピュータ、ラップトップ、電子タブレットデバイス、全地球測位システム（global positioning system：ＧＰＳ）受信機、ポータブルメディアプレイヤー、携帯情報端末（personal digital assistant：ＰＤＡ）、他のネットワークアクセスデバイス、および、データを送受信できる他の処理デバイスを含む、任意のコンピューティングデバイスとインターフェイス接続することができる。
【００２９】
たとえば、特定の一実現化例では、クライアントデバイスは、アップルｉＰｈｏｎｅ（登録商標）（たとえば、アップルｉＰｈｏｎｅ６）、アップルｉＰａｄ（登録商標）（たとえば、アップルｉＰａｄ、またはアップルｉＰａｄ  ｍｉｎｉ）、アップルｉＰｏｄ（登録商標）（たとえば、アップルｉＰｏｄ  Ｔｏｕｃｈ）、サムスン（Samsung）ギャラクシー（Galaxy）製品（たとえば、ギャラクシーＳシリーズ製品、またはギャラクシーノート（Galaxy Note）シリーズ製品）、グーグル（登録商標）ネクサス（Nexus）デバイス（たとえば、グーグルネクサス６、グーグルネクサス７、またはグーグルネクサス９）、およびマイクロソフトデバイス（たとえば、マイクロソフトサーフェス（Surface）タブレット）といった、スマートフォンまたはタブレットデバイスであり得る。典型的には、スマートフォンは、電話部分（および関連付けられた無線機）とコンピュータ部分とを含み、それらはタッチスクリーンディスプレイを介してアクセス可能である。
【００３０】
電話部分のデータ（たとえば、連絡先および電話番号）と、コンピュータ部分のデータ（たとえば、ブラウザを含むアプリケーションプログラム、画像、ゲーム、ビデオ、および音楽）とを格納するための不揮発性メモリがある。スマートフォンは典型的には、写真およびビデオを撮るためのカメラ（たとえば、前向きのカメラまたは後部カメラ、もしくは両方）を含む。たとえば、スマートフォンまたはタブレットは、１つ以上の他のデバイスにストリーミングされ得るライブビデオを撮るために使用され得る。
【００３１】
筐体２０７は、プロセッサ、メモリ、大容量ストレージデバイス２１７などといった、よく知られたコンピュータコンポーネント（それらのうちのいくつかは図示されず）を収容する。大容量ストレージデバイス２１７は、大容量ディスクドライブ、フロッピー（登録商標）ディスク、磁気ディスク、光ディスク、光磁気ディスク、固定ディスク、ハードディスク、ＣＤ−ＲＯＭ、書込可能ＣＤ、ＤＶＤ、書込可能ＤＶＤ（たとえば、ＤＶＤ−Ｒ、ＤＶＤ＋Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ＋ＲＷ、ＨＤ−ＤＶＤ、またはブルーレイ（登録商標）ディスク）、フラッシュおよび他の不揮発性ソリッドステートストレージ（たとえば、ＵＳＢフラッシュドライブまたはソリッドステートドライブ（solid state drive：ＳＳＤ））、バッテリによってバックアップされた揮発性メモリ、テープストレージ、リーダ、および他の同様の媒体、ならびにこれらの組合せを含んでいてもよい。
【００３２】
この発明の、コンピュータにより実現される、またはコンピュータにより実行可能なバージョン、もしくはコンピュータプログラム製品が、コンピュータ読取可能媒体を使用して具現化され、コンピュータ読取可能媒体上に格納され、またはコンピュータ読取可能媒体に関連付けられてもよい。コンピュータ読取可能媒体は、命令を実行のために１つ以上のプロセッサに提供することに関与する任意の媒体を含んでいてもよい。そのような媒体は、不揮発性媒体、揮発性媒体、および伝送媒体を含むものの、それらに限定されない多くの形を取ってもよい。不揮発性媒体は、たとえば、フラッシュメモリ、もしくは、光学ディスクまたは磁気ディスクを含む。揮発性媒体は、キャッシュメモリまたはＲＡＭなどのスタティックメモリまたはダイナミックメモリを含む。伝送媒体は、同軸ケーブル、銅線、光ファイバー線、およびバスに配置されたワイヤを含む。伝送媒体はまた、無線波および赤外線データ通信中に生成されるような電磁波、無線周波、音響波、または光波の形を取り得る。
【００３３】
たとえば、本発明のソフトウェアの、機械により実行可能なバイナリバージョンが、ＲＡＭまたはキャッシュメモリ内に、もしくは大容量ストレージデバイス２１７上に格納されてもよく、または存在してもよい。本発明のソフトウェアのソースコードも、大容量ストレージデバイス２１７（たとえば、ハードディスク、磁気ディスク、テープ、またはＣＤ−ＲＯＭ）上に格納されてもよく、または存在してもよい。さらに別の例として、この発明のコードは、ワイヤ、無線波を介して、または、インターネットなどのネットワークを通して伝送されてもよい。
【００３４】
図３は、本発明のソフトウェアを実行するために使用されるコンピュータシステム２０１のシステムブロック図を示す。図２と同様に、コンピュータシステム２０１は、モニタ２０３と、キーボード２０９と、大容量ストレージデバイス２１７とを含む。コンピュータシステム５０１はさらに、中央プロセッサ３０２、システムメモリ３０４、入力／出力（Ｉ／Ｏ）コントローラ３０６、ディスプレイアダプタ３０８、シリアルまたはユニバーサルシリアルバス（universal serial bus：ＵＳＢ）ポート３１２、ネットワークインターフェイス３１８、およびスピーカ３２０といったサブシステムを含む。この発明はまた、追加の、またはより少ないサブシステムを有するコンピュータシステムで使用されてもよい。たとえば、あるコンピュータシステムは２つ以上のプロセッサ３０２を含んでいてもよく（すなわち、マルチプロセッサシステム）、または、あるシステムはキャッシュメモリを含んでいてもよい。
【００３５】
３２２などの矢印は、コンピュータシステム２０１のシステムバスアーキテクチャを表わす。しかしながら、これらの矢印は、サブシステム同士をリンクするよう機能する任意の相互接続スキームの例示である。たとえば、スピーカ３２０は、ポートを通して他のサブシステムに接続されてもよく、または、中央プロセッサ３０２への内部直接接続を有していてもよい。プロセッサは、複数のプロセッサまたはマルチコアプロセッサを含んでいてもよく、それは、情報の並列処理を許可してもよい。図２に示すコンピュータシステム２０１は、本発明での使用にとって好適なコンピュータシステムの単なる一例である。本発明での使用にとって好適なサブシステムの他の構成は、当業者には容易に明らかになるであろう。
【００３６】
コンピュータソフトウェア製品は、Ｃ、Ｃ＋＋、Ｃ＃、パスカル（Pascal）、フォートラン（Fortran）、パール（Perl）、（マスワークス（MathWorks）、www.mathworks.comからの）マトラボ（Matlab）、ＳＡＳ、ＳＰＳＳ、ＪａｖａＳｃｒｉｐｔ（登録商標）、ＡＪＡＸ、Ｊａｖａ（登録商標）、パイソン（Python）、アーラン（Erlang）、およびルビー・オン・レイルズ（Ruby on Rails）といった、さまざまな好適なプログラミング言語のうちのいずれで書かれてもよい。コンピュータソフトウェア製品は、データ入力モジュールおよびデータ表示モジュールを有する独立したアプリケーションであってもよい。これに代えて、コンピュータソフトウェア製品は、分散オブジェクトとしてインスタンス化され得るクラスであってもよい。コンピュータソフトウェア製品はまた、（オラクル社（Oracle Corporation）からの）Ｊａｖａ  Ｂｅａｎｓ、またはエンタープライズＪａｖａ  Ｂｅａｎｓ（オラクル社からのＥＪＢ）といったコンポーネントソフトウェアであってもよい。
【００３７】
システム用のオペレーティングシステムは、マイクロソフトウィンドウズ（登録商標）ファミリーのシステム（たとえば、ウィンドウズ（登録商標）９５、９８、Ｍｅ、ウィンドウズＮＴ、ウィンドウズ２０００、ウィンドウズＸＰ、ウィンドウズＸＰ  ｘ６４エディション、ウィンドウズビスタ（Vista）、ウィンドウズ７、ウィンドウズ８、ウィンドウズ１０、ウィンドウズＣＥ、ウィンドウズモバイル、ウィンドウズＲＴ）、シンビアン（Symbian）ＯＳ、タイゼン（Tizen）、リナックス（登録商標）、ＨＰ−ＵＸ、ＵＮＩＸ（登録商標）、サン（Sun）ＯＳ、ソラリス（Solaris）、Ｍａｃ  ＯＳ  Ｘ、アップルｉＯＳ、アンドロイド（登録商標）、アルファ（Alpha）ＯＳ、ＡＩＸ、ＩＲＩＸ３２、またはＩＲＩＸ６４のうちの１つであってもよい。他のオペレーティングシステムが使用されてもよい。マイクロソフトウィンドウズは、マイクロソフト社の商標である。
【００３８】
また、コンピュータはネットワークに接続されてもよく、このネットワークを使用して他のコンピュータにインターフェイス接続されてもよい。ネットワークは、とりわけ、イントラネット、またはインターネットであってもよい。ネットワークは、有線ネットワーク（たとえば、銅を使用）、電話網、パケットネットワーク、光学ネットワーク（たとえば、光ファイバーを使用）、または無線ネットワーク、もしくはこれらの任意の組合せであってもよい。たとえば、データおよび他の情報は、Ｗｉ−Ｆｉ（数例を挙げると、ＩＥＥＥ規格８０２．１１、８０２．１１ａ、８０２．１１ｂ、８０２．１１ｅ、８０２．１１ｇ、８０２．１１ｉ、８０２．１１ｎ、８０２．１１ａｃ、および８０２．１１ａｄ）、近距離無線通信（near field communication：ＮＦＣ）、無線自動識別（radio-frequency identification：ＲＦＩＤ）、モバイルまたはセルラー無線（たとえば、２Ｇ、３Ｇ、４Ｇ、３ＧＰＰ  ＬＴＥ、ＷｉＭＡＸ、ＬＴＥ、ＬＴＥアドバンスト、フラッシュＯＦＤＭ、ＨＩＰＥＲＭＡＮ、アイバースト（iBurst）、ＥＤＧＥエボリューション、ＵＭＴＳ、ＵＭＴＳ−ＴＤＤ、１ｘＲＤＤ、およびＥＶ−ＤＯ）といったプロトコルを使用した無線ネットワークを使用して、コンピュータとこの発明のシステムのコンポーネント（またはステップ）との間で渡されてもよい。たとえば、あるコンピュータからの信号が、コンポーネントまたは他のコンピュータへ、少なくとも部分的に無線で転送されてもよい。
【００３９】
ウェブブラウザがコンピュータワークステーションシステム上で実行される一実施形態では、ユーザは、インターネットなどのネットワークを通して、ワールド・ワイド・ウェブ（World Wide Web：ＷＷＷ）上のシステムにアクセスする。ウェブブラウザは、ＨＴＭＬ、ＸＭＬ、テキスト、ＰＤＦ、およびポストスクリプトを含むさまざまなフォーマットのウェブページまたは他のコンテンツをダウンロードするために使用されており、システムの他の部分へ情報をアップロードするために使用されてもよい。ウェブブラウザは、ウェブ上のリソースを識別するためにユニフォーム・リソース・アイデンティファイヤ（uniform resource identifier：ＵＲＬ）を使用してもよく、ウェブ上のファイルを転送する際にハイパーテキスト転送プロトコル（ＨＴＴＰ）を使用してもよい。
【００４０】
他の実現化例では、ユーザは、ネイティブアプリケーションおよび非ネイティブアプリケーションのいずれかまたは双方を通して、システムにアクセスする。ネイティブアプリケーションは、特定のコンピューティングシステム上にローカルにインストールされ、そのコンピューティングシステムのオペレーティングシステムまたは１つ以上のハードウェアデバイス、もしくはこれらの組合せに固有である。これらのアプリケーション（「アプリ」と呼ばれる場合もある）は、直接インターネットアップグレードパッチングメカニズムを介して、またはアプリケーションストア（たとえば、アップルｉＴｕｎｅｓおよびＡｐｐ  ｓｔｏｒｅ、グーグルプレイ（Google Play）ストア、ウィンドウズフォン（Windows Phone）ストア、およびブラックベリー（登録商標）Ａｐｐ  Ｗｏｒｌｄストア）を通して、（たとえば周期的に）アップデートされ得る。
【００４１】
システムは、プラットフォームから独立した非ネイティブアプリケーションで動作可能である。たとえば、クライアントは、１つ以上のサーバから、当該サーバとのネットワーク接続を使用して、ウェブアプリケーションを通してシステムにアクセスし、当該ウェブアプリケーションをウェブブラウザにロードすることができる。たとえば、ウェブアプリケーションは、ウェブブラウザによって、アプリケーションサーバからインターネットを通してダウンロードされ得る。非ネイティブアプリケーションも、ディスクなどの他のソースから得られ得る。
【００４２】
図４は、典型的にはセンサ４０９とクラウド４１２との間にあるエッジゲートウェイまたは同等物上で動作するエッジコンピューティングプラットフォーム４０６のブロック図を示す。エッジコンピューティングプラットフォームは、産業用機械および他の産業用インターネット・オブ・シングスを管理し最適化するために重要であるエッジインテリジェンスを導き出すことを可能にする。エッジゲートウェイのコンポーネントは、取込み４２１と、強化４２５と、複合イベント処理（complex event processing：ＣＥＰ）エンジン４２９と、適用４３２と、式言語を通した解析４３５と、移送４３８とを含む。クラウドは、エッジプロビジョニングおよびオーケストレーション４４３と、クラウドおよびエッジ解析ならびにアプリポータビリティ４４６とを含み得る。
【００４３】
上述のように、エッジコンピューティングプラットフォームの特定の一実現化例は、フォグホーンからのものである。フォグホーンは、「エッジインテリジェンス」という急速に台頭してきているドメインにおけるリーダーである。制御システムおよび物理センサのより近くで高性能処理、解析、および異種アプリケーションをホストすることにより、フォグホーンの画期的なソリューションは、閉ループデバイス最適化のためのエッジインテリジェンスを可能にする。これは、製造、石油およびガス、電力および水、運輸、採鉱、再生可能エネルギー、スマートシティなどにおける法人顧客のために、ビッグデータおよび現場でのリアルタイム処理をもたらす。フォグホーンの技術は、世界の有力な産業用インターネットイノベータ、ならびに、クラウドコンピューティング、高性能エッジゲートウェイ、およびＩｏＴシステムインテグレーションにおける主要事業者によって採用されている。
【００４４】
フォグホーンは、ストリームモードおよびバッチモード双方でのエッジアプリのための強化されたＩｏＴデバイスおよびセンサデータアクセス；解析関数を実行するための非常に効率的で表現的なＤＳＬ；低フットプリント機械上で動作可能である強力な小型解析エンジン；さらなる機械学習のために収集されたデータをクラウドへ送信するための発行機能；エッジアプリを開発するためのＳＤＫ（多言語）；構成のエッジデプロイメント、アプリ、および解析式を管理するための管理コンソールを提供する。
【００４５】
フォグホーンは、産業用機械からのセンサデータのリアルタイムの現場ストリーム処理を可能にする、効率的で非常にスケーラブルなエッジ解析プラットフォームを提供する。フォグホーンのソフトウェアスタックは、エッジおよびクラウド上で動作するサービスの組合せである。
【００４６】
「エッジ」ソリューションは、未処理のデータをオフライン解析のためにクラウド環境へ発行するオプションを用いて、ローカルストレージリポジトリへのセンサデータの取込みをサポートしてもよい。しかしながら、多くの産業環境および産業デバイスはインターネット接続性がなく、このデータを使用できなくしている。しかし、インターネット接続性があったとしても、生成されるデータの純然たる量は、利用可能な帯域幅を容易に上回るであろう。または、あまりに法外なコストがかかるためにクラウドに送信できないであろう。加えて、データがクラウドにアップロードされ、データセンターで処理され、結果がエッジに送り返される時までに、行動を取るには遅すぎるかもしれない。
【００４７】
フォグホーンのソリューションは、解析エンジンとしても公知である超小型の複合イベント処理（ＣＥＰ）エンジンと、多くの着信センサストリームのデータに関する規則を表現する強力で表現的なドメイン固有言語（domain specific language：ＤＳＬ）とを提供することによって、この問題に対処する。これらの表現からの出力は次に、高くつく機械故障またはダウンタイムを防止するために、ならびに、リアルタイムの産業活動およびプロセスの効率および安全性を高めるために、直ちに使用され得る。
【００４８】
フォグホーンのプラットフォームは、低フットプリント環境および高スループットまたはゲートウェイ環境で動作する能力；着信ストリーミングセンサデータに作用できる非常にスケーラブルで高性能のＣＥＰエンジン；強化されたデータアクセスを用いた異種アプリの開発およびエッジへのデプロイメント；クラウドおよびエッジを越えるアプリケーションモビリティ；進んだ機械学習（machine learning：ＭＬ）およびクラウドとエッジとの間のモデル転送を含む。独創的に、フォグホーンは、主な産業用データ取込みプロトコル（たとえば、ＯＰＣ−ＵＡ、モドバス（Modbus）、ＭＱＴＴ、ＤＤＳなど）、および他のデータ転送プロトコルをサポートする。加えて、ユーザは、カスタムプロトコルアダプタを、フォグホーンのデータ取込み層へ容易にプラグインすることができる。
【００４９】
フォグホーンのエッジサービスは、ＩＩｏＴデバイスが存在するネットワークのエッジで動作する。エッジソフトウェアスタックは、センサおよび産業用デバイスからのデータを高速データバス上へ取込み、次にユーザ定義の解析式をストリーミングデータに対して実行して、洞察を得てデバイスを最適化する役割を担う。これらの解析式は、フォグホーンの非常にスケーラブルで小フットプリントの複合イベント処理（ＣＥＰ）エンジンによって実行される。
【００５０】
フォグホーンのエッジサービスはまた、時間ベースのセンサデータクエリについてのローカル時系列データベースと、ストリームモードおよびバッチモード双方でデータを消費できるアプリケーションを開発するための多言語ＳＤＫとを含む。オプションで、このデータはまた、顧客が選んだクラウド格納先へ発行され得る。
【００５１】
フォグホーンのプラットフォームはまた、エッジをリモートに構成し管理するためにクラウド環境または構内環境で動作するサービスを含む。フォグホーンのクラウドサービスは、解析式を開発およびデプロイメントし、ドッカー（Docker）（www.docker.com）として公知であるアプリケーションを使用してアプリケーションをエッジへデプロイメントし、顧客のアイデンティティアクセス管理および持続性ソリューションとのサービスの統合を管理するための管理ＵＩを含む。プラットフォームはまた、クラウドで開発された機械学習モデルを、エッジで実行され得るセンサ式へ変換することもできるであろう。
【００５２】
例として、あるアプリケーションは、キャビテーションイベントによるポンプへの高くつく損傷を防止するために、リアルタイムデータ監視および解析、予測保守スケジューリング、ならびに自動化された流れの方向転換を適用する。別の例は、発電を最大化し、機器の寿命を延ばし、正確なエネルギー予測のために履歴解析を適用するためにフォグホーンエッジインテリジェンスソフトウェアを使用した、風力エネルギー管理システムである。
【００５３】
図５は、エッジコンピューティングプラットフォームのより詳細なブロック図を示す。このプラットフォームは、データ取込み５１２、データ処理５１５、およびデータ発行５１８という３つの論理層または区分を有する。データ取込みコンポーネントは、データを生成するセンサまたはデバイス５２３に接続されるエージェント５２０を含む。エージェントは、それぞれのプロトコルサーバからの１つ以上のプロトコルを介して、センサからデータを集め、または取込む。エージェントは、とりわけ、ＭＱＴＴ、ＯＰＣ  ＵＡ、モドバス、およびＤＤＳといったプロトコル用のクライアントまたはブローカーであり得る。センサによって提供または出力されるデータは典型的には、バイナリデータストリームである。センサからエージェントへのこのデータの伝送または配信は、プッシュ法またはプル法によるものであり得る。
【００５４】
プッシュは、所与のトランザクションに対する要求が送信側（たとえばセンサ）によって開始される通信のスタイルを記述する。プル（またはゲット）は、情報の伝送に対する要求が受信側（たとえばエージェント）によって開始される通信のスタイルを記述する。別の通信手法は、受信側またはエージェントが、センサが送信するべきデータを持っているか周期的に問合せるかまたはチェックする、ポーリングである。
【００５５】
ＭＱＴＴ（以前はＭＱテレメトリトランスポート（Telemetry Transport））とは、ＴＣＰ／ＩＰプロトコルに加えて使用するための、ＩＳＯ規格の発行−サブスクライブベースの「軽量」メッセージ通信プロトコルである。代替的なプロトコルは、アドバンストメッセージキューイングプロトコル、ＩＥＴＦ制約アプリケーションプロトコル、ＸＭＰＰ、およびウェブアプリケーションメッセージングプロトコル（Web Application Messaging Protocol：ＷＡＭＰ）を含む。
【００５６】
ＯＰＣ統一アーキテクチャ（OPC Unified Architecture：ＯＰＣ  ＵＡ）とは、ＯＰＣ協議会（OPC Foundation）によって開発された、相互運用性のための産業用Ｍ２Ｍ通信プロトコルである。それは、オープンプラットフォーム通信（Open Platform Communications：ＯＰＣ）の後継版である。
【００５７】
モドバスとは、元々１９７９年にモディコン（Modicon）（現在のシュナイダーエレクトリック（Schneider Electric））によってそのプログラマブルロジックコントローラ（ＰＬＣ）とともに使用するために発行された、シリアル通信プロトコルである。単純かつ頑強であるため、それはそれ以降、すべての意図および目的のために標準通信プロトコルとなった。それは現在、産業用電子デバイスを接続する、一般に利用可能な手段である。
【００５８】
データ処理５１５はデータバス５３２を含み、それは、データ取込み層のエージェント５２０に接続される。データバスは、すべての接続されたコンポーネント間のデータおよび制御メッセージ双方のための中央バックボーンである。コンポーネントは、データバスを通って流れるデータおよび制御メッセージをサブスクライブする。解析エンジン５３５は、１つのそのような重要なコンポーネントである。解析エンジンは、式言語５３８で開発された解析式に基づいて、センサデータの解析を行なう。データバスに接続する他のコンポーネントは、構成サービス５４１と、メトリックサービス５４４と、エッジマネージャ５４７とを含む。データバスはまた、未加工のバイナリデータを消費可能なデータフォーマット（ＪＳＯＮなど）へ復号するとともに、必要で有用な追加のメタデータで装飾することによって、センサからの着信データを強化する「デコーダサービス」を含む。また、強化は、データ復号、メタデータ装飾、データ正規化などを含み得るが、それらに限定されない。
【００５９】
ＪＳＯＮ（ＪａｖａＳｃｒｉｐｔオブジェクト表記法とも呼ばれる）とは、属性値ペアからなるデータオブジェクトを伝送するために人間が読めるテキストを使用する、オープンスタンダードフォーマットである。ＪＳＯＮは、非同期ブラウザまたはサーバ通信（ＡＪＡＪ）または双方のために使用される共通データフォーマットである。ＪＳＯＮの代替例はＸＭＬであり、それはＡＪＡＸによって使用される。
【００６０】
エッジマネージャはクラウド４１２に、特にクラウドマネージャ５５２に接続する。クラウドマネージャは、同様にクラウドにある、顧客アイデンティティおよびアクセス管理（identity and access management：ＩＡＭ）用プロキシ５５５とユーザインターフェイスコンソール５５８とに接続される。また、クラウドを介してアクセス可能なアプリ５６１もある。アイデンティティおよびアクセス管理とは、正しい個人が正しい時間に正しい理由で正しいリソースにアクセスすることを可能にする、セキュリティおよびビジネス規律である。
【００６１】
データ処理５１５内では、ソフトウェア開発キット（software development kit：ＳＤＫ）５６４コンポーネントもデータバスに接続し、それは、エッジゲートウェイ上にデプロイメントされ得る、機能するアプリケーション５６７の作成を可能にする。ソフトウェア開発キットはまた、データを取出すためにローカル時系列データベースに接続する。アプリケーションは、ドッカーなどのコンテナ技術を使用することなどによってコンテナ化され得る。
【００６２】
ドッカーコンテナは、１つのソフトウェアを完全なファイルシステムで包み、ファイルシステムは、コード、ランタイム、システムツール、およびシステムライブラリといった、それが動作するために必要なものすべてを含み、サーバにインストールされ得るものを何でも含む。これは、ソフトウェアが、それが動作している環境にかかわらず、常に同じように動作することを保証する。
【００６３】
データ発行５１８は、クラウド内の格納位置５７３に接続されるデータパブリッシャ５７０を含む。また、ソフトウェア開発キット５６４のアプリケーション５６７は、時系列データベース５７６内のデータにアクセスできる。時系列データベース（time-series database：ＴＳＤＢ）とは、時系列データ、時間によって索引付けされた数の配列（たとえば、日付−時刻、または日付−時間範囲）を取扱うために最適化されたソフトウェアシステムである。時系列データベースは典型的には、新しい情報がデータベースに追加されると最も古い情報が除去される、回転または循環バッファまたはキューである。データパブリッシャ５７０もデータバスに接続し、ローカル時系列データベースに、またはクラウドストレージに格納される必要があるデータをサブスクライブする。
【００６４】
図６は、エッジインフラストラクチャ６０２とクラウドインフラストラクチャとの間の動作フローを示す。いくつかの特定のエッジインフラストラクチャは上に説明された。センサ６０６からデータが集められる。これらのセンサは、産業用デバイス、小売デバイス、ヘルスケアデバイス、または医療デバイス、もしくは、電力または通信用途、もしくは、これらの任意の組合せのためのものであり得る。
【００６５】
エッジインフラストラクチャはソフトウェアプラットホーム６０９を含み、それは、データ処理６１２と、ローカル時系列データベース６１５と、クラウドシンク６１８と、解析複合イベント処理エンジン（ＣＥＰ）６２１と、解析リアルタイムストリーミングドメイン固有言語（ＤＳＬ）６２４（たとえば、フォグホーンによるＶｅｌ言語）と、リアルタイムアグリゲーションおよびアクセス６２７とを有する。プラットフォームは、以下により詳細に説明される仮想センサ６３０を含み得る。仮想センサは、強化されたリアルタイムデータアクセスを提供する。
【００６６】
プラットフォームは、ソフトウェア開発キットまたはＳＤＫを使用して開発され得る、アプリまたはアプリケーション１、２および３などの１つ以上のアプリケーション６３３を介してアクセス可能である。アプリは（たとえば、複数の異なる言語で開発された）異種であってもよく、複合イベント処理エンジン６２１を活用するとともに、機械学習を行なうことができる。アプリは、アプリストア６３７を使用して配布可能であり、アプリストア６３７は、エッジプラットフォーム開発者またはエッジプラットフォームの顧客（パートナーと呼ばれてもよい）によって提供されてもよい。アプリストアを通して、ユーザは、アプリをダウンロードし、他人と共有することができる。アプリは、機械学習、遠隔監視、予測保守、または動作インテリジェンス、またはこれらの任意の組合せを含む、解析および適用６３９を行なうことができる。
【００６７】
アプリについては、エッジとクラウドとの間に動的アプリモビリティがある。たとえば、フォグホーンのソフトウェア開発キットを使用して開発されたアプリケーションは、エッジ上に、またはクラウド内にデプロイメント可能であり、それにより、エッジとクラウドとの間にアプリモビリティを達成する。アプリは、エッジの一部として、またはクラウドの一部として使用され得る。一実現化例では、この特徴はアプリがコンテナ化されることによって可能になり、そのため、アプリは、それらが実行されるプラットフォームから独立して動作可能である。同じことが解析式についても言える。
【００６８】
クラウドまたは私的データセンター６４４でのデータの監視または格納を含む、統合運営および管理６４０を可能にするデータアプリがある。
【００６９】
物理センサは電子変換器であり、それは、その環境のいくつかの特性をアナログまたはデジタル測定値として測定する。アナログ測定値は典型的には、アナログ／デジタル変換器を使用してデジタル量に変換される。センサデータは、必要ベースで測定（ポーリング）されるか、または、一定速度のストリームとして利用可能である。典型的なセンサ仕様は、範囲、精度、解像度、ずれ、安定性、および他の属性である。多くの測定システムおよびアプリケーションは、処理、移送、または格納のためにセンサデータを直接利用し、または通信する。
【００７０】
システムは、解析式言語を使用して作成されたソフトウェアベースのセンサである、仮想センサとも呼ばれる「プログラマブルソフトウェア定義センサ」を有する。一実現化例では、解析式言語は、フォグホーンの解析式言語である。この式言語はＶｅｌとして公知である。Ｖｅｌ言語は、実行の待ち時間が少ない制約された低フットプリント環境においてリアルタイムストリーミング解析をサポートするために効率的に実現される。たとえば、システムの待ち時間は約１０ミリ秒以下であり得る。
【００７１】
一実現化例では、プログラマブルソフトウェア定義センサは、「センサ式言語」（sensor expression language）またはＳＸＬと呼ばれる宣言型アプリケーションプログラムインターフェイス（ＡＰＩ）を用いて作成される。ＳＸＬ言語の特定の一実現化例は、フォグホーンからのＶｅｌである。Ｖｅｌセンサは、この構成を通して作成されたＶｅｌセンサであり、物理センサおよびＶｅｌセンサを含む複数のソースによって生成されたデータを処理することから導き出された測定値を提供する。本願では、ＶｅｌおよびＳＸＬは交換可能に使用される。
【００７２】
Ｖｅｌセンサは、これら３つのソースのうちのいずれか１つまたはそれらの組合せから導き出され得る。
【００７３】
１．単一のセンサデータ。
１．１．単一の物理センサから導き出される仮想センサまたはＶｅｌセンサは、任意の組合せの動的較正、信号処理、数式、データ圧縮またはデータ解析を使用して、着信センサデータを変換し得る。
【００７４】
２．複数の物理センサデータ。
２．１．複数の異種物理センサから（上述の方法を使用して）変換として導き出された仮想センサまたはＶｅｌセンサ。
【００７５】
３．Ｖｅｌセンサ装置の実現にとって利用可能にされた、物理センサデータと仮想センサデータとの組合せ。
【００７６】
Ｖｅｌセンサはドメイン固有であり、特定のアプリケーションを念頭に置いて作成される。Ｖｅｌプログラミングインターフェイスの特定の一実現化例は、アプリケーションが、変換（たとえば数式）およびアグリゲーションを通してデータ解析を定義することを可能にする。Ｖｅｌは、典型的にはプログラミング言語に基づいた１組の数学演算子を含む。Ｖｅｌセンサは、Ｖｅｌ構成またはプログラムを実行することによって、ランタイムにデータに作用する。
【００７７】
Ｖｅｌセンサの作成：Ｖｅｌセンサは、データをリアルタイムで利用可能にするためのソフトウェア装置として設計される。これは、アプリケーションによって必要とされるレートでＶｅｌセンサデータを生成するために、Ｖｅｌで開発されたアプリケーションが、組込まれたコンピュートハードウェアに対してリアルタイムで実行されることを必要とする。これを達成するために、システムは高効率の実行エンジンを含む。
【００７８】
Ｖｅｌセンサの利点は、以下を含む。
１．プログラム可能性：Ｖｅｌは、Ｖｅｌセンサをプログラマブルにして、データを合成し、データ品質、頻度および情報についての特定のアプリケーション要件に整合させる。Ｖｅｌセンサは、物理センサおよび他の（たとえば、前から存在する）Ｖｅｌセンサから供給されたデータにプラグインするための無線ソフトウェアアップグレードとして広く分散され得る。このため、アプリケーション開発者は、物理インフラストラクチャのレイアウトから独立したビジネスロジックの効率的実行の助けとなるデジタルインフラストラクチャを作成することができる。
【００７９】
２．保守性または透明性：Ｖｅｌセンサは、アプリケーションと物理センサとの間にデジタル抽象化層を作成し、それは、物理センサへのアップグレードおよびサービスによる物理インフラストラクチャの変化から開発者を隔離する。
【００８０】
３．効率：Ｖｅｌセンサは、物理センサからの未加工データをそれらに含まれる情報の正確な表現へ変換することによって、情報管理における効率を生み出す。この効率は、アプリケーションにおける下流での計算、ネットワーキング、および格納のようなＩＴリソースの効率的な利用につながる。
【００８１】
４．リアルタイムデータ：Ｖｅｌセンサは、実在または物理センサデータストリームから計算されるリアルタイムセンサデータを提供する。これは、データを最小の時間遅延でアプリケーションにとって利用可能にする。
【００８２】
実現化例：システムは、Ｖｅｌインターフェイスに基づいて、Ｖｅｌセンサのスケーラブルでリアルタイムの実現化例を設計した。Ｖｅｌは、Ｊａｖａ言語によってサポートされる演算子を含み、物理センサおよびそれらのプロトコルと良好に統合される。
【００８３】
システムは、実行される物理センサのデータに対する演算を正確に表現するための新規の方法をもたらす。この宣言型の式は、デジタル抽象化の定義を、物理センサに対する実現から隔てる。
【００８４】
さまざまな型のデータのストリームのセットと、それらのストリームにおけるデータの特定のパターンに反応しそれら特定のパターンを処理することを意図した関数のセットとが与えられると、本発明は、データがストリームで到着するとこれらの関数が適切かつ効率的に呼び出され得るようにこれらの関数を記述および変換する技術である。
【００８５】
この種の問題を解決する必要性は、すべての形式のデータフロープログラミングで共通して発生する。これは、エンタープライズデータセンター内およびエンタープライズデータセンター間のデータフローなどの非常に大規模なアーキテクチャ、ならびに埋込まれたデバイスにおけるイベントのフローなどの非常に小規模なアーキテクチャに適用可能である。
【００８６】
本発明は、データフロープログラミングのすべての領域に適用可能であるが、一致を検出でき、ハンドラ関数を適用できる速度が最も重要であり、実行に費やすストレージおよび計算リソースが限られている場合に最適である。
【００８７】
実施例。所与の整数のストリームから、１つ以上の非零値に１つ以上の零が続くものをマッチングしたい。このパターンがマッチすると、非零値の和を計算し、その結果を別のストリームに書き込みたい。
【００８８】
この問題のパターンマッチング部分を正規表現の表記法で書き、和の計算を別途算術式として書くことができる。それが起こると、エッジコンピューティングにおいてデータフローアプリケーションで使用するために設計されたＶｅｌプログラミング言語を使用することにより、変換全体を統一された表記法で書くことができ、したがって、
【００８９】
【表１】
2019518264.tif 000003
【００９０】
この技術は、上記の関数のパラメータ化を状態機械に変換するであろう。次に、それは、一致をその状態機械に基づいて決定性有限オートマトンとして実現し、結果の一致を合計式に供給するであろう。このフローを図７に示す。これは、状態０  ７０５、状態１  ７１０、「リストａから」ブロック７１５、および「和（ａ）をプッシュする」ブロック７２０である。
【００９１】
この問題は、各ハンドラ関数ごとにマッチング関数を生成することで解決できる。マッチング関数は、ストリームからデータのウィンドウを入力として受け入れ、一致の場合は真を返し、不一致の場合は偽を返す。データがウィンドウを通って流れると、一致が見つかるまで、マッチング関数を繰り返し適用する必要がある。一致が見つかると、ハンドラ関数が適用される。
【００９２】
この解決策は、ハンドラ関数がデータベースクエリに対して使用されるのと同様の方法で指定されるため、生ずる。ＳＱＬのようなＷＨＥＲＥ節は、一致のための条件を記述するブール式を与え、マッチング関数はこの式の直接的コンパイルである。
【００９３】
別々のマッチング関数は、新たなデータがストリームバッファに流入するときに個別に評価されなければならない。一致は各関数ごとに独立して判断される。
【００９４】
状態機械を使用して一致を実行する方が、複数の任意のブール式を繰り返し適用するよりも、効率的である。
【００９５】
本発明は、関数のパラメータを宣言するパターン記述言語から状態機械を導出する。導出された状態機械は、データストリーム内において、一致を、従来のブール式マッチング関数よりも、より効率的に検出する。
【００９６】
導出された状態機械はまた、データストリームにおいて検出された一致のためにハンドラ関数のセットを実装してもよい。複数のマッチング関数および対応するハンドラ関数を組み合わせて、どのハンドラ関数に対しても効率的に一致を認識する単一の状態機械に縮小してもよい。
【００９７】
導出された状態機械はまた、状態機械によって認識されるシーケンスを変更することなく、追加のノードを介する自由（イプシロン）遷移を含むように拡張されてもよい。
【００９８】
このような追加のノードを介して遷移することにより、データ上でさまざまなアクションをトリガしてもよい。たとえば、決定性有限オートマトン（ＤＦＡ）またはスタックマシンのシフトバッファにおけるデータの、保持領域への収集をトリガすることができる。これらのデータは、後で関数適用に対する引数の基礎を形成してもよい。
【００９９】
この出願ではＤＦＡという用語を使用しているが、これらのオートマトンまたはユニットはスタックマシンと称されてもよい。厳密に言えば、決定性有限オートマトンは、空間における有限の性能を意味する。しかしながら、この特許のオートマトンは、必ずしも有限であるとは限らず、非有限であり得るが、依然として単純であり得る。したがって、この特許に記載されているＤＦＡは、非有限であってもよい。
【０１００】
このような追加のノードを介して遷移することにより、以前のノードで取り込まれたデータを関数適用引数として使用して、ハンドラ関数の呼び出しをトリガすることもできる。
【０１０１】
正規表現および値式の局面を組み合わせたスクリプトからの変換により、パターンのマッチングおよび値の計算を効率的に行い得る拡張された状態機械またはＤＦＡが生まれる。
【０１０２】
結果として生じる組み合わされたマッチングまたは計算アルゴリズムは、パターンマッチングおよび値計算の別個の編成よりも効率的である。
【０１０３】
語彙ソースからＤＦＡまたは状態機械を構築する方法は、非決定性有限オートマトン（ＮＦＡ）で始まり、次いでそれを最小のＤＦＡに縮小する。ＤＦＡの目的は、一連の入力データ内でパターンを認識することである。この議論のため、状態機械を通って流れるデータをトークンと呼び、ＤＦＡによって認識される特定のパターンをトークンの言語と呼ぶ。
【０１０４】
図８のＮＦＡの部分を考える。この部分は偶然ＤＦＡでもあるが、この例では重要ではない。それは、トークンアルファの受信で、状態Ａ８０５から状態Ｂ８１０に遷移する。
【０１０５】
図９に示すように、イプシロン遷移９２０を有する追加のノードを追加することによって、このＮＦＡを拡張することができる。イプシロンエッジは、入力の状態にかかわらず、いつでも‐あたかも自由に‐辿られることができる。
【０１０６】
１つ以上のイプシロンエッジが存在すると、状態機械は非決定性になるが、しかし、イプシロンエッジはアルゴリズムによって除去されてもよく、ＮＦＡはこの手段によって同等のＤＦＡに縮小され、表駆動法によって効率的に実施されることができる。したがって、効率的な実装の戦略を依然として維持しながら、これらの別途のイプシロン遷移を導入することができる。
【０１０７】
図９の状態機械は、トークンアルファ９２５の受信で状態Ａ９０５から状態Ｘ９１５に遷移し、それから随意に状態Ｘから状態Ｂ９１０に進むことができる。アルファの刺激は、図８におけるより単純な機械と同様に、依然として状態Ａから状態Ｂへの遷移をもたらす結果となり、この遷移を達成するために追加の入力は必要ない。したがって、図９のＮＦＡは、図８と同じ言語を変換することが分かる。そうするためには、単に、状態Ｘを通る別途の状態遷移が必要である。
【０１０８】
別途の状態は、副作用のパフォーマンスをそれに関連付けるために役立つ。これらの副作用が状態機械の定義も状態機械を流れるデータも変更しない限り、追加のノードは言語の認識に影響を与えないが、副作用は追加作業を行い得る。
【０１０９】
データフロー反応実現例では、追加作業には、データに対する任意の数の有用なアクション、またはそのデータを使用することを含めることができる。例示的な一実現例では、作業は以下を含む。
【０１１０】
１．ノードを流れるデータを検査し、それのコピーを外部コレクタに発する。
２．データがノードを通過する際にデータに変換を適用し、変換されたデータを一時バッファに収集する。または、
３．収集したデータを一時バッファから追加の変換にフラッシュし、その結果を別のＤＦＡまたはスタックマシンにプッシュする。
【０１１１】
例として、ソースフラグメントを考える：
【０１１２】
【表２】
2019518264.tif 000004
【０１１３】
フラグメントは、２つの項からなるパターンを記述する。（１）ａと呼ばれる第１項。非零値の１回以上の繰り返しとマッチする。（２）名前が与えられていない第２項。１つ以上の零の繰り返しとマッチする。
【０１１４】
これを反応の基礎として使用したいと考える。呼び入れられたソースから値を読み、入力の中でフラグメントのパターンを認識すると、フラグメントの右辺を評価し、呼び出された宛先に結果をプッシュすることで、反応する。
【０１１５】
たとえば、値[101, 202, 303, 0, 0]からなる場合、最初の３つの値をａに、最後の２つの値を匿名の第２項にバインドすることで、パターンをマッチングするであろう。次に、ａにバインドされた値[101, 202, 303]のリストに合計関数を適用することによって、右辺を評価し、６０６を返すであろう。次いで６０６をプッシュアウトするであろう。
【０１１６】
本発明によるこの例のような関数パターンの変換は、コンピュータ実行の変換プログラムを介して実施することができる。プログラムは、２つの異なる形式の変換：関数指向部分“sum(a)”を、計算を実行するであろう実行可能文のブロックに変換すること、およびパターン指向部分“a:{!= 0} .. {>0}, :0 .. {>0}”を、パターンを認識し、引数を取り込み、関数を呼び出すであろうＤＦＡまたはスタックマシンに変換すること、を実行しなくてはならないだろう。前者をタスク関数変換と呼び、後者をタスクパターン変換を呼ぼう。
【０１１７】
関数変換は、コンパイラおよびインタプリタの書込みを専門とするコンピュータプログラマによってよく理解されている。パターン変換、関数変換とパターン変換とのフィッティング、ならびにその後のパターン認識および関数ディスパッチの自動化は、本発明の主題である。
【０１１８】
関数変換は、ソーステキストを受け入れ、テキストをトークンに分割し、その後、文法によって導かれて、ソーステキストの構文的内容を記述する抽象構文木（ＡＳＴ）の葉を形成するようにトークンを配置することからなる。次に、抽象構文木は、ソースによって記述される関数を評価するために必要な命令のブロックを最終的に生成する一連のアルゴリズムによって走査される。
【０１１９】
パターン変換は、上述の構文解析によって形成された抽象構文木から始まる。抽象構文木には、パターン宣言のルートを形成する１つ以上のノードが含まれる。たとえば、上記の我々のパターンは、図１０の左下に示すように、２つの子を有する単一のルートノードで構成され、各子はパターンの１つの項を記述するかもしれない。図１０において、反応ルートノード１００５、パターンルートノード１０１０、和(a)ノード１０１５、ノード１０２０、および<no name>（名前無し）ノード１０が存在する。
【０１２０】
マッチングする例およびそれをマッチングする繰り返しを認識するように指定するパターン項ノードが、正規表現における項と同じ情報を担持することを認識する。さらに、子ノードのシーケンスは、まとめて順に、正規表現の項の線形連言（linear conjunction）と同じ情報を特定する。正規表現または正規表現の項の線形連言は、ＮＦＡへの変換項とすることができる。我々は、本発明において同じアルゴリズムが使用され得、パターン項は正規表現の項の代わりとなることを発見した。
【０１２１】
基本的なＮＦＡがそのように形成されたら、それに、別途の、副作用誘導状態を、アクションがパターン項によって必要とされる位置において注入し、受容状態の後、反応の関数を呼び出すことができる。
【０１２２】
この例を続けると、項ａは、それにマッチする値のリストを収集し、最終的にそれらを引数として反応の関数に渡し得ることを必要とする。したがって、図９に示す変換を項ａの結果であるＮＦＡ状態に適用し、新たな状態を使用して、マッチングする項を収集する作業を行なう。次いで、変換を、再び、今度はＮＦＡの受容状態に適用し、収集された値を使用して反応の関数を呼び出し、結果を反応のコンシューマにプッシュし、収集バッファをクリアする。この強化されたＮＦＡがＤＦＡに変換され、状態が縮小された後、図７に示すマシンが残る。
【０１２３】
ステップは、状態機械エンジンを駆動するよう状態アクション表を用いるためのアルゴリズムのように、ＮＦＡをＤＦＡに変換し、ＤＦＡを状態縮小し、ＤＦＡを状態アクション表として表現するために使用される。
【０１２４】
本発明の技術によって生成されたＮＦＡは、変換されて表に表現されることができる。ただし、結果の表には、各状態を通過するときに実行される副作用ラムダからなる別途の列が含まれる。このような状態アクションラムダ表を使用する自動化エンジンは、他の技術とは異なり、遷移するたびに追加のラムダを実行する。
【０１２５】
データフローコンピューティング環境で使用するためのリアクティブ関数を記述し変換する方法であって、（ｉ）リアクティブ関数を識別することと、（ｉｉ）関数への入力を提供するパラメータのパターンを識別することと、（ｉｉｉ）関数に渡された引数に基づいて評価されるべき式を識別することと、（ｉｖ）パラメータのパターンを、パターンにマッチする入力のシーケンスを認識することができる状態機械に変換することと、（ｖ）状態機械を、入力データを収集および変換してそれを関数に対する引数として使用する準備をする作業を行なう追加の状態で拡張することと、（ｖｉ）状態機械を、単純なソフトウェアまたはハードウェアによる自動化が可能な状態アクション効果表に縮小することとを備える。
【０１２６】
関数のセット、および引数として値のシーケンスを与えられると、本発明は、引数がマッチする関数に実行をディスパッチするか、または引数がいずれの関数ともマッチしないと判断する、方法である。この方法は、値式、型式、および正規表現を組み合わせることによって、それが、型システムで表現可能な値のシーケンスを曖昧さなしにマッチングできるという点において新規である。
【０１２７】
この種の問題を解決する必要があるのは、トランスレータ、インタープリタ、コンパイラの開発においてであり、多相的ディスパッチの概念と密接に関係している。シーケンスの任意の接頭辞を構成する要素が単一のオブジェクト（タプル）を構成すると考えるならば、正しい関数にディスパッチするタスクは、タプルのクラスのメソッドの多相的ディスパッチと等価であると考えることができる。
【０１２８】
本発明は、この種の多相的ディスパッチが必要とされるあらゆる状況に適用可能である。これには、プログラムの外部から発生したデータのストリームに応答する必要があるイベント駆動型またはリアクティブ型プログラムのすべての態様が含まれる。本発明は、エッジもしくはフォグコンピューティング環境またはネットワーク接続環境で頻繁に発生するような、複数のデータストリームのリアルタイム処理に関する適用例において特に有用である。
【０１２９】
正規表現は、通常、特定のパターンに適合する文字列を検出するために使用される。最も密接に関連する多くの正規表現言語、およびそれらに基づいた効率的なマッチングエンジンを実装する多くのツールがある。これらは、一般に、文字のシーケンスのマッチングに限定される。
【０１３０】
文字列以外のドメインで動作する他のパターンベースの表記法がある。ＸＭＬ文書においてパターンを記述するＸＰＡＴＨがその一例である。これらの表記法は、通常、正規表現よりも完全性が低く、パワフルではないことが多く、特定のドメインに合わせて調整されている。
【０１３１】
いくつかのプログラミング言語は、型ベースのパターンマッチングシステムを用いてランタイム多相的ディスパッチを実行する。関数の複数のオーバーロードが定義され、それらの各々は異なるパターンの型および値をとり、引数の型および値を関数パラメータのパターンと照合することによって、ディスパッチが実行時に解決される。Haskellはそのようなプログラミング言語の１つである。
【０１３２】
言語仕様言語は、文脈自由文法を一連の生成規則として記述する。これらの規則は言語の構文を構成する。コンパイラコンパイラは、これらの規則を、言語のインスタンスを認識できる表駆動型決定性有限状態機械に変換する。Bisonは、そのような言語仕様言語およびそれの関連するコンパイラコンパイラの例である。
【０１３３】
正規表現などの文法駆動型パターンマッチングシステムは、決定性有限オートマトン（ＤＦＡ）や状態機械などの単純な機械として表現できるため、効率的実行の利点があるが、それらには、完全な型システムの幅広いモデリング機能はない。Haskellで使用されているような型駆動型パターンマッチングシステムは、はるかにより豊富なモデリング機能を備えているが、合理的に効率的な実装を優先して表現できるものをしばしば犠牲にし、それでも依然として、ＤＦＡに基づく高速マッチングシステムほど効率的ではない。
【０１３４】
本発明は、型に基づくマッチングシステムを扱い、それは、その型の中で表現可能なすべての状態と照合することができながら、依然として状態機械として効率的に実施され得る。型と状態との一般化されたパターンは、パターンのインスタンスを効率的に認識する表駆動型状態機械に変換される。
【０１３５】
これらのパターンに基づいて関数パラメータを定義することにより、関数はまさにどのような恣意的なデータパターンともマッチングし、マッチングにおいて、マッチングするデータ要素間からその引数をバインドすることができる。メンバー関数の状態機械をマージし、その結果を最小の状態数に縮小することによって、関数の合併（union）のためのマッチングパターンを記述する状態機械が形成される。オーバーロード間の曖昧さ回避、または全体的な不一致の検出は、シーケンス内で可能な限り早く起こり、関数適用の解決をスピードアップする。また、シーケンス内でできるだけ遅くまで一致を遅らせて、可能な限り多くの入力を受け入れる関数の「貪欲」バージョンを生成することもできる。
【０１３６】
あるメソッドは、値式、型式、および正規表現を組み合わせて、それが、型システムで表現可能な任意の値のシーケンスと曖昧さなくマッチングし得るようにする。このメソッドは関数適用を解決し、最小限の判断数で正しいオーバーロードにディスパッチする。このメソッドにより、オーバーロードされた関数適用は、文脈自由文法と同じ作業を実行し、文法的な下位構成要素を帰納的に認識して変換関数をそれに適用することによって特定の言語を認識することができる。
【０１３７】
このメソッドは、複数の異なる型を含む型システムに関連して適用可能であり、たとえば、（１）整数、実数、および文字列などの基本的な単相型の集合（set）。（２）多相型の集合およびそれらのコンストラクタ、特に、我々が間もなく論ずるある特定のプロパティを持つ多相集合型。（３）sum型。（４）レコードの形式のproduct型。（５）パターンの形式のproduct型。タプルの、それのフィールドの繰り返しを含むことへの一般化である。（６）ラムダ型。パターン型を任意の型にマッピングする。（７）ラムダのリストからなる多ラムダ型。
【０１３８】
集合は、１つ以上の要素の範囲からなる多相型である。集合型は、それが含む要素の型上においてパラメータ化され、たとえば、整数の集合は文字列の集合とは異なる型である。集合型は、その内容の制限によってさらに特徴づけられる。特に、集合型は、有限もしくは無限であるよう、またはその左辺もしくは右辺において閉じられているかもしくは開いているよう、またはこれらの任意の組み合わせであるように、制約されてもよい。以下の整数の集合の例を考えてみよう。
【０１３９】
【表３】
2019518264.tif 000005
【０１４０】
[>= 1]と[> 0]との間に区別はなく、なぜならば、要素は整数型であり、整数は相異なって可算であるからである。要素が、仮に、実数や文字列のように、非可算型である場合、明示的な包含または特定の端点の包含が必要となる。たとえば、集合[>= “cat”]は、文字列“cat”、および辞書編集上“cat”の後に分類するすべての文字列で構成されている。
【０１４１】
集合のインスタンスを型として使用してもよい。そのような型のインスタンスは、集合の要素でなければならない。たとえば、型として使用される集合[> 0]は、正の整数だけを値として許可するであろう。実際、すべての型をこのように考えることができる。たとえば、単相の整数型は、すべての整数の集合からなる集合型と考えることができる。
【０１４２】
我々のsum型は、他の型の単純な合併（union）である。たとえば、型int（整数）または型string（文字列）は、その２つの構成要素型の和である。sum型の構成要素型のいずれかの何れのインスタンスも、sum型のインスタンスである。これにより、たとえば、各々が整数または文字列のいずれかである値のリストである型リスト（intまたはstring）を記述することができる。unionのunionは平坦（flatten）になり、型式（intもしくはstring）または（intもしくはreal（実数））はintまたはrealまたはstringに等しくなる。unionにおける型の順序は重要ではないが、正規性のため、すべてのunion型をここにおいてそれらの構成要素がアルファベット順であるように提示する。
【０１４３】
我々のレコード型は名前付きフィールドを使用し、各フィールドを型に関連付ける。たとえば、{birthday: date; first_name: string; last_name: string}（{誕生日: 日付; 名: 文字列; 姓: 文字列}）レコード型は常に有限数のフィールドを有し、各フィールドは型内において一意の名前を有する。フィールドの順序は重要ではない。{x: int; y: int}は{y: int; x: int}と同じであるが、unionに対してしたように、我々はレコード型を、それらの構成要素がアルファベット順にある状態で提示する。
【０１４４】
レコードの型はそれ自体がレコードであることに注意されたい。値{x: 3; y: 4}は型{x: int; y: int}を有する。
【０１４５】
我々のパターン型は、型のシーケンスとして定義されている点で、タプルに似ている；しかしながら、タプルは暗示的にその要素の各々が正確に１回現れると仮定しているが、パターンはそれの各要素が繰り返しを有することを許す。この繰り返しは整数の集合として与えられる。たとえば、パターン<a: int # [1 .. 3]; b: string # [1 .. 3]>は１つから３つの整数の後に１つから３つの文字列が続くものとマッチする。
【０１４６】
ラムダのパラメータとして使用すると、パターンのフィールドはラムダの評価内でバインドされる引数を生じさせる。たとえば、前の段落で与えられたパターンをマッチングした後、範囲に２つのローカル識別子ａおよびｂを有するであろう。Ａの値は１つから３つの整数のリストになり、ｂの値は１つから３つの文字列のリストになるであろう。
【０１４７】
パターンについて１つ以上のフィールドが名前を持たないことも有効である。名前のないフィールドはマッチングされるが、それに対するどのような値も引数としてバインドされない。たとえば、<a: int # [ 1 .. 3 ]; string # [ 1 .. 3] >をマッチングした場合、前のように１つから３つの整数の後に１つから３つの文字列が続くものをマッチングさせ、整数をａというリストとしてバインドするが、文字列はバインドしないであろう。
【０１４８】
パターンは無限長であってもよい。たとえば、パターン<a: int # [ 1 .. ]>は１つ以上の整数と上限なしでマッチする。これは有効である。ただし、無限入力ストリームを処理するために使用する場合、無限のパターンを、値の収集をいつ停止すべきか示す時間間隔などの他のトリガとペアにする必要がある。
【０１４９】
一般に、パターンは、それがマッチするデータを消費するが、しかしながら、そのデータの部分集合のみを消費することも、またはまったく消費しないことが可能である。パターンには、ピークポイントと呼ばれるアットマークが含まれてもよく、それを越えて、パターンはデータとマッチし、引数をバインドするが、入力ストリームからは消費しない。たとえば、パターン<a: int; b: int; peek; c: int> は３つの整数とマッチし、３つのローカル識別子をバインドするが、入力から２つの整数しか消費しない。
【０１５０】
フィールドのないレコードまたはフィールドのないパターンを有することは有効である。これらの２つのケースは、両方ともproduct型を意味するため、互いに有意に区別できない。語彙的には、この概念をボイドというキーワードで指定する。ボイドは一意の値である。それ自身の型でもある。合併で使用される場合、ボイドはintまたはvoidなど、任意選択的な型の表記をもたらし、存在する場合にはintである値を意味するが、まったく存在しないかもしれない。
【０１５１】
我々の目的のために、型マッチングは構造的であり、名目上のものではない。型には名前はなく、記述だけがある。同じ記述を有する２つの型は同じ型である。記述が別の型の記述の部分集合である型は、その型の一般化である。たとえば、型{x: int; y: int}および{x: int; y: int; z: int}を考える。２つのフィールド-xおよびy-を有する型は、３つのフィールド-x, yおよびz-を有する型の部分集合であるため、前者は後者の一般化と見なすことができる。これはパターンにも当てはまる。別のものの接頭辞であるパターンもその一般化である。
【０１５２】
我々のラムダ型は、入力パターンを出力型にマッピングする。たとえば、<int # [1 .. 3]> → intは、１つから３つの整数をとり、ある整数を返す、ある関数の型である。我々の多ラムダ型は、ラムダ型のリストで構成されている。ラムダの順序はここでは重要である。多ラムダ適用を解決する際、それの構成要素ラムダのうちマッチする最初のラムダにディスパッチすることになる。
【０１５３】
このように定義されると、多ラムダをディスパッチするのに必要なパターンマッチングは、決定性有限オートマトン（ＤＦＡ）に縮小され得る。どのようにするかを示すために、比較のための基礎として状態機械の構築方法を使用し、必要に応じてそれを拡張する。ある記述は、まず、非決定性有限オートマトン（ＮＦＡ）を構築すること、および次いでそれをＤＦＡに縮小することを含むが；しかしながら、実際には、これは一般に単一のステップで行うことができる。
【０１５４】
前述したように、この出願ではＤＦＡという用語を使用しているが、これらのオートマトンまたはユニットはスタックマシンと称されてもよい。厳密に言えば、決定性有限オートマトンは、空間における有限の性能を暗示する。しかしながら、この特許のオートマトンは、必ずしも有限であるとは限らず、非有限であり得るが、依然として単純であり得る。したがって、この特許に記載されているＤＦＡは、非有限であってもよい。
【０１５５】
第１に、多ラムダの構成要素-個々のラムダパターン-は、離接の要素として考えなければならない。正規表現を変換する場合、構文a|b (a OR B)は離接であり、一致ａ１１０５または一致ｂ１１１０である。我々の例では、a AND bは各々ラムダパターンである。図１１に従って離接のための部分グラフを作成する。
【０１５６】
我々は個々のパターンのフィールドをまず合接により表わす。正規表現の変換では、構文ａｂ１２１０は合接であり、一致ａ１２０５の後にｂ１２１５が続く。我々の例では、a AND bはパターンの各フィールドである。図１２に従って、合接のための部分グラフを作成する。
【０１５７】
フィールドの反復係数は、従来はa+またはa*またはa{n:m}と書かれた正規表現の閉包と同じである。ここでも、図１３のような構造でこれらの閉包を表現できる。この場合、反復集合の値に基づいて、部分グラフにおけるなんらかの変化が必要になる。たとえば、ノードｉ１３０５からノードｊ１３１０への順方向イプシロン１３１５は、集合が零を含む場合にのみ含まれる。これらの変化は大部分明白であり、ここで説明したのと同じ基本的な考え方に沿って継続する。
【０１５８】
中間のＮＦＡが完結した後、それをＤＦＡに縮小し、次いでそのＤＦＡを最小のＤＦＡに達するまで状態縮小する。次に、ＤＦＡを、状態機械の自動化に使用される通常の種類のソフトウェアまたはハードウェアによる自動化に適した状態−アクション表として表現する。この表の受容状態は、多ラムダへのエントリポイントをマーキングし、中間状態は引数をバインドするために使用されるデータの集まりを提供する。
【０１５９】
ＤＦＡがそのように自動化され、入力ストリームが提供されると、それは、ストリームからの入力の接頭辞にマッチし、正しいオーバーロードにディスパッチしてそれらを処理し、計算結果を生成する。このプロセスが繰り返されることが許されている場合、結果は、入力ストリームからの一致ごとに１つの、生じた結果のシーケンスである。これは、データストリーム内で検出されたさまざまな型の引数の対応するパターンによってトリガされる多相型関数によって、入力データストリームの効率的なリアルタイム処理を提供する。
【０１６０】
値と型識別子との混合を含む複数の種類の関数引数を含むデータストリームに応答して多相型関数の実行をディスパッチする方法であって、（ｉ）実行されるべき多相型関数を識別することを備え、当該多相型関数は、異なる種類の引数のパターンに各々が関連付けられる複数のオーバーロードを有し、前記方法はさらに、（ｉｉ）各オーバーロードについて、オーバーロードの引数パターンをマッチングすることによって、入力ストリームからバインドされる引数値の集合にわたって評価される出力式を識別することと、（ｉｉｉ）各オーバーロードの引数パターンを、入力ストリームにおけるパターンについて一致を効率的に認識するＤＦＡに変換することと、（ｉｖ）個々のオーバーロードのＤＦＡを、全体として多相型関数のための単一のＤＦＡに結合することとを備え、結果として得られる結合されたＤＦＡは、個々のＤＦＡによってマッチングされるであろう任意のパターンをマッチングし、マッチングする入力を処理すべきオーバーロードを選択することができ、前記方法はさらに、（ｖ）結合されたＤＦＡにデータストリームを適用し、ＤＦＡは、次いで、必要に応じてストリームからデータを検査もしくは消費またはその両方を行なって、一致または無一致を判定し、一致の場合には、入力引数値を適切にバインドし、評価されるべき適切な出力式を選択することと、（ｖｉ）出力式の評価をディスパッチし、結果を返すこととを備える。
【０１６１】
リアクティブ関数によって生成される異なる型のデータのストリームのセットが与えられると、本発明は、それらのストリームを、それらの出力が、統合された型の単一のストリームに効率的に構成され得るように、表現する技術である。
【０１６２】
この種の問題を解決する必要性は、すべての形式のデータフロープログラミングで共通して発生する。これは、エンタープライズデータセンター内およびエンタープライズデータセンター間のデータフローなどの非常に大規模なアーキテクチャ、ならびに埋込まれたデバイスにおけるイベントのフローなどの非常に小規模なアーキテクチャに適用可能である。
【０１６３】
本発明は、データフロープログラミングのすべての領域に適用可能であるが、一致を検出でき、ハンドラ関数を適用できる速度が最も重要であり、実行に費やすストレージおよび計算リソースが限られている場合に最適である。
【０１６４】
実施例。ｎ個の別個の入力ストリームのセットからなる流入Ai:0<k<nを考える。各ストリームは、型Tiの要素のキューで構成される。各ストリームは、型Ti→Uiのリアクティブ関数fiによって消費および変換されており、型Uiの要素のキューから各々がなる流出のｎ個のストリームBiが存在する。すべてのストリームBiを、Σ Tk→Σ Ukのマージ関数mを用いて、単一のストリームCにマージしたい。
【０１６５】
３つのストリームの間で発生するこのようなマージの例をＶｅｌ言語で書いて以下に示す。
【０１６６】
【表４】
2019518264.tif 000006
【０１６７】
ストリームCは、B0、B1およびB2からの値から構成され、それらが生成されるときにインターリーブされる。Bストリームの内容を実現することにポイントがないことに注意されたく、なぜならばそれらはCストリームを構成するためだけに使用されるためである。それらは匿名の一時的な部分式として同じく簡単に表現できるであろう。
【０１６８】
【表５】
2019518264.tif 000007
【０１６９】
本発明は、各変換関数fiを決定性有限オートマトン（ＤＦＡ）に変換し、マージ関数mをこれらのＤＦＡの合併として単一の最小ＤＦＡに変換することを記載する。その結果、中間流Biの内容を実現する必要なく流入Aiを流出Cにマージする最大効率的な手段が得られる。
【０１７０】
この技術は、繰り返し適用され、後続の中間流の層を単一のリアクティブ関数に融合させることができる。これは、Ｖｅｌの場合のように、宣言型データフロー言語のインフィックスまたは演算子で表されるマージの概念と整合している。
【０１７１】
この問題はブルートフォースによって解決できる。すなわち、マージ関数が中間流の唯一のコンシューマであっても、中間流を実現し、それらを消費することによって達成される。
【０１７２】
また、マージ関数では、それの流入および流出が、すべて、同じ型のものであるか、そうでなければ、型のないシステムの場合においては未分類のものであることを必要とすることもよくある。これは、それらの型システムにunion型（sum型とも呼ばれる）がないためである。データフローシステムにおける真のマージの存在は、union型の使用を要求する。
【０１７３】
一部のデータフローシステムでは、真のマージを欠き、代わりに複数入力単一出力リアクティブ変換を実施する。これらはそれら自体有用な構成体であるが、真のマージ関数ほど単純でも一般的でもなく、完全に最適化することはできない。
【０１７４】
マッチング関数をＤＦＡとして表現することは、ブール型の任意の式として表現するよりも効率的である。各自の駆動流入を伴う複数のマッチング関数のＤＦＡは、単一の流出を伴うマージ関数を表す単一の効率的なＤＦＡを形成するために統合される。ＤＦＡのマージは、できるだけ早くまたはできるだけ遅く結果がマッチングするように行われ、結果として２つの異なる潜在的に望ましい挙動が生じる。複数の反応を１つのＤＦＡに構成することにより、最小の機械、つまり、最小数の判断を用いてすべての一致を実行するアルゴリズムが得られる。最小の機械は、小規模なプラットフォーム用の複数の反応の最も好適な実現例である。最小の機械は、マッチング式の複数の別々の評価よりもアルゴリズム上の利点を有するため、他のすべてが等しい場合、より効率的に実行される。
【０１７５】
変換ＤＦＡのセットを単一のＤＦＡにマージするには、正規表現で代替（alternation）を考えるように変換ＤＦＡを考慮する必要がある。正規表現を変換する場合、構文a|bは代替であり：一致a OR 一致bである。我々の例では、a AND bは各々変換関数からのＤＦＡである。図１１に従ってそれらの代替のための部分グラフを作成する。
【０１７６】
中間の非決定性有限オートマトン（ＮＦＡ）が完結した後、それをＤＦＡに縮小し、次いでそのＤＦＡを最小のＤＦＡに達するまで状態縮小する。次に、ＤＦＡを、状態機械の自動化に使用される通常の種類のソフトウェアまたはハードウェアによる自動化に適した状態−アクション表として表現する。この表の受容状態は、マージされたデータ要素が出力ストリームに放出される点をマーキングする。
【０１７７】
ＤＦＡがそのように自動化され、入力ストリームのセットが提供される場合、ＤＦＡは、各入力を、その入力に関連付けられた元の変換関数に従って変換し、すべての結果を１つの出力上でともにインターリーブして与える。
【０１７８】
入力データの複数の独立したストリームを出力データを単一のストリームにマージする方法は、（ｉ）複数の潜在的な入力データストリームを識別することと、（ｉｉ）入力ストリームごとに１つ、各入力ストリームにおけるデータ上で実行され、その結果が一緒になるようマージされる、複数の変換関数を識別することと、（ｉｉｉ）入力データ要素を、複数のストリームから同時に受け取り、データ要素を単一の出力ストリームにインタリーブするマージ関数を識別することと、（ｉｖ）各変換関数を、変換を効率的に実行するＤＦＡに変換することと、（ｖ）変換ＤＦＡを、変換を効率的に実行し、その結果を単一のストリームにインターリーブする単一の結合されたＤＦＡにマージすることと、（ｖｉ）結合されたＤＦＡにデータストリームを適用し、ＤＦＡは次いで変換およびマージの作業を実行することと、（ｖｉｉ）マージされた出力を使用のために宛先にディスパッチすることとを備える。
【０１７９】
本発明は、Ｖｅｌプログラミング言語でソフトウェアを開発するためのツールおよび関連する方法である。Ｖｅｌは、データフロープログラムの表現に役立つプログラミング言語である。正しいデータフロープログラミングには多くの課題がある。いくつかはすべての形式のコンピュータプログラミングに共通する課題であり、他のいくつかはデータフローパラダイムに特有の課題である。このツールは、以下を含む、Ｖｅｌプログラミングの多くの分野に対応している：（１）構文的および意味的な正しさをチェックする。（２）論理的な正しさをチェックする。（３）デバッグ支援。（４）ソースコードを安全かつポータブルな形式（つまり、パッケージ化されたコード）に変換する。（５）さまざまなコンピューティングプラットフォーム、特に小規模なプラットフォームに適した、ネイティブで最適なバイナリ形式へのソースコードまたはパッケージ化されたコードの変換。（６）パッケージ化されたコードの記述およびその署名の確認。（７）パッケージ化されたコードのバッチモード解釈。（８）Ｖｅｌソースのインタラクティブな解釈。（９）パッケージ化されたコードまたはネイティブコードを実行するデータフロー環境のシミュレーション。（１０）ライブデータフロー環境におけるバイナリコードの遠隔実行、監視、および制御。
【０１８０】
これらは、Ｖｅｌ言語でソフトウェアを開発している誰もが達成する必要があるタスクである。本発明は、Ｖｅｌプログラミングに熟練した者が、正確で有用なソフトウェアを作成することを可能にするために、これらの分野すべてにおいて十分なサポートを提供する。
【０１８１】
構文上および意味上の正しさをチェックすることは、多くの形態の自動ソフトウェア変換に共通するタスクである。論理的な正しさをチェックするためのツールは、通常、変換ツール自体には組み込まれていない。これらの種類のツールは別々に存在するのが一般的であり、それらがテストしているコードの不完全な洞察をしばしば伴う。
【０１８２】
デバッグはソフトウェア開発の共通タスクであるが、ほとんどのデバッグツールは命令型プログラミングに重点を置いている。関数型およびリアクティブプログラミングのデバッグは、命令型デバッグとはまったく異なる課題を提示するため、それほど一般的に対応されない。特に、これらの言語では、「フライト中の」計算を検査するのは困難であり得、なぜならば、それらの値はデバッガ（およびデバッガプログラマ）が覗き得るアドレスを有さないことが多いからである。
【０１８３】
複数のネイティブプラットフォームアーキテクチャを対象とする能力は、Ｃなどのシステム言語のコンパイラにはまれではないが、スクリプトレベルの言語では一般的に見られるパワーではない。スクリプト言語は、コンパイルされないか、またはそれらのホストのために部分的にコンパイルされるかまたはジャストインタイムでコンパイルされる（ジットされる(jitted)）傾向があるが、クロスコンパイル（１つのアーキテクチャで実行されるが、別のアーキテクチャに対してコードを生成するコンパイラ）はまれである。小規模なプラットフォーム上で実行するためにスクリプトレベルの言語を具体的にコンパイルすることは非常に珍しいことである。
【０１８４】
対話型シェルは、スクリプト言語の共通の機能である。たとえば、Pythonはシェルを実装している。実際の、またはシミュレートされたデータフロー環境に接続されるシェルは、あまり一般的ではない。
【０１８５】
コンパイルされたコードの遠隔実行は、一部のオペレーティングシステムの機能であり、オープンソースおよび商用の両方のいくつかのサードパーティツールからも利用可能である。これらは、具体的に小規模なプラットフォームを対象としない傾向があるが、小規模なプラットフォーム用の遠隔実行ツールの例が存在する。これらはデータフロープログラミングに特有のものではなく、遠隔で実行されるべきプログラムを開発するのに使用されるツールに組み込まれていない。
【０１８６】
Ｖｅｌコードを開発するための単一の統合されたツールは、Ｖｅｌ言語で作業するソフトウェア開発者にとって有用で便利である。このツールは主にＶｅｌ言語を変換するコンパイラであるが、Ｖｅｌプログラミングに関連する他のいくつかの関数のセットも提供する。ツールで論理的な正しさのテストを構文的および意味的な正しさのテストとともに実行すると、開発者はより効率的になり、コードの正確性を高めることができる。論理テストでは、コンパイラによるコードの洞察の恩恵があり、診断メッセージはより完全なものになり得る。対話型シェルにより、開発者はコードをテストして即座の応答を得ることができる。これは開発やデバッグに便利である。シェルはまた、プログラマがデータフロー環境を視認できるようにする。
【０１８７】
小規模なプラットフォームでの使用に適したスタンドアロンのバイナリ実行可能コードを生成することは、さまざまな小型デバイスで複雑な計算を実行することにしばしば依存する、物のインターネット使用事例を可能にする。シミュレートされたデータフロー環境を提供することで、開発者はコードにおけるバグを解消し、論理的な正しさに対するテストと連携して、パッケージが正しく動作していることを実証できる。コンパイルされたパッケージを遠隔で実行する場合、特に遠隔プラットフォームが小さい場合、プログラマは、自分のプログラム上で迅速に、プログラムをそれのターゲットハードウェア上で１つのコマンドでコンパイルしテストすることを、たとえターゲットプラットフォームが、自分がその上で開発しているものでなくても、反復できる。
【０１８８】
言語をそれの語彙的表現からこの中間の記号的表現に変換（フェーズ１コンパイル）し、次いでこの中間表現を計算ハードウェアによって実行され得る形式に変換（フェーズ２コンパイル）するプロセス。
【０１８９】
Ｖｅｌフェーズ１変換ツールは、コンパイラに共通する一般的な戦略に従い、具体的には次のとおりである。（１）入力文字列を解析してそれをトークンのシーケンスに分解する。（２）トークンのシーケンスを解析して構文木を形成する。（３）構文木内の記号宣言を識別する。（４）構文木内の記号参照の特定および解決。（５）共通の部分式の削除や定数の折り畳みなどの初期の最適化。（６）型チェック。（７）最適化および記号成熟の追加フェーズ。（８）記号の最終決定および中間表現の放出。
【０１９０】
Ｖｅｌフェーズ１トランスレータの際立った特徴の１つは、それが、決定性有限オートマトンまたはＤＦＡを用いて、関数適用に必要なパターンマッチングを実行し、反応をトリガすることである。フェーズ１変換ツールは以下を含む。（１）入力言語を構文木に変換する構文解析器。（２）解析中の言語がＤＳＬまたはマクロ解析器の態様で解析器によって修正され得るように、変換中のプログラムが自己参照を行うことを可能にする語彙バインドコンポーネント。（３）バインドされた構文木を、データフロー、パターン、反応、関数式、タイマー、および入出力パラメータ化を表す記号に変換する意味解析アルゴリズム。（４）式木を、多かれ少なかれマイクロプロセッサＡＬＵ命令への直接変換に適したスタックに変換する式トランスレータ。（５）反応のパターンおよび式を潜在的に非最小のＤＦＡの中間収集物に変換するためのＤＦＡジェネレータ。（６）ＤＦＡの中間収集物から統合された最小のＤＦＡを作成するためのＤＦＡ結合および縮小アルゴリズム。
【０１９１】
フェーズ１変換ツールの出力は以下を含む：（１）変換に関与する各ストリームの論理的アイデンティティ。各々が複数のストリームの中で一意的な参照であり得るようにする。（２）各ストリームにおけるデータにおけるフローの記述。各々、内方向（反応に向かう、すなわち外部ソースへのサブスクリプション）、外方向（反応から離れる、つまり外部の宛先へのパブリケーション）、内方向および外方向の両方（パブリケーション／サブスクリプションのペア）、または内部（他の反応における中間ステップとしてのみ使用されるため、パブリケーションまたはサブスクリプションとして表面化されない）である。（３）各ストリームにおいて流れるデータの型の記述。ストリームに注入またはストリームから抽出されるデータが型の正しさを静的にチェックされるように、都度有限項で記述される。（４）ＤＦＡの状態および遷移を記述する表のセット。（５）反応の間に実行されるべき計算を記述する式スタックのセット。（６）ストリーム入力をＤＦＡ入力にマッピングする表。（７）時限イベント（timed event）をＤＦＡ入力にマッピングする表。（８）ＤＦＡ出力をアクションのペアにマッピングする表。各ペアは、式スタックへの参照およびストリーム出力から構成され、ＤＦＡの出力が所与の式で変換され、次いで所与のストリームにプッシュされることを示す。
【０１９２】
Ｖｅｌインタプリタおよびデータフローシミュレータはフェーズ１変換の出力を直接使用する。インタプリタはコードの実行においてハードウェアプラットフォームをエミュレートし、データフローシミュレータはストリーミングデータ環境をエミュレートし、Ｖｅｌストリームに入力を提供し、Ｖｅｌストリームから出力を収集する。これらの２つのタスクを命令解釈およびデータフローエミュレーションと呼ぼう。
【０１９３】
命令解釈は、コンパイラおよびインタプリタの作成を専門とするコンピュータプログラマがよく理解するタスクのカテゴリである。タスクには、実行時変数の状態を格納できる実行コンテキストを構築し、プログラムの命令を一度に１つずつ実行し、実行コンテキストからデータにアクセスし、必要に応じてそれを更新することが含まれる。
【０１９４】
Ｖｅｌの場合、実行コンテキストには、変換の過程でデータのストリームを保持するキューのセット、およびＤＦＡで記述された変換を実行する表駆動型の状態機械エンジンも含まれている必要がある。キューは、データの流通チャネルを記述する、Ｖｅｌソースにおける宣言のため、発生する。これらのうちのいくつかは、Ｖｅｌプログラムの外部入力または出力であり、他のいくつかは入力と出力との間の中間状態を記述する純粋な内部チャネルである。
【０１９５】
データフローエミュレーションは、ファイルやソケットなどのデータのために外部ソースおよびシンクへのアクセスを提供することと、これらの外部システムと解釈されているＶｅｌプログラムとの間でデータを交換するために必要なプログラミングとからなる。これには、外部ソースからデータを読み出してそれらデータをプログラムの入力を表すキューにプッシュする注入関数と、プログラム出力を表すキューからデータをポップしてそれらデータを外部シンクに書き込む抽出関数とが含まれる。
【０１９６】
本発明によるＶｅｌの解釈が正規とは異なるところでは、ＤＦＡが関与するようになる態様である。状態機械エンジンは、キューからデータを読み取り、それらデータを使用してそれらのＤＦＡの状態を前進させる。ＤＦＡ表には、ＤＦＡがそれらの状態を通過するときに実行される副作用の列が含まれる。これらの副作用は、命令解釈を呼び出して計算を実行し、その結果は他のキューにプッシュされ、これが他のＤＦＡをトリガする。
【０１９７】
このようにして、本発明による解釈中のＶｅｌプログラムは、最初に、高速かつ小規模な状態機械のセットによって表され、必要なときに一般的な命令解釈にドロップバックするだけである。これにより、命令解釈だけですべて処理される場合よりも、プログラムの実行効率が向上する。
【０１９８】
Ｖｅｌフェーズ２変換ツールは、大部分、Ｖｅｌ言語に固有ではなく、実行対象のプラットフォームに固有である。フェーズ２トランスレータのＶｅｌ言語関連コンポーネントは次のとおりである。（１）フェーズ１によって生成された中間表現の初期取入れ。（２）反応性システムを生成するフェーズ２コード生成の全体的編成。（３）データフォーマットの外部エンコードおよびデコード、またはリアルタイムクロックの内部調整を実行するもののような、ランタイムサポートコンポーネントのライブラリの提供。
【０１９９】
マルチソース・マルチ宛先データフロー環境におけるデータストリームのリアルタイム処理のためにプログラムを作成するためのツールは、以下を含む。（１）複数の潜在的なデータストリームを識別すること。（２）ストリームにおけるデータのパターンに対応するリアクティブ関数およびパラメータのセットを識別すること。（３）宣言されたパターンにマッチするデータを変換するための処理関数およびパラメータのセットを識別すること。（４）データが収集または破棄される時間の間隔や、データが収集または破棄される前後の特定の時点など、データフローのパターンが比較される時限イベントのセットを識別すること。（５）識別されたストリーム、反応、関数、および時限イベントを記述するデータフロープログラムを作成すること。（６）このプログラムを、Ｖｅｌプログラム文を対応するＤＦＡに変換するためのＤＦＡジェネレータを組み込んだフェーズ１変換ツールと、プラットフォーム上での実行のために変換されたＶｅｌ文に対応するプラットフォーム固有のハードウェア命令を生成するためのフェーズ２変換ツールとを備える２フェーズ変換ツールに、入力として与えること。（７）変換ツールの各フェーズの出力を受け取ること。
【０２００】
フェーズ１変換ツールの出力は、以下を含むインタプリタコンポーネントによって使用されてもよい：（１）コードの実行においてハードウェアプラットフォームをエミュレートする命令インタプリタ。（２）ストリーミングデータ環境をエミュレートし、Ｖｅｌストリームに入力を提供し、Ｖｅｌストリームから出力を収集するデータフローシミュレータ。
【０２０１】
フェーズ１変換ツールの出力は、以下を含むフェーズ２変換ツールへの入力として使用することができる：（１）中間表現からの命令をターゲットハードウェアプラットフォームによる実行に適した形式に変換するハードウェア命令ジェネレータ。（２）データフロー環境におけるリアクティブプログラムとしての使用に適した形式に出力の生成を向けるプログラム編成モジュール。（３）実行に必要なランタイムサポートコンポーネントのライブラリ。フェーズ２変換ツールの出力は、対象とされるハードウェアプラットフォーム上での使用に適した実行可能なプログラムである。
【０２０２】
図１４は、入力から仮想センサを生成するために使用されるＶｅｌセンサ式言語エンジン１４０７を示す。センサ式言語エンジンは、物理センサまたは他の仮想センサから入力をとる。入力のいくつかの例は、入口圧力１４１１、出口圧力１４１４、温度１４１７、およびフロー１４２０を含む。任意の数の入力または入力の組み合わせを仮想センサへ入力として使用できる。入力に基づいて、センサ式言語エンジンは、圧力差１４３１、温度１４３４（ケルビンであってもよい）、および蒸気圧１４３７などの出力とともに仮想センサを生成することができる。任意の数の仮想センサおよび出力が存在し得る。説明したように、出力は、仮想センサに対する入力の数学的関数とすることができる。
【０２０３】
図１４は、仮想センサを表すボックス（たとえば、１４３１，１４３４、および１４３７）を示しているが、仮想センサは複数の出力を有することができる。たとえば、仮想センサ１４３１および１４３４は、２つの出力を有する単一の仮想センサに組み合わせることができる。仮想センサ１４３１，１４３４および１４３７は、３つの出力を有する単一の仮想センサに組み合わせることができる。
【０２０４】
図１４のＶｅｌセンサ式言語エンジン１４０７の内部は、以下に説明するデータフロープログラミングによって特徴付けることができる。入力として供される異なるタイプのデータのストリームのセットが与えられ、データフロープログラムを介してこれらの入力を出力のストリームに変換することが望まれる場合、本発明は、パターンマッチング動作をデータフローグラフの原理動作として容易にするような態様でデータフローグラフを実装し、データ変換を呼び出す原理メカニズムとしてパターンマッチングを組み込む技術である。
【０２０５】
この種の問題を解決する必要性は、すべての形式のデータフロープログラミングで共通して発生する。それは、エンタープライズデータセンター内およびエンタープライズデータセンター間のデータフローなどの非常に大規模なアーキテクチャ、ならびに埋込まれたデバイスにおけるイベントのフローなどの非常に小規模なアーキテクチャに適用可能である。
【０２０６】
本発明は、データフロープログラミングのすべての領域に適用可能であるが、パターン一致を検出でき、ハンドラ関数を適用できる速度が最も重要であり、実行に費やすストレージおよび計算リソースが限られている場合に最適である。
【０２０７】
いくつかの背景情報がデータフロープログラミングについて以下に示されており、パターン駆動型反応に関する以下の議論の基礎として役立つだろう。データフロープログラミングは、コンピュータプログラムを、フローグラフと呼ばれる有向グラフとしてモデル化し、各外部ノードはプログラムの入力または出力を指定し、各内部ノードは実行されるべき操作を指定する。各ノードに流入するデータは入力をその動作に提供し、その動作の結果はそのノードから流出するデータを提供する。ノードの対間の有向エッジは、一方のノードの出力を他方のノードの入力とする。したがって、データはグラフに入り、さまざまな動作を介してグラフ内を移動し、何らかの有用な態様で、すべて連続的な流れで、変換されて、グラフを出る。
【０２０８】
フローグラフ構造。図１５は、フローグラフの例を示す。データは、３つの入力ノード（ｉｎ１  １５０６、ｉｎ２  １５０９、ｉｎ３  １５１２）を介してグラフに入り、４つの別々の動作ノード（ｏｐ１  １５２２、ｏｐ２  １５２５、ｏｐ３  １５２８、およびｏｐ４  １５３３）で変換され、２つの出力ノード（ｏｕｔ１  １５４６およびｏｕｔ２  １５４８）を介して出る。ｅ１〜ｅ７のエッジは、データが流れることが許される経路を示す。
【０２０９】
入力ノードはインジェクタと呼ばれ、出力ノードはエクストラクタと呼ばれる。これらのノードは、グラフを外部データシステムに接続する役割を果たす。それらは、データを変換することはないが、実現例によっては一時的にデータをバッファリングすることもある。図１５のインジェクタおよびエクストラクタは、反転ハウス形のノードで表されている。
【０２１０】
動作が実行される内部ノードは、トランスデューサと呼ばれる。トランスデューサに到着する各入力に対して、トランスデューサは０個以上の出力を生成することができる。図１５のトランスデューサは、円形のノードで表されている。
【０２１１】
出力を送信するノードはプロデューサと呼ばれ、入力データを受信するノードはコンシューマと呼ばれる。インジェクタは一種のプロデューサであり、エクストラクタは一種のコンシューマである。トランスデューサは、プロデューサおよびコンシューマの両方である。図１６は、この関係を示す。
【０２１２】
図１６は、ノードの種類の階層を示す。インジェクタ１６０８およびトランスデューサ１６１３は、プロデューサ１６１９に入力する。トランスデューサ１６１３およびエクストラクタ１６２２は、コンシューマ１６２５に入力する。プロデューサ１６１９およびコンシューマ１６２５はノード１６３４に入力する。
【０２１３】
各プロデューサには、０個以上の出力エッジが付き得る。各出力エッジは、生成されたデータをプロデューサから運び去る。各コンシューマには、０個以上の入来エッジが付き得る。各入来エッジは、消費されるべきデータをコンシューマに運ぶ。
【０２１４】
それぞれの固有のエッジは、厳密に１つのプロデューサを厳密に１つのコンシューマに接続し、さらに、任意の所与のプロデューサとコンシューマとのペアに対して、多くて１つの固有のエッジが存在し得る。言い換えれば、任意の所与のプロデューサとコンシューマとのペアは、固有のエッジで接続されているか、または接続されない。
【０２１５】
各固有のエッジは、エッジのプロデューサの観点から見ると、生成されたデータを運び去るため、一種の出力エッジである。各固有のエッジは、エッジのコンシューマの観点から見ると、消費されるべきデータを担持するため、一種の入来エッジでもある。
【０２１６】
図１７は、エッジの種類の階層およびエッジのノードに対する濃度を示す。この図は、エッジの種類と、それらのプロデューサおよびコンシューマとの計数論的な関係を示す。プロデューサ１７０８および固有のエッジ１７１４は、出力エッジ１７２０に入力する。固有のエッジ１７１４およびコンシューマ１７２３は、入来エッジ１７２６に入力する。出力エッジ１７２０および入来エッジ１７２６は、エッジ１７３５に入力する。
【０２１７】
トランスダクション。上記のように、インジェクタおよびエクストラクタはそれらのデータを変更せず、データにおけるすべての変更はトランスデューサによって実行される。関数適用のように、トランスダクションは入力値をとり、それらを出力値に変換するが、関数とは異なり、トランスダクションは複数の入力値を取り込んで保持することができ、後で０個以上の出力値を生成することができる。トランスダクションの出力は、バーストとして生成されたとしても、出力ストリームに別々に入る。
【０２１８】
入力データは、１つ以上のプロデューサからトランスデューサに到着する。新たなデータが到着するたびに、トランスデューサは活性化し、つまり、動作する機会が与えられる。選択されるアクションは、新たなデータを破棄すること、それを後のある時間まで内部的にバッファリングすること、または以前のバッファリングされたデータと一緒に新たなデータを使用して１つ以上の新たな出力を生成することであるかもしれない。
【０２１９】
たとえば、図１５のｏｐ１は、入力として（エッジｅ１に沿って）整数からなる単一のストリームを消費し、出力として（エッジｅ５に沿って）整数のストリームを生成するトランスデューサであると想像してもよい。さらに、ｏｐ１は、２つの入力を内部的にバッファリングし、第３の入力の到着で、３つの入力の平均に等しい出力を生成するような態様でプログラムされている、と想像してみよう。
【０２２０】
Ｔｒａｃｅ（１）は、ｏｐ１の周りのフローグラフの部分のアクションの可能な例を示す。入力データは１２：００時に到着し始め、１２：０５までにｏｐ１は３つの入力[12, 16, 5]を見、それらの平均は11である。動作ノードｏｐ１は、それが最終入力を受信したのと同じ瞬間１２：０５にその平均をそれの出力として生成する。このパターンは１２：０６で開始して繰り返し、ｏｐ１は１２：１０で別の出力を生成する、等々。
【０２２１】
【表６】
2019518264.tif 000008
【０２２２】
そのインバウンドエッジを介して到着するその正式な入力に加えて、トランスデューサは非正式な入力をタイムアウトの形で宣言することもできる。タイムアウトは、トランスデューサがそれの活性化と活性化との間において時間切れになることを望む最大時間量である。タイムアウトが満了する前に新たな入力が到着しない場合、トランスデューサはいずれにせよ活性化するが、それがタイムアウトしたことを示す特別な状態でそうする。このようにして、トランスデューサは、データの存在とならんでデータの欠如に対して作用することができる。トランスデューサが活性化するたびに、それは新たなタイムアウトを宣言するオプションを有する。
【０２２３】
ｏｐ１のアルゴリズムを改訂して、それは１０分のタイムアウトを有する、とする。３つの値がその時間に到着しなかった場合、ｏｐ１は何であれそれが有する値の平均を生成する。
【０２２４】
Ｔｒａｃｅ（２）は、新たな時間認識ｏｐ１の周りのフローグラフの部分のアクションの可能な例を示す。入力データは１２：００時に到着し始め、その時点でｏｐ１は１０分のタイムアウトを宣言する。別の入力は２分後の１２：０２に到着するが、タイムアウトが１２：１０に切れる前にそれ以上のデータは到着しない。１２：１０で、ｏｐ１はそれが見た２つの入力の平均を生成し、それ以上のタイムアウトは宣言しない、等々。
【０２２５】
【表７】
2019518264.tif 000009
【０２２６】
サンプリング対トリガ。トランスデューサに２つ以上の入力がある場合、その入力の一部が常にトランスデューサに出力を生成させ、他の入力はトランスデューサに決して出力を生成させないことがある。
【０２２７】
たとえば、図１４のｏｐ４は、２つの整数のストリームを入力として（エッジｅ５およびｅ６に沿って）消費し、ある整数のストリームを出力として（エッジｅ７に沿って）を生成するトランスデューサであると想像してもよい。さらに、入力がｅ６に沿って到着するたびにｏｐ４が入力のコピーを内部的に保存するように、ｏｐ４がプログラムされているとする。このようにして、ｏｐ４は常にｅ６からの最新の値を知るが、ｅ６に沿って値が到着しても、ｏｐ４は何も生成しない。
【０２２８】
さらに、入力がｅ５に沿って到着すると、ｏｐ４はその入力とｅ６からの最新の値との和に等しい出力をｅ７に沿って生成する。Ｔｒａｃｅ（３）は、ｏｐ４周辺のフローグラフの部分のアクションの可能な例を示す。
【０２２９】
【表８】
2019518264.tif 000010
【０２３０】
１２：００時の時点で、ｏｐ４は値２０がｅ６に沿って到着するのを見る。ｏｐ４はこれをｅ６の最新の値としてキャッシュする。１２：０５および１２：１０で、値がｅ５に沿って到着する。いずれの場合も、ｏｐ４は、ｅ５のライブ値とｅ６のキャッシュされた値とを使用して出力を生成する。１２：１５に、ｏｐ４はｅ６から新たな値（３０）をキャッシュし、それを使用して、別の入力がｅ５に沿って到着する１２：２０に出力を生成する。
【０２３１】
この例では、ｏｐ４はｅ６をサンプリングしているが、それはｅ５によってトリガされている。サンプリングは、トランスデューサ内部のデータの蓄積を含む受動的なアクションであり、一方トリガは、新たな、蓄積データを利用して出力を生成するアクションである。
【０２３２】
トランスデューサがそれの入力のすべてをサンプリングし、タイムアウトによってのみトリガされる場合がある。上述のｏｐ１の時間認識バージョンは、そのようなトランスデューサの一例である。
【０２３３】
トランスデューサがインバウンドエッジをまったく有さず、それでいて出力を生成することも可能である。そのようなトランスデューサは単にタイマーであり、タイムアウトでのみトリガする。これは、安定した一連のデータが固定されたスケジュールで生成されることが望まれる一部の適用例で役立ち得る。
【０２３４】
トリガ条件のないトランスデューサは無益であり、誤っている。
スケジューリング。 トランスデューサは、入力を受信するたびに、もしくはタイムアウトが満了すると、またはその両方で、活性化する。活性化ごとに、トランスデューサは０個以上の出力を生成し得る。まだ消費されていない出力を生成したプロデューサはホットである。そうでなければそれはコールドである。
【０２３５】
ホットなプロデューサの出力を処理する手法を選択するのは、グラフエンジン次第である。２つの一般的な、同等に有効な戦略がある。プロデューサ駆動型およびコンシューマ駆動型である。
【０２３６】
プロデューサ駆動型グラフでは、プロデューサはできるだけ早く活性化する。それによって生成された出力はそれの出力エッジに沿って移動し、それのコンシューマでキューに入れられる。これは、プッシュモデルとも呼ばれる。これは、データが準備ができ次第、プロデューサがデータをそれらのコンシューマにプッシュするからである。このモデルでは、プロデューサは最小の時間の間ホットのままである。
【０２３７】
コンシューマ駆動型グラフでは、プロデューサはそれのコンシューマが消費する準備ができたときにのみ活性化する。それが生成する出力は、コンシューマが既にそれらを待っているので、キューに入れられない。これは、コンシューマがそれらのプロデューサからデータをプルするため、プルモデルとも呼ばれる。このモデルでは、プロデューサは無期限にホットなままであってもよい。
【０２３８】
データフローの方向はどちらの戦略でも同じである、つまりプロデューサからコンシューマへ、であることに注意されたい。違いは、データフローを開始するインパルスがプロデューサまたはコンシューマのどちらの側に存在するかである。
【０２３９】
データフロープログラムの実装。ほぼすべてのプログラミング言語でデータフローの概念を実現し得るが、いくつかの言語は他の言語よりも適している。
【０２４０】
データフロープログラムは、ScalaやHaskellなどの関数型言語で記述されることがよくある。そのような言語は、副作用なしに評価されるべき一連の数式としてプログラムをモデル化するからである。
【０２４１】
関数型言語で実装されたグラフでは、各トランスデューサの動作は式で定義され、各ノードのランタイムアクションは単純にそれの式の評価である。副作用が発生しないので、実行モデルが簡素化され、ノードが繰り返しかつ独立して動作することを確実にするのを助ける。グラフの最適化も単純化され、なぜならば、式を結合して簡略化するために使用される代数はグラフノードにも適用できるからである。
【０２４２】
しかしながら、純粋に関数型の言語では、獲得された状態に依存するトランスダクションを実施することは難しいかもしれない。そのような場合、ＪａｖａやＣ＋＋などの命令型言語が望ましいかもしれず、なぜならば、そのような言語はプログラムを一連の命令としてモデル化し、副作用（内部バッファリングなど）は許容されるからである。
【０２４３】
命令型言語で実現されたグラフでは、各トランスデューサの動作は、入力が到着するたびに、もしくはタイムアウトが満了するとき、またはその両方で呼び出されるイベントハンドラ関数で定義される。この関数は、フィットするとみなされる任意の内部的なアクションを自由に取り、出力を生成するか、もしくはタイムアウトを宣言するか、またはその両方であり得る。これにより、実装者に大きな柔軟性が与えられるが、グラフの最適化は非常にはるかにより困難となり、なぜなら、イベントハンドラのアクションについて外部的に判断するのは難しいからである。
【０２４４】
言語にかかわらず、グラフの自動化フレームワーク（グラフエンジン）と、それのノードの仕様と、それのエッジの接続（グラフトポロジ）とは、一般に、コードライブラリを使用して処理される。ライブラリは、典型的には、トランスデューサを構成するクラス、トランスデューサをエッジで接続するメソッド、イベント駆動型システムとしてグラフを実行するメインループなどの抽象化を提供する。言語の柔軟性およびライブラリは、グラフで表現可能なものの限界と、グラフが実行される効率とを定義する。
【０２４５】
パターン駆動型反応。本発明の中心的な概念は、トランスデューサのアクションをパターンマッチングのタスクの周りに編成することである。この議論の目的のために、パターンマッチャー（または単に「マッチャー」と略記する）は、構文規則および時間関連規則のセットを与えられると、データ担持イベントの入来ストリームを規則的なデータ構造に編成し得るアルゴリズムである。このようなアルゴリズムの一例として、時限順方向右端（１）またはＴＦＲ（１）パターンマッチングと呼ばれる手法がある。
【０２４６】
論理プログラミング。パターン宣言は、命令型プログラミングおよび関数型プログラミングの両方とは異なるモデルである、論理プログラミングの一形式である。論理プログラミングでは、１つ以上の自由変数が宣言され、値がそれらにどのように割り当てられるかについての規則が与えられ得る。さらに、１つ以上の従属式が定義され、自由変数を参照する。実行時、自由変数は規則に従って値を取得し、従属式が次いで評価される。
【０２４７】
【表９】
2019518264.tif 000011
【０２４８】
定義（４）において、bは自由変数であり、b + 1はbを含む従属式である。値をbに代入する規則は単純であり、bは値をリスト[ 1, 2, 3 ]から順に取る。実行後、aはしたがって[ 2, 3, 4 ]に等しい。
【０２４９】
パターンルール。パターンルールは、入力のストリームで期待されるパターンを宣言する論理式の一形式である。それはラムダ式に似ているが、それを代わりに小文字のpi (π)とともに導入することで、それをそのようなものから区別する。
【０２５０】
【表１０】
2019518264.tif 000012
【０２５１】
（５）において、パターンp1は、３つの自由変数a, b, およびcとしてその順で宣言される。入力ストリームに適用すると、各自由変数は入力からの単一の値にバインドし、つまり、各自由変数は、パターンが適用されるストリームと同じ型である。パターンを適用した結果は、従属式によって矢印の右側に与えられ、この場合、３つの入力の平均に等しくなる。このパターンは、事実上（１）に示すトランスダクションである。
【０２５２】
関数が値に適用されるであろう態様でp1をストリームに適用し得る。たとえば、xが整数のストリームである場合、p1(x)は、３でグループ化して平均化したｘにおける値からなる整数の新たなストリームになるであろう。p1(p1(x))は平均の平均となるであろう、等々。
【０２５３】
【表１１】
2019518264.tif 000013
【０２５４】
（６）では、（５）を少し短くし、より一般的であるように改訂する。３つの入力(a, b, c)を別々にリストするのではなく、それらを３つの要素の長さである単一の入力dとして収集する。dは、単に１つのかわりに、入力ストリームからの３つの値にマッチする。ストリームの型がTの場合、dの型はlist(T)になる。リストの要素を合計する組み込み関数sumを使用して平均値を計算する。p2はp1と機能的に同一である。
【０２５５】
【表１２】
2019518264.tif 000014
【０２５６】
（７）では、（６）を改訂して可変長一致の概念をタイムアウトとともに導入する。今度はdの長さが間隔1..3として与えられ、これは入力からの１つの値と３つの値との間でマッチすることを意味する。dの型はlist(T)のままである。それが１つの入力にしかマッチしない場合は、それは１つの要素のリストになる。マッチャーは最大３つの値が到着するまで最大１０分間待機するが、時間切れになると１つまたは２つの値を受け入れる。平均値が、ここで、リスト内の要素の数を返す追加の組み込み関数lenを使用して計算される。このパターンは、事実上、（２）に示すトランスダクションである。
【０２５７】
【表１３】
2019518264.tif 000015
【０２５８】
（８）では、（７）を改訂して、オープンエンド一致の概念をタイムアウトとともに導入する。dの長さには上限がない。それは、少なくとも１つの値とマッチすることになるか、または、１０分のウィンドウ内でできるだけ多くそうすることができる。パターンはタイムアウトによってのみトリガされる。
【０２５９】
【表１４】
2019518264.tif 000016
【０２６０】
（９）において、（８）を改訂して、オープンエンド一致の概念をタイムアウトなしで導入する。（８）にあるように、dの長さには上限はないが、今度は、パターンをトリガするものはなにもない。それ自体で適用されると、このパターンは誤ったものになるであろう。それは、後のセクションのトピックである結合のコンテキストでのみ意味がある。
【０２６１】
フローグラフに関しては、パターンルールの各適用は、トランスデューサを単一の入力で定義する。（パターンにタイムアウトがある場合は、トランスデューサもタイムアウトを有する。）トランスデューサにはパターンルールから導出されるマッチャーの定義が含まれている。入力値が到着すると、その値はマッチャーに渡される。マッチャーが一致を生成すると、その一致は引数として使用されて従属式を評価し、次いでその結果はトランスデューサによって生成される。
【０２６２】
まだ満たされていないパターンは、コールドトランスデューサをもたらし、完全に満足されたパターンは、ホットトランスデューサをもたらす。しかしながら、可変長のパターンが部分的に満たされている場合、トランスデューサを記述するために新たな状態、すなわちウォーム状態が必要である。ウォームトランスデューサは出力を生成する準備ができているが、出力を生成する必要はない。これは、準備ができており、できるだけ早く生成しなければならないホットトランスデューサとは対照的である。
【０２６３】
【表１５】
2019518264.tif 000017
【０２６４】
（１０）で定義されたp6が、トランスデューサによって表される入力ストリームに適用されるのを考える。入力が到着する前、トランスデューサはコールドである。単一の入力が到着した後、そのパターンが部分的に満足されるので、トランスデューサはウォームになる。それは最大でさらに２つの入力を受け入れること、またはそれが既に有するものをマッチすることができる。さらに２つの入力が到着すると、トランスデューサはホットになる。先に出力を生成しなければ、それ以上の入力を受け付けることはできない。
【０２６５】
トランスデューサ準備のための２状態（ホット、コールド）モデルの代わりの３状態（ホット、ウォーム、コールド）は本発明の重要な特徴の１つである。それは、パターン駆動型反応を直接促進する。これがなければ、可変長パターンは使用できないであろう。
【０２６６】
結合。結合とは、１つの出力ストリームを生成するために一緒に評価される２つ以上の入力ストリームを結合することである。たとえば、冷蔵庫に２つのセンサがあり、１つはドア用であり他方は温度用である場合、ドアが閉じられたときに平均温度を生成するよう２つのストリームを結合するかもしれない。
【０２６７】
【表１６】
2019518264.tif 000018
【０２６８】
【表１７】
2019518264.tif 000019
【０２６９】
どちらかの入力が変化すると、出力が生成されることに注意されたい。つまり、評価は、それの入力における変化によってトリガされている。
【０２７０】
【表１８】
2019518264.tif 000020
【０２７１】
（１２）では、追加のトリガ条件を追加する。これは３分のタイムアウトである。次の表は、この新たなトリガ条件に照らしてx, y,およびz2の可能な値を与える。
【０２７２】
【表１９】
2019518264.tif 000021
【０２７３】
タイムアウト間隔は各値が生成された後に再開され、それは、その値がタイムアウトによって生成されるかまたは入力における変化によって生成されるかどうかにかかわらないことに注意されたい。トリガの目的で、タイムアウトは別の入力として扱われている。
【０２７４】
【表２０】
2019518264.tif 000022
【０２７５】
（１３）では、（９）で定義したオープンエンドのパターンp5を含む結合を示す。（p5は上限なしで１つ以上の値を収集することを想起されたい。）次の表は、この新たなトリガ条件に照らしてx, y,およびz3の可能な値を示す。
【０２７６】
【表２１】
2019518264.tif 000023
【０２７７】
オープンエンドのパターンp5は単独では何もトリガできないため、出力の生成はxによっては決してトリガされないことに注意されたい。しかしながら、yの変化は生産を引き起こし、その過程で、少なくとも１つの値を収集したと仮定して、p5を閉じさせることができる。12:00から12:08まで、aはxから値を収集している。12:08で、yにおける変化により、収集は閉じられ、出力が生成される。12:10では、出力は生成されず、なぜならば、yに変化があるものの、収集aは空であるからである。しかしながら、その後の最初の機会(12:13)において、aのための値が与えられており、別の出力が生成される、等々。
【０２７８】
（１１）、（１２）、（１３）において、a in x, b in y, a in p5(x)およびevery 2(min)という式は、トリガ式（triggering expression）の例である。それらは、従属式が評価される条件を定義する。
【０２７９】
トリガ式の値は、ホット、ウォームまたはコールドである。入力ストリームに結び付けられたトリガ式の場合、その値はストリームのプロデューサの準備度が反映されている。クロックに結び付けられたトリガ式の場合、タイムアウトが満了すると値はホットになり、それ以外の場合はコールドになる。時間ベースのトリガ式は決してウォームにならない。）
２つのトリガ式を論理積演算子と組み合わせて、新たなトリガ式を生成することができる。組み合わされたトリガ式の新たな値は、以下の真理値表で定義されているように、それの左辺および右辺のオペランドによって決まる。
【０２８０】
【表２２】
2019518264.tif 000024
【０２８１】
２つのトリガ式を論理積演算子と組み合わせて、新たなトリガ式を生成することもできる。組み合わされたトリガ式の新たな値は、以下の真理値表で提示されているように、それの左辺および右辺のオペランドによって決まる。
【０２８２】
【表２３】
2019518264.tif 000025
【０２８３】
フローグラフに関しては、パターンルールの各適用は、トランスデューサを２つ以上の入力で定義する。（パターンが結合を有し、タイムアウトを有する場合は、トランスデューサもタイムアウトを有する。）トランスデューサには、従属式およびトリガ式の定義が含まれている。
【０２８４】
結合のトリガ式がホットになると、まだ閉じられていないすべての入力パターンが閉じられ、従属式が評価される。
【０２８５】
結合のトリガ式がウォームになると、トランスデューサはメッセージをそれのプロデューサの各々に送り、プロデューサが加速することを要求する。
【０２８６】
加速されたトランスデューサはできるだけ早くそのマッチを閉じる。すでにウォームである場合は、ホットになる。コールドである場合は、考えられ得る中間のウォーム状態をバイパスして、そのもっとも早い機会にホットになる。出力を生成するとすぐに、トランスデューサは自動的に減速し、再び加速されるまで通常の挙動を再開する。
【０２８７】
加速されたインジェクタは、可能ではあるが、加速されないインジェクタとなんら異なることなく振舞う。それは、次に値を注入するときに減速する。
【０２８８】
加速されたプロデューサによって生成された出力は、加速を要求したものだけでなく、それのすべてのコンシューマに送信されることに注意されたい。これにより、すべてのオブザーバにわたってデータフローの一貫性のあるビューが維持される。
【０２８９】
コンシューマがプロデューサを加速する能力は、本発明の重要な特徴の１つである。それはパターン駆動型反応を直接促進する。これがなければ、オープンエンドのパターンは使用できないであろう。
【０２９０】
フィルタリング。結合がトリガされ、その従属式が評価された後、それはまだ出力を生成しなくてもよい。オプションのフィルタを使用すると、望ましくない結果が抑制され得る。
【０２９１】
【表２４】
2019518264.tif 000026
【０２９２】
（１４）ではフィルタの例を示す。 キーワードifの後の式は、出力として生成されるべき従属式の値に対して真と評価されなければならない。
【０２９３】
フィルタの概念は、フローグラフの構造に変化をもたらさない。それは、トランスデューサがトリガされた後にトランスデューサによって行われる別途のステップにすぎない。しかしながら、パターンマッチングなしでは、トランスデューサのすべての活性化は、これのような式の評価を必要とするであろうと考えられ、なぜならば活性化（入力の到着）とトリガ（評価についての前提条件の満足）との間に区別がないであろうからであることは注目に値する。
【０２９４】
式の評価は、パターンマッチングよりはるかに効率が悪いことがよくある。充分に設計されたパターンマッチングアルゴリズムでは、マッチごとに１回だけ各入力が考慮されるが、式は、条件が満たされるまで何度も各入力を再評価する必要があるかもしれない。純粋に式ベースのトランスデューサは、したがって、それが実際に生成を行なうよりも、生成するかどうかを決定するのに、より多くの時間を費やし得る。
【０２９５】
活性化とトリガとの間の区別は、本発明の重要な特徴の１つである。それが可能にするパフォーマンスの向上は、パターン駆動型アプローチの主な利点の１つである。
【０２９６】
サンプリング。先に述べたように、すべての誤りのないトランスデューサには何らかの形式のトリガを有さなければならず、パターン駆動型および結合トランスデューサはそれらのトリガを宣言的に定義する。また、サンプリングを使用するトランスデューサを宣言することも可能である。
【０２９７】
【表２５】
2019518264.tif 000027
【０２９８】
（１５）の目的のため、xおよびyは各々整数のストリームであると仮定する。ここで定義されるトランスデューサは、xによってトリガされるが、yだけをサンプリングする。これは、xはトリガ式に現れるが、yは従属式にのみに現れるためである。yは整数のストリームなので、その型はsequence(int)であり、接頭演算子latestは、式が評価される時点でこのシーケンスの最前端の値を参照する。
【０２９９】
フローグラフの観点からは、トランスデューサは２つの入力を有し、１つはxから、もう１つはyからである。しかしながら、入力がyから到着すると、値はトランスデューサによって単にキャッシュされる。xからの入力の到着は、従属式の評価をトリガし、それはyのキャッシュされた値を使用することになる。
【０３００】
トランスデューサをトリガする入力とトランスデューサが単にサンプリングする入力との間を宣言的に区別する能力は、本発明の重要な特徴の１つである。これは、トランスデューサが、副作用を伴うサンプルキャッシングのような動作を行っている場合でも、トランスデューサの定義を純粋に宣言的なままにすることができる。
【０３０１】
関数型−論理最適化。我々は、これまで、（パターンマッチングおよび結合の）論理プログラミングと、（従属式およびフィルタ式（filtering expression）の）関数型プログラミングとの組み合わせは、純粋に宣言的な方法で大きな範囲のトランスダクションを表現することができることを見てきた。関数型−論理プログラミングのコンビネーションスタイルには、関数型プログラミングの利点の多くがありながら、その制約や複雑さの多くを緩和する。それは、命令型プログラミングに頼ることなく、大抵の現実的な意図を表現することができる。
【０３０２】
関数型−論理プログラムにおける関数式は、関数型プログラムを最適化し得るのと同じ方法で最適化することができる。この種の最適化は、プロデューサとコンシューマとの長い連鎖を単一のトランスデューサに集約して、グラフを同時に、より小さく、より速く実行することができる。
【０３０３】
さらに、規則として表現される論理パターンを統合された状態機械に組み合せることもできる。この最適化の厳密な性質は、使用されているマッチングアルゴリズムに依存する。たとえば、ＴＦＲ（１）の場合、単一のソースに適用されるすべてのパターンを組み合わせて１つの状態機械を形成して、ストリームへのすべての入力が１回だけ評価されるようにすることを保証することができる。
【０３０４】
関数型−論理宣言が有する、データフロープログラミングが最適化のために幅広い範囲の機会を保持しながら用いられる有用なプログラムの大部分を表現する能力は、本発明の重要な特徴の１つである。それは、簡潔に宣言されたプログラムが、より小さく、より速いフローグラフをもたらすことを可能にする。
【０３０５】
ある実装形態では、システムは以下を備える：各々がセンサに接続され、センサからデータ（例：ストリームデータ）を受信する、ある数のエージェントと、エージェントに接続されるデータバスを含み、一連の相互接続されたトランスダクションを形成することによって入力のストリームを出力のストリームに変換するデータ処理コンポーネントとを備える。各トランスダクションは、参照として外部データソースまたはトランスデューサのうちの少なくとも１つを各々が与えられる１つ以上の入力と、参照として外部データシンクまたはトランスデューサのうちのいずれか少なくとも１つに各々が与えられる１つ以上の出力と、各入力について、各入力に適用されて、生の入力をフィルタリング、収集、および整理して、より有用な、部分的に処理された形式にし、誤った入力を除去するパターンとを含み得る。
【０３０６】
少なくとも１つのエージェントは以下を含む：入力キューは、コンピュータメモリにおいて第１のメモリ位置を有し、入力キューは、処理されるべきトークンの先入れ先出しシーケンスを第１のメモリ位置に格納し、キューにおける各トークンに関連付けられるタイムスタンプは、関連付けられるトークンが入力キューに入った時間を示し、トークンはネットワークを介して入力キューによって受信される。ドライバコンポーネントは、入力キューに接続され、バックトラッキングなしで入力キューにおけるトークンを処理し、１つ以上の所定の入力パターンにマッチする、トークンのシーケンスにおけるパターンを識別し、マッチした所定の入力パターンを識別すると、出力イベント出力を生成する。出力キューは、ドライバコンポーネントに接続され、コンピュータメモリにおいて第２のメモリ位置を含み、出力キューは、第２のメモリ位置に、ドライバコンポーネントによって生成された出力イベントの先入れ先出しシーケンスを格納する。状態表コンポーネントはドライバコンポーネントに接続され、状態表コンポーネントは所定の入力パターンを状態表フォーマットで格納する。状態スタックコンポーネントは、ドライバコンポーネントに接続され、コンピュータメモリにおいて第３のメモリ位置を有し、状態スタックコンポーネントは第３のメモリ位置にフレームの後入れ先出しのシーケンシャルストレージを格納する。フレームには、変換状態番号、記号、およびデッドラインが含まれる。
【０３０７】
各トランスダクションは、フィルタ式をいつ評価するかを判断するために使用されるトリガ式を含み得る。トリガ式は、ノードのツリーとして定義され、各ノードは、入力のうちの１つに対する参照と、時間の単位で時間の間隔として与えられるタイムアウトと、少なくとも２つの子を含み、各子は別のトリガ式ノードによって表わされる、二項連言演算子と、少なくとも２つの子を含み、各子は別のトリガ式ノードによって表わされる、二項選言演算子とのうちの少なくとも１つである。
【０３０８】
各トランスダクションはフィルタ式を含み得、フィルタ式はマッチした入力のドメインで指定され、フィルタ式はトランスダクションがいつ出力を生成するかを決定するブール結果をもたらす。入力パターンは、ゼロ長さまたは無制限（もしくは無限に大きい）長さを含む可変長の入力シーケンスとマッチすることができる。
【０３０９】
入力パターンを入力シーケンスとマッチングしようと試みた結果は、完全性の少なくとも３つの異なる状態または度合いを有することができる。入力パターンを入力シーケンスとマッチングしようと試みた結果は、少なくとも３つの異なる状態を有することができる。３つの異なる状態は、入力パターンの最小入力にマッチするまで、マッチングの試みは第１の状態にあることと、最小入力にマッチした後、最大入力にマッチするまで、マッチングの試みは第２の状態にあることと、最大入力にマッチした後、マッチングの試みは第３の状態にあることとを含むことができる。第１の状態は「コールド」状態と呼ぶことができる。第２の状態は「ウォーム」状態と呼ぶことができる。そして、第３の状態は「ホット」状態と呼ばれる。
【０３１０】
データフローはセンサからエージェントにプッシュベースであることができる。エージェントの入力のすべてが少なくとも第２の状態にあるとき、およびセンサの入力のうちの１つ以上が第３の状態にあるとき、そしてトリガ式の結果が前記第２の状態にあるとき、データフローは、エージェントによってセンサからプルベースに変化し得る。エージェントは、第２の状態にあるそれのセンサを加速して、各そのようなセンサに、それのパターンが完全にマッチしたと考えさせ、したがって各そのようなセンサを第３の状態になるようにし、それの出力を生成させる。これは、エージェントに、それのセンサからデータを効果的にプルさせる。
【０３１１】
限定的に長いかまたはオープンエンドのパターンがトランスダクションで有用に使用されることを可能にされる。センサの１つ以上は、物性をデジタル量に変換するハードウェアデバイスであることができる。デジタル量はストリーム化される。
【０３１２】
別の実装形態では、方法は以下を備える：ある数のエージェントおよびセンサを相互接続することを備え、エージェントはセンサに接続され、センサからデータのストリームを受信し、方法はさらに、センサからの入力のストリームを、一連の相互接続されたトランスダクションを介して、出力のストリームに変換することを備える。各トランスダクションは、参照として外部データソースまたはトランスデューサのいずれかに各々が与えられる１つ以上の入力と、参照として外部データシンクまたはトランスデューサのいずれかに各々が与えられる１つ以上の出力と、各入力について、各入力に適用されて、生の入力をフィルタリング、収集、および整理して、より有用な、部分的に処理された、または一致した形式にし、誤った入力を除去するパターンと、フィルタ式をいつ評価するかを判断するために使用され、ノードのツリーとして定義されるトリガ式とを含む。
【０３１３】
各ノードは、入力のうちの１つに対する参照、何らかの便利な時間の単位で特徴づけられる時間の間隔として与えられるタイムアウト、２つの子を含み、各子は別のトリガ式ノードである、二項連言演算子、または、２つの子を含み、各子は別のトリガ式ノードである、二項選言演算子、のうちの少なくとも１つである。マッチした入力のドメインで定義され、トランスダクションがいつ出力を生成するかを決定するブール結果をもたらすフィルタ式が、あり得る。マッチした入力のドメインで定義され、トランスダクションの出力を生成する型の任意の組み合わせの結果をもたらす１つ以上の式が、あり得る。
【０３１４】
入力パターンは、ゼロ長さまたは無制限長さを含む可変長の入力シーケンスとマッチすることができ、それの最小入力がマッチするまでは、コールド状態と考えられ、それの最小入力がマッチした後、それの最大入力がマッチするまでは、ウォーム状態と考えられ、それの最大入力がマッチした後は、ホット状態と考えられる。トランスデューサのマッチングの準備の完全性モデルは、２つ以下の異なる度合いではなく、少なくとも３つの異なる度合いによって特徴付けられる。３つの度合いの完全性モデルは、可変長パターンの処理を可能にするパターン駆動型反応を直接容易にする。
【０３１５】
プロデューサからコンシューマへのデータフローは、エージェントの入力のすべてが少なくともウォーム状態にあるとき、およびセンサの入力の１つ以上がホット状態にあるとき、そしてトリガ式の結果がウォーム状態にあるときを除き、プッシュベースである。そのとき、エージェントはそれのウォーム状態のセンサを加速して、各そのようなセンサに、それのパターンが完全にマッチしたと考えさせ、したがって各そのようなセンサをホット状態になるようにし、それの出力を生成させてもよい。これは、センサに、それが接続されている他のプロデューサデータを効果的にプルさせることができる。これは、限定的に長いかまたはオープンエンドのパターンがトランスダクションで有用に使用されることを可能にする。
【０３１６】
本発明のこの記載は、例示および説明のために提示されたものである。それは、網羅的であることを意図するものでもなく、本発明を記載された正確な形態に限定することも意図されておらず、上記教示に照らして多くの修正および変形が可能である。実施形態は、本発明の原理およびその実際の適用を最もよく説明するために選択され、記載された。この記載により、当業者は、本発明を、さまざまな実施形態において、および特定の用途に適したさまざまな修正を加えて、最も有効に活用し実施することが可能になる。本発明の範囲は、特許請求の範囲によって規定される。
【図１】
2019518264.tif 000028
【図２】
2019518264.tif 000029
【図３】
2019518264.tif 000030
【図４】
2019518264.tif 000031
【図５】
2019518264.tif 000032
【図６】
2019518264.tif 000033
【図７】
2019518264.tif 000034
【図８】
2019518264.tif 000035
【図９】
2019518264.tif 000036
【図１０】
2019518264.tif 000037
【図１１】
2019518264.tif 000038
【図１２】
2019518264.tif 000039
【図１３】
2019518264.tif 000040
【図１４】
2019518264.tif 000041
【図１５】
2019518264.tif 000042
【図１６】
2019518264.tif 000043
【図１７】
2019518264.tif 000044
【国際調査報告】
2019518264.tif 000045
2019518264.tif 000046