Re: lisp style question

[Rivka Miller]

On Dec 2 2010, 5:11 pm, Katalin Sinkov <lispstyl...@gmail.com> wrote:
> On Dec 2, 12:50 am, "Frode V. Fjeld" <fr...@netfonds.no> wrote:
>
> > Katalin Sinkov <lispstyl...@gmail.com> writes:
> > > In the {} world I would return a small table like
>
> > > width 1
> > > height 2
> > > weight 3
>
> > Typically in Lisp you'd return either a property or association list.
>
> > I.e: (WIDTH 1 HEIGHT 2 WEIGHT 3) with accessor GETF,
>
> > or ((WIDTH . 1) (HEIGHT . 2) (WEIGHT . 3)) with accessor ASSOC.
>
> > --
> > Frode V. Fjeld
>
> Of all the four or five replies, I found yours most helpful although
> brief. This is perhaps due to me being a beginner, although the
> replies seem very promising and I am desirous of understanding them. I
> have just read the paper by McCarthy and the micro manual.

> assoc. and pair. are the most elementary of the functions, although
> not primitive and used in evaluator for working the symbol table.

> but beyond this, i could not understand your post.

> what is an "assoc list" and "a property list" and their difference ?

> what is "setf" and how to write it in terms of the elementary
> functions, car/cdr/cons/quote/cond/atom/eq ?

I have a few questions about this post from the past that I stumbled.
http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/fe797358c6550f1d/

Are these "car/cdr/cons/quote/cond/atom?/eq?" the only seven
primitives needed to describe a minimal lisp?

What about the values NIL or can it be described as () and is implicit
in cons - and how?

In addition, are not the concepts, lambda, and label needed as
primitives to define the auxiliary functions assoc. and pair. to
access and construct the environment? If that the primitive lambda is
an abstraction specifier (for free variable binding specification),
then it cannot be used as a function identifier or an operation name.

> how to conveniently costruct the list that goes with getf ?

> Presently I use the emacs IDE only and restricted to elisp, though i
> can (require 'cl) so what are
> the correponding operation in elisp ?
>
> what are the corresponding functions to defclass/defstruct in elisp ?
> I assume people are assuming CL.
>
> Could you comment a little on the post of Captain Obvious and Pascal
> Bourguignon ?
>
> The former has "values" and the latter has "make-volume" and colons.
> How did the constructor "make-volume" come to be ?
>
> Is it a feature in elisp ?
>
> Thanks for your help.
>
> Katalin

Thanks.
Rivka

[arc]

Rivka Miller <rivkau...@gmail.com> writes:

>
> Are these "car/cdr/cons/quote/cond/atom?/eq?" the only seven
> primitives needed to describe a minimal lisp?

I reckon not.

I'm not aware of any accepted criteria for something being a lisp (not
that I'd necessarily know if there were — I'm no expert).

But I reckon most people who are at all familiar with lisp would expect
something claiming to be a lisp would be Turing-complete, or if not
Turing-complete then at least as powerful as the simply-typed lambda
calculus or thereabouts.

You need both conditionals and loops (or equivalent) to do that, and
this list looks like it's only got conditionals in there.

At best this is a simple data-description language, with some ability to
define data conditionally.

What makes you think this is a suitable list of primitives?

> What about the values NIL or can it be described as () and is implicit
> in cons - and how?

Cons creates a simple data structure of two elements, called a 'pair'.
That data structure has two accessors, car and cdr, to get the first and
last (or right and left, if you like) element respectively. That's all it is.

So, no, NIL is not implicit in cons.

In order to be able to build a recursive list structure, you need to be
able to tell when you've got to the end of the list.

If you're building a list structure using cons, you need to have a value
to store in the CDR element that flags the end of the list. It has to
store something, after all (<= cons has two arguments).

(proper) Lists have a recursive property of the CDR of the list is also
a list.

So whatever the value that you use to terminate lists has to also count
as a list, if this property is to hold.

Now, you could just decide that the number 3 is what you're going to use
to terminate lists, which would mean that 3 on its own also counts as a
list with no elements. But that's just confusing, and also it would
mean that if you have a list of lists, you could never be sure whether a
3 denotes a list which happens to be empty, or bears its usual semantics
of the number 3.

