#挑战30天在头条写日记#

高阶虚拟机 (HVM) 是一种纯函数式运行时，具有惰性、 无垃圾收集 和 大规模并行的特点 。它也是 beta 最优的 ，这意味着，对于高阶计算，在某些情况下，它可以比替代方案（包括 Haskell 的 GHC）快指数级（在渐近意义上）。

这是可能的，因为一种新的计算模型， 交互网络 ，它取代了 图灵机 和 Lambda 演算 。该模型以前的实现在实践中效率低下，但是最近的突破极大地提高了其效率，从而产生了 HVM。尽管相对较新，但它在某些情况下已经击败了成熟的编译器，并且正在不断改进。

欢迎来到计算机的大规模并行未来！

例子

本质上，HVM 是一种简约的函数式语言，被编译为基于交互网络的新型运行时。这种方法不仅内存效率高（不需要 GC），而且还有两个显着的优点： 自动并行性 和 beta 最优性 。这个想法是，您编写一个简单的功能程序，HVM 会将其转换为大规模并行、β 优化的可执行文件。下面的示例突出了这些实际优势。

冒泡排序

来自：HVM/examples/sort/bubble/main.hvm

来自：HVM/examples/sort/bubble/main.hs

// sort : List -> List
(Sort Nil)         = Nil
(Sort (Cons x xs)) = (Insert x (Sort xs))

// Insert : U60 -> List -> List
(Insert v Nil)         = (Cons v Nil)
(Insert v (Cons x xs)) = (SwapGT (> v x) v x xs)

// SwapGT : U60 -> U60 -> U60 -> List -> List
(SwapGT 0 v x xs) = (Cons v (Cons x xs))
(SwapGT 1 v x xs) = (Cons x (Insert v xs))

sort' :: List -> List
sort' Nil         = Nil
sort' (Cons x xs) = insert x (sort' xs)

insert :: Word64 -> List -> List
insert v Nil         = Cons v Nil
insert v (Cons x xs) = swapGT (if v > x then 1 else 0) v x xs

swapGT :: Word64 -> Word64 -> Word64 -> List -> List
swapGT 0 v x xs = Cons v (Cons x xs)
swapGT 1 v x xs = Cons x (insert v xs)

hvm是什么模块,hvm是什么线

在此示例中，我们在 HVM 和 GHC（Haskell 的编译器）上运行简单的递归冒泡排序。请注意，算法是相同的。该图表显示每个运行时对给定大小的列表进行排序所花费的时间（越低越好）。紫色线显示 GHC（单线程），绿色线显示 HVM（1、2、4 和 8 线程）。正如您所看到的，两者的性能相似，但 HVM 具有较小的优势。遗憾的是，它的性能并没有随着内核的增加而提高。那是因为冒泡排序本质上是一种顺序算法，因此 HVM 无法对其进行改进。

基数排序

来自：HVM/examples/sort/radix/main.hvm

来自：HVM/examples/sort/radix/main.hs

// Sort : Arr -> Arr
(Sort t) = (ToArr 0 (ToMap t))

// ToMap : Arr -> Map
(ToMap Null)       = Free
(ToMap (Leaf a))   = (Radix a)
(ToMap (Node a b)) =
  (Merge (ToMap a) (ToMap b))

// ToArr : Map -> Arr
(ToArr x Free) = Null
(ToArr x Used) = (Leaf x)
(ToArr x (Both a b)) =
  let a = (ToArr (+ (* x 2) 0) a)
  let b = (ToArr (+ (* x 2) 1) b)
  (Node a b)

// Merge : Map -> Map -> Map
(Merge Free       Free)       = Free
(Merge Free       Used)       = Used
(Merge Used       Free)       = Used
(Merge Used       Used)       = Used
(Merge Free       (Both c d)) = (Both c d)
(Merge (Both a b) Free)       = (Both a b)
(Merge (Both a b) (Both c d)) =
  (Both (Merge a c) (Merge b d))

