Skip to content

Instantly share code, notes, and snippets.

@duangsuse
Created October 5, 2018 14:14
Show Gist options
  • Save duangsuse/fc33ea2690d77a0cc1fe0f0a4ce8b4f2 to your computer and use it in GitHub Desktop.
Save duangsuse/fc33ea2690d77a0cc1fe0f0a4ce8b4f2 to your computer and use it in GitHub Desktop.
Sexp language reference

Sexp 程序设计语言 实现参考手册

Sexp 词法参考

Sexp 语言支持以下词条类型:

  • 字符串(支持 Heredoc 和 String interpolation)
  • 符号(symbol)
  • 字符(char)
  • 括号(方括号和圆括号)
  • 空值(nil
  • 布尔值(boolean
  • 数值(支持所有字类型、BigIntegerBigDecimal
  • 注释和空格(行注释和区间注释)
  • 正则表达式(/body/flags
  • 区间词法(0..1s1
  • 自定义符号词法

词法原则上不支持全角符号,并且应该是可以在字符流中识别分词的,以词条流的形式输出

字符串词法

'string
"string"
<<$END
string
END
  <<|END
  string
  END
"string\n\"\t"
'single\ quoted\
next\ line
"string ${"interpolation"}"
"1 + 1 = $(+ 1 1)"
"1 e 10 + 2 = $[** (+ 2 10) 1]"
(define hello (name)
  (r "Hello, $name.!"))

字符串文本是不能跨行的,Heredoc 则必须是跨行的,Heredoc 不处理任何转义字符

请注意,Sexp 为了支持递归文法,表达式内联是在解析阶段重新分词的,内联表达式中显然不能出现 } 字符

变量引用内联则支持以下语法: "Hi $name" "Hello $name.!" (以 . 切分变量名)

为尽可能简化词法,$() 内联只专门支持一级内联(调用),即不能出现第二个闭括号,但可以使用 []

字符串标记

r"Raw String"
b"String Bytes"
x"CString Bytes"
c"Char Byte"
s"Blank-splited string array"
w"String character array"
  • Raw String 不会处理任何逃逸(转义)字符,只以 " 作为字符串结尾
  • String Bytes 创建一个 byte[] 数组
  • CString Bytes 创建一个以 \00 结束的 C 字符串 byte[] 数组
  • Char Byte 创建一个 byte 表示内部的 ASCII 字符
  • Blank-splited string array 创建一个数组 "as ba cs" => ["as", "ba", "cs"]
  • String character array 创建一个 char[] 数组

标记可以不被放在后面的原因是 flag 只有一个字符,性能和实现复杂的问题可以无视

符号词法

symbol

符号即为 Sexp 语言中的标识符,默认不可识别的文法即作为标识符

字符词法

'c' ; 必须在 *单个字符* 后加上单引号,否则作为字符串

'string\ no\ spaces' ; 创建一个字符 Buffer 序列,而不是字符串对象
; 其与 ' 字符串的区别在于以 ' 结尾

括号词法

(paren)
[paren]
(([] [()]))

[]() 语义上是等价的,唯一的要求是必须匹配

括号文法用于创建 S 表达式列表

空值词法

null
nil
#n
() ; 词法上的 ()

布尔词法

#t
#f
true
false

数值词法

01 0x1 0b1001 0o122 2323N 32323R 2233.223F 66666L 6B 1_000

Sexp 支持所有常用的 Java 数值类型字面

0x 代表十六进制,其数字部分必须小写

0b 代表二进制

0o 代表八进制

默认为十进制

包含 . 代表是小数,不过,只有在使用十进制表示时其能正常工作(显然没人会用二进制或十六进制表示小数,一般此文法被仅用来进行位运算)

_ 默认被无视

- 作为负号必须出现在第一位,而 Sexp 数值文法不支持默认的正号

N 代表 NatureBigInteger) 数,R 代表 RealBigDecimal

其它自长度从小到大依次是 B S I L F D,类型标识必须大写并且在最后一位,默认小数类型为 Double,整数为 Integer

Sexp 支持 1E10 这种 Exponent 表示方法,写在类型标记前面 1E10D,不支持小写的 e,因为在解析十六进制时可能与数字部分混淆

注释和空格、换行

; 行注释
;- 块注释 -;

;- --  ;
 块注释
;  -- -;

EOF 为 0x04 0x1a 0(^D ^Z EOF)

换行为 [\r\n{EOF}]

空格为 [ \t{NL}\f\v]\v"\u000b"

通用逃逸字符为 \a\b\e\f\n\r\s\t\v\\

Unicode 逃逸字符: \uXXXX \UXXXXXXXX

Ascii 逃逸字符: \xXX

" 字符串中可以使用这些 \"

' 中还可以使用 \<newline> \<space> 逃逸字符

正则表达式

/regexBody/idmsuxU

创建 Java Pattern 对象,/ 前为 flags

仅允许 Escape \/ 代表正则内部出现的 /,因为正则引擎会自己处理其他逃逸字符

为了提高解析性能和优化词法统一可猜测性,flags 放在后面,并且第一个字符不能是空格,不然作为 / 符号识别

正则表达式在分词器中应该作为可选语法,即可以动态调整的语法使用

额外添加语言分词器使用的 flag E 代表空格会被 \<space> 表示,用于解决第一个字符不能是空格的词法冲突问题

区间

0..1 开区间

0...1 左开右闭区间

0..10s2 2 步数区间

为了与标识符词法区别,区间的左部必须是数字,如果不是,一般使用内部库函数创建区间

(.. a b step) (... a b step)

否则,0rstart..end 也可以表示 (start, end) 区间

自定义符号词法

你可以设置一个字符为自定义一元运算符,这样,它在解析阶段就会被结合为这样:

(define-syntax ': (lambda (e)
  (display e)))

:1 ; (display e) ; e = 1
:(too young) ;(:too :young)

规则 : 会匹配类似 <space>: 这样的流(而实际上,它识别任何以 : 起始的词条,这和词条切分有关)

Sexp 语法

Sexp 使用堆解析器来构造 S-表达式列表 Java 对象,而不是递归下降法,它在顶层支持这种语法:

1 (2 3) (4 (5) 'string)

Sexp PIRV 编译器会把所有顶层语句逐个编译成字节码,顶层语句和内部语句其实是类似的

(lambda (r 1 (23) (4 (5) 'string)))

Sexp 的解析器 HeapParser 会在顶层的解析结果顶部放置 (r),此后你的代码都在 r 函数参数求值环境中执行

Lambda 里则不会帮你添加 r,所以那里只能使用一个函数调用(也可以自己加 r

执行(展开)规则

  1. (symbol arglist) => resolve(symbol)(eval(arglist));
  2. (closure-value arglist) => closure-value(eval(arglist));
  3. ((closure sexp) arglist) => eval(closure sexp)(eval(arglist));
  4. () => null
  5. object => object
  6. symbol => resolve(symbol);

闭包创建

使用 lambda 闭包来创建闭包 (lambda (args) body)

Sexp 不支持 rest 参数optional 参数 但支持传统 vararg

(lambda (vararg) (r 1))

(lambda (a b c)
  (+ a (- b c)))

闭包标记

  • noarg(无参数)
  • onearg(一个参数)
  • twoarg(两个参数)
  • threearg(三个参数)
  • vararg(不定参)
  • append(前置执行)
  • eval(call-by-name 即时求值)
  • lazy(call-by-need 延迟求值)
  • pure(纯函数)
  • noreturn(不会返回的函数)
  • void(不需要返回值的函数)
  • inline(指定内联函数)
  • internal(代表内部执行器的函数)
  • noexcept(不会抛出异常的函数)
  • nobind(不包含自由变量引用)
  • optimized(内部加速指令代表的函数)
  • tailrec(尾递归函数)
  • coroutine(携程函数,这个标识给人看的)

流程控制

  • yield 提前返回
  • label 定义标记
  • goto 转到标记执行
(label 'a)
(print 1)
(goto 'a)

(print 1 yield 2) ; 2: never reached
(r 'foo yield 'bar) ; => 'foo

(r 1 2 3) ; 返回 3(最后一个被求值的参数)

(if cond_expr (r code))
(unless cond_expr (r code))
(when expr
  "1" (display "Foo")
  "2" (display "bar")
  'is Float (display "Bad")
  'typed 'double (display "Good"))

(case expr
  1 (r 1)
  (r 0))

(set! v (cond
  (eq .gets "OK") #t
  else #f))

(loop (display "Tee"))
(loopn 10 (display "10 times"))

(let val = true
  (while val (set! val false)))

(eval '(display 1))
(eval (list :display "Hello"))

(apply set! 'foo' 1)

(eq? a 1) ; value compare
(eql? a a)

异常处理

Sexp PIRV 对代码的执行是基于调用栈帧的,每个函数都会在新建的栈帧上执行,而它们的参数在本层栈帧求值

PIRV 的栈帧设置有异常捕获表,PIRV 可以捕获 Java 和 Sexp 内建的异常,尾调用优化不会影响到异常的捕捉

(define dangerous!
  (lambda (raise 'sample "Sample exception")))

(catch
  ('sample "Sample") (display "Sample exception")
  (dangerous!))

Sexp 库函数

内部类型

字符串

字符

列表

空指针

布尔类型

数值类型

正则表达式类型

区间类型

Sexp 特殊类型

符号(Symbol)

引用(Box)

闭包(Closure)

上下文绑定(Binding)

配对(Pair)

异步任务(Promise)

状态(VMState)

自动类型转换和提升

Sexp PIRV 虚拟机

Sexp 是一个基于虚拟机的字节码解释型语言,Scheme 代码通过 pirv.Compiler 翻译为中间语言,并随后在 pirv.ParenVM 中解释执行

实现的大部分字节码设计基于 R. Kent Dybvig 1987 年发布的论文 《三种 Scheme 实现模型》

虚拟机状态

由于 Java 拥有高层运行环境而且提供了丰富的函数库,PIRV 不需要跟踪栈大小、栈顶地址以及手动维护调用栈

class ParenStackFrame {
    val closure: Closure
    val stack: Stack<Any?>
    val retAddress: Int
    val chain: ParenStackFrame?
    val errorHandlers: ArrayMap<String, Closure>
    var tcoCounter: Int
}

class ParenVMState {
    val controlFrames: Stack<ParenStackFrame>
    val globals: HashMap<Symbol, Any?>
    var value: Any?
    var pc: Int
}

虚拟机指令

const 指令 - 设置 value 寄存器

arg 指令 - 将 value 压入执行栈

test 指令 - 进行流程分支

closure 指令 - 创建 Closure

save 指令 - 捕获程序执行状态

restore 指令 - 恢复程序执行状态

halt 指令 - 终止程序执行

frame 指令 - 压入执行栈帧

apply 指令 - 执行函数

tailapply 指令 - 尾调用优化的 apply (记录尾调用堆栈)

return 指令 - 从函数中返回

shift 指令 - 抛弃栈帧实际执行尾调用优化

getlocal

getcapture

getglobal

setlocal

setcapture

setglobal

boxit

unwrap

jump

nop

trace

branchif

branchunless

branchnull

raise

catch

优化指令

dup

pop

tostring

putnull

toarray

puts

gets

once

plus

minus

multiply

divide

power

modulo

inc

dec

eq

eql

ne

lt

le

gt

ge

and

or

not

newlist

aget

aset

length

cons

car

cdr

指令序列化

Sexp AST 编译

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment