ããã«ã¡ã¯ãã¢ããã¡ã¯ãšã³ãžãã¢ã® id:knj-mf ã§ãã ä»å㯠TypeScript ã®åã¬ãã«ããã°ã©ãã³ã°ã§ã¡ãã£ãšé¢çœããã®ãäœã£ãã®ã§ç޹ä»ããããšæããŸãã äœãäœã£ãã®ïŒ TypeScript ã®åã¬ãã«ããã°ã©ãã³ã°ã¯ãäºæ³ã«åããŠæ§ã
ãªãã®ãå®è£
ã§ããŠããŸãããšã§æåã ã£ããããŸãã type-challenges ã®ããã«ããããã¯æ®éã®ããã°ã©ãã³ã°ã§å®è£
ãããã®ã§ã¯ïŒããšæã£ãŠããŸããããªãã®ãŸã§å®è£
ã§ããŠããŸããŸããããã§ãäœã£ãŠã¿ããã®ãäžèšã«ãªããŸãã æ©éãåäœã玹ä»ããŸãããã®ãã㪠Brainf**k ããã°ã©ã ã®æåååã⊠ãã®ããã«ãåèšç®äžã§è§£éãããŠããŸãïŒãšãããã®ã§ãã ããçšåºŠã®åœ¢ã«ãªããã®ã¯ã§ããã®ã§ããã®èšäºã§ã¯ãåã¬ãã«ããã°ã©ãã³ã°ãšæžãå³ã®è¿ã (å人差ããããŸã) Haskell å®è£
ãšç
§ãããªãããã©ã®ããã«èããŠãã®ãåããå®è£
ããŠãã£ãã®ãã玹ä»ããŸãã cwd-k2/bf-in-type ã®ãªããžã㪠ã«å®è£
ãããã®ã§ãæ°ã«ãªãæ¹ã¯æå
ã§åäœãå®è£
ãèŠãŠã¿ãŠãã ããã Brainf**kïŒ ãã£ã 8 ã€ã®åœä»€ãããªãé£èªããã°ã©ãã³ã°èšèªã§ããèšèªã®ä»æ§ãšããŠããªãåçŽæå¿«ã§ã¯ãããŸããããã¥ãŒãªã³ã°å®å
šãšããŠç¥ãããŠããŸãã(ã¡ãã£ãšäŒæ¥ã®å
¬åŒããã°ã«ã¯èŒãã¥ãã衚èšãå«ãã®ã§ãä»å㯠** ãšãã颚ã«äŒããããŠããã ããŸãâŠ) èŠçŽ ãšããŠã次㮠4 ã€ã®ãã®ãæã¡ãŸãã èŠçŽ å
容 ããã°ã©ã ããŒã å®è¡ããããã°ã©ã å ã¡ã¢ãªããŒã å€ãèšé²ããã»ã«ã®å ããã°ã©ã ãã€ã³ã¿ çŸåšåç
§ããŠããããã°ã©ã åœä»€åäžã®äœçœ® ã¡ã¢ãªãã€ã³ã¿ çŸåšåç
§ããŠããã¡ã¢ãªããŒãã®äœçœ® 8 ã€ã®åœä»€ã¯æ¬¡ã®ãããªåçŽãªãã®ã§ãã åœä»€ å
容 > ã¡ã¢ãªãã€ã³ã¿ãã€ã³ã¯ãªã¡ã³ãïŒæ¬¡ã®ã»ã«ãžïŒ < ã¡ã¢ãªãã€ã³ã¿ããã¯ãªã¡ã³ãïŒåã®ã»ã«ãžïŒ + çŸåšã»ã«ã®å€ãã€ã³ã¯ãªã¡ã³ã - çŸåšã»ã«ã®å€ããã¯ãªã¡ã³ã . çŸåšã»ã«ã®å€ã ASCII æåãšããŠåºå , 1 ãã€ãèªã¿èŸŒã¿ãçŸåšã»ã«ãžæ ŒçŽ [ çŸåšã»ã«ã 0 ãªãã察å¿ãã ] ã®çŽåŸãžãžã£ã³ã ] çŸåšã»ã«ã 0 ã§ãªããã°ã察å¿ãã [ ã®çŽåŸãžãžã£ã³ã ãã£ãããããã°ã©ã ããŒãäžã«èšèŒããã 8 ã€ã®åœä»€ã®åãé æ¬¡å®è¡ããªããã¡ã¢ãªããŒãã®å€ãæžãæãã€ã€ãé©å® I/O ããŠãã圢ã®ããã°ã©ãã³ã°èšèªã«ãªããŸãã å®éã® Brainf**k ããã°ã©ã ãã®ãã®ã¯ãŸã£ããå®çšæ§ããªãã®ã§ããããã®ç°¡åãªåœä»€ã»ãããããªãèšèªåŠçç³»ã®å®è£
ã«ã¯æè²ç䟡å€ããããŸããçµæ§æžããŠã¿ãããšããããšãããšã³ãžãã¢ã®æ¹ãå€ãã®ã§ã¯ãªãã§ããããã TypeScript ã®åã¬ãã«ããã°ã©ãã³ã° ãšããã§ãTypeScript ã«ã¯ (TypeScript ã«éããŸããã) åã¬ãã«ããã°ã©ãã³ã°ããããŸããæ¬åœã«åçŽãªäŸã ãšãäžèšã®ãããªãã®ã§ãã type ExtendsObject < T > = T extends object ? true : false ãããäœãããŠããã®ããšãããšãåãã§ãã¯ã®éã«å®æœãããåèšç®ãå®è£
ããŠãããšããããšã§ããäžèšã®ãããªæ¡ä»¶åå²ãªã©ã®ããžãã¯ãåã¬ãã«ã§è§£æ±ºãããŠããŸããšããããšã§ããã ãã®åã¬ãã«ããã°ã©ãã³ã°ãªã®ã§ããã衚çŸåã¯ããŠããããã¥ãŒãªã³ã°å®å
šãªç³»ã«ãªã£ãŠããŸã£ãŠãããšã®ãã£ã±ãã®è©å€ã§ãã åããåãæ°ãã«èšç®ã§ããŠããŸããšããããšã¯âŠ æ¥œããããã°ã©ãã³ã°ã®æéã®å§ãŸãã§ããã å®è£
æ¹é é·ããªã£ãŠããŸãã®ã§ã以éã§ã¯ Brainf**k ã BF ãšèšèŒããããšã«ããŸãã BF åŠçç³»ãåã¬ãã«ã«èœãšã蟌ãã«ããã£ãŠã次㮠4 ã€ã®èŠçŽ ã«åããŠèããŸãã ããŒãæ§é äœ ( Tape ) â ã¡ã¢ãªã»ããã°ã©ã ãå
±éããŠè¡šçŸããããŒã¿æ§é çŸåšäœçœ®ãæã¡ã€ã€ãååŸã«ç§»åããèœåãæã€ è©äŸ¡åš ( Runner ) â ã¡ã¢ãªããŒããšããã°ã©ã ããŒããæããå®è¡ç¶æ
ã¡ã¢ãªãå€åããã€ã€ããã°ã©ã ãã€ã³ã¿ãç§»åãããããåæã«æ±ã ã¢ã¯ã·ã§ã³ ( Action ) â 1 ã¹ãããå®è¡ã®çµæãšããŠå€çã«èŠæ±ãã广 (ãªã«ãããªã / å
¥å / åºå / çµäº) è©äŸ¡ã«ãŒã ( Exec ) â ã¢ã¯ã·ã§ã³ãè§£éããŠè©äŸ¡åšãåããå
¥åãæ¶è²»ãã€ã€åºåãèç©ããã¡ã€ã³ã«ãŒã åã¬ãã«ããã°ã©ãã³ã°ã§ã¯å¯äœçšãçŽ çŽã«æžããªããããå
¥åºåããã¢ã¯ã·ã§ã³åããšããŠããŒã¿ã«èœãšããŠãããå€åŽã®ã«ãŒãã§ãããè§£éãã圢ã«ããã®ããã€ã³ãã§ãã以éããã®é ã§åèŠçŽ ã®å®è£
ãèŠãŠãããŸãã ãŸããé©å®åèå®è£
ãšã㊠Haskell ã®å®è£
ãåãããŠç€ºããŠããŸãã TypeScript å®è£
㯠v5.4 以éã§åäœç¢ºèªããŠããŸãã å®è£
äžã®å¶çŽ å¶çŽãšããŠãå®è£
ã¬ãã«ã«å¹ããŠãããã®ããããŸããæ°å€ã§ã®æŒç®ãæ°å€âæåã®å€æãåºæ¬çã«ã§ããªãããšãããã®ã§ããäžå¯èœã§ã¯ãªãã§ãããã¿ãã« (åã¬ãã«é
å) ã® length ãåããããªå®è£
ã«ãªããã¡ãªã®ã§ãŸãããã©ããªããŸãã ä»å㯠ASCII ç¯å²ã§ã€ã³ã¯ãªã¡ã³ãã»ãã¯ãªã¡ã³ããèããã ããªã®ã§ãæ°åãã§èª€éåãããšãã§ããŸãã NumToCharMap[65] ã®ããã«åç
§ãããš 'A' ãšããåã«è§£æ±ºãããããšããããããå®çŸ©ããŸããã æ°å€æå倿ãã€ã³ã¯ãªã¡ã³ãã»ãã¯ãªã¡ã³ããããã®å®è£
export type NumToCharMap = [ '\x00' , '\x01' , '\x02' , '\x03' , '\x04' , '\x05' , '\x06' , '\x07' , '\x08' , '\x09' , '\x0A' , '\x0B' , '\x0C' , '\x0D' , '\x0E' , '\x0F' , '\x10' , '\x11' , '\x12' , '\x13' , '\x14' , '\x15' , '\x16' , '\x17' , '\x18' , '\x19' , '\x1A' , '\x1B' , '\x1C' , '\x1D' , '\x1E' , '\x1F' , '\x20' , '\x21' , '\x22' , '\x23' , '\x24' , '\x25' , '\x26' , '\x27' , '\x28' , '\x29' , '\x2A' , '\x2B' , '\x2C' , '\x2D' , '\x2E' , '\x2F' , '\x30' , '\x31' , '\x32' , '\x33' , '\x34' , '\x35' , '\x36' , '\x37' , '\x38' , '\x39' , '\x3A' , '\x3B' , '\x3C' , '\x3D' , '\x3E' , '\x3F' , '\x40' , '\x41' , '\x42' , '\x43' , '\x44' , '\x45' , '\x46' , '\x47' , '\x48' , '\x49' , '\x4A' , '\x4B' , '\x4C' , '\x4D' , '\x4E' , '\x4F' , '\x50' , '\x51' , '\x52' , '\x53' , '\x54' , '\x55' , '\x56' , '\x57' , '\x58' , '\x59' , '\x5A' , '\x5B' , '\x5C' , '\x5D' , '\x5E' , '\x5F' , '\x60' , '\x61' , '\x62' , '\x63' , '\x64' , '\x65' , '\x66' , '\x67' , '\x68' , '\x69' , '\x6A' , '\x6B' , '\x6C' , '\x6D' , '\x6E' , '\x6F' , '\x70' , '\x71' , '\x72' , '\x73' , '\x74' , '\x75' , '\x76' , '\x77' , '\x78' , '\x79' , '\x7A' , '\x7B' , '\x7C' , '\x7D' , '\x7E' , '\x7F' , ] & { [ i: number ] : ' \x00 ' } ; export type CharToNumMap = { '\x00' : 0 x00 , '\x01' : 0 x01 , '\x02' : 0 x02 , '\x03' : 0 x03 , '\x04' : 0 x04 , '\x05' : 0 x05 , '\x06' : 0 x06 , '\x07' : 0 x07 , '\x08' : 0 x08 , '\x09' : 0 x09 , '\x0A' : 0 x0A , '\x0B' : 0 x0B , '\x0C' : 0 x0C , '\x0D' : 0 x0D , '\x0E' : 0 x0E , '\x0F' : 0 x0F , '\x10' : 0 x10 , '\x11' : 0 x11 , '\x12' : 0 x12 , '\x13' : 0 x13 , '\x14' : 0 x14 , '\x15' : 0 x15 , '\x16' : 0 x16 , '\x17' : 0 x17 , '\x18' : 0 x18 , '\x19' : 0 x19 , '\x1A' : 0 x1A , '\x1B' : 0 x1B , '\x1C' : 0 x1C , '\x1D' : 0 x1D , '\x1E' : 0 x1E , '\x1F' : 0 x1F , '\x20' : 0 x20 , '\x21' : 0 x21 , '\x22' : 0 x22 , '\x23' : 0 x23 , '\x24' : 0 x24 , '\x25' : 0 x25 , '\x26' : 0 x26 , '\x27' : 0 x27 , '\x28' : 0 x28 , '\x29' : 0 x29 , '\x2A' : 0 x2A , '\x2B' : 0 x2B , '\x2C' : 0 x2C , '\x2D' : 0 x2D , '\x2E' : 0 x2E , '\x2F' : 0 x2F , '\x30' : 0 x30 , '\x31' : 0 x31 , '\x32' : 0 x32 , '\x33' : 0 x33 , '\x34' : 0 x34 , '\x35' : 0 x35 , '\x36' : 0 x36 , '\x37' : 0 x37 , '\x38' : 0 x38 , '\x39' : 0 x39 , '\x3A' : 0 x3A , '\x3B' : 0 x3B , '\x3C' : 0 x3C , '\x3D' : 0 x3D , '\x3E' : 0 x3E , '\x3F' : 0 x3F , '\x40' : 0 x40 , '\x41' : 0 x41 , '\x42' : 0 x42 , '\x43' : 0 x43 , '\x44' : 0 x44 , '\x45' : 0 x45 , '\x46' : 0 x46 , '\x47' : 0 x47 , '\x48' : 0 x48 , '\x49' : 0 x49 , '\x4A' : 0 x4A , '\x4B' : 0 x4B , '\x4C' : 0 x4C , '\x4D' : 0 x4D , '\x4E' : 0 x4E , '\x4F' : 0 x4F , '\x50' : 0 x50 , '\x51' : 0 x51 , '\x52' : 0 x52 , '\x53' : 0 x53 , '\x54' : 0 x54 , '\x55' : 0 x55 , '\x56' : 0 x56 , '\x57' : 0 x57 , '\x58' : 0 x58 , '\x59' : 0 x59 , '\x5A' : 0 x5A , '\x5B' : 0 x5B , '\x5C' : 0 x5C , '\x5D' : 0 x5D , '\x5E' : 0 x5E , '\x5F' : 0 x5F , '\x60' : 0 x60 , '\x61' : 0 x61 , '\x62' : 0 x62 , '\x63' : 0 x63 , '\x64' : 0 x64 , '\x65' : 0 x65 , '\x66' : 0 x66 , '\x67' : 0 x67 , '\x68' : 0 x68 , '\x69' : 0 x69 , '\x6A' : 0 x6A , '\x6B' : 0 x6B , '\x6C' : 0 x6C , '\x6D' : 0 x6D , '\x6E' : 0 x6E , '\x6F' : 0 x6F , '\x70' : 0 x70 , '\x71' : 0 x71 , '\x72' : 0 x72 , '\x73' : 0 x73 , '\x74' : 0 x74 , '\x75' : 0 x75 , '\x76' : 0 x76 , '\x77' : 0 x77 , '\x78' : 0 x78 , '\x79' : 0 x79 , '\x7A' : 0 x7A , '\x7B' : 0 x7B , '\x7C' : 0 x7C , '\x7D' : 0 x7D , '\x7E' : 0 x7E , '\x7F' : 0 x7F , } & { [ k : string ]: 0 x00 ; } ; export type DecrementMap = [ 0 x7F , 0 x00 , 0 x01 , 0 x02 , 0 x03 , 0 x04 , 0 x05 , 0 x06 , 0 x07 , 0 x08 , 0 x09 , 0 x0A , 0 x0B , 0 x0C , 0 x0D , 0 x0E , 0 x0F , 0 x10 , 0 x11 , 0 x12 , 0 x13 , 0 x14 , 0 x15 , 0 x16 , 0 x17 , 0 x18 , 0 x19 , 0 x1A , 0 x1B , 0 x1C , 0 x1D , 0 x1E , 0 x1F , 0 x20 , 0 x21 , 0 x22 , 0 x23 , 0 x24 , 0 x25 , 0 x26 , 0 x27 , 0 x28 , 0 x29 , 0 x2A , 0 x2B , 0 x2C , 0 x2D , 0 x2E , 0 x2F , 0 x30 , 0 x31 , 0 x32 , 0 x33 , 0 x34 , 0 x35 , 0 x36 , 0 x37 , 0 x38 , 0 x39 , 0 x3A , 0 x3B , 0 x3C , 0 x3D , 0 x3E , 0 x3F , 0 x40 , 0 x41 , 0 x42 , 0 x43 , 0 x44 , 0 x45 , 0 x46 , 0 x47 , 0 x48 , 0 x49 , 0 x4A , 0 x4B , 0 x4C , 0 x4D , 0 x4E , 0 x4F , 0 x50 , 0 x51 , 0 x52 , 0 x53 , 0 x54 , 0 x55 , 0 x56 , 0 x57 , 0 x58 , 0 x59 , 0 x5A , 0 x5B , 0 x5C , 0 x5D , 0 x5E , 0 x5F , 0 x60 , 0 x61 , 0 x62 , 0 x63 , 0 x64 , 0 x65 , 0 x66 , 0 x67 , 0 x68 , 0 x69 , 0 x6A , 0 x6B , 0 x6C , 0 x6D , 0 x6E , 0 x6F , 0 x70 , 0 x71 , 0 x72 , 0 x73 , 0 x74 , 0 x75 , 0 x76 , 0 x77 , 0 x78 , 0 x79 , 0 x7A , 0 x7B , 0 x7C , 0 x7D , 0 x7E , ] & { [ i: number ] : 0x7F ; } ; export type IncrementMap = [ 0 x01 , 0 x02 , 0 x03 , 0 x04 , 0 x05 , 0 x06 , 0 x07 , 0 x08 , 0 x09 , 0 x0A , 0 x0B , 0 x0C , 0 x0D , 0 x0E , 0 x0F , 0 x10 , 0 x11 , 0 x12 , 0 x13 , 0 x14 , 0 x15 , 0 x16 , 0 x17 , 0 x18 , 0 x19 , 0 x1A , 0 x1B , 0 x1C , 0 x1D , 0 x1E , 0 x1F , 0 x20 , 0 x21 , 0 x22 , 0 x23 , 0 x24 , 0 x25 , 0 x26 , 0 x27 , 0 x28 , 0 x29 , 0 x2A , 0 x2B , 0 x2C , 0 x2D , 0 x2E , 0 x2F , 0 x30 , 0 x31 , 0 x32 , 0 x33 , 0 x34 , 0 x35 , 0 x36 , 0 x37 , 0 x38 , 0 x39 , 0 x3A , 0 x3B , 0 x3C , 0 x3D , 0 x3E , 0 x3F , 0 x40 , 0 x41 , 0 x42 , 0 x43 , 0 x44 , 0 x45 , 0 x46 , 0 x47 , 0 x48 , 0 x49 , 0 x4A , 0 x4B , 0 x4C , 0 x4D , 0 x4E , 0 x4F , 0 x50 , 0 x51 , 0 x52 , 0 x53 , 0 x54 , 0 x55 , 0 x56 , 0 x57 , 0 x58 , 0 x59 , 0 x5A , 0 x5B , 0 x5C , 0 x5D , 0 x5E , 0 x5F , 0 x60 , 0 x61 , 0 x62 , 0 x63 , 0 x64 , 0 x65 , 0 x66 , 0 x67 , 0 x68 , 0 x69 , 0 x6A , 0 x6B , 0 x6C , 0 x6D , 0 x6E , 0 x6F , 0 x70 , 0 x71 , 0 x72 , 0 x73 , 0 x74 , 0 x75 , 0 x76 , 0 x77 , 0 x78 , 0 x79 , 0 x7A , 0 x7B , 0 x7C , 0 x7D , 0 x7E , 0 x7F , 0 x00 , ] & { [ i: number ] : 0x00 ; } ; ããŒãæ§é äœ BF ã§ã¯ãã¡ã¢ãªãçšæããŠãã€ã³ã¿æäœã»ãã€ã³ã¿ãä»ããæäœãåæã«ãªã£ãŠããŸãã ãã¡ããåã¬ãã«ããã°ã©ãã³ã°ã§å¯äœçšã¯èšè¿°ãã«ããããããã€ã³ã¿åæãšãªã£ãŠããéšåãåèããåã衚çŸåã®å¥ã®åœ¢ã«çœ®ãæããå¿
èŠããããŸãã ã¡ã¢ãªãããã°ã©ã ãåãããŒãæ§é ã§æããŸããä»çç®ããŠããå€ããã®å·Šå³ã«åãç¶ããŠããæ§åãèããã®ãäžèšã®ãããªæ§é ã«ãªããŸãã ããŒãæ§é äœã®å®è£
ãã®ãããªæ§é äœã¯ãHaskell ã§ã® data 宣èšãšåããããªåœ¢ã§ãTypeScript ã®åã§ã¯ãªããžã§ã¯ãåã«ãã宣èšãã§ããŸãã data Tape a = Tape { prevs :: [a] , curr :: a , nexts :: [a] } extends unknown[] ã«ãã£ãŠåãªãé
ååã§ã¯ãªããåèŠçŽ ãç¬ç«ãã åã¬ãã«é
åãšããŠã®ã¿ãã« ãå©çšã§ããŸãã export type Tape < Hs extends unknown [], C , Ts extends unknown []> = { h : Hs c : C t : Ts } ããã§ããã€ãã®åºæ¬çãªæäœãå®çŸ©ããŠããŸããŸãããã çŸåšã®å€ã«å¯Ÿããæäœ ã€ã³ã¯ãªã¡ã³ãã»ãã¯ãªã¡ã³ã èªã¿åºããæžã蟌㿠ããŒãäžã®ç§»å çç®ããããããå·Šå³ã«ç§»åããæäœ 察å¿ãã [ , ] ãžã®ãžã£ã³ãã¯ç¹°ãè¿ãã«ãã£ãŠå®çŸãã åºæ¬æäœã®å®è£
Tape a ããæ°ãã Tape a ãäœã ( Tape a -> Tape a ) ãšãã圢ã®å®è£
ãšãªããŸãã -- | 次ã®èŠçŽ ã«ç§»å next :: Tape a -> Tape a next (Tape prevs curr (n : nexts)) = Tape (curr : prevs) n nexts -- | åã®èŠçŽ ã«ç§»å prev :: Tape a -> Tape a prev (Tape (p : prevs) curr nexts) = Tape prevs p (curr : nexts) -- | çŸåšã®èŠçŽ ãã€ã³ã¯ãªã¡ã³ã incr :: Enum a => Tape a -> Tape a incr (Tape prevs curr nexts) = Tape prevs (succ curr) nexts -- | çŸåšã®èŠçŽ ããã¯ãªã¡ã³ã decr :: Enum a => Tape a -> Tape a decr (Tape prevs curr nexts) = Tape prevs (pred curr) nexts -- | çŸåšã®èŠçŽ ãååŸ get :: Tape a -> a get (Tape _ curr _) = curr -- | çŸåšã®èŠçŽ ãèšå® put :: a -> Tape a -> Tape a put a (Tape prevs _ nexts) = Tape prevs a nexts TypeScript ã®åã§ãåæ§ã«ã Tape ãåãåã£ãŠæ°ãã Tape ãäœæãããšããæ¹éã§å®è£
ã§ããŸãã [infer H, ...infer Hs] ã®ãã¿ãŒã³ãããã³ã°ã«ãããåã¬ãã«é
åã®èŠçŽ (head, rest) ãæ±ãããšãã§ããŠããŸããŸãã export type Prev < M > = M extends Tape < [infer H , ... infer Hs] , infer C , infer Ts > ? Tape< Hs , H , [C , ... Ts] > : never export type Next < M > = M extends Tape < infer Hs , infer C , [infer T , ... infer Ts] > ? Tape< [C , ... Hs] , T , Ts > : never export type Incr < M > = M extends Tape < infer Hs , infer C extends number , infer Ts > ? Tape< Hs , IncrementMap [C], Ts > : never export type Decr < M > = M extends Tape < infer Hs , infer C extends number , infer Ts > ? Tape< Hs , DecrementMap [C], Ts > : never export type PutC < M , C > = M extends Tape < infer Hs , unknown , infer Ts > ? Tape < Hs , C , Ts > : never ããã°ã©ã å®è¡ åºæ¬çãªæ§é ãæäœã¯å®çŸ©ããŠããŸã£ãã®ã§ã次ã¯ã€ã³ã¿ããªã¿ãšããŠéèŠãªå®è¡ã«ã€ããŠèããŸãã è©äŸ¡åšãšããŠã®å®è¡ç³»å
éš (ã¡ã¢ãªã»ããã°ã©ã ãã€ã³ã¿) ãšå€çãšã®ãããšããå«ã广ã®ç®¡çã®éšåããæ¬¡ã®ãããªåœ¢ã§åãåããŸãã åã¬ãã«ããã°ã©ãã³ã°ã§ã¯å
¥åºåããã®ãŸãŸæ±ãããšã¯ã§ããªãã®ã§ãå
¥ååŸ
ã¡ãåºåããããšããããšã¯ç¹å¥ãªç¶æ
ãšããŠè¡šçŸããããšã«ããŸãã è©äŸ¡åšã®å
éšç¶æ
ãã¡ãã¯è³ã£ãŠã·ã³ãã«ã§ãã ç¶æ
ã¯ã¡ã¢ãªãããã°ã©ã ã®ããŒã (çŸåšäœçœ®ãä¿æãã) ããæã ãããè©äŸ¡ã«éãããšã«ãã£ãŠã次ã®å®è¡ã«é¢ããç¶æ
ãåºãŠãã data Machine = Machine { memory :: DT.Tape Int , program :: DT.Tape Char } type Runner < M , P > = { mem : M prg : P } å€éšãšã®ãããšããå«ãã¢ã¯ã·ã§ã³ ä»ã®ã¡ã¢ãªã»ããã°ã©ã ãå«ããå
çšã®æ§é ãè©äŸ¡ããŠåŸãããã¢ã¯ã·ã§ã³ã§ãã -- | äœãããªããå
¥åèŠæ±ãåºåèŠæ±ãçµäºã® 4 ã€ã®ã¢ã¯ã·ã§ã³ãæã€ data WithAction a = ActionN { hold :: a } -- ^ å€éšã«ã¯äœãããªã | ActionI { hold :: a } -- ^ å
¥åèŠæ± | ActionO { hold :: a, out :: Int } -- ^ åºåèŠæ± | ActionE -- ^ çµäº ãããåã¬ãã«ããã°ã©ãã³ã°ã§åçŸãããšãADT ããã¯åå¥ã®åãšããŠå®çŸ©ããŠãããŠãåŸã§ extends ãªã©ã®æ¡ä»¶åå²ããŠãããæ¹ãçŽ çŽã«ãªããŸãã type ActionN < R > = { action : "N" ; runner : R } type ActionI < R > = { action : "I" ; runner : R } type ActionO < R , O > = { action : "O" ; runner : R ; output : O } type ActionE = { action : "E" } 8 ã€ã®åœä»€ã«å¯Ÿããæäœã®æŽç è©äŸ¡åšã®ç¶æ
ãšã¢ã¯ã·ã§ã³ãåãšããŠå®çŸ©ã§ããã®ã§ã次ã¯ããã°ã©ã ã®ç€ºãåœä»€ãåŠçããŠããå®è£
ãèããŠãããŸãã ããã¯æåã«ç¢ºèªãã BF ã® 8 ã€ã®åœä»€ã«å¯ŸããŠã次ã®è©äŸ¡åšã®ç¶æ
ãšèšç®ã®å¹æãå«ãå
šäœãè¿ã圢ã§å®çŸ©ããŠããã°è¯ãã§ãã ã€ã³ã¯ãªã¡ã³ã ãã¯ãªã¡ã³ã 次ãåç
§ (ãã€ã³ã¿ã€ã³ã¯ãªã¡ã³ã) åãåç
§ (ãã€ã³ã¿ãã¯ãªã¡ã³ã) while (ãžã£ã³ã) while end (ãžã£ã³ãããã¯) getchar putchar åœä»€â次ã®ç¶æ
ã»ã¢ã¯ã·ã§ã³ ããŠãå³ã§æŽçã§ããã®ã§ãå®è£
ã«ãã®ãŸãŸèœãšããŠãããŸãã çŸåšã®åœä»€ãã€ã³ã¿ãæãåœä»€ã«å¿ããŠã次㮠Action ãšç¶æ
ãè¿ããŸãã -- | 次ã®ã¹ããããå®è¡ããç¶æ
ãšã¢ã¯ã·ã§ã³ãè¿ã step :: Machine -> WithAction Machine step machine = case pc of '+' -> ActionN $ machine { memory = DT.incr (memory machine), program = DT.next (program machine) } '-' -> ActionN $ machine { memory = DT.decr (memory machine), program = DT.next (program machine) } '>' -> ActionN $ machine { memory = DT.next (memory machine), program = DT.next (program machine) } '<' -> ActionN $ machine { memory = DT.prev (memory machine), program = DT.next (program machine) } '[' -> ActionN $ machine { program = if mc == 0 then skip (program machine) else DT.next (program machine) } ']' -> ActionN $ machine { program = if mc /= 0 then back (program machine) else DT.next (program machine) } ',' -> ActionI { hold = machine { program = DT.next (program machine) } } '.' -> ActionO { hold = machine { program = DT.next (program machine) }, out = DT.get (memory machine) } _ -> ActionE where (pc, mc) = (,) <$> DT.get . program <*> DT.get . memory $ machine TypeScript ã§æžããŠããã»ãšãã©åã察å¿ããããŸãã type Step < R > = R extends Runner < infer M extends TapeMm , infer P extends TapePg > ? P[ 'c' ] extends '+' ? ActionN< Runner < Incr < M >, Next < P >>> : P[ 'c' ] extends '-' ? ActionN< Runner < Decr < M >, Next < P >>> : P[ 'c' ] extends '>' ? ActionN< Runner < Next < M >, Next < P >>> : P[ 'c' ] extends '<' ? ActionN< Runner < Prev < M >, Next < P >>> : P[ 'c' ] extends '[' ? ActionN< Runner < M , M [ 'c' ] extends 0 ? Skip < P > : Next < P >>> : P[ 'c' ] extends ']' ? ActionN< Runner < M , M [ 'c' ] extends 0 ? Next < P > : Back < P >>> : P[ 'c' ] extends ',' ? ActionI< Runner < M , Next < P >>> : P[ 'c' ] extends '.' ? ActionO< Runner < M , Next < P >>, M [ 'c' ]> : ActionE : never; ç¶æ
ã»ã¢ã¯ã·ã§ã³âç¶ç¶ 次ã¯ç¶æ
ãã¢ã¯ã·ã§ã³ãåããŠã次ã®ã¹ãããã«ç¶ç¶ããŠããã«ãŒããå®è£
ããŠãããŸãã äžèšã® step ãå®è¡ãããã® Action ã«å¿ããæäœãå®è¡ããŠãããŸãã -- | å
¥åãæ¶è²»ã»åºåãåéããªãã step ãç¹°ãè¿ã loop :: (Machine -> WithAction Machine) -> (String, Machine) -> String loop step (input, machine) = go (step machine) where -- ã¢ã¯ã·ã§ã³ã«å¯Ÿå¿ããåäœãå®è¡ããååž°ã«é²ã go (ActionN machine') = loop step (input, machine') -- ãã®ãŸãŸæ¬¡ãž go (ActionI machine') = loop step (iTail, machine'') where -- å
¥åãæ¶è²»ããŠã¡ã¢ãªã«æžã蟌ã¿ã次ã«é²ã (iHead : iTail) = input machine'' = machine' { memory = DT.put (fromEnum iHead) (memory machine') } go (ActionO machine' out) = toEnum out : loop step (input, machine') -- åºåãåéããæ¬¡ã«é²ã go ActionE = [] -- çµç«¯ TypeScript ã®åã®æ¹ã§ã¯ãä»åã¯æååã®çޝç©ãä¿æãã圢ã§å®è£
ããŠããŸããã¡ãã£ãšåœåãç°ãªã£ãŠããŸã£ãŠããŸããããã£ãŠããããšã¯åãã§ãã type Exec < R , I extends string , O extends string = '' > = Step < R > extends infer WithAction ? WithAction extends ActionN< infer Q > ? Exec< Q , I , O > : WithAction extends ActionI< infer Q > ? I extends ` ${ infer F }${ infer S } ` ? Exec< Read < Q , CharToNumMap [F]>, S , O > : Exec< Read < Q , 0>, I , O > : WithAction extends ActionO< infer Q , infer N extends number > ? Exec< Q , I , ` ${ O }${ NumToCharMap [N] } ` > : WithAction extends ActionE ? O : never : never; ãŸãšã TypeScript ã§ Brainf**k åŠçç³»ã®åã¬ãã«ããã°ã©ã ã®å®è£
ã«ã€ããŠèŠãŠãããŸããã è£è¶³ãšããŠãTypeScript ã®åã¬ãã«ããã°ã©ãã³ã°å®è¡ç³»ã«ã¯æ¬¡ã®ãããªå¶çŽããããŸãã åã®ååž°è©äŸ¡åæ°ãã€ãŸãå®è¡ã§ããã¹ãããæ°ãå¶éãããŠãã Tape æ§é äœã®ä¿æããèŠçŽ åã®é·ãã«å¶éããã (ã©ã¡ããå€§äœ 1,000 çšåºŠã®ã€ã¡ãŒãž) äžæ¹ããã®ãããªå¶éãããäžã§ããåé ã«ç€ºããäŸã®ããã«ç°¡å㪠Hello World ã®äŸãŸã§ã¯å®è£
ã§ããŠããŸããŸãã ã¿ãªããããã²èªåã®åã¬ãã«ããã°ã©ãã³ã°ã«ææŠããŠã¿ãŠãã ããã ç§ãä»å瀺ããå®è£
ãæåã§ã¯ãªããšæããŸããããã£ãšè¯ããã®ãæžããŠã¿ããããªã©ã楜ããã§ã¿ãŠãã ããã ä»é² Haskell ã®ã³ãŒãå
šæãæ²èŒããŠãããŸãã cwd-k2/bf-in-type ã®ãªããžããª ãšæ¯èŒããããŸãã¯æå
ã§ãã¹ãå®è¡ãããªã©ããŠãã ããã ãã£ã¬ã¯ããªæ§æ . âââ Data â  âââ Tape.hs âââ Interpreter.hs âââ Main.hs Data/Tape.hs module Data.Tape ( Tape( .. ), zeros, fromList, next, prev, incr, decr, get, put, ) where -- | ããŒãæ§æ§é äœ -- * ååŸã«ç¡éã«èŠçŽ ããããçŸåšèŠçŽ (éã®å
ã«ãããã®) ãäžå¿ã«é
眮ããŠãã -- -- > <-prev- ... 4 5 6 <<7>> 8 9 10 ... -next-> data Tape a = Tape { prevs :: [a] , curr :: a , nexts :: [a] } deriving Show -- | ãŒãåæåãããç¡éé·ã®ããŒã zeros :: Enum a => Tape a zeros = Tape (repeat $ toEnum 0 ) (toEnum 0 ) (repeat $ toEnum 0 ) -- | ãªã¹ãããããŒããäœæ fromList :: [a] -> Tape a fromList (x : xs) = Tape [] x xs fromList [] = undefined -- ä»åã¯ç¹ã«èããã«æªå®çŸ©ãšãã -- | 次ã®èŠçŽ ã«ç§»å next :: Tape a -> Tape a next (Tape prevs curr (n : nexts)) = Tape (curr : prevs) n nexts -- | åã®èŠçŽ ã«ç§»å prev :: Tape a -> Tape a prev (Tape (p : prevs) curr nexts) = Tape prevs p (curr : nexts) -- | çŸåšã®èŠçŽ ãã€ã³ã¯ãªã¡ã³ã incr :: Enum a => Tape a -> Tape a incr (Tape prevs curr nexts) = Tape prevs (succ curr) nexts -- | çŸåšã®èŠçŽ ããã¯ãªã¡ã³ã decr :: Enum a => Tape a -> Tape a decr (Tape prevs curr nexts) = Tape prevs (pred curr) nexts -- | çŸåšã®èŠçŽ ãååŸ get :: Tape a -> a get (Tape _ curr _) = curr -- | çŸåšã®èŠçŽ ãèšå® put :: a -> Tape a -> Tape a put a (Tape prevs _ nexts) = Tape prevs a nexts Interpreter.hs module Interpreter ( bf ) where import qualified Data.Tape as DT import Data.List (unfoldr) -- | ã¡ã¢ãªãšããã°ã©ã ãæã€ data Machine = Machine { memory :: DT.Tape Int , program :: DT.Tape Char } deriving Show -- | äœãããªããå
¥åèŠæ±ãåºåèŠæ±ãçµäºã® 4 ã€ã®ã¢ã¯ã·ã§ã³ãæã€ data WithAction a = ActionN { hold :: a } -- ^ å€éšã«ã¯äœãããªã | ActionI { hold :: a } -- ^ å
¥åèŠæ± | ActionO { hold :: a, out :: Int } -- ^ åºåèŠæ± | ActionE -- ^ çµäº deriving Show -- | 察å¿ãã @']'@ ãŸã§ããã°ã©ã ãã¹ããããã skip :: DT.Tape Char -> DT.Tape Char skip = skipInner 0 where skipInner n program = let program' = DT.next program in case DT.get program' of '[' -> skipInner (n + 1 ) program' ']' -> if n == 0 then program' else skipInner (n - 1 ) program' _ -> skipInner n program' -- | 察å¿ãã @'['@ ãŸã§ããã°ã©ã ãæ»ã back :: DT.Tape Char -> DT.Tape Char back = backInner 0 where backInner n program = let program' = DT.prev program in case DT.get program' of ']' -> backInner (n + 1 ) program' '[' -> if n == 0 then program' else backInner (n - 1 ) program' _ -> backInner n program' -- | 次ã®ã¹ããããå®è¡ããç¶æ
ãšã¢ã¯ã·ã§ã³ãè¿ã step :: Machine -> WithAction Machine step machine = case pc of '+' -> ActionN $ machine { memory = DT.incr (memory machine), program = DT.next (program machine) } '-' -> ActionN $ machine { memory = DT.decr (memory machine), program = DT.next (program machine) } '>' -> ActionN $ machine { memory = DT.next (memory machine), program = DT.next (program machine) } '<' -> ActionN $ machine { memory = DT.prev (memory machine), program = DT.next (program machine) } '[' -> ActionN $ machine { program = if mc == 0 then skip (program machine) else DT.next (program machine) } ']' -> ActionN $ machine { program = if mc /= 0 then back (program machine) else DT.next (program machine) } ',' -> ActionI { hold = machine { program = DT.next (program machine) } } '.' -> ActionO { hold = machine { program = DT.next (program machine) }, out = DT.get (memory machine) } _ -> ActionE where (pc, mc) = (,) <$> DT.get . program <*> DT.get . memory $ machine -- | å
¥åãæ¶è²»ã»åºåãåéããªãã step ãç¹°ãè¿ã loop :: (Machine -> WithAction Machine) -> (String, Machine) -> String loop step (input, machine) = go (step machine) where -- ã¢ã¯ã·ã§ã³ã«å¯Ÿå¿ããåäœãå®è¡ããååž°ã«é²ã go (ActionN machine') = loop step (input, machine') -- ãã®ãŸãŸæ¬¡ãž go (ActionI machine') = loop step (iTail, machine'') where -- å
¥åãæ¶è²»ããŠã¡ã¢ãªã«æžã蟌ã¿ã次ã«é²ã (iHead : iTail) = input machine'' = machine' { memory = DT.put (fromEnum iHead) (memory machine') } go (ActionO machine' out) = toEnum out : loop step (input, machine') -- åºåãåéããæ¬¡ã«é²ã go ActionE = [] -- çµç«¯ -- | Bf ããã°ã©ã ãããå
¥åãåãåã£ãŠåºåãè¿ã颿°ãäœã bf :: String -> [Char] -> String bf program input = loop step (input', machine) where input' = input ++ repeat ' \0 ' machine = Machine { memory = DT.zeros , program = DT.next $ DT.fromList ( "#" ++ program ++ "#" ) } Main.hs module Main where import Interpreter -- | ãããŒã¯ãŒã«ããã Bf ããã°ã©ã helloWorld :: String helloWorld = "++++++++++[>+++++++>++++++++++>+++++++++++>+++>+++++++++>+<<<<<<-]>++.>+.>--..+++.>++.>---.<<.+++.------.<-.>>+.>>." -- | ãšã³ãŒãã Bf ããã°ã©ã echo :: String echo = "+[,.]" main :: IO () main = do let getOutputBf = bf helloWorld putStr $ getOutputBf "ããã«ã¡ã¯ \n "