Slaying the Dragon: Implementing a Programming Language in Ruby

1.
SLAYINGTHEDRAGON

2.
AGUIDETOIMPLEMENTINGYOUROWN PROGRAMMINGLANGUAGE

3.
HELLO!

5.

7.

8.
¯ˉ_(ツ)_/¯ˉ

9.
FUN!

10.
UNDERSTANDHOWPROGRAMMING LANGUAGESWORK

11.
SystemStackError

12.
def case_when n case n when :foo 42 when :bar 88 when :foobar 4288 end end def hash_lookup n { foo: 42 bar: 88 foobar: 4288 }[n] end

13.
UNDERSTANDHOWCOMPUTERS WORK

14.
If you don'tknow how compilers work, then you don't know how computers work. - Steve Yegge (http://steve-yegge.blogspot.sg/2007/06/rich-programmer-food.html)

15.
LET'SMAKEALISP

16.
SUPEREASYTOIMPLEMENT

17.
The "most powerfullanguage in the world” that can be defined in "a page of code." - Alan Kay

18.
HOMOICONIC

19.
TONSOFGUIDESONLINE

20.
norvig.com/lispy.html

21.
buildyourownlisp.com

22.
github.com/kanaka/mal

23.
MAL

24.
mal>

25.
mal> (+ 2 6)

26.
mal> (+ 2 6) => 8 mal>

27.
mal> (+ 2 6) => 8 mal> LISP FORM

28.
mal> (+ 2 6) => 8 mal> (-‐ 4 8)

29.
mal> (+ 2 6) => 8 mal> (-‐ 4 8) => -‐4 mal>

30.
mal> (+ 2 6) => 8 mal> (-‐ 4 8) => -‐4 mal> (+ (-‐ 4 8) 10)

31.
mal> (+ 2 6) => 8 mal> (-‐ 4 8) => -‐4 mal> (+ (-‐ 4 8) 10) => 6 mal>

32.
mal> (+ 2 6) => 8 mal> (-‐ 4 8) => -‐4 mal> (+ (-‐ 4 8) 10) => 6 mal> (< 4 10)

33.
mal> (+ 2 6) => 8 mal> (-‐ 4 8) => -‐4 mal> (+ (-‐ 4 8) 10) => 6 mal> (< 4 10) true

34.
mal>

35.
mal> (if (< 4 10) 42 88)

36.
mal> (if (< 4 10) 42 88) => 42

37.
mal>

38.
mal> (fn* [x] (* x x)) => #<function> mal>

39.
mal> (fn* [x] (* x x)) => #<function> mal> PARAMS

40.
mal> (fn* [x] (* x x)) => #<function> mal> FUNCTION BODY

41.
irb> lambda { |x| x * x }

42.
mal> (fn* [x] (* x x)) => #<function> mal> ((fn* [x] (* x x)) 8)

43.
mal> (fn* [x] (* x x)) => #<function> mal> ((fn* [x] (* x x)) 8) => 64

44.
mal> (fn* [x] (* x x)) => #<function> mal> ((fn* [x] (* x x)) 8) => 64 FUNCTION THAT YOU WANT TO CALL

45.
mal> (fn* [x] (* x x)) => #<function> mal> ((fn* [x] (* x x)) 8) => 64 ARGUMENTS

46.
irb> lambda { |x| x * x }.call 8

47.
mal> (fn* [x] (* x x)) => #<function> mal> ((fn* [x] (* x x)) 8)) => 64 mal> (def sq (fn* [x] (* x x))) => #<function>

48.
mal> (fn* [x] (* x x)) => #<function> mal> ((fn* [x] (* x x)) 8)) => 64 mal> (def sq (fn* [x] (* x x))) => #<function> mal> (sq 8) => 64

49.
•  NOWYOUKNOW(BASIC)LISP!

50.
•  BEFOREWEDIVEIN

51.
•  RUBINIUS

52.
•  LLVM

53.
•  ALANGAUGEPLATFORM

54.
•  WHATTHEHECKISAVIRTUAL MACHINE?

55.
•  ANABSTRACTMACHINE

57.
•  LET’SDIVEIN!

58.
•  CUSTOMIZINGRUBINIUS’ COMPILATIONPIPELINE

60.
•  FILE|STRING

61.
•  FILE|STRING COMPILEDMETHOD

63.
•  CUSTOMIZETWOTHINGS INTHISPIPELINE

64.
•  PARSER

65.
•  ABSTRACTSYNTAXTREE PARSER

66.
•  MALPARSER

67.
TOKENIZER

68.
TOKENIZER READER

69.
TOKENIZER READER PARSINGLOGIC

70.
•  TOKENIZER

71.
(+ my_var 42)

72.
(+ my_var 42) ['(', '+', 'my_var', '42', ')']

73.
/[s,]*(~@|[[]{}()'`~^@]|"(?:.|[^"])*"|;.*|[^s[]{}('"`,;)]*)/

74.
•  LEXINGINRUBY

75.
[1] pry(main)>

76.
[1] pry(main)> require 'ripper' => true [2] pry(main)>

77.
[1] pry(main)> require 'ripper' => true [2] pry(main)> Ripper.lex 'foo = 123'

78.
[1] pry(main)> require 'ripper' => true [2] pry(main)> Ripper.lex 'foo = 123' => [[[1, 0], :on_ident, "foo"], [[1, 3], :on_sp, " "], [[1, 4], :on_op, "="], [[1, 5], :on_sp, " "], [[1, 6], :on_int, "123"]]

79.
(+ my_var 42) ['(', '+', 'my_var', '42', ')']

80.
•  READER

81.
['(', '+', 'my_var', '42', ')']

82.
['(', '+', 'my_var', '42', ')'] [:list, [:symbol, '+'], [:symbol, 'my_var'], [:integer, 42]]

83.
•  MALGRAMMAR

85.

86.

87.

88.

89.
<form> ::= <list> | <atom> def read_form(tokens) if tokens.first =~ /((|[)/ read_list(tokens) else read_atom(tokens.shift) end end

90.

91.
<list> ::= '(' <form>* ')' | '[' <form>* ']' def read_list(tokens) list = [:list] tokens.shift # pop our opening paren while tokens.first !~ /()|])/ list << read_form(tokens) end tokens.shift # pop our closing paren list end

92.

93.
<atom> ::= a-‐z+ | 0-‐9+ | true | false def read_atom(token) case token when /^-‐?d+$/ [:integer, token.to_i] when 'true' [:boolean, :true] when 'false' [:boolean, :false] when /^D+$/ [:symbol, token] else raise 'Reader error: Unknown token' end end

94.
['(', '+', 'my_var', '42', ')'] (+ my_var 42) [:list, [:symbol, '+'], [:symbol, 'my_var'], [:integer, 42]]

95.
•  PARSINGLOGIC

96.
•  ABSTRACTSYNTAXTREES

97.
(+ my_var 42)

98.
(+ my_var 42)

99.
(+ my_var 42) LEFT HAND SIDE

100.
(+ my_var 42) LEFT HAND SIDE RIGHT HAND SIDE

101.
(+ my_var 42) AddNode.new(SymbolNode.new('my_var'), IntegerNode.new(42)) LEFT HAND SIDE RIGHT HAND SIDE

102.
(if (< n 2) 42 88)

103.
(if (< n 2) 42 88)

104.
(if (< n 2) 42 88) CONDITIONAL

105.
(if (< n 2) 42 88) CONDITIONAL THEN BRANCH

106.
(if (< n 2) 42 88) CONDITIONAL THEN BRANCH ELSE BRANCH

107.
(if (< n 2) 42 88) if_node = IfNode( LessThanNode( SymbolNode('n'), IntegerNode(2) ), IntegerNode(42), IntegerNode(88) ) CONDITIONAL THEN BRANCH ELSE BRANCH

108.
if_node.condition => LessThanNode( SymbolNode('n'), IntegerNode(2) )

109.
if_node.condition => LessThanNode( SymbolNode('n'), IntegerNode(2) ) if_node.then_branch => IntegerNode(42)

110.
if_node.condition => LessThanNode( SymbolNode('n'), IntegerNode(2) ) if_node.then_branch => IntegerNode(42) if_node.else_branch => IntegerNode(88)

111.
def parse_sexp(sexp) type, *rest = sexp case type when :boolean boolean = sexp.last if boolean == :true Malady::AST::TrueBooleanNode.new else Malady::AST::FalseBooleanNode.new end when :symbol name = sexp.last builtins.fetch(name, Malady::AST::SymbolNode.new(name) when :integer Malady::AST::IntegerNode.new sexp[1] when :list rest.map { |sexp| parse(sexp) } end end

112.
•  RUBINIUSBYTECODE

113.
•  STACKBASEDVM

114.
1 + 2

115.
STACK 1 + 2 INSTRUCTIONS

116.
STACK 1 + 2 push 1 INSTRUCTIONS

117.
STACK 1 + 2 push 1 INSTRUCTIONS 1

118.
STACK 1 + 2 push 1 push 2 INSTRUCTIONS 1

119.
STACK 1 + 2 push 1 push 2 INSTRUCTIONS 1 2

120.
STACK 1 + 2 push 1 push 2 add INSTRUCTIONS 1 2

121.
STACK 1 + 2 push 1 push 2 add INSTRUCTIONS 3

122.
•  RUBINIUSBYTECODE

123.
-‐> % rbx compile -‐B -‐e '123+42' ============= :__script__ ============== Arguments: 0 required, 0 post, 0 total Arity: 0 Locals: 0 Stack size: 2 Literals: 1: :+ Lines to IP: 1: 0..9 0000: push_int 123 0002: push_int 42 0004: send_stack :+, 1 0007: pop 0008: push_true 0009: ret -‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐

124.
•  GENERATINGBYTECODE

126.
class IntegerNode < Node attr_reader :value def initialize(value) @value = value end def bytecode(g) pos(g) g.push_int value end end

127.
class AddNode < Node def initialize(lhs, rhs) @lhs, @rhs = lhs, rhs end def bytecode(g) pos(g) lhs.bytecode(g) rhs.bytecode(g) g.send(:+, 1) end end

128.
class IfNode < Node attr_reader :condition, :then_branch, :else_branch def initialize(filename, line, condition, then_branch, else_branch) super @condition = condition @then_branch = then_branch @else_branch = else_branch end def bytecode(g) pos(g) end_label = g.new_label else_label = g.new_label condition.bytecode(g) g.goto_if_false else_label then_branch.bytecode(g) g.goto end_label else_label.set! else_branch.bytecode(g) end_label.set! end end

129.
class IfNode < Node ... def bytecode(g) pos(g) end_label = g.new_label else_label = g.new_label condition.bytecode(g) g.goto_if_false else_label then_branch.bytecode(g) g.goto end_label else_label.set! else_branch.bytecode(g) end_label.set! end end

130.

131.

132.

133.

134.

135.
•  NOWYOUHAVEAWORKING PROGRAMMINGLANGUAGE!

136.
•  WHERETOGETHELP?

137.
github.com/kanaka/mal

139.
github.com/queenfrankie/lani

140.
rubinius.com/doc/en/virtual-‐machine/instructions/

141.
github.com/jsyeo/malady

142.
•  QUESTIONS?

143.
•  POSTSCRIPT

144.
http://philosecurity.org/2009/01/12/interview-‐with-‐an-‐adware-‐author

145.
YODAWG

Slaying the Dragon: Implementing a Programming Language in Ruby

More Related Content

What's hot

Viewers also liked

Similar to Slaying the Dragon: Implementing a Programming Language in Ruby

Recently uploaded

Slaying the Dragon: Implementing a Programming Language in Ruby