Lambda the Ultimate

(Note, I don't use any concatenative language, although I do use an HP-41 and have programmed it)

The trick is simply to use small, functional words (i.e., local stack effects). That way, you only have to treat words as black boxes that take input and give output, aka functions. When you start having to track the stack, it's probably a good hint you need to break the word down in a couple more intuitive words (or that your interface for that word is extremely messy).

The trick is small, easily testable words. Any time you do lots of stack manipulations is a sign that you need to refactor. 'Thinking Forth' has lots of good advice in this area:

http://thinking-forth.sourceforge.net

Manfred von Thun's Joy pages also covers this in some of the articles. His one on the quadratic formula for example:

http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-quadratic.html

       -b  +/- sqrt(b^2 - 4 * a * c)
       -----------------------------
                  2 * a

(define quadratic-formula
   (lambda (a b c)
      (let ([minusb (- 0 b)]
            [radical (sqrt (- (* b b) (* 4 ( * a c))))]
            [divisor (* 2 a)] )
         let ([root1 (/ (+ minusb radical) divisor)]
              [root2 (/ (- minusb radical) divisor)])
           (cons root1 root2)))))

quadratic-formula(a, b, c) def= (root1, root2)
   where minusb = - 0 b
         radical = sqrt (- (* b b) (* 4 (* a c))))
         divisor = * 2 a
         root1 = / (+ minusb radical) divisor
         root2 = / (- minusb radical) divisor

quadratic-2  ==                               # a b c => [root1 root2 ]
   [ [ [ pop pop 2 * ]                        # divisor
       [ pop 0 swap - ]                       # minusb
       [ swap dup * rollup * 4 * - sqrt ] ]   # radical
     [i] map ]
   ternary i
   [ [ [ + swap / ]                           # root1
       [ - swap / ] ]                         # root2
     [i] map ]
  ternary.

The difference that stands out most is that none of the variables are explicitly named -- the names on the right are only comments. These comments are not equivalent to using names in the code -- what if they were wrong? The variables have to be referred to by keeping track of their position on the stack (which is what I was getting at in the reference to de Bruijn indices above). OK, it is possible to mitigate this problem by minimizing the size of the stack at any given time, but the risk of making an error is going to be larger for any given number of variables than it is in an equivalent program that uses names. Some proportion of those errors won't be found by testing. For a large program, that is likely to add up to an unacceptable risk.

[Edit: corrected "0 - b" to "- 0 b"]

In Factor, the quadratic formula is a non-problem. Just embed a domain-specific language for infix arithmetic and be done with it. It is very easy to write such a language that compiles down to concatenative code which then runs through Factor's native compiler. It already exists; see contrib/algebra/ in the distribution.

About the rate of errors being higher; my experience is not conclusive either way. I have found that the time going from noting a bug, to resolving it, to fixing it is very short in Factor. Unit tests flow easily, and debugging is pure joy with tools like our GUI inspector, single-stepper, various tracing tools, and of course, the grand-daddy of them all, the REPL. Many stack errors can be caught statically, using the stack effect inferencer.

I will admit, I have had a few several-day-long debugging marathons, however these had nothing to do with the stack, but issues such as buggy relocation in the compiler's code generator leading to clobbered code, or incorrect rewriting rules in the optimizer, and so on.

On the other hand, the other large piece of software I maintain, jEdit is written in Java. Like all Java software, it is a pain to maintain, and I always find new, mysterious bugs that are almost impossible to resolve, due to Java's non-interactive, static nature, and laborous edit/compile/run cycle.

And then you're not writing the arithmetic in a concatenative language. The example just happened to use arithmetic, though; the criticisms (e.g. about the potential error-proneness of the stack implicitly introducing variables without names) are not specific to that case.

It is very easy to write such a language that compiles down to concatenative code which then runs through Factor's native compiler.

