Actors acting as Lambdas

The Untyped Lambda Calculus encoded as actors (F#'s MailboxProcessors)

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60:

// Useful type aliases
type Actor = MailboxProcessor<obj>
type Ident = string
type Cond = Actor
type Env = Actor
 
 
let (<!>) (actor : Actor) (msg : 'T) = actor.Post msg
 
// run forever - template
let start<'T> (work : 'T -> unit) : Actor =
    MailboxProcessor<obj>.Start(fun mb ->
        let rec loop () =
            async {
                let! msg = mb.Receive()
                match msg with
                | :? 'T as msg' -> work msg'
                | _ -> () // oops... undefined behaviour
                return! loop ()
            }
        loop () )
 
// Helper print expression
let printExp = start<obj>(fun value -> printfn "Print: %A" value)
 
// Enviroment encoding functions
let emptyEnv =
    start<Cond * Ident>(fun _ -> ()(*oops... undefined behaviour*))
let buildEnv ident value env =
    start<Cond * Ident>(fun (cond, ident') -> if ident = ident' then cond <!> value else env <!> (cond, ident'))
 
// Closures are also actors
let closure ident body env =
    start<Cond * obj>(fun (cond, arg) -> let env' = buildEnv ident arg env in body <!> (cond, env'))
 
// Lambda Calculus expressions
let constExp value = start<Cond * Env>(fun (cond, _) -> cond <!> value)
let identExp ident = start<Cond * Env>(fun (cond, env) -> env <!> (cond, ident))
 
let lambdaExp ident body =
    start<Cond * Env>(fun (cond, env) -> cond <!> closure ident body env)
 
let appExp exp argExp =
    start<Cond * Env>(fun (cond, env) ->
        let closureCond =
            start<Cond>(fun closure ->
                let argCond = start<obj>(fun value -> closure <!> (cond, value))
                argExp <!> (argCond, env))
        exp <!> (closureCond, env))
 
// Examples
 
let idExp = lambdaExp "x" (identExp "x")
let example = appExp idExp (constExp 42)
 
example <!> (printExp, emptyEnv) // Print: 42
 
let selfAppExp = lambdaExp "x" (appExp (identExp "x") (identExp "x"))
let omega = appExp selfAppExp selfAppExp
omega <!> (printExp, emptyEnv) // run forever

Multiple items
type MailboxProcessor<'Msg> =
  interface IDisposable
  new : body:(MailboxProcessor<'Msg> -> Async<unit>) * ?cancellationToken:CancellationToken -> MailboxProcessor<'Msg>
  member Post : message:'Msg -> unit
  member PostAndAsyncReply : buildMessage:(AsyncReplyChannel<'Reply> -> 'Msg) * ?timeout:int -> Async<'Reply>
  member PostAndReply : buildMessage:(AsyncReplyChannel<'Reply> -> 'Msg) * ?timeout:int -> 'Reply
  member PostAndTryAsyncReply : buildMessage:(AsyncReplyChannel<'Reply> -> 'Msg) * ?timeout:int -> Async<'Reply option>
  member Receive : ?timeout:int -> Async<'Msg>
  member Scan : scanner:('Msg -> Async<'T> option) * ?timeout:int -> Async<'T>
  member Start : unit -> unit
  member TryPostAndReply : buildMessage:(AsyncReplyChannel<'Reply> -> 'Msg) * ?timeout:int -> 'Reply option
  ...

Full name: Microsoft.FSharp.Control.MailboxProcessor<_>

--------------------
new : body:(MailboxProcessor<'Msg> -> Async<unit>) * ?cancellationToken:System.Threading.CancellationToken -> MailboxProcessor<'Msg>

type obj = System.Object

Full name: Microsoft.FSharp.Core.obj

type Ident = string

Full name: Script.Ident

Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = System.String

Full name: Microsoft.FSharp.Core.string

type Cond = Actor

Full name: Script.Cond

type Actor = MailboxProcessor<obj>

Full name: Script.Actor

type Env = Actor

Full name: Script.Env

val actor : Actor

val msg : 'T

member MailboxProcessor.Post : message:'Msg -> unit

val start : work:('T -> unit) -> Actor

Full name: Script.start

val work : ('T -> unit)

type unit = Unit

Full name: Microsoft.FSharp.Core.unit

val mb : MailboxProcessor<obj>

val loop : (unit -> Async<'a>)

val async : AsyncBuilder

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.async

val msg : obj

member MailboxProcessor.Receive : ?timeout:int -> Async<'Msg>

val msg' : 'T

val printExp : Actor

Full name: Script.printExp

val value : obj

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

val emptyEnv : Actor

Full name: Script.emptyEnv

val buildEnv : ident:Ident -> value:'a -> env:Actor -> Actor

Full name: Script.buildEnv

val ident : Ident

val value : 'a

val env : Actor

val cond : Cond

val ident' : Ident

val closure : ident:Ident -> body:Actor -> env:Actor -> Actor

Full name: Script.closure

val body : Actor

val arg : obj

val env' : Actor

val constExp : value:'a -> Actor

Full name: Script.constExp

val identExp : ident:'a -> Actor

Full name: Script.identExp

val ident : 'a

val env : Env

val lambdaExp : ident:Ident -> body:Actor -> Actor

Full name: Script.lambdaExp

val appExp : exp:Actor -> argExp:Actor -> Actor

Full name: Script.appExp

val exp : Actor

val argExp : Actor

val closureCond : Actor

val closure : Cond

val argCond : Actor

val idExp : Actor

Full name: Script.idExp

val example : Actor

Full name: Script.example

val selfAppExp : Actor

Full name: Script.selfAppExp

val omega : Actor

Full name: Script.omega

Raw view Test code New version

More information

Link:	http://fssnip.net/4m
Posted:	12 years ago
Author:	Nick Palladinos
Tags:	actors , lambda calculus , mailboxprocessor