Other articles

  1. Prolog Programs, Order of Evaluation, and Functional Equivalents

    While teaching Prolog this semester I had a few thoughts about Prolog programs and their equivalent programs in a functional programming language like Haskell.


    The Peano Naturals

    The Peano numbers are a unary number system for positive natural numbers where the zero is represented by a Z (or 0, or any atom - it doesn't matter) and every successor of a natural number N is the function S applied to N. We would therefore represent the natural number 3 with the term S(S(S(Z))). To look at it differently: in the Peano axioms, the naturals are defined as the set that contains zero and a closure over the successor function. In haskell we would define the type of the naturals like this:

    data N = Z | S N
    

    In Prolog we don't need a type definition for the naturals, as terms are generated without types. Now we want a predicate that checks whether our input is a natural number as we've defined it. The idea is that the term is a natural, iff either the term is a Z or it has an S as its root and its parameter is a natural. In Prolog we would write it intuitively like this:

    naturals(z).
    naturals(s(X)) :- naturals(X).
    

    And indeed this checks whether our input is a natural number. The query naturals(s(s(z))). returns true while naturals(foo). does not. Writing down this program in Haskell is not very useful since the type system does not allow us to have anything else but a natural as the function parameter but let's pretend:

    naturals v = case v of
                  S x -> naturals x
                  Z -> True
                  _ -> False
    

    And of course, calling naturals $ S $ S Z in haskell has the correct type and returns true. But this haskell program only corresponds to the case where we actually call the Prolog predicate with a bound parameter. We could call the prolog predicate with a free binding pattern like naturals(X). and get bindings for X for every solution, so every natural number. The corresponding Haskell programm would be:

    naturals_f  = [ Z ] ++ map S naturals_f
    

    This might need some explaining: The list corresponds to some notion of non-determinism. In Prolog the non-determinism is baked into the language due to backtracking from failed predicate evaluations and us asking for mor answers. The Prolog program essentially says: Z is a solution. Everything with an S is a solution, if the "content" of the S is a solution as well. That's the same for our haskell programm. In our list of solutions we know that Z is in it and for every solution we have, adding an S leads to another one. And evaluating naturals_f starts to calculate the infinite list of natural numbers.

    Now consider the following Prolog program where we switched the order of the clauses:

    naturals(s(X)) :- naturals(X).
    naturals(z).
    

    This still works nicely for the bound case where we call naturals(s(s(z)). But if we now call naturals(X) we quickly get ERROR: Out of local stack. The natural intuition might be that the order of clauses does not matter but it does in this case. Writing down the equivalent Haskell programm we are able to see why:

    naturals_f  = map S naturals_f ++ [ Z ]
    

    We have the recursion before we have any solution. Well, the solution is easy: just write the simple case in the first line and the recursive case in the second. But let's consider another problem.

    Repeated Printing

    Consider the problem of repeatedly printing a character:

    repeat(0, _).
    repeat(N, C) :- write(C), NN is N - 1, repeat(NN, C).
    

    This looks very correct and is very wrong.

    ?- repeat(5, f).
    fffff
    true ;
    ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...
    

    Now we see why it's nice to represent the naturals als Peano numbers. After hitting 0 there's a choice point left and asking for another solution leads to the negatives and printing our character in an infinite loop. So let's augment the second rule to prevent us from going into the negatives.

    repeat(0, _).
    repeat(N, C) :- N > 0, write(C), NN is N - 1, repeat(NN, C).
    % query:
    ?- repeat(5, f).
    fffff
    true ;
    false.
    

    This looks better but we still have a choice point left over which might be not so nice. The problem is that the matched patterns are not disjoint and after the end of the recursion there's still a pattern left over that fits. We can't encode that N should be larger than 0 in the head of the rule. Remember that we can match naturals larger than 0 (or any other number) in the rule head using Peano numbers - that's why they are so cool.

    But how do we fix our problem with the left-over choice point? There are two ways we can do it. We can either introduce a cut or reorder the rules.

    % Variant 1a: The order doesn't matter but we introduce a cut
    repeat(0, _) :- !.
    repeat(N, C) :- N > 0, write(C), NN is N - 1, repeat(NN, C).
    
    % Variant 1b: If we promise to be good and only call repeat with a positive numeric argument, we can even leave out the range check
    repeat(0, _) :- !.
    repeat(N, C) :- write(C), NN is N - 1, repeat(NN, C).
    
    % Variant 2: The order does matter
    repeat(N, C) :- N > 0, write(C), NN is N - 1, repeat(NN, C).
    repeat(0, _).
    

    I personally think that the variant without the cut is nicer. So for terminating rules, it might be better to have the "smaller" rule last as to not leave choice-points hanging around. Of course, this only works if the matched terms in the rules are proper subsets of each other so that we actually can order the rules in that fashion. In general, that might not be possible.

    Conclusion

    • The order of rules can (in theory) not affect termination. But if our rules are already non-terminating for our query, the order and timeliness of results does matter. Then order does matter.
    • Disjoint rule heads are important to not have left-over choice points.
    • If rules are terminating but the rule heads are not disjoint, they still should be ordered carefully.
    • Implicit conditions (N > 0) can lead to non-obvious non-termination if they are not made explicit.
    • By encoding data properties in the term structure we can make some implicit conditions explicit and make rule-heads disjoint.
    • Having numerical conditions in rule-heads would be really nice. Maybe some Prolog implementation in the future allows for that.

  2. Clojure and the Mandelbrot set on LEGO Mindstorms EV3

    The LeJOS operating system for LEGO Mindstorms EV3 is, as I said before, a small Linux with an embedded JVM.


    Running Clojure:

    To run Clojure on the EV3 I had to download the Clojure runtime, unzip it and throw away everything but the actual jar-file clojure-1.8.0.jar.

    Then the jar-file needs to be transfered to the EV3 (via scp for example) and can be executed via ssh with jrun -jar clojure-1.8.0.jar (I already have an alias in my ~/.ssh/config for the EV3). After about two minutes we have a Clojure repl that we can use to answer the important questions of our time.

    Takes about two minutes to start the repl

    Actually coding something:

    The first thing we have to notice is, that the leJOS menu stays visible when we opened the clojure repl. This is a problem insofar, that when we use the Clojure code to interact with (for example) the display, both the leJOS menu and our application want to use the display and their interactions will overlap in unpredictable ways (for me both images were "fighting", but the system might as well crash).

    So I created a shell script that kills the existing java process and opens it again once our command ran.

    #!/bin/sh
    killall java
    jrun # ... we will look at that later
    ~/lejos/bin/startmenu &
    

    Now we want to actually write Clojure code where we calculate members of the Mandelbrot set. The Mandelbrot set is the set of all numbers \(c\) for which \(z_n\) with \(z_0 = 0\) and \(z_{n+1} = z_{n}^2 + c\) does not diverge (when \(n\) goes to infinity). This is calculated in the complex plane. The numbers for which this doesn't diverge are usually drawn in black while the diverging numbers remain white.

    I looked for a Java-based library for the complex numbers and found one with Apache. This library was insofar underwhelming, that taking a complex number to the power of an arbitrary Integer doesn't work as one expects. The library always uses the following equivalence: \(y^x = exp(x \times log(y))\) which is fine in general but doesn't work if \(y\) is zero, which is the base case but also no problem with positive integer powers. Took me an hour because that is not at all well documented (for the integer-case). So the first thing is, to write our own pow function: (defn pow [y, x] (if (.equals y Complex/ZERO) y (.pow y x)))

    Now we can define both \(z_n\) and whether any \(z_n\) diverges:

    (defn zn [n, c] ( if (== n 0) Complex/ZERO (.add c (pow (zn (- n 1) c) 2.0 ) ) ))
    (defn diverges [x] (or (.isNaN x) (.isInfinite x) (< 2.0 (.abs x))))
    

    And the idea is, to set the whole display to black and evaluate for every black pixel \(z_1\) and then for every remaining black pixel \(z_2\). Once a pixel was set to white, we no longer need to evaluate it, because we already know it diverges.

    So here's the full code for mb.clj:

    (import [org.apache.commons.math3.complex Complex])
    (import [lejos.hardware.lcd LCD])
    (import [lejos.utility Delay])
    
    (defn pow [y, x] (if (.equals y Complex/ZERO) y (.pow y x) ))
    (defn zn [n, c] ( if (== n 0) Complex/ZERO (.add c (pow (zn (- n 1) c) 2.0 ) ) ))
    (defn diverges [x] (or (.isNaN x) (.isInfinite x) (< 2.0 (.abs x))))
    
    (defn scale_x [x] ( - (/ (* 2.5 x) LCD/SCREEN_WIDTH ) 2.0 ))
    (defn scale_y [y] ( - (/ (* 2.0 y) LCD/SCREEN_HEIGHT) 1.0 ))
    
    (doseq [x (range  LCD/SCREEN_WIDTH )
            y (range  LCD/SCREEN_HEIGHT)] (LCD/setPixel x y 1))
    
    (doseq [rep (range 1 1000)]
      (doseq [x (range  LCD/SCREEN_WIDTH )
              y (range  LCD/SCREEN_HEIGHT)]
              (
                  if (== 1 (LCD/getPixel x y))
                  (if (diverges (zn rep (Complex. (scale_x x) (scale_y y)))) (LCD/setPixel x y 0))
              )
      )
    )
    

    We don't need a delay at the end because this will take long enough.

    But now we have to think about running this. Basically we need to include every jar we use into the java classpath and then run the clojure main with our script as the parameter. For org.apache.commons.math3 we need the commons-math3-3.6.1.jar from Apache and for the lejos namespace we need the ev3classes.jar from leJOS (which is not included on the system because it is usually compiled into the finished jar).

    Once this is all done we can basically run our application with jrun -cp "../ev3classes.jar:./commons-math3-3.6.1.jar:../clojure-1.8.0.jar" clojure.main mb.clj.

    After a few hours, it will look like this

    I am pretty sure it is possible to compile the whole jar with the correct main using eclipse/ant and whatnot. But that's the first successful experiment in this direction. Here's a timelapse of the program in action.


  3. Upgrading Fedora 24 to 25

    Fedora 25 was released a few days ago.

    I've upgraded one of my machines. The others are soon to follow. Fedora 25 switches from X11 to Wayland as a default. For my laptop I had to switch last release because my laptop's touchpad was nowhere to be found in X. For this release I am looking forward to not getting to play games on my main desktop. I am sure to blog about any problems I happen upon.

    If you're running Fedora 24 you can easily upgrade to Fedora 25 running the following console commands. But before that, make sure your system is fully upgraded and rebooted, especially if you installed some kernel updates.

    sudo dnf install dnf-plugin-system-upgrade
    sudo dnf system-upgrade download --releasever=25 --allowerasing
    

    The --allowerasing argument allows some packages to be deleted during the process. I had some dangling haskell packages, that needed to be deleted. No problem there.

    Once all the downloads are done, type sudo dnf system-upgrade reboot to reboot your system starting the actual upgrading process.


    And yeah, I broke my work setup that used proprietary NVidia drivers to get a second monitor running.


Page 1 / 6 »

links

social

Theme based on notmyidea