for this end of week i present an n-ary version of the classic expt of Scheme.
I needed it because i use n-ary procedures in infix and it worked with +,-,*,/ which are n-ary but not with expt.
I did not know why Scheme does not provide n-ary exponentiation, perheaps because of the mathematical properties of exponentiation required to made the computation, here are the properties from wikipedia :
This is translate in Scheme by: (expt b (expt p q)) because of the right-associativity (conventional).
Example in Python: b ** p ** q , there should exist such a function in scheme : (** b p q) but not.
Here is a possible implementation:
(define (**-not-tail-rec b . pQ)
(cond ((null? pQ) 1) ; by convention 2^() = 2⁰ = 1 it is like this in Mathematics
((null? (cdr pQ)) (expt b (car pQ))) ; example : 2³
(else
(expt b (apply **-not-tail-rec pQ))))) ; example 2 ³ ⁴ = 2^(3^4) still like this in Mathematics
The above version is working but i prefer a tail recursive version (even if there happen ,with exponentiation ,more quickly an arithmetic overflow before a possible stack overflow) :
;; a tail recursive version with an accumulator
(define (** b . pQ)
(define (**-tail-rec p Q)
(if (null? p)
Q ; when finish we return the accumulator
(**-tail-rec (cdr p)
(expt (car p) Q)))) ; p ^ Q
(if (null? pQ)
1 ; by convention 2^() = 2⁰ = 1 it is like this in Mathematics
(let ((Qp (reverse pQ))) ; because exponentiation is right-associative we will compute from right to left, so we need to reverse the list
(expt b (**-tail-rec (cdr Qp) (car Qp)))))) ; start with Q,a number in the accumulator and p being a list
yes i had mentioned in my original post the part of wikipedia about that.
But i should be very carefull coding the parser , you can understand what i mean when reading this post about Intel Fortran, a professional compiler:
this could lead to wrong result when used without parenthesis.
i have to fix (if possible ,because i'm in a melting of infix and prefix! ) such a thing in my own parser before releasing it.
(I think it is possible to fix that without too much complexity)
A lot of language prefer to use exponentiation as a function ( pow in C for example) instead of an operator because it can be confusing due to the special operator precdence rules caused by right-associativity of exponentiation (or non associativity , in mathematic ,instead of computer science there is no such notion of right/left associativity , they simply say it is not associative, and you're right as a mathematician to specify it)
thank you for your remark.
Need to fix now the same problem as about the Intel Fortran compiler now! .....
Just a few cool feature i'm adding and testing in Scheme+/curly-infix (but not yet commited) :
#lang reader SRFI-105
(require Scheme+)
(define (foo x y) {-4 · sin(x) + x · y ² - 5 · x / y})
(foo 1.23 3.4)
8.640021262861444
this is equivalent to python code as :
from math import *
def foo(x,y):
return -4 * sin(x) + x * y ** 2 - 5 * x / y
foo(1.23,3.4)
8.640021262861444
some other test examples:
{2 ³}
8
{(2 ³) ⁴}
4096
{3 · (2 ³ - 1)}
21
use the mathematic · character for multiplication : AltGr + Maj (CAPS) + 1 --> · on french keyboard ,Option + h on MacOS (did not know on US keyboard?)
and more example that all have been tested to give the same result as Python.
note that superscript character are not hard to get on my keyboard (french) in Emacs or Vim, one can use this:
;; note: under Linux and on a PC (french) keyboard superscript characters
;; can be generated with the keystroke sequence: ^ n where n is a number or sign
;; under MacOS the keystroke sequence is : Command Shift + n (you really need to type + key for superscript)
;; Using the text editor vim, one can produce subscripted and superscripted numbers by using the digraphs control-k-ns for subscription and control-k-nS for superscription, where n is an Arabic numeral.
Of course the usual mathematical notation for 2 ** (3 ** 4) is to have the
4 be a superscript on the 3, rather as you showed a superscript
on the 2 ** 3. So the 4 needs to be higher and smaller than the 3.
The superscript notation you show us in coventional math notation
corresponds to (2 ** 3) ** 4.
yes but there is no way in terminal,text editor (Emacs,Vim) to create or display such notation, you can not superscript more than one single time.
And only a few set of character can be superscript for math: the integer numbers positive and negative , also the sign + and - and the parenthesis ( ) .
Example (from the source code Scheme+/superscript):
(define script-string "⁻⁺⁰¹²³⁴⁵⁶⁷⁸⁹") ; super script
(BTW: i could add support for symbols and a few arithmetic with ( ) also)
To be used this should accessible by the keyboard in many geographic versions, example is 'lambda' symbol λ which is not often used because not easy to get on keyboard. (unless on Mac OS where does exist a shortcut Control + Command + Space)
I added the notation below lately to allow multiple level of exponentiation , but perheaps i should remove this feature, the original idea was to allow "natural" math notation in Scheme+ but this now goes the opposite as it is ambiguous and can lead to errors of understanding the code.
I had the 2 versions with one commented in code of parser:
(def (sexpr-superscript lst) ; deal with **
(when (null? lst)
(return lst))
(define elem (car lst))
(cond ((operator-symbol-or-syntax? elem) (cons elem ; we keep it in the resulting list
(superscript-operator-loop (cdr lst)))) ; and loop in the superscript-operator-loop state
((superscript? elem) (cons '** ;'expt ;(syntax **) ;'** ; ** with superscript
(cons (syntax-superscript-number->number elem) ; number
;;(superscript-operator-loop (cdr lst))))) ; forbid repeated superscript
(sexpr-superscript (cdr lst))))) ; loop (follow automata)
(else ; got an other sexpr, we keep it in the resulting list
(cons elem
(sexpr-superscript (cdr lst)))))) ; loop in the same state
so it is really easy to change it, i do not know what i will do in the release of code, i think i can leave it as an hidden feature but perheaps i will remove it definitively.
The finite state machine for this part of parser is quite simple, it just replace any superscript encountered by ** followed by the superscript number translated in normal number:
Welcome to DrRacket, version 8.15 [cs].
Language: reader SRFI-105, with debugging; memory limit: 14000 MB.
SRFI-105 Curly Infix parser for Racket Scheme and R6RS by Damien MATTEI
(based on code from David A. Wheeler and Alan Manuel K. Gloria.)
Possibly skipping some header's lines containing space,tabs,new line,etc or comments.
SRFI-105.rkt : number of skipped lines (comments, spaces, directives,...) at header's beginning : 12
Parsed curly infix code result =
(module repl racket (provide (all-defined-out)) (require Scheme+))
> {2 ³}
($nfx$ 2 ³)
!*prec-generic-infix-parser : terms=(.#<syntax 2> .#<syntax ³>)
!*prec-generic-infix-parser : parsed-superscript=(.#<syntax 2> ** 3)
!*prec-generic-infix-parser : parsed+-=(.#<syntax 2> ** 3)
!*prec-generic-infix-parser : deep-terms=(.#<syntax 2> ** 3)
!*prec-generic-infix-parser 1 : deep-terms=(.#<syntax 2> ** 3)
!*prec-generic-infix-parser : recalling recall-infix-parser via map
recall-infix-parser : expr =.#<syntax 2>
recall-infix-parser : detected syntax,passing from syntax to list (will be used if it is a list)
recall-infix-parser (after syntax test) : expr= .#<syntax 2>
recall-infix-parser : (list? expr)= #f
recall-infix-parser : expr not list.
recall-infix-parser : expr =**
recall-infix-parser (after syntax test) : expr= **
recall-infix-parser : (list? expr)= #f
recall-infix-parser : expr not list.
recall-infix-parser : expr =3
recall-infix-parser (after syntax test) : expr= 3
recall-infix-parser : (list? expr)= #f
recall-infix-parser : expr not list.
!*prec-generic-infix-parser 2 : deep-terms=(.#<syntax 2> ** 3)
!*prec-generic-infix-parser : rv : deep-terms:(.#<syntax 2> ** 3)
$nfx$ op1 e1 : parsed-args=.#<syntax (** 2 3)>
8
#<eof>
and the whole code of module is :
(module superscript-parser racket/base
(provide superscript-operator-loop)
(require Scheme+/superscript
Scheme+/def
Scheme+/operators)
;; parsing superscript ⁻⁺⁰¹²³⁴⁵⁶⁷⁸⁹ natural numbers
;; see parser-superscript.odg or jpeg image file
;; note: under Linux and on a PC (french) keyboard superscript characters
;; can be generated with the keystroke sequence: ^ n where n is a number or sign
;; under MacOS the keystroke sequence is : Command Shift + n (you really need to type + key for superscript)
;; Using the text editor vim, one can produce subscripted and superscripted numbers by using the digraphs control-k-ns for subscription and control-k-nS for superscription, where n is an Arabic numeral.
;; {3 · 5 + 2}
;; 17
;; {3 · 5 + 2 ³}
;; !*-generic-infix-parser : terms = ((.#<syntax +> (.#<syntax ·> .#<syntax 3> .#<syntax 5>) (** .#<syntax 2> 3)))
;; $nfx$ : parsed-args=.#<syntax (+ (· 3 5) (** 2 3))>
;; 23
;; {3 ² + 2 · 3 · 5 + 5 ²}
;; 64
;; {3 ⁻²}
;; 1/9
;; {2 ¹⁰}
;; 1024
(define (error-superscript lst)
(error "Error parsing superscript : the superscript are in a wrong position in the list: " lst))
(def (superscript-operator-loop lst)
;;(display "superscript-operator-loop : lst=") (display lst) (newline)
(when (null? lst)
(return lst))
(define elem (car lst))
(cond ((operator-symbol-or-syntax? elem) (cons elem ; we keep it in the resulting list
(superscript-operator-loop (cdr lst)))) ; and loop in the same machine state
((superscript? elem) (error-superscript lst))
(else
(cons elem ; we keep it in the resulting list
(sexpr-superscript (cdr lst))))))
(def (sexpr-superscript lst) ; deal with **
(when (null? lst)
(return lst))
(define elem (car lst))
(cond ((operator-symbol-or-syntax? elem) (cons elem ; we keep it in the resulting list
(superscript-operator-loop (cdr lst)))) ; and loop in the superscript-operator-loop state
((superscript? elem) (cons '** ;'expt ;(syntax **) ;'** ; ** with superscript
(cons (syntax-superscript-number->number elem) ; number
;;(superscript-operator-loop (cdr lst))))) ; forbid repeated superscript
(sexpr-superscript (cdr lst))))) ; loop (follow automata)
(else ; got an other sexpr, we keep it in the resulting list
(cons elem
(sexpr-superscript (cdr lst)))))) ; loop in the same state
) ; end module
;; {2 ⁴ ²}
;; 65536
;; {- 2 ³}
;; -8
;; {3 * - 2 ⁴ ² + 1}
;; -196607
