Home > C#, computation expression, F#, monad, Push > Push Operation. A Few Words on Computation Expressions/Monads

Push Operation. A Few Words on Computation Expressions/Monads

January 30, 2012 Leave a comment Go to comments

As we have seen in the previous post, it is easy to implement Push types and operations:

  [<PushType("FLOAT")>]
    type Float =
        inherit PushTypeBase

        new () = {inherit PushTypeBase ()}
        new (f : float) = {inherit PushTypeBase(f)}

        static member Me = Float()

        [<PushOperation("/")>]
        static member Divide() =
            match processArgs2 Float.Me.MyType with
            | [a1; a2] -> 
                if a2.Raw<float>() = 0. 
                then 
                    pushResult a1
                    pushResult a2
                else pushResult(Float(a1.Raw<float>() / a2.Raw<float>()))
            | _ -> ()

Here is an example of an implementation of FLOAT./ operation: a division of two integers on top of the stack.

Since in Push an operation is denoted by “OP_TYPE.OP_NAME”, it is convenient from the implementation standpoint to group operations that are unique to a specific type under the definition of this type. Operations are declared static and that declaration is enforced by the system.

Methods, implementing operations take no arguments, since all of the information is implied in implementation: we know exactly the type of stack we are working with, as well as how to obtain arguments from it.

Minimizing Code Duplication. Generic Operations.

Some push operations are “generic” in a sense, that each type implements one. E.g.: DUP, YANK, SWAP, etc manipulate stacks of their type (i.e. INTEGER.DUP pushes a duplicate of the top of the INTEGER stack).

In order to minimize code duplication, it is possible to define “Generic” Push types. These types do not have names and no stack is created for them. They are simply “bags of operations”.

Generic stock operations are implemented as follows:

    [<GenericPushType>]
    type Ops ()=
        [<GenericPushOperation("<", AppliesTo=[|"INTEGER"; "FLOAT"|])>]
        static member Lt tp =
            dualOp (<) tp Bool.Me.MyType

        [<GenericPushOperation(">", AppliesTo=[|"INTEGER"; "FLOAT"|])>]
        static member Gt tp =
            dualOp (>) tp Bool.Me.MyType

        [<GenericPushOperation("=")>]
        static member Eq tp =
            dualOp (=) tp Bool.Me.MyType
          
        [<GenericPushOperation("DUP", Description = "Pushes the duplicate of the top of the stack")>]
        static member dup tp =
            if stockTypes.Stacks.[tp].length = 0 then ()
            else 
                stockTypes.pushResult (peek stockTypes.Stacks.[tp])

        [<GenericPushOperation("POP", Description = "Pops the top of the stack")>]
        static member pop tp =
            processArgs1 tp |> ignore

        [<GenericPushOperation("ROT", Description = "Rotates 3 top stack entries")>]
        static member rot tp =
            pushResult (new Integer(2L))
            Ops.yank tp

The type that bags these operations is decorated with GenericPushType attribute. No name is specified, since this is not a “type” at all, just a bag of operations. Each operation is decorated with GenericPushOperation attribute, that besides the name and the description of the operation can have an AppliesTo argument that filters out the types to which the operation applies. So, for example operations “>”, “<", "=" apply to numeric types only.

The signature of a method that implements a generic operation is slightly different than that of a regular operation. There is a string argument denoting the type of the operation. This is used to determine on which stack to perform the operation. The type argument can be any of the current types: "INTEGER", "FLOAT", etc.

A Word about Monads

All Push operations have a very similar structure. They do the following:

  1. Pop one or two arguments from the stack. If the stack has fewer arguments – quit.
  2. Present the top of the stack as the right-hand argument and the next value on the stack as the left-hand one.
  3. Make sure the conditions for performing the operation are met. E.g., if the operation is “/”, top of the stack is not 0. If they are not met, push the arguments back and return.
  4. Execute the operation.
  5. Push the result onto the appropriate stack.

The devide operation on the FLOAT type goes through exactly these steps:

        [<PushOperation("/")>]
        static member Divide() =
            match processArgs2 Float.Me.MyType with
            | [a1; a2] -> 
                if a2.Raw<float>() = 0. 
                then 
                    pushResult a1
                    pushResult a2
                else pushResult(Float(a1.Raw<float>() / a2.Raw<float>()))
            | _ -> ()

The following helper functions are almost ubiquitously used.
processArgs2 (processArg1) – pops 2 (1) arguments from the top of the stack and presents them in the right order. If it returns anything but a list of two objects of the right type, the operation does nothing.
pushResult – pushes result of the operation to the appropriate stack. Or in this case returns arguments to the stack, if one of them is 0.

Basically, code for all operations looks very similar. Which leads us to think that computation expressions (aka “Monads”) are a good fit for implementing operations. Monads allow for an easy way to factor out the common “side effects” of the code being executed, and just let us concentrate on functionality. So, for example, the computation expression-based implementation of the division operation above looks like this:


    [<PushOperation("/")>]
    static member Divide() =
        let divide stack = 
            push {
                let! right = popOne stack
                let! left = popOne stack
                if right <> 0. then
                    return! (result stack (left / right))
            }
        divide Float.Me.MyType

Note:

  • in this case we do not need to special-case the fact that arguments are returned to the stack if the operation cannot be performed. We were able to include that functionality into the implementation of the “push” computation expression.
  • No need to call Raw() to extract values. This is also encoded in the computation expression.
  • No special provision is made for the case when there are fewer than two arguments. Again, the computation expression takes care of that.
  • The code is easier to read. All of the “common” functionality is factored out of the “push{}”.

Monadic implementation will be discussed in detail in the future posts.

Implementing a Generic Op in C#

For testing, I have implemented a TOSTRING operation for INTEGER type as a generic operation. This operation represents the top of the INTEGER stack as string literal and pushes the result to the LITERAL stack:

   [GenericPushType]
    public class IntegerOpExtension
    {
        [GenericPushOperation("TOSTRING", 
            Description="Converts top integer to a literal", 
            AppliesTo= new string [] {"INTEGER"})]
        public static void ConvertToString()
        {
            if(TypeFactory.isEmptyStack("INTEGER"))
            {
                return;
            }

            long val = TypeFactory.processArgs1("INTEGER").Raw<long>();

            TypeFactory.pushResult (new Literal(val.ToString()));
        }
    }
Categories: C#, computation expression, F#, monad, Push Tags:
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: