Lazy K is 何

入出力


lazy kでhello world書いた

ignore_input

#define ignore_input k
  • code頭に置いて、入力を無視する
  • k PROGRAM INPUT -> PROGRAM

簡単な関数

#define id (skk)
#define true k
#define false (ki)
#define zero false
#define one id

何とか書ける

car cdr / head tail

  • car list = list true
  • cdr list = list false

しかし

\ x y . y x

が書けない

とりあえず文字列を持ってきてtrue/falseを試してみる

Hello worldプログラムの一覧 # Lazy_K - Wikipedia

#define helloworld ``s``si`k```s``sss```s``s`ks`ssi``ss`ki``s`ksk`k``s``si`k` \
    ``ss``s``ss`ki``ss```ss`ss``ss`ki``s`ksk`k``s``si`k```s``si``ss``ss`ki``` \
    ss`s``sss``ss`ki``s`ksk`k``s``si`k```s``si``ss``ss`ki```ss`s``sss``ss`ki` \
    `s`ksk`k``s``si`k```ss``s``sss``ss```ss`ss``ss`ki``s`ksk`k``s``si`k```ss` \
    `ss``s``sss``s``sss``ss`ki``s`ksk`k``s``si`k```s``ss```ssi``ss`ki``ss`ki` \
    `s`ksk`k``s``si`k```s``si``ss``s``sss``ss`ki``ss```ss``ssi``ss`ki``s`ksk` \
    k``s``si`k```ss``s``sss``ss```ss`ss``ss`ki``s`ksk`k``s``si`k```ss``ss``ss \
    ``ss``s``sss``ss```ss`ss``ss`ki``s`ksk`k``s``si`k```s``si``ss``ss`ki```ss \
    `s``sss``ss`ki``s`ksk`k``s``si`k```s``ss`ki``ss```ss`ss``ss`ki``s`ksk`k`` \
    s``si`k```ss```ss`ss``ss`ki``s`ksk`k`k```sii```sii``s``s`kski
ignore_input (helloworld false)
##=> ello, world

動く

T[]変換

\ x y. y x

wikipediaの例と同じだけど、自分でも変換する

#define rev (s (k (s i)) k)

car / cdr

\ x y. y x ができたので作れるように

#define car (rev true)
#define cdr (rev false)
ignore_input (cdr helloworld)
##=> ello, world

succ

  • \ n f x. f (n f x) も変換
  • 結構頑張る
#define succ (s (k (s (s (k s) k))) (s (s (k s) k) (k i)))

cons

  • succだけあっても使えないのでcons
  • lazy-kはスコットエンコーディング
  • \ x y z . z x y
#define cons (s (s (k s) (s (k k) (s (k s) (s (k (s i)) (s (k k) i))))) (k (s (k k) i)))
#define cons (s (s (k s) (s (k k) (s (k s) (s (k (s i)) k)))) (k k))
##=> Iello, world

演算

plus = \ m n. m succ n
mult = \ m n f. m (n f)
pow = \ m n n (mult m) one # 不要
#define plus (s (s (k s) (s (k k) (s i (k succ)))) (k i))
#define mult (s (s (k s) (s (k k) (s (k s) k))) (k i))
#define pow (s (s (k s) (s (k (s i)) (s (k k) mult))) (k (k one)))
  • 手作業で丁寧に変換

hello world

出力すべき数を確認する

$ ghc -e 'print $ map ord "hello world"'
[104,101,108,108,111,32,119,111,114,108,100]

$ ghc -e 'print $ map (($ "") . showIntAtBase 2 intToDigit . ord) "hello world"'
["1101000","1100101","1101100","1101100","1101111","100000","1110111","1101111","1110010","1101100","1100100"]

数字を定義

#define two (s (s (k s) k) i) # 無駄な変換
#define double (mult two)
#define four (double two)
#define eight (double four)
#define sixteen (double eight)
#define thirtytwo (double sixteen)
#define sixtyfour (double thirtytwo)
#define eof (pow four four)
  • lazy-kは256をもってeofとする
  • 2進数万歳
  • 2は変換しておいた

完成

ignore_input
(cons (plus sixtyfour (plus thirtytwo eight)) # h
(cons (plus sixtyfour (plus thirtytwo (plus four one))) # e
(cons (plus sixtyfour (plus thirtytwo (plus eight four))) # l
(cons (plus sixtyfour (plus thirtytwo (plus eight four))) # l
(cons (plus sixtyfour (plus thirtytwo (plus eight (plus four (plus two one))))) # o
(cons thirtytwo # ' '
(cons (plus sixtyfour (plus thirtytwo (plus sixteen (plus four (plus two one))))) # w
(cons (plus sixtyfour (plus thirtytwo (plus eight (plus four (plus two one))))) # o
(cons (plus sixtyfour (plus thirtytwo (plus sixteen two))) # r
(cons (plus sixtyfour (plus thirtytwo (plus eight four))) # l
(cons (plus sixtyfour (plus thirtytwo four)) # e
(cons eof k))))))))))))
$ gcc -E a.lazy.cpp > a.lazy && echo hoge | ./lazy a.lazy
hello world

lazy kでhello world書いた

2014/04/11
twoの定義が抜けてたので修正