Archive

Archive for the ‘Push’ Category

The Push Monad: Introduction

March 16, 2012 Leave a comment

Chapter 5 of Friendly F# has a great practical explanation of F# computation expressions often called “monads” from their use in computer science and Haskell. The material in Chapter 5 of the book does a lot to demystify the concept, theoretical coverage of which is done well in this Wikipedia article.

Monads are an example of things best grasped by actually doing. So I set out to implement one in my project.

What Friendly F# discussion instills above all (confirmed by the Wiki article) is that a monad in functional programming is a great way to subsume some common side effects or patterns under an explicit syntax that serves several purposes:

  • Unclutter the code
  • Make the pattern visible thus improving readability, while at the same time
  • Avoiding “action at a distance” anti-pattern, where things seem to happen magically but it is extremely hard to figure out what is actually responsible for the magic

In this particular case, the monadic pattern is implied by the Push language: all programs are 100% robust, i.e. all syntactically correct programs execute without throwing an exception and the state of the system is preserved. This means that every time something occurs that makes execution of an operation impossible, we need to “unwind” the system and return it to its state before execution had started. It would be nice to factor all of that out of the implementation so we can concentrate exclusively on semantics of the operations.

So, while implementing Push operations the following must be done:

  1. See if there are enough arguments on stack(s). If there were less than enough exit.
  2. Start executing the operation. If the operation cannot be completed return everything back to the stack(s), exit. Else:
  3. Push result to the appropriate stack.

For instance, here is an implementation of one of Push operations written without the use of monads:

        [<PushOperation("%")>]
        static member Mod() =
            match processArgs2 Float.Me.MyType with
            | [a1; a2] -> 
                if a2.Raw<float>() = 0. 
                then 
                    pushResult a1
                    pushResult a2
                else
                    let quot = Math.Floor(Math.Floor(a1.Raw<float>()) / Math.Floor(a2.Raw<float>()))
                    let res =  a1.Raw<float>() - quot * a2.Raw<float>()
                    pushResult(Float(res))
            | _ -> ()

Here all the steps are recognizable:

  1. Pop two arguments from the FLOAT stack using processArgs2. If it returns anything but a list of two values exit.
  2. Check if the second argument is 0. If so, return arguments back to the stack and exit, otherwise execute the operation.
  3. Push the result back to the FLOAT stack

Here is the monadic version:

    [<PushOperation("%")>]
    static member Mod() =
        let getMod stack = 
            push {
                let! right = popOne stack
                let! left = popOne<float> stack
                if right <> 0. then
                    let quot = Math.Floor(Math.Floor(left) / Math.Floor(right))
                    return! result stack (left - quot * right)
            }
        getMod Float.Me.MyType

We no longer need to explicitly handle the pattern mentioned above. All the steps and branches are contained within our definition of the “push” monad, so no magic here. The reader of the code knows where to look for explanation of the side effects.

If there are less than 2 values on top of the FLOAT stack, execution will not go forward and previous arguments will be returned to the stack.

If the right argument is 0, “unwinding” of the state will also happen automatically without any need to handle this case explicitly.

One other convenience: we can now factor out extracting the value from an object we get from the top of a stack (by calling its Raw<’a>() function). This is done by implementing the monad and presented through compiler sugar of “let!” assignment. A great improvement on maintainability and ease of implementation.

“Under the hood” details to be discussed in the next post.

Push Operation. A Few Words on Computation Expressions/Monads

January 30, 2012 Leave a comment

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:

Implementing a Push Type

January 29, 2012 Leave a comment

From a developer’s point of view, a Push type is implemented through a class, derived from PushTypeBase, as mentioned in the previous post.

Once the type is implemented in any .NET language the system will hook it into the currently available types, will add a parser and a stack for it.