Right -- I didn't say that concatenative languages aren't suitable as intermediate languages (although I wonder why you would use them in preference to a register-based IL, if you're targetting a register-based machine).

I have found that the time going from noting a bug, to resolving it, to fixing it is very short in Factor.

And in applicative languages as well, usually, if you notice the bug.

... jEdit is written in Java. Like all Java software, it is a pain to maintain, ...

Did I inadvertently defend Java?

Maybe it could function this way, as something easier to reason about than a register-based machine?

It seems there are a few orthogonal ways languages like Forth differ from e.g. Scheme:
* postfix vs. prefix
* stack-manipulation vs. named-variables
* eschewing of parentheses (though they might make for greater readability)

Scheme & other languages (C) can of course use a stack; they just address it differently.

[Anyone use a postfix language that uses named variables?]

Just embed a domain-specific language for infix arithmetic and be done with it.

And then you're not writing the arithmetic in a concatenative language.

Let's try rewriting that a little bit differently...

Just use monads (like an embeded domain-specific language) for sequencing side-effects and be done with it.

And then you're not writing functions in a pure language.

I agree. The corollary to your point about names is the presence of all the names in the Joy code which have nothing to do with the problem domain, like pop, swap, dup, and rollup. That's a classic sign of a low-level language (think of assembler).

Also, in concatenative languages, the programmer depends heavily on abstractions which the language doesn't enforce or even know about: every time you use pop, you're making an assumption about what's on the stack, but that assumption could be violated by unrelated code, as though an expression such as:

(let ((x 33))
  (foo)
  x)

...could return a value other than 33, if foo had a bug. This kind of non-local side effect for bugs is reminiscent of something like a pointer error. In other contexts, this sort of behavior is called "unsafe": that an abstraction is not protected from unauthorized outside interference.

In the concatenative context, you can play language lawyer and claim that since the language doesn't have the notion of a local binding, nothing is being violated. However, that would only be a good argument if programmers didn't need to rely heavily on faking local bindings in concatenative languages.

The corollary to your point about names is the presence of all the names in the Joy code which have nothing to do with the problem domain, like pop, swap, dup, and rollup

What about names like let, labels, multiple-value-bind and setf in Common Lisp programs? They also have nothing to do with the problem domain. Is CL low level, "like assembler"?

This kind of non-local side effect for bugs is reminiscent of something like a pointer error. In other contexts, this sort of behavior is called "unsafe": that an abstraction is not protected from unauthorized outside interference.

Factor has a stack effect inferencer that could be used to check that foo does in fact return the right values.

Suppose you write a function that takes a mutable object as input, and it violates its contract by mutating the object into an incorrect state; how is this any different from a function with an invalid stack effect? Are you going to argue in favor of purely-functional languages, which are solely the domain of academics?

What about names like let, labels, multiple-value-bind and setf in Common Lisp programs? They also have nothing to do with the problem domain. Is CL low level, "like assembler"?

First, I'm referring partly to frequency of occurrence. When you look at a piece of code, what stands out? If you see very few names that relate to the problem domain, and many names that relate to some abstraction in the programming language, that's a problem for the comprehensibility of the code.

Second, many of the names you mentioned are used to introduce names that are relevant to the problem domain. As such, they're still more meaningful to the problem being solved than stack operators are.

Even concatenative languages acknowledge that names are important, since they all support global names. What logic is used to justify the idea that you can only have global names? It boils down to something like "because it's easy to implement a language that way, and possible to get away with it and work around it". That's not a good argument from the language user's perspective. It might explain why you, as an implementor of such a language, are enthusiastic about them, though.

Factor has a stack effect inferencer that could be used to check that foo does in fact return the right values.

Suppose you write a function that takes a mutable object as input, and it violates its contract by mutating the object into an incorrect state; how is this any different from a function with an invalid stack effect?

It's different in that the caller knows that he's passed a mutable object to that function — it's not a case where an essentially unrelated function can destroy an abstraction which it has no connection to.

However, it's true that side effects are a major cause of problems, which is why the most powerful languages provide ways to control side effects. Having all programs depend implicitly on a stack which can be directly side-effected by any function is a step backwards in this respect.

Are you going to argue in favor of purely-functional languages, which are solely the domain of academics?

First, it's demonstrably false that they are "solely the domain of academics". Simple refutation: Erlang is used to run telecom switches, and it's a purely functional language. There are plenty more examples where that came from.

Second, while I wouldn't use purely functional languages in every context, I do use languages that encourage and support the controlling of side effects, and I do write code which avoids side effects for the most part. This has numerous provable benefits — if you want to start arguing against them, I'd point you here.

Lest I be taken as entirely negative about concatenative languages, I should mention that I've written systems in Forth, experimented with Joy, and written a toy Joy interpreter. I think they're very interesting languages, and can be fun and useful in certain kinds of applications, but I don't think that those languages can support the kind of claims you seem to want to make. If Factor can support such claims, that would be interesting, but you're not going to convince many people by blustering about it and making over-the-top criticisms of other, proven languages.

What logic is used to justify the idea that you can only have global names?

I'm not sure what logic is used, because I don't follow it. Factor has variables and nested namespaces and scope. Did you even bother to look at it?

Could be used? That implies that this is not something which happens automatically, to transparently guarantee the safety of unrelated "bindings" (or whatever you want to call them in a concatenative language). If that's the case, then this creates an area that the user has to worry about, which would otherwise not need to be worried about. It's hard to see how that would be a benefit.

I could easily add some tools to do this automatically for every new word definition.

Lest I be taken as entirely negative about concatenative languages, I should mention that I've written systems in Forth, experimented with Joy, and written a toy Joy interpreter.

So your only experience with concatenative languages is having written a toy Joy interpreter? If I write a toy interpreter for a simple applicative language, like Scheme, then notice that this toy interpreter is hard to work with, should I conclude that applicative languages on the whole are useless?

If Factor can support such claims, that would be interesting, but you're not going to convince many people by blustering about it and making over-the-top criticisms of other, proven languages.

Show where I have been "blustering" and making over-the-top criticisms.

I'm not sure what logic is used, because I don't follow it. Factor has variables and nested namespaces and scope. Did you even bother to look at it?

Well, we need to be clear about whether we're discussing actual concatenative languages in general, or Factor in particular. The discussion started out more generally. I've looked briefly at Factor, some months ago, but I didn't find that it sufficiently addressed the sort of concerns I've mentioned. Since it's still under development, it'll be interesting to see how it turns out over time.

Regarding my point about global names, I didn't state that clearly. What I was referring to is that these languages demonstrate that they recognize that supporting safe bindings between names and values is important, but within individual procedures, they don't provide such a feature, i.e. temporary name/value bindings that can be relied on for the life of a procedure. Does Factor provide such a feature?

I could easily add some tools to do this automatically for every new word definition.

Lest I be taken as entirely negative about concatenative languages, I should mention that I've written systems in Forth, experimented with Joy, and written a toy Joy interpreter.

So your only experience with concatenative languages is having written a toy Joy interpreter?

Show where I have been "blustering" and making over-the-top criticisms.

This is a richer level of functionality than offered by most languages discussed on this web site

one could even conclude that applicative languages are totally non-productive, and not even capable of implementing their own optimizing native compilers.

Are you going to argue in favor of purely-functional languages, which are solely the domain of academics?

I've already responded to specific cases, but some of the quotes in question are as follows:

You see, the very first post to this thread was your disparaging claim that concatenative languages are unsuitable for developing applications. Instead of discussing the Kont language, you decided to troll instead. You don't even bother refuting my points, and instead draw blanket conclusions and generalizations based on your limited experience with Joy and Forth.

I know you wouldn't be very happy if I went and jumped into threads where discussion of ML and Haskell is taking place, claiming that static typing is overly restrictive. So why do you do the equivalent thing here?

You see, the very first post to this thread was your disparaging claim that concatenative languages are unsuitable for developing applications.

I responded to another post which made a point which I agreed with. I said concatenative languages show a particular sign of being a low-level language. I believe that's true, and I've defended that in exchanges with others. I'm not even sure if you disagree, since you haven't addressed my points, but I assume from your general reaction that you disagree.

Instead of discussing the Kont language, you decided to troll instead.

I'm not trolling. However, I noticed that instead of discussing the Kont language yourself, you decided to talk about Factor. I'm having difficulty discerning the rules you think I should be following here.

You don't even bother refuting my points

Which points are those? Afaict, I've responded to every one of your substantive points. I suggest you reread the thread more carefully.

and instead draw blanket conclusions and generalizations based on your limited experience with Joy and Forth.

You're free to dispute my points, with rational arguments, but lashing out at academia, applicative languages, "most languages discussed on this web site", and research languages doesn't qualify. It's particularly ironic given that your own language would, by some definitions, qualify as a research language.

I know you wouldn't be very happy if I went and jumped into threads where discussion of ML and Haskell is taking place, claiming that static typing is overly restrictive.

Heh. Your assumption is incorrect, assuming that what you have to say has more basis in rational argument than your comments on those languages so far.

So why do you do the equivalent thing here?

This is a forum for discussion of programming languages. I'm interested in the semantics of programming languages, and among other things, how those semantics relate to the user experience of programming. My original post in this thread wasn't intended as a critique of Kont specifically (and besides, Brian Mastenbrook has already heard my opinion on this issue). Rather, it was an attempt to characterize one of the semantic issues that distinguishes concatenative languages from languages with name-based procedure-local abstractions (a.k.a. local variables). I believe that this issue is one of the factors which underlies a common negative user reaction to these languages. As someone interested in concatenative languages, I would think you might have some interesting thoughts on the matter, but for whatever reason, you haven't chosen to offer those yet. Other people have, though, which is the reason I'm here.

Let me reiterate those substatiative points, if you don't understand Slava (even though he's being perfectly clear). First, I'd just like to remind you that you won't convince Slava or me to stop using concatenative languages because we're perfectly comfortable with them, no matter how low-level you prove them to be.


I said concatenative languages show a particular sign of being a low-level language.

I don't think concatenative languages are more low-level. They just handle things differently, in a way that other languages happen to use as an intermediate form. This does not mean at all that it is worse, just different. If a C compiler uses an intermediate form that is single assignment only, does that mean that C higher-level than any kind of single assignment form? Of course not.


Rather, it was an attempt to characterize one of the semantic issues that distinguishes concatenative languages from languages with name-based procedure-local abstractions (a.k.a. local variables). I believe that this issue is one of the factors which underlies a common negative user reaction to these languages.

How are local variables abstractions? Could you explain that? How are they more abstract and flexible than stack shuffling operators?

First, I'd just like to remind you that you won't convince Slava or me to stop using concatenative languages because we're perfectly comfortable with them, no matter how low-level you prove them to be.

