Loading ...
Sorry, an error occurred while loading the content.

GP, meta programming and reflection

Expand Messages
  • Tom Lenaerts
    Metaprogramming can be defined as the art of programming programs which can read, manipulate or write other programs. A typical example are interpreters.
    Message 1 of 6 , Mar 2, 2003
    • 0 Attachment
      Metaprogramming can be defined as the art of programming programs which
      can read, manipulate or write other programs. A typical example are
      interpreters. These are programs which are able to manipulate and
      reason about lower level programs. In most cases, the interpreter is
      referred to as the meta-level and the program is at the object level.

      Since GP is all about the evolution of programming, it seems logical
      that one would like to evolve combinations of meta programs and object
      programs to solve problems. I was wondering whether this issue has been
      recognised before in GP. I assume it has yet i'm not aware of any major
      contribution in this context. Can somebody provide me with a pointer?
      If this has not been recognised before, can anyone explain why it might
      not seem relevant for a GP system?

      Tom


      --

      Tom Lenaerts (tlenaert@...)
      Artificial Intelligence Lab (ARTI)
      Computational Modeling Lab (CoMo)
      Department of Computer Science (DINF)
      Faculty of Science
      Vrije Universiteit Brussel
      Pleinlaan 2, 1050 Brussels
      http://como.vub.ac.be/Members/tom.htm
    • Lee Spector
      Tom, The Push project and the PushGP genetic programming system provide some points of contact to these ideas. The Push programming language allows for
      Message 2 of 6 , Mar 2, 2003
      • 0 Attachment
        Tom,

        The Push project and the PushGP genetic programming system provide some
        points of contact to these ideas. The Push programming language allows for
        explicit code manipulation and many of the interesting features of
        evolutionary computing systems based on Push (like PushGP) derive from this
        capability. For example, it is simple for a Push program to duplicate
        chunks of its own code (with possible modificiations) to implement modules,
        eliminating the need for any add-on ADF/ADM mechanisms. Other "fancy" GP
        features (like support for recursion and evolution of genetic operators)
        are also supported naturally by the code-self-manipulation features.

        On the other hand, it's not always clear in an evolved Push program what's
        the "meta" program and what's the "object" program -- one often finds a
        bunch of self-manipulating/self-executing code that uses non-traditional
        techniques. So I don't know if this is really what you're after.

        More information on the Push project (including code and papers) can be
        found at http://hampshire.edu/lspector/push.html

        That page is not 100% current -- for example I know that there are at least
        three other versions of Push in existence (one in Java by Russ Abbott at
        http://abbott.calstatela.edu/GeneticProgramming/, one by Keith Downing, and
        one in C by Chris Perry and Jon Klein and incorporated into the Breve
        simulation environment). This stuff isn't yet on the page... I ought to
        update it soon...

        I'd be happy to discuss any of this further with you.

        -Lee



        Metaprogramming can be defined as the art of programming programs which
        can read, manipulate or write other programs. A typical example are
        interpreters. These are programs which are able to manipulate and
        reason about lower level programs. In most cases, the interpreter is
        referred to as the meta-level and the program is at the object level.

        Since GP is all about the evolution of programming, it seems logical
        that one would like to evolve combinations of meta programs and object
        programs to solve problems. I was wondering whether this issue has been
        recognised before in GP. I assume it has yet i'm not aware of any major
        contribution in this context. Can somebody provide me with a pointer?
        If this has not been recognised before, can anyone explain why it might
        not seem relevant for a GP system?

        Tom


        --

        Tom Lenaerts (tlenaert@...)
        Artificial Intelligence Lab (ARTI)
        Computational Modeling Lab (CoMo)
        Department of Computer Science (DINF)
        Faculty of Science
        Vrije Universiteit Brussel
        Pleinlaan 2, 1050 Brussels
        <http://como.vub.ac.be/Members/tom.htm>http://como.vub.ac.be/Members/tom.htm

        Yahoo! Groups Sponsor
        ADVERTISEMENT
        <http://rd.yahoo.com/M=246920.2960106.4328965.2848452/D=egroupweb/S=1705948923:HM/A=1464858/R=0/*http://www.gotomypc.com/u/tr/yh/cpm/grp/300_Cquo_1/g22lp?Target=mm/g22lp.tmpl>



        To unsubscribe from this group, send an email to:
        genetic_programming-unsubscribe@yahoogroups.com



        Your use of Yahoo! Groups is subject to the
        <http://docs.yahoo.com/info/terms/>Yahoo! Terms of Service.

        --
        Lee Spector
        Dean, School of Cognitive Science
        Associate Professor of Computer Science lspector@...
        Cognitive Science, Hampshire College http://hampshire.edu/lspector/
        Amherst, MA 01002 413-559-5352, Fax: 413-559-5438
      • Mariusz Nowostawski
        ... This is quite an accurate statement about meta-programming, however the comment about interpreters is not really true. For some languages and some
        Message 3 of 6 , Mar 2, 2003
        • 0 Attachment
          Tom Lenaerts wrote:
          > Metaprogramming can be defined as the art of programming programs which
          > can read, manipulate or write other programs. A typical example are
          > interpreters. These are programs which are able to manipulate and
          > reason about lower level programs. In most cases, the interpreter is
          > referred to as the meta-level and the program is at the object level.

          This is quite an accurate statement about meta-programming, however
          the comment about interpreters is not really true. For some languages
          and some interpreters it may be the case that we deal with
          meta-programming, but this is not always the case. Not all
          interpreters can "manipulate" programs and not all programs can
          "manipulate" their interpreters.

          One can look at interpreter/program as an example of
          meta-level/base-level relationship, but this is stretching the
          definition. I am not sure which was your main objective, so I will
          briefly address both of the topics.

          > Since GP is all about the evolution of programming, it seems logical
          > that one would like to evolve combinations of meta programs and object
          > programs to solve problems. I was wondering whether this issue has been
          > recognised before in GP. I assume it has yet i'm not aware of any major
          > contribution in this context. Can somebody provide me with a pointer?
          > If this has not been recognised before, can anyone explain why it might
          > not seem relevant for a GP system?


          "Meta-programming" in GP
          ==================================

          We deal with meta-programming when we have the notion of base level,
          which is "manipulated" or "reasoned about" by meta-level. "Manipulated"
          is not precisely defined. It is accepted to understand it as full
          structural and functional reflective capabilities, i.e. retrospection,
          reification and introspection. Programming languages are referred as
          capable of meta-programming if they are capable of structural and
          functional reflection See for example:
          http://www4.informatik.uni-erlangen.de/Projects/PM/Java/publications.html
          for some articles about building meta-programming environment in Java
          for Java (MetaJava).

          Indeed, it is very interesting idea and could be applied to GP or other
          evolutionary system. I think, that the main reason for this idea to be
          somehow neglected and that is not really present in the literature is
          its complexity. The capabilities offered by meta-programming
          environments are so complex, that even human programmers need special
          training and paradigm shift to be able to use them effectively. I
          strongly believe though, that eventually all our evolutionary code
          generators will be fully reflective. And that future generations of
          evolutionary computation researchers will wonder how we could go for so
          long without it. At the moment however, we do not know exactly how we
          could deal with the complexity offered by meta-programming paradigm.

          I would be interested myself hearing about others working in
          meta-programming evolutionary systems.




          "Interpreter/program" relationship in GP
          =============================================

          Interpreter/program relationship, again, has very interesting
          implications in GP and code generation. Again, it is not widely used
          notion in GP-like research. I can speculate that the reason is probably
          "field boundaries": evolutionary computation community and theoretical
          computation community are probably forming two quite disjoint sets ;o)

          "Interpreter/program" notion naturally forms a particular ordering (or
          organising) relationship, which may be used to describe a particular
          hierarchy of levels of organisation. See [1] for details about
          organising relations in respect to emergence and hierarchies. In context
          of evolving programs in general (as already pointed out by Lee) Push
          system can be one of the examples.

          I have discussed the idea itself and its implications in details in [2],
          where I have used PushGP system as one of the (ideal) examples. I am
          working on more formal formulation of this notion, and would be glad to
          hear others using it as well.



          [1] S. Jones. Organizing relations and emergence. In R. K. Standish, M.
          A. Bedau, and H. A. Abbass, editors, Artificial Life VIII: Proceedings
          of the Eight International Conference on Artificial Life, pages 418-422.
          MIT Press, 2002.


          [2] M. Nowostawski. Hierarchical code generators. In E. Blotta, D.
          Gross, T. Smith, T. Lenaerts, S. Bullock, H. H. Lund, J. Bird, R.
          Watson, P. Pantano, L. Pagliarini, H. A. Abbass, R. K. Standish, and M.
          A. Bedau, editors, Artificial Life VIII: Workshops, pages 63-72.
          University of New South Wales, Australia, 2002.



          ps. One should keep in mind two different meanings of the term
          "reflection". The more formal meaning of this term is different from its
          common use. Java is not formally reflective language, even though
          marketing departments are selling it as reflective. To be fair and
          precise, Java is retrospective language, with some retrospection
          capabilities.
          Similarly with Push (no offense Lee): the language is not reflective in
          the proper meaning of the term.



          --
          best regards
          Mariusz
        • Lee Spector
          Mariusz Nowostawski wrote: ps. One should keep in mind two different meanings of the term reflection . The more formal meaning of this term is different from
          Message 4 of 6 , Mar 2, 2003
          • 0 Attachment
            Mariusz Nowostawski wrote:
            ps. One should keep in mind two different meanings of the term
            "reflection". The more formal meaning of this term is different from its
            common use. Java is not formally reflective language, even though
            marketing departments are selling it as reflective. To be fair and
            precise, Java is retrospective language, with some retrospection
            capabilities.
            Similarly with Push (no offense Lee): the language is not reflective in
            the proper meaning of the term.

            Mariusz,

            No offense taken, and I may even agree, but could you provide a pointer to
            the definition of reflection that you are using? By definitions I've been
            able to find just now (for example at
            http://www2.parc.com/csl/groups/sda/projects/reflection96/docs/malenfant/ref96/node2.html)
            full reflection is probably not even possible. But that doesn't mean that a
            language with certain reflective features (e.g. in which programs can
            transform parts of their own code in arbitrary ways and then execute them)
            doesn't provide useful metaprogramming facilities.

            Thanks, -Lee
            --
            Lee Spector
            Dean, School of Cognitive Science
            Associate Professor of Computer Science lspector@...
            Cognitive Science, Hampshire College http://hampshire.edu/lspector/
            Amherst, MA 01002 413-559-5352, Fax: 413-559-5438
          • Mariusz Nowostawski
            Lee Spector wrote: [...] ... The best description, together with semi-definitions about object oriented reflection (meta-programming in object-oriented
            Message 5 of 6 , Mar 2, 2003
            • 0 Attachment
              Lee Spector wrote:
              [...]
              > No offense taken, and I may even agree, but could you provide a pointer to
              > the definition of reflection that you are using? By definitions I've been

              The best description, together with semi-definitions about object
              oriented reflection (meta-programming in object-oriented context) I was
              refering to, is given in:

              R. Douence, M. Südholt: "The next 700 reflective object-oriented
              languages", École des mines de Nantes, technical report, no. 99-1-INFO, 1999
              http://www.emn.fr/info/recherche/publications/RR99/99-1-INFO.ps.gz

              > able to find just now (for example at
              > http://www2.parc.com/csl/groups/sda/projects/reflection96/docs/malenfant/ref96/node2.html)
              > full reflection is probably not even possible. But that doesn't mean that a
              > language with certain reflective features (e.g. in which programs can
              > transform parts of their own code in arbitrary ways and then execute them)
              > doesn't provide useful metaprogramming facilities.

              Yes indeed. The quoted definitions (by J. Malenfant, M. Jacques and F.N.
              Demers) are fine with me and I agree with them. I am not suggesting that
              a language has meta-programming capabilities only if it can provide
              *all* the necessary reflective features; some are enough.

              However, no matter what the details of the definition are, the central
              notion in meta-programming is always reification. Even if the language
              has very limited reflective capabilities, as long as it provides
              explicitely a reification process (reification of its structure or/and
              behaviour), then I would call it "meta-programming capable".

              Push program can transform pieces of itself and execute these pieces,
              but it does not have a proper reification mechanism. I do not think
              there is a mechanism to reify bits of Push program structure from the
              meta-level into the object level, which can be then operated on.

              Java program can manipulate bits and pieces of its own bytecode
              representation, but it does not mean Java is a meta-programming
              language. It would be only the case, if you could in Java (and in
              analogy, in Push) reify a meta-level-object, like Java object, class,
              procedure and so on, so you can manipulate it as if it was a first order
              object in your language. For example in meta-programming procedural
              languages you can build a generic procedure which takes itself or
              another procedure as an argument and changes it (or itself) somehow. In
              Push you need to have the actual chunks of code at hand to be able to
              manipulate them, and you cannot build a generic mechanism of changing a
              procedure, because Push does not have a representation of procedure as
              such. It does not have explicit reification.

              Of course it is a great step forward from the traditional languages used
              in evolutionary computation, and it indeed has some very interesting and
              powerful reflective features. It fits somewhere in between
              non-meta-programming language and meta-programming language category, I
              guess...

              Hope that helps,

              best regards
              Mariusz


              > --
              > Lee Spector
              > Dean, School of Cognitive Science
              > Associate Professor of Computer Science lspector@...
              > Cognitive Science, Hampshire College http://hampshire.edu/lspector/
              > Amherst, MA 01002 413-559-5352, Fax: 413-559-5438
            • Juergen Schmidhuber
              The first meta-GP system (1987) was described in: @misc{Sch:87, author = {J. Schmidhuber}, title = {{Evolutionary principles in self-referential learning.
              Message 6 of 6 , Mar 10, 2003
              • 0 Attachment
                The first meta-GP system (1987) was described in:

                @misc{Sch:87,
                author = {J. Schmidhuber},
                title = {{Evolutionary principles in self-referential learning.
                Diploma thesis, Institut f\"{u}r Informatik,
                Technische Universit\"{a}t M\"{u}nchen}},
                year = {1987}}

                Meta-GP recursively applies metalevel GP to the task of finding
                better program-modifying programs on lower levels - the goal is
                to use GP for improving GP:
                http://www.idsia.ch/~juergen/gp.html

                Of course, the more principled and theoretically optimal metalearner
                is the "Optimal Ordered Problem Solver" OOPS described here:
                http://www.idsia.ch/~juergen/oops.html

                Cheers,
                Juergen http://www.idsia.ch/~juergen/





                Tom Lenaerts wrote:
                > Metaprogramming can be defined as the art of programming programs which
                > can read, manipulate or write other programs. A typical example are
                > interpreters. These are programs which are able to manipulate and
                > reason about lower level programs. In most cases, the interpreter is
                > referred to as the meta-level and the program is at the object level.
                >
                > Since GP is all about the evolution of programming, it seems logical
                > that one would like to evolve combinations of meta programs and object
                > programs to solve problems. I was wondering whether this issue has been
                > recognised before in GP. I assume it has yet i'm not aware of any major
                > contribution in this context. Can somebody provide me with a pointer?
                > If this has not been recognised before, can anyone explain why it might
                > not seem relevant for a GP system?
                >
                > Tom
                >
                >
              Your message has been successfully submitted and would be delivered to recipients shortly.