Discussion:
Beginner's Question: Abstract Datatypes
(too old to reply)
Antti Ylikoski
2015-10-10 06:10:19 UTC
Permalink
I started authoring a multi user poker game, after the recommendation
of Mark Tarver.

I shall do it with abstract datatypes, the sketch is as follows:

------------------------------------------------------------

(datatype card
\\ and its operations....
)

(datatype deck-of-cards
\\ its operations....
)

(datatype poker-hand
\\ the operations.....
)

(datatype player
\\ the ops......
)

(datatype poker-game
\\ the ops......
\\ a settable number of players with settable different strategies
\\ One or several ones may be humans, ie. users
)

(datatype poker-strategy
\\ Can be set for a player
)

------------------------------------------------------------

I wrote the following stack abstract datatype for an exercise, but I
need to ask one question -- one more beginner's question!

Without type checking, this will work:

------------------------------------------------------------

***@mydebian:~/ShenResearch$ ./Shen

Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver


(0-) (load "stack.shen")
type#stack
empty-stack
push
top
pop

run time: 0.07599999848753214 secs
loaded

(1-)

------------------------------------------------------------

but it makes as error with type checking:

------------------------------------------------------------

***@mydebian:~/ShenResearch$ ./Shen

Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver


(0-) (tc +)
true

(1+) (load "stack.shen")
empty-stack lacks a proper signature.


(2+)

------------------------------------------------------------

The file "stack.shen" is as follows:

------------------------------------------------------------

\\
\\ Stack as an Abstract Datatype
\\
\\ AJY 2015-10-10
\\
\\ Implementation as a list of conses



(datatype stack

__________________________________
empty-stack: (--> (stack A));

___________________________________
push: (A --> (stack A) --> (stack A));

___________________________________
top: ((stack A) --> A);

____________________________________
pop: ((stack A) --> (stack A));

)


(define empty-stack
-> []) \\ Returns an empty stack


(define push
Obj St -> (cons Obj St)) \\ Pushes and returns stack


(define top
St -> (head St)) \\ Returns the top element


(define pop
St -> (tail St)) \\ Removes the top element, returns stack


------------------------------------------------------------

Some help would be very much appreciated.



yours, A. J. Y.
HELSINKI
Finland
--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+***@googlegroups.com.
To post to this group, send an email to ***@googlegroups.com.
Visit this group at http://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
Mark Tarver
2015-10-10 09:49:21 UTC
Permalink
It would probably be simpler and more useful to use concrete datatypes.
Define a card as such.

Mark
Post by Antti Ylikoski
I started authoring a multi user poker game, after the recommendation
of Mark Tarver.
------------------------------------------------------------
(datatype card
\\ and its operations....
)
(datatype deck-of-cards
\\ its operations....
)
(datatype poker-hand
\\ the operations.....
)
(datatype player
\\ the ops......
)
(datatype poker-game
\\ the ops......
\\ a settable number of players with settable different strategies
\\ One or several ones may be humans, ie. users
)
(datatype poker-strategy
\\ Can be set for a player
)
------------------------------------------------------------
I wrote the following stack abstract datatype for an exercise, but I
need to ask one question -- one more beginner's question!
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (load "stack.shen")
type#stack
empty-stack
push
top
pop
run time: 0.07599999848753214 secs
loaded
(1-)
------------------------------------------------------------
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (tc +)
true
(1+) (load "stack.shen")
empty-stack lacks a proper signature.
(2+)
------------------------------------------------------------
------------------------------------------------------------
\\
\\ Stack as an Abstract Datatype
\\
\\ AJY 2015-10-10
\\
\\ Implementation as a list of conses
(datatype stack
__________________________________
empty-stack: (--> (stack A));
___________________________________
push: (A --> (stack A) --> (stack A));
___________________________________
top: ((stack A) --> A);
____________________________________
pop: ((stack A) --> (stack A));
)
(define empty-stack
-> []) \\ Returns an empty stack
(define push
Obj St -> (cons Obj St)) \\ Pushes and returns stack
(define top
St -> (head St)) \\ Returns the top element
(define pop
St -> (tail St)) \\ Removes the top element, returns stack
------------------------------------------------------------
Some help would be very much appreciated.
yours, A. J. Y.
HELSINKI
Finland
--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+***@googlegroups.com.
To post to this group, send an email to ***@googlegroups.com.
Visit this group at http://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
Antti Ylikoski
2015-10-10 12:46:35 UTC
Permalink
OK

Now the poker.shen is as you recommended, and it will type check and
compile.

Thanks.