sort :: Arr -> Arr
sort t = toArr 0 (toMap t)

toMap :: Arr -> Map
toMap Null       = Free
toMap (Leaf a)   = radix a
toMap (Node a b) =
  merge (toMap a) (toMap b)

toArr :: Word64 -> Map -> Arr
toArr x Free       = Null
toArr x Used       = Leaf x
toArr x (Both a b) =
  let a' = toArr (x * 2 + 0) a
      b' = toArr (x * 2 + 1) b
  in Node a' b'

merge :: Map -> Map -> Map
merge Free       Free       = Free
merge Free       Used       = Used
merge Used       Free       = Used
merge Used       Used       = Used
merge Free       (Both c d) = (Both c d)
merge (Both a b) Free       = (Both a b)
merge (Both a b) (Both c d) =
  (Both (merge a c) (merge b d))

hvm是什么模块,hvm是什么线

在此示例中，我们尝试基于合并不可变树的基数排序。在这个测试中，目前，单线程性能优于 GHC - 而且这种情况经常发生，因为 GHC 更老并且具有更多的微优化 - 然而，由于该算法本质上是并行的，HVM 能够超越GHC 给予足够的核心。通过 8 个线程 ，HVM 对大型列表进行排序的速度比 GHC 快 2.5 倍。

请记住，可以使用par注释并行化 Haskell 版本，但这需要耗时、昂贵的重构 - 并且在某些情况下，甚至不可能单独使用所有可用的并行性par 。另一方面，HVM 将自动通过所有可用内核分配并行工作负载，从而实现水平可扩展性。随着HVM的成熟，单线程差距将显着缩小。

拉姆达乘法

来自：HVM/examples/lambda/multiplication/main.hvm

来自：HVM/examples/lambda/multiplication/main.hs

// Increments a Bits by 1
// Inc : Bits -> Bits
(Inc xs) = λex λox λix
  let e = ex
  let o = ix
  let i = λp (ox (Inc p))
  (xs e o i)

// Adds two Bits
// Add : Bits -> Bits -> Bits
(Add xs ys) = (App xs λx(Inc x) ys)

// Multiplies two Bits
// Mul : Bits -> Bits -> Bits
(Mul xs ys) =
  let e = End
  let o = λp (B0 (Mul p ys))
  let i = λp (Add ys (B0 (Mul p ys)))
  (xs e o i)

-- Increments a Bits by 1
inc :: Bits -> Bits
inc xs = Bits $ \ex -> \ox -> \ix ->
  let e = ex
      o = ix
      i = \p -> ox (inc p)
  in get xs e o i

-- Adds two Bits
add :: Bits -> Bits -> Bits
add xs ys = app xs (\x -> inc x) ys

-- Muls two Bits
mul :: Bits -> Bits -> Bits
mul xs ys =
  let e = end
      o = \p -> b0 (mul p ys)
      i = \p -> add ys (b0 (mul p ys))
  in get xs e o i

hvm是什么模块,hvm是什么线

此示例使用λ 编码实现按位乘法。其目的是展示 HVM 的另一个重要优势：beta 最优性。该图表没有错误：HVM 乘以 λ 编码数的 速度比 GHC 快得多 ，因为它可以处理具有最优渐近性的高阶程序，而 GHC 则不能。尽管这项技术看起来很深奥，但它实际上对于设计高效的函数算法非常有用。例如，一种应用程序是为不可变数据类型实现运行时砍伐森林。一般来说，HVM 能够2^n在线性时间内应用任何可熔函数时间，这听起来不可能，但确实如此。

在plotly.com上制作的图表。

入门

每晚安装 Rust：
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh rustup toolchain install nightly
安装HVM：
cargo +nightly install hvm
运行 HVM 表达式：
hvm run "(@x(+ x 1) 41)"

项目地址：https://github.com/HigherOrderCO/HVM

hvm功能 (hvm是什么模块)

例子

冒泡排序

基数排序

拉姆达乘法

入门