You sound almost as though you're nervous I might succeed! ;) But I really have no interest in changing your choice of programming language. No, the point is to understand more about programming language features and their consequences. Of course, this can lead to changing preferences, programming style, etc — mine have certainly changed a great deal over the years. But more importantly, a good understanding of PL features and how they affect programs and programming can make you a better programmer in any language. It can also help in assessing the appropriateness of a language in a given situation, and help with cutting through hype about particular programming languages.

I don't think concatenative languages are more low-level. They just handle things differently, in a way that other languages happen to use as an intermediate form. This does not mean at all that it is worse, just different.

That particular issue is different in a way that's more low-level. This has been covered in a few posts, and connected to Alan Perlis' observation that low-level implies that "programs require attention to the irrelevant". The irrelevant thing in this case is direct stack manipulation, which you've acknowledged: "there are only a few cases where the stack really matters". You've suggested elsewhere that the same is true of lexical names, but I've addressed this in my response to your last point below.

If a C compiler uses an intermediate form that is single assignment only, does that mean that C higher-level than any kind of single assignment form? Of course not.

C code is certainly usually higher-level than any internal single-assignment form it's likely to be compiled to. The way you can tell that is to look at the extra operations that are being performed in the single-assignment code, to deal with the constraints of single assignment — the fact that those extra operations aren't necessary in the C source indicates that they are irrelevant to the expression of the original problem, and indicates that the single-assignment form is lower level.

If your concern is with generalization, i.e. drawing conclusions about "...any kind of single assignment form", that's not what I'm doing. I'm looking at specific languages that regularly embed direct stack manipulation operators in their code, and concluding that this is a lower-level way of dealing with abstraction over values than using names, in most cases.

How are local variables abstractions? Could you explain that? How are they more abstract and flexible than stack shuffling operators?

A local variable is an abstraction in the same way that any name is an abstraction. The name refers to some other thing, and we can use the name and manipulate whatever it refers to without knowing which specific thing it refers to. That's abstraction.

When you push a value on a stack and later apply some operation to that value, that's also a kind of abstraction. However, not all abstractions are equal. Direct stack manipulation alone doesn't scale very well, as every concatenative programmer already knows. As procedures get bigger, keeping track of values via stack manipulation gets more complex. Early on in the thread, we were reminded that "any time you do lots of stack manipulations is a sign that you need to refactor." And what do you do when you refactor? You create names, which (implemented properly) are more scalable, safer abstractions than storing values on a stack.

So one question is, if names are so useful and important when code scales up past a single procedure, mightn't they be useful locally, within a procedure? And of course, many languages demonstrate that they are.

One of the critical features of names is that they can actually serve two purposes:

1. A name acts as a way to refer to a value, i.e. a name is a "reference", or can be said to "denote" some value.
2. A name can provide information to programmers about the value, or its role in the computation, i.e. a name can also have a "sense" or "connotation".

This why we try to pick informative names, and why the expression you gave elsewhere in this thread was compiling dataflow optimize linearize simplify generate, instead of a b c d e f. Defined appropriately, both expressions could have the exact same computational effect, but one is much more meaningful to us than the other. When we omit names from our code, we're omitting one of the only things which connects the code to the problem it's solving, and that's something that should be done thoughtfully. If a language commonly forces you to omit names, that's something worth taking a close look at. Using a stack to abstract values hardly ever serves the second purpose above.

However, naming every value isn't necessary or appropriate, either. In the expression quoted above, it's not necessary to name the intermediate values, and most languages support this sort of omission of names in one form or another.

But omitting names is one thing; replacing them with operators that manipulate an abstraction (the stack) that's not otherwise directly relevant to the computation is something else entirely. Using stack shuffling operators is a low-level detail no matter how you look at it, and wherever this replaces the use of names which might be informative, you have a double loss of the program's ability to express its algorithm to the human reader.

In general, it's difficult to argue that expressing most problems in terms of an essentially LIFO stack is an approach that makes sense in and of itself. The most convincing arguments, I think, have to do with the benefits of that approach to language implementation: by pushing some of the work of arranging the abstraction mechanism onto the user, the job of the language implementation is simplified, which can have various benefits.

I'm sure there's plenty in what I've written above for a concatenative fan to object to. Keep in mind I've programmed in these languages, and I'm familiar with the arguments. I could make them myself: you don't need local names because factoring keeps procedures small enough to be tractable; non-local names used in conjunction with the stack locally works out very well most of the time; languages which force you to name e.g. function return values just to be able to rearrange them to pass to another function are similarly obscuring the solution to the problem; etc. etc. My main interest is in characterizing the differences in a more specific way than just saying something along the lines of "I don't like this", or "I think this is a fun way to program". There are obviously differences, but if we can't describe their effect clearly other than just listing the technical features, that implies a gap in our understanding.

In #comment-8723, Anton wrote:

So one question is, if names are so useful and important when code scales up past a single procedure, mightn't they be useful locally, within a procedure? And of course, many languages demonstrate that they are.

I'm not sure if the following quote supports your contention. I ran into it while skimming through Forth Sorts Fruit Down Under by Paul Frenger in ACM SIGPLAN Notices, vol. 40, no. 8, aug 2005 (not yet online):

The CF [ColdForth] manual has other interesting chapters to describe its features: numbers/parameters (CF supports local variables via stack frames), the memory manager, I/O handling (mostly for accessing files), strings, object-oriented extensions, TCP/IP capability and the multi-tasker, for example.

Even concatenative languages acknowledge that names are important, since they all support global names. What logic is used to justify the idea that you can only have global names? It boils down to something like "because it's easy to implement a language that way, and possible to get away with it and work around it". That's not a good argument from the language user's perspective. It might explain why you, as an implementor of such a language, are enthusiastic about them, though.

Aside from the fact that several concatenative languages do actually support local variables, the reason they're frowned upon is because in most cases they are an impediment to proper factoring. In a great deal of applicative code, the variables are simply assigned useless placeholder names. This should indicate something to you: most of the time, those names are unnecessary.

However, it's true that side effects are a major cause of problems, which is why the most powerful languages provide ways to control side effects.

Believe it or not, not everyone considers Haskell and friends to be the pinnacle of language design or expressive power. It's worrying to me that this claim of "most powerful" is accepted here essentially on faith. How do you define power? The APL dialects and derivatives, for example, are all much more expressive than any purely functional language. What do you think of tacit programming in J?

Simple refutation: Erlang is used to run telecom switches, and it's a purely functional language.

Erlang is not purely functional (ets, dets, mnesia, process dictionary, the list goes on).

If Factor can support such claims, that would be interesting, but you're not going to convince many people by blustering about it and making over-the-top criticisms of other, proven languages.

The original poster likened concatenative programming to "writing a Turing machine program, or directly in the lambda calculus using de Bruijn indices." Perhaps you should reconsider whose claims are 'over the top'.

Aside from the fact that several concatenative languages do actually support local variables

the reason they're frowned upon is because in most cases they are an impediment to proper factoring.

In a great deal of applicative code, the variables are simply assigned useless placeholder names. This should indicate something to you: most of the time, those names are unnecessary.

Believe it or not, not everyone considers Haskell and friends to be the pinnacle of language design or expressive power.

It's worrying to me that this claim of "most powerful" is accepted here essentially on faith. How do you define power?

