Hi,

I am currently developing a "chimeric" language that may have AI uses, hence this post. The language will combine features of Prolog and Haskell with two new features: implications and structured output. Currently I am defining the grammar that will be allowed in version 1.

The above may seem vague, so I will list some examples of what will work when it is completed. If you already have a basic grasp of Prolog and Haskell, everything should be fairly understandable. Let's begin.

--------
isExpressed(substance, gene) :- expresses(substance, gene).
expressedGenes(substance) = [x | x <- expresses(substance, x)].
--------

Before introducing anything really new, let me explain the above. The first statement is true when 'substance' expresses 'gene'; A fairly simple Prolog construct.

The second statement uses the list comprehension feature from Haskell. It will return a list of genes expressed by the given 'substance'.

--------
commonElements(xs, ys) = [x | x <- xs, y <- ys, x == y].
commonGenes((x:[])) = expressedGenes(x).
commonGenes((x:xs)) = commonElements(expressedGenes(x), commonGenes(xs)).
substancesThatExpress((gene:[])) = [sub | sub <- expresses(sub, gene)].
substancesThatExpress((g:enes)) = commonElements(substancesThatExpress(g), substancesThatExpress(enes)).
--------

Here it gets a little more interesting. :-)

commonElements returns a list of elements that exist in both of the list arguments

commonGenes returns a list of genes that a given list of substances both express

substancesThatExpress returns a list of all substances that express a given list of genes

So far, everything above comes from either Prolog or Haskell -- or some combination thereof.

--------
neuron(name) -> expresses(name, 'gene1'), expresses(name, 'gene2'), expresses(name, 'geneN').
--------

The above is an example of an implication (notice the familiar mathematic notation A -> B, read A implies B). The use of this feature will be, primarily, to ease the input of data. Say the following line is encountered after the above:

--------
neuron('corticoSpinal').
--------

This would then assume that all of the predicates are true. In this example, 'corticoSpinal' would express 'gene1', 'gene2', and 'geneN'.

The final feature of version 1 will be structured output. A slight modification to a previous predicate will serve as a decent example.

--------
isExpressed(substance, gene) :- expresses(substance, gene) ? gene + " is expressed by " + substance : gene + " is NOT expressed by " + substance.
--------

If the predicate is true, the first string is displayed. Otherwise, the latter is.

My purpose in posting this is to get an idea of how useful it will be and some applications for it. As my examples demonstrate, I am biased towards using it to help with genetic research.

The language will be developed as a special topics computer science course next semester, so my professor may not allow me to develop the first version as an open source project. After the course, however, it will definitely go that route.

Any comments and/or critiques will be appreciated. :-)

Thanks,
-Steven

What's the point to create a completely new language? Most time it will be better to stick to an existing language and build a library or extension to it. In this case, it seems that a new class in Haskell with a -> operator and a simple reasoning engine would suffice.

Of course, doing a practise in a Language Design course is a very good reason! 8) Before any design, you should state very clearly what this language should accomplish and in what form it's different from previous ones. You may benefit of reading the design goals for some popular ( 1 , 2 ) and not so popular languages ( 3 , 4 ).

If the focus is in learning how to program a language, it should have a very simple syntax and few built-ins. If you mean it to be used in genetic research, make this a design goal and follow each customization needed to facilitate that job; don't hesitate to throw out the 'general language' goals.

Thanks for the informative reply. I will do my best to answer your questions. Again, comments/critiques are welcome.

What's the point in creating a completely new language?

I could, as you suggested, build an extension to Haskell, but -- I very well may be wrong -- I believe Haskell only allows you to define functions. For the genetic research angle I am going for, data about the existing environment must be known before any computations can take place, which is why I included the Prolog.

In addition to the above, a further goal of mine is to use the language as a server and allow researchers to query the server so they can test and verify different theories before taking them to the lab. Because non-computer science researchers will be allowed to formulate their own queries and make additions to the environment, an easily understandable format needs to be used*; another plus for the Prolog-style syntax.

Finally, in order for my work to count as an independent study in Computer Science, I have to abstract the language so that it can be used for a variety of tasks. And, well, I want to learn how to design a language. ^_^

As always, comments, critiques, and suggestions are very welcome.

-Steven

------------
*An example modification that a researcher could input

transcriptFactor('tf-alpha'). // tf-alpha is added to the environment
activates('tf-alpha', 'geneXYZ'). // tf-alpha activates geneXYZ
deactivates('tf-alpha', 'gene1'). // tf-alpha turns off gene1

then the researcher could re-run previous queries, add more stuff, re-run queries, ad infinitum until they get the desired result
------------

In this case, I believe there is more at stake than just design practise. Prolog and Haskell are both high-level languages with fundamentally different approaches.

• Prolog shines with its logical and inductive power. The unification is extremely flexible and search is fast when used correctly.
• Haskell shines from the functional point of view, with very powerful meta-operators. Intrinsic lazy evaluation is one of my favourite features.

Combining the two has been a goal for many people on either side, as they both stand to benefit. It's not been done to my knowledge, so it can't be that straightforward!

But, there's nothing wrong with trying. :-)

Since you stated that unification -- when done correctly -- is powerful, do you know of any web resources that discuss or explain the proper way of implementing the feature?

...or maybe a good book? I'm thinking of purchasing either Modern Compiler Design since it has sections on functional and logic based interpreters, but the reviews of it [on Amazon] are fairly mixed. Any suggestions?

