标签: denotational-semantics

我发誓曾经有一件T恤出售,上面写着不朽的话:

什么部分

你不明白吗？

就我而言,答案就是......全部!

特别是,我经常在Haskell论文中看到这样的符号,但我不知道它的含义是什么.我不知道它应该是什么样的数学分支.

我当然认识到希腊字母的字母,以及诸如"∉"之类的符号(通常意味着某些东西不是一组的元素).

另一方面,我以前从未见过"⊢"(维基百科称它可能意味着"分区").我也不熟悉这里使用的vinculum.(通常它表示一个级分,但是这并不出现在这里是这种情况.)

如果有人至少可以告诉我从哪里开始想要理解这个符号海洋的含义,那将会有所帮助.

这里描述的Haskell的底部被认为是任何有错误,未终止或涉及无限循环的计算,是任何类型的......这是否特定于Haskell？我们知道在莱迪思理论中,还有一个概念Bottom......并且不应该根据定义的顺序定义底部？

我对指称语义的概念有点困惑.据我所知,指称语义应该描述函数和表达式如何在特定的编程语言中工作.用于描述这些功能以及它们如何工作的正确形式究竟是什么？究竟什么是"域",以及如何构建映射函数？

举个例子,"做Y同时Y"的映射函数是什么？

我一直在网上阅读大量资料,但这很难理解.这些描述是否类似于无上下文语法？

请让我知道,谢谢!

编辑

考虑以下关于参考ECMAScript语言规范的答案响应- 11.13.2化合物分配

考虑为什么这些,

javascript:
   o="";  o = o + (o+=1)    ; alert(o);
   o="";  o =     (o+=1) + o; alert(o);

不一样.从左到右的脚本评估存在时间语义问题(参考:ECMA规范. - 加法运算符).一个结果是+操作员不一定是可交换的.

这可以通过以下方式看出:

javascript:
   o=1;  o = o + (o+=1)    ; alert(o);
   o=1;  o =     (o+=1) + o; alert(o);

要么

javascript:
   o=" _ ";  o = o + (o+=1)    ; alert(o);
   o=" _ ";  o =     (o+=1) + o; alert(o);

懒惰的评估范例,由我错误地和不恰当地使用从而产生下面的问题,也是我个人工作方式的一个不好的属性.

原帖

以下考虑因素可能已经得到解决,但似乎没有.如果是这样,是否可以提供与讨论的链接？

Gecko Javascript运行时引擎的正式指称语义是一个谜.经验测试令人筋疲力尽,无法详尽无遗.

• 是否有可用的权威形式规范或官方参考,明确定义Gecko如何解释Javascript？

参考文献ECMAScript语言规范似乎不够,但是为这些脚本的混合提供了信任,例如, …

我理解(我认为)Haskell seq会(通常)将其第一个参数减少到WHNF,并在GHCi中看到这种行为:

?> let x = (trace "foo" Foo (trace "bar" Bar 100)) in seq x 0
foo
0

但是,虽然文档evaluate说它也减少了它对WHNF的参数,但看起来它实际上完全将其参数完全减少到正常形式:

?> let x = (trace "foo" Foo (trace "bar" Bar 100)) in evaluate x
foo
Foo bar
(Bar 100)

我可以确认这个(明显的)差异

?> let y = (trace "foo" Foo (trace "bar" Bar 100))
?> seq y 0
foo
0
?> :sprint y
y = <Foo> _

和

?> let z …

是否存在可以在类型检查器中指定某个计算是否可以保证终止的函数式语言？或者,你能在Haskell中做到这一点吗？

关于Haskell,在这个答案中,海报上写道

通常的思考方式是每个Haskell类型都被"解除" - 它包含⊥.也就是说,Bool对应{?, True, False}而不仅仅是{True, False}.这表示Haskell程序不能保证终止并且可以有例外.

另一方面,关于阿格达的这篇论文表明了这一点

正确的Agda程序是通过类型检查和终止检查的程序

即,所有Agda程序都将终止,并且Bool在Agda中完全对应{True, False}.

因此,例如,在Haskell中,您可以拥有类型的值IO a,这告诉类型检查器需要IO来计算相关值.你有一个类型Lifted a断言有问题的计算可能不会终止吗？也就是说,您允许非终止,但在类型系统中将其分开.(显然,就像在Agda中一样,你只能将值分成"绝对终止"和"可能不会终止")如果没有,是否有语言可以做到这一点？

我正在尝试在Haskell中编写一个程序来计算具有整数变量,一维(整数)数组和函数的命令式语言程序的指称语义.我开始的功能是这样的类型:

    progsem :: Prog -> State -> State

国家如下:

    type State (Name -> Int, Name -> Int -> Int)

第一部分是整数变量的值,而第二部分是特定索引处的数组变量的值.

该计划将具有以下品质:

• progsem将在程序执行后返回结果状态

• 函数有两个参数列表,一个用于整数变量,另一个用于数组变量.

• 函数是按值调用的结果

以下是命令式语言的抽象语法:

     -- names (variables) are just strings.
     type Name = String

     -- a program is a series (list) of function definitions, followed by a
     -- series of statements.
     type Prog = ([FunDefn],[Stmt])

     -- a statement is either...
     data Stmt =
         Assign Name Exp              -- ...assignment (<name> := <exp>;)
       | If BExp [Stmt] [Stmt]        -- ...if-then-else (if …

我的意思是,从定义来看:

fix f 是函数的最不固定点 f

换一种说法:

最不明确的x那样f x = x.

任何nullary类型的最小定义值是undefined.这里仍有一些含糊不清,undefined可能意味着"将抛出错误"(更好)或"永远不会终止"(更糟糕).正如推理和试验所显示的那样,fix (+1)并且fix pred :: Word两者似乎都没有接近终止(即使pred 0是一个错误),因此在这两种选择之间可能总是选择"永不终止"的更糟糕的一种.(可以逃脱的fix是无聊const 1,但稍后会.)

这不是有用的应用方式fix.

有用的应用方式fix是:

fix (\f x -> if x > 7 then f (x - 1) else x)

- 也就是说,使用fix神奇地产生递归函数.(这永远不会让我感到惊讶.)这可以被视为在两个函数之间进行选择:\f x -> f (x - 1)并且\_ x -> x,其中一个函数永远不会评估它的第一个绑定变量.这是一个危险的玩具,因为我们仍然可以得到意外地翻转即非终止了半个其领域一样容易作为一个函数> …