H＃、独自のプログラミング言語を作成する

良い一日。
この記事では、Visual Studio 2010の主要な革新の1つ、つまり関数型プログラミング言語F＃を確認します。

F＃の構文と可能性を、私たちが発明したプログラミング言語用に独自のインタープリターを作成する例を使用して検討します（結局、例について何かを話すことは常に興味深いです）。

解決しようとしているタスク、つまりプログラミング言語の構文について説明します。これは非常に単純で、見たいものです。

function Summ(a,b,c)
{
val d = a+b+c;
print d;
return d;
}

function MyEvaluations(a,b,c)
{
val in = Summ(a,b,1);
val out = Summ(b,c,1);
val d = in*out;
return d;
}

function Program()
{
print(MyEvaluations(1,2,3));
}


そのため、パラメーターの受け渡しと戻り値、印刷、算術演算、ローカル変数を持つ関数をサポートしています。
これの実装を開始します。このため、ここから追加のF＃Power Packをインストールする必要があります

語彙

次に、F＃Parsed Language Starterオンラインテンプレートから新しいF＃プロジェクトを作成し、lexer.fslを除くすべてのファイルをクリアします。
このファイルの内容を処理するために、まず言語を骨ごとに分析しましょう。 「トークン」という言葉は、プログラミング言語を構成する最小限のレンガを意味します。
トークンには、キーワード、ブラケット、コンマ、名前、一般に、プログラムのソースコードを構成するすべてのものが含まれます。 トークンのレベルでは、関数や他の論理ユニットはありません。

lexer.fslファイルを開く
F＃では、キーワードモジュールは名前空間に類似しており、usingキーワードはオープンキーワードです。したがって、最初に記述することは、作業領域を決定することです。

{
module Lexer
open System
open Parser
open Microsoft.FSharp.Text.Lexing

let lexeme lexbuf =
LexBuffer<char>.LexemeString lexbuf
}
let digit = [ '0' - '9' ]
let whitespace = [ ' ' '\t' ]
let newline = ( '\n' | '\r' '\n' )
let symbol = [ 'a' - 'z''A' - 'Z' ]

F＃の変数はletキーワードを使用して宣言されます。また、ここで正規表現を使用できます。
そのため、行の下のすべてのコードを削除します

rule tokenize = parse

これはサービスマーカーであり、言語の説明が下に表示されることを示し、次のコードを挿入します。

| whitespace { tokenize lexbuf }
| newline { tokenize lexbuf }

// Operators
| "+" { PLUS }
| "-" { MINUS }
| "*" { MULTIPLE }
| "/" { DIVIDE }
| "=" { EQUALS }

// Misc
| "(" { LPAREN }
| ")" { RPAREN }
| "," { COMMA }
| ";" { ENDOFLINE }
| "{" { BEGIN }
| "}" { END }

// Keywords
| "function" { FUNCTIONKW }
| "return" { RETURN }
| "var" { VARIABLE }


このファイルは追加のPowerPackライブラリツールによって処理されるため、このファイル自体のF＃コードは中括弧の最初のブロックに囲まれています。
これが最も簡単な部分です。ここでは、言語に存在する文字列定数または正規表現を記述するだけで、算術演算子、角かっこ、3つのキーワード、コンマ、セミコロンのいくつかがあります。
次に、正規表現を使用して、コードから変数/関数の数と名前を「引き出す」ようにインタープリターをトレーニングします。 実際、この段階で、プレーンテキストコードを次のようなオブジェクトのシーケンスに変換しました。

FUNCTIONKEYWORD NAME LPAREN NAME COMMA NAME COMMA NAME RPAREN
BEGIN
VARIABLE NAME EQUALS NAME PLUS NAME PLUS NAME ENDOFLINE
…..


各オブジェクトには独自のタイプがあり、上記の例で示されています。
ただし、DECIMALおよびNAMEオブジェクトにも値が必要です。
これを行うには、次の行を記述します。

| digit+( '.' digit+)? { DECIMAL(Double.Parse(lexeme lexbuf)) }
| symbol+ { VARNAME(String.Copy(lexeme lexbuf)) }

| eof { EOF }

