Functional Thread 14 : Parser Combinators

JNumber Parser
From json.org
A number is very much like a C or Java number, except that the octal and hexadecimal formats are not used.

The following syntax diagram summarises the specification for the JNumber parser.
770140

Again we'll break this seemingly complex syntax diagram into its constituent parts; representing each as a sub parsing function that'll we composite together to create the JNumber parser:

Optional Negative Sign
The pOptionalSign defines a optional - character parser, used to denote only the negative sign.
C#:
module JSON =
...
// --- Parse a JNumber ---
let private pOptionalSign = Parser.opt (Parser.pchar '-') <?> "Optional Sign"


Zero Parser
The pDigit1to9 defines a 0 digit character parser, used to denote only a zero digit.
C#:
module JSON =
...
// --- Parse a JNumber ---
...
  let private pZero = Parser.pstring "0" <?> "Zero"


Digit 1 to 9 Parser
The pDigit1to9 defines a 1 to 9 digit character parser, used to denote any of the number's digits, excluding the zero 0 digit.
C#:
module JSON =
...
// --- Parse a JNumber ---
...
let private pDigit1to9 = Parser.satisfy (fun c -> Char.IsDigit c && c <> '0') "Digit 1 to 9"


Digit Parser
The pDigit defines a 0 to 9 digit character parser, used to denote any of the number's digits.
C#:
module JSON =
...
// --- Parse a JNumber ---
...
  let private pDigit = Parser.satisfy Char.IsDigit "Digit"


Dot Parser
The pDot defines a . character parser, used to denote an decimal part of a number.
C#:
module JSON =
...
// --- Parse a JNumber ---
...
  let private pDot = Parser.pchar '.' <?> "Dot ."


Exponent Symbol Parser
The pE defines an orElse parser between e or E character, used to denote an exponent part of a number.
C#:
module JSON =
...
// --- Parse a JNumber ---
...
  let private pE = Parser.pchar 'e' <|> Parser.pchar 'E' <?> "Exponent Symbol"


Optional +/- Parser
The pOptionalPlusMinus defines an optional plus + or minus - sign parser.
C#:
module JSON =
...
// --- Parse a JNumber ---
...
  let private pOptionalPlusMinus = Parser.opt (Parser.pchar '-' <|> Parser.pchar '+') <?> "Optional +/-"


Non Zero Integer Parser
The pIntegerNonZero parser requires a pDigit1to9 prefix tied to a zerp or more digits (0 to 9) Parser.manyChars pDigit.
C#:
module JSON =
...
// --- Parse a JNumber ---
...
  let private pIntegerNonZero = pDigit1to9 .>>. Parser.manyChars pDigit <&> fun (h, t) -> string h + t


Integer Parser
The pInteger parser is a orElse between a pZero parser and a pIntegerNonZero parser.
C#:
module JSON =
...
// --- Parse a JNumber ---
...
let private pInteger = pZero <|> pIntegerNonZero <?> "Integer Non Zero"


Fraction Parser
The pFraction parser requires a pDot prefix but it excludes it from the result by linking it with the >>. infix operator tied to a 1 or more digits (0 to 9) Parser.many1Chars pDigit.
C#:
module JSON =
...
// --- Parse a JNumber ---
...
  let private pFraction = pDot >>. Parser.many1Chars pDigit <?> "Fraction"


Exponent Parser
The pExponent parser requires a pE prefix but it excludes it from the result by linking it with the >>. infix operator tied to an optional +/- sign pOptionalPlusMinus, tied (andThen .>>. operator) to a 1 or more digits (0 to 9) Parser.many1Chars pDigit.
C#:
module JSON =
...
// --- Parse a JNumber ---
...
   let private pExponent = pE >>. pOptionalPlusMinus .>>. Parser.many1Chars pDigit <?> "Exponent"


Convert Helper Function
convert is a helper function to transform the result of the jNumber parser to a float and then a JNumber that encapsulates that float i.e. a set of tuples wrapped in a tuple wrapped in another tuple. The (((sign, int), fraction), exponent) parameter syntax serves to splat the tupled values as variables with the same names; which we then glue together using a new infix operator |>? that converts an Option wrapped value to string using a string conversion function; we add everything together with the + infix operator and then pipe that through to float; which converts a string to a float, and finally we pipe to JNumber to encapsulate the float in a JValue.
C#:
module JSON =
...
// --- Parse a JNumber ---
...
let private convert (((sign, int), fraction), exponent) =
    (sign |>? string) + int + (fraction |>? fun n -> "." + n) + (exponent |>? fun (s, d) -> "e" + (s |>? string) + d) |> float |> JNumber
The |>? infix operator is used to match over a Option wrapped value, converting the result to a string using a string conversion function parameter. This operator is defined as follows as will be added to the Parser library's Parser and Operator modules.
C#:
[<RequireQualifiedAccess>]
module Parser =
...
  let optToString opt f =
    match opt with
    | None -> ""
    | Some x -> f x
...

[<AutoOpen>]
module Operators =
...
  // Infix Option to string
  let (|>?) = Parser.optToString


JNumber parser tied to JValue
Finally we take all our sub parser and tie them together with the infix andThen operator .>>.; the pFraction and pExponent are defined as optional re Parser.opt, finally we convert the result; which is a tuple of tuple of tuple to JNumber i.e. a member value of the JValue discriminated union type we declared above.
C#:
module JSON =
...
// --- Parse a JNumber ---
...
  let private jNumber = pOptionalSign .>>. pInteger .>>. Parser.opt pFraction .>>. Parser.opt pExponent <&> convert <?> "JNumber"
 
Last edited:
JObject Parser
From json.org
An object is an unordered set of name/value pairs. An object begins with { and ends with }. Each name is followed by : and the name/value pairs are separated by ,.

The following syntax diagram summarises the specification for the JObject parser.
770144

Again we'll break this seemingly complex syntax diagram into its constituent parts; representing each as a sub parsing function that'll we composite together to create the JObject parser:

Forward reference problem
In the above diagram; the key / value pair presents a problem; we haven't defined a parser for JValue yet because JValue requires us to first define all its member parsers on which its definition depends, namely:
  • JString, JNumber, JObject, JArray, JBool, JNull
value-png.770108

Its a bit of a chicken or the egg problem, how do we reference a parser before we have defined it.
Mutual Recursion
It's a frequently reoccurring problem in parsing called Mutual Recursion, where two mathematical or computational objects, such as functions or data types, are defined in terms of each other.


Create a Forward Reference
The trick to address this is to create a forward reference to the jValue parser that initially has a dummy internal parser reference; which throws an exception. Later on, after we've define jValue we will the update the reference to point to jValue's parser code.

We add the following code to the Parser module to achieve this:
C#:
[<RequireQualifiedAccess>]
module Parser =
...
  let public createParserForwardedToRef<'a>() =
      let dummyParser=
        let f input : ParserResult<'a * ParserInput> = failwith "unfixed forwarded parser"
        { Func = f; Label = "undefined" }
      // ref to placeholder Parser
      let parserRef = ref dummyParser
      // wrapper Parser
      let f input = runInput !parserRef input // forward input to the placeholder
      let wrapperParser = { Func = f; Label = "undefined" }
      wrapperParser, parserRef
Note:
Internally the createParserForwardedToRef<'a> function assigns the dummyParser with a mutable reference.
C#:
let parserRef = ref dummyParser
The return value from this function is a tuple, where the first value wrapperParser is the parser initially setup with a dummy parser routine that we can use as a forward reference to jValue and the second value parserRef is the mutable reference that we have to update once we are ready to define the real jValue parser.



Key / Value Parser
The pKeyValue defines a parser for a key/value combination where the key is parsed as a pQuotedString as we defined it for JString earlier, then zero or more spaces that we exclude .>> from the output, followed by a : and zero or more spaces that we also exclude .>> from the output, sequenced andThen .>>. with a jValue and zero or more spaces that we also exclude .>> from the output,
C#:
module JSON =
...
  // -- Create a forward reference to jValue Parser
  let private jValue, private jValueReference = Parser.createParserForwardedToRef<JValue>()

// --- Parse a JObject ---
  let private pKeyValue = pQuotedString .>> Parser.spaces .>> (Parser.pchar ':' .>> Parser.spaces) .>>. jValue .>> Parser.spaces


Sequence of Key / Value Parsers Separated by a Comma
The pKeyValues defines a parser for one or more multiple key/values separated by a comma.
C#:
module JSON =
...
// --- Parse a JObject ---
...
  let private pKeyValues = Parser.sepBy1 pKeyValue (Parser.pchar ',' .>> Parser.spaces)



jValue Parser
The jObject defines a parser of one or more Key / Values pairs using pKeyValues parser that is prefixed with a { and suffixed with a }; the curly braces are excluded from the output by the >>. and .>> infix operators respectively. The output is then converted to a Map, using the Map.ofList function and then wrapped as a JObject, a member value of JValue.
C#:
module JSON =
...
// --- Parse a JObject ---
...
let private jObject = Parser.between (Parser.pchar '{' .>> Parser.spaces) pKeyValues (Parser.pchar '}' .>> Parser.spaces) <&> Map.ofList <&> JObject <?> "JObject"
 
Last edited:
JArray Parser
From json.org
An array is an ordered collection of values. An array begins with [ and ends with ]. Values are separated by ,.

The following syntax diagram summarises the specification for the JArray parser.
770146
Again we'll break this syntax diagram into its constituent parts; representing each as a sub parsing function that'll we composite together to create the JArray parser:

Forward reference problem?
In the above diagram; we also have a mutual recursion to jValue; fortunately we have already addressed this for jObject and can use the same forward referenced jValue without a problem.



Values Parser
The pValues defines a parser for one or more jValue delimited by a comma; we also exclude any zero or more spaces from the output.
C#:
module JSON =
...
// --- Parse a JArray ---
  let private pValues = Parser.sepBy1 (jValue .>> Parser.spaces) (Parser.pchar ',' .>> Parser.spaces)



jArray Parser
The jArray defines a parser for pValues encapsulated by an opening [ and a closing ]; we excludes both of these from the output and also exclude any zero or more spaces from the output. The output is then wrapped in a JArray, a member value of JValue.
C#:
module JSON =
...
// --- Parse a JArray ---
...
  let private jArray = Parser.between (Parser.pchar '[' .>> Parser.spaces) pValues (Parser.pchar ']' .>> Parser.spaces) <&> JArray <?> "JArray"
 
JBool Parser
The JBoolparser is a relatively simple parser to define; we simply define a jTrue sub parser that checks for the string "true" and another sub parser jFalse that checks for the string "false"; we then link these two together using the orElse infix operator <|> and we ignore the string result and simply return a JBool wrapping either boolean true or false, a member value of JValue.
C#:
module JSON =
...
  // --- Parse a JBool ---
  let private jBool =
    let jTrue = Parser.pstring "true" >>% JBool true
    let jFalse = Parser.pstring "false" >>% JBool false
    jTrue <|> jFalse <?> "JBool"



JNull Parser
The JNull is the easiest parser to define; we simply define a jNull parser that checks for the string "null" and we ignore the result and simply return a JNull, a member value of JValue.
C#:
let JSON =
...
  // --- Parse a JNull ---
  let private jNull = Parser.pstring "null" >>% JNull <?> "JNull"



JValue Parser
From json.org
A value can be a string in double quotes, or a number, or true or false or null, or an object or an array. These structures can be nested.
value-png.770108


Simply said the jValue parser is a choice between the jString, jNumber, jObject, jArray, jBool and jNull parsers. As we have already defined jValue as a Parser.createParserForwardedToRef<JValue>(), we need only update the mutable reference jValueReference to point to the valid computation of a jValue.

C#:
module JSON =
...
  // -- Parse a jValue ---
  jValueReference := Parser.choice [jNull; jBool; jString; jNumber; jArray; jObject ]
  let public parse str = Parser.run (jValue <?> "JValue") str
The := is a special assignment operator for updating mutable references; which we assign to a Parser.choice between jNull; jBool; jString; jNumber; jArray; jObject i.e. an orElse composition of parsers.

We also have defined a helper function called parse, which takes a string as input (a JSON string) and then tries to parse it with our jValue parser.


Recap
The complete JSON parser is as follows:
C#:
namespace Endofunk.Parser
open System

type JValue =
  | JString of string
  | JNumber of float
  | JObject of Map<string, JValue>
  | JArray of JValue list
  | JBool of bool
  | JNull

