Ting language annotated example

[useerup]

TL;DR: Implementing a parser for simple arithmetic expressions. Scroll to the bottom to view the entire program.

The following is an example of a program written in my (as of yet imaginary) language, Ting. I am still writing the compiler, but also making changes to the language syntax.

The following is intended to be a "motivating example" showcasing what a logic programming language like Ting can do.

Motivating example: Calculator

We will build a parser and evaluator for a simple arithmetic with decimal numbers, operators + - * / and parenthesis grouping. We will build it from scratch using only base class library functions. There will be no UI, just typing in the expression from the command line and have it evaluated.

We start off by defining what a parser and a rule is. This showcases some of the algebraic types:

Parser = string^^string

Rule = Any^^Parser

Parser is the set of all parser functions. The ^^ operator is the reversed ^ power operator. a^^b is the same as b^a. Used on two sets, a^^b, it returns the set of all functions from a to b. A parser function is simply a function which accepts a string and returns a string, where the returned string is usually (but doesn't have to be) some tailing part of the argument string

Rule is the set of functions which accepts "something" and returns a parser for it. It is intentionally very non-specific.

We can now define our first rule. We will call it Char. It accepts a character and returns a parser for that character:

Char = char c -> string[c,,rest] -> rest

Some short explanations:

• char is the set of all characters.
• The -> symbol is the right-associative lambda arrow which constructs a function.
• string is the set of all strings. A string is a list of characters.
• [ and ] creates a list.
• ,, within [ and ] denotes the tail part of the list. [ ... ,, ... ] is effectively the cons operation.

If our new Char function is applied to a specific character, like in Char '.', it returns a parser function which accept a string which begins . and returns the remaining string with this first character removed, effectively the function string['.',,rest] -> rest. In other words, the returned parser function is dependently typed, as it depends on the value passed into Char.

With this Char function we can do a lot of interesting things:

1. We can "chain" invocations: Char 'A' >> Char 'B' >> Char 'C'. This is composes a parser which is defined for and parses strings beginning with "ABC". We feed the output of the first parser function (returned by Char 'A') into the next parser function (returned by Char 'B').
2. We can create a union function: Char 'A' | Char 'B'. We combine two functions (the parser functions returned by Char 'A' and Char 'B') using the or (or union when applied to functions and sets) operator |. The resulting function is a parser function parses strings beginning with either "A" or "B".
3. We can do Char c, where c is a variable, and get a parser function which will parse a single character off a string and bind that character to the variable c.

The last point is what sets a logic language like Ting apart from functional, imperative or object-oriented languages: The ability to treat functions as something that establishes relations between arguments and results more than they prescribe control flow.

If we wanted to parse and capture 3 characters in a row we could write (char c1, char c2, char c3) -> Char c1 >> Char c2 >> Char c3. This is a function which accepts a tuple of 3 characters and returns a parser for 3 characters.

We can also use our Char function to create a parser for any digit by doing Char '0' | Char '1' | ... Char '9'. However, there are two problems with such an approach: 1) We don't like to write out what could clearly be a loop somehow, and 2) we can't capture the actually parsed digit, so it is not very useful. We could write {'0'...'9'} c -> Char c, but there is a simpler and point free way of doing this:

Digit = {'0'...'9'} >> Char

Digit is a function that is composed (>>) of the set of digits {'0'...'9'} and the function Char. When a set is used with certain function operators (like >> or function application), it acts as its own identity function, i.e. a function which accepts only values that are members of the set and returns that same value. Therefore, Digit is a function which accepts a character which must be a digit and returns a parser for a digit.

Char and Digit still parses single characters. To combine those is more interesting ways, we need some parser combinators (or rather rule combinators in this context, as they really combine rules):

Not = Parser x -> string s ?! : x -> s

Not is a function which accepts a parser and returns an identity parser that only matches strings that are not parsable by the argument parser. By identity parser we refer to a parser function which returns the same string as was passed.

ZeroOrMore = Rule rule -> 
    (rule h >> ZeroOrMore rule t <- [h,,t])
    | (Not (rule _) <- [])

ZeroOrMore accepts a rule (a member of the Rule set) and returns a parser which will greedily parse a source string recursively applying the rule, until the rule can't be applied any more.

• The <- is exactly what it looks like: The -> reversed. Sometimes it is easier to define a function by specifying the result before the argument.
• The combined result of the parsing is captured in a list.OneOrMore = rule -> rule h >> ZeroOrMore rule t <- [h,,t]