これはコンストラクター呼び出しとして解釈できます。 中括弧で囲まれているのは、データ型だけです。 処理後、プログラムテキストはこれらのタイプのオブジェクトのシーケンスになります。
eof-解析されたテキストの終わりを知らせるサービストークン

解析

データ型がどこから来たのか、そしてNAMEが文字列コンテンツを持ち、DECIMALが数値である理由を少し明確にするために、Parser.fsyファイルを開き、次のコードを貼り付けます。

%{
open ParserLibrary
open System
%}

%start start

%token <Double> DECIMAL
%token PLUS MINUS MULTIPLE DIVIDE
%token LPAREN RPAREN
%token FUNCTIONKW RETURN VARIABLE
%token BEGIN END
%token EQUALS
%token <String> VARNAME
%token ENDOFLINE
%token COMMA
%token EOF
%type <WholeProgram> start

%%


ここにすべてのデータ型が示されています。型に値が必要な場合、この値の型は山括弧で囲まれています。
開始は、いわゆる「文法公理」です。これは、コードを解釈するときに「収集」しようとするものです。

文法は次の形式で書かれています。

: | | | … | …

最初の行は次のようになります。

start: | WholeProgram

これは、分析の目標が「プログラム全体」を取得することであることを示唆しています
よく見ると「プログラム全体」は関数のリストにすぎません
したがって、この事実を書きます。

WholeProgram:
| FunctionDescription
| WholeProgram FunctionDescription

この記録形式でリストを形成するというかなり珍しい形式に注目する価値があります。実際、各要素の「コンポーネント」の数は固定する必要があります。私たちの言語で可能な機能の数を制限しないために、このようなトリックを選びます。 システムが最初の関数を見つけると-それからWholeProgramオブジェクトを作成し、2番目の関数を見ると-隣にWholeProgram（最初の関数から）とFunctionDescription（2番目の関数）があり、システムはこれらのオブジェクトの両方を新しいWholeProgramに折りたたみ、制限を削除しますプログラムテキスト内の関数の総数。
文法を説明すると、次の図が得られます。

関数が何であるかを記述します：

FunctionDescription:
| FunctionKeyWord FunctionTitle Begin End
| FunctionKeyWord FunctionTitle Begin OperatorsList End

表現の2番目のバージョンのみに制限することもできますが、この場合、コードからわかるように、空の関数はインタープリターでエラーになります。この関数は、キーワード、見出し、中括弧、および場合によっては関数内の演算子のセットで構成されます-その本体
関数ヘッダーは、その名前、括弧、および場合によってはパラメーターのリストで構成されます。

FunctionTitle:
| VarName LParen RParen //
| VarName LParen VarName RParen // . ,
| VarName LParen VarName AdditionParametersList RParen //

AdditionParametersListおよびOperatorsListオブジェクトはリストであるため、WholeProgramと同様に定義されます。

OperatorsList:
| Operator
| OperatorsList Operator

AdditionParametersList:
| Comma VarName
| AdditionParametersList Comma VarName

演算子は、関数の本体内のプログラムの1行です;言語には2つのオプションがあります。

Operator:
| VaribaleKeyWord VarName Equals Expression EndOfLine
| ReturnKeyWord Expression EndOfLine

たとえば、次の行に対応します。

val d = in*out;
return d;

最初に、乗算と除算が加算と減算よりも優先順位の高い演算であることを考慮して、4つの算術演算を定義しました。

Expression:
| Expression PLUS HighExpression
| Expression MINUS HighExpression
| HighExpression // "Operator"' Expresson, "" .
HighExpression:
| HighExpression MULTIPLY Operand
| HighExpression DIVIDE Operand
| Operand // , - .

この分離により、式2 + 2 * 2をExpression Plus HighExpressionとして解析し、HighExpressionを別のサブツリーに展開できます：Expression Plus（HighExpression MULTIPLY Operand）。操作の優先度を正しく処理します。
下位レベルでは、オペランドは、数値、既存の変数の名前、関数の名前、または括弧内の式（必要な場合）のいずれかです。

Operand:
| DECIMAL
| VarName
| FunctionTitle
| LParen Expression RParen // Expression , .

F＃（現在は純粋な形式）に戻り、パターンマッチングを使用したコンストラクターなどの可能性を考えてみましょう。つまり、使用したデータ型を説明します。

namespace ParserLibrary
open System