So Lisps have a distinguished value, denoted NIL or '(), which isn't a
number or any other otherwise 'useful' value, to take this role. In
some lisps, this value is also used to take the role of falsity.

> In addition, are not the concepts, lambda, and label needed as
> primitives to define the auxiliary functions assoc. and pair. to
> access and construct the environment?

If you added lambda to the above list, that'd be enough for a simple
lisp-like general-purpose programming language. Many other lisp
stalwarts could be defined using that subset.

Lambda gets you variable binding and looping (through recursion).

However without set!/setq, you'd be unable to mutate any data, so the
language would be entirely functional (no side effects).

Actually, lambda is enough for a Turing-complete programming language on
its own. It not only can be used to bind variables and to loop, but it
can be used for conditionals, data structures, and even numbers!

I don't think many people would consider the lambda calculus a
lisp, but I suppose one could argue that it's just a very minimal one,
lacking a lot of the features that one would normally associate with
lisp (including lists! maybe you could argue it's a lisp analogously to
'() being a list...)

> If that the primitive lambda is an abstraction specifier (for free
> variable binding specification), then it cannot be used as a function
> identifier or an operation name.

Why not? the following is valid Scheme:

(define plus1 (lambda (x) (+ x 1)))
(define lambda plus1)
(lambda 3)
=> 4

I've just used the identifier 'lambda' to denote a procedure that adds
one to a number, so apparently you can do this.

Of course, i've now lost the ability to define anonymous functions, and
it's probably not a bright idea to redefine lambda to mean such an
unexpected thing.

But there are valid reasons to want to redefine lambda.

(you need to distinguish between identifiers and their denotations).

> Thanks.
> Rivka

--
-arc

[Pascal J. Bourguignon]

arc <arc.del...@vorsicht-bissig.de> writes:

> Rivka Miller <rivkau...@gmail.com> writes:
>
>>
>> Are these "car/cdr/cons/quote/cond/atom?/eq?" the only seven
>> primitives needed to describe a minimal lisp?
>
> I reckon not.
>
> I'm not aware of any accepted criteria for something being a lisp (not
> that I'd necessarily know if there were — I'm no expert).
>
> But I reckon most people who are at all familiar with lisp would expect
> something claiming to be a lisp would be Turing-complete, or if not
> Turing-complete then at least as powerful as the simply-typed lambda
> calculus or thereabouts.

Your expression is tainted.

Lambda Calculus and Universal Turing Machines are Turing-equivalent, but Lambda
Calculus is much more powerful than Universal Turing Machines. Just try to
implement a Universal Turing Machine in Lambda Calculus (easy, it was
done in 1959 by John McCarthy in his paper), then try to implement
Lambda Calculus in a Universal Turing Machine (AFAIK, nobody has ever
done that. Somebody has trace some paper talking about it, but I don't
think LC was implemented on a TM in that paper).

You could just try to do it, you may have fun.

> What makes you think this is a suitable list of primitives?

Lambda Calculus is all you need. The primitives are LAMBDA and function
application, which is denoted by () in lisp.

> So Lisps have a distinguished value, denoted NIL or '(), which isn't a
> number or any other otherwise 'useful' value, to take this role. In
> some lisps, this value is also used to take the role of falsity.

It's trivial to implement types in untyped lambda calculus.

cons = (lambda (a d) (lambda (k) (k a d))) ; in CL, add funcall.
car = (lambda (k) (k (lambda (a d) a)))
cdr = (lambda (k) (k (lambda (a d) d)))

Use Church's Numerals for cardinals.

box = cons
type-of = car
value-of = cdr

type-null = 0
type-cons = 1
type-cardinal = 2
type-character = 3 ; value-of is the ascii code of the character.


So you can represent:

NIL = (box type-null 0)
CONS = (lambda (a d) (cons type-cons (cons a d)))
42. = (box type-cardinal 42)
#\A = (box type-character 65)

etc.

(And just try to do that in Turing Machines! Bouahahah!)

>> In addition, are not the concepts, lambda, and label needed as
>> primitives to define the auxiliary functions assoc. and pair. to
>> access and construct the environment?
>
> If you added lambda to the above list, that'd be enough for a simple
> lisp-like general-purpose programming language. Many other lisp
> stalwarts could be defined using that subset.
>
> Lambda gets you variable binding and looping (through recursion).
>
> However without set!/setq, you'd be unable to mutate any data, so the
> language would be entirely functional (no side effects).

