Bittis Blog - ramblings of a (half) bitter mind

Logtalk - Hello World

2009-12-18T01:44:00.011+01:00

According to the SWI-Prolog Mailing List, ...

Logtalk is an object-oriented logic programming language that can use most
Prolog implementations as a back-end compiler. As a multi-paradigm language, it includes support for both prototypes and classes, protocols (interfaces), component-based programming through category-based composition, event-driven programming, and high-level multi-threading programming.

For this, it seems worth trying Logtalk in order to lift Prolog programming to a different level (more contained). As usually, the first program show-casing some programming language is the famous "hello world" program. Unlike, other programming languages the Prolog version of "hello world" is a family relation.

Since this post is merely to maintain flow, I will present a "hello world" in Logtalk. Logtalk helps decomposing program logic by offering the well known concept of object and interface (including visibility of object members).

Behold .. the magic "hello world":


:- object(first_program).
  :- public(main/1).

  hello_world(Text) :- write(Text), nl.

  main(Text) :-
    hello_world(Text).

:- end_object.

As can be guessed, the program is quite simple. An object called first program is declared,
offering a publicly visible method called main. main passes one argument, i.e. some text to print, to the famous hello_world procedure. hello_world calls Prolog's write function to write the passed text on some line, adding a newline at the end of the text.

After consulting the program, one may call main using


first_program::main('Hello World').

Prolog – Mindstorms (I)

2009-10-04T12:35:00.001+02:00

The last friday, I received my Lego Mindstorms NXT 2.0 – THANKS! Unfortunately, I lack the necessary power supply in form of 6AA batteries. Clearly, I went to my favorite retailer – Amazon – and ordered a couple of rechargeable ones (including the recharger).

Since my mind is somehow attached to Prolog, I asked myself would it be possible to do the mind-storming in Prolog … so I fired up the information retrieval engine of the day … and hit:

[English] New Mexico State University: Building and Programming Robots
http://www.cs.nmsu.edu/~tson/classes/fall03-579/schedule.htm
[German] University of Potsdam: Programmieren in Prolog
http://www.cs.uni-potsdam.de/wv/03SS/aktuell.html#SECTION00051000000000000000
[German] Toni Gläser: LEGOLOG - Lego Mindstorms und ein Golog-Planer Eine Einführung und ein Überblick über das Konzept und die
Programmierung sowie die Implementation von Aufgaben für
den Roboter
http://www.kbs.uni-hannover.de/~brase/Paper/studienarbeit_Prolog.pdf
[English] Fermé and Gaspar: RCX+PROLOG
A platform to use Lego Mindstorms™ Robots in
Artificial Intelligence courses
http://dme.uma.pt/ferme/Papers/Ferme-Gaspar07.pdf
[English] University of Toronto: Cognitive Robotics
http://www.cs.toronto.edu/cogrobo/main/systems/index.html
[English] Nalepa: Prototype Prolog API for Mindstorms NXT
http://www.springerlink.com/content/9r47108w18835742/

Clearly, I will inspect some of these resources soon to see what’s in the Lego Prolog toolbox. Until then happy robot-building.

Adventures In Prolog - General Reading (2)

2009-09-12T11:24:00.002+02:00

Since I have not posted anything for while, I thought I keep the flow running, by pointing to Boehm's "Document Analysis Experiment" - applied NLP using Prolog.

Taken from the Overview section:

The main purpose of this document analysis program is to count the number of useful words in the document in various ways, and to use NLP to (hopefully)
improve the analysis.

You may find his project useful and interesting - so happy reading.

Adventures In Prolog - ProjectEuler20

2009-08-18T23:44:00.005+02:00

Continuing with the Euler Quest, a simple and straight-forward solution to Project Euler's problem 20 is presented.

The problem statement reads:

Find the sum of the digits in the number 100!

Where ! denotes the faculty operator.

One (simple) way to solve the problem goes as follows:

Firstly, calculate the value of 100!. Secondly, convert the value into a list of digits. Thirdly, sum each digit. Lastly, output the cumulative result.

A translation of this solution may read like:


euler_20_1(F, Out) :-
  fac(F, Fac),
  string_to_list(Fac, CList),
  euler_20_1_t(CList, 0, Out), !.

euler_20_1_t([], Current, Current).

euler_20_1_t([X|Y], Current, Out) :-
  number_chars(N, [X]),
  NewCurrent is Current + N,
  euler_20_1_t(Y, NewCurrent, Out).

The fac predicate computes the faculty of some positive integer number. string_to_list is a built-in predicate converting a string into its character list representation and number chars converts between ascii character code and number. Building only on these relatively few predicates the code should be straight-forward.

Please note, that this solution is not the most efficient, in fact it may not work for very large numbers. To reduce the complexity of the faculty operation, we might additional knowledge like:

multiplying a number n by a multiply of 10 (n mod 10 = 0), does not change the value of the sum of the digits of the result. For example

3*4*10 = 120 but sum_digit(3*4*10) = sum_digit(3*4*100) = sum_digit(3*4) = 3

Now building on such knowledge, one might cut all numbers that multiplied together yield a multiply of 10 from the faculty operation. This approach will be covered in a future post.

On a different side node, a Prolog implementation of the Porter stemming algorithm can be found here.

Adventures In Prolog - Euler7 and the Nth Prime

2009-08-18T10:06:00.005+02:00

Building on our previous prime-related posts, today's post will cover a solution to Project Euler's 7th Problem, i.e. finding the 10001st prime. Now, the solution to this problem can be easily expressed in thought and then converted to some programming language …

Starting with the lowest and first prime – 2 - , we check each subsequent number j > i, for primality. Whenever we find a j such that j is prime, we increment a prime counter c by one and continue testing numbers k > j. This is done until c reaches the number 10001.

The Prolog code below is an expression of this idea, added with some prime numbers found during the process of finding the 10001st prime. This means, given the border of some prime interval, i.e. 100th prime = i and 200th prime = j, we may start looking for the 150th prime within the number interval [i,j], instead of starting at 2 and checking each number until the prime counter reaches 150. Also, we might have defined the euler_7 predicate to be dynamic, i.e. updatable, such that whenever we find some kth prime, it will be stored in the fact database.


%EULER7 the 10001 prime
euler_7(4409, 600) :- !.

