StepFunctionsだけで無駄に壮大な4bit加算器を作ったよ

StepFunctionsはお好きですか？はい、私は好きです。

先日Workflow Studioもできて、複雑なフローも簡単に作れるようになりました。
それを駆使して4bit加算器(4bitの数値2つを足し合わせる回路)を作ってみたのでご報告です。

## StepFunctionsで論理回路

先日、なんだか眠れないなーと布団の中でゴロゴロしてたらふと天啓を得ました。
「StepFunctionsで論理回路が作れるぞ」という天啓を。

ということで、そこから起きてNOT, AND, OR回路を作ってみました。ノッてしまって午前3時まで眠れませんでした…。

### NOT回路

![step_functions_4bit_adder_not.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/d8b240fe-c489-f04b-15bb-ae4618575ced.jpeg)

これがNOT回路です。

![step_functions_4bit_adder_or_flow.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/45d99700-b805-3089-cde6-00d2218070d2.jpeg)

定義は以下のようになっています。
<details><summary>NOTの定義</summary><div>

```json
{
  "Comment": "This is your state machine",
  "StartAt": "not",
  "States": {
    "0": {
      "Type": "Pass",
      "End": true,
      "Parameters": {
        "bit": 0
      }
    },
    "1": {
      "Type": "Pass",
      "Parameters": {
        "bit": 1
      },
      "End": true
    },
    "Fail": {
      "Type": "Fail"
    },
    "not": {
      "Type": "Choice",
      "Choices": [
        {
          "Variable": "$.bit",
          "NumericEquals": 0,
          "Next": "1"
        },
        {
          "Variable": "$.bit",
          "NumericEquals": 1,
          "Next": "0"
        }
      ],
      "Default": "Fail"
    }
  }
}
```
</div></details>



入力として、以下のようなフォーマットを想定しています。

```json
{
  "bit": <0 or 1>
}
```

NOTなので、bitを反転したものが出力になります。
例えば0を入れると、次のJSONが出力されます。

```json
{
  "bit": 1
}
```

組み立てとしては、`not`と名付けているChoice stateでbitの値を見て、
0なら問答無用で1を出力するPass state, 1なら問答無用で0を出力するPass Stateに送っている形です。

それから、一応0, 1以外が来たらFail stateに送るようにしました。

### AND回路

![step_functions_4bit_adder_and.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/afcd6026-9e2e-5cea-04ab-8a61d3ffe5ed.jpeg)

次にAND回路です。

![step_functions_4bit_adder_and_flow.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/9a3c2df4-29e6-738d-9cf7-1c78e3231b79.jpeg)

定義は以下のようになっています。
<details><summary>ANDの定義</summary><div>

```json
{
  "Comment": "This is your state machine",
  "StartAt": "and",
  "States": {
    "0": {
      "Type": "Pass",
      "Parameters": {
        "bit": 0
      },
      "End": true
    },
    "1": {
      "Type": "Pass",
      "End": true,
      "Parameters": {
        "bit": 1
      }
    },
    "Fail": {
      "Type": "Fail"
    },
    "and": {
      "Type": "Choice",
      "Choices": [
        {
          "And": [
            {
              "Variable": "$[0].bit",
              "NumericEquals": 1
            },
            {
              "Variable": "$[1].bit",
              "NumericEquals": 1
            }
          ],
          "Next": "1"
        },
        {
          "And": [
            {
              "Variable": "$[0].bit",
              "NumericEquals": 1
            },
            {
              "Variable": "$[1].bit",
              "NumericEquals": 0
            }
          ],
          "Next": "0"
        },
        {
          "And": [
            {
              "Variable": "$[0].bit",
              "NumericEquals": 0
            },
            {
              "Variable": "$[1].bit",
              "NumericEquals": 1
            }
          ],
          "Next": "0"
        },
        {
          "And": [
            {
              "Variable": "$[0].bit",
              "NumericEquals": 0
            },
            {
              "Variable": "$[1].bit",
              "NumericEquals": 0
            }
          ],
          "Next": "0"
        }
      ],
      "Default": "Fail"
    }
  }
}
```
</div></details>

入力として、以下のようなフォーマットを想定しています。

