I'm not an expert but isn't Haskell sorta mathy? I guess what you mean by mathematical foundation seems a little vague and open to interpretation... as is programming language. Turing machines and imperative languages are obviously not very strongly mathematical in practice (as if Turing machines are used in practice...) but what about the lambda calculus? how is that not a mathematical basis for computation?

### Xah Lee

Shared publicly -while reading David Flanagan's JavaScript Book yesterday, i realized, that no computer language has math foundation. For example, what's a object? in Java, JavaScript, Python, Perl? what's a function?

one could give a reasonable definition, as did Flanagan rather painstakingly, but that's like 1700s mathematician's concept of real number or limit. Sure, everybody understand it, and 99.99% of the time there's no any problem, but a sound logical definition is lacking.

#perl #python #lisp #javascript

one could give a reasonable definition, as did Flanagan rather painstakingly, but that's like 1700s mathematician's concept of real number or limit. Sure, everybody understand it, and 99.99% of the time there's no any problem, but a sound logical definition is lacking.

#perl #python #lisp #javascript

1

29 comments

+Dan Lentz probably easiest way to express this is to have a conversation. Let's say emacs lisp. What's a function? define it, and i'll shoot back on how it's not well defined, and you can refine it, and the process goes on, but ultimately, i think we ends up with the entire compiler, and still no good definition or the definition isn't practical (is in not remotely connected to what we'd call a function anymore), and at that point of detail, We'll probably end up saying a logical definition isn't necessary, a waste of time. (which i don't think it is a waste of time. and i think it's a problem that causes langs to be all incomprehensible and more complex)

i could be wrong, but am pretty sure not.

i could be wrong, but am pretty sure not.

i think the idea is easily understood if one's familiar with the history of math foundations. That's the gist of what am saying, anyway.

Dan Lentz

+

1

2

1

2

1

But emacs lisp is a poor example, as are perl, javascript, etc. They neither purport nor attempt to be rigorous in that way. Emacs lisp, in particular, is first and foremost intended to be suitable as an integrated scripting language for a text editor and at every step of its design it makes trade offs to be as effective as possible in that capacity.

Common-lisp makes similar trade-offs (without apology) in order to provide a practical computing platform capable of addressing a given problem domain in whatever manner the developer envisions: want OO, it has it. Want functional? It has it. Want to design your own paradigm? It is more flexible in its ability to metamorph into whatever you envision. Take XMLisp for example. That bring said, and because it us gat I'm most familiar with, CL is perfectly capable platform for implementation of something as rigorourous as you like. One example of this that comes to mind is a small project that was on lisppaste about a year ago by pascal bougeron (sp?) otherwise known as informatimago.com where he implemented a lambda calculus based computing model from the ground up. Just lambda nothing else. Numbers, for example, were built out of lambda, not any other primitive representation. Obviously he didn't go to the extent of developing a whole extensive platform based on this, but had did develop it far enough that you could see how it could continue to be extended to become one. Obviously strict lambda-calculus is not the most effective or convenient computing model for general real-world computation but this is an example of how one might do such things using a pure mathematical lambda-calculus model of computation.

I know very little about Haskell so I'll drop it, but I was under the impression that it's foundations were fairly rigorous.

I think the definition of function is fairly well known. Purely functional languages take pains to be faithful to the concept.

What is an object? An object is the composite of a function and an environment. An environment is a set of frames. A frame is a collection of bindings. A binding is the association of a variable and a value that is held to be true for some scope and extent. That is all stuff from SICP. Objects may, but do not have to, deviate from pure functions by allowing these bindings to be mutable locatives for storage of information local to the object(s) known as it's state. This deviates from pure function but turns out to be very useful in practice. Alternatively one may look to monads for a more pure way to deal with this sort of concern but that is another topic.

In practical terms an object is typically a simple a lexical closure:

(defvar object

(let ((x 1)(y 2))

(Lambda (op &optional (value '%unbound%))

(If (functionp op)

(Funcall op x y)

(If (EQ value '%unbound%)

(Symbol-value op)

(Setf (Symbol-value op) value))))))

(Funcall object #'+) => 3

(Funcall object 'x) => 1

(Funcall object 'x 5) => 5

(Funcall object #'+) => 7

(Funcall object 'x) => 5

Oh well that's very primitive and off the cuff but it serves as the basic example. For a really amazing example of this, see Doug hoytes book Let over Lambda, where he develops a very useful object system using what he calls pandoric closures. At heart they are based on nothing more than I used above. I like these things quite a bit actually and use them in many of my projects as a lightweight more flexible alternative to CLOS that is especially good when ... Oh never mind its a whole other conversation. I can give you a link to source if you want. It's in my cl-ctrie project on github there's a file called ctrie-lambda.lisp which includes everything (my customized implementation) and an example at bottom showing a simple use scenario.

Common-lisp makes similar trade-offs (without apology) in order to provide a practical computing platform capable of addressing a given problem domain in whatever manner the developer envisions: want OO, it has it. Want functional? It has it. Want to design your own paradigm? It is more flexible in its ability to metamorph into whatever you envision. Take XMLisp for example. That bring said, and because it us gat I'm most familiar with, CL is perfectly capable platform for implementation of something as rigorourous as you like. One example of this that comes to mind is a small project that was on lisppaste about a year ago by pascal bougeron (sp?) otherwise known as informatimago.com where he implemented a lambda calculus based computing model from the ground up. Just lambda nothing else. Numbers, for example, were built out of lambda, not any other primitive representation. Obviously he didn't go to the extent of developing a whole extensive platform based on this, but had did develop it far enough that you could see how it could continue to be extended to become one. Obviously strict lambda-calculus is not the most effective or convenient computing model for general real-world computation but this is an example of how one might do such things using a pure mathematical lambda-calculus model of computation.

I know very little about Haskell so I'll drop it, but I was under the impression that it's foundations were fairly rigorous.

I think the definition of function is fairly well known. Purely functional languages take pains to be faithful to the concept.

What is an object? An object is the composite of a function and an environment. An environment is a set of frames. A frame is a collection of bindings. A binding is the association of a variable and a value that is held to be true for some scope and extent. That is all stuff from SICP. Objects may, but do not have to, deviate from pure functions by allowing these bindings to be mutable locatives for storage of information local to the object(s) known as it's state. This deviates from pure function but turns out to be very useful in practice. Alternatively one may look to monads for a more pure way to deal with this sort of concern but that is another topic.

In practical terms an object is typically a simple a lexical closure:

(defvar object

(let ((x 1)(y 2))

(Lambda (op &optional (value '%unbound%))

(If (functionp op)

(Funcall op x y)

(If (EQ value '%unbound%)

(Symbol-value op)

(Setf (Symbol-value op) value))))))

(Funcall object #'+) => 3

(Funcall object 'x) => 1

(Funcall object 'x 5) => 5

(Funcall object #'+) => 7

(Funcall object 'x) => 5

Oh well that's very primitive and off the cuff but it serves as the basic example. For a really amazing example of this, see Doug hoytes book Let over Lambda, where he develops a very useful object system using what he calls pandoric closures. At heart they are based on nothing more than I used above. I like these things quite a bit actually and use them in many of my projects as a lightweight more flexible alternative to CLOS that is especially good when ... Oh never mind its a whole other conversation. I can give you a link to source if you want. It's in my cl-ctrie project on github there's a file called ctrie-lambda.lisp which includes everything (my customized implementation) and an example at bottom showing a simple use scenario.

+Dan Lentz i'm not very convinced. The subject of this post can be interpreted broadly, but let's be specific and narrow, so maybe it could be more useful. in particular, i want to claim, that the term "function" doesn't have a logical foundation in almost all computer languages. (i chose function instead of object because i think it's simpler. I think the question can also be: what's a array, list, closure, reference, macro ,and perhaps even expression, primitive...)

i do not know precisely to what degree is well-defined to me, or what i mean by logical foundation, but we can find out when we discuss.

let's pick a lang, hopefully something both you and me know well, and start asking what's a function.

also, my intention isn't tricky. I simply wanted to know, for example, when a average programer asks 'what's a function" (or what's a object, in lang xyz, as this'd be more common, can be seen in stackoverflow), and what answer can one give?

and again, most programer would understand what it is after a rough description, as you did gave the descriptions. But i wanted a foundational definition, a definition that one can for example write a algorithm that determine whether something is a function or not.

i do not know precisely to what degree is well-defined to me, or what i mean by logical foundation, but we can find out when we discuss.

let's pick a lang, hopefully something both you and me know well, and start asking what's a function.

also, my intention isn't tricky. I simply wanted to know, for example, when a average programer asks 'what's a function" (or what's a object, in lang xyz, as this'd be more common, can be seen in stackoverflow), and what answer can one give?

and again, most programer would understand what it is after a rough description, as you did gave the descriptions. But i wanted a foundational definition, a definition that one can for example write a algorithm that determine whether something is a function or not.

No I agree entirely. But I stand behind that formal systems can and have been implemented, the informatimago lambda calculus being one concrete example. Of course none of those languages you mentioned are (or ever aspired to be) even remotely mathematical.

BTW a function is a mapping between two sets called the domain and range whereby every element of the domain is mapped to one and only one element of the range.

Or something close to that it's been a while since my last math quiz... :)

BTW a function is a mapping between two sets called the domain and range whereby every element of the domain is mapped to one and only one element of the range.

Or something close to that it's been a while since my last math quiz... :)

+Dan Lentz the issue you mentioned, about foundation of computer languages, i don't have disagreement neither.

though, i don't believe anything that Pascal guy says. He's a Common Lisp nutcase. His lambda calculus, and basically all lisper's talk of it, is pure bullshit. They don't know math.

though, i don't believe anything that Pascal guy says. He's a Common Lisp nutcase. His lambda calculus, and basically all lisper's talk of it, is pure bullshit. They don't know math.

And again, a function + environment = an object.

How can you say that the notion of an array is not precisely defined and then go and be perfectly happy working with matrices on paper? So is a matrix not something that can be defined either?

How can you say that the notion of an array is not precisely defined and then go and be perfectly happy working with matrices on paper? So is a matrix not something that can be defined either?

only a few programer i can trust when it comes to the math subject of logic, lamba calculus, or programing language foundations. For example, the Mark guy who invented Qi, or some of the Scheme Lisp of Rice University guys, John McCarthy, or EWD guy.

I've worked with a bunch of his code. He's not a dumb guy. But just about everyone is the CL community is indeed some form of nutcase... Myself included :)

Dan Lentz

+

1

2

1

2

1

Did you find the code I was talking about and read it? Or are you simply rejecting it based on your personal prejudices and past disagreements?

but ultimately, when one talk about lambda calculus, one got to have strong pure math background, because that's the realm, the ground, the context. That's what programers don't have.

Naturally -- very few programmers are competent mathematicians. Myself included -- although I have tried to stretch as far as I can plus a bit to at least not be completely ignorant mathematically -- just mostly ignorant ;). I did a minor in math and concentration in mathematics of computation but to be honest it got to a point like after diff-EQ and before complex variables where it was really starting to get onerous to deal with. Without exclusively focusing on it it was really difficult to keep going and absorb. And I really started to not enjoy it.

OTOH I contend that similarly very few mathematicians are good programmers (they are all under the impression that they are, however...). It is a different set of skills just with some overlap.

I have read a number of severe criticisms of Qi.

OTOH I contend that similarly very few mathematicians are good programmers (they are all under the impression that they are, however...). It is a different set of skills just with some overlap.

I have read a number of severe criticisms of Qi.

+Dan Lentz i'm skipping what you post about the Pascal guy, because we've been dissing each other for half a decade in comp.lang.lisp. I've seen enough of his arguments. He is perhaps among the top 5 Common Lisp fanatics in comp.lang.lisp since about 2006 (after Naggum and Kent went away). Note: Common Lisp only, not other. For example, he'd diss clojure, scheme, NewLisp, in a fanatical way. He also called Ruby creator Matz as idiot... lol. So, what am saying is that, sometimes i make hyperbolic claims and people call me a troll, he and others are not much better.

Fabrice Popineau

+

1

2

1

2

1

I don't know how much relevant you will find it, but I think your original question is wrecked. Programming languages apply in a context much different from maths. Mathematica is a programming language and a tool to do maths. But that's pretty uncommon. The rest of the times, programming languages apply on finite data sets, not quite the same domain as maths. The machine on which they run is sequential, and so are input/output. Math usually does not handle time : mathematical properties are time independent. There is a difference between a (mathematical) function and an algorithm.

So the question is not so much about mathematical foundations of programming languages, but how to mathematically handle properties of programs, which is a little bit different.

Mathematical models of computation do exist (Turing Machines, ASM etc.) and the bridge from high level programming languages to those models too. However it is hard to cope with it.

It is true that the only easy case of proving program properties is with pure lambda calculus (no mutability). This is the closest to mathematical objects. Whenever mutability , sequentiality or parallelism enters the game (and you can't discard them for any real application), thing get messy.

Here are two pointers I think that are of interest. The first one is about formal methods at MS

http://research.microsoft.com/en-us/news/features/terminator.aspx

and

http://research.microsoft.com/apps/pubs/default.aspx?id=70038

The second one is about Coq which is one of the most advanced tools in the area of building "safe" code :

http://coq.inria.fr/

So the question is not so much about mathematical foundations of programming languages, but how to mathematically handle properties of programs, which is a little bit different.

Mathematical models of computation do exist (Turing Machines, ASM etc.) and the bridge from high level programming languages to those models too. However it is hard to cope with it.

It is true that the only easy case of proving program properties is with pure lambda calculus (no mutability). This is the closest to mathematical objects. Whenever mutability , sequentiality or parallelism enters the game (and you can't discard them for any real application), thing get messy.

Here are two pointers I think that are of interest. The first one is about formal methods at MS

http://research.microsoft.com/en-us/news/features/terminator.aspx

and

http://research.microsoft.com/apps/pubs/default.aspx?id=70038

The second one is about Coq which is one of the most advanced tools in the area of building "safe" code :

http://coq.inria.fr/

Time can be handled very effectively, actually, in a way quite well suited to immutable values and functional orientation. If every binding is associated with a time representation as well as value, then that can easily be immutable. Rebinding a variable simply associates the replacement value and an updated time coordinate. The old ones never go away -- it will always be true that at the time point in question it's value used to be the previous one. Time coordinates might be some type of serial number, a transaction identifier, or even a uuid.

For an excellent example of this approach in practice have a look at Datomic -- a graph type database hosted on JVM and very popular in the clojure community.

More generally what I've been calling a time coordinate may be more broadly interpreted as a unique designation of context. IE there is no inherent need to even model this "time" coordinate as a sequential property at all. Only one that is computable in a manner that facilitates future retrieval of the bound value in the context designated by that coordinate. This relates to the use of UUID's that I mentioned previously: they are an ideal means of computing values appropriate for use as such context, but with no requirement for centralized coordination in a distributed environment. This is a crucial advantage for development of parallel computing models.

For an excellent example of this approach in practice have a look at Datomic -- a graph type database hosted on JVM and very popular in the clojure community.

More generally what I've been calling a time coordinate may be more broadly interpreted as a unique designation of context. IE there is no inherent need to even model this "time" coordinate as a sequential property at all. Only one that is computable in a manner that facilitates future retrieval of the bound value in the context designated by that coordinate. This relates to the use of UUID's that I mentioned previously: they are an ideal means of computing values appropriate for use as such context, but with no requirement for centralized coordination in a distributed environment. This is a crucial advantage for development of parallel computing models.

+Fabrice Popineau what you posted is about foundation of programing languages. It's slightly different from what i want though.

simple question that programer asks all the time: what's a object, what's a list, what's a reference. For example in lisp, what's the list is eternally confusing, because each lang's idea of a "list" is different, and the word it self are sometimes used in broad English meaning, but sometimes in some lang it has a very specific technical meaning.

i was reading Flanagan book book, and he's quite painstaking about definitions in detail, more than any i've read in comp lang book. Yet, when i think about it, what's a object in js, i realized it's still not answerable, unless one goes on into several pages of describtion, yet still isn't a definition as do epsilon-delta limit of math.

same applies to most terms in most languages.

simple question that programer asks all the time: what's a object, what's a list, what's a reference. For example in lisp, what's the list is eternally confusing, because each lang's idea of a "list" is different, and the word it self are sometimes used in broad English meaning, but sometimes in some lang it has a very specific technical meaning.

i was reading Flanagan book book, and he's quite painstaking about definitions in detail, more than any i've read in comp lang book. Yet, when i think about it, what's a object in js, i realized it's still not answerable, unless one goes on into several pages of describtion, yet still isn't a definition as do epsilon-delta limit of math.

same applies to most terms in most languages.

in emacs lisp, it has listp that tells us exactly what's a list. It has also several others on all other types in list. So, i think elisp do answer my question. That is, something is X when Xp(X) returns t.

Fabrice Popineau

+

1

2

1

2

1

+Xah Lee What you want, I have the feeling that you would find it in Coq or in Isabelle, where all kind of entities have to be precisely defined, and their behavior too. Some of these tools allow you to generate actual programs, and "good" ones (without bugs, meeting their specs).

In some way, they allow you to program in a clean environment.

In some way, they allow you to program in a clean environment.

+Fabrice Popineau i think someday i'll have to learn them (Coq or Isabelle).

actually to be precise there is no such thing as a list in CL. There are cons cells, which are well-defined. A list is a composite higher level structure that can be built from them but so may trees and rings. Or improper lists. They are not primitive and I don't think whether or not their semantics has a bearing on the fundamental well-definedness of the language. Cons cells otoh are very explicitly defined and I don't understand what ambiguity you see in them.

You keep returning to the issues of the mathematical foundations of objects in JavaScript and I think you are not going to find what you are looking for there. But to say that there do not exist languages which DO have rigorously defined mathematical foundation based on the single example which doesn't is not a valid argument. Even if you are unwilling to look at example implementations of lambda calculus, fabrice has proposed two others that are also valid counter examples. Even if you are unwilling to look at LC implementation in Common Lisp there are others in other languages which equally satisfy the criterion you seem to keep returning to -- a rigorous and purely mathematical model of computation.

Also, it's not a very convincing argument to me that LC simply cannot be discussed with anyone but the most gifted mathematicians. If there is some reason it does not satisfy the requirements you have listed, then explain specifically why not. If it is an argument of such depth and complexity that it is over my head then so much the better -- it will give me something to study and an opportunity for expanding my horizons. But as it stands it seems like you've just done some hand-waving and denial as a blanket refutation of that avenue of discussion

You keep returning to the issues of the mathematical foundations of objects in JavaScript and I think you are not going to find what you are looking for there. But to say that there do not exist languages which DO have rigorously defined mathematical foundation based on the single example which doesn't is not a valid argument. Even if you are unwilling to look at example implementations of lambda calculus, fabrice has proposed two others that are also valid counter examples. Even if you are unwilling to look at LC implementation in Common Lisp there are others in other languages which equally satisfy the criterion you seem to keep returning to -- a rigorous and purely mathematical model of computation.

Also, it's not a very convincing argument to me that LC simply cannot be discussed with anyone but the most gifted mathematicians. If there is some reason it does not satisfy the requirements you have listed, then explain specifically why not. If it is an argument of such depth and complexity that it is over my head then so much the better -- it will give me something to study and an opportunity for expanding my horizons. But as it stands it seems like you've just done some hand-waving and denial as a blanket refutation of that avenue of discussion

+Dan Lentz foundation of comp lang is well done, i don't question that.

what i wanted to explore is a more precise definition of many common things in computer languages that average programers need to know. Things like object, primitive, function, inheritance, list, etc. I roughly claimed it's mostly not defined in most langs, and i think it's bad. At least, JavaScript lang fails miserably on Object. Perl also fail in object. I am pretty sure python fail in definition of object too. Yet, object is critical a concept in these langs, and it has certain technical meaning in javascript and python.

what i wanted to explore is a more precise definition of many common things in computer languages that average programers need to know. Things like object, primitive, function, inheritance, list, etc. I roughly claimed it's mostly not defined in most langs, and i think it's bad. At least, JavaScript lang fails miserably on Object. Perl also fail in object. I am pretty sure python fail in definition of object too. Yet, object is critical a concept in these langs, and it has certain technical meaning in javascript and python.

No, mostly I am still engaged in the discussion as a means of procrastination rather then making the revisions to my CV that were requested by a recruiter who I need to get back to today. I don't know why but resumes are the most loathesome documents in the universe to have to work on. Plus, also, I thought there was some merit to a few of the points I was trying to address from your posts and the general enjoyment of contributing to an interesting discussion.

But yes, on the broad strokes it seems like we may agree. I didn't intend for any of my comments to give the impression of ranting, ill temper, or anything other than good-natured discussion. If that seemed to be the case, I apologize.

But yes, on the broad strokes it seems like we may agree. I didn't intend for any of my comments to give the impression of ranting, ill temper, or anything other than good-natured discussion. If that seemed to be the case, I apologize.

+Xah Lee JavaScript has an ECMA definition, so I bet that those concepts are well defined somewhere. OTOH, Perl and Python are only defined by their implementation.

Add a comment...