AJY
Post by Mark Tarver
It would probably be simpler and more useful to use concrete datatypes.
Define a card as such.
Mark
Post by Antti Ylikoski
I started authoring a multi user poker game, after the recommendation
of Mark Tarver.
------------------------------------------------------------
(datatype card
\\ and its operations....
)
(datatype deck-of-cards
\\ its operations....
)
(datatype poker-hand
\\ the operations.....
)
(datatype player
\\ the ops......
)
(datatype poker-game
\\ the ops......
\\ a settable number of players with settable different strategies
\\ One or several ones may be humans, ie. users
)
(datatype poker-strategy
\\ Can be set for a player
)
------------------------------------------------------------
I wrote the following stack abstract datatype for an exercise, but I
need to ask one question -- one more beginner's question!
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (load "stack.shen")
type#stack
empty-stack
push
top
pop
run time: 0.07599999848753214 secs
loaded
(1-)
------------------------------------------------------------
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (tc +)
true
(1+) (load "stack.shen")
empty-stack lacks a proper signature.
(2+)
------------------------------------------------------------
------------------------------------------------------------
\\
\\ Stack as an Abstract Datatype
\\
\\ AJY 2015-10-10
\\
\\ Implementation as a list of conses
(datatype stack
__________________________________
empty-stack: (--> (stack A));
___________________________________
push: (A --> (stack A) --> (stack A));
___________________________________
top: ((stack A) --> A);
____________________________________
pop: ((stack A) --> (stack A));
)
(define empty-stack
-> []) \\ Returns an empty stack
(define push
Obj St -> (cons Obj St)) \\ Pushes and returns stack
(define top
St -> (head St)) \\ Returns the top element
(define pop
St -> (tail St)) \\ Removes the top element, returns stack
------------------------------------------------------------
Some help would be very much appreciated.
yours, A. J. Y.
HELSINKI
Finland
--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+***@googlegroups.com.
To post to this group, send an email to ***@googlegroups.com.
Visit this group at http://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
Samuel Falvo II
2016-08-10 20:24:48 UTC
Permalink
This post is dredging up the past a bit, but since I'm a beginner, I think
it's apropos.

What is the value proposition of abstract data types in the precise context
of Shen? A lot of explanation has gone into explaining concrete data
types, but ADTs get almost a passing mention in comparison. The example
provided in the book, while it illustrates the syntax that goes into
creating an ADT, might not have used the best illustrative example, since
it seems like a CDT would have worked just as well, in as many lines of
code, and with similar abstraction properties.

Some things I observe:

1) In Antti's work, the datatype and the implementation are colocated in
the same source; suggesting that a concrete data type would work as well.
The public interface would certainly be the same as viewed by clients of
the code. So, I'm wondering why Antti chose to use an ADT here instead of
a CDT?

2) From reading Book of Shen, 3rd. Ed., I have some confusion over the
namespacing of the types. For example, and this is purely hypothetical,
let's suppose I'm trying to write a window manager for a homebrew computer
of my own design. There can be many different kinds of on-screen gadgets:
windows, menus, icons, that sort of thing. These, ideally, can be
represented (at least conceptually if not in part) with a single ADT called
on-screen-gadget. If I put a (datatype on-screen-gadget ... ) in GUI
package, it seems that the names of the procedures for the ADT would have
to also sit inside the GUI package too, yes? It's not clear to me how I
can use an ADT to define an interface in a single location to multiple
implementations of on-screen-gadgets.

Now I'm not necessarily looking to clone CLOS here; but since OO is what
I'm currently most familiar with, I was wondering what the "Shen Way" of
resolving this issue is, and how ADTs would or could help (or not!) in this
situation.

Many thanks for any helpful advice given.


\\
Post by Antti Ylikoski
\\ Stack as an Abstract Datatype
\\
\\ AJY 2015-10-10
\\
\\ Implementation as a list of conses
(datatype stack
__________________________________
empty-stack: (--> (stack A));
___________________________________
push: (A --> (stack A) --> (stack A));
___________________________________
top: ((stack A) --> A);
____________________________________
pop: ((stack A) --> (stack A));
)
(define empty-stack
-> []) \\ Returns an empty stack
(define push
Obj St -> (cons Obj St)) \\ Pushes and returns stack
(define top
St -> (head St)) \\ Returns the top element
(define pop
St -> (tail St)) \\ Removes the top element, returns stack
------------------------------------------------------------
Some help would be very much appreciated.
yours, A. J. Y.
HELSINKI
Finland
--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+***@googlegroups.com.
To post to this group, send an email to ***@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
Willi Riha
2016-08-11 02:31:42 UTC
Permalink
I am tempted to reply in detail to the proposed ‘abstract’ data type
‘stack’, but I shall refrain from doing so.

The implementation is very much a ‘concrete’ data type – stack implemented
as a list! Not abstract at all!

It is completely insecure, because knowing what the implementation is, I
can get hold of the element below the top by invoking (nth 2 stack), or
whatever.