module JSON =
  // --- Parse a JString ---
  let private unescapedChars = ['\u005c'; '\u0022']
  let private pUnescapedChar = Parser.satisfy (fun c -> unescapedChars |> List.contains c |> not) "Unescaped Character"
  let private escapedChars = ["\\\"", '\u0022'; "\\\\", '\u005c'; "\\/", '\u002f'; "\\b", '\u0008'; "\\f", '\u000c'; "\\n", '\u000a'; "\\r", '\u000d'; "\\t", '\u0009']
  let private pEscapedChar = escapedChars |> List.map (fun (c, r) -> Parser.pstring c >>% r) |> Parser.choice <?> "Escaped Character"
  let private pUnicodeChar =
    let pId = Parser.pchar '\\' >>. Parser.pchar 'u'
    let pHex = Parser.anyOf (['0'..'9'] @ ['A'..'F'] @ ['a'..'f'])
    let convert (((h1, h2), h3), h4) = Int32.Parse(sprintf "%c%c%c%c" h1 h2 h3 h4, Globalization.NumberStyles.HexNumber) |> char
    pId >>. pHex .>>. pHex .>>. pHex .>>. pHex <&> convert <?> "Unicode Character"
  let private pQuotedString =
    let pQuote = Parser.pchar '\"' <?> "Quote"
    let pCharacters = pUnescapedChar <|> pEscapedChar <|> pUnicodeChar
    pQuote >>. Parser.manyChars pCharacters .>> pQuote
  let private jString = pQuotedString <&> JString <?> "JString"

  // --- Parse a JNumber ---
  let private pOptionalSign = Parser.opt (Parser.pchar '-') <?> "Optional Sign"
  let private pZero = Parser.pstring "0" <?> "Zero"
  let private pDigit1to9 = Parser.satisfy (fun c -> Char.IsDigit c && c <> '0') "Digit 1 to 9"
  let private pDigit = Parser.satisfy Char.IsDigit "Digit"
  let private pDot = Parser.pchar '.' <?> "Dot ."
  let private pE = Parser.pchar 'e' <|> Parser.pchar 'E' <?> "Exponent Symbol"
  let private pOptionalPlusMinus = Parser.opt (Parser.pchar '-' <|> Parser.pchar '+') <?> "Optional +/-"
  let private pIntegerNonZero = pDigit1to9 .>>. Parser.manyChars pDigit <&> fun (h, t) -> string h + t
  let private pInteger = pZero <|> pIntegerNonZero <?> "Integer Non Zero"
  let private pFraction = pDot >>. Parser.many1Chars pDigit <?> "Fraction"
  let private pExponent = pE >>. pOptionalPlusMinus .>>. Parser.many1Chars pDigit <?> "Exponent"
  let private convert (((sign, int), fraction), exponent) =
    (sign |>? string) + int + (fraction |>? fun n -> "." + n) + (exponent |>? fun (s, d) -> "e" + (s |>? string) + d) |> float |> JNumber
  let private jNumber = pOptionalSign .>>. pInteger .>>. Parser.opt pFraction .>>. Parser.opt pExponent <&> convert <?> "JNumber"

  // -- Create a forward reference to jValue Parser
  let private jValue, private jValueReference = Parser.createParserForwardedToRef<JValue>()

  // --- Parse a JObject ---
  let private pKeyValue = pQuotedString .>> Parser.spaces .>> (Parser.pchar ':' .>> Parser.spaces) .>>. jValue .>> Parser.spaces
  let private pKeyValues = Parser.sepBy1 pKeyValue (Parser.pchar ',' .>> Parser.spaces)
  let private jObject = Parser.between (Parser.pchar '{' .>> Parser.spaces) pKeyValues (Parser.pchar '}' .>> Parser.spaces) <&> Map.ofList <&> JObject <?> "JObject"

  // --- Parse a JArray ---
  let private pValues = Parser.sepBy1 (jValue .>> Parser.spaces) (Parser.pchar ',' .>> Parser.spaces)
  let private jArray = Parser.between (Parser.pchar '[' .>> Parser.spaces) pValues (Parser.pchar ']' .>> Parser.spaces) <&> JArray <?> "JArray"

  // --- Parse a JBool ---
  let private jBool =
    let jTrue = Parser.pstring "true" >>% JBool true
    let jFalse = Parser.pstring "false" >>% JBool false
    jTrue <|> jFalse <?> "JBool"

  // --- Parse a JNull ---
  let private jNull = Parser.pstring "null" >>% JNull <?> "JNull"

  // -- Parse a jValue ---
  jValueReference := Parser.choice [jNull; jBool; jString; jNumber; jArray; jObject ]
  let public parse str = Parser.run (jValue <?> "JValue") str
 
Last edited:
Recap of the Parser library
Here's a complete listing of the Parser library including the changes we made whilst building the JSON parser.
C#:
namespace Endofunk.Parser
open System

type Offset = { X : int; Y : int }

module Offset =
  let initial = { X = 0; Y = 0 }
  let incX offset = { offset with X = offset.X + 1 }
  let incY offset = { X = 0; Y = offset.Y + 1 }

type ParserInput = { Offset : Offset; Lines : string[] }
 
module ParserInput =
  let create s =
    if String.IsNullOrEmpty(s) then { Lines = [||]; Offset = Offset.initial }
    else { Lines = s.Split([| "\r\n"; "\n" |], StringSplitOptions.None); Offset = Offset.initial }
  let current input = if input.Offset.Y < input.Lines.Length then input.Lines.[input.Offset.Y] else "EOF"
  let nextChar input =
    if input.Offset.Y >= input.Lines.Length then input, None
    else
      let line = current input
      if input.Offset.X < line.Length then { input with Offset = input.Offset |> Offset.incX }, Some line.[input.Offset.X]
      else { input with Offset = input.Offset |> Offset.incY }, Some '\n'

type ParserOffset = { Line : string; X : int; Y : int }

module ParserOffset =
  let fromInput input = { Line = ParserInput.current input; X = input.Offset.X; Y = input.Offset.Y }
      
type public ParserLabel = string
type public ParserError = string

type public ParserResult<'a> =
  | Success of 'a
  | Failed of ParserLabel * ParserError * ParserOffset

type public Parser<'a> = { Func : ParserInput -> ParserResult<'a * ParserInput>; Label : ParserLabel }
    
[<RequireQualifiedAccess>]
module Parser =
  /// Print a parsed result
  let public print result =
    match result with
    | Success(value, input) -> printfn "%A" value
    | Failed(label, error, offset) ->
      printfn "Error parsing %s at line %i column %i\n%s\n%s" label offset.Y offset.X offset.Line (sprintf "%*s^%s" offset.X "" error)

  /// Run a parser with some input
  let public runInput p input = p.Func input
  /// Run the parser with a string as input
  let public run p str = runInput p (ParserInput.create str)

  /// Update the label in the parser
  let setLabel p label =
    let f input =
      match p.Func input with
      | Success s -> Success s
      | Failed(oldLabel, err, offset) -> Failed(label, err, offset)
    { Func = f; Label = label }
  /// Infix version of setLabel
  let private (<?>) = setLabel

  /// Monad conformance
  let public flatmap f p =
    let label = "Undefined"
    let f input =
      match runInput p input with
      | Failed(label, err, offset) -> Failed(label, err, offset)
      | Success(head, tail) -> runInput (f head) tail
    { Func = f; Label = label }
  /// Alternative function for flatmap
  let public bind = flatmap
  /// Infix of flatmap
  let private (>>=) p f = flatmap f p
  /// Lift a value into a Parser
  let public rtn x =
    let label = sprintf "%A" x
    let f input = Success(x, input)
    { Func = f; Label = label }

  /// Functor conformance
  let public map f = flatmap (f >> rtn)
  /// Infix of map
  let private (<!>) = map
  /// Infix Reverse of map (piping)
  let private (<&>) x f = map f x
  /// ALternative Infix Reverse of map (piping)
  let private (|>>) = (<&>)

  /// Applicative Functor conformance
  let public apply fP xP = fP >>= fun f -> xP >>= fun x -> rtn (f x)
  /// Infix of apply
  let private (<*>) = apply
  /// Lift a single parameter function into the Parser world and apply
  let public liftA fn aP = rtn fn <*> aP
  /// Lift a two parameter function into the Parser world and apply
  let public liftA2 fn aP bP = liftA fn aP <*> bP
  /// Lift a three parameter function into the Parser world and apply
  let public liftA3 fn aP bP cP = liftA2 fn aP bP <*> cP
  /// Lift a four parameter function into the Parser world and apply
  let public liftA4 fn aP bP cP dP = liftA3 fn aP bP cP <*> dP
  /// Lift a five parameter function into the Parser world and apply
  let public liftA5 fn aP bP cP dP eP = liftA4 fn aP bP cP dP <*> eP
  /// Lift a six parameter function into the Parser world and apply
  let public liftA6 fn aP bP cP dP eP fP = liftA5 fn aP bP cP dP eP <*> fP

  /// Combine two parsers (logical conjunction)
  let public andThen p1 p2 =
    let label = sprintf "%s andThen %s" p1.Label p2.Label
    p1 >>= fun r1 -> p2 >>= fun r2 -> rtn (r1, r2) <?> label
  /// Infix of andThen
  let private (.>>.) = andThen
  /// Keep only the result of the left side parser
  let andThenFst p1 p2 = p1 .>>. p2 |> map (fun (a, b) -> a)
  /// Infix of andThenFst
  let private (.>>) = andThenFst
  /// Keep only the result of the right side parser
  let andThenSnd p1 p2 = p1 .>>. p2 |> map (fun (a, b) -> b)
  /// Infix of andThenSnd
  let private (>>.) = andThenSnd
  /// Keep only the result of the middle parser
  let public between p1 p2 p3 = p1 >>. p2 .>> p3

  /// Combine two parsers (logical disjunction)
  let public orElse p1 p2 =
    let label = sprintf "%s orElse %s" p1.Label p2.Label
    let f input =
      let r1 = runInput p1 input
      match r1 with
      | Success _ -> r1
      | Failed _ -> runInput p2 input
    { Func = f; Label = label }
  /// Infix of orElse
  let private (<|>) = orElse
  /// Choose from a list of Parsers
  let public choice pss = List.reduce (<|>) pss

  /// Higher Order Parser
  let public satisfy pred label =
    let f input =
      match ParserInput.nextChar input with
      | _, None -> Failed(label, "End of Input", ParserOffset.fromInput input)
      | tail, Some head ->
        if pred head then Success(head, tail)
        else Failed(label, sprintf "Unexpected '%c'" head, ParserOffset.fromInput input)
    { Func = f; Label = label}
    
  let rec public sequence ps =
    let cons head tail = head :: tail
    let consP = liftA2 cons
    match ps with
    | [] -> rtn []
    | head :: tail -> consP head (sequence tail)

  /// Match zero or more occurrences of the specified parser
  let rec private zeroOrMore p input =
    match runInput p input with
    | Failed(_, _, _) -> [], input
    | Success(head, tail) ->
      let (nextHeads, remainingTail) = zeroOrMore p tail
      (head :: nextHeads, remainingTail)

  /// Matches zero or more occurrences of the specified parser
  let public many p =
    let label = sprintf "many %s" p.Label
    let rec f input = Success(zeroOrMore p input)
    { Func = f; Label = label }
  /// Matches one or more occurrences of the specified parser
  let public many1 p =
    let label = sprintf "many1 %s" p.Label
    p >>= fun head -> many p >>= fun tail -> rtn (head :: tail) <?> label

  /// Parses an optional occurrence of p and returns an option value.
  let public opt p =
    let label = sprintf "opt %s" p.Label
    p <&> Some <|> rtn None <?> label

  let optToString opt f =
    match opt with
    | None -> ""
    | Some x -> f x

  /// Parses one or more occurrences of p separated by sep
  let public sepBy1 p sep =
    let sepThenP = sep >>. p
    p .>>. many sepThenP <&> fun (p, pList) -> p :: pList
    <?> "sepBy1"
  /// Parses zero or more occurrences of p separated by sep
  let public sepBy p sep = sepBy1 p sep <|> rtn [] <?> "sepBy"

  // Type parsers
  // -------------------------------------------------------------------
  /// Parse a char
  let public pchar c =
    let pred ch = (ch = c)
    let label = sprintf "%c" c
    satisfy pred label

  /// Choose from a list of characters
  let public anyOf cs =
    let label = sprintf "anyOf %A" cs
    cs
    |> List.map pchar
    |> choice
    <?> label

  /// Convert char list to string 
  let private charListToString cs = String(List.toArray cs)

  /// Parses a sequence of zero or more chars
  let manyChars p = many p <&> charListToString <?> "manyChars"
  /// Parses a sequence of one or more chars
  let many1Chars p = many1 p <&> charListToString <?> "many1Chars"

  /// Parse a specific string
  let public pstring s =
    s
    |> List.ofSeq
    |> List.map pchar
    |> sequence
    |> map charListToString
    <?> s

  // Whitespace parsers
  // -------------------------------------------------------------------
  /// Parse a whitespace char
  let ws = satisfy Char.IsWhiteSpace "Whitespace"
  /// Parse zero or more whitespace char
  let spaces = many ws
  /// Parse one or more whitespace char
  let spaces1 = many1 ws

  /// Create a forward reference
  let public createParserForwardedToRef<'a>() =
      let dummyParser=
        let f input : ParserResult<'a * ParserInput> = failwith "unfixed forwarded parser"
        { Func = f; Label = "undefined" }
      // ref to placeholder Parser
      let parserRef = ref dummyParser
      // wrapper Parser
      let f input = runInput !parserRef input // forward input to the placeholder
      let wrapperParser = { Func = f; Label = "undefined" }
      wrapperParser, parserRef

