The Artima Developer Community
Sponsored Link

Weblogs Forum
What is the type of 42?

6 replies on 1 page. Most recent reply: Oct 30, 2006 11:00 PM by Cleo Saulnier

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 6 replies on 1 page
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

What is the type of 42? (View in Weblogs)
Posted: Oct 25, 2006 3:08 PM
Reply to this message Reply
Summary
In Joy any number is an executable program, which pushes the the number on to the stack. This begs the question: what is the type of 42? In Cat I created two separate types, but now I am rethinking that choice.
Advertisement
When I was designing Cat I started with the assumption that the type of a number such as 42, must be a function which pushes a primitive integer type onto the stack. So the type of 42 would be:
42 : ()->(int)
The type of a function which yielded 42 would be:
[42] : ()->(()->(int))
In Joy the operation for evaluating functions is "i". The equivalent in Cat is "eval". The type of eval in Cat currently is:
eval : (A (A:any*)->(B:any*))->(B)
This meant that the following was badly typed in Cat:
42 eval
This is because eval expected a function on the top of the stack, but 42 produced a primitive on the top of the stack. You would have to instead write:
[42] eval

The decision for this type design was based on two things:

  1. That kind of type system was more familiar to me
  2. The programs more closely mapped to assembly language as-is
In assembly an operation which yields 42 and the value 42 are very different things. My thought was that I wanted to be able to trivially map Cat functions to assembly code. My concern is that the execution loop of an assembly program where values were executable would be non-trivial. I assumed you would need a switch statement and this would signficiantly hurt performance (Cat is striving to become a full competitor with real assembly code, so performance is a big concern). I am no longer convinced that this would actually be a problem.

The first issue is writing the type of numbers. It appears that what is needed is the ability to name new types and express them recursively:

42 : int;
int = ()->(int);
The next challenge is converting to assembly code. I haven't worked out all of the details, but I believe that when generating assembly, I need to simply insert type conversion routines at key places (i.e. where an integer is being executed, or treated like a function).

Do all this seem sane and rational?


Cleo Saulnier

Posts: 77
Nickname: vorlath
Registered: Dec, 2005

Re: What is the type of 42? Posted: Oct 26, 2006 3:38 PM
Reply to this message Reply
This is the age old breaking the recursion problem. You must decide what you want to use as a primitive type. Something that can't be broken down anymore. SmallTalk uses built-in objects for their numbers. C/C++,Pascal,Lisp uses primitive types (or literals).

There are two forces at work here. In C++ for example, there are two type systems. One for functions and one for classes. What you're doing is trying to combine both execution types and data types together. It's logical that you would encounter this problem (if I understand everything correctly).

In C++, class A and class B are two different types even though their composition may be the same. Yet they are both classes (in Java this would be Class).

But functions in C++ aren't like that. Two functions have the same type if their prototypes match. The name of the prototype, if any, doesn't come into the equation. It is composition based while classes are name based.

So my question to you is do you use duck typing as in C++ functions? Or do you use static typing as in C++ classes?

There's a solution to both scenarios, even when merged. From past comments, I will assume you are using duck typing. That a function that has type (int)->(int) is the same type as another function (int)->(int) regardless if you name these types differently. Their values, the functions in question, are different, but their types are the same.

