Skip to content

Commit

Permalink
more semantic analysis, refactor readme
Browse files Browse the repository at this point in the history
  • Loading branch information
@hoosierEE
hoosierEE committed Jul 29, 2024
1 parent 4a053ae commit f5abc57
Show file tree
Hide file tree
Showing 2 changed files with 59 additions and 63 deletions.
99 changes: 49 additions & 50 deletions README.org
View file
Original file line number Diff line number Diff line change
Expand Up @@ -6,18 +6,16 @@
- how: first build a Python prototype, then implement in CUDA/C++ (or perhaps [[https://ziglang.org/download/0.11.0/release-notes.html#GPGPU][Zig]] or [[https://pkg.odin-lang.org/vendor/OpenGL/][Odin]]?)
- maybe one day: a fast DSL for data-intensive kernels embedded in a distributed system environment like [[https://gleam.run/][Gleam]]

keywords: "array-oriented" "interpreted" "functional" "automatic memory management"
PL jargon: =array-oriented= =interpreted= =functional= =automatic memory management= =eager=

** types
- builtin types - int, float, string, symbol
- built-in types - float, integer, string, symbol
- special values - =0w= (infinity), =0n= (null float), =0N= (null integer)
- compound types
- list-like
- tensor - same type, N dimensional
- vector - same type, 1 dimensional (simplest tensor)
- list - any types, any shape
- dict-like
- table - keys (column names) are symbols, values are same-shape vectors
- dict - keys are any fundamental type, values are arbitrary
- dict - list of key-value pairs; keys must be symbols, values can be any type
- list-like
- vector - 1-dimensional contiguous storage for values of one type e.g: "vector of integers"
- list - 1-dimensional storage for any types

** k crash course
K is a vector language descended from APL, with hints of lisp.
Expand Down Expand Up @@ -119,44 +117,45 @@ CPU=1 cd element && make

* Development Roadmap
This project is in the *experimental*, pre-alpha stage.
Some [[https://github.com/doctest/doctest/tree/master/doc/markdown#reference][doctest]] tests exist, but no coverage goals yet.

[0/3]
- [-] prototype implementation
- [X] lex/scan/tokenize
- [X] parse
- [-] semantic analysis
- [ ] rank polymorphic verbs
- [ ] iterators
- [ ] type checking
- [-] type inference
- [X] primitive types (int|float|string|symbol)
- [X] vec
- [X] list
- [ ] expression
- [ ] lambda
- [ ] tensor
- [ ] dict
- [ ] table
- [X] name binding
- [X] function application
- [X] variable names and lexical scope
- [X] composition/projection =(2+)1=
- [X] projection ⇒ lambda
- [ ] composition ⇒ lambda
- [ ] errors (mutable, rank, unused, ...)
- [-] code generation
- [ ] tree-walk interpreter
- [X] simple arithmetic =1+2=
- [X] array arithmetic =1 2+3 4=
- [ ] iterators =+/1 2 3=
- [ ] structural functions =4 3#!5=
- [ ] hardware accelerated implementation
- [ ] full test suite compatibility with prototype
- [ ] benchmarks showing it is faster
- [ ] stable release(s)
- [ ] pick a version numbering system (and stick to it)
- [ ] formal grammar
- [ ] standard library
- [ ] package management
- [ ] documentation, playground, tutorials
Some [[https://github.com/doctest/doctest/tree/master/doc/markdown#reference][doctest]] tests [[https://github.com/hoosierEE/element/blob/main/src/main.cc#L119][exist]], but no coverage goals yet.
Some [[https://github.com/hoosierEE/element/blob/main/prototype/Test.py][unit tests]] exist in the prototype folder.

** prototype implementation [2/4]
- [X] lex/scan/tokenize
- [X] parse
- [-] semantic analysis [3/12]
- [ ] rank polymorphic verbs
- [ ] iterators
- [ ] type checking
- [-] type inference
- [X] primitive types (int|float|string|symbol)
- [X] vec
- [ ] list
- [ ] expression
- [ ] lambda
- [ ] dict
- [ ] name binding
- [ ] function application
- [ ] variable names and lexical scope
- [X] composition/projection =(2+)1=
- [X] projection ⇒ lambda
- [X] composition ⇒ lambda
- [ ] partial application reduction ={x+y}[0;]= ⇒ ={0+x}=
- [ ] errors (mutable, rank, unused, ...)
- [ ] code generation [0/5]
- [ ] tree-walk interpreter
- [ ] simple arithmetic =1+2=
- [ ] array arithmetic =1 2+3 4=
- [ ] iterators =+/1 2 3=
- [ ] structural functions =4 3#!5=

** hardware accelerated implementation [0/2]
- [ ] full test suite compatibility with prototype
- [ ] benchmarks showing it is faster

** stable release(s) [0/5]
- [ ] pick a version numbering system (and stick to it)
- [ ] formal grammar
- [ ] standard library
- [ ] package management
- [ ] documentation, playground, tutorials
23 changes: 10 additions & 13 deletions prototype/Semantic.py
View file
Original file line number Diff line number Diff line change
Expand Up @@ -26,15 +26,15 @@ def __repr__(s):

def vectype(xs:list[Ast]) -> type:
types = {ty(x.node) for x in xs}
return float if int in types and float in types else types.pop()
return float if (int in types and float in types) else types.pop()

def infer(a:Ast) -> Val:
'''infer types from literal expressions'''
match (a.node,a.children):
case ('vec',b): return Val(a,vectype(b))
case ('{',p,b): return Ast(a.node,*map(infer,a.children))
case ('[',()): return Val(a.node,'NIL')
case (node,()): return Val(node,ty(node[0]))
case ('{',_): return Ast(a.node,*map(infer,a.children))
case ('[',()): return Val(a.node,Nil)
case (node,()): return Val(node,ty(node))
case (node,children): return Ast(a.node,*map(infer,children))
case _: raise SyntaxError(f'unmatched: {a}')

Expand All @@ -46,15 +46,13 @@ def lamp(a:Ast) -> Ast:
if (v:=a.children[0].node)[0] in VERB and v.endswith(':'):
return Ast('{',Ast('[',ax), Ast(v,ax))
return Ast('{',Ast('[',ax,ay), Ast(v,ax,ay))
case 'prj',2:
return Ast('{',Ast('[',ax), Ast(a.children[0].node,lamp(a.children[1]),ax))
case _:
return Ast(a.node, *map(lamp,a.children))
case 'prj',2: return Ast('{',Ast('[',ax), Ast(a.children[0].node,lamp(a.children[1]),ax))
case _: return Ast(a.node, *map(lamp,a.children))

def lamc(a:Ast) -> Ast:
'''merge compositions into inner lambda'''
match a.node:
case 'cmp': # 2 children
case 'cmp': # exactly 2 children
match a.children[0].node, a.children[1].node:
case '{','{':
b1 = a.children[0].children[1]
Expand All @@ -64,9 +62,8 @@ def lamc(a:Ast) -> Ast:
args,b2 = a.children[1].children
return Ast('{',args,Ast(a.children[0].node,b2))
case '{',b: return lamc(Ast('cmp',a.children[0],(lamc(a.children[1]))))
case b,c: return lamc(Ast('cmp',lamc(a.children[0]),lamc(a.children[1])))
case _:
return Ast(a.node, *map(lamc,a.children))
case b,c: return lamc(Ast('cmp',*map(lamc,a.children))) #lamc(a.children[0]),lamc(a.children[1])))
case _: return Ast(a.node,*map(lamc,a.children))

def get_params(a:Ast) -> str:
'''get x y z arguments from lambdas'''
Expand All @@ -85,4 +82,4 @@ def formalize(a:Ast) -> Ast:

def Sema(a:Ast) -> Ast|Val:
'''semantic analysis wrapper'''
return infer(formalize(lamc(lamp(a))))
return (formalize(lamc(lamp(a))))

0 comments on commit f5abc57

Please sign in to comment.