On Jan 5, 6:58 am, Xah Lee<address@hidden> wrote:
On Dec 31 2010, 11:04 pm, girosenth<address@hidden> wrote:
How to improve the readability of (any) LISP or any highlevel
functional language to the level of FORTH ?
some basics that might be helpful.
〈What's Function, What's Operator?〉
http://xahlee.org/math/function_and_operators.html
--------------------------------------------------
What's Function, What's Operator?
Xah Lee, 2010-12-14, 2011-01-06
Typically, we understand what “function” and “operator” mean, but
programer may have a hard time explaining them, and mathematician may
never thought about it. Here, we clarify a bit on the meaning of the
word “function” and “operator”, their context, their relation.
--------------------------------
Function is a Mathematical Concept
Function you probably understand. A function takes a input, and output
a value for a given input. The inputs are called “parameters”. A
specific set of input is called “arguments”. The number of parameters
of a function is called the function's “arity”. So, for example, the
function “sin” has arity 1. A constant, such as 35, π, can be
considered as functions of no parameter, so they are functions of
arity 0. A function of 2 parameters, such as f(x,y) := x+y has arity
2.
Function is a mathematical concept. Viewed in another way, it's a map
from one space (aka set) to another.
--------------------------------
Operator is About Notation
A operator, is less of a mathematical concept, but more of a concept
of notation. Or, in computer language contexts, a element of syntax. A
“operator” is a symbol (or symbols) that are written to indicate
operations. For example, we write 1+2, the “+” is a operator, and the
“1” and “2” are its “operands”. Mathematically, operator is a function
that acts on its operands. The operands are the arguments of the
function.
--------------------------------
Binary Operators
Typically, operators takes 2 arguments, the left and right of the
symbol. e.g. 2×3, 3/4, 2^3, union {3,4}∪{2,4,1}, etc.
--------------------------------
Unary Operators
But there are also 1-argument operators. For example the minus sign
-3, and the logical not ¬ sign, the factorial 3!, square root √3.
--------------------------------
Multi-symbol Operators
Operators can also involve other forms with more symbols. For example,
the absolute sign |-3|, floor ⌊3.8⌋ uses a bracket, summation ∑ takes
4 arguments, a expression, a variable, and start and end values. The
anti-derivative (aka indefinite integral) ∫ takes 2 arguments, a
expression and a symbol. In traditional notation, the integration
operator involves 2 symbols, ∫ and ⅆ. For example, we write ∫ sin(x)
ⅆx .
--------------------------------
Implicit Operators
Operator can be a bit complicated. For example -3 can be interpreted
in several ways. We can think of the minus sign as unary operator
acting on the argument 3. So, mathematically, it is a function of 1
arity that returns the addictive inverse of the element 3. Or, we can
interprete it as one single entity, a element of Reals denoted -3.
When we write 3-2, the ways to interprete it gets a bit more complex.
One way to think of it as a notation shorthand for 3 + (-2). The -2
part can be thought of as before. Another way is to think of - as a
binary operator on 3 and 2, but this seemingly simple interpretation
is a bit complex. Because, what is math definition of the minus binary
function? I'm not sure how it can be defined in terms of algebra
without ultimately thinking of it as additon of 2 elements, one being
a addictive inverse. The other way is to think of it as a real line,
moving the first argument to the left by a distance of the second
argument. Of course ultimately these are equivalent, but i can't think
of a simple, direct, interpretation that can serve as a math
foundation. Also, this is directly related to how does one interprete
division, such as 3/2.
The multiplication operator also gets complicated. For example, when
we write 3 x, it usually means 3*x. The space acts as implicit
multiplication sign. But when we write 3 +2, the space there has no
significance. When we write 3x, even there is no space nor any
operator, but we mean 3*x. As a computer language syntax based on
traditional notation, the parsing rule is not trivial.
Operator Stickiness
There's also the concept of “operator stickiness” (aka “operator
precendence”) at work that makes expressions with operators more
concise. When we write3△4▲5, how do you know it's (3△4)▲5 or 3△(4▲5)?
The concept of operator stickiness is needed to resolve that.
Otherwise, you'll need to always write 3+(4*5) instead of the simpler
3+4*5. But this again, also introduced more complexity. When you have
a expression of tens of different operators, it becomes a problem of
remembering the stickiness grammar for each operator. (in practice,
when you are not sure about the procedence, you usually just use
explicit priority indicator by parens. This often happens in
programing with logic operators (e.g. and&&, or ||, not !.)
Forgetting Operator Precedence is a common error in programing. In
written math for human communication, it is prone to
miscommunication.)
--------------------------------
Operator is tied to Notation
Because the concept of “operator” more has to do with syntax and
notation, and when considering traditional math notation of writing in
“2-dimensions”, also the fact that traditional math notation has a lot
ambiguities, it gets a bit complicated and not as imprecise as we
like. (See: The Problems of Traditional Math Notation)
Mathematically, operator and function are the same thing.
Math function in traditional notation has the form e.g. sin(x),
f(x,y), where the things inside the paren are its parameter/arguments,
and function name is placed to the left.
Operators are useful because writing everything out in full function
notation gets very cumbersome and hard to read. For example, we write
3+4*5 instead of plus(3,times(4,5)) or +(3,*(4,5)).
Here's a example of traditional notation using operators:
-b+√(b^2-4 a c)/(2 a)
If you don't allow space as implicit multiplication sign, then you
have to write:
-b+√((b^2)-4*a*c)/(2*a)
If you don't allow the the concept of operator precedence, then you
have to write:
(-b)+(√((b^2)-((4*a)*c))/(2*a))
If you prefer the structural clarity of the traditional function
notation f(x), you have to write:
/(+(-(b),√(+(^(b,2),-(*(4,a,c))))),*(2,a))
If you prefer words than symbols, as traditionally practiced when
writing out functions, you have to write:
divide(add(minus(b),sqrt(add(power(b,
2),minus(times(4,a,c))))),times(2,a))
The notation using operators is much concise, readable, but at the
cost of relatively complex lexical grammar. The full functional
notation is precise, grammatically simple, but difficult to read.
In math context, it's best to think of functions instead of operator,
and sometimes also use a uniform function notation, where all
arguments are explicitly indicated in one uniform way.
Here's what Wikipedia has to say about operators: Operation
(mathematics). Quote:
An operation ω is a function of the form ω : X1 × … × Xk → Y. The
sets Xj are called the domains of the operation, the set Y is called
the codomain of the operation, and the fixed non-negative integer k
(the number of arguments) is called the type or arity of the
operation.
Note that it doesn't really speaks of “operators”, but speaks of
“operations”, and flatly defines operation as a function.
--------------------------------
Traditional Function Notation sin(x) Isn't Perfect
Note that, even the functional notation such as sin(x), isn't perfect.
Problem of Functions Returning Functions
Normally, with full function notation, you'd expect that execution
order of operations clearly corresponds to the nesting structure. For
example, in our example before:
divide(add(minus(b),sqrt(add(power(b,
2),minus(times(4,a,c))))),times(2,a))
The inner-most parts are evaluated first.
But there's a problem when a function returns a function. For example,
the derivative takes a function and returns a function. We might
write:
derivative(f)
Now, if we want to evaluate the result at 3, then we might write:
derivative(f)(3)
You can see that the notation no longer nests. The operator precedence
issue is back. Now, you need to have a slightly more complex notion of
precedence to work out the notation.
One solution to this is the lisp language's syntax. In lisp syntax,
everything is written inside a paren. The first element is the
function name, the rest is its arguments. So, sin(x) would be written
as (sin,x). (comma is used for separator) Our derivative example would
then be:
((derivative,f),3)
In this way, the syntax remains a pure nested form, and provides the
utmost precision.
Our formula example in fully nested syntax be:
(/,(+,(-,b),(√,(+,(^,b,2),(-,(*,4,a,c))))),(*,2,a))
We could change the comma separator to space. So, it would look like
this:
(/ (+ (- b) (√ (+ (^ b 2) (- (* 4 a c))))) (* 2 a))
(Note: actual lisp language's syntax is not 100% regular. Many of its
syntax does not have the form (a b c ...). See: Fundamental Problems
of Lisp.)
--------------------------------
Syntax Design for Computer Languages
Mixing Operator Syntax with Full Function Notation Syntax
In most computer language, they allow both the operator and full
function syntax. For example, you can write (sin(x))^2+3. (almost all
languages do this; e.g. C, C++, C#, Java, Pascal, Perl, Python, Ruby,
Bash, PowerShell, Haskell, OCaml. The only exception is lisps.)
(Though, almost all computer languages does not have a regular syntax,
in fact, non of any major computer lang has a syntax specification.
The closest one that has a somewhat regular and simple syntax grammar
is Mathematica. See: The Concepts and Confusions of Prefix, Infix,
Postfix and Fully Nested Notations ◇ Math Notations, Computer
Languages, and the “Form” in Formalism.)
Mixed form is normal, and most flexible. Because, not all functions
have a associated operator symbol. And, writing everything in nested
brackets is not readible and hard to write too. The question is, is it
possible to design a syntax, that is fully regular with a very simple
lexical grammar, and easy to read and write?
Xah ∑ http://xahlee.org/ ☄