In Shen, not everything that is listed under the dataype heading makes an
abstract data type. As a matter of fact, and Mark was very kind not to
point this out, what is listed under datatype stack is completely
redundant, as it does not convey any information to the Shen system. (Just
as in the attempted ‘abstract’ data type, complex, proposed by the same
author a couple of months ago).

An abstract data type, mathematically speaking, is a rather difficult
concept. It requires knowledge of algebraic structures and operations
(homomorphisms).

Implementing an abstract data type in a programming language, basically,
amounts to restricting the user to the operations that are associated with
the data type. This is often not so easy, especially when the code cannot
be hidden.

In C/C++, there is a public interface (a .h file) which informs the user of
the syntax and functionality of the available functions. The actual code is
contained in a .c or .c++ file not seen by the user.

In Shen, certainly in the OS version, the source code of all libraries is
publicly available, and implementation details are readily available, and
could be exploited for nefarious purposes.

Implementing data types by means of absvectors makes such a practice much
more difficult. absvectors, in Shen come very close to a (readable) and
secure implementation of abstract data types.
Post by Antti Ylikoski
I started authoring a multi user poker game, after the recommendation
of Mark Tarver.
------------------------------------------------------------
(datatype card
\\ and its operations....
)
(datatype deck-of-cards
\\ its operations....
)
(datatype poker-hand
\\ the operations.....
)
(datatype player
\\ the ops......
)
(datatype poker-game
\\ the ops......
\\ a settable number of players with settable different strategies
\\ One or several ones may be humans, ie. users
)
(datatype poker-strategy
\\ Can be set for a player
)
------------------------------------------------------------
I wrote the following stack abstract datatype for an exercise, but I
need to ask one question -- one more beginner's question!
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (load "stack.shen")
type#stack
empty-stack
push
top
pop
run time: 0.07599999848753214 secs
loaded
(1-)
------------------------------------------------------------
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (tc +)
true
(1+) (load "stack.shen")
empty-stack lacks a proper signature.
(2+)
------------------------------------------------------------
------------------------------------------------------------
\\
\\ Stack as an Abstract Datatype
\\
\\ AJY 2015-10-10
\\
\\ Implementation as a list of conses
(datatype stack
__________________________________
empty-stack: (--> (stack A));
___________________________________
push: (A --> (stack A) --> (stack A));
___________________________________
top: ((stack A) --> A);
____________________________________
pop: ((stack A) --> (stack A));
)
(define empty-stack
-> []) \\ Returns an empty stack
(define push
Obj St -> (cons Obj St)) \\ Pushes and returns stack
(define top
St -> (head St)) \\ Returns the top element
(define pop
St -> (tail St)) \\ Removes the top element, returns stack
------------------------------------------------------------
Some help would be very much appreciated.
yours, A. J. Y.
HELSINKI
Finland
--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+***@googlegroups.com.
To post to this group, send an email to ***@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
Samuel Falvo II
2016-08-11 03:52:52 UTC
Permalink
Thanks, but this does not seem relevant to what I'm asking. Python, too, suffers from what you describe, and Ruby and Javascript moreso. These languages succeed nonetheless.

I'm asking what the value proposition of ADTs are in Shen, along with a suitable example for me to study. In other words, when/where would I use them, and why. The examples I've seen so far are so contrived as to not serve to elucidate their features uniquely in the Shen type ecosystem.
--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+***@googlegroups.com.
To post to this group, send an email to ***@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
Mark Tarver
2016-08-20 08:52:22 UTC
Permalink
The value of ADTs in Shen is that of other languages; TBoS explains it in a
paragraph.

*By hiding inessential information on how the abstract datatype is
implemented and allowing access to the data structure only through the
accessor functions, abstract datatypes build a barrier of abstraction
between the essential properties of the datatype and the accidental
properties of how we choose to implement it. This in turn, reduces
information load and allows flexibility in making changes to the
representation without having to rewrite large stretches of code.*

*

TBoS p 250*


Mark
Post by Samuel Falvo II
Thanks, but this does not seem relevant to what I'm asking. Python, too,
suffers from what you describe, and Ruby and Javascript moreso. These
languages succeed nonetheless.
I'm asking what the value proposition of ADTs are in Shen, along with a
suitable example for me to study. In other words, when/where would I use
them, and why. The examples I've seen so far are so contrived as to not
serve to elucidate their features uniquely in the Shen type ecosystem.
--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+***@googlegroups.com.
To post to this group, send an email to ***@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
Samuel Falvo II
2016-08-23 05:41:16 UTC
Permalink
Post by Mark Tarver
The value of ADTs in Shen is that of other languages; TBoS explains it in
a paragraph.
OK, I just had an epiphany. I noticed in the provided stack example,
there's a definition:

(define top
S -> (S top))

So, if we represent S with a dispatching lambda as the examples
demonstrate, this allows for polymorphism amongst different
implementations, as long as the type-checker can prove compliance with the
declared interface.

