hidekuno / go-scheme Goto Github PK

View Code? Open in Web Editor NEW

0.0 1.0 0.0 889 KB

Subset Scheme implements

Go 98.80% Dockerfile 0.35% JavaScript 0.79% Makefile 0.07%

golang scheme gtk2 docker sicp wasm

go-scheme's Introduction

Implementation of Scheme (subset version) by Go Lang

Overview

Implemented a Lisp for Go Lang lessons. (It's Scheme base)
As an implementation goal, we will provide an environment for easily operating a graphic program.

Quality

Level at which a simple program works
- https://github.com/hidekuno/go-scheme/blob/master/scheme/lisp_test.go
I confirmed that the SICP graphic language program works.
- https://github.com/hidekuno/picture-language

TEST & Run (CLI interpreter)

Requirement

go lang installed.

cd ${HOME}
git clone https://github.com/hidekuno/go-scheme
cd go-scheme/scheme
go test -v
go run cmd/lisp/main.go

TEST coverage(C0)

cd ${HOME}/go-scheme/scheme
go test -cover -coverprofile /tmp/cover.out
go tool cover -func=/tmp/cover.out

TEST Benchmark

cd ${HOME}/go-scheme/scheme
go test -bench .

TEST & Run (Scheme on GUI for Draw)

Requirement

X server is running.

cd ${HOME}/go-scheme/draw
go test -v
go run cmd/lisp/main.go

Then type "(draw-init)"

TEST & Run (Scheme on Web API Server)

cd {HOME}/go-scheme/web
go test -v
go run cmd/api/main.go

Build & Run (Scheme on Web Assembly)

cd {HOME}/go-scheme/web/wasm
cp /usr/local/go/misc/wasm/wasm_exec.js .
GOARCH=wasm GOOS=js go build -o lisp.wasm lisp_wasm.go
cd {HOME}/go-scheme/web
go run cmd/wasm/main.go

Run on docker

Requirement

docker is running.
X Server is running.(XQuartz 2.7.11 for mac)

Build(my operation log)

cd ${WHERE}/go-scheme/docker
docker build --target=go-scheme -t hidekuno/go-scheme --file=./Dockerfile .
docker login
docker push hidekuno/go-scheme
docker logout

macOS

docker pull hidekuno/go-scheme
xhost +
docker run -it --name go-scheme -e DISPLAY=docker.for.mac.localhost:0 hidekuno/go-scheme /root/glisp

Linux

docker pull hidekuno/go-scheme
xhost +
docker run -it --name go-scheme -e DISPLAY=${HOSTIP}:0.0 hidekuno/go-scheme /root/glisp

Windows11+WSL2+WSLg

docker pull hidekuno/go-scheme
docker run -it -v /tmp/.X11-unix:/tmp/.X11-unix -e DISPLAY=:0 --name go-scheme hidekuno/go-scheme /root/glisp

For environments where the X server is not running

docker pull hidekuno/go-scheme
docker run -it --name go-scheme hidekuno/go-scheme /root/lisp

go-scheme's People

Contributors

Watchers

go-scheme's Issues

仮想マシンを作る

コンパイラを作成する前に、まずVMを作る。

プログラムカウンタ(eip)
スタック(esp)
命令セット(インストラクション)
GCはGo任せなので、実装しない

整数値の実装を変更する

Bignumをサポートする
組み込み型をint->int64に変更する

Function:SetEnvメソッドの名前変更

SetNamebaseEnv
に変更

SICP図形言語を動かす

まずは,この規模のプログラムを動くか検証する
https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2.4

パフォーマンスが劣化する

実験結果はこの通り

[kunohi@centos7-dev-docker src]$ go run lisp_main_dev.go lisp.go
scheme.go>  (define test-list (map (lambda (n) (rand-integer 10000))(iota 600)))
test-list
scheme.go>  (define qsort
  (lambda (l)
    (if (null? l) l
        (append (qsort (filter (lambda (n) (< n (car l))) (cdr l)))
                (cons (car l) (qsort (filter (lambda (n) (not (< n (car l))))(cdr l)) ))))))
    qsort
scheme.go>  (time (qsort test-list))
740.788075ms
nil
scheme.go>  (time (qsort test-list))
2.624298923s
nil
scheme.go>  (time (qsort test-list))
4.897149342s
nil
scheme.go>  (time (qsort test-list))
7.732988955s
nil
scheme.go>

フラクタル言語

Schemeで記述できるようにする。

パッケージ構成を見直す

パッケージ名、ディレクトリ構成、ファイル名を見直す

プラットホーム、アーキテクチャによる振る舞いの違い

Linux 32bit

[hideki@gentoo src]$ go run lisp.go 
scheme.go>  (atan 1)
0.7853981633974483
scheme.go>  (define pi (* 4 (atan 1)))
pi
scheme.go>  pi
3.141592653589793
scheme.go>  (tan (/ (* 45 pi) 180))
0.9999999999999999
scheme.go>  (quit)
[hideki@gentoo src]$ uname -a
Linux gentoo.mukogawa.or.jp 2.6.18-411.el5 #1 SMP Mon Jul 11 18:16:41 CDT 2016 i686 i686 i386 GNU/Linux
[hideki@gentoo src]$

MacOSX 64bit

macbookair:src hideki$ go run lisp.go 
scheme.go>  (define pi (* 4 (atan 1)))
pi
scheme.go>  pi
3.141592653589793
scheme.go>  (tan (/ (* 45 pi) 180))
1
scheme.go>  (quit)
macbookair:src hideki$ uname -a
Darwin macbookair.local 17.6.0 Darwin Kernel Version 17.6.0: Tue May  8 15:22:16 PDT 2018; root:xnu-4570.61.1~1/RELEASE_X86_64 x86_64
macbookair:src hideki$

ネストされたlet式（環境) に対応

下記のような式に対応

((let ((a 10)) (lambda () (let ((a 20)) a))))

Webに対応する

いくつかのAPIを実装する
マルチユーザーに対応する(環境)

末尾再帰の実装

無理に実現はしない

文字型のサポート

こーゆーこと

gosh> (string->list "ABC")
(#\A #\B #\C)
gosh>

cond 構文の実装

力業で何とかなるが

0(ゼロ)除算、0(ゼロ)剰余演算のチェック

このままだとpanicになる

scheme.go>  (/ 10 0)
panic: runtime error: integer divide by zero

goroutine 1 [running]:
main.(*Integer).Div(0xc42000a800, 0x54cd40, 0xc42000a7a0, 0x7fbdef02e101, 0x54cd40)
        /home/kunohi/go-scheme/src/lisp.go:212 +0x70

Let式の中で複数の式を評価するようにした

diff --git a/src/lisp.go b/src/lisp.go
index 1c99d22..f90f552 100644
--- a/src/lisp.go
+++ b/src/lisp.go
@@ -1381,7 +1381,17 @@ func build_func() {
                if letsym != nil {
                        (*env).Regist(letsym.Value, NewLetLoop(NewList(pname), v[body]))
                }
-               return eval(v[body], NewSimpleEnv(env, &local_env))
+
+               nse := NewSimpleEnv(env, &local_env)
+               var last_exp Expression
+               for idx := body; idx < len(v); idx += 1 {
+                       if exp, err := eval(v[idx], nse); err == nil {
+                               last_exp = exp
+                       } else {
+                               return nil, err
+                       }
+               }
+               return last_exp, nil
        }

関数名、型名、変数名を規約に合わせる

スネークケース、もしくはconstでの使用(アンダースコアを排除する)

Dockerに対応する

CentOS7の公式を利用する

[kunohi@centos7-dev-docker ~]$ docker search centos --limit 5
NAME                          DESCRIPTION                                     STARS               OFFICIAL            AUTOMATED
centos                        The official build of CentOS.                   4553                [OK]
jdeathe/centos-ssh            CentOS-6 6.9 x86_64 / CentOS-7 7.4.1708 x86_…   98                                      [OK]
openshift/base-centos7        A Centos7 derived base image for Source-To-I…   31
pivotaldata/centos-gpdb-dev   CentOS image for GPDB development. Tag names…   6
pivotaldata/centos            Base centos, freshened up a little with a Do…   2
[kunohi@centos7-dev-docker ~]$

数学関数の対応

Sin cos

map関数で未定義変数でエラーにならなかった

scheme.go>  (map (lambda (n) (cons l n)) (iota 10))
((cons l n)(cons l n)(cons l n)(cons l n)(cons l n)(cons l n)(cons l n)(cons l n)(cons l n)(cons l n))
scheme.go>

Let loopの対応

検討

bsortでpanic

Or演算子で評価しないようにする

クォートに対応する

こーゆー記述に対応する

gosh> (list? '(1 2 3))
#t
gosh> (symbol? 'a)
#t
gosh>

ホワイトスペース(TAB,LF,CR)の扱い

式の中にホワイトスペース（空白を除く）が混じると、正常に評価されなくなる。

Web I/Fをマルチユーザーに対応する

気が向いた時にでも

いくつかのリスト関数、文字列関数、文字関数を実装

http://practical-scheme.net/gauche/man/gauche-refj/WenZi-.html#g_t_6587_5b57
http://practical-scheme.net/gauche/man/gauche-refj/WenZi-Lie-.html#g_t_6587_5b57_5217
http://practical-scheme.net/gauche/man/gauche-refj/peatorisuto.html#g_t_30da_30a2_3068_30ea_30b9_30c8
このあたりから、使えそーなものを

変数評価でpanic()が発生

今回の末尾再帰には関連性はないと思われる。（既存バグの可能性大)

[kunohi@centos7-dev-docker src]$ go run lisp.go lisp_main.go
scheme.go>  (let loop ((i 0)(j 10)(k 10)) (if (<= 1000000 i) i (if (= j k) (loop (+ 100 i)(+ 1 i)))))
panic: runtime error: index out of range

goroutine 1 [running]:
main.(*LetLoop).Execute(0xc42006c190, 0xc42000e4e0, 0xc420050290, 0x2, 0x3, 0x0, 0x0, 0x0, 0x0)

()を入力するとpanic

[kunohi@centos7-dev-docker src]$ go run lisp.go
scheme.go>  ()
panic: runtime error: index out of range

goroutine 1 [running]:
main.eval(0x548300, 0xc42007a240, 0xc42000e3d0, 0x548300, 0xc42007a240, 0x2, 0x0)
	/home/kunohi/go-scheme/src/lisp.go:616 +0xb7d
main.do_core_logic(0xc4200140bc, 0x2, 0xc42000e3d0, 0x400, 0xc4200140bc, 0x2, 0x0)
	/home/kunohi/go-scheme/src/lisp.go:667 +0xa8
main.do_interactive()
	/home/kunohi/go-scheme/src/lisp.go:693 +0x330
main.main()
	/home/kunohi/go-scheme/src/lisp.go:1217 +0x25
exit status 2
[kunohi@centos7-dev-docker src]$

有理数の対応

Gaucheでは

gosh> (/ 10 3)
10/3
gosh>

現状

scheme.go>  (/ 10 3)
3
scheme.go>

となる

drawツールがlisp対話モードでフリーズ

exitボタンをクリックするとフリーズする

データ型に情報を返すインターフェイス

Javaの Object.toString()のようなモノ

"("の評価で失敗する

Extra close parethesis `)` (list.go:669)

パラメータ評価の不具合

評価式が副作用に影響されている

scheme.go>  (let loop ((a (list 1 2 3))(b 0)) (if (null? a) b (loop (cdr a)(+ b (car a)\|                                return sexp, err                                         
))))                                                                                    |                        }                                                                
Not Enough Parameter Number                                                             |                        fn, ok := e.(*Function)                                          
scheme.go>  (let loop ((b 0)(a (list 1 2 3))) (if (null? a) b (loop (+ b (car a))(cdr a\|                        if !ok {                                                         
))))                                                                                    |                                return sexp, NewRuntimeError("Not Function")             
6                                                                                       |                        }                                                                
scheme.go>

#<undef> の実装追加(Nilクラスとして実装)

こーならないと、いけない

gosh> (cond ((not (= 1 1)) 10)) 
#<undef>
gosh>

パフォーマンス改善その２

単純に、eval()がcallされるので、こーなる。

scheme.go>  (let loop ((i 0)) (if (<= 1000000 i) i (loop (+ 1 i))))
runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

runtime stack:
runtime.throw(0x4eb3e1, 0xe)
        /usr/lib/golang/src/runtime/panic.go:605 +0x95
runtime.newstack(0x0)
        /usr/lib/golang/src/runtime/stack.go:1050 +0x6e1
runtime.morestack()
        /usr/lib/golang/src/runtime/asm_amd64.s:415 +0x86

loopが関数として評価されるため、eval()のcall回数が増大する

drawツールで画像が再描画されない

exposeイベントハンドラー内の問題？

パフォーマンスチューニング

学習用とはいえ、いくらなんでも、10万件のソートで14秒もかかるのは、如何なモノか。

scheme.go>  (define test-list (map (lambda (n) (rand-integer 10000))(iota 100000)))
test-list
scheme.go>  (define qsort (lambda (l)(if (null? l) l (append (qsort (filter (lambda (n) (< n (car l)))(cdr l)))(cons (car l)(qsort (filter (lambda (n) (not (< n (car l))))(cdr l\
))))))))
qsort
scheme.go>  (time (qsort test-list))
14.78499272s
nil
scheme.go>  (time (qsort test-list))
14.714609871s
nil
scheme.go>

パッケージ構成見直し

gtk, webが追加えない環境でも、lispだけは動くようにする

Web Assemblyを実装

学習のため

32bit環境のブラウザでは動作しない

遅延評価のサポート

delay, forceの実装

cons,appendの修正

(define hanoi                                                                                                                                                                     
  (lambda (from to work n)                                                                                                                                                        
    (if (>= 0 n) '() (append (hanoi from work to (- n 1)) (list (list (cons from to) n)) (hanoi work to from (- n 1))))))

グラフアプリを共通化

棒グラフ、折れ線グラフの処理を共通化

syntaxシュガーに対応する

こーゆー記述を許す

(define (gcm n m)(let ((mod (modulo n m)))(if (= mod 0) m (gcm m mod))))

簡易的なコンパイラを作る

仮想マシンが終わったあとで

Goroutine concurrency(並行/並列)

の対応

Mapの実装

Filter reduceを組み込む
Goshでサンプル作成

TEST コード強化

可能な限り書いて、Go言語の自動テストを見極める。

継続の実装

call/ccの実装

Windowが二重起動される

ロックをかけていないため、２重起動される。

階層化されたENV(名前空間)の対応

下記のようなコードに対応する

(define a 100)
(define (hoge)                                                                                                                                                                    
  (define a 20)                                                                                                                                                                   
  a)                                                                                                                                                                              
(define (foo)                                                                                                                                                                     
  (define a 30)                                                                                                                                                                   
  a)

Parser処理の不具合

[kunohi@centos7-dev-docker go-scheme]$ git diff a65e8a9deee6e813a6ce7e250f4d11251ed4b432 src/lisp.go
diff --git a/src/lisp.go b/src/lisp.go
index 11ad780..a393e2c 100644
--- a/src/lisp.go
+++ b/src/lisp.go
@@ -448,6 +448,11 @@ func create_ast(tokens []string) (Expression, int, error) {
 
                count := 1
                for {
+                       if tokens[0] == ")" {
+                               count = count + 1
+                               break
+                       }
+
                        exp, c, err := create_ast(tokens)
                        if err != nil {
                                return nil, c, err
@@ -460,10 +465,6 @@ func create_ast(tokens []string) (Expression, int, error) {
                                err := NewSyntaxError("unexpected ')' while reading")
                                return nil, 0, err
                        }
-                       if tokens[0] == ")" {
-                               count = count + 1
-                               break
-                       }
                }
                item := NewList(L)
                return item, count, nil
[kunohi@centos7-dev-docker go-scheme]$

hidekuno / go-scheme Goto Github PK

go-scheme's Introduction

Implementation of Scheme (subset version) by Go Lang

Overview

Quality

TEST & Run (CLI interpreter)

Requirement

TEST coverage(C0)

TEST Benchmark

TEST & Run (Scheme on GUI for Draw)

Requirement

TEST & Run (Scheme on Web API Server)

Build & Run (Scheme on Web Assembly)

Run on docker

Requirement

Build(my operation log)

macOS

Linux

Windows11+WSL2+WSLg

For environments where the X server is not running

go-scheme's People

Contributors

Watchers

go-scheme's Issues

Recommend Projects

Recommend Topics

Recommend Org