Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
10ステップで作るお手軽インタプリタ開発
Search
Ushitora Anqou
October 22, 2018
Programming
3
1k
10ステップで作るお手軽インタプリタ開発
10ステップで、フィボナッチ数列が再帰により計算できる程度のインタプリタをつくります。レポジトリは以下です。
https://github.com/ushitora-anqou/simplinterp
Ushitora Anqou
October 22, 2018
Tweet
Share
More Decks by Ushitora Anqou
See All by Ushitora Anqou
Oblivious Online Monitoring for Safety LTL Specification via Fully Homomorphic Encryption
anqou
1
910
F*でプログラムの正しさを証明する
anqou
1
1.1k
「自作CPUでサイゼリヤ問題」を支える技術
anqou
2
340
ぼくのかんがえたさいきょうのマリオAI
anqou
1
570
seccamp2018でセルフホストCコンパイラをつくった
anqou
8
5.5k
Other Decks in Programming
See All in Programming
なんとなくわかった気になるブロックテーマ入門/contents.nagoya 2025 6.28
chiilog
1
130
The Evolution of Enterprise Java with Jakarta EE 11 and Beyond
ivargrimstad
1
850
Effect の双対、Coeffect
yukikurage
5
1.4k
GoのGenericsによるslice操作との付き合い方
syumai
2
680
CursorはMCPを使った方が良いぞ
taigakono
0
150
Team topologies and the microservice architecture: a synergistic relationship
cer
PRO
0
940
F#で自在につくる静的ブログサイト - 関数型まつり2025
pizzacat83
0
310
LINEヤフー データグループ紹介
lycorp_recruit_jp
0
760
Enterprise Web App. Development (2): Version Control Tool Training Ver. 5.1
knakagawa
1
120
WindowInsetsだってテストしたい
ryunen344
1
190
SODA - FACT BOOK
sodainc
1
1.1k
関数型まつり2025登壇資料「関数プログラミングと再帰」
taisontsukada
2
840
Featured
See All Featured
The Web Performance Landscape in 2024 [PerfNow 2024]
tammyeverts
8
660
I Don’t Have Time: Getting Over the Fear to Launch Your Podcast
jcasabona
32
2.3k
Improving Core Web Vitals using Speculation Rules API
sergeychernyshev
16
940
The World Runs on Bad Software
bkeepers
PRO
69
11k
Building Applications with DynamoDB
mza
95
6.5k
Done Done
chrislema
184
16k
Building Flexible Design Systems
yeseniaperezcruz
328
39k
Facilitating Awesome Meetings
lara
54
6.4k
Making the Leap to Tech Lead
cromwellryan
134
9.3k
Testing 201, or: Great Expectations
jmmastey
42
7.5k
A better future with KSS
kneath
239
17k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
Transcript
10 εςοϓͰͭ͘Δ ͓खܰΠϯλϓϦλ։ൃ ࠡ ᲒᲶ @ushitora anqou 1
Δ͜ͱ • ؆୯ͳΠϯλϓϦλΛ C ݴޠͰॻ͘ɻ • ϑΟϘφονྻΛܭࢉͰ͖Δɻ • Strongly inspired
by https://youtu.be/JAtN0TGrNE4 2
Θ͔ͬͯ΄͍͜͠ͱ • ݴޠॲཧܥݴ͏΄Ͳ͘͠ͳ͍ɻ • ཧࡶ͕࣮ͩ͢ΕΘ͔Δɻ • ΈΜͳ C ίϯύΠϥΛͭ͘Ζ͏ʂ 3
ιʔε https://github.com/ ushitora-anqou/ simplinterp 4
5
6
7
ΠϯλϓϦλͬͯͳΜͩΖ͏ ΠϯλϓϦλʢӳ: interpreterʣͱ ɺϓϩάϥϛϯάݴޠͰॻ͔Ε ͨιʔείʔυͳ͍͠தؒදݱΛ ஞ࣍ղऍ͠ͳ͕Β࣮ߦʢӳޠ൛ʣ ͢ΔϓϩάϥϜͷ͜ͱɻ ʢWikipedia ΑΓʣ 8
ΠϯλϓϦλͬͯͳΜͩΖ͏ ͭ͘ΕΘ͔Δ 9
Step
Step 0 C ݴޠͷจࣈྻॲཧ ↓ H e l l o
\0 char *p = "Hello"; • C ݴޠʹ͓͍ͯจࣈྻʮจࣈ͕ϝϞ Ϧ্ʹฒͼɺऴ͕\0 ͷͷʯ • ϙΠϯλͰจࣈྻͷઌ಄ཁૉΛࢦ͢ɻ 10
Step 0 C ݴޠͷจࣈྻॲཧ ↓ H e l l o
\0 char *p = "Hello"; p; // address *p; // ’H’ *(p + 1); // ’e’ p[1]; // ’e’ *p++; // ’H’ *p; // ’e’ 11
Step 1 ಈ͘ίʔυΛॻ͘ #include <stdio.h> int eval(char *p) { return
0; } int main(int argc , char ** argv) { return eval(argv [1]); } eval() ͰϓϩάϥϜͷ࣮ߦΛߦ͏ɻ ./main "program" 12
Step 1 ಈ͘ίʔυΛॻ͘ ςετΛॻ͘ɻ #!/bin/sh # ʢதུʣ runtest "0" 0
runtest ͰϓϩάϥϜͷਖ਼ৗ࣮ߦΛ͔֬ ΊΔɻ 13
Step 2 ࣗવΛಡΉ ΛҰݸಡΈࠐΜͰɺͦΕΛฦ͢ɻ runtest "0" 0 runtest "1" 1
runtest "42" 42 ͜ͷΑ͏ͳग़ྗΛಘΔʹʁ 14
Step 2 ࣗવΛಡΉ ΛҰݸಡΈࠐΜͰɺͦΕΛฦ͢ɻ int eval(char *p) { int ival
= 0; while (isdigit (*p)) { ival = ival * 10 + *p - ’0’; p++; } return ival; } ٙϗϫΠτϘʔυͰղઆɻ 15
Step 3 ͠ࢉΛ͢ ͠ࢉͬͯԿͩΖ͏ɻ runtest "1+42" 43 runtest "23+42" 65
runtest "1+2+4" 7 runtest "1+2+4+10" 17 ͜ͷΑ͏ͳग़ྗΛಘΔʹʁ 16
Step 3 ͠ࢉΛ͢ ʮ͠ࢉʯͱ 1. ॳΊʹ͕དྷΔɻ 2. ͦͷޙʹʮ+ ʯ͕ 0
ճҎ্܁Γ ฦ͢ɻ e.g. 42, 1+2, 1+2+3 17
Step 3 ͠ࢉΛ͢ 1. ॳΊʹ͕དྷΔɻ 2. ͦͷޙʹʮ+ ʯ͕ 0 ճҎ্܁Γ
ฦ͢ɻ ͠ࢉ := ( ‘+’ )* 18
Step 3 ͠ࢉΛ͢ ͠ࢉ := ( ‘+’ )*
int ival = parse_integer (); while (*p++ == ’+’) ival += parse_integer (); return ival; ٙϗϫΠτϘʔυͰղઆɻ 19
Step 4 Ҿ͖ࢉΛ͢ ಉ͡Α͏ʹͯ͠ΈΔɻ runtest "1+2 -3+5" 5 ͜ͷΑ͏ͳग़ྗΛಘΔʹʁ 20
Step 4 Ҿ͖ࢉΛ͢ ͠ࢉ := ( ( ‘+’ |
‘-’ ) )* e.g. 42, 1+3, 12-3, 4+2-5+4-1 ͠ࢉ :thinking face: 21
int ival = parse_integer (); while (*p != ’\0’) {
switch (*p) { case ’+’: p++; ival += parse_integer (); break; case ’-’: p++; ival -= parse_integer (); break; default: goto end; } } end: return ival; 22
Step 5 ֻ͚ࢉɾׂΓࢉΛ͢ ಉ͡Α͏ʹ࣮͢Δʁ runtest "1*2+3" 5 runtest "13/3+4" 8
runtest "1+2*3" 7 runtest "1*2+3*4" 14 runtest "5/2+99/3" 35 ͜ͷΑ͏ͳग़ྗΛಘΔʹʁ 23
Step 5 ֻ͚ࢉɾׂΓࢉΛ͢ ͠ࢉ:= ( ( ‘+’ | ‘-’
| ‘*’ | ‘/’) )* 2*3+4 Αͦ͞͏ɻ 24
Step 5 ֻ͚ࢉɾׂΓࢉΛ͢ ͠ࢉ:= ( ( ‘+’ | ‘-’
| ‘*’ | ‘/’) )* 2*3+4 Αͦ͞͏ɻ 4+2*3 ʁ 24
Step 5 ֻ͚ࢉɾׂΓࢉΛ͢ ԋࢉࢠͷ༏ઌॱҐͱʁ 4 + (2 * 3) -
(6 / 3) ͠ࢉͷཁૉͱֻ͚ͯ͠ࢉΛ͑Δɻ ͱֻ͚ࢉಉ͡ѻ͍ɻ 25
Step 5 ֻ͚ࢉɾׂΓࢉΛ͢ ֻ͚ࢉ:= ( ( ‘*’ | ‘/’
) )* ͠ࢉ:= ֻ͚ࢉ ( ( ‘+’ | ‘-’ ) ֻ͚ࢉ )* શͯͷϓϩάϥϜʮ͠ࢉʯ e.g. 42, 1+2-3, 2*3/2, 2*3+4*5-10/3 26
int parse_add () { int ival = parse_mul (); while
(*p != ’\0’) { switch (*p) { case ’+’: p++; ival += parse_mul (); continue; case ’-’: p++; ival -= parse_mul (); continue; } break; } return ival; } 27
int parse_mul () { int ival = parse_integer (); while
(*p != ’\0’) { switch (*p) { case ’*’: p++; ival *= parse_integer (); continue; case ’/’: p++; ival /= parse_integer (); continue; } break; } return ival; } 28
Step 6 ؔݺͼग़͠Λ࣮ ͷग़ྗΛߦ͏ؔ P() Λͭ͘Δɻ ؔͷΓ 0 ͱ͓ͯ͘͠ɻ runtest
"P(1)" 0 # 1 on screen 29
Step 6 ؔݺͼग़͠Λ࣮ F(2) / 2 + G(3+4*2) * H(0)
- 5 • ؔͷΓͱಉ͡ѻ͍ɻ • ؔͷҾʮ͠ࢉʯ 30
Step 6 ؔݺͼग़͠Λ࣮ ؔݺग़:= ‘P’ ‘(’ ͠ࢉ ‘)’ |
ֻ͚ࢉ:= ؔݺग़ ( ( ‘*’ | ‘/’ ) ؔݺग़ )* ͠ࢉ:= ֻ͚ࢉ ( ( ‘+’ | ‘-’ ) ֻ͚ࢉ )* 31
int parse_mul () { int ival = parse_funccall (); while
(*p != ’\0’) { switch (*p) { case ’*’: p++; ival *= parse_funccall (); continue; case ’/’: p++; ival /= parse_funccall (); continue; } break; } return ival; } 32
int parse_funccall () { if (*p == ’P’) { p++;
expect(’(’); int ival = parse_add (); expect(’)’); printf("%d\n", ival ); return 0; } return parse_integer (); } 33
Step 7 ࣜͷ۠ΓΛՃ ‘;’ ͰࣜΛ۠ΕΔΑ͏ʹ͢Δɻ runtest "P(1);10+2;3" 3 ࠷ऴతͳҰ൪࠷ޙͷࣜͷɻ 34
Step 7 ࣜͷ۠ΓΛՃ ؔݺग़:= ‘P’ ‘(’ ࣜ ‘)’ |
ֻ͚ࢉ:= ؔݺग़ ( ( ‘*’ | ‘/’ ) ؔݺग़ )* ͠ࢉ:= ֻ͚ࢉ ( ( ‘+’ | ‘-’ ) ֻ͚ࢉ )* ࣜ:= ͠ࢉ ( ‘;’ ͠ࢉ )* શͯͷϓϩάϥϜʮࣜʯ 35
int eval() { int ival = parse_add (); while (*p
== ’;’) { p++; ival = parse_add (); } return ival; } 36
Step 8 Ҿͳؔ͠ఆٛΛՃ Ҿͳ͠ͷؔఆ͕ٛͰ͖ΔΑ͏ʹ͢Δɻ runtest "F{1}F()" 1 runtest "F{5/2+99/3 -3*4}F()"
23 runtest "F{5/2+99/3 -3*4;100 -24}F()"\ 76 ໊ؔେจࣈΞϧϑΝϕοτ 1 จࣈɻ ؔఆٛϓϩάϥϜͷઌ಄ͷΈͰՄೳɻ 37
Step 8 Ҿͳؔ͠ఆٛΛՃ F{5/2+99/3-3*4;100-24} • ໊͕ؔ࢝ΊʹདྷΔɻ • {ͱ}ͰؔຊମΛғΉɻ • ؔຊମࣜΛ;
Ͱ۠ͬͨͷɻ • ؔͷΓؔຊମΛධՁ͠ ͨɻ 38
Step 8 Ҿͳؔ͠ఆٛΛՃ F{5/2+99/3-3*4;100-24} ؔఆٛ := [ ‘A’-‘Z’ ] ‘{’
ࣜ ‘}’ ؔݺग़ := ‘P’ ‘(’ ࣜ ‘)’ | [ ‘A’-‘Z’ ] ‘(’ ‘)’ | 39
int eval() { while (1) { if (’A’ <= *p
&& *p <= ’Z’ && *(p + 1) == ’{’) { parse_funcdef (); continue; } return parse_exprs (); } } 40
char *funcbuf [256]; void parse_funcdef () { int n =
*p++; expect(’{’); funcbuf[n] = p; while (*p != ’\0’ && *p++ != ’}’) ; } 41
int parse_funccall () { // ... process of P()... //
then other functions if (’A’ <= *p && *p <= ’Z’) { int name = *p; p++; expect(’(’); expect(’)’); char *old_p = p; p = funcbuf[name ]; int ival = parse_exprs (); p = old_p; return ival; } return parse_integer (); } 42
Step 9 Ҿ͋ΓؔఆٛΛՃ Ҿ͋Γͷؔఆ͕ٛͰ͖ΔΑ͏ʹ͢Δɻ runtest "F{a}F(42)" 42 runtest "F{a+b;a*b}F(1 ,1+1)"
2 ҾখจࣈΞϧϑΝϕοτ 1 จࣈɻ ݺͼग़͠ଆΧϯϚͰ۠ͬͯ͢ɻ 43
Step 9 Ҿ͋ΓؔఆٛΛՃ F{a+b;a*b} • ͱҾΛಉʹѻ͏ɻ • ؔͷதΛධՁ͢Δͱ͖ʹɺҾΛ ରԠ͢Δʹ͢Γସ͑Δɻ ͺͦ͜ΜΘ͔ΒΜʂ͆ͷͰҾΛม
ʢvariableʣͱ͍͏໊લͰ࣮ͨ͠ɻ 44
Step 9 Ҿ͋ΓؔఆٛΛՃ F{a+b;a*b} ม := [ ‘a’-‘z’ ] |
ؔݺग़ := ‘P’ ‘(’ ࣜ ‘)’ | [ ‘A’-‘Z’ ] ‘(’ ‘)’ | ม 45
int *varbuf; int parse_variable () { if (’a’ <= *p
&& *p <= ’z’) return varbuf [(int)*p++]; return parse_integer (); } 46
Step 9 Ҿ͋ΓؔఆٛΛՃ parse funccall() ͷղઆ 1. ໊ؔͱ (ΛಡΉɻ 2.
มςʔϒϧΛ࡞ΔɻҾΛධՁͯ͠ tmpbuf ʹೖΕΔɻ 3. ) ΛಡΉɻ 4. p ͱ funcbuf[name] ΛೖΕସ͑Δɻ 5. tmpbuf ͱ varbuf ΛೖΕସ͑Δɻ 47
Step 9 Ҿ͋ΓؔఆٛΛՃ parse funccall() ͷղઆ 6. parse exprs() ΛݺͿ͜ͱͰؔຊମΛಡ
Ήɻ͜ͷ͕Γɻ 7. ্ͰೖΕସ͑ͨ p ͱ varbuf Λݩʹ͢ɻ 8. ΓΛฦ͢ɻ 47
Step 10 ϑΟϘφονྻΛग़ྗ͢Δ ඞཁͳݴޠػೳશ࣮ͯɻ runtest "1*2+3" 5 runtest "13/3+4" 8
runtest "P(1);10+2;3" 3 runtest "F{a+b;a*b}F(1 ,1+1)" 2 ͜ΕΒΛ༻͍ͯϑΟϘφονྻΛग़ྗ͢ Δʹʁ 48
Step 10 ϑΟϘφονྻΛग़ྗ͢Δ F{P(a);F(b,a+b)}F(1,1) % ./main "F{P(a);F(b,a+b)}F(1,1)" | head -25
2 ͷྦྷͱ͔ܭࢉͰ͖Δɻ 49
·ͱΊ 50
·ͱΊ ݴޠॲཧܥ Δ͚ͩ 50
͝ਗ਼ௌ ͋Γ͕ͱ͏͟͝ ͍·ͨ͠ 51