Beginner's Question: Abstract Datatypes

[Antti Ylikoski]

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:

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

antti@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:

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

antti@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

[Mark Tarver]

It would probably be simpler and more useful to use concrete datatypes.   Define a card as such.

Mark

[Antti Ylikoski]

OK

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

Thanks.

AJY

[Samuel Falvo II]

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.

[Willi Riha]

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. 

[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.

[Willi Riha]

Sorry, this was not a reply to your question - I was referring to Antti's posting!

On Saturday, October 10, 2015 at 10:39:28 AM UTC+1, Antti Ylikoski wrote:

[Antti Ylikoski]

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@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@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

[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.

  

 

On Saturday, October 10, 2015 at 10:39:28 AM UTC+1, Antti Ylikoski wrote:

[Antti Ylikoski]

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

--
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 qilang+unsubscribe@googlegroups.com.
To post to this group, send email to qil...@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

[Antti Ylikoski]

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

AJY

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

Idem

[Neal Alexander]

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)))

[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.

                                                                                                                                                                                   TBoS p 250

 

Mark

[Samuel Falvo II]

On Saturday, August 20, 2016 at 1:52:23 AM UTC-7, Mark Tarver wrote:

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.

[Samuel Falvo II]

On Saturday, August 20, 2016 at 1:52:23 AM UTC-7, Mark Tarver wrote:

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.