It is theoretically possible to do a form of JIT compilation, where you compile the normal function (presuming function calls), but keep the source around and dynamically compile and link in branches of code for when the argument is a macro.
Basically, you'd have a jump table based on the argument. If it was a function, you'd jump to the function version. If it was a macro, you'd look it up in a hash table to see if it had been used before. If not, compile the function again and add the new one to the hash table.
Obviously, this wouldn't be as fast as a normal function call, since you'd have to do runtime checking of one of the arguments, but if you were careful the common case could be quite fast, with only the macro calls being slow and only new macro calls taking more than a small amount of time.
Of course, this is only one possible implementation. It is true that any language that supports macros could not be entirely statically compiled, but then again as far as I know any higher-order functional language requires runtime compilation as well. It partly depends on how you define "compilation."
It is true that any language that supports macros could not be entirely statically compiled
Actually, in a language with no side effects, I don't think there's anything keeping run time level code from being used at compile time, as long as there's already enough information to compile it. Who would ever know? ;) This means you have the most unique benefits of macros, that of being able to program them in the same language and environment as the rest of the program.
This is the basis behind Blade, an extensible statically compiled language I was making before I realized the lack of side effects made it really hard for me to write code for. :-p
> before I realized the lack of side effects made it really hard for me to write code for. :-p
So that's why you stopped working on Blade. I was curious! ^_^ Can you speak more about your realization that side effect-free programming is impractical? I've sometimes found myself tempted by pure FP, you see.
[PRO TIP: Click "link" (or "parent") on this comment, so you can view it (mostly) by itself rather than squashed against the right side of the page.]
For me, when I was writing my spider solitaire program, I had a couple of global variables, the-deck and the-piles, which represented the state of the game. the-deck was a list of randomly permuted cards, which were integers from 0 to 51 (or 0-25 with two suits, or 0-12 with one suit). the-piles was a list of piles, which were lists of cards (the zeroth element was the top of the pile), and the cards were of the form (list card revealed?), where "card" = 0-51 and "revealed" = t/nil. (Yes, a card is an integer in the deck, but a list of an integer and t/nil on the board. This does not need to be changed.)
To flip over the top card of the nth pile, I went:
(= (cadar the-piles.n) t)
To deal a card (face up) to top of each pile from the deck, I said:
(forlen i the-piles
(push (list pop.the-deck t) the-piles.i))
To move a chain of n cards from (the top of) one pile to another, I went:
(let (a b) (split the-piles.i n)
(= the-piles.i b
the-piles.j (join a the-piles.j)))
Also, I created a global variable called "prev-states", and every move the user performed would
(let (a b) pop.prev-states
(= the-deck a the-piles b))
. Now, what would you do in a "pure functional programming" language? If there were no assignment whatsoever, not even to global variables, I'd probably effectively implement global state by making every function take an extra argument representing global state, and shifting code around in other ways. If you could assign to global variables but all data structures were immutable (I think Clojure is like that, correct me if I'm wrong), then I'd have to keep rebinding the entire "the-piles" list when all I wanted to do was alter one or two piles. Revealing the top card of the nth pile would look something like this:
(= the-piles
(join (take (- n 1) the-piles)
(list:cons (list (car the-piles.n) t) (cdr the-piles.n))
(drop n the-piles)))
(Note that "push" and "pop" are legal because they just do global assignment; they don't alter any data structures). And then moving a chain of n cards from i to j would look like this:
(= the-piles
; ... oh god I have to know whether i>j
;(join (take (dec:min i j) the-piles)
; ... egad I may as well just say (if (< i j) ...
;(if (< i j)
; (join (take dec.i the-piles)
; (list:drop n the-piles.i)
; (cut the-piles i dec.j)
; (list:join (take n the-piles.i) the-piles.j)
; (drop j the-piles))
; (join ... egad the repetition is intolerable
; hmm, this'll work
(with (new-i (list:drop n the-piles.i)
new-j (list:join (take n the-piles.i) the-piles.j))
(if (< i j)
(join (take dec.i the-piles)
new-i
(cut the-piles i dec.j)
new-j
(drop j the-piles))
(join (take dec.j the-piles)
new-j
(cut the-piles j dec.i)
new-i
(drop i the-piles)))))
On the plus side, I would no longer need to use "deepcopy" when creating a backup of the game state.
(push (list the-deck the-piles) prev-states)
Which is pretty much the only benefit I'd get from outlawing modification of data structures, which I assume is what "pure functional programming" would mean. Don't even talk to me about how this would look if I had to simulate global variables...
Functional programming is a useful tactic in some cases. For example, I use a "chain-length" function, which might, say, take the list (7♥ 8♥ 9♣) and return 2, the number of revealed cards of consecutive rank of the same suit. I first thought about making it take "i" as an argument, referring to the ith pile in the-piles, but I made it take the list "xs" instead, and that allowed me to use it for other purposes: e.g. determining whether a move of n cards from pile i to j will create a longer single-suited chain. (Like, moving that 7♥ 8♥ chain onto a 9♥. I have a couple of AI-assistance procedures that look for moves satisfying conditions like that.) The expression is:
(is (+ n chain-length:the-piles.j)
(chain-length:join (take n the-piles.i) the-piles.j))
Had I written "chain-length" to refer just to the ith pile in the global "the-piles" variable, I'd... basically have to rewrite most of it. So factoring out things into individual functions (which, btw, is, I think, in the category of things called "functional programming", but isn't usually the same as making things side-effect-free) is frequently a good thing--it makes the program easier to write, to read, to understand, and to maintain.
But the goal, the reason you'd want to do it, is not because it's called "functional programming"--it's to make the program easier to write/read/understand/maintain. And if something called "functional programming" makes it harder to do those things, then I would advocate throwing it out. I think preventing all side effects, or all side effects except those on global variables, falls firmly into the latter category; I think my example demonstrates this.
; Move a chain of n cards from i to j.
(zap [let (taken leftovers) (split _.i n)
(copy _ i leftovers j (join taken _.j))]
the-piles)
; Reveal the top card of the nth pile.
(def copdate (orig . kvs)
(apply copy orig (mappend [list _.0 (_.1:orig _.0)] pair.kvs)))
(zap [copdate _ n [cons (list _.0 t) cdr._]] the-piles)
In principle I agree, disabling the programmer's ability to use mutation without reason is just frustrating. But I don't expect an example to help show this; most examples we could come up with would probably have easy-in-hindsight solutions like this. I think the point is that mutation gives us more easy ways to do things, so that we can quickly experiment and stuff.
I see you want to push the example to its limit a bit. ^_^ Well, I assume this hypothetical language would be stocked with utilities that made up for what its pureness missed out on. How believable are these?
That's definitely what I meant, and I was going to just say so, but whan I saw the ":)" I realized akkartik probably knew that and meant something like "that may not be 'oh god' complicated, but it's still not nearly as convenient as the mutating code." I don't know if that's a correct interpretation, but it made it more interesting to respond. ^_^
Yeah, I like the way you handle the-deck and the-piles. And I like this style of programming in general (i.e. a few global variables to keep state, functions corresponding to verbs in the problem space that manipulate the globals in an intuitive way). You've reminded me of how preventing all side effects could get awkward by ruling out this style of programming entirely.
To clarify, I'm not mostly interested in eliminating side effects because of some obsession with purity, but rather for performance sake. I've been pursuing so many lang design choices like fexprs/first-class macros that are supposed to really cripple performance, that I'm starting to worry my hobby implementations aren't even going to run. I'd heard that Haskell and Clojure get a big performance boost from enforced immutability/no side effects because it guarantees that most operations can safely be run concurrently, so I've just considered it an option.
I'm a real novice when it comes to optimization, and I'm certainly interested in techniques that could help me get decent performance without having to sacrifice mutability. TCO, strategic memoization, compiler hints? Any tips on this front could be really useful to me.
Aww, you know I can't resist talking about my hobby horses. XD
Blade is written in Groovy right now, and to make partial evaluation possible, everything is done in continuation-passing style. Partial calculations' continuations are held in stasis until the definitions they're waiting for become available. I guess it's related to cooperative multithreading and single-assignment variables, but I'm kinda playing it by ear.
Back when my work on Blade was petering off, the main reason was that Groovy's syntax wasn't very friendly for continuation-passing style. I really missed macros, and I wasn't in the mood for writing a complicated Groovy AST transformation. I wanted to just port it to Arc or something, but I had trouble writing Arc code itself without getting hung up in all the abstraction leaks (particularly unhygienic macros) and absent features (particularly OO-style type-based dispatch and weak references).
Meanwhile, thanks to ranting about Blade here, I realized it wouldn't be a good REPL language. Single-assignment has gotta paint people into corners at a REPL, and the alternative would be to compile the whole application over and over, using some meta-runtime to orchestrate the compiles. But what runtime?
Also, I began to suspect Bllade's design itself would result in something ugly to use and possibly even unusable. A declaration's behavior would depend on definitions, and a definition's value would be what the declararions said it was, and naturally there'd be deadlocks. The deadlocks were easy to avoid in toy examples, but I didn't know what limitations and gotchas Blade would develop once it matured. (I still wonder about that.)
So a plan fell into place: I could pursue a language that had similar high hopes for extensibility as Blade, but in a REPL-friendly form. That language's evaluation model would be much more familiar to me, and it would be closer to any of the languages I might choose to implement it in, so I'd probably be able to implement it faster and more confidently. Then I could use the resulting language--and the lessons I learned from it--to experiment with different variations on CPS and finish Blade.
So I started working on that language, and I called it Penknife. ^^
Altogether, I don't think this was based on any bad experience with pure functional programming. It was more about my expectation of those bad experiences, together with the frustration of writing CPS code in longhand Groovy.
> Meanwhile, thanks to ranting about Blade here, I realized it wouldn't be a good REPL language. Single-assignment has gotta paint people into corners at a REPL,
> So a plan fell into place: I could pursue a language that had similar high hopes for extensibility as Blade, but in a REPL-friendly form.
So the REPL was a large part of it. I've heard too that single-assignment is problematic for REPLs, but I don't quite understand why. Can't you just use let everywhere you'd use = and def ordinarily?
; Scribbling at the REPL
arc> (= x 5)
5
arc> (def add1 (n) (+ n 1))
#<procedure: add1>
arc> (add1 x)
6
; Single-assignment version
arc> (let x 5)
nil
arc> (let add1 [+ _ 1])
nil
arc> (let x 5
(let add1 [+ _ 1]
(add1 x)))
6
REPLs should provide a convenient way to grab commands from the history anyway, so you can just keep building on your previous let. It is more cumbersome, but you also avoid some of the nasty surprises that come after you've accumulated a complex state in your REPL.
Could this style of REPL'ing address the problems posed to REPLs by single-assignment, or are there larger problems I'm ignoring?
Update: In the particular REPL example I've shown, there's no need for the style transformation since nothing gets redefined. Hopefully you can still gather what I mean from it! ^_^
Can't you just use let everywhere you'd use = and def ordinarily?
Well, single-assignment can have variables that are introduced without values and then assigned to later. It's a bit of a relaxation of pure FP that (I think) doesn't sacrifice referential transparency. Hmm... actually, a lambda that assigns to a binding outside itself is not referentially transparent, so oh well. :-p
In any case, Blade isn't directly supposed to be a single-assignment or pure sort of language. I just want to view the space of Blade declarations as a completely orderless set, letting the compilation of each one run in parallel semantically, and I still want it to have an intuitive kind of determinism. Inasmuch as I can orderlessly orchestrate side effects in ways I find bearably intuitive, I'll probably add side effects to Blade.
Blade side effects would also be limited by the fact that I want to build up to an IDE that rewinds the compile when you edit. In fact, I'm almost certain my current plan won't work well with that. I expect custom declaration syntaxes to be supported by core-syntax declarations that happen to branch based on the declarations they find by reading the project tree, but then editing any part of a file would invalidate the branching itself and cause recompilation of all the custom-syntax declarations in that file. Seems there'll need to be a more edit-resistant kind of branching. I already expect a bit of IDE cooperation with this--it doesn't have to be as hackish as diffing plain text--but that's where my ideas leave off.
...Actually, I've got a bit of an idea already. XD A declaration that observes a file's contents in order to branch can limit its observation to some method that doesn't rely on the contents of the individual declarations, and then each of the branches can observe just its own part of the file. The core syntax already works like this, essentially splitting the file based on appearances of "\n\n[".
Anyway, you've gotten me thinking and ranting. ^_^
---
Would this style of REPL'ing address the problems posed to it by single-assignment, or are there other problems I've ignored?
The kind of problem I expect to happen is that I'll define something once, I'll define something based on that, and then I'll realize the first thing had a bug, but I won't be able to redefine it as simply as I can in Arc. Once I do enter the correct version, I'll have to paste in all the things that depend on it too.
To draw a connection, it's similar to how when you want to redefine a macro in Arc, you have to re-enter all the code that used the macro in order for it to use the new one, whereas fexprs wouldn't have this problem.