I'm not sure why I didn't get this on first reading, or when replying.
This makes some more sense. I'll need to play more with this in practice
to get a better feel, but I think I have an understanding of when this form
of data type should be preferred over concrete now.

Thanks again, Mark, for taking the time to respond. Apologies for being a
bit daft in this particular topic.
--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+***@googlegroups.com.
To post to this group, send an email to ***@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
Samuel Falvo II
2016-08-23 05:14:41 UTC
Permalink
Post by Mark Tarver
The value of ADTs in Shen is that of other languages; TBoS explains it in
a paragraph.
*By hiding inessential information on how the abstract datatype is
implemented and allowing access to the data structure only through the
accessor functions, abstract datatypes build a barrier of abstraction
between the essential properties of the datatype and the accidental
properties of how we choose to implement it. This in turn, reduces
information load and allows flexibility in making changes to the
representation without having to rewrite large stretches of code.*
I read it, but I just don't believe it at face-value. As Willi mentioned
in another message in this thread, with Shen, you have access to the source
code backing the data type, concrete or abstract. Even if I were to write
a package that exposed an ADT that used lambda expressions to obscure its
implementation, it's entirely possible (and indeed likely) that someone
will study the code, and construct access patterns that exploit how it's
implemented. For instance, if I may be allowed to contrive a hypothetical
situation, let's suppose I'm writing a new desktop for a fancy GUI, and I
want to support automation by 3rd party tools. I want something that
represents a filesystem directory. We can pretend this implementation uses
an interface quite similar to (get) and (put), albeit with predefined
relations. For instance, a client might write:

(define is-system-volume-valid?
DirInstance ->
(let num-files (get-dir - number-of-files DirInstance)
num-subdirs (get-dir - number-of-directories DirInstance)
shell-exists? (get-dir "SHELL.BIN" file-exists? DirInstance)
(and shell-exists? (> (+ num-files num-subdirs) 15))))

Under one implementation, the directory DirInstance can in fact be
represented concretely with a property vector, particularly those which are
read from disk storage. In this case, (get-dir) and (put-dir) are thin
veneers over (get) and (put), respectively. Another implementation,
however, could be implemented as a network client, and its interface is
managed dynamically as an RPC channel. In this situation, the concrete
representation will have no relationship to the property vector-like
behavior we desire. Whichever approach we choose, ADT or CDT, the client
programmer will have the freedom to inspect the source code behind the
DirInstance type, and can learn all sorts of things about its
implementation, even if the only thing the programmer sees at the REPL are
typed lambda expressions.

Put another way, the ADT merely makes it less convenient to deep-inspect
the guts of the type, but certainly not impossible. Provided you implement
its concrete representation with a collection of closures, it does makes it
difficult to impossible to abuse. I'm not sure if this property holds,
however, if you use other representations.

Since maintaining full ADT abstraction depends on the curious programmer
not reading the ADT's source, I'm thinking you can get the same benefits as
an ADT with a CDT if you impose the same constraints on the programmer. In
particular:

* Do not inspect the DT's source code.
* Do not deep-inspect or otherwise depend on the structure of any instance
of the DT.
* Access the DT instance only through its package's exported functions.

If the first two bullets are adhered to, then I (as a data type author)
retain the ability to alter implementation details without needing to
change huge amounts of code in client applications.

Once again: I'm not saying *not* to use ADTs. I'm just questioning when
they would offer tangible benefits to other programmers. Clearly they do
or else they wouldn't be part of the language. However, the gentleman's
agreement I listed above is sufficient to retain the properties of an ADT
but with a CDT as well. This seems to work in Perl, Python, Ruby, and
other dynamically-typed languages.

Apologies if this topic is exhausting; not trying to poke a hornet's nest,
just trying to learn best practices. If you prefer to drop the subject,
which is the sense I get, I'll just let it go. :-)

