Re: Lambda - let's write it down

Dave Harris wrote:
> no.spam@no.spam.com (Maciej Sobczak) wrote (abridged):
> 
>
>
> Yes. Very much so. At least in latently typed languages, whether
> dynamically type-checked like Smalltalk and Lisp, or statically
> type-checked like Haskell.

Some nits: The term "latently typed" refers to languages where values
carry around a type tag at run-time. Type errors like trying to add an
integer to a string are only detected and signalled during the execution
of a program. "Latently typed" is just another way of saying
"dynamically typed." Scheme and Common Lisp are latently-typed languages
(although Common Lisp allows for optional type declarations). Scripting
languages tend to be latently-typed.

In contrast, the term "statically typed" refers to languages where
expressions are typed at compile time. Some statically-typed langauges
require (manifest) type declarations, and some infer the types directly
from the code without the need for type declarations. Miranda, Haskell,
and SML are statically-typed langauges.

(The terms "strong" and "weak" typing seem to refer to how hard/easy it
is to circumvent the type system, or to the degree to which the type
information exists in the first place.)

The issue of support for (real) lambda (by way of closures as you bring
up) is orthogonal to the issue of types.

(Java and C++ are more accurately described as being a mixture of static
and dynamic typing in that given the ability to subtype, an object may
carry around a tag at run-time specifying to which of a set of subtypes
the object really belongs.)


> I don't know of any language that has closures which doesn't also have
> garbage collection, but I think that's because languages without GC are
> rare. I suspect that practical experience of this combination will have to
> be gained in C++ itself. [...]

Languages with (real) lambda universally support GC because you can't do
(real) closures without it. Lambda is a good thing. Static typing is
also a good thing, but it takes more work to do it well, which is why
scripting languages tend to punt on the issue and just go with latent
typing.

(This is not to say that I think adding (real) lambda to C++ is a good
idea--which is not to say that I think adding some of the things being
described in this thread to C++ is a bad idea--as long as it's not
called lambda.)

-thant

--
"Now, the temptation is going to be, by well-meaning people such as
yourself and others here, as we run up to the issue, to get me to
negotiate with myself in public," -- George W. Bush, December 20, 2004


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated.    First time posters: Do this! ]

Dave Harris wrote:

> No, it doesn't. That's "dynamically typed", as opposed to "statically
> typed". "Latently typed" means that the types are not stated explicitly in
> the program source. The opposite is "manifestly typed".


> I didn't invent this terminology; here are a couple of web pages which use
> it:
>     http://osteele.com/archives/2003/08/test-versus-type
>     http://onestepback.org/articles/usingruby/strong.html


My understanding has always been that latently typed was another term
for dynamically typed, and that the opposite of "manifestly typed" was
"type inferred" or "implicitly typed." The first web page I googled
concurred with my understanding. However, I will admit that as I dig
around, there seems to be no real agreement on the terminology, which
seems to have changed over the years. And indeed the problem seems to be
that people have not considered various axes-of-features as independent
of each other. Note that the first article you cite uses the term in a
way that seems to correlate more with my understanding than with yours:

"Python is an example of latent typing: types are always checked, just
not at compile time."

Regardless, my apologies for starting an argument over terminology.
 
>
>
> It is orthogonal to the issue of type-checking, but not orthogonal to the
> issue of whether types need to be declared. This is because the
> declarations make the lambda more verbose, and an aim of lambda is to be
> concise.

The aim of lambda is to enable functional composition, and the power of
functional composition goes *way* beyond its ability to *syntactically*
shorten a computer program:

http://lists.cs.wisc.edu/archive/pl.../msg00020.shtml

Sorry the example is in SML, but C++ just doesn't cut it for this kind
of thing--even with the modifications being discussed in this thread. (I
have the same program in Scheme lying around somewhere.) SML infers
types as much as it can. But sometimes you need to declare types, and
you can always add (redundant) type declarations. Doing so in the
example above would do little to detract from the point it was making
about the power of functional composition.

-thant


--
"Gold: monetary unit of the peaceable kingdom. Dollah: toilet
paper of the war whores." --machinehead


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated.    First time posters: Do this! ]

Thant Tessman <thant@acm.org> writes:

[...]

