Use Frege List from Java code

Question

I would like to understand how Frege List works and how is it possible to use it from Java. While I downloaded the Frege compiler code, I found difficult to understand what a Frege List is from the Frege code.

Doing some tests I saw that a Frege List is an instance of the TList class in Java with a special method, called _Cons(), that returns a DCons object. DCons is, as expected, a pair where the first element of the pair corresponds to the head of the list while the second element is the tail, thus another TList. When _Cons() is called on an empty lists, the return value is null. Therefore, to implement a Java iterator over Frege TList, one could write:

public class TListIterator implements Iterator<Object> {
    DCons elem;
    public TListIterator(TList list) {
      this.elem = list._Cons();
    }

    @Override
    public boolean hasNext() {
      return this.elem != null;
    }

    @Override
    public Object next() {
      final Object head = Delayed.<Object>forced( this.elem.mem1 );
      this.elem = this.elem.mem2.<TList>forced()._Cons();
      return head;
    }

    @Override
    public void remove() {
      throw new RuntimeException( "Remove is not implemented" );
    }
}

My questions are:

• Is my explanation of TList correct?
• Is TListIterator correct?
• where can I find more informations on what TList, DList and DCons are in the Frege compiler source code? Are they documented?
• A more generic question on best practices in Frege: when you want Java code to use a Frege value, is it better to return Java "standard" Objects from Frege code or is it better to directly use Frege classes from Java? My opinion is that the former is easier to write than the latter but has a little conversion overhead. For instance, a TListIterator can always be avoided by converting the TList into a Java LinkedList from Frege.

Answer 1

First of all, the ultimate guide for calling into Frege from Java is this wiki page.

It explains, among others, how frege data declarations appear in Java code.

The only special thing about lists is that there is no explicit Frege declaration of it anywhere, but we can assume that it looks like:

data List a = List | Cons a (List a)

Note that the identifier List after the equal sign is the constructor for empty lists, usually called Nil. The reason that it is called List (the same as the type) is because the routine for mangling frege names into valid java names translates [] into List. And in Frege source code we use [] as the type name and the constructor name as well.

Here is the outline of the Java code corresponding to the above:

public interface TList extends frege.runtime.Value, frege.runtime.Lazy {
  public TList.DCons _Cons() ;
  public TList.DList _List() ;
  final public static class DCons extends frege.runtime.Algebraic implements TList {
    private DCons(final java.lang.Object arg$1, final frege.runtime.Lazy arg$2) {
      mem1 = arg$1; mem2 = arg$2;
    }
    final public static TList mk(final java.lang.Object arg$1, final frege.runtime.Lazy arg$2) {
      return new DCons(arg$1, arg$2);
    }
    final public DCons _Cons() { return this; }
    final public TList.DList _List() { return null; }
    final public java.lang.Object mem1 ;
    final public frege.runtime.Lazy mem2 ;
  }
  final public static class DList extends frege.runtime.Algebraic implements TList {
    private DList() {}
    final public static TList mk() { return it; }
    final public static DList it = new DList();
    final public DList _List() { return this;}
    final public TList.DCons _Cons() { return null; }
  }
}

As you see, the overall type is an interface TList. The only thing you can do with a list is to check the variant, for this we have the methods _List() and _Cons(). As you correctly observed, _Cons() returns null for the empty list, and a TLIst.DCons instance for a non-empty list. From there you can extract the head (mem1) and the tail (mem2).

As far as I can see, your list iterator should work fine.

Observe the simple encoding to avoid duplicate names in Java:

• Frege type Foo gets the name TFoo in Java.
• Frege data constructor Bar gets the name DBar
• The method that checks if we have a DBar is _Bar. (Note that there is no explicit field that encodes the constructor, this way we use the JVM object header for our purpose where this is encoded anyway)

The naming is, of course, a bit cryptic at first sight. But it is also not exactly intended for the average user. In fact, I didn't think that calling Frege from Java would be interesting at all for anyone. But now I think differently, and we are designing a way to make it possible to implement a Java interface in Frege (it looks like this would serve your purpose here also).

For your last question, I'd say it depends. It is surely the best if you can return just int or double or string. If that doesn't work and you need a list, then your approach with a custom Iterator is preferrable, IMHO. The alternative would be to create a Java List, but this is not pure because List would have to be declared mutable in Frege. In addition, you would be wasting space by effectively duplicating the list.

Yet another possibility would be to return an Array. For example, as you can see in the REPL, the following

foo a b c = arrayFromList [a,b,c] :: JArray Int

would get a signature like:

final public static int[] foo(...