The APL dialects and derivatives, for example, are all much more expressive than any purely functional language. What do you think of tacit programming in J?

I consider tacit programming — which has strong similarities to point-free style — to be higher-level than direct stack manipulation, for the reasons stated elsewhere in this thread. However, all of these things have pros and cons. The cons tend to have to do with being more difficult to reason about, especially as expressions scale up. Ideally, a language should be able to support a variety of styles, so that the appropriate one can be picked in a given situation. Of all of these, I don't see direct stack manipulation as one that's likely to be the best choice in most situations.

On the subject of scaling up expressions, the traditional concatenative answer to that is that you should factor larger expressions into multiple words. However, that means you're relying on names for abstraction again, just on a scale greater than the local procedure. How does this reconcile with the idea that using local names is an impediment to refactoring?

Erlang is not purely functional (ets, dets, mnesia, process dictionary, the list goes on).

The original poster likened concatenative programming to "writing a Turing machine program, or directly in the lambda calculus using de Bruijn indices." Perhaps you should reconsider whose claims are 'over the top'.

Aside from the fact that several concatenative languages do actually support local variables, the reason they're frowned upon is because in most cases they are an impediment to proper factoring. In a great deal of applicative code, the variables are simply assigned useless placeholder names. This should indicate something to you: most of the time, those names are unnecessary.

Programmers, and typical programming styles in various languages, differ considerably in how many named intermediate variables they use (personally I find the number of intermediates in the above Scheme code a bit excessive). But it's generally agreed, I think, that introducing variables with useless names is bad style. In functional-applicative languages, it's almost always possible to avoid this. The need for temporaries with useless names, e.g. loop indices, in imperative-applicative languages (some more than others) is indeed a valid criticism of them.

The need for temporaries with useless names, e.g. loop indices, in imperative-applicative languages (some more than others) is indeed a valid criticism of them.

I disagree that temporaries have "useless names". Loop indices may not be referenced other than as a control structure, but part of the essence of reasoning within an imperative paradigm is knowing the current state. Not being able to name part of that state is what I would consider to be a weakness. The only useless names I can think of is for function arguments that aren't used. And in better languages, you don't actually have to name those. ;>

Functional languages can "name part of the state". Do you consider not being able to not name part of the state a weakness? The only way to avoid it in many imperative languages would require programming in a dramatically different style than the the language supports.

I agree. The corollary to your point about names is the presence of all the names in the Joy code which have nothing to do with the problem domain, like pop, swap, dup, and rollup. That's a classic sign of a low-level language (think of assembler).

Are the stack manipulation functions that you mention (pop, swap, dup, etc.) a sign of a low-level language or a linear language (like Linear Lisp)? Or are all linear langauges low-level by definition?

Also, in concatenative languages, the programmer depends heavily on abstractions which the language doesn't enforce or even know about: every time you use pop, you're making an assumption about what's on the stack, but that assumption could be violated by unrelated code

That sounds like a plea for static typing.

...every time you use pop, you're making an assumption about what's on the stack, but that assumption could be violated by unrelated code

Is it really that much different from the applicative language example? If your function takes three integers, how do you know you're calling it with the arguments in the correct order? Especially in the presence of macros?