[<AutoOpen>]
module Operators =
  /// Infix version of setLabel
  let (<?>) = Parser.setLabel
  /// Infix of flatmap
  let (>>=) p f = Parser.flatmap f p
  /// Reverse Infix of flatmap
  let (=<<) = Parser.flatmap
  /// Infix of map
  let (<!>) = Parser.map
  /// Reverse Infix of map (piping)
  let (<&>) x f = Parser.map f x
  // Alternative Reverse Infix of <&>
  let (|>>) = (<&>)
  /// Infix of andThen
  let (.>>.) = Parser.andThen
  /// Keep only the result of the left side parser
  let (.>>) = Parser.andThenFst
  /// Keep only the result of the right side parser
  let (>>.) = Parser.andThenSnd
  /// Infix of orElse
  let (<|>) = Parser.orElse
  /// Applies parser p ignores the result and return x
  let (>>%) p x = p <&> fun _ -> x
  // Infix Option to string 
  let (|>?) = Parser.optToString

The two source file lengths; excluding blank lines and comments is:
  • 172 lines for Parser.fs
  • 51 lines for JSON.fs
 
Testing the JSON Parser
The tests will be based on the 5 JSON examples on json.org's example page:

C#:
open Endofunk
open Endofunk.Parser

[<EntryPoint>]
let main argv =

  let testJSON1 = """{
      "glossary": {
          "title": "example glossary",
      "GlossDiv": {
              "title": "S",
        "GlossList": {
                  "GlossEntry": {
                      "ID": "SGML",
            "SortAs": "SGML",
            "GlossTerm": "Standard Generalized Markup Language",
            "Acronym": "SGML",
            "Abbrev": "ISO 8879:1986",
            "GlossDef": {
                          "para": "A meta-markup language, used to create markup languages such as DocBook.",
              "GlossSeeAlso": ["GML", "XML"]
                      },
            "GlossSee": "markup"
                  }
              }
          }
      }
  }"""
  JSON.parse testJSON1 |> Parser.print

  let testJSON2 = """{"menu": {
    "id": "file",
    "value": "File",
    "popup": {
      "menuitem": [
        {"value": "New", "onclick": "CreateNewDoc()"},
        {"value": "Open", "onclick": "OpenDoc()"},
        {"value": "Close", "onclick": "CloseDoc()"}
      ]
    }
  }}"""
  JSON.parse testJSON1 |> Parser.print

  let testJSON3 = """{"widget": {
      "debug": "on",
      "window": {
          "title": "Sample Konfabulator Widget",
          "name": "main_window",
          "width": 500,
          "height": 500
      },
      "image": {
          "src": "Images/Sun.png",
          "name": "sun1",
          "hOffset": 250,
          "vOffset": 250,
          "alignment": "center"
      },
      "text": {
          "data": "Click Here",
          "size": 36,
          "style": "bold",
          "name": "text1",
          "hOffset": 250,
          "vOffset": 100,
          "alignment": "center",
          "onMouseUp": "sun1.opacity = (sun1.opacity / 100) * 90;"
      }
  }}"""
  JSON.parse testJSON3 |> Parser.print

  let testJSON4 = """{"web-app": {
    "servlet": [   
      {
        "servlet-name": "cofaxCDS",
        "servlet-class": "org.cofax.cds.CDSServlet",
        "init-param": {
          "configGlossary:installationAt": "Philadelphia, PA",
          "configGlossary:adminEmail": "[email protected]",
          "configGlossary:poweredBy": "Cofax",
          "configGlossary:poweredByIcon": "/images/cofax.gif",
          "configGlossary:staticPath": "/content/static",
          "templateProcessorClass": "org.cofax.WysiwygTemplate",
          "templateLoaderClass": "org.cofax.FilesTemplateLoader",
          "templatePath": "templates",
          "templateOverridePath": "",
          "defaultListTemplate": "listTemplate.htm",
          "defaultFileTemplate": "articleTemplate.htm",
          "useJSP": false,
          "jspListTemplate": "listTemplate.jsp",
          "jspFileTemplate": "articleTemplate.jsp",
          "cachePackageTagsTrack": 200,
          "cachePackageTagsStore": 200,
          "cachePackageTagsRefresh": 60,
          "cacheTemplatesTrack": 100,
          "cacheTemplatesStore": 50,
          "cacheTemplatesRefresh": 15,
          "cachePagesTrack": 200,
          "cachePagesStore": 100,
          "cachePagesRefresh": 10,
          "cachePagesDirtyRead": 10,
          "searchEngineListTemplate": "forSearchEnginesList.htm",
          "searchEngineFileTemplate": "forSearchEngines.htm",
          "searchEngineRobotsDb": "WEB-INF/robots.db",
          "useDataStore": true,
          "dataStoreClass": "org.cofax.SqlDataStore",
          "redirectionClass": "org.cofax.SqlRedirection",
          "dataStoreName": "cofax",
          "dataStoreDriver": "com.microsoft.jdbc.sqlserver.SQLServerDriver",
          "dataStoreUrl": "jdbc:microsoft:sqlserver://LOCALHOST:1433;DatabaseName=goon",
          "dataStoreUser": "sa",
          "dataStorePassword": "dataStoreTestQuery",
          "dataStoreTestQuery": "SET NOCOUNT ON;select test='test';",
          "dataStoreLogFile": "/usr/local/tomcat/logs/datastore.log",
          "dataStoreInitConns": 10,
          "dataStoreMaxConns": 100,
          "dataStoreConnUsageLimit": 100,
          "dataStoreLogLevel": "debug",
          "maxUrlLength": 500}},
      {
        "servlet-name": "cofaxEmail",
        "servlet-class": "org.cofax.cds.EmailServlet",
        "init-param": {
        "mailHost": "mail1",
        "mailHostOverride": "mail2"}},
      {
        "servlet-name": "cofaxAdmin",
        "servlet-class": "org.cofax.cds.AdminServlet"},
  
      {
        "servlet-name": "fileServlet",
        "servlet-class": "org.cofax.cds.FileServlet"},
      {
        "servlet-name": "cofaxTools",
        "servlet-class": "org.cofax.cms.CofaxToolsServlet",
        "init-param": {
          "templatePath": "toolstemplates/",
          "log": 1,
          "logLocation": "/usr/local/tomcat/logs/CofaxTools.log",
          "logMaxSize": "",
          "dataLog": 1,
          "dataLogLocation": "/usr/local/tomcat/logs/dataLog.log",
          "dataLogMaxSize": "",
          "removePageCache": "/content/admin/remove?cache=pages&id=",
          "removeTemplateCache": "/content/admin/remove?cache=templates&id=",
          "fileTransferFolder": "/usr/local/tomcat/webapps/content/fileTransferFolder",
          "lookInContext": 1,
          "adminGroupID": 4,
          "betaServer": true}}],
    "servlet-mapping": {
      "cofaxCDS": "/",
      "cofaxEmail": "/cofaxutil/aemail/*",
      "cofaxAdmin": "/admin/*",
      "fileServlet": "/static/*",
      "cofaxTools": "/tools/*"},
  
    "taglib": {
      "taglib-uri": "cofax.tld",
      "taglib-location": "/WEB-INF/tlds/cofax.tld"}}}"""
  JSON.parse testJSON4 |> Parser.print

  let testJSON5 = """{"menu": {
      "header": "SVG Viewer",
      "items": [
          {"id": "Open"},
          {"id": "OpenNew", "label": "Open New"},
          null,
          {"id": "ZoomIn", "label": "Zoom In"},
          {"id": "ZoomOut", "label": "Zoom Out"},
          {"id": "OriginalView", "label": "Original View"},
          null,
          {"id": "Quality"},
          {"id": "Pause"},
          {"id": "Mute"},
          null,
          {"id": "Find", "label": "Find..."},
          {"id": "FindAgain", "label": "Find Again"},
          {"id": "Copy"},
          {"id": "CopyAgain", "label": "Copy Again"},
          {"id": "CopySVG", "label": "Copy SVG"},
          {"id": "ViewSVG", "label": "View SVG"},
          {"id": "ViewSource", "label": "View Source"},
          {"id": "SaveAs", "label": "Save As"},
          null,
          {"id": "Help"},
          {"id": "About", "label": "About Adobe CVG Viewer..."}
      ]
  }}"""
  JSON.parse testJSON5 |> Parser.print
 
  // return an integer exit code
  0
 
JSON Test Output
Code:
JObject
  (map
     [("glossary",
       JObject
         (map
            [("GlossDiv",
              JObject
                (map
                   [("GlossList",
                     JObject
                       (map
                          [("GlossEntry",
                            JObject
                              (map
                                 [("Abbrev", JString "ISO 8879:1986");
                                  ("Acronym", JString "SGML");
                                  ("GlossDef",
                                   JObject
                                     (map
                                        [("GlossSeeAlso",
                                          JArray [JString "GML"; JString "XML"]);
                                         ("para",
                                          JString
                                            "A meta-markup language, used to create markup languages such as DocBook.")]));
                                  ("GlossSee", JString "markup");
                                  ("GlossTerm",
                                   JString
                                     "Standard Generalized Markup Language");
                                  ("ID", JString "SGML");
                                  ("SortAs", JString "SGML")]))]));
                    ("title", JString "S")]));
             ("title", JString "example glossary")]))])

JObject
  (map
     [("glossary",
       JObject
         (map
            [("GlossDiv",
              JObject
                (map
                   [("GlossList",
                     JObject
                       (map
                          [("GlossEntry",
                            JObject
                              (map
                                 [("Abbrev", JString "ISO 8879:1986");
                                  ("Acronym", JString "SGML");
                                  ("GlossDef",
                                   JObject
                                     (map
                                        [("GlossSeeAlso",
                                          JArray [JString "GML"; JString "XML"]);
                                         ("para",
                                          JString
                                            "A meta-markup language, used to create markup languages such as DocBook.")]));
                                  ("GlossSee", JString "markup");
                                  ("GlossTerm",
                                   JString
                                     "Standard Generalized Markup Language");
                                  ("ID", JString "SGML");
                                  ("SortAs", JString "SGML")]))]));
                    ("title", JString "S")]));
             ("title", JString "example glossary")]))])

JObject
  (map
     [("widget",
       JObject
         (map
            [("debug", JString "on");
             ("image",
              JObject
                (map
                   [("alignment", JString "center"); ("hOffset", JNumber 250.0);
                    ("name", JString "sun1"); ("src", JString "Images/Sun.png");
                    ("vOffset", JNumber 250.0)]));
             ("text",
              JObject
                (map
                   [("alignment", JString "center");
                    ("data", JString "Click Here"); ("hOffset", JNumber 250.0);
                    ("name", JString "text1");
                    ("onMouseUp",
                     JString "sun1.opacity = (sun1.opacity / 100) * 90;");
                    ("size", JNumber 36.0); ("style", JString "bold");
                    ("vOffset", JNumber 100.0)]));
             ("window",
              JObject
                (map
                   [("height", JNumber 500.0); ("name", JString "main_window");
                    ("title", JString "Sample Konfabulator Widget");
                    ("width", JNumber 500.0)]))]))])

