Erlang/Elixir [填坑] lazy

luikore · 2013年07月08日 · 最后由 recurlamlisp 回复于 2013年07月28日 · 3959 次阅读

强烈谴责 b 大给别人挖坑的行为 hello interpreter: http://ruby-china.org/topics/11301

一般编程语言的函数调用都是 strict order 的, 就是所有参数传给一个函数之前, 会将所有参数求值, 再跑进函数体里. 但有些表达式/语句结构的组成部分却是延迟的, 例如 or 表达式的短路效果:

def f
  puts 'f'
  true
end

def g
  puts 'g'
  false
end

f or g    # 只有 f 调用了, g 没调用
f and g # g 调用了

所以在 ruby 里, andor 是不能重新定义的.

如果把 if ... else 当成一个表达式

(if-else cond true-clause false-clause)

那表达式的 true-clause 和 false-clause 都是延迟执行的. 到底执行哪个要进入到 if-else 函数体内才能决定.

为了定义条件语句和支持短路的布尔运算符, SICP 的 lazy 其实是定义了两个 primitive:

  • (delay-it exp) 对 exp 延迟求值
  • (force-it exp) 无视状况对 exp 立刻求值

全盘 lazy 是什么样子? 就是所有的 exp 都变成了 (delay-it exp). 那么 (force-it exp) 也变成了 (delay-it (force-it (delay-it exp))) 执行不下去了. 所以至少 force-it 不能做 lazy 变换, 某些默认函数也要添加 force-it 去让程序能跑下去.

默认 lazy 的 haskell, 可以理解为 IO monad 自动给表达式加上了 force-it, 并且通过类型限制, 禁止在 force-it 的外面加上 delay-it.


back to erlang

delay 直接和 quote 差不多 force 就要调用一个不同版本的 apply, 这个 apply 的 prim 里要忽略掉 delay

首先把 b 大的代码改造下...

- module(sexp).
- compile({no_auto_import, [apply/2]}).
- compile(export_all).
% make:all([load]).

eval(Env, []) ->
    {Env, []};
eval(Env, [H|T]) ->
    {Env1, RH} = apply(Env, H),
    {Env2, RT} = eval(Env1, T),
    {Env2, [RH|RT]}.

apply(Env, Atom) when is_atom(Atom) ->
    {Atom, Value} = proplists:lookup(Atom, Env),
    {Env, Value};
apply(Env, [Op|Args]) ->
    {Env1, Func} = apply(Env, Op),
    Func(Env1, Args).

quote(Env, [X]) ->
    {Env, X}.

new_env() ->
    [
     {quote, fun quote/2},
    ].

SICP 里只有 quote, atom 就不搞了

其中通过 fun quote/2 获取了 lambda object, 就不需要加个 prim 去手工 dispatch 了.

make:all([load]).
E = sexp:new_env().
{_, a} = sexp:apply(E, [quote, a]).
{_, quote} = sexp:apply(E, [quote, quote]).
{_, [a, b, c]} = sexp:apply(E, [quote, [a, b, c]]).

force 的实现, 就是先把环境改造下, 插个 delay = nodelay 进去, 然后对 AST 求值, 然后再恢复环境

force(Env, [X]) ->
    Env1 = [{delay, fun nodelay/2}|Env],
    {Env2, Value} = apply(Env1, X),
    {[{delay, fun delay/2}|Env2], Value}.

delay 和 nodelay

delay(Env, [X]) ->
    {Env, X}.

nodelay(Env, [X]) ->
    {Env1, Value} = apply(Env, X),
    {Env, Value}.

现在终于可以定义 ifelse 了... 回忆 lambda calculus, true 和 false 可以定义为下面这俩货:

true = λ x _ . x
false = λ _ y . y

翻译成 erlang 就是

truef(Env, [X, _]) ->
    apply(Env, X).

falsef(Env, [_, Y]) ->
    apply(Env, Y).

ifelse(Env, [Pred, True, False]) ->
    {Env1, Value} = apply(Env, Pred),
    Value(True, False).

(写完回头一看, 诶! 为什么没用 delay 和 force 实现!) ...

最后补充下 new_env (apply 和 eval 也能放进去的呀干嘛不放)

new_env() ->
    [
        {true,   fun truef/2},
        {false,  fun falsef/2},
        {eval,   fun eval/2},
        {apply,  fun apply/2},
        {quote,  fun quote/2},
        {delay,  fun delay/2},
        {force,  fun force/2},
        {ifelse, fun ifelse/2},
    ].

代码能否跑还没测, 喝个粥先...

1楼 已删除

我来打酱油...

#2 楼 @wppurking 我是胡乱写的... 对怎么实现 lisp 的语义没兴趣...

怒赞

@luikore

class Lisp
  def initialize
    @env = { 
      :label => lambda { |(name,val), _| @env[name] = val },
      :quote => lambda { |sexpr, _| sexpr[0] },
      :car   => lambda { |(list), _| list[0] },
      :cdr   => lambda { |(list), _| list.drop 1 },
      :cons  => lambda { |(e,cell), _| [e] + cell },
      :eq    => lambda { |(l,r), _| l == r },
      :if    => lambda { |(cond, thn, els), ctx| eval(cond, ctx) ? eval(thn, ctx) : eval(els, ctx) },
      :atom  => lambda { |(sexpr), _| (sexpr.is_a? Symbol) or (sexpr.is_a? Numeric) }
    }
  end

  def apply fn, args, ctx=@env
    return @env[fn].call(args, ctx) if @env[fn].respond_to? :call

    self.eval @env[fn][2], Hash[*(@env[fn][1].zip args).flatten(1)]
  end

  def eval sexpr, ctx=@env
    if @env[:atom].call [sexpr], ctx
      return ctx[sexpr] if ctx[sexpr]
      return sexpr
    end

    fn = sexpr[0]
    args = (sexpr.drop 1)
    args = args.map { |a| self.eval(a, ctx) } if not [:quote, :if].member? fn
    apply(fn, args, ctx)
  end
end
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册