Lazy K 入門（4）　Lazy K プログラムを書いてみる

Posted at 2026-08-29

はじめに

プログラミング言語 Lazy K とは何か、どのように書けるのか、実際に使うときに気をつけないといけないことまでを追っていきたいと思っています。

今回は、実際にLazy K プログラムを書いてみたいと思います。

第１回：コンビネータとラムダ計算　
第２回：Lazy K の入出力とチャーチ数
第３回：ラムダ計算のいろいろ
第４回：Lazy K プログラムを書いてみる　← いまここ

Echo プログラム

Lazy K でかける簡単なプログラムは、Hello, World!...ではなく、Echoプログラムです。
Echoプログラムは、ラムダ計算の式で書くと以下のようになります。

λx. x

入力を受け取ってそのまま出力に返すので、こうなります。
Lazy K のコードは以下のようになります。

Iコンビネータの定義そのままなので上のようになります。
初めてのLazy Kコードをかけました！

Lazy K での数値の表し方

Lazy Kで数値は実際どのようなコードになるでしょうか。
小さい数で試してみます。

0 := λf. λx. x        → `ki
1 := λf. λx. f x
  →η λf. f            → i
2 := λf. λx. f (f x)  → ``s``s`kski
3 := ...              → ``s``s`ksk``s``s`kski
...

となります。
つまり、``s``s`kskをiに一つずつ加えていく形になります。
Lazy Kコードでは結果的にこれが並ぶことになります。
数値が $1$ 増えると $10$ 文字増えることになるので、最適化をしていかないとどんどん長くなってしまいます。

Hello, World!

Hello, Worldはどうなるのでしょうか。
以降、簡単のためリストを[a_0, a_1, ...,a_{n-1}]の形で表し、ペアを(x, y)で表します。
それぞれラムダ計算の式で書くと、(CONS a_0 (CONS a_1 (... (CONS a_{n-1} NIL)...)))、CONS x yを表します。
Hello, Worldは入力を受け取って、"Hello, World!"に対応するリストを返せば良いです。
つまり、リストの中身は、[72, 101, 108, 108, 111, 44, 32, 87, 111, 114, 108, 100, 33, 256]とすれば良いです（最後にEOFを表す256を追加していることに注意）。
つまり、ラムダ計算式で書くと、

λx. [72, 101, 108, 108, 111, 44, 32, 87, 111, 114, 108, 100, 33, 256]

です。
いくつか数値の最適化を入れてLazy Kのコードにすると、

`k````s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk```si``s`s``s`kski``s``s`kski````s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk```s`s``s`kski``s``s`ksk``s``s`kski````s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk```s`s``s`kski``s``s`ksk``s``s`kski````s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk```s`s``s`kski``s``s`ksk``s``s`kski````s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk```s`s``s`kski``s``s`ksk``s``s`kski````s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk```s``s`k`s``s`ksk``siii``s``s`kski````s``s`ks``s`kk``s`ks``s`k`sik`kk```s``s`k`s``s`ksk``siii``s``s`kski````s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk```s`s``s`kski``s``s`ksk``s``s`kski````s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk```s`s``s`kski``s``s`ksk``s``s`kski````s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk```s`s``s`kski``s``s`ksk``s``s`kski````s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk```s`s``s`kski``s``s`ksk``s``s`kski````s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk```s`s``s`kski``s``s`ksk``s``s`kski````s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk```s``s`k`s``s`ksk``siii``s``s`kski````s``s`ks``s`kk``s`ks``s`k`sik`kk```sii```sii``s``s`kski`kk