| Sorry the example is in SML, but C++ just doesn't cut it for this kind
| of thing--even with the modifications being discussed in this thread. (I
| have the same program in Scheme lying around somewhere.) SML infers
| types as much as it can. But sometimes you need to declare types, and
| you can always add (redundant) type declarations. Doing so in the
| example above would do little to detract from the point it was making
| about the power of functional composition.

And the price of that deceptive facility, i.e. Hindley-Milner typing,
is the ban of overloading -- except when the language itself declares
that it knows about some symbols (e.g."+") but do not give programmers
ways to overload.  OCaml chosed to remain consistent -- and carry the
logic to the extreme where, for instantce, "*" is for intergers and
"*." is for floating point.  Haskell removed that limitation through
"type classes", which in C++ would correspond to abstract class
templates -- the "Haskell dictionaries" would correspond to "C++ vtables".

Decades of going in circles, with increasing resource spent in
obfuscation of common sense.

--
Gabriel Dos Reis
gdr@integrable-solutions.net

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated.    First time posters: Do this! ]

thant@acm.org (Thant Tessman) wrote (abridged): 
>
> The aim of lambda is to enable functional composition, and the power of
> functional composition goes *way* beyond its ability to *syntactically*
> shorten a computer program:
>
> 	http://lists.cs.wisc.edu/archive/pl.../msg00020.shtml

Functional composition is a good thing, and it's something we can already
do in C++. The lambda proposals don't so much enable it as provide a nicer
syntax for it. All of the proposals for lambda so far are things which can
be translated directly into 1998 C++.

Which isn't to say that the benefits are only syntactic. The translation
would add details, and the lack of irrelevant detail is part of what
raises the abstraction level. Your SML code omits 3 kinds of detail:

(1) Explicit memory management.
(2) Explicit type declarations.
(3) Names of anonymous functions.

If all 3 were put back in, the code would still be structured the same but
it wouldn't be so clear or so abstract. And I doubt it would still fit in
a page.

I don't think we have an argument here. We're both making the point that
just addressing (3) on its own won't give C++ the full benefits of lambda
as found in SML et al, and that the proposal shouldn't be judged as if it
would.

If you are saying that (1) is more important than (2), then I'm not
disagreeing. I just think both are factors. I couldn't honestly talk about
the success of lambdas in functional languages without mentioning type
inference.

-- Dave Harris, Nottingham, UK

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated.    First time posters: Do this! ]

Thant Tessman wrote:

> My understanding has always been that latently typed was another term
> for dynamically typed, and that the opposite of "manifestly typed" was
> "type inferred" or "implicitly typed." The first web page I googled
> concurred with my understanding. However, I will admit that as I dig
> around, there seems to be no real agreement on the terminology, which
> seems to have changed over the years. And indeed the problem seems to be
> that people have not considered various axes-of-features as independent
> of each other. Note that the first article you cite uses the term in a
> way that seems to correlate more with my understanding than with yours:
>
> 	"Python is an example of latent typing: types are always checked, just
> not at compile time."

That's also inaccurate, in most senses of the word "checked."  It's
fairly rare for any Python program to ask about the type of a variable.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated.    First time posters: Do this! ]

Gabriel Dos Reis wrote:
> Thant Tessman <thant@acm.org> writes:
>
> [...]
>
> | Sorry the example is in SML, but C++ just doesn't cut it for this kind
> | of thing--even with the modifications being discussed in this thread. (I
> | have the same program in Scheme lying around somewhere.) SML infers
> | types as much as it can. But sometimes you need to declare types, and
> | you can always add (redundant) type declarations. Doing so in the
> | example above would do little to detract from the point it was making
> | about the power of functional composition.
>
> And the price of that deceptive facility, i.e. Hindley-Milner typing,
> is the ban of overloading -- except when the language itself declares
> that it knows about some symbols (e.g."+") but do not give programmers
> ways to overload.  OCaml chosed to remain consistent -- and carry the
> logic to the extreme where, for instantce, "*" is for intergers and
> "*." is for floating point.  Haskell removed that limitation through
> "type classes", which in C++ would correspond to abstract class
> templates -- the "Haskell dictionaries" would correspond to "C++ vtables".
>
> Decades of going in circles, with increasing resource spent in
> obfuscation of common sense.


