127被浏览3678分享邀请回答#lang racket
(struct FDef (args body) #:transparent)
(struct None () #:transparent)
(define (lookup key env)
(cond [(null? env) (None)]
[(equal? key (first (first env))) (second (first env))]
[else (lookup key (rest env))]))
(define (update key val env)
(cond [(null? env) (list key val)]
[(equal? key (first (first env)))
(cons (list key val) (rest env))]
[else (cons (first env) (update key val (rest env)))]))
(define (op? op)
(or (symbol=? op '==) (symbol=? op '+)
(symbol=? op '-)
(symbol=? op '*)))
(define (is-value? v) (or (number? v) (boolean? v)))
(define (aexp op l r)
['+ (+ l r)]
['* (* l r)]
['- (- l r)]
['== (eq? l r)]))
(define (new-function-name old-name args)
(string-&symbol (string-append (symbol-&string old-name)
(number-&string (equal-hash-code args)))))
; peval: [(symbol, FDef)] SExpr -& ([(symbol, FDef)], SExpr)
(define (peval fdefs expr)
(define (pe expr env)
(match expr
[(or (? number?) (? boolean?)) expr]
[(? symbol?)
(define val (lookup expr env))
(if (None? val) expr val)]
[`(,(? op? op) ,l ,r)
(define lv (pe l env))
(define rv (pe r env))
(if (and (is-value? lv) (is-value? rv))
(aexp op lv rv)
`(,op ,lv ,rv))]
[`(if ,cnd ,thn ,els)
(define cnd-v (pe cnd env))
(if (is-value? cnd-v)
(if cnd-v (pe thn env) (pe els env))
`(if ,cnd ,(pe thn env) ,(pe els env)))]
[`(,fname ,args ...)
(define fun (lookup fname fdefs))
(define args-v (map (λ (v) (pe v env)) args))
(define new-env (map list (FDef-args fun) args-v))
(define-values (statics dyns) (partition (compose is-value? second) new-env))
(if (empty? dyns)
(pe (FDef-body fun) statics)
(let ([new-fname (new-function-name fname statics)])
(when (None? (lookup new-fname fdefs))
(set! fdefs `((,new-fname 'placeholder) ,@fdefs))
(set! fdefs (update new-fname (FDef (map first dyns) (pe (FDef-body fun) statics)) fdefs)))
`(,new-fname ,@(map second dyns))))]))
(reverse `(,(pe expr '()) ,fdefs)))
(module* test #f
(define add (list 'add (FDef '(x y) '(+ x y))))
; (add 1 2) 直接被解释为3
(check-equal? (second (peval (list add) '(add 1 2))) 3)
; (add 1 a) 则解释为(add180528 a)
; 同时生成了一个特化的函数 'add180528, 也就是(λ (y) (+ 1 y))
(check-equal? (peval (list add) '(add 1 a))
(list 'add180528 (FDef '(y) '(+ 1 y)))
(list 'add (FDef '(x y) '(+ x y))))
'(add180528 a))))
171 条评论分享收藏感谢收起怎样理解 Partial Evaluation_百度知道
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。
怎样理解 Partial Evaluation
我有更好的答案
不全面的评估
为您推荐：
其他类似问题
partial的相关知识
等待您来回答简单的说，智商高就效率高，我这样的就效率低ˊ_&ˋ
简单的说，智商高就效率高，我这样的就效率低ˊ_&ˋ
FreeMonad将任意一个函子f变为一个Monad，是所有Monad的initial object，因此所有Monad都可以从FreeMonad得到。可以将FreeMonad看成是自然数结构的一种表示，而FreeMonad到Monad的态射则是对这种自然数结构的求值。&br&FreeMonad的数据结构定义如下：&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&kr&&data&/span& &span class=&kt&&Free&/span& &span class=&n&&f&/span& &span class=&n&&a&/span& &span class=&ow&&=&/span& &span class=&kt&&Pure&/span& &span class=&n&&a&/span& &span class=&o&&|&/span& &span class=&kt&&Roll&/span& &span class=&p&&(&/span&&span class=&n&&f&/span& &span class=&p&&(&/span&&span class=&kt&&Free&/span& &span class=&n&&f&/span& &span class=&n&&a&/span&&span class=&p&&))&/span&
&/code&&/pre&&/div&和自然数的递归形式定义（邱奇数）有着同样的形式：&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&kr&&data&/span& &span class=&kt&&N&/span& &span class=&ow&&=&/span& &span class=&kt&&Z&/span& &span class=&o&&|&/span& &span class=&kt&&S&/span& &span class=&kt&&N&/span&
&/code&&/pre&&/div&自然数和FreeMonad的值对应关系如下：&br&&div class=&highlight&&&pre&&code class=&language-text&&0
Roll (f (Pure a))
Roll (f (Roll (f (Pure a)))
&/code&&/pre&&/div&因此FreeMonad的类型Free f a和自然数集合相对应，而单个FreeMonad的值则对应着一个自然数。FreeMonad可以看成是函子f多次作用在Pure a上的结果，作用次数就是自然数的值。&br&FreeMonad和其他的free object一样，具有如下的泛性质。&br&&img src=&/cf963d4f6b066d0d44aaf9_b.jpg& data-rawwidth=&346& data-rawheight=&224& class=&content_image& width=&346&&即若存在从X到F（FreeMonad)的ins态射，给定态射f，将得到一个唯一的态射free f，将F（FreeMonad）变换到G（任意Monad）。也就是说当我们构造好一个FreeMonad后，只要提供单个X的求值函数f，就可以得到一个唯一的该FreeMonad的求值函数free f。构造FreeMonad的过程是先通过ins态射来得到一个单个的FreeMonad，再使用Monad的组合操作join将多个单个的FreeMonad组合成一个FreeMonad。&br&而根据FreeMonad的定义，这个ins态射是一定存在的，因此也相应的得到了free f的定义，具体如下：&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&nf&&ins&/span& &span class=&ow&&::&/span& &span class=&p&&(&/span&&span class=&kt&&Functor&/span& &span class=&n&&f&/span&&span class=&p&&)&/span& &span class=&ow&&=&&/span& &span class=&n&&f&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&kt&&Free&/span& &span class=&n&&f&/span& &span class=&n&&a&/span&
&span class=&nf&&ins&/span& &span class=&n&&fa&/span& &span class=&ow&&=&/span& &span class=&kt&&Roll&/span& &span class=&p&&(&/span&&span class=&n&&fmap&/span& &span class=&kt&&Pure&/span& &span class=&n&&fa&/span&&span class=&p&&)&/span&
&span class=&nf&&free&/span& &span class=&ow&&::&/span& &span class=&p&&(&/span&&span class=&kt&&Functor&/span& &span class=&n&&f&/span&&span class=&p&&,&/span& &span class=&kt&&Monad&/span& &span class=&n&&g&/span&&span class=&p&&)&/span& &span class=&ow&&=&&/span&
&span class=&p&&(&/span&&span class=&n&&forall&/span& &span class=&n&&a&/span&&span class=&o&&.&/span& &span class=&n&&f&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&g&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&p&&(&/span&&span class=&n&&forall&/span& &span class=&n&&a&/span&&span class=&o&&.&/span& &span class=&kt&&Free&/span& &span class=&n&&f&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&g&/span& &span class=&n&&a&/span&&span class=&p&&)&/span&
&span class=&nf&&free&/span& &span class=&n&&f&/span& &span class=&p&&(&/span&&span class=&kt&&Pure&/span& &span class=&n&&a&/span&&span class=&p&&)&/span&
&span class=&ow&&=&/span& &span class=&n&&return&/span& &span class=&n&&a&/span&
&span class=&nf&&free&/span& &span class=&n&&f&/span& &span class=&p&&(&/span&&span class=&kt&&Roll&/span& &span class=&n&&fa&/span&&span class=&p&&)&/span& &span class=&ow&&=&/span& &span class=&n&&join&/span& &span class=&p&&(&/span&&span class=&n&&f&/span& &span class=&p&&(&/span&&span class=&n&&fmap&/span& &span class=&p&&(&/span&&span class=&n&&free&/span& &span class=&n&&f&/span&&span class=&p&&)&/span& &span class=&n&&fa&/span&&span class=&p&&))&/span&
&/code&&/pre&&/div&上面的函数free是一个解释器(Interpreter)，其参数f是单个FreeMonad的求值函数，由此得到组合后的FreeMonad的求值函数free f。&br&至此，我们得到了 &a data-hash=&bda2c703adda& href=&///people/bda2c703adda& class=&member_mention& data-editable=&true& data-title=&@阅千人而惜知己& data-hovercard=&p$b$bda2c703adda&&@阅千人而惜知己&/a&提到的Free Monad，其意义是分离我们的打造的Monadic DSL与对这个DSL的Monadic解释。这里的函子f就是InteractionOp。&br&最后，按照Monad不过是自函子上的Monoid上的说法，FreeMonad其实和FreeMonoid具有一样的形式，具体如下：&br&&img src=&/f333fc7b5d4a0cfd75ea9_b.jpg& data-rawwidth=&216& data-rawheight=&48& class=&content_image& width=&216&&&br&接下来，我们来看看几种常见的Functor构成的Free Monad。&br&首先，来看看Maybe这个Functor构成的Free Monad，具体定义如下：&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&kt&&Free&/span& &span class=&kt&&Maybe&/span& &span class=&n&&a&/span& &span class=&ow&&=&/span& &span class=&kt&&Pure&/span& &span class=&n&&a&/span&
&span class=&o&&|&/span& &span class=&kt&&Free&/span& &span class=&kt&&Nothing&/span&
&span class=&o&&|&/span& &span class=&kt&&Free&/span& &span class=&p&&(&/span&&span class=&kt&&Just&/span& &span class=&p&&(&/span&&span class=&kt&&Free&/span& &span class=&kt&&Maybe&/span& &span class=&n&&a&/span&&span class=&p&&))&/span&
&/code&&/pre&&/div&因为有&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&c1&&-- Any function map to Nothing should get Nothing&/span&
&span class=&nf&&fmap&/span& &span class=&kr&&_&/span& &span class=&kt&&Nothing&/span& &span class=&ow&&=&/span& &span class=&kt&&Nothing&/span&
&span class=&c1&&-- So Free Nothing bind to any function should get Free Nothing&/span&
&span class=&kt&&Free&/span& &span class=&kt&&Nothing&/span& &span class=&o&&&&=&/span& &span class=&kr&&_&/span& &span class=&ow&&=&/span& &span class=&kt&&Free&/span& &span class=&kt&&Nothing&/span&
&/code&&/pre&&/div&因此，我们可以用Nothing来结束Free Maybe a组成的运算序列，如下所示&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&nf&&freeMaybeSeq&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&x&/span& &span class=&ow&&&-&/span& &span class=&kt&&Free&/span& &span class=&p&&(&/span&&span class=&kt&&Just&/span& &span class=&p&&(&/span&&span class=&kt&&Pure&/span& &span class=&mi&&3&/span&&span class=&p&&))&/span&
&span class=&kt&&Free&/span& &span class=&kt&&Nothing&/span&
&span class=&c1&&-- The sequence should terminate on it&/span&
&span class=&kt&&Free&/span& &span class=&p&&(&/span&&span class=&kt&&Just&/span& &span class=&p&&(&/span&&span class=&kt&&Pure&/span& &span class=&p&&(&/span&&span class=&n&&x&/span& &span class=&o&&+&/span& &span class=&mi&&4&/span&&span class=&p&&)))&/span&
&span class=&c1&&-- This line can't be executed&/span&
&/code&&/pre&&/div&&br&另外，Maybe自身也是一个Free Monad，其构造如下所示：&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&kr&&newtype&/span& &span class=&kt&&Const&/span& &span class=&n&&a&/span& &span class=&n&&b&/span& &span class=&ow&&=&/span& &span class=&kt&&Const&/span& &span class=&n&&a&/span&
&span class=&kr&&deriving&/span&&span class=&p&&(&/span&&span class=&kt&&Show&/span&&span class=&p&&)&/span&
&span class=&kr&&instance&/span& &span class=&kt&&Functor&/span& &span class=&p&&(&/span&&span class=&kt&&Const&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&kr&&where&/span&
&span class=&n&&fmap&/span& &span class=&n&&f&/span& &span class=&p&&(&/span&&span class=&kt&&Const&/span& &span class=&n&&v&/span&&span class=&p&&)&/span& &span class=&ow&&=&/span& &span class=&kt&&Const&/span& &span class=&n&&v&/span&
&span class=&c1&&-- data Maybe a = Just a | Nothing&/span&
&span class=&c1&&--
~= Pure a | Free (Const ())&/span&
&span class=&c1&&-- Mabye a ~ Free (Const ()) a&/span&
&span class=&kt&&Free&/span& &span class=&p&&(&/span&&span class=&kt&&Const&/span& &span class=&nb&&()&/span&&span class=&p&&)&/span& &span class=&n&&a&/span& &span class=&ow&&=&/span& &span class=&kt&&Pure&/span& &span class=&n&&a&/span&
&span class=&o&&|&/span& &span class=&kt&&Free&/span& &span class=&p&&(&/span&&span class=&kt&&Const&/span& &span class=&nb&&()&/span&&span class=&p&&)&/span&
&/code&&/pre&&/div&&br&接下来，我们来看看List这个Free Monad是如何构成的，具体构造如下：&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&kt&&Free&/span& &span class=&kt&&[]&/span& &span class=&n&&a&/span& &span class=&ow&&=&/span& &span class=&kt&&Pure&/span& &span class=&n&&a&/span&
&span class=&o&&|&/span& &span class=&kt&&Free&/span& &span class=&p&&[&/span&&span class=&kt&&Free&/span& &span class=&kt&&[]&/span& &span class=&n&&a&/span&&span class=&p&&]&/span&
&/code&&/pre&&/div&List具有不确定计算的能力，我们可以在下面看到其应用：&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&nf&&freeListSeq&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&x&/span& &span class=&ow&&&-&/span& &span class=&kt&&Free&/span& &span class=&p&&[&/span&&span class=&kt&&Pure&/span& &span class=&mi&&2&/span&&span class=&p&&,&/span& &span class=&kt&&Pure&/span& &span class=&mi&&3&/span&&span class=&p&&]&/span&
&span class=&n&&y&/span& &span class=&ow&&&-&/span& &span class=&kt&&Free&/span& &span class=&p&&[&/span&&span class=&kt&&Pure&/span& &span class=&mi&&4&/span&&span class=&p&&,&/span& &span class=&kt&&Pure&/span& &span class=&mi&&5&/span&&span class=&p&&,&/span& &span class=&kt&&Pure&/span& &span class=&mi&&6&/span&&span class=&p&&]&/span&
&span class=&n&&return&/span& &span class=&p&&(&/span&&span class=&n&&x&/span& &span class=&o&&*&/span& &span class=&n&&y&/span&&span class=&p&&)&/span&
&/code&&/pre&&/div&用ghci可以看到其结果是所有可能结果的组合，具体如下：&br&&div class=&highlight&&&pre&&code class=&language-text&&*Main& freeListSeq
Free [Free [Pure 8,Pure 10,Pure 12],Free [Pure 12,Pure 15,Pure 18]]
&/code&&/pre&&/div&&br&最后，我们来看看由Id这个看起来最没用的Functor构成的Free Monad，具体定义如下：&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&kt&&Free&/span& &span class=&kt&&Id&/span& &span class=&n&&a&/span& &span class=&ow&&=&/span& &span class=&kt&&Pure&/span& &span class=&n&&a&/span& &span class=&o&&|&/span& &span class=&kt&&Free&/span& &span class=&p&&(&/span&&span class=&kt&&Id&/span& &span class=&p&&(&/span&&span class=&kt&&Free&/span& &span class=&kt&&Id&/span& &span class=&n&&a&/span&&span class=&p&&))&/span&
&/code&&/pre&&/div&这个Free Monad等同于延迟求值的序列，也是一个Monad如下所示：&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&kt&&Delay&/span& &span class=&n&&a&/span& &span class=&ow&&=&/span& &span class=&kt&&Now&/span& &span class=&n&&a&/span& &span class=&o&&|&/span& &span class=&kt&&Later&/span& &span class=&p&&(&/span&&span class=&kt&&Delay&/span& &span class=&n&&a&/span&&span class=&p&&)&/span&
&span class=&c1&&-- Infinite delayed value&/span&
&span class=&nf&&never&/span& &span class=&ow&&::&/span& &span class=&kt&&Delay&/span& &span class=&n&&a&/span&
&span class=&nf&&never&/span& &span class=&ow&&=&/span& &span class=&kt&&Later&/span& &span class=&n&&never&/span&
&span class=&kr&&instance&/span& &span class=&kt&&Functor&/span& &span class=&kt&&Delay&/span& &span class=&kr&&where&/span&
&span class=&n&&fmap&/span& &span class=&n&&f&/span& &span class=&p&&(&/span&&span class=&kt&&Now&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&ow&&=&/span& &span class=&kt&&Now&/span& &span class=&p&&(&/span&&span class=&n&&f&/span& &span class=&n&&a&/span&&span class=&p&&)&/span&
&span class=&n&&fmap&/span& &span class=&n&&f&/span& &span class=&p&&(&/span&&span class=&kt&&Later&/span& &span class=&n&&d&/span&&span class=&p&&)&/span& &span class=&ow&&=&/span& &span class=&kt&&Later&/span& &span class=&p&&(&/span&&span class=&n&&fmap&/span& &span class=&n&&f&/span& &span class=&n&&d&/span&&span class=&p&&)&/span&
&span class=&kr&&instance&/span& &span class=&kt&&Applicative&/span& &span class=&kt&&Delay&/span& &span class=&kr&&where&/span&
&span class=&n&&pure&/span& &span class=&ow&&=&/span& &span class=&kt&&Now&/span&
&span class=&kt&&Now&/span& &span class=&n&&f&/span& &span class=&o&&&*&&/span& &span class=&n&&d&/span& &span class=&ow&&=&/span& &span class=&n&&fmap&/span& &span class=&n&&f&/span& &span class=&n&&d&/span&
&span class=&kt&&Later&/span& &span class=&n&&df&/span& &span class=&o&&&*&&/span& &span class=&n&&d&/span& &span class=&ow&&=&/span& &span class=&kt&&Later&/span& &span class=&p&&(&/span&&span class=&n&&df&/span& &span class=&o&&&*&&/span& &span class=&n&&d&/span&&span class=&p&&)&/span&
&span class=&kr&&instance&/span& &span class=&kt&&Monad&/span& &span class=&kt&&Delay&/span& &span class=&kr&&where&/span&
&span class=&n&&return&/span& &span class=&ow&&=&/span& &span class=&kt&&Now&/span&
&span class=&kt&&Now&/span& &span class=&n&&a&/span& &span class=&o&&&&=&/span& &span class=&n&&f&/span& &span class=&ow&&=&/span& &span class=&n&&f&/span& &span class=&n&&a&/span&
&span class=&kt&&Later&/span& &span class=&n&&d&/span& &span class=&o&&&&=&/span& &span class=&n&&f&/span& &span class=&ow&&=&/span& &span class=&kt&&Later&/span& &span class=&p&&(&/span&&span class=&n&&d&/span& &span class=&o&&&&=&/span& &span class=&n&&f&/span&&span class=&p&&)&/span&
&/code&&/pre&&/div&&br&这个Delay a延迟求值序列是一个偏序集，两个Delay a类型的值存在竞争，其竞争结果是延迟步骤最少的Delay a类型的值。多个Delay a类型的值的竞争结果是其中延迟步骤最少的Delay a类型的值。&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&nf&&race&/span& &span class=&ow&&::&/span& &span class=&kt&&Delay&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&kt&&Delay&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&kt&&Delay&/span& &span class=&n&&a&/span&
&span class=&nf&&race&/span& &span class=&p&&(&/span&&span class=&kt&&Now&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&kr&&_&/span& &span class=&ow&&=&/span& &span class=&kt&&Now&/span& &span class=&n&&a&/span&
&span class=&nf&&race&/span& &span class=&p&&(&/span&&span class=&kt&&Later&/span& &span class=&kr&&_&/span&&span class=&p&&)&/span& &span class=&p&&(&/span&&span class=&kt&&Now&/span& &span class=&n&&b&/span&&span class=&p&&)&/span& &span class=&ow&&=&/span& &span class=&kt&&Now&/span& &span class=&n&&b&/span&
&span class=&nf&&race&/span& &span class=&p&&(&/span&&span class=&kt&&Later&/span& &span class=&n&&d&/span&&span class=&p&&)&/span& &span class=&p&&(&/span&&span class=&kt&&Later&/span& &span class=&n&&d'&/span&&span class=&p&&)&/span& &span class=&ow&&=&/span& &span class=&n&&race&/span& &span class=&n&&d&/span& &span class=&n&&d'&/span&
&span class=&nf&&omegaRace&/span& &span class=&ow&&::&/span& &span class=&p&&[&/span&&span class=&kt&&Delay&/span& &span class=&n&&a&/span&&span class=&p&&]&/span& &span class=&ow&&-&&/span& &span class=&kt&&Delay&/span& &span class=&n&&a&/span&
&span class=&nf&&omegaRace&/span& &span class=&p&&[&/span&&span class=&n&&d&/span&&span class=&p&&]&/span&
&span class=&ow&&=&/span& &span class=&n&&d&/span&
&span class=&nf&&omegaRace&/span& &span class=&p&&(&/span&&span class=&n&&d&/span&&span class=&kt&&:&/span&&span class=&n&&ds&/span&&span class=&p&&)&/span& &span class=&ow&&=&/span& &span class=&n&&race&/span& &span class=&n&&d&/span& &span class=&p&&(&/span&&span class=&kt&&Later&/span& &span class=&p&&(&/span&&span class=&n&&omegaRace&/span& &span class=&n&&ds&/span&&span class=&p&&))&/span&
&/code&&/pre&&/div&偏序集加上bottom值和子集最小上界的函数，我们就有了Domains，具体定义如下：&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&kr&&class&/span& &span class=&kt&&Dom&/span& &span class=&n&&a&/span& &span class=&kr&&where&/span&
&span class=&n&&bot&/span& &span class=&ow&&::&/span& &span class=&n&&a&/span&
&span class=&n&&lub&/span& &span class=&ow&&::&/span& &span class=&p&&[&/span&&span class=&n&&a&/span&&span class=&p&&]&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&
&span class=&kr&&instance&/span& &span class=&kt&&Dom&/span& &span class=&n&&b&/span& &span class=&ow&&=&&/span& &span class=&kt&&Dom&/span& &span class=&p&&(&/span&&span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&b&/span&&span class=&p&&)&/span& &span class=&kr&&where&/span&
&span class=&n&&bot&/span& &span class=&n&&a&/span& &span class=&ow&&=&/span& &span class=&n&&bot&/span&
&span class=&n&&lub&/span& &span class=&n&&fs&/span& &span class=&n&&a&/span& &span class=&ow&&=&/span& &span class=&n&&lub&/span& &span class=&p&&(&/span&&span class=&n&&fmap&/span& &span class=&p&&(&/span&&span class=&nf&&\&/span&&span class=&n&&f&/span& &span class=&ow&&-&&/span& &span class=&n&&f&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&n&&fs&/span&&span class=&p&&)&/span&
&span class=&kr&&instance&/span& &span class=&p&&(&/span&&span class=&kt&&Dom&/span& &span class=&n&&a&/span&&span class=&p&&,&/span& &span class=&kt&&Dom&/span& &span class=&n&&b&/span&&span class=&p&&)&/span& &span class=&ow&&=&&/span& &span class=&kt&&Dom&/span& &span class=&p&&(&/span&&span class=&n&&a&/span&&span class=&p&&,&/span& &span class=&n&&b&/span&&span class=&p&&)&/span& &span class=&kr&&where&/span&
&span class=&n&&bot&/span& &span class=&ow&&=&/span& &span class=&p&&(&/span&&span class=&n&&bot&/span&&span class=&p&&,&/span& &span class=&n&&bot&/span&&span class=&p&&)&/span&
&span class=&n&&lub&/span& &span class=&n&&ps&/span& &span class=&ow&&=&/span& &span class=&p&&(&/span&&span class=&n&&lub&/span& &span class=&p&&(&/span&&span class=&n&&fmap&/span& &span class=&n&&fst&/span& &span class=&n&&ps&/span&&span class=&p&&),&/span& &span class=&n&&lub&/span& &span class=&p&&(&/span&&span class=&n&&famp&/span& &span class=&n&&snd&/span& &span class=&n&&ps&/span&&span class=&p&&))&/span&
&/code&&/pre&&/div&类型Delay a也是Dom的实例，定义如下：&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&kr&&instance&/span& &span class=&kt&&Dom&/span& &span class=&p&&(&/span&&span class=&kt&&Delay&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&kr&&where&/span&
&span class=&n&&bot&/span& &span class=&ow&&=&/span& &span class=&n&&never&/span&
&span class=&n&&lub&/span& &span class=&ow&&=&/span& &span class=&n&&omegaRace&/span&
&/code&&/pre&&/div&&br&基于Domains，我们可以构造出最小不动点，可以将任意非递归函数变换为递归函数（若该非递归函数的递归形式存在）。具体如下所示：&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&nf&&iterate&/span& &span class=&ow&&::&/span& &span class=&p&&(&/span&&span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&p&&[&/span&&span class=&n&&a&/span&&span class=&p&&]&/span&
&span class=&nf&&iterate&/span& &span class=&n&&f&/span& &span class=&n&&a&/span& &span class=&ow&&=&/span& &span class=&n&&a&/span& &span class=&kt&&:&/span& &span class=&n&&iterate&/span& &span class=&n&&f&/span& &span class=&p&&(&/span&&span class=&n&&f&/span& &span class=&n&&a&/span&&span class=&p&&)&/span&
&span class=&c1&&-- least fixpoint function&/span&
&span class=&nf&&lfp&/span& &span class=&ow&&::&/span& &span class=&kt&&Dom&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&p&&(&/span&&span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&
&span class=&nf&&lfp&/span& &span class=&n&&f&/span& &span class=&ow&&=&/span& &span class=&n&&lub&/span& &span class=&p&&(&/span&&span class=&n&&iterate&/span& &span class=&n&&f&/span& &span class=&n&&bot&/span&&span class=&p&&)&/span&
&/code&&/pre&&/div&将最小不动点函数应用到类型Delay a上，我们有&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&c1&&--
Dom (Integer -& Delay Integer) Dom (Integer -& Delay Integer)&/span&
&span class=&c1&&-- fib = lfp ((Integer -& Delay Integer) -& (Integer -& Delay Integer)&/span&
&span class=&nf&&fib&/span& &span class=&ow&&::&/span& &span class=&kt&&Integer&/span& &span class=&ow&&-&&/span& &span class=&kt&&Delay&/span& &span class=&kt&&Integer&/span&
&span class=&nf&&fib&/span& &span class=&ow&&=&/span& &span class=&n&&lfp&/span& &span class=&p&&(&/span&&span class=&nf&&\&/span&&span class=&n&&fib&/span& &span class=&ow&&-&&/span& &span class=&nf&&\&/span&&span class=&n&&n&/span& &span class=&ow&&-&&/span&
&span class=&kr&&if&/span& &span class=&n&&n&/span& &span class=&o&&==&/span& &span class=&mi&&0&/span& &span class=&kr&&then&/span& &span class=&n&&return&/span& &span class=&mi&&0&/span&
&span class=&kr&&else&/span& &span class=&kr&&if&/span& &span class=&n&&n&/span& &span class=&o&&==&/span& &span class=&mi&&1&/span& &span class=&kr&&then&/span& &span class=&n&&return&/span& &span class=&mi&&1&/span&
&span class=&kr&&else&/span& &span class=&kr&&do&/span&
&span class=&n&&x&/span& &span class=&ow&&&-&/span& &span class=&n&&fib&/span& &span class=&p&&(&/span&&span class=&n&&n&/span&&span class=&o&&-&/span&&span class=&mi&&2&/span&&span class=&p&&)&/span&
&span class=&n&&y&/span& &span class=&ow&&&-&/span& &span class=&n&&fib&/span& &span class=&p&&(&/span&&span class=&n&&n&/span&&span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&)&/span&
&span class=&n&&return&/span& &span class=&p&&(&/span&&span class=&n&&x&/span& &span class=&o&&+&/span& &span class=&n&&y&/span&&span class=&p&&)&/span&
&span class=&p&&)&/span&
&/code&&/pre&&/div&在ghci中运行fib函数有如下的结果：&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&o&&*&/span&&span class=&kt&&Main&/span&&span class=&o&&&&/span& &span class=&n&&fib&/span& &span class=&mi&&8&/span&
&span class=&kt&&Now&/span& &span class=&mi&&21&/span&
&/code&&/pre&&/div&&br&至此，我们等价实现了Data.Function中的fix函数，用fix实现的fib函数如下：&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&nf&&fibx&/span& &span class=&ow&&=&/span& &span class=&n&&fix&/span& &span class=&p&&(&/span&&span class=&nf&&\&/span&&span class=&n&&fib&/span& &span class=&ow&&-&&/span& &span class=&nf&&\&/span&&span class=&n&&n&/span& &span class=&ow&&-&&/span&
&span class=&kr&&if&/span& &span class=&n&&n&/span& &span class=&o&&==&/span& &span class=&mi&&0&/span& &span class=&kr&&then&/span& &span class=&mi&&0&/span&
&span class=&kr&&else&/span& &span class=&kr&&if&/span& &span class=&n&&n&/span& &span class=&o&&==&/span& &span class=&mi&&1&/span& &span class=&kr&&then&/span& &span class=&mi&&1&/span&
&span class=&kr&&else&/span& &span class=&n&&fib&/span& &span class=&p&&(&/span&&span class=&n&&n&/span&&span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&)&/span& &span class=&o&&+&/span& &span class=&n&&fib&/span& &span class=&p&&(&/span&&span class=&n&&n&/span&&span class=&o&&-&/span&&span class=&mi&&2&/span&&span class=&p&&)&/span&
&span class=&p&&)&/span&
&/code&&/pre&&/div&在ghci中运行fib函数有如下的结果：&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&o&&*&/span&&span class=&kt&&Main&/span&&span class=&o&&&&/span& &span class=&n&&fibx&/span& &span class=&mi&&8&/span&
&span class=&mi&&21&/span&
&/code&&/pre&&/div&
FreeMonad将任意一个函子f变为一个Monad，是所有Monad的initial object，因此所有Monad都可以从FreeMonad得到。可以将FreeMonad看成是自然数结构的一种表示，而FreeMonad到Monad的态射则是对这种自然数结构的求值。 FreeMonad的数据结构定义如下： data Fre…
&b&结论更新:&/b&&br&原来的版本速度主要慢在 div 除法和 even函数上面.&br&直接在原来的版本上把相应操作换成quot 和 与 位运算后, 再开启优化选项(-O3), 速度提升到了0.3s, 也是接近C的速度. 可见关键在于这两个操作, 与使用unboxed类型, strict无关, 开启优化后这些工作ghc会帮我们完成. (不过使用unboxed类型依然会快一点!而且不用开启优化选项就很快)&br&&br&相关部分代码&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&nf&&collatzNext&/span& &span class=&ow&&::&/span& &span class=&kt&&Int&/span& &span class=&ow&&-&&/span& &span class=&kt&&Int&/span&
&span class=&nf&&collatzNext&/span& &span class=&n&&a&/span& &span class=&ow&&=&/span& &span class=&n&&r&/span& &span class=&p&&`&/span&&span class=&n&&quot&/span&&span class=&p&&`&/span& &span class=&mi&&2&/span& &span class=&c1&&-- 0.30 with -O3&/span&
&span class=&c1&&--collatzNext a = r `div` 2 -- 1.39s with -O3&/span&
&span class=&kr&&where&/span&
&span class=&n&&r&/span& &span class=&ow&&=&/span& &span class=&kr&&if&/span& &span class=&n&&a&/span& &span class=&o&&.&.&/span& &span class=&mi&&1&/span& &span class=&o&&==&/span& &span class=&mi&&0&/span& &span class=&kr&&then&/span& &span class=&n&&a&/span& &span class=&kr&&else&/span& &span class=&mi&&3&/span& &span class=&o&&*&/span& &span class=&n&&a&/span& &span class=&o&&+&/span& &span class=&mi&&1&/span& &span class=&c1&&-- 使用and运算代替even函数&/span&
&span class=&nf&&collatzLen&/span& &span class=&ow&&::&/span& &span class=&kt&&Int&/span& &span class=&ow&&-&&/span& &span class=&kt&&Int&/span&
&span class=&nf&&collatzLen&/span& &span class=&n&&n&/span& &span class=&ow&&=&/span& &span class=&n&&collatzIter&/span& &span class=&n&&n&/span& &span class=&mi&&0&/span&
&span class=&kr&&where&/span&
&span class=&n&&collatzIter&/span& &span class=&mi&&1&/span& &span class=&n&&len&/span& &span class=&ow&&=&/span& &span class=&n&&len&/span&
&span class=&n&&collatzIter&/span& &span class=&n&&n&/span& &span class=&n&&len&/span& &span class=&ow&&=&/span& &span class=&n&&collatzIter&/span& &span class=&p&&(&/span&&span class=&n&&collatzNext&/span& &span class=&n&&n&/span&&span class=&p&&)&/span& &span class=&p&&(&/span&&span class=&n&&len&/span& &span class=&o&&+&/span& &span class=&mi&&1&/span&&span class=&p&&)&/span&
&/code&&/pre&&/div&&br&------------&br&补充:&br&非常影响性能的点:&br&判断奇偶数(even)时, 使用 &b&位运算&/b& 代替&i&求余&/i&, 速度会从使用unboxed类型后的&b&1.27s&/b&直接提升到&b&0.29s&/b&.&br&&br&乘法运算 替换成 一次位移一次加法,性能提升不明显. 不过 &a data-hash=&c0b6df892e7f& href=&///people/c0b6df892e7f& class=&member_mention& data-editable=&true& data-title=&@Tang Boyun& data-tip=&p$b$c0b6df892e7f& data-hovercard=&p$b$c0b6df892e7f&&@Tang Boyun&/a&的结论 ghc优化底层不够好的结论是对的.&br&&br&----------&br&&br&补充: 我没有使用llvm后端&br&----------&br&&br&&b&我在使用&/b&&u&unboxed类型以及&/u&&b&用位运算实现(even)之后, 速度由原来的 2s多提高到了0.29s左右, 基本等价于C的速度.&/b&&br&&br&以下是代码:&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&cm&&{-# LANGUAGE MagicHash #-}&/span&
&span class=&cm&&{-# LANGUAGE UnboxedTuples #-}&/span&
&span class=&kr&&import&/span& &span class=&nn&&GHC.Types&/span&
&span class=&kr&&import&/span& &span class=&nn&&GHC.Prim&/span&
&span class=&nf&&collatzNext&/span& &span class=&ow&&::&/span& &span class=&kt&&Int&/span&&span class=&o&&#&/span& &span class=&ow&&-&&/span& &span class=&kt&&Int&/span&&span class=&o&&#&/span&
&span class=&nf&&collatzNext&/span& &span class=&n&&a&/span& &span class=&ow&&=&/span&
&span class=&kr&&case&/span& &span class=&n&&andI&/span&&span class=&o&&#&/span& &span class=&n&&a&/span& &span class=&mi&&1&/span&&span class=&o&&#&/span& &span class=&kr&&of&/span&
&span class=&mi&&0&/span&&span class=&o&&#&/span& &span class=&ow&&-&&/span& &span class=&n&&quotInt&/span&&span class=&o&&#&/span& &span class=&n&&a&/span& &span class=&mi&&2&/span&&span class=&o&&#&/span&
&span class=&o&&--&/span&&span class=&kr&&_&/span&
&span class=&ow&&-&&/span& &span class=&p&&(&/span&&span class=&mi&&3&/span&&span class=&o&&#&/span& &span class=&o&&*#&/span& &span class=&n&&a&/span& &span class=&o&&+#&/span& &span class=&mi&&1&/span&&span class=&o&&#&/span&&span class=&p&&)&/span& &span class=&p&&`&/span&&span class=&n&&quotInt&/span&&span class=&o&&#&/span&&span class=&p&&`&/span& &span class=&mi&&2&/span&&span class=&o&&#&/span&
&span class=&kr&&_&/span&
&span class=&ow&&-&&/span& &span class=&p&&((&/span&&span class=&n&&uncheckedIShiftL&/span&&span class=&o&&#&/span& &span class=&n&&a&/span& &span class=&mi&&1&/span&&span class=&o&&#&/span&&span class=&p&&)&/span& &span class=&o&&+#&/span& &span class=&n&&a&/span& &span class=&o&&+#&/span& &span class=&mi&&1&/span&&span class=&o&&#&/span&&span class=&p&&)&/span& &span class=&p&&`&/span&&span class=&n&&quotInt&/span&&span class=&o&&#&/span&&span class=&p&&`&/span& &span class=&mi&&2&/span&&span class=&o&&#&/span&
&span class=&nf&&collatzLen&/span& &span class=&ow&&::&/span& &span class=&kt&&Int&/span&&span class=&o&&#&/span& &span class=&ow&&-&&/span& &span class=&kt&&Int&/span&&span class=&o&&#&/span&
&span class=&nf&&collatzLen&/span& &span class=&n&&n&/span& &span class=&ow&&=&/span& &span class=&n&&collatzIter&/span& &span class=&n&&n&/span& &span class=&mi&&0&/span&&span class=&o&&#&/span&
&span class=&kr&&where&/span&
&span class=&n&&collatzIter&/span& &span class=&mi&&1&/span&&span class=&o&&#&/span& &span class=&n&&len&/span& &span class=&ow&&=&/span& &span class=&n&&len&/span&
&span class=&n&&collatzIter&/span& &span class=&n&&n&/span& &span class=&n&&len&/span& &span class=&ow&&=&/span& &span class=&n&&collatzIter&/span& &span class=&p&&(&/span&&span class=&n&&collatzNext&/span& &span class=&n&&n&/span&&span class=&p&&)&/span& &span class=&p&&(&/span&&span class=&n&&len&/span& &span class=&o&&+#&/span& &span class=&mi&&1&/span&&span class=&o&&#&/span&&span class=&p&&)&/span&
&span class=&nf&&main&/span& &span class=&ow&&::&/span& &span class=&kt&&IO&/span& &span class=&nb&&()&/span&
&span class=&nf&&main&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&print&/span& &span class=&p&&(&/span&&span class=&kt&&I&/span&&span class=&o&&#&/span& &span class=&p&&(&/span&&span class=&n&&find_max_len&/span& &span class=&mi&&1&/span&&span class=&o&&#&/span& &span class=&mi&&0&/span&&span class=&o&&#&/span&&span class=&p&&))&/span&
&span class=&nf&&find_max_len&/span& &span class=&ow&&::&/span& &span class=&kt&&Int&/span&&span class=&o&&#&/span& &span class=&ow&&-&&/span& &span class=&kt&&Int&/span&&span class=&o&&#&/span& &span class=&ow&&-&&/span& &span class=&kt&&Int&/span&&span class=&o&&#&/span&
&span class=&nf&&find_max_len&/span& &span class=&mi&&1000000&/span&&span class=&o&&#&/span& &span class=&n&&max_len&/span& &span class=&ow&&=&/span& &span class=&n&&max_len&/span&
&span class=&nf&&find_max_len&/span& &span class=&n&&n&/span& &span class=&n&&max_len&/span& &span class=&ow&&=&/span&
&span class=&kr&&case&/span& &span class=&n&&cn&/span& &span class=&o&&&#&/span& &span class=&n&&max_len&/span& &span class=&kr&&of&/span&
&span class=&mi&&0&/span&&span class=&o&&#&/span& &span class=&ow&&-&&/span& &span class=&n&&find_max_len&/span& &span class=&n&&nn&/span& &span class=&n&&max_len&/span&
&span class=&kr&&_&/span& &span class=&ow&&-&&/span& &span class=&n&&find_max_len&/span& &span class=&n&&nn&/span& &span class=&n&&cn&/span&
&span class=&kr&&where&/span&
&span class=&n&&nn&/span& &span class=&ow&&=&/span& &span class=&n&&n&/span& &span class=&o&&+#&/span& &span class=&mi&&1&/span&&span class=&o&&#&/span&
&span class=&n&&cn&/span& &span class=&ow&&=&/span& &span class=&n&&collatzLen&/span& &span class=&n&&n&/span&
&/code&&/pre&&/div&
结论更新: 原来的版本速度主要慢在 div 除法和 even函数上面. 直接在原来的版本上把相应操作换成quot 和 与 位运算后, 再开启优化选项(-O3), 速度提升到了0.3s, 也是接近C的速度. 可见关键在于这两个操作, 与使用unboxed类型, strict无关, 开启优化后这些工…
&p&声明: 下面的信息仅仅是我在社区道听途说而来的, 不一定准确&/p&&p&从我的观察来看: 基本没有什么关系, 虽然 Simon Peyton Jones 在 MSRC 做研究员, 但是这层关系应该是 M$ 支持 SPJ &做编程语言领域研究& 而不是研究 Haskell 或者是开发 GHC, GHC 开发应该是研究的成果. 例如最近的 &a href=&///?target=https%3A///en-us/research/publication/compiling-without-continuations/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Compiling without continuations - Microsoft Research&i class=&icon-external&&&/i&&/a& , &a href=&///?target=https%3A//redd.it/5rnpha& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&redd.it/5rnpha&/span&&span class=&invisible&&&/span&&i class=&icon-external&&&/i&&/a& , GHC 不少改进都是各种研究成果转化而来的.&/p&&p&就像 A History of Haskell 里说的, 其实到现在也是差不多...&/p&&blockquote&At the same time, the language has simultaneously served as a highly effective laboratory in which to explore advanced language design ideas, especially in the area of type systems and meta-programming. &/blockquote&&p&所以 M$ 应该没有直接上说对 Haskell 有什么干预, 虽然挺早的时候设计 Haskell 的人跟 M$ 有不少关联, 例如 Erik Meijer, Erik Meijer 也把不少 Haskell 里的不错的东西加在 C# 里了, 例如很多人都赞赏有加的 LINQ, 其实就是在用 Monad. BTW,
Erik Meijer 最后也是去了 FB.&/p&&p&之前 Simon Marlow 也在 M$, 性质应该跟 SPJ 类似, 后来为了写完鱼书, 离开了 M$, 写完书后加入了 Facebook, 记得当时跟社区说不会影响对 GHC 的开发,
Simon Marlow 主要是搞 RTS 方面的, 期间也带了小弟搞定了 GHC 这么多年来的坑: &a href=&///?target=https%3A//ghc.haskell.org/trac/ghc/wiki/DeterministicBuilds& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&DeterministicBuilds - GHC&i class=&icon-external&&&/i&&/a&&/p&&p&啊, BOS 也是在 Facebook (&/p&&p&至于钱方面, 也没有看到 M$ 有直接支持的地方, 不像 Rust, Go, Scala 那样背后有个公司在滋磁. 去年的 Google Summer of Code 没申请成功, 社区募捐自己搞了 Haskell Summer of Code. &/p&&p&AFAIK, 现在 GHC 只有一个人全职在开发, 就是 Well-Type 的这个同学 &a href=&///?target=https%3A///bgamari& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&bgamari (Ben Gamari) · GitHub&i class=&icon-external&&&/i&&/a&. &/p&&br&&p&啊 还有这位 &a href=&///?target=https%3A///in/austinseipp& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://www.&/span&&span class=&visible&&/in/austins&/span&&span class=&invisible&&eipp&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/p&&br&&p&一下子写了好多 OT 的东西, 不过还是希望大家有能力给社区做做贡献&/p&
声明: 下面的信息仅仅是我在社区道听途说而来的, 不一定准确从我的观察来看: 基本没有什么关系, 虽然 Simon Peyton Jones 在 MSRC 做研究员, 但是这层关系应该是 M$ 支持 SPJ "做编程语言领域研究" 而不是研究 Haskell 或者是开发 GHC, GHC 开发应该是研究…
pandoc 文本格式转换利器 &br&&br&Pandoc 一个用 Haskell 编写的文档格式转换软件&br&&br&输入格式可以是： markdown ,Textile, reStructuredText, HTML,
LaTeX;&br&&br&输出语言非常丰富，包括： markdown, reStructuredText, XHTML, HTML 5, LaTeX , ConTeXt,RTF, DocBook XML, OpenDocument XML, ODT, Word docx, GNU Texinfo, MediaWiki markup, EPUB, Textile, groff man, Emacs Org-Mode, AsciiDoc,Slidy, DZSlides, S5 HTML slide shows. 如果安装了 LaTeX ,甚至还可以输出为 PDF 格式！&br&&br&项目主页：&a href=&///?target=http%3A//johnmacfarlane.net/pandoc/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&johnmacfarlane.net/pand&/span&&span class=&invisible&&oc/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&
pandoc 文本格式转换利器 Pandoc 一个用 Haskell 编写的文档格式转换软件 输入格式可以是： markdown ,Textile, reStructuredText, HTML, LaTeX; 输出语言非常丰富，包括： markdown, reStructuredText, XHTML, HTML 5, LaTeX , ConTeXt,RTF, DocBook XML, …
這週把惰性求值實現了一遍，終於覺得有自信回答這個問題了。我在這裡的解釋會比較簡略，不過推薦來讀我翻譯的文章《&a href=&///?target=http%3A//shouya.github.io/blog/how-lazy-evaluation-works-in-haskell/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Haskell 怎麼實現惰性求值&i class=&icon-external&&&/i&&/a&》（&a class=& wrap external& href=&///?target=https%3A///lazy-evaluation-works-haskell/& target=&_blank& rel=&nofollow noreferrer&&原文&i class=&icon-external&&&/i&&/a&），和實現了惰性求值的 &a class=& wrap external& href=&///?target=https%3A///shouya/thinking-dumps/tree/master/lazy& target=&_blank& rel=&nofollow noreferrer&&Loli&i class=&icon-external&&&/i&&/a& 語言。 &br&&br&首先，Loli 類似 Haskell 惰性求值的實現主要在兩方面：第一，動態閉包的傳參方式實現 non-strict 的語意；第二，用自訂類型支持方便的 streaming，為了接近 Haskell，我在 Loli 中用的是 ADT 的支持 。&br&&br&動態閉包（dynamic closure）的傳參方式就是說，求值器在求值一個 function application 的時候不會對其參數求值，而是會封到一個動態閉包裡。動態閉包其實就是一個帶 binding 的表達式，動態閉包有很多名字，有的叫之 thunk，也有些地方稱之為 redex，不過就我的理解動態閉包不能和 redex 畫上等號，因為在我的實現裡 redex 還包括其他一些表達式類型。所有的值只有在用到的時候才會被規約到模範型（normal form）。做到這點並不會很難，scheme 的 delay 和 force 函數就可以用來實現簡單的手動惰性求值功能。&br&&br&其實第二個的要點在於支持弱首模範式（weak-head normal form），來實現自訂數據類型值的 non-strict 語意。也就是說，數據類型構造子（data type constructor）的參數也像函數參數一樣被封入動態閉包裡，即使這個數據類型值被要求強行規約也不會對其構造子參數進行規約。&br&&br&唉，我不太擅長用人類語言描述這個過程，其實 Loli 核心的惰性求值代碼不過是下面一段，不介意的話直接讀 Racket 代碼吧：&br&&br&&div class=&highlight&&&pre&&code class=&language-scheme&&&span class=&p&&(&/span&&span class=&k&&define &/span&&span class=&p&&(&/span&&span class=&nf&&eval-preliminary&/span& &span class=&nv&&force?&/span&&span class=&p&&)&/span&
&span class=&p&&(&/span&&span class=&err&&λ&/span& &span class=&p&&(&/span&&span class=&nf&&expr&/span& &span class=&nv&&env&/span&&span class=&p&&)&/span&
&span class=&p&&(&/span&&span class=&nf&&cond&/span&
&span class=&p&&[(&/span&&span class=&nf&&normal?&/span& &span class=&nv&&expr&/span&&span class=&p&&)&/span& &span class=&nv&&expr&/span&&span class=&p&&]&/span&
&span class=&p&&[(&/span&&span class=&nf&&redex?&/span& &span class=&nv&&expr&/span&&span class=&p&&)&/span& &span class=&p&&(&/span&&span class=&k&&if &/span&&span class=&nv&&force?&/span& &span class=&p&&(&/span&&span class=&nf&&reduce&/span& &span class=&nv&&expr&/span& &span class=&nv&&env&/span&&span class=&p&&)&/span& &span class=&nv&&expr&/span&&span class=&p&&)]&/span&
&span class=&p&&[(&/span&&span class=&nf&&appl?&/span& &span class=&nv&&expr&/span&&span class=&p&&)&/span&
&span class=&p&&(&/span&&span class=&k&&let &/span&&span class=&p&&([&/span&&span class=&nv&&ecar&/span& &span class=&p&&(&/span&&span class=&nf&&eval-force&/span& &span class=&p&&(&/span&&span class=&nb&&cadr &/span&&span class=&nv&&expr&/span&&span class=&p&&)&/span& &span class=&nv&&env&/span&&span class=&p&&)])&/span&
&span class=&p&&(&/span&&span class=&k&&define &/span&&span class=&p&&(&/span&&span class=&nf&&reduce-opt&/span& &span class=&nv&&val&/span&&span class=&p&&)&/span& &span class=&p&&(&/span&&span class=&k&&if &/span&&span class=&nv&&force?&/span& &span class=&p&&(&/span&&span class=&nf&&reduce&/span& &span class=&nv&&val&/span& &span class=&nv&&env&/span&&span class=&p&&)&/span& &span class=&nv&&val&/span&&span class=&p&&))&/span&
&span class=&p&&(&/span&&span class=&nf&&cond&/span&
&span class=&p&&[(&/span&&span class=&err&&λ&/span&&span class=&nv&&?&/span& &span class=&nv&&ecar&/span&&span class=&p&&)&/span&
&span class=&p&&(&/span&&span class=&nf&&reduce-opt&/span& &span class=&p&&(&/span&&span class=&nf&&eval-lambda&/span& &span class=&nv&&ecar&/span& &span class=&p&&(&/span&&span class=&nf&&make-closure&/span& &span class=&nv&&env&/span& &span class=&p&&(&/span&&span class=&nb&&caddr &/span&&span class=&nv&&expr&/span&&span class=&p&&))))]&/span&
&span class=&p&&[(&/span&&span class=&nf&&proc?&/span& &span class=&nv&&ecar&/span&&span class=&p&&)&/span&
&span class=&p&&(&/span&&span class=&nf&&reduce-opt&/span& &span class=&p&&(&/span&&span class=&nf&&eval-proc&/span& &span class=&nv&&ecar&/span& &span class=&p&&(&/span&&span class=&nf&&make-closure&/span& &span class=&nv&&env&/span& &span class=&p&&(&/span&&span class=&nb&&caddr &/span&&span class=&nv&&expr&/span&&span class=&p&&))))]&/span&
&span class=&p&&[&/span&&span class=&k&&else &/span&&span class=&p&&(&/span&&span class=&nf&&error&/span& &span class=&s&&&unknown expression&&/span&&span class=&p&&)]))])))&/span&
&span class=&p&&(&/span&&span class=&k&&define &/span&&span class=&nv&&eval&/span&
&span class=&p&&(&/span&&span class=&nf&&eval-preliminary&/span& &span class=&no&&#f&/span&&span class=&p&&))&/span&
&span class=&p&&(&/span&&span class=&k&&define &/span&&span class=&nv&&eval-force&/span& &span class=&p&&(&/span&&span class=&nf&&eval-preliminary&/span& &span class=&no&&#t&/span&&span class=&p&&))&/span&
&span class=&p&&(&/span&&span class=&k&&define &/span&&span class=&p&&(&/span&&span class=&nf&&reduce&/span& &span class=&nv&&expr&/span& &span class=&nv&&env&/span&&span class=&p&&)&/span&
&span class=&p&&(&/span&&span class=&k&&let &/span&&span class=&p&&([&/span&&span class=&nv&&result&/span& &span class=&p&&(&/span&&span class=&nf&&cond&/span&
&span class=&p&&[(&/span&&span class=&nf&&ref?&/span&
&span class=&nv&&expr&/span&&span class=&p&&)&/span& &span class=&p&&(&/span&&span class=&nf&&follow-ref-force&/span& &span class=&p&&(&/span&&span class=&nb&&cadr &/span&&span class=&nv&&expr&/span&&span class=&p&&)&/span& &span class=&nv&&env&/span&&span class=&p&&)]&/span&
&span class=&p&&[(&/span&&span class=&err&&λ&/span&&span class=&nv&&raw?&/span& &span class=&nv&&expr&/span&&span class=&p&&)&/span& &span class=&p&&(&/span&&span class=&nf&&make-lambda&/span& &span class=&nv&&expr&/span& &span class=&nv&&env&/span&&span class=&p&&)]&/span&
&span class=&p&&[(&/span&&span class=&nf&&closure?&/span& &span class=&nv&&expr&/span&&span class=&p&&)&/span& &span class=&p&&(&/span&&span class=&nf&&resolve-closure&/span& &span class=&nv&&expr&/span&&span class=&p&&)]&/span&
&span class=&p&&[(&/span&&span class=&nf&&normal?&/span& &span class=&nv&&expr&/span&&span class=&p&&)&/span& &span class=&nv&&expr&/span&&span class=&p&&]&/span&
&span class=&p&&[&/span&&span class=&k&&else &/span&&span class=&p&&(&/span&&span class=&nf&&error&/span& &span class=&s&&&neither redex nor normal!&&/span&&span class=&p&&)])])&/span&
&span class=&p&&(&/span&&span class=&k&&if &/span&&span class=&p&&(&/span&&span class=&nf&&redex?&/span& &span class=&nv&&result&/span&&span class=&p&&)&/span&
&span class=&p&&(&/span&&span class=&nf&&reduce&/span& &span class=&nv&&result&/span& &span class=&nv&&env&/span&&span class=&p&&)&/span&
&span class=&nv&&result&/span&&span class=&p&&)))&/span&
&/code&&/pre&&/div&
這週把惰性求值實現了一遍，終於覺得有自信回答這個問題了。我在這裡的解釋會比較簡略，不過推薦來讀我翻譯的文章《》（），和實現了惰性求值的
語言。 首先，Loli 類似 Haskell 惰性求值的實現主要在兩方面：第一，動態…
&p&LWT只是实现, 关键是在LWT 之上的&a href=&/p/& class=&internal&&并发&/a&模型不同.&/p&&p&在听过名字而且有 LWT 的语言有三个 Erlang, Haskell, Go, 但是它们的并发模型并不一样. 不妨把 LWT想象成在 OS 提供的硬件抽象上为了实现想要的并发模型语义再上一层的包装, 共同点只是几个都想执行调度单元变得轻量罢了.&/p&&p&回顾 &a href=&///?target=http%3A//mgampkay.github.io/posts/history-of-ghc-io-manager.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&GHC IO管理器的进化历程&i class=&icon-external&&&/i&&/a&, 就会发现 Haskell 就像 &a class=&member_mention& href=&///people/2d8f51b98& data-hash=&2d8f51b98& data-hovercard=&p$b$2d8f51b98&&@Canto Ostinato&/a& 所说的那样一开始没想着像 Erlang 那样, 都是按共享内存的思路来搞的.
而 Erlang, 看 Joe Armstrong &a href=&///?target=http%3A//www.erlang.org/download/armstrong_thesis_2003.pdf& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Making Reliable Distributed Systems in the Presence of Software Errors&i class=&icon-external&&&/i&&/a&
就知道, 人家思路完全不一样, 整个系统都搭在 Actor + 消息传递的模型上. 这就是 &a class=&member_mention& href=&///people/2d8f51b98& data-hash=&2d8f51b98& data-hovercard=&p$b$2d8f51b98&&@Canto Ostinato&/a& 所说的数据同步的方式不同.&/p&&p&Erlang 这样的数据同步方式优点还是有不少的:&/p&&p&每个&进程&一个堆的话相当于这个进程里面的资源的声明周期跟这个进程绑定起来, 一旦这个进程生命周期结束, 里面的资源就要释放, 资源里面最重要的是内存, 这样 Erlang RTS 里 GC 的成本就会均摊下来, 也不用有常见的 STW 问题, 达到软实时的效果. 写代码的时候还可以利用&进程&的生命周期做些资源管理的事, 例如访问 DB 的时候 DB 返回的结果转为 Erlang 的数据结构之后就不需要了, 这个之后就可以用一个临时进程作为中介, 处理完就销毁这个进程就完事了.
当然消息传递的 copy 也是有点问题的, Erlang 里不是所有东西都放在进程的堆里面的, 例如大于 64 字节的 binary 会在对外用引用计数管理,
有时候进程的生死没管好会有内存侧漏现象, 还好 Erlang 提供的工具挺好跟踪 (&/p&&p&还有一个优点就是完全的分布式, Haskell 虽然提供了几个比较好用可以组合的共享内存并发原语, 已经可以实现常见的并发模式, 但是这些并不能搬到分布式上面去(参考Simon Marlow的Parallel and Concurrent Programming in Haskell). 但是 Erlang 的 OTP 早就是按分布式设计的, 单机只是单节点, 整个 application 模型, 还有supervisor + gen_server 模式无论在单机还是分布式情况都可以 apply, 之前翻译 &a href=&/p/& class=&internal&&剖析Haskell应用架构&/a& 并发那一小结提到的模型, 其实就是手动实现的类似的模式. 可以这么说, Erlang 的模型和模式搞后端服务就是爽, Haskell + Cloud Haskell 要跟上还要等不知道多久.&/p&&p&至于 Erlang 这样搞的缺点? 缺点就是跟主流不太一样 (&/p&&p&从模型反推 LWT 底层算是答了题目没 (&/p&
LWT只是实现, 关键是在LWT 之上的模型不同.在听过名字而且有 LWT 的语言有三个 Erlang, Haskell, Go, 但是它们的并发模型并不一样. 不妨把 LWT想象成在 OS 提供的硬件抽象上为了实现想要的并发模型语义再上一层的包装, 共同点只是几个都想执行调度单元…
Haskell 以后就没有语言默认惰性求值/按名传递了，恰恰说明认真学习了 Haskell 的人觉得太给力了，没必要再去造 Haskell 以外的惰性求值/按名传递的编程语言了。&br&&br&&blockquote&&i&Haskell is the reason I am still a programmer today.&br&&/i&[...]&br&I'd been toying with writing my own programming language for 15 years or so by that point, and they all looked like the child of Perl, Python and C++ --
because those were what I knew -- with a dash of immutability thrown in. When I found Haskell I realized that here was a language that not only did all the things I was trying to do, but it did them &i&better&/i&.&br&&br&&i&The Haskell community simply had better answers than I did!&br&&/i&&br&（大意是 ekmett 这位同学自己捣鼓了 15 年的自造编程语言，但他发现 Haskell 才知道天外有天，Haskell 就是给出了更好的答案。）&br&&br&&i&(&a href=&///?target=https%3A///What-is-your-review-of-Haskell-programming-language/answer/Edward-Kmett%3Fsrid%3Dg3ET& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Edward Kmett's answer to What is your review of Haskell (programming language)?&i class=&icon-external&&&/i&&/a&)&br&&/i&&/blockquote&&br&纯函数式编程设计成 non-strict 是个非常自然的决定，因为纯函数的调用和求值是没有顺序的，限定任何一个求值顺序都会导致滑向 imperative 的思想。由此我们发现，non-strict 语义意味着更强的可组合性和更容易做公式推理的效果。比如说&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&nf&&factorial&/span& &span class=&n&&n&/span& &span class=&ow&&=&/span&
&span class=&kr&&if&/span& &span class=&n&&n&/span& &span class=&o&&==&/span& &span class=&mi&&0&/span&
&span class=&kr&&then&/span& &span class=&mi&&1&/span&
&span class=&kr&&else&/span& &span class=&n&&n&/span& &span class=&o&&*&/span& &span class=&n&&factorial&/span& &span class=&p&&(&/span&&span class=&n&&n&/span& &span class=&o&&-&/span& &span class=&mi&&1&/span&&span class=&p&&)&/span&
&/code&&/pre&&/div& 就不能被写成&br&&div class=&highlight&&&pre&&code class=&language-haskell&&&span class=&nf&&factorial&/span& &span class=&n&&n&/span& &span class=&ow&&=&/span&
&span class=&kr&&let&/span& &span class=&n&&next&/span& &span class=&ow&&=&/span& &span class=&n&&factorial&/span& &span class=&p&&(&/span&&span class=&n&&n&/span& &span class=&o&&-&/span& &span class=&mi&&1&/span&&span class=&p&&)&/span&
&span class=&kr&&in&/span&
&span class=&kr&&if&/span& &span class=&n&&n&/span& &span class=&o&&==&/span& &span class=&mi&&0&/span&
&span class=&kr&&then&/span& &span class=&mi&&1&/span&
&span class=&kr&&else&/span& &span class=&n&&n&/span& &span class=&o&&*&/span& &span class=&n&&next&/span&
&/code&&/pre&&/div&据我所知，在任何其它层面考虑 non-strict 的语义的好处都没有足够的说服力。&br&&br&很显然的一点：所谓的“惰性求值”在非函数式语言里面基本上是废的。而一个函数式语言呢？一个会 OCaml 的在 freenode #haskell 表示：&br&&div class=&highlight&&&pre&&code class=&language-text&&&Onemorenickname_& dramforever, i come to haskell because there are some things that are /much/ simpler here
&Onemorenickname_& like, default lazyness
&/code&&/pre&&/div&（这位同学之前在抱怨的是 Haskell 没有一个 OCaml 那么棒的 module system）&br&其实我看到这个的时候也挺惊讶的，因为讲道理，我还真没见过几个初学 Haskell 的表示惰性求值好的。&br&&br&你看，non-strict 多棒啊。&br&&br&但是问题是什么呢？纯函数式编程都快失传了。&br&Imperative 的观念深入人心到，其它的编程方式都是不存在的。&br&&blockquote&比如我有三个函数f1,f2,f3,和flow主控函数，我希望在这个flow主控函数里，按照自己的意图，分别运行f1,f3,f2函数。仅仅面对这样的一个简单的功能需求，我却是无从下手？如何表达这种需求？&br&在haskell函数里，无法顺序运行多个函数或语句？&br&内心都要抓狂了&a href=&///?target=https%3A///winterland1989/magic-haskell/issues/35& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&(link)&i class=&icon-external&&&/i&&/a&&/blockquote&&br&（在以上回答中的所有引文都只做举例，并非“挂人”的目的。如有人感到无法接受请评论告诉我，我会修改。）
Haskell 以后就没有语言默认惰性求值/按名传递了，恰恰说明认真学习了 Haskell 的人觉得太给力了，没必要再去造 Haskell 以外的惰性求值/按名传递的编程语言了。 Haskell is the reason I am still a programmer today. [...] I'd been toying with writing…
&p&这个问题我一起也问过，后来读了SPJ的那两篇论文大概就明白了：&/p&&p&G-machine：就是graph machine图计算机，FP的程序基本上都可以用一个表达式的图表示，图计算机就是对这个图求值的机器，总的说来对图的求值是一个不停合并图上的节点生产新节点的过程。例如：&/p&&div class=&highlight&&&pre&&code class=&language-text&&let x = 2 + 3 in x * x
&/code&&/pre&&/div&&p&一个简单的想法是先计算出5，然后创建一个新的节点5 * 5，然后再对这个节点求值，于是求值过程中就产生了很多临时的、立即进入的节点，这些中间节点也被叫做是spine，求值过程是沿着spine完成的。&/p&&p&但是这样就产生了很多额外的allocation，在The Spineless_G-machine那篇论文里，SPJ详细描述了一种可以避免创建图上的中间节点的方案。&/p&&p&首先有个基础叫做lambda lifting，这是来自John Hughes的关键性观察：我们可以把程序里，很多捕捉了外围绑定的闭包函数中的这些绑定，转换成函数的参数，从而消除闭包，得到的这个函数就可以自由脱离书写的作用域，被静态的编译到机器码里。这些被float out的函数也叫supercombinator（我擦，搞得跟超级赛亚人一样什么鬼）。然后一个程序就是一堆supercombinator的组合，整个程序的执行就和传统的顺序执行大大相似了，把main函数这个表达式求个值，遇到supercombinator就是一次call。&/p&&p&如果我们完全这样顺序执行会遇到一个问题，就是共享节点的冗余计算问题：刚刚的例子里，如果我们不创建新的节点，顺序计算完了第一个x，第二个x还会再被算一遍。于是SPJ提出了Spineless reduction的概念：我们只有当面临需要重复计算的情况时，才去创建节点，不然就一路顺序算下去。论文和核心思路是把图的更新操作和共享联系起来，如果一个计算的结果没有被共享，那就直接放到寄存器／栈上继续执行下去，否则要更新对应的节点。&/p&&p&tagless是另一个非常有趣的设计：传统的图推导机需要区分thunk和WHNF，然后在求值过程中区别对待，但是SPJ意识到，WHNF不过是一段entry code比较特别的计算，于是他统一了thunk和WHNF的内存表示，由一个统一的header指针直接指向进入闭包（SPJ用闭包统一指代以上两种情况）的机器码，这部分内容在GHC wiki上有详细的解释：&a href=&///?target=https%3A//ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/HeapObjects& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Commentary/Rts/Storage/HeapObjects - GHC&i class=&icon-external&&&/i&&/a& ， 感兴趣的读者不妨仔细阅读，非常的inspiring。&/p&&p&在tagless的基础上，人们又进一步做了point tagging之类的优化，fascinating！&/p&
这个问题我一起也问过，后来读了SPJ的那两篇论文大概就明白了：G-machine：就是graph machine图计算机，FP的程序基本上都可以用一个表达式的图表示，图计算机就是对这个图求值的机器，总的说来对图的求值是一个不停合并图上的节点生产新节点的过程。例如：l…
&p&根据自动机的理论模型来就行, 用&a href=&///?target=https%3A//zh.wikipedia.org/wiki/%25E6%259C%%E7%258A%25B6%25E6%E6%259C%25BA& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&wikipedia&i class=&icon-external&&&/i&&/a&里那个例子为例:&/p&&img src=&/a2054288eff828a0d950b1ba31726bd9_b.png& data-rawwidth=&404& data-rawheight=&234& class=&content_image& width=&404&&&br&&div class=&highlight&&&pre&&code class=&language-lhs&&符号表:
&span class=&cs&&& &/span&&span class=&nf&&symbols&/span& &span class=&ow&&=&/span& &span class=&p&&[&/span&&span class=&sc&&'a'&/span&&span class=&o&&..&/span&&span class=&sc&&'z'&/span&&span class=&p&&]&/span&
&span class=&cs&&& &/span&&span class=&kr&&data&/span& &span class=&kt&&State&/span& &span class=&ow&&=&/span& &span class=&kt&&Start&/span& &span class=&o&&|&/span& &span class=&kt&&NFound&/span& &span class=&o&&|&/span& &span class=&kt&&IFound&/span& &span class=&o&&|&/span& &span class=&kt&&CFound&/span& &span class=&o&&|&/span& &span class=&kt&&Error&/span& &span class=&o&&|&/span& &span class=&kt&&Success&/span& &span class=&kr&&deriving&/span& &span class=&kt&&Show&/span&
初始状态集:
终结状态集:
[Error, Success]
&span class=&cs&&& &/span&&span class=&nf&&match&/span& &span class=&ow&&::&/span& &span class=&kt&&State&/span& &span class=&ow&&-&&/span& &span class=&kt&&Char&/span& &span class=&ow&&-&&/span& &span class=&kt&&State&/span&
&span class=&cs&&& &/span&&span class=&nf&&match&/span& &span class=&kt&&Start&/span&
&span class=&sc&&'n'&/span& &span class=&ow&&=&/span& &span class=&kt&&NFound&/span&
&span class=&cs&&& &/span&&span class=&nf&&match&/span& &span class=&kt&&Start&/span&
&span class=&kr&&_&/span&
&span class=&ow&&=&/span& &span class=&kt&&Error&/span&
&span class=&cs&&& &/span&&span class=&nf&&match&/span& &span class=&kt&&NFound&/span& &span class=&sc&&'i'&/span& &span class=&ow&&=&/span& &span class=&kt&&IFound&/span&
&span class=&cs&&& &/span&&span class=&nf&&match&/span& &span class=&kt&&NFound&/span&
&span class=&kr&&_&/span&
&span class=&ow&&=&/span& &span class=&kt&&Error&/span&
&span class=&cs&&& &/span&&span class=&nf&&match&/span& &span class=&kt&&IFound&/span& &span class=&sc&&'c'&/span& &span class=&ow&&=&/span& &span class=&kt&&CFound&/span&
&span class=&cs&&& &/span&&span class=&nf&&match&/span& &span class=&kt&&IFound&/span&
&span class=&kr&&_&/span&
&span class=&ow&&=&/span& &span class=&kt&&Error&/span&
&span class=&cs&&& &/span&&span class=&nf&&match&/span& &span class=&kt&&CFound&/span& &span class=&sc&&'e'&/span& &span class=&ow&&=&/span& &span class=&kt&&Success&/span&
&span class=&cs&&& &/span&&span class=&nf&&match&/span& &span class=&kt&&CFound&/span&
&span class=&kr&&_&/span&
&span class=&ow&&=&/span& &span class=&kt&&Error&/span&
&span class=&cs&&& &/span&&span class=&nf&&matchNice&/span& &span class=&ow&&::&/span& &span class=&kt&&String&/span& &span class=&ow&&-&&/span& &span class=&kt&&State&/span&
&span class=&cs&&& &/span&&span class=&nf&&matchNice&/span& &span class=&n&&str&/span& &span class=&ow&&=&/span& &span class=&n&&matchNice'&/span& &span class=&n&&str&/span& &span class=&kt&&Start&/span&
&span class=&cs&&&
&/span&&span class=&kr&&where&/span&
&span class=&cs&&&
&/span&&span class=&nf&&matchNice'&/span& &span class=&kr&&_&/span&
&span class=&kt&&Error&/span&
&span class=&ow&&=&/span& &span class=&kt&&Error&/span&
&span class=&cs&&&
&/span&&span class=&nf&&matchNice'&/span& &span class=&kt&&[]&/span&
&span class=&kt&&Success&/span& &span class=&ow&&=&/span& &span class=&kt&&Success&/span&
&span class=&cs&&&
&/span&&span class=&nf&&matchNice'&/span& &span class=&p&&(&/span&&span class=&n&&x&/span&&span class=&kt&&:&/span&&span class=&n&&xs&/span&&span class=&p&&)&/span& &span class=&n&&state&/span&
&span class=&ow&&=&/span& &span class=&n&&matchNice'&/span& &span class=&n&&xs&/span& &span class=&p&&(&/span&&span class=&n&&match&/span& &span class=&n&&state&/span& &span class=&n&&x&/span&&span class=&p&&)&/span&
&span class=&cs&&&
&/span&&span class=&nf&&matchNice'&/span& &span class=&kr&&_&/span&
&span class=&kt&&Success&/span& &span class=&ow&&=&/span& &span class=&kt&&Error&/span&
&/code&&/pre&&/div&效率什么的忽略, 大概是这个意思~&br&&br&--&br&补上一个用Elixir的宏的例子&br&&div class=&highlight&&&pre&&code class=&language-elixir&&&span class=&kd&&defmodule&/span& &span class=&nc&&Fsm&/span& &span class=&k&&do&/span&
&span class=&n&&fsm&/span& &span class=&o&&=&/span& &span class=&p&&[&/span&
&span class=&ss&&running&/span&&span class=&p&&:&/span& &span class=&p&&{&/span&&span class=&ss&&:pause&/span&&span class=&p&&,&/span& &span class=&ss&&:paused&/span&&span class=&p&&},&/span&
&span class=&ss&&running&/span&&span class=&p&&:&/span& &span class=&p&&{&/span&&span class=&ss&&:stop&/span&&span class=&p&&,&/span& &span class=&ss&&:stopped&/span&&span class=&p&&},&/span&
&span class=&ss&&paused&/span&&span class=&p&&:&/span& &span class=&p&&{&/span&&span class=&ss&&:resume&/span&&span class=&p&&,&/span& &span class=&ss&&:running&/span&&span class=&p&&}&/span&
&span class=&p&&]&/span&
&span class=&k&&for&/span& &span class=&p&&{&/span&&span class=&n&&state&/span&&span class=&p&&,&/span& &span class=&p&&{&/span&&span class=&n&&action&/span&&span class=&p&&,&/span& &span class=&n&&next_state&/span&&span class=&p&&}}&/span& &span class=&o&&&-&/span& &span class=&n&&fsm&/span& &span class=&k&&do&/span&
&span class=&kd&&def&/span& &span class=&k&&unquote&/span&&span class=&p&&(&/span&&span class=&n&&action&/span&&span class=&p&&)(&/span&&span class=&k&&unquote&/span&&span class=&p&&(&/span&&span class=&n&&state&/span&&span class=&p&&)),&/span& &span class=&ss&&do&/span&&span class=&p&&:&/span& &span class=&k&&unquote&/span&&span class=&p&&(&/span&&span class=&n&&next_state&/span&&span class=&p&&)&/span&
&span class=&k&&end&/span&
&span class=&kd&&def&/span& &span class=&n&&initial&/span&&span class=&p&&,&/span& &span class=&ss&&do&/span&&span class=&p&&:&/span& &span class=&ss&&:running&/span&
&span class=&k&&end&/span&
&span class=&nc&&Fsm&/span&&span class=&o&&.&/span&&span class=&n&&initial&/span&
&span class=&c1&&# :running&/span&
&span class=&nc&&Fsm&/span&&span class=&o&&.&/span&&span class=&n&&initial&/span& &span class=&o&&|&&/span& &span class=&nc&&Fsm&/span&&span class=&o&&.&/span&&span class=&n&&pause&/span&
&span class=&c1&&# :paused&/span&
&span class=&nc&&Fsm&/span&&span class=&o&&.&/span&&span class=&n&&initial&/span& &span class=&o&&|&&/span& &span class=&nc&&Fsm&/span&&span class=&o&&.&/span&&span class=&n&&pause&/span& &span class=&o&&|&&/span& &span class=&nc&&Fsm&/span&&span class=&o&&.&/span&&span class=&n&&pause&/span&
&span class=&c1&&# ** (FunctionClauseError) no function clause matching in Fsm.pause/1&/span&
&/code&&/pre&&/div&via &a href=&///?target=http%3A///2014/06/understanding-elixir-macros-part-1.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&&i class=&icon-external&&&/i&&/a&
根据自动机的理论模型来就行, 用里那个例子为例: 符号表:
& symbols = ['a'..'z']
& data State = Start | NFound | IFound | CFound | Error | Success deriving Show
初始状态集:
终结状态集:
[Error, Success]
等你学会用一些高大上的hackage写一些靠谱的程序之后，我推荐你阅读《The Implementation of Functional Programming Languages》。这是我院simon大神写的，深入浅出，感人肺腑，入木三分。
等你学会用一些高大上的hackage写一些靠谱的程序之后，我推荐你阅读《The Implementation of Functional Programming Languages》。这是我院simon大神写的，深入浅出，感人肺腑，入木三分。
&p&Monad可以用來規範所有的上下文敏感文法(context-sensitvie grammar)語言. Comonad可以用來建立前者語言的解釋器(intepreter)或剖析器(parser)&/p&&p&建構上下文敏感文法的語言及其剖析器, 要是這還不夠實用, 我就不清楚啥叫實用了&/p&&p&簡單說, Monad建構產生語言, Comonad解構分析語言. 若Monad具體型別是m a, Comonad的具體型別是w a, 那就會存在一個函數 w a -& m a -& a, 此函數讓一個剖析器跟一個語言一起執行產生出 a&/p&&p&數學中有不少東西都具有互為對偶的結構, 對偶的結構攪和在一起會產生一個遺忘原本結構的值, 例如列向量跟行向量內積是實數, Comonad的w a跟Monad的m a一同產生a, 也是類似這麼回事&/p&&p&順便提我用得是Idris, 用來建一些隨機模型的EDSL&/p&
Monad可以用來規範所有的上下文敏感文法(context-sensitvie grammar)語言. Comonad可以用來建立前者語言的解釋器(intepreter)或剖析器(parser)建構上下文敏感文法的語言及其剖析器, 要是這還不夠實用, 我就不清楚啥叫實用了簡單說, Monad建構產生語言, Como…
谢邀, 感觉用这种小花做个碎花裙子应该挺好看的, via &a href=&///?target=https%3A//wiki.haskell.org/Haskell_logos/New_logo_ideas& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Haskell logos/New logo ideas&i class=&icon-external&&&/i&&/a&&br&&br&&b&感谢各位支持 我样子比较彪悍 不适合女装&/b&&br&&img src=&/v2-66ad0d3171fe_b.png& data-rawwidth=&292& data-rawheight=&75& class=&content_image& width=&292&&&img src=&/v2-5ad3180931efe4e21f4edb3b704f4735_b.png& data-rawwidth=&516& data-rawheight=&182& class=&origin_image zh-lightbox-thumb& width=&516& data-original=&/v2-5ad3180931efe4e21f4edb3b704f4735_r.png&&&img src=&/v2-d16c17e517af2ffe232ec9_b.png& data-rawwidth=&1310& data-rawheight=&1162& class=&origin_image zh-lightbox-thumb& width=&1310& data-original=&/v2-d16c17e517af2ffe232ec9_r.png&&
谢邀, 感觉用这种小花做个碎花裙子应该挺好看的, via
感谢各位支持 我样子比较彪悍 不适合女装
已有帐号？
无法登录？
社交帐号登录