-Steven

Without any knowledge of both Prolog and Haskell:

I want to point you to the Ruby language.

Its a very high level OO language and takes the best of perl, python, java and a couple of others. Ruby has no primitives (like java), everything is a objekt. It allows the overloading of signs (+/-/*) and has extremely powerfull iteration constructs (maybe compareable to Haskell's). There are implementations for all noticeable platforms and also a Java port (JRuby). One subproject tries to put Ruby on top of the proposed Perl6 VM. Even without it: Ruby can use perl modules without hassles.

...just my 2 cent.

Ruby may work, but Haskell and Prolog both work on different paradigms than standard structured languages like Perl, Python, etc.

With Prolog, you basically give it a "knowledge base", ask it questions, and let it infer what is true or various relationships. The programmer doesn't have to mess with implementation details such as how to search through the knowledge base or match queries. You just give it what you want to find, and it does the rest.

Haskell works in a ... similar fashion [in regards to avoiding messy details], but allows the programmer a lot more flexibility when defining functions. For example, I am sure you have played with or have seen an implementation of quicksort in some structured language; a nice ugly mess. Here is quicksort in Haskell:

quickSort [] = []
quickSort (x:xs) = quickSort [y | y <- xs, y < x] ++ [x] ++ quickSort [y | y <- xs, y >= x]

Two lines that are fairly easy to understand. ^_^

My initial goal is to merge the strengths of the two languages that I think are most useful: the inferencing ability of Prolog; and, primarily, the list comprehension features of Haskell. If I can build an interpreter that manages the above, I will start adding more features from each language.

On the other hand, Ruby could be used to make an implementation of the interpreter. That might make an interesting project one day. :smirk:

-Steven

Perhaps you should read about the Constraint Logic Programming paradigm, it could give you some nice ideas to include in your language. It is a more powerful reasoning method than Prolog's, basically consists in a branch&bound depth-first search with forward-looking and intelligent backtracking.

Constraints look very interesting and seem like they would fit in as an interesting component. Just to make sure I understand what you're thinking, take a look at the following and let me know if it fits with your thoughts.

Let me think of a trivial example and some syntax. Hrmm... Never using that paradigm before, it is difficult for me to think of one. Well, I will have to do some programming in a language like Eclipse before I can implement something like that. Maybe a feature for version 2?

If I understand correctly, constraints define variables based on their relationship with other variables. Is that right?

As far as implementing the language goes, I plan on reading some in-depth material about both the Warren and Vienna Abstract Machines this weekend to fine tune my thoughts.

-Steven

Constraints are best used with multi-valued variables, i.e. variables with domains bigger than 2. First you define which variables exist and which are their domains, and then you add constraints that forbid some combinations of values to occur simultaneously.

A trivial example? Suppose you have two series A and B of "nucleotide" variables: A1 A2 A3 A4 ... and B1 B2 B3 B4 ... Each of this Ai and Bi variables have the same domain = {adenine, thymine, guanine, cytosine}.

Then you want to match the two series and add a "base pair" constraint between variable A1 and B1, another similar constraint between A2 and B2... Each constraint allows the variables to take only these value pairs: (Ai=adenine, Bi=thymine) (Ai=thymine, Bi=adenine) (Ai=guanine, Bi=cytosine) or (Ai=cytosine, Bi=guanine). All these constraints are equal except for the variables involved.

So if you later assign Ai with value adenine, you can propagate the constraint and prune from Bi the values adenine, guanine and cytosine which are not supported. In this example this leaves you with only 1 value left in the domain of Bi so you can also assign Bi with the value thymine.

If you ever reach a state with an empty domain, for example if Bi was previously decided not to be thymine, you have to backtrack and erase the decision to assign Ai with adenine.

Note that if later in the program you want to try and match the chain A with B shifted one place, i.e. clean the constraints Ai-Bi and put a new constraint between each Ai with B(i+1), then it is a different "constraint problem" and you have to restart the "constraint solver" procedure - the information gathered through the previous solution search is no longer applicable to this new problem.

That was the perfect example for me; thank you so much. I now understand what constraints are and how useful they can be. My mind is now in a similar state to when I first learned of functional programming after about seven years of imperative programming. Wow. :satisfied grin:

Tomorrow I present my project to the chair of the Computer Science Department for final approval. Methinks that adding constraints to the language will make an excellent project for the summer or fall semester.

On another note, does the syntax of the language bother anyone? Specifically the fact that a predicate can return a list? I'm afraid that some people -- especially those with a strong Prolog background -- may find that notion uneasy.

Thanks again!

-Steven

Note that your language contains both predicates and functions. A clever idea would be to cleanly distinguish them.

You can define a Boolean type for predicates, and a typecast from empty and non-empty function returns to boolean. The typecast may be implicit (maybe in the :- operator?) or explicit.

I was thinking about that as I lay in bed this morning. My initial idea was to allow predicates to return lists, but my teacher was having trouble with that. So I started thinking of implementing predicates as a boolean function [easily definable in Haskell] with the ability to unify with other predicates, which actually seems to be easier from an implementation standpoint.

Boy, aren't the things I think about in bed oh-so interesting? :rolleyes:

-Steven

Hi :)

If you are going to program serious AI, use Common Lisp... It is a lot of work towards AI programming in the language and libs...

:)