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
210
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
55
An introduction to fibers
ddfreyne
0
160
Code as data (RubyConfBY 2019 edition)
ddfreyne
0
95
Code as data
ddfreyne
0
140
How to memoize
ddfreyne
0
150
Clean & fast code with enumerators
ddfreyne
0
110
Fibers
ddfreyne
0
440
Let’s create a programming language! [SoundCloud HQ edition]
ddfreyne
0
190
Let’s write a parser! [SoundCloud HQ edition]
ddfreyne
0
210
Other Decks in Programming
See All in Programming
Macとオーディオ再生 2024/11/02
yusukeito
0
220
From Subtype Polymorphism To Typeclass-based Ad hoc Polymorphism- An Example
philipschwarz
PRO
0
170
レガシーな Android アプリのリアーキテクチャ戦略
oidy
1
170
AWS IaCの注目アップデート 2024年10月版
konokenj
3
3.1k
Boost Performance and Developer Productivity with Jakarta EE 11
ivargrimstad
0
900
CSC509 Lecture 08
javiergs
PRO
0
110
現場で役立つモデリング 超入門
masuda220
PRO
13
3k
Kaigi on Rails 2024 - Rails APIモードのためのシンプルで効果的なCSRF対策 / kaigionrails-2024-csrf
corocn
5
3.4k
Generative AI Use Cases JP (略称:GenU)奮闘記
hideg
0
160
Dev ContainersとGitHub Codespacesの素敵な関係
ymd65536
1
130
EventSourcingの理想と現実
wenas
6
2.1k
Honoの来た道とこれから
yusukebe
19
3.1k
Featured
See All Featured
No one is an island. Learnings from fostering a developers community.
thoeni
19
3k
Designing Experiences People Love
moore
138
23k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
191
16k
Navigating Team Friction
lara
183
14k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
159
15k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
26
1.4k
Done Done
chrislema
181
16k
4 Signs Your Business is Dying
shpigford
180
21k
Reflections from 52 weeks, 52 projects
jeffersonlam
346
20k
Build your cross-platform service in a week with App Engine
jlugia
229
18k
Bootstrapping a Software Product
garrettdimon
PRO
305
110k
What's new in Ruby 2.0
geeforr
342
31k
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