(apply quadratic-formula '(1 0 -4))
(apply quadratic-formula (reverse '(1 0 -4))

For better reference to linear lanugages (which also mentions the quadradic formula!) see Linear Logic and Permutation Stacks--The Forth Shall Be First

Are the stack manipulation functions that you mention (pop, swap, dup, etc.) a sign of a low-level language or a linear language (like Linear Lisp)? Or are all linear langauges low-level by definition?

I would say that Linear Lisp is certainly lower-level than ordinary Lisp, yes. I'll admit I can't give a formal definition of "low-level" off the top of my head, but I'd be interested to hear (reasoned) arguments about how something like Linear Lisp or the concatenative languages are not lower-level.

That sounds like a plea for static typing.

Yes, it is. The question is what the costs of introducing it are. The costs of introducing a safe name abstraction are negative. The costs of introducing static typing are positive, and arguably not insignificant. In the static typing case, I find the costs high enough that I can easily justify using it in some cases, and avoiding it in others. In the case of relying primarily on direct interaction with a stack to store values, I can easily justify avoiding that in most cases.

Is it really that much different from the applicative language example? If your function takes three integers, how do you know you're calling it with the arguments in the correct order?

It's different at least in the sense that that's a local effect: the error is confined to the interface between the caller and the callee, and doesn't compromise unrelated abstractions elsewhere in the program.

I'm not saying that any language with named bindings solves all such problems, I'm just saying that there's a spectrum of safety and levels of abstraction, and that a language with named bindings which can make some guarantees about those bindings is both safer and higher-level than a language that doesn't have those features.

I would say that Linear Lisp is certainly lower-level than ordinary Lisp, yes. I'll admit I can't give a formal definition of "low-level" off the top of my head, but I'd be interested to hear (reasoned) arguments about how something like Linear Lisp or the concatenative languages are not lower-level.

Well I don't know if I can define "low-level" either, but of the cuff, I'd point to higher order functions and a clean algebra of programs as indicators of higher-levelness. Maybe the assembly language remark was aimed more at Forth and less at something like Joy?

Well I don't know if I can define "low-level" either, but of the cuff, I'd point to higher order functions and a clean algebra of programs as indicators of higher-levelness. Maybe the assembly language remark was aimed more at Forth and less at something like Joy?

I agree that HOFs and algebraic compability are high-level indicators. That moves a language like Joy up the spectrum I mentioned, but it doesn't necessarily make up for all of its problems. The Joy code sample near the beginning of this thread provides an example of low-level code, by my definition and Alan Perlis'.

Though I don't particularly like that Joy code, concatenative languages do provide both of those things in your definition of high level languages. HOFs are ubiquitous in Joy, Factor and Kont, renamed combinators. They are used more frequently than HOFs in any applicative language I've seen. As for theory, there's tons of concatenative theory. Check out the Joy and Factor websites for more details, but really, there's tons of this stuff.

I'll admit I can't give a formal definition of "low-level" off the top of my head

A programming language is low level when its programs require attention to the irrelevant.

Although I don't think it's really completely correct to label languages high or low level. At most you can say that writing in a given language generally results in high or low level code.

Anyway, by that definition, concatenative code is low-level because it forces you to write your solution in terms of a stack, despite the fact that there's no stack in your problem specification.

Likewise, monads result in low-level code, because you're forced to think about category theory just to print "hello" :-)

I agree with everything you wrote. :)

In the concatenative context, you can play language lawyer and claim that since the language doesn't have the notion of a local binding, nothing is being violated. However, that would only be a good argument if programmers didn't need to rely heavily on faking local bindings in concatenative languages.

Sounds a lot like type errors in dynamically checked languages... But now I guess I'm the one trolling... ;)

Indeed, (let ((x 33)) (foo) x) can return something other than 33; specifically, it can return ⊥ if foo does not terminate. Likewise, executing pop on an empty stack likewise produces ⊥. This interpretation depends on the view that the words of concatenative languages are functions from sequences to other sequences, which is Manfred's fundamental insight.

Joy is different from other concatenative languages because it is functional: it is impossible to make any changes of state except through the file functions (the fact that read, write, etc. do not pop the file object off the stack constitutes the concatenative analogue of the I/O monad). Global words can be defined at read time, but cannot be changed at run time; thus they are analogous to function definitions rather than global variables.

Indeed, (let ((x 33)) (foo) x) can return something other than 33; specifically, it can return ⊥ if foo does not terminate.

True, but irrelevant, since this problem applies to all useful general-purpose languages, so doesn't affect a relative comparison of features between languages.

Likewise, executing pop on an empty stack likewise produces ⊥

Empty stack is a special case that's not as problematic, because it can be detected and flagged when it happens. The cases that are problematic are when the stack is not empty, but is out of sync with the program's expectations. That's when the programmer's implicit abstractions are violated.

The cases that are problematic are when the stack is not empty, but is out of sync with the program's expectations.

Is that a problem caused by concatenativityness (!), or by dynamicism? If your language allows you to push 1 or 2 things on the stack, depending on a conditional, then I'll agree it has the potential to become a mess. But it seems like you should be able to prevent getting "out-of-sync" with static analysis. Like requiring both branches of an "if" statement have the same stack effect. Am I missing something?

The Factor language apparently includes a stack effect inference tool which performs such analysis. The documentation mentions combining unit testing with stack effect inferencing to check the stack effect of procedures (words). This seems like a lot of trouble to go to to achieve a kind of safety that other languages get for free.

I'm not saying that this issue alone makes concatenative languages unfit for human consumption. However, I think the negative reaction to the tractability of these languages that's been expressed by some posters in this thread is not an uncommon one, and I've attempted to identify a couple of the semantic issues which underly this reaction. In this particular case, I'm saying that even if you get past the lack of procedure-local name/value bindings, that the approach these languages take to local value abstraction is less safe and requires more care than languages with name-based local abstraction.

Likewise, executing pop on an empty stack likewise produces ⊥



Empty stack is a special case that's not as problematic, because it can be detected and flagged when it happens. The cases that are problematic are when the stack is not empty, but is out of sync with the program's expectations. That's when the programmer's implicit abstractions are violated.


There are no problems at all about empty stacks. Factor solves the stack underflow problem by mprotecting (or something like that) the memory directly underneath the stack, triggering a segfault if there's underflow. Should this happen, the segfault can be caught like any other exception, and it the toplevel of the repl, it's caught automatically and printed out, also like any other exception. All this stuff about ⊥ is useless outside of research. An infinite loop has a very different outcome than stack underflow.

Actually I think the more important point is why you should have to use six of these (pop, swap, dup, rollup, map, ternary) in such a simple example.

As long as we're alread discussing it, we might as well mention the original thread that spawned the quadratic formula article. Also note a previous discussion on point-free programming on LtU. And some might be interested in Pointless Haskell.

Here is another example of non-local bugs: a badly-formed HTML post in a naive weblog system can break the whole page.

I guess you meant that though it's absolutely possible to have a PL in which the value of (let ((x 33)) (foo) x) is not 33 (e.g., because of effects - exceptions, nontermination, continuations, etc.), such a PL is less safe than reasonable?

No, I meant that assuming normal completion of foo, one can rely on a value of 33 being returned from that expression. If foo has an exception, that's fine, and presumably happens for a reason. The case I'm pointing to as undesirable is if the expression ends up returning 42 or the string "gotcha" instead, i.e. the program produces an incorrect result.

Here is another example of non-local bugs: a badly-formed HTML post in a naive weblog system can break the whole page.

there's nothing to stop you (or rather, a language implementer) from labelling items on the stack. in otuto you'd have something like

{ quadratic | a b c } => 
  { roots ~ b  sqrt - * 4 * a c * b b  * 2 a }
where
  { roots | x y z } => { / + x y z  / - x y z }

which seems clear enough, apart from the RPN.

disclaimer - i can't remember the exact details of otuto v1, and v2 is stalled until i gain enough patience to return to the uml tool (i'm trying to implement it in c++ for various (vaguely financial) reasons).

Once you add names then the code is no longer concatenative. For example if you were to add names for items on the stack as an extension of the Joy language, then each quotation would need a pointer to its lexical scope. You can no longer compose functions by concatenating lists of words because the two quotations may come from different lexical environments.

[edit: otuto is very interesting, by the way. I hadn't realized what language your example was from.]

If quotations were first-class types in Joy, rather than lists of words, they could hold a pointer to their lexical context. Appending two quotations could be implemented with a 'cord' data structure, that simply holds references to both quotations, and when evaluated, iterates over the first one, followed by the second one, in each case using the correct lexical context. Concatenative languages (and Lisp, where lambdas are first-class too) are not all about cons cells and lists.

For a simple example suppose we have a Joy-like language plus an operator 'let' that takes a value, a quoted symbol, and another quotation which is evaluated in an environment where that symbol is bound to the value.

2 [x] [x 1 +] let

1 [x] [[x]] let   2 [x] [[x +]] let   concat

[x x +]

[x x +] i

there is no lexical scope during evaluation. that syntax is a very simple "template" for rewriting the stack (actually, stacks). so you'd define dup as:

{ dup | x } => { | x x }

there's some syntactic sugar involving implicit quoting that means you can write that as

{ dup | x } => { x x } 

but that's beside the point. all that the otuto definitions describe is how you rearrange the stack(s). you could implement them by cross-compiling to an intermediate representation without variable names (using swap, roll etc etc) (i believe - i've never bothered to prove it, but i would be amazed if it were not true).

i'm not 100% convinced i understand what concatenative is, so i can't say otuto is concatenative, but i'm pretty sure that those variable names are just sugar. a long time back, when i mentioned this on the joy email list, someone added something similar to another language there.

As I understand it, if a language is concatenative then functions are sequences of operators where you can take any function and split it at any point and you have two valid functions, or you can join two functions and have a valid function. I'm not sure what it would mean to split or join functions in otuto, since they are rules with 4 separate sections, not simple sequences of operations.

well, the rules are restricted - they always match a single value on the left hand stack. so the top value on that stack can be interpreted as the current instruction. if you then take the right hand stack as "values" then you can think of a rule as saying how to apply the intruction (top of the left stack) to the values.

ok, now if you continue with that, a definition like:

{ foo | a } => { bar baz | a a }

is equivalent to defining foo as bar baz dup in a concatenative language.

now if you accept, as i argued above, that the variables are just syntactic sugar, then that implies, i think, that there is a simple mapping from otuto to concatenative languages.

(this breaks down with meta-programming, though, since you can change the assumptions made above).

A language in which the concatenation of programs denote the composition of functions has been called a concatenative language. I first heard this terminology from Billy Tanksley. -- Manfred von Thun

otuto is concatenative. so is XY.

Here's one version of quadratic in that language, which uses names to similar effect (that is, to map items from the stack to multiple locations in the body of the code):

; quadratic { [a b c] b -: a c * 4 * b 2 ^ -. .5 ^ [1 -1] * + a 2 * % } ;

regarding your proposal for cross-compilation, i think it would be sufficient to compile programs like quadratic, in which names are used to map items from the stack to multiple locations, to programs which consist of an initial reordering of items on the stack, followed by code which is name-free.

Billy Tanksley has suggested a notation (supported in XY) in which an initial "shuffle-pattern" is followed by name-free code. For example, compile

{ [a b c] a b * a c * + }

to

abc--abac * [*] dip +

[edited to show an example of compilation from pattern-notation to shuffle-notation]

Say, in imperative PLs one can concatenate statements (usually using ';'), and quite often "imperative" means working in some compound monad. Well, I might understand "composition of functions" a bit wrongly...

I don't think squinting is necessary at all. In fact, lately I've been thinking that there might be a benefit for newbies by writing a monad tutorial using a language like Joy. Subroutines (quotations) in Joy are lists of functions and you interpret them by folding in a 'compose' and applying to a stack...

fold compose id [1 4 dup * +]

Replace 'compose' with 'bind' for your favorite monad, and I think you might be on your way to removing much of the mystery behing monads (or at least you've given them an opportunity to see monads that aren't tied up in Haskell syntax and type-classes).

They recently made much more sense to me when I combined the two pieces of information that monads are (1) an algebraic structure that (2) forces a particular evaluation order. None of the tutorials on the web I have read, even I think some Simon Peyton-Jones stuff really mention both of those facts, then illustrate with reference to examples like lists with mapping, and factorial, which are familiar functions that, ignoring associativity information, in their common recursive definitions have a defined evaluation order.

I don't know whether otutu as a whole is applicative or a hybrid, but the above code is definitely applicative. (RPN vs prefix vs infix is a separate, and much less significant, issue.)

The code is not applicative, it's just reverse RPN (just polish notation) and it uses named variables. There is still a stack.

I consider concatenative languages suitable for high-level programming, in fact I am the lead developer of the Factor programming language. As always, the burden of bridging the gap between the programmer and the language lies squarely on the development tools at one's disposal, and the simplicity of concatenative languages allows one to develop such tools more easily than with other languages.

A meta-circular interpreter is a page of code in Factor, and it is not an academic exercise; it is used to implement a single-stepper. I'd like to see a single-stepper in another language that is equally clear.

There is a static stack effect inferencer tool, also used by the compiler. The compiler takes maximal advantage of the simple semantics to implement the concatenative equivalent of "lambda lifting", and various other optimizations such as partial evaluation.

I'm not sure what you mean by "How can you build reusable encapsulated abstractions?". If you look at Factor's library, you will see a very high degree of abstraction and code reuse. There is no "boilerplate" code.

Re: "writing a Turing machine program"; after working with Factor's libraries for sequences and mathematics, going back to a language like Java with annoyingly hand-coded boilerplate loops seems more like a Turing machine.

Your emphasis on the word "seem" suggests that you don't believe that concatenative languages are used to develop non-trivial applications. Well, notwithstanding the clear fact that there is enough commercial demand to keep several Forth vendors in business, Factor has an HTTP server with a continuation-based web framework, a GUI toolkit-in-progress, various development tools, and more.

This is a richer level of functionality than offered by most languages discussed on this web site, so ironically, one could even conclude that applicative languages are totally non-productive, and not even capable of implementing their own optimizing native compilers.

While it's true that there are few complex concatenative languages, there are plenty of equally simple applicative ones. I'm not particularly interested in comparing, say, Factor with Java; I'm interested in the effects of concatenative vs. applicative semantics for otherwise comparable languages.

[...] an HTTP server with a continuation-based web framework, a GUI toolkit-in-progress, various development tools, and more [...] is a richer level of functionality than offered by most languages discussed on this web site

Even though this web site disproportionately discusses research languages and prototype language implementations, still I think that assertion is very likely false. And also beside the point, since the maturity of language implementations is not the topic of discussion.

... one could even conclude that applicative languages are totally non-productive, and not even capable of implementing their own optimizing native compilers.

This is just trolling.

Even though this web site disproportionately discusses research languages and prototype language implementations, still I think that assertion is very likely false. And also beside the point, since the maturity of language implementations is not the topic of discussion.

"Research language" is a euphemism for "useless language". I'm really only interested in practical concerns. I write code, and I like to write stable code quickly, and I find that concatenative languages let me do this just as easily as applicative ones, with the additional advatange that writing tools is easier. You can discuss semantics, static type systems, weakly final coalgebras and other academic concerns until you are blue in the face, but it will not change the fact that for me, thinking in terms of a stack is not a problem.

You can discuss semantics, static type systems, weakly final coalgebras and other academic concerns until you are blue in the face, but it will not change the fact that for me, thinking in terms of a stack is not a problem.

Perhaps. However, the next person who has to deal with your code may indeed have a problem. I could truthfully say "for me, dealing with unrestricted pointers in C is not a problem", but the broader consequences of everyone holding that opinion are not pretty.

And where do you think the ideas for features in 'mainstream' languages come from?

While it's true that there are few complex concatenative languages, there are plenty of equally simple applicative ones. I'm not particularly interested in comparing, say, Factor with Java; I'm interested in the effects of concatenative vs. applicative semantics for otherwise comparable languages.

The point is, you can't do a lot of the stuff Factor does in an applicative language. I can't imagine Factor being applicative. The closest parallel I can find is Common Lisp, but there are many things about Factor that make it much better. One example that comes to mind is the word watch. The implementation isn't more than 3 or 4 lines, and what it does is it prints out the name of the word and the contents of the datastack when the word is called. It's been really useful for me and I've been able to get rid of all the debugging prints in my code. One time, I needed to see what was on the stack when leaving the word, so I made a new watch-after thing. It also only took 4 lines and not much thought. In Common Lisp, this would probably take the form of a new macro for when defining a function or macro, but that technique is less flexible. In Haskell or ML, making a debugging tool like this is even harder, involving complicated templating libraries.


Even though this web site disproportionately discusses research languages and prototype language implementations, still I think that assertion is very likely false. And also beside the point, since the maturity of language implementations is not the topic of discussion.

I, unlike Slava, am OK with research languages. They're good for research. As lothed as Slava is to admit it, Factor isn't really suitable for most applications yet. Of course, it is intended for use, but Factor's libraries aren't mature enough, especially crucial ones like the GUI library. Factor has a pretty good FFI, but that's not because it's concatenative. We really shouldn't discuss this, though, you're right.


This is just trolling. [about applicative languages being nonproductive]

Yeah

One example that comes to mind is the word watch. The implementation isn't more than 3 or 4 lines, and what it does is it prints out the name of the word and the contents of the datastack when the word is called.

Obviously, anything which involves dealing directly with the stack will be easiest in a language which gives you direct access to the stack. The question is how many things fall into this category, and whether they're worth the consequences of allowing direct manipulation of the stack, and in what situations. For example, Forth-like languages are often used in constrained embedded environments, in which case some of these concerns may be balanced by other advantages of these languages.

BTW, Common Lisp and many Schemes have something like a "trace" macro that provides similar functionality to the word watch, although the implementation of that is more than 3 or 4 lines. They usually print the incoming arguments and the return value, i.e. both the entry and exit from a traced function.

The question is how many things fall into this category, and whether they're worth the consequences of allowing direct manipulation of the stack, and in what situations.

That's actually a good point, but let me turn that question around: how many things fall into the category where you need lexically named variables to do certain things? I used to think many, but you can really do everything without them (but for a few circumstances, dynamically scoped variables help). The concatenative paradigm is not just a way to manipulate the stack directly, it's a whole different paradigm of programming where some things are more elegant and others less. After a while, it tends to feel like most things are more elegant, but from your perspective, everything will look awkward at first. For an example of something which comes out really great, here's the heart of the Factor compiler:

M: compound (compile)
    compiling dataflow optimize linearize simplify generate ;

Yes, I know that's a terrible argument, but I don't care. It's a reason I use Factor anyway. At this point, rather than feeling that concatenative languages are backwards, I feel like they're in the exact right order. They do reflect the order of evaluation, however important or unimportant that is.


For example, Forth-like languages are often used in constrained embedded environments, in which case some of these concerns may be balanced by other advantages of these languages.

Well, Factor isn't really that into constrained embedded environments, it's more for general programming, which can be done better because of it's abstraction capabilities, some of which rest on its being concatenative.


BTW, Common Lisp and many Schemes have something like a "trace" macro that provides similar functionality to the word watch, although the implementation of that is more than 3 or 4 lines. They usually print the incoming arguments and the return value, i.e. both the entry and exit from a traced function.

Not only does it take more code to do such a simple task but you have to alter the original code to do it. In Factor, at the repl, you can just enter one short line of code to watch a word (\ word-name watch). One thing about Factor that's great but unrelated to its concatenativity is that you can mutate stuff like word bodies, though you don't normally do this outside of debugging. There's probably an applicative language that does that.

how many things fall into the category where you need lexically named variables to do certain things?

I used to think many, but you can really do everything without them

The concatenative paradigm is not just a way to manipulate the stack directly, it's a whole different paradigm of programming where some things are more elegant and others less. After a while, it tends to feel like most things are more elegant, but from your perspective, everything will look awkward at first.

I implemented and maintained Forth programs for a couple of years. It was fun, but part of the reason I used Forth was because it was in a small, embedded-like control environment, where the alternatives were languages like C and assembler. The points I've raised are not about things being backwards or seeming awkward.

For an example of something which comes out really great, here's the heart of the Factor compiler:

M: compound (compile) compiling dataflow optimize linearize simplify generate ;

I agree, it's great when something works out in a way that seems intuitive. However, my experience is that different things can seem intuitive for different problems. If I wanted to write an expression like the above, I could do it quite easily in many higher-order functional languages, using a fold over a list of procedures, which could easily be made to look something like, e.g. in Scheme:

(concatenate input compiling dataflow optimize linearize simplify generate)

Well, Factor isn't really that into constrained embedded environments, it's more for general programming, which can be done better because of it's abstraction capabilities, some of which rest on its being concatenative.

Not only does it take more code to do such a simple task but you have to alter the original code to do it. In Factor, at the repl, you can just enter one short line of code to watch a word (\ word-name watch).

(concatenate input compiling dataflow optimize linearize simplify generate)

The Lisp/Scheme equivalent, at the repl, is just one short line of code, (trace proc-name). No alteration of the original code is required.

But the implementation of Common Lisp's trace is more complicated than the Factor equivalent.

"Need"? None. However, the number of situations in which having lexically named variables is useful is high, IME.

Please provide me with a situation where the solution with variables is much better. I know one, math, but that situation seems to be isolated, so I made a minilanguage (which I'm currently redoing) to use infix syntax for math. Do you think this is a more general problem than that? I'm seriously interested in this.


(concatenate input compiling dataflow optimize linearize simplify generate)

I don't think that code would work since the stack effects of many of those words are not ( a -- b ). The only way to make it work would be to have each of those functions take a stack and return a stack, but that's just like implementing a lightweight concatenative language on top of Scheme. Incidentally, I believe someone has done that with Common Lisp...


Since stacks are irrelevant to most problems, unless you can abstract its use away, the need to use one seems to me like a hit against a language's abstraction capabilities.

You're right, I guess; there are only a few cases where the stack really matters. It matters like lexically scoped variables matter in normal code, which really is irrelavent to abstraction. But then there are properties of Kont and Factor (but not Forth) that lend it to more abstraction, like the use of combinators to replace macros in languages like Lisp and built-in syntax like C. Combinators to the programmer look like ordinary code that just happens to do something with a quotation, and they do function when run like that by the interpreter. But then the compiler inlines them to make them as fast as a macro. I'm not explaining them very well, though.


The Lisp/Scheme equivalent, at the repl, is just one short line of code, (trace proc-name). No alteration of the original code is required.

Really? Oh, ok, then never mind that point. I don't have much experience with Lisp development tools.

Please provide me with a situation where the solution with variables is much better. I know one, math, but that situation seems to be isolated, so I made a minilanguage (which I'm currently redoing) to use infix syntax for math. Do you think this is a more general problem than that? I'm seriously interested in this.

I don't think that code would work since the stack effects of many of those words are not ( a -- b ). The only way to make it work would be to have each of those functions take a stack and return a stack, but that's just like implementing a lightweight concatenative language on top of Scheme. Incidentally, I believe someone has done that with Common Lisp...

Uh-oh, you're showing signs of being infected by stack-oriented thinking, which is one of the problems that can be caused by using a language which forces you to think in terms of its implementation details all the time. It doesn't require "each of those functions take a stack and return a stack" — for a start, procedures in most applicative languages can receive multiple values using ordinary named parameters, and multiple values can typically be returned in various ways, such as lists, tuples, or other kinds of collection. A Scheme version which uses lists applied to ordinary procedures with named arguments, is as simple as this:

  (define (concatenate input-args . procs)
    (fold apply input-args procs))

Since stacks are irrelevant to most problems, unless you can abstract its use away, the need to use one seems to me like a hit against a language's abstraction capabilities.

You're right, I guess; there are only a few cases where the stack really matters. It matters like lexically scoped variables matter in normal code, which really is irrelavent to abstraction.

Named variables are certainly not irrelevant to abstraction. Again, see my other reply.

But then there are properties of Kont and Factor (but not Forth) that lend it to more abstraction, like the use of combinators to replace macros in languages like Lisp and built-in syntax like C. Combinators to the programmer look like ordinary code that just happens to do something with a quotation, and they do function when run like that by the interpreter. But then the compiler inlines them to make them as fast as a macro. I'm not explaining them very well, though.

Uh-oh, you're showing signs of being infected by stack-oriented thinking,

What a great way to refute somebody's point! This is just like putting your hands over your ears, and saying "neener, neener, I'm not listening". Perhaps you've been infected by Scheme-oriented thinking?

The sentence after the one you quoted contains the refutation.

Regarding the "infected" comment, I hope LittleDan didn't take that too personally, it was certainly intended lightheartedly. I should have put a smiley after it.

However, it's also a serious point. When you find yourself saying things like "The only way to make it work would be to have each of those functions take a stack and return a stack", talking about such a specific structure as a stack when the problem is in fact a much more general one, that's a clear sign that you're thinking too much in terms of implementation and too little in terms of specification. It's an easy mistake to make, and I suspect we all do it to some degree from time to time.

However, there's an additional risk in using a language which forces you to think in terms of a single datastructure everywhere, which is that you start conceiving of all problems in terms of that datastructure.

I'd be especially concerned about exposing inexperienced programmers to languages that require this kind of thinking, because you'd be ingraining bad habits in them from the very beginning.

Shriram Krishnamurthi's talk The Swine Before Perl provides a nice example of how powerful abstraction capabilities can help make code understandable. It'd be interesting to see a Factor (or Kont?) version of that program, for comparison.

I started to implement that Swine Before Perl program, but after doing the non-macro part, which came out a bit cleaner than the Scheme program IMHO, I really felt like this is enough. What benefit do you derive from making that a macro? In Factor, syntax extension isn't as common as in Scheme because it's not needed as much, and in Kont, there is no syntax extension. If you're making that macro for a speed boost, that's just showing that you have a bad implementation of the language. I still made a seperate syntax for defining the state machine, though. The code is below.

IN: state-machine
USING: kernel hashtables sequences lists ;

SYMBOL: init
SYMBOL: loop
SYMBOL: end

: c[ad]+r
    #! Initial datastructure
    {{ [[ init {{ [[ CHAR: c loop ]] }} ]]
       [[ loop {{ [[ CHAR: a loop ]]
                  [[ CHAR: d loop ]]
                  [[ CHAR: r end  ]] }} ]]
       [[ end  {{ [[ CHAR: r end  ]] }} ]] }} ; 

: walk-states ( seq states -- ? )
    init swap rot [
        >r ?hash r> swap ?hash
    ] each-with end = ;

: {| POSTPONE: {{ POSTPONE: [[ ; parsing
: :: POSTPONE: {| ; parsing
: -> ; parsing
: || POSTPONE: ]] POSTPONE: [[ ; parsing
: ;; POSTPONE: ]] POSTPONE: }} POSTPONE: ]] POSTPONE: [[ ; parsing
: |} POSTPONE: ]] POSTPONE: }} POSTPONE: ]] POSTPONE: }} \ walk-states swons ; parsing