Thanks for taking the time to respond. It's appreciated.
--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+***@googlegroups.com.
To post to this group, send an email to ***@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
Willi Riha
2016-08-11 14:16:13 UTC
Permalink
Sorry, this was not a reply to your question - I was referring to Antti's
posting!
Post by Antti Ylikoski
I started authoring a multi user poker game, after the recommendation
of Mark Tarver.
------------------------------------------------------------
(datatype card
\\ and its operations....
)
(datatype deck-of-cards
\\ its operations....
)
(datatype poker-hand
\\ the operations.....
)
(datatype player
\\ the ops......
)
(datatype poker-game
\\ the ops......
\\ a settable number of players with settable different strategies
\\ One or several ones may be humans, ie. users
)
(datatype poker-strategy
\\ Can be set for a player
)
------------------------------------------------------------
I wrote the following stack abstract datatype for an exercise, but I
need to ask one question -- one more beginner's question!
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (load "stack.shen")
type#stack
empty-stack
push
top
pop
run time: 0.07599999848753214 secs
loaded
(1-)
------------------------------------------------------------
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (tc +)
true
(1+) (load "stack.shen")
empty-stack lacks a proper signature.
(2+)
------------------------------------------------------------
------------------------------------------------------------
\\
\\ Stack as an Abstract Datatype
\\
\\ AJY 2015-10-10
\\
\\ Implementation as a list of conses
(datatype stack
__________________________________
empty-stack: (--> (stack A));
___________________________________
push: (A --> (stack A) --> (stack A));
___________________________________
top: ((stack A) --> A);
____________________________________
pop: ((stack A) --> (stack A));
)
(define empty-stack
-> []) \\ Returns an empty stack
(define push
Obj St -> (cons Obj St)) \\ Pushes and returns stack
(define top
St -> (head St)) \\ Returns the top element
(define pop
St -> (tail St)) \\ Removes the top element, returns stack
------------------------------------------------------------
Some help would be very much appreciated.
yours, A. J. Y.
HELSINKI
Finland
--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+***@googlegroups.com.
To post to this group, send an email to ***@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
Antti Ylikoski
2016-08-11 16:02:13 UTC
Permalink
I fixed the definition of the stack as an abstract datatype.

The corrected stack.shen comes as an attachment.

Now the stack ADT works as below:

------------------------------------------------------------

***@antti-HP-Compaq-dc7100-SFF-PE271ET ~/stack $ ./Shen

Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: CLisp
port 1.9 ported by Mark Tarver


(0-) (tc +)
true

(1+) (load "stack.shen")

type#stack : symbol
empty-stack : (--> (stack A))
push : (A --> ((stack A) --> (stack A)))
top : ((stack A) --> A)
pop : ((stack A) --> (stack A))
run time: 0.9239999689161777 secs

typechecked in 410 inferences
loaded : symbol

(2+) (set st (empty-stack))
[] : (stack A)

(3+) (push zap (value st))
[zap] : (stack symbol)

(4+) (push foo (value st))
[foo] : (stack symbol)

(5+) (set st (push bar (value st)))
[bar] : (stack symbol)

(6+) (set st (push zap (value st)))
[zap bar] : (stack symbol)

(7+) (set st (push froob (value st)))
[froob zap bar] : (stack symbol)

(8+) (top (value st))
froob : A

(9+) (pop (value st))
[zap bar] : (stack A)

(10+) (tc -)
false : boolean

(11-) (QUIT)
***@antti-HP-Compaq-dc7100-SFF-PE271ET ~/stack $

------------------------------------------------------------

Some notes as to the netiquette.

I will not argument with others here. And Mark was highly correct
when saying that net naval battles should not be posted in the group.
It is bad netiquette.

But as to the ADTs: The Shen system is a brilliant help for the
programmer who wants to create something truly complex. I saw this
when writing ANN software with Shen.

And, one more note: I wrote about the "non type secure DEFSTRUCT" by
Ramil Farkshatov. It is not non type secure, as RF corrected me. Sorry!

yours, AJY
HELSINKI
Finland, the EU
Post by Willi Riha
Sorry, this was not a reply to your question - I was referring to Antti's
posting!
Post by Antti Ylikoski
I started authoring a multi user poker game, after the recommendation
of Mark Tarver.
------------------------------------------------------------
(datatype card
\\ and its operations....
)
(datatype deck-of-cards
\\ its operations....
)
(datatype poker-hand
\\ the operations.....
)
(datatype player
\\ the ops......
)
(datatype poker-game
\\ the ops......
\\ a settable number of players with settable different strategies
\\ One or several ones may be humans, ie. users
)
(datatype poker-strategy
\\ Can be set for a player
)
------------------------------------------------------------
I wrote the following stack abstract datatype for an exercise, but I
need to ask one question -- one more beginner's question!
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (load "stack.shen")
type#stack
empty-stack
push
top
pop
run time: 0.07599999848753214 secs
loaded
(1-)
------------------------------------------------------------
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (tc +)
true
(1+) (load "stack.shen")
empty-stack lacks a proper signature.
(2+)
------------------------------------------------------------
------------------------------------------------------------
\\
\\ Stack as an Abstract Datatype
\\
\\ AJY 2015-10-10
\\
\\ Implementation as a list of conses
(datatype stack
__________________________________
empty-stack: (--> (stack A));
___________________________________
push: (A --> (stack A) --> (stack A));
___________________________________
top: ((stack A) --> A);
____________________________________
pop: ((stack A) --> (stack A));
)
(define empty-stack
-> []) \\ Returns an empty stack
(define push
Obj St -> (cons Obj St)) \\ Pushes and returns stack
(define top
St -> (head St)) \\ Returns the top element
(define pop
St -> (tail St)) \\ Removes the top element, returns stack
------------------------------------------------------------
Some help would be very much appreciated.
yours, A. J. Y.
HELSINKI
Finland
--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+***@googlegroups.com.
To post to this group, send an email to ***@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
Willi Riha
2016-08-12 00:06:28 UTC
Permalink
I do not argue about issues when there is nothing to argue about..