とかになります（3367文字、そのうち``s``s`kskは263回）。
100だけ先に計算しておくと(λx. (λh. [...]) (2 10))

`k```s`k```s``s`ks``s`kk``s`ks``s`k`sik`kk```s``s``s`ks`s`k``s`ksk``s`k`sik`s``s`ksk``s``s`kski``s``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk`s``s`ksk``s``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk```si`k`s``s`ksk```s`s``s`kski``s``s`kski``s``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk```si`k`s``s`ksk```s`s``s`kski``s``s`kski``s``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s`k`s``s`ksk```si`k`s``s`ksk``s``s`ksk```si`s``s`ksk``s``s`kski``s`k```s``s`ks``s`kk``s`ks``s`k`sik`kk````si`k`s``s`ksk```s``s`k`s``s`ksk``siii``s``s`kski```s``s`k``s`ksk`s``s`ksk``sii``s``s`kski``s`k```s``s`ks``s`kk``s`ks``s`k`sik`kk```s``s`k`s``s`ksk``siii``s``s`kski``s`k```s``s`ks``s`kk``s`ks``s`k`sik`kk````si`k`s``s`ksk```s`s``s`kski``s``s`ksk``s``s`kski``s``s`ksk``s``s`ksk```sii``s``s`kski``s``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s`k`s``s`ksk```si`k`s``s`ksk``s``s`ksk```si`s``s`ksk``s``s`kski``s``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s`k`s``s`ksk``s`k`s``s`ksk``s``si`k`s``s`ksk`k```s``s`k``s`ksk`s``s`ksk``sii``s``s`kski``s``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``si`k`s``s`ksk`k```s`s``s`kski``s``s`kski`k````s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk```s`s``s`kski``s``s`ksk``s``s`kski````s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk```s``s`k`s``s`ksk``siii``s``s`kski````s``s`ks``s`kk``s`ks``s`k`sik`kk```sii```sii``s``s`kski`kk```s``s`kski``s``s`ksk```si`s``s`ksk``s``s`kski

となり、半分以下になりました（1521文字、そのうち``s``s`kskは44回）。
おそらくもっと短くできます。
Hello, Worldが大変な言語はいくつかありますが、その中の一つだと思います。

足し算

まずは、一桁の数値を改行区切りで2つ受け取って足し算をして出力するプログラムを書いてみましょう。
今回は、答えも1桁であるという制約の元行います。
つまり、入力

input

3
5

に対し、期待する出力は、

output

です。
入力列からインデックス0と2をとってくると、それぞれが数値を表す文字コードになっています。
'0'はASCIIコード48なので、それらを足したものから48を引くと、求める出力になっています。
ということで、

λx. [SUB (PLUS (CAR x) (NTH x 2)) 48, 256]

は求めるラムダ計算式になるでしょう。
Lazy Kコードに直すと、

``s``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`k``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik``s``s`k``si`k`s``s`ksk``si`kk``s``s`k`s`k``si`kk``s`k`s``si`k``si`k`kik`k``s``s`kski`k```s``s`k``s`ksk`s``s`ksk``s``siii``s``s`kski`k````s``s`ks``s`kk``s`ks``s`k`sik`kk```sii```sii``s``s`kski`kk

これを実行すると、確かに期待動作通りに動きます。

足し算（改）

次に1桁に限らず、2つの数値を改行区切りで渡して足し算の答えを返すプログラムを書いてみましょう。
例えば、次のような入力をします。

input

17
46

期待する出力は以下の通りです。

output

まず、入力文字列を数値に直す必要があります。
'0'はASCIIコード48なので、数値の文字列を数値に変える関数は次のように書けます。

STRING_TO_INT := 
  λl. Y (
    λf. λl. IF (ISNIL l) 0 (
      PLUS 
      (MULT 10 (f (CDR l))) 
      (SUB (CAR l) 48)
    )
  ) (REVERSE l)

この関数では

まずリストを反転する (REVERSE l)
一番後ろまで送って $0$ を返す (IF (ISNIL l) 0 (...))
後ろから「それまでの答えに $10$ をかけてリストの数値をたす」を繰り返す。（PLUS (MULT 10 (f (CDR l))) (SUB (CAR l) 48)）

という操作を行います。
逆に数値を文字列に直す必要もあります。

INT_TO_STRING := 
  λn. REVERSE (
    Y (
      λf. λn. IF (ISZERO n) NIL (
        CONS 
        (PLUS (MOD n 10) 48) 
        (f (DIV n 10))
      )
    ) n
  )

ほとんどSTRING_TO_INTの逆操作になっています。

$10$ を割っていって、 $0$ まで送って NIL を返す (IF (ISZERO n) NIL (...))
後ろから「それまでの答えの前に $10$ で割ったあまりをリストの前につけたす」を繰り返す。（CONS (PLUS (MOD n 10) 48) (f (DIV n 10))）
リストを反転する (REVERSE (...))

これで必要な関数は揃いました。
構成していきます。

