Joy, purely functional?
e1_t — 2001-12-07 17:39:55
I've only discovered Joy recently. It's an interesting language.
I was wondering how are claims that Joy is purely functional
justified? I can't see how Joy is any more pure than StandardML for
example. True, StandardML does support assignments (through
references) but even without them it's still not a pure functional
language as it still supports side-effects.
In a pure functional language if a function, given certain arguments,
returns some result than that function will return that result every
time those particular arguments are passed to the function again.
That is not the case with Joy's I/O functions for example. 'get'
takes no parameters from the stack and out of nowhere it creates a
value and pushes it on the stack.
Now I'm not sure if I'm missing something here but this doesn't work
in pure functional languages.
Ivan
Reuben Thomas — 2001-12-07 17:43:09
> I was wondering how are claims that Joy is purely functional
> justified?
You're right, really.
John Cowan — 2001-12-07 18:43:26
e1_t wrote:
> That is not the case with Joy's I/O functions for example. 'get'
> takes no parameters from the stack and out of nowhere it creates a
> value and pushes it on the stack.
> Now I'm not sure if I'm missing something here but this doesn't work
> in pure functional languages.
Get takes an additional hidden argument which is the stream of
things that will ever be returned by it. You can say that the
whole local filesystem is an implicit argument.
--
Not to perambulate || John Cowan <
jcowan@...>
the corridors ||
http://www.reutershealth.com
during the hours of repose ||
http://www.ccil.org/~cowan
in the boots of ascension. \\ Sign in Austrian ski-resort hotel
Billy Tanksley — 2001-12-07 20:34:49
From: e1_t [mailto:
e1_t@...]
>I've only discovered Joy recently. It's an interesting language.
>I was wondering how are claims that Joy is purely functional
>justified?
I don't think we can accurately say that. :-) I think it would be better
to say that Joy is exploring the nature of pure functionality within a
concatenative framework.
Note that some people would deny that Joy is a functional language because
it isn't based on the lambda calculus (yes, I saw a definition which
included that); others would deny that Joy is a computer language because it
has very little syntax (Forth got kicked out of a huge study for that
reason). So I think it's worthwhile to examine the boundaries of
'functional'.
>I can't see how Joy is any more pure than StandardML for
>example. True, StandardML does support assignments (through
>references) but even without them it's still not a pure functional
>language as it still supports side-effects.
Supporting side-effects isn't the counterindication of functionality,
though; it's simply the MANNER in which most existing languages fail to be
functional. The true counterindication is that the rewriting rules of the
language don't apply in the presence of certain words. One interesting
thing about Joy is that all of its rewriting rules apply to all of its
words, even the ones with side effects. This seems to suggest that Joy is a
very purely functional language; it's impressive that it's also very purely
imperative and procedural.
>In a pure functional language if a function, given certain arguments,
>returns some result than that function will return that result every
>time those particular arguments are passed to the function again.
True. That's 'referential transparency', and it guarantees that 'f(x)' is
constant within the scope of x. Unfortunately, the entire rule is nonsense
in a concatenative language; even if we try to talk about 'x f' (which is a
trivial subset of the ways f can be applied to x), we don't get very far
without defining a lot more about x and f. Essentially, this rule is NOT a
rewriting rule in Joy, so the fact that Joy fails to preserve it can't say
anything about whether Joy is a functional language.
>That is not the case with Joy's I/O functions for example. 'get'
>takes no parameters from the stack and out of nowhere it creates a
>value and pushes it on the stack.
>Now I'm not sure if I'm missing something here but this doesn't work
>in pure functional languages.
Again, I don't think of Joy as a purely functional language; like you, I
have a bias against side-effects, because all my training I've been told
that they make it impossible to be function. More and more, though, I'm
suspecting that I've been told wrong.
>Ivan
-Billy
e1_t — 2001-12-07 22:54:51
>
> Get takes an additional hidden argument which is the stream of
>
> things that will ever be returned by it. You can say that the
> whole local filesystem is an implicit argument.
>
That reasoning could also be used for impure functional languages and
in fact imperative languages as well.
What happens if you write a function that uses 'get'? Does that
function also take a hidden argument (afterall it does cause a side-
effect)? How does the compiler/interpreter know which function takes
hidden arguments and which one doesn't?
The question of whether the compiler needs to know that is in fact
relevant - functional languages are viewed as better then imperative
languages simply because they can be implemented to utilize
equational reasoning (which can ultimatly be used to optimize an
abstract and inefficient program that is easily readable by a human,
i.e. a math formula, into an efficient form that may be harder to
comprehend) and because they are better suited to parallel
programming (the order of evaluation of pure, side-effect free
functions is irrelevant therefore they can be executed in parallel).
One of my current projects is Metafor, a functional language based on
Forth that can be implemented as an extension to Forth. I was
surprised when I came accross Joy as the syntax is very similar. I'm
still designing Metafor and haven't even started implementing it yet
simply because I'm still evaluating the potential flaws and one of
the biggest is the way side-effects are handled in the current
design. In fact I was hoping someone would respond the way you did
because my reasoning behind hiding side-effects in Metafor is similar
(although goes into more detail).
It is based around a concept I call chaotic functions and introducing
the concept of time expressed with infinite precision. Every chaotic
function at the time of evaluation takes the current point in time (a
hidden argument or a dummy argument) as one of it's arguments (kind
of like defining state as a function of time). Only the atomic
chaotic functions (such as 'get') need to be defined as chaotic. Any
function that uses the output of a chaotic function in the
computation of it's own result automatically becomes chaotic. A
function that calls a chaotic function but doesn't use it's output in
the computation of it's own output is a mutator (it changes the world
but doesn't affect the function that called it).
Defining functions that cause side-effects as time-bound makes sense
since side-effects are sequential. Also state of a variable in
imperative languages can only change with time so it makes sense that
state is expressed as a function of time in a functional language.
I was wondering if anyone has any criticisms of this approach? It
resembles embedding an imperative language within a functional one
but from what I can see so far I don't see how this could affect
equational reasoning. The approach might be missing some additional
rules though.
I've written an incomplete paper on this that describes how this
works in more detail if anyone is interested.
Ivan
Billy Tanksley — 2001-12-07 23:52:00
From: e1_t [mailto:
e1_t@...]
>What happens if you write a function that uses 'get'? Does that
>function also take a hidden argument (afterall it does cause a side-
>effect)? How does the compiler/interpreter know which function takes
>hidden arguments and which one doesn't?
It seems pretty clear that if you call a function which affects state, you
also affect state.
>The question of whether the compiler needs to know that is in fact
>relevant - functional languages are viewed as better then imperative
>languages simply
You give two seperate reasons; let me look at them closely.
>because they can be implemented to utilize
>equational reasoning (which can ultimatly be used to optimize an
>abstract and inefficient program that is easily readable by a human,
>i.e. a math formula, into an efficient form that may be harder to
>comprehend)
This is very important, and in fact fundamental to the distinction between
functional and non-functional languages. The important part isn't that it's
_possible_ to transform from readable-but-inefficient to
efficient-but-unreadable; the point is that those transformations can be
done according to text-based rules rather than semantic analysis. These
rules are called the "rewriting rules" of the language.
One of the fundamental rewriting rules of lambda-based languages is
"typographically identical expressions produce identical results." This
rule is not present in concatenative languages like Joy and Forth; but this
rule is the basis for the prohibition against changing state. I question,
therefore, whether the prohibition against changing state applies to
concatenative languages.
>and because they are better suited to parallel
>programming (the order of evaluation of pure, side-effect free
>functions is irrelevant therefore they can be executed in parallel).
Here's a problem. By the nature of a stack-based language, the order of
execution is given by the programmer. In order to change it, you have to
analyse the program exhaustively.
I could say, based on this, that applicative languages are a better choice
for this sort of analysis, because the order of evaluation of the arguments
to a function isn't specified by the programmer; therefore, the parallel
compiler can freely reorder and split. Unfortunately, such parallelism is
uniformly short-lived, and results in passing a lot of data back and forth
between processors; usually a bad thing. In practice, nobody's managed to
produce a usable parallelizer based on this, in spite of many decades of
effort, much money, and exclusive focus on applicative languages (which seem
to be, as I've mentioned, the best hope).
Why do you think concatenative languages, which look less parallel, will be
better for this than applicative languages?
I think the only solution is to make it easy for programmers to build
parallelism into their programs. Provide synchonization and APL-style array
operations.
>One of my current projects is Metafor, a functional language based on
>Forth that can be implemented as an extension to Forth.
Facinating! I've heard about Metafor here, but I wasn't able to find any
info source. Could you discuss it a bit?
>It is based around a concept I call chaotic functions and introducing
>the concept of time expressed with infinite precision. Every chaotic
This has been studied before. One of the more interesting ways of looking
at it introduces it by dividing time discretely, rather than continuously;
you can access the result of past calls as part of the definition of the
function, thereby allowing you to define recursive functions mathematically.
>I was wondering if anyone has any criticisms of this approach? It
>resembles embedding an imperative language within a functional one
>but from what I can see so far I don't see how this could affect
>equational reasoning. The approach might be missing some additional
>rules though.
Well, the worst problem is that it doesn't affect equational reasoning at
all; it's an analytical principle and not a textual one. Textually,
concatenative language already are impossible to reorder; analytically,
they're equivalent to applicative languages.
>I've written an incomplete paper on this that describes how this
>works in more detail if anyone is interested.
I'm always interested.
>Ivan
-Billy
e1_t — 2001-12-08 01:07:42
>
> >I can't see how Joy is any more pure than StandardML for
> >example. True, StandardML does support assignments (through
> >references) but even without them it's still not a pure functional
> >language as it still supports side-effects.
>
> Supporting side-effects isn't the counterindication of
functionality,
> though; it's simply the MANNER in which most existing languages
fail to be
True - a functional language can have side-effects.
> functional. The true counterindication is that the rewriting rules
of the
> language don't apply in the presence of certain words. One
interesting
> thing about Joy is that all of its rewriting rules apply to all of
its
> words, even the ones with side effects. This seems to suggest that
Joy is a
> very purely functional language; it's impressive that it's also
very purely
> imperative and procedural.
I'm going to have to read more about Joy.
>
> >In a pure functional language if a function, given certain
arguments,
> >returns some result than that function will return that result
every
> >time those particular arguments are passed to the function again.
>
> True. That's 'referential transparency', and it guarantees that 'f
(x)' is
> constant within the scope of x. Unfortunately, the entire rule is
nonsense
> in a concatenative language; even if we try to talk about 'x f'
(which is a
> trivial subset of the ways f can be applied to x), we don't get
very far
> without defining a lot more about x and f. Essentially, this rule
is NOT a
> rewriting rule in Joy, so the fact that Joy fails to preserve it
can't say
> anything about whether Joy is a functional language.
>
I never really thought about it that way.
But that wouldn't hold for a lazy concatenative language. A lazy
functional language has to be side-effect free and I think that still
holds even for concatenative languages.
On the other hand a program written in a lazy concatenative language
would compile into an abstract syntax tree that resembles an
applicative language.
> >That is not the case with Joy's I/O functions for example. 'get'
> >takes no parameters from the stack and out of nowhere it creates a
> >value and pushes it on the stack.
> >Now I'm not sure if I'm missing something here but this doesn't
work
> >in pure functional languages.
>
> Again, I don't think of Joy as a purely functional language; like
you, I
> have a bias against side-effects, because all my training I've been
told
> that they make it impossible to be function. More and more,
though, I'm
> suspecting that I've been told wrong.
>
Well it depends on whether the notion of a function is really
necessary. For many problems it isn't since they're not much harder
to solve in imperative languages. This is especially true for Forth.
Forth is not a functional language but many of the techniques used in
writing programs in functional languages also apply to writing
programs in Forth.
Very good response by the way - it has given me a lot to think about.
Ivan
Reuben Thomas — 2001-12-08 18:35:42
> What happens if you write a function that uses 'get'? Does that
> function also take a hidden argument (afterall it does cause a side-
> effect)? How does the compiler/interpreter know which function takes
> hidden arguments and which one doesn't?
In Haskell, the use of the IO monad makes this explicit in the type
system: the return type of any function that does IO is "contaminated"
with the IO monad.
--
http://sc3d.org/rrt/ | egrep, n. a bird that debugs bison
Brian C. Robinson — 2001-12-08 20:37:20
Billy Tanksley made a strange utterance something like this:
>others would deny that Joy is a computer language because it
>has very little syntax (Forth got kicked out of a huge study for that
>reason).
Not a computer language? That doesn't make any sense. It seems to run on
my computer. What is the justification for that claim?
--
"The best programmers that I have ever met have an amazing ability to make
nasty sh*t disappear. *Poof*" Gareth Reeves --
reevesg@...
e1_t — 2001-12-08 21:45:32
--- In concatenative@y..., Billy Tanksley <wtanksley@b...> wrote:
>
> You give two seperate reasons; let me look at them closely.
>
> >because they can be implemented to utilize
> >equational reasoning (which can ultimatly be used to optimize an
> >abstract and inefficient program that is easily readable by a
human,
> >i.e. a math formula, into an efficient form that may be harder to
> >comprehend)
>
> This is very important, and in fact fundamental to the distinction
between
> functional and non-functional languages. The important part isn't
that it's
> _possible_ to transform from readable-but-inefficient to
> efficient-but-unreadable; the point is that those transformations
can be
> done according to text-based rules rather than semantic analysis.
These
I agree. I should have clarified that better but that's what I meant.
Although the only thing I forgot to say was really that it's not
impossible to implement an imperative language that transforms
readable and inefficient programs into more efficient forms but that
implementing a functional language that does that is a LOT easier.
My initial point was related to claims about Joy being a pure
functional language. Since Joy doesn't make a distinction between
functions with side-effects and pure functions the reasoning that Joy
is a pure functional language because of hidden arguments being
passed to functions with side-effects implies that impure functional
languages are in fact pure and that even most imperative languages
are 1st-order pure functional languages - but they're not. That was
the main reason why I stated the main differences between imperative
and functional languages.
> rules are called the "rewriting rules" of the language.
>
> One of the fundamental rewriting rules of lambda-based languages is
> "typographically identical expressions produce identical results."
This
> rule is not present in concatenative languages like Joy and Forth;
but this
> rule is the basis for the prohibition against changing state. I
question,
> therefore, whether the prohibition against changing state applies to
> concatenative languages.
>
That's a very good point. In fact I never thought about it in that
way.
Ok. Unless I'm missing something here, that means writing a lazy
concatenative system doesn't make much sense since laziness is
something that aids in equational reasoning of lambda-based languages
which are clearly different from concatenative ones.
In the language I'm designing I didn't really pay attention to
whether it's concatenative or not - in fact until I found out about
Joy I wasn't aware of the properties of concatenative systems. My
goal was simply to extend Forth (in my personal view the ultimate
meta-language and arguably the most elegant imperative language ever
designed) into a functional language that could utilize equational
reasoning of lambda-based systems which as it turns out isn't
necessary. So the only thing Forth is really missing in order to
become an impure functional language are higher order functions.
On the other hand equational reasoning of lambda-based systems is
closer to how humans think or better said how we're tought to think
in schools. Wouldn't that mean that most problems devised by most
people are in fact better suited to lambda-based systems?
Concatenative systems do indeed resemble imperative ones in many ways
and formulating problems for concatenative systems is consequently
similar to designing problems for imperative systems (especially
Forth) so again the programmer has to simplify or reformulate many
problems.
> >and because they are better suited to parallel
> >programming (the order of evaluation of pure, side-effect free
> >functions is irrelevant therefore they can be executed in
parallel).
>
> Here's a problem. By the nature of a stack-based language, the
order of
> execution is given by the programmer. In order to change it, you
have to
> analyse the program exhaustively.
>
I don't see stack as a problem.
Also analysis of all Forth-like languages is relatively simple. I
don't see that as a problem either if it's done at compile time.
> I could say, based on this, that applicative languages are a better
choice
> for this sort of analysis, because the order of evaluation of the
arguments
> to a function isn't specified by the programmer; therefore, the
parallel
I think that explains why side-effects in a concatenative language
don't conflict with the rewriting rules of the language in a simpler
way. Simply because programs are in fact sequential.
> compiler can freely reorder and split. Unfortunately, such
parallelism is
> uniformly short-lived, and results in passing a lot of data back
and forth
> between processors; usually a bad thing. In practice, nobody's
managed to
> produce a usable parallelizer based on this, in spite of many
decades of
> effort, much money, and exclusive focus on applicative languages
(which seem
> to be, as I've mentioned, the best hope).
>
> Why do you think concatenative languages, which look less parallel,
will be
> better for this than applicative languages?
>
I never said they were.
Again as I said my goal was extending Forth into a functional
language that utilizes equational reasoning of lambda-based systems.
This may still be worth exploring. Forth is a lot like an abstract
assembly language. If it was extended into a very simple lazy
functional language that is easy to analyze and optimize then
extending Forth further into a highly abstract lazy lambda-based
language would become relatively easy.
> I think the only solution is to make it easy for programmers to
build
> parallelism into their programs. Provide synchonization and APL-
style array
> operations.
>
Ultimatly if you want to build an efficient system you can't rely on
the capabilities of the language you're using (or better said
implementation of it) to optimize that system - you have to do it
yourself by using the right data structures and design. The same
doesn't only hold for writing speed/memory efficient programs but
also programs that exploit parallelism.
> >One of my current projects is Metafor, a functional language based
on
> >Forth that can be implemented as an extension to Forth.
>
> Facinating! I've heard about Metafor here, but I wasn't able to
find any
You must have heard of another system with the same name since not
many people know about my project (or any of my other projects for
that matter). That means I'm going to have to find a new name for it.
A while ago I actually looked on the net for languages or programs
already named Metafor and I didn't find any so I decided to name it
Metafor. Yesterday I looked again and it seems there's already a
theorem prover called metafor.
> info source. Could you discuss it a bit?
>
Well as I already said my goal was to extend Forth into a simple
functional language. Since I wasn't aware of the properties of
concatenative languages I simply assumed the only form of reasoning
that can be applied to functional languages was equational reasoning
found in lambda-based systems - I was aware there were other systems
too but they're all related so I didn't think it matters.
Initially I wanted to change Forth into a simple (but easily
readable) functional language that's just as flexible as Forth.
The very first design was a system with a few layers and the last
layer was fairly complex and programs written in it resembled
algebraic proofs. I liked that system but I couldn't find a way to
make it flexible. I still want to implement something like this
eventually but on top of a simpler functional language. Actually I
found a theorem prover whose theorems look a bit like programs
written in this language. The theorem prover is called OTTER.
I came up with a few other designs and in the end I decided that
extending Forth into a Forth-like functional language in such a way
that doesn't destroy Forth itself was a better idea.
The last design of Metafor (well... it doesn't have a name anymore
but for now I'll keep refering to it as Metafor) is very similar to a
lazy version of Joy.
Soon after I came up with that design I found out about Joy.
> >It is based around a concept I call chaotic functions and
introducing
> >the concept of time expressed with infinite precision. Every
chaotic
>
> This has been studied before. One of the more interesting ways of
looking
Wouldn't be the first time I reinvented the wheel. I was suspecting
it has been done before but I couldn't find any info on the net on
anything similar.
> at it introduces it by dividing time discretely, rather than
continuously;
> you can access the result of past calls as part of the definition
of the
> function, thereby allowing you to define recursive functions
mathematically.
>
Are there any papers on this available on the net?
> >I was wondering if anyone has any criticisms of this approach? It
> >resembles embedding an imperative language within a functional one
> >but from what I can see so far I don't see how this could affect
> >equational reasoning. The approach might be missing some
additional
> >rules though.
>
> Well, the worst problem is that it doesn't affect equational
reasoning at
> all; it's an analytical principle and not a textual one. Textually,
> concatenative language already are impossible to reorder;
analytically,
> they're equivalent to applicative languages.
>
What do you mean by textual principle?
Ivan
Louis Madon — 2001-12-09 07:56:09
On Saturday, December 8, 2001, at 08:54 AM, e1_t wrote:
> ...
> It is based around a concept I call chaotic functions and introducing
> the concept of time expressed with infinite precision. Every chaotic
> function at the time of evaluation takes the current point in time (a
> hidden argument or a dummy argument) as one of it's arguments (kind
> of like defining state as a function of time). Only the atomic
> chaotic functions (such as 'get') need to be defined as chaotic. Any
> function that uses the output of a chaotic function in the
> computation of it's own result automatically becomes chaotic. A
> function that calls a chaotic function but doesn't use it's output in
> the computation of it's own output is a mutator (it changes the world
> but doesn't affect the function that called it).
> Defining functions that cause side-effects as time-bound makes sense
> since side-effects are sequential. Also state of a variable in
> imperative languages can only change with time so it makes sense that
> state is expressed as a function of time in a functional language.
This sounds reasonable, using the concept of time feels quite intuitive
to me.
Regarding your distinction between chaotic functions and mutators - is
it really neccesary? (sorry, I'm a minimalist :-)
Assuming time is treated as a dummy argument (ie. not hidden) then what
happens when you DUP it - can you call a chaotic function multiple times
with the same time value and be guaranteed the same result?
If time is an implicit argument, then the compiler needs to do some kind
of pre-compilation analysis (to first convert the program into a purely
functional form in which the time argument is explicit): I like this
approach in principle since you can control how the time argument gets
manipulated (eg. prevent it from being DUPed).
> I was wondering if anyone has any criticisms of this approach?
> It
> resembles embedding an imperative language within a functional one
> but from what I can see so far I don't see how this could affect
> equational reasoning. The approach might be missing some additional
> rules though.
I think that if your primary motivation is on doing advanced program
optimization (this is my main interest) there are two key things to
consider:
1- How to express sequentiality in purely functional programs so that
I/O can be embedded in them
2- How to delineate the scope of I/O _effects_ so that unnecessary
constraints are not imposed on the compiler: if the effects of two I/O
operations are independent, they can be re-ordered.
I think your proposal addresses (1) just fine, but AFAICT, does not
address (2). So for example, if I wanted to write a program that updated
a file 'foo' and another file 'baz' and the two updates are independent
(so do not have to occur in any particular order or could even be done
in parallel) then I don't want to artificially impose an order on those
updates by threading a time argument through them.
>
> I've written an incomplete paper on this that describes how this
> works in more detail if anyone is interested.
Yes, please add me to your "interested people" list.
Louis.
[Non-text portions of this message have been removed]
Louis Madon — 2001-12-09 08:16:22
On Sunday, December 9, 2001, at 04:35 AM, Reuben Thomas wrote:
> > What happens if you write a function that uses 'get'? Does that
> > function also take a hidden argument (afterall it does cause a side-
> > effect)? How does the compiler/interpreter know which function takes
> > hidden arguments and which one doesn't?
>
> In Haskell, the use of the IO monad makes this explicit in the type
> system: the return type of any function that does IO is "contaminated"
> with the IO monad.
I think a simpler solution is possible in Joy: since Joy programs
already have a well-defined order, it is unnecessary to introduce a new
abstraction like monads to express sequentiality. All that should be
needed is a trivial type system that works bottom-up on the program DAG
marking each definition as "pure" or "impure" depending on whether it
contains impure functions (starting with a set of primitive impure
functions like 'get' and 'put').
Armed with this information, a compiler could easily convert the
program into a purely functional form wherein the hidden world-state
argument is made explicit.
However, for this to work, Joy must drop its current support for
recursive definitions: I for one would be happy to see them go.
Louis.
[Non-text portions of this message have been removed]
Louis Madon — 2001-12-09 08:17:18
On Saturday, December 8, 2001, at 09:52 AM, Billy Tanksley wrote:
>
> One of the fundamental rewriting rules of lambda-based languages is
> "typographically identical expressions produce identical results." This
> rule is not present in concatenative languages like Joy and Forth; but
> this
> rule is the basis for the prohibition against changing state.
Apart from I/O functions like get and put, in what way is this
equivalence rule not present in Joy: can you give an example?
Louis.
[Non-text portions of this message have been removed]
e1_t — 2001-12-09 20:12:48
--- In concatenative@y..., Louis Madon <madonl@b...> wrote:
>
> Regarding your distinction between chaotic functions and mutators -
is
> it really neccesary? (sorry, I'm a minimalist :-)
>
Mutators are just a concept - the language itself doesn't need a
system for distinguishing between a function and a mutator. The
compiler can automatically determine if a function is a mutator.
The reason why I felt they are important is because a mutator is a
function that's essentially pure - it's output only depends on it's
input. Therefore the order of evaluation of mutators is still
irrelevant. The side-effects caused by mutators can be completely
separated from them.
> Assuming time is treated as a dummy argument (ie. not hidden) then
what
> happens when you DUP it - can you call a chaotic function multiple
times
> with the same time value and be guaranteed the same result?
>
Time as such is not a function. If it's not hidden it can be
implemented as a dummy type. A value of type time automatically and
constantly updates itself to reflect the current point in time. All
values of type time are in fact the same but the evaluation of
something like t dup = or t dup > always returns false. Similarly t
dup < always returns true. This is why I said that this approach is
similar to embedding an imperative language within a functional one.
Arguably such a language is still impure but equational reasoning
still works since the compiler can distinguish between functions that
return consistant values based on the arguments passed to them and
can therefore completely replace a sequence like 2.0 sqrt with the
actual square root of 2 if it knows that sqrt is a pure function. Of
course this only works if the compiler is capable of analysing
functions and for indirect threaded Forth systems that shouldn't be a
problem - all words can easily be analysed (with the exception of
those written in assembler but that's not really a problem).
I'm pretty sure Joy can be implemented in a similar way.
While many people think indirect threaded Forths are obsolete and
practically all optimizing implementations of Forth are subroutine
threaded I think this approach could lead to superior performance due
to global optimizations. Indirect threaded code can easily be
compiled into machine code.
> If time is an implicit argument, then the compiler needs to do some
kind
> of pre-compilation analysis (to first convert the program into a
purely
> functional form in which the time argument is explicit): I like
this
> approach in principle since you can control how the time argument
gets
> manipulated (eg. prevent it from being DUPed).
>
The conversion isn't necessary - the concept of time is simply there
to aid the compiler in seeing which functions are pure. Time
variables can be eliminated and discarded during parsing.
> I think that if your primary motivation is on doing advanced
program
> optimization (this is my main interest) there are two key things to
> consider:
>
> 1- How to express sequentiality in purely functional programs so
that
> I/O can be embedded in them
> 2- How to delineate the scope of I/O _effects_ so that unnecessary
> constraints are not imposed on the compiler: if the effects of two
I/O
> operations are independent, they can be re-ordered.
>
> I think your proposal addresses (1) just fine, but AFAICT, does not
> address (2). So for example, if I wanted to write a program that
updated
> a file 'foo' and another file 'baz' and the two updates are
independent
> (so do not have to occur in any particular order or could even be
done
> in parallel) then I don't want to artificially impose an order on
those
> updates by threading a time argument through them.
>
You're right - this doesn't address the 2nd problem at all. In fact I
didn't pay a lot of attention to the 2nd problem. I was more
concerned with code optimization then exploiting parallelism and I
was satisfied with the fact that pure functions can be executed in
parallel.
This could be solved by adding an additional declarator (or even
declarators... I'm not sure - I think one would be sufficient) for
atomic functions but that would increase the complexity of the
language and isn't very elegant either. Also it would probably only
be applicable to Forth (Joy's syntax would be ruined with such
construct).
Monads are a lot more elegant and address both issues but they're too
impractical for stack based languages and even more impractical for
typeless languages.
Another thing is that as far as parallel execution goes I'm not
completely sure whether addressing the 2nd problem would help much in
terms of performance. I'm not sure if dispatching independant chaotic
functions for execution accross multiple processors would be faster
than just having one processor dedicated to chaotic functions and
other processors executing pure functions. There are many factors
that need to be taken into account.
Ivan
Manfred von Thun — 2001-12-10 07:20:14
On Fri, 7 Dec 2001, John Cowan wrote:
> e1_t wrote:
>
> > That is not the case with Joy's I/O functions for example. 'get'
> > takes no parameters from the stack and out of nowhere it creates a
> > value and pushes it on the stack.
"out of nowhere" is actually a good phrase. The trick is to make
the "nowhere" explicit, see below. - Manfred
> > Now I'm not sure if I'm missing something here but this doesn't work
> > in pure functional languages.
>
> Get takes an additional hidden argument which is the stream of
> things that will ever be returned by it. You can say that the
> whole local filesystem is an implicit argument.
You are exactly right.
Over time my view on this matter has changed quite often,
ranging over
1. Joy is purely functional
(the first version did not have get and put)
2. Joy is almost purely functional, and most programs are pure.
(at that time I did not have "filnam" include)
3. Most Joy programs are purely functional, but one needs some
impurity, at least include, get and put.
So, restricted to the stack functions it is pure.
4. a) If a language is purely functional,
then it has a rewriting system for every concept
b) Joy does not have rewriting rules for file handling
Therefore
c) Joy is not purely functional
5. I now think that 4b is false, and Joy is pure after all
The tricky part is to design the rewriting rules for file handling.
Here are some ideas for get:
One has to make the currently open input file explicit.
Suppose it contains just three numerals, 44, 55, 66.
As a notation, write <44 55 66> for this file.
Suppose we execute the program: 11 22 + get get +
For the rewriting, place the file in front of the program.
Then the rewriting has to look like this:
1. <44 55 66> 11 22 + get get +
2. 11 <44 55 66> 22 + get get +
3. 11 22 <44 55 66> + get get +
4. 11 22 + <44 55 66> get get +
5. 33 <44 55 66> get get +
6. 44 <55 66> get +
7. 33 44 55 <66> +
8. 33 44 55 + <66>
9. 33 99 <66>
In other words, input files have this rewriting rule:
<a b c ..> get ==> a <b c ..> (lines 6 and 7)
and for X other than get,
<a b c ..> X ==> X <a b c ..> (other lines)
So, get behaves just like uncons.
Anything else commutes with an explicitly expressed input file.
If one uses the notation that in an output file the last thing
written to it is the first thing in the notation,
then put behaves like cons.
So, Joy programs denote unary functions from complex structure
comprising:
A stack
A (default) input file and a (default) output file
Other currently open files
A local file system
A symbol table (accessible through body)
Other useful things (other than files) one might want to add:
maybe another stack, or a queue, or a deque
maybe a dictionary or association table
maybe an assignable state ? (Heresy?)
...
Whatever operations there are for manipulating the other
parts of the structure, for each operation one will need
a rewriting rule to show that it does not destroy the functional
purity.
If this can be done in a unified manner, it seems that Joy will
NOT need an analogue of monads (Joynads?), each one specialised
for handling one part of the structure, and exotic methods for
combining monads to handle several parts ...
This has been on my mind for some time now, and one day I shall get
around to writing it up properly for the rewriting paper.
In the meantime I'll write up a short version for the
Further Frequenly Asked Questions. The question seems to get
raised periodically.
- Manfred
e1_t — 2001-12-10 15:12:23
--- In concatenative@y..., Louis Madon <madonl@b...> wrote:
>
> 1- How to express sequentiality in purely functional programs so
that
> I/O can be embedded in them
> 2- How to delineate the scope of I/O _effects_ so that unnecessary
> constraints are not imposed on the compiler: if the effects of two
I/O
> operations are independent, they can be re-ordered.
>
I reread what Billy Tanksley wrote. It seems I forgot all of what he
said and just went back to what I was saying before. Sorry.
1 actually doesn't need to be addressed in either Joy or Forth since
they're already sequential.
To do proper code optimizations making a distinction between pure and
impure functions isn't necessary - every function that can be
analyzed can already be reduced to a simpler form without any
additional abstractions.
This approach therefore only helps with lambda-based languages for
which there already exists a better solution - monads.
As far as concatenative languages go this could only help with
parallelism but as you mentioned it doesn't address the 2nd problem
at all.
Ivan
Billy Tanksley — 2001-12-10 17:11:04
From: Louis Madon [mailto:
madonl@...]
>On Saturday, December 8, 2001, at 09:52 AM, Billy Tanksley wrote:
>> One of the fundamental rewriting rules of lambda-based languages is
>> "typographically identical expressions produce identical
>> results." This
>> rule is not present in concatenative languages like Joy and
>> Forth; but this
>> rule is the basis for the prohibition against changing state.
>Apart from I/O functions like get and put, in what way is this
>equivalence rule not present in Joy: can you give an example?
Okay, in Joy "+" is a complete program. But the value of "+" isn't the same
everywhere it's used; it depends on something + has no control over, on
something which there's no typographical way of discovering.
>Louis.
-Billy
Billy Tanksley — 2001-12-10 18:33:56
From: Louis Madon [mailto:
madonl@...]
>I think a simpler solution is possible in Joy: since Joy programs
>already have a well-defined order, it is unnecessary to
>introduce a new
>abstraction like monads to express sequentiality.
I agree.
>All that should be
>needed is a trivial type system that works bottom-up on the
>program DAG
>marking each definition as "pure" or "impure" depending on whether it
>contains impure functions (starting with a set of primitive impure
>functions like 'get' and 'put').
That would certainly work.
I'd go a step further, were I interested in this: I'd make each type of
"impure" (i.e. sequence-dependant) operation its own thread, optimise them
seperately, then link them together and optimize them as a group.
Each file would form a seperate thread, as would the system dictionary and
the stack. ONLY words which affect that specific file would go in that
file's thread.
> However, for this to work, Joy must drop its current support for
>recursive definitions: I for one would be happy to see them go.
Why? That doesn't make sense to me.
>Louis.
-Billy
S. Alexander Jacobson — 2001-12-10 22:32:46
I think the correct answer is that you should be able to accumulate
optimization macro libraries. A Macro would be something that takes a
regular expression of functions and replaces them with another. e.g.
A regular expression would be something like: . foo . goo
This would match [1 foo 2 goo] as well as ["blah" foo "glah" goo].
Macro code would run and return a list which would replace whatever was
located at . foo . goo.
The macro implementation would run recursively until all reductions were
evaluated.
-Alex-
On Mon, 10 Dec 2001, e1_t wrote:
> --- In concatenative@y..., Louis Madon <madonl@b...> wrote:
> >
> > 1- How to express sequentiality in purely functional programs so
> that
> > I/O can be embedded in them
> > 2- How to delineate the scope of I/O _effects_ so that unnecessary
> > constraints are not imposed on the compiler: if the effects of two
> I/O
> > operations are independent, they can be re-ordered.
> >
>
> I reread what Billy Tanksley wrote. It seems I forgot all of what he
> said and just went back to what I was saying before. Sorry.
> 1 actually doesn't need to be addressed in either Joy or Forth since
> they're already sequential.
> To do proper code optimizations making a distinction between pure and
> impure functions isn't necessary - every function that can be
> analyzed can already be reduced to a simpler form without any
> additional abstractions.
> This approach therefore only helps with lambda-based languages for
> which there already exists a better solution - monads.
> As far as concatenative languages go this could only help with
> parallelism but as you mentioned it doesn't address the 2nd problem
> at all.
>
> Ivan
>
>
___________________________________________________________________
S. Alexander Jacobson i2x Media
1-917-783-0889 voice 1-212-697-1427 fax
Billy Tanksley — 2001-12-10 22:34:46
From: S. Alexander Jacobson [mailto:
shop2it@...]
>I think the correct answer is that you should be able to accumulate
>optimization macro libraries. A Macro would be something that takes a
>regular expression of functions and replaces them with another. e.g.
Regexps would only seldom work -- but that's the basic idea, yes.
>The macro implementation would run recursively until all
>reductions were evaluated.
Actually, it would have to be run heuristically -- there's no way to tell
what reduction to evaluate next, and no way to know when to stop. You have
to make educated guesses.
>-Alex-
-Billy
Ocie Mitchell — 2001-12-10 22:41:18
--- e1_t <
e1_t@...> wrote:
> --- In concatenative@y..., Louis Madon <madonl@b...>
> wrote:
> >
> > Regarding your distinction between chaotic
> functions and mutators -
> is
> > it really neccesary? (sorry, I'm a minimalist :-)
> >
>
> Mutators are just a concept - the language itself
> doesn't need a
> system for distinguishing between a function and a
> mutator. The
> compiler can automatically determine if a function
> is a mutator.
> The reason why I felt they are important is because
> a mutator is a
> function that's essentially pure - it's output only
> depends on it's
> input. Therefore the order of evaluation of mutators
> is still
> irrelevant. The side-effects caused by mutators can
> be completely
> separated from them.
I don't think this necessarily follows. If the
mutator alters the outside world, then changing the
order of execution of mutators changes the outcome.
Consider:
open_refrigerator
remove_beer
close_refrigerator
open_beer
drink_beer
Some reordering is possible, specifically
close_refrigerator and open_beer could be swapped, but
arbitrary reordering is not possible.
Ocie
__________________________________________________
Do You Yahoo!?
Send your FREE holiday greetings online!
http://greetings.yahoo.com
Billy Tanksley — 2001-12-10 22:49:36
From: Brian C. Robinson [mailto:
brian.c.robinson@...]
>Billy Tanksley made a strange utterance something like this:
>>others would deny that Joy is a computer language because it
>>has very little syntax (Forth got kicked out of a huge study for that
>>reason).
>Not a computer language? That doesn't make any sense. It
>seems to run on my computer. What is the justification for that
>claim?
There was none, really -- just what I said, that it didn't have any syntax
and was almost completely unlike any of the real computer languages the
study's organiser knew of.
She was right, of course; but her "real languages" were actually all
"applicative languages". She just needed to broaden her horizons a bit.
-Billy
Louis Madon — 2001-12-11 00:38:14
On Tuesday, December 11, 2001, at 03:11 AM, Billy Tanksley wrote:
> From: Louis Madon [mailto:madonl@...]
> >On Saturday, December 8, 2001, at 09:52 AM, Billy Tanksley wrote:
>
> >> One of the fundamental rewriting rules of lambda-based languages is
> >> "typographically identical expressions produce identical
> >> results." This
> >> rule is not present in concatenative languages like Joy and
> >> Forth; but this
> >> rule is the basis for the prohibition against changing state.
> >Apart from I/O functions like get and put, in what way is this
> >equivalence rule not present in Joy: can you give an example?
>
> Okay, in Joy "+" is a complete program. But the value of "+" isn't the
> same
> everywhere it's used; it depends on something + has no control over, on
> something which there's no typographical way of discovering.
>
Hmmm, I'm afraid I don't understand.
In fact, now that I think about it pure functional languages don't seem
to have this property, for example (in Haskell):
foo a b = let x = (+) in x a b
bar a b = let x = (*) in x a b
The expression "x a b" is typographically identical within both foo and
bar and yet it means two different things (addition in the first case,
multiplication in the second).
Maybe I've totally misunderstood your intended meaning ...
Louis.
[Non-text portions of this message have been removed]
Louis Madon — 2001-12-11 00:38:50
On Tuesday, December 11, 2001, at 04:33 AM, Billy Tanksley wrote:
>
> ...
> > However, for this to work, Joy must drop its current support for
> >recursive definitions: I for one would be happy to see them go.
>
> Why? That doesn't make sense to me.
Well if I have:
foo == ... bar ...
bar == ... foo ...
there is no longer any clearly defined topographical order for the type
inferencer to follow (its not a DAG anymore).
You could come up with a more complicated scheme to handle cycles but
since Joy can provide recursion without resorting to recursive
definitions, such definitions are redundant - I'd prefer to eliminate
them and so avoid the extra complexity.
Louis.
[Non-text portions of this message have been removed]
Billy Tanksley — 2001-12-11 00:58:06
From: Louis Madon [mailto:
madonl@...]
>On Tuesday, December 11, 2001, at 03:11 AM, Billy Tanksley wrote:
>> From: Louis Madon [mailto:madonl@...]
>> >On Saturday, December 8, 2001, at 09:52 AM, Billy Tanksley wrote:
>> >> One of the fundamental rewriting rules of lambda-based
>> >> languages is
>> >> "typographically identical expressions produce identical
>> >> results." This
>> >> rule is not present in concatenative languages like Joy and
>> >> Forth; but this
>> >> rule is the basis for the prohibition against changing state.
>> >Apart from I/O functions like get and put, in what way is this
>> >equivalence rule not present in Joy: can you give an example?
>> Okay, in Joy "+" is a complete program. But the value of
>> "+" isn't the same everywhere it's used; it depends on
>> something + has no control over, on something which there's
>> no typographical way of discovering.
>Hmmm, I'm afraid I don't understand.
>In fact, now that I think about it pure functional languages
>don't seem to have this property, for example (in Haskell):
>foo a b = let x = (+) in x a b
>bar a b = let x = (*) in x a b
>The expression "x a b" is typographically identical within
>both foo and bar and yet it means two different things (addition
>in the first case, multiplication in the second).
No problem -- my definition clearly mentioned scope (although I admit that
by the time I'd typed it a million times I left out the mention of scope,
and by Murphy's law that's the one you happened to quote). The two
definitions you give use completely seperate scopes, and so referential
transparency doesn't apply to them.
You shouldn't take my word for it if you doubt. Look up referential
transparency anywhere on the net. Some sloppy definitions will define it as
being a prerequisite of a functional language (it's not, unless your
language is applicative); all will explain that it means (at least) that two
identical expressions in the same scope mean the same thing.
>Maybe I've totally misunderstood your intended meaning ...
You seem to catch it well enough; you're just not reading the example I
gave. Take a look again.
We all know what + means in Joy; we've agreed not to use scopes to cover it
up (that's a bad habit). We also agree that it's a complete expression: a
valid program could be built containing only it. Yet it has no fixed value,
and some other textual occurance of + could result in a completely different
value (without meaning anything different).
In a functional C program, f(3) is an expression, and it means only one
thing; next time the compiler sees it, it can just replace the value already
computed for f(3). In C, "+" is NOT an expression, so nothing can be said
about it, and f() isn't a valid expression, so nothing can be said of it.
But in Joy, "+" is a perfectly valid expression, and yet nothing can be said
about its final value -- it might result in a constant, or it might not.
>Louis.
-Billy
Billy Tanksley — 2001-12-11 01:02:40
From: Louis Madon [mailto:
madonl@...]
>On Tuesday, December 11, 2001, at 04:33 AM, Billy Tanksley wrote:
>> > However, for this to work, Joy must drop its current support for
>> >recursive definitions: I for one would be happy to see them go.
>> Why? That doesn't make sense to me.
>Well if I have:
>foo == ... bar ...
>bar == ... foo ...
>there is no longer any clearly defined topographical order for
>the type inferencer to follow (its not a DAG anymore).
Ah, so your problem is mutually recursive definitions, not recursive
definitions. That makes more sense. Yes, I don't like Joy's support for
undeclared forward references; it not only makes parsers harder to build, it
also makes the language slower for any number of different operations.
>You could come up with a more complicated scheme to handle cycles but
>since Joy can provide recursion without resorting to recursive
>definitions, such definitions are redundant - I'd prefer to eliminate
>them and so avoid the extra complexity.
Agreed.
>Louis.
-Billy
Billy Tanksley — 2001-12-11 01:03:49
From: e1_t [mailto:
e1_t@...]
>> This is very important, and in fact fundamental to the distinction
>> between
>> functional and non-functional languages. The important part isn't
>> that it's
>> _possible_ to transform from readable-but-inefficient to
>> efficient-but-unreadable; the point is that those transformations
>> can be
>> done according to text-based rules rather than semantic analysis.
>I agree. I should have clarified that better but that's what I meant.
>Although the only thing I forgot to say was really that it's not
>impossible to implement an imperative language that transforms
>readable and inefficient programs into more efficient forms but that
>implementing a functional language that does that is a LOT easier.
Yes. And the reason that it's easier is that it's an entirely different
sort of task. In a pure functional language, all of the language's
rewriting rules apply anywhere, so you don't have to run expensive tests to
check whether they apply; you just rewrite. Indeed, in Joy, all of the
language's rewriting rules apply everywhere. Therefore, Joy is a pure
functional language.
>My initial point was related to claims about Joy being a pure
>functional language. Since Joy doesn't make a distinction between
>functions with side-effects and pure functions the reasoning that Joy
>is a pure functional language because of hidden arguments being
>passed to functions with side-effects implies that impure functional
>languages are in fact pure and that even most imperative languages
>are 1st-order pure functional languages - but they're not. That was
>the main reason why I stated the main differences between imperative
>and functional languages.
The differences you stated are correct, but they don't go to the root of the
difference. They only mention some specific differences, which happen to
only apply to a specific type of language, applicative.
>> rules are called the "rewriting rules" of the language.
>> One of the fundamental rewriting rules of lambda-based languages is
>> "typographically identical expressions produce identical results."
>> This
>> rule is not present in concatenative languages like Joy and Forth;
>> but this
>> rule is the basis for the prohibition against changing state. I
>> question,
>> therefore, whether the prohibition against changing state applies to
>> concatenative languages.
>That's a very good point. In fact I never thought about it in that
>way.
>Ok. Unless I'm missing something here, that means writing a lazy
>concatenative system doesn't make much sense since laziness is
>something that aids in equational reasoning of lambda-based languages
>which are clearly different from concatenative ones.
Yes. In fact, I've discussed this on the list in the past. Laziness
doesn't make sense in a concatenative language, because the order of
execution is strictly laid out by the programmer. However, the things which
laziness is used for still make sense, and there are better ways of getting
them.
As far as I can see, the first purpose of laziness is to give controlled,
delayed execution. The best way I can see to provide that is to define a
new list type which by its nature was delayed.
The second purpose is to allow optimization. However, there's another thing
which allows optimization -- it's called an "optimiser". I don't see
anything which forbids using one. I'll give a pseudo-algorithm for
optimizing concatenative code below; this is only a pseudo-algorithm because
one vital step requires a heuristic, and I don't know what would make a good
rule.
If applicative languages can be lazy, then perhaps a concatenative language
which follows this algorithm (or one based on a tree-expansion, same basic
idea) should be called "diligent".
So here goes, in four parts (unless I add another part and forget to change
the number here). Oh, I'm going to use vocabulary without defining it. I
hope that you can figure out the meaning from the use; if not, assume that
it's my mistake and ask me what I mean.
To optimise a function in a concatenative language:
1 Read the type of the function; write it into the dictionary along with
the name of the function.
2 Load appropriate starting type-tokens on the type stack, each of them
marked 'unknown'.
3 Translate the word into machine code by the procedure discussed in
[Note2]. Note that the procedure calls this 'inlining'; inlining is very
similar to translation.
4 Compare the ending state of the type stack with the word's definition,
producing an error if needed. Mark the output parameters in the definition
according to whether or not they're 'known' according to the typestack.
Done.
Note1: There are three ways to Compile a word at compile time. Some words
have more than one choice possibility; in that case the correct answer must
be chosen heuristically, or by analysing more of the program. Here are the
three choices:
- Generate a call to it: always if the word is a state-dependant
primitive. If some of the words' inputs are 'known', you will have to also
generate literals with those values (they will be on the data stack).
- Execute it: if and only if the word's input is completely known.
- Inline it [Note2]: only if it's not a primitive.
After Compiling any word, reduce the type stack using the type information
defined as part of the word.
Note2: Inlining a definition means to:
1 lookup the first word, matching its input types to the top of the type
stack.
2 Compile that word [Note1].
3 Compile the rest of the definition [Note1].
The heuristic in Note1 means that this produces variable results, but if the
harshest possible heuristic is chosen, it means that the highest-level
routine will contain ALL of the state-altering primitives, and the other
definitions will be cut and carved in order to extract those primitives from
them.
Note that the potentially recursive nature of step 3 of Note2 allows you to
partially inline a word -- you can inline the first three calls in the word,
and then generate a call which jumps directly to execute the rest.
>In the language I'm designing I didn't really pay attention to
>whether it's concatenative or not - in fact until I found out about
>Joy I wasn't aware of the properties of concatenative systems.
Me neither. And same here -- I was also playing around with a Forthlike
language.
>My
>goal was simply to extend Forth (in my personal view the ultimate
>meta-language and arguably the most elegant imperative language ever
>designed) into a functional language that could utilize equational
>reasoning of lambda-based systems which as it turns out isn't
>necessary. So the only thing Forth is really missing in order to
>become an impure functional language are higher order functions.
That's a reasonable statement. Actually, with one more change Forth could
be a pure functional language: if Forth didn't support viewing its own
source it would be purely concatenative, and therefore purely functional.
>On the other hand equational reasoning of lambda-based systems is
>closer to how humans think or better said how we're tought to think
>in schools.
Very late, and only in certain formal contexts. For good reason: the world
isn't declarative. Unless you're a god.
>Wouldn't that mean that most problems devised by most
>people are in fact better suited to lambda-based systems?
Problems devised by people aren't worth solving. Better to solve real
problems. And real problems are ALWAYS imperative: you don't just want to
think about a situation without doing anything.
>Concatenative systems do indeed resemble imperative ones in many ways
>and formulating problems for concatenative systems is consequently
>similar to designing problems for imperative systems (especially
>Forth)
I don't know why you'd want to create problems when there are already so
many of them out there. Create solutions instead.
>so again the programmer has to simplify or reformulate many
>problems.
Good. That's called "thinking", and like it or not, it's an essential part
of the problem-solving process.
>> >and because they are better suited to parallel
>> >programming (the order of evaluation of pure, side-effect free
>> >functions is irrelevant therefore they can be executed in
>> >parallel).
>> Here's a problem. By the nature of a stack-based language, the
>> order of
>> execution is given by the programmer. In order to change it, you
>> have to analyse the program exhaustively.
>I don't see stack as a problem.
I don't either -- but what I said is still true. The order of execution is
fixed by the programmer in stack-based languages. There are very few
(actually, no) rewriting rules in concatenative languages which allow
juggling execution order; all transformations preserve order.
>Also analysis of all Forth-like languages is relatively simple. I
>don't see that as a problem either if it's done at compile time.
No, it's not a problem; however, confining the solution to full analysis
means that we can't do something that the applicative language can (the
applicative language can choose different orders of execution).
>> I could say, based on this, that applicative languages are a better
>> choice
>> for this sort of analysis, because the order of evaluation of the
>> arguments
>> to a function isn't specified by the programmer; therefore, the
>> parallel
>I think that explains why side-effects in a concatenative language
>don't conflict with the rewriting rules of the language in a simpler
>way. Simply because programs are in fact sequential.
Exactly. Note, however, that this sequence allows two things:
1. Seperation into parallel sequences.
2. Strict ordering of "usefulness" of data.
Because the sequence is precisely fixed, and because the compiler can assume
the programmer placed data in a logical place, the compiler can know that
data deep on the stack is less immediately useful than data near the top of
the stack. Register allocation, cache allocation, and paging all become
almost trivial -- make the top of the stack fast, and the bottom of the
stack slow, and everything will work out.
>> Why do you think concatenative languages, which look less parallel,
>> will be better for this than applicative languages?
>I never said they were.
Hmm. I thought you said that transforming sequential into parallel programs
was one of your goals.
>Again as I said my goal was extending Forth into a functional
>language that utilizes equational reasoning of lambda-based systems.
I think I addressed that.
>This may still be worth exploring.
Quite simply, I don't think so. The equational reasoning of lambda-based
systems is useful for lambda-based systems. Forth is not lambda-based; it's
based on a complete replacement for lambda.
>Forth is a lot like an abstract
>assembly language. If it was extended into a very simple lazy
>functional language
Instead, *reduce* it into a very simple diligent functional language. All
you have to do is disable the ability to read and modify your own source,
and Forth will be fully functional. Laziness is irrelevant and impossible,
but diligence could be profitable.
>that is easy to analyze and optimize then
As I've mentioned...
>extending Forth further into a highly abstract lazy lambda-based
>language would become relatively easy.
Highly abstract, yes. Lambda-based, no.
>> I think the only solution is to make it easy for programmers to
>> build parallelism into their programs. Provide synchonization
>> and APL-style array operations.
>Ultimatly if you want to build an efficient system you can't rely on
>the capabilities of the language you're using (or better said
>implementation of it) to optimize that system - you have to do it
>yourself by using the right data structures and design. The same
>doesn't only hold for writing speed/memory efficient programs but
>also programs that exploit parallelism.
That's partially true, and partially not. If the language doesn't offer
synchronization, there's simply no way to safely write explicitly parallel
programs. If the language is explicitly sequenced (as are all concatenative
languages), there's no way to write implicitly parallel programs. Both are
desirable for certain things.
>> >One of my current projects is Metafor, a functional language based
>> >on Forth that can be implemented as an extension to Forth.
>> Facinating! I've heard about Metafor here, but I wasn't able to
>> find any
>You must have heard of another system with the same name since not
>many people know about my project (or any of my other projects for
>that matter). That means I'm going to have to find a new name for it.
Search the archives of this list -- it was mentioned here, quite a while
ago. I'm almost certain that whoever mentioned it mentioned the author as
having a very short, mixed name -- e1_t certainly looks familiar.
You know what, though? I can't find a WORD about Metafor in the archives
(aside from this discussion). I think you'll have to just ignore me until I
figure out where I found that.
>A while ago I actually looked on the net for languages or programs
>already named Metafor and I didn't find any so I decided to name it
>Metafor. Yesterday I looked again and it seems there's already a
>theorem prover called metafor.
Ah. Perhaps, then, Metaforth? :-)
>> info source. Could you discuss it a bit?
[snip]
Thanks! Interesting history.
>> This has been studied before. One of the more interesting ways of
>> looking
>Wouldn't be the first time I reinvented the wheel. I was suspecting
>it has been done before but I couldn't find any info on the net on
>anything similar.
Happens to all of us :-).
>> at it introduces it by dividing time discretely, rather than
>> continuously;
>> you can access the result of past calls as part of the definition
>> of the function, thereby allowing you to define recursive functions
>> mathematically.
>Are there any papers on this available on the net?
There's an entire language implementation SOMEWHERE. I lost the bookmark,
but let me see what I can do:
http://www-verimag.imag.fr/SYNCHRONE/lustre-english.html
Lustre is the closest to what I'm thinking of, but it's not the language I
saw. The one I saw was a high-level functional declarative language, and
this is all that and low-level too.
http://www-sop.inria.fr/meije/esterel/esterel-eng.html
Nope, doesn't even look familiar.
>> >I was wondering if anyone has any criticisms of this approach? It
>> >resembles embedding an imperative language within a functional one
>> >but from what I can see so far I don't see how this could affect
>> >equational reasoning. The approach might be missing some
>> >additional rules though.
>> Well, the worst problem is that it doesn't affect equational
>> reasoning at
>> all; it's an analytical principle and not a textual one. Textually,
>> concatenative language already are impossible to reorder;
>> analytically, they're equivalent to applicative languages.
>What do you mean by textual principle?
Um... A principle which can be applied simply by looking at arbitrary text.
Your principle, that calling a state-dependant function makes you
state-dependant, is an analytical principle. You can't apply it without
deriving a complete tree of the entire program.
Applicative functional languages have the "referential transparency"
principle: any two valid programs in the same scope which look alike ARE the
same program. Concatenative functional languages have different rules, one
of which is that any two valid programs can be pasted together to form
another valid program, and any valid program can be split on any token
boundary to form two valid programs. Note that I use that rule in my
optimiser -- because I can split programs, I can inline the first part of a
word and call the rest.
>Ivan
-Billy
Massimo Dentico — 2001-12-11 01:15:52
Louis Madon wrote:
[Removed discussion with Serguey Zefirov about Joy,
and concatenative languages in general, not having
a type system with principal types and excerpt from
Ph.D. dissertation of Kris De Volder about the
expressive power of undecidable and ambiguous type
systems ...]
Lennart Augustsson's Cayenne is a prototype language
implementation with such undecidable and ambiguous
type system (specifically dependent types):
-
http://www.md.chalmers.se/~augustss/cayenne/
--
Massimo Dentico
Reuben Thomas — 2001-12-11 10:06:17
> The macro implementation would run recursively until all reductions were
> evaluated.
In real life, until you give up: optimization won't terminate, as some
combinations of macros will end up cancelling out, and some will expand
the program and be able to be applied infinitely many times.
venusian_1999 — 2001-12-11 13:13:19
Sorry if I've broken the attributions; confused by the yahoo's editor...
--- In concatenative@y..., Billy Tanksley <wtanksley@b...> wrote:
> From: Louis Madon [mailto:madonl@b...]
> >You could come up with a more complicated scheme to handle cycles but
> >since Joy can provide recursion without resorting to recursive
> >definitions, such definitions are redundant - I'd prefer to eliminate
> >them and so avoid the extra complexity.
> Agreed.
Not contributed much to this list recently but I'm still plugging away
at my own concatenative language.
I've always liked the idea of disallowing implicit recursion in
concatenative languages however building an efficient and flexible
combinator for N-ary mutual recursion seems difficult.
My pet problem is parsing: the target for my language is to be able to
build combinator parsers with the same ease that Prolog allows DCGs to
be built. By their nature parse rules are mutually recursive, not
merely between small localised groups but between arbitrary rules.
What would the N-ary recursive combinator look like?
Maybe:
[ [] [] [] []... ] [A] Nrec
Where Nrec executes program A, which leaves an integer (X) on top of
the stack. If X==0 Nrec finished else it recurses by executing the
Xth program from the list of programs.
This is pretty horrible, agreed, and I'm certainly not proposing it as
a Good Thing, but what would a Good Thing be? How does one of the set
of mutual functions name another to call other than by ordinal
position in a list?
--
Martin Young.
S. Alexander Jacobson — 2001-12-11 13:24:29
My recollection is that functional programs have some property where
every rewrite is strictly smaller in some sense than the expression being
replaced. We could enforce that.
-Alex-
On Tue, 11 Dec 2001, Reuben Thomas wrote:
> > The macro implementation would run recursively until all reductions were
> > evaluated.
>
> In real life, until you give up: optimization won't terminate, as some
> combinations of macros will end up cancelling out, and some will expand
> the program and be able to be applied infinitely many times.
>
>
___________________________________________________________________
S. Alexander Jacobson i2x Media
1-917-783-0889 voice 1-212-697-1427 fax
Reuben Thomas — 2001-12-11 13:35:47
> My recollection is that functional programs have some property where
> every rewrite is strictly smaller in some sense than the expression being
> replaced. We could enforce that.
Sounds like a bogus recollection to me, unless it excludes recursion. As
soon as you have a recursion combinator (as a lambda term), you get
rewrites that are bigger than the original.
e1_t — 2001-12-11 17:04:29
--- In concatenative@y..., Ocie Mitchell <ocie_mitchell@y...> wrote:
> --- e1_t <e1_t@y...> wrote:
> > --- In concatenative@y..., Louis Madon <madonl@b...>
> > wrote:
> > >
> > > Regarding your distinction between chaotic
> > functions and mutators -
> > is
> > > it really neccesary? (sorry, I'm a minimalist :-)
> > >
> >
> > Mutators are just a concept - the language itself
> > doesn't need a
> > system for distinguishing between a function and a
> > mutator. The
> > compiler can automatically determine if a function
> > is a mutator.
> > The reason why I felt they are important is because
> > a mutator is a
> > function that's essentially pure - it's output only
> > depends on it's
> > input. Therefore the order of evaluation of mutators
> > is still
> > irrelevant. The side-effects caused by mutators can
> > be completely
> > separated from them.
>
> I don't think this necessarily follows. If the
> mutator alters the outside world, then changing the
> order of execution of mutators changes the outcome.
> Consider:
>
You didn't read all of what I said. Side effects caused by mutators
can be completely separated from them. Only the function that causes
the side effect can't be reordered.
In other words every mutator can be split into two functions, a pure
function and a function that causes the side effect.
Non-atomic chaotic functions cannot complete the computation of their
output without knowing the output of another chaotic function
(doesn't matter if it's atomic or not). Chaotic functions, being time
bound, are basically stalling the caller function unless the caller
function ignores the output and calls the chaotic function just to
cause a side effect in which case the caller function is a mutator.
Mutators can proceed in calculating and returning their output
without having to wait for the side-effect to occur. Furthermore they
can also be optimized and reduced to a simpler form just like pure
functions.
Note that atomic mutators are really chaotic functions. In Joy 'put'
could be described as an atomic mutator.
> open_refrigerator
> remove_beer
> close_refrigerator
> open_beer
> drink_beer
>
> Some reordering is possible, specifically
> close_refrigerator and open_beer could be swapped, but
> arbitrary reordering is not possible.
>
I'm not sure I follow the example.
It seems to me that none of those functions are mutators. For example
in order for someone to close the fridge, the fridge door first has
to be opened. That suggests the existance of a state of the fridge
door. Therefore open_refrigerator and close_refrigerator are chaotic.
Ivan
Billy Tanksley — 2001-12-11 17:11:25
From: e1_t [mailto:
e1_t@...]
>You didn't read all of what I said. Side effects caused by mutators
>can be completely separated from them. Only the function that causes
>the side effect can't be reordered.
>In other words every mutator can be split into two functions, a pure
>function and a function that causes the side effect.
Three functions, actually. One which doesn't cause or depend on the side
effect, one primitive which simply causes the side effect, and one which
depends on the side effect but doesn't cause it.
>Ivan
-Billy
Billy Tanksley — 2001-12-11 18:15:28
From: S. Alexander Jacobson [mailto:
shop2it@...]
>My recollection is that functional programs have some property where
>every rewrite is strictly smaller in some sense than the
>expression being replaced. We could enforce that.
Not by any rule I've ever seen! If there were any such rule, no
nonfunctional language could EVER hope to compete with any functional one.
Manifestly, this is NOT the case -- although there are VERY good functional
compilers, they take a LOT of effort to make.
>-Alex-
-Billy
Ocie Mitchell — 2001-12-11 19:14:43
--- e1_t <
e1_t@...> wrote:
> --- In concatenative@y..., Ocie Mitchell
> <ocie_mitchell@y...> wrote:
> > --- e1_t <e1_t@y...> wrote:
> > > --- In concatenative@y..., Louis Madon
> <madonl@b...>
> > > wrote:
> > > >
> > > > Regarding your distinction between chaotic
> > > functions and mutators -
> > > is
> > > > it really neccesary? (sorry, I'm a minimalist
> :-)
> > > >
> > >
> > > Mutators are just a concept - the language
> itself
> > > doesn't need a
> > > system for distinguishing between a function and
> a
> > > mutator. The
> > > compiler can automatically determine if a
> function
> > > is a mutator.
> > > The reason why I felt they are important is
> because
> > > a mutator is a
> > > function that's essentially pure - it's output
> only
> > > depends on it's
> > > input. Therefore the order of evaluation of
> mutators
> > > is still
> > > irrelevant. The side-effects caused by mutators
> can
> > > be completely
> > > separated from them.
> >
> > I don't think this necessarily follows. If the
> > mutator alters the outside world, then changing
> the
> > order of execution of mutators changes the
> outcome.
> > Consider:
> >
>
> You didn't read all of what I said. Side effects
> caused by mutators
> can be completely separated from them. Only the
> function that causes
> the side effect can't be reordered.
> In other words every mutator can be split into two
> functions, a pure
> function and a function that causes the side effect.
>
> Non-atomic chaotic functions cannot complete the
> computation of their
> output without knowing the output of another chaotic
> function
> (doesn't matter if it's atomic or not). Chaotic
> functions, being time
> bound, are basically stalling the caller function
> unless the caller
> function ignores the output and calls the chaotic
> function just to
> cause a side effect in which case the caller
> function is a mutator.
> Mutators can proceed in calculating and returning
> their output
> without having to wait for the side-effect to occur.
> Furthermore they
> can also be optimized and reduced to a simpler form
> just like pure
> functions.
I see. So you are saying that a function that causes
a side effect, but doesn't have a return value
dependant on that side effect can be optimized, as
long as we remember to still cause the side effect to
happen somehow?
>
> Note that atomic mutators are really chaotic
> functions. In Joy 'put'
> could be described as an atomic mutator.
>
> > open_refrigerator
> > remove_beer
> > close_refrigerator
> > open_beer
> > drink_beer
> >
> > Some reordering is possible, specifically
> > close_refrigerator and open_beer could be swapped,
> but
> > arbitrary reordering is not possible.
> >
>
> I'm not sure I follow the example.
> It seems to me that none of those functions are
> mutators. For example
> in order for someone to close the fridge, the fridge
> door first has
> to be opened. That suggests the existance of a state
> of the fridge
> door. Therefore open_refrigerator and
> close_refrigerator are chaotic.
Well, in a properly designed program you could make
these functions depend on the state of the world.
I.E. don't remove the beer until the fridge is open...
Its probably not the best example, and if I
understand what you said before, then the function
calls could be reordered as long as the side effects
they produce are still applied to the outside world in
the correct order.
Ocie
__________________________________________________
Do You Yahoo!?
Check out Yahoo! Shopping and Yahoo! Auctions for all of
your unique holiday gifts! Buy at
http://shopping.yahoo.com
or bid at
http://auctions.yahoo.com
S. Alexander Jacobson — 2001-12-11 20:54:16
You are mixing two different issues.
1. Whether a program is guaranteed to terminate.
One language that I know is guaranteed to terminate is Charity.
http://www.cpsc.ucalgary.ca/projects/charity/home.html
It is not turing complete, but they argue that you almost never need
turing completeness.
2. Whether reduction actually reduces.
I think that all functional programming implementations are built on the
assumption that the interpreter compiler can guarantee that a rewrite
does not add evaluation complexity. i don't remember the details, but i
think it is a necessary aspect of funtional implementations.
-alex-
On Tue, 11 Dec 2001, Billy Tanksley wrote:
> From: S. Alexander Jacobson [mailto:shop2it@...]
>
> >My recollection is that functional programs have some property where
> >every rewrite is strictly smaller in some sense than the
> >expression being replaced. We could enforce that.
>
> Not by any rule I've ever seen! If there were any such rule, no
> nonfunctional language could EVER hope to compete with any functional one.
> Manifestly, this is NOT the case -- although there are VERY good functional
> compilers, they take a LOT of effort to make.
>
> >-Alex-
>
> -Billy
>
___________________________________________________________________
S. Alexander Jacobson i2x Media
1-917-783-0889 voice 1-212-697-1427 fax
Billy Tanksley — 2001-12-11 21:09:30
From: S. Alexander Jacobson [mailto:
shop2it@...]
>You are mixing two different issues.
>1. Whether a program is guaranteed to terminate.
>One language that I know is guaranteed to terminate is Charity.
>http://www.cpsc.ucalgary.ca/projects/charity/home.html
>It is not turing complete, but they argue that you almost never need
>turing completeness.
Thanks for the pointer -- interesting. I've never found an interesting, non
turing complete language. I wonder if this is the first one.
>2. Whether reduction actually reduces.
>I think that all functional programming implementations are
>built on the
>assumption that the interpreter compiler can guarantee that a rewrite
>does not add evaluation complexity. i don't remember the
>details, but i
>think it is a necessary aspect of funtional implementations.
Okay, here's the answer: no, I'm not confusing them. Optimization does not
always terminate (and in fact, isn't computable) in part because there are
many different aspects of optimization, and rewrites which improve one
aspect usually hurt another one, and rewrites which do nothing but hurt may
in some cases be the only way to reach a state where you can apply a very
beneficial rewrite.
Another reason why optimization isn't computable is that the things you're
trying to optimise are quite often uncomputable -- for example, speed. The
only way to find how fast a function is, is to run it: and often your answer
will depend on the input as much as the program.
These are why you can NOT possibly be right. If you still think you're
right (and for all I know you may be), please explain.
Hmm, I'm studying my reply below -- I never mentioned ANYTHING about
computability and termination. Why did you bring it up in a reply to me?
My original argument was strictly pragmatic, and your reply to it has
absolutely nothing to do with it.
>-alex-
>On Tue, 11 Dec 2001, Billy Tanksley wrote:
>
>> From: S. Alexander Jacobson [mailto:shop2it@...]
>>
>> >My recollection is that functional programs have some property where
>> >every rewrite is strictly smaller in some sense than the
>> >expression being replaced. We could enforce that.
>>
>> Not by any rule I've ever seen! If there were any such rule, no
>> nonfunctional language could EVER hope to compete with any
>> functional one. Manifestly, this is NOT the case -- although
>> there are VERY good functional compilers, they take a LOT of
>> effort to make.
Louis Madon — 2001-12-11 21:58:34
On Tuesday, December 11, 2001, at 11:13 PM, venusian_1999 wrote:
> ...
> I've always liked the idea of disallowing implicit recursion in
> concatenative languages however building an efficient and flexible
> combinator for N-ary mutual recursion seems difficult.
>
> My pet problem is parsing: the target for my language is to be able to
> build combinator parsers with the same ease that Prolog allows DCGs to
> be built. By their nature parse rules are mutually recursive, not
> merely between small localised groups but between arbitrary rules.
>
> What would the N-ary recursive combinator look like?
>
> Maybe:
>
> [ [] [] [] []... ] [A] Nrec
>
> Where Nrec executes program A, which leaves an integer (X) on top of
> the stack. If X==0 Nrec finished else it recurses by executing the
> Xth program from the list of programs.
>
> This is pretty horrible, agreed, and I'm certainly not proposing it as
> a Good Thing, but what would a Good Thing be? How does one of the set
> of mutual functions name another to call other than by ordinal
> position in a list?
Well this is one of the unsolved problems in Joy right now. If you
consider a mutually recursive group of functions like a graph, eg in the
simple two-function case:
----> A <---> B
This graph just depicts one possibility, we might want to enter at B
instead. The point is that the group can be described by a graph and
each node in that graph will have a specific number of edges entering
and exiting.
So my idea is, we implement each node as a quotation such that when it
is called, there will be a list of quotations at the top of the stack
representing each outgoing edge for that node.
In the graph depicted above, A will see a singleton list containing
[edge_to_B] and B will also see a singleton list containing
[edge_to_A]. Each node is responsible for selecting and invoking the
appropriate outgoing edge when it runs (if none is invoked then
execution automatically exits the whole recursive group). The whole
thing comes together as follows:
[ [A] [B] ... ] [G] Nrec
where G describes the connectivity of the graph (eg. as an adjaceny
matrix).
Now I don't know that this is any more of a Good Thing than you've
suggested, but I guess throwing some alternatives onto the table is a
start.
Louis.
[Non-text portions of this message have been removed]
S. Alexander Jacobson — 2001-12-11 22:17:57
On Tue, 11 Dec 2001, Billy Tanksley wrote:
> Another reason why optimization isn't computable is that the things you're
> trying to optimise are quite often uncomputable -- for example, speed. The
> only way to find how fast a function is, is to run it: and often your answer
> will depend on the input as much as the program.
>
> These are why you can NOT possibly be right. If you still think you're
> right (and for all I know you may be), please explain.
I just did a little bit of homework. I am talking about beta reduction.
An optimization library is just a set of rewriting rules like this.
anytime you see e.g.
1 + 1 -
replace it with [].
Some sets of optimization rules will terminate. Others won't.
> Hmm, I'm studying my reply below -- I never mentioned ANYTHING about
> computability and termination. Why did you bring it up in a reply to me?
> My original argument was strictly pragmatic, and your reply to it has
> absolutely nothing to do with it.
I wasn't sure why you were talking about competition.
Beta reduction does not strike me as a competitive issue.
-Alex-
>
> >-alex-
>
> >On Tue, 11 Dec 2001, Billy Tanksley wrote:
> >
> >> From: S. Alexander Jacobson [mailto:shop2it@...]
> >>
> >> >My recollection is that functional programs have some property where
> >> >every rewrite is strictly smaller in some sense than the
> >> >expression being replaced. We could enforce that.
> >>
> >> Not by any rule I've ever seen! If there were any such rule, no
> >> nonfunctional language could EVER hope to compete with any
> >> functional one. Manifestly, this is NOT the case -- although
> >> there are VERY good functional compilers, they take a LOT of
> >> effort to make.
>
___________________________________________________________________
S. Alexander Jacobson i2x Media
1-917-783-0889 voice 1-212-697-1427 fax
Billy Tanksley — 2001-12-11 22:33:19
From: S. Alexander Jacobson [mailto:
shop2it@...]
>On Tue, 11 Dec 2001, Billy Tanksley wrote:
>> These are why you can NOT possibly be right. If you still
>> think you're
>> right (and for all I know you may be), please explain.
>I just did a little bit of homework. I am talking about beta
>reduction.
Ah! Yes, beta reduction is important as a counterpart to lambda expansion.
However, it has next to nothing to do with optimization; it's merely part of
compilation.
>An optimization library is just a set of rewriting rules like this.
>anytime you see e.g.
>1 + 1 -
>replace it with [].
>Some sets of optimization rules will terminate. Others won't.
Right. Any set of optimization rules which includes expansions will have
uncomputable termination. Any set of rules which does not include
expansions will be incomplete (but useful; witness peephole optimisers).
Beta reduction could certainly be one of the rules in a functional
applicative optimiser's vocabulary; its effect would be to define a new
function. This is a VERY complicated rule, though, and requires analysis of
code across multiple scopes; it's NOT in any way simple. The equivalent
rule in a functional concatenative optimiser is purely textual and requires
no analysis: if you find two textually identical sequences of tokens, you
can always replace them with a call to a word defined as that sequence of
tokens.
>> Hmm, I'm studying my reply below -- I never mentioned ANYTHING about
>> computability and termination. Why did you bring it up in a
>> reply to me?
>> My original argument was strictly pragmatic, and your reply to it has
>> absolutely nothing to do with it.
>I wasn't sure why you were talking about competition.
>Beta reduction does not strike me as a competitive issue.
Ah. That's amusing; thanks for working through the confusion with me. The
things you say make sense now, except I'm still a little confused on what
this has to do with making functional languages easy to optimize.
>-Alex-
-Billy
Manfred von Thun — 2001-12-12 03:26:49
On Tue, 11 Dec 2001, venusian_1999 wrote:
...
> I've always liked the idea of disallowing implicit recursion in
> concatenative languages however building an efficient and flexible
> combinator for N-ary mutual recursion seems difficult.
...
> What would the N-ary recursive combinator look like?
> Maybe:
> [ [] [] [] []... ] [A] Nrec
> Where Nrec executes program A, which leaves an integer (X) on top of
> the stack.
I had a similar solution some years back.
I just dug it out from the now defunct tstlib.joy
LIBRA
(* mutual recursion combinator for any number of functions: *)
(* mutinx - MUTual recursion by INdeX *)
mutinx == dupd at i;
(* an example: the two predicates "even" and "odd": *)
mr_even_odd ==
[ [ [pop null] [pop pop true ] [[pred] dip 1 mutinx] ifte ]
[ [pop null] [pop pop false] [[pred] dip 0 mutinx] ifte ] ];
mr_even == mr_even_odd 0 mutinx;
mr_odd == mr_even_odd 1 mutinx.
...
> This is pretty horrible, agreed, and I'm certainly not proposing it as
> a Good Thing, but what would a Good Thing be?
Horrible, yes. Similar in horribility to LET and LETREC in Lisp/Scheme.
Manageable at a small scale, but not when too big.
> How does one of the set
> of mutual functions name another to call other than by ordinal
> position in a list?
Well, some kind of (runtime!) search could be used instead.
> --
> Martin Young.
e1_t — 2001-12-12 19:10:48
--- In concatenative@y..., Billy Tanksley <wtanksley@b...> wrote:
> >Again as I said my goal was extending Forth into a functional
> >language that utilizes equational reasoning of lambda-based
systems.
>
> I think I addressed that.
>
> >This may still be worth exploring.
>
> Quite simply, I don't think so. The equational reasoning of lambda-
based
> systems is useful for lambda-based systems. Forth is not lambda-
based; it's
> based on a complete replacement for lambda.
>
> >Forth is a lot like an abstract
> >assembly language. If it was extended into a very simple lazy
> >functional language
>
> Instead, *reduce* it into a very simple diligent functional
language. All
> you have to do is disable the ability to read and modify your own
source,
> and Forth will be fully functional. Laziness is irrelevant and
impossible,
> but diligence could be profitable.
>
Let me rephrase that. Think of it as transforming a program written
in a lambda based language into a program written in a concatenative
language although instead of writing a compiler (like Haskell2Joy or
something similar) you extend Forth into a simple lambda-based
language that can further be extended into Haskell or some other
lambda based language.
It's not something I'm interested in doing (at least not anymore
since I found out about the properties of concatenative languages)
but I still think it's worth doing.
> >> at it introduces it by dividing time discretely, rather than
> >> continuously;
> >> you can access the result of past calls as part of the
definition
> >> of the function, thereby allowing you to define recursive
functions
> >> mathematically.
>
> >Are there any papers on this available on the net?
>
> There's an entire language implementation SOMEWHERE. I lost the
bookmark,
> but let me see what I can do:
>
> http://www-verimag.imag.fr/SYNCHRONE/lustre-english.html
>
> Lustre is the closest to what I'm thinking of, but it's not the
language I
> saw. The one I saw was a high-level functional declarative
language, and
> this is all that and low-level too.
>
> http://www-sop.inria.fr/meije/esterel/esterel-eng.html
>
> Nope, doesn't even look familiar.
>
Thanks for the links.
Ivan
e1_t — 2001-12-12 19:15:36
--- In concatenative@y..., Billy Tanksley <wtanksley@b...> wrote:
>
> Three functions, actually. One which doesn't cause or depend on
the side
> effect, one primitive which simply causes the side effect, and one
which
> depends on the side effect but doesn't cause it.
>
I don't see how splitting it into 3 functions helps. I think two is
sufficient.
Primitive that causes the side effect and the one that depends on the
side effect go together.
Whether the code can further be optimized or whether it should be
inlined is a problem for the compiler.
The main point is that the code that doesn't depend on the side
effect can be separated and reordered.
Ivan
Billy Tanksley — 2001-12-12 21:42:40
From: e1_t [mailto:
e1_t@...]
>--- In concatenative@y..., Billy Tanksley <wtanksley@b...> wrote:
>> Three functions, actually. One which doesn't cause or depend on
>> the side effect, one primitive which simply causes the side
>> effect, and one which depends on the side effect but doesn't cause
>> it.
>I don't see how splitting it into 3 functions helps. I think two is
>sufficient.
>Primitive that causes the side effect and the one that depends on the
>side effect go together.
>Whether the code can further be optimized or whether it should be
>inlined is a problem for the compiler.
>The main point is that the code that doesn't depend on the side
>effect can be separated and reordered.
But there's no guarantee that the part of the function before the primitive
doesn't depend on a side effect. It could be depending on a completely
different side effect, brought over from some other function. Splitting the
function doesn't magically allow you to reorder.
3 functions isn't essential, but it does give the basic idea; that the only
thing forcing a split is the primitive itself, which can then be hoisted to
any level in the hierarchy (by one of the simplest rules in a concatenative
language).
For example, suppose that "!" is the only primitive in the following
definitions (no attempt is made here to make sense):
: f 3 ;
: h 45 f ;
: g h ! h ;
: d 3 ! ;
: me 3 d g g h ! f ;
This could be reduced to:
: f 3 ;
: h 45 f ;
: g1 h ;
: g2 ! ;
: g3 h ;
: d1 3 ;
: d2 ! ;
: d3 ;
From that "me" can become:
: me 3 d1 ! d3 g1 ! g3 g1 ! g3 h ! f ;
All of the primitives are in a single function; this may make some types of
optimization much easier.
>Ivan
-Billy
Joel Kelso — 2001-12-13 14:21:55
> Beta reduction could certainly be one of the rules in a functional
> applicative optimiser's vocabulary; its effect would be to define a new
> function. This is a VERY complicated rule, though, and requires analysis of
> code across multiple scopes; it's NOT in any way simple. The equivalent
> rule in a functional concatenative optimiser is purely textual and requires
> no analysis: if you find two textually identical sequences of tokens, you
> can always replace them with a call to a word defined as that sequence of
> tokens.
Is that last bit true when quotation isn't extensional ? Eg the
"Quotation Revisited" bit from the rewriting systems paper. I know
that optimisation isn't really the point of Joy, but would a
concatenative language with extensional quotation has more scope
for the kind of program transformations you need for optimisation ?
Joel Kelso
--
chiral@...
How many angels can mosh on the head of a pin ?
Billy Tanksley — 2001-12-13 18:46:12
From: Joel Kelso [mailto:
chiral@...]
>> The equivalent
>> rule in a functional concatenative optimiser is purely
>> textual and requires
>> no analysis: if you find two textually identical sequences
>> of tokens, you
>> can always replace them with a call to a word defined as
>> that sequence of tokens.
>Is that last bit true when quotation isn't extensional ?
I don't know what you mean by "isn't extensional" in this context -- I know
too many uses for that word.
But this is true whenever it's possible to define a quotation as "a token".
It's certainly possible in Joy. (Of course, you couldn't write this kind of
optimiser in Joy itself -- or at least, not as an extension to Joy; you'd
have to write a complete compiler. Joy doesn't support defining words,
although I think it should.)
>Joel Kelso
-Billy
Louis Madon — 2001-12-13 23:04:41
On Friday, December 14, 2001, at 12:21 AM, Joel Kelso wrote:
>
> ...
> Is that last bit true when quotation isn't extensional ? Eg the
> "Quotation Revisited" bit from the rewriting systems paper. I know
> that optimisation isn't really the point of Joy, but would a
> concatenative language with extensional quotation has more scope
> for the kind of program transformations you need for optimisation ?
>
My experience is that making quotation extensional simplifies the formal
model of the language - for one thing you don't need lists as a
primitive anymore, since extensional quotation can be defined as
[a b c ... ] == \id \a compose \b compose \c compose ...
where \ is a primitive quotation operator that works only on single
functions (\id refers to the quoted identity function) and compose is
function composition. Moreover there is an interesting relationship
that then emerges between compose, the i combinator and the implicit
function composition operator, they are one and the same! They differ
only in how they obtain their operands:
q r compose -- both operands given explicitly
q i -- right operand implicitly obtained as the program
continuation
. -- both operands implicit, composes the program so far
with its continuation
(here I'm using '.' to denote the implicit function composition operator)
so except for differences in how operands are obtained, we have
compose == i == .
I'm now using the above formulation of extensional quotation in the
optimising compiler that I'm developing and it has simplified many
things without sacrificing expressiveness (you can still define the y
combinator for example).
Louis.
[Non-text portions of this message have been removed]
Billy Tanksley — 2001-12-14 18:34:58
From: e1_t [mailto:
e1_t@...]
>--- In concatenative@y..., Billy Tanksley <wtanksley@b...> wrote:
>> >Again as I said my goal was extending Forth into a functional
>> >language that utilizes equational reasoning of lambda-based
>> >systems.
>Let me rephrase that. Think of it as transforming a program written
>in a lambda based language into a program written in a concatenative
>language although instead of writing a compiler (like Haskell2Joy or
>something similar) you extend Forth into a simple lambda-based
>language that can further be extended into Haskell or some other
>lambda based language.
>It's not something I'm interested in doing (at least not anymore
>since I found out about the properties of concatenative languages)
>but I still think it's worth doing.
Oh, I think I see what you mean. I thought you were suggesting adding
lambda-like functionality into Forth; I think I see that you're suggesting
being able to translate arbitrary concatenative code to and from applicative
form, and therefore being able to apply some of the specialized reserach
that's been done into applicative languages.
Cool! I agree, that would probably be useful. I also agree that it's not
my #1 interest; there's too much about concatenative languages to discover.
-Billy
Manfred von Thun — 2001-12-17 02:57:51
Hello Everyone
I have been very impressed by the recent discussions, but I
have not had the time to reply to at least some of them. That will
have to wait till mid-January.
In the meantime, a very happy Christmas to all.
- Manfred
Jack_Waugh — 2002-02-28 20:23:04
Jack_Waugh — 2002-02-28 22:00:43