JObject
  (map
     [("web-app",
       JObject
         (map
            [("servlet",
              JArray
                [JObject
                   (map
                      [("init-param",
                        JObject
                          (map
                             [("cachePackageTagsRefresh", JNumber 60.0);
                              ("cachePackageTagsStore", JNumber 200.0);
                              ("cachePackageTagsTrack", JNumber 200.0);
                              ("cachePagesDirtyRead", JNumber 10.0);
                              ("cachePagesRefresh", JNumber 10.0);
                              ("cachePagesStore", JNumber 100.0);
                              ("cachePagesTrack", JNumber 200.0);
                              ("cacheTemplatesRefresh", JNumber 15.0);
                              ("cacheTemplatesStore", JNumber 50.0); ...]));
                       ("servlet-class", JString "org.cofax.cds.CDSServlet");
                       ("servlet-name", JString "cofaxCDS")]);
                 JObject
                   (map
                      [("init-param",
                        JObject
                          (map
                             [("mailHost", JString "mail1");
                              ("mailHostOverride", JString "mail2")]));
                       ("servlet-class", JString "org.cofax.cds.EmailServlet");
                       ("servlet-name", JString "cofaxEmail")]);
                 JObject
                   (map
                      [("servlet-class", JString "org.cofax.cds.AdminServlet");
                       ("servlet-name", JString "cofaxAdmin")]);
                 JObject
                   (map
                      [("servlet-class", JString "org.cofax.cds.FileServlet");
                       ("servlet-name", JString "fileServlet")]);
                 JObject
                   (map
                      [("init-param",
                        JObject
                          (map
                             [("adminGroupID", JNumber 4.0);
                              ("betaServer", JBool true);
                              ("dataLog", JNumber 1.0);
                              ("dataLogLocation",
                               JString "/usr/local/tomcat/logs/dataLog.log");
                              ("dataLogMaxSize", JString "");
                              ("fileTransferFolder",
                               JString
                                 "/usr/local/tomcat/webapps/content/fileTransferFolder");
                              ("log", JNumber 1.0);
                              ("logLocation",
                               JString "/usr/local/tomcat/logs/CofaxTools.log");
                              ("logMaxSize", JString ""); ...]));
                       ("servlet-class",
                        JString "org.cofax.cms.CofaxToolsServlet");
                       ("servlet-name", JString "cofaxTools")])]);
             ("servlet-mapping",
              JObject
                (map
                   [("cofaxAdmin", JString "/admin/*");
                    ("cofaxCDS", JString "/");
                    ("cofaxEmail", JString "/cofaxutil/aemail/*");
                    ("cofaxTools", JString "/tools/*");
                    ("fileServlet", JString "/static/*")]));
             ("taglib",
              JObject
                (map
                   [("taglib-location", JString "/WEB-INF/tlds/cofax.tld");
                    ("taglib-uri", JString "cofax.tld")]))]))])

JObject
  (map
     [("menu",
       JObject
         (map
            [("header", JString "SVG Viewer");
             ("items",
              JArray
                [JObject (map [("id", JString "Open")]);
                 JObject
                   (map
                      [("id", JString "OpenNew"); ("label", JString "Open New")]);
                 JNull;
                 JObject
                 JObject
                   (map [("id", JString "ZoomIn"); ("label", JString "Zoom In")]);
                   (map
                      [("id", JString "ZoomOut"); ("label", JString "Zoom Out")]);
                 JObject
                   (map
                      [("id", JString "OriginalView");
                       ("label", JString "Original View")]); JNull;
                 JObject (map [("id", JString "Quality")]);
                 JObject (map [("id", JString "Pause")]);
                 JObject (map [("id", JString "Mute")]); JNull;
                 JObject
                   (map [("id", JString "Find"); ("label", JString "Find...")]);
                 JObject
                   (map
                      [("id", JString "FindAgain");
                       ("label", JString "Find Again")]);
                 JObject (map [("id", JString "Copy")]);
                 JObject
                   (map
                      [("id", JString "CopyAgain");
                       ("label", JString "Copy Again")]);
                 JObject
                   (map
                      [("id", JString "CopySVG"); ("label", JString "Copy SVG")]);
                 JObject
                   (map
                      [("id", JString "ViewSVG"); ("label", JString "View SVG")]);
                 JObject
                   (map
                      [("id", JString "ViewSource");
                       ("label", JString "View Source")]);
                 JObject
                   (map [("id", JString "SaveAs"); ("label", JString "Save As")]);
                 JNull; JObject (map [("id", JString "Help")]);
                 JObject
                   (map
                      [("id", JString "About");
                       ("label", JString "About Adobe CVG Viewer...")])])]))])
The above 5 outputs are the textual representation of the parse values encoded as in the JValue AST.
FYI. the computation time for each of the 5 examples is very fast; sub nanosecond range.
 
Last edited:
Building a Logo Turtle Graphics parser
To build an example of an end to end parser; I've chosen to tackle Logo's turtle graphics syntax because:
  • It's very simple syntax and hence building the parser will be easy to understand
  • Similarly the interpreter will be easy to understand
To avoid having to build separate code for Windows, Linux and macOS -- I've decided to use the Monogame's Framework (previously XNA) together with Google's cross platform Skia Graphics Engine.

In the coming days; we'll build a parser for the basic Logo turtle graphics syntax -- essentially text input to abstract syntax tree. Followed by an interpreter of the AST; that converts Logo AST into Skia Graphics draw commands, and renders that to a window.

Note:
I won't be building any "fancy" UI for this; it will be a simple command line logo file parser; that opens a window with the rendered result.
 
Last edited:
Creating a Monogame / Skia Graphics project blank
In Visual Studio create a .NET Core -- Console Application, and select F# a the language.
Type in TurtleDesktop for the Project Name, and Turtle for the Solution Name, and click Create.

Add the following Nugets to the TurtleDesktop project:
  • MonoGame.Framework.DesktopGL.Core (3.7.0.7)
  • MonoGame.Content.Builder (3.7.0.9) />
  • SkiaSharp (1.68.1.1)

Create a Monogame Content folder
Although we won't be using this; we for completeness will create a Content folder for Monogame and add a default content builder pipeline configuration.

Add a new text file to the Content folder and name it Content.mgcb -- replace the contents with the following default content builder configuration:
Code:
#----------------------------- Global Properties ----------------------------#

/outputDir:bin/$(Platform)
/intermediateDir:obj/$(Platform)
/platform:DesktopGL
/config:
/profile:Reach
/compress:False

#-------------------------------- References --------------------------------#


#---------------------------------- Content ---------------------------------#
Change the build action for the Content.mgcb to MonoGameContentReference -- this can also be done later by replacing the contents of TurtleDesktop.fsproj with the text I'll provide for reference at the end of this post.

Note:
Although this will not be required for our logo parser / interpreter; it is being included as a template default for the Monogame framework; because its required to add custom texture, sound and font assets. i.e. what you most likely need to build a UI for this.


Replace everything in Program.fs with this
C#:
[<EntryPoint>]
let main argv =
  use controller = new Controller()
  controller.Run()
  0 // return an integer exit code

Add a New File (F# Source File) to the TurtleDesktop named Controller.fs; drag to reorder this file so it appears above Program.fs in the solution explorer.

Note:
The order of Controller.fs is important because F#'s compiler parses code in a top down order; hence for Program.fs to be able to create a new instance of Controller it must have been parsed by the compiler before it get to Program.fs.


Add the following code to Controller.fs
C#:
namespace Endofunk
open Microsoft.Xna.Framework
open Microsoft.Xna.Framework.Graphics
open Microsoft.Xna.Framework.Input
open SkiaSharp
open System
open System.Runtime.InteropServices

type Controller () as this =
  inherit Game()

  let graphics = new GraphicsDeviceManager(this)
  let mutable spriteBatch = Unchecked.defaultof<SpriteBatch>
  let mutable backBuffer = Unchecked.defaultof<Texture2D>
  let mutable (w, h) = (0, 0)
  let mutable lastUpdate = Unchecked.defaultof<TimeSpan>
  let mutable surface = Unchecked.defaultof<SKSurface>
  let mutable canvas = Unchecked.defaultof<SKCanvas>
  let mutable p = Vector2(0.f, 0.f)

  do
    this.Content.RootDirectory <- "Content"
    this.IsMouseVisible <- true
    graphics.PreferredBackBufferWidth <- 800
    graphics.PreferredBackBufferHeight <- 600

  override this.Initialize() =
    base.Initialize()

  override this.LoadContent() =
    spriteBatch <- new SpriteBatch(this.GraphicsDevice)

    // TODO: use this.LoadContent to load your game content here
    h <- graphics.PreferredBackBufferHeight
    w <- graphics.PreferredBackBufferWidth
    let imageInfo = new SKImageInfo(w, h, SKImageInfo.PlatformColorType, SKAlphaType.Premul)
    backBuffer <- new Texture2D(graphics.GraphicsDevice, w, h)
    surface <- SKSurface.Create(imageInfo)
    canvas <- surface.Canvas

  override this.Update (gameTime) =
    if (GamePad.GetState(PlayerIndex.One).Buttons.Back = ButtonState.Pressed || Keyboard.GetState().IsKeyDown(Keys.Escape)) then this.Exit()

    if (gameTime.TotalGameTime - lastUpdate).TotalMilliseconds > 20. then
        lastUpdate <- gameTime.TotalGameTime

        canvas.DrawColor(SKColors.Aquamarine)
        let paint = new SKPaint()
        paint.TextSize <- 72.0f
        paint.IsAntialias <- true
        paint.IsStroke <- false
        let skia = "Skia Ready"
        let width = paint.MeasureText(skia) / 2.0f
        paint.Color <- SKColors.MediumAquamarine
        canvas.DrawText(skia, float32 (w / 2) - width, float32 (h / 2) + 72.0f / 2.0f, paint)
        let pixmap = surface.PeekPixels()
        let pixelptr = pixmap.GetPixels()
        let pixels : byte[] = Array.zeroCreate (h * pixmap.RowBytes)
        Marshal.Copy(pixelptr, pixels, 0, pixels.Length)
        backBuffer.SetData(pixels)

    base.Update(gameTime)

  override this.Draw (gameTime) =
    this.GraphicsDevice.Clear Color.Black

    // TODO: Add your drawing code here
    spriteBatch.Begin()
    spriteBatch.Draw(backBuffer, new Rectangle(0, 0, w, h), Color.White * 1.0f)
    spriteBatch.End()
    base.Draw(gameTime)


Change the Assembly Name
Change the Assembly name of TurtleDesktop to Turtle in project options, alternatively in TurtleDesktop.fsproj; which for reference should look like this:
Code:
<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>netcoreapp3.1</TargetFramework>
    <AssemblyName>Turtle</AssemblyName>
  </PropertyGroup>
  <ItemGroup>
    <MonoGameContentReference Include="Content\Content.mgcb" />
    <PackageReference Include="MonoGame.Framework.DesktopGL.Core" Version="3.7.0.7" />
    <PackageReference Include="MonoGame.Content.Builder" Version="3.7.0.9" />
    <PackageReference Include="SkiaSharp" Version="1.68.1.1" />
    <Compile Include="Controller.fs" />
    <Compile Include="Program.fs" />
  </ItemGroup>
</Project>


Run the project and you should see the following window:
773430

Note:
This should work without modification on Windows, macOS or Linux. Only exception is that on Linux you would have to use Visual Studio Code with the Ionide-fsharp plugin.
 
Last edited:
Create a Shared Project
In the event that we night want to also build a UI for Android, iOS, Playstation, etc. at a later stage, we'll create all of our shared code based in a shared project; this could also alternatively be split off to a Dynamic-link Library (DLL).

Add a New Project to the Turtle solution; name TurtleShared which is using the Multiplatform Library template called Shared Project with the language set to F#. In the event that you are unable to find that template I will share the complete text for TurtleShared.shproj and an an image of the complete solution's folder structure, so that you can be create this manually if needed.

Note:
MonoGame's framework supports most of the popular platforms namely: iOS, MacOS, Android, Linux, Windows Phone 8, Windows Desktop, Windows 10, PlayStation 4, PlayStation Vita, Xbox One, Nintendo Switch, tvOS


Add the Parser code to the TurtleShared project
Add a New File to the TurtleShared project named Parser.fs; add the following code to it:
 
Last edited:
C#:
namespace Endofunk
open System

type Offset = { X : int; Y : int }
module Offset =
  let initial = { X = 0; Y = 0 }
  let incX offset = { offset with X = offset.X + 1 }
  let incY offset = { X = 0; Y = offset.Y + 1 }

type ParserInput = { Offset : Offset; Lines : string[] }
module ParserInput =
  let create s =
    if String.IsNullOrEmpty(s) then { Lines = [||]; Offset = Offset.initial }
    else { Lines = s.Split([| "\r\n"; "\n" |], StringSplitOptions.None); Offset = Offset.initial }
  let current input = if input.Offset.Y < input.Lines.Length then input.Lines.[input.Offset.Y] else "EOF"
  let nextChar input =
    if input.Offset.Y >= input.Lines.Length then input, None
    else
      let line = current input
      if input.Offset.X < line.Length then { input with Offset = input.Offset |> Offset.incX }, Some line.[input.Offset.X]
      else { input with Offset = input.Offset |> Offset.incY }, Some '\n'

type ParserOffset = { Line : string; X : int; Y : int }
module ParserOffset =
  let fromInput input = { Line = ParserInput.current input; X = input.Offset.X; Y = input.Offset.Y }
     
type public ParserLabel = string
type public ParserError = string
type public ParserResult<'a> =
  | Success of 'a
  | Failed of ParserLabel * ParserError * ParserOffset

type public Parser<'a> = { Func : ParserInput -> ParserResult<'a * ParserInput>; Label : ParserLabel }
   