λx. APPEND (
  INT_TO_STRING (
    CAR (
      2 (
        λp. (
          λa. λx. (
            λp. (PLUS a (STRING_TO_INT (CAR p)), CDR p)
            ) (Y (
              λf. λx. 
                IF 
                (GE (CAR x) 16) 
                ((λp. ((CAR x, CAR p), CDR p)) (f (CDR x))) 
                (NIL, CDR x)
            ) x)
        ) (CAR p) (CDR p)
      ) (0, x)
    )
  )
) [256]

Lazy Kコードに直します。

``s``s`k```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`ki``si`k`k`k`ki``s`k`s``s`ks``s`kk``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``si`kk``s``s`ksk`k``si`k`ki``s`k``s`k```ss`k`k`kk```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`ki``si`k`k`k`ki``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``si`k`ki`k``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``si`kk```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`k``si`k`s``s`ksk``s```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s``s`ks``s`k`s`ks``s`k`s``s`ks``s`k`s`ki``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikk``s``s`ks``s`k`s`ks``s``s`ks``s`kk``s`ksk`k``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik`k`ki`kk`k``s``s`ksk```si`s``s`ksk``s``s`kski`k```s``s`k``s`ksk`s``s`ksk``s``siii``s``s`kski``s`k`s``s``s`ki``s``s`k`s``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikkk`k```si`s``s`ksk``s``s`kski`k`kk``s``s`ksk`k``s```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s``s`ks``s`k`s`ks``s`k`s``s`ks``s`k`s`ki``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikk``s`k`s`k`s`k`s``s`ksk``s``s`ks``s`k`s`ks``s``s`ks``s`kk``s`ksk`k``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik`k`ki`k`k`k`ki`k``s``s`ksk```si`s``s`ksk``s``s`kski``s`k``si`kk``s`k```s``s`kski``s``s`k``s``s`ks``s`kk``s``s`ks``s`k`s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ks``s`kk``si`k`s``s`ksk`k``s`k``s`k```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`ki``si`k`k`k`ki`k`ki``s`k`s``s`k``si`k`s``s`ksk``s``s`k``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik``si`kk`k```s``s`k``s`ksk`s``s`ksk``s``siii``s``s`kski``s`k`s`k```s`ksk``s``s`ksk```si`s``s`ksk``s``s`kski``s``s`ksk`k``si`k`ki```ss`k`k`kk```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`ki``si`k`k`k`ki``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``si`k`ki`k``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``si`kk``si`kk`k``si`k`ki`k```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s``s`ks``s`k`s``s`ki``s``s`k``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikk``si`kk`k```s``siii``s``s`kski``s`k`s``s``s`ks``s`k`s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ks``s`kk``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``si`kk`k``si`kk`k``si`k`ki``s``s`ksk`k``si`k`ki`k``s`k```s``s`ks``s`kk``s`ks``s`k`sik`kk`kk``si`k`ki``si`kk``si`k`ki```s``s`ks``s`kk``s`ks``s`k`sik`kk`ki`k````s``s`ks``s`kk``s`ks``s`k`sik`kk```sii```sii``s``s`kski`kk

これに先の入力を入れると確かに期待する出力が得られます。

式の説明は以下の通りです。

ペア(0, 入力)を作る ((0, x))
数値を改行区切りで分ける(Y (λf. λx. IF (GE (CAR x) 16) ((λp. ((CAR x, CAR p), CDR p)) (f (CDR x))) (NIL, CDR x)) x)
- 詳細は以下の通り。
  1. 改行があるまで送ってペア(NIL, それ以降の文字列)を作る ((NIL, CDR x))
  2. ペアに今見ている文字列を加えていく ((λp. ((CAR x, CAR p), CDR p)) (f (CDR x)))
- 改行(LF)の文字コードは10なので、短くかける16以上かそうでないかで区切る
- もし空白も入れたいなら32で区切る(空白の文字コードは32)
- ペアとして(数値を表す文字列,それ以降の文字列)を返す
元のペアのCARに現在の数値を足し、CDRをそれ以降の文字列に変更する((PLUS a (STRING_TO_INT (CAR p)), CDR p))
2回繰り返す (2 (...) (0, x))
CARを文字列に直して256を末尾に加えて出力 (APPEND (INT_TO_STRING (CAR (...))) [256])

足し算（改２）

先ほど足し算を実装できましたが、問題があります。
例えば以下の入力を与えます。

