Skip navigation.

Notes to self

Whatever I feel like writing

Posts tagged with "language"

Monads in Pythton

Wednesday, 9. January 2008, 18:46:20

, ,

This is noteworthy: Peter Thatcher has implemented Monads in pure Python and gives examples of how to use them here: http://www.valuedlessons.com/2008/01/monads-in-python-with-nice-syntax.html

I don't quite get what's going in on in his code - needs more thorough reading, but it sure looks interresting.

No comments

Perfect Type System

Thursday, 18. October 2007, 17:55:01

, , ,

Whenever you venture into the realm of language design, you will eventually touch on type systems. Type systems are an inherent part of any language, and many languages are famous specifically for their type systems - Haskell and Ruby comes to mind.

Boiled down, this means that if you design a language, you will also find yourself designing a type system.

This brings me to an old quote:

A design is perfect not when there is nothing more to add,
but when there is nothing more to take away.



How does this relate to type systems? A perfect type system by this definition would be more than minimal - almost non-existent.

Take assembler: Everything is bits and bytes, and bytes can be grouped in words who's size depend on the target processor architecture.

This might be minimal but it is hardly practical; the whole purpose of a programming language is to provide abstractions, and that can't really be said about assembler.

Assembler has primitives, numbers of varying bit-width, but in order to provider higher levels of abstractions, another meta-type is needed; aggregates - a collection or grouping of primitives. Without both aggregates and primitives, then it'll be pretty hard to define a practical and proper high-level language.

Now, the challenge is to find the minimum set of members for these two meta-types. First up is primitives, and I propose that we can do with just a single member and some syntactic sugar.

Consider how the notion of a number can be the only primitive in a language; characters are really just a special case of numbers, and integrals and reals can be unified into a single type. This could be simulated with cohesion as it is in many languages, or by not considering integrals and reals to be two separate types
at all.

With a sufficiently high-level language, we can also unify finite precision and infinite precision numbers into a single type. The Strongtalk implementation of the Smalltalk language is able to automatically detect overflow in finite precision numeric types, and convert them on the fly to their infinite
counterparts.

If we're willing to defer performance considerations to an implementation detail, we could simplify things even further by making all numbers infinite precision decimals. Characters would be nothing more than a unicode ordinal and a bit of syntactic sugar.

This way, we'd end up with a single primitive type: the Number.

So what of the aggregates? How many members of this meta-type are required for a proper type system? Once again, I propose that the answer is just one; the Function.

Let's contemplate that idea a little, and see how it will compare to the type system of an existing functional language, such as Haskell.

In Haskell, I would count functions, lists, tuples and `data` types to be among the aggregates. The challenge for my alleged functions-as-only-aggregate is now to figure out how to represent each of these meta-types as functions.

Functions themselves are a no-brainer in this regard to let us jump straight to lists: A list is an ordered sequence of values, these values are most often iterated and re-arranged when worked with on programs. For the purpose of iteration, and special kind of functions exists in the Python languages that are called generators - they are functions that can return multiple times during a single invocation, a poor mans continuation, if you will.

So using continuations, it becomes quite easy to create ordered sequences of values - every time you need the next value in an iteration, you just 'continue' to the next return value of the continuation. Then add some syntactic sugar so the complexity of continuations doesn't bleed into code where it is not needed, and we have a very powerful list representation.

If we make our type system dynamic (non-static, to be precise), then tuples would be in the same exact ballpark as lists. I don't think we even need to distinguish between tuples and lists at all, if our type system is dynamic, and I'm not sure it's needed in a static type system either - Java, for instance, seems to be doing just fine without tuples.

Lists was arguable the most important meta-type to get straight, but object or struct-like types, types with named attributes or parts, are extremely useful as well - many languages allow for some interesting magic by facilitating introspection of the names and values of parts of these types.

Let's return to the generators in Python. These functions are able to stop in the middle of their execution to return values. Then they wait to resume execution when the next value is requested - their complete state is preserved while they wait, and they resume execution from the exact point they left off.

Now, Python is a procedural (and object-oriented) language and as such has the ability to assign values to variables. Then imagine a continuation that is waiting to be resumed, and that we were able to access the variables inside the scope of the continuation.

This solution is arguably less elegant than the list solution, and also raises a number of questions; specifically, in a functional language, functions tend to not really have any state at all, much less a state where the values have names.

Functional languages like Lisp and Haskell are declarative. This makes stateful functions obtuse and very hard, if not impossible, to create. Haskell have monads for representing state, but they are not quite the same thing as a function, and as such would be a separate member of the aggregate meta-type, distinct from the functions.

