The Power of Large Language Models for Translations

One of the earliest use cases of large language models, i.e. text-based generative AI, was for translating text provided in one input language into another language - a literal transformation of source to target if you will - greetings almighty transformer model.

Before that, translation was often based on rule-based and or statistical models like Hidden Markov models, and later some variant of the recursive neural network models like RNN and LSTM. But then the transformer came, and blew everything that was before out of the park.

While many more powerful, novel and interesting adoptions of generative AI for text have taken center stage in the last month and years, the translation of text from one language into another language still feels magical. Just a few years back we would have searched for individual words in our offline or online dictionaries and translated between German and English or any other language word by word. We would have depended on our or someone else's expertise of forming natural and gramatical sentences. We would have looked up similar uses of a word, reference texts and the like in cases we wanted to know more or simply weren't sure.

Now, we enter our words, phrases, sentences, paragraphs or even whole documents into a translation service like google translate, or DeepL's translator. We can give guidance in terms of tone, grammaticality, verboseness, target audience, and generally steer the generation towards our intenteded use and recipients.

You may have experienced PowerPoint's live translation of speech. While we browse through our slides, talking in whatever language, english subtitles are pushed out almost synchronously. Yes, sometimes it goes wrong, not always is the right word used. But just few years back the online translation was a service that was only used for high-profile events or in exceptional settings. Today, it is available within a consumer application for a moderate price! We simply press a button and in the matter of seconds - Hola amigo. There you go understandable utterances. Sure, this might not necessarily be at the level required to win the Purlitzer price, but hey! It comes in the language of your choice! Yes, the target language needs to be a somewhat actively spoken language otherwise only limited training data is available. But you get my point.

Pair this with generative model's power to take a few samples of our voice and recreate our speech bit by bit. Pair this with generative's power to create somewhat realistic images and avatars of us - et voilà. You have a virtual replica of you. Explore the countries of the world. Even if you do not speak the language of the country you are visiting that moment. There is a good chance that your avatar does! These are magical times indeed.

Generative AI in Action: Streamlining Presentation Creation

 

Introduction

In today’s fast-paced corporate environment, managers and executives frequently find themselves tasked with presenting complex information to diverse audiences. Crafting a compelling narrative for a presentation—whether it's about a project update, evaluating a technology, or pitching an idea—requires time, focus, and creativity. But what if there was a way to streamline this process while enhancing its effectiveness?

Generative AI can act as your creative assistant, helping you outline, structure, and refine presentations tailored to your audience's needs. Surely, it often acts as my personal assistance.

In this post, we’ll explore a real-world use case of leveraging Generative AI to create a presentation, demonstrating how it can save time, enhance communication, convince and possibly excite your audience.

From Blank Slide to a first Narrative

Picture this: you’re tasked with introducing a new technology to a mixed audience of experts and non-specialists. You sit down to create your slides, but the empty canvas stares back at you. You may have a title, but translating your knowledge into an engaging presentation feels daunting.

Some key questions arise:

• How do you structure your presentation for maximum clarity?
• How do you simplify complex jargon for non-experts?
• How can you ensure the presentation resonates with your audience?

These are common challenges for managers, often exacerbated by tight deadlines and competing priorities. Generative AI offers a solution.

Using Generative AI to develop your presentation

Define the Objectives

Before turning to Generative AI, start by clarifying the goals of your presentation. For instance:

1. Introduce a new technology in a clear and engaging manner.
2. Communicate key strengths, weaknesses, and use cases.
3. Establish yourself as a knowledgeable and approachable resource.

These objectives set the foundation for your AI-powered workflow.

Crafting a Prompt for Generative AI

A well-designed prompt is critical to generating meaningful results. Your prompt should provide:

1. Context: Describe your role (e.g., project manager, team lead) and the purpose of the presentation.
2. Audience Details: Specify the audience composition (e.g., non-specialists, executives).
3. Desired Outcomes: Outline the presentation’s goals, such as informing or inspiring action.
4. Format Preferences: Include details about the structure, tone (e.g., formal, engaging), and desired interactive elements (e.g., quizzes, demos).
5. Duration: Mention the expected length of the presentation.

Surely, there are many more elements you must consider when developing a compelling presentation. But to get started this provides you with a good first framework.

Applying the above to a particular case, you may start by:

I am a team manager preparing a 10-minute presentation introducing non-specialists to the basics of baking white bread. The presentation should be engaging, interactive, and designed to excite the audience about baking.

Refine and verify your proposal

Generative AI can draft slides, suggest narratives, or even create interactive elements. However, you remain the editor-in-chief:

• Verify Accuracy: Double-check facts and figures generated by the AI.
•  Tailor for Relevance: Ensure the content aligns with your goals and audience needs.
•  Add Personal Touch: Incorporate anecdotes, examples, or visuals to make the presentation uniquely yours.

A Practical Example: Introducing a Hobby with AI 