type Operator =
| VarOperator of string * Expression
| ReturnOperator of Expression

and Operand =
| DECIMALOP of Double
| SUBEXPROP of Expression
| VARNAMEOP of String
| FUNCOP of FunctionTitle

and HighExpression =
| MULTIPLY of HighExpression * Operand
| DIVIDEOP of HighExpression * Operand
| VAR of Operand

and Expression =
| SUMM of Expression * HighExpression
| SUB of Expression * HighExpression
| HighExpression of HighExpression

and FunctionTitle = String * List<String>
and FunctionDescription = FunctionTitle * OperatorsList
and OperatorsList = List<Operator>
and AdditionParamsList = List<String>
and WholeProgram = List<FunctionDescription>

実際、9つのオブジェクトを宣言しました。各オブジェクトには、異なるパラメーターを持つ複数の名前付きコンストラクターがあります（実際、このようなコンストラクターのセットはC ++のユニオンに似ています）
このコンテキストでのアスタリスク「*」は乗算ではなく、パラメータ区切り文字、つまり タイプOperatorの VarOperatorという名前のコンストラクターは、文字列（string）と式（expression）を受け取ります
インタプリタを作成する最初の部分を完了するために必要なことは、これらのデータ型をParser.fsyファイルに接続することです。このため、各条件の横にある中括弧で対応するコンストラクタを記述します
次のようになります。

start: WholeProgram { $1 }

WholeProgram:
| FunctionDescription { $1 :: [] }
| WholeProgram FunctionDescription { $1 @ ($2 :: []) }

FunctionTitle:
| VARNAME LPAREN RPAREN { $1, [] }
| VARNAME LPAREN VARNAME RPAREN { $1, $3 :: [] }
| VARNAME LPAREN VARNAME AdditionParamsList RPAREN { $1, $3 :: $4 }

AdditionParamsList:
| COMMA VARNAME { $2 :: [] }
| AdditionParamsList COMMA VARNAME { $1 @ ($3 :: []) }

OperatorsList:
| Operator { $1 :: [] }
| OperatorsList Operator { $1 @ ($2 :: []) }

FunctionDescription:
| FUNCTIONKW FunctionTitle BEGIN END { $2, [] }
| FUNCTIONKW FunctionTitle BEGIN OperatorsList END { $2, $4 }

Operator:
| VARIABLE VARNAME EQUALS Expression ENDOFLINE { VarOperator($2, $4) }
| RETURN Expression ENDOFLINE { ReturnOperator($2) }

Expression:
| Expression PLUS HighExpression { SUMM($1, $3) }
| Expression MINUS HighExpression { SUB($1, $3) }
| HighExpression { HighExpression $1 }

HighExpression:
| HighExpression MULTIPLE Operand { MULTIPLY($1, $3) }
| HighExpression DIVIDE Operand { DIVIDEOP($1, $3) }
| Operand { VAR $1 }

Operand:
| DECIMAL { DECIMALOP($1) }
| VARNAME { VARNAMEOP($1) }
| FunctionTitle { FUNCOP($1) }
| LPAREN Expression RPAREN { SUBEXPROP($2) }

$ 1、$ 2など 条件内の変数の数です
このコードを例として使用して、F＃のもう1つの優れた機能であるリストの操作を紹介します。
式A :: Bは、要素Aを追加したリストBに基づいて新しいリストを作成して返すことを意味します
[]-空のリスト
また、コードでリストを直接または範囲から指定することもできます。例：
[1,2,3,4,5]または[1..5]
この場合、100 :: [1..5]は次のようなリストを返します：[100,1,2,3,4,5]
@演算子-2つの既存のリストの和集合から新しいリストを作成します。
例：[1..5] @ [6..10]は[1..10]を返します

テンプレートによる選択の場合-任意のタプル（FunctionDescription、OperatorsListなど）と同義である同じ型に対して、名前付きコンストラクターを指定することに注意してください-宣言した順序でパラメーターをリストするだけですタプル。
したがって、これがF＃がプレーンテキストから解析ツリーを作成するために必要なすべてです。2番目の部分は解釈です。
Program.fsファイルを開き、使用する名前空間に対して書き込みを開きます。

open System
open Microsoft.FSharp.Text.Lexing
open System.Collections.Generic;
open ParserLibrary
open Lexer
open Parser


解釈

さらに、解釈のために、関数のリスト（または、より良い辞書）、各関数の名前付きスタック（変数名の競合がないように）、および現在実行されている関数の名前が必要です。
これを行うには、すでにおなじみのキーワードletを使用して変数を宣言します。

let stack = Dictionary<String, Dictionary<String,Double>>()
let functionsList = Dictionary<String, FunctionDescription>()
let mutable currentFunctionName = "Program" ;


古典的な関数型プログラミングでは、すべてのオブジェクトは不変です。これは、リストを操作する例で見ることができます。リストにアイテムを追加する代わりに、既存のものに基づいて新しいオブジェクトを作成します。 これにより、プログラムをシームレスに並列化できます。 複雑な同期を記述する必要はありません。
F＃は関数型言語であり、.NETライブラリ全体を完全にサポートしているため、可変オブジェクトを操作できます。 この場合、データの完全なコピーは行われず、オブジェクトへの参照のみがコピーされます。これにより、必要に応じて書き込み時のコピーの一種であるデータを美しく並列化する機能を損なうことなく、速度の妥協を達成できます。

だから、解釈に入りましょう：
式を解析することから始めましょう
テンプレートによる選択で関数を宣言し、rec-キーワード、EvaluateExpression-名前、expression-パラメーターを許可します。
型を宣言するとき、テンプレートによる選択でコンストラクタを作成したとき、関数を実行するブランチを選択するときに同じテンプレートを使用することを思い出してください。 例：渡されたパラメーター式がSUMM（式、highExpression）コンストラクターを使用して作成された場合、追加ブランチなどを実行します。
この関数は、以前に作成されたコンストラクターを実際に繰り返し、それぞれに特定のアクションを割り当てることに気付くかもしれません

let rec evaluateExpression expression =
match expression with
| SUMM (expr, hexpr) -> (evaluateExpression expr) + (evaluateHighExpression hexpr)
| SUB (expr, hexpr) -> (evaluateExpression expr) - (evaluateHighExpression hexpr)
| HighExpression hexpr -> evaluateHighExpression hexpr

and evaluateHighExpression highExpression =
match highExpression with
| MULTIPLY (hexpr, oper) -> (evaluateHighExpression hexpr) * (EvaluateOperand oper)
| DIVIDEOP (hexpr, oper) -> (evaluateHighExpression hexpr) / (EvaluateOperand oper)
| VAR oper -> EvaluateOperand oper

and EvaluateOperand oper =
match oper with
| DECIMALOP x -> x
| VARNAMEOP x -> stack.Item(currentFunctionName).Item(x)
| FUNCOP x -> evaluateFunction x
| SUBEXPROP x -> evaluateExpression x

変数と関数のサポートを導入したため、この場合のハンドラーを作成する必要があります。 変数の場合、すべては多かれ少なかれ単純です。現在の関数の変数の値を含む辞書に行き、変数の名前で値を取得します（VARNAMEOPはString型に関連付けられていることを思い出してください）

関数との接触の場合、関数のヘッダーに従って呼び出し元の関数からパラメーターをコピーし、その実行を開始する必要があります。
これを行うには、次のコードを追加します。

and evaluateFunction(f:FunctionTitle) =
let caller = currentFunctionName;
let newStack = Dictionary<String, Double>()
let realParams = functionsList.Item (f |> GetFunctionName) |> GetFormalParamsListDecription

let formalParams = GetFormalParamsListTitle(f)
ignore <| List.mapi2 ( fun i x y -> newStack.Add(x, stack.Item(caller).Item(y))) realParams formalParams

currentFunctionName <- GetFunctionName(f)
stack.Add(currentFunctionName, newStack)

let operatorsList = functionsList.Item(GetFunctionName f) |> GetOperatorsList

let result = RunFunction operatorsList

ignore <| stack.Remove(currentFunctionName)

currentFunctionName <- caller
result
//

これも機能ですが、テンプレートを選択するのではなく、より馴染みのある形式です。