```json
[
  { "bit": <0 or 1> },
  { "bit": <0 or 1> }
]
```

ANDなので、2つのbitのANDが出力になります。
例えば0, 1を入れると、次のJSONが出力されます。

```json
{
  "bit": 0
}
```

組み立てもNOTとほとんど同じです。
Choice stateで条件分岐して、出力を生成するPass stateに送っています。

### OR回路
![step_functions_4bit_adder_or.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/6884c206-2704-95ad-af6e-5ccf8c9da86c.jpeg)

最後にOR回路です。

![step_functions_4bit_adder_or_flow.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/f9098e23-0459-ee5f-fe09-0aaa94aa3149.jpeg)


定義は以下のようになっています。
<details><summary>ORの定義</summary><div>

```json
{
  "Comment": "This is your state machine",
  "StartAt": "or",
  "States": {
    "0": {
      "Type": "Pass",
      "End": true,
      "Parameters": {
        "bit": 0
      }
    },
    "1": {
      "Type": "Pass",
      "End": true,
      "Parameters": {
        "bit": 1
      }
    },
    "or": {
      "Type": "Choice",
      "Choices": [
        {
          "And": [
            {
              "Variable": "$[0].bit",
              "NumericEquals": 1
            },
            {
              "Variable": "$[1].bit",
              "NumericEquals": 1
            }
          ],
          "Next": "1"
        },
        {
          "And": [
            {
              "Variable": "$[0].bit",
              "NumericEquals": 1
            },
            {
              "Variable": "$[1].bit",
              "NumericEquals": 0
            }
          ],
          "Next": "1"
        },
        {
          "And": [
            {
              "Variable": "$[0].bit",
              "NumericEquals": 0
            },
            {
              "Variable": "$[1].bit",
              "NumericEquals": 1
            }
          ],
          "Next": "1"
        },
        {
          "And": [
            {
              "Variable": "$[0].bit",
              "NumericEquals": 0
            },
            {
              "Variable": "$[1].bit",
              "NumericEquals": 0
            }
          ],
          "Next": "0"
        }
      ],
      "Default": "Fail"
    },
    "Fail": {
      "Type": "Fail"
    }
  }
}
```
</div></details>

入力として、以下のようなフォーマットを想定しています。

```json
[
  { "bit": <0 or 1> },
  { "bit": <0 or 1> }
]
```

ORなので、2つのbitのORが出力になります。
例えば0, 1を入れると、次のJSONが出力されます。

```json
{
  "bit": 1
}
```

組み立てもNOTとほとんど同じです。
Choice stateで条件分岐して、出力を生成するPass stateに送っています。

### ポイント