All that needs to be done is:

  1. Declare a class, deriving from PushTypeBase, and decorated with PushType attribute. Here the required parameter to the attribute is the name of the type:
        [<PushType("FLOAT")>]
        type Float =
            inherit PushTypeBase
             
  2. Define default constructor, and the constructor with one argument: the underlying type value, e.g., for a FLOAT type – a float type value:

    in C#:

            public Float() : base() {};
            public Float(double d) : base (d) {};
             

    and here is the syntax for the same in F#:

            new () = {inherit PushTypeBase ()}
            new (f : float) = {inherit PushTypeBase(f)}
             
  3. For easy access to the type name of this Push type, define a static member and instantiate it with the default constructor.
              static member Me = Float()
             
  4. Implement custom parsing if required by creating a parse function and overriding the base class Parser property. Or simply override the Parser property to return Unchecked.defaultof<ExtendedTypeParser> in F#, null in C#:

            // custom parsing
            static member parse s =
                let result = ref Unchecked.defaultof<float>
                if not (System.Double.TryParse(s, result)) 
                then 
                    Unchecked.defaultof<PushTypeBase> 
                else 
                    new Float(!result) :> PushTypeBase
    
            override t.Parser 
                with get() = 
                    ExtendedTypeParser(Float.parse)
             
  5. Override the base class ToString() implementation, if necessary. The base implementation will simply call the ToString() of the underlying value type if it is implemented.
  6. Implement type specific operations (more in the next post):
           [<PushOperation("+")>]
            static member Add() =
                match processArgs2 Float.Me.MyType with
                | [a1; a2] -> pushResult(Float(a1.Raw<float>() + a2.Raw<float>()))
                | _ -> ()
                
            [<PushOperation("*")>]
            static member Multiply() =
                match processArgs2 Float.Me.MyType with
                | [a1; a2] -> pushResult(Float(a1.Raw<float>() * a2.Raw<float>()))
                | _ -> ()
    
             