input

324
733

出力は以下のようになります。

output

出力はあっていますが、問題は実行時間です。
3桁同士の足し算でも数秒かかってしまいます（自分の環境では5秒程度）。
他の方法を考える必要があります。
そこで、数値を10進数のまま桁の逆順でリスト化してみます。
例えば324なら[4,2,3]というリストを作るということです。
こうすることで、各桁ごとに最大値が9になるので実行時間を短縮することができます。

（補足）

2進数とかにしても良いですが、入出力との整合性のため10進数のままの方がおそらく楽（結局2進数に直すのは面倒）
逆順にする必然性はないですが、実装の時に逆順の方がおそらく楽

まずは、数値を表す文字列をリストにする関数を作ります。
nはリストの長さを表します。
nは数値の桁数以上である必要があり、桁数より大きい場合には0埋めをします。

STRING_TO_N-INTLIST :=
  λx. λn. Y (λf. λx. λn.
    IF
    (ISNIL x)
    (n (λl. (0, l)) NIL)
    (PRED (CAR x) 48, f (CDR x) (PRED n))
  ) (REVERSE x) n

nを導入したのは、計算をするときに桁数がそろえてあった方が楽だからです。
また、繰り上がり時に余計な心配をする必要がなくなるからです。

逆方向の関数も作っておきます。

N-INTLIST_TO_STRING :=
  λl. 
    IF
    (Y (λf. λl. 
      IF 
      (ISNIL l)
      TRUE
      (
        IF
        (ISZERO (CAR l))
        (f (CDR l))
        FALSE
      )
    ))
    [48]
    (Y (
      λf. λl.
        IF
        (ISNIL x)
        NIL
        (PLUS (CAR x) 48, f (CDR x) (PRED n))
      ) 
      (Y (
        λf. λl. 
          IF 
          (ISNIL l)
          TRUE
          (
            IF
            (ISZERO (CAR l))
            (f (CDR l))
            l
          )
      ) (REVERSE x))
    )

余計な0を除く必要があるので、REVERSEした後に0を除く処理をしているのと、元が0の場合に'0'を返す処理を行っています。

次に、この数値リストに1をたす関数を作ります。

SUCC_N-INTLIST :=
  Y (λf. λl.
    IF
    (GE (CAR l) 9)
    (0, f (CDR l))
    (SUCC (CAR l), CDR l)
  )

繰り上がりを丁寧に行えば良いです。

さらに、リスト同士の足し算を行う必要があります。

PLUS_N-INTLIST :=
  Y (λf. λx. λy. 
    IF
    (ISNIL y)
    x
    (
      (λa.
        IF 
        (GT a 9)
        (SUB a 10, f (SUCC_N-INTLIST (CDR x)) (CDR y))
        (a, f (CDR x) (CDR y))
      ) (PLUS (CAR x) (CAR y))
    )
  )

一応(xの長さ) >= (yの長さ)であれば動きますが、同じであることを想定しています。
これも繰り上がりをうまくやれば問題ありません。

ということで構築します。

λx. APPEND (
  N-INTLIST_TO_STRING (
    CAR (
      2 (
        λp. (
          λa. λx. (
            λp. (PLUS_N-INTLIST a (STRING_TO_N-INTLIST (CAR p) 64), CDR p)
            ) (Y (
              λf. λx. 
                IF 
                (GE (CAR x) 16) 
                ((λp. ((CAR x, CAR p), CDR p)) (f (CDR x))) 
                (NIL, CDR x)
            ) x)
        ) (CAR p) (CDR p)
      ) (64 (λl. (0, l)) NIL, x)
    )
  )
) [256]

ほぼINTをN-INTLISTに変えただけです。
64桁まで実行できます。

Lazy Kコードに直すと

