Bluish Coder

Programming Languages, Martials Arts and Computers. The Weblog of Chris Double.


2017-03-20

Relational Programming in Mozart/Oz

A video I watched recently on logic programming, A Vision for Relational Programming in miniKanren, by William Byrd gives some interesting examples of relational programming using miniKanren.

miniKanren is an embedded constraint logic programming language designed for writing programs as relations, rather than as functions or procedures. Unlike a function, a miniKanren relation makes no distinction between its inputs and outputs, leading to a variety of fascinating behaviors. For example, an interpreter written as a relation can also perform code synthesis, symbolic execution, and many other tasks.

The video demonstrates how a relational interpreter can be used not just to evaluate expressions but to also generate valid expressions given a result. Other examples of relational programming would be the Prolog examples in my Shen Prolog post where relational functions like member can be used to enumerate all members of a list, as well as the traditional finding a member in a list.

I like to use the Mozart Programming System for exploring logic programming and this post goes through converting some examples in Mozart/Oz. Mozart is an implementation of the Oz programming language. The book "Concepts, Techniques, and Models of Computer Programming" is a good textbook for learning the different programming models that Mozart enables, including the relational model. For the examples here I'm using Mozart 1.3.x. It's an old language and implementation but I like to experiment with languages that are a bit different to mainstream languages.

The Prolog examples following can be tested in the online SWI Prolog implementation, Swish.

Basic example

The following function in Prolog has multiple values that be used as an argument:

foo(one).
foo(two).
foo(three).

Passing either one, two or three succeeds:

foo(one).
true

foo(two).
true

foo(four).
false

Using backtracking it's possible to enumerate all valid arguments:

foo(X).
X = one
X = two
X = three

The function findall can be used to return all values in a list:

findall(X, foo(X), Y).
Y = [one, two, three]

Backtracking in Mozart/Oz is not the default. Mozart provides the choice statement to enable backtracking. A choice statement contains a sequence of clauses separated by [] where a 'choice point' is created for each group of clauses. Each clause is tried in turned - if a particular clause fails then execution backtracks to a previous choice point and is resumed until one succeeds or all fails. The equivalent implementation of foo in Mozart is:

fun {Foo}
   choice
      one
   []
      two
   []
      three
   end
end

Prolog uses an automatic depth first search to find solutions. Mozart doesn't do automatic search - programs involving choice points must be run in a search engine that can implement any form of search required. A default search engine is provided that does depth first search. Here we create a search object and enumerate all the valid results manually:

Y = {New Search.object script(Foo)}
{Browse {Y next($)}
[one]

{Browse {Y next($)}
[two]

{Browse {Y next($)}
[three]

{Browse {Y next($)}
nil

The Mozart syntax can look a little strange at first but it's not too difficult to understand once it's learnt. New instantiates an object. Search.object is the class of the object being created. script(Foo) is a record that is being passed to the constructor of Search.object. The Foo is the function we created previously. The remaining statements call the next method on the object. next takes as an argument a variable that receives the result of the call. The use of $ tells Mozart to pass a temporary variable to receive the result, and return that result as the result of the call. This result is passed to Browse which displays the result in the GUI browser. Results are returned in single element lists and when there are no more results, nil is returned.

There is a library function to return all possible solutions in a list, Search.all:

{Browse {Search.all Foo 1 _ $}}
[one two three]

The ability to interactively drive the search enables writing programs that control the search process. The Explorer is a Mozart tool that uses this ability to show an interactive graph of the search space of a program. It can be run to show a graph of all solutions in Foo with:

{Explorer.all Foo}

Membership testing

In Prolog a function to test membership of a list can be written as:

mem(X, [X|_]).
mem(X, [_|Y]) :- mem(X, Y).

This states that X is a member of the list if X is the head of the list (the first element), or if it is a member of the tail of the list.

mem(2, [1,2,3]).
true.

Thanks to Prolog's backtracking you can also use this function to enumerate all values in the list:

mem(X, [1,2,3]).
1
2
3

In Swish you need to click 'Next' to get each result. You can return all results as a list with findall:

findall(X, mem(X, [1,2,3]), Y).
Y = [1, 2, 3].

This is what the non-backtrackable member function looks like in Mozart:

fun {Mem X Ys}
   case Ys
   of nil then false
   [] Y|Yr then X==Y orelse {Mem X Yr}
   end
end

{Browse {Mem 1 [1 2 3]}}
true

A backtrackable version of this code uses choice instead of case to create choice points in each clause:

proc {Mem X Ys}
   choice
      Ys = X|_
   []
      Yr
   in
      Ys = _|Yr
      {Mem X Yr}
   end
end

Here proc is used instead of fun. A procedure doesn't return a value. It is expected to bind values to arguments to return a result. In this case either X or Ys will be bound depending on what is passed as an argument. Given the call Mem 1 [1 2 3] then the first clause of choice succeeds - the head of the list is equal to X. With the call Mem X [1 2 3] then X will be successively bound to each element of the list depending on what order the search engine used to evaluate it uses. Mem 1 Y will enumerate all possible lists containing 1:

{Browse {Search.all proc {$ L} {Mem 1 [1 2 3]} end 1 _ $}}
[_]

{Browse {Search.all proc {$ L} {Mem L [1 2 3]} end 1 _ $}}
[1 2 3]

Y={New Search.object script(proc {$ L} {Mem 1 L} end)}
{Browse {Y next($)}}
[1|_]

{Browse {Y next($)}}
[_|1|_]

{Browse {Y next($)}}
[_|_|1|_]

The difference here compared to our search over Foo is that an anonymous procedure is passed to the search engine. Foo was aleady a single argument procedure so it didn't require a wrapper. The anonymous procedure takes a single argument which is expected to be bound to the result of a single iteration. In the first example no result is bound, just the fact that the Mem call succeeds is enough. In the second, L is bound to the first argument to Mem resulting in a list of all valid first arguments. In the third, L is bound to the second argument to Mem resulting in a list of all valid lists that contain the element 1. This is infinite so we only iterate the first few solutions.

Syntax checker

The miniKanren video referenced earlier, A Vision for Relational Programming in miniKanren, has an example of a simple language syntax checker implemented in the relational style. The equivalent Mozart implementation is:

proc {LCSyn Term}
   choice
      {IsAtom Term true}
   []
      X T
   in
      Term = lambda(X T)
      {IsAtom X true}
      {LCSyn T}
   []
      E1 E2
   in
      Term = [E1 E2]
      {LCSyn E1}
      {LCSyn E2}
   end
end

A Term is either an atom, a lambda record containing an argument and body, or application of two expressions (here represented as a list). A Term can be tested to see if it is valid with:

{Browse {Search.one.depth
         proc {$ L}
            {LCSyn lambda(foo bar)}
         end
         1 _ $}}

A result of [_] indicates that it succeded (nil would be a failure). Thanks to the magic of relational programming it's possible to enumerate all valid terms:

Y={New Search.object script(LCSyn)}
{Browse {Y next($)}}
[lambda(_ _)]

{Browse {Y next($)}}
[[_ _]]

{Browse {Y next($)}}
[[lambda(_ _) _]]

{Browse {Y next($)}}
[[[_ _] _]]

Reversible Factorial

As a final example, the following program implements a factorial function that can compute the factorial of a number, or the number given its factorial:

proc {Fact ?N ?F}
   proc {Fact1 ?N ?F}
      choice
         N = 0
         F = 1
      []
         N1 F1
      in
         N1::0#FD.sup
         F1::0#FD.sup
         N >: 0
         N1 =: N - 1
         F =: N * F1
         {Fact1 N1 F1}
      end
   end
in
   N::0#FD.sup
   F::0#FD.sup      
   {Fact1 N F}
   {FD.distribute naive [N F]}
end

% Factorial of 5
{Browse {Search.all proc {$ L} {Fact 5 L} end 1 _ $}}
[120]

% What factorial gives the answer 24
{Browse {Search.all proc {$ L} {Fact L 24} end 1 _ $}}
[4]

This uses a few more Mozart features but is essentially a search through the choice points in a choice statement. In this case it also uses Finate Domain Constraints. This allows telling Mozart what the range of a particular integer value can be, provides constraints upon that value and the search process will attempt to find a solution that results in the integer containing a single value. The syntax X::0#5 constrains the variable X to be from zero to five. FD.sup is a constant for an implementation defined maximum upper bound. Operators ending in : impose constraints on values that can be backtracked during search. There's a limitation to this approach in that the finite domain constraint has an implementation defined maximum upper value and the search will fail if it hits this value which unfortunately limits the practicality of a reverse factorial.

Mozart/Oz summary

Mozart/Oz has a lot of other interesting functionality. Distributed objects, GUI programming, Concurrency, amongst others. It's a fun tool to experiment with and Concepts, Techniques, and Models of Computer Programming is an excellent read.

Unfortunately development of Mozart has slowed from its heyday. A reimplementation of Mozart, called Mozart 2 is being worked on that uses LLVM for the code generator and replaces the internal constraint programming system with the Gecode toolkit. Development seems to have stalled recently and it lacks many of the features that already exist in older Mozart versions. Hopefully it'll pick up steam again.

For this reason I continue to use Mozart 1.3.x. There is a 1.4.x version but it has some issues that make me avoid using it. The distributed layer was replaced with an implementation written in C++ which has some bugs that I've been unable to work around in projects where I used it. The distribution panel is broken due to the hooks it requires not being implemented by the new C++ layer. At some point Mozart 2 may be complete enough for me to move to that version. I make the occasional fixes to 1.3.x and 1.4.x to keep it building and running on Linux.

Even though Mozart seems to be in a holding pattern it's a great for exploring ideas and the list of papers is a good resource for learning about distributed programming, constraints and concurrency. Some interesting projects implemented in Mozart include:

Tags: mozartoz 

2017-02-22

Borrowing Internal Pointers in ATS

Recently Robert O'Callahan wrote a post on what Rust can do that other languages can't. It involves getting a pointer to an internal field of a stack allocated object and having the type system ensure that the lifetime of that pointer doesn't outlive the owning object.

As soon as I saw this I thought "Aha, ATS can do that!" but I suspected it would be quite a bit more verbose. It turns out it's possible but tedious to do and while ATS 1 can do it in safe code, ATS 2 requires some help. This isn't a "Robert's post is wrong" post or a tear down of Rust, it's a thought experiment in how to do things in ATS that are easier in Rust. Plus ATS is in no way a "remotely mainstream language".

The following is a representation of the scenario that works in ATS 1. First we declare the type of an object that contains two fields:

viewtypedef X = @{
  a= int,
  b= int
}

A function that safely returns a pointer to one of the fields looks like this:

fun get_b_ref {l:addr} (pf: X @ l | x: ptr l):
              [l2:addr] (int @ l2, int @ l2 -<lin> X @ l | ptr l2) =
let
  val p = &(x->b)
  prval pf = view@ (x->b)
in
  #[.. | (pf, llam pf => let
          prval () = view@ (x->b) := pf
        in
          view@ (!x)
        end
    | p)]
end

This can look imposing if you're not familiar with ATS. What does this all mean? Once you're familiar with ATS you can read this as get_b_ref takes a pointer to an X and a proof that you can use it. It consumes this proof meaning we can't access the X object after calling. It returns a pointer to an int - one of the internal fields of X - and provides a proof to use it as an int. It also returns a proof function that consumes that proof of an int and returns the original proof that there is an X at l - allowing you to use the original x as an X again and preventing using the returned pointer to an int due to the proof allowing you to use that getting consumed.

In more detail, it defines a function, get_b_ref, that takes a pointer to an X object as an argument: (pf: X @ l | x: ptr l). The items to the left of the | are proof arguments and only exist at type checking time. This says that pf contains a proof that an object of type X exists at address l. The l is defined in the {l:addr} section of the function declaration meaning l is a memory address. The items to the right of the | are normal values. In this case, x is a pointer with address l. Because we have a pointer at address l and a proof that an object of type X exists at l we can treat the pointer safely as being a pointer to an X. The function consumes the proof when called. That means that the proof cannot be used again so we can no longer treat x as a pointer to an X. It's a pointer to something we can't do anything with after calling.

The result of the function comes after the : symbol. The (int @ l2, int @ l2 -<lin> X @ l | ptr l2) is the meat of it. Again, proofs are to the left of the | and normal values to the right. In this case the right is ptr l2 which means a pointer of some address, l2, is returned. The intent of the function is to return an internal pointer to one of the int fields so we'd expect to have it return a proof that l2 points to an int. The proof returned is a tuple: (int @ l2, int @ l2 -<lin> X @ l).

The first field of that tuple is int @ l2 which is the proof we expected. So a caller of this function will have a pointer to an int and the proof to use it as such. The second field of the tuple is int @ l2 -<lin> X @ l. This is the syntax for declaring an anonymous function type. The items to the left of the -<...> are the arguments to the function and the items to the right are the return value. The second field of the tuple is therefore a function that takes a proof that an int exists at address l2 and returns a proof that an X exists at l. The lin means this function is linear - it can only be used once. Because this tuple appears in the proof section of the result, this anonymous function is a proof function - it is called at type checking time.

The implementation of the function gets a pointer to the b field of the object and a proof that we can use it:

val p = &(x->b)
prval pf = view@ (x->b)

The prval line is proof code that runs at type checking time. view@ is a ATS keyword that gets the proof for an object if we can access it. Once we get a proof using view@ we need to return it later else the proof checking fails. This is a form of 'borrowing' - we are borrowing the proof to access the internal object and we have to give it back later otherwise we can't access that field again and the compiler complains if we don't give it back.

The main part of the return value is:

(pf, llam pf => let
              prval () = view@ (x->b) := pf
            in
              view@ (!x)
            end
        | p)]

It is a tuple, with two proof arguments and a value. The first proof argument is the proof of int @ someaddress to access the internal field we got earlier using view@. The second is a linear lambda function. That function is what returns the proof back to the view@ for the internal field in this line:

prval () = view@ (x->b) := pf

This is the returning of the proof we borrowed earlier. The linear lambda function returns the view@ of the original X object. The value being returned p is the pointer to the internal field.

The [.. | ] syntax is a way of telling the compiler that the return value is of a particular existential type and that it should compute it from the context of the expression such that it matches the [l2:addr] existential result type we declared in the function declaration. Ideally the compiler would infer this without our help but unfortunately it does not. It will tell us if we get it wrong though.

Usage of the function looks like:

implement main() = let
  var x: X = @{ a=1, b=2 }
  val (pf, pff | p) = get_b_ref(view@ x | &x)
  val _ = !p := 3
  prval () = view@ x := pff(pf)
in
  println!("x.b = ", x.b)
end

A variable x is declared on the stack. We get a pointer to the b field using the function above and set that field via the pointer. We're allowed to do this because we have a proof that p is a pointer to an int via the pf proof variable. Calling get_b_ref makes x no longer usable as get_b_ref consumed the proof to access it. The proof function, pff is used to return the proof to access X so we can then use x again. After that we can't use the internal pointer to b anymore. The compiler prevents the escape of the proof to access the internal pointer from the lifetime of the stack variable x.

Unfortunately this code doesn't work in ATS 2. The equivalent code, which fails to compile, is:

fun get_b_ref {l:addr} .<>. (pf: X @ l | x: ptr l):<>
                            [l2:addr] (int @ l2, int @ l2 -<lin> X @ l | ptr l2) =
let
  val p = addr@(x->b)
  prval pf = view@ (x->b)
in
  (pf, llam (pf) => let
          prval () = view@ (x->b) := pf
        in
          view@ (!x)
        end
    | p)
end

ATS 2 does not allow the use of view@ (!x) inside the lambda if the x comes from outside the lambda as it does in this case. Maybe this will change in future iterations of ATS 2 but currently it does not. One workaround is to resort to embedded C code:

#include "share/atspre_define.hats"
#include "share/atspre_staload.hats"

viewtypedef X = @{
  a= int,
  b= int
}
extern viewtypedef "X" = X

%{
int* get_b_ref(X* x) {
  return &x->atslab__b;
}
%}

extern fun get_b_ref {l:addr} (pf: X @ l | x: ptr l):<>
         [l2:addr] (int @ l2, int @ l2 -<lin> X @ l | ptr l2) = "mac#get_b_ref"

implement main0() = let
  var x: X = @{ a=1, b=2 }
  val (pf, pff | p) = get_b_ref(view@ x | addr@ x)
  val _ = !p := 3
  prval () = view@ x := pff(pf)
in
  println!("x.b = ", x.b)
end

Here the X object is given a name "X" that can be accessed from C using the line:

extern viewtypedef "X" = X

The get_b_ref function is implemented in C and given an extern definition that matches the previous one. Although the C implementation is effectively 'unsafe' code, any calls of get_b_ref from ATS is safe as the type defines exactly what it does. This is an example of implementing a typesafe kernel around potentially unsafe code. In this case there is no runtime overhead as the typesafe kernel is proof code.

Which approach to use depends on the project. Often the overhead of implementing safe pointer code in ATS in terms of satisfying the proofs of the implementation is too much at the time. Embedded C with a safe external definition is a faster approach to get things done. Later the C code could be replaced with proof-correct ATS as desired.

Hopefully this gives some insight in what ATS can do, and gives some appreciation of the simplicity of the approach Rust has taken. ATS tends towards providing the low level tools to build the level of access you want but this has cognitive and syntactic overhead. Once you're famliar with the system it becomes understandable but it's probably not "new user friendly" like Rust is.

Tags: ats 

2017-01-19

Transitioning from ATS1 to ATS2

ATS is a programming language I've used a lot in the past. A new version was released a while ago, ATS2, that resulted in various library and language changes and I never got around to transitioning my code to it. Many of my existing posts on ATS are still relevant but some syntax has changed and many of my examples won't compile in the new system. I'm playing around with ATS 2 now and will note some of the major differences I've encountered in this post to get some of my existing ATS1 examples to build.

The first thing to note is that there's some extensive documentation for ATS2 compared to when I first started learning. This was very helpful in learning the differences.

Starting with a simple 'hello world' program:

implement main0() = print("Hello World\n")

Put in a 'hello.dats' file this can be compiled with:

$ patscc -o hello hello.dats
$ ./hello
Hello World

Notice that the main entry function is called main0. In ATS1 this was main. In ATS2 the use of main is to mirror the C main function in that it can take arguments and return a value:

#include "share/atspre_define.hats"
#include "share/atspre_staload.hats"

implement main(argc, argv) =
  if argc = 2 then
    (print("Hello "); print(argv[1]); print_newline(); 0)
  else
    (print("This program requires an argument.\n"); 1)

main takes the traditional argc and argv arguments that the C language main function takes. The function must return an integer value - in this example 0 for success and 1 for failure. Note the two #include statements. These are boilerplate used by ATS to enable the ATS compiler atsopt to gain access to certain external library packages and the definitions of various library functions.

$ patscc -o hello1 hello1.dats
$ ./hello1
This program requires an argument.
$ ./hello1 World
Hello World

In my Linear Datatypes in ATS article I showed an example of declaring a datatype and folding over it:

datatype list (a:t@ype) =
  | nil (a)
  | cons (a) of (a, list a)

fun {seed:t@ype}{a:t@ype} fold(f: (seed,a) -<> seed, s: seed, xs: list a): seed =
  case+ xs of
  | nil () => s
  | cons (x, xs) => fold(f, f(s, x), xs)

implement main() = let
  val a = cons(1, cons(2, cons(3, cons(4, nil))))
  val b = fold(add_int_int, 0, a)
  val c = fold(mul_int_int, 1, a)
  val () = printf("b: %d c: %d\n", @(b, c))
in
  ()
end

This won't compile in ATS2 due to:

  • add_int_int and mul_int_int don't exist in ATS2. They are replaced with g0int_add_int and g0int_mul_int.
  • printf doesn't exist in ATS2. I don't know of a replacement for this other than multiple print statements.
  • main needs to be main0.

The working ATS2 version becomes:

#include "share/atspre_define.hats"
#include "share/atspre_staload.hats"

datatype list (a:t@ype) =
  | nil (a)
  | cons (a) of (a, list a)

fun {seed:t@ype}{a:t@ype} fold(f: (seed,a) -<> seed, s: seed, xs: list a): seed =
  case+ xs of
  | nil () => s
  | cons (x, xs) => fold(f, f(s, x), xs)

implement main0() = let
  val a = cons(1, cons(2, cons(3, cons(4, nil))))
  val b = fold(g0int_add_int, 0, a)
  val c = fold(g0int_mul_int, 1, a)
  val _ = print("b: ")
  val _ = print_int (b)
  val _ = print (" c: ")
  val _ = print_int (c)
  val _ = print_newline()
in
  ()
end

Compiling this fails at the link stage however:

$ patscc -o test test.dats
/tmp/ccfgUdP6.o: In function `mainats_void_0':
t2_dats.c:(.text+0x138): undefined reference to `atsruntime_malloc_undef'
t2_dats.c:(.text+0x15c): undefined reference to `atsruntime_malloc_undef'
t2_dats.c:(.text+0x180): undefined reference to `atsruntime_malloc_undef'
t2_dats.c:(.text+0x1a4): undefined reference to `atsruntime_malloc_undef'
collect2: error: ld returned 1 exit status

The reason for this is the example uses dynamic memory allocation. ATS2 requires a command line argument to tell it to use the libc functions for allocating and freeing memory:

$ patscc -DATS_MEMALLOC_LIBC -o test test.dats
$ ./test
b: 10 c: 24

The same article shows a linear version of the datatype using dataviewtype:

dataviewtype list (a:t@ype) =
  | nil (a)
  | cons (a) of (a, list a)

fun {a:t@ype} free(xs: list a): void =
  case+ xs of
  | ~nil () => ()
  | ~cons (x, xs) => free(xs)

fun {seed:t@ype}{a:t@ype} fold(f: (seed,a) -<> seed, s: seed, xs: !list a): seed =
  case+ xs of
  | nil () => (fold@ xs; s)
  | cons (x, !xs1) => let val s = fold(f, f(s, x), !xs1) in fold@ xs; s end

implement main() = let
  val a = cons(1, cons(2, cons(3, cons(4, nil))))
  val b = fold(add_int_int, 0, a)
  val c = fold(mul_int_int, 1, a)
  val () = printf("b: %d c: %d\n", @(b, c))
in
  free(a)
end

Here the list type is linear. References to a list value can't be aliased and they must be explicitly consumed. In ATS2 this code now looks like:

#include "share/atspre_define.hats"
#include "share/atspre_staload.hats"

datavtype list (a:t@ype) =
  | nil (a)
  | cons (a) of (a, list a)

fun {a:t@ype} free(xs: list a): void =
  case+ xs of
  | ~nil () => ()
  | ~cons (x, xs) => free(xs)

fun {seed:t@ype}{a:t@ype} fold(f: (seed,a) -<> seed, s: seed, xs: !list a): seed =
  case+ xs of
  | nil () => (s)
  | cons (x, xs1) => let val s = fold(f, f(s, x), xs1) in s end


implement main0() = let
  val a = cons(1, cons(2, cons(3, cons(4, nil))))
  val b = fold(g0int_add_int, 0, a)
  val c = fold(g0int_mul_int, 1, a)
  val _ = print("b: ")
  val _ = print_int (b)
  val _ = print (" c: ")
  val _ = print_int (c)
  val _ = print_newline()
in
  free a
end

This is mostly the same but the implementation of fold is simplified. There is no longer a need to use the "!" suffix when declaring the xs1 variable in the pattern match and the fold@ is not needed. In the cases where it is needed then an @ syntax seems to be used in the pattern match for ATS2:

fun {seed:t@ype}{a:t@ype} fold(f: (seed,a) -<> seed, s: seed, xs: !list a): seed =
  case+ xs of
  | nil () => (s)
  | @cons (x, xs1) => let val s = fold(f, f(s, x), xs1) in fold@ xs; s end

There is some discussion about this in the ATS tutorial but I need to look into it in detail to work out where it is needed now.

Another difference in this example is using datavtype instead of dataviewtype. The ATS2 examples I've seen consistently use the shorter word but the longer one still seems to work.

ATS2 makes more extensive use of templates. One thing that I found a pain point in ATS1 was dealing with higher order functions. ATS has multiple function types. There are functions that have no external environment (eg. plain C functions), closures which contain a pointer to an environment, linear closures where the closure envionment must be explicitly free'd, etc. (see closures in ATS for some examples). Writing higher order functions like map and filter would often require implementing a version for each type of function with duplicated boilerplate code.

The ATS2 library uses function templates specialized within the implementation of higher order functions to deal with this boilerplate. Here is an example of the technique adapted from Programming in ATS:

#include "share/atspre_define.hats"
#include "share/atspre_staload.hats"

datatype list (a:t@ype) =
  | nil (a)
  | cons (a) of (a, list a)

extern fun{a:t@ype}{b:t@ype} map$impl(x: a): b

fun{a:t@ype}{b:t@ype} map(xs: list a): list b = let
  fun loop(xs: list a): list b =
    case+ xs of
    | nil () => nil ()
    | cons(x, xs) => cons(map$impl<a><b>(x), loop(xs))
in
  loop(xs)
end

This implements a 'map' template function that takes a list of type a and returns a list of type b. It iterates over the list calling another template function called map$impl on each element and conses up the result. The map$impl function takes an a and returns a b. It is left unimplemented so far. The following is an implementation of a map that applies a function over the list:

fun{a:t@ype}{b:t@ype} map_fun(xs: list a, f: a -<fun> b) = let
  implement map$impl<a><b> (x) = f(x)
in
  map<a><b>(xs)
end

Here the map$impl function is implemented internally to map_fun to call the passed in function. The version that uses a closure does the same:

fun{a:t@ype}{b:t@ype} map_clo(xs: list a, f: a -<cloref> b) = let
  implement map$impl<a><b> (x) = f(x)
in
  map<a><b>(xs)
end

In this way the code that does the looping and mapping is implemented once in the map function and shared amongst the implementations that take the different function types. The caller doesn't need to know about templates to use it:

implement main0() = let
  val n = 5
  val a: list int = cons(1, cons(2, cons(3, cons(4, nil))))
  val b = map_fun(a, lam(x) => x * 2)
  val c = map_clo(a, lam(x) => x * n)

in
  ()
end

A lot of the ATS library implementation seems to take this approach, with template specialisation being used to extend it.

There are other additions to ATS2 that I haven't looked at yet. The constraint solver can be replaced with an external solver like Z3. There are backends for other languages, including JavaScript. There's a Try ATS online service for trying out the language and support for a C++ FFI.

I probably won't rewrite my existing ATS1 posts to be ATS2 compatible but will write about any changes needed to get things to compile if they're non-obvious.

Tags: ats 

2017-01-18

Running X11 apps in an rkt container

rkt is a container runtime I've been using on a few projects recently. I was creating a container for Mozart which uses emacs as an IDE. This requires running an X11 application within the container and have it displayed on the host display.

To get this working I needed to mount my hosts X11 unix domain socket inside the container and provide an Xauthority file that gave the container the rights to connect to the host X server.

The following shell commands use acbuild to create a container that runs xclock as an example of the process:

acbuild begin docker://ubuntu:16.04
acbuild set-name bluishcoder.co.nz/xclock
acbuild run -- apt install --no-install-recommends --yes x11-apps
acbuild run -- rm -rf /var/lib/apt/lists/*
acbuild environment add DISPLAY unix$DISPLAY
acbuild environment add XAUTHORITY /root/.Xauthority
acbuild mount add x11socket /tmp/.X11-unix
acbuild mount add x11auth /root/.Xauthority
acbuild set-exec xclock
acbuild write --overwrite xclock.aci
acbuild end

It uses an Ubuntu Linux image from the Docker hub as a base and installs x11-apps. To reduce disk space it removes cached package files afterwards. A DISPLAY environment variable is set to point to use the same DISPLAY as the host. The XAUTHORITY enviroment variable is set to point to a file in the home directory of the root user in the container.

The mount subcommands expose the x11socket and x11auth endpoints to point to where the X11 unix domain socket and the Xauthority file are expected to be. These will be provided by the rkt invocation to mount host resources in those locations.

The final part of the script sets the executable to be xclock and writes the aci file.

On the host side we need to create an Xauthority file that provides the container access to our X11 server. This file needs to be set so that any hostname can connect to the X11 server as the hostname for the container can change between invocations. To do this the authentication family in the file needs to be set to FamilyWild. I got the steps to do this from this stack overflow post:

xauth nlist :0 | sed -e 's/^..../ffff/' | xauth -f myauthority nmerge -

This will retrieve the Xauthority information for display :0 and modify the first four bytes to be ffff. This sets the authority family to FamilyWild. A new file called myauthority is created with this data. This file will be mapped to the x11auth mount point in the container.

The container can be executed with rkt:

rkt run --insecure-options=image xclock.aci \
        --volume x11socket,kind=host,source=/tmp/.X11-unix \
        --volume x11auth,kind=host,source=./myauthority

The --volume command line arguments map the mount points we defined in the acbuild commands to locations on the host. The running xclock application should now appear on the host X11 display.

Tags: rkt 

2016-08-30

Kicking the tires of Shen Prolog

Shen is a lisp based programming language with some interesting features. Some of these include:

It's the last point I want to look at in this post. I've been doing some programming in Prolog recently and wanted to explore how to do similar things in Shen. This post compares some prolog examples to the equivalent Shen prolog to compare the differences.

Installing

There are quite a few options for installing Shen. For this post I used shen-scheme running on chibi-scheme.

First I installed Chibi:

$ git clone https://github.com/ashinn/chibi-scheme/
$ cd chibi-scheme
$ sudo make install

Then shen-scheme:

$ git clone https://github.com/tizoc/shen-scheme
$ cd shen-scheme
$ make
$ chibi-scheme -Rshen.runner
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Scheme, implementation: chibi-scheme
port 0.14 ported by Bruno Deferrari

(0-) 

There is a JavaScript port of Shen that is available online to try that may work for these examples depending on browser support. I was able to use it in Firefox.

For prolog I use SWI Prolog. This comes with many great libraries and examples to use prolog for 'real world' use cases. The examples can be tried online using Swish.

Member of a list

A popular example of using prolog is the member function (here I use mem to not clash with a builtin member function):

mem(X, [X|_]).
mem(X, [_|Y]) :- mem(X, Y).

In prolog syntax a variable is in uppercase and a list is destructured into its head and tail using the syntax [Head | Tail]. The first rule states that X is a member of a list if it appears at the head of the list. The second rule states that X is a member of a list if it is member of the tail of the list.

Some examples of membership testing (?- is the prolog prompt):

?- mem(1,[1,2,3]).
true

?- mem(3,[1,2,3]).
true

Thanks to the magic of prolog it's possible to use the same function to enumerate all items of the list:

?- mem(X,[1,2,3]).
X = 1 ;
X = 2 ;
X = 3.

In this case the prolog toplevel first gives the result X = 1 with a prompt to continue. Using ; prints each result in turn. The query can be read as "What value of X, given the following list, will return true for a call to mem".

The prolog function findall can be used to return a list of all results without needing interaction from the toplevel:

?- findall(X, mem(X, [1,2,3]), Y).
Y = [1, 2, 3].

findall binds to the third argument a list containing all the values of the first argument when substituted in the query in the second argument that result in true. In this case a 1, 2 or 3 value of X results in mem(X, [1,2,3]) being true.

Shen prolog uses s-expression syntax and requires a defprolog construct to introduce rules. The equivalent to the mem function above would be:

(defprolog mem
  X [X|_] <--;
  X [_|Y] <-- (mem X Y);
)

Shen uses '<--' in place of the prolog ':-' syntax, ';' in place of '.' and calls are made in s-expression format. Calling prolog definitions requires the use of prolog?. The membership testing examples become (the (1-), etc are Shen prompts):

(1-) (prolog? (mem 1 [1 2 3]))
true

(2-) (prolog? (mem 3 [1 2 3]))
true

Shen has the equivalent of prolog's findall:

(3-) (prolog? (findall X [mem X [1 2 3]] Y)
              (return Y))
[3 2 1]

Note that the second argument to findall needs to be an atom. In this case, a list (hence the square brackets), not an s-expression function call. To get the actual results of the Y variable the return function is used. return terminates a prolog query and returns the value of its argument.

Appending lists

Another common prolog example is appending two lists. Given the call append(X, Y, Z), Z will contain the result of appending Y to X:

app([],Y,Y).
app([H|T],Y,[H|T2]) :- app(T, Y, T2).

This states that appending an empty list to a second list results in the second list. Appending a list X and Y will put the head of X at the head of the result and recursively call append with the tail of the first list, the original second list and the currently unbound tail of the result list.

All three arguments can be unbound when calling app. Here are some examples:

# Is [1] appended to [2] the list [1,2]
?- app([1],[2],[1,2]).
true.

# What is the result of appending [1,2,3] and [4,5,6]
?- app([1,2,3],[4,5,6],X).
X = [1, 2, 3, 4, 5, 6].

# What list, when appended to [7,8,9] produces [4,5,6,7,8,9]
?- app(X,[7,8,9],[4,5,6,7,8,9]).
X = [4, 5, 6] ;

# What lists can be append to each other to produce [1,2,3]
?- findall([X,Y], app(X, Y, [1,2,3]), Z).
Z = [
      [[],        [1, 2, 3]],
      [[1],       [2, 3]],
      [[1, 2],    [3]],
      [[1, 2, 3], []]
    ].

The direct translation to Shen prolog is:

(defprolog app
  [] Y Y <--;
  [H|T] Y [H|T2] <-- (app T Y T2);
)

/* Is [1] appended to [2] the list [1 2] */
(4-) (prolog? (app [1] [2] [1 2]))
true

/* What is the result of appending [1,2,3] and [4,5,6] */
(5-) (prolog? (app [1 2 3] [4 5 6] X)
              (return X))
[1 2 3 4 5 6]

/* What list, when appended to [7,8,9] produces [4,5,6,7,8,9] */
(6-) (prolog? (app X [7 8 9] [4 5 6 7 8 9])
              (return X))
[4 5 6]

/* What lists can be append to each other to produce [1,2,3] */
(7-) (prolog? (findall [X Y] [app X Y [1 2 3]] Z)
              (return Z))
[[[1 2 3] []]
 [[1 2]   [3]]
 [[1]     [2 3]]
 [[]      [1 2 3]]
]

Factorial

One way of defining factorial in Prolog is:

fac(0,1).
fac(N,R) :- N > 0,
            N1 is N - 1,
            fac(N1, R1),
            R is N * R1.

The is predicate in prolog is used for binding the result of arithmetic expressions to a variable. Use of fac looks like:

# Is 120 the factorial of 5
?- fac(5,120).
true ;

# What is the factorial of 10?
?- fac(10, X).
X = 3628800 ;

# What factorial gives the result of 5040?
?- fac(X, 5040).
ERROR: >/2: Arguments are not sufficiently instantiated

Note that in this case the backtracking to compute the answer to the last question was not possible. This is because of the way prolog handles boolean and arithmetic expressions. They are non-logical operations and are calculated using an arithmetic evaluator using efficient system arithmetic. Many prolog systems provide a way around this using constraint logic programming which I'll demonstrate later.

Translating to Shen prolog:

(defprolog fac
  0 1 <--;
  N R <-- (when (> N 0))
          (is N1 (- N 1))
          (fac N1 R1)
          (is R (* N R1));
)

The boolean comparison is introduced using the Shen prolog when function. The is predicate becomes the is function. Other than this the translation is straightfoward as is usage:

# Is 120 the factorial of 5
(8-) (prolog? (fac 5 X) (identical X 120))
true

# What is the factorial of 10?
(9-) (prolog? (fac 10 X) (return X))
3628800

# What factorial gives the result of 5040?
(10-) (prolog? (findall X [fac X 5040] Y) (return Y))
invalid type, expected Number: (#(shen.pvar 2))

Note the use of identical in the first example. My first attempt at trying the direct prolog translation gave the following:

(8-) (prolog? (fac 5 120))
vector-ref: not a vector: (120)

I raised a question on the mailing list about it and the answer was that is in Shen Prolog was specifically designed to bind a variable and it has found a number and not a variable. The use of identical was suggested for the solution.

In the third example backtracking doesn't work with arithmetic expressions in Shen prolog as in the Prolog example.

As mentioned previously, many prolog systems include constraint logic programming libraries that can be used to provide backtracking with arithmetic. This is the equivalent factorial programming using one such library in SWI Prolog:

:- use_module(library(clpfd)).
fac(0,1).
fac(N,R) :- N #> 0,
            N1 #= N - 1,
            R #= N * F1,
            fac(N1, F1).

?- fac(X,5040).
X = 7 ;

Databases

A common use of prolog is querying databases of facts. An example from here presents some bible facts and queries:

parent(abraham,ismael).
parent(abraham,isaac).
parent(isaac,esau).
parent(isaac,iacob).

# Did Abraham have children
?- parent(abraham, _).
true ;

# All the father/son pairs
?- findall([F, S], parent(F, S), Y).
Y = [[abraham, ismael], [abraham, isaac], [isaac, esau], [isaac, iacob]].

# Find the grandchildren of abraham
?- findall(G, (parent(abraham, X), parent(X, G)), Y).
Y = [esau, iacob].

Translating to Shen prolog:

(defprolog parent
  abraham ismael <--;   
  abraham isaac <--;
  isaac esau <--;
  isaac iacob <--;
)

/* Did Abraham have children */
(11-) (prolog? (parent abraham _))
true

# All the father/son pairs
(12-) (prolog? (findall [F S] [parent F S] Y) (return Y))
[[isaac iacob] [isaac esau] [abraham isaac] [abraham ismael]]

# Find the grandchildren of abraham
(defprolog grandchild
  F G <-- (parent F X) (parent X G);
)

(13-) (prolog? (findall G [grandchild abraham G] Y) (return Y))
[iacob esau]

In the last example I had to add a new relation for grandchild as I could not see a way of including multiple clauses in findall as the prolog example did.

Calling Prolog to Shen and vice versa

Calling from prolog to Shen can be done with the is function as shown previously with arithmetic:

(defprolog hi
  N <-- (is _ (output "Hello ~S~%" N));
)

(14-) (prolog? (hi "World"))
Hello "World"

It's also possible to use return to return the result of a Shen expression to the top level:

(defprolog double
  X <-- (return (* X 2));
)

(15-) (prolog? (double 5))
10

To pass values from Shen to prolog in variables, use receive to bind a prolog variable with the equivalent shen variable. Given the Shen prolog version of factorial earlier it can be called from a Shen function as follows:

(define shen-fac
  N -> (prolog? (receive N)
                (fac N R)
                (return R)))
shen-fac

(16-) (shen-fac 5)
120

Shen functions are introduced using define and arguments are pattern matched similar to ML-like languages. The arguments to pattern match against appear first, followed by -> and then the body to be run if that pattern matched. In this case the shen-fac function is defined to take one argument, N.

Palindromes

This one is a bit of a prolog mind bender and makes use of difference lists. The goal is to have a predicate, palindrome, that is true if the list given to it is a palindrome. That is, the list is the same when read forwards or backwards. The description of the solution is based on this stackoverflow answer.

In a difference list a list is represented as the difference between a normal list and some sublist of the tail of that list that is unknown. So if (X,Y) represents a difference list of list X that has some tail Y then an empty list would be represented as (Xs, Xs). That is, if Xs is the tail of a difference list Xs, then the actual list it represents is the empty list. A single element dffference list is ([X|Xs], Xs) which is a list containing X as the head and any tail, where the difference is that tail. Notice the tails here are unbound - they have no actual concrete representation and any tail would work.

Difference lists are useful for things like efficient concatenation since only binding the tail of a list is needed to concatenate. Given a difference list ([1 2 3|X], X) and ([4 5 6|Y], Y), the concatenation of the two only requires binding X to [4 5 6|Y], giving the difference list ([1 2 3 4 5 6|Y],Y). No copying of lists needs to occur and the concatenation is done in constant time.

In the following example the idea is used to determine if a list is a palindrome. Here is the prolog code:

palindrome(L, L).
palindrome([_|L], L).
palindrome([E|Xs], Tail)  :- palindrome(Xs, [E|Tail]).

palindrome takes two arguments to represent the difference list. The first clause states that the difference list (L,L) is always a palindrome. A difference list where its tail is the list itself is an empty list as described previously and an empty list is always a palindrome.

The second clause states that a single element list is always a palindrome. As noted before, a difference list ([X|Xs], Xs) is a single element list containing X.

The third clause is describing that for a list with more than one element to be a palindrome it must be of the form E ... E, where E is a single element and ... is the elements between them and those elements are also a palindrome. Using difference lists the list will have some tail, Tail. This means that E ... E | Tail is a palindrome if ... is a palindrome and Tail is the ignored part of difference list to be subtracted.

So the head of the third clause obtains the first element of the list with [E|Xs] and some Tail for the difference. It states that this is a palindrome if the difference list (Xs, E|Tail) is also a palindrome. And this matches our explanation in the previous paragrah - E ... E | Tail is a palindrome if ... is a palindrome where ... is Xs in our clause.

Using difference lists to solve palindromes allows efficiently pattern matching against the last item of the list - the Tail part of the difference list is effectively used as a pointer to the end of the list so the match against E ... E can be done.

Prolog usage example:

?- palindrome([1,2,2,1],[]).
true ;

?- palindrome([1],[]).
true ;

?- palindrome([1,2,3],[]).
false.

Prolog can even generate solutions interactively:

?- palindrome(X, []).
X = [] ;
X = [_4402] ;
X = [_4402, _4402] ;
X = [_4402, _4414, _4402] ;
X = [_4402, _4414, _4414, _4402] ;
X = [_4402, _4414, _4426, _4414, _4402] ;
X = [_4402, _4414, _4426, _4426, _4414, _4402] .

Note how the list contains anonymous elements but are palindromes.

The translation to Shen is:

(defprolog palindrome
  L L <--;
  [_|L] L <--;
  [E|Xs] Tail <-- (palindrome Xs [E|Tail]);
)

(17-) (prolog? (palindrome [1 2 2 1] []))
true

(18-) (prolog? (palindrome [1] []))
true

(19-) (prolog? (palindrome [1 2 3] []))
false

I've not found a way to interactively generate solutions as in the prolog example.

Wrapping the Shen prolog definition of palindrome into a Shen function for easy use from programs can be done with:

(define palindrome?
  L -> (prolog? (receive L) (palindrome L [])))

(20-) (palindrome? [a b b a])
true

Conclusion

There are other features of Shen prolog, including an equivalent of cut, other builtin functions and the ability to suspend unification and use pattern matching in places for efficiency. These are described in The Book of Shen.

The typechecker for Shen is implemented using the prolog facilities in Shen.

For more information on Shen, try:

Tags: shen  prolog 


This site is accessable over tor as hidden service mh7mkfvezts5j6yu.onion, or Freenet using key:
USK@1ORdIvjL2H1bZblJcP8hu2LjjKtVB-rVzp8mLty~5N4,8hL85otZBbq0geDsSKkBK4sKESL2SrNVecFZz9NxGVQ,AQACAAE/bluishcoder/-44/


Tags

Archives
Links