In the process of speeding up the test suite and splitting it, we may consider migrating it to Tasty: http://documentup.com/feuerbach/tasty

It may further speed up the tests by running them in parallel.

This is a task for everyone, so do it and reassign this task to the person below you alphabetically.

https://wiki.haskell.org/Programming_guidelines#File_Format

{- |
Module      :  <File name or $Header$ to be replaced automatically>
Description :  <optional short text displayed on contents page>
Copyright   :  (c) 2014-2015 HKU
License     :  BSD3

Maintainer  :  <email>
Stability   :  unstable | experimental | provisional | stable | frozen
Portability :  portable | non-portable (<reason>)

<module description starting at first column>
-}

As the source language grows it becomes hard to know which features are available. We should have a document in the wiki documenting the features and giving a few usage examples.

brunosoliveira created an issue 2014-10-14
Currently we are using unsafeCoerce to get cheap&quick coercions between PHOAS expressions. However I think this is a mistake. We should be using an undebruijn function. The benefit would be better debugging/error-messages and potentially a solution to the weird substitution issue (by enforcing a dedebruijn after every traversal).

Simplify adds redundant ids to every argument in the function application. As I can see, according to the type, it translates to some recursively structured identity function. The translation scheme can be described by the following recursive function [ ]:

[a] = λ(x : a). x
[a -> τ] = λ(x : a -> τ). λ(y : a). [τ] (x ((λ(d : a). d) y))

Here is an example:

If we have

λ(f : Int -> Int). λ(x : Int). f x

After simplification

λ(f : Int -> Int). λ(x : Int). f ((λ(y : Int). y) x) 

If we have

λ(f : (Int -> Int) -> Int). λ(g : Int -> Int). f g

After simplification

λ(f : (Int -> Int) -> Int). λ(g : Int -> Int). 
     f ((λ(x : Int -> Int). λ(y : Int). (λ(z : Int). z) (x ((λ(d : Int). d) y))) g)

After peval

\ (f : (Int -> Int) -> Int).
  \ (g : Int -> Int).
    f
      let x = g
      in
      \ (y : Int).
        let z = x let d = y in d
        in
        z

This task is to make the partial evaluator detect such structure, and replaces it by its argument.

The fractals failed to display and cause stack overflow in examples/fractals or use f2j/f2ji to compile and run fractals directly with compilation option stack and apply.

Allow patterns to appear on the left-hand side of the equal sign.

As a user of f2ji, I found that if you :run some source code that doesn't typecheck, f2ji will remove it.

f2ji> :run examples/ObjectAlgebra2.sf 
error: eval is not a member of the type IEval
invalid expression sf2Java
f2ji> :run examples/ObjectAlgebra2.sf 
examples/ObjectAlgebra2.sf does not exist

systemfcompiler % hg status 
! examples/ObjectAlgebra2.sf