euler_7(Out, Xth) :-
  Xth < 600, !,
  euler_7_t(2, 1, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 700, !,
  euler_7_t(4409, 600, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 1000, !,
  euler_7_t(5279, 700, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 1100, !,
  euler_7_t(7917, 1000, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 1200, !,
  euler_7_t(8831, 1100, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 1500, !,
  euler_7_t(9733, 1200, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 2000, !,
  euler_7_t(12553, 1500, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 3000, !,
  euler_7_t(17389, 2000, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 4000, !,
  euler_7_t(27449, 3000, Xth, Out).
  
euler_7(Out, Xth) :-
  Xth < 5000, !,
  euler_7_t(37813, 4000, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 7000,
  euler_7_t(48611, 5000, Xth, Out), !.

euler_7(Out, Xth) :-
  Xth < 10001,
  euler_7_t(70657, 7000, Xth, Out), !.

euler_7(Out, Xth) :-
  euler_7_t(104743, 10001, Xth, Out), !.


euler_7_t(P, Xth, Xth, P) :-
  is_prime(P), !.
  
euler_7_t(NP, Xth, Xth, P) :-
  NewPrime is NP + 1,
  euler_7_t(NewPrime, Xth, Xth, P), !.

euler_7_t(X, Xth, Gth, Prime) :-
  is_prime(X),
  Y is X + 1,
  Yth is Xth + 1,
  euler_7_t(Y, Yth, Gth, Prime), !.

euler_7_t(X, Xth, Gth, Prime) :-
  Y is X + 1,
  euler_7_t(Y, Xth, Gth, Prime).
%EULER7 the 10001 prime

Adventures in Prolog - Some more Primes

2009-07-09T10:10:00.012+02:00

Again, we are going to tackle some problems mentioned in the list of 99-Prolog problems. Today's post builds upon the gcd predicate defined last time to attack problems:

P31 = is_prime

P35 = prime_factors

P36 = prime_factors_mult

P39 = prime_list

Now, building on the previously defined gcd predicate, on may define a prime inductively:

a prime is a number which is only (divisible by one and itself)

the smallest prime is 2

any number greater than 2 is either composite or prime

Building on this definition we may translate the smallest prime into a Prolog predicate quite easily. To determine the primeness/composibility of any number greater than 2, one may use the gcd predicate. Recalling that a prime p is a number which cannot be divided by any number in ]1, p[, the following predicate may be given:


is_prime(2) :- !.
is_prime(3) :- !.
is_prime(X) :-
  X >= 2,
  UpperBound is round(sqrt(X)) + 1,
  is_prime_t(X, 2, UpperBound), !.

is_prime_t(_, UpperBound, UpperBound).
is_prime_t(X, CurrentFactor, UpperBound) :-
  gcd(X, CurrentFactor, GCD),
  GCD = 1, !,
  NewFactor is CurrentFactor + 1,
  is_prime_t(X, NewFactor, UpperBound).

As can be seen above, two elementary cases (2 and 3) are given and any number not 2 or 3 is checked for primeness. Instead of checking composibility of a prime p for any number in ]1, p[, one may use any number in ]1, square_root(p)]. The reason why I used the rounded value of the square root + 1 is the case of checking 4 which would be determined as a prime because of:


is_prime_t(4, 2, 2).

Instead of the + 1, we might also a check on whether some number is even. Since we know that 2 is not only the smallest prime but also the only even prime number, such a check might greatly enhance the solution search.

Using this definition of is_prime, we might define the prime_list predicate quite easily. A prime list is generated from any number within some interval [a, b], which is prime. We might differentiate three cases (where the last is for convenience) in the definition of prime_list:

the interval is [a,b] where a=b

the interval is [a,b] where a<b

the interval is [a,b] where b<a

Case one results in a list containing one prime if a is itself a prime number. Case 3 will be mapped to case 2 where a and b are switched. This results in a possible prime_predicate as follows:


prime_list(X, X, [X]) :-
  is_prime(X), !.

prime_list(X, X, []) :- !.

prime_list(X, Y, L) :-
  X > Y,
  prime_list_t(Y, X, [], L), !.
 
prime_list(X, Y, L) :-
  prime_list_t(X, Y, [], L), !.
 
prime_list_t(X, X, CurrentPrimes, OutPrimes) :-
  is_prime(X), !,
  append(CurrentPrimes, [X], OutPrimes);
  OutPrimes = CurrentPrimes.

prime_list_t(X, Y, CurrentPrimes, OutPrimes) :-
  is_prime(X), !,
  append(CurrentPrimes, [X], NewPrimes),
  Z is X + 1,
  prime_list_t(Z, Y, NewPrimes, OutPrimes).
 
prime_list_t(X, Y, CurrentPrimes, OutPrimes) :-
  Z is X + 1,
  prime_list_t(Z, Y, CurrentPrimes, OutPrimes).

The last problem to cover is the prime factorization of some given number. This problem is handled by the two predicates prime_factors and prime_factors_mult. Where the first contains each (possibly duplicate) prime factor and prime_factors_mult delivers a power representation of the prime factors of some given number. The approach taken is quite simple, again the factorization of a prime number contains itself (and one which is not included). Also, any composite number can be represented uniquely by a product of prime factors. For example, 4 = 2 * 2 or 12 = 2 * 2 * 3. Now, provided this property of a natural number we may define our two predicates like this:


prime_factors(0, []) :- !.
prime_factors(1, []) :- !.
prime_factors(X, [X]) :- is_prime(X), !.
prime_factors(X, Out) :-
  prime_factors_t(X, 2, [], Out), !.
  
prime_factors_t(1, _, Out, Out).

prime_factors_t(X, TestFactor, CurrentFactors, Out) :-
  gcd(X, TestFactor, GCD),
  GCD \== 1, !,
  append(CurrentFactors, [GCD], NewFactors),
  Z is X / TestFactor,
  prime_factors_t(Z, TestFactor, NewFactors, Out).
  
prime_factors_t(X, TestFactor, CurrentFactors, Out) :-
  NewTestFactor is TestFactor + 1,
  prime_factors_t(X, NewTestFactor, CurrentFactors, Out).
  
prime_factors_mult(0, []) :- !.
prime_factors_mult(1, []) :- !.
prime_factors_mult(X, [X]) :- is_prime(X), !.
prime_factors_mult(X, Out) :-
  prime_factors_mult_t(X, 2, 0, [], Out), !.

prime_factors_mult_t(1, _, _, Out, Out).
prime_factors_mult_t(X, X, CurrentPower, CurrentFactors, Out) :-
  Power is CurrentPower + 1,
  append(CurrentFactors, [[X, Power]], Out).

prime_factors_mult_t(X, TestFactor, Power, CurrentFactors, Out) :-
  gcd(X, TestFactor, GCD),
  GCD \== 1, !,
  NewPower is Power + 1,
  Z is X / TestFactor,
  prime_factors_mult_t(Z, TestFactor, NewPower, CurrentFactors, Out).

prime_factors_mult_t(X, TestFactor, Power, CurrentFactors, Out) :-
  Power >= 1,
  append(CurrentFactors, [[TestFactor, Power]], NewFactors),
  NewTestFactor is TestFactor + 1,
  prime_factors_mult_t(X, NewTestFactor, 0, NewFactors, Out).

prime_factors_mult_t(X, TestFactor, Power, CurrentFactors, Out) :-
  Power = 0,
  NewTestFactor is TestFactor + 1,
  prime_factors_mult_t(X, NewTestFactor, 0, CurrentFactors, Out).

Essentially, prime_factors_mult performs the same steps as prime_factors. However, instead of creating a list for some prime factor right from the beginning, the power of that prime factor is accumulated and stored at last.

Happy, Prolog-ing and if you find any errors/typos please report them.

Adventures in Prolog - GCD and Coprime

2009-07-07T22:51:00.005+02:00

Today's post follows the tradition of the my last post, i.e. it continues with another problem stated in the list of 99 Prolog problems. Today, we are going to have a look at problem 32 and 33.

Problem 32 concerns the implementation of a greatest common divisor predicate (gcd). In an earlier post, I implemented a gcd routine in Python. We are going to reuse this definition of gcd here, using a ternary predicate/relation.

The Prolog definition of gcd makes use of gcd's recursive definition, which are:

the gcd of two numbers x and y is equal to the gcd of x - y and y for y <>
the gcd of some number and 0 is the number
the gcd of some number and 1 is 1

Now, given the above properties (and some more) a possible gcd predicate might look like this:


gcd(A, 0, A) :- !. %includes gcd(0,0)
gcd(1, _, 1) :- !.
gcd(A, A, A) :- !.

gcd(A, B, GCD) :-
  A < B, !,
  X is B - A,
  gcd(X, A, GCD).

gcd(A, B, GCD) :-
  X is A - B,
  gcd(X, B, GCD).

Provided the above definition of gcd, the solution to problem P33 is given within the problem statement. For this, a predicate to determine coprimality may be defined as is:


coprime(X, X) :- fail.
coprime(X, Y) :- gcd(X, Y, 1).

Clearly, we could add more clause to avoid a computation of gcd when it is obviously not necessary. However this was omitted here.

Adventures In Prolog - Duplicate List Members

2009-07-03T17:36:00.005+02:00

Today's post is about problem 14 from the list of 99 Prolog problems (see here):


(*) Duplicate the elements of a list.
Example:
?- dupli([a,b,c,c,d],X).
X = [a,a,b,b,c,c,c,c,d,d]

Since the problem is marked with one star, a solution should be within reach. Now, to duplicate each element of the list, we do the following:

We traverse the list element by element until we reach the last element, i.e. the empty list.

For each element (excluding the empty list), the element is added twice to a newly built output list.

Given the above solution statement, a possible translation to Prolog code might look like this:


dupli([], []).
dupli(L, O) :-  dupli_t(L, [], O).

dupli_t([], Current, Current).
dupli_t([H|T], CList, OutList) :-  
  append(CList, [H, H], IntermediateList),  
  dupli_t(T, IntermediateList, OutList).

Adventures in Prolog – A Simple Tokenizer

2009-06-28T14:16:00.009+02:00

Today’s post is concerned with presenting a simple tokenizer that I have written during the last couple of weeks (not full-time off course). The tokenizer’s goal is to – off course – tokenize a provided sentence or input sequence of characters. For example, the following sentence:


“This is my world!”

Should be split up into individual descriptors/ tokens of the respective string part they cover, such as:


Word(This), Space(5), Word(is), Space(8), Word(my), Space(11), Word(world), EndOfSentence(!)

Now, given that the position of a space between characters can be computed by taking the length of the character sequence and adding one to it, we might not need to store the Space explicitly. Also, to avoid verbose representation of tokens we might shorten the name of individual tokens a bit. Since Prolog reserves upper case characters for variables, we might change the casing of tokens too. For example, the above token stream might be collapsed to:


w(This), w(is), w(my), w(world), eos(!)

Now, what difference does it make whether this is written with a capital t or not? Clearly, this is at the beginning of a sentence, but since we now that it is at the beginning of the sentence we might change casing here. Also transforming to lower case characters simplifies the implementation of the tokenizer somewhat, since we don’t need to deal with specific representations of a single character. For this, all characters will be transformed to lower case characters and the above sequence of tokens reduces too:


w(this), w(is), w(my), w(world), eos(!)

Adding a complement to the end of sentence indicator, i.e. beginning of sentence, marks each distinct sentence, such that the above token stream looks like:
bos(i), w(this), w(is), w(my), w(world), eos(!)
i in the bos() token identifies the ith sentence in a set of sentences. As you may see from the above example there are a few situations one wants to deal with in order to tokenize real-world sentences. For this, the tokenizer is spread across several Prolog files, each covering a separate aspect or token. Tokens covered are:

Words
Description: A sequence of letters, possibly containing “-“ (bar), or “’” (apostrophe).
Example: Hello, world, top-down, Mike’s, Andreas’, don’t
Simple Numbers (integer, float)
Description: A sequence of digits, possibly containing a “.” (dot)
Example: 1234, 12.343
Names, Quantities and Abbreviations
Description: special words, stored in a name, quantity, abbreviation map
Example: 5m (five meter), MS (Microsoft)
Unknown and unrecognized character streams
Description: A sequence of arbitrary characters closed by a “ “ (space)
Example: 34sd=+

Please note that in order to identify a sentence, a sentence must be properly terminated with one of the following: ‘.’ (Dot), ‘?’ (Question mark) or ‘!’ (Exclamation mark). Other types of (sub)sentence termination , such as the ‘-‘ (bar), ‘;’, (Semicolon), ‘,’ (comma) are handled as sentence fragment terminators. If you want to use the tokenizer, you may either tokenize a file containing sentences or a string. For this, you may use either of the following predicates:


tokenize_string(+InString, -OutTokenList)

```
tokenize_file(+InFile, -OutTokenList)
```

For example, you might ask:


3 ?- tokenize_string("this is my world!", X).
X = [[bos(0), w(this), w(is), w(my), w(world), eos(!)]].

Or you might ask:


tokenize_file(‘Path to file’, X).

The Prolog source code of the tokenizer can be found here. It is stored as a zip container. You will find the following inside the zip-file:

Prolog source files (extension pl)

Directory “Corpora” with two text files containing some text to test the tokenizer on.

Please note that I do not claim its robustness or coverage of 99% of the possible sentences. Also, performance has not been a major concern for me. For this you will not find the use of difference lists or optimized database access. This might be a future task as well. In fact, this is one of the many open points. However, in case that you do have found a bug, error or recommendation, please do contact me. Currently, I try to add features to the tokenizer and make it more stable. Also, documentation and code cleanup is a item on the to-do list.

Adventures in Prolog - LinkList (2)

2009-06-07T19:45:00.003+02:00

Some time ago, I have done a small tokenizer, which I will present in one of the upcoming posts. However, this post is another link to some Prolog tutorials:

http://www.intranet.csupomona.edu/~jrfisher/www/prolog_tutorial/intro.html

All posted links and links that I will post in the future, will be collected on my Prolog link site at:

http://sites.google.com/site/bittermanpage/Home/prolog-links

This link will be available in the side bar as well.

Adventures in Prolog - LinkList

2009-06-04T13:20:00.001+02:00

Here is a link to the Prolog directory of CMU's AI group:

http://www.cs.cmu.edu/Groups/AI/lang/prolog/

Adventures in Prolog - General Reading (1)

2009-05-25T11:40:00.005+02:00

Today's post is merely the advertisement of a dissertation thesis that might be an interesting read:

Can Logic Programming Execute as Fast as Imperative Programming?
Peter Lodewijk Van Roy

ABSTRACT
The purpose of this dissertation is to provide constructive proof that the logic programming language Prolog can be implemented an order of magnitude more efficiently than the best previous systems, so that its speed approaches imperative languages such as C for a significant class of problems. The driving force in the design is to encode each occurrence of a general feature of Prolog as simply as possible. The resulting system, Aquarius Prolog, is about five times faster than Quintus Prolog, a high performance commercial system, on a set of representative programs. The design is based on the following ideas:
Reduce instruction granularity. Use an execution model, the Berkeley Abstract Machine (BAM), that retains the good features of the Warren Abstract Machine (WAM), a standard execution model for Prolog, but is more easily optimized and closer to a real machine.
Exploit determinism. Compile deterministic programs with efficient conditional branches. Most predicates written by human programmers are deterministic, yet previous systems often compile them in an inefficient manner by simulating conditional branching with backtracking.
Specialize unification. Compile unification to the simplest possible code. Unification is a general pattern-matching operation that can do many things in the implementation: pass parameters, assign values to variables, allocate memory, and do conditional branching.
Dataflow analysis. Derive type information by global dataflow analysis to support these ideas.

The thesis can be found here.

On that note I would like to mention a paper going for a similar direction, actually I found the thesis because of the paper.

Optimizing Prolog for Small Devices: A Case Study
M. Carro, J. Morales, Henk L. Muller, G. Puebla, M. Hermenegildo

Abstract
In this paper we present the design and implementation of a wearable application in Prolog. The application program is a “sound spatializer.” Given an audio signal and real time data from a head-mounted compass, a signal is generated for stereo headphones that will appear to come from a position in space. We describe high-level and low-level optimizations and transformations that have been applied in order to fit this application on the wearable device. The end application operates comfortably in real-time on a wearable computer, and has a memory foot print that remains constant over time enabling it to run on continuous audio streams. Comparison with a version hand-written in C shows that the C version is no more than 20-40% faster; a small price to pay for a high level description.

The paper can be found here.

The reason why posting these documents, is my thinking of maybe porting or reusing an existing Prolog implementation for the Nintendo DS. Unfortunately, I have not made great progress. But with some time, there may be something out there.

Adventures in Prolog - Simplify Sum (4)

2009-05-16T22:17:00.004+02:00

Last post was concerned with implementing the simplification of an additive (compound) term. The proposed solution consists of three elementary steps (sorting, simplifying and reducing). Although the proposed solution is quite flexible, i.e. works on any atom not specifically a single character,
the sorting of characters decreases performance somewhat. For this, this post is concerned with a more targeted approach to the introduced problem.

Given an additive (compound) term containing numbers and (unitary) variable symbols (e.g., a, b, x, y, z), we wish to obtain a reduced form of this term, which simplifies the same variables and sums multiple numbers to one single number.

The following solution makes use of:

The (German and English) alphabet contains only 26 elementary characters (variable symbols)
Character symbols can be ordered according to their occurence within the alphabet.

Instead of operating on additive compound term, the proposed solution operates on a character array , i.e. array indexing individual variable characters. The following solution consists of two main steps:

Simplification of additive (compound) term
Computing a reduced printable form (string) of the simplified term.

Now, given the perimeters of the proposed approach, this is what it looks like:


map_index(a, 1).
map_index(b, 2).
map_index(c, 3).
map_index(d, 4).
map_index(e, 5).
map_index(f, 6).
map_index(g, 7).
map_index(h, 8).
map_index(i, 9).
map_index(j, 10).
map_index(k, 11).
map_index(l, 12).
map_index(m, 13).
map_index(n, 14).
map_index(o, 15).
map_index(p, 16).
map_index(q, 17).
map_index(r, 18).
map_index(s, 19).
map_index(t, 20).
map_index(u, 21).
map_index(v, 22).
map_index(w, 23).
map_index(x, 24).
map_index(y, 25).
map_index(z, 26).
map_index(V, 27) :- number(V).

map_index defines the array index of each variable symbol. index 27 is reserved as the computation cell for numbers.


increment(1, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A1, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- A1 is A + 1.
increment(2, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B1, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- B1 is B + 1.
increment(3, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C1, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- C1 is C + 1.
increment(4, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D1, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- D1 is D + 1.
increment(5, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E1, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- E1 is E + 1.
increment(6, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F1, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- F1 is F + 1.
increment(7, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G1, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- G1 is G + 1.
increment(8, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H1, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- H1 is H + 1.
increment(9, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I1, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- I1 is I + 1.
increment(10, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J1, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- J1 is J + 1.
increment(11, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K1, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- K1 is K + 1.
increment(12, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L1, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- L1 is L + 1.
increment(13, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M1, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- M1 is M + 1.
increment(14, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N1, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- N1 is N + 1.
increment(15, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O1, P, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- O1 is O + 1.
increment(16, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P1, Q, R, S, T, U, V, W, X, Y, Z, NN]) :- P1 is P + 1.
increment(17, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q1, R, S, T, U, V, W, X, Y, Z, NN]) :- Q1 is Q + 1.
increment(18, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R1, S, T, U, V, W, X, Y, Z, NN]) :- R1 is R + 1.
increment(19, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S1, T, U, V, W, X, Y, Z, NN]) :- S1 is S + 1.
increment(20, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T1, U, V, W, X, Y, Z, NN]) :- T1 is T + 1.
increment(21, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U1, V, W, X, Y, Z, NN]) :- U1 is U + 1.
increment(22, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V1, W, X, Y, Z, NN]) :- V1 is V + 1.
increment(23, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W1, X, Y, Z, NN]) :- W1 is W + 1.
increment(24, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X1, Y, Z, NN]) :- X1 is X + 1.
increment(25, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y1, Z, NN]) :- Y1 is Y + 1.
increment(26, _, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z1, NN]) :- Z1 is Z + 1.

increment(27, Inc, [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN],
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, NN1]) :- NN1 is NN + Inc.

increment uses an index and updates the respective variable or number cell. Note that, variables may only be
incremented by one, whereas numbers can be incremented by any other number (adding two numbers).


simplify(In) :-
simplify_a(In, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], OutMap),
print_simplified(OutMap), !.

simplify(_).

simplify_a(X, InMap, OutMap) :-
  atomic(X),
  map_index(X, I),
  print('Index: '), print(I), nl,
  increment(I, X, InMap, OutMap), !.

simplify_a(A + B, InMap, OutMap) :-
  atomic(A),
  atomic(B),
  map_index(A, I1),
  map_index(B, I2),
  increment(I1, A, InMap, TMap),
  increment(I2, B, TMap, OutMap), !.

simplify_a(A + B, InMap, OutMap) :-
  compound(A),
  atomic(B),
  map_index(B, I),
  increment(I, B, InMap, TMap),
  simplify_a(A, TMap, OutMap), !.

simplify_a(_, InMap, InMap).

simplify calls simplify_a, which is responsible for obtaining a simplified representation from some additive term.


print_simplified(In) :-
  print('Result:'), nl,
  str_simplified_t(In, 1, '', OutStr),
  print(OutStr), nl, !.

get_no(_, 0, '').
get_no(Char, 1, Char).
get_no(Char, X, X*Char).

str_simplified_t([0|Rest], Index, TStr, RStr) :-
  Index1 is Index + 1,
  str_simplified_t(Rest, Index1, TStr, RStr), !.

str_simplified_t([X, 0], 26, TStr, RStr) :-
  map_index(Char, 26),
  RStr = TStr + X*Char, !.

str_simplified_t([X, N], 26, TStr, RStr) :-
  map_index(Char, 26),
  get_no(Char, X, XStr),
  RStr = TStr + XStr + N, !.

str_simplified_t([X|R], 1, _, RStr) :-
  map_index(Char, Loop),
  get_no(Char, X, AStr),
  I1 is Loop + 1,
  str_simplified_t(R, I1, AStr, RStr), !.

str_simplified_t([X|R], Loop, TStr, RStr) :-
  map_index(Char, Loop),
  get_no(Char, X, XStr),
  AStr = TStr + XStr,
  I1 is Loop + 1,
  str_simplified_t(R, I1, AStr, RStr).

print_simplified calls str_simplified_t to compute the reduced string representing a simplified additive term of the initial additive term.

As one can see this solution is somewhat less complex and more performant than the previous solution. Most of the code is responsible for computing array indices or updating an array cell. For this, further (code length) optimizations may be identified. The array approach completely avoids the sort predicate thereby reducing run-time overhead. On the downside, this approach works with single characters instead of any atom.

Adventures in Prolog - Simplify Sum (3)

2009-05-12T13:17:00.044+02:00

In an earlier installment the simplify_sum predicate was discussed. However it was not really a feature complete solution to the initially motivated problem. For this, this post is concerned with providing a newer version, which actually solves the following problem.

Given some additive formulae, such as:
1
a
1 + a
a + a
1 + a + 9 + b + a + b + c
we wish to obtain the following results:

1
1*a (or a)
1*a + 1 (or a + 1)
2*a
2*a + 2*b + 1*c + 10 (or 2*a + 2*b + c + 10)

The proposed solution will consist of three parts:

1.
order all parts of an additive equation according to letters and numbers.
place letters in order of the alphabet and summarize numbers, such that at most one number is present.

2.
summarize all variables. this leads to the transformation of x into 1*x

3.
reduce all variables from 1*x to x.

Translating the above sequence of steps into a Prolog program, leads to the following definition of the simplify_sum predicate:


simplify_sum(In, Final) :-
  sort_sum(In, SortedOut),
  simplify(SortedOut, Result),
  strip_sum(Result, Final), !.

A first naive implementation of sort_sum, checks whether some parameter is an atom or a number and arranges the output accordingly. The high level predicate sort_sum makes use of the acutal predicate called sort_sum_t. sort_sum_t implements a bubble sort approach to arrange numbers and atoms. If two numbers are encountered they are reduced to their sum.Elementary cases are only one number, one atom, two atoms, two numbers and atom and number. Compound cases split the input argument into simpler forms until input is elementary.


%sort_sum_t
sort_sum_t(X + Y, X + Y) :-
  atom(X),
  number(Y), !.

sort_sum_t(X + Y, X + Y) :-
  atom(X),
  atom(Y),
  char_code(X, CX),
  char_code(Y, CY),
  CX =< CY, !.

sort_sum_t(X + Y, Y + X) :-
  atom(X),
  atom(Y), !.

sort_sum_t(X + Y, Y + X) :-
  number(X),
  atom(Y), !.

sort_sum_t(X + Y, Res) :-
  number(X),
  number(Y),
  Res is X + Y, !.

%compounds
sort_sum_t(C + X, Res) :-
  sort_sum_t(C, R1),
  number(R1),
  number(X),
  Res is X + R1, !.

sort_sum_t(C + X, X + R1) :-
  sort_sum_t(C, R1),
  number(R1),
  atom(X), !.

sort_sum_t(C + X, A + Res) :-
  sort_sum_t(C, A + B),
  number(B),
  number(X),
  Res is B + X, !.

sort_sum_t(C + X, A + B + X) :-
  sort_sum_t(C, A + B),
  atom(B),
  number(X), !.

sort_sum_t(C + X, Res + B) :-
  sort_sum_t(C, A + B),
  number(B),
  atom(X),
  sort_sum_t(A + X, Res), !.

sort_sum_t(C + X, Res + B) :-
  sort_sum_t(C, A + B),
  atom(B),
  atom(X),
  char_code(B, CB),
  char_code(X, CX),
  CX =< CB,
  sort_sum_t(A + X, Res), !.

sort_sum_t(C + X, A + B + X) :-
  sort_sum_t(C, A + B),
  atom(B),
  atom(X), !.

sort_sum(X, X) :- atom(X), !.
sort_sum(X, X) :- number(X), !.

sort_sum(In, Out) :- sort_sum_t(In, Out), !.

sort_sum(_, _).

Now that an input additive term is sorted according to variables and numbers, it may be processed. This processing, i.e. summing equal atoms and numbers is handled by the simplify predicate, which in turn calls simplify_t to summarize some additive input term. special cases correspond to those identified for the sort_sum predicate. However, simplify_t can make use of the following: (1) there is only one number in the input term, which is at the right most position and (2) an atom follows another atom which is either equal to itself (only having higher quantity) or is a smaller atom.


simplify_t(X, 1*X) :- atom(X), !.

simplify_t(A*X, A*X) :-
  atom(X),
  number(A), !.

simplify_t(X*A, A*X) :-
  atom(X),
  number(A), !.

simplify_t(X, X) :- number(X), !.

simplify_t(X + Y, 1*X + Y) :-
  atom(X),
  number(Y), !.

simplify_t(X + Y, 1*X + 1*Y) :-
  atom(X),
  atom(Y),
  X \= Y, !.

simplify_t(X + X, 2*X) :- atom(X), !.

simplify_t(X + I*X, J*X) :-
  atom(X),
  number(I),
  J is I + 1, !.

simplify_t(X + X*I, J*X) :-
  atom(X),
  number(I),
  J is I + 1, !.

simplify_t(I*X + X, J*X) :-
  atom(X),
  number(I),
  J is I + 1, !.

simplify_t(X*I + Y, I*X + Y) :-
  atom(X),
  atom(Y),
  number(I), !.

simplify_t(I*X + Y, I*X + Y) :-
  atom(X),
  atom(Y),
  number(I), !.

simplify_t(X + Y*I, X + I*Y) :-
  atom(X),
  atom(Y),
  number(I), !.

simplify_t(X + I*Y, X + I*Y) :-
  atom(X),
  atom(Y),
  number(I), !.

simplify_t(A*X + B*X, C*X) :-
  atom(X),
  number(A),
  number(B),
  C is A + B, !.

simplify_t(X + Y, X + Y) :-
  atom(X),
  atom(Y), !.

simplify_t(A*X + B*Y, U + V) :-
  simplify_t(A*X, U),
  simplify_t(B*Y, V), !.

%compounds
simplify_t(C + X, R + X) :-
  number(X),
  simplify_t(C, R), !.

simplify_t(A + B, R*X) :-
  simplify_t(A, M*X),
  simplify_t(B, N*X),
  atom(X),
  R is M + N, !.

simplify_t(A + B, M*X + N*Y) :-
  simplify_t(A, M*X),
  simplify_t(B, N*Y),
  atom(X),
  atom(Y),
  X \= Y, !.

simplify_t(A + B, M + R*X) :-
  simplify_t(A, M + N*X),
  simplify_t(B, S*X),
  atom(X),
  R is N + S, !.

simplify_t(A + B, M + N + SX) :-
  simplify_t(A, M + N),
  simplify_t(B, SX), !.

simplify(In, Out) :- simplify_t(In, Out), !.

simplify(_, _).

Now that an additive term is transformed to its reduced form, the only thing left is to remove any unnecessary 1. That is reduce each 1*x to x. Again the compound case is reduced to atomic cases, which are 1*x = x, n*x = n*x, number = number.


strip_sum(X, X) :- number(X), !.

strip_sum(1*X, X) :- atom(X), !.

strip_sum(N*X, N*X) :-
  atom(X),
  number(N), !.

strip_sum(A + B, A1 + B1) :-
  strip_sum(A, A1),
  strip_sum(B, B1), !.

running the following example:


simplify_sum(a + b + c + d + a + c + 70 + a+ a + 50, X).
X = 4*a+b+2*c+d+120.

shows the correct working of simplify_sum.

As mentioned sort_sum makes use of a bubble sort approach, which clearly is less than optimal. For this, the next post is concerned with using a different sort_sum approach to speed simplify_sum up.

Adventures in Prolog - Computations with lists VII

2009-04-17T18:55:00.003+02:00

Again, as I am quite busy these days, I will present some not recent predicates, just to keep the flow going. Quite recently, I have seen the world of depth, breadth and intelligent search in Prolog. For this, I am working on an implementation of the 8-queens problem. Unfortunately, this is nothing to show off at the moment. But probably in 2 weeks or so, I will be able to show present it here and demonstrate how elegantly one may solve problems using Prolog.

Today's post is about the detection of a palindrome using Prolog. A palindrome is defined as some word that can be read from start to end or end to start and it will not change. For example, the word ANNA is a palindrome.

Now, using the idea that a palindromic word is a word that can be read back and forth and does not change, we come with the following ...

Let X be some word. If X is the empty word then it is a palindrome. If X is not the empty word then let Y be the reverse of X. If Y equals X, X is a palindromic word. Instead of focussing on words, we focus on lists.

%palin/1 X is a palindrome
palin([]).
palin(X) :- revList(X, Y), X = Y.

A more succinct version of the above would avoid the additional test of equality, i.e. lead to the following predicate:

palin(X) :- revList(X, X).

Which clearly is the the same, i.e. if reversing X leads to X, then clearly, X has to be palindromic. revList is a binary predicate that takes a list as input and outputs the reverse list.

Adventures in Prolog - Computations with lists VI

2009-04-06T08:49:00.002+02:00

Today's post is merely to get the flow going and the blog updated. That is it is about the simple concatenation of two lists. Just like the append predicate appends some element at the end of a list, concatenate_list joins two lists by recursively reducing one list until it is the empty list.

%concatenate_list/3
concatenate_list([], List, List).
concatenate_list([H1¦T1], [H2¦T2], [H1¦T3]) :-
concatenate_list(T1, [H2¦T2], T3).

Adventures in Prolog - Link List I

2009-03-30T17:05:00.003+02:00

Today's post is merely a compilation of interesting resources on Prolog.

Learn Prolog Now - An online (and paperback) book to learn Prolog

Aspect-Oriented Programming Prolog

Adventures in Prolog - another online book to learn Prolog

P99-Ninety-Nine Prolog Problems - a set of Prolog challenges organized into different degree of difficulty and domains

So happy reading and solving problems :D

Adventures in Prolog - computations with Lists V

2009-03-17T11:29:00.002+01:00

Today's post presents a predicate defined for lists that is as simple as yesterdays rem_dups/2. flatten/2 is concerned with flattening an arbitrary list to a one-dimensional list/array.The idea behind flatten is pretty simple, i.e. if a list is non-flat we lower its dimensionality by taking theinner of that list and process it further until we reach a one-dimensional list.

%flatten/2
flatten([], []).
flatten([[]], []).
flatten([[HT]], X) :- flatten([HT], X).
flatten([[H]T], X) :- flatten([HT], X).
flatten([H[T]], X) :- flatten([HT], X).
flatten([HT], X) :-
flatten(T, Y),
append([H], Y, X).

Adventures in Prolog - computations with lists IV

2009-03-16T14:55:00.003+01:00

Today's post is merely a modification to yesterdays post, i.e. the remove duplicate functions will be streamlined. rem_dups2/2 is a replication of rem_dups/2 with less dependencies, i.e. it does not use the remove/3 predicate thereby improving performance. A drawback is that rem_dups2 does not preserve order of list elements when producing output, i.e. the last occurence of a duplicate list element will be preserved in the output list.

rem_dups2([X[]], [X]).

rem_dups2([HT], X) :-
member(H, T),
!,
rem_dups2(T, X);
rem_dups2(T, Y),
append([H], Y, X).

Adventures in Prolog - Computations with lists III

2009-03-15T19:42:00.002+01:00

This week's post is concerned with another operation on lists, i.e. how to compute a set given a list. This means that given a list containing any values, we wish to remove duplicates from this list to obtain a set containing unique members. The predicate rem_dups/2 does exactly this.

rem_dups([X[]], [X]).

rem_dups([HT], X) :-
member(H, T),
!,
remove(H, T, Y),
rem_dup([HY], X);
rem_dup(T, Y),
append([H], Y, X).

The problem forumulation basically says that if the head of a list is contained within the tail of the list it is a duplicate. Consequently, this duplicate (and any further duplicate of H) is removed from T. Since we want to retain H, we need to connect it with the list that does not contain any instance of H, i.e. X. This procedure is followed for all elements of the list. If a list element does not have a duplicate it is not removed from the list.

rem_dup makes use of auxiliary predicates like remove/3, append/3 and member/2. member/2 checks whether some X is element of some list L. remove/3 removes some X from list L1 yielding the result list L2. append/3 does the opposite it appends some X to an existing list L1 yielding L2.

Adventures in Prolog - Link

2009-03-05T21:55:00.003+01:00

Since I am quite occupied these days, I will only post a link to some intellectual stimulus today.

If you follow this link you will be taken to "The First 10 Prolog Programming Contests". So indulge some brain food.

Adventures in Prolog - Simplify Sum (2)

2009-02-25T21:31:00.003+01:00

The last post showed how to compute simple addition expressions. To provide a more structured approach to the problem at hand, I decided to write a small Prolog program that actually recognizes such addition expressions. This program basically represents a Prolog conversion of the grammar underlying such addition expressions. Because Prolog notation and grammer are so close, I will not comment on the following Prolog clauses.

addition_expression(A) :- sum_term(A).
addition_expression(A) :-
A = X + Y,
addition_expression(X),
sum_term(Y).

sum_term(X) :- number(X).
sum_term(X) :- atom(X).
sum_term(X) :- prod_term(X).

prod_term(X) :- X = A * B, number(A), atom(B).
prod_term(X) :- X = A * B, atom(A), number(B).

Adventures in Prolog - Simplify Sum (1)

2009-02-22T20:24:00.002+01:00

Today's post is concerned with (the first part of) an example task from the book "Prolog Programming For Artificial Intelligence" - it is a about the simplification of additive terms using Prolog's facilities to reason about the type of some symbol.

For example, Prolog offers the following (and more) built-in predicates:

number/1 - is the argumet passed, a number, e.g. number(1) returns true
atom/1 - is the passed argument an atom, e.g. atom(x) returns true
compound/1 - is the passed argument a compound term, e.g. compound(X+Y) returns true

Now, that we know how to inspect the type of some Prolog symbol, we may take a look onto today's task. Given some summation, the task is to simplify this summation, using some predicate called simplify_sum or simp_sum (for short).

For example:

1 +2 +3 = 6
1 +a = a +1
a + b + 1 + c = a+ b +c + 1
a + 1 +2 + b = a + b + 3

So in short, the summation should be ordered with atoms first and aggregated numbers last. The original task by Bratko is concerned with the aggration of atoms as well, such as x +x = 2*x, but I will keep this for the next post.

So based on the above statement of the problem, we must consider some elementary cases, such as:

number + atom = atom + number
number + number = number
atom1 + atom2 = atom1 + atom2
atom + number = atom + number

These cases will act as the recursion anchor in our simp_sum clauses. Based on this reduction to the simplest form of the problem (please note, that we do not consider a case where only one atom or one number is passed to simp_sum), we identify more advanced incarnations of the problem.

We must consider the following:

some compound term + number
some compound term + atom

cases as well. The reason for compound term occuring only on the left-hand side is the associativity of the + operator. For example. 3 + 4 + 5 is (3 + 4) + 5 and consuequently we have 3+ 4 +5 = compound + number where compound = number + number.

Putting together all this information we might come up with the following ...

simp_sum(X + Y, R) :- number(X), number(Y), R is X + Y.
simp_sum(X + Y, X + Y) :- atom(X), number(Y).
simp_sum(X + Y, Y + X) :- atom(Y), number(X).
simp_sum(X + Y, X + Y) :- atom(X), atom(Y), X \== Y.

%Result of simpsum is not compound
simp_sum(X + Y, Z) :-
simp_sum(X, X0), number(X0), number(Y), Z is X0 + Y.
simp_sum(X + Y, Y + X0) :-
simp_sum(X, X0), number(X0), atom(Y).

%Result of simpsum is compound
simp_sum(X + Y, A + Y0) :-
simp_sum(X, X0), number(Y), X0 = A + B,
number(B), simp_sum(B+Y, Y0).

simp_sum(X + Y, A + B + Y) :-
simp_sum(X, X0), number(Y), X0 = A + B, atom(B).

simp_sum(X + Y, A + Y + B) :-
simp_sum(X, X0), atom(Y), X0 = A + B, number(B).

simp_sum(X + Y, A + B + Y) :-
simp_sum(X, X0), atom(Y), X0 = A + B, atom(B).

When Prolog is asked:

simp_sum(1 + b + 2 + c + a + 4 + d + 39 + e+ f + 122, X).

It answers correctly:

X = b+c+a+d+e+f+168 .

Adventures in Prolog - Computations with lists II

2009-02-19T19:43:00.004+01:00

As mentioned in my last post, this post is concerned with building some abstraction when computing with lists. For this, I will abstract the the addList and mulList prodecures into one more general processList procedure. processList will iterate over a list and process it according to some user-defined function. Users of F# might recognize this from F#'s map function offered by a list object.

At first we define the processList function. processList takes 4 input parameters - a list, a processing function some identity element and the result. processList processes some input list according to the provided processing function. The identity Identity element is used to process the empty list. The result of this operation is placed into the variable Res.

%processList/4
processList([], F, Identity, Identity) :- functor(_, F, 3).
processList([HT], F, Identity, Res) :-
functor(_, F, 2),
processList(T, F, Identity, L1),
apply(F, [H, L1, Res]).

The functor procedure checks whether the user supplied processing function F is indeed a function accepting 3 Variables (F/3). processList is similar to mulList or addList, in that it uses the recursive definition of a list to process each list element. apply is used to call the user-supplied procedure F with submitted input variables.

By itself processList does not do much, it is merely the skeleton to enable abstract computation on lists. To make use of it, we have to define some processing function F.
As mentioned, I want to use processList to abstract addList and mulList. For this, let's define two ternary relations add and mul. add is used to realize addList and mul is given to realize mulList. Their definition is straightforward and presented in the following.

%test ops
add(X, 0, X).
add(0, _, 0).
add(X, Y, Z) :- Z is X + Y.

mul(_, 0, 0).
mul(0, _, 0).
mul(X, 1, X).
mul(1, X, X).
mul(X, Y, Z) :- Z is X*Y.

Given the above definitions, we may ask Prolog now:
?- processList([1, 2, 3, 4, 5], add, 0, R).
, which yields:
R = 15

Clearly, add and mul are simple examples but more powerful processing functions can be implemented and passed to processList.

Adventures in Prolog - Computations with lists

2009-02-18T21:29:00.003+01:00

My last post was concerned with basic computations in Prolog using the powerful technique - recursion. Today's post is concerned with recursion as well, but this time recursion is applied to Prolog's main data structure - the list.

A list in Prolog is a recursive data structure itself. Why? Because a list can be built by remembering the following ...

1. the empty list [] is a list
2. a list can be built by appending any list T to an item H, which yields [HT]

Using this definition we can see that the list [1, 2, 3, 4] is indeed a list with H = 1 and T = [2, 3, 4]. Consequently, a list cannot only be built from points 1. and 2. but also decomposed according to 1. and 2. Therefore 1. and 2. form the underlying principle when computing with lists in Prolog.

Now that we have covered the basic principle underlying a list. I will present two operations on lists - the addition of elements of a list (sumList) and the multiplication of elements of a list (mulList).

Both operations make use of the presented recursive structure of a list. The needed recursion anchor is the processing of the empty list. This maps to the identity operation in addition and multiplication. Identity in addition is performed using the zero element thus - a + 0 = 0 + a = a. Identity in multiplication is done by multiplying with the one element thus a * 1 = 1 * a = a.

Employing both identities, the definition of sumList and mulList become straightforward. A list is peeled down until it is stripped to the empty list, in this case the identity operation is performed. While peeling the list each element is either added or multiplied with the result obtained by performing the operation on the remaining unpeeled list (the list's tail T).

%sumList/2 sum list elements%
sumList([], 0).
sumList([HT], L) :-
sumList(T, L1),
L is H + L1.

%mul list elements%
mulList([], 1).
mulList([HT], L) :-
mulList(T, L1),
L is H * L1.

In my next post, I will cover the abstraction from special computations on lists to defining a general operation on a list, which executes a special function on each list item. This is similar to F#'s list-map function.

Adventures in Prolog - Simple computations

2009-02-15T19:15:00.004+01:00

This time I present a way to calculate the ith power of some integer j (i is also an integer number). Clearly, this is nothing too sophisticated but it will be helpful for some other program, I want to show later on.

Power is implemented as a simple ternary relation, which uses recursion. The base cases for power are of course the 0th and 1st power of some integer number. All other powers will be dependant on this anchor. The ith power of j means that j is multiplied with itself i times. For instance, the 3rd power of 2 is eigth, which is 2 * 2 * 2 = 8. This is used to implement the recursive core of power, which is ith power of j is the j * (i-1)th power of j.

After the basic power relation, power10 and power2 show how to use existing relations to implement some simple abstractions.


%power/3
power(X, 0, 1).
power(X, 1, X).
power(X, Y, Z) :-
  Y1 is Y - 1,
  power(X, Y1, Z1),
  Z is X * Z1.

%power10/2
power10(P, R) :- power(10, P, R).
%power2/2
power2(P, R) :- power(2, P, R).

Adventures in Prolog - Fibonacci

2009-02-15T10:52:00.000+01:00

As I have played around with Prolog lately, I wanted to share some enriching moments with my new favourite pet. We start of with the famous Fibonnaci numbers and their computation in Prolog. To spice things up, I used the dynamic clause, which enables one to add clauses to an existing database.


:- dynamic(fib/2).
fib(0, 1).
fib(1, 1).
fib(F, X) :-
  F1 is F-1,
  F2 is F-2,
  fib(F1, X1),
  fib(F2, X2),
  X is X1 + X2,
  asserta(fib(F, X)).


So what does this listing do? Clearly, it computes the ith value of the Fibonacci sequence using recoursion. Therefore, the recoursion anchor - 1st and 0th value - of the sequence is established first. After that the definition of the sequence is given in its known form. 
By making the predicate fib/2 dynamic, we can add facts to the list of clauses covering fib/2. Dynamic has to be executed upon loading the fib database. That is why we write :- dynamic(fib/2). .
Now new knowledge about the Fibonnaci values can be added to the database. This is what is done later one with the asserta statement - asserta adds new clauses at the beginning of the database (assertz at the end). The value of the computation of the jth Fibonacci sequence value (fib(J, X)) is added as a fact to the database, thereby speeding up future computations of the same Fibonacci sequence value.

Adventures in F# - A port of the simplest Herbivore

2008-08-23T21:07:00.000+02:00

Following the past of my previous post, this time I present a barebones stripped-down version of the Herbivore that ships with the Terrarium SDK. The code is will equip you with a compilable herbivore, which however does nothing but sit in your terrarium. Just like in the previous post, I did not strip out some of the inline comments, which may be helpful to some of us.

So here comes the code ...
namespace CBHerbivore

#light
#r "E:\\Development\\my fsharp\\Terrarium\\Terrarium\\OrganismBase.dll"

open System;;
open System.Drawing;;
open System.Collections;;
open System.IO;;
open OrganismBase;;

//Sample Herbivore
//The following Assembly attributes must be applied to each
//Organism Assembly


[<assembly: OrganismClass("CBHerbivore.CBHerbivore")>]
//The class that derives from Animal
[<assembly: AuthorInformation("Christian Bitter", "x@y.z")>]
//It's an herbivore
[<CarnivoreAttribute(false)>]

//This value must be between 24 and 48, 24 means faster
//reproduction
//while 48 would give more defense and attack power
//Make it smaller for reproduction


[<MatureSize(26)>]

//AnimalSkin = AnimalSkinFamilyEnum.Beetle, you can be a Beetle
//an Ant, a Scorpion, an Inchworm, or a Spider
//MarkingColor = KnownColor.Red, you can choose to mark your
//creature with a color.
//This does not affect appearance in the game.


[<AnimalSkin(AnimalSkinFamily.Beetle)>]
[<MarkingColor(KnownColor.Red)>]

//You get 100 points to distribute among these attributes to define
//what your organism can do.  
//Choose them based on the strategy your organism will use.
//This organism hides and has good eyesight to find plants.

[<MaximumEnergyPoints(0)>]

//Don't need to increase this as it just sits next to plants

[<EatingSpeedPoints(0)>] //Ditto
[<AttackDamagePoints(0)>] //Doesn't ever attack
[<DefendDamagePoints(0)>]

//This attribute changes the skin of our herbivore, 
//which is now going to be a beetle.
//Point Based Attributes
//Doesn't even defend


[<MaximumSpeedPoints(0)>] //Doesn't need to move quickly
[<CamouflagePoints(50)>] //Try to remain hidden
[<EyesightPoints(50)>] //Need this to find plants better 

type CBHerbivore () =   
  inherit Animal()  
  override sh.Initialize() = ()  
  override sh.SerializeAnimal (m:MemoryStream) = ()  
  override sh.DeserializeAnimal (m:MemoryStream) = ()As you may see, the main difference between this herbivore and the previous plant, is the base type our herbivore type needs to implement, and some attributes declared on our animal. In this case the abstract Animal class, declares 3 abstract members (Initialize, SerializeAnimal, DesirializeAnimal), which need to be implemented by our herbivor. Attributes control some of the properties of our herbivore, such as its moving speed, etc. 
Again, if you compile this type and introduce it to your terrarium, do not be surprised, to see, that the animal is stiff and not moving like an animal during hibernation. This is due to not implemented event handlers. These event handlers are responsible for your animal's interaction with its environment.

Adventures in F# - A Plant for Terrarium 2

2008-08-23T14:08:00.000+02:00

Recently, my beloved Terrarium-game has reappeared from the neatherworlds of software. As some of you may know, Terrarium's intend was to showcase the back then rather new and exciting .NET platform version 1.x (not that it is not still exciting). Although from a gamer's perspective, the graphics weren't all to great, from a technology standpoint, it featured great things, such as Webservices, Reflection, etc.

At some point Terrarium ceased to exist, which was a shame, since the community was quite active developing plants, herbivores and carnivores for the virtual ecosystem that Terrarium simulates. I for myself, developed some simple creatures too (a simple decision-based/state-based agent), as part of a project I did during university for my AI course. More advanced (in comparison to my creature) could be imported showcasing great AI stuff such as A*, neural networks, planning, etc.

However, in an community effort, Terrarium was relaunched lately on codeplex and will hopefully see great new additions, such as a port to a more current version of the .NET platform and DirectX.

In a small attempt I tried to put my superficial F# skills to work, and decided to port a plant organism to F#. My attempt can be seen in the following lines of code. For a C# version, see the codeplex discussion here. I decided to leave the comments from the discussion as is.

namespace CBPlant

We open a namespace for the plant organism

#light #r "E:\\Path to OrganismBase.dll\\OrganismBase.dll"

We set the environment to lightweight and reference the OrganismBase.dll, which contains all the Terrarium2 stuff.

open System;; open System.Drawing;; open System.Collections;; open System.IO;; open OrganismBase;;

We open some namespaces, which we are going to use later and dive right into the code.
// Sample Herbivore

//Strategy
//This animal moves until it finds a food source and 
//then stays there
// The following Assembly attributes must be applied to each 
//Organism Assembly
[<assembly: OrganismClass("CBPlant.CBPlant")>]    // The class that derives from Animal
[<assembly: AuthorInformation("XYZ", "x@y.z")>] // Provide Author Information
do()
Assembly-level attributes have to be declared via a global do() statement. See the discussion here.

//3.2 Plants 
//The definition of a plant is relatively easy since plants do not have to have any sort of movement defined to allow them to locate sources of food. 
//Each plant has three basic functions: 
//1. Grow 
//2. Reproduce by spreading seeds 
//3. Be eaten by herbivores 
//A plant organism does not need to contain any methods, it just has three properties that define how a plant functions. 
//4 
//1. The “MaximumEnergyPoints” property allows the developer to state how many energy points a herbivore will gain by consuming this plant. The maximum allowed is 10. 
//2. The “MatureSize” property which must be a number between 24 and 48 states the maximum size a plant can grow to when it has survived for some amount of time without being consumed. The smaller a plant is, the faster it will be able to reproduce. As a plant gets larger it will become easier for herbivores to see and will more likely be consumed. 
//3. The “SeedSpreadDistanceAttribute” states the maximum distance a plant can spread seeds from its current location. The maximum allowed is 100. These three properties alone are enough to define a functioning plant for the Terrarium game. 
// This value must be between 26 and 48, 26 means faster reproduction 
// while 48 would give more defense and attack power 
// Make it smaller for reproduction*) 
[<MatureSize(26)&gt;] 
[<SeedSpreadDistance(100)>] 
// Point Based Attributes 
// You get 100 points to distribute among these attributes to define 
// what your organism can do.Choose them based on the strategy your organism 
// will use. This organism hides and has good eyesight to find plants
[<MaximumEnergyPoints(10)>] 

type CBPlant () = 
  inherit Plant ()
  override cb.SerializePlant (m:MemoryStream) = ()
  override cb.DeserializePlant (m:MemoryStream) = ()
;;
We define a new plant type, called CBPlant (full CBPlant.CBPlant). This type is a subclass of the abstract class Plant. We have to implement Plant's two abstract members, which according to the example is just an empty method body. If we compile this by invoking 
fsc OrganismBase.dll CBPlant.fs -a
A new library will be created, containing just this simple type.
Hopefully, I will get to play some more with F# and Terrarium doing some other stuff, like porting the Herbivore, Carnivore and start to add some real behaviour.



Adventures in F# - F# and ADO.NET
2008-08-23T11:43:00.000+02:00
Today's post is rather simplistic in what it does, but it illustrates some key language elements of F#, such as exception handling. 
The task to accomplish is quite it easy, nameley, to connect to a SQL Server 2005 database called "TestDB" on my local machine, using ADO.NET to pull out some rows of the "Person" table having the following schema:
Person (
  PersonID: int; 
  FirstName nvarchar(50); 
  LastName nvarchar (50); 
  Street nvarchar(50); 
  City nvarchar(50); 
  ZIP int
)
The code we use in F# is a rather straightforward conversion of some typical C# code, and as such is probably not the best way to do things, but it gets the task done, and may illustate the point.
#light
We use the lightweight syntax option.

open System.Data;
open System;
open System.Data.SqlClient;
As a next step, we have to open the correct namespaces.

let ADONetTest = 
  let conStringBuilder = new SqlConnectionStringBuilder()
  conStringBuilder.IntegratedSecurity <- true
  conStringBuilder.["Data Source"] <- "localhost"
  conStringBuilder.InitialCatalog <- "TestDB"
  let con = new SqlConnection(conStringBuilder.ConnectionString)
These lines create the connection to the SQL Server 2005 database "TestDB" on my local machine. As you may see I use a mixture of passing values to properties (IntegratedSecurity, InitialCatalog) and the indexer (["Data Source"]) that is defined on the SqlConnectionStringBuilder type.

  try
      con.Open()
      let cmdString = "SELECT * FROM [dbo].[Person]"
      let cmd = new SqlCommand(cmdString, con)
      cmd.CommandType <- CommandType.Text
      using (cmd.ExecuteReader()) (fun reader ->
          if (reader.HasRows) then
              (
                  printfn "Queried: %s" cmdString
                  while (reader.Read()) do
                      (
                          let id = reader.GetInt32(0)
                          let firstName = reader.GetString(1)
                          let lastName = reader.GetString(2)
                          let street = reader.GetString(3)
                          let city = reader.GetString(4)
                          let zip = reader.GetInt32(5) 
                          printfn "%d %s %s %s %s %d" id firstName lastName street city zip
                      )
                  done
              )
          else (printfn "Empty result")
      )
      con.Close()
  with
      | :? System.Data.SqlClient.SqlException as sqlEx -> printfn "%A" sqlEx.Message
      | _ -> printfn "Unknown Exception"
  
  (con :> IDisposable).Dispose ()
;;

This part is responsible for the main functionality. We open the previously specified connection. We do this in a try-with block, to be prepared in case of exceptions. We actually try to handle one exceptio, the SqlExceptio. In the with block, we use type/pattern matching rule (|:? SqlException) to catch this particular exception. Since we do not have a handling strategy in place, a printf command is issued.The next with rule gets executed on whatever type not matching SqlException. We indicate that we do not even care about what it is (| _) using an anonymous rule. 
Inside our try block, we declare a SqlCommand and pass in the Sql query stored in the cmdString. variable. This command encapsulates a Select-From-Where SQL-query. We execute the query, using one of F#'s equivalent's of the C# using statement - the using statement (the other one would be use).
The using keeps track for us, that in the case of an exception the "Dispose" method of the object used in the using statement is called - in this case it would be the Dispose declared by the result of  SqlCommand.ExecuteReader() - a DataReader object.
Inside the using block, it is asked whether the result of the query (DataReader) actually has rows that were returned by our particular query. This is done by if (reader.HasRows) then () else ().In case rows were returned by that query,they are enumerated by the while do () done loop. This loop does nothing but print each row present in the DataReader.
The last statement to mention is the  (con :> IDisposable).Dispose (). This statement casts the connection object into the IDisposable and calls the Dispose method on it. This has to be done, since it is not automatically called by a try-with block, and we have to ensure that all used objects are properly disposed of - espacially those that abstract native resources, such as database or file connections.



Small one - SourceSafe via command line
2008-08-20T11:01:00.000+02:00
Yes, I haven't been blogging for quite a bit and this small post is not going to change that but at least it is a little somethin'. I've been digging into F# and have had some great learning experience but this is nothing to really present now.

Today I show a little snippet that let's you load some project ("XYZ") from SourceSafe into a specific folder (<Target Directory>). This may come in handy in some sort of automatic build invironment.

At first you need to define, i.e. set as environment variables: 
1. SourceSafe User Account, supplied with sufficient privileges to actually access the project you want to retrieve
2. The account's password
3. The path to the SourceSafe DB's SourceSafe configuration file (srcsafe.ini)

Next you ask SourceSafe to change the working directory for the project, you are going to load. You do this via "ss Workfold". 
The last step is to load/get the actual project into the working directory.


SET SSUSER=<your SourceSafe Account>
SET SSPWD=<your SourceSafe Account's Password>
SET SSDIR=<the path to your SourceSafe DB>

"SOURCESAFEDIR\ss.exe" Workfold $/<Path to XYZ>/XYZ "<Target Directory>"
"SOURCESAFEDIR\ss.exe" get $/<Path to XYZ>/XYZ -R


The only problem with this solution is, that SourceSafe is going to ask you, whether the intended working folder is the correct one. To fix this we include a change of the current directory into the <Target Directory> and everything will be fine.


SET SSUSER=<your SourceSafe Account>
SET SSPWD=<your SourceSafe Account's Password>
SET SSDIR=<the path to your SourceSafe DB>

cd "<Target Directory>"

"SOURCESAFEDIR\ss.exe" Workfold $/<Path to XYZ>/XYZ "<Target Directory>"
"SOURCESAFEDIR\ss.exe" get $/<Path to XYZ>/XYZ -R


Another way to accomplish this sort of automatic build environment is by the use of SourceSafe initialization variables. These let one configure the SourceSafe environment. By specifying a custom SourceSafe initialization file, one may configure all aspects to one's needs.


Aventures in F# - Fibs
2008-05-02T00:14:00.000+02:00
Today's post is about the famous Fibbonaci sequence: 0, 1, 1, 2, 3, 5, 8, ...

I will present a recursive and an iterative F# approach to generating the sequence.

The Fibbonaci number n = Fib(n) is generated as follows:

Fib(n) = Fib(n-2) + Fib(n-1) where Fib(0) = 0 and Fib(1) = 1

The condition Fib(0) and Fib(1) are the anchor to end the recursion and otherwise it is dug into the recursion. Consequently, ...

1. Recursive Approach


let rec FibRec n =
if n = 0 then 0
else if n = 1 then 1
else (FibRec (n-2) + FibRec(n-1))
;;

As you can see the function is rather straightforward and follows the definition closely. However, its recursive nature make it rather unsuiting for large values of n - you will notice that for large values of n the recursion slows the process down.

2. Iterative approach

let FibIt n =
if n = 0 then 0
else if n = 1 then 1
else
let fibA = Array.create (n+1) 0
fibA.[0] <- 0 fibA.[1] <- 1 for i = 2 to n do
fibA.[i] <- fibA.[i-2] + fibA.[i-1] fibA.[n] ;; 

As you can see the iterative approach employs Fib(0) and Fib(1) equally as anchors. However, it uses a for loop starting at two to fill an array at index i with the Fibbonaci number Fib(i). Clearly, we do not need the array but it will come in handy at a later stage.

Although being faster, i.e. compare the recursive approach with the iterative approach for Fib(40) and you will notice some time difference, both approaches suffer data overflow. This means that Fib(48) displays correctly but Fib(49) wraps around the integer boarder and becomes a negative number. Therefore we have to find a way around this problem - probably the next time.

I have come around some valuable resources with respect to F# 

Marius Bancila's Blog: http://mariusbancila.ro/blog/
Robert Pickering's Strange Blog: http://strangelights.com/blog/




Aventures in F# - words is all you need
2008-04-29T09:27:00.000+02:00
F# let's you specify the same thing in different styles - depending on your likings (clarity, purity, style, compactness, problem-domain-specific) you my choose the appropriate expression.

For example: Assume we have a list of numbers and want to transform them in a certain way, e.g. we want to square them.

1. generate a list of numbers
let numbers = [for i in 1..10 -> i];;

Now we have different options to reach our goal, i.e. transforming the elements of the list to be equal to their respective square, i.e. i -> i * i

The first way to do this is to generate the set with squared numbers.
let sqnumbers = [for i in 1..10 -> i * i];;
While it solves the problem, it was not exactly what I was looking for.

So we define a function that takes an integer list as input and generates the appropriate output list by taking each element squaring it and appending it to the output list.
Let sqfunc be this function.

One way of calling sqfunc is: sqfunc numbers;;

But we could also use F#'s incredible pipelining operator >
which would result in: numbers > sqfunc;;
The operator matches perfectly the way of reading it, i.e. "put numbers into the pipeline component sqfunc" - Nice
So If we were to compute the fourth power of our numbers list we could write:
numbers > xfunc > xfunc;;

The pipeline operator is nothing but syntatctic suggar, being defined as:
let (>) x f = f x
where x is the input to apply the function f on.

Since we work on lists, we may also use the map function defined on list types. The map function takes as input a function that transforms elements of an input list. Therefore we may write
List.map (fun x -> x * x) numbers;;

This exhibits F#'s anonymous function values - so much like a C# delegate type as an input parameter to a function List.map.


Adventures in F#
2008-04-24T12:50:00.000+02:00
Adventure 1: Reversing an integer list

let rec ReverseList (l: int list) =
 match l with
 ¦ H::T -> (ReverseList T) @ [H]
 ¦ [] -> []

The code is quite simple. It does the following:
define a recoursive function (rec keyword) on integer list argument
use pattern matching (match with) on the argument l to decompose l into a head and a tail. The head is the head (first) element of l and tail is the remainder of l.
use this knowledge to call itself recoursively
It is checked whether l consists of a head H and a tail T, if yes, then ReverseList calls itself with T (the list consisting of the tail of l, i.e. l without the head element) and concatenates (@ operator) the result with the list consisting of the headelement ([H])
if the input argument l is the empty list ([]), then ReverseList exits by returning the empty list.





3D Engine Design
2007-12-06T10:55:00.000+01:00
During the past weeks, I haven't been able to come up with something new and/or meaningful. But for those interested in building a 3D engine, I came across the Lightfeather 3D engine. And the guys over there describe (in a high level manner - functional point of view) the design of their engine. So an experienced graphics developer might use this information to design a "copy" or get inspired by the Lightfeather engine.

Following is the "table of contents" of the Lightfeather 3D engine design:
Introduction
Geometry
Scene
Portals
Rendering



Talk like an animal, walk like an animal ...
2007-11-28T13:45:00.000+01:00
Well, after some time has passed, it seems that Microsoft's Terrarium is at least surfacing again. I have played around with Terrarium while doing some AI in the university. Official links are not working but googling a bit has popped a Microsoft site about some Canadian Terrarium contest. Look here http://msdn.microsoft.com/canada/terrarium/ in the bottom of the page you may even download some video made at the contest but it is not working.

The new download link on windowsclient.net is this one https://windowsclient.net/downloads/folders/starterkits/entry1269.aspx

Browsing through MSDN has surfaced that Tom Anderson did a VB.NET port of Terrarium from .NET framework version 1.x to 2.0. You will find the respective MSDN post here
http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=373738&SiteID=1
Unfortunately, he has stopped working on the project and there is no visible link to me where one can grab the .NET 2.0 port of Terrarium.


Maybe there is some time left to play around a bit ...


Newbie on the CCR Road
2007-10-06T23:00:00.001+02:00
This post is about the CCR part of MRS, in particular I am going to do some simple examples about ports and a simple arbiter the Receiver.
CCR components use ports to communicate with each other. Just like a human being uses speech, verbal speech, or mimicry to communicate, so do CCR components use ports to communicate with each other. Ports are used to
Send a message to a particular receiver.
Receive a message from a particular sender.
In terms of CCR port, we have to define how the message, looks like that our port is going to receive. For this, we have to define the message's underlying data type or more precisely we have to create a port, which receives a message with some particular data type.
Port<string> stringPort = new Port<string>();
This creates a new port, which is able to send and receive message of type string. Now, that we have defined our port, how are do we send a message? Nothing simpler than that, the port offers an instance method Post. This method accepts a formal parameter item of type string. So the canonical "Hello World" example looks like this
stringPort.Post("Hello World");
This passes the item of type string with value "Hello World" to our stringPort, where it waits to be taken from the port for whatever one wants to do with it. To illustrate that the sent item is really "sitting" on the stringPort, we could simply do the following:
if (inputPort.ItemCount > 0)
{
string item = inputPort.Test() as string;

if (!string.IsNullOrEmpty(item))
{
Console.WriteLine("Item: " + item);
}
}
This shows two things. The first (1) being, that you may query the number of items waiting on some port by the ports field ItemCount and the second (2) being that you may test the port for the presence of items. If there is one ore more items on the port, then Test will return this item as an object and remove it from the queue of available items. Fortunately, the removal of an item is an atomic process, so that we won't going to race condition hell.
At times you may want to be able to send and receive more than just one item on some port. Therefore, the CCR offers a so called PortSet, which is just that a set of Ports. For example, to create a PortSet accepting a string and DateTime message, we would do the following:
PortSet<string, DateTime> messageDateTimePort = new
PortSet<string, DateTime>();
To avoid passing ports around in some program and taking individual items of some port, the CCR offers arbiters. Arbiters coordinate incoming messages passed between ports. In order to not manually call the Test method on the stringPort, we are going to declare a so called Receiver, which will be active whenever an item is waiting on a port matching the Receiver's signature. For example,
Receiver<string> stringReceiver = new
Receiver<string>(
true,
stringPort,
null,
new
IterativeTask<string>(MessageHandler));
this creates a Receiver, which accepts string items waiting on stringPort. The first parameter with value true sets persistence to true for this receiver. This means that the Receiver continues to receive string items even after it has received one string item. The null value is passed to the constraints formal parameter and the last parameter wires up a message handler, which actually takes care of string items incoming from stringPort. The MessageHandler function is nothing special (of course, you are free to add your own logic to it) and looks like this
private static
IEnumerator<ITask> MessageHandler(string message)
{
Console.WriteLine("Received Message: " + message);
yield break;
}
To make things complete, a small sample illustrates the previous things. The example creates a simple string port, which is used by a secondary thread to to send the current time to. This message is received by a Receiver arbiter and printed out to the console. The program terminates if the user presses any key. In this case we stop the secondary thread and simple exit the program.
using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

using Microsoft.Ccr.Core;

namespace CCRTest5
{
class Program
{
private static bool running = false;

static void Main(string[] args)
{
Console.WriteLine("CCRTest5 - send to a message port and use arbiter to receive");

Port<string> stringPort = new
Port<string>();
Console.WriteLine("Created Port<string>");

Thread messageThread = new Thread(new
ParameterizedThreadStart(AddItemFunc));

Receiver<string> stringReceiver = new
Receiver<string>(
true,
stringPort,
null,
new
IterativeTask<string>(MessageHandler));

Console.WriteLine("Created Receiver");

Console.WriteLine("Starting Arbiter");
Arbiter.Activate(new
DispatcherQueue(), stringReceiver);

Console.WriteLine("Starting AddItem Thread");
messageThread.Start(stringPort);

Console.WriteLine("Press key to exit");
Console.ReadLine();

//abort
running = false;
Thread.Sleep(500);

if (messageThread.ThreadState == ThreadState.Running)
{
try
{
messageThread.Abort();
}
catch { }
}
}

private static
IEnumerator<ITask> MessageHandler(string message)
{
Console.WriteLine("Received Message: " + message);
yield break;
}

private static void AddItemFunc(object port)
{
running = true;
Port<string> messagePort = port as
Port<string>;

while(running)
{
messagePort.Post(DateTime.Now.ToString());
Thread.Sleep(500);
}
}
}
}
More on arbiters and CCR in the next post.



A simple GreatestCommonDivisor service in C# - Part2
2007-09-27T08:43:00.000+02:00
What if we wanted to consume our previously built GCD Service by a web browser, such as Internet Explorer? ... Nothing easier than that. In fact, with minimal effort we can implement this functionality.
Firstly, we have to (1) declare that our service supports the HTTPQuery operation, secondly we have to (2) implement a handler for this HTTPQuery request, and thirdly we may (3) test the service with a browser.

1.
Just add the HTTPQuery port to the GCD service's port set, which is defined in GCDTypes.cs (assuming that your service is named GCD).

[ServicePort()]
public class GCDOperations : PortSet<..., HttpQuery, ...>
{}

So now that we have declared that our service is capable of understanding a HttpQuery action, we need to implement a routine, which handles such HttpQuery requests - a HTTPQueryGCDHandler.

2. Add the following lines to the GCD.cs

[ServiceHandler(ServiceHandlerBehavior.Concurrent)]
public virtual IEnumerator HTTPQueryGCDHandler(HttpQuery httpQuery) {
if (!string.IsNullOrEmpty(httpQuery.Body.Query["Action"]) &&
httpQuery.Body.Query["Action"] == "GCD")
{
string _M = httpQuery.Body.Query["M"];
string _N = httpQuery.Body.Query["N"];

int _intM = 1;
int _intN = 1;

if (!Int32.TryParse(_M, out _intM))
{
this.LogError("Failed to parse M");
httpQuery.ResponsePort.Post(
new HttpResponseType(new GcdtestState(-1)));
yield break;
}

if (!Int32.TryParse(_N, out _intN))
{
this.LogError("Failed to parse N");
httpQuery.ResponsePort.Post(
new HttpResponseType(new GcdtestState(-1)));
yield break;
}

int _GDC = this.ComputeGCD(_intM, _intN);
this.LogError("GDC = " + _GDC);

httpQuery.ResponsePort.Post(
new HttpResponseType(new GcdtestState(_GCD)));
}
else
{
this.LogError("Action is not GDC");
httpQuery.ResponsePort.Post(
new HttpResponseType(new GcdtestState(-1)));
}

yield break;
}

Besides computing the greatest common divisor and returning it as a http response, this handler does not do too much. It analyses whether the passed Action equals GCD and if so it tries to take the (hopefully) supplied parameters M and N. The service uses M and N to compute their GCD and if successful, passes the result back. If an error occurs, this service returns -1. The handler does not update the service's internal GCD state because of the following recommendation from the MRS help :

"As both GET and QUERY requests are defined by DSSP as not having any
side-effects, GET and QUERY handlers should be marked as
ServiceHandlerBehavior.Concurrent using the ServiceHandler attribute so that the
infrastructure knows that these handlers can run concurrently. "

3.With the handler in place, we may test our service. So we execute it by opening a browser and typing in the following URL

http://localhost:50000/GCD?Action=GCD&M=15&N=3

and this will return the correct result of 3. Note, that depending on you configuration the port and service name might be different. In fact, in the previous tutorial the service's name was GCDService, so you might want to take this into consideratio.

Although this was only a minor sample, I am trying to do something more meaningful with DSS and I hope to provide another small tutorial soon. So read you soon.

Christian


A simple GreatestCommonDivisor service in C# - Part 1
2007-09-15T17:58:00.000+02:00
I was finally able to get the GCD service up and running. Essentially it does nothing different than my previously posted GCD service, which is implemented in VPL. So to recall, this service computes the greatest common divisor of two positive integer numbers (inputx, inputy) and outputs the result as greatestcommondivisor.

Based on this description of what the service does, the remainder of this post will guide you through the process of how I built such a rather simple DSS service using the MRS object model and C# as implementation language (as mentioned you could also choose VB.NET, C++).

This kind of tutorial is divided into distinct steps beginning at creating a new service project to the final result being the service we want.


Create new DSS Service
The first thing one has to do in order to set up a basic GreatestCommonDivisor service is to create a new DSS service.We will do so by creating a new Visual Studio 2005 Project. More specifically it is a "Simple DSS Service (1.5)" project (it is assumed that you have MRS 1.5 installed). Select the mentioned project type and name it as you please (e.g., "GCDService") (see here for more detail). This will create a file for the service (e.g., GCDService.cs) a manifest file (e.g., *.manifest.xml) and a file for the types used by the service (e.g., GCDServiceTypes.cs).

Define what is the objective of the service
The service should do nothing special, just compute the greatest common divisor of two non-negative integer numbers m and n.This can be easily accomplished via euclids algorithm. In a previous post about python, I gave a recoursive implementation for this algorith, which is why I won't do it here again. So let us assume we have built a function, which implements euclids algorithm. The function's signature might look like this

public static int ComputeGreatestCommonDivisor(int m, int n)
{/*function's implementation not shown*/}

Define the input message
A DSS Service accepts input messages of some form coming from some input port, handles these messages and sends some output message as a response to its ouput port. For example, to get information about the state of a DSS service, this service has to handle a Get request, i.e. a "Get" message sent to the input port of this service. The DSS service receives the "Get" message does something and might respond to this message by sending "Hello World" as answer to its output port.
Similarly, our "GreatestCommonDivisor" service might get a request to compute the greatest common divisor (GCD) of two non-negative integer numbers n and m. Therefore, such a request might incorporate the n, and m sent to our service and the expected response might be the GCD of m and n. Consequently, we have to define such a request or how such a GCD message must look like to be accepted as GCD message by our service and to be handled appropriately. The following lines of code, which we add to the types source code file (e.g., GCDServiceTypes.cs), define such a GCD request

[DataContract(Name="ComputeGreatestCommonDivisor")]
public class ComputeGCDRequest
{
private int _inputX;

[DataMember(IsRequired = true, Name = "InputX")]
public int InputX
{
get { return (this._inputX); }
set { this._inputX = value; }
}

private int _inputY;

[DataMember(IsRequired = true, Name = "InputY")]
public int InputY
{
get { return (this._inputY); }
set { this._inputY = value; }
}

public ComputeGCDRequest()
{
this.InputX = 1;
this.InputY = 1;
}
public ComputeGCDRequest(int x, int y)
{
this._inputX = x;
this._inputY = y;
}
}

The ComputeGCDRequest defines how a request to our service has to look like. It defines m and n (InputX, InputY). Each request has to be marked with the DataContractAttribute attribute, so DSS can wire things up for us. Fields we want to incorporate in our request have to be marked with DataMemberAttribute attribute (those fields are part of the message serialization process when the ComputeGCDRequest message is serialized over some channel). These two attributes take some optional arguments such as "Name" and "IsRequired".
Define a message handler for the input message
The sheer presence of such a GCD request message type won't bring us far. We have to do define a GCD request (I), and add this GCD request to list of requests understood by our service (II). Afterwards we have to set up a mechanism that whenever a GCD request is issued to our service, takes the message, which abstracts this request and acts accordingly (III). So defining a GCD request serive, involves defining what the incoming GCD request message body looks like and defining what the result of processing a GCD request is, may it be success or failure. The following lines of source code, added to the GCDServiceTypes.cs, define a ComputeGCD request type ...

public class ComputeGCD :
Query<ComputeGCDRequest, PortSet<GCDState, Fault>>{

public ComputeGCD(int m, int n) :
base(new ComputeGCDRequest(m, n))
{
this.Body.InputX = m;
this.Body.InputY = n;
}

public ComputeGCD() :
base()
{ }

}

The ComputeGCD request type, subclasses the Query<> type, and defines the incoming message to be our previously declared ComputeGCDRequest message and the result will be a GCDState on success and the pre-defined Fault on failure. A Portset is a collection of ports (a set of ports) and a port is just an abstraction that allows services to communicate with each other. So to signal that our GCDService actually understands the ComputeGCD type, we have to add this type to the GCDService service's operations port set, which is defined in the GCDServiceTypes.cs file.

[ServicePort()]
public class GCDServiceOperations :
PortSet<DsspDefaultLookup, DsspDefaultDrop, Get, ComputeGCD>
{}

Now that our GCDService declares being able to understand GCD requests, we have to make him do so. More specifically we have to set up a message handler that jumps in whenever a GCDRequest is sent to our GCDService. The following lines of code, added to the GCDService.cs will be in charge of this.

[ServiceHandler(ServiceHandlerBehavior.Exclusive)]
public virtual IEnumerator ComputeGCDHandler(ComputeGCD computeGCD)
{
int M = computeGCD.Body.InputX;
int N = computeGCD.Body.InputY;

int gcd = ComputeGreatestCommonDivisor(M, N);

this._state.GCD = gcd;

LogInfo("=========\r\nGcdTest\r\n=========");
LogInfo(string.Format("M = {0}\r\nN = {1}\r\nGCD= {2}",
computeGCD.Body.InputX,
computeGCD.Body.InputY,
this._state.GCD));

computeGCD.ResponsePort.Post(new GCDState(gcd));

yield break;
}

The ComputeGCDHandler handler takes the ComputeGCD request as input and unwraps the necessary InputX and InputY fields from message's body. It then uses these two numbers as input to our ComputeGreatestCommonDivisor method, which computes the greatest common divisor and stores it in the gcd parameter. This gcd parameter is stored into the state of the service, which is of type GCDState. This GCDState encapsulates the state of the service, which is the greatest common divisor computed by the service. Actually the state is not really necessary, because we don't do much with it. At last, the message handler outputs the result of the operation to the output port for success, which was of type GCDState. The LogInfo calls are merely for debugging. Since this service alters its internal state, we have to make sure that this happens in an exclusive fashion, i.e. while updating the state no access to the state is granted. This is what the

[ServiceHandler(ServiceHandlerBehavior.Exclusive)]

Attribute declaration is for. It ensures that no race condition can occur by exclusively granting access to the internals our service.
Define the GCDState type
What is left, is to define what the state of our GCDService looks like. As mentioned, our service doesn't need to have a state but I have to decided to give it one (mainly for learning purposes). The GCDState type is define in the GCDServiceTypes.cd and can be modified like this

[DataContract()]
public class GCDState
{
private int _GCD;

[DataMember(IsRequired=true, Name = "GreatestCommonDivisor")]
public int GCD
{
get { return (this._GCD); }
set { this._GCD = value; }
}

public GCDState()
{
this._GCD = 1;
}

public GCDState(int gcd)
{
this._GCD = gcd;
}

}
Let's test
Now that we have set things up. We are ready to build the service and test it. Therefore compile everything. Open the MRS Visual Programming Language to build a new test service using our GCDService. I have done that and the test service can be seen here (my GCDService is named "GreatestCommonDivisor"). 

I hope you enjoyed building this service as much as I did and I hope to have something ready for you asap.
Christian



Online Lectures
2007-09-13T14:25:00.000+02:00
Hi folks,

I found this link about online learning in video form on another blog and thought I could repost it here

http://videolectures.net/

so thanks goes out to

http://smart-machines.blogspot.com/

Both links are available in the sidebar.

Other online lectures


http://www.researchchannel.org/prog/displayinst.aspx?fID=880

Christian


Microsoft Robotics Studio - First Sight
2007-09-08T18:16:00.000+02:00
Microsoft Robotics Studio (MRS)

I have recently come accross this great piece of new technology, offered for free by big MS [1]. MRS allows to program robots and other external devices via a visual programming language (VPL) or your prefered .NET programming language, such as VB.NET or C#. MRS main abstraction is a service.
 
Assuming you use VPL, a service is graphically represented as a box. Services exist in their own space and can be combined via message passing. In fact, services communicate via a SOAP-like protocol. This communication act is graphically represented by wires between services. Where such a wire connects the output of one service to the input of another. It is up to the developer of a service to decide what a service does, i.e. what kind kind of messages a service understands and what output a service produces. Therefore one can develop rather simple services such as a NoOP service, which does nothing, to a more complex service that for example takes a picture from a webcam. The great news is that MS ships MRS with a bunch of pre-built services, such as a Text-to-Speech service. This service takes some input message and renders it as its audio representive.
 
Since I have been able to play around with MRS, I wanted to share my first project, which calculates the greatest common divisor of two positive integer number m and n. Currently it is assumed that m is greater than n. The main routine that computes the gcd of m and n can be seen below here. As in yesterdays post, we make use of the fact that gcd (m, n) = gcd (n, r) where n = m % n and % is defined as the modulus of m and n. At the moment there is no swapping of m and n, in case n is greater than m (gcd (m,n) = gcd(n,m)). A possible example setting can be seen here. This example simply takes 10 and 5 as input and produces the expected output 5. I hope that this simple service will be one of many to come on my road to do cool stuff with MRS.

[1] Microsoft Robotics Studio: http://msdn2.microsoft.com/de-de/robotics/bb625969.aspx



Working the Snake - Python
2007-09-07T08:32:00.001+02:00
I finally found my way to (Iron) Python[1][2] - well I did some Python in the beginning of my studies but lost focus after some time. The experience was quite impressive, since development time is greatly reduced by such a dynamic language. I managed to get some small programs running in less then 1 hour and of course I want to share them with you - precious audience. Since these are my first scripts, I assume that they are  not quite correct/stable/... - they are simple and not very error-safe (no checking of arguments ) ...

The first is some simple factorial program, which tries to find the greatest common divisor (gcd)of two numbers by employing the fact that gcd (x, y) = gcd (y, r) where r = x mod y. Since I do not know how a scope for loops can be created (scoping a while/for loop) I did the routine recoursively. The second function builds on the first and is allows to ask whether some number x is a prime number by using the simple strategy of finding a gcd within the range of 1..root(x)


import System
def gcd(x,y):
    if y == 1 : return 1
    elif y == 0: return y
    elif x == y : return y
    elif x return gdc(y,x)
    n = x % y
   if n == 0: return y
   return gcd(y, n)

def IsPrime(x):
   if x == 1 : return 1
   elif x == 2 : return 1
   elif x == 3 : return 1
  tempsqrt = System.Math.Sqrt(x)
  tempsqrt = System.Convert.ToInt32(tempsqrt)
   for i in range(tempsqrt) :
    j = i + 1
    divisor = gcd(x,j)
   if divisor != 1 : return 0
   return 1


The second program is about the all time recursion favorite - the fibonaci numbers ...

the Fibonaci (Fib ) numbers are defined as follows

Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-2) + Fib(n-1)

example

n             0  1  2  3  4  5 6
Fib (n)   0  1  1  2  3  5  8
and here is the program - putting python suggar just around the exemplified formulae

import System
def Fibonaci(n):
   if n <= 0: return 0
   if n == 1: return 1
   return Fibonaci(n-2) + Fibonaci(n-1)

References:

[1] IronPython - www.codeplex.com/IronPython
[2] Python - www.python.org


2007-03-22T21:31:00.000+01:00
Well not much happened today. I was able to implement a triangle filling routine and read a bit on .NET remoting. I thought about how to implement a Z-Buffer for my small system and thought about homogenous clipping as well.

The problems I have right now are:
I want to implement basic triangle 2D screen-space clipping. Which itself is not a big deal but I do not want to implement a polygon filling scan-line algorithm. A polygon may be the outcome of a triangle clipped against a rectangular clip window. So what is there to do ? Either clip a triangle which produces a polygon and implement a "simple" scanline algorithm to fill that polygon. The other option is of course to split the triangle into a series of triangles. Either way has its intricacies.
As mentioned in yesterday's I want to implement homogenous clipping for triangles. Which makes things even more complicated then a simple 2D clipper. The reason is that not only a triangle can be split into a series of triangles during the clipping process but also extra state is necessary. Remember, we do not only clip the triangle and generate new triangles that form the clipped triangle but we have to generate appropriate values for associated color, texture and normal data.
I want the filling of the z-buffer and the filling of the framebuffer to be separate. Although expensive, I want to maintain this separation for flexibility.
With these "basic" things I should be busy for some days :D ...

For all the people who want to do some graphics stuff I recommend the following books. At least they served my understanding quite well.
Practical Linear Algebra: A Geometry Toolbox
Computer Graphics: Principles and Practise
Real-time Rendering
Math for 3D Game Programming & Computer Graphics
a web reference on the topic
3D Graphic Engine Essentials
Software Rendering School
Happy reading


2007-03-21T13:26:00.000+01:00
In reference to yesterday's post I continued a bit and implemented the following
Line drawing via DDA and Bresenham
Basic Cohen-Southerland Clipping in 2D
These routines may not be the fastet but this actually not the point since the code is written in managed C# and makes no use of any optimizations. It's sole purpose is learning. The next things that need to be done are
drawing of triangles (including basic fill)
a Z-Buffer (at least I have already set up the basics)
clipping in homogenous clip space
simple scene-graph
If anyone is interested in some sources - I can either post them here or put them online on my website. I also thought about making the whole engine a bit more flexible. So I thought I could
divide all the pipeline elements into pipeline stages. Each stage has access to some renderstate and does only execute on some defined input. As a consequence one would get something similar to vertex and fragment programs and a non-fixed function pipeline. But of course this is only some thinking and I should better get things set up before reasoning about making it most flexible.


2007-03-20T10:48:00.000+01:00
I have been quite busy these days writing my own small 3d engine. I did some small stuff with OpenGL in the past and to understand at least a bit better what is going on behind the scenes, I decided to do my own small renderer. I know, why write another software renderer if there is so much available. But at least for me I can say, that what I implement I do understand a little better.

Of course, it takes some time to get the basics running. Until know it does only little (only perspective projection is covered), such as the transformation from an object's local space to actual screen space. But many things are left to do such as homogenous clipping, 2D clipping, painting ...

The things I want to implement as a next step are
rasterization (lines via bresenham, basic filling - flat shading)
homogenous clipping
2d clipping
a primitive scene graph
Since basic rasterization often produces flicker, I looked for a basic method to do double-buffering with windows forms and .NET and these are some of my findings:

Enable double buffering for a control (e.g., Form) via setting a control's property DoubleBuffered = true
Set a control's style via calling Control.SetStyle(ControlStyles.AllPaintingInWmPaint | ControlStyles.OptimizedDoubleBuffer, true);
This gives you basic double-buffering in an instant. But sometimes one wants to have a bit more control over the actual double-buffering process and therefore, the .NET framework provides several new classes in the System.Drawing namespace, such as:
BufferedGraphics
BufferedGraphicsContext
BufferedGraphicsManager
You can obtain an AppDomain's main BufferedGraphicsContext by using the Current property of the BufferedGraphicsManager or you may create your own BufferedGraphicsContext. A BufferedGraphicsContext can be used to create a BufferedGraphics object (the Off-screen buffer you want to use for drawing) and associate this object to an output device (e.g. display).
Use a BufferedGraphicsContext.Allocate method to create a BufferedGraphics object and to render the contents of such a BufferedGraphics object to an output device use the BufferedGraphics.Render method, which allows you to set the desired output device or use the one supplied to the BufferedGraphics.Allocate method. Drawing to such an off-screen buffer is easily done via a BufferedGraphics.Graphics property.

Of course, if this is not what you want you may still use a Bitmap object to do all off-screen drawing and draw that bitmap to the display.


Back again :D
2007-03-11T00:17:00.000+01:00
A long time ago ... in this galaxy :D ...

Well, it has been a while since I wrote the last post. But since I was finally able to conclude my studies this thursday, the 8th of march, I hope to be around more often. I will probably start my first work on april the 2nd. My new employer will be Avanade Deutschland GmbH (german office of Avanade Inc.). And I am quite happy about that since I expect a great learning experience - well but let's see ...

Since I am not too busy these days I will try to have a look onto several things such as SQL Server 2005 and maybe I get my hands dirty with Phoenix again.

Best regards

Christian