Ask letrec to have a syntactic requirement to disallow problematic mutual recursion

[zonyitoo]

let rec func1 : Int = {
    let func2 : Int = func1;
    func2
};
func1

Compile passed but threw java.lang.NullPointerException in runtime.

Corresponding Haskell is

func1 :: Int
func1 = func2

func2 :: Int
func2 = func1

When calling func1, it should be an infinity loop.

It is a simplified test case.

[zonyitoo]

Moreover, this is invalid in F2J

let func2 : Int = func1;

let func1 : Int = func2;

func1

Compiler reported error: ‘func1’ is not in scope. It make sense, but could be improved.

[bixuanzju]

@zonyitoo In you second example, if you mean mutually recursive functions, you should use let rec ... and syntax like

let rec func2 : Int = func1 and
func1 : Int = func2;
func1

[zhiyuanshi]

I would like to thank @zonyitoo a lot for reporting those interesting cases!

[zonyitoo]

@bixuanzju You can try to run your code, it should report null pointer exception.

[bixuanzju]

@zonyitoo Exactly, assign it to me now.

[bixuanzju]

@zonyitoo According to our translation rules, java.lang.NullPointerException is expected. After all, this is a problematic program. In Haskell, it will loop forever, and in our language, it will throw exception. May I ask what is your expected result?

[zonyitoo]

@bixuanzju I want to write a simple parser to parse arithmetic expression, the definition in Haskell is

expr   :: Parser Int
addop  :: Parser (Int -> Int -> Int)
factor :: Parser Int

expr = [f x y | x <- expr, f <- addop, y <- factor] ++ factor
addop = [(+) | _ <- char '+'] ++ [(-) | _ <- char '-']
factor = natual ++ bracket (char '(') expr (char ')')

Please pay attention on the definition of expr and factor. I got a null pointer exception when I try to run a test on F2J. The example on the top is a simplified case of this.

[bixuanzju]

@zonyitoo Could you show me the full f2j program? I don't understand "The example on the top is a simplified case of this", if this is the case, then your definition is wrong because you said the Haskell version will go to infinite loop, let alone our own version.

[zonyitoo]

Alright. Please refer to https://github.com/zonyitoo/parser-combinators-f2j/blob/master/src/parser.sf#L199

[brunocdsoliveira]

@zonyitoo There is an important difference between fcore and Haskell: Haskell is a lazy language, whereas f2j is not. Therefore programs such as:

ones = 1 : ones

which are fine in Haskell will not work directly in fcore. fcore is in that sense like Scala, OCaml or other call-by-value functional languages. As George when you meet him this morning about call-by-name arguments and Thunks, which you can use in this case to achieve similar results to Haskell.

[bixuanzju]

@zonyitoo I still can't figure out what's wrong. Could you provide me a simplified test case where the Haskell version can run, whereas ours not.

[zonyitoo]

@bixuanzju I know the version that I just provided to you is a left recursive definition, so it won't end even in Haskell. So I just write a non-left-recursive (looks non-left-recursive) version: https://github.com/zonyitoo/parser-combinators-f2j/blob/master/src/parser.sf#L199.

Moreover, I think @brunocdsoliveira is right, we need lazy evaluation, which is call-by-name in this situation. The example/CallByName.sf doesn't provide any useful information about call-by-name.

[zonyitoo]

Here is a Haskell version of the parser, which works exactly what I want.

module Main (main) where
import Data.Char

type Parser a = String -> [(a,String)]

result :: v -> Parser v
result v = \inp -> [(v, inp)]

zero :: Parser v
zero = \_ -> []

item :: Parser Char
item []     = []
item (x:xs) = [(x, xs)]

bind :: Parser a -> (a -> Parser b) -> Parser b
p `bind` f = \inp -> concat [f v inp' | (v,inp') <- p inp]

sat :: (Char -> Bool) -> Parser Char
sat p = item `bind` \x -> if p x then result x else zero

char :: Char -> Parser Char
char x = sat (\y -> x == y)

digit :: Parser Char
digit = sat (\x -> '0' <= x && x <= '9')

plus :: Parser a -> Parser a -> Parser a
p `plus` q = \inp -> (p inp ++ q inp)

many :: Parser a -> Parser [a]
many p = plus (bind p (\x -> bind (many p) (\xs -> result (x:xs)))) (result [])

many1 :: Parser a -> Parser [a]
many1 p = bind p (\x -> bind (many p) (\xs -> result (x:xs)))

nat :: Parser Int
nat = bind (many1 digit) (\xs -> result (eval xs))
    where
        eval xs = foldl1 op [ord x - ord '0' | x <- xs]
        m `op` n = 10 * m + n

bracket :: Parser a -> Parser b -> Parser c -> Parser b
bracket open p close = bind open (\_ -> bind p (\x -> bind close (\_ -> result x)))

chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
p `chainl1` op = bind p (\x -> bind (inner) (\fys -> result (foldl (\x' (f,y) -> f x' y) x fys)))
    where
        inner = many (bind op (\f -> bind p (\y -> result (f,y))))