[<RequireQualifiedAccess>]
module Parser =
  /// Print a parsed result
  let public print result =
    match result with
    | Success(value, input) -> printfn "%A" value
    | Failed(label, error, offset) ->
      printfn "Error parsing %s at line %i column %i\n%s\n%s" label offset.Y offset.X offset.Line (sprintf "%*s^%s" offset.X "" error)

  /// Run a parser with some input
  let public runInput p input = p.Func input
  /// Run the parser with a string as input
  let public run p str = runInput p (ParserInput.create str)

  /// Update the label in the parser
  let setLabel p label =
    let f input =
      match p.Func input with
      | Success s -> Success s
      | Failed(oldLabel, err, offset) -> Failed(label, err, offset)
    { Func = f; Label = label }
  /// Infix version of setLabel
  let private (<?>) = setLabel

  /// Monad conformance
  let public flatmap f p =
    let label = "Undefined"
    let f input =
      match runInput p input with
      | Failed(label, err, offset) -> Failed(label, err, offset)
      | Success(head, tail) -> runInput (f head) tail
    { Func = f; Label = label }
  /// Alternative function for flatmap
  let public bind = flatmap
  /// Infix of flatmap
  let private (>>=) p f = flatmap f p
  /// Lift a value into a Parser
  let public rtn x =
    let label = sprintf "%A" x
    let f input = Success(x, input)
    { Func = f; Label = label }

  /// Functor conformance
  let public map f = flatmap (f >> rtn)
  /// Infix of map
  let private (<!>) = map
  /// Infix Reverse of map (piping)
  let private (<&>) x f = map f x
  /// ALternative Infix Reverse of map (piping)
  let private (|>>) = (<&>)

  /// Applicative Functor conformance
  let public apply fP xP = fP >>= fun f -> xP >>= fun x -> rtn (f x)
  /// Infix of apply
  let private (<*>) = apply
  /// Lift a single parameter function into the Parser world and apply
  let public liftA fn aP = rtn fn <*> aP
  /// Lift a two parameter function into the Parser world and apply
  let public liftA2 fn aP bP = liftA fn aP <*> bP
  /// Lift a three parameter function into the Parser world and apply
  let public liftA3 fn aP bP cP = liftA2 fn aP bP <*> cP
  /// Lift a four parameter function into the Parser world and apply
  let public liftA4 fn aP bP cP dP = liftA3 fn aP bP cP <*> dP
  /// Lift a five parameter function into the Parser world and apply
  let public liftA5 fn aP bP cP dP eP = liftA4 fn aP bP cP dP <*> eP
  /// Lift a six parameter function into the Parser world and apply
  let public liftA6 fn aP bP cP dP eP fP = liftA5 fn aP bP cP dP eP <*> fP

  /// Combine two parsers (logical conjunction)
  let public andThen p1 p2 =
    let label = sprintf "%s andThen %s" p1.Label p2.Label
    p1 >>= fun r1 -> p2 >>= fun r2 -> rtn (r1, r2) <?> label
  /// Infix of andThen
  let private (.>>.) = andThen
  /// Keep only the result of the left side parser
  let andThenFst p1 p2 = p1 .>>. p2 |> map (fun (a, b) -> a)
  /// Infix of andThenFst
  let private (.>>) = andThenFst
  /// Keep only the result of the right side parser
  let andThenSnd p1 p2 = p1 .>>. p2 |> map (fun (a, b) -> b)
  /// Infix of andThenSnd
  let private (>>.) = andThenSnd
  /// Keep only the result of the middle parser
  let public between p1 p3 p2 = p1 >>. p2 .>> p3

  /// Combine two parsers (logical disjunction)
  let public orElse p1 p2 =
    let label = sprintf "%s orElse %s" p1.Label p2.Label
    let f input =
      let r1 = runInput p1 input
      match r1 with
      | Success _ -> r1
      | Failed _ -> runInput p2 input
    { Func = f; Label = label }
  /// Infix of orElse
  let private (<|>) = orElse
  /// Choose from a list of Parsers
  let public choice pss = List.reduce (<|>) pss

  /// Higher Order Parser
  let public satisfy pred label =
    let f input =
      match ParserInput.nextChar input with
      | _, None -> Failed(label, "End of Input", ParserOffset.fromInput input)
      | tail, Some head ->
        if pred head then Success(head, tail)
        else Failed(label, sprintf "Unexpected '%c'" head, ParserOffset.fromInput input)
    { Func = f; Label = label}
   
  let rec public sequence ps =
    let cons head tail = head :: tail
    let consP = liftA2 cons
    match ps with
    | [] -> rtn []
    | head :: tail -> consP head (sequence tail)

  /// Match zero or more occurrences of the specified parser
  let rec private zeroOrMore p input =
    match runInput p input with
    | Failed(_, _, _) -> [], input
    | Success(head, tail) ->
      let (nextHeads, remainingTail) = zeroOrMore p tail
      (head :: nextHeads, remainingTail)

  /// Matches zero or more occurrences of the specified parser
  let public many p =
    let label = sprintf "many %s" p.Label
    let rec f input = Success(zeroOrMore p input)
    { Func = f; Label = label }
  /// Matches one or more occurrences of the specified parser
  let public many1 p =
    let label = sprintf "many1 %s" p.Label
    p >>= fun head -> many p >>= fun tail -> rtn (head :: tail) <?> label

  /// Parses an optional occurrence of p and returns an option value.
  let public opt p =
    let label = sprintf "opt %s" p.Label
    p <&> Some <|> rtn None <?> label

  let optToString opt f =
    match opt with
    | None -> ""
    | Some x -> f x

  /// Parses one or more occurrences of p separated by sep
  let public sepBy1 p sep =
    let sepThenP = sep >>. p
    p .>>. many sepThenP <&> fun (p, pList) -> p :: pList
    <?> "sepBy1"
  /// Parses zero or more occurrences of p separated by sep
  let public sepBy p sep = sepBy1 p sep <|> rtn [] <?> "sepBy"

  /// Parse a char
  let public pchar c =
    let pred ch = (ch = c)
    let label = sprintf "%c" c
    satisfy pred label

  /// Choose from a list of characters
  let public anyOf cs =
    let label = sprintf "anyOf %A" cs
    cs
    |> List.map pchar
    |> choice
    <?> label

  /// Convert char list to string
  let private charListToString cs = String(List.toArray cs)

  /// Parses a sequence of zero or more chars
  let manyChars p = many p <&> charListToString <?> "manyChars"
  /// Parses a sequence of one or more chars
  let many1Chars p = many1 p <&> charListToString <?> "many1Chars"
  let manyChars1 = many1Chars

  /// Parse a specific string
  let public pstring s =
    s
    |> List.ofSeq
    |> List.map pchar
    |> sequence
    |> map charListToString
    <?> s

  /// Parse a whitespace char
  let ws = satisfy Char.IsWhiteSpace "Whitespace"
  /// Parse zero or more whitespace char
  let spaces = many ws
  /// Parse one or more whitespace char
  let spaces1 = many1 ws

  /// Create a forward reference
  let public createParserForwardedToRef<'a>() =
    let dummyParser=
      let f input : ParserResult<'a * ParserInput> = failwith "unfixed forwarded parser"
      { Func = f; Label = "undefined" }
    // ref to placeholder Parser
    let parserRef = ref dummyParser
    // wrapper Parser
    let f input = runInput !parserRef input // forward input to the placeholder
    let wrapperParser = { Func = f; Label = "undefined" }
    wrapperParser, parserRef

  /// parse a digit
  let public digitChar = satisfy Char.IsDigit  "Digit"
  // define parser for one or more digits
  let public digits = manyChars1 digitChar

  // Parse an integer
  let public pint =
    let convert (sign, digits) =
      let n = digits |> int
      match sign with
      | Some _ -> -n
      | None -> n
    opt (pchar '-') .>>. digits |> map convert <?> "Integer"

  // Parse a float
  let public pfloat =
    let convert (((sign, digits1), point), digits2) =
      let n = sprintf "%s.%s" digits1 digits2 |> float
      match sign with
      | Some _ -> -n
      | None -> n
    opt (pchar '-') .>>. digits .>>. pchar '.' .>>. digits |> map convert <?> "Float"

[<AutoOpen>]
module Operators =
  /// Infix version of setLabel
  let (<?>) = Parser.setLabel
  /// Infix of flatmap
  let (>>=) p f = Parser.flatmap f p
  /// Reverse Infix of flatmap
  let (=<<) = Parser.flatmap
  /// Infix of map
  let (<!>) = Parser.map
  /// Reverse Infix of map (piping)
  let (<&>) x f = Parser.map f x
  // Alternative Reverse Infix of <&>
  let (|>>) = (<&>)
  /// Infix of andThen
  let (.>>.) = Parser.andThen
  /// Keep only the result of the left side parser
  let (.>>) = Parser.andThenFst
  /// Keep only the result of the right side parser
  let (>>.) = Parser.andThenSnd
  /// Infix of orElse
  let (<|>) = Parser.orElse
  /// Applies parser p ignores the result and return x
  let (>>%) p x = p <&> fun _ -> x
  // Infix Option to string
  let (|>?) = Parser.optToString
 
Add a file for Logo
Add a New File to the TurtleShared project named Logo.fs, and add the following minimal placeholder code to it:
C#:
namespace Endofunk

module Logo =
  let todo = "a lot"

Recap
The Turtle Solution folder should like this:
773434

For clarity the TurtleShared.shproj should look like this:
Code:
<Project ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
  <PropertyGroup>
    <ProjectGuid>{9F79CB66-5103-413A-9E9E-2185849C7DA4}</ProjectGuid>
  </PropertyGroup>
  <Import Project="$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props" Condition="Exists('$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props')" />
  <Import Project="$(MSBuildExtensionsPath32)\Microsoft\VisualStudio\v$(VisualStudioVersion)\CodeSharing\Microsoft.CodeSharing.Common.Default.props" />
  <Import Project="$(MSBuildExtensionsPath32)\Microsoft\VisualStudio\v$(VisualStudioVersion)\CodeSharing\Microsoft.CodeSharing.Common.props" />
  <Import Project="TurtleShared.projitems" Label="Shared" />
  <Import Project="$(MSBuildExtensionsPath32)\Microsoft\VisualStudio\v$(VisualStudioVersion)\CodeSharing\Microsoft.CodeSharing.FSharp.targets" />
  <ProjectExtensions>
    <MonoDevelop>
      <Properties>
        <Policies>
          <TextStylePolicy RemoveTrailingWhitespace="True" NoTabsAfterNonTabs="False" EolMarker="Native" FileWidth="80" TabWidth="2" TabsToSpaces="True" IndentWidth="2" scope="text/plain" />
        </Policies>
      </Properties>
    </MonoDevelop>
  </ProjectExtensions>
</Project>

The TurtleShared.projitems should look like this:
Code:
<?xml version="1.0" encoding="utf-8"?>
<Project xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
  <PropertyGroup>
    <MSBuildAllProjects>$(MSBuildAllProjects);$(MSBuildThisFileFullPath)</MSBuildAllProjects>
    <HasSharedItems>true</HasSharedItems>
    <SharedGUID>{9F79CB66-5103-413A-9E9E-2185849C7DA4}</SharedGUID>
  </PropertyGroup>
  <PropertyGroup Label="Configuration">
    <Import_RootNamespace>TetrisShared</Import_RootNamespace>
  </PropertyGroup>
  <ItemGroup>
    <Compile Include="$(MSBuildThisFileDirectory)Parser.fs" />
    <Compile Include="$(MSBuildThisFileDirectory)Logo.fs" />
  </ItemGroup>
</Project>

The TurtleDesktop.fsproj should look like this:
Code:
<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>netcoreapp3.1</TargetFramework>
    <AssemblyName>Turtle</AssemblyName>
  </PropertyGroup>
  <Import Project="..\TurtleShared\TurtleShared.projitems" Label="Shared" Condition="Exists('..\TurtleShared\TurtleShared.projitems')" />
  <ItemGroup>
    <MonoGameContentReference Include="Content\Content.mgcb" />
    <PackageReference Include="MonoGame.Framework.DesktopGL.Core" Version="3.7.0.7" />
    <PackageReference Include="MonoGame.Content.Builder" Version="3.7.0.9" />
    <PackageReference Include="SkiaSharp" Version="1.68.1.1" />
    <Compile Include="Controller.fs" />
    <Compile Include="Program.fs" />
  </ItemGroup>
</Project>

Note:
The order of entries in the TurtleDesktop.fsproj is important because of the top/down parsing of the F# compiler.