Much easier to implement setq in lambda calculus (or any other purely
functional programming language) than in Turing Machines.

> Actually, lambda is enough for a Turing-complete programming language on
> its own. It not only can be used to bind variables and to loop, but it
> can be used for conditionals, data structures, and even numbers!

Yes.

> I don't think many people would consider the lambda calculus a
> lisp, but I suppose one could argue that it's just a very minimal one,
> lacking a lot of the features that one would normally associate with
> lisp (including lists! maybe you could argue it's a lisp analogously to
> '() being a list...)

Definitely. Lisp is just a metalinguistic library over Lambda Calculus.



--
__Pascal Bourguignon__
http://www.informatimago.com

[arc]

"Pascal J. Bourguignon" <p...@informatimago.com> writes:

> arc <arc.del...@vorsicht-bissig.de> writes:
>
>> Rivka Miller <rivkau...@gmail.com> writes:
>>
>>>
>>> Are these "car/cdr/cons/quote/cond/atom?/eq?" the only seven
>>> primitives needed to describe a minimal lisp?
>>
>> I reckon not.
>>
>> I'm not aware of any accepted criteria for something being a lisp (not
>> that I'd necessarily know if there were — I'm no expert).
>>
>> But I reckon most people who are at all familiar with lisp would expect
>> something claiming to be a lisp would be Turing-complete, or if not
>> Turing-complete then at least as powerful as the simply-typed lambda
>> calculus or thereabouts.
>
> Your expression is tainted.

Tainted? What a hilarious accusation! Tainted with what? Evil? Please
let it be evil — evil is always so much more sexy than the alternatives
in the movies, but my conscience won't let me commit much of it in real
life. I'm not going to be too troubled by saying things about Turing
completeness though...

> Lambda Calculus and Universal Turing Machines are Turing-equivalent,
> but Lambda Calculus is much more powerful than Universal Turing
> Machines.

Perhaps the problem is that you're interpreting 'power' to mean
something different from me? In other words, maybe it's your
comprehension that's tainted (by evil!), and not my expression...

I'm using 'power' to mean 'computational power'. Two systems have the
same computational power if the the set of functions they can compute is
the same. Hopefully you agree that the lambda calculus and Turing
machines are of equivalent power in this sense.

What do you mean by 'power' when you say that the lambda calculus is
more powerful than Turing machines?

Anyway, the point was the language Rivka described is inadequate to
serve as a general-purpose programming language. Even if you expect a
lisp to be 'more powerful' than a Turing machine in some sense, you
still expect it to be at least as powerful as a Turing machine.

> Just try to
> implement a Universal Turing Machine in Lambda Calculus (easy, it was
> done in 1959 by John McCarthy in his paper)

Do you mean this paper?

http://www-formal.stanford.edu/jmc/recursive.html

Are you sure he's actually using the lambda calculus there? I thought
McCarthy didn't understand the lambda calculus when he wrote this —
didn't this come up in a recent thread here?

Also, early LISPs were all dynamically scoped, or so I understand. The
lambda calculus is lexically scoped, and in fact I believe that was the
major source of the motivation to make Scheme lexically scoped. This
doesn't seem compatible with McCarthy using the lambda calculus in this
paper.

He does seem to be using a substitution model of evaluation, so there
are certainly some similarities, but I suspect it's not actually the
same.

I reckon Sussman and Steele's paper "Scheme: An Interpreter for Extended
Lambda Calculus" is more like what you descibed:

http://library.readscheme.org/page1.html

Thanks for mentioning the McCarthy paper, though, I'll definitely save
it to read at some point.

> , then try to implement
> Lambda Calculus in a Universal Turing Machine (AFAIK, nobody has ever
> done that. Somebody has trace some paper talking about it, but I don't
> think LC was implemented on a TM in that paper).

What do you think a (modern, lexically scoped) Lisp compiler is? :]

OK, so a physical silicon-and-wire computer isn't exactly a universal
turing machine, but their execution model is similar enough for people
to call them Turing machines. If you can write a compiler for an x86
machine, you can write a compiler for a UTM.

