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
SwiftUI Viewの責務分離
elmetal
PRO
0
140
Unity Android XR入門
sakutama_11
0
140
密集、ドキュメントのコロケーション with AWS Lambda
satoshi256kbyte
0
170
Formの複雑さに立ち向かう
bmthd
1
720
『品質』という言葉が嫌いな理由
korimu
0
160
AWS Lambda functions with C# 用の Dev Container Template を作ってみた件
mappie_kochi
0
240
Honoをフロントエンドで使う 3つのやり方
yusukebe
4
2.1k
Writing documentation can be fun with plugin system
okuramasafumi
0
120
SwiftUIで単方向アーキテクチャを導入して得られた成果
takuyaosawa
0
260
Java Webフレームワークの現状 / java web framework at burikaigi
kishida
9
2.2k
時計仕掛けのCompose
mkeeda
1
280
第3回 Snowflake 中部ユーザ会- dbt × Snowflake ハンズオン
hoto17296
4
360
Featured
See All Featured
The Power of CSS Pseudo Elements
geoffreycrofte
75
5.5k
Producing Creativity
orderedlist
PRO
343
39k
Mobile First: as difficult as doing things right
swwweet
223
9.3k
Improving Core Web Vitals using Speculation Rules API
sergeychernyshev
8
270
Building an army of robots
kneath
302
45k
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
27
1.9k
Fireside Chat
paigeccino
34
3.2k
Making Projects Easy
brettharned
116
6k
Done Done
chrislema
182
16k
Rails Girls Zürich Keynote
gr2m
94
13k
Dealing with People You Can't Stand - Big Design 2015
cassininazir
366
25k
XXLCSS - How to scale CSS and keep your sanity
sugarenia
248
1.3M
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