In the next post
In the next post we'll start building the Parser for the Logo Turtle Graphics language, covering initially the following set of commands:
  • forward or fd -- the # of pixels to draw forward in a straight line; in the direction the "turtle" is facing
  • backward or bk -- the # of pixels to draw backwards in a straight line; in the direction that the "turtle" is facing
  • left or lt -- the # of degrees to rotate counter clockwise.
  • right or rt -- the # of degrees to rotate clockwise.
  • repeat -- repeat a block of instructions a # of times


The goal will be to parse logo code similar to follow:
Code:
repeat 8 [repeat 4 [fd 100 rt 90] rt 45]
Which once interpreted should render the following:
773438
 
Last edited:
AST for Logo
The ideal structure to represent a language parser is an abstract syntax tree; a disjunction between different syntax but also to record values associated with that disjunction. In F# the best choice for this is a Discriminated Union type.
C#:
// Type aliases to improve readability
type Distance = int
type Degree = int
type Quantity = int

type Command =
  | Walk of Distance
  | Turn of Degree
  | Repeat of Quantity * Command list


Turtle State
To keep track of the turtle we need a record type that stores the position and heading of the turtle..
C#:
type Turtle = { X: float; Y: float; Angle: Degree }


Parser for Logo Turtle Graphics Syntax
Let's build a set of parser combinators to parse the logo syntax to the above AST; fo now we'll limit the commands to forward, backward, left, right and repeat.
Reference: https://www.tutorialspoint.com/logo/logo_turtle.htm


Parser for Forward and Backward
The forward or fd and backward or bk keywords both have an associated numerical value that indicated the distance (in pixels) for the turtle to travel.

C#:
module Logo =
  let private pforward = (Parser.pstring "forward" <|> Parser.pstring "fd") >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces |>> fun n -> Walk
  let private pbackward = (Parser.pstring "backward" <|> Parser.pstring "bk") >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces |>> fun n -> Walk(-n)
In the above pforward parser we're searching for either forward or fd followed by 1 or more spaces, which we use to find an integer followed by zero or more spaces. The operators specify that whilst we need the other search combinators; we only want to retain the integer value; which we map <&> to a Walk encapsulating the integer distance in pixels from our current offset.
The pbackward parser is the same as pforward except that for pbackward we encapsulate a negative n with Walk.


Parser for Left and Right
The left or lt and right or rt keywords also have an associated numerical value which indicates how many degrees we want to rotate our turtle; left is a positive value, whilst right is a negative value.

C#:
module Logo =
  ...
  let private pleft = (Parser.pstring "left" <|> Parser.pstring "lt") >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> Turn
  let private pright = (Parser.pstring "right" <|> Parser.pstring "rt") >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> fun n -> Turn(-n)
In the above pleft parser we're searching for either left or lt followed by 1 or more spaces, which we use to find an integer followed by zero or more spaces. The operators specify that whilst we need the other search combinators; we only want to retain the integer value; which we map <&> to a Turn encapsulating the integer degree rotation from our current offset.
The pright parser is the same as pleft except that for pright we encapsulate a negative n with Turn.


Parser for Repeat
The repeat keyword also has an associated numerical value which indicates how many time we want to repeat the code encapsulated in a set of square brackets "repeat 2 [ ... ]".

The repeat keyword can not only repeat commands like forward or left, but can also repeat another repeat block.

The word block is important because that can comprise of a choice of 1 or more command parsers including repeat. This gets us into a another chicken or egg scenario again where we want a block between square brackets to be a choice of command parsers including repeat; but we haven't defined repeat yet because it needs us to first define the commands parser.

So to fix this we have to create a forward referencing parser for repeat; which has a default stand in dummy parser until we've define the block parser that'll replace it.

C#:
module Logo =
  ...
  let private prepeat, private prepeatRef = Parser.createParserForwardedToRef()
  let private pcommands = Parser.choice [pforward; pbackward; pleft; pright; prepeat]
  let private pblock = Parser.between (Parser.pstring "[") (Parser.pstring "]") (Parser.many1 (pcommands .>> Parser.spaces))
  prepeatRef := Parser.pstring "repeat" >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces .>>. pblock <&> fun (n, cmds) -> Repeat(n, cmds)
In the above code we've define the prepeat parser as a forward reference parser; which has a reference pointer that we can update at a later stage; after we've created the pcommands parser.

Now we can define a parser called pcommands which is a choice between all our parsers including repeat. Next we define the pblock parser; which specifies a 1 or many occurrences of pcommands parsers encapsulated within a set of square braces, surrounded by spaces.

Finally we update the prepeatRef to a parser with the keyword "repeat"; that retains the integer number of repetitions and the block of commands -- which is then mapped <&> to Repeat union that encapsulates both the number of repetitions and the block of pcommands.


Logo Parsing Helper function
Finally we need a function to simplify the running of our parser and to return only the AST.
C#:
module Logo =
...
  let public parse code =
    match Parser.run (Parser.many pcommands) code with
    | Success(result, _) -> result
    | Failed(message, _, _) -> failwith message
The parse helper function takes in the code as a string; and then runs a parser that will match many; zero or more pcommands parsers.


Let's test it
C#:
let code = "repeat 16 [repeat 8 [fd 100 rt 45] rt 22]"
let result = Logo.parse code
printfn "%A" result


The output from this is...
Code:
[Repeat (16,[Repeat (8,[Walk 100; Turn -45]); Turn -22])]
As you can see our code has been parsed into the Commands AST; with the fd captured as Walk, and the rt captured as a Turn with a negative degree value, etc...



Recap
To recap our full parser code should looks like this.
C#:
// Type aliases to improve readability
type Distance = int
type Degree = int
type Quantity = int

type Command =
  | Walk of Distance
  | Turn of Degree
  | Repeat of Quantity * Command list

type Turtle = { X: float; Y: float; Angle: Degree }

module Logo =
  let private pforward = (Parser.pstring "forward" <|> Parser.pstring "fd") >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> Walk
  let private pbackward = (Parser.pstring "backward" <|> Parser.pstring "bk") >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> fun n -> Walk(-n)
  let private pleft = (Parser.pstring "left" <|> Parser.pstring "lt") >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> Turn
  let private pright = (Parser.pstring "right" <|> Parser.pstring "rt") >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> fun n -> Turn(-n)
  let private prepeat, private prepeatRef = Parser.createParserForwardedToRef()
  let private pcommands = Parser.choice [pforward; pbackward; pleft; pright; prepeat]
  let private pblock = Parser.between (Parser.pstring "[") (Parser.pstring "]") (Parser.many1 (pcommands .>> Parser.spaces))
  prepeatRef := Parser.pstring "repeat" >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces .>>. pblock <&> fun (n, cmds) -> Repeat(n, cmds)

  let public parse code =
    match Parser.run (Parser.many pcommands) code with
    | Success(result, _) -> result
    | Failed(message, _, _) -> failwith message



In the next post
In the next post we'll build an interpreter for that AST; that will take our commands and converted them into graphics draw calls to render the result of our turtle graphics syntax.
 
Last edited:
Writing an Logo AST Interpreter
The interpreter will take an AST and translate that into something else; which in this case will be to render the result of the Logo code that we parsed.

A bit of background
Traditionally the turtle starts by default at the centre of the window; these X / Y values will be used to initialise the turtle's record; for the Angle; the tradition is for the turtle to be pointing upwards i.e. a 90 degree rotation to the left.


Creating an Execute function
The execute function takes in four parameters; an AST of Commands; a width / height of the window and the GraphicsDevice we'll use to render a MonoGame texture; the result of the execute function.

The translation of the left and right angle adjustments is easy; we simply need to create a new turtle record where we have added the Turn parameter value to the turtle's Angle property.
C#:
let execute cmds w h g =
...
    let rec perform turtle = function
...
      | Turn n -> { turtle with Angle = turtle.Angle + n }
...


The translation of the forward and backward commands, requires us to compute the offset from our current X / Y based on the Angle our turtle is facing. What we know is the origin X / Y, the distance to Walk and the Angle the turtle is heading.

Circle equations
The destination X / Y points for our drawLine can be calculated using the parametric form of the circle equation; an equation that requires: an Angle, a X / Y starting point and a Distance we will Walk.

774106

The 'x and y' are the two coordinates that we need to compute; this can be done using the parametric circle formulas:
774110
Distance is the r; the radius, Theta is the Angle in radians, and x and y is the X and Y property values in turtle.

These formulas are translated into the following helper function; to which we pass the turtle parameter and the distance to travel. The turtle record has the current X / Y coordinates and the Angle the turtle is facing.
C#:
let calcTargetCoord turtle distance =
    let rad = Math.PI * float turtle.Angle / 180.0
    (turtle.X, turtle.Y, turtle.X + float distance * Math.Cos rad, turtle.Y + float distance * Math.Sin rad)
First we convert the Angle in degrees to radians; next we compute a tuple result representing the x' and y' result values (x and y primes values) that will be used as the target point for the drawLine.

Translation of Walk in the AST.
C#:
let execute cmds w h g =
    let texture = new Texture2D(g, w, h)
    let imageInfo = SKImageInfo(w, h, SKImageInfo.PlatformColorType, SKAlphaType.Premul)
    let surface = SKSurface.Create(imageInfo)
    let canvas = surface.Canvas
    let turtle = { X = float w / 2.0; Y = float h / 2.0; Angle = -90; PenDown = true }
    let pen = new SKPaint()
    pen.Color <- SKColors.AntiqueWhite
    pen.IsAntialias <- true
    let rec perform turtle = function
      | Walk n ->
        let x, y, x', y' = calcTargetCoord turtle n
        canvas.DrawLine(float32 x, float32 y, float32 x', float32 y', pen)
        { turtle with X = x'; Y = y' }
      | Turn n -> { turtle with Angle = turtle.Angle + n }
...
In the above code; we create a MonoGame Texture2D that is the same width (w) and height (h) of the Window; we define a Skia canvas of the same size; define the default location of the turtle and its default angle; then create a default pen. In the Walk match we compute the x' / y' primes and then draw the line; finally updating the position of the turtle i.e. at the end of the.line; the prime x' and y'.


In the Next Post
In the next post we'll define what happens for repeat and we recurse over the input AST; render our Skia canvas to the Texture2D result and finally adjust the Monogame controller to render the Textured2D.
 
Last edited:
Building the Texture2D
I haven't described up till this point why we need to build a Textured2D; assuming that the reader knows how Microsoft's XNA; now called MonoGame works. MonoGame is a very basic game engine that uses only textures (images) -- what this means is that unlike Microsoft.Windows.Forms; there is no way to draw 2D lines or any other vector based graphics directly to the UI.

The only way to get Google's Skia graphics framework to integrate with MonoGame is to generate the vector graphics draw calls on a Skia canvas and then convert that canvas to a Texture2D; a compatible format that MonoGame can render. The way we achieve this is as follows:
  • Create a Skia canvas of the same size as the MonoGame window -- a canvas is a vector 2D drawing surface
  • Draw lines on the canvas
  • Create a Texture2D with the same size as the Skia canvas.
  • Retrieve the memory pointer address of the pixels on the Skia canvas.
  • Create a byte array with a size big enough to contain all the pixels on the Skia canvas.
  • Marshal.Copy all the data from the Skia canvas pixel memory to the byte array.
  • Set the memory pointer of the Textured2D to the address of the byte array.
The above process will in an interactive UI be repeated each time Skia's canvas is changed -- to ensure that the Texture2D rendered by MonoGame accurately duplicates Skia's canvas.



Interpreting the Repeat command
C#:
  let execute cmds w h g =
    let texture = new Texture2D(g, w, h)
    let imageInfo = SKImageInfo(w, h, SKImageInfo.PlatformColorType, SKAlphaType.Premul)
    let surface = SKSurface.Create(imageInfo)
    let canvas = surface.Canvas
    let turtle = { X = float w / 2.0; Y = float h / 2.0; Angle = -90; PenDown = true }
    let pen = new SKPaint()
    pen.Color <- SKColors.AntiqueWhite
    pen.IsAntialias <- true
    let rec perform turtle = function
      | Walk n ->
        let x, y, x', y' = calcTargetCoord turtle n
        canvas.DrawLine(float32 x, float32 y, float32 x', float32 y', pen)
        { turtle with X = x'; Y = y' }
      | Turn n -> { turtle with Angle = turtle.Angle + n }
      | Repeat (n, cmds) ->
        let rec repeat turtle = function
          | 0 -> turtle
          | n -> repeat (performAll turtle cmds) (n - 1)
        repeat turtle n
    and performAll = List.fold perform
    performAll turtle cmds |> ignore