The goal is to try the new unboxing approach. Simply put, incorporate all types (primitive types and references type into one closure class. See the code below:

package boxing;

abstract class Closure {
    int ix; // int input, or other primitive types
    Object ox; // ref input for closure
    int iout; // int output, or other primitive types
    Object oout; // ref output

    abstract void apply();
}

// Int -> Int
class Inc extends Closure {
    public void apply() { // Int -> Int
        this.iout = ix+1;
    }
}

// apply : (A -> B) -> A -> B
// apply = \f . \x . f x
class Apply extends Closure {
    Closure ap = this;

    public void apply() {
        oout = new Closure() {
                public void apply() {
                    Closure f = (Closure) ap.ox;
                    f.ix = this.ix; // set arguments, potentially could have a tag to decide which assignement to make.
                    f.ox = this.ox;
                    f.apply();
                    this.iout = f.iout; // set the outputs
                    this.oout = f.oout;
                }
            };
    }
}

public class Main {
    public static void main(String args[]) {
        Inc inc = new Inc();
        Apply apply = new Apply();
        long start, end;

        start = System.nanoTime();
        apply.ox = inc; // wrap(inc)
        apply.apply();
        Closure c = (Closure) apply.oout;
        c.ix = 10;
        c.apply();
        end = System.nanoTime();

        System.out.println("Time:" + (end - start));

        System.out.println(c.iout);
    }
}

Here, the class Closure has multiple input and output fields, one for each type. The steps are the followings:

1. Write an example (factorial?) using this approach by hand, and test it to see if it's ok.
2. Formalize the idea.
3. Then implement it.

As @xieningning points out, the following example should be a valid program:

let rec
  map A B (f:A->B) (n:Int): Bool =
    if(n<0)
    then True
    else map A B f (n-1)
and
  f(x:Int):Int = x+1
in
  map Int Int f 6

However, I am confirmed that in develop branch, the above program crashed somewhere in the frontend, resulting the notorious segmentation fault.

Currently in back-ends, there are still a lot of repeated codes around (most of which are quite similar with their counterparts in Base translation).

This task is to use some technique called Variation Point to reduce those repetitions as much as possible. Simply put, we spot those differences, abstract them away and put into new translation records.

isLeft and other related functions are newly introduced to Data.Either, which should not be used if we want our compiler to work on GHC 7.6.3.

(Create a Unit type -- should be there) and map to it

#!haskell

let f A = 0
in 0

This is the minimal program where JVM complains with this pattern.

The SystemF pretty printer gives

#!haskell

let f  = /\A. 0 in 0

But the closureF gives

#!haskell

let f = lam (/\A. 0) in 0

Jeremy has started working on it.

Port the code from the partition-checking project.

Complete the following tasks:

1. Write the standard big-step interpreter for a subset of our core language:

• variables, application, lambda, if-expressions, primitives, let, type application, type abstraction.

2. Write the symbolic interpreter & execution trees.

3. Write the pretty-printer. Improve the simple pretty printer.

4. Hook up the Symbolic Interpreter to f2ji, allowing users to use it from the command line.

:se exp

5. Create conditional compilation infrastructure on f2ji to avoid depending on Z3. Talk to Emma.

6. Port the Z3-related code.

There is an example that should typecheck. See the code below:

#!haskell

let getTwo A B (x : A) : A = x;
let getThree A B C (y : B) : B = getTwo B C y;
getThree Int String Int "abc"

Whereas f2j gives the "type mismatch" message:

#!c++

expected: A
  actual: B

Everything is OK if the user tries to avoid such overlapping in source file. But that should be a bug in TypeCheck, and probably similar to the previous substitution problem.

In the process of speeding up the test suite and splitting it, we may consider migrating it to Tasty: http://documentup.com/feuerbach/tasty

It may further speed up the tests by running them in parallel.

Allow patterns to appear on the left-hand side of the equal sign.

As we discussed in the seminar talk, the following code gives parse error.

#!haskell

type ToInt A = Int;
type Hide = { test : forall A. ToInt A -> Int };
let f (x : Hide) = x.test (ToInt String) 5;
0

By Weixin's comment in issue #184, it is

#!haskell

x.test (ToInt String) 5

that causes the error, which uses

#!haskell
javaexpr : aexpr "." LOWERID "(" comma_exprs0 ")"

to parse the code. The parentheses imply an Expr inside, not a Type.

Probably we need curly braces to distinguish Type from Expr.

George please take a look at it. This one should have higher priority than issue #184. Currently we are all engaged in different issues. We will help you later.

There is an example that should typecheck. See the code below:

let getTwo [A,B] (x: A): A = x;
let getThree [A,B,C] (y: B): B = getTwo [B,C] y;
getThree [Int,String,Int] "abc"

Whereas f2j gives the "type mismatch" message:

expected: A
  actual: B

Everything is OK if the user tries to avoid such overlapping in source file. But that should be a bug in TypeCheck, and probably similar to the previous substitution problem.

As @xieningning points out, the following example should be a valid program:

let rec
  map A B (f:A->B) (n:Int): Bool =
    if(n<0)
    then True
    else map A B f (n-1)
and
  f(x:Int):Int = x+1
in
  map Int Int f 6

However, I am confirmed that in develop branch, the above program crashed somewhere in the frontend, resulting the notorious segmentation fault.

something like a custom generator in Haskell’s QuickCheck. E.g. generate a 100,000-node AST of algebraic expressions using mutually recursive calls (kind of opposite of parsing).

Although the default behavior (shift) in both of the cases of conflict is what we want.

The clone method we have now is problematic in that it only sets the last argument. Instead, we want to clone the arguments all the way up to the outermost closure.

Output like this

\ (f : (Int -> Int) -> Int).
  \ (g : Int -> Int).
    f
      let x = g
      in
      \ (y : Int).
        let z = x let d = y in d
        in
        z

is not pretty. Brackets are still necessary in the above example:

\ (f : (Int -> Int) -> Int).
  \ (g : Int -> Int).
    f
      (let x = g
      in
      \ (y : Int).
        let z = x (let d = y in d)
        in
        z)

I am confirmed when running the following tailfact example

let rec fact (acc : Int) (n : Int) : Int =
if n == 0 then acc
else fact (acc * n) (n - 1)
in
fact 1 10

like f2j -r tail_fact.sf -m apply -m stack in the refactor-base branch will give you an exception, but make test says everything is fine.

Could this have something to do with Emma's recent work of making make test faster?

runtime.jar does not get updated if there is already an old one in path.

This is the cause of Emma having not been able to use f2j to run compiled Java programs.

Currently, "createWrap" check whether the previous statements contain any "Next.next" assignments (which in this translation correspond to .apply() calls); if not, it creates an empyClosure to wrap the resulting expression, and assigns it to Next.next for the main body loop to be able to process it.

https://bitbucket.org/brunosoliveira/systemfcompiler/src/9b8f3a85d45e19208c9ef46ec62aceb77148961f/compiler/StackTransCFJava.hs?at=default#cl-103

a few variant of zipWIth. For example:
zipWith1 : (Int -> Int) -> [Int] -> [Int]
zipWith2 : (Int -> Int -> Int) -> [Int] -> [Int] -> [Int]
zipWith5 : (Int -> Int -> Int -> Int -> Int -> Int) -> [Int] -> [Int] -> [Int] -> [Int] -> [Int] -> [Int]
zipWith10 : ...
and show
zipWith5 (\x1 x2 x3 x4 x5 -> x1 + x2 + x3 + x4 + x5) list1 list1 list1 list1 list1
With functions as objects and our implementation there will be 6 applications going on.

Implement in:

with high input value (overflowing) for SystemF (with all optimizations), functions-as-objects+trampolines versions in Scala, Java8, and Clojure

with low input value (not yet overflowing) for SystemF (with all optimizations) + non-trampoline versions of Scala, Java8, and Clojure + fastest trampoline
Selected more complex bench

(Create a Unit type -- should be there) and map to it

For months now we have been commenting out the simplifier in some cases to avoid issues in the backend.

While that's a momentary workaround, what really needs to be done is to make sure that the backend can process the code after simplification.

Seems some changes happening in the parser part, which cripple make test again. Could we agree that every time we push to the repo, at least pass all the tests?

This is a task for everyone, so do it and reassign this task to the person below you alphabetically.

https://wiki.haskell.org/Programming_guidelines#File_Format

{- |
Module      :  <File name or $Header$ to be replaced automatically>
Description :  <optional short text displayed on contents page>
Copyright   :  (c) 2014-2015 HKU
License     :  BSD3

Maintainer  :  <email>
Stability   :  unstable | experimental | provisional | stable | frozen
Portability :  portable | non-portable (<reason>)

<module description starting at first column>
-}

The goal is to try the new unboxing approach. Simply put, incorporate all types (primitive types and references type into one closure class. See the code below:

package boxing;

abstract class Closure {
    long ix; // long input, or other primitive types + there should be a TAG
    Object ox; // ref input for closure
    long iout; // int output, or other primitive types + there should be a TAG
    Object oout; // ref output

    abstract void apply();
}

// Int -> Int
class Inc extends Closure {
    public void apply() { // Int -> Int
        this.iout = ix+1;
    }
}

// apply : (A -> B) -> A -> B
// apply = \f . \x . f x
class Apply extends Closure {
    Closure ap = this;

    public void apply() {
        oout = new Closure() {
                public void apply() {
                    Closure f = (Closure) ap.ox;
                    f.ix = this.ix; // set arguments, potentially could have a tag to decide which assignement to make.
                    f.ox = this.ox;
                    f.apply();
                    this.iout = f.iout; // set the outputs
                    this.oout = f.oout;
                }
            };
    }
}

}

The below should be self-explanatory.

Running test from testsuite/tests/run-pass/
-------------------------------------
-------------------------------------
Compileation Option: [Naive]
Running simpl_mandelbrot.sf
1
Running Thunk.sf
I'm here!
Running bob1.sf
Haskell
Running intersection.sf
2
Running Apply.sf
2
Running EvenOddSelect.sf
1
Running fact.sf
3628800
Running substr.sf
bc
Running bob.sf
35
Running .
testsuite/tests/run-pass/. does not exist

And make test2 stops there.

Pretty printing

#!haskell
let id A (x : A) = x
in
id (forall A. A -> A) id Int

in Core gives

#!haskell

(\ (a : forall A. A -> A). a (forall A. C -> C) a Int) (/\ A. \ (a : D). a)

1. skips "B"
2. "C" and "D" are not bound

This is a task for everyone, so do it and reassign this task to the person below you alphabetically.
https://wiki.haskell.org/Programming_guidelines#File_Format

#!haskell
{- |
Module      :  <File name or $Header$ to be replaced automatically>
Description :  <optional short text displayed on contents page>
Copyright   :  (c) 2014-2015 HKU
License     :  BSD3

Maintainer  :  <email>
Stability   :  unstable | experimental | provisional | stable | frozen
Portability :  portable | non-portable (<reason>)

<module description starting at first column>
-}

TApp implicitly.