: final-machine
    {| init :: CHAR: c -> loop ;;
       loop :: CHAR: a -> loop ||
               CHAR: d -> loop ||
               CHAR: r -> end  ;;
       end  :: CHAR: r -> end  |} ;

Is there something wrong with that code? It seems to be a bit shorter than the Scheme code.

Edit: as Slava correctly pointed out on the #concatenative channel, those cosmetic macros are completely stupid and the first version is really the one that should preferably be used.

here's how to activate it

"cadar" final-machine

or

"cadar" c[ad]+r walk-states

dan, that's way too much code. so is krishnamurthi's scheme implementation.

a state machine is a matrix. rows are states and columns are inputs. in this case, the machine has four rows corresponding to the four states: error, init, more, end; and 256 columns, corresponding to possible ascii inputs.

if the machine is in state i and sees input j, then it should enter state k. using two dimensional scalar indexing, k = machine[i;j].

the algorithm should consume inputs and index out the next state, leaving the sequence of states visited as its result (a vector of indices). repeated indexing in k is implemented as:

  result:index matrix\indices

i.e.

  k0:matrix[index;indices 0]
  k1:matrix[k0;indices 1]
  k2:matrix[k1;indices 2]
  :

in k, the algorithm is realized as:

  s:@'[4 256#0;_ic("";"c";"adr";"r");:;(!0;2;2 2 3;3)]
  m:1 s\_ic