I'd be highly surprised if this hasn't been done before. If it hasn't,
it's just because no-one's been bothered, not that it's impossible. I
mean, sure, it'd be significantly harder than writing a compiler for a
regular machine, as a Turing machine is a good deal more primitive.
Things that are primitives (like addition and fetching data from a
location in memory) in a regular machine would have to be implemented.

> You could just try to do it, you may have fun.

I have actually toyed with this idea before! I think it would be quite
instructive. I can't see myself getting on to it any time soon,
though.

>
>> What makes you think this is a suitable list of primitives?
>
> Lambda Calculus is all you need. The primitives are LAMBDA and function
> application, which is denoted by () in lisp.

Yes, I said so myself. Did you even bother to read my post to the end
before replying?


I liked your example of how to implement some Lisp primitives in the
lambda calculus, by the way.

--
-arc.

[Pascal J. Bourguignon]

That's what Turing-equivalent means. "Turing-equivalent" has a
mathematical definition. "power" has not.

> What do you mean by 'power' when you say that the lambda calculus is
> more powerful than Turing machines?

Expressive power. Power of being usable to write practical programs.

> Anyway, the point was the language Rivka described is inadequate to
> serve as a general-purpose programming language. Even if you expect a
> lisp to be 'more powerful' than a Turing machine in some sense, you
> still expect it to be at least as powerful as a Turing machine.

Which is not saying much! You only need a single well choosen
instruction to make a machine Turing-equivalent. Also, they're usually
more powerful than Turing Machines (a human being can write real programs with
single-instruction Von Neumann machines, not with Turing Machines (you
involved compilers, I mentionned nobody ever implemented Lambda Calculus
in a Turing Machine).

>> Just try to
>> implement a Universal Turing Machine in Lambda Calculus (easy, it was
>> done in 1959 by John McCarthy in his paper)
>
> Do you mean this paper?
>
> http://www-formal.stanford.edu/jmc/recursive.html

I meant section 2.8 of AIM-8

A machine readable copy is at
http://www.informatimago.com/develop/lisp/com/informatimago/small-cl-pgms/aim-8

> Are you sure he's actually using the lambda calculus there? I thought
> McCarthy didn't understand the lambda calculus when he wrote this —
> didn't this come up in a recent thread here?

Yes. But it's trivial to implement this lisp in lambda calculus. It
can be done in a long afternoon, or a short week end.

> Also, early LISPs were all dynamically scoped, or so I understand. The
> lambda calculus is lexically scoped, and in fact I believe that was the
> major source of the motivation to make Scheme lexically scoped. This
> doesn't seem compatible with McCarthy using the lambda calculus in this
> paper.

If you take care of avoiding shadowing variables, and not trying to capture
closures, then programs should be equivalent with lexical binding and
with dynamic binding. Take emacs as an example.

But you can just implement dynamic binding for the lisp you implement in
lambda calculus. Add an evening.

Now doing the same in Turing Machine would take man.years…

> He does seem to be using a substitution model of evaluation, so there
> are certainly some similarities, but I suspect it's not actually the
> same.
>
> I reckon Sussman and Steele's paper "Scheme: An Interpreter for Extended
> Lambda Calculus" is more like what you descibed:
>
> http://library.readscheme.org/page1.html
>
> Thanks for mentioning the McCarthy paper, though, I'll definitely save
> it to read at some point.
>
>> , then try to implement
>> Lambda Calculus in a Universal Turing Machine (AFAIK, nobody has ever

>> done that. Somebody has traced some paper talking about it, but I don't

>> think LC was implemented on a TM in that paper).
>
> What do you think a (modern, lexically scoped) Lisp compiler is? :]
>
> OK, so a physical silicon-and-wire computer isn't exactly a universal
> turing machine, but their execution model is similar enough for people
> to call them Turing machines.

1- they're wrong to call them Turing Machines, architecturally they're
quite different. They're Von Neuman machines.

2- they're not Turing Machine for lack of unbounded memory.

so our computers are not even "Turing complete".

> If you can write a compiler for an x86
> machine, you can write a compiler for a UTM.
>
> I'd be highly surprised if this hasn't been done before. If it hasn't,
> it's just because no-one's been bothered, not that it's impossible.