Adding to the Interpreter; we match against a Result that has two associated values; a Quantity and a list<Command>. For a repeat Quantity of zero; we simply return the turtle record structure unchanged. For a Quantity greater than zero we recursively call the repeat function to process the encapsulated list<Command> decrementing the Quantity until it reaches zero and exits.

The performAll function that is called in the Repeat matches recursion is a monoidal reducing operation like "Sum all integer in a list" i.e. List.Fold; except that here we are reducing over perform interpreter function, a function with the following reducer signature: Turtle -> Command -> Turtle i.e. changing the turtle's record state to reflect the result of reducing with a Command.

To start the reduction process of the parsed commands we simply call the performAll reducing function and provide the Turtle record and the parsed list<Command>.

The remainder of the we need to add is the code to quickly copy the pixels from the Skia canvas to the Texture2D required by MonoGame.
C#:
let execute cmds w h g =
    let texture = new Texture2D(g, w, h)
    let imageInfo = SKImageInfo(w, h, SKImageInfo.PlatformColorType, SKAlphaType.Premul)
    let surface = SKSurface.Create(imageInfo)
    let canvas = surface.Canvas
    let turtle = { X = float w / 2.0; Y = float h / 2.0; Angle = -90; PenDown = true }
    let pen = new SKPaint()
    pen.Color <- SKColors.AntiqueWhite
    pen.IsAntialias <- true
    let rec perform turtle = function
      | Walk n ->
        let x, y, x', y' = calcTargetCoord turtle n
        canvas.DrawLine(float32 x, float32 y, float32 x', float32 y', pen)
        { turtle with X = x'; Y = y' }
      | Turn n -> { turtle with Angle = turtle.Angle + n }
      | Repeat (n, cmds) ->
        let rec repeat turtle = function
          | 0 -> turtle
          | n -> repeat (performAll turtle cmds) (n - 1)
        repeat turtle n
    and performAll = List.fold perform
    performAll turtle cmds |> ignore
    let pixelMap = surface.PeekPixels()
    let pixelAddr = pixelMap.GetPixels()
    let pixels : byte[] = Array.zeroCreate (h * pixelMap.RowBytes)
    Marshal.Copy(pixelAddr, pixels, 0, pixels.Length)
    texture.SetData(pixels)
    texture
The final step of the execute function is to return the texture (a MonoGame Texture2D) that has a copy of the Skia canvas's pixels. This resulting Textured2D can then be rendered in the MonoGame's game loop.



Changing MonoGame Controller to test the interpreter
For expediency I'm going to share a complete listing of the code for the Controller.fs to both parse a test Logo program and to interpret it; generating a Texture2D and finally rendering it to the MonoGame display.

Note:
I have removed all the previous Skia / Monogame template test code.

C#:
namespace Endofunk
open Microsoft.Xna.Framework
open Microsoft.Xna.Framework.Graphics
open Microsoft.Xna.Framework.Input
type Controller () as this =
  inherit Game()
  let graphics = new GraphicsDeviceManager(this)
  let mutable spriteBatch = Unchecked.defaultof<SpriteBatch>
  let mutable backBuffer = Unchecked.defaultof<Texture2D>
  let mutable (w, h) = (0, 0)
  do
    this.Content.RootDirectory <- "Content"
    this.IsMouseVisible <- true
    graphics.PreferredBackBufferWidth <- 800
    graphics.PreferredBackBufferHeight <- 800
  override this.Initialize() =
    base.Initialize()
  override this.LoadContent() =
    spriteBatch <- new SpriteBatch(this.GraphicsDevice)
    // TODO: use this.LoadContent to load your game content here
    h <- graphics.PreferredBackBufferHeight
    w <- graphics.PreferredBackBufferWidth
    let code = "repeat 16 [repeat 8 [fd 100 rt 45] rt 22]"
    let cmds = Logo.parse code
    backBuffer <- LogoInterpreter.execute cmds h w graphics.GraphicsDevice

  override this.Update (gameTime) =
    if (GamePad.GetState(PlayerIndex.One).Buttons.Back = ButtonState.Pressed || Keyboard.GetState().IsKeyDown(Keys.Escape)) then this.Exit()
    base.Update(gameTime)
  override this.Draw (gameTime) =
    this.GraphicsDevice.Clear Color.Black
    // TODO: Add your drawing code here
    spriteBatch.Begin()
    spriteBatch.Draw(backBuffer, Rectangle(0, 0, w, h), Color.White * 1.0f)
    spriteBatch.End()
    base.Draw(gameTime)



Run the Application
We ready to run the application and let our parser and interpreter render the result of the following logo code:
C#:
repeat 16 [repeat 8 [fd 100 rt 45] rt 22]

774390
 
Last edited:
Extending our Logo Parser's syntax
All we have to convert our application into a workable Logo command line parser / renderer is to provide support for a command line filepath parameter to point to a custom Logo program file.... however before we do that; let's look at first extending our parser to support some more Logo syntax.

The syntax we'll focus on adding will include:
  • setpensize -- change the pixel width of Skia's pen.
  • setx -- change the X coordinate
  • sety -- change the Y coordinate
  • setxy -- change the X and Y coordinates
  • seth -- change the Angle of the turtle
  • penup -- lift up the drawing pen i.e. do not draw to the canvas
  • pendown -- put down drawing pen i.e. draw to the canvas
C#:
module Logo =
let private pforward = (Parser.pstring "forward" <|> Parser.pstring "fd") >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> Walk
  let private pbackward = (Parser.pstring "backward" <|> Parser.pstring "bk") >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> fun n -> Walk(-n)
  let private pleft = (Parser.pstring "left" <|> Parser.pstring "lt") >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> Turn
  let private pright = (Parser.pstring "right" <|> Parser.pstring "rt") >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> fun n -> Turn(-n)
  let private psetpensize = Parser.pstring "setpensize" >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> fun n -> PenSize(n)
  let private psetx = Parser.pstring "setx" >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> fun n -> SetX(n)
  let private psety = Parser.pstring "sety" >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> fun n -> SetY(n)
  let private psetxy = Parser.pstring "setxy" >>. Parser.spaces1 >>. Parser.pint .>>. Parser.spaces .>>. Parser.pint .>> Parser.spaces <&> fun ((x, a), y) -> SetXY(x, y)
  let private pseth = (Parser.pstring "setheading" <|> Parser.pstring "seth") >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> fun n -> SetH(n)
  let private ppenup = (Parser.pstring "penup" <|> Parser.pstring "pu") .>> Parser.spaces <&> fun _ -> PenDown(false)
  let private ppendown = (Parser.pstring "pendown" <|> Parser.pstring "pd") .>> Parser.spaces <&> fun _ -> PenDown(true)
  let private prepeat, private prepeatRef = Parser.createParserForwardedToRef()
  let private pcommands = Parser.choice [pforward; pbackward; pleft; pright; psetpensize; psetx; psety; psetxy; pseth; ppenup; ppendown; prepeat]
  let private pblock = Parser.between (Parser.pstring "[") (Parser.pstring "]") (Parser.many1 (pcommands .>> Parser.spaces))
  prepeatRef := Parser.pstring "repeat" >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces .>>. pblock <&> fun (n, cmds) -> Repeat(n, cmds)
If you have follow along and understood the code up till now; then the definition of these parsers should be easy enough to understand... note that we have added the new parsers (psetpensize; psetx; psety; psetxy; pseth; ppenup; ppendown) to the pcommands parsers.

Let's add support for these commands to the Interpreter
C#:
let execute cmds w h g =
    let texture = new Texture2D(g, w, h)
    let imageInfo = SKImageInfo(w, h, SKImageInfo.PlatformColorType, SKAlphaType.Premul)
    let surface = SKSurface.Create(imageInfo)
    let canvas = surface.Canvas
    let turtle = { X = float w / 2.0; Y = float h / 2.0; Angle = -90; PenDown = true }
    let pen = new SKPaint()
    pen.Color <- SKColors.AntiqueWhite
    pen.IsAntialias <- true
    let rec perform turtle = function
      | Walk n ->
        let x, y, x', y' = calcTargetCoord turtle n
        if turtle.PenDown then canvas.DrawLine(float32 x, float32 y, float32 x', float32 y', pen)
        { turtle with X = x'; Y = y' }
      | Turn n -> { turtle with Angle = turtle.Angle + n }
      | PenSize n ->
        pen.StrokeWidth <- float32 n
        turtle
      | SetX x -> { turtle with X = float w / 2.0 + float x }
      | SetY y -> { turtle with Y = float h / 2.0 + float y }
      | SetXY (x, y) -> { turtle with X = float w / 2.0 + float x; Y = float h / 2.0 + float y }
      | SetH n -> { turtle with Angle = n }
      | PenDown x -> { turtle with PenDown = x }  
      | Repeat (n, cmds) ->
        let rec repeat turtle = function
          | 0 -> turtle
          | n -> repeat (performAll turtle cmds) (n - 1)
        repeat turtle n
    and performAll = List.fold perform
    performAll turtle cmds |> ignore
    let pixelMap = surface.PeekPixels()
    let pixelAddr = pixelMap.GetPixels()
    let pixels : byte[] = Array.zeroCreate (h * pixelMap.RowBytes)
    Marshal.Copy(pixelAddr, pixels, 0, pixels.Length)
    texture.SetData(pixels)
    texture
Again the above code should not be too difficult to understand; we match against the Command type; retrieve the associated value(s) and effect changes to the turtle. The only commands that are a bit different is the setpensize action; which is affecting the Skia pen we use for drawing i.e. we set its StrokeWidth to match the pen size specified in the code. The other two commands that are different are penup and pendown; which require us to track the state of the pen; to support this we have modified the Turtle record to add a boolean property called PenDown.

C#:
type Turtle = { X: float; Y: float; Angle: Degree; PenDown: bool }

// similarly we have change the initial state of the turtle to include this
let turtle = { X = float w / 2.0; Y = float h / 2.0; Angle = -90; PenDown = true }

The only change we needed to make to support the penup and pendown syntax is on the Walk action; i.e. we need only draw when the pen is down; and only adjust the X / Y properties when it is up.

C#:
...
Walk n ->
        let x, y, x', y' = calcTargetCoord turtle n
        if turtle.PenDown then canvas.DrawLine(float32 x, float32 y, float32 x', float32 y', pen)
        { turtle with X = x'; Y = y' }
...


Let's test some of our new Syntax
Here is a full extract of the Controller.fs code including a new Logo code string with some of the new syntax:
C#:
namespace Endofunk
open Microsoft.Xna.Framework
open Microsoft.Xna.Framework.Graphics
open Microsoft.Xna.Framework.Input
type Controller () as this =
  inherit Game()
  let graphics = new GraphicsDeviceManager(this)
  let mutable spriteBatch = Unchecked.defaultof<SpriteBatch>
  let mutable backBuffer = Unchecked.defaultof<Texture2D>
  let mutable (w, h) = (0, 0)
  do
    this.Content.RootDirectory <- "Content"
    this.IsMouseVisible <- true
    graphics.PreferredBackBufferWidth <- 800
    graphics.PreferredBackBufferHeight <- 800
  override this.Initialize() =
    base.Initialize()
  override this.LoadContent() =
    spriteBatch <- new SpriteBatch(this.GraphicsDevice)
    // TODO: use this.LoadContent to load your game content here
    h <- graphics.PreferredBackBufferHeight
    w <- graphics.PreferredBackBufferWidth
    let code = "setxy 200 0 setpensize 4 repeat 12 [repeat 5 [pd fd 120 rt 144] setpensize 2 pu fd 120 rt 30]"
    let cmds = Logo.parse code
    backBuffer <- LogoInterpreter.execute cmds h w graphics.GraphicsDevice

  override this.Update (gameTime) =
    if (GamePad.GetState(PlayerIndex.One).Buttons.Back = ButtonState.Pressed || Keyboard.GetState().IsKeyDown(Keys.Escape)) then this.Exit()
    base.Update(gameTime)
  override this.Draw (gameTime) =
    this.GraphicsDevice.Clear Color.Black
    // TODO: Add your drawing code here
    spriteBatch.Begin()
    spriteBatch.Draw(backBuffer, Rectangle(0, 0, w, h), Color.White * 1.0f)
    spriteBatch.End()
    base.Draw(gameTime)

Running the application renders the following result.
774396
As you can hopefully see; 1 of the stars has a thicker line width; because initially we set it to 4, and then change it to 2.
 
Last edited:
Wrapping up this thread
To end off this thread with a more practically applicable parser for production code; I'l be modifying my previous logo language parser code to use the production ready library called FParsec,
- Library: https://github.com/stephan-tolksdorf/fparsec
- Nuget: https://www.nuget.org/packages/FParsec/1.1.1-RC