e.g.

  m'("car";"cdr";"cadr";"cddr";"cdar";"caddr")
(1 2 2 3
 1 2 2 3
 1 2 2 2 3
 1 2 2 2 3
 1 2 2 2 3
 1 2 2 2 2 3)

a 0 in the return vector indicates that m has entered the error state.

on my pentium 4, 3 ghz machine timings are:

 10k elements: 0 ms
 100k elements: 15 ms
 1m elements: 187 ms

state-machine is just a special case of index-scan, which in turn is a special case of scanning a function on its input. if you understand +, and you understand summation as repeated application of +, and you understand indexing, then it's a small step to knowing how to code up a state-machine.

a state machine is a matrix?

FSMs are graphs, which have matrix representations. Sloppy language, but hey.

hey indeed.

my point was that recursive 2d indexing captures the behavior of fsms, no matter what they "really" are, if, indeed, they are anything at all beyond how they are represented in different programming languages. no need to follow that long and winding road into the metaphysics of abstract objects.

obligatory reading: paul benacerraf, "what numbers could not be."

#include <stdio.h>
int main(int argc,char**argv) {
    char S[4][256]={{0},{['c']=2},{['a']=2,['d']=2,['r']=3},{['r']=3}},s=1;
    if(argc

Simplicity > Abstraction.

That's great guys, unfortunately, it seems to miss the point fairly completely. Recall, Anton's pointer to the talk said (emphasis mine):
Shriram Krishnamurthi's talk The Swine Before Perl provides a nice example of how powerful abstraction capabilities can help make code understandable.

Neither the C, K, nor Factor code is quite as understandable as that presented in slide 38 of Shriram's talk. What's more (and probably more important), is that neither is as flexible as what he presents either. What he's shown[1] is a simple syntax extension for generating (fairly efficient) automata from these simple, clear descriptions via macros. Given the spec for another automata, your solutions would have you hard-coding your new state tables while Shriram's would have you quickly done with the code and onto some other problem.

[1] At least that's what I believe he's shown... I'm only working with the slides, and I know just enough Scheme to get myself in trouble -- feel free to taunt me if I'm wrong. One of these days I'll have to get over the Lisp allergy I picked up when I was a wee lad and really give Scheme a good look.

-30-

The Factor code that Dan showed is equivalent to the Scheme code.

I'd like you to explain why you think that this:

(init : (c -> more))
(more : (a -> more)
        (d -> more)
        (r -> end))
(end  : (r -> end))

Any more flexible than this:

: c[ad]+r
    {{ [[ init {{ [[ CHAR: c loop ]] }} ]]
       [[ loop {{ [[ CHAR: a loop ]]
                  [[ CHAR: d loop ]]
                  [[ CHAR: r end  ]] }} ]]
       [[ end  {{ [[ CHAR: r end  ]] }} ]] }} ;

The Factor version has a bit more punctuation, because Dan did not extend the syntax; he just used Factor's hashtable literals. Also he uses character literals instead of symbols.

And for what its worth, I consider the omission of hashtables from the Scheme standard to be an unacceptable limitation. I don't like the way typical Scheme code is written, using lists (including alists) and symbols for everything. It might look pretty but it just doesn't scale as well as other data structures for most tasks.

I was just about to leave a note that the factor version may be just as flexible, because I am completely unfamiliar with it, and I couldn't figure out exactly what was going on. I more or less figured out what he was doing after I posted the message.

I stand corrected there...

-30-

Unless I'm confused (which happens on a regular basis), I believe you're wrong. The Factor equivalent of this (from pg. 38)...

(automaton init
 (init : (c -> more))
 (more : (a -> more)
         (d -> more)
         (r -> end))
 (end  : (r -> end)))

...looks like...

: final-machine
    {| init :: CHAR: c -> loop ;;
       loop :: CHAR: a -> loop ||
               CHAR: d -> loop ||
               CHAR: r -> end  ;;
       end  :: CHAR: r -> end  |} ;

...not a lot of difference to my eyes.

i don't think i missed either point.

for a machine with n states, use an n x 256 matrix m.

for each (state : input -> nextstate), assign

      m[state;input]:nextstate

to run on input i:

      r:1 m\i

setting up a particular machine can be done line-by-line, as in the scheme example, or it can be done all at once, as my example shows.

no macros, no special syntax. if state-machines are matrices, and recognition is recursive two-dimensional indexing, then implement it as such, as directly as possible.

This particular task does not even call for a state machine at all:

: swine ( sequence -- ? )
    "c" ?head >r "r" ?tail r> and [ "ad" contained? ] [ drop f ] ifte ;