If it takes more than 80 man.year to do, then it would be impossible to
do for any human being, even if he bothered!

> I
> mean, sure, it'd be significantly harder than writing a compiler for a
> regular machine, as a Turing machine is a good deal more primitive.
> Things that are primitives (like addition and fetching data from a
> location in memory) in a regular machine would have to be implemented.
>
>> You could just try to do it, you may have fun.
>
> I have actually toyed with this idea before! I think it would be quite
> instructive. I can't see myself getting on to it any time soon,
> though.
>
>>
>>> What makes you think this is a suitable list of primitives?
>>
>> Lambda Calculus is all you need. The primitives are LAMBDA and function
>> application, which is denoted by () in lisp.
>
> Yes, I said so myself. Did you even bother to read my post to the end
> before replying?

No. It's more lively to answer while reading! :-)

> I liked your example of how to implement some Lisp primitives in the
> lambda calculus, by the way.
>
> --
> -arc.

[arc]

"Pascal J. Bourguignon" <p...@informatimago.com> writes:

> arc <arc.del...@vorsicht-bissig.de> writes:
>
>> "Pascal J. Bourguignon" <p...@informatimago.com> writes:
>>
>>> arc <arc.del...@vorsicht-bissig.de> writes:
>>>

>>> Lambda Calculus and Universal Turing Machines are Turing-equivalent,
>>> but Lambda Calculus is much more powerful than Universal Turing
>>> Machines.
>>
>> Perhaps the problem is that you're interpreting 'power' to mean
>> something different from me? In other words, maybe it's your
>> comprehension that's tainted (by evil!), and not my expression...
>>
>> I'm using 'power' to mean 'computational power'. Two systems have the
>> same computational power if the the set of functions they can compute is
>> the same. Hopefully you agree that the lambda calculus and Turing
>> machines are of equivalent power in this sense.
>
> That's what Turing-equivalent means. "Turing-equivalent" has a
> mathematical definition. "power" has not.

Another hilarious objection!

I'm sure you must just be having me on here. Obviously we're not
writing in a formal, mathematically precise language here. And even if
we were, in those languages it's entirely apropos to define new terms.

Anyway, it's perfectly ordinary to use 'power' in this sense, as a few
minutes with Google can demonstrate:

"In computational complexity theory, decision problems are typically
defined as formal languages, and complexity classes are defined as the
sets of the formal languages that can be parsed by machines with limited
computational power."