パイプライン演算子「|>」を調べてみましょう。実際、これは関数チェーンを呼び出すより理解しやすい方法です。以前にOuterFunction（InnerFunction（Validate（data）））を記述する必要がある場合は、F＃でこのチェーンを「展開」できます：data |>検証|> InnerFunction |> OuterFunction
両方のエントリは同じ結果になりますが、「|>」演算子を使用する場合、関数は左から右に適用されます。長いチェーンの場合はより便利です。
これらの関数の特徴は、戻り値、たとえば関数を書く必要がないことです。
テスト（a）= a * 10
* 10を返しますが、これは部分的に便利ですが、「誤って」値を返さないように注意する必要があります（ところで、VSはすべての意図しない戻り値を強調します）。行の先頭ですべて無視することを返します-逆パイプライン演算子「<|」を使用します。「|>」と同じように、反対方向でのみ機能し、関数は右から左に適用されます。
単純な割り当ての場合、値が返されないように、「=」の代わりに「<-」演算子を使用します

行をさらに詳しく分析してみましょう。

ignore <| List.mapi2 ( fun i x y -> newStack.Add(x, stack.Item(caller).Item(y))) realParams formalParams

Listクラスには一連のmapi *メソッド（異なる数のリスト）が含まれます。これらのメソッドの本質は、複数のリスト（この場合は2）を並行して処理し、両方のリストの要素番号と要素自体を長さを前提としてハンドラー関数に渡すことですリストは等しいです。 mapi2メソッドは、3つのパラメーター、ハンドラー関数、および2つの処理済みリストを受け入れます。
たとえば、次のコードを実行した結果として：

let firstList = [1..5]
let secondList = [6..10]
ignore <| List.mapi2 ( fun i x y -> Console.WriteLine(10*x+y)) firstList secondList

結果が得られます：16 27 38 49 60

関数を呼び出すときと言語で記述するときは、括弧内のパラメーターの順序が同じであるため、呼び出しリストと関数宣言の要素をペアで処理するだけです。
funキーワードは、リストを処理するために使用する新しい関数を定義します（C＃でラムダとの類似性を描くことができます）。この関数は3つのパラメーターを取ります。iは両方のリストの現在の要素の番号、xとyはそれぞれ最初と2番目のリストの要素です。
したがって、ここでは、呼び出し元の関数のスタックから変数を新しいスタックにコピーしています。

パラメーターを準備した後、関数を呼び出し、結果を記憶し、辞書（スタック）を削除し、呼び出し元の関数の名前を復元します。

let result = RunFunction operatorsList

ignore <| stack.Remove(currentFunctionName)

currentFunctionName <- caller
result

なぜなら returnは書き込む必要はありません。値を返すには、返す変数の名前を書き込むだけです。

次に、runFunctionメソッドを作成します。

and RunFunction(o:OperatorsList) =
ignore <| List.map ( fun x -> EvaluateOperator x) o
stack.Item(currentFunctionName).Item( "return" )

List.mapメソッドはリストのすべての要素を反復処理し、現在のスタックから結果の変数を返すだけです。

and EvaluateOperator operator =
match operator with
| VarOperator (name, expr) -> stack.Item(currentFunctionName).Add(name, evaluateExpression expr)
| ReturnOperator expr -> stack.Item(currentFunctionName).Add( "return" , evaluateExpression expr)

私たちの言語には2種類の演算子しかありません。これは変数宣言または戻り値のいずれかです。どちらの場合も値を計算して辞書（スタック）に追加し、戻りの場合は言語での戻りがキーワードであり、安全にできるという事実を使用します既に宣言されている変数との競合を恐れることなく、独自の目的で使用してください。
言語で事前定義されたいくつかの関数を使用するため、I / Oを実装するためにいくつかのチェックを追加します。

and RunFunction(o:OperatorsList) =
if currentFunctionName.Equals "print" then
stack.Item(currentFunctionName).Add( "return" , 0.0)
Console.WriteLine(stack.Item(currentFunctionName).Item( "toPrint" ).ToString())
if currentFunctionName.Equals "get" then
Console.Write( "Input: " );
stack.Item(currentFunctionName).Add( "return" , Double.Parse(Console.ReadLine()))
if currentFunctionName.Equals "Program" then
stack.Item(currentFunctionName).Add( "return" , 1.0)

ignore <| List.map ( fun x -> EvaluateOperator x) o
stack.Item(currentFunctionName).Item( "return" )

