Ah, thanks for posting about my Fexl language. Although I'm the author of it, and somewhat fond of it, I must emphasize this caveat: http://news.ycombinator.com/item?id=2717560 .
Although lazy evaluation is quite amazing, in certain circumstances I find that it's kicking my ass. For example, consider a function that simply sums the numbers from 1 to N:
\sum == (\N
long_le N 0
0
(long_add N (sum (long_sub N 1)))
)
Or, more tersely, using the semicolon as a syntactic "pivot" to avoid right-nesting:
\sum == (\N long_le N 0 0; long_add N; sum; long_sub N 1)
The problem is that when you call (sum 100000) it builds up a giant chain of (long_add 100000; long_add 99999; long_add 99998; ...) and then evaluates that monstrosity recursively.
So I need to do some more work on forcing early evaluation. You can start by using the standard accumulator trick:
\sum == (\total\N
long_le N 0
total
(sum (long_add total N) (long_sub N 1))
)
\sum = (sum 0)
But even then you still have the massive recursion problem because you're not forcing the addition operation early.
I'm thinking I just need to allow basic types like "long" to be called as functions with no effect (i.e. equivalent to the identity function, so you can do things like this:
\sum == (\total\N
long_le N 0
total
(
\total = (long_add total N)
total; # force evaluation; result is I (identity function)
sum total (long_sub N 1)
)
)
However, even that doesn't always do the trick, particularly when you're dealing with higher-level values that aren't basic data types. The problem occurs generally when you build up a big "chain" of calculations with arbitrary values, and you have no simple way of forcing evaluation along the way.
This is, of course, the classic struggle between eager and lazy evaluation. But if I don't do the evaluation lazily, I can't define recursion in terms of the closed-form Y combinator, namely (Y F) = (F (Y F)). Instead I'd have to define it in terms of some kind of run-time "environment" using either key-value pairs or the de Bruijn positional technique -- something I've managed to avoid thanks to lazy evaluation in terms of pure combinators.
So I must say that although Fexl is an interesting pure-combinator lazy evaluation language, the jury is still out on its practical utility, in my humble opinion. I've used it in some projects as an embedded interpreter, but the application was quite constricted so you didn't encounter some of these larger issues.
the discussion of side effects on that page is confusing. all you seem to be saying is that any function can be redefined. you do not need to mention side-effects to say that. it is confusing because anyone reading who knows about functional programming is going to see mention of "side effects" and "print" and expect some kind of discussion related to the problems that monads in haskell address (that you can change and examine state in the file system).
also, you should explicitly say somewhere that it is eager (not lazy) (if it is).
also, i couldn't find any discussion of whether it is possible to mutate state (i assume not, but you don't say). related, a table of contents would be a big help - and obvious initial question is "how are data structures handled?" and you don't know where to find the answer when you at the top of the page.
(this is not meant to say that your language is bad - i am just trying to help you "sell" you language to people that read your page!)
What is an "expression language"? I just started doing Java EE crap and there is an assortment of "ELs" that you can embed in your java apps.
Outside of Java, an "expression language" doesn't make any sense to me. An expression, statement, binding, assignment, application, and abstraction are all constructs, or elements of programming languages. Most of them can be implemented using others, sure, but I expect all useful languages to be capable of all. So, my question is, what makes an expression language an expression language, to the exclusion of all other constructs? (IOW, why is that particular part being made into a defining characteristic of the language?)
:) It's a function expression language, meaning a language for expressing pure functions of an arbitrary nature. It's really just a variant of the lambda calculus, and I compile those expressions into combinators to eliminate all variables.
For example, the "flip" function for swapping the order of two functions is this:
\flip = (\x\y y x)
But Fexl converts that into pure combinators like so:
\flip = (S (C (S I)) C)
Actually it uses the higher level combinators L, R, I, etc. so that flip is defined as:
\flip = (L I)
But the higher-level are shorthand for forms that use S and C only.
Ah -- concatenative languages, yes. I'm becoming a big fan of simple token-based concatenative languages. See my summary here of my recent travails: http://fexl.com/second_thoughts .
In short, instead of Fexl I've started using a simple token-based language. Like Joy, my token-based language uses a stack. But my language also uses a global mutable key-value space, and it only supports keys and values which are strings (which may be interpreted as numbers).
I think my little language is easier to "execute" manually on a white-board in a way that's easy for non-programmers to follow along. I don't need a lot of arcane "stack flip-aroo" operators like Forth and Joy use.
So how do I do a sort you ask? I just jam a bunch of keys into the key-value space and then use "next" to iterate through them. The key-value space does the sorting for me.
What about strictly sequential lists you ask? I can just store a bunch of keys using a scheme like this:
By prefixing a single character which represents the number of digits, I get the proper numerical order when I iterate in ASCII character order.
You know what my real goal is? I want to be able to give my non-programmer colleagues the ability to embed little snippets of computation here and there, making simple things simple, but also imposing no upper bound on the possibilities of what they might do.
You went off the rails because you replaced (C z) with z. That is not a valid equivalence. (C z) does not equal z. But (C z) applied to anything else does equal z. So in particular, (C z) (C z) equals z.
Here's how the reduction sequence goes:
: S C C z
= (C z) (C z)
= z
If you think about it, that second C can be replace with anything and it still works:
: S C anything z
= (C z) (anything z)
= z
That C there simply "holds on" to its first argument, and then when it encounters any second argument, it ignores it completely and yields up the thing it was holding onto.
Also, you'd be surprised at how self-application can actually mean something. Consider how a recursive function is defined using the Y combinator, which is governed by this rule:
Y F = F (Y F)
OK now that's not exactly self-application yet, but now let's dig into the Y combinator a bit and see how it can be defined in terms of a Q combinator:
Y = S Q Q
Now what is Q you ask? It can be defined as a lambda expression this way:
\Q = (\x\y x (y y))
Aha! There's a self-application for you. See how y is applied to itself there.
Now let's use the abstraction algorithm to convert Q into combinators step by step, removing the variables:
\Q = (\x\y x (y y))
\Q = (\x S (\y x) (\y y y))
\Q = (\x S (C x) (S (\y y) (\y y)))
\Q = (\x S (C x) (S I I))
\Q = (S (\x S (C x)) (\x S I I))
\Q = (S (S (\x S) (\x C x)) (C (S I I))
\Q = (S (S (C S) C)) (C (S I I))
OK that was kind of fun but all I did was demonstrate that Q can be defined in terms of S and C. That's actually somewhat irrelevant. The main point is to demonstrate that when you apply the Y combinator to an arbitrary function, you can in effect get recursion. So let's follow the reduction sequence:
: Y F
= S Q Q F
= (Q F) (Q F)
= Q F (Q F)
= F ((Q F) (Q F))
= F (S Q Q F)
= F (Y F)
Now let's show how you can actually remove self-reference from a recursive function. Consider this recursive definition of the function which appends two lists:
\append == (\x\y x y \h\t cons h; append t y)
Now as it turns out, the "==" in Fexl is merely a short-hand which does this for you:
\append = (Y \append \x\y x y \h\t cons h; append t y)
That's actually a non-recursive definition of append there. Consider the body of the function by itself:
(Y \append \x\y x y \h\t cons h; append t y)
There are no free variables in that. The inner call to "append" actually refers to the \append when encloses it. So you actually have a fully closed form function there which calls itself.
You can look at it this way, separating that inner function out and calling it F:
\F = (\append \x\y x y \h\t cons h; append t y)
\append = (Y F)
So if we actually apply that function to two lists, it goes like this:
: append x y
= Y F x y
= F (Y F) x y
= F append x y
= (\x\y x y \h\t cons h; append t y) x y
= x y \h\t cons h; append t y
And then it proceeds from there depending on what x is. It's amazing stuff, being able to defined a fully closed-form function which somehow manages to reach out and call itself. :)
What a difference a day makes. The day after this discussion about my problems with lazy evaluation, I figured out an incredibly simple solution: http://fexl.com/eager_and_lazy
OK, I'll discuss what's different and leave "better" out of it.
1. In Fexl, there is no distinction between data and function. All data structures such as lists, pairs, etc. are represented as functions.
2. Fexl has a small grammar, about as small as I think is feasible for expressing arbitrary functions. You could actually omit these rules:
exp => \ sym = term exp
exp => \ sym == term exp
exp => ; exp
But the resulting forms would be far more difficult to write and understand.
3. Fexl has a very simple compilation and evaluation strategy, reducing everything to combinatorial forms. There are no "environments" or "closures" or "contexts" being whipped around at run-time. The resulting Fexl executable program is about 35K in size.
4. Unlike other functional programming languages, Fexl does not rely on "pattern matching" for branching on the different possible forms of a piece of data. Instead, it simply calls that piece of data as a function, passing in the appropriate handlers for the various cases. For example, using excessively verbose function names here:
list
handle_empty_list
\head\tail handle_first_item head; handle_remainder tail
5. Fexl doesn't really have a distinct concept for defining a name -- that's all handled normally by lambda calculus. However it does provide the syntactic shorthand "=". For example this function:
\square = (\x mul x x)
print (square 4)
Is equivalent to this function, which does not use the "=":
(\square print (square 4)) (\x mul x x)
I'm not exactly sure if that's oh-so-different from other programming languages, but I'll venture a guess that many of those other languages use a symbol table to store function definitions at run-time, while Fexl does not.
6. Fexl never creates circular data structures in memory. Now because of lazy evaluation, you can create logically circular or infinite structures in Fexl, but these are always closed forms and never involve literal circularity in memory. Consequently it is possible to manage memory using reference counting -- and Fexl does that. Some may not like that, but it's simple and it gets the job done. The code even has a built-in assertion to ensure that all memory was properly reclaimed at the end of a run.
(I'm not certain that other languages create circular structures in memory, but I am certain that Fexl does not so I thought it worth mentioning.)
[+] [-] fexl|14 years ago|reply
Although lazy evaluation is quite amazing, in certain circumstances I find that it's kicking my ass. For example, consider a function that simply sums the numbers from 1 to N:
Or, more tersely, using the semicolon as a syntactic "pivot" to avoid right-nesting: The problem is that when you call (sum 100000) it builds up a giant chain of (long_add 100000; long_add 99999; long_add 99998; ...) and then evaluates that monstrosity recursively.So I need to do some more work on forcing early evaluation. You can start by using the standard accumulator trick:
But even then you still have the massive recursion problem because you're not forcing the addition operation early.I'm thinking I just need to allow basic types like "long" to be called as functions with no effect (i.e. equivalent to the identity function, so you can do things like this:
However, even that doesn't always do the trick, particularly when you're dealing with higher-level values that aren't basic data types. The problem occurs generally when you build up a big "chain" of calculations with arbitrary values, and you have no simple way of forcing evaluation along the way.This is, of course, the classic struggle between eager and lazy evaluation. But if I don't do the evaluation lazily, I can't define recursion in terms of the closed-form Y combinator, namely (Y F) = (F (Y F)). Instead I'd have to define it in terms of some kind of run-time "environment" using either key-value pairs or the de Bruijn positional technique -- something I've managed to avoid thanks to lazy evaluation in terms of pure combinators.
So I must say that although Fexl is an interesting pure-combinator lazy evaluation language, the jury is still out on its practical utility, in my humble opinion. I've used it in some projects as an embedded interpreter, but the application was quite constricted so you didn't encounter some of these larger issues.
That is why I emphasized this caveat earlier today: http://news.ycombinator.com/item?id=2717560 .
[+] [-] eru|14 years ago|reply
In your example I'd use foldl' (the prime is important) in Haskell for a strict sum.
[+] [-] andrewcooke|14 years ago|reply
also, you should explicitly say somewhere that it is eager (not lazy) (if it is).
also, i couldn't find any discussion of whether it is possible to mutate state (i assume not, but you don't say). related, a table of contents would be a big help - and obvious initial question is "how are data structures handled?" and you don't know where to find the answer when you at the top of the page.
(this is not meant to say that your language is bad - i am just trying to help you "sell" you language to people that read your page!)
[+] [-] lucian1900|14 years ago|reply
Btw, interesting language, this Flex of yours.
[+] [-] mahmud|14 years ago|reply
Outside of Java, an "expression language" doesn't make any sense to me. An expression, statement, binding, assignment, application, and abstraction are all constructs, or elements of programming languages. Most of them can be implemented using others, sure, but I expect all useful languages to be capable of all. So, my question is, what makes an expression language an expression language, to the exclusion of all other constructs? (IOW, why is that particular part being made into a defining characteristic of the language?)
[+] [-] fexl|14 years ago|reply
For example, the "flip" function for swapping the order of two functions is this:
But Fexl converts that into pure combinators like so: Actually it uses the higher level combinators L, R, I, etc. so that flip is defined as: But the higher-level are shorthand for forms that use S and C only.[+] [-] pwang|14 years ago|reply
http://en.wikipedia.org/wiki/Joy_(programming_language)
[+] [-] fexl|14 years ago|reply
In short, instead of Fexl I've started using a simple token-based language. Like Joy, my token-based language uses a stack. But my language also uses a global mutable key-value space, and it only supports keys and values which are strings (which may be interpreted as numbers).
I think my little language is easier to "execute" manually on a white-board in a way that's easy for non-programmers to follow along. I don't need a lot of arcane "stack flip-aroo" operators like Forth and Joy use.
So how do I do a sort you ask? I just jam a bunch of keys into the key-value space and then use "next" to iterate through them. The key-value space does the sorting for me.
What about strictly sequential lists you ask? I can just store a bunch of keys using a scheme like this:
By prefixing a single character which represents the number of digits, I get the proper numerical order when I iterate in ASCII character order.You know what my real goal is? I want to be able to give my non-programmer colleagues the ability to embed little snippets of computation here and there, making simple things simple, but also imposing no upper bound on the possibilities of what they might do.
[+] [-] Gotttzsche|14 years ago|reply
C x y = x
S x y z = (x z) (y z)
\I = (S C C)
so uh... that would evaluate to (\z (C z) (C z)), right? and then to (\z z z)? but then you got z twice. what does that even mean? applying z to z?
[+] [-] fexl|14 years ago|reply
You went off the rails because you replaced (C z) with z. That is not a valid equivalence. (C z) does not equal z. But (C z) applied to anything else does equal z. So in particular, (C z) (C z) equals z.
Here's how the reduction sequence goes:
If you think about it, that second C can be replace with anything and it still works: That C there simply "holds on" to its first argument, and then when it encounters any second argument, it ignores it completely and yields up the thing it was holding onto.[+] [-] eru|14 years ago|reply
Where _ stands for a value that doesn't matter.
And actually for any x we have S C x == I.
[+] [-] fexl|14 years ago|reply
Now let's use the abstraction algorithm to convert Q into combinators step by step, removing the variables:
OK that was kind of fun but all I did was demonstrate that Q can be defined in terms of S and C. That's actually somewhat irrelevant. The main point is to demonstrate that when you apply the Y combinator to an arbitrary function, you can in effect get recursion. So let's follow the reduction sequence: Now let's show how you can actually remove self-reference from a recursive function. Consider this recursive definition of the function which appends two lists: Now as it turns out, the "==" in Fexl is merely a short-hand which does this for you: That's actually a non-recursive definition of append there. Consider the body of the function by itself: There are no free variables in that. The inner call to "append" actually refers to the \append when encloses it. So you actually have a fully closed form function there which calls itself.You can look at it this way, separating that inner function out and calling it F:
So if we actually apply that function to two lists, it goes like this: And then it proceeds from there depending on what x is. It's amazing stuff, being able to defined a fully closed-form function which somehow manages to reach out and call itself. :)[+] [-] fexl|14 years ago|reply
[+] [-] gmartres|14 years ago|reply
[+] [-] fexl|14 years ago|reply
1. In Fexl, there is no distinction between data and function. All data structures such as lists, pairs, etc. are represented as functions.
2. Fexl has a small grammar, about as small as I think is feasible for expressing arbitrary functions. You could actually omit these rules:
But the resulting forms would be far more difficult to write and understand.3. Fexl has a very simple compilation and evaluation strategy, reducing everything to combinatorial forms. There are no "environments" or "closures" or "contexts" being whipped around at run-time. The resulting Fexl executable program is about 35K in size.
4. Unlike other functional programming languages, Fexl does not rely on "pattern matching" for branching on the different possible forms of a piece of data. Instead, it simply calls that piece of data as a function, passing in the appropriate handlers for the various cases. For example, using excessively verbose function names here:
5. Fexl doesn't really have a distinct concept for defining a name -- that's all handled normally by lambda calculus. However it does provide the syntactic shorthand "=". For example this function: Is equivalent to this function, which does not use the "=": I'm not exactly sure if that's oh-so-different from other programming languages, but I'll venture a guess that many of those other languages use a symbol table to store function definitions at run-time, while Fexl does not.6. Fexl never creates circular data structures in memory. Now because of lazy evaluation, you can create logically circular or infinite structures in Fexl, but these are always closed forms and never involve literal circularity in memory. Consequently it is possible to manage memory using reference counting -- and Fexl does that. Some may not like that, but it's simple and it gets the job done. The code even has a built-in assertion to ensure that all memory was properly reclaimed at the end of a run.
(I'm not certain that other languages create circular structures in memory, but I am certain that Fexl does not so I thought it worth mentioning.)