expr :: Parser Int
expr = factor `chainl1` addop

addop :: Parser (Int -> Int -> Int)
addop = plus (bind (char '+') (\_ -> result (+))) (bind (char '-') (\_ -> result (-)))

factor :: Parser Int
factor = plus nat (bracket (char '(') expr (char ')'))


main :: IO ()
main = putStrLn (show (expr "1+2"))

[zonyitoo]

To explain that, the code in Haskell

expr :: Parser Int
expr = factor `chainl1` addop

addop :: Parser (Int -> Int -> Int)
addop = plus (bind (char '+') (\_ -> result (+))) (bind (char '-') (\_ -> result (-)))

factor :: Parser Int
factor = plus nat (bracket (char '(') expr (char ')'))

are similar in F2J

let operation = {
    let addop (a : Int) (b : Int) : Int = a + b;
    let subop (a : Int) (b : Int) : Int = a - b;
    let mulop (a : Int) (b : Int) : Int = a * b;
    let divop (a : Int) (b : Int) : Int = a / b;

    -- Fancy style
    foldr[Parser[Int -> Int -> Int], Parser[Int -> Int -> Int]] (plus[Int -> Int -> Int])
        (bind[Char, Int -> Int -> Int] (char '+') (\(c : Char) -> result[Int -> Int -> Int] addop))
        (Cons[Parser[Int -> Int -> Int]]
            (bind[Char, Int -> Int -> Int] (char '-') (\(c : Char) -> result[Int -> Int -> Int] subop))
            (Cons[Parser[Int -> Int -> Int]]
                (bind[Char, Int -> Int -> Int] (char '*') (\(c : Char) -> result[Int -> Int -> Int] mulop))
                (Cons[Parser[Int -> Int -> Int]]
                    (bind[Char, Int -> Int -> Int] (char '/') (\(c : Char) -> result[Int -> Int -> Int] divop))
                    (Nil[Parser[Int -> Int -> Int]]))))
};

let rec expr : Parser[Int] =
    chainl1[Int] factor operation
and factor : Parser[Int] =
    plus[Int] natural (bracket[Char, Int, Char] (char '(') expr (char ')'));

except that the F2J program supports add, sub, mul and div operations. The Haskell program works while F2J program crashes with null pointer exception.

[bixuanzju]

Hmm, this is still somewhat complex to debug. Could you simplify it further to a minimal example?

[zonyitoo]

@bixuanzju I think this should be considered as a bug, not a question. It is obviously that there is a bug in here but it is hard to locate. I am trying to simplify it.

Actually, if the example that on top work, maybe it will work too.

[brunocdsoliveira]

@zonyitoo: I think your program would loop in a call-by-value language (say Scala). Try this instead:

let rec expr : Parser[Int] =
    \(s: PolyString) . chainl1[Int] factor operation s
and factor : Parser[Int] =
    \(s : PolyString) . plus[Int] natural (bracket[Char, Int, Char] (char '(') expr (char ')')) s;

[zonyitoo]

@brunocdsoliveira THAT IS UNBELIEVABLE! It works!

Why the following two piece of code is different?

let rec expr : Parser[Int] =
    chainl1[Int] factor operation
and factor : Parser[Int] =
    plus[Int] natural (bracket[Char, Int, Char] (char '(') expr (char ')'));

The code above reports null pointer exception.

let rec expr : Parser[Int] =
    \(s : PString) -> chainl1[Int] factor operation s
and factor : Parser[Int] =
    \(s : PString) -> plus[Int] natural (bracket[Char, Int, Char] (char '(') expr (char ')')) s;

The above code works fine!!

And why Haskell works??

[brunocdsoliveira]

well, in a call-by-name language eta-expansion:

(\x . e x) = e 

is indeed a valid equality. But that is not true in a call-by-value language. Suppose e is a program that loops, lets call that program infinity. Now suppose that you have the following two programs:

(\x . 1) infinity

and

(\x . 1) (\x . infinity x)

Then in a call by value you'll get the following:

(\x . 1) infinity 

~~>

infinity

and

(\x . 1) (\x . infinity x)

~~>

1

This is precisely what is happening in your program above. If you want to understand better why your program loops, calculate the steps of the program step-by-step a few times. If you use call-by-value rules (reduce arguments first before passing arguments to the functions), you'll see that your factor and expo arguments start reducing forever. However, if you add a lambda around them, then evaluation of a lambda is immediate and the evaluation goes in a very different way.

[zonyitoo]

@brunocdsoliveira

if you add a lambda around them, then evaluation of a lambda is immediate and the evaluation goes in a very different way

I see!! Thanks Dr. Oliveira!!

[brunocdsoliveira]

You are welcome: a free lesson on Programming Languages ;)

[bixuanzju]

Problem solved

[brunocdsoliveira]

@bixuanzju: Not quite. There is still a problem in that those NullPointerExceptions should not be happening. The better solution would be that letrec would have a syntactic requirement that there is at least one argument to the function. However this is not a big priority.