If you only had ONE kind of primitive type 'int' (without float's for example), none of this is a problem. But we must first resolve what is the definition of this primitive type. You seem to have built your system on the concept that "everything is a function". If 42 is a function, then is an int the function itself or the "thing" it returns? If you allow both definitions, I have a feeling you will regret it. I could not come to terms with this in my own system and had to ditch the idea completely.

I'll tell you what I did and you can decide for yourself. In my system, I have somewhat of a "everything is a component" system. My system has no concept of functions (good riddance), but components can take input and produces output values (they all "execute" in parallel though). My problem became about how to define a value. Naturally, we think that a component should return or produce this value. As I said, this did not work for me. I threw that idea out.

I decided that the component *itself* was the value. It takes no input and produces no output, yet the internals contains a value, namely 42 as per your example. This internal 42 has no type, no value and only exists for the compiler's sake. In your case, the function called 42 would take no input and produce no output, yet would still be a function and 'contain' 42 in some manner.

define 42 {}
42: ()->()
int: ()->()

So 42 is both a function and an int which simply resolve to ()->(). So you can say that 42 is a different instance than 5, yet both are of the same type ()->(). We can also rest assured that no normal function will accept nothing and return nothing as that would be pointless if it has no side-effects. This means we can easily tell the difference between primitive types and normal functions. I consider this an important feature. ()->(int) isn't obvious at all.

But what if we have multiple primitive types? If you don't support duck typing and you have a system where types remember their names, it's automatic. This is the class A is different than class B scenario.

But if you have duck typing like functions in C++ where two different functions having the same prototype are of the same type, then you must qualify ()->(). One example could be this.

int: ()->()#int
float: ()->()#float

They are both empty functions, but have different qualifiers which makes them different. You're trying to use the return value as the qualifier with ()->(int) and end up with recursion. I personally don't see that as a viable solution.

These qualifiers can be ditched at compile time if no longer needed at runtime so that only the raw values and code remains. The cool thing about qualifiers is that you can insert new primitive types at any time and while old compilers won't be able to generate code for those types, they will still be able to check if the program is "correct" typewise.

The qualifier can also be used for normal functions if you so choose. If you want a function to only operate on function x as input, then you have a way to specify that by defining the type of function x with a qualifier. You'll have to worry about collisions, but that's another discussion. So duck typing would have no qualifiers, whereas static typing would.

My system is much more elaborate, but I hope I'm in the ballpark of what you're talking about. Sorry for being so verbose.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: What is the type of 42? Posted: Oct 26, 2006 6:43 PM
Reply to this message Reply
> So my question to you is do you use duck typing as in C++
> functions? Or do you use static typing as in C++
> classes?

I am hesitant to use the term duck type, but yes Cat function types are matched based on their signatures ... as opposed to their names or implementation.

> They are both empty functions, but have different
> qualifiers which makes them different. You're trying to
> use the return value as the qualifier with ()->(int) and
> end up with recursion. I personally don't see that as a
> viable solution.

The recursion is intentional along with the qualifier.

I am trying to express the fact that integers can be evaluated like functions, so declaring them to be empty functions would not be completely accurate.

What my proposal implies is that


42 == eval(42) == eval(eval(42)) == ...


In other words all primitives are recursive functions (e.g. they yield themselves).

However as you point out the labeling of these types is improtant. So I have to introduce the notion of tagged recursive types.


A = ()->()
B = ()->()


A is not compatible with with B. But both are compatible with eval:


eval : (X (X:any* Y:any*))->(Y)
eval(A)
eval(B)


I should point out that this dicsussion about the type of primitives is moot for the upcoming version 1.0 of Cat (unless I somehow double the number hours in a day).

> My system is much more elaborate, but I hope I'm in the
> ballpark of what you're talking about. Sorry for being so
> verbose.

I always appreciate your ideas and enthusiastic participation in blog discussions.

Tim LS

Posts: 37
Nickname: parchandri
Registered: Jul, 2005

Re: What is the type of 42? Posted: Oct 26, 2006 10:42 PM
Reply to this message Reply
42 : int;
int = ()->(int);

This blew my mind the first time I read through it, but then it started to make sense. And then I think I thought of a problem.

As the cat language evaluates 42, it puts 42 on the stack.

()->(int).

if you write a program like

42 eval

the result is the same as

42

so the type of a number is a hack to make it unaffected by evaluation - it evaluates to itself. As the expression 42 in C or lisp just gives you 42 back.
A primitive is just something that is unaffected by evaluation.
I think the recursive type definition can be used to define primitivity, but not 'int-ness'. What defines intness is not primitivity, it is the capabilities or morphisms of integers. Think of groups, rings, fields, set theory definitions of an int here.

Cleo Saulnier

Posts: 77
Nickname: vorlath
Registered: Dec, 2005

Re: What is the type of 42? Posted: Oct 27, 2006 8:33 AM
Reply to this message Reply
> The recursion is intentional along with the qualifier.

I've looked at it again and because there are no side-effects, a function that returns 42 may as well be the value 42. I guess I was stuck on imperative languages, so I offered the empty function as an alternative to differentiate an int and a function that produces an int. I see now there's no point.

BTW, what exactly is the purpose of having an int evaluate to itself? Have you thought how the public will receive this concept?

Also, what's wrong with a simple type system where 'int' stays as is (non-function)? If it's found in the source, then the compiler can inject a built in function that pushes the value on the stack. eval would no longer work on it though. I don't see that as a problem anyhow. 42 evaluates on its own. {[42] eval} would work though. This seems cleaner to me, but this is probably because it's what is commonly done.

> I always appreciate your ideas and enthusiastic
> participation in blog discussions.

Thanks! BTW, you ever find the more technical weblogs get the least responses?

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: What is the type of 42? Posted: Oct 27, 2006 11:51 PM
Reply to this message Reply
> BTW, what exactly is the purpose of having an int evaluate
> to itself?

I'll be honest, you are convincing me that there is no great appeal to it. :-)

Which means I was unable to come up with a good answer.

> I always appreciate your ideas and enthusiastic
> > participation in blog discussions.
>
> Thanks! BTW, you ever find the more technical weblogs get
> the least responses?

Yeah, I've noticed that but I can't really expect people to get as excited as me about esoteric type systems in unknown languages ;-)

