hakank.blogg

« maj 2009 | Main | september 2009 »

augusti 30, 2009

The Pop-11 programming language and Poplog environment

First I must apologize for the Swedish readers for including an english text here: Sorry about that. I may do it again, but this blog has not permanently gone English. It has, however, changed its focus somewhat in other ways from the start in june 2003.

Pop-11 and its environment Poplog is relatively unknown, originally designed for research and education in artificial intelligence. From What is Poplog:

Poplog is an integrated toolkit providing a highly extendable collection of languages and tools for teaching, research and development. By default it includes incremental compilers for three powerful AI programming languages
* Pop-11--the core language -- used to implement itself and the others;
* Common Lisp; and
* Prolog;
as well as
* Standard ML, a widely used functional language.

...

Most of Poplog is implemented in Pop-11, including the incremental compilers for all four languages and the integrated programmable editor.

Here I will mostly write about the programming language Pop-11, but also mention how it is possible to integrate Pop-11, Prolog, and Lisp. See the programs below.

Pop-11/Poplog is a huge system which includes - besides the four languages mentioned above and the VED editor which is also used for the help/teach system - much material for learning the system, as well as learning artificial intelligence. "Huge" above refers to the content of the system, not to the actual memory "footprint". For more about the size, see the entry Size at the Free Poplog page.

The language Pop-11 is Lisp-like in its approach but uses an Algol-like syntax. It has many of my favorite features of a programming language:

• interactive environment
• array/list comprehension
• pattern matching (on lists), and supports regular expressions
• functional programming, higher order functions
• multi-paradigm approach
• arbitrary precision

Some larger teaching examples

Here are some examples of the teach/help files. Many of these shows how to use a specific library, and some of them just teaches an artificial intelligence concept.

• Eliza, the famous Eliza program
• Analogy/Evans, Evans' Analogy program (simplified version)
• Poprulebase, rule based database, e.g. for expert system
• Objectclass, object oriented programming
• database, database for pattern matching etc
• matcher, the basic pattern matcher
• super, an extension of pattern matching in Pop-11's database super_example, more about SUPER
• grammar analysing sentences
• solver: a GPS and (General Problem Solver), STRIPS like solver
• solvems: another problem solving library
• storygrammar, generation of sentences given a grammar
• schemata
• SimAgent TOOLKIT,
• lists, how to use lists

Documents and links

• Free Poplog Portal
• Teaching material
• Primer, probably the best way of start to learning Pop-11
• Robin Popplestone's Pop-11 book (draft)
• How to think like a scientist, draft of Pop-11 version
• Rosetta Code: Pop-11
• Poplog online
• Wikipedia: Pop-11
• Mike Sharples, David Hogg, Chris Hutchison, Steve Torrance, David Young: Computers and Thought: A practical Introduction to Artificial Intelligence, online book on artificial intelligence using Pop-11 as programming language
• comp.lang.pop FAQ
• Wikipedia: POP-11
• Jocelyn Paine in Dr Dobbs 'Dobbs Code Talk' (Mars 2009): Poplog, continuations, Eliza, AI education, and Prolog

Mailing lists

• comp.lang.pop
• pop-forum
• pop-dev

My Pop-11/Poplog page

My Pop-11/Poplog page contains some of my Pop-11 programs. Some of them are the "mandatory" programs I always implement when learning a new programming language.

Some of the program below requires functions from the GOSPL (Global Open Source Poplog Library) library, such as split, split_with. GOSPL was available from www.poplog.org, but that site seems to be defunct right now. The library is now available from www.cs.bham.ac.uk/research/projects/poplog/, or more specific here: gospl_1_2_0.tar.gz

• init.p
  init.p: My init.p file.
• compiling
  compile_test.p demonstres how to:
  - compile a Pop-11 program to a saved (.psv) image,
  - compile to an executable program.
  Note: This was tested on a Linux machine (Mandriva).
• Concordance
  concord.p: Reads a file and show the number of occurrence of the words (sorted in order of occurrence). Requires GOSPL (see above).
• Project Euler
  euler_project.p: My Pop-11 solutions of the first 16 Euler Project problems. Requires newmemo.p, and GOSPL (see below). A note about the style in this program: When learning a programming language which has an interactive shell, I tend to use one-liners and array comprehension a lot. Especially in this case, since I used much of the principles used from my Lisp programs (using loop a lot).
• join (string)
  join.p is a small utility function to join the characters of a string.
  Syntax: join(string, separator)
  e.g. join('hello,world','|') results in h|e|l|l|o|,| |w|o|r|l|d. This is used for example in read_test.p.
• Lisp in Pop-11
  lisp_in_pop11_test.p demonstrates how to run (Poplog's) Lisp code in Pop-11.
• Grammar generation (swedish)
  mygram.p generates some swedish (nonsense) sentences given a simple grammar and lexicon. It uses the GRAMMAR library (which includes a simple english grammar and lexicon).
  
  The generating sentences is presented first as a parse tree, then the sentence.

  ** [s [np [snp_t [det_t ett]
                   [adj_t svagt]
                   [adj_aux_t [fastän trött]]
                   [noun_t handsfack]]]
        [vp [verb [grävde ned]]
            -
            [verb_aux [utan vett och sans]]
            -
            [np [snp_n [det_n en] [noun_n buske]]]]]
  
  ;;; The sentence:
  ** ett svagt [fastän trött] handsfack [grävde ned] - [utan vett och sans] - en buske.
  
  ;;; Flattened
  ** ett svagt fastän trött handsfack grävde ned - utan vett och sans - en buske.
  

  Which may be translated as something like

  a weak although tired glove department dug down - without wit or sense - a bush
  

  Also, see tparse_test_swe.p mentioned below for generating the parse tree from this sentence.
• Memo function
  newmemo.p defines a Memo function (from Robin Popplestone's Pop-11 book) and use it for the Fibonacci sequence.
• N-puzzle
  n-puzzle.p: 8-puzzle and 15-puzzle, etc using the library SOLVEMS.
• Pop-11 in Lisp
  pop11_in_lisp_test.lsp: Simple demonstration how to run Pop-11 code in (Poplog's) Lisp.
• Pop-11 in Prolog
  pop11_in_prolog_test.pl: Simple demonstration how to run Pop-11 code in (Poplog's) Prolog.
• Prolog in Pop-11
  prolog_in_pop11_test.p: Simple demonstration how to run (Poplog's) Prolog code in Pop-11.
• Primes / dynamic ("lazy") lists
  primes.p generates prime numbers using a dynamic ("lazy") list.
• Regular expressions
  Pop-11 has regular expressions, albeit with a slighly different syntax than we are used to. The program read_test.p reads a word list and test each words against the regular expressions of consecutive characters, e.g. ".*a.*.b.*c.*" (in Pop-11 'a@.@*b@.@*c@.@*'), ".*b.*c.*d.*", ".*c.*d.*e.*", etc.
  
  Using the standard Linux wordlist /usr/dict/words if found no word where there are 6 consecutive letters, but there are many of length 5. e.g.

  ** [Testing abcde a@.@*b@.@*c@.@*d@.@*e]
  ** [abecedaire abecedaries abjectedness aborticide absconded abscondedly
          abscondence absconder absconders abstractedness ambuscade ambuscaded
          ambuscader ambuscades ambuscadoed amebicide amoebicide bambocciade
          bambochade carbacidometer Cerambycidae nonabstractedness Oxylabracidae
          scabicide unabstractedness]
  Counter: 25
  
  ...
  
  ** [Testing qrstu q@.@*r@.@*s@.@*t@.@*u]
  ** [quasi-respectful quasi-respectfully]
  Counter: 2
  
  ...
  
  

  Using a swedish wordlist I found some words of 6 consecutive characters.

  ** [Testing klmnop k@.@*l@.@*m@.@*n@.@*o@.@*p]
  ** [alkoholmonopol kaliumtetracyanokuprat kaliumtetracyanoplatinat komplemento  peration kulminationspunkt vinkelmätningsmikroskop]
  

  This program requires join.p.
• String matching, strmatches
  read_test_strmatches.p: Read a word list and test each words against a string pattern of consecutive characters. Same as read_test.p (see above), but uses the strmatches function (not in the standard Poplog distribution). This version is much slower than using regular expression. Also, see comments below about strmatches.
• Solver: Banana problem
  solver_banana_problem.p: (GPS) Banana problem using SOLVER library (schema and problem from Norvig "Paradigms of Artificial Intelligence Programming").
• Solver: Block worlds
  solver_blocks_world.p: (GPS) Blocks world problem using SOLVER library (schema and problem from TEACH SOLVER).
• Solver: Maze problem
  solver_maze_problem.p: (GPS) Maze problem using SOLVER library (schema and problem from Norvig "Paradigms of Artificial Intelligence Programming").
• Solver: School problem
  solver_school_problem.p: (GPS) School problem using SOLVER library (schema and problem from Norvig "Paradigms of Artificial Intelligence Programming").
• Timing
  timing_test.p: Two timing functions which only run the procedure once (as opposed to the builtin timing which runs many times). One definition is a syntax word, the other is a procedure proper. Includes a simple test.
• Parsing (swedish text)
  tparse_test_swe.p: Parses (simple) swedish sentences given a simple grammar and lexicon. Uses the TPARSE library.
  
  Continuing from the grammar example above:

  listparses("s", [ett svagt
                   [fastän trött]
                   handsfack
                   [grävde ned]
                   [utan vett och sans]
                   en buske])==>
  
  ** [[s [np [snp_t [det_t ett]
                    [adj_t svagt]
                    [adj_aux_t [fastän trött]]
                    [noun_t handsfack]]]
         [vp [verb [grävde ned]]
             [verb_aux [utan vett och sans]]
             [np [snp_n [det_n en] [noun_n buske]]]]]]
  

Installation

This is how I install Pop-11/Poplog when a new version arrives. I run on a linux and the current_poplog directory is a symbolic link to the actual latest distribution directory. Here I assume that the version is v15.63.

• move the previous installation, e.g.

    rm current_poplog # this is a link
     mv v15.63 v15.63.old
  

• Download the latest version of ./get-and-install-v15.63-poplog-here (or whatever version) from http://www.cs.bham.ac.uk/research/projects/poplog/v15.63/#installing.
• chmod +x get-and-install-v15.63-poplog-here
• ./get-and-install-v15.63-poplog-here
• After the installation:
  ln -s v15.63 current_poplog
• Fetch the latest contrib.tar.gz
  Unpack and copy in
  current_poplog/pop/v15.63/pop/packages/contrib/

Posted by hakank at 09:26 FM Posted to Program | Comments (1)

augusti 05, 2009

En uppdatering om vad som händer

Som tidigare nämts så är det på andra bloggen My Constraint Programming Blog det händer saker numera.

Vad har hänt där då (sedan maj)? Faktiskt en hel del. Jag länkar inte till alla inlägg utan endast till några "high lights":

Maj

* Report from SweConsNet2009, including my presentation, som alltså är en rapport från villkorsprogrammeringsworkshopen SweConsNet09, där jag var med och föreläste en stund. Stora delar av maj gick åt till att förebereda för denna föreläsning.

Juni

* Lyckades efter ett antal genomläsningar av några olika skrifter förstå hur det globala villkoret (global constraint) cumulatives funkar i Gecode, och skrev om detta i Scheduling with the cumulatives constraint in Gecode .

* Publicerade och bloggade om villkorsprogrammeringssystemet ECLiPSe (nej, det ska inte förväxlas med utveckligs-GUI:t). Det är ett riktigt trevligt Prolog-baserat system med mycket användbara utökningar såsom loopar och arrays som gör att man inte måste lösa allting med rekursioner och listor. Se vidare My ECLiPSe page som nu innehåller cirka 120 modeller; till största delen har just desamma utökningar används.

Juli

* Skapade ett samlingssida över de problem som modellerats i fler än ett villkorsprogrammeringssystem: Common constraint programming problems som presenterades i Common constraint programming problems.

* Modellerade mina cirka 17 basmodeller ("learning models") i ett ytterligare villkorsprogrammeringssystem: Tailor, som konverterar Essence' (ett högnivåspråk liksom t.ex. MiniZinc och Comet) till Minion, Gecode eller FlatZinc (det som MiniZinc använder). Och det var just stödet av FlatZinc inspirerade till detta.

Tailor presenterades i New Tailor version (v0.3.2) and My Essence'/Tailor page.
Se mera på My Tailor/Essence' page.

Augusti, idag faktiskt

Följande når världen för första gången här, nämligen en liten MiniZinc-modell som löser Strimko-problem. Strimko är en mer avancerad variant av latinska kvadrater (alla rader respektive alla kolumner måste innehålla distinkta värden) där man även ska se till så att ytterligare villkor i form av en "strängar" av celler också måste vara olika. (Strimko är således inte helt väsensskilt från Sudoku.)

MiniZinc-modellen är strimko.mzn med de tre probleminstanserna:
strimko_067.dzn, strimko_068.dzn samt strimko_070.dzn.

Inspiration till detta var från bloggen 360: A New Twist on Latin Squares.

Till sist, för denna gång
För en sammanställning över de olika villkorsprogrammeringssystem jag kikat (och fortfarande kikar) på, se översiktsidan med det passande - men i någon mån förutsägbara - namnet My Constraint Programming Page.

Posted by hakank at 07:50 EM Posted to Constraint Programming