I'll try one more time: Whether a programming language supports
functional composition and how a programming language handles types HAVE
NOTHING TO DO WITH EACH OTHER. I've written exactly the same program in
Scheme. (In fact, I wrote it in Scheme before I wrote it in SML.) Scheme
is dynamically typed, and (with the right libraries) supports
overloading just fine. And I have no doubt the same program could be
easily written in Haskell and OCaml (and Miranda, which, if I remember
correctly, requires type declarations). The difference between all these
languages and C++ is that they support what elsewhere in this thread are
called "full closures." Not coincidentally, they all provide automatic
memory management.

(I happen to prefer SML's module system to OCaml's OO support, but that
is an entirely different subject.)


-thant

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated.    First time posters: Do this! ]

"Dave Harris" <brangdon@cix.co.uk> wrote in message
news:memo.20050114002643.1356A@brangdon.m...

> I don't know of a
> language which combines dynamic type checking with manifestly declared
> types, but it is logically possible and I suspect would be a very good
> idea.

PHP 5 does this. You may optionally declare the type in a signature, and if
the passed-in object is not (derived from) this type, it will give a
run-time error. PHP is dynamically typed.

> I didn't invent this terminology; here are a couple of web pages which use
> it:
>     http://osteele.com/archives/2003/08/test-versus-type
>     http://onestepback.org/articles/usingruby/strong.html
>
> Many other references mix them up.

Yes. Often you see discussions about "strong vs weak typing", when they're
really about static vs dynamic typing. Dynamically typed languages (at least
scripting languages) tend also to have more implicit conversions. However,
as I understand, this is not the same as "weak typing" (or is it? See the
following). BCPL is an example of a weakly typed language (as is e.g.
assembly code), where type errors are not detected. However, may this
definition be used for languages with "eager conversions"? When a language -
such as PHP - permits implicit conversions between almost anything (with
more or less reasonable results), isn't it then also easier to get
undetected type errors, due to using an object in an improper way, but
conversions lets you "get away with it" without error messages?

> That's usually because they don't
> consider all the possibilities; they conflate "latent" with "dynamic"
> which may have  you.

"latent" typing is a terminology that I find confusing in itself, and I
suspect that many wouldn't know (or agree about) what it means, without
reading a definition, somewhere. "implicit" vs "explicit" typing I think
gives a more, er, explicit way of stating what it's about.

> Some people go on to use "inferred types" for
> latent, but that could mean Fortran's feature of deducing a variable's
> type from its name: "i" is always integer, "r" is always real etc.

Hm, well, "type inference" is another common terminology for implicit/latent
typing, and I hardly think people would think of type inferred from the
"names", when they hear about inferred types. At least I think it's less
chance for that, than for someone understanding what "latent typing" means,
without prior definition. Then again, it's hard to tell what "most people"
would think.

> It seems to me that all 4 concepts are important and need names

Indeed. As well as the strong vs weak distinction. I'm also wondering about
the eager/not eager conversion distinction, unless it may be folded into
strong/weak.

>, and the names I use here are the clearest.

There may be some debate about that. :) One of the pages you give link to
above uses "explicit"/"implicit" as the terminology (with
"manifest"/"latent" in parenthesis).
 
>
> It is orthogonal to the issue of type-checking, but not orthogonal to the
> issue of whether types need to be declared. This is because the
> declarations make the lambda more verbose, and an aim of lambda is to be
> concise.
>
> In Java, for example, exception specifications are mandatory. So a Java
> lambda may need to declare its return type, the types of all its
> arguments, and the types of all the exceptions it can throw. That can add
> up to so many names that it is clearer to separate out the function and
> not use lambda at all.

It's interesting that you should mention Java, as Java has its own lambda
"hack", in the form of anonymous inner classes (often used for event
listeners). However, using inheritance from an interface, this relies always
on dynamical dispatch.

Regards,

Terje



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated.    First time posters: Do this! ]

David Abrahams wrote:
> Thant Tessman [quoting a referenced article] wrote:
 
>
>
> That's also inaccurate, in most senses of the word "checked."  It's
> fairly rare for any Python program to ask about the type of a variable.

I'm no Python expert, but my impression was that it was similar to
Scheme in that types aren't associated with variables at all, but with
values. That is, a variable could be assigned e.g. an integer value one
moment, and e.g. a string the next. In this kind of a language, values
carry around with them information about their type, and the types of
*values* (not variables) are checked when the program tries to do
something with them (e.g. add them together). [1] So the quoted
statement not only concurrs with my understanding of Python, but with
with my otherwise supposedly inaccurate understanding of the term
"latently typed." [2]