I will just *state* again that the proposed stack implementation* is not an
abstract data type*, but very much a *concrete* one. Never mind, you are
now satisfied that it works.
.
Read the Shen Book 3rd ed, chapter 21, where it is spelled out that the an
obvious *list implementation of a stack is concrete. *Maybe you know
better?

You will find a genuine abstract stack Shen implementation in terms of
lambda functions, which, so I believe, simulates the so-called "term
algebra" of an abstract data type..
It is impossible to perform any illegal operations on such stacks - you
can't even see the elements currently on the stack - you can only inspect
the 'top' element, as required..
.
If somebody cannot tell the difference between pigs and cows, because after
all, they are animals, reared to be slaughtered for human consumption, then
there is absolutely no point attempting to explain to them that they are
different.

Your stack implementation works for you (even though it does not deal with
errors), - call it whatever you like, but, please,do not call it an
"abstract data type", because, it ain't!.

No more comments from me, unless some more outrageous claims are
forthcoming.
Post by Antti Ylikoski
I started authoring a multi user poker game, after the recommendation
of Mark Tarver.
------------------------------------------------------------
(datatype card
\\ and its operations....
)
(datatype deck-of-cards
\\ its operations....
)
(datatype poker-hand
\\ the operations.....
)
(datatype player
\\ the ops......
)
(datatype poker-game
\\ the ops......
\\ a settable number of players with settable different strategies
\\ One or several ones may be humans, ie. users
)
(datatype poker-strategy
\\ Can be set for a player
)
------------------------------------------------------------
I wrote the following stack abstract datatype for an exercise, but I
need to ask one question -- one more beginner's question!
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (load "stack.shen")
type#stack
empty-stack
push
top
pop
run time: 0.07599999848753214 secs
loaded
(1-)
------------------------------------------------------------
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (tc +)
true
(1+) (load "stack.shen")
empty-stack lacks a proper signature.
(2+)
------------------------------------------------------------
------------------------------------------------------------
\\
\\ Stack as an Abstract Datatype
\\
\\ AJY 2015-10-10
\\
\\ Implementation as a list of conses
(datatype stack
__________________________________
empty-stack: (--> (stack A));
___________________________________
push: (A --> (stack A) --> (stack A));
___________________________________
top: ((stack A) --> A);
____________________________________
pop: ((stack A) --> (stack A));
)
(define empty-stack
-> []) \\ Returns an empty stack
(define push
Obj St -> (cons Obj St)) \\ Pushes and returns stack
(define top
St -> (head St)) \\ Returns the top element
(define pop
St -> (tail St)) \\ Removes the top element, returns stack
------------------------------------------------------------
Some help would be very much appreciated.
yours, A. J. Y.
HELSINKI
Finland
--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+***@googlegroups.com.
To post to this group, send an email to ***@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
Antti Ylikoski
2016-08-12 04:54:50 UTC
Permalink
See TBoS p.249:

"We have defined a stack as an abstract datatype..."

the example in question is from TBoS pp. 248--249 in the beginning of Ch.
21.

https://en.wikipedia.org/wiki/Abstract_data_type

