Evidently not. I was talking about functional programming languages and SSA. You interjected and said (paraphrasing) that "it" strikes you as backwards, like forth. Lisp has SSA variables, by the way. Scheme does, at least in the context of a single REPL-cycle. This is how Scheme functions get their names. Without the let or define syntactic forms, functions would have to be anonymous.
No, your assertion is not correct. The programs are not the same, because they do not perform the same computation.
My programs perform isomorphic computations. Sure, using functional syntax I'll get a result like "f(x) = y". And using logical syntax, I'll get something along the lines of "|- f(x,y)". (Or if I just did it with the same interpreter, f(x,y) = #t. (Are you going to complain about the syntactic sleight of hand there too?)
Only in a technical sense. When it is said that logic programming languages use "unification", they are overloading the term to mean that they use a particular algorithm (the "unification" algorithm) that gives the most general unification, and they use this to search for all ways of satisfying a given relation. Functional languages only give at most one way a relation can be satisfied (which is, after all, what makes a relation a function!).
The technical sense is the only sense that matters in technical discussions. I'll take your explanation as a concession of the point. By the way, a unification, if it exists, is unique up to isomorophism.
Nice try, but no! Finite domains? The domain of a function in a functional program can be infinite.
If you know of a computer that can store arbitrary integers (let alone a set of arbitrary cardinality), I suggest you buy stock now. Functional programming is not the same as the lambda calculus, though they are obviously closely related. If we were talking about the lambda calculus.
And you haven't even proven the other half of the equivalence, that logic programs can be trivially rewritten as functional languages. Give some evidence for that: a program is equivalent to the function it computes, so given that the logic program given before computes all numbers x, y for which the relation "sum" holds for sum(x, y, 10), how would you transform the program to give that list of numbers in a functional language?
You're trolling, right? I have already done this, twice. The answer lies in the meaning of beta-reduction in the context of truth functions. (More succinctly, truth functions ARE FUNCTIONS). There's no need to "translate" the program, because application of truth functions is a specialized form of functional evaluation. The fact that logic programming languages use specialized unification algorithms is immaterial to this point. They are still computing the "substitution instance" join of the truth functional values of certain sentences.
Not very surprising. Vim comes in first in resource economy. Emacs second. TextMate third. Xcode fourth. But the difference between emacs and TextMate is negligible. Xcode is rather large in comparison, but I wouldn't call it a monstrosity. (I realize you didn't call it one -- it's the only "full featured" IDE I have installed on this box)
I'll stick to TextMate unless I'm building Cocoa applications or logged in remotely.
That's just disingenuous. True, you could write the definitions of "add" from the Prolog program (with trivial adjustments for syntax) in Haskell, and it would define the same "add" function, in a purely mathematical sense. But it wouldn't be the same program.
The right word to use here is "correct", not "disingenuous." You evidently don't understand my point. The model for evaluation in a logical programming language is called "unification". From the Wikipedia article:
In mathematical logic, in particular as applied to computer science, a unification of two terms is a join (in the lattice sense) with respect to a specialisation order. That is, we suppose a preorder on a set of terms, for which t* ? t means that t* is obtained from t by substituting some term(s) for one or more free variables in t. The unification u of s and t, if it exists, is a term that is a substitution instance of both s and t. If any common substitution instance of s and t is also an instance of u, u is called minimal unification.[1]
A lattice of sentences is formed, and the image of the lattice under truth functions (the arrow, cup, cap, biconditional, negation) is considered.
Guess how functional programming languages are evaluated. By unification! Only, instead of just considering truth functions (they are included), arbitrary functions are evaluated. Logical programming is, trivially, a specialized form of functional programming. One that deals with truth functions. The fact that logical programming languages use different algorithms to compute the join is a mere implementation detail and irrelevant to this point.
The "hard" part is showing that every functional program has an equivalent logical program. Since these are all finite domains, a brute force approach is fine. Take a function F (as a set). For each element (x,y) in F, declare that f(x) = y is true using the logical language's syntax. Use short-hand syntax if you'd like. Q.E.D.
Maybe I'm missing something, but all of the turing-complete approaches to computation are equivalent, and there are accordingly transformations between them. What makes this transformation more trivial than the others, that it renders the distinction between logic and functional programming less meaningful than the distinction between functional and any other approach?
This is rather hard to answer. Obviously, my point wasn't about models of computation. It was about the equivalence of programming paradigms. For example, it turns out that continuations and objects are equivalent in this sense. You can implement objects using continuations. You can implement continuations using objects. Neither alone is Turing complete. So the Church-Turing thesis doesn't apply. In effect, objects and continuations are just different syntax for the same idea. This is unlike Turing machines and the Lambda calculus, which are conceptually very different -- functions are inherently stateless, whereas Turing machines change over time.
Specifically addressing your question: the intimate relationship between functions and truth functions (a specific kind of function, and a necessary concept for the definition of functions). As I said, a function can easily generate a truth function. A truth function can even more trivially generate a function (since it's a function already).
Now, note that because of this paradigmatic equivalence, functional and logical programming share properties that might have seemed surprising before. They're both side-effect free. Both, in principle, allow currying (despite being very non-obvious in the case of logical programming).
Yes, it is just a Lisp dialect. Common Lisp is the other major dialect. First, note that Common Lisp's specification is around 1300 pages long. Scheme's is about 70. Obviously, CLisp has more features "built in" to the language. It also has better support for macros. However, Scheme's weaknesses aren't so weak in practice. Most Scheme implementations come with de facto standard libraries implementing most of CLisp's extras. Macros are kind of a big deal, but Scheme does support them. On the other hand, Scheme supports continuations, which CLisp cannot.
I personally like Scheme because I was looking for a good functional/OO language. Scheme was originally designed to study the Actors model of computation (a kind of message passing OO model), and obviously has strong functional support. It's small and easy to learn. CLisp just looked intimidating to me.:-)
But unlike constants those single-assignment vars can't be optimized at compile time, and still can't replace normal variables.
Red herring. Single Static Assignment introduces an entire class of possible optimizations to code structure. But the compile time optimizations you mention are designed to put the constants in SSA form so that SSA form optimizations can be carried out. GCC uses SSA form internally a lot.
Functional language variables are strange. They're essentially a part of the environment, not a part of the program. Use them like you would environment variables and you'll be fine. Writing an OO framework in a functional language is pretty easy (that's what they were designed for in the first place). So maintaining state (locally) is possible.
add(X, 0, Sum):- Sum = X. add(0, Y, Sum):- Sum = Y. add(X, Y, Sum):- dec(X, 1, X2), inc(Y, 1, Y2), add(X2, Y2, Sum).
(at prompt) > add(2, 3, Sum) Sum = 5 (as you say, trivially reproduceable in any functional language.) > add(X, 3, 5) X = 2 (How do you "trivially" reproduce this in a functional language?) > add(X, Y, 2) X = 0, Y = 2 X = 1, Y = 1 X = 2, Y = 0 (Likewise?)
You're going to shit bricks when you realize just how trivial the transformation is. It's already in a functional language. A truth functional language. A truth function is a function that takes a sentence to a truth value.
The crux of the matter is that a function F can be defined to be a set of ordered pairs with the property that if (x,y) and (x,z) are in F, then y = z. In short, a function F is a model for the predicate f(x,y) (which is short for f(x) = y). Moreover, sentences of the form f(x) = y (one for each x in the domain) completely determine F.
You used a similar construct in your example. As I'm sure you're aware, 'add(X,Y,Sum)' is a predicate meaning "X + Y = Sum". Also, the inc and dec "sentences" are short-hand for a class of sentences of the form "(X - n) + (Y + n) = Sum", where n is free in my description. Thus the addition function is completely determined.
In case you missed it, I wrote that I'm a mathematician (making your counter-example redundant), but that there are few mathematicians here. Usenet is a better resource for this kind of question.
For the record, my last job involved data mining a 5000 dimensional space.
In the context of truth functions, unification is function application. The difficulty is in showing that unification is sufficient to "trivially" emulate function application. In broad strokes, this is done by first noting that a function F can be written as a set of ordered pairs with the property that if (x, y) in F and (x, z) in F, then y = z. Thus suggests a truth functional definition of the function, which I will summarize by defining a class of propositions. We say f(x) = y iff (x,y) in F. Propositions of the form f(x) = y can trivially undergo unification.
If you know perl, you can learn functional programming in about a day. You can learn the concepts involved in about an hour. See http://perl.plover.com/lambda/.
As far as your example goes, note that if you allow yourself mathematical syntax, since trans1 = G(item), F(trans1) = F ( G(item) ). Indeed, since F and G are functions, we can create a new function (F o G) given by the rule (F o G)(x) = F( G(x) ). This is called functional composition. Lambda is a function constructor, as it is in the lambda calculus.
The functional program says:
1. create a function called 'compose2' which takes two arbitrary functions (which for the purposes of the definition will be called F and G) as arguments. Define compose2 as F ( G ( x) ).
2. Let "target" be the result of applying (F o G)(x) (as described above) to each element in a list called source_list. (The semantics of map mean that target is a list such that target[i] = (F o G)(source_list[i])
The distinction between a functional and logic programming language is merely syntactical, due to the trivial characterization of functions in terms of truth functions (and truth functions in terms of functions).
Mathematician here, though this isn't my field. Slashdot isn't a very good place to ask this kind of question, since there aren't many mathematicians on here, and it's a very broad topic. I suggest Usenet -- specificially the sci.math newsgroup. I know at least 50 mathematicians who post regularly, and a lot more lurk (and occassionally answer questions).
Blah blah blah... Libertarian... blah blah Ayn Rand is my hero... blah blah blah.
In case you hadn't noticed, stores invite people onto their premises. You have implicit (and often explicit) permission to enter a store to do business. The terms under which that business occurs can only be settled by actually doing the business, which requires that the customer be in the store. The only way to turn an invitee into a trespasser is to ask them to leave.
I prefer a fountain pen and vellum. Easier and faster to write with than pencil and paper, giving me more time to focus on the material rather than taking notes. Rhodia makes very nice "vellum paper" notebooks, and Schaeffer makes $10 "disposable" refillable fountain pens. I got one of those on a lark and was hooked. Try it sometime. You might like it.
First, he assumes that all elliptical galaxies have a point-of-view from which they appear circular. I don't think anyone has determined this to be the case, and he doesn't really have a way to get this from his data.
Assuming the galaxies are elliptical, this is a trivial result of projective geometry.
There's not any "circumvention" going on, any more than it's circumvention that I can processes running both GPL and non-GPL applications on my PC. Just some hypervisor hype from - surprise! - a hypervisor vendor.
Well, that's not exactly fair. If you're running a GPL kernel and a non-GPL application on your PC, you can set up a "rootkit" on the kernel to capture the non-GPL application's output, circumventing the manufacturer's DRM. This is why Tivo started using signed binaries. The hypervisor scheme makes this scheme impossible.
But I agree. Using a hypervisor in this fashion is clearly not a GPL violation, in letter or spirit.
Slashdot Mirror
Evidently not. I was talking about functional programming languages and SSA. You interjected and said (paraphrasing) that "it" strikes you as backwards, like forth. Lisp has SSA variables, by the way. Scheme does, at least in the context of a single REPL-cycle. This is how Scheme functions get their names. Without the let or define syntactic forms, functions would have to be anonymous.
No, your assertion is not correct. The programs are not the same, because they do not perform the same computation.
My programs perform isomorphic computations. Sure, using functional syntax I'll get a result like "f(x) = y". And using logical syntax, I'll get something along the lines of "|- f(x,y)". (Or if I just did it with the same interpreter, f(x,y) = #t. (Are you going to complain about the syntactic sleight of hand there too?)
Only in a technical sense. When it is said that logic programming languages use "unification", they are overloading the term to mean that they use a particular algorithm (the "unification" algorithm) that gives the most general unification, and they use this to search for all ways of satisfying a given relation. Functional languages only give at most one way a relation can be satisfied (which is, after all, what makes a relation a function!).
The technical sense is the only sense that matters in technical discussions. I'll take your explanation as a concession of the point. By the way, a unification, if it exists, is unique up to isomorophism.
Nice try, but no! Finite domains? The domain of a function in a functional program can be infinite.
If you know of a computer that can store arbitrary integers (let alone a set of arbitrary cardinality), I suggest you buy stock now. Functional programming is not the same as the lambda calculus, though they are obviously closely related. If we were talking about the lambda calculus.
And you haven't even proven the other half of the equivalence, that logic programs can be trivially rewritten as functional languages. Give some evidence for that: a program is equivalent to the function it computes, so given that the logic program given before computes all numbers x, y for which the relation "sum" holds for sum(x, y, 10), how would you transform the program to give that list of numbers in a functional language?
You're trolling, right? I have already done this, twice. The answer lies in the meaning of beta-reduction in the context of truth functions. (More succinctly, truth functions ARE FUNCTIONS). There's no need to "translate" the program, because application of truth functions is a specialized form of functional evaluation. The fact that logic programming languages use specialized unification algorithms is immaterial to this point. They are still computing the "substitution instance" join of the truth functional values of certain sentences.
Let's compare my `top`:
PID COMMAND %CPU TIME #TH #PRTS #MREGS RPRVT RSHRD RSIZE VSIZE
1030 vim 0.0% 0:00.15 1 14 19 816K 1.15M 2.26M 27.7
993 Xcode 0.0% 0:02.52 1 71 208 5.14M 7.75M 10.3M 145M
992 TextMate 0.0% 0:00.78 1 64 83 2.31M 3.79M 5.74M 121M
983 emacs 0.0% 0:00.18 1 15 28 1.18M 3.64M 3.56M 56.0M
Not very surprising. Vim comes in first in resource economy. Emacs second. TextMate third. Xcode fourth. But the difference between emacs and TextMate is negligible. Xcode is rather large in comparison, but I wouldn't call it a monstrosity. (I realize you didn't call it one -- it's the only "full featured" IDE I have installed on this box)
I'll stick to TextMate unless I'm building Cocoa applications or logged in remotely.
Fuck, I severed a nerve in my finger a few months ago. Cooking accident. It's gonna take years to grow back? FUCK.
The right word to use here is "correct", not "disingenuous." You evidently don't understand my point. The model for evaluation in a logical programming language is called "unification". From the Wikipedia article:A lattice of sentences is formed, and the image of the lattice under truth functions (the arrow, cup, cap, biconditional, negation) is considered.
Guess how functional programming languages are evaluated. By unification! Only, instead of just considering truth functions (they are included), arbitrary functions are evaluated. Logical programming is, trivially, a specialized form of functional programming. One that deals with truth functions. The fact that logical programming languages use different algorithms to compute the join is a mere implementation detail and irrelevant to this point.
The "hard" part is showing that every functional program has an equivalent logical program. Since these are all finite domains, a brute force approach is fine. Take a function F (as a set). For each element (x,y) in F, declare that f(x) = y is true using the logical language's syntax. Use short-hand syntax if you'd like. Q.E.D.
Sorry, didn't know.
Yes.
Maybe I'm missing something, but all of the turing-complete approaches to computation are equivalent, and there are accordingly transformations between them. What makes this transformation more trivial than the others, that it renders the distinction between logic and functional programming less meaningful than the distinction between functional and any other approach?
This is rather hard to answer. Obviously, my point wasn't about models of computation. It was about the equivalence of programming paradigms. For example, it turns out that continuations and objects are equivalent in this sense. You can implement objects using continuations. You can implement continuations using objects. Neither alone is Turing complete. So the Church-Turing thesis doesn't apply. In effect, objects and continuations are just different syntax for the same idea. This is unlike Turing machines and the Lambda calculus, which are conceptually very different -- functions are inherently stateless, whereas Turing machines change over time.
Specifically addressing your question: the intimate relationship between functions and truth functions (a specific kind of function, and a necessary concept for the definition of functions). As I said, a function can easily generate a truth function. A truth function can even more trivially generate a function (since it's a function already).
Now, note that because of this paradigmatic equivalence, functional and logical programming share properties that might have seemed surprising before. They're both side-effect free. Both, in principle, allow currying (despite being very non-obvious in the case of logical programming).
Yes, it is just a Lisp dialect. Common Lisp is the other major dialect. First, note that Common Lisp's specification is around 1300 pages long. Scheme's is about 70. Obviously, CLisp has more features "built in" to the language. It also has better support for macros. However, Scheme's weaknesses aren't so weak in practice. Most Scheme implementations come with de facto standard libraries implementing most of CLisp's extras. Macros are kind of a big deal, but Scheme does support them. On the other hand, Scheme supports continuations, which CLisp cannot.
:-)
I personally like Scheme because I was looking for a good functional/OO language. Scheme was originally designed to study the Actors model of computation (a kind of message passing OO model), and obviously has strong functional support. It's small and easy to learn. CLisp just looked intimidating to me.
Dance for me, puppet. Tell me more about Erlang.
The informed know more about Erlang than you do. They know your opinion doesn't matter. But they also know your opinion is entertaining.
But unlike constants those single-assignment vars can't be optimized at compile time, and still can't replace normal variables.
Red herring. Single Static Assignment introduces an entire class of possible optimizations to code structure. But the compile time optimizations you mention are designed to put the constants in SSA form so that SSA form optimizations can be carried out. GCC uses SSA form internally a lot.
Functional language variables are strange. They're essentially a part of the environment, not a part of the program. Use them like you would environment variables and you'll be fine. Writing an OO framework in a functional language is pretty easy (that's what they were designed for in the first place). So maintaining state (locally) is possible.
I don't mean to butt in with a contrary opinion, but have you looked into Scheme lately? There are several Scheme -> C/native code compilers available. http://community.schemewiki.org/?category-implemen tations
You're going to shit bricks when you realize just how trivial the transformation is. It's already in a functional language. A truth functional language. A truth function is a function that takes a sentence to a truth value.
The crux of the matter is that a function F can be defined to be a set of ordered pairs with the property that if (x,y) and (x,z) are in F, then y = z. In short, a function F is a model for the predicate f(x,y) (which is short for f(x) = y). Moreover, sentences of the form f(x) = y (one for each x in the domain) completely determine F.
You used a similar construct in your example. As I'm sure you're aware, 'add(X,Y,Sum)' is a predicate meaning "X + Y = Sum". Also, the inc and dec "sentences" are short-hand for a class of sentences of the form "(X - n) + (Y + n) = Sum", where n is free in my description. Thus the addition function is completely determined.
In case you missed it, I wrote that I'm a mathematician (making your counter-example redundant), but that there are few mathematicians here. Usenet is a better resource for this kind of question.
For the record, my last job involved data mining a 5000 dimensional space.
In the context of truth functions, unification is function application. The difficulty is in showing that unification is sufficient to "trivially" emulate function application. In broad strokes, this is done by first noting that a function F can be written as a set of ordered pairs with the property that if (x, y) in F and (x, z) in F, then y = z. Thus suggests a truth functional definition of the function, which I will summarize by defining a class of propositions. We say f(x) = y iff (x,y) in F. Propositions of the form f(x) = y can trivially undergo unification.
If you know perl, you can learn functional programming in about a day. You can learn the concepts involved in about an hour. See http://perl.plover.com/lambda/.
As far as your example goes, note that if you allow yourself mathematical syntax, since trans1 = G(item), F(trans1) = F ( G(item) ). Indeed, since F and G are functions, we can create a new function (F o G) given by the rule (F o G)(x) = F( G(x) ). This is called functional composition. Lambda is a function constructor, as it is in the lambda calculus.
The functional program says:
1. create a function called 'compose2' which takes two arbitrary functions (which for the purposes of the definition will be called F and G) as arguments. Define compose2 as F ( G ( x) ).
2. Let "target" be the result of applying (F o G)(x) (as described above) to each element in a list called source_list. (The semantics of map mean that target is a list such that target[i] = (F o G)(source_list[i])
Way simpler, once you get it.
The distinction between a functional and logic programming language is merely syntactical, due to the trivial characterization of functions in terms of truth functions (and truth functions in terms of functions).
Proving a theorem with ten different methods is very interesting. Those methods are often useful for proving novel theorems.
Mathematician here, though this isn't my field. Slashdot isn't a very good place to ask this kind of question, since there aren't many mathematicians on here, and it's a very broad topic. I suggest Usenet -- specificially the sci.math newsgroup. I know at least 50 mathematicians who post regularly, and a lot more lurk (and occassionally answer questions).
Blah blah blah... Libertarian... blah blah Ayn Rand is my hero... blah blah blah.
In case you hadn't noticed, stores invite people onto their premises. You have implicit (and often explicit) permission to enter a store to do business. The terms under which that business occurs can only be settled by actually doing the business, which requires that the customer be in the store. The only way to turn an invitee into a trespasser is to ask them to leave.
Pencil and paper are the tools to learn math.
I prefer a fountain pen and vellum. Easier and faster to write with than pencil and paper, giving me more time to focus on the material rather than taking notes. Rhodia makes very nice "vellum paper" notebooks, and Schaeffer makes $10 "disposable" refillable fountain pens. I got one of those on a lark and was hooked. Try it sometime. You might like it.
I suggest you try it. More fun than letting it spill.
Dude, I was eating.
First, he assumes that all elliptical galaxies have a point-of-view from which they appear circular. I don't think anyone has determined this to be the case, and he doesn't really have a way to get this from his data.
Assuming the galaxies are elliptical, this is a trivial result of projective geometry.
There's not any "circumvention" going on, any more than it's circumvention that I can processes running both GPL and non-GPL applications on my PC. Just some hypervisor hype from - surprise! - a hypervisor vendor.
Well, that's not exactly fair. If you're running a GPL kernel and a non-GPL application on your PC, you can set up a "rootkit" on the kernel to capture the non-GPL application's output, circumventing the manufacturer's DRM. This is why Tivo started using signed binaries. The hypervisor scheme makes this scheme impossible.
But I agree. Using a hypervisor in this fashion is clearly not a GPL violation, in letter or spirit.