2020/05/19

2020/05/19

# xv6の構成要素の継続の分析

# 研究目的

  • OS自体そのものは高い信頼性が求められるが、 OSを構成するすべての処理をテストするのは困難である。
    • 実際に動かしてみないと解らないバグ, デッドロック問題などが存在する
  • 実装の時点で信頼性を高めたい
  • 実際にOS上に動くアプリケーションも、実行される前に事前にバグを検知したい
  • このOSを実装する前に、 小さなOSで再実装を行う
  • 小さなunixであるxv6 kernelを、状態遷移を基本とした単位でのプログラミングに適したCbCで再実装を行っている
  • このためには現状のxv6kernelの処理の状態遷移の分析が必要である。
    • その結果を、 継続ベースでのプログラミングに変換していく必要がある。
  • xv6kernelの構成要素の一部に着目し、状態遷移系の分析と状態遷移系を元に継続ベースでxv6の再実装を行う。

# 先週やったこと

  • TA関連
  • pro3の相談対応
  • 最後の親知らずを抜歯する
  • Gearsで下記散らかしていたPerlスクリプトを整理した
  • golangでインタプリタを書き始めた
    • Gears(CbC)でも実装し直していますが、う〜ん…
  • growi/hackmdのhttps対応
    • ついでに自分の個人サイトもリニューアル

# Gearsの整理

  • 自分で書いてて当時なぜ実装したのか覚えてないPerスクリプトが多数放置されていた
    • とりあえずrmした(hgで管理してるし…)
    • Pod書いてたスクリプトはちゃんと理解できた
      • SYNOPSISは大事ですね…
  • わりとGears忘れているのでリハビリ中…
    • そもそも今までどういう文法だったかをparallel_executionからおさらい
    • とりあえずxv6の書き換えを進めていきます

# golang製のインタプリタ

  • 積んでいたWriting An Interpreter In Goをやり始めた
  • monkeyインタプリタを実装する
    • 頑張って写経してレキサーまでは実装した
    • ただ実装するだけだと面白くないのでGearsに変換するのを考えている
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
package lexer

import "firefly/hg/Members/anatofuz/monkey/token"

// Lexer model
type Lexer struct {
	input        string
	position     int // current position in input (points to current char)
	readPosition int // current reading position in input(after current char)
	ch           byte
}

// New create Lexer instance and start lex
func New(input string) *Lexer {
	l := &Lexer{input: input}
	l.readChar()
	return l
}

func (l *Lexer) readChar() {
	if l.readPosition >= len(l.input) {
		l.ch = 0
	} else {
		l.ch = l.input[l.readPosition]
	}

	l.position = l.readPosition
	l.readPosition++
}

//NextToken is create token.Token after read from input
func (l *Lexer) NextToken() token.Token {
	var tok token.Token

	l.skipWhitespace()

	switch l.ch {
	case '=':
		tok = newToken(token.ASSIGN, l.ch)
	case '+':
		tok = newToken(token.PLUS, l.ch)
	case '-':
		tok = newToken(token.MINUS, l.ch)
	case '!':
		tok = newToken(token.BANG, l.ch)
	case '/':
		tok = newToken(token.SLASH, l.ch)
	case '*':
		tok = newToken(token.ASTERISK, l.ch)
	case '<':
		tok = newToken(token.LT, l.ch)
	case '>':
		tok = newToken(token.GT, l.ch)
	case ';':
		tok = newToken(token.SEMICOLON, l.ch)
	case ',':
		tok = newToken(token.COMMA, l.ch)
	case '(':
		tok = newToken(token.LPAREN, l.ch)
	case ')':
		tok = newToken(token.RPAREN, l.ch)
	case '{':
		tok = newToken(token.LBRACE, l.ch)
	case '}':
		tok = newToken(token.RBRACE, l.ch)
	case 0:
		tok.Literal = ""
		tok.Type = token.EOF

	default:
		if isLetter(l.ch) {
			tok.Literal = l.readIdentifier()
			tok.Type = token.LookupIdent(tok.Literal)
			return tok
		} else if isDigit(l.ch) {
			tok.Type = token.INT
			tok.Literal = l.readNumber()
			return tok
		} else {
			tok = newToken(token.ILLEGAL, l.ch)
		}

	}

	l.readChar()
	return tok
}

func newToken(tokenType token.TokenType, ch byte) token.Token {
	return token.Token{Type: tokenType, Literal: string(ch)}
}

func (l *Lexer) readIdentifier() string {
	position := l.position
	for isLetter(l.ch) {
		l.readChar()
	}
	return l.input[position:l.position]
}

func isLetter(ch byte) bool {
	return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' || ch == '_'
}

func (l *Lexer) skipWhitespace() {
	for l.ch == ' ' || l.ch == '\t' || l.ch == '\n' || l.ch == '\r' {
		l.readChar()
	}
}

func (l *Lexer) readNumber() string {
	positon := l.position
	for isDigit(l.ch) {
		l.readChar()
	}
	return l.input[positon:l.position]
}

func isDigit(ch byte) bool {
	return '0' <= ch && ch <= '9'
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package token

const (
	ILLEGAL = "ILLEGAL"
	EOF     = "EOF"

	IDENT = "IDENT"
	INT   = "INT"

	// Operators
	ASSIGN   = "="
	PLUS     = "+"
	MINUS    = "-"
	BANG     = "!"
	ASTERISK = "*"
	SLASH    = "/"

	LT = "<"
	GT = ">"

	COMMA     = ","
	SEMICOLON = ";"

	LPAREN = "("
	RPAREN = "("
	LBRACE = "{"
	RBRACE = "}"

	// Keywords
	FUNCTION = "FUNCTION"
	LET      = "LET"
	TRUE     = "TRUE"
	FALSE    = "FALSE"
	IF       = "IF"
	ELSE     = "ELSE"
	RETURN   = "RETURN"
)

type TokenType string

type Token struct {
	Type    TokenType
	Literal string
}

var keywords = map[string]TokenType{
	"fn":     FUNCTION,
	"let":    LET,
	"true":   TRUE,
	"false":  FALSE,
	"if":     IF,
	"else":   ELSE,
	"return": RETURN,
}

//LookupIdent is jugde ident or defined keywords
func LookupIdent(ident string) TokenType {
	if tok, ok := keywords[ident]; ok {
		return tok
	}
	return IDENT
}

# Gears製のインタプリタ

  • parallel_execution以下に例題として実装していく路線で…
  • とりあえずlexerのInterfaceとTokenのInterfaceを考えていた
    • 入出力はDataGearなので、 __code next(int len, ...) みたいなのはできない
    • 引数で __code hoge(Impl* foo, const char* ch) みたいにプリミティブ型を指定するのもダメそう
1
2
3
4
5
6
typedef struct lexer <Type, Impl> {
    __code read_char(Impl* lexer, string ch, __code next(... ));
    __code eat_whitespace(Impl* lexer, string ch, __code next(... ));
    __code next_token(Impl* lexer, __code next(struct token* tok, ...));
    __code next(....);
} lexer;
  • いろいろ考えるとnext_tokenだけで良さそう
    • 呼び出すたびにtokenが生成される
    • 呼び出すたびにlexer自体の状態が変化するのがちょっとアレな気はする
      • mapみたいなオペレーションが必要?
  • Gearsのリハビリも兼ねてとりあえず実装してみます

# growi/hackmdのhttps対応

Licensed under CC BY-NC-SA 4.0
comments powered by Disqus
Built with Hugo
Theme Stack designed by Jimmy