AJY
HELSINKI
Finland, the EU
Post by Willi Riha
I do not argue about issues when there is nothing to argue about..
I will just *state* again that the proposed stack implementation* is not
an abstract data type*, but very much a *concrete* one. Never mind, you
are now satisfied that it works.
.
Read the Shen Book 3rd ed, chapter 21, where it is spelled out that the an
obvious *list implementation of a stack is concrete. *Maybe you know
better?
You will find a genuine abstract stack Shen implementation in terms of
lambda functions, which, so I believe, simulates the so-called "term
algebra" of an abstract data type..
It is impossible to perform any illegal operations on such stacks - you
can't even see the elements currently on the stack - you can only inspect
the 'top' element, as required..
.
If somebody cannot tell the difference between pigs and cows, because
after all, they are animals, reared to be slaughtered for human
consumption, then there is absolutely no point attempting to explain to
them that they are different.
Your stack implementation works for you (even though it does not deal with
errors), - call it whatever you like, but, please,do not call it an
"abstract data type", because, it ain't!.
No more comments from me, unless some more outrageous claims are
forthcoming.
Post by Antti Ylikoski
I started authoring a multi user poker game, after the recommendation
of Mark Tarver.
------------------------------------------------------------
(datatype card
\\ and its operations....
)
(datatype deck-of-cards
\\ its operations....
)
(datatype poker-hand
\\ the operations.....
)
(datatype player
\\ the ops......
)
(datatype poker-game
\\ the ops......
\\ a settable number of players with settable different strategies
\\ One or several ones may be humans, ie. users
)
(datatype poker-strategy
\\ Can be set for a player
)
------------------------------------------------------------
I wrote the following stack abstract datatype for an exercise, but I
need to ask one question -- one more beginner's question!
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (load "stack.shen")
type#stack
empty-stack
push
top
pop
run time: 0.07599999848753214 secs
loaded
(1-)
------------------------------------------------------------
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (tc +)
true
(1+) (load "stack.shen")
empty-stack lacks a proper signature.
(2+)
------------------------------------------------------------
------------------------------------------------------------
\\
\\ Stack as an Abstract Datatype
\\
\\ AJY 2015-10-10
\\
\\ Implementation as a list of conses
(datatype stack
__________________________________
empty-stack: (--> (stack A));
___________________________________
push: (A --> (stack A) --> (stack A));
___________________________________
top: ((stack A) --> A);
____________________________________
pop: ((stack A) --> (stack A));
)
(define empty-stack
-> []) \\ Returns an empty stack
(define push
Obj St -> (cons Obj St)) \\ Pushes and returns stack
(define top
St -> (head St)) \\ Returns the top element
(define pop
St -> (tail St)) \\ Removes the top element, returns stack
------------------------------------------------------------
Some help would be very much appreciated.
yours, A. J. Y.
HELSINKI
Finland
--
You received this message because you are subscribed to a topic in the
Google Groups "Shen" group.
To unsubscribe from this topic, visit https://groups.google.com/d/
topic/qilang/UEJyD7W7iBQ/unsubscribe.
To unsubscribe from this group and all its topics, send an email to
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+***@googlegroups.com.
To post to this group, send an email to ***@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
Antti Ylikoski
2016-08-12 09:19:47 UTC
Permalink
https://en.wikipedia.org/wiki/Abstract_data_type

AJY

Indeed, there is there nothing to argue about. Pigs and cows?

Idem
Post by Willi Riha
I do not argue about issues when there is nothing to argue about..
I will just *state* again that the proposed stack implementation* is not
an abstract data type*, but very much a *concrete* one. Never mind, you
are now satisfied that it works.
.
Read the Shen Book 3rd ed, chapter 21, where it is spelled out that the an
obvious *list implementation of a stack is concrete. *Maybe you know
better?
You will find a genuine abstract stack Shen implementation in terms of
lambda functions, which, so I believe, simulates the so-called "term
algebra" of an abstract data type..
It is impossible to perform any illegal operations on such stacks - you
can't even see the elements currently on the stack - you can only inspect
the 'top' element, as required..
.
If somebody cannot tell the difference between pigs and cows, because
after all, they are animals, reared to be slaughtered for human
consumption, then there is absolutely no point attempting to explain to
them that they are different.
Your stack implementation works for you (even though it does not deal with
errors), - call it whatever you like, but, please,do not call it an
"abstract data type", because, it ain't!.
No more comments from me, unless some more outrageous claims are
forthcoming.
Post by Antti Ylikoski
I started authoring a multi user poker game, after the recommendation
of Mark Tarver.
------------------------------------------------------------
(datatype card
\\ and its operations....
)
(datatype deck-of-cards
\\ its operations....
)
(datatype poker-hand
\\ the operations.....
)
(datatype player
\\ the ops......
)
(datatype poker-game
\\ the ops......
\\ a settable number of players with settable different strategies
\\ One or several ones may be humans, ie. users
)
(datatype poker-strategy
\\ Can be set for a player
)
------------------------------------------------------------
I wrote the following stack abstract datatype for an exercise, but I
need to ask one question -- one more beginner's question!
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (load "stack.shen")
type#stack
empty-stack
push
top
pop
run time: 0.07599999848753214 secs
loaded
(1-)
------------------------------------------------------------
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (tc +)
true
(1+) (load "stack.shen")
empty-stack lacks a proper signature.
(2+)
------------------------------------------------------------
------------------------------------------------------------
\\
\\ Stack as an Abstract Datatype
\\
\\ AJY 2015-10-10
\\
\\ Implementation as a list of conses
(datatype stack
__________________________________
empty-stack: (--> (stack A));
___________________________________
push: (A --> (stack A) --> (stack A));
___________________________________
top: ((stack A) --> A);
____________________________________
pop: ((stack A) --> (stack A));
)
(define empty-stack
-> []) \\ Returns an empty stack
(define push
Obj St -> (cons Obj St)) \\ Pushes and returns stack
(define top
St -> (head St)) \\ Returns the top element
(define pop
St -> (tail St)) \\ Removes the top element, returns stack
------------------------------------------------------------
Some help would be very much appreciated.
yours, A. J. Y.
HELSINKI
Finland
--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+***@googlegroups.com.
To post to this group, send an email to ***@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
Neal Alexander
2016-08-12 11:20:59 UTC
Permalink
I remember finding the topic ambiguous when I first read it too. At the
moment, I don't have the book here to review, but I assume that I was
probably confusing the subject with Haskell's Type Classes or Abstract Base
Classes / Interfaces from OOP langs.