``s``s`k```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`ki``si`k`k`k`ki``s`k`s``s`ks``s`kk``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``si`kk``s``s`ksk`k``si`k`ki``s`k``s``s``s`ki```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`ki``si`k`k`k`ki`kk``s``s`ks``s`k`s``s`ki``s`k``s``si`k`k`ki`kk``si`kk``s``s`ksk`k``si`k`ki`k`k`ki`k````s``s`ks``s`kk``s`ks``s`k`sik`kk```s``s`k``s`ksk`s``s`ksk``s``siii``s``s`kski`kk``s`k```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`ki``si`k`k`k`ki`k`kk``s`k`s``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`k``si`k`s``s`ksk``si`kk`k```s``s`k``s`ksk`s``s`ksk``s``siii``s``s`kski``s``s`ksk`k``si`k`ki``s``s`k``s`k`s``s`k``s``s``s`ksk`k``sii``s``s`ksk`k``sii``s``s`ks``s`k`s`ks``s``s`ks``s`kk``s`ks``s`k`s`ki``s`k`s``s`k``s``s`ks``s`k`s`k``s``s`ksi`k`k`ki``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikk``s`k`s``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikkk``si`kkk`k``s``s`ksk`k``si`k`ki`k`kik```ss`k`k`kk```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`ki``si`k`k`k`ki``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``si`k`ki`k``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``si`kk`k`ki``s`k``si`kk``s`k```s``s`kski``s``s`k``s``s`ks``s`kk``s``s`ks``s`k`s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ks``s`kk```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`k`s``s`ki``si`k`k`k`kik``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`k`s`ks``s`k`s`k`s`k`s``s`ki``s``s`k`s`k``s``si`k`ki`kk``s`k`s``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikkk`k```si`s``s`ksk``s``s`kski``s`k`s`k`s`k`s``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik`k``s``s`ksk```si`s``s`ksk``s``s`kski``s`k`s`k`s`kk``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s``s`ks``s`k`s``s`ki``s``s`k``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikk``s`k`s``s`ksk``si`kk`k``s``s`ksk```si`s``s`ksk``s``s`kski``s`k`s`k```s``s`ks``s`kk``s`ks``s`k`sik`kk`ki``s``s`ksk`k``si`k`ki`k``s``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s`k`s``s`ksk``si`kk``si`k`ki``si`k`ki`k`k``si`k`ki``s`k`s`k`s`k`s``s``s`ks``s`kk``s`ks``s`k`sik`kk``s`k`s`k`s`kk``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``si`k`ki`k`k``si`k`ki`k``s``s`ks``s`kk``s`k``si`k`s``s`ksk``si`kk`k``si`kk`k``s``s`k``s`k```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s``s`ks``s`kk``s`ki``si`k`k`k`ki`k``s``si`k```s``s`ks``s`kk``s`ks``s`k`sik`kk`ki`k`kk``s`k`s``s`ks``s`kk``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`k``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik``si`kk`k```s``s`k``s`ksk`s``s`ksk``s``siii``s``s`kski``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``si`k`ki`k`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`ki```ss`k`k`kk```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`ki``si`k`k`k`ki``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``si`k`ki`k``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``si`kk``si`kk`k```si``s`s``s`kski``s``s`kski`k``si`k`ki`k```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s``s`ks``s`k`s``s`ki``s``s`k``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikk``si`kk`k```s``siii``s``s`kski``s`k`s``s``s`ks``s`k`s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ks``s`kk``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``si`kk`k``si`kk`k``si`k`ki``s``s`ksk`k``si`k`ki`k``s`k```s``s`ks``s`kk``s`ks``s`k`sik`kk`kk``si`k`ki``si`kk``si`k`ki```s``s`ks``s`kk``s`ks``s`k`sik`kk`````si``s`s``s`kski``s``s`kski```s``s`ks``s`kk``s`ks``s`k`sik`kk`ki`kk`k````s``s`ks``s`kk``s`ks``s`k`sik`kk```sii```sii``s``s`kski`kk

これを実行すると、先ほどは数秒かかっていた3桁の足し算を数ミリ秒で実行できます。
さらに、桁数がもっと大きくなっても(答えが64桁以下なら)一瞬で終わります。
このように、実行時間を気にするとなるといくつか工夫をしていくことが必要になってきます。

終わりに

今回は、実際にLazy Kのプログラムを書いていきました。
Lazy Kはチューリング完全な言語なので、理論上は計算可能な計算はすべてできます。
実際に書いてみると面白いと思います。
ありがとうございました。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

Lazy K 入門（4） Lazy K プログラムを書いてみる

はじめに

Echo プログラム

Lazy K での数値の表し方

Hello, World!

足し算

足し算（改）

足し算（改２）

終わりに

Lazy K 入門（4）　Lazy K プログラムを書いてみる