C# developers
FParsec.CSharp is a thin wrapper library around the F# FParsec library; to add on a C# friendly API.
- Library: https://github.com/bert2/FParsec.CSharp
- Nuget: https://www.nuget.org/packages/FParsec.CSharp/


The goal of the last post will be twofold:
  • To translate the last logo code that was built using the draft parser combinator library built in this thread to FParsec instead.
  • To enhance the previous logo parser by adding on support more syntax including named procedures with parameters.
 
Switching over to FParsec
It would take a lot more effort to get our custom parser combinator up to the standard of existing production reading libraries like FParsec. Practically though it makes far more sense to use a library like FParsec where many of the challenges with parsing have already be solved.

Building a custom library like we've done in this thread is however never a lost cause, because in trying to understand how something is built, we end up with a far more deeper understanding of parser combinators, more specifically how they may be enhanced to improve not only the parsing of data, but also to improve tracing by adding on custom error parsing error, etc. We'll touch on a bit of this in this thread.


Code differences between custom parser to FParsec
Let's starts by comparing the changes to our existing logo language parser code to switch over from our custom parser library to FParsec.

First off we need to add the following Nuget to our project:


Let's now look at a few before and after code changes

Before
C#:
module Logo =
  let private pforward = (Parser.pstring "forward" <|> Parser.pstring "fd") >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> Walk
  let private pbackward = (Parser.pstring "backward" <|> Parser.pstring "bk") >>. Parser.spaces1 >>. Parser.pint .>> Parser.spaces <&> fun n -> Walk(-n)
...


After
C#:
module Logo =
  open FParsec .// open the FParsec namepace
  let private pforward = (pstring "forward" <|> pstring "fd") >>. spaces1 >>. pfloat |>> fun n -> Walk(int n)
  let private pbackward = (pstring "backward" <|> pstring "bk") >>. spaces1 >>. pfloat |>> fun n -> Walk(int -n)
...
As you can hopefully see the switchover is fairly easy as our previous combinator API purposefully shared many of the same design directions. These were all FYI derived from the original Parsec library in Haskell.

The remainder of this thread will be focused on switching over to FParsec, removing our previous parser combinator code, as it will no longer be needed with FParsec, and then on adapting our logo language AST and parser to support more language syntax including support named procedures with parameters. We'll end off by looking at how we can enhance our FParsec code to make it more easier to debug with parser tracing information that can be turned on or off as needed.


...but before that let's get a little sidetracked
Language Integrated Query that was first introduced by Microsoft in the .NET framework stems from ideas in Haskell and the work of Microsoft research with regards to combinators; from for example Erik Meijer and Daan Leijen (among others):
Related to FParsec -- Daan Leijen is the author of the Parsec Library in Haskell on which many of the ideas in this thread are based.

Linq built from functional programming ideas in Haskell; with its very unique Linq syntax was designed to make available it easier to exploit functional concepts like monads and parser combinators in C# and .NET. Luke Hoban (Microsoft) as example published the following blog post ahead of the official release of Linq in the .NET 3.5 framework in November 2007:
 
Last edited:
Variables, Parameters, Procedures and Procedural Calls
We need to enhance our logo language AST to support storing the additional syntax needed to support procedures with parameters and procedural calls.

C#:
namespace Endofunk.Logo

module AST =
  type Name = string
  type Parameter = string

  type Value =
    | Number of int
    | Variable of Parameter

  type Distance = Value
  type Degree = Value
  type Width = Value
  type Red = Value
  type Green = Value
  type Blue = Value
  type Alpha = Value
  type XCoord = Value
  type YCoord = Value

  type Command =
    | Forward of Distance
    | Backward of Distance
    | Left of Degree
    | Right of Degree
    | PenSize of Value
    | PenDown of bool
    | Repeat of Value * Command list
    | SetX of XCoord
    | SetY of YCoord
    | SetXY of XCoord * YCoord
    | SetRandomXY
    | SetH of Degree
    | SetPenColor of Red * Green * Blue
    | SetPenAlpha of Alpha
    | Call of Name * Value list
    | Procedure of Name * Parameter list * Command list

  type Turtle = { X: float; Y: float; Angle: int; PenDown: bool }
The concept of a Parameter and a Variable requires us to modify the way we capture the concept of a Value type.

The Command AST has been modified to use the new Value type; because essentially any syntax could be tied to input from a Variable as opposed to a Literal value.

More so I've added support to specifically distinguish between Left / Right turns, and Forward / Backward walk progressions. The reason for this is provide for now a more concrete pathway to deal with negative / positive values in the AST's Interpreter e.g. it's quite easy to capture the concept of a negative Integer literal value, but it becomes a bit more difficult to represent when its a Variable .

In addition we have a new Call type with two parameters:
  • Name -- The name of the procedural Call.
  • Value list -- List of input Value(s) tied to the procedural Call.
...and a new Procedure type with three parameters:
  • Name -- The name of the Procedure.
  • Parameter list -- List of the name procedure's defined parameters.
  • Command list -- List of the Command(s) that make up the body of the named Procedure.
Note:
Naturally a lot more changes would be required if you wanted to support all of the logo language's syntax -- this example code is in no way a representation of a perfect AST for a language.
I've chosen to keep it simple in this thread. Send me a PM if you need examples of a more comprehensive AST for a language like C#.
 
Last edited:
Parser for Values, Variables, Parameters & Procedures


Parsers to identify the parts of a named Procedure

The following is an example of how a name Procedure is defined in logo.
Code:
to square :size                                         
  repeat 4 [fd :size rt 90]        
end
The above syntax can be broken down into an Identifier, Parameter, and Variable.

C#:
namespace Endofunk.Logo
...

module Parser =
  open FParsec
  open AST

  let (||>>) fa fb =
    let f n = fa n || fb n
    f

  // Create a new parser combinator to back track on match failures with
  // procedural calls that have 1 or more parameters.
  let backtrackingSepBy1 p sep = pipe2 p (many (sep >>? p)) (fun head tail -> head :: tail)

  let procs = ref [] // mutable memory to store named procedures found
  let private pidentifier =
    let isDash c = c = '-'
    many1Satisfy2L (isLetter ||>> isDash) (isLetter ||>> isDigit ||>> isDash)  "identifier"
  let private pparameter = pstring ":" >>. pidentifier
  let private pnumber = pfloat |>> (int >> Number)
  let private pvariable = pnumber <|> (pparameter |>> Variable)
The infix operator ||>> that I have defined is to simplify the composition of logical disjunctions (OR) between predicates, for example:

The pidentifier parser combinator can be rewritten in long form as follows:
C#:
  let private pidentifier =
    let isDash c = c = '-'
    let isTailChar c = (isLetter c || isDigit c || isDash c) // composition of predicates
    let isHeadChar c = (isLetter c || isDash c) // composition of predicates
    many1Satisfy2L isHeadChar isTailChar "identifier"
The pvariable parser combinator as you see is a logical disjunction (OR) between a pnumber parser and pparameter parser.


Translation of previous parsers to FParsec
The following parsers below are a translation of the previous parsers to use the FParsec library.
C#:
  let private pforward = (pstring "forward" <|> pstring "fd") >>. spaces1 >>. pvariable |>> Forward
  let private pbackward = (pstring "backward" <|> pstring "bk") >>. spaces1 >>. pvariable |>> Backward
  let private pleft = (pstring "left" <|> pstring "lt") >>. spaces1 >>. pvariable |>> Left
  let private pright = (pstring "right" <|> pstring "rt") >>. spaces1 >>. pvariable |>> Right
  let private ppensize = pstring "setpensize" >>. spaces1 >>. pvariable  |>> PenSize
  let private pbool b: Parser<bool, unit> = preturn b
  let private ppenup = (pstring "penup" <|> pstring "pu") >>. pbool false |>> PenDown
  let private ppendown = (pstring "pendown" <|> pstring "pd") >>. pbool true |>> PenDown
  let private psetx = pstring "setx" >>. spaces1 >>. pvariable |>> SetX
  let private psety = pstring "sety" >>. spaces1 >>. pvariable  |>> SetY
  let private psetxy = pstring "setxy" >>. spaces1 >>. pvariable .>>. spaces1 .>>. pvariable |>> fun ((x, _), y) -> SetXY(x, y)
  let private psetrandomxy = pstring "setrandomxy" >>% SetRandomXY
  let private pseth = pstring "seth" >>. spaces1 >>. pvariable |>> SetH
  let private psetpencolor = pstring "setpencolor" >>. spaces1 >>. pvariable .>>. spaces1 .>>. pvariable .>>. spaces1 .>>. pvariable |>> fun ((((red, _), green), _), blue) -> SetPenColor(red, green, blue)
  let private psetpenalpha = pstring "setpenalpah" >>. spaces >>. pvariable .>> spaces1 |>> SetPenAlpha
  let private prepeat, prepeatRef = createParserForwardedToRef ()

The only additions to the previous parser code is:
  • psetrandomxy -- generate a random XY coordinate
  • psetpencolor -- set the pen color using 3 input Values; representing the color components Red, Green and Blue.
  • psetpenalpha -- set the Alpha value for pen color.


Forward reference for Procedural Call parsers
With a similar mutual recursion to the chicken and egg scenario we had with the prepeat parser; where we needed to create a parser that was dependant on the pcommand parser; and the pcommand parser which is mutually tied to the prepeat parser.
Mutual Recursion
It's a frequently reoccurring problem in parsing called Mutual Recursion, where two mathematical or computational objects, such as functions or data types, are defined in terms of each other.

When it comes to procedural calls we have a similar but more complex challenge; in that we need the pcommand parser to include our pcall parser. The difficulty is that the pcall parser is variable because Named Procedures are initially undefined, as they are depedant of the procedures that the parser will encounter in the logo code it is parsing; for example:

Once we've parsed this logo code:
Code:
to square :size                                         
  repeat 4 [fd :size rt 90]        
end
We can conclude that we need a parser for any procedural calls to the square procedure with a single parameter :size. Meaning that we need to dynamically build new parsers as we parse a logo input file / stream -- which we need to be referenced by the pcommand parser.


Dynamically building a parser
To resolve the mutual recursion reference challenges between the procedural call pcall parser and the pcommand parser. We define a pcall, pcallRef forward reference to a parser; in addition we need a place in memory procs to store name procedures details as we encounter them in the code we are parsing.

This place in memory procs is then used to dynamically construct the procedural call parsers and in effect inject these into the pcommand parsing process through the pcall's mutable forward reference.

In the following code we defined a mutable forward reference to the pcall parser; which is then logically tied into the pcommand parser as a choice of available parsers.
C#:
  let private pcall, pcallRef = createParserForwardedToRef ()
  let private pcommand = choice [pforward; pbackward; pleft; pright; ppensize; ppenup; ppendown; psetxy; psetx; psety; psetrandomxy; pseth; psetpencolor; psetpenalpha; prepeat; pcall]

The following function accesses the in place memory procs to dynamically build parsers that can identify procedural calls for named procedures that the pprocedure parse has successfully parsed.

The code below make use of F# List constructor syntax to iterate over the elements stored in the procs reference variable, creating a dynamic parser using the name and parameters ps captured by pprocedure -- this is then composited into a single logical disjunction (OR) parser using the choice combinator. We then finally update the mutable reference to the pcall parser to ensure that once we've parsed code for a new named procedure; the pcommand parser will be able to identify procedural calls to these name procedures.
C#:
  let updateCalls () =
    pcallRef :=
      choice [
        for (name, ps) in (!procs) ->
          pstring name >>. spaces >>. opt (backtrackingSepBy1 pvariable spaces)
          |>> fun optArgs ->
            match optArgs with
            | Some args -> Call(name, args)
            | _ -> Call(name, [])
      ]
  updateCalls()
The result of the dynamically created parser contains a procedural call's parameter values; which can be zero or more; we finally pattern match over this opt (optional) result to return an AST Call with arguments, or another without arguments.

Note:
This means that our parser requires that name procedures are defined before they are used i.e. in a top / down order.
The backtrackingSepBy1 parser defined previously is a special combinator that is not available in FParsec's default set of primitives. It is a combinator that tries to optionally match against 1 or more pvariable parsers separated by spaces; in the event of a failure it backtracks to ensure another parser can be attempted.


Update the prepeat mutable forward reference
Now that we have defined the pcommand parser we can update the prepeatRef forward reference with the parser code for a repeat code bock; a block that can not only repeat any of the command but also another repeat block.
C#:
  let pblock = between (pstring "[" .>> spaces) (spaces >>. pstring "]") (many1 (pcommand .>> spaces))
  prepeatRef := pstring "repeat" >>. spaces1 >>. pvariable .>> spaces .>>. pblock |>> fun (arg, commands) -> Repeat(arg, commands)
 
Last edited:
Top
Sign up to the MyBroadband newsletter
X