ما هو النوع الوجودي؟
-
08-07-2019 - |
سؤال
قرأت من خلال مقالة ويكيبيديا الأنواع الوجودية.لقد جمعت أنها تسمى الأنواع الوجودية بسبب العامل الوجودي (∃).لست متأكدًا من المغزى من ذلك، رغم ذلك.ما الفرق بين
T = ∃X { X a; int f(X); }
و
T = ∀x { X a; int f(X); }
?
المحلول
عند يعرف شخص ما ∀X
نوع عالمية يقولونه: <م> يمكنك سد العجز في أي نوع تريد، ولست بحاجة إلى معرفة أي شيء عن هذا النوع لأقوم بعملي، وأنا سوف أشير فقط إلى أنه opaquely كما X
م>.
عند يعرف شخص ما ∃X
نوع جودية يقولونه: <م> سوف تستخدم أيا كان نوعها أريد هنا. أنت لن تعرف أي شيء عن هذا النوع، بحيث يمكنك الرجوع إليها فقط opaquely كما X
م>.
والعالمي تمكنك من كتابة أشياء مثل:
void copy<T>(List<T> source, List<T> dest) {
...
}
وظيفة copy
ليس لديه فكرة عما سيكون T
في الواقع، ولكن لا حاجة إليها.
وأنواع الوجودية سوف تمكنك من كتابة أشياء مثل:
interface VirtualMachine<B> {
B compile(String source);
void run(B bytecode);
}
// Now, if you had a list of VMs you wanted to run on the same input:
void runAllCompilers(List<∃B:VirtualMachine<B>> vms, String source) {
for (∃B:VirtualMachine<B> vm : vms) {
B bytecode = vm.compile(source);
vm.run(bytecode);
}
}
وكل تنفيذ الجهاز الظاهري في القائمة يمكن أن يكون لها نوع بايت كود مختلفة. وظيفة runAllCompilers
ليس لديه فكرة ما هو نوع بايت كود، ولكنها لا تحتاج إلى؛ كل ما يفعله هو تتابع بايت كود من VirtualMachine.compile
إلى VirtualMachine.run
.
ونوع جافا البدل (مثلا: List<?>
) هي شكل محدود جدا من أنواع الوجودية
<القوي> تحديث: هل نسيت أن أذكر أنه يمكنك نوع من أنواع محاكاة وجودية مع أنواع عالمية. أولا، والتفاف نوع عالمي لإخفاء المعلمة نوع. ثانيا، ومراقبة قلب (هذا بمقايضة بشكل فعال "أنت" و "أنا" جزء في التعريفات أعلاه، وهذا هو الفرق الأساسي بين جوديات والمسلمات).
// A wrapper that hides the type parameter 'B'
interface VMWrapper {
void unwrap(VMHandler handler);
}
// A callback (control inversion)
interface VMHandler {
<B> void handle(VirtualMachine<B> vm);
}
والآن نحن يمكن أن يكون VMWrapper
استدعاء VMHandler
منطقتنا التي لديه وظيفة handle
كتبته عالميا. الأثر الصافي هو نفسه، رمز لديه لعلاج B
كما مبهمة.
void runWithAll(List<VMWrapper> vms, final String input)
{
for (VMWrapper vm : vms) {
vm.unwrap(new VMHandler() {
public <B> void handle(VirtualMachine<B> vm) {
B bytecode = vm.compile(input);
vm.run(bytecode);
}
});
}
}
ومثال تنفيذ VM:
class MyVM implements VirtualMachine<byte[]>, VMWrapper {
public byte[] compile(String input) {
return null; // TODO: somehow compile the input
}
public void run(byte[] bytecode) {
// TODO: Somehow evaluate 'bytecode'
}
public void unwrap(VMHandler handler) {
handler.handle(this);
}
}
نصائح أخرى
قيمة نوع وجودي يحب ∃x. F(x)
هو زوج تحتوي على بعض يكتب x
و أ قيمة من النوع F(x)
.في حين أن قيمة نوع متعدد الأشكال مثل ∀x. F(x)
هو وظيفة هذا يأخذ نوعا ما x
و ينتج عنه قيمة النوع F(x)
.في كلتا الحالتين، يتم إغلاق النوع عبر مُنشئ نوع ما F
.
لاحظ أن طريقة العرض هذه تمزج بين الأنواع والقيم.والدليل الوجودي نوع واحد وقيمة واحدة.الدليل الشامل عبارة عن مجموعة كاملة من القيم المفهرسة حسب النوع (أو التعيين من الأنواع إلى القيم).
إذن الفرق بين النوعين اللذين حددتهما هو كما يلي:
T = ∃X { X a; int f(X); }
هذا يعنى:قيمة النوع T
يحتوي على نوع يسمى X
, ، قيمة a:X
, ، ووظيفة f:X->int
.منتج لقيم النوع T
عليه أن يختار أي اكتب ل X
والمستهلك لا يستطيع أن يعرف أي شيء عنه X
.إلا أن هناك مثال واحد عليه يسمى a
وأنه يمكن تحويل هذه القيمة إلى int
بإعطائها ل f
.وبعبارة أخرى، قيمة النوع T
يعرف كيفية إنتاج int
بطريقة ما.حسنًا، يمكننا التخلص من النوع المتوسط X
وقل فقط:
T = int
أما القياس الكمي عالميًا فهو مختلف قليلاً.
T = ∀X { X a; int f(X); }
هذا يعنى:قيمة النوع T
يمكن أن تعطى أي نوع X
, ، وسوف تنتج قيمة a:X
, ، ووظيفة f:X->int
بغض النظر X
يكون.بعبارة أخرى:مستهلك لقيم النوع T
يمكن اختيار أي نوع ل X
.ومنتج لقيم النوع T
لا أستطيع أن أعرف أي شيء على الإطلاق عنه X
, ولكن يجب أن تكون قادرة على إنتاج قيمة a
لأي اختيار X
, ، وتكون قادرة على تحويل هذه القيمة إلى int
.
من الواضح أن تنفيذ هذا النوع أمر مستحيل، لأنه لا يوجد برنامج يمكنه إنتاج قيمة من كل نوع يمكن تخيله.إلا إذا كنت تسمح السخافات مثل null
أو قيعان.
وبما أن الوجودي عبارة عن زوج، فيمكن تحويل الحجة الوجودية إلى حجة عالمية عبر الكاري.
(∃b. F(b)) -> Int
بالضبط مثل:
∀b. (F(b) -> Int)
السابق هو أ المرتبة 2 وجودي.وهذا يؤدي إلى الخاصية المفيدة التالية:
كل نوع من الرتبة الكمية وجوديا
n+1
هو نوع من الرتبة كميا عالمياn
.
هناك خوارزمية قياسية لتحويل الوجوديات إلى عالميات، تسمى Sklemization.
أعتقد أنه من المنطقي شرح الأنواع الوجودية مع الأنواع العالمية، حيث أن المفهومين متكاملان، أي.أحدهما هو "عكس" الآخر.
لا أستطيع الإجابة على كل التفاصيل حول الأنواع الوجودية (مثل إعطاء تعريف دقيق، وسرد جميع الاستخدامات الممكنة، وعلاقتها بأنواع البيانات المجردة، وما إلى ذلك) لأنني ببساطة لست على دراية كافية بذلك.سأوضح فقط (باستخدام جافا) ما هذه المقالة هاسكل ويكي تنص على أنها التأثير الرئيسي للأنواع الوجودية:
يمكن أن تكون الأنواع الوجودية مستخدم لعدة أغراض مختلفة.لكن ما هم يفعل هو "إخفاء" متغير النوع على الجانب الأيمن.عادةً، أي متغير نوع يظهر على اليمين يجب أن يظهر أيضًا على اليسار […]
مثال الإعداد:
الكود الزائف التالي ليس صالحًا تمامًا لـ Java، على الرغم من أنه سيكون من السهل إصلاح ذلك.في الواقع، هذا بالضبط ما سأفعله في هذه الإجابة!
class Tree<α>
{
α value;
Tree<α> left;
Tree<α> right;
}
int height(Tree<α> t)
{
return (t != null) ? 1 + max( height(t.left), height(t.right) )
: 0;
}
اسمحوا لي أن أشرح لك هذا باختصار.نحن نحدد…
نوع العودي
Tree<α>
والذي يمثل عقدة في شجرة ثنائية.كل عقدة تخزن أvalue
من نوع ما α ولها إشارات إلى اختياريleft
وright
الأشجار الفرعية من نفس النوع.وظيفة
height
والتي تُرجع المسافة الأبعد من أي عقدة ورقية إلى العقدة الجذريةt
.
الآن، دعونا نحول الكود الزائف أعلاه إلى height
في بناء جملة جافا الصحيح!(سأستمر في حذف بعض القواعد النموذجية من أجل الإيجاز، مثل اتجاه الكائن ومعدلات إمكانية الوصول.) سأعرض حلين محتملين.
1.حل النوع العالمي:
الحل الأكثر وضوحًا هو القيام بذلك ببساطة height
عام عن طريق إدخال معلمة النوع α في توقيعه:
<α> int height(Tree<α> t)
{
return (t != null) ? 1 + max( height(t.left), height(t.right) )
: 0;
}
سيسمح لك هذا بالإعلان عن المتغيرات وإنشاء تعبيرات من النوع α داخل تلك الوظيفة، إذا أردت ذلك.لكن...
2.الحل النوعي الوجودي:
إذا نظرت إلى نص طريقتنا، ستلاحظ أننا لا نصل فعليًا أو نعمل مع أي شيء من هذا النوع α!لا توجد تعبيرات بهذا النوع، ولا أي متغيرات تم الإعلان عنها بهذا النوع...فلماذا يتعين علينا أن نجعل height
عام على الإطلاق؟لماذا لا يمكننا أن ننسى ببساطة α؟وكما تبين، يمكننا:
int height(Tree<?> t)
{
return (t != null) ? 1 + max( height(t.left), height(t.right) )
: 0;
}
كما كتبت في بداية هذه الإجابة، فإن الأنواع الوجودية والعالمية متكاملة/مزدوجة بطبيعتها.وهكذا، إذا كان الحل النوع العالمي هو القيام به height
أكثر عامة، فيجب أن نتوقع أن الأنواع الوجودية لها تأثير معاكس:أصنعه أقل عام، أي عن طريق إخفاء/إزالة معلمة النوع α.
ونتيجة لذلك، لم يعد بإمكانك الإشارة إلى نوع t.value
في هذه الطريقة ولا التعامل مع أي تعبيرات من هذا النوع، لأنه لم يتم ربط أي معرف به.(ال ?
حرف البدل هو رمز خاص، وليس معرفًا "يلتقط" نوعًا.) t.value
أصبحت مبهمة فعليا؛ربما يكون الشيء الوحيد الذي لا يزال بإمكانك فعله به هو كتابته عليه Object
.
ملخص:
===========================================================
| universally existentially
| quantified type quantified type
---------------------+-------------------------------------
calling method |
needs to know | yes no
the type argument |
---------------------+-------------------------------------
called method |
can use / refer to | yes no
the type argument |
=====================+=====================================
وهذه كلها أمثلة جيدة، ولكن اخترت أن الإجابة على هذا السؤال بشكل مختلف قليلا. أذكر من الرياضيات، التي ∀x. P (خ) تعني "لجميع المالكين ×، يمكنني إثبات أن P (خ)". وبعبارة أخرى، بل هو نوع من وظيفة، وكنت تعطيني x و لدي طريقة لاثبات ذلك بالنسبة لك.
في نظرية النمط، ونحن لا نتحدث عن البراهين، ولكن من الأنواع. حتى في هذا المجال فإننا نعني "لأي نوع X تعطيها لي، وأنا سوف أعطيك نوع P محددة". الآن، لأننا لا تعطي P الكثير من المعلومات حول X بالإضافة إلى حقيقة أنه هو نوع، P لا يمكن أن تفعل الكثير معها، ولكن هناك بعض الأمثلة. P يمكن أن تخلق نوع من "جميع أزواج من نفس النوع": P<X> = Pair<X, X> = (X, X)
. أو نستطيع خلق نوع الخيار: P<X> = Option<X> = X | Nil
، حيث النيل هو نوع من المؤشرات فارغة. يمكننا تقديم قائمة للخروج منه: List<X> = (X, List<X>) | Nil
. لاحظ أن آخر واحد هو العودية، قيم List<X>
إما أزواج حيث العنصر الأول هو X والعنصر الثاني هو List<X>
وإلا فمن مؤشر فارغة.
والآن، في الرياضيات ∃x. P (س) يعني "أنا يمكن أن تثبت أن هناك العاشر معينة بحيث P (خ) غير صحيح". قد يكون هناك العديد من مثل هذه العاشر، ولكن لاثبات ذلك، هو واحد يكفي. وهناك طريقة أخرى للتفكير في الأمر هو أنه يجب أن يكون موجودا هناك مجموعة غير فارغة من أزواج دليل وبرهان {(س، ف (خ))}.
وترجمت إلى كتابة نظرية: وهناك نوع في ∃X.P<X>
الأسرة هو نوع من X ونوع P<X>
المقابلة. لاحظ أنه في حين قبل أعطينا X إلى P، (بحيث كنا نعرف كل شيء عن X ولكن P القليل جدا) أن العكس هو الصحيح الآن. P<X>
لا نعد لإعطاء أي معلومات عن X، مجرد أن هناك وجود واحد، وهذا هو في الواقع نوع.
وكيف يكون هذا مفيدا؟ حسنا، يمكن أن يكون P النوع الذي لديه وسيلة لتعريض لها الداخلي نوع X. مثال سيكون كائن الذي يخفي التمثيل الداخلي X. حالته على الرغم من أن لدينا أي وسيلة لمعالجة مباشرة، يمكننا أن نلاحظ تأثير من قبل يمكن بدس في P. يكون هناك العديد من التطبيقات من هذا النوع، ولكن هل يمكن استخدام كل من هذه الأنواع بغض النظر عن أي تم اختيار واحد بعينه.
وهناك نوع الوجودي هو نوع مبهمة.
والتفكير في التعامل مع الملف في يونكس. أنت تعرف نوعه هو عدد صحيح، بحيث يمكنك بسهولة تزييفه. يمكنك، على سبيل المثال، في محاولة لقراءة من مقبض 43. اذا حدث ذلك حتى يتسنى للبرنامج لديه ملف مفتوح مع هذا المؤشر معين، سوف تقرأ منه. التعليمات البرمجية ليس من الضروري أن تكون ضارة، مجرد قذرة (على سبيل المثال، مقبض يمكن أن يكون متغير غير مهيأ).
ومخفيا وهو نوع جودي من البرنامج. إذا fopen
إرجاع نوع وجوديا، كل ما يمكن أن تفعله مع أنها لاستخدامه مع بعض وظائف المكتبة التي تقبل هذا النوع الوجودي. على سبيل المثال، فإن رمز الزائفة التالية تجميع:
let exfile = fopen("foo.txt"); // No type for exfile!
read(exfile, buf, size);
وأعلن واجهة "قراءة" ما يلي:
وهناك وجود نوع T مثل ما يلي:
size_t read(T exfile, char* buf, size_t size);
ووexfile متغير ليس عدد صحيح، وليس char*
، وليس بنية الملف لا شيء يمكنك التعبير في النظام النوع. لا يمكنك تعريف متغير له نوع غير معروف وأنت لا يمكن أن يلقي، ويقول، وهو مؤشر إلى أن نوع غير معروف. فإن اللغة لا تسمح لك.
للإجابة مباشرة على سؤالك:
مع النوع العالمي، استخدامات T
يجب أن تتضمن معلمة النوع X
.على سبيل المثال T<String>
أو T<Integer>
.بالنسبة لاستخدامات النوع الوجودي لـ T
لا تقم بتضمين معلمة النوع هذه لأنها غير معروفة أو غير ذات صلة - فقط استخدمها T
(أو في جافا T<?>
).
مزيد من المعلومات:
الأنواع العالمية/المجردة والأنواع الوجودية هي ازدواجية في المنظور بين المستهلك/العميل للكائن/الوظيفة والمنتج/تنفيذه.عندما يرى أحد الطرفين نوعًا عالميًا، يرى الآخر نوعًا وجوديًا.
في Java يمكنك تحديد فئة عامة:
public class MyClass<T> {
// T is existential in here
T whatever;
public MyClass(T w) { this.whatever = w; }
public static MyClass<?> secretMessage() { return new MyClass("bazzlebleeb"); }
}
// T is universal from out here
MyClass<String> mc1 = new MyClass("foo");
MyClass<Integer> mc2 = new MyClass(123);
MyClass<?> mc3 = MyClass.secretMessage();
- من وجهة نظر أ عميل ل
MyClass
,T
عالمي لأنه يمكنك استبدال أي نوع بهT
عند استخدام هذه الفئة ويجب أن تعرف النوع الفعلي لـ T عندما تستخدم مثيلاً لـMyClass
- من منظور أساليب المثال في
MyClass
بحد ذاتها،T
وجودي لأنه لا يعرف النوع الحقيقي منهT
- في جافا،
?
يمثل النوع الوجودي - وبالتالي عندما تكون داخل الفصل،T
هو في الأساس?
.إذا كنت ترغب في التعامل مع مثيلMyClass
معT
وجودية، يمكنك أن تعلنMyClass<?>
كما فيsecretMessage()
المثال أعلاه.
تُستخدم الأنواع الوجودية أحيانًا لإخفاء تفاصيل تنفيذ شيء ما، كما تمت مناقشته في مكان آخر.قد تبدو نسخة Java من هذا كما يلي:
public class ToDraw<T> {
T obj;
Function<Pair<T,Graphics>, Void> draw;
ToDraw(T obj, Function<Pair<T,Graphics>, Void>
static void draw(ToDraw<?> d, Graphics g) { d.draw.apply(new Pair(d.obj, g)); }
}
// Now you can put these in a list and draw them like so:
List<ToDraw<?>> drawList = ... ;
for(td in drawList) ToDraw.draw(td);
من الصعب بعض الشيء التقاط هذا بشكل صحيح لأنني أتظاهر بأنني أتحدث في نوع ما من لغات البرمجة الوظيفية، وهو ما لا تفعله Java.لكن النقطة هنا هي أنك تلتقط نوعًا ما من الحالة بالإضافة إلى قائمة من الوظائف التي تعمل على تلك الحالة ولا تعرف النوع الحقيقي لجزء الحالة، لكن الوظائف تعرف ذلك نظرًا لأنها كانت متطابقة مع هذا النوع بالفعل .
الآن، في Java، جميع الأنواع غير النهائية غير البدائية وجودية جزئيًا.قد يبدو هذا غريبا، ولكن لأنه تم الإعلان عن متغير كـ Object
من المحتمل أن تكون فئة فرعية من Object
بدلاً من ذلك، لا يمكنك الإعلان عن النوع المحدد، فقط "هذا النوع أو فئة فرعية".وهكذا، يتم تمثيل الكائنات كجزء من الحالة بالإضافة إلى قائمة من الوظائف التي تعمل على تلك الحالة - يتم تحديد الوظيفة التي سيتم استدعاؤها بالضبط في وقت التشغيل عن طريق البحث.هذا يشبه إلى حد كبير استخدام الأنواع الوجودية المذكورة أعلاه حيث يكون لديك جزء من الحالة الوجودية ووظيفة تعمل على تلك الحالة.
في لغات البرمجة المكتوبة بشكل ثابت دون الكتابة الفرعية والإرسال، تسمح الأنواع الوجودية للشخص بإدارة قوائم الكائنات المكتوبة بشكل مختلف.قائمة T<Int>
لا يمكن أن تحتوي على أ T<Long>
.ومع ذلك، قائمة T<?>
يمكن أن تحتوي على أي اختلاف T
, ، مما يسمح للشخص بوضع العديد من أنواع البيانات المختلفة في القائمة وتحويلها جميعًا إلى int (أو القيام بأي عمليات يتم توفيرها داخل بنية البيانات) عند الطلب.
يمكن للمرء دائمًا تحويل سجل من النوع الوجودي إلى سجل دون استخدام عمليات الإغلاق.تتم كتابة الإغلاق بشكل وجودي أيضًا، حيث تكون المتغيرات الحرة التي تم إغلاقه مخفية عن المتصل.وبالتالي فإن اللغة التي تدعم عمليات الإغلاق ولكن ليس الأنواع الوجودية يمكن أن تسمح لك بإجراء عمليات إغلاق تشترك في نفس الحالة المخفية التي كنت ستضعها في الجزء الوجودي من الكائن.
يبدو أنني أتيت متأخرًا بعض الشيء، ولكن على أي حال، تضيف هذه الوثيقة وجهة نظر أخرى حول ماهية الأنواع الوجودية، على الرغم من أنها ليست ملحدة للغة على وجه التحديد، إلا أنه يجب أن يكون من الأسهل فهم الأنواع الوجودية إلى حد ما: http://www.cs.uu.nl/groups/ST/Projects/ehc/ehc-book.pdf (الفصل 8)
يمكن وصف الفرق بين النوع الكمي العالمي والنوع الوجودي بالملاحظة التالية:
استخدام قيمة مع نوع ∀ يحدد النوع الذي سيتم اختياره لإنشاء مثيل لمتغير النوع الكمي.على سبيل المثال، المتصل بوظيفة الهوية "id::∀a.a → a" يحدد النوع الذي سيتم اختياره لمتغير النوع a لهذا التطبيق المحدد للمعرف.بالنسبة لتطبيق الوظيفة "id 3"، فإن هذا النوع يساوي Int.
إنشاء قيمة بالنوع الكمي ∃ يحدد ويخفي نوع متغير النوع الكمي.على سبيل المثال، قد يكون منشئ "∃a.(a, a → Int)" قد قام ببناء قيمة من هذا النوع من "(3, lectx → x)"؛قام منشئ آخر بإنشاء قيمة بنفس النوع من "('x', lectx → ord x)".من وجهة نظر المستخدمين، كلتا القيمتين لهما نفس النوع وبالتالي يمكن استبدالهما.تحتوي القيمة على نوع محدد تم اختياره لمتغير النوع a، لكننا لا نعرف أي نوع، لذلك لم يعد من الممكن استغلال هذه المعلومات.تم "نسيان" معلومات نوع القيمة المحددة هذه؛نحن نعرف فقط أنه موجود.
يوجد نوع عالمي لجميع قيم معلمة (معلمات) النوع.يوجد النوع الوجودي فقط لقيم معلمة (معلمات) النوع التي تلبي قيود النوع الوجودي.
على سبيل المثال، في Scala، إحدى طرق التعبير عن النوع الوجودي هي النوع المجرد الذي يقتصر على بعض الحدود العليا أو السفلية.
trait Existential {
type Parameter <: Interface
}
على نحو مكافئ، النوع العالمي المقيد هو نوع وجودي كما في المثال التالي.
trait Existential[Parameter <: Interface]
يمكن لأي موقع استخدام توظيف Interface
لأن أي أنواع فرعية قابلة للإنشاء من Existential
يجب أن تحدد type Parameter
والتي يجب أن تنفذ Interface
.
أ حالة منحلة النوع الوجودي في Scala هو نوع مجرد لا تتم الإشارة إليه مطلقًا وبالتالي لا يلزم تعريفه بواسطة أي نوع فرعي.يحتوي هذا بشكل فعال على تدوين مختصر لـ List[_]
في سكالا و List<?>
في جافا.
إجابتي مستوحاة من مارتن أوديرسكي اقتراح للتوحيد أنواع مجردة ووجودية.ال الشريحة المصاحبة يساعد على الفهم.
والبحث في أنواع البيانات المجردة والمعلومات يختبئ جلب أنواع الوجودية إلى لغات البرمجة. جعل مجردة نوع البيانات يخفي المعلومات حول هذا النوع، لذلك العميل من هذا النوع لا يمكن الاعتداء عليه. يقول كنت قد حصلت على إشارة إلى كائن ... بعض اللغات تسمح لك أن يلقي إشارة إلى إشارة إلى بايت وفعل أي شيء تريد أن قطعة من الذاكرة. لأغراض ضمان سلوك البرنامج، فإنه من المفيد للغة لفرض التي كنت تعمل فقط على الإشارة إلى كائن عبر الطرق المصمم الكائن يقدمها. كنت تعرف نوع موجود، ولكن لا شيء أكثر من ذلك.
<اقتباس فقرة>وانظر:
وأنواع مجردة لديك الوجودي نوع، ميتشل وبلوتكين
http://theory.stanford.edu/~jcm /papers/mitch-plotkin-88.pdf
اقتباس فقرة>وكما فهمت انها وسيلة الرياضيات لوصف واجهات / فئة مجردة.
وأما بالنسبة T = ∃X {X ل. الباحث و (X)؛ }
لC # فإنه يترجم إلى نوع مجردة عام:
abstract class MyType<T>{
private T a;
public abstract int f(T x);
}
و"الوجودية" يعني فقط أن هناك بعض الأنواع التي تطيع للقواعد المحددة هنا.