# 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

    In regard to the "Joy, purely functional?" thread starting at

    http://groups.yahoo.com/group/concatenative/message/883

    , readers may also be interested by the approaches to I/O in

    Clean and in Fudgets.

    http://www.cs.kun.nl/~clean/

    http://www.cs.chalmers.se/~hallgren/Thesis/top.html

## Jack_Waugh — 2002-02-28 22:00:43

    Charity seems to have moved to

    http://www.cpsc.ucalgary.ca/Research/charity/home.html