Something like below can work if you want OOP semantics. The example is
broken despite type checking though, because the rules overlap in the
(stack string) instance - i.e. [stack "ab" [...]] has the same type as
[stack ["a" "b"] [...]]. I assume you can add a second parameter to the
stack type, describing the underlying container, but I got bored and gave
up trying to get it to work after 10min.

(datatype rules-00
PUSH : (A --> (list A) --> (list A));
TOP : ((list A) --> A);
POP : ((list A) --> (list A));
DATA : (list A);
==================================================
[stack DATA [POP TOP PUSH]] : (stack A);)

(datatype rules-01
PUSH : (string --> string --> string);
TOP : (string --> string);
POP : (string --> string);
DATA : string;
==================================================
[stack DATA [POP TOP PUSH]] : (stack string);)


\\ Abstract API boilerplate

(define stack-push
{ A --> (stack A) --> (stack A) }
A [stack S [P T Push]] -> [stack (Push A S) [P T Push]])


\\ Instances

(define empty-string-stack
{ --> (stack string) }
-> [stack ""
[(function tlstr) (function hdstr) (function cn)]])

(define empty-list-stack
{ --> (stack A) }
-> [stack []
[(function tail) (function head) (function cons)]])

\\ Test

(stack-push "a"
(stack-push "b"
(empty-string-stack)))

(stack-push "a"
(stack-push "b"
(empty-list-stack)))
Post by Willi Riha
I do not argue about issues when there is nothing to argue about..
I will just *state* again that the proposed stack implementation* is not
an abstract data type*, but very much a *concrete* one. Never mind, you
are now satisfied that it works.
.
Read the Shen Book 3rd ed, chapter 21, where it is spelled out that the an
obvious *list implementation of a stack is concrete. *Maybe you know
better?
You will find a genuine abstract stack Shen implementation in terms of
lambda functions, which, so I believe, simulates the so-called "term
algebra" of an abstract data type..
It is impossible to perform any illegal operations on such stacks - you
can't even see the elements currently on the stack - you can only inspect
the 'top' element, as required..
.
If somebody cannot tell the difference between pigs and cows, because
after all, they are animals, reared to be slaughtered for human
consumption, then there is absolutely no point attempting to explain to
them that they are different.
Your stack implementation works for you (even though it does not deal with
errors), - call it whatever you like, but, please,do not call it an
"abstract data type", because, it ain't!.
No more comments from me, unless some more outrageous claims are
forthcoming.
Post by Antti Ylikoski
I started authoring a multi user poker game, after the recommendation
of Mark Tarver.
------------------------------------------------------------
(datatype card
\\ and its operations....
)
(datatype deck-of-cards
\\ its operations....
)
(datatype poker-hand
\\ the operations.....
)
(datatype player
\\ the ops......
)
(datatype poker-game
\\ the ops......
\\ a settable number of players with settable different strategies
\\ One or several ones may be humans, ie. users
)
(datatype poker-strategy
\\ Can be set for a player
)
------------------------------------------------------------
I wrote the following stack abstract datatype for an exercise, but I
need to ask one question -- one more beginner's question!
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (load "stack.shen")
type#stack
empty-stack
push
top
pop
run time: 0.07599999848753214 secs
loaded
(1-)
------------------------------------------------------------
------------------------------------------------------------
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Common Lisp, implementation: SBCL
port 2.0 ported by Mark Tarver
(0-) (tc +)
true
(1+) (load "stack.shen")
empty-stack lacks a proper signature.
(2+)
------------------------------------------------------------
------------------------------------------------------------
\\
\\ Stack as an Abstract Datatype
\\
\\ AJY 2015-10-10
\\
\\ Implementation as a list of conses
(datatype stack
__________________________________
empty-stack: (--> (stack A));
___________________________________
push: (A --> (stack A) --> (stack A));
___________________________________
top: ((stack A) --> A);
____________________________________
pop: ((stack A) --> (stack A));
)
(define empty-stack
-> []) \\ Returns an empty stack
(define push
Obj St -> (cons Obj St)) \\ Pushes and returns stack
(define top
St -> (head St)) \\ Returns the top element
(define pop
St -> (tail St)) \\ Removes the top element, returns stack
------------------------------------------------------------
Some help would be very much appreciated.
yours, A. J. Y.
HELSINKI
Finland
--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+***@googlegroups.com.
To post to this group, send an email to ***@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.
Continue reading on narkive:
Loading...