To illustrate, let’s say you want to use Generative AI to prepare a fun, engaging presentation about your hobby: baking bread. Here’s how AI can assist. Remember the key is to craft a meaningful prompt. 

Create a 10-minute presentation introducing non-experts to baking white bread. The tone should be fun and interactive, and the goal is to excite the audience about trying it themselves. Include step-by-step instructions, a quick quiz, and a slide with tips for beginners.

This looks good enough for a start. We may include some details about ourself. We may also add details on how language and tone of the presentation should be or that we would like to include content on common definitions, terms, etc. This is something you may experiment with and evaluate the differences in generated responses.

So, if we feed this prompt to Claude what will we get - head down to the end of the article to see for yourself. Claude create an engaging interactive presentation structure. It entered a little quiz and also questions throughout the presentation. A practical section on baking an actual bread makes the topic lively and memoryable.

What's in it for me?

Now, you may be a bit sceptical, thinking why should I care? I have heard that Generative AI hallucinates or something else. Surely, if you are the expert in the content and in creating presentations in the blink of an eye, then Generative AI may not have much to offer here. But I argue, that you may still learn a few tricks simply by seeing what narrative and structure is generated based on your understanding and provided input. If you are like me, then you may care about:

• Time Efficiency: Speeds up the initial outline and draft creation process. 
• Enhanced Creativity: Offers fresh perspectives and ideas.
• Tailored Outputs: Adapts content for diverse audiences and objectives. 
• Consistency: Ensures structured, cohesive presentations. 

By integrating Generative AI into your workflow, you can focus on refining and personalizing content rather than starting from scratch.

Call to action

Have you tried using Generative AI in your role? Share your experiences in the comments or reach out for a free guide on crafting effective AI prompts for presentations!

Let Generative AI draft your Job Profiles

Today’s post is about how I use Generative AI to streamline one of my day-to-day responsibilities. As a group manager, efficiency and precision are at the core of everything we do. Generative AI is a game changer to analyze and transform natural language. Naturally, I use Generative AI to draft documents. One such workflow involves drafting job profiles. So, let’s dig deeper.

The Traditional Way of Creating Job Profiles

Before Generative AI, whenever I had to create a job profile, I went through the same motions repeatedly:

• Solve writer’s block
• look at post profiles
• and a lot of back-and-forth.

I would get input from various sources, compile responsibilities, required skills, and experience, and then refine the language to ensure it was clear and engaging. This process cost time and often inconsistent.

Enter Generative AI

With Generative AI, we’ve cut down the time spent on drafting job profiles significantly. Here’s how it works in our day-to-day operations:

1. Data Input

We start by feeding the AI with data. This includes information about the role, key responsibilities, required skills, and any specific qualifications. We also input data from previous job postings and performance metrics to give the AI a comprehensive understanding of what we’re looking for.

2. AI-Powered Drafting

Once the data is in, the AI gets to work. It analyzes the input and generates a draft job profile. What’s amazing is that the AI can tailor the language to fit our company’s tone and branding, ensuring consistency across all our job postings.

3. Human Touch

While AI does the heavy lifting, we still add a human touch. We review the draft. This is critical, since not everything that the AI generates makes sense to us. So, we review and adjust as we go. This collaboration between human creativity and AI efficiency ensures that the final job profile is polished and precisely targeted.

Why Generative AI Rocks for Job Profiles

Here are a few reasons why I love using Generative AI for creating job profiles:

·         Time-Saver: Instead of researching countless companies and profiles to hit the right note when it comes to external communication, I simply have the AI integrate external posts and adapt them to what I need.

·         Consistency: The AI ensures that all job profiles maintain a consistent tone and structure.

·         Adaptability: As I enter a recruitment process, needs my change slightly around the core themes. The AI easily adapts to new requirements and ensures job profiles are always up to date.

Real-World Impact

Since implementing Generative AI, we’ve noticed a significant improvement in the quantity and quality of candidates applying for our positions. The AI’s ability to pinpoint key skills and qualifications has made our job profiles more appealing to top talent. Plus, the time saved on drafting profiles means we can focus more on the interview and selection process, ensuring we hire the best fit for our team.

Final Thoughts

Embracing Generative AI has been a game-changer for me. It’s not just about saving time; it’s about enhancing the entire recruitment process. By automating one of the more mundane tasks, we’ve freed up valuable resources to focus on innovation and growth. Sure, you will tweak here and make an edit there but to have that first draft surely is liberating.

If you’re in a similar role or industry, I highly recommend exploring how Generative AI can benefit your candidate search process. Trust me, once you see the potential, you’ll wonder how you ever managed without it.

If you have any questions or want to share your own AI experiences, feel free to drop a comment below.

Generative AI: Your Always-Available Learning Partner

The AI Revolution Is Here - But What Does It Mean for You?

