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
Software Architecture
hschwentner
6
2.1k
Spring gRPC について / About Spring gRPC
mackey0225
0
220
sappoRo.R #12 初心者セッション
kosugitti
0
230
Rails アプリ地図考 Flush Cut
makicamel
1
110
AWSマネコンに複数のアカウントで入れるようになりました
yuhta28
2
160
How mixi2 Uses TiDB for SNS Scalability and Performance
kanmo
30
11k
Kanzawa.rbのLT大会を支える技術の裏側を変更する Ruby on Rails + Litestream 編
muryoimpl
0
220
Honoとフロントエンドの 型安全性について
yodaka
4
250
[JAWS-UG横浜 #80] うわっ…今年のServerless アップデート、少なすぎ…?
maroon1st
1
170
Amazon Q Developer Proで効率化するAPI開発入門
seike460
PRO
0
110
“あなた” の開発を支援する AI エージェント Bedrock Engineer / introducing-bedrock-engineer
gawa
11
1.8k
定理証明プラットフォーム lapisla.net
abap34
1
1.7k
Featured
See All Featured
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
6
540
Gamification - CAS2011
davidbonilla
80
5.1k
Into the Great Unknown - MozCon
thekraken
35
1.6k
How to Ace a Technical Interview
jacobian
276
23k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
33
2.1k
Writing Fast Ruby
sferik
628
61k
Sharpening the Axe: The Primacy of Toolmaking
bcantrill
40
2k
[RailsConf 2023] Rails as a piece of cake
palkan
53
5.2k
Fontdeck: Realign not Redesign
paulrobertlloyd
82
5.4k
No one is an island. Learnings from fostering a developers community.
thoeni
21
3.1k
How To Stay Up To Date on Web Technology
chriscoyier
790
250k
Site-Speed That Sticks
csswizardry
3
370
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