Here is an example of extending the language with the URL type, implemented in C#:

    [PushType("URL")]
    public class UrlPushType : Type.PushTypeBase
    {
        public UrlPushType() : base() {}
        public UrlPushType(Uri url) : base(url) {}

        static UrlPushType UrlParse(string url)
        {
            try
            {
                if (!url.Trim().StartsWith("http://", true, CultureInfo.InvariantCulture))
                {
                    return null;
                }

                Uri uri = new Uri(url);
                if (uri.HostNameType != UriHostNameType.Dns)
                {
                    return null;
                }

                return new UrlPushType(uri);

            }
            catch (Exception)
            {
                return null;                
            }
        }

        public override Type.ExtendedTypeParser Parser
        {
            get 
            {
                return new Type.ExtendedTypeParser(UrlParse);
            }
        }

        [PushOperation("DOMAIN", Description="Extract domain name from the URL")]
        static void ExtractDomain()
        {
            // pop the URL from the URL stack
            var arg = TypeFactory.processArgs1("URL");

            //if there is nothing there...
            if (arg == null)
            {
                return;
            }

            // extract the underlying data
            var uri = arg.Raw<Uri>();

            //create the new URI
            var newUri = new UrlPushType(new Uri(uri.Host));
            
            // push it back to the URL stack.
            TypeFactory.pushResult(newUri);
        }

        public override string ToString()
        {
            return base.ToString();
        }
Categories: C#, F#, Push Tags:

Defining a Base for Push Types

January 28, 2012 Leave a comment

Let’s take a look at how the base from which all Push types derive is defined.

namespace push.types
 
[<AutoOpen>]
module Type =
    
    open System.Reflection
    open push.exceptions
    open System.Diagnostics
    open System
 
    let Random = Random (int DateTime.UtcNow.Ticks)
 
    [<DebuggerDisplay("Value = {Value}")>]
    [<StructuredFormatDisplay("{StructuredFormatDisplay}")>]
    [<AbstractClass>]
    type PushTypeBase () = 
        [<DefaultValue>] 
        val mutable private value : obj
 
        [<DefaultValue>]
        val mutable private myType : string
 
        new (v) as this = PushTypeBase()
                            then this.value <- v
 
        member t.Value with get() = t.value
 
        static member private GetMyType (me : #PushTypeBase) =
            if System.String.IsNullOrEmpty(me.myType)
            then
                me.myType <- (me.GetType().GetCustomAttributes(typeof<PushTypeAttribute>, false).[0] :?> PushTypeAttribute).Name
            me.myType   
 
        // if something more than default action is necessary
        // this should be overridden
        abstract member Eval : PushTypeBase
        default t.Eval = t
                
        abstract member MyType : string with get
        default t.MyType with get () = PushTypeBase.GetMyType(t)
 
        abstract member isQuotable : bool with get
        default t.isQuotable with get () = false
 
        member t.Raw<'a> () =
            match t.Value with
            | :? 'a as raw -> raw
            | _ -> failwithf "could not convert to the right type"
 
        abstract StructuredFormatDisplay : obj
        default t.StructuredFormatDisplay =
            box t.Value
 
        override t.ToString() =
            t.Value.ToString()
 
        abstract Parser : ExtendedTypeParser with get
    
    and     // override this delegate to parse extended types
        ExtendedTypeParser = delegate of string -> PushTypeBase

Push types are represented (in all .NET languages) by classes derived from PushTypeBase. This is an abstract class and the listing above shows its definition.
Two properties are essential for all classes, deriving from PushTypeBase:
Value – an object that represents the actual value of the instance of this type
MyType - name of the Push type (i.e. INTEGER) that this object represents.

Implementation of the Value property is straightforward. MyType is slightly harder because it needs to be bootstrapped for each individual push type. In other words, once the instance of this type is created, we need to actually discover its Push type.

An easy way out would be to just let the developer set this property at object instantiation, but since Push types are already decorated by attributes, that specify their names, which is necessary for dynamic discovery, I did not want to introduce code duplication.

So, the function that drives this virtual property, GetMyType, actually takes an instance of the PushTypeBase derived class:

static member private GetMyType (me : #PushTypeBase) =

The “#” in type annotation means “any class, that has #PushTypeBase somewhere in its derivation hierarchy.

This function actually looks at the instance of the class it is given and extracts the name of Push type from its custom attributes. It only does that once, on first call. In the implementations of PushTypeBase it is necessary to define a variable that would refer to an instance of the same type. Kind of ugly, but avoids code duplication. MyType can then be accessed through this variable: Me.MyType

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

    static member Me = Float()

    override t.ToString() =
        t.Raw<float>().ToString("F")

   

Another function to note is Raw(). This property unboxes the actual value of the Value property and presents it as an F# object or value. A type parameter is necessary for that. For instance, the FLOAT type can return string representations of its objects by overriding the .NET object ToString() functions as shows in the above example.

Noteworthy Stuff

:
1. [<AutoOpen>] attribute at the module level instructs F# to open the module automatically, once its containing namespace is being open. I find it very convenient.
2.

    [<DebuggerDisplay("Value = {Value}")>]
    [<StructuredFormatDisplay("{StructuredFormatDisplay}")>]
    [<AbstractClass>]

Decorating classes with DebuggerDisplay and StructuredFormatDisplay attributes, and then implementing custom displays saves a lot of time debugging and should generally be done for most if not every object.

Here is a snapshot taken during execution of a simple test:

        [TestMethod]
        public void DoSimple()
        {
            var prog = "(CODE.QUOTE (5 INTEGER.+) CODE.QUOTE (3 5 INTEGER.*) CODE.DO CODE.DO)";
            Program.ExecPush(prog);
 
            Assert.AreEqual(20, TestUtils.Top<long>("INTEGER"));
        }

This program does the following:

1. Pushes (5 INTEGER.+) on the CODE stack
2. Pushes (3 5 INTEGER.*) on the CODE stack
3. Executes the program on top of the CODE stack
   (the result is 3 *5 pushed to INTEGER stack)
4. Executes the program on top of the CODE stack
   (the result is 5 pushed to INTEGER tack and then
   5 + 15 pushed on top of the INTEGER stack.

Here is a snapshot of the interpreter state taken during this execution.
Because of DebuggerDisplay and StructuredFormatDisplay for various objects, the state of the INTEGER stack can be clearly observed.

Debugger Watch Window

Categories: F#, Push Tags: , ,
Follow

Get every new post delivered to your Inbox.