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)))
)
\sum == (\N long_le N 0 0; long_add N; sum; long_sub N 1)
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)
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)
)
)
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 .
In your example I'd use foldl' (the prime is important) in Haskell for a strict sum.
\chain = (\state
\state = (event1 state)
\state = (event2 state)
\state = (event3 state)
state)
\chain = (\state
event3;
event2;
event1;
state)
This certainly does not matter if you're just chaining three events together, but try linking that chain together 20000 times to give you 60000 events. Oh it works, but it's nasty with memory usage.
So maybe I can introduce something into Fexl, without sacrificing elegance, which forces some level of evaluation of the event applications.
I did try forcing at least a top-level evaluation of each event along the way, using a technique sort of like this:
\eval = (\state state I \_\_ I)
Then I did this bit of nastiness:
\chain = (\state
\state = (event1 state) eval state;
\state = (event2 state) eval state;
\state = (event3 state) eval state;
state)
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!)
On your second point, Fexl is definitely not eager. It is the laziest thing you'll ever see.
And no, you cannot mutate state in any way.
On the subject of "how are data structures handled", I do address that at the top in "RULE 1: Everything is a function." There I say that all data are represented as functions, and I do show a little link to some exposition below.
Thanks for the help on "selling" the language -- until now, I haven't been concerned about that because it's all for my own purposes. But I take your point.
Btw, interesting language, this Flex of yours.
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?
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
: S C anything z
= (C z) (anything z)
= z
Where _ stands for a value that doesn't matter.
And actually for any x we have S C x == I.
Often when I develop a Fexl function I actually use "_" as a placeholder for "something I haven't implemented yet". So if I'm doing something with a list, I might say:
list
_
\head\tail _
For example I used this approach to implement an associative key-value map structure which uses nested lists, where a list at level N branches on the Nth character of the key, so it's a radix-style algorithm but without splitting the keys into pieces:
# Helper function.
\map_put == (\map\pos\key\val
map
(item (pair key (pair val end)) map)
\head\tail
head \top_key\top_node
# Do a three-way comparison of key char at pos
# with the top key char at that pos.
long_compare (string_at key pos) (string_at top_key pos)
# key char is less than top key char
(item (pair key (pair val end)) map)
# key char equals top key char
(
top_node \top_val\top_map
\new_head =
(
string_compare key top_key
(pair key (pair val
(map_put top_map (long_add pos 1) top_key top_val)))
(pair key (pair val top_map))
(pair top_key (pair top_val
(map_put top_map (long_add pos 1) key val)))
)
item new_head tail
)
# key char is greater than top key char
(item head (map_put tail pos key val))
)
# The actual function (map_put key val). This just
# calls the helper function with position 0 to start.
# I should probably re-order the helper function so
# pos is the last argument, then I can define this
# function simply as \map_put = (map_put 0).
\map_put = (\map\key\val map_put map 0 key val) Y F = F (Y F)
Y = S Q Q
\Q = (\x\y x (y y))
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))
: 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)
\append == (\x\y x y \h\t cons h; append t y)
\append = (Y \append \x\y x y \h\t cons h; append t y)
(Y \append \x\y x y \h\t cons h; append t y)
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)
: 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
\L = (\x\y\z (x z) y) # send z to left side only
\R = (\x\y\z x (y z)) # send z to right side only
Now let's abstract the Q definition using L and R in addition to S and C where possible:
\Q = (\x\y x (y y))
\Q = (\x R x (\y y y))
\Q = (\x R x (S I I))
\Q = (L (\x R x) (S I I))
\Q = (L R (S I I))
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
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
\square = (\x mul x x)
print (square 4)
(\square print (square 4)) (\x mul x x)
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.)
(define cons (lambda (car cdr) (lambda (z) (z 'pair car cdr))))
(define car (lambda (pair) (pair (lambda (type car cdr) car)))) ; we don't actually check type correctness in this simple example
(define cdr (lambda (pair) (pair (lambda (type car cdr) cdr))))
(define type-of (lambda (x) (x (lambda (type . rest) type))))
(define pair? (lambda (x) (eqv? 'pair (type-of x))))
Symbols in turn can be lifted out to be functions, whose type "symbol" is some particular function, say identity: here we need to have an atomic operation to define whether two functions are realised using the same closure, which is the usual meaning of eqv?.
While Scheme has mutable structures (e.g., set-car!) and circular structures, this alternate language would not.
Note that the Haskell 98 standard does not require implementations to let circular structures be defined, ghc does allow them (e.g., ones = 1:ones is a circular structure in ghc, but Haskell 98 would allow a Haskell to implement it as an infinite list).
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?)
For example, the "flip" function for swapping the order of two functions is this:
\flip = (\x\y y x)
\flip = (S (C (S I)) C)
\flip = (L I)
http://en.wikipedia.org/wiki/Expression_Language
http://docs.jboss.org/seam/latest/reference/en-US/html/elenh...
http://java.sun.com/products/jsp/reference/techart/unifiedEL...
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:
item/a1 ... item/a9
item/b10 ... item/b99
item/c100 ... item/c999
item/d1000 ... item/d9999
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.