https://stackoverflow.com/questions/22592440
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian- Extensible Languages
Probably the most common examples of an extensible language are the Lisp family (Common Lisp, Scheme, Clojure) which have a syntactic macro system. This macro system allows you think of Lisp programs as ones that run at two points in time—once "during compilation" and again "at runtime". The "during compilation" phase takes certain parts of a Lisp program and expands them syntactically into more complex Lisp programs. The "at runtime" part runs like a regular language.
This phase distinction allows us to extend the control structures of a language because we can abstract over common idioms without executing anything. For instance, given that we have an if construct
(if true then else) ==> then
(if false then else) ==> else
we can build a cond structure where each body is evaluated only if its paired with a true value
(cond (test1 body1) (test2 body2) (test3 body3))
by transforming it into a set of nested if statements at runtime
(do (if test1 body1 null)
(if test2 body2 null)
(if test3 body3 null))
Note that this cannot be done (normally) at runtime because in normal Lisp evaluation we'd have to evaluate each of the bodies 1-3 before we could even determine whether they should be executed, making cond pretty useless.
In Haskell we get a lot of these advantages from laziness and purity. Since the compiler won't compute things until they're needed, we can be more judicious about when things are actually computed. Frequently this is talked about as "using data structures as control structures", but we'll see more of that in what follows.
- Laziness
The way to think of laziness is that whenever you have a computation, no matter how silly
f = 3 -- pending!
it "pends" until it is needed.
print f -- now we compute `f` and print it
This becomes especially important when you have complex data structures where parts can remain as pending even while others are computed. The linked list forms some great examples
-- [1,2,3,...] infinite list
nums = let go n = n : go (n+1)
in go 1
Again, remember that this computation, in a lazy setting, will not be run until it is actually needed. If we were to print it, we'd see the numbers stream out one by one. In a strict setting the interpreter would be forced to compute the entire list before printing a single one of them... and thus it would hang without computing a single number.
As another example, consider the function take which, given a number n, trims off the first n elements of a list. On finite lists its behavior is obvious.
> take 3 [1,2,3,4,5,6]
[1,2,3]
> take 5 [1,2,3]
[1,2,3]
But what's less obvious is that in a lazy setting it works perfectly on infinite structures as well
> take 5 nums
[1,2,3,4,5]
In this way, we've specified the nums computation more generally than people often must when using enumeration notation like [1..10]. In fact, we've simply asked for "all" of the numbers instead of conflating the definition of nums with some information about how to select which numbers we desire.
We leave that to the consumer. After all, the consumer is the one which knows how many numbers it needs. Again consider a statement like (take n) nums where take n, the consumer, knows it needs n numbers and thus nums, the producer, need not worry about it.
There's a great deal more to this concept, but to directly answer your final question about f
f n = 1 + f n
it's important to talk about what it means for a consumer to "demand" something in the same way that take "demands" a list of a certain size. Your function f indeed will never terminate and could never be "forcibly terminated" by a consumer except in one situation: the consumer could just completely ignore it.
consumer fun = 3
> consumer f
3
We can talk about this in terms of what kinds of things f produces which can be "partially demanded". In particular, all we can expect from f is the final result and thus we must wait on it to complete in order to "demand" anything from it at all. We need to be creative and think of a way to produce partial answers in order to be meaningfully stopped by a consumer.
One way is to encode numbers using Peano numbers. They look like this (in Haskell)
data Peano = Zero | Successor Peano
and we would write
0 ==> Zero
1 ==> Successor Zero
3 ==> Successor (Successor (Successor Zero))
We can adjust f to operate on Peano by replacing the (1+) with Successor as they mean about the same thing.
f n = Successor (f n)
And now if we write a consumer which is, say, a predicate about whether a Peano is greater than or equal to n
gte :: Peano -> Peano -> Bool
gte Zero Zero = True
gte Zero (Successor n) = True
gte (Successor n) (Successor m) = gte n m
we can talk about statements like
gte Zero n ==> True -- even without evaluating `n` at all
gte (Successor Zero) n ==> True -- while evaluating only one "layer" of `n`
and evaluate things like
> gte (Successor (Successor Zero)) (f 10)
True
where gte "forcibly halts" f after computing two layers, a sufficient demand in order for gte to proceed.