条件判定の部分で、入力のJSONから値を切り出すためにJsonPathを使っています。
ただし、一般的なJsonPathとは若干仕様が違っていて、機能が制限されていたりします（[公式ドキュメント](https://docs.aws.amazon.com/ja_jp/step-functions/latest/dg/amazon-states-language-paths.html)）。

ここでは配列の要素を取得しようとしていたのですが(`$[0].bit` といった部分です)、公式ドキュメントに明確な説明がなく探り当てるのに苦労しました。。

## 半加算器

NOT, AND, ORができれば次はやっぱり半加算器でしょう。2つのbitを入力して、それらの和と繰り上がりを返すやつです。

回路図で言うとこんな感じ。

![step_functions_4bit_adder_half1.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/65e21db5-a2e5-5abb-ee39-6b8f7fa02c6c.jpeg)
![step_functions_4bit_adder_half2.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/25ac6eb5-33e4-ed4a-6ca7-69a6de520898.jpeg)

StepFunctionsをネストさせてこれを作ってみます。かなり壮大になりましたが、回路図に忠実になっていると思います。

![step_functions_4bit_adder_half_flow.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/b10d2e0a-7e0c-bc01-19ee-e01fc53c1594.jpeg)

定義は以下のようになっています。
<details><summary>半加算器の定義</summary><div>

```json
{
  "Comment": "This is your state machine",
  "StartAt": "split_s_c",
  "States": {
    "split_s_c": {
      "Type": "Parallel",
      "Branches": [
        {
          "StartAt": "split_s",
          "States": {
            "split_s": {
              "Type": "Parallel",
              "Branches": [
                {
                  "StartAt": "split_s0",
                  "States": {
                    "split_s0": {
                      "Type": "Parallel",
                      "Branches": [
                        {
                          "StartAt": "bitA_s0",
                          "States": {
                            "bitA_s0": {
                              "Type": "Pass",
                              "Parameters": {
                                "bit.$": "$[0].bit"
                              },
                              "End": true
                            }
                          }
                        },
                        {
                          "StartAt": "bitB_s0",
                          "States": {
                            "bitB_s0": {
                              "Type": "Pass",
                              "Next": "NotB_s0",
                              "Parameters": {
                                "bit.$": "$[1].bit"
                              }
                            },
                            "NotB_s0": {
                              "Type": "Task",
                              "Resource": "arn:aws:states:::states:startExecution.sync:2",
                              "Parameters": {
                                "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:Not",
                                "Input.$": "$"
                              },
                              "End": true,
                              "OutputPath": "$.Output"
                            }
                          }
                        }
                      ],
                      "Next": "A_And_NotB"
                    },
                    "A_And_NotB": {
                      "Type": "Task",
                      "Resource": "arn:aws:states:::states:startExecution.sync:2",
                      "Parameters": {
                        "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:And",
                        "Input.$": "$"
                      },
                      "End": true,
                      "OutputPath": "$.Output"
                    }
                  }
                },
                {
                  "StartAt": "split_s1",
                  "States": {
                    "split_s1": {
                      "Type": "Parallel",
                      "Branches": [
                        {
                          "StartAt": "bitA_s1",
                          "States": {
                            "bitA_s1": {
                              "Type": "Pass",
                              "Parameters": {
                                "bit.$": "$[0].bit"
                              },
                              "Next": "NotA_s1"
                            },
                            "NotA_s1": {
                              "Type": "Task",
                              "Resource": "arn:aws:states:::states:startExecution.sync:2",
                              "Parameters": {
                                "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:Not",
                                "Input.$": "$"
                              },
                              "End": true,
                              "OutputPath": "$.Output"
                            }
                          }
                        },
                        {
                          "StartAt": "bitB_s1",
                          "States": {
                            "bitB_s1": {
                              "Type": "Pass",
                              "Parameters": {
                                "bit.$": "$[1].bit"
                              },
                              "End": true
                            }
                          }
                        }
                      ],
                      "Next": "NotA_And_B"
                    },
                    "NotA_And_B": {
                      "Type": "Task",
                      "Resource": "arn:aws:states:::states:startExecution.sync:2",
                      "Parameters": {
                        "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:And",
                        "Input.$": "$"
                      },
                      "End": true,
                      "OutputPath": "$.Output"
                    }
                  }
                }
              ],
              "Next": "(A_And_NotB)_Or_(NotA_And_B)"
            },
            "(A_And_NotB)_Or_(NotA_And_B)": {
              "Type": "Task",
              "Resource": "arn:aws:states:::states:startExecution.sync:2",
              "Parameters": {
                "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:Or",
                "Input.$": "$"
              },
              "End": true,
              "OutputPath": "$.Output"
            }
          }
        },
        {
          "StartAt": "split_c",
          "States": {
            "split_c": {
              "Type": "Parallel",
              "Branches": [
                {
                  "StartAt": "bitA_c",
                  "States": {
                    "bitA_c": {
                      "Type": "Pass",
                      "Parameters": {
                        "bit.$": "$[0].bit"
                      },
                      "End": true
                    }
                  }
                },
                {
                  "StartAt": "bitB_c",
                  "States": {
                    "bitB_c": {
                      "Type": "Pass",
                      "Parameters": {
                        "bit.$": "$[1].bit"
                      },
                      "End": true
                    }
                  }
                }
              ],
              "Next": "A_And_B"
            },
            "A_And_B": {
              "Type": "Task",
              "Resource": "arn:aws:states:::states:startExecution.sync:2",
              "Parameters": {
                "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:And",
                "Input.$": "$"
              },
              "End": true,
              "OutputPath": "$.Output"
            }
          }
        }
      ],
      "End": true
    }
  }
}
```
</div></details>

入力として、以下のようなフォーマットを想定しています。

```json
[
  { "bit": <0 or 1> },
  { "bit": <0 or 1> }
]
```

例えば1, 1を入れると和が0, 繰り上がりが1なので、次のJSONが出力されます。

```json
[
  { "bit": 0 },
  { "bit": 1 }
]
```

### ポイント

Parallel stateの分岐が収束する部分では、分岐の最終出力が配列になってやってきます。
そのため、AND, ORの入力は配列を受け取るようにしています。

また、StepFunctionsのネストもポイントです。
Workflow Studioで、 `タスクが完了するまで待機` にチェックを入れておきましょう。

![step_functions_4bit_adder_sync.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/661196e5-0343-f630-6eed-3a483cabd6c7.jpeg)

定義でいうと、

```json
"Resource": "arn:aws:states:::states:startExecution.sync:2"
```

にあたります。
こうしておかないと、非同期実行になるためStepFunctionsの結果を戻してもらえません。

そして、出力にはいろいろな情報が付いてくるので、出力をフィルタリングしてあげましょう。

![step_functions_4bit_adder_output_filter.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/e918a375-1e9b-f0fb-7dc9-57124d6a8b83.jpeg)

## 4bit加算器

ここまで来たら複数ビットの加算器を作りたくなりますね。
4bitの和と最終桁の繰り上がり(桁あふれ)を求めるものを作ってみました。

回路図で言うとこんな感じ。

![step_functions_4bit_adder_4bit1.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/1a00d3f6-f35f-b7ae-5a22-9de3eea6edbb.jpeg)

StepFunctionsだとこうなりました。

![step_functions_4bit_adder_4bit_flow.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/41bafdce-82ef-5c6b-3e03-829fc48a9fe1.jpeg)

定義は以下のようになっています。
<details><summary>4bit加算器の定義</summary><div>

```json
{
  "Comment": "This is your state machine",
  "StartAt": "calc_1",
  "States": {
    "calc_1": {
      "Type": "Parallel",
      "Branches": [
        {
          "StartAt": "digit_0",
          "States": {
            "digit_0": {
              "Type": "Pass",
              "Parameters": [
                {
                  "bit.$": "$.numA[0]"
                },
                {
                  "bit.$": "$.numB[0]"
                }
              ],
              "Next": "half_addr_0"
            },
            "half_addr_0": {
              "Type": "Task",
              "Resource": "arn:aws:states:::states:startExecution.sync:2",
              "Parameters": {
                "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:HalfAdder",
                "Input.$": "$"
              },
              "End": true,
              "OutputPath": "$.Output"
            }
          }
        },
        {
          "StartAt": "digit_1",
          "States": {
            "digit_1": {
              "Type": "Pass",
              "Parameters": [
                {
                  "bit.$": "$.numA[1]"
                },
                {
                  "bit.$": "$.numB[1]"
                }
              ],
              "Next": "half_addr_1"
            },
            "half_addr_1": {
              "Type": "Task",
              "Resource": "arn:aws:states:::states:startExecution.sync:2",
              "Parameters": {
                "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:HalfAdder",
                "Input.$": "$"
              },
              "End": true,
              "OutputPath": "$.Output"
            }
          }
        },
        {
          "StartAt": "digit_2",
          "States": {
            "digit_2": {
              "Type": "Pass",
              "Parameters": [
                {
                  "bit.$": "$.numA[2]"
                },
                {
                  "bit.$": "$.numB[2]"
                }
              ],
              "Next": "half_addr_2"
            },
            "half_addr_2": {
              "Type": "Task",
              "Resource": "arn:aws:states:::states:startExecution.sync:2",
              "Parameters": {
                "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:HalfAdder",
                "Input.$": "$"
              },
              "End": true,
              "OutputPath": "$.Output"
            }
          }
        },
        {
          "StartAt": "digit_3",
          "States": {
            "digit_3": {
              "Type": "Pass",
              "Parameters": [
                {
                  "bit.$": "$.numA[3]"
                },
                {
                  "bit.$": "$.numB[3]"
                }
              ],
              "Next": "half_addr_3"
            },
            "half_addr_3": {
              "Type": "Task",
              "Resource": "arn:aws:states:::states:startExecution.sync:2",
              "Parameters": {
                "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:HalfAdder",
                "Input.$": "$"
              },
              "End": true,
              "OutputPath": "$.Output"
            }
          }
        }
      ],
      "Next": "calc_2"
    },
    "calc_2": {
      "Type": "Parallel",
      "Next": "calc_3",
      "Branches": [
        {
          "StartAt": "calc2_s0",
          "States": {
            "calc2_s0": {
              "Type": "Pass",
              "Parameters": {
                "bit.$": "$[0][0].bit"
              },
              "End": true
            }
          }
        },
        {
          "StartAt": "calc2_c0_st1",
          "States": {
            "calc2_c0_st1": {
              "Type": "Pass",
              "Parameters": [
                {
                  "bit.$": "$[0][1].bit"
                },
                {
                  "bit.$": "$[1][0].bit"
                }
              ],
              "Next": "half_addr_0_1"
            },
            "half_addr_0_1": {
              "Type": "Task",
              "Resource": "arn:aws:states:::states:startExecution.sync:2",
              "Parameters": {
                "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:HalfAdder",
                "Input.$": "$"
              },
              "End": true,
              "OutputPath": "$.Output"
            }
          }
        },
        {
          "StartAt": "calc2_ct1",
          "States": {
            "calc2_ct1": {
              "Type": "Pass",
              "End": true,
              "Parameters": {
                "bit.$": "$[1][1].bit"
              }
            }
          }
        },
        {
          "StartAt": "calc2_st2_ct2",
          "States": {
            "calc2_st2_ct2": {
              "Type": "Pass",
              "End": true,
              "InputPath": "$[2]"
            }
          }
        },
        {
          "StartAt": "calc2_st3_ct3",
          "States": {
            "calc2_st3_ct3": {
              "Type": "Pass",
              "End": true,
              "InputPath": "$[3]"
            }
          }
        }
      ]
    },
    "calc_3": {
      "Type": "Parallel",
      "Next": "calc_4",
      "Branches": [
        {
          "StartAt": "calc3_s0",
          "States": {
            "calc3_s0": {
              "Type": "Pass",
              "End": true,
              "InputPath": "$[0]"
            }
          }
        },
        {
          "StartAt": "calc3_s1",
          "States": {
            "calc3_s1": {
              "Type": "Pass",
              "Parameters": {
                "bit.$": "$[1][0].bit"
              },
              "End": true
            }
          }
        },
        {
          "StartAt": "calc3_ct01_ct1",
          "States": {
            "calc3_ct01_ct1": {
              "Type": "Pass",
              "Parameters": [
                {
                  "bit.$": "$[1][1].bit"
                },
                {
                  "bit.$": "$[2].bit"
                }
              ],
              "Next": "or_ct01_ct1"
            },
            "or_ct01_ct1": {
              "Type": "Task",
              "Resource": "arn:aws:states:::states:startExecution.sync:2",
              "Parameters": {
                "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:Or",
                "Input.$": "$"
              },
              "End": true,
              "OutputPath": "$.Output"
            }
          }
        },
        {
          "StartAt": "calc3_st2_ct2",
          "States": {
            "calc3_st2_ct2": {
              "Type": "Pass",
              "End": true,
              "InputPath": "$[3]"
            }
          }
        },
        {
          "StartAt": "calc3_st3_ct3",
          "States": {
            "calc3_st3_ct3": {
              "Type": "Pass",
              "End": true,
              "InputPath": "$[4]"
            }
          }
        }
      ]
    },
    "calc_4": {
      "Type": "Parallel",
      "Next": "calc_5",
      "Branches": [
        {
          "StartAt": "calc4_s0",
          "States": {
            "calc4_s0": {
              "Type": "Pass",
              "End": true,
              "InputPath": "$[0]"
            }
          }
        },
        {
          "StartAt": "calc4_s1",
          "States": {
            "calc4_s1": {
              "Type": "Pass",
              "End": true,
              "InputPath": "$[1]"
            }
          }
        },
        {
          "StartAt": "calc4_c1_st2",
          "States": {
            "calc4_c1_st2": {
              "Type": "Pass",
              "Parameters": [
                {
                  "bit.$": "$[2].bit"
                },
                {
                  "bit.$": "$[3][0].bit"
                }
              ],
              "Next": "half_addr_c1_st2"
            },
            "half_addr_c1_st2": {
              "Type": "Task",
              "Resource": "arn:aws:states:::states:startExecution.sync:2",
              "Parameters": {
                "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:HalfAdder",
                "Input.$": "$"
              },
              "End": true,
              "OutputPath": "$.Output"
            }
          }
        },
        {
          "StartAt": "calc4_ct2",
          "States": {
            "calc4_ct2": {
              "Type": "Pass",
              "End": true,
              "Parameters": {
                "bit.$": "$[3][1].bit"
              }
            }
          }
        },
        {
          "StartAt": "calc4_st3_ct3",
          "States": {
            "calc4_st3_ct3": {
              "Type": "Pass",
              "End": true,
              "InputPath": "$[4]"
            }
          }
        }
      ]
    },
    "calc_5": {
      "Type": "Parallel",
      "Next": "calc_6",
      "Branches": [
        {
          "StartAt": "calc5_s0",
          "States": {
            "calc5_s0": {
              "Type": "Pass",
              "End": true,
              "InputPath": "$[0]"
            }
          }
        },
        {
          "StartAt": "calc5_s1",
          "States": {
            "calc5_s1": {
              "Type": "Pass",
              "InputPath": "$[1]",
              "End": true
            }
          }
        },
        {
          "StartAt": "calc5_s2",
          "States": {
            "calc5_s2": {
              "Type": "Pass",
              "End": true,
              "Parameters": {
                "bit.$": "$[2][0].bit"
              }
            }
          }
        },
        {
          "StartAt": "calc5_ct012_ct2",
          "States": {
            "calc5_ct012_ct2": {
              "Type": "Pass",
              "Parameters": [
                {
                  "bit.$": "$[2][1].bit"
                },
                {
                  "bit.$": "$[3].bit"
                }
              ],
              "Next": "or_ct012_ct2"
            },
            "or_ct012_ct2": {
              "Type": "Task",
              "Resource": "arn:aws:states:::states:startExecution.sync:2",
              "Parameters": {
                "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:Or",
                "Input.$": "$"
              },
              "End": true,
              "OutputPath": "$.Output"
            }
          }
        },
        {
          "StartAt": "calc5_st3_ct3",
          "States": {
            "calc5_st3_ct3": {
              "Type": "Pass",
              "End": true,
              "InputPath": "$[4]"
            }
          }
        }
      ]
    },
    "calc_6": {
      "Type": "Parallel",
      "Next": "calc_7",
      "Branches": [
        {
          "StartAt": "calc6_s0",
          "States": {
            "calc6_s0": {
              "Type": "Pass",
              "End": true,
              "InputPath": "$[0]"
            }
          }
        },
        {
          "StartAt": "calc6_s1",
          "States": {
            "calc6_s1": {
              "Type": "Pass",
              "InputPath": "$[1]",
              "End": true
            }
          }
        },
        {
          "StartAt": "calc6_s2",
          "States": {
            "calc6_s2": {
              "Type": "Pass",
              "End": true,
              "InputPath": "$[2]"
            }
          }
        },
        {
          "StartAt": "calc6_c2_st3",
          "States": {
            "calc6_c2_st3": {
              "Type": "Pass",
              "Parameters": [
                {
                  "bit.$": "$[3].bit"
                },
                {
                  "bit.$": "$[4][0].bit"
                }
              ],
              "Next": "half_addr_c2_st3"
            },
            "half_addr_c2_st3": {
              "Type": "Task",
              "Resource": "arn:aws:states:::states:startExecution.sync:2",
              "Parameters": {
                "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:HalfAdder",
                "Input.$": "$"
              },
              "End": true,
              "OutputPath": "$.Output"
            }
          }
        },
        {
          "StartAt": "calc4_ct3",
          "States": {
            "calc4_ct3": {
              "Type": "Pass",
              "End": true,
              "Parameters": {
                "bit.$": "$[4][1].bit"
              }
            }
          }
        }
      ]
    },
    "calc_7": {
      "Type": "Parallel",
      "Next": "result",
      "Branches": [
        {
          "StartAt": "calc7_s0",
          "States": {
            "calc7_s0": {
              "Type": "Pass",
              "End": true,
              "InputPath": "$[0]"
            }
          }
        },
        {
          "StartAt": "calc7_s1",
          "States": {
            "calc7_s1": {
              "Type": "Pass",
              "InputPath": "$[1]",
              "End": true
            }
          }
        },
        {
          "StartAt": "calc7_s2",
          "States": {
            "calc7_s2": {
              "Type": "Pass",
              "InputPath": "$[2]",
              "End": true
            }
          }
        },
        {
          "StartAt": "calc7_s3",
          "States": {
            "calc7_s3": {
              "Type": "Pass",
              "End": true,
              "Parameters": {
                "bit.$": "$[3][0].bit"
              }
            }
          }
        },
        {
          "StartAt": "calc5_ct0123_ct3",
          "States": {
            "calc5_ct0123_ct3": {
              "Type": "Pass",
              "Parameters": [
                {
                  "bit.$": "$[3][1].bit"
                },
                {
                  "bit.$": "$[4].bit"
                }
              ],
              "Next": "or_ct0123_ct3"
            },
            "or_ct0123_ct3": {
              "Type": "Task",
              "Resource": "arn:aws:states:::states:startExecution.sync:2",
              "Parameters": {
                "StateMachineArn": "arn:aws:states:ap-northeast-1:xxxxxxxxxxxx:stateMachine:Or",
                "Input.$": "$"
              },
              "End": true,
              "OutputPath": "$.Output"
            }
          }
        }
      ]
    },
    "result": {
      "Type": "Pass",
      "End": true,
      "Parameters": {
        "sum.$": "States.Array($[0].bit, $[1].bit, $[2].bit, $[3].bit)",
        "carry.$": "$[4].bit"
      }
    }
  }
}
```
</div></details>

### ポイント

残念ながら、StepFunctionsでは各ステートの入力は１つだけです。回路図のように、複数のステートの任意の出力を同時に入力として扱うようなことはできません。そこで、Parallel stateを使って複数入力を擬似的に実現しています。

StepFunctionのワークフローに寄せる形で書くと以下のような形です。見た目は変わっていますがやっていることは同じです。

![step_functions_4bit_adder_4bit2.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/7ef6d26e-1a2f-eaeb-cbf2-935b957beecf.jpeg)

## 動かしてみよう！！

さて、ついに動かすときがやってきました。
以下のJSONを入力してみます。ビットの順序が逆転しますが、0101(5) + 1110(14)をしています。

```json
{
  "numA": [1, 0, 1, 0],
  "numB": [0, 1, 1, 1]
}
```

結果は…

![step_functions_4bit_adder_result1.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/034b4e87-caac-3bf4-ce6c-100036ccb0d5.jpeg)


```json
{
  "sum": [1, 1, 0, 0],
  "carry": 1
}
```

ということで、桁あふれまで一緒にしてあげると、10011(19)ということで、正しく計算できています！！
ここまで計算するのに48,515\[msec]かかってる…壮大だ！

時間がかかっている要因としては、やはりStepFunctionsをネストしているところで完了待ちをしているところが大きいです。
例として4つの半加算器の完了待ちの部分を出して見ましたが、半加算器の中でもStepFunctionsのネストで完了待ちをしている部分があり、、それはまぁ時間がかかりますよね。

![step_functions_4bit_adder_result2.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/39565/517bd3ef-5970-e218-9af6-a29d353f0d5a.jpeg)

## まとめ

今回は秋の夜長にStepFunctionsで遊んでみました。
いざやってみると、意外と詰まるところや知らないところが出てきて、やっぱり触ってなんぼだなと改めて感じました。

こんな遊び記事がお好みの方は以下も一緒にどうぞ！

* [究極のCloudFormationをたずねて三千里](https://qiita.com/Kta-M/items/53bfd638eae21b76250f)
* [メールにパスワード付きzipを添付して「パスワードは別途お送りいたします」とする慣習がめんどくさいのでなんとかした](https://qiita.com/Kta-M/items/afa94a6728416511b78b)