We could instead allow for assigning aliases to the expressions that make up a function, and the values that these expressions generate would be accessible through these aliases when the continuation halts.

This still wouldn't be entirely elegant, and there's also the question of what happens when the continuation is continued - I don't see an obviously correct answer to this question, so a language would be forced to define a convention in this regard, and such a convention will certainly surprise and bite a few people, as it is destined to be misunderstood or assumed to have a different behavior.

Regardless, I think it is doable, albeit it isn't pretty. So a language would probably have to take that fact into account, and either provide some heavy syntactic sugar to make this bearable to work with, or be designed in such a way that you will need these kinds of types less, or both.

At the bottom of it all, I think it is possible to design a programming language around a minimalist type system like this. It would probably be the kind of languages that are easy to learn but difficult to master - a very, interesting, language to be sure.

Would such a type system be perfect? I'm not sure, 'perfect' is tainted with subjectivism, but I do think that it would be rather elegant if we disregard the way that we implemented struct-like types - I suppose you can't make a language without compromise.

1 comment

Official: Haskell is the Best Language

Saturday, 18. August 2007, 11:50:05

, , ,

When having few lines of code is more important than runtime and memory performance, and when the rage is all about binary trees, nsieve-bits, charmeneos, recursion and regex-dna, then Haskell is the language for you.

The proof is right here in the computer language shootout - completely objective, and undestorted linguistic statistics!

1 comment

Rise of functional (article)

Wednesday, 18. July 2007, 06:17:14

, , ,

I came upon this article by Pat Eyler of Linux Journal:
http://www.linuxjournal.com/node/1000217/print

A nice little read that suggests that my prediction about Haskell getting a come back ain't entirely off, rather, this guy is seeing pretty much the same patterns - he only did it before I did, plus he's putting his money on Erlang whereas I have a gut feeling about Haskell.

And while I'm at it, here's a bonus link to an article that goes beyond static/dynamic and strong/loose in discussing how to discuss types: http://cdsmith.twu.net/types.html

2 comments

A programmin language is (at some point in the future) born.

Sunday, 15. July 2007, 10:55:46

, , , ...

Like the evil genious that I am, *cough-cough*, I'm conducting secret experiments in programming language design in my spare time.

It's not like I know what I'm doing; by no means do I have any formal qualifications in language design - pretty much I'm just having fun.

Anyway, I've spend a lot of time pondering how the syntax should look like and what kind of language it should be, but since I've barely started on the parser (the lexer is quite far, on the other hand), I think it'd be way premature to go into those details - let it just be told that brevity and conciceness are key.

Instead, let me tease you with some code snips that shows off some syntax and functionality that I'de like to make possible (did I mention that I've barely started on the parser?).

First, given a list of objects who has a description method returning a string, how do we concatenate all the non-empty descriptions with newlines in between?
mylist[@x:x.description()][!=''].join('\n')
Of couse there are languages that can do this in less code, but somehow I don't feel like taking on the beast that is APL :wink:

From left to right, we first have the "mylist" identifier that refers to our source list of objects.

Then comes a map expression that, for each element 'x' in 'mylist', injects the value of 'x.description()' into a new list. Map expressions are destinguished by the AT sign and should contain an expression that will evaluate to a function object - in this instance, a function literal.

Next up is the funky fella that is a filter expression. They are basically an operator followed by some expression, contained in square brackets. Each element in a source list is placed in front of the operator and the completed expression is evaluated, and if it amounts to boolean True, then the element in question is injected into a new list. Filter expressions are somewhat limited in that they are required to contain that leading operator - for those needing more power than that, the good ol' trusty filter() function exists.

Finally we have a list of interesting descriptions and we call the join() method on that list. This will cause the list to concatenate the string version of its elements into one big string, where each element is seperated by the string that is parsed to the join() method as an argument.

All in all, pretty simple.

The second example I want to show you is the infinite fibonacci sequence, but before we jump to the beef, let's just recap what such a thing looks like in, say, Python:
def fib():
    x,y=0,1
    yield x; yield y
    while True: x,y = y,x+y; yield y
Four lines and a generator function later, the fib is ready for prime time.

Wait, four lines? Surely Haskell can do that better!
fib :: [Int]
fib = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]
Down to two lines, not bad! I can't even begin to imagine what this would look like in Java.

Alright, I've held it off long enough, let's see how it looks like in my mysterious language X (I have yet to come up with a good name for it - suggestions are welcome):
fib = [0,1,[-2:].sum..]
I think I'm just gonna let that code speak for itself... :wink: (because too many things are going on under the hood and, as I said, I don't want to go into details just yet)

1 comment