( http://en.wikipedia.org/wiki/Formal_language )


"Church’s lambda calculus is equivalent in power to the Turing machine,
although Church and Turing both developed their respective models of
computation independently. "

( http://classes.soe.ucsc.edu/cmps112/Spring03/readings/lambdacalculus/project3.html )

"A major theme of the 20th Century has been the growing understanding of
the nature of computation. This began in earnest in the 1930's with the
independent introduction of several theoretical models of computation,
including the recursive functions, the lambda calculus and the Turing
machine. While these models were very different in character, they were
soon proven to be of equal power and are now widely considered to
represent the most powerful level of computation possible. Turing
machines, in particular, have been a very influential model and are the
basis for the physical computers we use today."

( http://www.amirrorclear.net/academic/research-topics/other-topics/hypercomputation.html )

"Right; that was all I was trying to say with the 'a TuringMachine is
considerably "lower-level"' comment. Note that it is independent of the
arguments about interaction and encapsulation given in
InteractiveComputationIsMorePowerfulThanNonInteractive, which deal with
power, not expressiveness."

( http://c2.com/cgi/wiki?ModelsOfComputation )

That last one is interesting as that commenter is explicitly making a
distinction between power and expressiveness.

I'm surprised you aren't familiar with this usage, actually, given that
it's pretty common, and you clearly know a bit about the area.

(just for the record, I think 'power' meaning expressive power is pretty
common too, and I wouldn't object to anyone using that. The word 'power'
means a lot of different things in computing contexts, including the
ability of machine to accomplish a number of tasks in a particular time,
so it's important to work out which one the writer is using before
accusing them of tainted expression...)

>
>> What do you mean by 'power' when you say that the lambda calculus is
>> more powerful than Turing machines?
>
> Expressive power. Power of being usable to write practical programs.

And does this have a mathematical definition? It sounds like it's got a
lot to do with what humans find easy to do, so I'm doubtful...

>
>> Anyway, the point was the language Rivka described is inadequate to
>> serve as a general-purpose programming language. Even if you expect a
>> lisp to be 'more powerful' than a Turing machine in some sense, you
>> still expect it to be at least as powerful as a Turing machine.
>
> Which is not saying much!

It's not saying much to say a language is not turing complete? (*laughs*)

I'm sure you must be joking here (or maybe not thinking about what
you're saying). The language Rivka describes is not really suitable for
writing any programs with it. It's suitable for maybe a simple
data-description language. There's certainly a big difference between
this and a Turing-complete language.

Even if you're talking about expressiveness, Rivka's language isn't up
to expressing many computations, even though what it can express it
might express more clearly than a UTM is.

>
>>> Just try to
>>> implement a Universal Turing Machine in Lambda Calculus (easy, it was
>>> done in 1959 by John McCarthy in his paper)
>>
>> Do you mean this paper?
>>
>> http://www-formal.stanford.edu/jmc/recursive.html
>
> I meant section 2.8 of AIM-8
>
> A machine readable copy is at
> http://www.informatimago.com/develop/lisp/com/informatimago/small-cl-pgms/aim-8

That's the same paper.

>
>> Are you sure he's actually using the lambda calculus there? I thought
>> McCarthy didn't understand the lambda calculus when he wrote this —
>> didn't this come up in a recent thread here?
>
> Yes. But it's trivial to implement this lisp in lambda calculus. It
> can be done in a long afternoon, or a short week end.

So he didn't implement LISP in the lambda calculus. And you're
complaining that I'm not precise enough...

>
>> If you can write a compiler for an x86
>> machine, you can write a compiler for a UTM.
>>
>> I'd be highly surprised if this hasn't been done before. If it hasn't,
>> it's just because no-one's been bothered, not that it's impossible.
>
> If it takes more than 80 man.year to do, then it would be impossible to
> do for any human being, even if he bothered!

I'm not convinced it would be that difficult.

Conceptually, all you really have to do is to take the simplest CPU
instruction set that has already has a lamdba calculus compiler written
for it, and then implement all of those instructions on a UTM. A lot of
this will be quite boring - you'd need to implement accessing a memory
address and reading a word to a routine that moves the head back and
forth between the part of the tape that represents a register to the
part of the tape that represents the memory address and copy the data a
bit at a time.

That might not be the nicest way to do it, but it would work, so the
problem really reduces to implementing a von Neumann machine on a UTM.
That might be a bit of work, but surely not 80 man years.

Anyway, sure, I think the lambda calculus is much nicer than Turing
machines too.


--
-arc.

[Pascal J. Bourguignon]

arc <arc.del...@vorsicht-bissig.de> writes:

>> Expressive power. Power of being usable to write practical programs.
>
> And does this have a mathematical definition? It sounds like it's got a
> lot to do with what humans find easy to do, so I'm doubtful...

Yes, it also have a mathematical, information theoric definition.

>>> Anyway, the point was the language Rivka described is inadequate to
>>> serve as a general-purpose programming language. Even if you expect a
>>> lisp to be 'more powerful' than a Turing machine in some sense, you
>>> still expect it to be at least as powerful as a Turing machine.
>>
>> Which is not saying much!
>
> It's not saying much to say a language is not turing complete? (*laughs*)

No, it is not saying much to say that a language IS Turing Complete.

There's no point in mentionning that a language is Turing Complete,
because Turing Machines are Turing Complete, and are utterly inusable
for any practical purpose.

And even for theorical purpose, you're probably better off sticking with
Lambda Calculus.

> I'm sure you must be joking here (or maybe not thinking about what
> you're saying). The language Rivka describes is not really suitable for
> writing any programs with it. It's suitable for maybe a simple
> data-description language. There's certainly a big difference between
> this and a Turing-complete language.

Rivka's over look is easily explainable. Both in lambda calculus and in
lisp, function application is invisible, since it's merely f a or (f a).

Well, in lisp you could write: (apply 'f a) to make application
explicit…

> Even if you're talking about expressiveness, Rivka's language isn't up
> to expressing many computations, even though what it can express it
> might express more clearly than a UTM is.

At least, you get what I mean!

>>> Are you sure he's actually using the lambda calculus there? I thought
>>> McCarthy didn't understand the lambda calculus when he wrote this —
>>> didn't this come up in a recent thread here?
>>
>> Yes. But it's trivial to implement this lisp in lambda calculus. It
>> can be done in a long afternoon, or a short week end.
>
> So he didn't implement LISP in the lambda calculus. And you're
> complaining that I'm not precise enough...

No. But implementing LISP in LC is something I did (partially) and you
can do in a week end.

>>> If you can write a compiler for an x86
>>> machine, you can write a compiler for a UTM.
>>>
>>> I'd be highly surprised if this hasn't been done before. If it hasn't,
>>> it's just because no-one's been bothered, not that it's impossible.
>>
>> If it takes more than 80 man.year to do, then it would be impossible to
>> do for any human being, even if he bothered!
>
> I'm not convinced it would be that difficult.
>
> Conceptually, all you really have to do is to take the simplest CPU
> instruction set that has already has a lamdba calculus compiler written
> for it, and then implement all of those instructions on a UTM. A lot of
> this will be quite boring - you'd need to implement accessing a memory
> address and reading a word to a routine that moves the head back and
> forth between the part of the tape that represents a register to the
> part of the tape that represents the memory address and copy the data a
> bit at a time.
>
> That might not be the nicest way to do it, but it would work, so the
> problem really reduces to implementing a von Neumann machine on a UTM.
> That might be a bit of work, but surely not 80 man years.
>
> Anyway, sure, I think the lambda calculus is much nicer than Turing
> machines too.

Good, so we agree.

[Nicolas Neuss]

arc <arc.del...@vorsicht-bissig.de> writes:

[snip]

>>> If you can write a compiler for an x86
>>> machine, you can write a compiler for a UTM.
>>>
>>> I'd be highly surprised if this hasn't been done before. If it hasn't,
>>> it's just because no-one's been bothered, not that it's impossible.
>>
>> If it takes more than 80 man.year to do, then it would be impossible to
>> do for any human being, even if he bothered!
>
> I'm not convinced it would be that difficult.
>
> Conceptually, all you really have to do is to take the simplest CPU
> instruction set that has already has a lamdba calculus compiler written
> for it, and then implement all of those instructions on a UTM. A lot of
> this will be quite boring - you'd need to implement accessing a memory
> address and reading a word to a routine that moves the head back and
> forth between the part of the tape that represents a register to the
> part of the tape that represents the memory address and copy the data a
> bit at a time.
>
> That might not be the nicest way to do it, but it would work, so the
> problem really reduces to implementing a von Neumann machine on a UTM.
> That might be a bit of work, but surely not 80 man years.
>

Agreed. Some years ago I wrote (in CL of course) a small Turing machine
assembler with sufficiently many operators that I could write a
factorial program for the TM.

IIRC that was a really nice exercise. So I'm quite sure that there
exist also more powerful TM assembler languages somewhere.

Nicolas

[arc]

"Pascal J. Bourguignon" <p...@informatimago.com> writes:

> arc <arc.del...@vorsicht-bissig.de> writes:
>
>>> Expressive power. Power of being usable to write practical programs.
>>
>> And does this have a mathematical definition? It sounds like it's got a
>> lot to do with what humans find easy to do, so I'm doubtful...
>
> Yes, it also have a mathematical, information theoric definition.

Where could I find this?

>>>> Anyway, the point was the language Rivka described is inadequate to
>>>> serve as a general-purpose programming language. Even if you expect a
>>>> lisp to be 'more powerful' than a Turing machine in some sense, you
>>>> still expect it to be at least as powerful as a Turing machine.
>>>
>>> Which is not saying much!
>>
>> It's not saying much to say a language is not turing complete? (*laughs*)
>
> No, it is not saying much to say that a language IS Turing Complete.

But it is saying much to point out that it *isn't* Turing Complete? Good,
because that's what I was doing :-P

> There's no point in mentionning that a language is Turing Complete,
> because Turing Machines are Turing Complete, and are utterly inusable
> for any practical purpose.

What Turing complete tells you is that the language can encode any
computable function (and normally it comes with a caveat, sometimes
implicit, within the limits of the space available. I'm sure you know
this and are just prentending you don't to vex me).

So we've got two dimensions to describe programming languages, power and
expressiveness:
^
|expressiveness
Rivka's 'lisp' X Lisp
| |
X X X X |
ini files SQL simply |
typed λ |
X Assembly
----------------------------------|------------------->
power Turing-computable Hypercomputability
|
X Turing Machines
|
X Malbolge

(OK, so they're not really entirely independent: a less powerful
language can't express a computation a more powerful language can. But
you get the idea)

By saying there's no point in saying that a language is turing-complete,
you're telling me there's no point in noting that you can't write a
programme in an ini file, or no point in telling Rivka that the language
they describe isn't any kind of general programming language.

Sometimes also it's a surprise that a language is turing complete,
because this isn't always intentional. HTML5 and CSS3 have recently been
shown to be Turing complete, for example.

Also, discovering that the lambda calculus, recursive functions, and
Turing machines (and all sorts of other computation apparatus) compute
the same set of functions was regarded as a fundamental discovery
(maybe *the* fundamental discovery) of computer science.


So just because there are turing-complete languages that aren't useful
doesn't mean that it's a pointless thing to say. I'm not sure why you'd
even say that.

( Do you take this attitude to everything in life? There's no point in
saying a material conducts electricity, because some materials that
conduct electricity aren't useful as electrical components? )

> And even for theorical purpose, you're probably better off sticking with
> Lambda Calculus.

Is this all just because you hate the term 'turing complete'? Well,
I'll try to remember to call it 'lambda calculus complete' if I think
you might be reading, but 'Turing complete' is the commonly-accepted
term for what I was trying to describe.

--
-arc.

[Pascal J. Bourguignon]

arc <arc.del...@vorsicht-bissig.de> writes:

> ( Do you take this attitude to everything in life? There's no point in
> saying a material conducts electricity, because some materials that
> conduct electricity aren't useful as electrical components? )

For that matter, no material is entirely non-conductor, so indeed,
saying that a material conducts electricity doesn't say much. But my
point with LC vs TM is a little different, as you have noted with your
2D graph.

>> And even for theorical purpose, you're probably better off sticking with
>> Lambda Calculus.
>
> Is this all just because you hate the term 'turing complete'? Well,
> I'll try to remember to call it 'lambda calculus complete' if I think
> you might be reading, but 'Turing complete' is the commonly-accepted
> term for what I was trying to describe.

In a way, yes.
You're right, I'd prefer if we said lambda-calculus complete :-)

[jurgen_defurne]

On Tuesday, November 6, 2012 9:12:34 AM UTC+1, arc wrote:

> Rivka Miller writes:
>
>
>
> >
>
> > Are these "car/cdr/cons/quote/cond/atom?/eq?" the only seven
>
> > primitives needed to describe a minimal lisp?
>
>
>
> I reckon not.
>
>
>
> I'm not aware of any accepted criteria for something being a lisp (not
>
> that I'd necessarily know if there were — I'm no expert).
>
>
>
> But I reckon most people who are at all familiar with lisp would expect
>
> something claiming to be a lisp would be Turing-complete, or if not
>
> Turing-complete then at least as powerful as the simply-typed lambda
>
> calculus or thereabouts.
>
>
>
> You need both conditionals and loops (or equivalent) to do that, and
>
> this list looks like it's only got conditionals in there.
>
>
>
> At best this is a simple data-description language, with some ability to
>
> define data conditionally.
>
>
>
> What makes you think this is a suitable list of primitives?

I suppose it is this link :

http://www.paulgraham.com/rootsoflisp.html

Of course, if you start to try to implement this, then you need a couple of other things.

In the past two months I implemented a small interpreter written in C, which
does this. It implements a small Lisp with only a lexical environment. I also made a list
of things still missing wrt. error checking, type validity of arguments, checks on the
number of arguments, setq functionality. I do not even have . and ', one needs to use a
literal quote. What I also need is a garbage collector, execution of primitive procedures
and a list of primitive procedures which can access my virtual machines. I have strings
but no string operators, and I do not have any kind of number. These are treated as
symbols at this moment.

But it is a nice exercise and a great way to have insight in and appreciate all the work
that has gone into any programming language the last 50 years.

Regards,

Jurgen