source: branches/f4grobner/parse.lisp@ 1111

;;; -*- Mode: Lisp; Syntax: Common-Lisp; Package: Grobner; Base: 10 -*-



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;                                                                              

;;;  Copyright (C) 1999, 2002, 2009, 2015 Marek Rychlik <rychlik@u.arizona.edu>          

;;;                                                                              

;;;  This program is free software; you can redistribute it and/or modify        

;;;  it under the terms of the GNU General Public License as published by        

;;;  the Free Software Foundation; either version 2 of the License, or           

;;;  (at your option) any later version.                                         

;;;                                                                              

;;;  This program is distributed in the hope that it will be useful,             

;;;  but WITHOUT ANY WARRANTY; without even the implied warranty of              

;;;  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               

;;;  GNU General Public License for more details.                                

;;;                                                                              

;;;  You should have received a copy of the GNU General Public License           

;;;  along with this program; if not, write to the Free Software                 

;;;  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  

;;;                                                                              

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;

;; Parser of infix notation. This package enables input

;; of polynomials in human-readable notation outside of Maxima,

;; which is very useful for debugging.

;;

;; NOTE: This package is adapted from CGBLisp.

;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;



(defpackage "PARSE"

  (:use :cl :order :ring-and-order :monomial :term :polynomial :ring)

  (:export "PARSE PARSE-TO-ALIST" "PARSE-STRING-TO-ALIST" 

           "PARSE-TO-SORTED-ALIST" "PARSE-STRING-TO-SORTED-ALIST" "^" "["

           "POLY-EVAL"

           ))



(in-package "PARSE")



