如何实现Prolog范式字符列表的常量空间高效读取
当使用chars(长度为1的原子组成的字符列表)表示文本时,在项中写入chars有以下可选方式:
"First,"双引号列表表示法(6.3.7)效率最高,至少需要n+2个字符,仅当Prolog标志double_quotes设为chars时可正常回读。['N',e,x,t,',']列表表示法至少需要2n+1个字符,写法相对简洁,但需通过ignore_ops(false)启用,读取时要匹配完全相同的运算符配置,鲁棒性较差。'.'('L','.'(a,'.'(s,'.'(t,'.'(',',[])))))范式表示法对列表也采用函数形式,至少需要7n+2个字符,虽字符数较多,但互操作性最优,既不依赖double_quotes标志,也不受各类运算符声明影响。
以范式表示法写入chars可实现常量空间开销,但读取环节实现更复杂:以'.'(a,开头的序列也可能指向'.'(a,Further,b)类项,朴素读取方案需等待完整字符列表读取完成再处理,会占用额外空间,而绝大多数场景下'.'(a,都是列表构造器'.'(a,Further)。
现需解决问题:如何在读取范式表示的项时,针对其中的chars部分实现常量辅助空间的高效读取?
为简化问题可仅考虑sampleterm/1类型的项,要求支持读取所有以范式编写的该类项,也可采用DCG形式实现,示例定义如下:
sampleterm([]). sampleterm(a). sampleterm(b). sampleterm('.'(E,Es)) :- % 合法列表构造器 sampleterm(E), sampleterm(Es). sampleterm('.'(E,F,G)) :- % 非列表构造器 sampleterm(E), sampleterm(F), sampleterm(G).
若可实现该空间高效读取能力,Scryer、Trealla等支持紧凑chars内部表示的Prolog系统可进一步提升性能,目前我尝试过read/1方法,但效果不理想。
内容的提问来源于stack exchange,提问作者false
相关产品推荐
相关产品推荐

