Lists

In statically typed functional languages, the type of lists is typically recursively defined to consist of the empty list, or of some value (the head of the list) consed to another list (the tail of the list).

So, if we write “::” for the consing operator, and “[]” for the empty list, then for example 4::[] is the list consisting of only one element, which is 4. Similarly, we can have a list 1::2::3::4::[], which consists of 4 elements.

Something like 1::2 is not a valid list in statically typed languages, because 2 is not a list. So rather than write 1::2, you have to write 1::2::[].

To just blindly mimic this behavior of lists in Babel-17 causes problems. In Babel-17, two issues combine to make conventional lists problematic:

  1. We can have lazy and concurrent lists, for example 1::lazy(2::[]) or 1::concurrent(2::[]).
  2. An expression should always have one deterministic value.

Now look at the following code:

val x = 1::lazy(2)
x.head

Which value has “x” ? And which value is returned by above block? If we mimic how lists usually behave, then the evaluation of 1::lazy(2) should lead to a dynamic exception, because 1::2 is not a proper list. This means that the above block also evaluates to a dynamic exception. But in order to determine that 1::lazy 2 is not a proper list, we need to defy the purpose of the lazy attribute! This is not problematic if the argument of lazy is just 2. But if the argument of lazy is some complicated expression that takes a minute to evaluate, then it becomes problematic.

Therefore, in Babel-17, we need to allow that 1::2 is a valid list. Then the above block simply evaluates to 1.

To make this work smoothly, we furthermore identify 1::2 and 1::2::[]. Therefore, the value of

(1::2).tail

is not 2, but 2::[].

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: