用Go语言实现的Scheme解释器

Question

用Go语言实现的Scheme解释器

gocompiler-constructionschemelispinterpreter

4

我是一名基础的Go程序员，我一直在研究这个小的Scheme解释器，并试图理解它的工作原理。

我在这里找到了它： https://pkelchte.wordpress.com/2013/12/31/scm-go/ 我阅读了网页，但仍然难以理解它的工作原理，因为源代码显然是由一个比我更熟悉Go的人编写的。

特别是这些行让我难以理解：

e := expression.(type) // Line 73

我不确定.(type)的含义是什么，我以为它是类型转换，但它看起来不像我之前见过的类型转换。

switch p := procedure.(type) {
case func(...scmer) scmer:
    value = p(args...)
case proc:
    en := &env{make(vars), p.en}
    switch params := p.params.(type) {
    case []scmer:
        for i, param := range params {
            en.vars[param.(symbol)] = args[i]
        }
    default:
        en.vars[params.(symbol)] = args
    }
    value = eval(p.body, en)

说实话，我并不是很理解这段代码。这里需要翻译的是第73到86行。

*tokens = (*tokens)[1:] // Line 208

我不确定这行代码的意思，因为它的语法很奇怪。我知道这是指针，并且括号是因为 * 的存在。但我不确定这行代码的作用。

最后是以下几行代码：

token := (*tokens)[0]
*tokens = (*tokens)[1:]
switch token {
case "(": //a list begins
    L := make([]scmer, 0)
    for (*tokens)[0] != ")" {
        if i := readFrom(tokens); i != symbol("") {
            L = append(L, i)
        }
    }
    *tokens = (*tokens)[1:]
    return L

我也不知道这些代码的作用。第198至209行。

如果您需要完整的代码，请参考以下。我知道它有250行，但我真的很希望能够尽可能多地解释它在做什么。

/*
 * A minimal Scheme interpreter, as seen in lis.py and SICP
 * http://norvig.com/lispy.html
 * http://mitpress.mit.edu/sicp/full-text/sicp/book/node77.html
 *
 * Pieter Kelchtermans 2013
 * LICENSE: WTFPL 2.0
 */
package main

import (
    "bufio"
    "fmt"
    "log"
    "os"
    "reflect"
    "strconv"
    "strings"
)

func main() {
    Repl()
}

/*
 Eval / Apply
*/

func eval(expression scmer, en *env) (value scmer) {
    switch e := expression.(type) {
    case number:
        value = e
    case symbol:
        value = en.Find(e).vars[e]
    case []scmer:
        switch car, _ := e[0].(symbol); car {
        case "quote":
            value = e[1]
        case "if":
            if eval(e[1], en).(bool) {
                value = eval(e[2], en)
            } else {
                value = eval(e[3], en)
            }
        case "set!":
            v := e[1].(symbol)
            en.Find(v).vars[v] = eval(e[2], en)
            value = "ok"
        case "define":
            en.vars[e[1].(symbol)] = eval(e[2], en)
            value = "ok"
        case "lambda":
            value = proc{e[1], e[2], en}
        case "begin":
            for _, i := range e[1:] {
                value = eval(i, en)
            }
        default:
            operands := e[1:]
            values := make([]scmer, len(operands))
            for i, x := range operands {
                values[i] = eval(x, en)
            }
            value = apply(eval(e[0], en), values)
        }
    default:
        log.Println("Unknown expression type - EVAL", e)
    }
    return
}

func apply(procedure scmer, args []scmer) (value scmer) {
    switch p := procedure.(type) {
    case func(...scmer) scmer:
        value = p(args...)
    case proc:
        en := &env{make(vars), p.en}
        switch params := p.params.(type) {
        case []scmer:
            for i, param := range params {
                en.vars[param.(symbol)] = args[i]
            }
        default:
            en.vars[params.(symbol)] = args
        }
        value = eval(p.body, en)
    default:
        log.Println("Unknown procedure type - APPLY", p)
    }
    return
}

type proc struct {
    params, body scmer
    en           *env
}

/*
 Environments
*/

type vars map[symbol]scmer
type env struct {
    vars
    outer *env
}

func (e *env) Find(s symbol) *env {
    if _, ok := e.vars[s]; ok {
        return e
    } else {
        return e.outer.Find(s)
    }
}

/*
 Primitives
*/

var globalenv env

func init() {
    globalenv = env{
        vars{ //aka an incomplete set of compiled-in functions
            "+": func(a ...scmer) scmer {
                v := a[0].(number)
                for _, i := range a[1:] {
                    v += i.(number)
                }
                return v
            },
            "-": func(a ...scmer) scmer {
                v := a[0].(number)
                for _, i := range a[1:] {
                    v -= i.(number)
                }
                return v
            },
            "*": func(a ...scmer) scmer {
                v := a[0].(number)
                for _, i := range a[1:] {
                    v *= i.(number)
                }
                return v
            },
            "/": func(a ...scmer) scmer {
                v := a[0].(number)
                for _, i := range a[1:] {
                    v /= i.(number)
                }
                return v
            },
            "<=": func(a ...scmer) scmer {
                return a[0].(number) <= a[1].(number)
            },
            "equal?": func(a ...scmer) scmer {
                return reflect.DeepEqual(a[0], a[1])
            },
            "cons": func(a ...scmer) scmer {
                switch car := a[0]; cdr := a[1].(type) {
                case []scmer:
                    return append([]scmer{car}, cdr...)
                default:
                    return []scmer{car, cdr}
                }
            },
            "car": func(a ...scmer) scmer {
                return a[0].([]scmer)[0]
            },
            "cdr": func(a ...scmer) scmer {
                return a[0].([]scmer)[1:]
            },
            "list": eval(read(
                "(lambda z z)"),
                &globalenv),
        },
        nil}
}

/*
 Parsing
*/

//symbols, numbers, expressions, procedures, lists, ... all implement this interface, which enables passing them along in the interpreter
type scmer interface{}

type symbol string  //symbols are represented by strings
type number float64 //numbers by float64

func read(s string) (expression scmer) {
    tokens := tokenize(s)
    return readFrom(&tokens)
}

//Syntactic Analysis
func readFrom(tokens *[]string) (expression scmer) {
    //pop first element from tokens
    token := (*tokens)[0]
    *tokens = (*tokens)[1:]
    switch token {
    case "(": //a list begins
        L := make([]scmer, 0)
        for (*tokens)[0] != ")" {
            if i := readFrom(tokens); i != symbol("") {
                L = append(L, i)
            }
        }
        *tokens = (*tokens)[1:]
        return L
    default: //an atom occurs
        if f, err := strconv.ParseFloat(token, 64); err == nil {
            return number(f)
        } else {
            return symbol(token)
        }
    }
}

//Lexical Analysis
func tokenize(s string) []string {
    return strings.Split(
        strings.Replace(strings.Replace(s, "(", "( ",
            -1), ")", " )",
            -1), " ")
}

/*
 Interactivity
*/

func String(v scmer) string {
    switch v := v.(type) {
    case []scmer:
        l := make([]string, len(v))
        for i, x := range v {
            l[i] = String(x)
        }
        return "(" + strings.Join(l, " ") + ")"
    default:
        return fmt.Sprint(v)
    }
}

func Repl() {
    scanner := bufio.NewScanner(os.Stdin)
    for fmt.Print("> "); scanner.Scan(); fmt.Print("> ") {
        fmt.Println("==>", String(eval(read(scanner.Text()), &globalenv)))
    }
}

- Francis

1

我认为，除非你已经实现了大量自己的 Lisp 解释器，否则 Lisp 解释器不是检查新语言的好选择。如果你对 LISP 感兴趣，请阅读《LISP 的起源》（http://lib.store.yahoo.net/lib/paulgraham/jmc.ps）（注：后缀为 Postscript 的文件）。 - Sylwester

相关：zygomys 是用 Go 编写的 Lisp 解释器。 - milahu

2个回答

2

e := expression.(type) 是一个类型断言。

switch p := procedure.(type) { （带有以下 case 语句）是一个类型开关。

*tokens = (*tokens)[1:] 是一个切片表达式，改变了存储在 *tokens 中的值。

token := (*tokens)[0]       // Set token to first element of tokens slice.
*tokens = (*tokens)[1:]     // Update tokens to remove first element.
switch token {              // Switch on token.
case "(": //a list begins   // If token is "("
    L := make([]scmer, 0)       // Make a new, empty slice.
    for (*tokens)[0] != ")" {   // While the first element of tokens is not ")":
                                    // Read from tokens; if not empty symbol:
        if i := readFrom(tokens); i != symbol("") {
            L = append(L, i)        // Add the token read (in i) to L.
        }
    }
    *tokens = (*tokens)[1:]     // Remove the first element from tokens.
    return L                    // Return the newly created slice.

- iant

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ferhatelmas · Accepted Answer

第一个是类型开关。您可以在此处了解更多信息。

第二个是像Python中的切片（如果您知道它，应该很熟悉）。

ls = ls[1:]

我们跳过第一个元素并获取切片/列表的其余部分。

根据您的评论，我认为这不是尝试使用golang的好起点。