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
Let’s create a programming language! [RUG::B ed...
Search
Denis Defreyne
June 02, 2016
Programming
1
220
Let’s create a programming language! [RUG::B edition]
Denis Defreyne
June 02, 2016
Tweet
Share
More Decks by Denis Defreyne
See All by Denis Defreyne
The importance of naming
ddfreyne
0
72
An introduction to fibers
ddfreyne
0
180
Code as data (RubyConfBY 2019 edition)
ddfreyne
0
120
Code as data
ddfreyne
0
170
How to memoize
ddfreyne
0
180
Clean & fast code with enumerators
ddfreyne
0
130
Fibers
ddfreyne
0
460
Let’s create a programming language! [SoundCloud HQ edition]
ddfreyne
0
210
Let’s write a parser! [SoundCloud HQ edition]
ddfreyne
0
230
Other Decks in Programming
See All in Programming
ARA Ansible for the teams
kksat
0
150
AHC041解説
terryu16
0
590
TokyoR116_BeginnersSession1_環境構築
kotatyamtema
0
110
動作確認やテストで漏れがちな観点3選
starfish719
6
1k
ファインディの テックブログ爆誕までの軌跡
starfish719
2
1.1k
最近のVS Codeで気になるニュース 2025/01
74th
1
250
さいきょうのレイヤードアーキテクチャについて考えてみた
yahiru
3
730
いりゃあせ、PHPカンファレンス名古屋2025 / Welcome to PHP Conference Nagoya 2025
ttskch
1
270
chibiccをCILに移植した結果 (NGK2025S版)
kekyo
PRO
0
210
Software Architecture
hschwentner
6
2.1k
Lottieアニメーションをカスタマイズしてみた
tahia910
0
120
Rails アプリ地図考 Flush Cut
makicamel
1
110
Featured
See All Featured
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
33
2.8k
Designing for Performance
lara
604
68k
Become a Pro
speakerdeck
PRO
26
5.1k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
330
21k
How to Ace a Technical Interview
jacobian
276
23k
RailsConf 2023
tenderlove
29
1k
Learning to Love Humans: Emotional Interface Design
aarron
273
40k
Why You Should Never Use an ORM
jnunemaker
PRO
55
9.2k
Stop Working from a Prison Cell
hatefulcrawdad
267
20k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
49
2.3k
Fantastic passwords and where to find them - at NoRuKo
philnash
51
3k
A better future with KSS
kneath
238
17k
Transcript
Let’s create a programming language! DENIS DEFREYNE RUG : :B
JUNE 2, 2016
2 dynamic vs. static
3 dynamic vs. static
4 compiler interpreter vs.
5 compiler interpreter vs.
but why? 6
incremental 7
Language 1 8 Numbers
% 9 cat stuff.cke 4173 5 27 2016
% 10 cat stuff.cke | ./clarke 4173 5 27 2016
11 module Grammar extend DParse::DSL DIGIT = char_in('0'..'9') PROGRAM =
DIGIT end
12 res = Grammar::PROGRAM.apply($stdin.read) case res when DParse::Success handle_success(res)
when DParse::Failure handle_failure(res) end
13 def handle_success(success) p success.data end
14 DIGIT = char_in('0'..'9')
15 DIGIT = … NUMBER = repeat1(DIGIT)
16 DIGIT = … NUMBER = repeat1(DIGIT) .capture
17 DIGIT = … NUMBER = repeat1(DIGIT) .capture .map {
|d| d.to_i }
18 DIGIT = … NUMBER = … EXPRESSION = NUMBER
19 DIGIT = … NUMBER = … EXPRESSION = …
EXPRESSIONS = intersperse( EXPRESSION, char("\n").ignore, ).compact
20 DIGIT = … NUMBER = … EXPRESSION = …
EXPRESSIONS = … PROGRAM = seq(EXPRESSIONS, eof) .first
% 21 cat stuff.cke 4173 5 27 2016
% 22 cat stuff.cke | ./clarke [4173, 5, 27, 2016]
23 def handle_success(success) p success.data end
24 def handle_success(success) success.data.each do |expr| p eval_expr(expr) end end
25 def eval_expr(expr) expr end
% 26 cat stuff.cke | ./clarke 4173 5 27 2016
% 27 echo "aa" | ./clarke expected digit at line
1, column 1 aa ↑
Language 2 28 Functions
% 29 cat stuff.cke 4173 add(2, 5)
% 30 cat stuff.cke | ./clarke 4173 7
31 LETTER = char_in('a'..'z') FUNCTION_NAME = repeat1(LETTER).capture
32 FUNCTION_CALL = seq( FUNCTION_NAME, char('('), intersperse( lazy { EXPRESSION
}, char(','), ), char(')'), )
33 FUNCTION_CALL = seq( FUNCTION_NAME, char('('), intersperse( lazy { EXPRESSION
}, char(',').ignore, ).compact, char(')'), )
34 FUNCTION_CALL = seq( FUNCTION_NAME, char('(').ignore, intersperse( lazy { EXPRESSION
}, char(',').ignore, ).compact, char(')').ignore, ).compact
35 EXPRESSION = NUMBER
36 EXPRESSION = alt(NUMBER, FUNCTION_CALL)
% 37 cat stuff.cke 4173 add(2, 5)
% 38 cat stuff.cke | ./clarke 4173 ["add", [2, 5]]
39 def eval_expr(expr) expr end
40 def eval_expr(expr) case expr when Integer expr when Array
eval_function_call(expr) end end
41 def eval_function_call(expr) case expr[0] when 'add' expr[1] .map {
|e| eval_expr(e) } .reduce(:+) when 'mul' … end end
% 42 cat stuff.cke 4173 add(2, 5)
% 43 cat stuff.cke | ./clarke 4173 7
Ugh, we forgot about whitespace. 44
Cleanup 1 45 Abstract syntax
46 class IntNode < Struct.new(:value) end class FunCallNode < Struct.new(:name,
:arguments) end
47 DIGIT = … NUMBER = repeat1(DIGIT) .capture .map {
|d| d.to_i }
48 DIGIT = … NUMBER = repeat1(DIGIT) .capture .map {
|d| IntNode.new(d.to_i) }
49 FUNCTION_CALL = seq( FUNCTION_NAME, char('(').ignore, intersperse(…), char(')').ignore, ).compact
50 FUNCTION_CALL = seq( FUNCTION_NAME, char('(').ignore, intersperse(…), char(')').ignore, ).compact.map do
|data| FunCallNode.new(data[0], data[1]) end
51 def eval_expr(expr) case expr when Integer expr when Array
eval_function_call(expr) end end
52 def eval_expr(expr) case expr when IntNode expr.value when FunCallNode
eval_function_call(expr) end end
53 def eval_function_call(expr) case expr[0] when 'add' expr[1] .map {
|e| eval_expr(e) } .reduce(:+) when 'mul' … end end
54 def eval_function_call(expr) case expr.name when 'add' expr.args .map {
|e| eval_expr(e) } .reduce(:+) when 'mul' … end end
Cleanup 2 55 Environment
56 class FunDef < Struct.new(:args, :body) end
57 $env = {} $env['add'] = FunDef.new( ['a', 'b'], ->(a,
b) { a + b }, )
58 def eval_function_call(expr) case expr.name when 'add' expr.args .map {
|e| eval_expr(e) } .reduce(:+) when 'mul' … end end
59 def eval_function_call(expr) fun = $env[expr.name] values = expr.args.map {
|e| eval_expr(e) } fun.body.call(*values) end
… with error handling, of course. 60
Language 3 61 Variables
% 62 cat stuff.cke 4173 add(2,amount)
% 63 cat stuff.cke | ./clarke 4173 7
64 class VarNode < Struct.new(:name) end
65 VARIABLE_NAME = repeat1(LETTER).capture
66 VARIABLE_REFERENCE = VARIABLE_NAME .map { |d| VarNode.new(d) }
67 EXPRESSION = alt( NUMBER, FUNCTION_CALL, )
68 EXPRESSION = alt( NUMBER, FUNCTION_CALL, VARIABLE_REFERENCE, )
69 def eval_expr(expr) case expr when IntNode expr.value when FunCallNode
eval_function_call(expr) end end
70 def eval_expr(expr) case expr when IntNode expr.value when FunCallNode
eval_function_call(expr) when VarNode eval_var(expr) end end
71 def eval_var(expr) $env[expr.name] end
72 $env['amount'] = 5
Language 3.1 73 Variable assignment
% 74 cat stuff.cke 4173 amount=5 add(2,amount)
% 75 cat stuff.cke | ./clarke 4173 7
76 class AssignNode < Struct.new(:name, :rhs) end
77 ASSIGNMENT = seq( VARIABLE_NAME, char('='), lazy { EXPRESSION },
)
78 ASSIGNMENT = seq( VARIABLE_NAME, char('=').ignore, lazy { EXPRESSION },
).compact
79 ASSIGNMENT = seq( VARIABLE_NAME, char('=').ignore, lazy { EXPRESSION },
).compact.map do |data| AssignNode.new(data[0], data[1]) end
80 EXPRESSION = alt( NUMBER, FUNCTION_CALL, VARIABLE_REFERENCE, )
81 EXPRESSION = alt( NUMBER, FUNCTION_CALL, VARIABLE_REFERENCE, ASSIGNMENT, )
82 def eval_expr(expr) case expr when … … when AssignNode
eval_assign(expr) end end
83 def eval_assign(expr) $env[expr.name] = eval_expr(expr.rhs) end
Cleanup 3 84 Print function
85 def handle_success(success) success.data.each do |expr| p eval_expr(expr) end end
86 def handle_success(success) success.data.each do |expr| eval_expr(expr) end end
87 $env['print'] = FunDef.new( ['a'], ->(a) { p a },
)
% 88 cat stuff.cke 4173 amount=5 print(add(2,amount))
% 89 cat stuff.cke | ./clarke 7
Cleanup 4 90 Immutable env
91 def eval_expr(expr) case expr when … … when AssignNode
eval_assign(expr) end end
92 def eval_expr(expr, env) case expr when … … when
AssignNode eval_assign(expr, env) end end
93 def eval_assign(expr) $env[expr.name] = eval_expr(expr.rhs) end
94 def eval_assign(expr, env) $env[expr.name] = eval_expr(expr.rhs) end
95 def eval_assign(expr, env) val = eval_expr(expr.rhs) new_env = env.merge(expr.name
=> val) ValAndEnv.new(val, new_env) end
96 class ValAndEnv < Struct.new(:val, :env) end
97 def handle_success(success) success.data.each do |expr| eval_expr(expr) end end
98 def handle_success(success) init = ValAndEv.new(0, INITIAL_ENV)
99 def handle_success(success) init = ValAndEv.new(0, INITIAL_ENV) success.data.reduce(init) do |result,
e| eval_expr(e, result.env) end end
100 INITIAL_ENV = { 'add' => FunDef.new( ['a', 'b'], ->(a,
b) { a + b }, ) }
Language 4 101 Scopes
% 102 cat stuff.cke 4173 amount = { a =
2 b = 3 add(a, b) } print(add(2, amount))
% 103 cat stuff.cke | ./clarke 7
104 class ScopeNode < Struct.new(:exprs) end
105 SCOPE = seq( char('{'), repeat1(lazy { EXPRESSION }), char('}'),
)
106 SCOPE = seq( char('{').ignore, repeat1(lazy { EXPRESSION }), char('}').ignore,
).compact
107 SCOPE = seq( char('{').ignore, repeat1(lazy { EXPRESSION }), char('}').ignore,
).compact.map do |data| ScopeNode.new(data[0]) end
108 EXPRESSION = alt( NUMBER, FUNCTION_CALL, VARIABLE_REFERENCE, ASSIGNMENT, )
109 EXPRESSION = alt( NUMBER, FUNCTION_CALL, VARIABLE_REFERENCE, ASSIGNMENT, SCOPE, )
110 def eval_expr(expr, env) case expr when … … when
ScopeNode eval_scope(expr, env) end end
111 def eval_scope(expr, env) init = ValAndEnv.new(0, env) result =
expr.exprs.reduce(init) do |result, e| eval_expr(e, result.env) end ValAndEnv.new(result.val, env) end
112 def eval_scope(expr, env) init = ValAndEnv.new(0, env) result =
expr.exprs.reduce(init) do |result, e| eval_expr(e, result.env) end ValAndEnv.new(result.val, env) end
% 113 cat stuff.cke 4173 amount = { a =
2 b = 3 add(a, b) } print(add(2, amount))
Language 5 114 Conditionals
% 115 cat stuff.cke if (0) { print(100) } else
{ print(200) }
% 116 cat stuff.cke | ./clarke 200
SKIP 117
Language 6 118 Function definitions
% 119 cat stuff.cke fun multiply(a, b) { if (b)
{ add(a, multiply(a, sub(b, 1))) } else { 0 } } print(multiply(3, 5))
120 class FunDefNode < Struct.new( :name, :argument_names, :body) end
121 FUNCTION_DEF = seq( string('fun'), FUNCTION_NAME, char('('), intersperse( VARIABLE_NAME, char(','),
), char(')'), SCOPE, )
122 FUNCTION_DEF = seq( string('fun').ignore, FUNCTION_NAME, char('(').ignore, intersperse( VARIABLE_NAME, char(',').ignore,
).compact, char(')').ignore, SCOPE, ).compact
123 FUNCTION_DEF = seq( string('fun').ignore, FUNCTION_NAME, char('(').ignore, intersperse( VARIABLE_NAME, char(',').ignore,
).compact, char(')').ignore, SCOPE, ).compact.map do |data| FunDefNode.new(data[0], data[1], data[2]) end
124 class FunDef < Struct.new(:argument_names, :body) end
125
125 def eval_function_def(expr, env)
125 def eval_function_def(expr, env) fun_def = FunDef.new( expr.argument_names, expr.body)
125 def eval_function_def(expr, env) fun_def = FunDef.new( expr.argument_names, expr.body) ValAndEnv.new(
fun_def, env.merge(expr.name => fun_def), ) end
126 def eval_function_call(expr, env) fun = env[expr.name] values = expr.args.map
{ |e| eval_expr(e) } fun.body.call(*values)
127 def eval_function_call(expr, env) fun = env[expr.name] values = expr.args.map
{ |e| eval_expr(e) } case fun.body when Proc when Scope … fun.body.call(*values)
127 def eval_function_call(expr, env) fun = env[expr.name] values = expr.args.map
{ |e| eval_expr(e) } case fun.body when Proc when Scope … fun.body.call(*values)
128
128 when Scope new_env = env.merge( Hash[fun.argument_names.zip(values)])
128 when Scope new_env = env.merge( Hash[fun.argument_names.zip(values)]) eval_scope(fun.body, new_env) end
% 129 cat stuff.cke fun multiply(a, b) { if (b)
{ add(a, multiply(a, sub(b, 1))) } else { 0 } } print(multiply(3, 5))
Language 7 130 Operators
% 131 cat stuff.cke fun multiply(a, b) { if (b)
{ a + multiply(a, b - 1) } else { 0 } } print(multiply(3, 5))
132 10 - 2 - 5 * 2 + 2
^ 3 ^ 4
SKIP 133
etc.
Types! Loops! Closures! Objects! Classes! Inheritance! Tuples! Records! Typechecking! Multimethods!
Enumerations! Pattern matching! Currying! Modules! 135
136
136 L1 Numbers
136 L1 Numbers L2 Functions
136 L1 Numbers L2 Functions C1 Abstract syntax
136 L1 Numbers L2 Functions C1 Abstract syntax C2 Environment
136 L1 Numbers L2 Functions C1 Abstract syntax C2 Environment
L3 Variables
136 L1 Numbers L2 Functions C1 Abstract syntax C2 Environment
L3 Variables C3 Print function
136 L1 Numbers L2 Functions C1 Abstract syntax C2 Environment
L3 Variables C3 Print function C4 Immutable environment
136 L1 Numbers L2 Functions C1 Abstract syntax C2 Environment
L3 Variables C3 Print function C4 Immutable environment L4 Scopes
136 L1 Numbers L2 Functions C1 Abstract syntax C2 Environment
L3 Variables C3 Print function C4 Immutable environment L4 Scopes L5 Conditionals
136 L1 Numbers L2 Functions C1 Abstract syntax C2 Environment
L3 Variables C3 Print function C4 Immutable environment L4 Scopes L5 Conditionals L6 Function definitions
136 L1 Numbers L2 Functions C1 Abstract syntax C2 Environment
L3 Variables C3 Print function C4 Immutable environment L4 Scopes L5 Conditionals L6 Function definitions L7 Operators
137 github.com/ddfreyne/clarke
137 github.com/ddfreyne/clarke SOON
138 Ready to interpret your questions.
[email protected]
@DDFREYNE