関数の名前を確認し、結果に応じて、変数の値を出力するか、キーボードから値を読み取ります。
メインのreturnメソッドに書き込まないために、スペシャルを定義します。 関数本体が実行される前でも変数。

特に、ifブロックの本体を強調するために、F＃で重要なインデントが使用されます。
最後に行う必要があるのは、使用していない関数を特定し、パーサーを使用するシェルを作成することです。

let GetFunctionName f = match f with name, foo -> name
let GetFunctionNameDescription f = match f with t, foo -> GetFunctionName t
let GetFormalParamsListTitle t = match t with foo, paramerers -> paramerers
let GetFormalParamsListDecription f = match f with t, foo -> GetFormalParamsListTitle t
let GetOperatorsList f = match f with foo, o -> o
let GetTitle f = match f with t, too -> t

一部の型は単に同義語として宣言したため、コンストラクタ名がない単語の後に、すべてのパラメーターの列挙があり、矢印の後に関数本体があります。この場合、返される必要のある変数の名前を書き込むだけです。
括弧なしで関数呼び出しを記述することが珍しい場合、F＃を使用すると、次の形式でコードを記述できます。

let GetFunctionName(f) = match f with name, foo -> name
let GetFunctionNameDescription(f) = match f with t, foo -> GetFunctionName(t)
let GetFormalParamsListTitle(t) = match t with foo, paramerers -> paramerers
let GetFormalParamsListDecription(f) = match f with t, foo -> GetFormalParamsListTitle(t)
let GetOperatorsList(f) = match f with foo, o -> o
let GetTitle(f) = match f with t, too -> t

これらのエントリは完全に同等です。

最後の仕上げ

そして最後に、最後：

printfn "H#"

let mutable source = "" ;
let rec readAndProcess() =
printf ":"
match Console.ReadLine() with
| "quit" -> ()
| "GO" ->
try
printfn "Lexing..."
let lexbuff = LexBuffer<char>.FromString(source)

printfn "Parsing..."
let program = Parser.start Lexer.tokenize lexbuff
ignore <| List.map ( fun x -> functionsList.Add(GetFunctionNameDescription(x),x)) program
functionsList.Add( "print" ,(( "print" , [ "toPrint" ]), []))
functionsList.Add( "get" ,(( "get" , []), []))
printfn "Running..."
ignore <| (functionsList.Item( "Program" ) |> GetTitle |> evaluateFunction)

with ex ->
printfn "Unhandled Exception: %s" ex.Message

readAndProcess()
| expr ->
source <- source + expr
readAndProcess()

readAndProcess()

解析が成功した場合、キーボードから入力された文字列を解析しようとする新しい関数を定義します-受信したリスト（プログラム）からすべての関数をfunctionsList変数に追加します。
プログラムの先頭で関数を呼び出すには、ファイルの末尾にインデントせずに名前を書くだけです。
言語には2つの事前定義関数（getおよびprint）があるため、それらを追加してから、Programという関数を実行します。

この例で最後に説明できるのは、一致によってコンストラクターを定義しなかったオブジェクトを構築する興味深い方法です

and FunctionTitle = String * List<String>
and FunctionDescription = FunctionTitle * OperatorsList
and OperatorsList = List<Operator>
and AdditionParamsList = List<String>
and WholeProgram = List<FunctionDescription>

FunctionTitleオブジェクトが必要な場合、それを作成するには、そのパラメーター（Stringおよび<ListString>）を括弧で囲むだけで十分です。データ型を指定する必要はありません。

( "print" ,(( "print" , [ "toPrint" ]), []))

打ち上げ

さて、インタプリタを実行しましょう：


Enterキーを押すと、変数の値を入力するプロンプトが表示されます。


そしてその後：


まあ、プログラムは本当に動作します。
バイナリを含むソースコードはこちらからダウンロードできます 。

F＃のコードをもう一度見てみると、やりたいことを簡単に説明する最小限のものを書いたことがわかります。独自のインタープリターを作成して、〜200行のコードに収めることができます.F＃を使用すると、日常的な作業を取り除くことができます質問「what」には答えないが、質問「how」には答えるコード。 もちろん、最初はこの言語でのプログラミングは難しいように見えますが、メンテナンスが容易な柔軟なコードを作成できるため、場合によっては価値があります。
ご清聴ありがとうございました。