And again, the main point is that latent...er...dynamic typing has
nothing to do with lambda (beyond the fact that they both as a rule only
exist in languages that support automatic memory management).

-thant


[1] Good compilers will try, for performance reasons, to eliminate
run-time type checks where they have enough information to do so, and
Common Lisp, I understand, allows the programmer to provide optional
type declarations for this purpose.

[2] SML doesn't (for the most part) require type declarations, but it
does all its type checking at compile time. By the above definition, SML
is not latently typed.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated.    First time posters: Do this! ]

Dave Harris wrote:

[...]

> Functional composition is a good thing, and it's something we can already
> do in C++. The lambda proposals don't so much enable it as provide a nicer
> syntax for it. All of the proposals for lambda so far are things which can
> be translated directly into 1998 C++.

Functional composition in C++ is extremely limited, and refering to the
extensions proposed in this thread as "lambda" is misleading.


> Which isn't to say that the benefits are only syntactic. The translation
> would add details, and the lack of irrelevant detail is part of what
> raises the abstraction level. Your SML code omits 3 kinds of detail:
>
> (1) Explicit memory management.
> (2) Explicit type declarations.
> (3) Names of anonymous functions.
>
> If all 3 were put back in, the code would still be structured the same but
> it wouldn't be so clear or so abstract. And I doubt it would still fit in
> a page. [...]

At the end of this post I've appended my lexer generator rewritten to
eliminate all anonymous functions (and currying), and to include
complete explicit type declarations. (I've omitted the comments and the
testing code.) The code is less concise, but not by much. #2 and #3 are
nice things for a language to make optional when it can, but it should
be clear that the expressive power of functional composition is
something else entirely.

As for #1, it is a necessary, but not sufficient, precondition for
providing the advantages of functional composition.

-thant



---begin example---

type stream = char list * char list;
type streams = stream list;
type matcher = streams -> streams;
type matchers = matcher list;

fun tok (t : char) : matcher =
let fun f (s,h::r) = if h=t then SOME (h::s,r) else NONE
| f _ = NONE
in List.mapPartial f
end

fun applyToStreams (f : matcher, s : streams) : streams = f s

fun seq (rules : matchers) : matcher =
let fun f (streams : streams) : streams =
foldl applyToStreams streams rules
in f end

fun bar (rules : matchers) : matcher =
let fun f (streams : streams) : streams =
let fun g (f : matcher) : streams = f streams
in List.concat (map g rules) end
in f end

fun star (rule : matcher) : matcher =
let fun f (streams : streams) : streams =
let fun loop (streams : streams) : streams list =
case (rule streams) of
[] => []
| results => results::(loop results)
in List.concat (streams::(loop streams)) end
in f end

fun pos (rule : matcher) : matcher = seq [rule, star rule]

fun opt (rule : matcher) : matcher = bar [rule, fn x => x]

fun range (a : char, b : char) : matcher =
if b<a then range (b,a) else
let fun loop (i : int) : matchers = if (i<=Char.ord b)
then (tok (Char.chr i)) :: loop (i+1)
else []
in bar (loop (Char.ord a))
end

fun lit (s : string) : matcher = seq (map tok (String.explode s))

fun set (s : string) : matcher = bar (map tok (String.explode s))

---end example---

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated.    First time posters: Do this! ]

thant@acm.org (Thant Tessman) wrote (abridged):
> Functional composition in C++ is extremely limited, and refering to the
> extensions proposed in this thread as "lambda" is misleading.

OK; I'm not disagreeing with that. I've continued to use that name only
because I've not seen a good alternative. I don't like "anonymous
function" because these things are not functions, and I think "closure"
has the same or worst problems as "lambda". What name do you suggest we
use?

Also, what further features would be needed before you'd accept that C++
had genuine lambdas?


> At the end of this post I've appended my lexer generator rewritten to
> eliminate all anonymous functions (and currying), and to include
> complete explicit type declarations.

I agree that GC is more important than anonymous functions and explicit
type declarations.

I'm afraid I don't understand SML well enough to really follow what your
code is doing. In particular, to see what a C++ 1998 version would look
like, using structs for closures and smart pointers for garbage
collection. I imagine it would be several times more verbose, but would
still be recognisably structured the same.

-- Dave Harris, Nottingham, UK

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated.    First time posters: Do this! ]