If you are interested though there has been a bit more discussion at http://tech.groups.yahoo.com/group/concatenative/

Cleo Saulnier

Posts: 77
Nickname: vorlath
Registered: Dec, 2005

Re: What is the type of 42? Posted: Oct 30, 2006 11:00 PM
Reply to this message Reply
My intention wasn't to discourage. I was just wondering the reasoning behind this direction.

I read the yahoo group discussion topic by the same name and found this particularly curious:

"However i still find myself asking is there any substantial reason not to have ints as being self referential types which can be used whereever a function is required?"

How about implicit conversions depending on context?

copy: (A:any)->(A)

42 eval
means
42 [copy] eval

42 eval eval
means
42 [copy] eval [copy] eval

Say:
func: (A:int (B:any*)->(C:any*))->(C)

42 dup func
means
42 dup [copy] func

I'm not sure how you'd convert it if it was deeper on the stack. But [copy] would need to be inserted for each input of a function that needs it separatly.

For example, doing this would be wrong:
converting from:
42 eval
to
[42] eval

This is because
42 dup eval +
would incorrectly duplicate functions [42] when what you want is the top of stack to be a function and the next value a plain int. The input of eval needs to have [copy] inserted while the input of + is fine as is.

42 dup [copy] eval +
is correct.

You can then use the same technique for all primitive types such as bool and whatnot. So primitive types are subject to implicit conversions to functions if necessary. Unfortunately, I don't know if there's a problem where you don't know ahead of time if it's a function or a primitive type (where it can be either one). Only the primitive types would need conversions.

Not sure if that idea is useful to you, but I thought I'd throw it out there because it removes the need for recursion and seems to do what you want. However, I fear that you're looking for something that can be concisely stated in a formal definition where you need only look at the definition to see where primitive types fit in.

"I find myself comparing Cat code to Joy code, and
being jealous of the more powerful expressiveness of Joy."

I'm not familiar with Joy, but maybe it would help if you pinpointed what the "expressiveness" is.

Flat View: This topic has 6 replies on 1 page
Topic: What is the type of 42? Previous Topic   Next Topic Topic: Management Lessons


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us