Convert prefix s-expression back to infix?

[ashok-khanna]

First of all, many thanks for making this library available and also loadable via QuickLisp. I wanted to ask if it is possible to convert prefix s-expressions back to their original infix form?

If not, I'll add it to my list to implement in the medium term

[ashok-khanna]

Just to add this issue, I haven't achieved the solution, but I figured out the main way one could achieve this. Basically, you would want to edit out (i.e. remove) some of the post processing, which makes it relatively trivial to go backwards and recreate the original string. I haven't closed this comment yet, eventually if I have time, I will write the prefix->string function.

cmu-infix/src/cmu-infix.lisp

Line 704 in da62fa3

(defun post-process-expression (expression)

[ashok-khanna]

Adding to the above. If somebody makes the above post-processing change, I believe they can get a prefix -> infix function as follows:

(defun prefix->string (p)
  "Converts a prefix form expression to a string."
  (if (listp p)
      (if (equal (length p) 3)
	  (format nil "(~a ~a ~a)" (p->s (cadr p)) (p->s (car p)) (p->s (caddr p)))
	  (format nil "(~a (~a))" (p->s (car p)) (p->s (cadr p))))
      (format nil "~a" p)))

To do it for the normal case (i.e. without the post processing modification above, so that x + y + z becomes (+ x y z)), you can modify the above, but add a rule for when length of the prefix forms exceed 3.

If there are any issues with the above in testing, I will report back and modify. Sorry if the code is not in the cleanest form, I didn't want to spend too much time on it.

p.s. I really do recommend making the above post-processing change - it makes all the prefix forms a nested list where each node has a maximum of three children, this makes it much easier to work on prefix forms as you don't need to build for cases where a node can have a varying length due to x + y + z + a becoming (+ x y z a) etc.

[ashok-khanna]

(By the way, I'm not suggesting the change be made on the main repo - this is just some notes for others who may want to modify their own copy).

[ashok-khanna]

Just to add onto this, assuming the above post-processing change is made, below is a better version of prefix->string. It's not perfect and a bit of a hack, but hopefully useful for some use cases.

I need to do an overall clean up of the post-processing change & the below, basically there are some very valid use cases for post-processing that get ignored with the above & below hacks. However, I will do all those as a separate and more robust pull request to this package. For now sharing the (untested) below, to give inspiration to anyone else who wants to do something similar.

(defun prefix->string (p &key (starting-call t))
  "Converts a prefix form expression to a string."
  ;; This function transforms a prefix form expression
  ;; to a string. The main complexity is that infix
  ;; expressions have implied grouping (e.g. it is
  ;; clear that x + y * z is (+ x (* y z)) due to
  ;; multiplication having a higher priority.
  ;;
  ;; The string->prefix function accounts for this
  ;; implied grouping through the function
  ;; gather-superiors, which calls on operator-lessp.
  ;; The latter function uses *operator-ordering*
  ;; to correctly handle implicit groupings
  ;;
  ;; Here we do the reverse, but re-use these functions.
  ;; Each child (nested child) form of a prefix-form
  ;; returns a list of three values, its operator,
  ;; its string without grouping (i.e. without
  ;; parentheses) and its string with grouping (i.e.
  ;; with grouping)
  ;;
  ;; Once we receive this data from each child at a
  ;; a level below, we check whether the operator of
  ;; the parent has a lower priority than that of the
  ;; child. If so, we do not need to add parentheses
  ;; to group the child element and accordingly use
  ;; its version, without the parentheses (third item
  ;; in the list). Otherwise, we need to add grouping
  ;; to the child element with parentheses since it
  ;; has a lower priority than the parent element.
  ;;
  ;; We also assume generally that operators are
  ;; associative, so we remove parentheses when
  ;; parent and child elements use the same
  ;; operators
  ;;
  ;; The above is the general algorithm when
  ;; we are working with expressions of three items,
  ;; e.g. a + b. When we are working with expressions
  ;; of two items, e.g. sin (x) or (sin x), we are
  ;; effectively working with 'special' functions,
  ;; so we assume these are not associative (e.g.
  ;; (sin (sin y)) is not (sin x y). Accordingly,
  ;; we force grouping by constructing our string
  ;; list to always have parentheses for both
  ;; second and third items (refer start of this
  ;; discussion). Thus, we do not need to do any
  ;; special checks of comparing child & parent
  ;; operators here when the parent is a function
  ;; (i.e. a list of length 2), as we automatically
  ;; group the children.
  ;;
  ;; Finally, we do not want parentheses around
  ;; the final expression, so we add a flag
  ;; to accound for this (:starting-call)
  ;; We also don't want parantheses around

  ;; First check if p is a list of three elements,
  ;; a list of two elements or just an atom
  (cond ((and (listp p) (equal (length p) 3)) 
	 ;; First start off by binding some
	 ;; of the commonly used variables
	 (let* ((second-item-string-data (prefix->string (second p) :starting-call nil))
		(third-item-string-data (prefix->string (third p) :starting-call nil))
		(operator (car p))
		;; Now is the core of our function.
		;; Here is where we check whether
		;; the parent operator has lower priority
		;; than the child operator, or whether
		;; they are the same operator. If so, group
		;; If not, do not group. Grouping is done
		;; by using either the second item of the child's string-data
		;; (i.e. without parentheses) or the third item (with
		;; parentheses)
		;;
		;; One could probably reduce string-data to just a cons
		;; of the operator and the string without parentheses
		;; and that add the parentheses below as required.
		;; However, premature optimisation is the root of
		;; all evil, so I didn't do it just yet.
		;;
		;; Note in the below, we have to do this twice,
		;; one for the second element of a list, and one
		;; for the third
		(expression-string
		 (format nil "~a ~a ~a"
			 (if (or (operator-lessp operator (car second-item-string-data))
				 (eql (car second-item-string-data) operator))
			     (second second-item-string-data)
			     (third second-item-string-data))
			 operator
			 (if (or (operator-lessp operator (car third-item-string-data))
				 (eql (car second-item-string-data) operator))
			     (second third-item-string-data)
			     (third third-item-string-data)))))
	   ;; If it is a starting call, simply return
	   ;; Otherwise construct the necessary string-data
	   ;; to be handled above the chain
	   (if starting-call
	       expression-string
	       (list (car p) expression-string (format nil "(~a)" expression-string)))))
	;; Now look at the case where p is just a list of two items
	((and (listp p) (equal (length p) 2))
	 ;; This implies that p is a function call, e.g. (sin x)
	 ;; and not something where association or implicit
	 ;; operator priorities will apply - thus always group
	 (if starting-call
	     ;; Note how we automatically use the non-grouped
	     ;; version of the child (second item of string-data)
	     ;; This is to avoid duplicaiton of parentheses with
	     ;; "~a(~a)"
	     (format nil "~a(~a)" (car p) (second (prefix->string (cadr p) :starting-call nil)))
	     ;; Again we need to construct the string-data list here
	     (list nil
		   (format nil "~a(~a)" (car p) (second (prefix->string (cadr p) :starting-call nil)))
		   (format nil "~a(~a)" (car p) (second (prefix->string (cadr p) :starting-call nil))))))
	;; Now look at the case where p is just an atom
	(t 
	 ;; If p is not a list, simply check
	 ;; whether the function is a starting
	 ;; call and then either return it
	 ;; or construct the necessary list
	 ;; for handling above the chain (since
	 ;; there is only one element, we don't
	 ;; have to worry about grouping / parentheses, so the
	 ;; ELSE in the below is just to fit into
	 ;; the overall model of this function
	 (if starting-call
	     (format nil "~a" p)
	     (list nil (format nil "~a" p) (format nil "~a" p))))))

[ashok-khanna]

Just re-opening as I now think this is a valid improvement that can be made to the package:

• An option to turn on / off post-processing (for the correct subset of operators where turning post-processing off makes sense)
• A robust prefix->string function
• Change from (list operator string-without-parentheses string-with-parentheses) to simply (cons operator string-without-parentheses) and push the addition of parentheses to the level above -> this should be more efficient and more elegant. I think we definitely need to pass operator up the chain as this information gets lost in the string construction process (the whole purpose of CMU infix is to disentangle the implied operator priorities within a string, so we need to keep this data as we reverse the process from prefix form and back to original string)
• Proper testing of all use cases

Hopefully I can do something by year-end or early next year, whenever I get time to revisit this package.