In the past two years, Generative AI has moved from research labs into our daily lives through applications like ChatGPT, Midjourney, or Anthropic's Claude. While the media buzzes with predictions about an AI revolution, the singularity or arrival of Artificial General Intelligence, many technical managers like myself are asking a practical question: "How does this actually help me?"

I found myself asking the same question. After all, I've been writing documents, sending emails, and creating presentations throughout my career. They served their purpose - so why change now?

The Training Dilemma

Consider how we traditionally improve our professional skills:

• We attend technical writing workshops
• We participate in project management training
• We learn presentation techniques

Yet, these traditional approaches often fall short for two main reasons:

1. The Practicality Gap
Many training methods are either too theoretical or conflict with our real-world experience
2. The Time Problem
There's often a significant delay between learning a skill and applying it, leading to knowledge loss

Enter Generative AI: Your Personal Development Partner

This is where Generative AI transforms the learning landscape. Think of it as having a knowledgeable mentor available 24/7, ready to:

• Review and improve your writing
• Explain complex concepts
• Provide customized tutorials
• Offer immediate feedback

The Key to Success: Quality Input

However, there's one crucial principle to remember: the quality of AI assistance directly correlates with the quality of your questions. Consider these two approaches:

Less Effective:
"Hey AI, tell me about writing better emails."

More Effective:
"Please review this customer communication draft and suggest improvements for clarity and professionalism, focusing on our technical product launch."

Critical Thinking Remains Essential

Remember: You're in the driver's seat. While AI can provide suggestions and explanations, you must:

• Evaluate the relevance of AI responses
• Verify technical accuracy
• Apply context-specific knowledge
• Make final decisions based on your expertise

Looking Ahead

In upcoming posts, I'll share my personal journey with Generative AI, including:

• Real-world implementation challenges
• Successful use cases
• Limitations and workarounds
• Practical tips for technical managers

Stay tuned to learn how AI can complement your skills while avoiding common pitfalls.


*This post is part of a series exploring practical applications of Generative AI for technical managers.*

Unpacking AI's Future: Insights from Stanford's Lecture Series with Eric Schmidt

In the ever-evolving world of technology, many of us are striving to make sense of artificial intelligence (AI)—a field that is rapidly reshaping industries and economies. While grasping the technical aspects of AI is one challenge, understanding its broader implications on the economy and by extension to our daily lifes is another. This is where expert insights coming from politicians, researchers, or economic leaders become invaluable. A standout resource for anyone interested in AI's impact on the economy is Stanford University's lecture series, "The Age of AI" (ECON295/CS323). This series offers a deep dive into the intersection of AI and economic trends, providing a nuanced view of what the future might hold. At this point the series has just been made available, while it seemingly started earlier in the year. The second lecture features Eric Schmidt, former CEO of Google. Schmidt brings a wealth of experience to the table, sharing his perspective on the current state of AI and its potential trajectory. His insights are particularly relevant for those looking to understand not just how AI works, but how it might shape global markets and societies. He provides a nuanced view informed by his work at Google, as an advisor to the US government, angel investor and philantropist in the space Fortunately, Stanford has made this valuable lecture series accessible to a wider audience through YouTube. Whether you're a tech enthusiast, an economist, or simply curious about AI, this lecture offers a rare opportunity to hear from one of the leading voices in the field. Don't miss out on this opportunity to deepen your understanding of AI's role in the economy. Check out Stanford Stanford ECON295/CS323 I 2024 I The Age of AI! Lecture 2, available now on YouTube.

Logtalk - Hello World

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)

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:

1. [English] New Mexico State University: Building and Programming Robots
   http://www.cs.nmsu.edu/~tson/classes/fall03-579/schedule.htm
2. [German] University of Potsdam: Programmieren in Prolog
   http://www.cs.uni-potsdam.de/wv/03SS/aktuell.html#SECTION00051000000000000000
3. [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
4. [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
5. [English] University of Toronto: Cognitive Robotics
   http://www.cs.toronto.edu/cogrobo/main/systems/index.html
6. [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)

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

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

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

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:

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


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


3. 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

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:

1. the gcd of two numbers x and y is equal to the gcd of x - y and y for y <>
2. the gcd of some number and 0 is the number
3. 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

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:

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


2. 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

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:

1. Words
   Description: A sequence of letters, possibly containing “-“ (bar), or “’” (apostrophe).
   Example: Hello, world, top-down, Mike’s, Andreas’, don’t
2. Simple Numbers (integer, float)
   Description: A sequence of digits, possibly containing a “.” (dot)
   Example: 1234, 12.343
3. Names, Quantities and Abbreviations
   Description: special words, stored in a name, quantity, abbreviation map
   Example: 5m (five meter), MS (Microsoft)
4. 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)

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

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)

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)

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:

1. The (German and English) alphabet contains only 26 elementary characters (variable symbols)
2. 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:

1. Simplification of additive (compound) term
2. 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)

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

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.