Skip to search.

Breaking News Visit Yahoo! News for the latest.

×Close this window

concatenative · Discuss the concatenative variety of computer languages: Joy, Forth, Postscript

The Yahoo! Groups Product Blog

Check it out!

Group Information

? Already a member? Sign in to Yahoo!

Yahoo! Groups Tips

Did you know...
Hear how Yahoo! Groups has changed the lives of others. Take me there.

Messages

Advanced
Messages Help
Messages 3499 - 3528 of 4941   Oldest  |  < Older  |  Newer >  |  Newest
Messages: Show Message Summaries Sort by Date ^  
#3499 From: "William Tanksley, Jr" <wtanksleyjr@...>
Date: Sat Sep 8, 2007 5:18 pm
Subject: Re: [stack] Parameters: ordered versus named
wtanksle
Send Email Send Email
 
Don Groves <dgroves@...> wrote:
> William Tanksley, Jr wrote:
> > Don Groves <dgroves@...> wrote:
> >> The price we pay for the
> >> simplicity of
> >> concatenative syntax is the amount of parameter checking we must
> >> do at run-time which other languages to at compile-time.

> > Not true. Concatenative semantics don't require parameter passing, so
> > there is nothing to do to parameters at runtime. There are, of course,
> > other prices we must pay; but that's not one of them.

> While it's true there's nothing to do "to" parameters, we still must
> check for
> their existence, yes? If you want to trap stack underflow before it
> happens,
> for example. And what do we do when a user enters a string and a number
> then types "/"?

If you want to stop it before it happens, you're going to do static
analysis. That can be done in a concatenative language using a
linear-time algorithm plus some annotations (and provide typechecking
as a bonus), or it can be done using type inference (using the same
algorithms that many modern functional languages use). StrongForth
uses the former; Cat uses the latter.

> >> One beauty of concatenative notation is the hiding of information
> >> such as described here,

> > Nothing's hidden.

> >> but we all know that hidden info must be dealt with
> >> eventually,
> >> unless the language is so primitive as to not care about these
> >> matters.

> > But this is true. (Well, mostly -- Cat does type inferencing so you
> > don't always have to describe the types, while Enchilada defines its
> > semantics so that all its types are compatible.)

> Afraid I'm confused here. You say nothing is hidden, yet you agree (at
> least partially) with my next statement.

That's because concatenative languages, in general, don't hide
information; but I agree that if you do hide information, you have to
pay the price. I was also illustrating that the price to be paid
wasn't what you thought it was -- Cat pays the price not by being more
primitive, but by having a sophisticated static type inference system
(which can, of course, slow some things down, but is undeniably NOT
primitive and is a desirable feature for many purposes).

> Don Groves

-Billy

#3500 From: "Christopher Diggins" <cdiggins@...>
Date: Sat Sep 8, 2007 6:08 pm
Subject: Re: [stack] Parameters: ordered versus named
cdiggins.geo
Send Email Send Email
 
> That's because concatenative languages, in general, don't hide
> information; but I agree that if you do hide information, you have to
> pay the price. I was also illustrating that the price to be paid
> wasn't what you thought it was -- Cat pays the price not by being more
> primitive, but by having a sophisticated static type inference system
> (which can, of course, slow some things down, but is undeniably NOT
> primitive and is a desirable feature for many purposes).

A static type inference system certainly slows down compilation, but
all things given equal should speed up runtime execution because it
removes the need for runtime checks. Furthermore a static type
inference system makes it easier to optimize code, because you can
take advantage of properties that you have elucidated about the
runtime behaviour. However, every implementation is different.

A simple static type system has the disadvantage that typed terms will
disallow unbalanced stacks. You can't say things like:

if_tuesday [1] [1 2] ifte // does stack have one or two elements?

- Christopher

#3501 From: "William Tanksley, Jr" <wtanksleyjr@...>
Date: Sat Sep 8, 2007 6:24 pm
Subject: Re: [stack] Parameters: ordered versus named
wtanksle
Send Email Send Email
 
Christopher Diggins <cdiggins@...> wrote:
> A simple static type system has the disadvantage that typed terms will
> disallow unbalanced stacks. You can't say things like:
> if_tuesday [1] [1 2] ifte // does stack have one or two elements?

Correct. I hadn't intended to imply that static typing was bad; I was
just conceding his point that there are costs (no free lunch).

> - Christopher

-Billy

#3502 From: Don Groves <dgroves@...>
Date: Sat Sep 8, 2007 7:36 pm
Subject: Re: [stack] Parameters: ordered versus named
dgpdx64
Send Email Send Email
 
On Sep 8, 2007, at 19:55 , Christopher Diggins wrote:

> On 9/8/07, Don Groves <dgroves@...> wrote:
>>
>> On Sep 7, 2007, at 19:03 , William Tanksley, Jr wrote:
>>
>>> Don Groves <dgroves@...> wrote:
>>>
>>>> The price we pay for the
>>>> simplicity of
>>>> concatenative syntax is the amount of parameter checking we must
>>>> do at
>>>> run-time which other languages to at compile-time.
>>>
>>> Not true. Concatenative semantics don't require parameter
>>> passing, so
>>> there is nothing to do to parameters at runtime. There are, of
>>> course,
>>> other prices we must pay; but that's not one of them.
>>
>> While it's true there's nothing to do "to" parameters, we still must
>> check for
>> their existence, yes? If you want to trap stack underflow before it
>> happens,
>> for example. And what do we do when a user enters a string and a
>> number
>> then types "/"?
>
> This is where a static type system with type inference comes in
> useful. You can do all of this without annotation or runtime checks in
> the compiler. See Cat (http://www.cat-language.com).
>
> - Christopher

Thanks, I'll study what you've done with Cat.
--
Don

#3503 From: Don Groves <dgroves@...>
Date: Sat Sep 8, 2007 7:41 pm
Subject: Re: [stack] Parameters: ordered versus named
dgpdx64
Send Email Send Email
 
On Sep 8, 2007, at 19:18 , William Tanksley, Jr wrote:

> Don Groves <dgroves@...> wrote:
>> William Tanksley, Jr wrote:
>>> Don Groves <dgroves@...> wrote:
>>>> The price we pay for the
>>>> simplicity of
>>>> concatenative syntax is the amount of parameter checking we must
>>>> do at run-time which other languages to at compile-time.
>
>>> Not true. Concatenative semantics don't require parameter
>>> passing, so
>>> there is nothing to do to parameters at runtime. There are, of
>>> course,
>>> other prices we must pay; but that's not one of them.
>
>> While it's true there's nothing to do "to" parameters, we still must
>> check for
>> their existence, yes? If you want to trap stack underflow before it
>> happens,
>> for example. And what do we do when a user enters a string and a
>> number
>> then types "/"?
>
> If you want to stop it before it happens, you're going to do static
> analysis. That can be done in a concatenative language using a
> linear-time algorithm plus some annotations (and provide typechecking
> as a bonus), or it can be done using type inference (using the same
> algorithms that many modern functional languages use). StrongForth
> uses the former; Cat uses the latter

Just before falling asleep last night, it hit me what has caused my
confusion
about all this: I've been thinking of the interactive user, not
running an already
compiled program. Of course, when a program has been fed through the
interpreter without errors, stack- and type checking is no longer
necessary.
Thanks for you help!


>>>> One beauty of concatenative notation is the hiding of information
>>>> such as described here,
>
>>> Nothing's hidden.
>
>>>> but we all know that hidden info must be dealt with
>>>> eventually,
>>>> unless the language is so primitive as to not care about these
>>>> matters.
>
>>> But this is true. (Well, mostly -- Cat does type inferencing so you
>>> don't always have to describe the types, while Enchilada defines its
>>> semantics so that all its types are compatible.)
>
>> Afraid I'm confused here. You say nothing is hidden, yet you agree
>> (at
>> least partially) with my next statement.
>
> That's because concatenative languages, in general, don't hide
> information; but I agree that if you do hide information, you have to
> pay the price. I was also illustrating that the price to be paid
> wasn't what you thought it was -- Cat pays the price not by being more
> primitive, but by having a sophisticated static type inference system
> (which can, of course, slow some things down, but is undeniably NOT
> primitive and is a desirable feature for many purposes).

Agreed!
--
Don

#3504 From: Don Groves <dgroves@...>
Date: Sat Sep 8, 2007 7:52 pm
Subject: Re: [stack] Parameters: ordered versus named
dgpdx64
Send Email Send Email
 
On Sep 8, 2007, at 19:08 , Christopher Diggins wrote:

>> That's because concatenative languages, in general, don't hide
>> information; but I agree that if you do hide information, you have to
>> pay the price. I was also illustrating that the price to be paid
>> wasn't what you thought it was -- Cat pays the price not by being
>> more
>> primitive, but by having a sophisticated static type inference system
>> (which can, of course, slow some things down, but is undeniably NOT
>> primitive and is a desirable feature for many purposes).
>
> A static type inference system certainly slows down compilation, but
> all things given equal should speed up runtime execution because it
> removes the need for runtime checks. Furthermore a static type
> inference system makes it easier to optimize code, because you can
> take advantage of properties that you have elucidated about the
> runtime behaviour. However, every implementation is different.
>
> A simple static type system has the disadvantage that typed terms will
> disallow unbalanced stacks. You can't say things like:
>
> if_tuesday [1] [1 2] ifte // does stack have one or two elements?
>
> - Christopher

Clearly, I need to learn more about type systems. Here's the Catenate
code implementing ifte, what kind of type system does this represent?


int ifte_() {  // [f1] [f2] T|F ifte => (results of f1 if T)
		  //          		   => (results of f2 if F)
	 if (depth < 3) {
		 StackError("ifte", "underflow");
		 return OK;
		 }
	 if (!islist(Y)) {
		 printf("\nifte: Y must be a list\n");
		 return UNKNOWN;
		 }
	 if (!islist(Z)) {
		 printf("\nifte: Z must be a list\n");
		 return UNKNOWN;
		 }
	 if (X == TRUE) { 		 // T|F = true?
		 drop_(); drop_(); 	 // (y) drop T and 'else' part (f2)
		 id_(); 			 //     execute 'then' part
		 }
	 else { 			 // (n) false
		 drop_(); swap_(); drop_(); //     drop F and 'then' part (f1)
		 id_(); 			 //     execute 'else' part
		 }
	 return OK;
	 }
--
Don

#3505 From: "Christopher Diggins" <cdiggins@...>
Date: Sat Sep 8, 2007 8:42 pm
Subject: Re: [stack] Parameters: ordered versus named
cdiggins.geo
Send Email Send Email
 
On 9/8/07, Don Groves <dgroves@...> wrote:
> On Sep 8, 2007, at 19:08 , Christopher Diggins wrote:
>
> >> That's because concatenative languages, in general, don't hide
> >> information; but I agree that if you do hide information, you have to
> >> pay the price. I was also illustrating that the price to be paid
> >> wasn't what you thought it was -- Cat pays the price not by being
> >> more
> >> primitive, but by having a sophisticated static type inference system
> >> (which can, of course, slow some things down, but is undeniably NOT
> >> primitive and is a desirable feature for many purposes).
> >
> > A static type inference system certainly slows down compilation, but
> > all things given equal should speed up runtime execution because it
> > removes the need for runtime checks. Furthermore a static type
> > inference system makes it easier to optimize code, because you can
> > take advantage of properties that you have elucidated about the
> > runtime behaviour. However, every implementation is different.
> >
> > A simple static type system has the disadvantage that typed terms will
> > disallow unbalanced stacks. You can't say things like:
> >
> > if_tuesday [1] [1 2] ifte // does stack have one or two elements?
> >
> > - Christopher
>
> Clearly, I need to learn more about type systems. Here's the Catenate
> code implementing ifte, what kind of type system does this represent?
>
> int ifte_() { // [f1] [f2] T|F ifte => (results of f1 if T)
> // => (results of f2 if F)
> if (depth < 3) {
> StackError("ifte", "underflow");
> return OK;
> }
> if (!islist(Y)) {
> printf("\nifte: Y must be a list\n");
> return UNKNOWN;
> }
> if (!islist(Z)) {
> printf("\nifte: Z must be a list\n");
> return UNKNOWN;
> }
> if (X == TRUE) { // T|F = true?
> drop_(); drop_(); // (y) drop T and 'else' part (f2)
> id_(); // execute 'then' part
> }
> else { // (n) false
> drop_(); swap_(); drop_(); // drop F and 'then' part (f1)
> id_(); // execute 'else' part
> }
> return OK;
> }
> --
> Don

This is an example of a runtime checked language, also called a
dynamically typed language, though some theorists object to the term
dynamic typing. Personally I have no qualms with it.

-D

#3506 From: "Christopher Diggins" <cdiggins@...>
Date: Sat Sep 8, 2007 8:44 pm
Subject: Re: [stack] Parameters: ordered versus named
cdiggins.geo
Send Email Send Email
 
> Just before falling asleep last night, it hit me what has caused my
> confusion
> about all this: I've been thinking of the interactive user, not
> running an already
> compiled program. Of course, when a program has been fed through the
> interpreter without errors, stack- and type checking is no longer
> necessary.
> Thanks for you help!

An interpreter can still be statically typed. Each expression fed into
the interpreter can be type-checked before it is run, and compared
with the current stack configuration. AFAIK this is a property
particular to languages with compositional type systems (e.g.
statically typed concatenative languages!)

-D

#3507 From: Don Groves <dgroves@...>
Date: Sun Sep 9, 2007 1:47 am
Subject: Re: [stack] Parameters: ordered versus named
dgpdx64
Send Email Send Email
 
On Sep 8, 2007, at 19:44 , Christopher Diggins wrote:

>> Just before falling asleep last night, it hit me what has caused my
>> confusion
>> about all this: I've been thinking of the interactive user, not
>> running an already
>> compiled program. Of course, when a program has been fed through the
>> interpreter without errors, stack- and type checking is no longer
>> necessary.
>> Thanks for you help!
>
> An interpreter can still be statically typed. Each expression fed into
> the interpreter can be type-checked before it is run, and compared
> with the current stack configuration. AFAIK this is a property
> particular to languages with compositional type systems (e.g.
> statically typed concatenative languages!)
>
> -D


Thanks for the info. In what ways does Cat's inferred type system
differ?
--
Don

#3508 From: Don Groves <dgroves@...>
Date: Sun Sep 9, 2007 1:52 am
Subject: Re: [stack] Parameters: ordered versus named
dgpdx64
Send Email Send Email
 
On Sep 8, 2007, at 19:42 , Christopher Diggins wrote:

> On 9/8/07, Don Groves <dgroves@...> wrote:
>> On Sep 8, 2007, at 19:08 , Christopher Diggins wrote:
>>
>>>> That's because concatenative languages, in general, don't hide
>>>> information; but I agree that if you do hide information, you
>>>> have to
>>>> pay the price. I was also illustrating that the price to be paid
>>>> wasn't what you thought it was -- Cat pays the price not by being
>>>> more
>>>> primitive, but by having a sophisticated static type inference
>>>> system
>>>> (which can, of course, slow some things down, but is undeniably NOT
>>>> primitive and is a desirable feature for many purposes).
>>>
>>> A static type inference system certainly slows down compilation, but
>>> all things given equal should speed up runtime execution because it
>>> removes the need for runtime checks. Furthermore a static type
>>> inference system makes it easier to optimize code, because you can
>>> take advantage of properties that you have elucidated about the
>>> runtime behaviour. However, every implementation is different.
>>>
>>> A simple static type system has the disadvantage that typed terms
>>> will
>>> disallow unbalanced stacks. You can't say things like:
>>>
>>> if_tuesday [1] [1 2] ifte // does stack have one or two elements?
>>>
>>> - Christopher
>>
>> Clearly, I need to learn more about type systems. Here's the Catenate
>> code implementing ifte, what kind of type system does this represent?
>>
>> int ifte_() { // [f1] [f2] T|F ifte => (results of f1 if T)
>> // => (results of f2 if F)
>> if (depth < 3) {
>> StackError("ifte", "underflow");
>> return OK;
>> }
>> if (!islist(Y)) {
>> printf("\nifte: Y must be a list\n");
>> return UNKNOWN;
>> }
>> if (!islist(Z)) {
>> printf("\nifte: Z must be a list\n");
>> return UNKNOWN;
>> }
>> if (X == TRUE) { // T|F = true?
>> drop_(); drop_(); // (y) drop T and 'else' part (f2)
>> id_(); // execute 'then' part
>> }
>> else { // (n) false
>> drop_(); swap_(); drop_(); // drop F and 'then' part (f1)
>> id_(); // execute 'else' part
>> }
>> return OK;
>> }
>> --
>> Don
>
> This is an example of a runtime checked language, also called a
> dynamically typed language, though some theorists object to the term
> dynamic typing. Personally I have no qualms with it.
>
> -D


OK, that's what I thought it was. It seems dynamic typing means two
things: (1) run-time type checking; and (2) data is typed --
variables are
not. Clearly (1) allows (2) but (2) is not required. Is this part of
the source
of disagreement over the name?
--
Don

#3509 From: "pml060912" <pml540114@...>
Date: Sun Sep 9, 2007 6:25 am
Subject: Re: Parameters: ordered versus named
pml060912
Send Email Send Email
 
--- In concatenative@yahoogroups.com, Manfred Von Thun
<m.vonthun@...> wrote:
>
> For a long time I have been interested in the difference
> between the standard kind of lambda calculus languages
> and the concatenative languages. Only recently did it
> occur to me that there is a third class which has been around
> for some time. The three differ in how they treat actual
> and formal parameters in definitions of functions and in
> calls of functions. At one extreme are the concatenative
> languages, at the other extreme those in the third class.
> The standard lambda calculus languages are half way
> between these two extremes.
.
.
.
At the other extreme there should be languages
> which do not use  order at all but rely on names both
> in the body and in calls. Are there such beasts?
>
> In such languages definitions would again look as in
> lambda calculus languages:
>
> DEFINE foo(x,y,z)        # head of definition
>    = ...x...y...z...          # body of definition
>
> As before, you can change the order of the parameters
> without any need to change the body of the definition.
> But a call would look quite different: instead of relying
> on the order of the formal parameters, use their names
> as assignment statements, and make the assignments
> in any order. Hence any of the following would be OK
> as a call:
>
> foo(x=a; y=b; z=c)
> foo(y=b; z=c; x=a)
> foo(z=c; y=b; x=a)
>
> and so forth, a total of six possible combinations. All such
> calls would be equivalent. To summarise: body and call
> are done by using the names of the formal parameters.
> My understanding is that there are some languages which
> allow this kind of notation (Common Lisp ?, Ada ?) but
> I cannot remember any details --- anyone?? But as far
> as I know these languages use standard positional notation
> by default and allow this other notation only as a
> convenient variation. I have never heard of a language
> in which this way of calling is standard. Anyone??

That looks like something I came across in P.J.Brown's "Writing
Interactive Compilers and Interpreters", although I forget if he
stated it explicitly or just implied it. In essence, he suggested
handling parameters and local variables by a "don't care" method, in
which they were really global variables like any other, only their
values were stacked/reinitialised and then restored on call/return.
Then the function call construct is little more than a subroutine
that can return a value, and foo(x=a; y=b; z=c) is a macro for the
pushing and popping of global variables x, y and z on either side of
gosub foo. The function needs no special declaration, either.

I actually looked into this approach for its smaller
implementation "footprint" in two areas:-

- extending awkward languages like Cobol so that they could
comfortably support their own compilers (the released version would
have had the extensions disabled); and

- making user defined functions easy to implement in a spreadsheet.

The latter relates to my musings on where to go next in paper
exploring for Furphy, since a spreadsheet would make a comfortable
programming interface for a functional programming language. PML.

#3510 From: "Christopher Diggins" <cdiggins@...>
Date: Sun Sep 9, 2007 2:12 pm
Subject: Re: [stack] Parameters: ordered versus named
cdiggins.geo
Send Email Send Email
 
On 9/8/07, Don Groves <dgroves@...> wrote:
> On Sep 8, 2007, at 19:44 , Christopher Diggins wrote:
>
> >> Just before falling asleep last night, it hit me what has caused my
> >> confusion
> >> about all this: I've been thinking of the interactive user, not
> >> running an already
> >> compiled program. Of course, when a program has been fed through the
> >> interpreter without errors, stack- and type checking is no longer
> >> necessary.
> >> Thanks for you help!
> >
> > An interpreter can still be statically typed. Each expression fed into
> > the interpreter can be type-checked before it is run, and compared
> > with the current stack configuration. AFAIK this is a property
> > particular to languages with compositional type systems (e.g.
> > statically typed concatenative languages!)
> >
> > -D
>
> Thanks for the info. In what ways does Cat's inferred type system
> differ?
> --

From what?

-Christopher

#3511 From: "Christopher Diggins" <cdiggins@...>
Date: Sun Sep 9, 2007 2:23 pm
Subject: Re: [stack] Parameters: ordered versus named
cdiggins.geo
Send Email Send Email
 
> > This is an example of a runtime checked language, also called a
> > dynamically typed language, though some theorists object to the term
> > dynamic typing. Personally I have no qualms with it.
> >
> > -D
>
> OK, that's what I thought it was. It seems dynamic typing means two
> things: (1) run-time type checking; and (2) data is typed --
> variables are
> not. Clearly (1) allows (2) but (2) is not required.
> Is this part of
> the source
> of disagreement over the name?

I shouldn't speculate too much. I think the disagreement is
artificial. There were some threads on
http://www.Lambda-the-Ultimate.org related to the issue, but in
searching for them, I see many people happily talking about dyanmic
typing, without complaining about the term.

Dynamic typing invariably means: runtime checking of tags associated
with values. All values that are runtime checked would have to have
tags identifying their type. Of course, you can mix static typing with
dynamic typing if you want.

I'm sorry if I have confused the issues for you.

- Christopher

#3512 From: Don Groves <dgroves@...>
Date: Sun Sep 9, 2007 7:26 pm
Subject: Re: [stack] Parameters: ordered versus named
dgpdx64
Send Email Send Email
 
On Sep 9, 2007, at 19:12 , Christopher Diggins wrote:

> On 9/8/07, Don Groves <dgroves@...> wrote:
>> On Sep 8, 2007, at 19:44 , Christopher Diggins wrote:
>>
>>>> Just before falling asleep last night, it hit me what has caused my
>>>> confusion
>>>> about all this: I've been thinking of the interactive user, not
>>>> running an already
>>>> compiled program. Of course, when a program has been fed through
>>>> the
>>>> interpreter without errors, stack- and type checking is no longer
>>>> necessary.
>>>> Thanks for you help!
>>>
>>> An interpreter can still be statically typed. Each expression fed
>>> into
>>> the interpreter can be type-checked before it is run, and compared
>>> with the current stack configuration. AFAIK this is a property
>>> particular to languages with compositional type systems (e.g.
>>> statically typed concatenative languages!)
>>>
>>> -D
>>
>> Thanks for the info. In what ways does Cat's inferred type system
>> differ?
>> --
>
> From what?
>
> -Christopher

  From an "uninferred" one. I'm thinking a large part of my problem is
lack of vocabulary. I tried to find a definition of an "inferred" type
system via Google but was unsuccessful.
--
Don

#3513 From: Don Groves <dgroves@...>
Date: Sun Sep 9, 2007 7:29 pm
Subject: Re: [stack] Parameters: ordered versus named
dgpdx64
Send Email Send Email
 
On Sep 9, 2007, at 19:23 , Christopher Diggins wrote:

>>> This is an example of a runtime checked language, also called a
>>> dynamically typed language, though some theorists object to the term
>>> dynamic typing. Personally I have no qualms with it.
>>>
>>> -D
>>
>> OK, that's what I thought it was. It seems dynamic typing means two
>> things: (1) run-time type checking; and (2) data is typed --
>> variables are
>> not. Clearly (1) allows (2) but (2) is not required.
>> Is this part of
>> the source
>> of disagreement over the name?
>
> I shouldn't speculate too much. I think the disagreement is
> artificial. There were some threads on
> http://www.Lambda-the-Ultimate.org related to the issue, but in
> searching for them, I see many people happily talking about dyanmic
> typing, without complaining about the term.
>
> Dynamic typing invariably means: runtime checking of tags associated
> with values. All values that are runtime checked would have to have
> tags identifying their type. Of course, you can mix static typing with
> dynamic typing if you want.
>
> I'm sorry if I have confused the issues for you.
>
> - Christopher

No, my confusion is entirely my own and things are becoming clearer.
--
Don

#3514 From: "Christopher Diggins" <cdiggins@...>
Date: Sun Sep 9, 2007 9:06 pm
Subject: Re: [stack] Parameters: ordered versus named
cdiggins.geo
Send Email Send Email
 
On 9/9/07, Don Groves <dgroves@...> wrote:
> >> Thanks for the info. In what ways does Cat's inferred type system
> >> differ?
> >> --
> >
> > From what?
> >
> > -Christopher
>
> From an "uninferred" one. I'm thinking a large part of my problem is
> lack of vocabulary. I tried to find a definition of an "inferred" type
> system via Google but was unsuccessful.

Some examples of languages with type inference are ML, OCaML, Haskell,
F#, Scala, Boo, Nice, Cyclone, and of course Cat.

Type inference (also known as type reconstruction) is not a property
of the type system but rather a property of a language. Two languages
can share a type system, whereas one requires type annotations (a.k.a
type signatures) wheras another doesn't. Some type systems lend
themselves to type inference (e.g. ML style type systems). Type
inference is often achieved using what is known as the Hindley-Milner
algorithm.

Your most successful search keywords are going to be "type inference".

Hope this helps,
Christopher

#3515 From: John Cowan <cowan@...>
Date: Mon Sep 10, 2007 12:58 am
Subject: Re: [stack] Re: Parameters: ordered versus named
johnwcowan
Send Email Send Email
 
pml060912 scripsit:

> That looks like something I came across in P.J.Brown's "Writing
> Interactive Compilers and Interpreters", although I forget if he
> stated it explicitly or just implied it. In essence, he suggested
> handling parameters and local variables by a "don't care" method, in
> which they were really global variables like any other, only their
> values were stacked/reinitialised and then restored on call/return.

That's dynamic scoping (not to be confused with dynamic *typing*) and
it is a Really Really Bad Idea, because reasoning about the behavior
of programs becomes insanely difficult.  You wind up not being able to
know where the value of a variable is set unless you know the exact
path by which it was called, and no procedure can guarantee that the
values of its parameters are safe from tampering unless it never calls
any other procedure.  What's more, that particular *implementation*
of dynamic scoping (known as "shallow binding") only works in a single
thread of control; if there are multiple threads, it goes horribly wrong
in all sorts of ways.

Lexical scoping, in which variables only exist within the particular
portion of the program that declares them, is a far superior regime.
There are occasional uses for dynamic scoping here and there, and
some languages support it as an alternative to lexical scoping for
restricted use (Perl and Common Lisp, notably; also because of backward
compatibility).  But it's hard to believe that any modern work on
interpreters would recommend it.

--
"Well, I'm back."  --Sam        John Cowan <cowan@...>

#3516 From: "pml060912" <pml540114@...>
Date: Mon Sep 10, 2007 1:28 am
Subject: Re: Parameters: ordered versus named
pml060912
Send Email Send Email
 
--- In concatenative@yahoogroups.com, John Cowan <cowan@...> wrote:
>
> pml060912 scripsit:
>
> > That looks like something I came across in P.J.Brown's "Writing
> > Interactive Compilers and Interpreters", although I forget if he
> > stated it explicitly or just implied it. In essence, he suggested
> > handling parameters and local variables by a "don't care" method,
in
> > which they were really global variables like any other, only
their
> > values were stacked/reinitialised and then restored on
call/return.
>
> That's dynamic scoping (not to be confused with dynamic *typing*)
and
> it is a Really Really Bad Idea, because reasoning about the behavior
> of programs becomes insanely difficult.  You wind up not being able
to
> know where the value of a variable is set unless you know the exact
> path by which it was called, and no procedure can guarantee that the
> values of its parameters are safe from tampering unless it never
calls
> any other procedure.

That depends on what else is available to change them. As far as I
can see, it's less risky in spreadsheets than in other languages
since - depending on what base you have for building the formulas -
formula execution needn't change the cells you allocate for that use
(unless you foolishly use the same cell for one parameter as for the
formula using the parameter!). But as I said, at this point I'm just
mulling over ideas.

   What's more, that particular *implementation*
> of dynamic scoping (known as "shallow binding") only works in a
single
> thread of control; if there are multiple threads, it goes horribly
wrong
> in all sorts of ways.
>
> Lexical scoping, in which variables only exist within the particular
> portion of the program that declares them, is a far superior regime.
> There are occasional uses for dynamic scoping here and there, and
> some languages support it as an alternative to lexical scoping for
> restricted use (Perl and Common Lisp, notably; also because of
backward
> compatibility).  But it's hard to believe that any modern work on
> interpreters would recommend it.

P.J.Brown wrote the first edition in 1979, emphasising
implementation. He wasn't recommending this technique for the
language design, but as an implementation technique for passing
parameters to subroutines without having to implement the subroutine
bodies specially. You would constrain the language in other ways to
avoid some of these problems, for instance having an extra level of
indirection in descriptors would allow it to act more like parameter
handling in C. Brown also suggested having variables associated with
subroutines and only allowing access to other variables by giving
them what amounts to pathnames. On checking, I find that Brown only
recommended this technique for subroutines, not functions, and he
didn't specify the foo(x=a, y-b, z=c) notation for calling.

I realised that it wasn't the best way to extend Cobol (say) to make
it convenient for compiling itself, but it would have been a
realistic approach if the extended version was only used in house
with great care and not released. PML.

#3517 From: Don Groves <dgroves@...>
Date: Mon Sep 10, 2007 7:48 am
Subject: Re: [stack] Parameters: ordered versus named
dgpdx64
Send Email Send Email
 
On Sep 9, 2007, at 19:06 , Christopher Diggins wrote:

> On 9/9/07, Don Groves <dgroves@...> wrote:
>>>> Thanks for the info. In what ways does Cat's inferred type system
>>>> differ?
>>>> --
>>>
>>> From what?
>>>
>>> -Christopher
>>
>> From an "uninferred" one. I'm thinking a large part of my problem is
>> lack of vocabulary. I tried to find a definition of an "inferred"
>> type
>> system via Google but was unsuccessful.
>
> Some examples of languages with type inference are ML, OCaML, Haskell,
> F#, Scala, Boo, Nice, Cyclone, and of course Cat.
>
> Type inference (also known as type reconstruction) is not a property
> of the type system but rather a property of a language. Two languages
> can share a type system, whereas one requires type annotations (a.k.a
> type signatures) wheras another doesn't. Some type systems lend
> themselves to type inference (e.g. ML style type systems). Type
> inference is often achieved using what is known as the Hindley-Milner
> algorithm.
>
> Your most successful search keywords are going to be "type inference".
>
> Hope this helps,
> Christopher

Yes, it helps a lot! Having fried my brain for the last two hours
reading
up on type inference, one thing stands out for the development of
Catenate:
if I infer the type of a variable from its initialization literal,
and restrict that
variable from ever holding a different type, then I can disable type
checking
for compiled programs. I'm not thinking much about execution speed yet,
but doing this should speed up things considerably down the road.
--
Don

Programmer (n): an organism that turns coffee and cookies into software.

#3518 From: "William Tanksley, Jr" <wtanksleyjr@...>
Date: Thu Sep 20, 2007 12:41 am
Subject: Functional Forth?
wtanksle
Send Email Send Email
 
http://wiki.forthfreak.net/index.cgi?FunForth

Functional Forth. Written in a few lines of Forth. Speaks for itself.
I didn't know that was possible.

-Billy "fun fact 0=1" (a punny line out of context -- taken from ML source code)

#3519 From: "Chris Double" <chris.double@...>
Date: Thu Sep 20, 2007 1:43 am
Subject: Re: [stack] Functional Forth?
doublecnz
Send Email Send Email
 
On 9/20/07, William Tanksley, Jr <wtanksleyjr@...> wrote:
> http://wiki.forthfreak.net/index.cgi?FunForth
>
>  Functional Forth. Written in a few lines of Forth. Speaks for itself.
>  I didn't know that was possible.

That's pretty neat. With a few changes  to make it compatible with 4p
you can write some very Joy like code:

C{ dup * } { 1 2 3 4 } lmap .list
   => { 1 4 9 16 }

4p is a forth with some interesting control words:

http://maschenwerk.de/4p/control-flow.txt

Chris.
--
http://www.bluishcoder.co.nz

#3520 From: "Chris Double" <chris.double@...>
Date: Thu Sep 20, 2007 2:18 am
Subject: Re: [stack] Functional Forth?
doublecnz
Send Email Send Email
 
#3521 From: "Christopher Diggins" <cdiggins@...>
Date: Thu Sep 20, 2007 2:37 am
Subject: Function Level Programming
cdiggins.geo
Send Email Send Email
 
I am looking at the function level programming entry on Wikipeda (
http://en.wikipedia.org/wiki/Function-level_programming ) and I am
intrigued.

"This restriction means that functions in FP are a module (generated
by the built-in functions) over the algebra of functional forms, and
are thus algebraically tractable. For instance, the general question
of equality of two functions is equivalent to the halting problem, and
is undecidable, but equality of two functions in FP is just equality
in the algebra, and thus (Backus imagines) easier."

This sounds significant, but I don't know how to leverage such
information practically. What other kinds of things can you do if
functions are a module? Are functions a module in Joy?

Thanks,
Christopher

#3522 From: Don Groves <dgroves@...>
Date: Thu Sep 20, 2007 4:21 am
Subject: Re: [stack] Functional Forth?
dgpdx64
Send Email Send Email
 
On Sep 19, 2007, at 19:41 , William Tanksley, Jr wrote:

> http://wiki.forthfreak.net/index.cgi?FunForth
>
> Functional Forth. Written in a few lines of Forth. Speaks for itself.
> I didn't know that was possible.

Forth is one of the most malleable languages in existence due to
everything
being exposed and modifiable. I remember a comp.lang.forth response from
Elizabeth Rather of Forth, Inc. to someone who disliked Forth's
postfix syntax:
"Why don't you just change it then?"
--
Don Groves

"Computers are like Old Testament gods; lots of rules and no mercy."
-- Joseph Campbell

#3523 From: Don Groves <dgroves@...>
Date: Thu Sep 20, 2007 5:43 am
Subject: Re: [stack] Function Level Programming
dgpdx64
Send Email Send Email
 
On Sep 19, 2007, at 19:37 , Christopher Diggins wrote:

> I am looking at the function level programming entry on Wikipeda (
> http://en.wikipedia.org/wiki/Function-level_programming ) and I am
> intrigued.
>
> "This restriction means that functions in FP are a module (generated
> by the built-in functions) over the algebra of functional forms, and
> are thus algebraically tractable. For instance, the general question
> of equality of two functions is equivalent to the halting problem, and
> is undecidable, but equality of two functions in FP is just equality
> in the algebra, and thus (Backus imagines) easier."
>
> This sounds significant, but I don't know how to leverage such
> information practically. What other kinds of things can you do if
> functions are a module? Are functions a module in Joy?
>
> Thanks,
> Christopher

This thread has turned into the most information-dense thing I've read
since first encountering Joy. I've been downloading and printing for the
past hour!

I, too, am intrigued by this module idea and intend to do some serious
studying of the issues involved. Also Backus's FP, which has some
ideas I'd like to try implementing in Catenate.
--
Don Groves

"Every now and then a man's mind is stretched by a new idea and never
shrinks back to its former dimensions." -- Oliver Wendel Holmes, Sr.

#3524 From: Robbert van Dalen <robbert.van.dalen@...>
Date: Fri Sep 7, 2007 9:03 am
Subject: Re: [stack] Parameters: ordered versus named
r_v_dalen
Send Email Send Email
 
Hi Manfred,

Interesting post as usual.

You may want to check: http://blog.moertel.com/articles/2006/01/20/
wondrous-oddities-rs-function-call-semantics
Function definitions in the R language follow your classification #3:
bodies and calls rely on names.

- Robbert

#3525 From: Manfred Von Thun <m.vonthun@...>
Date: Tue Oct 2, 2007 5:35 am
Subject: Re: [stack] Parameters: ordered versus named
maggethun
Send Email Send Email
 
Thanks Robbert. Very interesting indeed. There is another feature
which I have not seen before (and which has nothing to do with
ordered/named parameters): one and the same procedure can
use Cartesian or polar coordinates, and their interrelation is
expressed in the list of (named) parameters. Very clever.

   - Manfred

On 7/9/07 7:03 PM, "Robbert van Dalen" <robbert.van.dalen@...> wrote:

> Hi Manfred,
>
> Interesting post as usual.
>
> You may want to check: http://blog.moertel.com/articles/2006/01/20/
> wondrous-oddities-rs-function-call-semantics
> Function definitions in the R language follow your classification #3:
> bodies and calls rely on names.
>
> - Robbert
>
>



[Non-text portions of this message have been removed]

#3526 From: "Don Groves" <dgroves@...>
Date: Mon Oct 15, 2007 4:32 am
Subject: Concatenative operators as functions over stacks.
dgpdx64
Send Email Send Email
 
I've long been intrigued by Manfred's statement that Joy operators are
best described as functions from stacks to stacks and last night
decided to put pencil to paper and try to put that idea into some sort
of formal form -- both to aid my understanding of the implications of
this statement, and to see if something useful might emerge from the
effort. Here's a synopsis of what I've come up with so far:

A stack S is a sequence (ordered collection) of terms S = s0, s1, ...,
s(t-1), s(t) where only the most recently added term, s(t) is
available. (Note: "t" can be though of as standing for "top") Except
for the identity function, id : S --> S, all functions on S must begin
with some operation on s(t).

The function notation I use is
f : S --> S\modifications
which reads "function f is a mapping from stack S onto stack S
modified by whatever follows the backslash." So we can define push and
pop as:

push(x,S) : S --> S\t=t+1 s(t)=x
x = pop(S) : S --> S\x=s(t) t=t-1

Given any pair x,S where x is a term and S a stack, we can compute,

pop(push(x,S)) = pop(S\t=t+1 s(t)=x) = x,S\t=t+1-1 = x,S

which is as expected.

So, here's the question -- can all required operations of a
concatenative language be defined in terms of these two primitive
stack operations and function composition?

To simplify the notation, we can get rid of the S (actually, make the
S implicit)
in the function definitions by push(x,S) = pushS(x) and pop(S) =
popS() and then
redefine them as push(x) and pop assuming there is only one stack
under  consideration.

The shuffle operators now become,

dup : S --> S\x=pop push(x) push(x)
swap : S --> S\x=pop y=pop push(x) push(y)
etc...

As Manfred points out, even concatenative literals behave as
functions. For any literal value v,
v : S --> S\push(v)

The arithmetic operators become,
add : S --> S\x=pop y=pop push(x+y)
etc...

Actually we can generalize arithmetic and relational operators as
binary operators,

binop(op) : S --> S\x=pop y=pop push(x op y) for op in
(+,-,*,/,mod,=,!=,...)

By adding additional notation for lists, sets, ..., this method seems
able to account for any concatentative operation. For example, if we
use the Haskell list notation [x|xs], then cons becomes,

cons : S --> S\x=pop [xs]=pop push([x|xs])

If we say that [Q] is a quoted program, we can define map as,

map : S --> S\[Q]=pop [y]=pop push([Q(y0) Q(y1) ... ])

The above seems to be the lambda calculus version of the situation as
it uses dummy variables. If variables are forbidden, the situation
becomes different quickly. If we try to write swap, for instance,
without dummy variables,

swap : S --> S\pop pop ? push push

we have an immediate problem -- how do we change the order of  the two
popped values? What replaces the question mark? Of course it is the C
combinator and now we're off down the combinator trail which Manfred
seems to prefer anyway.
If someone wants to take the time to produce a combinator version of
this notation, it would be a useful addition to our knowledge base, imho.

This is getting very long and I won't bore anyone with further details
but I'd like to know if anyone considers this a useful avenue for
further exploration. I'm thinking of writing a tiny interpreter using
only the methods given and hinted at here just to see how it goes and
what kind of program results.

One thing of interest is that the notation above lends itself to
direct compilation from a specification, if we remove the arrows and
just write

dup ::=  x=pop push(x) push(x)
etc...
--
Don Groves

#3527 From: "pml060912" <pml540114@...>
Date: Mon Oct 15, 2007 1:13 pm
Subject: Re: Concatenative operators as functions over stacks.
pml060912
Send Email Send Email
 
--- In concatenative@yahoogroups.com, "Don Groves" <dgroves@...> wrote:
>
> I've long been intrigued by Manfred's statement that Joy operators are
> best described as functions from stacks to stacks

If you just look at that on its own, it isn't enough. There's a
standard computer science result, that I don't have a reference to off
hand, that says that a PURE stack machine isn't Turing equivalent,
i.e. if you can only work within a limited depth of one stack at any
stage and the stack only holds simple values (roughly speaking). You
can get Turing equivalent if you have a two stack machine, or if you
have non-standard operators, e.g. like Forth's PICK and ROLL, or
non-functional stuff for memory peeking and poking like Forth's @ and !.

.
.
.
> So, here's the question -- can all required operations of a
> concatenative language be defined in terms of these two primitive
> stack operations and function composition?

No, not within the pure stack machine limit. When I look at my own
work with Furphy (mentioned in earlier threads), it turns out that all
operations in that take two stacks and return two stacks, but most
operations leave one - the return stack - essentially unchanged. So,
most operations can be thought of as taking and yielding a single
stack, but some need both; these are really higher order functions in
some sense (you can build PICK and ROLL using these and the simpler
operations). But you don't need to go beyond two stacks and end up
with a regress of stacks, a stack of stacks say.
.
.
.
> By adding additional notation for lists, sets, ..., this method seems
> able to account for any concatentative operation.

That's another way of expanding what you can do with one stack, enough
to make it Turing equivalent. And of course I provide that in Furphy
too - but it turns out, so far, that this is orthogonal to what Furphy
does with higher order, two stack using, operations. PML.

#3528 From: Don Groves <dgroves@...>
Date: Mon Oct 15, 2007 8:12 pm
Subject: Re: [stack] Re: Concatenative operators as functions over stacks.
dgpdx64
Send Email Send Email
 
On Oct 15, 2007, at 19:13 , pml060912 wrote:

> --- In concatenative@yahoogroups.com, "Don Groves" <dgroves@...>
> wrote:
>>
>> I've long been intrigued by Manfred's statement that Joy operators
>> are
>> best described as functions from stacks to stacks
>
> .
> .
>> By adding additional notation for lists, sets, ..., this method seems
>> able to account for any concatentative operation.
>
> That's another way of expanding what you can do with one stack, enough
> to make it Turing equivalent. And of course I provide that in Furphy
> too - but it turns out, so far, that this is orthogonal to what Furphy
> does with higher order, two stack using, operations. PML.

Thanks for the response, Peter.

Messages 3499 - 3528 of 4941   Oldest  |  < Older  |  Newer >  |  Newest
Add to My Yahoo!      XML What's This?

Copyright © 2010 Yahoo! Inc. All rights reserved.
Privacy Policy - Terms of Service - Guidelines NEW - Help