我花了一两个星期编写一个简单的逻辑解算器.构建它之后,我发现自己想知道它所解决的语言是否是图灵完备的.因此,我编写了一小组方程式,它们接受SKI组合子演算中的任何有效表达式,并生成包含该表达式的正常形式的结果集.由于SKI 是 Turing-complete,证明我的语言可以执行SKI将证明其图灵完整性.
然而,有一个小故障.解算器不会按正常顺序减少表达式.实际上它的作用是尝试每一个可能的减少订单.这意味着解决方案集通常很大.如果存在正常形式,它将存在于某处,但很难分辨到哪里.
这让我有两个问题:
我的语言图灵完整吗？或者我需要找到更好的证据吗？
解决方案的数量是输入的可计算函数吗？
(起初我假设解决方案集的大小在输入大小中是指数或因子.但仔细观察,这不是真的.你可以编写已经处于正常形式的巨大表达式,以及不终止的小表达式我有一种感觉,确定解决方案集的大小可能等于解决停机问题,但我不完全确定......)
我有一个有趣的问题,但我不确定如何用它来表达...
考虑lambda演算.对于给定的lambda表达式,有几种可能的缩减顺序.但其中一些不会终止,而另一些则会终止.
在lambda演算中,事实证明存在一个特定的减少顺序,如果实际存在,则保证总是以不可简化的解决方案终止.它被称为正常秩序.
我写了一个简单的逻辑解算器.但麻烦的是,它处理约束的顺序似乎对它是否找到任何解决方案产生了巨大影响.基本上,我想知道我的逻辑编程语言是否存在类似正常顺序的东西.(或者说,单纯的机器无法确定地解决这个问题.)
这就是我所追求的.据推测,答案关键取决于"简单逻辑解算器"到底是什么.所以我将尝试简要描述一下.
我的节目紧密地基于编程乐趣(Jeremy Gibbons&Oege de Moor)第9章中的组合系统.该语言具有以下结构:
求解器的输入是单个谓词.谓词可能涉及变量.求解器的输出为零或更多解.解决方案是一组变量赋值,它使谓词成为正确.
变量持有表达式.表达式是整数,变量名或子表达式的元组.
有一个等式谓词,用于比较表达式(不是谓词)的相等性.如果用其值替换每个(绑定)变量使两个表达式相同,则会感到满意.(特别是,每个变量都等于它自己,绑定与否.)这个谓词是使用统一来解决的.
还有AND和OR的运算符,它们以明显的方式工作.没有NOT运算符.
有一个"存在"运算符,它基本上创建局部变量.
定义命名谓词的工具支持递归循环.
关于逻辑编程的一个"有趣的事情"是,一旦你编写了一个命名谓词,它通常会向前和向后(有时甚至是横向).典型示例:用于连接两个列表的谓词也可用于将列表拆分为所有可能的对.
但有时向后运行谓词会导致无限搜索,除非您重新排列术语的顺序.(例如,交换一个AND的LHS和RHS或者一些OR.)我想知道是否有一些自动方法来检测运行谓词的最佳顺序,以确保在解决方案集完全正确的所有情况下立即终止有限.
有什么建议？
多少空间的STUArray使用Bool元素使用的每个元素？它真的把东西打包到一点吗？或者每个元素使用整个字节？
我已经看到一些消息来源随便提到"在Excel电子表格中使用Haskell"的想法- 好像这是每个人都熟悉和了解的东西.
这对我来说当然是个新闻.这个想法具有明显的吸引力--Haskell非常适合这种事情.但有没有人真正让这个工作？
如果GHC需要很长时间来编译某些东西,有没有办法找出它在做什么？
首先,我很高兴知道我是否真的崩溃了编译器(即,以某种方式将其置于某种无限循环中),或者它是否实际上正在取得进展,但速度非常慢.
其次,很高兴知道GHC编译过程的哪个部分遇到了麻烦.它是解析,desugaring,或类型检查,或核心优化,或代码生成,还是......？
有没有办法监控发生了什么？(请记住,如果GHC需要很长时间,这可能意味着它正在做很多工作,所以如果你要求太多的输出,它将是巨大的!)
GHC已经告诉你它正在尝试(重新)编译哪些模块.就我而言,问题是一个独立的模块.我想知道GHC陷入困境的地方.
好吧,所以这困扰了我一段时间,所以我想我会来问一个可能真正知道答案的人.
假设我有以下功能:
foobar x y = expensive x + cheap y
进一步假设该程序的一部分foobar 5作为输入,并在紧密循环中执行该功能数百万次.显然,我希望expensive 5计算一次,而不是一百万次.
我可以保留代码,或者我可以将其更改为
foobar x = let k = expensive x in \ y -> k + cheap y
这让我想知道......
GHC是否足够智能,可以自行消除重复的工作？(也就是说,第一个版本能做我想要的吗？)
如果不是,第二个版本是否确实解决了问题？(即,优化器是否会将其转换回与第一个版本相同的代码？)
通过对Haskell的各种类别的主题类各种教程阅读,我们发现之类的东西Monoid,Functor,Monad等等-所有这些有几十个实例.但出于某种原因,当我们到达时Arrow,只有两个实例:函数和monad.在这两种情况下,使用Arrow实例都不如直接使用底层事物那样强大且困难.
有没有人有任何有趣的箭头例子？我肯定肯定会有一些,但我从来没有遇到任何关于他们的文章......
好的,所以这是一个简单的问题.我写了一个函数debug :: String -> IO ().我想设置一下,这样当我以一种方式编译我的程序时,这个函数会写入标准错误,如果我以另一种方式编译我的程序,这个函数就变成了无操作.是否有一些简单的编译时间切换来做到这一点？或者我必须自己实施一些东西？
免责声明:这可以使用MVar ()简单的互斥锁轻松完成.我只是想知道它是否可以用STM完成.
我想原子地做以下事情:
阅读一些变量.
根据我刚刚阅读的内容决定要执行的I/O.
执行I/O.
将结果记录在变量中.
具体来说,假设我想跟踪我已读取的输入字节数,并假设在消耗了一定数量的字节后达到了EOF.(好吧,让两个线程同时从同一个文件中读取,可能是首先要做的事情,但请跟我一起去...)
显然,这不能是单个STM交易; 中间是I/O. 显然,将它作为两个未连接的交易也是错误的.(两个线程可以看到剩下一个字节的配额,并且都决定读取该字节.)
这个问题有一个很好的解决方案吗？或者STM只是这个任务的错误工具？
我正在尝试编写一个讨论二进制网络协议的小型Haskell程序,而且我遇到了一个令人惊讶的困难.
很明显二进制数据应该存储为ByteString.
问题:我应该hGet/ hPut单个多字节整数,还是更高效地构建ByteString整个事物并使用它？
看起来这个binary包应该在这里很有用.但是,binary只处理惰性 ByteString值.
问:是否hGet在偷懒 ByteString实际读取的字节严格的规定是多少？或者它是否尝试做某种懒惰的I/O？(我不想要懒惰的I/O!)
问题:为什么文档没有指定这个？
代码看起来会包含很多"获取下一个整数,将其与此值进行比较,如果没有则抛出错误,否则继续执行下一步..."我不确定如何干净地构造没有写意大利面条代码.
总之,我想要做的事情很简单,但我似乎正在努力寻找使代码看起来简单的方法.也许我只是过度思考这个并且遗漏了一些明显的东西......