(proclaim '(optimize (speed 0) (space 0) (safety 3) (debug 3)))



;; The function PARSE yields the representations as above.  The two functions

;; PARSE-TO-ALIST and PARSE-STRING-TO-ALIST parse polynomials to the alist

;; representations. For example

;;

;; >(parse)x^2-y^2+(-4/3)*u^2*w^3-5 --->

;; (+ (* 1 (^ X 2)) (* -1 (^ Y 2)) (* -4/3 (^ U 2) (^ W 3)) (* -5))

;;

;; >(parse-to-alist '(x y u w))x^2-y^2+(-4/3)*u^2*w^3-5 --->

;; (((0 0 2 3) . -4/3) ((0 2 0 0) . -1) ((2 0 0 0) . 1) ((0 0 0 0) . -5))

;;

;; >(parse-string-to-alist "x^2-y^2+(-4/3)*u^2*w^3-5" '(x y u w)) --->

;; (((0 0 2 3) . -4/3) ((0 2 0 0) . -1) ((2 0 0 0) . 1) ((0 0 0 0) . -5))

;;

;; >(parse-string-to-alist "[x^2-y^2+(-4/3)*u^2*w^3-5,y]" '(x y u w))

;; ([ (((0 0 2 3) . -4/3) ((0 2 0 0) . -1) ((2 0 0 0) . 1)

;;     ((0 0 0 0) . -5))

;;    (((0 1 0 0) . 1)))

;; The functions PARSE-TO-SORTED-ALIST and PARSE-STRING-TO-SORTED-ALIST

;; in addition sort terms by the predicate defined in the ORDER package

;; For instance:

;; >(parse-to-sorted-alist '(x y u w))x^2-y^2+(-4/3)*u^2*w^3-5

;; (((2 0 0 0) . 1) ((0 2 0 0) . -1) ((0 0 2 3) . -4/3) ((0 0 0 0) . -5))

;; >(parse-to-sorted-alist '(x y u w) t #'grlex>)x^2-y^2+(-4/3)*u^2*w^3-5

;; (((0 0 2 3) . -4/3) ((2 0 0 0) . 1) ((0 2 0 0) . -1) ((0 0 0 0) . -5))



;;(eval-when (compile)

;;  (proclaim '(optimize safety)))



(defun parse (&optional stream)

  "Parser of infix expressions with integer/rational coefficients

The parser will recognize two kinds of polynomial expressions:



- polynomials in fully expanded forms with coefficients

  written in front of symbolic expressions; constants can be optionally

  enclosed in (); for example, the infix form

        X^2-Y^2+(-4/3)*U^2*W^3-5

  parses to

        (+ (- (EXPT X 2) (EXPT Y 2)) (* (- (/ 4 3)) (EXPT U 2) (EXPT W 3)) (- 5))



- lists of polynomials; for example

        [X-Y, X^2+3*Z]          

  parses to

          (:[ (- X Y) (+ (EXPT X 2) (* 3 Z)))

  where the first symbol [ marks a list of polynomials.



-other infix expressions, for example

        [(X-Y)*(X+Y)/Z,(X+1)^2]

parses to:

        (:[ (/ (* (- X Y) (+ X Y)) Z) (EXPT (+ X 1) 2))

Currently this function is implemented using M. Kantrowitz's INFIX package."

  (read-from-string

   (concatenate 'string

     "#I(" 

     (with-output-to-string (s)

       (loop

         (multiple-value-bind (line eof)

             (read-line stream t)

           (format s "~A" line)

           (when eof (return)))))

     ")")))



;; New implementation based on the INFIX package of Mark Kantorowitz

(defun parse-to-alist (vars &optional stream)

  "Parse an expression already in prefix form to an association list form

according to the internal CGBlisp polynomial syntax: a polynomial is an

alist of pairs (MONOM . COEFFICIENT). For example:

  (WITH-INPUT-FROM-STRING (S \"X^2-Y^2+(-4/3)*U^2*W^3-5\")

        (PARSE-TO-ALIST '(X Y U W) S))

evaluates to

(((0 0 2 3) . -4/3) ((0 2 0 0) . -1) ((2 0 0 0) . 1) ((0 0 0 0) . -5))"

  (poly-eval (parse stream) vars))





(defun parse-string-to-alist (str vars)

  "Parse string STR and return a polynomial as a sorted association

list of pairs (MONOM . COEFFICIENT). For example:

(parse-string-to-alist \"[x^2-y^2+(-4/3)*u^2*w^3-5,y]\" '(x y u w))

 ([ (((0 0 2 3) . -4/3) ((0 2 0 0) . -1) ((2 0 0 0) . 1)

     ((0 0 0 0) . -5))

    (((0 1 0 0) . 1)))

The functions PARSE-TO-SORTED-ALIST and PARSE-STRING-TO-SORTED-ALIST

sort terms by the predicate defined in the ORDER package."

  (with-input-from-string (stream str)

    (parse-to-alist vars stream)))





(defun parse-to-sorted-alist (vars &optional (order #'lex>) (stream t))

  "Parses streasm STREAM and returns a polynomial represented as 

a sorted alist. For example:

(WITH-INPUT-FROM-STRING (S \"X^2-Y^2+(-4/3)*U^2*W^3-5\")

  (PARSE-TO-SORTED-ALIST '(X Y U W) S))

returns

(((2 0 0 0) . 1) ((0 2 0 0) . -1) ((0 0 2 3) . -4/3) ((0 0 0 0) . -5))

and

(WITH-INPUT-FROM-STRING (S \"X^2-Y^2+(-4/3)*U^2*W^3-5\")

  (PARSE-TO-SORTED-ALIST '(X Y U W) T #'GRLEX>) S)

returns

(((0 0 2 3) . -4/3) ((2 0 0 0) . 1) ((0 2 0 0) . -1) ((0 0 0 0) . -5))"

  (sort-poly (parse-to-alist vars stream) order))



(defun parse-string-to-sorted-alist (str vars &optional (order #'lex>))

  "Parse a string to a sorted alist form, the internal representation

of polynomials used by our system."

  (with-input-from-string (stream str)

    (parse-to-sorted-alist vars order stream)))



(defun sort-poly-1 (p order)

  "Sort the terms of a single polynomial P using an admissible monomial order ORDER.

Returns the sorted polynomial. Destructively modifies P."

  (sort p order :key #'first))



;; Sort a polynomial or polynomial list

(defun sort-poly (poly-or-poly-list &optional (order #'lex>))

  "Sort POLY-OR-POLY-LIST, which could be either a single polynomial

or a list of polynomials in internal alist representation, using

admissible monomial order ORDER. Each polynomial is sorted using

SORT-POLY-1."

  (cond

   ((eql poly-or-poly-list :syntax-error) nil)

   ((null poly-or-poly-list) nil)

   ((eql (car poly-or-poly-list) '[)

    (cons '[ (mapcar #'(lambda (p) (sort-poly-1 p order)) 

                     (rest poly-or-poly-list))))

   (t (sort-poly-1 poly-or-poly-list order))))