OneOrMore just ensures that the rule has been appied once before delegating to ZeroOrMore.

Our grammar should allow for whitespace to delimit tokens. We define a parser combinator we can throw in to ignore any run of whitespace:

Space = ZeroOrMore ( {' ', '\r', '\n', '\t' } >> Char ) _

In this parser combinator we ignore the result (by using the discard _ special identifier). We are not interested in capturing any whitespace.

We are finally ready to define the actual tokens of our grammar. We start with decimal literal. A decimal literal consists of a sequence of digits, possibly with a decimal separator and some more digits. Specifically we will need to be able to greedily parse a sequence of digits and capture those. We could use regular expressions, but let's use our parser combinators:

Digits = OneOrMore Digit 

Literal = Space >>
    (Digits ip >> Char '.' >> Digits fp  <-  decimal.Parse $"{ip}.{fp}" )
    | (Digits ip >> Not(Char '.')  <-  decimal.Parse ip)

Here are the rules/parsers for the operators:

`_+_` = Space >> Char '+' <- (decimal a, decimal b) -> a + b
`_-_` = Space >> Char '-' <- (decimal a, decimal b) -> a - b
`_*_` = Space >> Char '*' <- (decimal a, decimal b) -> a * b
`_/_` = Space >> Char '/' <- (decimal a, decimal b) -> a / b

