Questions about Common Lisp
comp.lang.scheme
decided to post them here because my starting point to Common Lisp is
Scheme.
(1) First question.
I have inherited a very old book that teaches Common Lisp. The book
was published in 1989, which means that it is two years my elder.
Believe it or not, the book was published before I was born! That is
old! The author is a certain Patrick Winston. Since Lisp (CL and
Scheme) are much more advanced than Java and Python, I concluded that
it was invented many years after Python, PHP or Java. I was amazed to
find out that in 1989 there were people writing books about Lisp!
Winston's book teaches that one must quote lambda expressions with #'
in order to use them. For instance, a program to find the permutations
of a list should be written thus:
(defun prm(b)
(if (null b) '(())
(mapcan #'(lambda(e)
(mapcar #'(lambda(p) (cons e p))
(prm (remove e b)) ) ) b)))
However, I tried to write the program using the Scheme convention:
(defun prm(b)
(if (null b) '(())
(mapcan (lambda(e)
(mapcar (lambda(p) (cons e p))
(prm (remove e b)) ) ) b)))
It worked perfectly well both in the Steel Bank Common Lisp and in
Maxima's underlying Lisp. If Common Lisp accepts the same conventions
as Scheme, what is the use of the #' quotation sign? One of my
theories is that modern Common Lisp is closer to Scheme than the
Ancient Common Lisp that Winston used to write his book. Possibly
Winston wrote his book right away after the design of Lisp. A few
design errors were fixed, and the useless #' function quotation mark
was removed. Is that so? In fact, the book gives me the impression
that Lisp was created not long before it was written.
(2) Second question.
I already noticed that Scheme does numerical calculations as fast as
C. I also read that Common Lisp is as fast as C too. I visited a site
where the author claims that CMU Common Lisp and Steel Bank Common
Lisp are as fast as C for numerical calculations. Unfortunately, all
benchmarks are limited to shifting array elements around. In any
case, I tried the benchmarks without optimizing the C code, and SBCL
was, indeed, as fast as C without optimization. However, when I was
comparing Scheme to C, I learned a few options for improving C
compilation:
-O3
-fomit-frame-pointer
-freg-struct-return
-malign-double
-march=prescott
-ffast-math
With these options, C becomes two times faster than SBCL. Since a lot
of people claim that Common Lisp is really as fast as C in many kind
of applications, I guess I am missing something. In Linux, I am using
CMUCL, and in Windows I am using SBCL.
(3) I did not find anything comparable to the named let. How Common
Lispers do when they need an on-the-fly recursive function?
(4) Since Lisp is around since 1989, how old are Python and Java?
Although Python looks quite primitive, it seems that Scheme and Lisp
draw many ideas from it. In fact, Scheme looks like an improved
Python: A more regular and easier to learn and handle (automatically)
syntax, more data types, tail call optimization, match-case, type
inference that leads to faster and safer programs, a better notation
for lists, compilation, etc. I wonder why Python programmers did not
swich to Scheme, when it was invented. I guess that the reason for
them sticking to Python is that there were a huge amount of code
already written in Python when Lisp was invented. Is that so?
Barry Margolin
<624672e7-dca7-46fa...@41g2000yqf.googlegroups.com>,
"comp.lang.scheme" <phi5...@yahoo.ca> wrote:
The original description of Common Lisp required it. But during the
ANSI standardization of Common Lisp, we added a LAMBDA macro that
expands (LAMBDA ...) into (FUNCTION (LAMBDA ...)). So you don't have to
use #' before lambda expressions any more. You still need it before
function names in many cases, particularly if you're referencing a local
function defined with FLET or LABELS.
> theories is that modern Common Lisp is closer to Scheme than the
> Ancient Common Lisp that Winston used to write his book. Possibly
I wouldn't say it's "closer to Scheme", we just added this one
convenience macro.
> Winston wrote his book right away after the design of Lisp. A few
> design errors were fixed, and the useless #' function quotation mark
> was removed. Is that so? In fact, the book gives me the impression
> that Lisp was created not long before it was written.
Lisp recently celebrated its 50th birthday. The Common Lisp dialect was
developed in the mid 80's, though, a few years after Scheme.
> (3) I did not find anything comparable to the named let. How Common
> Lispers do when they need an on-the-fly recursive function?
LABELS
> (4) Since Lisp is around since 1989, how old are Python and Java?
Lisp has been around since 1959, Scheme since the late 70's, Common Lisp
the mid 80's. Python was first developed in the late 80's, Java in the
mid 90's (it was developed for use with web pages, so it couldn't
predate the WWW).
> Although Python looks quite primitive, it seems that Scheme and Lisp
> draw many ideas from it. In fact, Scheme looks like an improved
> Python: A more regular and easier to learn and handle (automatically)
> syntax, more data types, tail call optimization, match-case, type
> inference that leads to faster and safer programs, a better notation
> for lists, compilation, etc. I wonder why Python programmers did not
> swich to Scheme, when it was invented. I guess that the reason for
> them sticking to Python is that there were a huge amount of code
> already written in Python when Lisp was invented. Is that so?
You've got things totally backwards. Python and Java took ideas from
Scheme and Lisp.
I suggest you check out their Wikipedia pages.
--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Marek Kubica
"comp.lang.scheme" <phi5...@yahoo.ca> wrote:
> (4) Since Lisp is around since 1989, how old are Python and Java?
1991 and 1995, respectively. The Java spec was co-written by Guy L.
Steele, one of the designers of Scheme.
> In fact, Scheme looks like an improved Python:
Infact Python has many similarities to Scheme. I wouldn't say that it
is improved Scheme but OTOH Scheme is not an improved Python. They did
things right that the other did wrong.
> A more regular and easier to learn and handle (automatically)
> syntax,
Handling code automatically is not a big concern if you don't have
macros. And the Python-Syntax is, if you ask starters, quite friendly.
I admit liking both. There are also people who like neither.
> more data types,
Actually, I doubt that Scheme has more data types than Python. Maybe it
depends on what you compare: datatypes build into the language or these
shipped in the Standard Library.
> I wonder why Python programmers did not swich to Scheme, when it was
> invented.
First, there was no Python and secondly.. maybe because it didn't fit
their needs? You should consider that not every features that you
mention that matters to you might neccessarily matter to others. I find
myself wondering how people can work with Java which is missing about
any functional feature you can think of. Somehow they manage.
regards,
Marek
Pascal J. Bourguignon
> With these options, C becomes two times faster than SBCL. Since a lot
> of people claim that Common Lisp is really as fast as C in many kind
> of applications, I guess I am missing something. In Linux, I am using
> CMUCL, and in Windows I am using SBCL.
Assume you have a F1 car and a Beatle.
If your purpose is to see which will go around a circuit faster guess which?
Now if your purpose is to traverse a continent guess which car will be fastest?
What is more useful, to go around in circles, or to traverse
continents (or go fetch your shopping)?
And finally, for people who still insist that a F1 is better because
it goes faster around the circuit, you could still play some tricks,
using a fast motor, removing unneeded devices, customize your Beatle,
and make it a race Beatle with reactor to go fast around circuits.
To understand what it means for C to be fast C vs. Common Lisp (or
Scheme), compare:
int f(int x){ (defun f (x)
return((x<1)?1:x*f(x-1));} (if (< x 1) 1 (* x (f (1- x)))))
printf(f(20)); vs. (print (f 20))
--
__Pascal Bourguignon__
Pascal Costanza
> (2) Second question.
> I already noticed that Scheme does numerical calculations as fast as
> C. I also read that Common Lisp is as fast as C too. I visited a site
> where the author claims that CMU Common Lisp and Steel Bank Common
> Lisp are as fast as C for numerical calculations. Unfortunately, all
> benchmarks are limited to shifting array elements around. In any
> case, I tried the benchmarks without optimizing the C code, and SBCL
> was, indeed, as fast as C without optimization. However, when I was
> comparing Scheme to C, I learned a few options for improving C
> compilation:
>
> -O3
> -fomit-frame-pointer
> -freg-struct-return
> -malign-double
> -march=prescott
> -ffast-math
>
> With these options, C becomes two times faster than SBCL. Since a lot
> of people claim that Common Lisp is really as fast as C in many kind
> of applications, I guess I am missing something. In Linux, I am using
> CMUCL, and in Windows I am using SBCL.
See http://www.lrde.epita.fr/~didier/research/verna.06.ecoop.pdf
> (3) I did not find anything comparable to the named let. How Common
> Lispers do when they need an on-the-fly recursive function?
The equivalent to Scheme's letrec is labels. There is no direct
equivalent to named let, but that's just a macro definition away.
> (4) Since Lisp is around since 1989, how old are Python and Java?
> Although Python looks quite primitive, it seems that Scheme and Lisp
> draw many ideas from it. In fact, Scheme looks like an improved
> Python: A more regular and easier to learn and handle (automatically)
> syntax, more data types, tail call optimization, match-case, type
> inference that leads to faster and safer programs, a better notation
> for lists, compilation, etc. I wonder why Python programmers did not
> swich to Scheme, when it was invented. I guess that the reason for
> them sticking to Python is that there were a huge amount of code
> already written in Python when Lisp was invented. Is that so?
LOL
Pascal
--
ELS'09: http://www.european-lisp-symposium.org/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Waldek Hebisch
> (2) Second question.
> I already noticed that Scheme does numerical calculations as fast as
> C. I also read that Common Lisp is as fast as C too. I visited a site
> where the author claims that CMU Common Lisp and Steel Bank Common
> Lisp are as fast as C for numerical calculations. Unfortunately, all
> benchmarks are limited to shifting array elements around. In any
> case, I tried the benchmarks without optimizing the C code, and SBCL
> was, indeed, as fast as C without optimization. However, when I was
> comparing Scheme to C, I learned a few options for improving C
> compilation:
>
> -O3
> -fomit-frame-pointer
> -freg-struct-return
> -malign-double
> -march=prescott
> -ffast-math
>
> With these options, C becomes two times faster than SBCL. Since a lot
> of people claim that Common Lisp is really as fast as C in many kind
> of applications, I guess I am missing something. In Linux, I am using
> CMUCL, and in Windows I am using SBCL.
>
The blanket claim "Common Lisp is as fast as C" is simply
false. On compute-intensive problems the factor of two between
sbcl and gcc is typical. You missed the fact that:
1) given reasonably imprecise speed claim you can typically manufacture
benchmark which supports it. Unfortunatly, single benchmark gives
you just a single data point. Good benchark comparing language
implementations will try representaive programs coded equally well
in both languages, but it is pretty easy to overlook important
factors and get misleading results.
2) a lot of people exaggerate: given that on compute intensive
problems interpreted implementations (like standard Python)
are about 100 times slower than gcc, beeing "only" two times
slower puts sbcl and gcc in one class and say Python in another.
3) many important problems are _not_ compute-intensive. Memory
access tends to flatten speed difference. Input-output may
completly dominate over computation time. Or computations
are done in a specialized library and main program just
works as a driver. In such cases speed differeces between
gcc compiled C and sbcl compiled Lisp may be not measurable
(or not worth to measure).
--
Waldek Hebisch
heb...@math.uni.wroc.pl
Taylor Venable
> It worked perfectly well both in the Steel Bank Common Lisp and in
> Maxima's underlying Lisp. If Common Lisp accepts the same conventions
> as Scheme, what is the use of the #' quotation sign?
Common Lisp *accepts* the same conventions of Scheme, but the
underlying reasons are different. In Common Lisp, an identifier can
refer to both functions and data; the #' is used to access the
function namespace. For example (in SBCL):
========[ EXAMPLE ]=============================================
This is SBCL 1.0.25, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* <
debugger invoked on a UNBOUND-VARIABLE: The variable < is unbound.
Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL.
restarts (invokable by number or by possibly-abbreviated name):
0: [ABORT] Exit debugger, returning to top level.
(SB-INT:SIMPLE-EVAL-IN-LEXENV < #<NULL-LEXENV>)
0] 0
* #'<
#<FUNCTION <>
* (let ((< 3) (> 4)) (list (< < >) (> < >)))
(T NIL)
================================================================
You'll often see #' used with higher-order functions that accept
functions like REDUCE and MAPCAR. Scheme, however, has only one
namespace for identifiers, so when you do this (in Chicken):
========[ EXAMPLE ]=============================================
CHICKEN
(c)2008 The Chicken Team
(c)2000-2007 Felix L. Winkelmann
Version 3.5.1 - openbsd-unix-gnu-x86 [ manyargs dload ptables applyhook ]
SVN rev. 13412 compiled 2009-02-26 on zeltennia.metasyntax.net (OpenBSD)
#;1> <
#<procedure C_lessp>
#;2> (let ((< 3) (> 4)) (list (< < >) (> < >)))
Error: call of non-procedure: 3
Call history:
<syntax> (let ((< 3) (> 4)) (list (< < >) (> < >)))
<syntax> (begin (list (< < >) (> < >)))
<syntax> (list (< < >) (> < >))
<syntax> (< < >)
<syntax> (> < >)
<eval> (list (< < >) (> < >))
<eval> (< < >) <--
================================================================
You can see that being in the position of a function which is applied
has no special meaning in Scheme like it does in Common Lisp.
For more information, see [http://en.wikipedia.org/wiki/Common_Lisp#The_function_namespace].
--
Taylor Christopher Venable
http://real.metasyntax.net:2357/
comp.lang.scheme
Very good explanation. Thank you very much.
comp.lang.scheme
You are write. I would never switch to C if the only gain is a factor
of 2 in speed. I also agree with you about the philosophy of
benchmarking. In fact, the only benchmark that I take in consideration
are assignments and homeworks given by my teachers of Numerical
Methods, Computer Graphics, and Artificial Intelligence. Since these
exercises were designed without benchmarks in view, they are not
biased. I noticed that Stalin and Bigloo are indeed fast.
comp.lang.scheme
Ops! I wrote "You are write", instead of "You are right".
Ray Dillinger
> I have a few questions about Common Lisp (and Python and Java), and
> decided to post them here because my starting point to Common Lisp is
> Scheme.
>
> (1) First question.
> I have inherited a very old book that teaches Common Lisp. The book
> was published in 1989, which means that it is two years my elder.
> Believe it or not, the book was published before I was born! That is
> old! The author is a certain Patrick Winston. Since Lisp (CL and
> Scheme) are much more advanced than Java and Python, I concluded that
> it was invented many years after Python, PHP or Java. I was amazed to
> find out that in 1989 there were people writing books about Lisp!
Lisp was spec'd in 1958 and the first implementation was in 1959.
As an idea, it's fifty years old. So, it's not just older than you,
it's probably older than your instructor. Lisp and FORTRAN are the
two oldest programming languages still in use. Common Lisp, in
particular, has been around since about 1983-4, a good 5 years
before the book you inherited was written, and represents a
public consolidation of many earlier proprietary derivatives of
the original 1959 Lisp.
Scheme was originally implemented in the middle 1970's (so it's older
than Common Lisp) as an investigation into some aspects of Object-
Oriented programming (an idea not yet current at the time) and has
matured as an effort to strip away unnecessary syntactic and semantic
cruft and while leaving everything expressible or implementable.
The Lisp book you have will teach you a version of the programming
language that will still work on current Common Lisp systems and which
will not look at all strange to modern Common Lisp programmers. The
only really new/revamped thing since then is CLOS (which is a very
complete object-oriented programming system, widely used by people
who use Common Lisp) and the MOP or MetaObject Protocol (which
allows CLOS to be customized, but most programs don't touch the MOP).
Most of Lisp's history has been spent waiting for the rest of the
programming language design community to catch up. Indeed, we're still
waiting. Java was designed and implemented by a team led by Guy Steele,
who is the same Guy Steele who earlier developed Scheme. The
"sacrifices" that leave Scheme the more advanced language of the two
were made for the sake of mainstream acceptance. It turns out that
most people don't like the parenthesized prefix syntax and by making
it something more like C++ (which is what people were used to at the
time) he managed to get them to accept into the mainstream a lot of
ideas that originated in Lisp but at that time didn't exist in
mainstream languages (like garbage collection). He sacrificed certain
features like syntactic abstraction, but most mainstream programmers
have never heard of it and won't miss it.
Dylan was an earlier attempt at the same general thing, (Lisp'ish
semantics in a C++'ish syntax) but never had a big-muscle (big-
money) company like SUN or a 'killer app' like mobile code for
browsers behind it so, even though it may have been semantically
cleaner (and preserved syntactic abstraction, albeit painfully),
it never quite made it.
For the most part every time a new language comes out, we look
at the syntax, because sometimes there are nice new syntax
inventions that make it easier for humans to conceive of and
reason about some classes of problems. But then we look at the
semantics to see what Lisp features it *lacks*. Semantically,
there hasn't been anything really new (except maybe monads)
for at least 30 years, that wasn't in Lisp first.
Welcome to Lisp, kid. It's been here all along.
Bear
Michele Simionato
wrote: Semantically,
> there hasn't been anything really new (except maybe monads)
> for at least 30 years, that wasn't in Lisp first.
What about Hindley-Milner type inference, Algebraic Data Types
and such? But perhaps they are older than 30 years ...
M. Simionato
Ray Dillinger
These do not add to the semantics of a language. They
provide ways of expressing and reasoning about semantic
restrictions (type restrictions) which Lisps generally
do not have in the first place.
They can be used (and have been used) to write Lisp systems
that produce more efficient object code, of course, by
proving that certain cases will or won't ever occur and
that certain errors do or don't have to be checked for.
But optimization techniques are not semantic extensions,
and do not change the semantics of correct Lisp programs.
Bear
Elena
> Michele Simionato wrote:
> > On Mar 15, 7:22 pm, Ray Dillinger <b...@sonic.net>
> > wrote: Semantically,
> >> there hasn't been anything really new (except maybe monads)
> >> for at least 30 years, that wasn't in Lisp first.
>
> > What about Hindley-Milner type inference, Algebraic Data Types
> > and such? But perhaps they are older than 30 years ...
>
>
> They can be used (and have been used) to write Lisp systems
Well, they are used to help programmers to write correct programs too,
so I wouldn't say they do not add to the semantics of a language. The
compiler wouldn't reject incorrect typed programs otherwise.
I'd bet Lispers dismiss such functionality because it can't be
implemented by macros ;-)
Pascal J. Bourguignon
It can.
It is dismissed, because it doesn't help much in reducing bugs, or
time to delivery, on the contrary. The problem being that even with a
very sophisticated type system, there are simple useful programs that
cannot be verified by the compiler, that must be verified with test
suites anyways. Checking the types dynamically, at run-time is as
safe, and it is more efficient in terms of programmer time.
--
__Pascal Bourguignon__
Elena
wrote:
> Elena <egarr...@gmail.com> writes:
> > I'd bet Lispers dismiss such functionality because it can't be
> > implemented by macros ;-)
>
> It can.
>
> It is dismissed, because it doesn't help much in reducing bugs, or
> time to delivery, on the contrary.
Come on, Pascal, you can't be serious. Are you? ^_^
You have made me remember about a Common Lisp package which tried to
implement Design by Contract. Very interesting demonstration of Common
Lisp's power, but not quite the real thing. Maybe it just wasn't the
implementor's main goal...
Anyway, you made a point: in everyday work, I'm feeling more and more
hampered by the compiler's requirement for always perfect type
correctness.
Pascal J. Bourguignon
> On 18 Mar, 20:42, p...@informatimago.com (Pascal J. Bourguignon)
> wrote:
>> Elena <egarr...@gmail.com> writes:
>> > I'd bet Lispers dismiss such functionality because it can't be
>> > implemented by macros ;-)
>>
>> It can.
>>
>> It is dismissed, because it doesn't help much in reducing bugs, or
>> time to delivery, on the contrary.
>
> Come on, Pascal, you can't be serious. Are you? ^_^
Yes, I am. This has been discussed almost to death in cll. Use
google groups.
> You have made me remember about a Common Lisp package which tried to
> implement Design by Contract. Very interesting demonstration of Common
> Lisp's power, but not quite the real thing. Maybe it just wasn't the
> implementor's main goal...
>
> Anyway, you made a point: in everyday work, I'm feeling more and more
> hampered by the compiler's requirement for always perfect type
> correctness.
Indeed. On the other hand, I'm not against (and regret a little a
felt lack of) tools to do global analyses (be it type inference or
other) and all kind of "symbolic" analysis, proof, debugging, etc.
There are some commercial products, mainly targeted at C++ or Java,
but nothing AFAIK for CL or even Scheme. (eg. there is a "debugging
in time" google video demonstrating an interesting debugger, but only
for Java on the JVM. We'd like to have something similar for Lisp).
http://video.google.fr/videoplay?docid=3897010229726822034&ei=A2nBSYHBGsyA-AbJp5mPAw
--
__Pascal Bourguignon__
Pascal Costanza
> Elena <egar...@gmail.com> writes:
>
>> On 18 Mar, 20:42, p...@informatimago.com (Pascal J. Bourguignon)
>> wrote:
>>> Elena <egarr...@gmail.com> writes:
>>>> I'd bet Lispers dismiss such functionality because it can't be
>>>> implemented by macros ;-)
>>> It can.
>>>
>>> It is dismissed, because it doesn't help much in reducing bugs, or
>>> time to delivery, on the contrary.
>> Come on, Pascal, you can't be serious. Are you? ^_^
>
> Yes, I am. This has been discussed almost to death in cll. Use
> google groups.
Depending on how your type system is defined, static types can actually
introduce bugs.
See http://p-cos.net/documents/dynatype.pdf
Sam TH
If your Lisp is sufficently expressive, you can express types using
it. In particular, I've implemented Typed Scheme, a typed dialect of
PLT Scheme, entirely using the PLT Scheme macro system.
For more on Typed Scheme, see here:
http://www.ccs.neu.edu/home/samth/typed-scheme/
Here's a paper about the implementation:
http://www.ccs.neu.edu/scheme/pubs/#scheme2007-ctf
sam th
Sam TH
>
> >> On 18 Mar, 20:42, p...@informatimago.com (Pascal J. Bourguignon)
> >> wrote:
> >>> Elena <egarr...@gmail.com> writes:
> >>>> I'd bet Lispers dismiss such functionality because it can't be
> >>>> implemented by macros ;-)
> >>> It can.
>
> >>> It is dismissed, because it doesn't help much in reducing bugs, or
> >>> time to delivery, on the contrary.
> >> Come on, Pascal, you can't be serious. Are you? ^_^
>
> > Yes, I am. This has been discussed almost to death in cll. Use
> > google groups.
>
> Depending on how your type system is defined, static types can actually
> introduce bugs.
>
> See http://p-cos.net/documents/dynatype.pdf
Your paper, while interesting, does not show static type systems
introducing bugs. They show that poorly-designed languages (those
with null) make it easy to add bugs when trying to work around a
static type system. Also, it shows that programming in a non-OO style
in Java is inconvenient in some cases.
Returning to the first point, imagine that we had an untyped Java.
And we were trying to implement a method that took a Frob f to
process, and boolean b that told us how to process it, and we would
return a Quux. If we were in the middle of development, we might do
this:
meth(f, b) {
if b then {
new Quux(f.getFrob1())
}
else {
// not yet implemented
return null;
}
This is just as bad as the example in your paper, but it is not at all
related to dynamic vs static typing. The problem here is with the
existence of null, not with type systems. For example, Haskell, a
*very* statically typed language, has a form named `undefined', which
you can put anywhere, and it raises an error when evaluated. If the
ease of not implementing things were my primary consideration, Haskell
would win out over other languages, typed or untyped.
Type systems are not the be-all and end-all of software correctness,
nor are they the right solution for every problem. But in the cases
where they are helpful, it's extremely useful to have static checks of
some properties of your program, so that you don't have to discover
those problems later (or perhaps not until your users experience the
bug), or re-verify those problems the next time you come back to a
piece of code. Does this absolve you of the responsibility to unit
test, etc? Of course not. But that doesn't make it not useful.
sam th
Pascal Costanza
> On Mar 19, 3:28 am, Pascal Costanza <p...@p-cos.net> wrote:
>> Pascal J. Bourguignon wrote:
>>> Elena <egarr...@gmail.com> writes:
>>>> On 18 Mar, 20:42, p...@informatimago.com (Pascal J. Bourguignon)
>>>> wrote:
>>>>> Elena <egarr...@gmail.com> writes:
>>>>>> I'd bet Lispers dismiss such functionality because it can't be
>>>>>> implemented by macros ;-)
>>>>> It can.
>>>>> It is dismissed, because it doesn't help much in reducing bugs, or
>>>>> time to delivery, on the contrary.
>>>> Come on, Pascal, you can't be serious. Are you? ^_^
>>> Yes, I am. This has been discussed almost to death in cll. Use
>>> google groups.
>> Depending on how your type system is defined, static types can actually
>> introduce bugs.
>>
>> See http://p-cos.net/documents/dynatype.pdf
>
> Your paper, while interesting, does not show static type systems
> introducing bugs.
Yes, it does. The examples show code that rely on the type system to
ensure "correctness" (of something), but where you get the counter effect.
> They show that poorly-designed languages (those
> with null) make it easy to add bugs when trying to work around a
> static type system. Also, it shows that programming in a non-OO style
> in Java is inconvenient in some cases.
>
> Returning to the first point, imagine that we had an untyped Java.
> And we were trying to implement a method that took a Frob f to
> process, and boolean b that told us how to process it, and we would
> return a Quux. If we were in the middle of development, we might do
> this:
>
> meth(f, b) {
> if b then {
> new Quux(f.getFrob1())
> }
> else {
> // not yet implemented
> return null;
> }
>
> This is just as bad as the example in your paper, but it is not at all
> related to dynamic vs static typing.
Sure. But proponents of dynamic languages typically don't argue that
dynamic typing helps to reduce bugs when compared to static typing. Only
the proponents of static languages say that static typing helps to
reduce bugs. I only need one counter example to show that this claim is
wrong, but I actually have shown three.
> The problem here is with the
> existence of null, not with type systems.
Indeed, the value of a language lies in the combination of its
constituent feature, not in single constituent features themselves.
> For example, Haskell, a
> *very* statically typed language, has a form named `undefined', which
> you can put anywhere, and it raises an error when evaluated.
You mean something like (error "bla") in Scheme or Common Lisp?
> Type systems are not the be-all and end-all of software correctness,
> nor are they the right solution for every problem.
We're in heavy agreement here.
> But in the cases
> where they are helpful, it's extremely useful to have static checks of
> some properties of your program, so that you don't have to discover
> those problems later (or perhaps not until your users experience the
> bug), or re-verify those problems the next time you come back to a
> piece of code. Does this absolve you of the responsibility to unit
> test, etc? Of course not. But that doesn't make it not useful.
In the presence of unit tests, static typing becomes much less interesting.
Pascal J. Bourguignon
> Returning to the first point, imagine that we had an untyped Java.
Perhaps you mean a dynamically typed Java.
> And we were trying to implement a method that took a Frob f to
> process, and boolean b that told us how to process it, and we would
> return a Quux. If we were in the middle of development, we might do
> this:
>
> meth(f, b) {
> if b then {
> new Quux(f.getFrob1())
> }
> else {
> // not yet implemented
> return null;
> }
>
> This is just as bad as the example in your paper, but it is not at all
> related to dynamic vs static typing. The problem here is with the
> existence of null, not with type systems. For example, Haskell, a
> *very* statically typed language, has a form named `undefined', which
> you can put anywhere, and it raises an error when evaluated. If the
> ease of not implementing things were my primary consideration, Haskell
> would win out over other languages, typed or untyped.
If, admitedly, (error "undefined") is too much work, you can always
(defun undefined () (error "undefined")) and use the form (undefiend),
which you can put anywhere in lisp too. Perhahs Haskell wins over
other languages, but the difference is not made on this feature.
> Type systems are not the be-all and end-all of software correctness,
> nor are they the right solution for every problem. But in the cases
> where they are helpful, it's extremely useful to have static checks of
> some properties of your program, so that you don't have to discover
> those problems later (or perhaps not until your users experience the
> bug), or re-verify those problems the next time you come back to a
> piece of code. Does this absolve you of the responsibility to unit
> test, etc? Of course not. But that doesn't make it not useful.
Having a dynamic language doesn't prevent writting static analysis
tools, including static type checkers. Some lisp compilers even
include one, such a sbcl.
--
__Pascal Bourguignon__
Sam TH
> Sam TH wrote:
> > On Mar 19, 3:28 am, Pascal Costanza <p...@p-cos.net> wrote:
> >> Pascal J. Bourguignon wrote:
> >>> Elena <egarr...@gmail.com> writes:
> >>>> On 18 Mar, 20:42, p...@informatimago.com (Pascal J. Bourguignon)
> >>>> wrote:
> >>>>> Elena <egarr...@gmail.com> writes:
> >>>>>> I'd bet Lispers dismiss such functionality because it can't be
> >>>>>> implemented by macros ;-)
> >>>>> It can.
> >>>>> It is dismissed, because it doesn't help much in reducing bugs, or
> >>>>> time to delivery, on the contrary.
> >>>> Come on, Pascal, you can't be serious. Are you? ^_^
> >>> Yes, I am. This has been discussed almost to death in cll. Use
> >>> google groups.
> >> Depending on how your type system is defined, static types can actually
> >> introduce bugs.
>
>
> > Your paper, while interesting, does not show static type systems
> > introducing bugs.
>
> Yes, it does. The examples show code that rely on the type system to
> ensure "correctness" (of something), but where you get the counter effect.
In all your examples, the guarantees of the Java type system are
maintained. Type systems do not prove "correctness". They prove the
absence of certain well-specified classes of errors (at least, sound
ones do).
> > They show that poorly-designed languages (those
> > with null) make it easy to add bugs when trying to work around a
> > static type system. Also, it shows that programming in a non-OO style
> > in Java is inconvenient in some cases.
>
> > Returning to the first point, imagine that we had an untyped Java.
> > And we were trying to implement a method that took a Frob f to
> > process, and boolean b that told us how to process it, and we would
> > return a Quux. If we were in the middle of development, we might do
> > this:
>
> > meth(f, b) {
> > if b then {
> > new Quux(f.getFrob1())
> > }
> > else {
> > // not yet implemented
> > return null;
> > }
>
> > This is just as bad as the example in your paper, but it is not at all
> > related to dynamic vs static typing.
>
> Sure. But proponents of dynamic languages typically don't argue that
> dynamic typing helps to reduce bugs when compared to static typing. Only
> the proponents of static languages say that static typing helps to
> reduce bugs. I only need one counter example to show that this claim is
> wrong, but I actually have shown three.
The claim that you appear to be arguing against is a language with a
static type system will have programs which have strictly fewer bugs
than similar programs in untyped languages. First, I don't think
anyone makes this strong claim. Second, you have not disproved it.
You've shown that sometimes, in Java, the easiest way to work around
the type system is to introduce a bug. This is true for almost any
aspect of language semantics, and has nothing to do with type
systems. You've also demonstrated that sometimes people want to
partially implement interfaces, and Java doesn't let them do that.
This is a claim about a particular type system, and one that we could
argue about the merits of. But it's not about type systems in
general.
> > The problem here is with the
> > existence of null, not with type systems.
>
> Indeed, the value of a language lies in the combination of its
> constituent feature, not in single constituent features themselves.
But null is the problem, whether or not you have type systems.
> > For example, Haskell, a
> > *very* statically typed language, has a form named `undefined', which
> > you can put anywhere, and it raises an error when evaluated.
>
> You mean something like (error "bla") in Scheme or Common Lisp?
Yes, but much more useful due to lazy evaluation.
> > But in the cases
> > where they are helpful, it's extremely useful to have static checks of
> > some properties of your program, so that you don't have to discover
> > those problems later (or perhaps not until your users experience the
> > bug), or re-verify those problems the next time you come back to a
> > piece of code. Does this absolve you of the responsibility to unit
> > test, etc? Of course not. But that doesn't make it not useful.
>
> In the presence of unit tests, static typing becomes much less interesting.
This isn't true at all. First, you're assuming, as many people do,
that the only point of static type systems is to ensure that simply
operations aren't trivially misapplied. However, type systems provide
other, even more significant, functionality. For example, they serve
as guaranteed-correct documentation about the inputs and outputs of an
interface. Second, theorems (such as those proved by type systems)
and tests provide incomparable benefits. Dijkstra had some useful
things to say on this point.
sam th
Elena
> If your Lisp is sufficently expressive, you can express types using
> it. In particular, I've implemented Typed Scheme, a typed dialect of
> PLT Scheme, entirely using the PLT Scheme macro system.
We were talking about type inference, not type declarations. Great and
useful work, anyway :-)
Sam TH
wrote:
> Sam TH <sam...@gmail.com> writes:
> > Returning to the first point, imagine that we had an untyped Java.
>
> Perhaps you mean a dynamically typed Java.
No, I meant "untyped". The term "dynamically typed" is useless, and
contradictory in most of its uses. [1]
> > And we were trying to implement a method that took a Frob f to
> > process, and boolean b that told us how to process it, and we would
> > return a Quux. If we were in the middle of development, we might do
> > this:
>
> > meth(f, b) {
> > if b then {
> > new Quux(f.getFrob1())
> > }
> > else {
> > // not yet implemented
> > return null;
> > }
>
> > This is just as bad as the example in your paper, but it is not at all
> > related to dynamic vs static typing. The problem here is with the
> > existence of null, not with type systems. For example, Haskell, a
> > *very* statically typed language, has a form named `undefined', which
> > you can put anywhere, and it raises an error when evaluated. If the
> > ease of not implementing things were my primary consideration, Haskell
> > would win out over other languages, typed or untyped.
>
> If, admitedly, (error "undefined") is too much work, you can always
> (defun undefined () (error "undefined")) and use the form (undefiend),
> which you can put anywhere in lisp too. Perhahs Haskell wins over
> other languages, but the difference is not made on this feature.
Note that laziness makes the Haskell feature substantially more
powerful than anything you can write in CL or Scheme.
> > Type systems are not the be-all and end-all of software correctness,
> > nor are they the right solution for every problem. But in the cases
> > where they are helpful, it's extremely useful to have static checks of
> > some properties of your program, so that you don't have to discover
> > those problems later (or perhaps not until your users experience the
> > bug), or re-verify those problems the next time you come back to a
> > piece of code. Does this absolve you of the responsibility to unit
> > test, etc? Of course not. But that doesn't make it not useful.
>
> Having a dynamic language doesn't prevent writting static analysis
> tools, including static type checkers. Some lisp compilers even
> include one, such a sbcl.
SBCL does not, to my knowledge, ensure the absence of any class of
errors. Can you describe what it's typechecker verifies?
sam th
[1] We could imagine a program that dynamically enforced some safety
properties, but that isn't what people typically mean by "dynamically
typed".
Pascal Costanza
Well, type errors, to be more precise. That is, states that are defined
to be errors by the type system. Which may actually not be errors.
That's what the claims typically sound like. (See Elena's claims in this
thread, for example.)
> Second, you have not disproved it.
Yes, with regard to such claims.
>>> The problem here is with the
>>> existence of null, not with type systems.
>> Indeed, the value of a language lies in the combination of its
>> constituent feature, not in single constituent features themselves.
>
> But null is the problem, whether or not you have type systems.
Null can be made not to be a problem. See Objective-C's treatment of
null, or generic functions as in Common Lisp or some Scheme systems, for
example.
>>> For example, Haskell, a
>>> *very* statically typed language, has a form named `undefined', which
>>> you can put anywhere, and it raises an error when evaluated.
>> You mean something like (error "bla") in Scheme or Common Lisp?
>
> Yes, but much more useful due to lazy evaluation.
Ugh, that's an unrelated feature.
>>> But in the cases
>>> where they are helpful, it's extremely useful to have static checks of
>>> some properties of your program, so that you don't have to discover
>>> those problems later (or perhaps not until your users experience the
>>> bug), or re-verify those problems the next time you come back to a
>>> piece of code. Does this absolve you of the responsibility to unit
>>> test, etc? Of course not. But that doesn't make it not useful.
>> In the presence of unit tests, static typing becomes much less interesting.
>
> This isn't true at all. First, you're assuming, as many people do,
> that the only point of static type systems is to ensure that simply
> operations aren't trivially misapplied. However, type systems provide
> other, even more significant, functionality. For example, they serve
> as guaranteed-correct documentation about the inputs and outputs of an
> interface. Second, theorems (such as those proved by type systems)
> and tests provide incomparable benefits. Dijkstra had some useful
> things to say on this point.
I heard these arguments before, and I would try to dismiss them, but
that's unrelated to the original topic here, so I won't, not here, not
now...
Ray Dillinger
> On 16 Mar, 16:09, Ray Dillinger <b...@sonic.net> wrote:
>> Michele Simionato wrote:
>> > On Mar 15, 7:22 pm, Ray Dillinger <b...@sonic.net>
>> > wrote: Semantically,
>> >> there hasn't been anything really new (except maybe monads)
>> >> for at least 30 years, that wasn't in Lisp first.
>>
>> > What about Hindley-Milner type inference, Algebraic Data Types
>> > and such? But perhaps they are older than 30 years ...
>>
>> These do not add to the semantics of a language. They...
>>
>> They can be used (and have been used) to write Lisp systems
>> that produce more efficient object code, of course, ...
>
> Well, they are used to help programmers to write correct programs too,
> so I wouldn't say they do not add to the semantics of a language. The
> compiler wouldn't reject incorrect typed programs otherwise.
I didn't say "not useful." I said "Don't add to the semantics of."
Type checking has some practical benefit. But it doesn't provide
any new ways to express algorithms.
There are no programs that pass strict type checking which are not
also type-correct without it. But there are type-correct programs
which cannot pass static type checking.
Ray Dillinger
> On Mar 19, 11:50 am, p...@informatimago.com (Pascal J. Bourguignon)
> wrote:
>> Sam TH <sam...@gmail.com> writes:
>> > Returning to the first point, imagine that we had an untyped Java.
>>
>> Perhaps you mean a dynamically typed Java.
>
> No, I meant "untyped". The term "dynamically typed" is useless, and
> contradictory in most of its uses.
Interesting. Everyone else in the world is using a useful and
consistent definition for the term, so if you have learnt a
definition of it which is useless and contradictory, I suggest
there may be things you can learn from standard programming
references.
Bear
Pascal J. Bourguignon
> SBCL does not, to my knowledge, ensure the absence of any class of
> errors. Can you describe what it's typechecker verifies?
For example:
S/CL-USER[26]> (compile nil (lambda () (car "abc")))
; in: LAMBDA NIL
; (CAR "abc")
;
; caught WARNING:
; Asserted type LIST conflicts with derived type (VALUES (SIMPLE-ARRAY CHARACTER (3)) &OPTIONAL).
; See also:
; The SBCL Manual, Node "Handling of Types"
;
; compilation unit finished
; caught 1 WARNING condition
#<FUNCTION (LAMBDA NIL) {3B22F1ED}>
NIL
NIL
--
__Pascal Bourguignon__
Stephen J. Bevan
> Sam TH wrote:
>> On Mar 19, 11:50 am, p...@informatimago.com (Pascal J. Bourguignon)
>> contradictory in most of its uses.
>
> Interesting. Everyone else in the world is using a useful and
> consistent definition for the term,
To a type theorist "dynamically typed" is an oxymoron, such languags
are "untyped". Whether you agree or not, it means not everyonen else
in the world agrees that "dynamically typed" is useful or consistent.
Sam TH
wrote:
> Sam TH <sam...@gmail.com> writes:
> > SBCL does not, to my knowledge, ensure the absence of any class of
> > errors. Can you describe what it's typechecker verifies?
>
> For example:
>
> S/CL-USER[26]> (compile nil (lambda () (car "abc")))
> ; in: LAMBDA NIL
> ; (CAR "abc")
> ;
> ; caught WARNING:
> ; Asserted type LIST conflicts with derived type (VALUES (SIMPLE-ARRAY CHARACTER (3)) &OPTIONAL).
> ; See also:
> ; The SBCL Manual, Node "Handling of Types"
First, SBCL does not reject this program, despite the warning.
Second, this is not a guarantee that `car' is not applied to "abc".
For example:
* (funcall (compile nil (lambda () ((lambda (f) (funcall f (read)))
(if (read) #'car #'cdr)))))
T
"abc"
debugger invoked on a TYPE-ERROR in thread #<THREAD "initial
thread" {A84D809}>:
The value "abc" is not of type LIST.
Note the lack of compiler warning.
A sound type system guarantees the absence of some classes of errors.
That's not what SBCL is doing.
sam th
Pascal J. Bourguignon
Here we have sound behavior: the error is a run-time event that can be
handled by the program (eventually by correcting itself, or in the
case of user I/O, perhaps with further user interaction).
Said otherwise, these errors are not errors.
SBCL doesn't reject the above program, because error processing is
part of the program, and this is always done in a strongly typed way
(here we have a TYPE-ERROR, not a PROGRAM-ERROR or a DIVIDE-BY-ZERO
error).
--
__Pascal Bourguignon__
Dirk van Deun
: >
: > Your paper, while interesting, does not show static type systems
: > introducing bugs.
: Yes, it does. The examples show code that rely on the type system to
: ensure "correctness" (of something), but where you get the counter effect.
I cannot resist pointing out that in the third example in your paper
you change the static type of a variable (cast to Employee) based
on a dynamic check (using instanceof) and then blame the static type
system for any bugs:
if (dilbert instanceof Employee) {
System.out.println("Employer: " + ((Employee)dilbert).getEmployer().getName();
}
It seems fairer to me to conclude that the interplay of dynamic and
static features is tricky. Neither is at fault by itself.
Dirk van Deun
--
Ceterum censeo Redmond delendum
Sam TH
Two points. First, I asked what guarantees were made the by the
compile time typechecker in SBCL. It appears that the answer is
'none'. This isn't a bug in SBCL - that's just not what the compiler
is designed to do. The SBCL compiler includes an unsound and
incomplete static analysis which produces warnings in some cases where
type errors might occur. But that means that it is not a "static type
checker", or at least not a sound one.
Second, while it's good that SBCL doesn't crash in this instance, that
isn't what "soundness" means. Soundness is about the agreement
between two models of a language. For example, between the dynamic
semantics of a language, and the type system for that language.
Considering only one model, as you do here, makes soundness
meaningless. SBCL is safe, but soundness does not come into play.
sam th
Sam TH
Type systems prove the absence of of a certain kind of error. Because
languages are hard to reason about, these systems must be
conservative, which means that they must rule out some programs that
do not have errors. But the class of things rules out are all errors.
Elena's claim, to quote:
"they are used to help programmers to write correct programs too"
is not disproved anywhere in your paper. What is proved is that
static type systems are not perfect, and that working around them can
sometimes be done in buggy ways.
> >>> The problem here is with the
> >>> existence of null, not with type systems.
> >> Indeed, the value of a language lies in the combination of its
> >> constituent feature, not in single constituent features themselves.
>
> > But null is the problem, whether or not you have type systems.
>
> Null can be made not to be a problem. See Objective-C's treatment of
> null, or generic functions as in Common Lisp or some Scheme systems, for
> example.
Neither CL nor Scheme have null, so they can't possibly be relevant
here.
> >>> For example, Haskell, a
> >>> *very* statically typed language, has a form named `undefined', which
> >>> you can put anywhere, and it raises an error when evaluated.
> >> You mean something like (error "bla") in Scheme or Common Lisp?
>
> > Yes, but much more useful due to lazy evaluation.
>
> Ugh, that's an unrelated feature.
I agree, but the argument in your paper is that untyped languages are
better because of the ease with which one can avoid implementing
things. I demonstrated that a paradigmatically strongly-typed
language, Haskell, is even better on this metric.
> >>> But in the cases
> >>> where they are helpful, it's extremely useful to have static checks of
> >>> some properties of your program, so that you don't have to discover
> >>> those problems later (or perhaps not until your users experience the
> >>> bug), or re-verify those problems the next time you come back to a
> >>> piece of code. Does this absolve you of the responsibility to unit
> >>> test, etc? Of course not. But that doesn't make it not useful.
> >> In the presence of unit tests, static typing becomes much less interesting.
>
> > This isn't true at all. First, you're assuming, as many people do,
> > that the only point of static type systems is to ensure that simply
> > operations aren't trivially misapplied. However, type systems provide
> > other, even more significant, functionality. For example, they serve
> > as guaranteed-correct documentation about the inputs and outputs of an
> > interface. Second, theorems (such as those proved by type systems)
> > and tests provide incomparable benefits. Dijkstra had some useful
> > things to say on this point.
>
> I heard these arguments before, and I would try to dismiss them, but
> that's unrelated to the original topic here, so I won't, not here, not
> now...
The only claims I made in that paragraph that are not simple facts was
that (a) Dijkstra had useful things to say, and (b) that the other
functionality provided by type systems is "more significant". The
rest of the claims, such as that theorems and tests demonstrate
incomparable things, are just facts which are true despite your
dismissals.
sam th
Sam TH
This is not correct. In Haskell, the use of type classes allows you
to write programs that would not make sense without the type system.
sam th
Matthias Blume
Just for reference, could you state that "useful and consistent definition"
that everyone else is using?
Thanks,
Matthias
Sam TH
Type inference can be implemented with macros as well. Complete type
inference for correct, untyped Scheme programs is impossible, so Typed
Scheme doesn't attempt that. But if you were willing to live with a
more restricted language (such as one like ML), then type inference
would be possible.
sam th
Elena
> Type inference can be implemented with macros as well. Complete type
> inference for correct, untyped Scheme programs is impossible, so Typed
> Scheme doesn't attempt that. But if you were willing to live with a
> more restricted language (such as one like ML), then type inference
> would be possible.
Heck! I did understand that macros were powerful, but not *that*
powerful...
Indeed I thought of a type system just like ML. I didn't know there
were much more advanced ways.
I agree with Pascal B. when he states that type checkers are useful as
a tool to help programmers in writing correct code, but I agree that
they could reject otherwise correct code and in my experience they are
cumbersome in the first stages of iterative development. Since, as far
as I can understand, you are saying that macros can't handle partially
type correct programs, then it would be nice if compilers could check
types as an option, issuing warnings where code seem to be wrong.
Sam TH
> On 20 Mar, 18:02, Sam TH <sam...@gmail.com> wrote:
>
> > Type inference can be implemented with macros as well. Complete type
> > inference for correct, untyped Scheme programs is impossible, so Typed
> > Scheme doesn't attempt that. But if you were willing to live with a
> > more restricted language (such as one like ML), then type inference
> > would be possible.
>
> Heck! I did understand that macros were powerful, but not *that*
> powerful...
In PLT Scheme, any static check of a module can be implemented with a
macro.
In any Scheme with procedural macros, by wrapping a form around the
code, any static check can be implemented.
>
> Indeed I thought of a type system just like ML. I didn't know there
> were much more advanced ways.
The reason ML is less expressive is that many Scheme programs can't be
written directly in ML (without encoding TheSchemeType). There are
more sophisticated type systems than ML, but that's not the important
issue - the issue is whether they admit type inference. ML's does,
Typed Scheme's doesn't.
> I agree with Pascal B. when he states that type checkers are useful as
> a tool to help programmers in writing correct code, but I agree that
> they could reject otherwise correct code and in my experience they are
> cumbersome in the first stages of iterative development. Since, as far
> as I can understand, you are saying that macros can't handle partially
> type correct programs, then it would be nice if compilers could check
> types as an option, issuing warnings where code seem to be wrong.
I didn't say that macros can't handle partially type-correct
programs. Macros are just a transformation system - it's up the the
typechecker to handle the programs. "Partially type-correct programs"
are a tricky subject, you can see my paper [1] for more on this.
[1] Interlanguage Migration: From Scripts to Programs, Tobin-Hochstadt
and Felleisen, DLS 2006
http://www.ccs.neu.edu/scheme/pubs/dls06-tf.pdf
sam th
Ray Dillinger
The way I learned it, "untyped" languages, including assembler,
are languages where the only thing the language semantics care
about in data is its size in bits. Any typed value with which
you may associate those bits is merely an artifact of which set
of values (ie, which type) you choose to associate with them at
a given instant. So, you have a bit pattern at a particular
address. Different parts of the code may treat that same bit
pattern as a character or a pointer or even executable code.
Such inconsistency, even when done deliberately and in a correct
program, is considered poor style, and rude to future maintainers.
Also, empirical evidence shows that such inconsistency or "type
punning" is more frequently the result of a programmer error than
something done deliberately and in a correct program.
Most such languages have syntaxes with several different ways of
writing the same bit pattern purely for the convenience of
programmers who think of the same bit pattern as several different
values (of different types). But there is no semantic difference
between them.
"Statically typed" languages, including for example Pascal,
associate a particular set of values (type) with a particular
memory location when the memory location is allocated, and do
not generally allow that association to be altered without
deallocating and reallocating the memory (as in stack frame
reallocation or dynamic memory management). On the plus side,
it eliminates the ability to "type pun" and thereby helps
eliminate a class of common errors. On the minus side, it
disallows even correct programs that use type punning. Also,
operations involving multiple types now require multiple
variables of different types and this leads to earlier
separation of execution paths, so it led to some "code bloat"
as compared to untyped assembly languages, both in source
and executable code. Type inference techniques have
dramatically reduced the source bloat of statically typed
languages but have done little to reduce executable bloat.
"Dynamically typed" languages, including for example Lisp, are
those in which all values of different types are distinguishable
from each other. So, while you no longer can exploit the
semantics of untyped languages in which you can interpret
ambiguous bit patterns differently depending on which type
you choose to associate with them, you can still use any
variable to store any value. On the plus side, it disallows
direct bit-centered "type punning" and that class of
inconsistency errors just as static typing does, while
allowing the flexibility of generic functions that can take
arguments of various different types, and defer separation of
execution paths by type until it actually makes a difference,
so some executable bloat can be recovered from statically
typed languages. Since no type declarations are required,
source bloat for that purpose doesn't happen either. On the
minus side, functions receiving an argument whose type is
not known in advance must sometimes do type checks, so there
is usually a performance penalty as runtime type checks are
performed. And since values in dynamically typed languages
are all distinguishable regardless of type, they typically
occupy more space in memory than bit patterns requiring
additional information to interpret as values of a given
type.
Bear
Ray Dillinger
This is interesting, and probably not consistent with type "checking"
as I understand it. Is it because of the presence of semantics in
Haskell that have different meanings depending solely on type
information?
Bear
George Neuner
The term "dynamically typed" is meaningless. but it is frequently used
as a lay synonym for "latently typed".
Lisp/Scheme have untyped bindings, but the data to which those
bindings refer is strongly typed.
George
George Neuner
wrote:
What you meant to say was "Haskell's type system is so ridiculously
restrictive that, without type classes, certain programs could not be
written in Haskell at all".
I would like to see an example of a program that can be written in
typed Haskell but cannot be written in untyped assembler.
George
Stephen J. Bevan
> The way I learned it, "untyped" languages, including assembler,
> are languages where the only thing the language semantics care
> about in data is its size in bits.
There are no bits and bytes in lambda calculus, it is the original
untyped language. The apparent desire to separate Lisp et al. from
assembler, Bliss, et all. is probably what led to "dynamically typed".
I'd be curious to now who coined the term and if they were in any way
familiar with any type theory. My guess is not, but then perhaps they
were but had/have a perverse sense of humour.
Pascal Costanza
This doesn't make sense. They must rule out some programs that do _not_
have errors, but at the same time these _are_ errors? What the heck?
So much for consistency...
It shows that blindly relying on the type system "helping" you to write
correct programs can lead to incorrectness.
Type systems don't do anything. They are just tools to be used, and you
have to think about their correct usage. The correctness is in the
thought process of the programmer, not in any of the tools!
>>>>> The problem here is with the
>>>>> existence of null, not with type systems.
>>>> Indeed, the value of a language lies in the combination of its
>>>> constituent feature, not in single constituent features themselves.
>>> But null is the problem, whether or not you have type systems.
>> Null can be made not to be a problem. See Objective-C's treatment of
>> null, or generic functions as in Common Lisp or some Scheme systems, for
>> example.
>
> Neither CL nor Scheme have null, so they can't possibly be relevant
> here.
OK, point taken.
>>>>> For example, Haskell, a
>>>>> *very* statically typed language, has a form named `undefined', which
>>>>> you can put anywhere, and it raises an error when evaluated.
>>>> You mean something like (error "bla") in Scheme or Common Lisp?
>>> Yes, but much more useful due to lazy evaluation.
>> Ugh, that's an unrelated feature.
>
> I agree, but the argument in your paper is that untyped languages are
> better because of the ease with which one can avoid implementing
> things. I demonstrated that a paradigmatically strongly-typed
> language, Haskell, is even better on this metric.
I only need the existence of _one_ static type system that leads to
incorrect programs to make my point, I don't need a universal claim. The
universal claim to disprove comes from the proponents of static type
systems. (that may not be you)
Stephen J. Bevan
> The term "dynamically typed" is meaningless. but it is frequently used
> as a lay synonym for "latently typed".
Indeed but then is the "typed" in "latently typed" really any more
meaningful than when it appears in "dynamically typed"? Either "type"
means something related to type theory or it doesn't. If it does then
how, when to all apparances such languages are untyped? If it does
not, then using the term surely muddied the waters given the existing
meaning of the word which applies perfectly well to programming
langauges and which dates back to before there were any stored program
computers.
Pascal Costanza
The typical reaction to this paper is that most people agree that at
least one of the examples is valid, and that at least one of the
examples is invalid. They never agree which is which, though. ;)
If (dilbert instanceof Employee) is true, that should be a static
guarantee, no?
Pascal Costanza
A statically typed language can be understood as a language where types
are associated with variables, whereas a dynamically typed language can
be understood as a language where types are associated with values. You
could call them type tags, but that doesn't make a big difference.
Stephen J. Bevan
> A statically typed language can be understood as a language where
> types are associated with variables, whereas a dynamically typed
> language can be understood as a language where types are associated
> with values.
Typed lambda calculus has no variables, values have a type, or not if
they are not well-typed according to the particular type theory.
> You could call them type tags, but that doesn't make a big difference.
I could indeed call them "type tags" and I agree it doesn't make a big
differnce since it still leaves "type" in there with a meaning that
has nothing obivous to do with any type theory.
I'm not looking to change the terminology, only note that not everyone
considers it consistent which is what Ray Dillinger claimed.
Pascal Costanza
"Type" doesn't need a type theory to have a consistent meaning.
If you are interested in having a sexual relationship with a person, but
that persons rejects you by saying "you are not my type", you don't
start by arguing that this is not consistent with some arbitrary type
theory (especially not if you still want to have a chance ;). You just
know what the other person means.
Likewise, if two programmers discuss a particular runtime exception they
encountered, and one of them says that this is probably because the two
involved values had incompatible types, the other also just knows what
is meant.
Don't make things more complicated than they are: The word "type" has a
meaning outside of type theory.
For example, there is a nice discussion what different kinds of types
there can be in the context of programming languages in
http://www.dreamsongs.com/Files/clos-book.pdf
Stephen J. Bevan
> "Type" doesn't need a type theory to have a consistent meaning.
>
> If you are interested in having a sexual relationship with a person,
> but that persons rejects you by saying "you are not my type", you
> don't start by arguing that this is not consistent with some arbitrary
Indeed not, but then why would one since type theory does not apply to
people? It does however apply to programming languages and did so
long before someone coined the term "dynamically typed".
Andrew Reilly
> It does however apply to programming languages
Some of them, perhaps. I doubt that type theory has much useful to say
about the practice of assembly language, forth or BCPL programming (among
others).
> and did so long before
> someone coined the term "dynamically typed".
I really doubt that, but I'm often wrong and keen to be corrected. Got a
reference handy?
Cheers,
--
Andrew
Stephen J. Bevan
> On Sat, 21 Mar 2009 16:01:08 -0700, Stephen J. Bevan wrote:
>> It does however apply to programming languages
>
> Some of them, perhaps. I doubt that type theory has much useful to say
> about the practice of assembly language, forth or BCPL programming (among
> others).
It would say that as defined they are untyped, monotyped or have a
small number of fixed types depending on how one wants to formulate a
type system to describe them. If one is willing to reject some
programs as ill-typed that are legal as defined in their respective
standards then one can use type theory to create type systems for
them. For example see "Strong Forth".
>> and did so long before someone coined the term "dynamically typed".
>
> I really doubt that, but I'm often wrong and keen to be corrected. Got a
> reference handy?
I'm not entirely sure what you are expecting a reference for, so I'll
start with Church and McCarthy. Church wrote the paper "A formulation
of the simple theory of types" in 1940 which presented a typed lambda
calculus and wrote the book "Calculi of Lambda conversion" in 1941.
That McCarthy knew about lambda calculus when creating Lisp is clear
since he wrote in a "History of Lisp" :-
To use functions as arguments, one needs a notation for functions,
and it seemed natural to use the -notation of Church (1941). I
didn't understand the rest of his book, so I wasn't tempted to try
to implement his more general mechanism for defining functions.
The lack of a lambda in the above is as per the (online) paper I'm
quoting. I assume it got lost in the LaTeX2HTML conversion.
Dirk van Deun
: > System.out.println("Employer: " + ((Employee)dilbert).getEmployer().getName();
: > }
: The typical reaction to this paper is that most people agree that at
: least one of the examples is valid, and that at least one of the
: examples is invalid. They never agree which is which, though. ;)
As a matter of fact, I disagree with the first (but that one had
already been criticized here), I need a longer think about the second,
and I disagree with the third. :-)
: If (dilbert instanceof Employee) is true, that should be a static
: guarantee, no?
So to come back to example three: here you yourself have shown why
dynamic checks should not be promoted into the static type system, and
therefore why a correct type checker will ignore them: the result of a
dynamic check is only guaranteed to be valid at the moment of the
check, and static types need to be Eternal Truth. To a static checker,
dilbert stays a person throughout, and can never be proven to be an
employee up to the point where the programmer explicitly casts him into
one, a cast that cannot be checked by the static checker; the checker
just allows itself to be overridden. (The Haskell type checker for
instance would never stand for such nonsense.)
So Java allows programmers to override its static checker and do their
own checks dynamically or even not at all. Sure that you can use
this to write buggy code, but don't blame static checking for that,
rather a lack of static checking.
If you want stronger guarantees, just disallow overriding the checker.
Dirk van Deun
: from each other. So, while you no longer can exploit the
: semantics of untyped languages in which you can interpret
: ambiguous bit patterns differently depending on which type
: you choose to associate with them, you can still use any
: variable to store any value. On the plus side, it disallows
: direct bit-centered "type punning" and that class of
: inconsistency errors just as static typing does, while
: allowing the flexibility of generic functions that can take
: arguments of various different types, and defer separation of
: execution paths by type until it actually makes a difference,
: so some executable bloat can be recovered from statically
: typed languages. Since no type declarations are required,
Is there still a difference in bloat if statically typed languages
have type classes like Haskell ? (Which allow for dynamic dispatch.)
(I would rather expect source code bloat than executable bloat,
because branching on a dynamic check is shorter than writing seperate
functions to call using dynamic dispatch.)
: source bloat for that purpose doesn't happen either. On the
: minus side, functions receiving an argument whose type is
: not known in advance must sometimes do type checks, so there
: is usually a performance penalty as runtime type checks are
: performed. And since values in dynamically typed languages
: are all distinguishable regardless of type, they typically
: occupy more space in memory than bit patterns requiring
: additional information to interpret as values of a given
: type.
Dirk van Deun
George Neuner
J. Bevan) wrote:
>George Neuner <gneu...@comcast.net> writes:
>> The term "dynamically typed" is meaningless. but it is frequently used
>> as a lay synonym for "latently typed".
>
>Indeed but then is the "typed" in "latently typed" really any more
>meaningful than when it appears in "dynamically typed"?
Yes. It means the types are not manifest in the source but are known
implicitly from and carried by the data ("carried by" meaning data is
tagged - languages with manifest types may also tag data). Both
manifest and latent typing can be analyzed statically.
"dynamic typing" is meaningless because it implies that types are
fluid and may change. While this can actually happen in Lisp because
object classes can be redefined at runtime, that facility is not used
by the vast majority of programs.
>Either "type" means something related to type theory or it doesn't.
"type" in all of these terms - even the lay terms - always means
something wrt type theory. Languages are classified by whether their
type systems are strong or weak, manifest or latent.
>If it does then how, when to all apparances such languages are untyped?
As I learned it, an "untyped" language is one in which data exists
only as raw words - ie. bits - and operators determine how their
operands are used.
>If it does not, then using the term surely muddied the waters given
>the existing meaning of the word which applies perfectly well to
>programming langauges and which dates back to before there were any
>stored program computers.
I agree that existing terminology should be used whenever possible ...
but that just isn't the way things happen.
George
Andrew Reilly
> I'm not entirely sure what you are expecting a reference for, so I'll
> start with Church and McCarthy. Church wrote the paper "A formulation
> of the simple theory of types" in 1940 which presented a typed lambda
> calculus and wrote the book "Calculi of Lambda conversion" in 1941. That
> McCarthy knew about lambda calculus when creating Lisp is clear since he
> wrote in a "History of Lisp" :-
Cool. Thanks for that. Clearly my reading list has to go a lot further
back in time. I must say that I'm amazed that this sort of thing was
being discussed before there were useful computers. What was the use of
type theory in those days of (presumably) mental models and pen-and-paper
reasoning?
Cheers,
--
Andrew
Stephen J. Bevan
> "dynamic typing" is meaningless because it implies that types are
> fluid and may change.
I agree that's one interpretation; but then one one interpretation of
"latent" is "dormant" which makes "latent typing" prima facia
meaningless. That said, I've no issue with someone defining "dynamic
typing" or "latent typing" to mean whatever they want it to mean; my
issue is with the claim that "everyone else in the world is using a
useful and consistent definition for the term".
> As I learned it, an "untyped" language is one in which data exists
> only as raw words - ie. bits - and operators determine how their
> operands are used.
There are no raw words or bits in (untyped) lambda calculus.
Pascal J. Bourguignon
When do you believe Computers were invented?
When do you believe TV was invented? (just to give another idea).
http://en.wikipedia.org/wiki/Computer#History_of_computing
http://en.wikipedia.org/wiki/History_of_IBM
http://en.wikipedia.org/wiki/Television#History
Things are invented long before they appear on the markets. And
people dream and think about them long before they're invented.
--
__Pascal Bourguignon__
Andrew Reilly
> When do you believe Computers were invented?
Well, Babbage had a go in the 19th century, but I didn't think that there
was much that would excite thoughts of programming issues until Bletchley
Park and other, similar exercises around the time of World War two. I
had imagined that thoughts of computability and the lambda calculus would
have waited until a few years of machine/assembly language had been done,
even if it pre-dated the development of Fortran and Lisp. I guess I
stand corrected.
Cheers,
--
Andrew
Pascal J. Bourguignon
In general technique lags fundamental research. At least, some
phenomenon may occur and may be "exploited" by some genious
technicians, but they're discarded by science and industry.
Wit free energy, anti-gravity, cold-fusion, etc.
You need at least one generation of new scientists to start to think
about the facts, and to elaborate a theory, before a new technique can
be developed refining the original experiments. This takes in general
at least 60 years. While you don't put the theory in the minds of
people, they won't accept what they see and refuse to act on it.
--
__Pascal Bourguignon__
Stephen J. Bevan
> What was the use of type theory in those days of (presumably) mental
> models and pen-and-paper reasoning?
Most, but not all, (programming) languages use some kind of grammar to
to partition terms/phrases into meaningful and not-meaningful. Type
theory would typically start with the programs in the first partition
and partition that again into meaningful and not-meaningful. Assuming
that one agrees that partitioning before evaluation is useful (and not
everyone does) then this is a useful task whether one has a
(electronic) computer or studying computability via pen-and-paper.
George Neuner
J. Bevan) wrote:
>George Neuner <gneu...@comcast.net> writes:
>>
>> As I learned it, an "untyped" language is one in which data exists
>> only as raw words - ie. bits - and operators determine how their
>> operands are used.
>
>There are no raw words or bits in (untyped) lambda calculus.
True, but the lambda calculus has no concept of "data" - all elements
of the calculus are functions.
George
Stephen J. Bevan
Then we have different defintions of 'data'; I would have said that
functions and data are synonymous in (untyped) lambda calculus.