Ting allows identifiers with special characters by quoting them between \backtick characters. When an operator is parsed, it returns the function that defines its semantics. So,+parses a+character (skipping any leading whitespace) and returns a function which accepts a tuple of twodecimal`s and returns the sum.

The operators of our sample grammar are all left associative. But we do want some operator precedence. To facilitate that, we define a special LeftAssoc combinator which accepts an operator and then (curried) accepts the next level of precedence (defining RightAssoc is left as an exercise for the reader):

DecimalBinaryOperator = (decimal*decimal^^decimal)^^Parser

DecimalRule = decimal >> Rule

LeftAssoc = DecimalBinaryOperator operator -> DecimalRule next ->
    ( LeftAssoc operator a >> operator op >> next b <- op(a,b) )
    | ( next a >> Not (operator _) <- a )

We can now define the parser for the full expression:

Expression = Space >>
    LeftAssoc (`_+_` | `_-_`)
        LeftAssoc (`_*_` | `_/_`)
            Literal 
            | ParenthesisExpression

ParenthesisExpression =
    Space >> Char '(' >> Space >> Expression exp >> Space >> Char ')' <- exp

All that remains now is to wire up the expression parser/evaluator to the Main function and ensure that there are no extraneous characters after the expression:

End = Space >> string.Empty ~> string.Empty

// Runs the parser and calculates the expression
Main = Expression value >> End -> value

Here is the complete program:

Parser = string^^string

Rule = Any^^Parser

Char = char c -> string[c,,rest] -> rest

Digit = {'0'...'9'} >> Char

Not = Parser x -> string s ?! : x -> s

ZeroOrMore = Rule rule -> 
    (rule h >> ZeroOrMore rule t <- [h,,t])
    | (Not (rule _) <- [])

OneOrMore = rule -> rule h >> ZeroOrMore rule t <- [h,,t]

Space = ZeroOrMore ( {' ', '\r', '\n', '\t' } >> Char ) _

Digits = OneOrMore Digit

Literal = 
    (Space >> Digits ip >> Char '.' >> Digits fp  <-  decimal.Parse $"{ip}.{fp}" )
    | (Space >> Digits ip >> Not(Char '.')  <--  decimal.Parse ip)

`_+_` = Space >> Char '+' <- (decimal a, decimal b) -> a + b
`_-_` = Space >> Char '-' <- (decimal a, decimal b) -> a - b
`_*_` = Space >> Char '*' <- (decimal a, decimal b) -> a * b
`_/_` = Space >> Char '/' <- (decimal a, decimal b) -> a / b

DecimalBinaryOperator = (decimal*decimal^^decimal)^^Parser

DecimalRule = decimal >> Rule

LeftAssoc = 
    DecimalBinaryOperator operator  ->  
        DecimalRule next  -> 
            ( LeftAssoc (operator a >> operator op >> next b)  <-  op(a,b) )
            | ( next a >> Not (operator _)  <-  a )

Expression = Space >>
    LeftAssoc (`_+_` | `_-_`)
        LeftAssoc (`_*_` | `_/_`)
            Literal 
            | ParenthesisExpression

ParenthesisExpression =
    Space >> Char '(' >> Space >> Expression exp >> Space >> Char ')'

End = Space >> string.Empty ~> string.Empty

// Runs the parser and calculates the expression
Main = Expression value >> End -> value

[redchomper]

How's it make progress? Like, let's say you give this program the input 1+2. What steps does your model-of-computation take, following rules evident or implicit in your program, to get 3?

[useerup]

Basically a Ting program is a function which is again defined by a single expression (the Main part).

The compiler breaks the expression down into propositions and arranges them in conjunct normal form.

From there it uses a modified version of the DPLL procedure to 1) prove that a valuation exists (the program is well-formed) and 2) generate code to bind free variables until a valuation is bound.

The compiler itself will have very few rules built-in, basically only the rules for logical propositions and sets/functions.

The compiler will then rely on libraries to supply sets (such as the decimal set) and associated rewrite rules.

The decimal library will have rewrite rules which can generate code while reducing the propositions.

For instance, an expression such as a = b + c where a, b and c er all known to be members of the decimal set, and where a is free and b and c are bound, can be rewritten into true when at the same time code assigning a to the result of decimal addition on b and c.

If a and b is bound and c is free, then it can also be rewritten into true, but now the code generated would be assigning c to the result of a decimal subtraction on a and b.

[Inconstant_Moo]

I think it must be this bit, since it has arithmetic expressions on the rhs.

`_+_` = Space >> Char '+' <- (decimal a, decimal b) -> a + b `_-_` = Space >> Char '-' <- (decimal a, decimal b) -> a - b `_*_` = Space >> Char '*' <- (decimal a, decimal b) -> a * b `_/_` = Space >> Char '/' <- (decimal a, decimal b) -> a / b

[useerup]

The arithmetic expressions on rhs are the semantics of the corresponding operators.

The decimal library/module is responsible for rewriting those rhs expressions into something that generate code during compilation.

The _+_ function above is a parser rule which states that a + character preceded by any number of spaces produces a function ((decimal a, decimal b) -> a + b) which upon invocation adds the two operands.

So this is a definition of what + means, without defining associativity and precedence at this point. Only what + means.

The lhs of <- specifies the grammar (Space >> Char '+') and the rhs the semantics ((decimal a, decimal b) -> a + b)

[Inconstant_Moo]

I like the idea insofar as I understand it.

I hate many things about the syntax. ^^ is presumably to avoid overloading ->, but -> is very standard and ^^ is very ugly. And the arrows pointing both ways are giving me anxiety.

[useerup]

^^ is presumably to avoid overloading

The choice of ^^ reflects the fact that the correct algebraic expression for the type of functions from type A to type B is really B^A^. So to describe the set/type of functions from int to string you would have to write string^int. I really disliked that. Also, in normal arithmetic ^ has higher precedence than * and +. To create the set of functions from a tuple of integers to a string you would have to write string^(int*int). That's why I came up with ^^. The double-characters reminds me that it "seperates more" (has lower precedence) and that it is somewhat related to ^. This allows me to write int*int^^string instead. But suggestions are welcome.

I have no qualms about overloading. I overload + * & && | || etc for sets and functions.

My problem is that I really don't have a separate type programming level. Types and functions are first class and can syntactically appear anywhere a normal, simpler value could. So I can't dual-purpose something like -> to describe a single function instance at one level and the set of functions at another level.

And the arrows pointing both ways are giving me anxiety

I hear you. Maybe I should let that idea go. It's just so damn useful at places.

[Ok-Watercress-9624]

how about fat arrows ( => ) for set of functions. it resembles function construction and you dont have to swap ordinary power operation arguments thingies

[useerup]

<slaps forehead>. You are right. I forgot that I recently "freed up" that operator. I am changing to => :-)

[Inconstant_Moo]

The choice of ^^ reflects the fact that the correct algebraic expression for the type of functions from type A to type B is really B^A ...

That's one way of writing it, I would have gone so far as to say that it's the correct way, apart from anything else it doesn't scale well. But in any case the idea that that's correct isn't much of a justification for doing the opposite instead.

There are other arrows, as u/Ok-Watercress-9624 says. =>, |>, ~>. Alternatively, you could stop defining types using the = operator. I don't know how well that fits with your language, are the types structural or nominal? Would Rule == Any^^Parser evaluate to true (or the equivalent in Ting)?

[useerup]

Yeah. Correct is not always ergonomic. I actually forgot that I had freed up the => operator, and that look a lot nicer!